Optimal Algorithm for Connected Dominating Sets

Nannan Zhao; Muqing Wu

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

225 downloads

Cite: BibTeX Plain Text

@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 Zhao¹^,*, Muqing Wu¹^,*

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.

Keywords: WSN Connected Dominating Sets MESH CDS Localized distributive algorithm

Published: 2012-05-29

: http://dx.doi.org/10.1007/978-3-642-29157-9_33