Title: Connected dominating set algorithms for wireless sensor networks

Authors: Najla Al-Nabhan; Mznah Al-Rodhaan; Abdullah Al-Dhelaan; Xiuzhen Cheng

Addresses: Department of Computer Science, King Saud University, Riyadh, Saudi Arabia ' Department of Computer Science, King Saud University, Riyadh, Saudi Arabia ' Department of Computer Science, King Saud University, Riyadh, Saudi Arabia ' Computer Science Department, The George Washington University, Washington DC, USA

Abstract: Wireless Sensor Networks (WSNs) are gaining more interest in a variety of applications. Of their different characteristics and challenges, network management and lifetime elongation are the most considered issues in WSN based systems. Connected Dominating Set (CDS) is known to be an efficient strategy to control network topology, reduce overhead, and extend network lifetime. Designing a CDS algorithm for WSNs is very challenging. This paper provides a review on connected dominating set construction techniques for wireless sensor networks.

Keywords: CDS; connected dominating sets; wireless sensor networks; WSNs; virtual backbone; maximal independent set; unit disk graph; approximation algorithms; network topology; overhead reduction; network lifetime.

DOI: 10.1504/IJSNET.2013.053719

International Journal of Sensor Networks, 2013 Vol.13 No.2, pp.121 - 134

Received: 13 Nov 2012
Accepted: 16 Jan 2013

Published online: 05 May 2013 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article