Paper Info
Title
Distributed Algorithm for Connected Dominating Set Construction in Sensor Networks
Abstract
Future Wireless Sensor Networks (WSNs) will be composed of a large number of densely deployed sensors. A key feature of such networks is that their nodes are untethered and unattended. Distributed techniques are expected in WSNs. Connected Dominating Sets (CDSs) have been widely used for virtual backbone construction in WSNs to control topology, facilitate routing, and extend network lifetime. This paper proposes a new distributed algorithm for CDS construction in WSNs. The algorithm represents an extension for our previously proposed centralized algorithm. The algorithm is intended to construct a CDS with the smallest ratio when compared to its centralized version. Simulation shows that our distributed approach has a maximum ratio of 1.53 to the centralized approach in term of CDS size, and it satisfies all of the geometrical properties of its canalized version. Based on this ratio, this distributed algorithm has an approximation factor of 7.65 to the optimal CDS. This approximation outperforms the existing distributed CDS construction algorithms.
Year
DOI
Venue
2013
10.1109/SMC.2013.467
SMC
Keywords
Field
DocType
centralized algorithm,cds size,cds construction,sensor networks,optimal cds,connected dominating set construction,smallest ratio,centralized approach,virtual backbone construction,maximum ratio,centralized version,cds construction algorithm,wireless sensor networks,approximation theory
Graph theory,Key distribution in wireless sensor networks,Computer science,Brooks–Iyengar algorithm,Approximation theory,Computer network,Distributed algorithm,Connected dominating set,Wireless sensor network,Distributed computing
Conference
ISSN
Citations 
PageRank 
1062-922X
1
0.36
References 
Authors
7
4
Name
Order
Citations
PageRank
Najla Al-Nabhan1196.49
Mznah Al-Rodhaan230622.90
Abdullah Al-Dhelaan352339.77
Xiuzhen Cheng43238210.23