UAVs Deployment Algorithms for Maximizing Backhaul Flow

This paper considers topology construction or design using unmanned aerial vehicles (UAVs) in order to maximize the traffic flow from a given source to a destination node. To this end, it outlines a mixed integer linear program (MILP) to optimize the placement of UAVs, and routing of flow from the said source to the destination. The problem is very challenging because the MILP requires an exhaustive collection of topologies, which increases exponentially with the number of UAVs and potential UAVs placement locations. To this end, this paper outlines two novel methods. The first is a heuristic centralized method called Distance-Based Location Selection (DBLS) that generates a subset of topologies to reduce the search space of the said MILP. The second method is a distributed Gibbs sampling based protocol (DGSP) that allows each UAV to determine its location iteratively and independently. Our results show that DBLS and DGSP achieve respectively $85\%$ and $72\%$ of the optimal maximum flow.