Journal Article

An energy efficient MCDS construction algorithm for wireless sensor networks

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

2012

Overview

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.33 opt and 17.33 n 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.

• Publisher: Springer International Publishing,Springer Nature B.V
• Subject: Algorithms / Cadmium sulfides / Communications Engineering / Computer networks / Construction / Disks / Energy management / Engineering / Information Systems Applications (incl.Internet) / Networks / Remote sensors / Routing (telecommunications) / Signal,Image and Speech Processing / Topology Control in Wireless Ad Hoc and Sensor Networks