Three connected dominating set algorithms for wireless sensor networks
by Najla Al-Nabhan; Bowu Zhang; Xiuzhen Cheng; Mznah Al-Rodhaan; Abdullah Al-Dhelaan
International Journal of Sensor Networks (IJSNET), Vol. 21, No. 1, 2016

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.

Online publication date: Sat, 04-Jun-2016

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Sensor Networks (IJSNET):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email