Blackbone2, an Efficient Deterministic Algorithm for creating 2-Connected m-dominating Set-based Backbones in Ad Hoc Networks


This paper introduces Blackbone2, a novel fully decentralized algorithm that aims at creating a robust backbone in ad hoc networks. Backbone robustness is supported by a 2-Connected $m$-dominating Set, $2,m$-CDS, and decentralization relies on the usage of two rules that only require two-hop knowledge in order to reduce the use of bandwidth. Blackbone2 deterministic approach guarantees a density-independent valid solution and is proved correct. The algorithm is also characterized by its efficient theoretical computation time, $mathcalO(Δ^2)$ with $Δ$ the average number of neighbors, which outperforms known solutions. The domination parameter, $m$, can be increased without changing the theoretical computation time. Efficiency of the Blackbone2 algorithm compared to the equivalent literature solutions is illustrated through simulations of a large panel of networks with a wide density range.

Proceedings of the Seventh ACM International Workshop on Mobility Management & Wireless Access