A Placement Algorithm for Enhanced Connectivity and Reliability in Wireless Ad-hoc Networks

In this paper we address the problem of providing full connectivity in large (wide area) ad hoc networks by placing advantaged nodes like UAVs (as relay nodes) in appropriate places. We provide a formulation where we can treat the connectivity problem as a clustering problem with a summation-form distortion function. We then adapt the Deterministic Annealing clustering algorithm to our formulation and using that, we and the minimum number and also locations of the UAVs required to provide full connectivity between all nodes.Furthermore, we describe enhancements that can be used to extend the basic connectivity problem to support notions of reliable connectivity that can lead to improved network performance. We establish the validity of our algorithm and compare its performance with optimal (exhaustive search) as well as non-optimal (hard clustering) algorithms. We show that our algorithm is near optimal both for the basic connectivity problem as well as extended notions of connectivity.