PaperlayerView exact revision on arXiv

Source-linked AI summary

Radio Map Based 3D Path Planning for Cellular-Connected UAV

Shuowen Zhang, Rui Zhang

arXiv:1912.00021v2cs.ITeess.SPeess.SY

TL;DR

Cellular-connected UAVs need 3D paths that minimize flight distance while meeting SINR targets despite spatially varying interference. This paper uses 3D channel and SINR radio maps with shortest-path optimization and quantization, achieving improved communication and flight efficiency with adjustable complexity.

  • Problem

    Existing UAV path-planning studies mainly use fixed-altitude 2D trajectories or homogeneous interference, motivating spatially aware 3D planning.

  • Method

    The framework builds 3D channel-gain and SINR maps, solves an equivalent shortest-path problem, and quantizes correlated neighboring grids for lower-complexity planning.

  • Results

    The proposed solution significantly improves UAV communication SINR and flight efficiency over benchmarks, while quantization reduces graph size and complexity.

  • Takeaways & Limitations

    Adjusting horizontal and vertical map quantization ratios provides a flexible performance–complexity trade-off for interference-aware 3D UAV path planning.

Abstract

from arXiv · show

In this paper, we study the three-dimensional (3D) path planning for a cellular-connected unmanned aerial vehicle (UAV) to minimize its flying distance from given initial to final locations, while ensuring a target link quality in terms of the expected signal-to-interference-plus-noise ratio (SINR) at the UAV receiver with each of its associated ground base stations (GBSs) during the flight. To exploit the location-dependent and spatially varying channel as well as interference over the 3D space, we propose a new radio map based path planning framework for the UAV. Specifically, we consider the channel gain map of each GBS that provides its large-scale channel gains with uniformly sampled locations on a 3D grid, which are due to static and large-size obstacles (e.g., buildings) and thus assumed to be time-invariant. Based on the channel gain maps of GBSs as well as their loading factors, we then construct an SINR map that depicts the expected SINR levels over the sampled 3D locations. By leveraging the obtained SINR map, we proceed to derive the optimal UAV path by solving an equivalent shortest path problem (SPP) in graph theory. We further propose a grid quantization approach where the grid points in the SINR map are more coarsely sampled by exploiting the spatial channel/interference correlation over neighboring grids. Then, we solve an approximate SPP over the reduced-size SINR map (graph) with reduced complexity. Numerical results show that the proposed solution can effectively minimize the flying distance/time of the UAV subject to its communication quality constraint, and a flexible trade-off between performance and complexity can be achieved by adjusting the grid quantization ratio in the SINR map. Moreover, the proposed solution significantly outperforms various benchmark schemes without fully exploiting the channel/interference spatial distribution in the network.

I. INTRODUCTION

The paper develops a radio-map-based framework for interference-aware 3D path planning of cellular-connected UAVs under general 3D air-ground channels. It models spatially varying channel gains and interference, transforms path planning into shortest-path optimization, and evaluates performance–complexity trade-offs through grid quantization.

  • Motivation: Cellular-connected UAVs require high-quality air-ground communications, while high-altitude LoS channels create both macro-diversity and stronger interference-related challenges.Cellular connectivity offers longer-range communication than Wi-Fi and can improve rate and reliability by leveraging advanced cellular technologies.
  • Limitations: Existing trajectory-design studies are limited by inaccurate LoS-only models, dedicated-resource assumptions that omit aerial-ground interference, and predominantly 2D fixed-altitude trajectories.Urban and suburban obstacles can cause shadowing and multipath effects, while varying altitude may improve performance under general 3D channel models.
  • Problem formulation: The paper minimizes the UAV’s flying distance between given initial and final locations while maintaining satisfactory communication quality with an associated GBS under interference from non-associated GBSs.With a given speed, minimizing flying distance also minimizes flight time.
  • Radio-map framework: The proposed radio maps combine each GBS’s large-scale channel-gain distribution on a sampled 3D grid with GBS loading factors to construct expected SINR levels across the fly region.Channel-gain maps can be obtained offline through dedicated UAV channel sensing and measurements.
  • Optimization and evaluation: The SINR map yields an equivalent graph-theoretic shortest path problem solved optimally with Dijkstra’s algorithm, while grid quantization reduces complexity by exploiting neighboring-point spatial correlation.Numerical results validate the algorithms, show a performance–complexity trade-off controlled by quantization ratios, and report significant improvement over benchmark schemes with incomplete spatial knowledge.

II. SYSTEM MODEL AND PERFORMANCE METRIC

The system models a cellular-connected UAV flying at constant speed from an initial to a final 3D location while communicating with associated ground base stations (GBSs). Offline path planning uses expected SINR, approximated from large-scale channel gains and GBS loading factors, and represented through an SINR map.

  • System model: The UAV flies from initial location U0 to final location UF in a 3D Cartesian space while potentially associating with M ≥1 GBSs.The UAV position is u(t) = [x(t), y(t), H(t)]T over mission duration T.
  • System model: The UAV moves at constant speed V meter/second, so its trajectory is determined solely by its flying path.The mission completion time is denoted by T.
  • Performance metric: Offline path planning adopts expected SINR because instantaneous SINR varies with small-scale fading and time-varying interference.Online countermeasures include channel coding, power control, and dynamic RB allocation.
  • Performance metric: The expected SINR is determined by GBS loading factors lm and small-scale fading distributions, but is approximated by a lower bound based on large-scale channel gains and loading factors.The resulting expected SINR can be calculated offline efficiently and used to construct an SINR map for 3D path planning.

III. SINR MAP CONSTRUCTION · A. Channel Gain Map

The paper constructs the SINR map for UAV path planning by first representing each GBS’s large-scale channel gains over a finite, discretized 3D region. This representation enables efficient storage and provides channel-gain values across UAV locations for subsequent SINR-map construction.

  • III. SINR MAP CONSTRUCTION: SINR-map construction begins by introducing the structure and storage of each GBS’s channel gain map.The channel gain maps serve as the basis for constructing the SINR map.
  • A. Channel Gain Map: Each GBS channel gain map represents the spatial distribution of its large-scale channel gain across 3D UAV locations.For the mth GBS, the map stores large-scale gains denoted by ¯h_m(u) for locations u ∈ R^3×1.
  • A. Channel Gain Map: To limit storage, the map covers only neighborhood locations whose large-scale gains exceed threshold ǫ.Locations with negligible gains are excluded from the truncated 3D region.
  • A. Channel Gain Map: The retained 3D space is discretized into grid cells with granularity ∆D, chosen so channel gain is approximately constant within each cell.This discretization converts the continuous spatial map into a finite grid representation.
  • A. Channel Gain Map: Each grid element corresponds to a 3D location indexed by the grid-coordinate sets X_m, Y_m, and Z_m.The map is organized over finite indices i_m, j_m, and k_m for the three spatial dimensions.
  • A. Channel Gain Map: The map dimensions are determined by the discretized locations whose large-scale gains are no smaller than ǫ.Outside the locations included in U_m^D, the paper assumes ¯h_m(u) = 0 for simplicity.
  • A. Channel Gain Map: For each GBS, storing the channel gain map requires only X_mY_mZ_m + 4 real numbers.The stored quantities include the map elements, the reference location, and the grid granularity ∆D.
  • A. Channel Gain Map: The channel gain maps for all M GBSs are assumed to be perfectly known with sufficiently small granularity ∆D.Under this assumption, the gain at any UAV location equals the map entry for its containing grid cell.

B. SINR Map

The SINR map combines 3D channel-gain maps and GBS loading factors to estimate expected SINR at discretized UAV locations and identify the best serving GBS. Its location-dependent associations and rapidly varying SINR support communication-aware path planning beyond nearest-GBS selection.

  • SINR-map construction: At each grid location, the method extracts large-scale gains from all M GBS channel maps, computes expected SINR, and selects the GBS with maximum expected SINR.A gain is set to zero when the location lies outside a GBS’s effective channel-gain map; otherwise, the gain comes from its associated cell.
  • Map domain and discretization: The SINR map is constructed over a sufficiently large 3D cuboid covering all possible UAV flight locations.The horizontal region has edge length L, while the cuboid height is H_R = H_max − H_min.
  • Map domain and discretization: Using channel-map granularity Δ_D, the cuboid is discretized into a D × D × Z grid represented by the location set U_D.Here, D = L/Δ_D and Z = H_R/Δ_D.
  • SINR-map construction: The overall SINR-map construction complexity across all grid locations is O(D^2ZM).The procedure evaluates candidate GBS links at every discretized UAV location using extracted channel gains and interference-related quantities.
  • Map characteristics: Location-specific channel and interference make the associated GBS not necessarily the nearest one, while the SINR map varies more abruptly than individual GBS channel-gain maps.This behavior is illustrated at H = 125 m under a specified set of GBS loading factors.

IV. PROBLEM FORMULATION FOR SINR-AWARE 3D PATH PLANNING

The section formulates SINR-aware 3D path planning as minimizing UAV flying time or distance between fixed endpoints while maintaining a target expected SINR at constant speed. It establishes a piecewise-linear optimal-path structure and motivates discretization and graph-theoretic reformulation because the continuous and grid-based problems are challenging to solve directly.

  • Continuous problem: The objective minimizes the UAV’s flying time or distance from u0 to uF while maintaining expected SINR γ̄(u(t)) ≥ γ̄T throughout flight at constant speed V.The path satisfies u(0) = u0, u(T) = uF, and ∥u̇(t)∥ = V.
  • Continuous problem: The continuous formulation is difficult because it contains infinitely many optimization variables and location-dependent channel gain and interference determine the expected SINR constraint.This dependence makes the problem more challenging than the prior interference-free LoS setting.
  • Path structure: The optimal path is piecewise linear, with each interior waypoint lying at the intersection of two adjacent cells that both satisfy the expected SINR target.The result follows from the convex-polyhedral structure of the cells.
  • Grid formulation: With sufficiently fine grid granularity ΔD, line segments between adjacent feasible grid points remain feasible because points within each cell share the same channel and SINR level.This property supports replacing the continuous path with a grid-based formulation.
  • Grid formulation: The grid-based problem uses SINR-feasible grid points, fixed start and end points, integer grid indices, and a bounded step between consecutive traversed points, but is a non-convex combinatorial optimization problem.The paper therefore reformulates it using graph theory to obtain optimal and suboptimal solutions.

V. OPTIMAL SOLUTION

The paper obtains the optimal solution by recasting (P1) as an equivalent shortest path problem in graph theory. Radio-map preprocessing removes grid points that cannot satisfy the SINR constraint, reducing the candidate graph.

  • Graph-based reformulation: (P1) is reformulated as an equivalent shortest path problem in graph theory.The graph initially represents the 3D grid used for UAV path planning.
  • Radio-map preprocessing: Only grid points satisfying [¯S]i,j,k ≥ ¯γT can potentially belong to a feasible path under the constraints in (18).This condition motivates preprocessing before constructing the effective graph.
  • 3D grid path structure: The path structure connects grid points along adjacent locations on the same or adjacent horizontal planes.The accompanying illustration defines grid points and paths between neighboring horizontal planes.

A. Radio Map Preprocessing

The preprocessing constructs a binary feasible map from the SINR map, marking grid points that meet the target threshold and enabling subsequent path planning.

  • A. Radio Map Preprocessing: The feasible map F ∈ {0, 1}^{D×D×Z} marks grid point (i, j, k) as feasible when [¯S]_{i,j,k} ≥ ¯γT; otherwise it is infeasible.A value [F]_{i,j,k} = 1 indicates feasibility, while [F]_{i,j,k} = 0 indicates infeasibility.
  • A. Radio Map Preprocessing: The preprocessing complexity is O(D^2Z).This complexity applies to constructing the feasible map from the SINR map.

B. Graph Based Problem Reformulation and Solution

The feasible 3D grid is reformulated as an undirected weighted graph whose shortest path exactly solves the UAV distance-minimization problem. Feasibility is determined by endpoint connectivity, while Dijkstra’s algorithm provides the solution when a path exists.

  • Graph construction: The feasible map is represented by an undirected weighted graph G_D whose vertices are feasible grid points.Each vertex U_D(i,j,k) corresponds to a grid location with [F]_i,j,k = 1.
  • Graph construction: Edges connect exactly those vertices whose corresponding grid points are adjacent, with weights equal to their Euclidean flying distance.The edge weight is ||u_D(i,j,k)−u_D(i′,j′,k′)||.
  • Feasibility checking: The original problem is feasible if and only if the initial and final vertices are connected in G_D.Connectivity can be checked using breadth-first search with complexity O(|V_D| + …).
  • Feasibility checking: As the SINR target increases, the feasible map and graph become sparser, making infeasibility more likely.This sparsity results from the stricter communication-quality constraint.
  • Shortest-path solution: When feasible, solving the shortest path from the initial to final vertex in G_D is equivalent to solving the original problem.Dijkstra’s algorithm using a Fibonacci heap has worst-case complexity O(|E_D| + |V_D| log |V_D|) = O(D^2Z log(D^2Z)).

VI. SUBOPTIMAL SOLUTION VIA GRID QUANTIZATION · A. Radio Map Preprocessing · B. Reduced-Size Graph and Suboptimal Solution

The paper reduces radio-map path-planning complexity by quantizing the 3D grid more coarsely horizontally than vertically, then solving a shortest-path problem on a smaller feasible graph. This produces feasible suboptimal paths while enabling a tunable performance–complexity trade-off.

  • VI. SUBOPTIMAL SOLUTION VIA GRID QUANTIZATION: The original graph’s complexity and edge-weight memory grow with horizontal grid size D and altitude levels Z, becoming impractical for large flight regions.With ∆D = 10 m, L = 200 km, and HR = 40 m, D = 2 × 10^4 and Z = 4, yielding D^2Z log(D^2Z) ≈ 3.4 × 10^10.
  • A. Radio Map Preprocessing: The proposed preprocessing applies larger quantization ratios to horizontal dimensions and smaller ratios to the vertical dimension because the altitude range is typically much smaller than the horizontal flight region.The ratios are denoted κxy for the x–y axes and κz for the z axis.
  • A. Radio Map Preprocessing: Each quantized grid point represents κxy^2κz neighboring original grid points whose channels and SINR values are typically highly correlated.The quantized point is placed at the center of its neighboring set and corresponding quantized cell.
  • A. Radio Map Preprocessing: A quantized grid point is feasible only when all neighboring original grid points satisfy the feasibility condition, producing the quantized feasible map ˜F.The map indicator [˜F]i,j,k equals 1 for feasible quantized points and 0 otherwise.
  • B. Reduced-Size Graph and Suboptimal Solution: The reduced graph connects feasible quantized points to adjacent points in 10 directions: 8 within a horizontal plane and 2 on adjacent horizontal planes.The corresponding distances are κxy∆D, 2κxy∆D, and κz∆D.
  • B. Reduced-Size Graph and Suboptimal Solution: The reduced graph has at most ˜D^2˜Z = D^2Z/(κxy^2κz) vertices, making it significantly smaller than the original graph.The edge weight equals the Euclidean distance between adjacent quantized grid points.
  • B. Reduced-Size Graph and Suboptimal Solution: Increasing κxy and/or κz generally worsens performance but decreases complexity, enabling a flexible trade-off through quantization-ratio selection.The suboptimal solution requires 1/(κxy^2κz) of the optimal solution’s complexity.

VII. NUMERICAL EXAMPLES

The numerical evaluation uses a UAV altitude range of 90–130 m and a flight from [5, 5, 95]T m to [625, 625, 125]T m. Experiments compare isotropic GBS gains with an LTE-standard tilted 8-element ULA model using 10 m radio-map granularity.

  • Experimental setup: The UAV altitude is constrained to Hmin=90 m and Hmax=130 m, giving an allowable range of HR=40 m.The initial and final locations are u0=[5, 5, 95]T m and uF=[625, 625, 125]T m, respectively.
  • Experimental setup: Sections VII-A–VII-C first evaluate a simplified scenario with isotropic GBS antenna gain, GA_m(u)=0 dB.The corresponding radio maps are illustrated in Figs. 2 and 4.
  • Experimental setup: The channel gain and SINR maps use granularity ΔD=10 m, with independently and randomly generated loading factors l=[0.0318, 0.6561, 0.3223, 0.9679, 0.2598, 0.7672]T.Each loading factor follows a uniform distribution in [0, 1].

A. Performance of Proposed Solution with Different Quantization Ratios

The study evaluates optimal and suboptimal path solutions under different horizontal quantization ratios and SINR targets. Results show that coarser quantization reduces feasibility and path-design flexibility, demonstrating a performance-complexity trade-off.

  • Evaluation setup: With κz = 1, the evaluation compares horizontal quantization ratios κxy ∈ {3, 7, 9} at expected SINR targets ¯γT = 0 dB and 3 dB.The comparison assesses the proposed optimal solution against suboptimal solutions using different quantization ratios.
  • Feasibility: The feasible SINR-target range is [−2.309, 5.284] dB because the minimum map value is −2.309 dB and (P1) becomes infeasible above 5.284 dB.These limits determine the range used in Fig. 9.
  • Feasibility: The optimal solution remains feasible for ¯γT > 3 dB, whereas suboptimal solutions with κxy = 7 and κxy = 3 become infeasible when ¯γT > 4 dB.The feasibility comparison is reported for the proposed path solutions in Fig. 9.
  • Performance-complexity trade-off: Required flying distance increases with κxy because coarser grid/SINR quantization provides less flexibility in path design.This observation validates the performance-complexity trade-off discussed in Section VI.
  • Quantization method: The quantization method and resulting suboptimal designs exploit spatial channel/SINR correlation among neighboring grid points.The passage identifies this mechanism as validating the proposed grid quantization approach.

B. Effectiveness of Interference-Aware Path Planning · C. Effectiveness of Terrain-Aware Path Planning

The proposed planner uses exact interference and terrain-dependent radio maps to select feasible, short UAV paths under expected-SINR constraints. Compared with interference- and terrain-unaware benchmarks, it remains more effective as interference increases or channel conditions vary.

  • B. Effectiveness of Interference-Aware Path Planning: The interference-aware evaluation compares the proposed solution with worst-case-interference and no-interference planning based on loading-factor bounds.Worst-case planning uses each GBS’s upper-bound loading factor lmax_m, while no-interference planning assumes zero loading and reduces the SINR map to an SNR map.
  • B. Effectiveness of Interference-Aware Path Planning: Benchmark scheme 1 becomes infeasible when ¯γT > −1 dB for l = ¯l and when ¯γT > 2 dB for the lower-loading case.This benchmark overestimates interference by using upper-bound loading factors.
  • B. Effectiveness of Interference-Aware Path Planning: 9.263 dB is the maximum achievable expected SINR target when loading factors decrease from l = ¯l to l = 0.4¯l.The maximum target increases from 5.284 dB to 9.263 dB as reduced loading produces less severe interference.
  • B. Effectiveness of Interference-Aware Path Planning: At ¯γT = 2 dB, feasible grid points become sparser as loading factors increase, imposing stricter channel-gain requirements during flight.The figure compares the proposed path with both benchmark paths under two loading-factor sets.
  • C. Effectiveness of Terrain-Aware Path Planning: Terrain-aware planning captures location-dependent LoS and NLoS conditions, providing communication-performance guarantees at every location along the UAV flight region.The evaluation compares this approach with LoS-only and NLoS-only channel-map constructions.
  • C. Effectiveness of Terrain-Aware Path Planning: Terrain-unaware benchmark schemes 3 and 4 become infeasible after the fourth and fifth expected-SINR target sample points, respectively.When feasible, both require significantly increased flying distance because their channel-gain and SINR maps are inaccurate.
  • C. Effectiveness of Terrain-Aware Path Planning: No connectivity outage is observed for the benchmark schemes under the stated setup.Connectivity outage is evaluated against the expected SINR target in Fig. 11.

D. Performance of Proposed Solution under Downtilted GBS Antennas · VIII. CONCLUDING REMARKS

Under downtilted GBS antennas, the SINR landscape and GBS associations become more heterogeneous because UAVs generally rely on weak sidelobes, motivating evaluation of the proposed path solution. The concluding remarks summarize the radio-map-based SPP framework and identify extensions to additional utilities, multiple UAVs, and uplink communication.

  • D. Performance of Proposed Solution under Downtilted GBS Antennas: At H = 125 m, downtilted GBS antennas produce a more heterogeneous SINR map than fixed isotropic antennas.SINR peaks are generally not close to GBSs.
  • D. Performance of Proposed Solution under Downtilted GBS Antennas: Weak sidelobes generally serve skyborne UAVs, making channel gain nonmonotonic with GBS-UAV distance.Consequently, the serving GBS is generally not the closest GBS.
  • D. Performance of Proposed Solution under Downtilted GBS Antennas: The paper illustrates the optimal path solution under an SINR target of ¯γT = −0.2 dB.Fig. 15 also illustrates an outage-tolerant solution with OT = 50 m.
  • VIII. CONCLUDING REMARKS: The paper formulates interference-aware 3D UAV path planning as flying-distance minimization subject to an expected receive-SINR target with associated GBSs.Its radio maps characterize large-scale GBS-UAV channel gains and expected SINR levels with optimal GBS association, enabling an equivalent shortest path problem.
  • VIII. CONCLUDING REMARKS: Future work can incorporate outage cost, average communication rate, and the number of GBS handovers into radio-map-based path planning.The passage notes that frequent handovers lead to additional consequences, but the provided text truncates that statement.
  • VIII. CONCLUDING REMARKS: Further extensions include multiple-UAV collision avoidance and interference-aware path planning under uplink communication constraints.Unlike downlink, uplink interference is caused by the UAV to non-associated GBSs.
Loading 1912.00021v2…