PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Power and 3D Trajectory Optimization for UAV-enabled Wireless Powered Communication Networks with Obstacles

Hongyang Pan, Yanheng Liu, Geng Sun, Junsong Fan, Shuang Liang, Chau Yuen

arXiv:2310.00384v1eess.SYcs.SY

TL;DR

UAV-enabled WPCNs must schedule power and flight paths to serve ground devices efficiently despite obstacles and limited onboard energy. The paper decomposes a joint power-allocation and 3D-trajectory problem and proposes separate algorithms for its subproblems. Simulations report gains in coverage and time efficiency, alongside reduced flight energy consumption.

  • Problem

    In obstacle-filled UAV-enabled WPCNs, power allocation and scheduling must improve energy utilization while serving widely spread devices under limited onboard energy and timeliness requirements.

    Source: §I · pp. 1–2

  • Method

    The authors formulate a joint power-allocation and 3D-trajectory problem, decompose it into UPAOP and UTTOP, and apply NSGA-II-KV and PSO-NGDP, respectively.

    Source: §I · p. 2

  • Results

    Coverage increases by up to 18.03% and time efficiency by 2.93%; PSO-NGDP reduces flight energy consumption by up to 25.30%, with greater savings as coverage area increases.

    Source: §I · p. 2

  • Takeaways & Limitations

    The formulation treats energy utilization as a joint objective involving WD coverage, time efficiency, and UAV flight distance.

    Source: §I · p. 2

Abstract

from arXiv · show

Unmanned aerial vehicle (UAV)-enabled wireless powered communication networks (WPCNs) are promising technologies in 5G/6G wireless communications, while there are several challenges about UAV power allocation and scheduling to enhance the energy utilization efficiency, considering the existence of obstacles. In this work, we consider a UAV-enabled WPCN scenario that a UAV needs to cover the ground wireless devices (WDs). During the coverage process, the UAV needs to collect data from the WDs and charge them simultaneously. To this end, we formulate a joint-UAV power and three-dimensional (3D) trajectory optimization problem (JUPTTOP) to simultaneously increase the total number of the covered WDs, increase the time efficiency, and reduce the total flying distance of UAV so as to improve the energy utilization efficiency in the network. Due to the difficulties and complexities, we decompose it into two sub optimization problems, which are the UAV power allocation optimization problem (UPAOP) and UAV 3D trajectory optimization problem (UTTOP), respectively. Then, we propose an improved non-dominated sorting genetic algorithm-II with K-means initialization operator and Variable dimension mechanism (NSGA-II-KV) for solving the UPAOP. For UTTOP, we first introduce a pretreatment method, and then use an improved particle swarm optimization with Normal distribution initialization, Genetic mechanism, Differential mechanism and Pursuit operator (PSO-NGDP) to deal with this sub optimization problem. Simulation results verify the effectiveness of the proposed strategies under different scales and settings of the networks.

I. INTRODUCTION

The paper studies UAV-enabled WPCNs with obstacles, where power allocation and 3D flight planning must balance device coverage, time efficiency, and UAV energy use. It decomposes the joint problem into two subproblems and proposes separate algorithms for them.

I. INTRODUCTION

  • The joint optimization targets more covered WDs, improved time efficiency, and shorter UAV flight distance while charging covered devices simultaneously and collecting their data one by one.The UAV either hovers to cover devices within its maximum range or flies to another hovering point.Source: §I · p. 2
  • Because JUPTTOP is NP-hard and variable-dimensional, the authors decompose it into UPAOP and UTTOP, using NSGA-II-KV and PSO-NGDP, respectively.NSGA-II-KV adds K-means initialization and a variable-dimension mechanism; PSO-NGDP uses pretreatment, normal initialization, genetic and differential mechanisms, and a pursuit operator.Source: §I · p. 2
  • Coverage increases by up to 18.03% and time efficiency by 2.93%; PSO-NGDP reduces flight energy consumption by up to 25.30%.The reported energy saving can increase as the coverage area increases.Source: §I · p. 2

II. RELATED WORK

  • Prior work covers UAV coverage, WPCN resource allocation, obstacle avoidance, and power allocation, with cited studies also noting limits involving UAV energy, obstacles, or fixed altitude.The reviewed obstacle-avoidance approaches include PSO, ant colony optimization, velocity-obstacle methods, and safe-DQN.Source: §II · pp. 2–3

III. SYSTEM MODEL

  • The system model comprises a UAV, ground WDs, charging and data-collection models, UAV energy use, and obstacles; the UAV selects hovering points while avoiding collisions.The UAV can charge covered WDs simultaneously and collect their data sequentially; devices beyond the maximum coverage range cannot be charged or served.Source: §III · p. 3, A. Network model · p. 3

B. Wireless charging model

The charging model uses RF energy transfer, while the data-collection model describes UAV-to-device links and achievable rates. Charging can be simultaneous across covered devices, but collection is sequential.

B. Wireless charging model

  • The UAV uses an RFID-based charging model and can charge all covered WDs simultaneously.The model describes received charging power from the UAV at a hovering point.Source: B. Wireless charging model · p. 3
  • Devices are charged to an energy threshold sufficient for a period of normal operation, rather than being fully charged.The stated rationale is to avoid extending hover time and its associated energy consumption.Source: B. Wireless charging model · p. 4

C. Wireless data collection model

  • Data collection follows an Air-to-Ground channel model with elevation-angle-dependent LoS probability, and the achievable rate must meet a minimum threshold.The UAV collects data from covered WDs one by one.Source: C. Wireless data collection model · p. 4

D. Energy consumption model of UAV

The paper models UAV propulsion energy in 2D and extends it to 3D, then represents obstacles using known size and position information. The obstacle setting constrains UAV flight and WD placement.

D. Energy consumption model of UAV

  • The 2D rotary-wing energy model separates communication energy from the energy needed to overcome gravity and propulsion, with communication energy described as much smaller.The model ignores acceleration and deceleration effects because they cost a tiny amount of time.Source: D. Energy consumption model of UAV · p. 5
  • The energy model is extended to 3D and incorporates instantaneous UAV speed, total flight time, UAV mass, gravity, and start and end altitudes.Source: D. Energy consumption model of UAV · p. 5

E. Obstacle model

  • Obstacle sizes and positions are assumed known; the simplified model parameterizes obstacle altitude and horizontal shape, with WDs randomly placed outside obstacle areas.Source: E. Obstacle model · p. 5

F. Multi-objective optimization problem

The formulation jointly weighs device coverage, time efficiency, and obstacle-avoiding flight distance to improve energy utilization. It models these objectives as trade-offs over UAV hovering points and uses Pareto-optimal solutions to represent competing choices.

F. Multi-objective optimization problem

  • A multi-objective problem may yield a set of non-dominated solutions rather than one optimum, so decision makers select from the Pareto front according to their requirements.A solution is non-dominated when no other solution is better in at least one objective without being worse in another.Source: F. Multi-objective optimization problem · p. 5

A. Problem formulation

  • The UAV covers WDs at hovering points, where it can serve multiple WDs simultaneously; the model assumes equal required energy and data size per WD.The UAV is also assumed to operate within altitude limits and use a fixed number of hovering points.Source: A. Problem formulation · p. 5
  • Because charging and data collection run concurrently, hovering time is set by the longer process, while their time mismatch and empty-point penalty also affect time efficiency.The penalty discourages solutions that include hovering points covering no WDs.Source: A. Problem formulation · pp. 6–7
  • K waypoints between adjacent hovering points let the UAV bypass or fly over obstacles, while minimizing flight distance also minimizes flying energy at constant speed.The waypoint and hovering-point altitudes must exceed obstacle heights.Source: A. Problem formulation · p. 7
  • The three objectives are maximizing covered WDs, improving time efficiency, and minimizing obstacle-avoiding flight distance, and their solutions trade off.For example, higher hovering altitudes may reduce obstacle-related flying distance but increase hovering time.Source: A. Problem formulation · pp. 6–7

B. Problem conversion and analysis

The authors decompose the difficult joint problem into power-allocation and trajectory subproblems. The trajectory search is NP-hard and can become large as hovering points, waypoints, and covered WDs increase.

B. Problem conversion and analysis

  • The joint problem is divided into UPAOP and UTTOP because its solution space is large, its dimension can vary, and the problem is NP-hard.With 20 hovering points, 20 waypoints, and 300 covered WDs, the stated solution dimension is 1,580.Source: B. Problem conversion and analysis · p. 8
  • UTTOP is formulated as a single-objective trajectory problem over the waypoint coordinates.Its objective is the obstacle-avoiding flight-distance objective f3.Source: B. Problem conversion and analysis · p. 8
  • UTTOP is NP-hard because a path between fixed endpoints among obstacles has indefinitely many possible trajectories.The paper consequently identifies the overall JUPTTOP as NP-hard as well.Source: B. Problem conversion and analysis · p. 8

V. ALGORITHM FOR UPAOP

The authors propose NSGA-II-KV to solve UPAOP, a constrained multi-objective problem with trade-offs and a variable-length solution. Its initialization and variable-dimension features address weaknesses of conventional NSGA-II for this setting.

V. ALGORITHM FOR UPAOP

  • UPAOP is a constrained multi-objective problem with trade-offs, making multi-objective evolutionary algorithms a feasible strategy without derivative information.The authors state that conventional NSGA-II does not meet the problem's requirements.Source: §V · p. 8
  • Conventional NSGA-II's random initialization does not use prior information, and its fixed-dimension handling does not fit UPAOP's changing solution length.The proposed method adds K-means initialization and a variable-dimension mechanism.Source: §V · p. 8
  • NSGA-II-KV is proposed for UPAOP, whose WD-power vector length changes with the number of covered WDs.The number of covered WDs is itself an optimization objective.Source: §V · p. 8

A. Conventional NSGA-II

The paper introduces NSGA-II-KV to address UPAOP's large constrained search space and changing power-vector length. It combines WD-based K-means initialization with a mechanism that accommodates dimension changes during evolution.

A. Conventional NSGA-II

1) K-means initialization operator:

  • NSGA-II-KV initializes UAV horizontal hovering coordinates from K-means cluster centers of WD locations.The UAV altitudes are initialized randomly within the constraints.Source: 1) K-means initialization operator · p. 8

2) Variable dimension mechanism:

  • The variable-dimension mechanism adds power values for uncovered WDs so crossover and mutation can proceed when the covered-WD count changes.Those added power values do not participate in objective-function calculations.Source: 2) Variable dimension mechanism · pp. 8–9

B. Proposed NSGA-II-KV

  • The algorithm iterates crossover and mutation, combines parent and offspring populations, applies non-dominated and crowding sorting, and retains elites.The population is initialized using the K-means operator.Source: 2) Variable dimension mechanism · p. 9

C. Complexity and convergence analysis of NSGA-II-KV

NSGA-II-KV’s complexity is dominated by NSGA-II objective calculations, and the paper claims the algorithm is convergent. For UTTOP, it motivates evolutionary search and describes waypoint pretreatment for obstacle avoidance.

1) Analysis of complexity:

  • O(NP^2 · Gmax · I2) is the overall NSGA-II-KV complexity, exceeding the K-means initialization cost under the stated conditions.The comparison assumes NP > M and I2 > N · I1; I2 is the time to calculate the two objectives.Source: 1) Analysis of complexity · p. 9

2) Analysis of convergence:

  • The authors claim NSGA-II-KV is convergent, based on analysis of evolutionary algorithms for unimodal and multimodal functions.The cited analysis gives lemmas concerning the probability of locating a promising area and distance from the initial to the optimal solution.Source: 2) Analysis of convergence · p. 9

VI. ALGORITHM FOR UTTOP

  • Because constrained UTTOP is NP-hard and conventional PSO can fall into local dilemmas, the paper proposes pretreatment followed by PSO-NGDP.The paper presents evolutionary algorithms as an alternative for finding feasible solutions in limited time.Source: §VI · p. 9

A. Conventional PSO

  • Conventional PSO iteratively updates particle positions and velocities while retaining each particle’s best position and the global best position.The particle position represents a solution; the velocity describes its change.Source: A. Conventional PSO · p. 9

B. Pretreatment method

  • Pretreatment divides the route between adjacent hovering points into subspaces and projects misplaced waypoints to nearby virtual planes; under stated assumptions, the resulting trajectory avoids obstacles.The argument assumes all waypoints are above obstacles and K is sufficiently large.Source: B. Pretreatment method · p. 10

C. Proposed PSO-NGDP

PSO-NGDP extends conventional PSO with four mechanisms for constrained UTTOP. The mechanisms initialize and update waypoint solutions while seeking to address search direction, local optima, and population diversity.

C. Proposed PSO-NGDP

  • PSO-NGDP extends conventional PSO with normal-distribution initialization, a genetic mechanism, a differential mechanism, and a pursuit operator.The paper proposes it for the continuous constrained UTTOP.Source: C. Proposed PSO-NGDP · p. 10

1) Normal distribution initialization:

  • Normal-distribution initialization replaces random initialization to provide higher-quality starting solutions and potentially improve convergence speed.The waypoint coordinates are initialized using a Gaussian random number.Source: 1) Normal distribution initialization · p. 10

2) Genetic mechanism:

  • The genetic mechanism exchanges same-index waypoint coordinates between two particles, aiming to help PSO escape local dilemmas.The exchange occurs with a certain probability.Source: 2) Genetic mechanism · p. 10

3) Differential mechanism:

  • The differential mechanism combines PSO with mutation and greedy natural selection to generate alternative solutions, maintain population size, and select better particles.The paper also describes synchronously updating velocities while applying the position-update equations.Source: 3) Differential mechanism · pp. 10–11

4) Pursuit operator:

The pursuit operator updates waypoint solutions using individual and global best positions, with the stated aim of reducing flight distance during obstacle handling.

4) Pursuit operator:

  • The pursuit operator uses both the global and individual optimal positions to update waypoint solutions and reduce flight distance.It is embedded iteratively into the obstacle-handling method.Source: 4) Pursuit operator · p. 11
  • The paper places pursuit-based updates within an iterative algorithm for handling obstacles and updating waypoint coordinates.The algorithm description identifies the current iteration and maximum iteration.Source: 4) Pursuit operator · p. 11
  • The update uses random factors and the disparity between the individual and global best waypoints, with velocity bounded by vmax.The velocity bounds can be dynamically tuned.Source: 4) Pursuit operator · p. 11

D. Complexity and convergence analysis of PSO-NGDP

PSO-NGDP’s complexity is analyzed through its pretreatment and obstacle-handling procedures. Its stated total complexity is driven by the worst-case obstacle-handling loop across particles and iterations.

D. Complexity and convergence analysis of PSO-NGDP

  • O((Zmax − Zmin) · M · K · Gmax/C4) is the stated PSO-NGDP complexity.The analysis gives O(K) for pretreatment and a larger worst-case cost for obstacle handling across iterations.Source: 1) Analysis of complexity · p. 11
  • The obstacle-handling loop may run up to (Zmax − Zmin)/C4 times when the initial altitude is Zmin and obstacle altitude is near Zmax.This worst-case assumption is used to derive the per-iteration complexity.Source: 1) Analysis of complexity · p. 11
  • Each iteration initializes waypoint coordinates, applies crossover and mutation, updates solutions, handles collisions, and recalculates fitness.The listed procedure also updates individual and global best solutions.Source: 1) Analysis of complexity · p. 12

2) Analysis of convergence:

Across the tested scenarios, NSGA-II-KV performs best overall for UPAOP, while PSO-NGDP achieves the fastest convergence and best results for UTTOP. The simulations examine both algorithms across obstacle scenarios and network sizes.

2) Analysis of convergence:

VII. SIMULATION RESULTS

  • The simulations cover six obstacle scenarios in 500- and 1,000-device networks, using 10 or 20 hovering points and 50-member populations over 300 iterations.The modeled area is 500 m × 500 m × 30 m, with UAV altitude limits of 5 m and 30 m.Source: §VII · p. 12

A. Results of UPAOP

  • NSGA-II-KV’s solution distributions verify convergence across Scenarios 1–6, and each plotted hover point covers at least one device, so n · Pe does not affect f2.The solution-distribution plots are Fig. 7; the hover-point scheduling and coverage views are Fig. 8.Source: A. Results of UPAOP · p. 12, Figure 7 · p. 12, Figure 8 · p. 13
  • NSGA-II-KV performs best in small networks and Scenario 5, and leads on f1 but ranks second on f2 in large-network Scenarios 4 and 6.K-means leads on f2 in Scenarios 4 and 6 with minimum-altitude hovering, but obstacle avoidance can require higher flight and greater distance.Source: A. Results of UPAOP · pp. 12–13, Table II · p. 13
  • NSGA-II-KV obtains the overall best performance for UPAOP, with running times comparable to other algorithms except faster K-means.The comparison accounts for K-means performing worse in small networks and damaging f3 when obstacles require greater flying distance.Source: A. Results of UPAOP · p. 13, Table II · p. 13

B. Results of UTTOP

  • Across all six scenarios, PSO-NGDP converges fastest, gives the best UTTOP results, avoids obstacles, and yields the least flight energy consumption.Its improved performance comes with more CPU running time, which the authors note is less consequential for typically offline planning.Source: Figure 10 · p. 13, B. Results of UTTOP · pp. 13–14, Figure 11 · p. 14

C. Stability tests of NSGA-II-KV and PSO-NGDP

Stability tests favor NSGA-II-KV for UPAOP and PSO-NGDP for UTTOP. The paper also relates UAV speed and altitude choices to propulsion energy, charging range, and obstacle avoidance, and identifies near-real-time unknown-obstacle handling as future work.

C. Stability tests of NSGA-II-KV and PSO-NGDP

A. The influence of propulsion power of UAV

B. The rationality of the maximum and minimum altitudes of UAV

IX. CONCLUSION

  • The proposed algorithms outperform comparison algorithms for UPAOP and UTTOP in simulations; near-real-time avoidance of unknown obstacles is left for future work.The paper formulates joint power and 3D trajectory optimization, then divides it into UPAOP and UTTOP.Source: §IX · p. 15
Loading 2310.00384v1…