Aerial Platform Placement Algorithms to Satisfy Connectivity, Capacity and Survivability Constraints in Wireless Ad-hoc Networks

In this paper, we address the problem of establishing full connectivity and satisfying required traffic capacity between disconnected clusters in large wireless ad-hoc ground networks by placing a minimum number of advantaged high flying Aerial Platforms (APs) as relay nodes at appropriate places. We also extend the connectivity solution in order to make the network survivable to a single AP failure. The problem of providing both connectivity and required capacity between disconnected ground clusters is formulated as a summation-form clustering problem with inter-AP distance constraints that make the AP network fully connected and with complexity costs that take care of cluster to AP capacity constraints. The resultant clustering problem is solved using Deterministic Annealing to find (near) globally optimal solutions for the minimum number and locations of the APs to establish full connectivity and provide required traffic capacity between disconnected clusters. In order to make the network single AP survivable, the connectivity solution is extended so that each AP connects to at least two neighboring APs and each ground cluster connects to at least two APs. We establish the validity of our algorithms by comparing it with optimal exhaustive search algorithms and show that our algorithms are near-optimal for the problem of establishing connectivity between disconnected clusters.