Adaptive $ D$-Hop Connected Dominating Set in Highly Dynamic Flying Ad-Hoc Networks

Abstract

By exploring the intelligent cooperation of unmanned aerial vehicle (UAV) swarms, the formed flying ad-hoc networks (FANETs) can support a variety of collaborative operations with real-time communications in emergency scenarios. To reduce the prohibitively high routing overhead with the connectivity guaranteed of multi-hop links, UAV swarms can construct a virtual backbone network (VBN) based on the graph-theoretical <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -hop connected dominating set ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -CDS), where each UAV outside VBN can send collected data to VBN within <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -hop distance. However, due to the high dynamics of FANETs in emergency scenarios, the optimal solution may not match the current status, which results in frequently intermittent connectivity. Besides, recomputing the solution from scratch will lead to significant maintance costs. Therefore, it is crucial to adapt the minimal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -CDS to topology changes. To this end, we propose an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \mathcal {O}(d\log (N))$</tex-math></inline-formula> -approximation algorithm (i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ N$</tex-math></inline-formula> denotes the maximal number of nodes) with expected <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \mathcal {\widetilde{O}}(d\Delta ^2)$</tex-math></inline-formula> (i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ \Delta$</tex-math></inline-formula> denotes the maximal degree of a vertex over the sequence of updates) time per update. The simulation results demonstrate that our adaptive solution can strike a better trade-off among the routing overhead, response time, and maintance costs per topology update compared with state-of-the-art schemes in emergency scenarios.