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-indpendent valid solution and is proved correct. The algorithm is also characterized by its efficient theoretical computation time, Ο(Δ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.