Date Added: Mar 2012
In wireless sensor network, a Connected Dominating Set (CDS) can be used as a virtual backbone for efficient routing. Constructing a Minimal CDS (MCDS) is good for packet routing and energy efficiency, but is an NP-hard problem. In this paper, an efficient approximation MCDS construction algorithm E-MCDS (Energy efficient MCDS construction algorithm) is proposed which explicitly takes energy consumption into account. E-MCDS contains two stages: the CDS construction stage and the pruning stage. The constructed CDS is approximately composed of two Independent Sets (IS).