Content area
Full text
(ProQuest: ... denotes non-US-ASCII text omitted.)
Academic Editor:Li-Hsing Yen
Department of Computer Science, College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia
Received 29 December 2013; Revised 12 May 2014; Accepted 13 May 2014; 10 June 2014
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
A wireless sensor network (WSN) is a wireless network that consists of thousands of very small stations called sensor nodes. The main function of sensor nodes is to monitor, record, and notify a specific condition at various locations to other stations and end users. WSNs are increasingly attractive as a means to provide more advanced, intelligent, and context-aware systems with implicit user interaction. They have a wide range of application areas such as geophysical monitoring, precision agriculture, habitat monitoring, transportation, health, military systems, and business processes [1, 2].
WSNs pose their unique challenges due to the lack of a central entity for organization, the sensors' limitation, and mobility of the participants, as well as the limited range of wireless communications. Furthermore, in most of their applications, sensors are flexibly and quickly deployed with minimal effort, eliminating the need for physical backbone infrastructure [1, 2]. As each sensor node is tightly power constrained and one-off, the lifetime of a WSN is limited. In order to prolong the network lifetime, energy-efficient protocols should be designed for the characteristic of WSNs [2, 3]. An important research problem in wireless-sensing networking is to find a small set of nodes that can collaborate to form a self-organizing network to substitute for the absence of infrastructure and central control. This virtual backbone plays a significant role in enhancing the network efficiency, extending its lifetime, and supporting routing processes as well as all other network tasks and applications.
Connected dominating sets (CDSs) have been widely used for constructing virtual backbone in wireless networks. Using CDS, routing will be restricted to the reduced graph formed by the CDS. Every node in a CDS, called dominator, is considered as a gateway, and only a gateway needs to keep routing information. Other nodes, called dominatees, need not keep any routing information. Moreover,...