Progressive ad-hoc route reconstruction using distributed UAV relays after a large-scale failure

In this paper, we address a route reconstruction problem using Unmanned Aerial Vehicles (UAVs) after a large-scale disaster where stationary ad-hoc networks are severely destructed. The main goal of this paper is to improve routing performance in a progressive manner by reconnecting partitioned networks through dispatched UAV relays. Our proposed algorithm uses two types of UAVs: global and local UAVs to collaboratively find the best deployment position in a dynamically changing environment. To obtain terrestrial network connectivity information and extract high-level network topology, we exploit the concept of strongly connected component in graph theory. Based on the understanding from a global point view, global UAVs recommend the most effective deployment positions to local UAVs so that they are deployed as relays in more critically disrupted areas. Simulation-based experiments validate that our distributed route reconstruction algorithm outperforms a counterpart algorithm in terms of steady-state and dynamic routing performance.