Distributed Algorithm for Connected Dominating Set Construction in Sensor Networks

被引：5

作者：

Al-Nabhan, Najla ^{[1
]}

Al-Rodhaan, Mznah ^{[1
]}

Al-Dhelaan, Abdullah ^{[1
]}

Cheng, Xiuzhen ^{[2
]}

机构：

[1] King Saud Univ, Dept Comp Sci, Riyadh, Saudi Arabia

[2] George Washington Univ, Dept Comp Sci, Washington, DC USA

来源：

2013 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC 2013) | 2013年

关键词：

distributed algorithms; cooperative algorithms; wireless sensor networks; distributed systems; graph theory; virtual backbone;

D O I：

10.1109/SMC.2013.467

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：4450 / 4455

页数：6

共 13 条

[1]

Al-Nabhan N., 2013, INT J SENSO IN PRESS

[2] Connected dominating set algorithms for wireless sensor networks [J].

Al-Nabhan, Najla ;

Al-Rodhaan, Mznah ;

Al-Dhelaan, Abdullah ;

Cheng, Xiuzhen .

INTERNATIONAL JOURNAL OF SENSOR NETWORKS, 2013, 13 (02) :121-134

[3]

Al-Nabhan N, 2012, LECT NOTES COMPUT SC, V7405, P705, DOI 10.1007/978-3-642-31869-6_62

[4]

Alzoubi K. M., 2002, Proceedings of the 35th Annual Hawaii International Conference on System Sciences, P3849, DOI 10.1109/HICSS.2002.994519

[5]

Alzoubi K. M., 2002, MOB AD HOC NETW COMP

[6]

[Anonymous], NSF INT WORKSH THEOR

[7]

Blum J, 2005, HDB COMBINATORIAL OP, P329

[8]

Li Y., 2005, WIRELESS COMMUNICATI, V5

[9]

Liu Z., 2010, Information Technology Journal, V9, P864, DOI 10.3923/itj.2010.864.876

[10]

Poe W.Y., 2009, P ASIAN INTERNET ENG, P77, DOI DOI 10.1145/1711113.1711127

← 1 2 →