An energy efficient MCDS construction algorithm for wireless sensor networks

作     者：Tang, Qiang Yang, Kun Li, Ping Zhang, Jianming Luo, Yuansheng Xiong, Bing 

作者机构：Changsha Univ Sci & Technol Sch Comp & Commun Engn Changsha Hunan Peoples R China Univ Essex Sch Comp Sci & Elect Engn Colchester CO4 3SQ Essex England 

出 版 物：《EURASIP JOURNAL ON WIRELESS COMMUNICATIONS AND NETWORKING》 (EURASIP无线通信与网络杂志)

年 卷 期：2012年第2012卷第1期

页      面：1-15页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主　　题：wireless sensor networks (WSNS) topology control connected dominating set (CDS) minimal CDS approximation algorithm energy efficiency 

摘      要：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 article, 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). The performance ratio of E-MCDS is analysed in both unit disk graph and disk graphs with bidirectional links, being 9.33opt and 17.33n(k)opt, respectively. The message complexity of E-MCDS is O(n). The simulation results have shown that E-MCDS performs well both in terms of the size of CDS constructed and the energy efficiency.