WSN19-4: Efficient Construction of Weakly-Connected Dominating Set for Clustering Wireless Ad Hoc Networks
Bo Han, Weijia Jia · Globecom · 2006
In most of the proposed clustering algorithms for wireless ad hoc networks, the cluster-heads form a dominating set in the network topology. A variant ofdominatingsetwhich is more suitable for cluster formation is theweakly-connecteddominatingset(WCDS). We propose an area based distributed algorithm for WCDS formation with time and message complexityO(n). In thisAreaalgorithm, we partition the wireless nodes into different areas, use some deterministic criteria to select the nodes for the WCDS in each area and adjust the area borders by adding additional nodes to the final WCDS. The effectiveness of our algorithm is confirmed through analysis and comprehensive simulation study.