Fast Deployment of UAV Networks for Optimal Wireless Coverage
Fast Deployment of UAV Networks for Optimal Wireless Coverage
复制标题
DOI：
10.1109/tmc.2018.2840143
复制
发表时间：
2019-03-01
影响因子：
7.9
通讯作者：
Duan, Lingjie
中科院分区：
文献类型：
--
作者：
Zhang, Xiao;Duan, Lingjie
无人机（UAV）网络已经成为一种有前途的技术，以快速地向地理区域提供无线覆盖，其中飞行的UAV可以快速地部署以用作小区站点。现有的工作无人机使能的无线网络忽略了快速无人机部署无线覆盖，这样的部署问题最近才被研究在传感器网络。与传感器不同，无人机应部署到空中，它们在飞行速度，操作高度和无线覆盖半径方面通常不同。考虑到无人机的异构性，以覆盖整个目标区域为目标，研究了两个无人机快速部署问题：一个是基于公平性考虑的最大部署时延最小化问题（min-max），另一个是基于效率考虑的总部署时延最小化问题（min-sum）。我们证明了min-max和min-sum问题在一般情况下都是NP-完全的。当无人机在同一地点进行调度时，我们提出了一个计算复杂度为O（n（2））的min-max问题的优化算法。当无人机从不同的位置被派遣时，我们提出在部署过程中保持它们的位置顺序，并成功地设计了一个计算复杂度为O（n（2）log 1/n）的全多项式时间近似方案（FPTAS），以相对误差n/n任意逼近全局最优值。最小和问题更具挑战性。当无人机从同一初始位置出发时，提出了一种线性时间近似算法。对于一般情况，我们进一步将其转化为一个动态规划，并提出了一个伪多项式时间算法来最优求解。
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 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.