Optimization of manet connectivity via smart deployment/movement of unmanned air vehicles

Abstract—Unmanned air vehicles (UAVs) can provide impor-tant communication advantages to ground-based wireless ad hoc networks. In this paper, the location and movement of UAVs are optimized to improve the connectivity of a wireless network. Four types of network connectivity are quantified: global mes-sage connectivity, worst-case connectivity, network bisection con-nectivity, and k-connectivity. The problems of UAV deployment and movement are formulated to improve the different types of connectivity. Both problems are NP-hard. For the deployment case, some heuristic adaptive schemes are proposed to yield simple but effective solutions. In addition, a closed-form solution for the two-node one-UAV case is provided. For k-connectivity, we propose an algorithm that improves connectivity using Delaunay triangulation. To optimize the UAV movement, an algorithm that tracks changes in the network topology is constructed. The simu-lation results show that by only deploying a single UAV, the global message network connectivity and the worst-case network connec-tivity can be improved by up to 109 % and 60%, respectively. The network bisection connectivity and the k-connectivity can also be significantly improved. Index Terms—Ad hoc network, network connectivity, unmanned air vehicle (UAV). I