PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-UAV Interference Coordination via Joint Trajectory and Power Control

Chao Shen, Tsung-Hui Chang, Jie Gong, Yong Zeng, Rui Zhang

arXiv:1809.05697v1math.OC

TL;DR

UAVs sharing spectrum can experience strong interference between their UAV–ground-terminal links, motivating joint trajectory and power control. The paper reduces the optimization using deployment locations and proposes SCA, parallel, and segment-by-segment methods; the reported methods reduce computation time, and spectrum sharing can outperform orthogonal schemes in sum rate.

  • Problem

    Concurrent UAV–ground-terminal links share spectrum, where strong line-of-sight links can make interference significant.

    Source: §I · p. 2

  • Method

    The paper uses a fly-hover-fly structure to reduce TPC around deployment locations, then proposes SCA, parallel, and segment-by-segment algorithms.

    Source: §VII · p. 27

  • Results

    The parallel TPC algorithm achieves nearly the same aggregate sum rate as its centralized counterpart with substantially reduced computation time, and spectrum-sharing UAV links can outperform orthogonal schemes.

    Source: §VII · p. 27

  • Takeaways & Limitations

    The proposed parallel and segment-by-segment algorithms provide computationally efficient approaches to the TPC problem.

    Source: §VII · p. 27

Abstract

from arXiv · show

In this paper, we consider an unmanned aerial vehicle-enabled interference channel (UAV-IC), where each of the $K$ UAVs communicates with its associated ground terminals (GTs) at the same time and over the same spectrum. To exploit the new degree of freedom of UAV mobility for interference coordination between the UAV-GT links, we formulate a joint trajectory and power control (TPC) problem for maximizing the aggregate sum rate of the UAV-IC for a given flight interval, under the practical constraints on the UAV flying speed, altitude, as well as collision avoidance. These constraints couple the TPC variables across different time slots and UAVs, leading to a challenging large-scale and non-convex optimization problem. By exploiting the problem structure, we show that the optimal TPC solution follows the fly-hover-fly strategy, based on which the problem can be handled by firstly finding an optimal hovering locations followed by solving a dimension-reduced TPC problem with given initial and hovering locations of UAVs. For the reduced TPC problem, we propose a successive convex approximation algorithm. To improve the computational efficiency, we further develop a parallel TPC algorithm that is effciently implementable over multi-core CPUs. We also propose a {segment-by-segment method} %virtual waypoint model which decomposes the TPC problem into sequential TPC subproblems each with a smaller problem dimension. Simulation results demonstrate the superior computation time efficiency of the proposed algorithms, and also show that the UAV-IC can yield higher network sum rate than the benchmark orthogonal schemes.

I. INTRODUCTION

The introduction presents joint trajectory and power control for a multi-UAV interference channel, including structural decomposition and efficient algorithms to maximize aggregate sum rate under flight and collision-avoidance constraints. It also outlines later algorithmic developments and the paper’s section sequence, then specifies notation.

A. Related Work

  • Prior work studied UAV placement, mobile relaying with TPC, and multi-UAV energy optimization and user association or scheduling.Source: A. Related Work · pp. 2–3

B. Contributions

  • The UAV-IC formulation jointly optimizes trajectories and transmission powers to maximize aggregate sum rate, subject to speed, altitude, and 3D collision-avoidance constraints.The problem is generally NP-hard and has many coupled TPC variables over long flight intervals.Source: B. Contributions · p. 3
  • Assuming UAVs return to their initial locations, the symmetric optimal solution enables decomposition into optimal hovering-location selection and lower-dimensional TPC optimization from initial to hovering locations.The decomposition also applies when UAV initial and destination locations differ.Source: B. Contributions · p. 4
  • The proposed SCA method uses a locally tight surrogate rate function to jointly update trajectories and transmission powers, while parallel and segment-by-segment methods target computational cost.The segment-by-segment strategy divides a long flight into consecutive smaller time segments; the parallel TPC algorithm is designed for multi-core CPUs.Source: B. Contributions · p. 4
  • The proposed algorithms improve computation-time efficiency over conventional AO and spectrum efficiency over FDMA/TDMA, while the SCA algorithm achieves comparable sum-rate performance to AO.Source: B. Contributions · p. 4
  • The paper previews distributed TPC and segment-by-segment methods for reducing computation time, FDMA and TDMA extensions, simulations, and a conclusion.The proposed SCA algorithms are extended to FDMA and TDMA in Section V; simulations are presented in Section VI.Source: B. Contributions · p. 5
  • The notation defines vector and matrix formatting, transpose and positive-semidefinite conventions, identity and all-one/all-zero vectors, norms, diagonal matrices, and the Kronecker product.The passages identify these conventions and operators for use throughout the paper.Source: B. Contributions · p. 5

II. SYSTEM MODEL AND PROBLEM FORMULATION

The system model considers UAVs communicating with associated ground terminals over a shared spectrum, and formulates joint trajectory and power control to maximize aggregate sum rate. The optimization incorporates flight and collision constraints and is challenging because it is non-convex, NP-hard, and large-scale.

II. SYSTEM MODEL AND PROBLEM FORMULATION

  • The model has K UAVs communicating with associated ground terminals simultaneously over the same spectrum; the analysis considers downlink and also applies to uplink.The UAVs and ground terminals are assumed to have omnidirectional antennas.Source: §II · p. 5
  • Trajectories must satisfy altitude and speed limits, maintain minimum separation between UAVs, and meet fixed initial and final locations.The considered round-trip setting requires each UAV to return to its initial location.Source: §II · pp. 6–7
  • The air-to-ground channel is modeled using free-space path loss, with line-of-sight propagation dominating in many practical scenarios.The channel gain depends on the distance between each UAV and ground terminal.Source: §II · p. 6
  • The objective jointly optimizes all UAV trajectories and transmission powers to maximize aggregate sum rate over the flight duration.Interference between UAV–GT links depends on both trajectories and transmission powers.Source: §II · p. 7
  • The TPC problem is NP-hard and can have many variables because the time-slot count must be large enough to model channel variation and collision avoidance.These challenges motivate computationally efficient methods for finding high-quality suboptimal solutions.Source: §II · p. 7

III. PROPOSED TPC OPTIMIZATION ALGORITHMS

The proposed solution first identifies UAV deployment locations, then optimizes trajectories and powers in a dimension-reduced problem. An SCA-based algorithm is used for that reduced TPC optimization.

III. PROPOSED TPC OPTIMIZATION ALGORITHMS

  • The approach first finds UAV deployment locations, then optimizes trajectories and transmission powers from the initial locations to those deployments.This staged formulation produces a dimension-reduced TPC problem.Source: §III · p. 8
  • The optimization procedure separates deployment-location selection from the subsequent trajectory-and-power design.The second stage optimizes UAV movement from initial locations to the selected deployment locations.Source: §III · p. 8
  • The reduced TPC problem is solved using a successive convex approximation algorithm.The paper presents this algorithm after introducing the reduced formulation.Source: §III · p. 8

A. Symmetry of TPC Solution

With a return-to-start constraint, an optimal TPC solution can be symmetric across the flight midpoint, yielding a fly-hover-fly structure. The authors use this structure to reduce the design problem and propose a two-step heuristic for selecting hovering locations and designing the remaining TPC.

A. Symmetry of TPC Solution

B. Heuristic 2-Step TPC Design

  • The heuristic first selects reachable hovering locations maximizing instantaneous sum rate, then solves TPC with those locations and M fixed.Its final step reconstructs the full-flight solution; optimizing M is difficult in general.Source: B. Heuristic 2-Step TPC Design · pp. 9–10
  • Without a return-to-start requirement, optimal TPC solutions are not generally symmetric, although fly-hover-fly remains applicable.When the flight interval is sufficiently long relative to travel time, fly-hover-fly is approximately optimal.Source: B. Heuristic 2-Step TPC Design · p. 11

C. SCA-based TPC Optimization

The section develops an SCA-based method for the reduced TPC problem. It constructs concave lower bounds to form convex subproblems, whose objective values converge; the cited AO alternative can attain comparable aggregate sum rate but is more computationally expensive.

C. SCA-based TPC Optimization

  • SCA successively solves convex approximations of the reduced TPC problem using trajectory and transmission-power variables.At each iteration, the approximation is formed around the current trajectory and power values.Source: C. SCA-based TPC Optimization · pp. 11, 13
  • The rate function is replaced by a concave lower bound that is a function of the power and trajectory variables.The method also uses a convex lower bound to handle the non-convex collision-avoidance constraint.Source: C. SCA-based TPC Optimization · pp. 12–13
  • The convex-subproblem objective values are non-decreasing and upper-bounded, so they converge as iterations increase.This is the stated convergence property for problem (23).Source: C. SCA-based TPC Optimization · p. 14
  • AO can yield aggregate sum rate comparable to Algorithm 1, but is computationally more expensive.AO alternates trajectory and power updates.Source: C. SCA-based TPC Optimization · p. 14

IV. TIME-EFFICIENT TPC OPTIMIZATION

The reduced TPC problem can still be computationally expensive when the number of UAVs or flight slots is large. The section proposes parallel and segment-by-segment approaches to improve computational efficiency.

IV. TIME-EFFICIENT TPC OPTIMIZATION

  • Even after reduction from O(KN) to O(KM) variables and constraints, TPC can remain expensive when K or M is large.This may occur, for example, when UAVs start far from their serving ground terminals.Source: §IV · p. 14
  • The proposed parallel algorithm can run on multicore computers or clusters and has significantly reduced computation time relative to Algorithm 1.The section presents it as one approach to address the remaining computational burden.Source: §IV · p. 14
  • The segment-by-segment method decomposes TPC over [0, M] into sequential subproblems, each covering a smaller flight interval.Source: §IV · p. 14

A. Parallel TPC Optimization

The parallel TPC algorithm separates UAV updates using ADMM and replaces a coupled non-convex update with a separable concave surrogate. This supports parallel computation over multicore CPUs and is intended to reduce computation time.

A. Parallel TPC Optimization

  • The algorithm applies ADMM to constraints relating pairwise UAV position differences to their trajectories.The associated updates are simple and separable across UAVs.Source: A. Parallel TPC Optimization · pp. 15–16
  • For the difficult coupled update, BSUMM supplies a concave, separable lower bound that enables parallel UAV updates.The surrogate is locally tight as ε approaches zero.Source: A. Parallel TPC Optimization · pp. 16–17
  • The proposed algorithm enables parallel computation over multicore CPUs and is expected to reduce computation time.The passage says the reduction is demonstrated in Section VI.Source: A. Parallel TPC Optimization · p. 17

B. Segment-by-Segment TPC Optimization

The segment-by-segment method addresses the time cost of solving the TPC problem when there are many discrete time slots. It divides the interval into smaller segments and solves their TPC subproblems sequentially.

B. Segment-by-Segment TPC Optimization

  • When the number of time slots M is large, the TPC problem remains time-consuming; the proposed method divides the interval into smaller segments.The paper summarizes the procedure in Algorithm 3.Source: B. Segment-by-Segment TPC Optimization · p. 18
  • Each segment contains Nseg time slots, and its trajectories and powers are determined using the preceding segment’s values.The segment subproblem is solved sequentially, with the initial location set to q[0] for the first segment.Source: B. Segment-by-Segment TPC Optimization · p. 18

V. TPC OPTIMIZATION OVER ORTHOGONAL CHANNELS

The section extends trajectory and power optimization to FDMA and TDMA schemes. It states that FDMA does not perform worse than TDMA and describes an SCA-based approach for the resulting problem.

V. TPC OPTIMIZATION OVER ORTHOGONAL CHANNELS

  • For FDMA, the resource fraction αk[n] is allocated to each UAV-GT pair at each slot, with the fractions summing to one.The section gives a concave lower bound for the FDMA rate that is concave in αk[n] and qk[n].Source: §V · p. 19
  • FDMA does not perform worse than TDMA in the stated comparison.The FDMA/TDMA trajectory and resource-allocation problem is handled using an approach similar to Algorithm 1, based on SCA.Source: §V · p. 19
  • For TDMA, the problem admits an optimal time allocation for αk[n].The stated approach applies a linear lower bound in the SCA formulation.Source: §V · p. 20

VI. SIMULATION RESULTS

The simulations examine altitude flexibility, TPC initialization, and algorithm performance under specified flight and channel settings. They report improved sum-rate performance and show how changing altitude supports collision avoidance.

A. Simulation Settings

  • Simulations use T=10 minutes, Pmax=30 dBm, speed limits VL=20 m/s, VA=5 m/s, and VD=3 m/s; B=10 MHz, β0=−50 dB, and N0=−160 dBm/Hz. Unless otherwise stated, GTs are randomly located in a 1 square kilometer area.Source: A. Simulation Settings · p. 20

B. Impact of Flight Altitude

  • Joint TPC greatly improves aggregate sum rate, with only UAV 1 transmitting during the first 20 time slots before the UAVs share the spectrum.The optimized scheme dynamically switches between TDMA and spectrum sharing.Source: B. Impact of Flight Altitude · p. 21
  • With altitude variation, optimized horizontal trajectories become straighter while UAVs vary their altitudes to avoid collisions.The simulations indicate that the extra altitude freedom can help collision avoidance and provide feasible initial trajectories for SCA-based algorithms.Source: B. Impact of Flight Altitude · p. 21

C. TPC Initialization

  • TPC initialization uses a four-step trajectory procedure; its straight initial paths can reduce M, and WMMSE initializes transmission powers.The section states that the procedure is used for the TPC problems and that smaller M is desirable.Source: C. TPC Initialization · pp. 21, 23

D. Optimized TPC Solution

The optimized trajectories use near-GT hovering locations and altitude changes for collision avoidance, while power and rate coordination can leave a UAV silent at its hovering point. The parallel TPC algorithm converges quickly for up to 10 UAVs in the reported examples.

D. Optimized TPC Solution

  • Optimized hovering locations are near serving GTs and close to Hmin; UAVs fly straight horizontally and change altitude for collision avoidance.UAVs 3 and 5 ascend and then descend to avoid collisions with UAVs 2 and 4.Source: D. Optimized TPC Solution · p. 23
  • UAV 2 is silent at its hovering location because of strong cross-link interference, but transmits during flight from time slot 56 to 78 by coordinating with nearby UAVs.The reported example uses K=6 and M=92.Source: D. Optimized TPC Solution · pp. 23–24

E. Convergence of Parallel TPC Algorithm

  • For K≤10, the parallel TPC algorithm reaches a high-accuracy solution within 10 iterations; for K=20, convergence is slower but relative precision remains below 10^-3.The two curves represent typical convergence behaviors from different random realizations.Source: Figure 5 · p. 25, E. Convergence of Parallel TPC Algorithm · p. 26

F. Throughput and Computation Time Comparison

The proposed TPC variants trade computation time against aggregate sum rate, while comparisons with orthogonal schemes show when coordinated spectrum sharing can be advantageous. The conclusion also describes the round-trip decomposition and identifies future extensions.

F. Throughput and Computation Time Comparison

  • Parallel TPC retains almost the centralized algorithm’s aggregate sum rate with significantly less computation time, while segment-by-segment cuts time further at about 5% rate loss.The segment-by-segment algorithm may lose about 5% of aggregate sum rate compared with Algorithm 1.Source: F. Throughput and Computation Time… · p. 26
  • The slot-by-slot method is less time efficient than the general segment-by-segment method.The slot-by-slot variant corresponds to setting Nseg = 1.Source: F. Throughput and Computation Time… · p. 26
  • The proposed TPC algorithms achieve almost the AO method’s aggregate sum rate while requiring less computation time.The parallel algorithm’s computation-time reduction is especially notable when K ≥3.Source: F. Throughput and Computation Time… · pp. 26–27
  • FDMA outperforms TDMA for all K and can exceed the non-orthogonal scheme at K = 2 under the considered short-term peak-power constraint.The passage attributes this comparison to considering short-term peak power constraints rather than long-term average power constraints.Source: F. Throughput and Computation Time… · p. 27
  • Non-orthogonal schemes outperform FDMA especially when K ≥3, indicating potential gains from spectrum sharing when trajectories and powers are coordinated.FDMA requires more computation time than TDMA for all K.Source: F. Throughput and Computation Time… · p. 27

VII. CONCLUSION

  • For round-trip missions, TPC solutions are symmetric, enabling approximate decomposition into optimal hovering-location selection followed by reduced TPC optimization; SCA jointly updates trajectories and powers.The SCA-based method updates trajectory and transmission-power variables together in each iteration.Source: §VII · p. 27
  • Future extensions include dynamically switching between FDMA and spectrum sharing under peak and average power constraints, and considering multi-antenna GTs and broadcast or multicast channels.The paper also identifies scenarios with more GTs than UAVs as a future direction.Source: §VII · pp. 27–28
Loading 1809.05697v1…