Fast Deployment of UAV Networks for Optimal Wireless Coverage

Abstract

Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique to rapidly provide wireless coverage to a geographical area, where a flying UAV can be fast deployed to serve as cell site. Existing work on UAV-enabled wireless networks overlook the fast UAV deployment for wireless coverage, and such deployment problems have only been studied recently in sensor networks. Unlike sensors, UAVs should be deployed to the air and they are generally different in flying speed, operating altitude and wireless coverage radius. By considering such UAV heterogeneity to cover the whole target area, this paper studies two fast UAV deployment problems: one is to minimize the maximum deployment delay among all UAVs (min-max) for fairness consideration, and the other is to minimize the total deployment delay (min-sum) for efficiency consideration. We prove both min-max and min-sum problems are NP-complete in general. When dispatching UAVs from the same location, we present an optimal algorithm of low computational complexity $O(n^2)$ for the min-max problem. When UAVs are dispatched from different locations, we propose to preserve their location order during deployment and successfully design a fully polynomial time approximation scheme (FPTAS) of computation complexity $O(n^2\log \frac{1}{\epsilon })$ to arbitrarily approach the global optimum with relative error $\epsilon$. The min-sum problem is more challenging. When UAVs are dispatched from the same initial location, we present an approximation algorithm of linear time. As for the general case, we further reformulate it as a dynamic program and propose a pseudo polynomial-time algorithm to solve it optimally.

References in corpus (5)

• Ultra Reliable UAV Communication Using Altitude and Cooperation Diversity
• 3D Placement of an Unmanned Aerial Vehicle Base Station for Maximum Coverage of Users with Different QoS Requirements
• Fast Deployment of UAV Networks for Optimal Wireless Coverage
• Trajectory Optimization for Completion Time Minimization in UAV-Enabled Multicasting
• Mobile Unmanned Aerial Vehicles (UAVs) for Energy-Efficient Internet of Things Communications

Cited by in corpus (13)

• Fast Deployment of UAV Networks for Optimal Wireless Coverage
• Energy-saving deployment algorithms of UAV swarm for sustainable wireless coverage
• Multi-UAV Cooperative Trajectory for Servicing Dynamic Demands and Charging Battery
• Predictive Deployment of UAV Base Stations in Wireless Networks: Machine Learning Meets Contract Theory
• Trajectory Design and Power Control for Multi-UAV Assisted Wireless Networks: A Machine Learning Approach
• Reinforcement Learning in Multiple-UAV Networks: Deployment and Movement Design
• Adaptive Deployment for UAV-Aided Communication Networks
• Placement and Routing Optimization for Automated Inspection with UAVs: A Study in Offshore Wind Farm
• Strategic Learning Approach for Deploying UAV-provided Wireless Services
• MmWave UAV Networks with Multi-cell Association: Performance Limit and Optimization
• Learn to Fly: A Distributed Mechanism for Joint 3D Placement and Users Association in UAVs-assisted Networks
• Edge Computing Enabled by Unmanned Autonomous Vehicles
• Dynamic Pricing and Capacity Allocation of UAV-provided Mobile Services