Wireless Communications and Applications. First International Conference, ICWCA 2011, Sanya, China, August 1-3, 2011, Revised Selected Papers

Research Article

Optimal Algorithm for Connected Dominating Sets

Download
228 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-29157-9_33,
        author={Nannan Zhao and Muqing Wu},
        title={Optimal Algorithm for Connected Dominating Sets},
        proceedings={Wireless Communications and Applications. First International Conference, ICWCA 2011, Sanya, China, August 1-3, 2011, Revised Selected Papers},
        proceedings_a={ICWCA},
        year={2012},
        month={5},
        keywords={WSN Connected Dominating Sets MESH CDS Localized distributive algorithm},
        doi={10.1007/978-3-642-29157-9_33}
    }
    
  • Nannan Zhao
    Muqing Wu
    Year: 2012
    Optimal Algorithm for Connected Dominating Sets
    ICWCA
    Springer
    DOI: 10.1007/978-3-642-29157-9_33
Nannan Zhao1,*, Muqing Wu1,*
  • 1: Beijing University of Posts and Telecommunications
*Contact email: znn812@gmail.com, wumuqing@bupt.edu.cn

Abstract

There is no infrastructure in most energy constrained networks, such as WSN. Connected Dominating Set (CDS) has been proposed as virtual backbone. The CDS pays the way for routing, data aggregation and activity scheduling. In order to reduce the backbone size and prolong the lifetime of networks, it is desirable to construct a Minimum CDS (MCDS). Unfortunately, it is a NP-hard problem with a distribute manner. In this paper, a distributive algorithm for MESH CDS is introduced. Theoretical analysis and simulation results are also presented to verify the efficiency of our algorithm.