An Asynchronous Distributed Algorithm for Constructing a Connected Dominating Set Optimized by Minimum-Weight Spanning Tree

摘要

A Connected Dominating Set (CDS) performs a vital role in wireless ad-hoc sensor networks, which can establish a virtual backbone and thus leads to less maintenance overhead and information exchanges in wireless communications. In this paper, our algorithm first finds a prior CDS and then uses the Minimum-Weight Spanning Tree (MST) to optimize the result. Our algorithm applies effective degree, the new term introduced in our algorithm, as the criterion to select the dominators in prior CDS construction. By 3-hop message relay combining with some rules, the selective paths to connect any two dominators within 3-hop distance can be recognized as the edges associated with respective weight by calculating the number of nodes over these paths. Thus, the graph induced by the prior CDS can be subtly converted to a weight graph. And then an MST can be found from this weight graph to further reduce the CDS size. The process of constructing the ultima CDS is continuous, parallel, above all, also totally asynchronous. We also analyse some useful structural properties of CDS generated by our algorithm. Extensive simulations are also implemented to further evaluate the performance of our algorithm by comparing with the existing algorithms. The simulation shows that in average our algorithm generates a CDS not only with smaller Average Hop Distance (AHD) but CDS size. The simulation also shows that it is more energy efficient than others in prolonging network lifetime.