Energy-Saving Deployment Algorithms of UAV Swarm for Sustainable Wireless Coverage

Recent years have witnessed increasingly more uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users. Each UAV is constrained in its energy storage and wireless coverage, and it consumesmost energy on flying to the top of the target area, thus leaving limited leftover energy for hovering at its deployed position and keeping wireless coverage. The literature largely overlooks the sustainability issues of deploying UAV swarm and the UAV-to-UAV cooperation, and we aim to maximize the minimum leftover energy storage among all the UAVs after their deployment. Our new energy-saving deployment problem captures that each UAV's wireless coverage is adjustable by its service altitude, and also takes the no-fly-zone (NFZ) constraint into account. We show that a UAV with larger initial energy storage in theUAVswarm should be deployed further away from the UAV station, and we propose an optimal energysaving deployment algorithm by jointly balancing heterogeneous UAVs' flying distances on the ground and final service altitudes in the sky. When n UAVs with different initial energy storages are dispatched from different initial locations, we prove this problem is NP-hard in general by reduction from partition problem. Despite of this, we propose to preserve the UAVs' location order and successfully design an approximation algorithm of complexity n log 1/epsilon to arbitrarily approach the optimum with error epsilon. Inspiring by this proposed (1 - epsilon)-approximation algorithm, we present a heuristic algorithm to solve the general case by balancing the efficiency and computation complexity well.