An improved distributed algorithm for connected dominating sets in wireless ad hoc networks
The idea of virtual backbone routing has been proposed for efficient routing among a set of mobile nodes in wireless ad hoc networks. Virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is a NP-hard problem. We propose a distributed, 3-phase protocol for calculating the CDS in this paper. Our new protocol largely reduces the number of nodes in CDS compared with Wu and Li's method, while message and time complexities of our approach remain almost the same as those of Wu and Li's method. We conduct extensive simulations and show our protocol can consistently outperform Wu and Li's method. The correctness of our protocol is proved through theoretical analysis.
Liu, Hui, Yi Pan, and Jiannong Cao. "An improved distributed algorithm for connected dominating sets in wireless ad hoc networks." In International Symposium on Parallel and Distributed Processing and Applications, pp. 340-351. Springer, Berlin, Heidelberg, 2004.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)