Topology Design Algorithms for Maximizing Flows in Multi-Hop UAVs Networks

Thanks to the rapid advancements in wireless communications, sensors, and electronics, Unmanned Aerial Vehicles (UAVs) have become more and more popular in communication systems. In particular, motivated by their versatility, low deployment cost, and networking capability, a swarm of UAVs can construct a multi-hop wireless network to connect remote or isolated ground users to the Internet, and thereby improve the coverage of existing communication networks. In addition to improving the capacity and coverage of communication networks, UAVs can also provide in-situ computing services. For example, UAVs can act as mobile servers in Multi-Access Edge Computing (MEC) systems. Moreover, with the advancement of Network Function Virtualization (NFV) technology, UAVs can host Virtualized Network Functions (VNFs) to process incoming traffic that belongs to different users.

Henceforth, this thesis aims to address topology construction problems where it considers placing UAVs to create a wireless backhaul that meets the following objectives: (i) maximum flow, or (ii) maximum computed flow. Objective (i) concerns the maximum amount of traffic between one or more source-destination pairs. In this respect, this thesis considers two scenarios. The first scenario contains homogeneous quad-rotor UAVs. The problem at hand is to determine the hovering location of a set of quad-rotor UAVs to create a multi-hop wireless backhaul that maximizes the flow rate between a source and destination ground node pair. In this regard, it outlines a mixed integer linear problem (MILP) to select the optimal location of UAVs and determine the amount of flow on each constructed link. Further, it presents a heuristic algorithm to place UAVs according to their distance to the destination node. Moreover, a distributed solution based on Gibbs sampling is also introduced to allow each UAV to learn its location independently. The simulation results show that the proposed heuristic algorithm and the distributed solution achieve respectively 85% and 72% of the optimal maximum flow.