Multi-Unmanned Aerial Vehicle (UAV) Networks is a promising solution to providing wireless coverage to ground users in challenging rural areas (such as Internet of Things (IoT) devices in farmlands), where the traditional cellular networks are sparse or unavailable. A key challenge in such networks is the 3D placement of all UAV base stations such that the formed Multi-UAV Network (i) utilizes a minimum number of UAVs while ensuring -- (ii) backhaul connectivity directly (or via other UAVs) to the nearby terrestrial base station, and (iii) wireless coverage to all ground users in the area of operation. This joint Backhaul-and-coverage-aware Drone Deployment (BoaRD) problem is largely unaddressed in the literature, and, thus, is the focus of the paper. We first formulate the BoaRD problem as Integer Linear Programming (ILP). However, the problem is NP-hard, and therefore, we propose a low complexity algorithm with a provable performance guarantee to solve the problem efficiently. Our simulation study shows that the Proposed algorithm performs very close to that of the Optimal algorithm (solved using ILP solver) for smaller scenarios. For larger scenarios, the proposed algorithm greatly outperforms the baseline approaches -- backhaul-aware greedy and random algorithm, respectively by up to 17% and 95% in utilizing fewer UAVs while ensuring 100% ground user coverage and backhaul connectivity for all deployed UAVs across all considered simulation setting.
翻译:多无人驾驶航空飞行器(UAV)网络是向具有挑战性的农村地区的地面用户提供无线覆盖(如在农地的互联网(IOT)装置)的无线覆盖的一个有希望的解决办法,因为传统的蜂窝网络是稀少或没有的。这种网络中的一个关键挑战是所有UAV基地站的3D位置,例如,已经建立的多无人驾驶航空飞行器网络(i)使用最低数量的UAV,同时确保 -- (ii) 直接(或通过其他无人驾驶飞行器)与附近的地面基地站的回航连接,(iii) 向行动地区的所有地面用户提供无线覆盖。这个联合的回程和隐蔽的Drone部署(BoARD)问题基本上在文献中解决了,因此是文件的焦点。我们首先将BoARD问题作为Integer Linear 程序(ILP) 来设计一个最小数量的UAVAV(IL) 。然而,我们提出一个低复杂性的算法,以有效解决问题。我们的模拟研究显示,拟议的算法在最大范围内进行更小的AVAVIL(S)的基底局和最小的推算法(S),同时使用最小的推算法,用最小的17的推算法(S)。