An energy efficient MCDS construction algorithm for wireless sensor networks
- PDF / 390,827 Bytes
- 15 Pages / 595.28 x 793.7 pts Page_size
- 2 Downloads / 232 Views
RESEARCH
Open Access
An energy efficient MCDS construction algorithm for wireless sensor networks Qiang Tang1*, Kun Yang1,2, Ping Li1, Jianming Zhang1, Yuansheng Luo1 and Bing Xiong1
Abstract 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.33nkopt, 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. Keywords: wireless sensor networks (WSNS), topology control, connected dominating set (CDS), minimal CDS, approximation algorithm, energy efficiency
1. Introduction The design of wireless sensor networks (WSNs) [1] is a highly complicated task with substantial impact on the quality, cost, and efficiency of real-life sensor applications. The sensor nodes are small electronic devices with limited energy, memory, and transmit power capabilities, which in some sensor network applications are also limited in number because of their high cost [2]. A typical goal in these network designs is to form a longlived WSN, such that the sensor nodes, using their sensing capabilities and wireless transceivers, effectively cover a region of interest and forward important information to a common collection point, usually referred as data sink. Topology control is one way to optimize the network’s topology by removing redundant links and active nodes. Topology control can improve bandwidth utilization, delivery ratio, extend network lifetime, and reduce interference [3] and the packet retransmission [4]. The topology control has mainly two types [5]: power control and hierarchical topology control. Power control is to adjust * Correspondence: [email protected] 1 School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China Full list of author information is available at the end of the article
the transmission power of nodes to construct a graph with better properties, such as minimal interference and minimal packet transmission cost or to improve the robustness of the network topology. The hierarchical topology aims to construct a connected dominating set (CDS) for improving the routing performance and saving energy of the network. A CDS serves as a virtual backbone for wireless network where all nodes in the network are dominated by the CDS, and the packets are forwarded through the CDS from the s
Data Loading...
