Title: Three connected dominating set algorithms for wireless sensor networks

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

Addresses: Department of Computer Science, King Saud University, Riyadh 11682, Saudi Arabia ' Department of Mathematics and Computer Systems, Mercyhurst University, Erie, PA 16546, USA ' Department of Computer Science, The George Washington University, Washington DC 20052, USA ' Department of Computer Science, King Saud University, Riyadh 11543, Saudi Arabia ' Department of Computer Science, King Saud University, Riyadh 11543, Saudi Arabia

Abstract: Computing connected dominating sets (CDSs) have been widely used to construct virtual backbones in wireless sensor networks, in order to control topology, facilitate routing and extend network lifetime. Constructing a minimum CDS is an NP-hard problem. For any CDS algorithm, the size of the constructed CDS is usually considered to be the most important performance factor. In this paper, we propose three novel algorithms to construct CDS in wireless sensor networks. The algorithms are intended to generate a small CDS. The first algorithm has a performance factor of 5 from the optimal solution. This approximation outperforms the existing state-of-the-art approaches. The other two algorithms are variations of the first algorithm with performance improvements. We include the performance analysis and simulation results that show the effectiveness of our algorithms in reducing the CDS size.

Keywords: connected dominating sets; CDS; wireless sensor networks; WSNs; maximal independent set; MIS; approximation algorithms; greedy algorithms; graph theory; virtual backbone; topology control; routing; network lifetime.

DOI: 10.1504/IJSNET.2016.076855

International Journal of Sensor Networks, 2016 Vol.21 No.1, pp.53 - 66

Received: 23 Sep 2013
Accepted: 02 Oct 2013
Published online: 04 Jun 2016 *

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