An improved distributed algorithm for connected dominating sets in wireless ad hoc networks

被引：0

作者：

Liu, Hui ^{[2
]}

Pan, Yi ^{[1
]}

Cao, Jiannong ^{[2
]}

机构：

[1] Department of Computer Science, Georgia State University, Atlanta, GA 30303, United States

[2] Department of Computing, Hong Kong Polytechnic University, Hong Kong, Hong Kong

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2004年 / 3358卷

基金：

中国国家自然科学基金;

关键词：

D O I：

10.1007/978-3-540-30566-8_41

中图分类号：

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

学科分类号：

0812 ;

摘要：

The idea of virtual backbone routing has been proposed for efficient routing among a set of mobile nodes in wireless ad hoc networks. Virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is a NP-hard problem. We propose a distributed, 3-phase protocol for calculating the CDS in this paper. Our new protocol largely reduces the number of nodes in CDS compared with Wu and Li's method, while message and time complexities of our approach remain almost the same as those of Wu and Li's method. We conduct extensive simulations and show our protocol can consistently outperform Wu and Li's method. The correctness of our protocol is proved through theoretical analysis. © Springer-Verlag Berlin Heidelberg 2004.

引用

页码：340 / 351

共 50 条

[41] Efficient Localized Protocols to Compute Connected Dominating Sets for Ad Hoc Networks
Almahorg, Khalid Ateyia M.
Naik, Sagar
Shen, Xuemin
2010 IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE GLOBECOM 2010, 2010,
[42] An efficient algorithm for constructing connected dominating set in Ad Hoc networks
Yin, Bolian
Shi, Hongchi
Shang, Yi
2007 4TH IEEE CONSUMER COMMUNICATIONS AND NETWORKING CONFERENCE, VOLS 1-3, 2007, : 244 - 248
[43] Routing in ad-hoc networks using minimum connected dominating sets
Das, B
Bharghavan, V
ICC'97: 1997 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS - TOWARDS THE KNOWLEDGE MILLENNIUM, CONFERENCE RECORD - VOLS 1-3, 1997, : 376 - 380
[44] An efficient algorithm for finding an almost connected dominating set of small size on wireless ad hoc networks
Li, Yamin
Peng, Shietung
Chu, Wanming
2006 IEEE INTERNATIONAL CONFERENCE ON MOBILE ADHOC AND SENSOR SYSTEMS, VOLS 1 AND 2, 2006, : 119 - +
[45] Constructing Minimum Connected Dominating Sets with Constant Update Time in Wireless Ad-hoc Sensor Networks
Ren, Sijun
Yi, Ping
Lin, Zhuqiulong
Guo, Chenxi
Wu, Yue
2014 IEEE 17TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND ENGINEERING (CSE), 2014, : 1570 - 1576
[46] Distributed algorithm for power aware connected dominating set for efficient routing in mobile Ad hoc networks
Bhattacharjee, Subhasis
Tripathi, Joydeep
Mistry, Oly
Dattagupta, Jayasree
2006 INTERNATIONAL SYMPOSIUM ON AD HOC AND UBIQUITOUS COMPUTING, 2007, : 66 - +
[47] Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets
Wu, H
Wu, B
Stojmenovic, I
PROCEEDINGS OF THE IASTED INTERNATIONAL CONFERENCE ON WIRELESS AND OPTICAL COMMUNICATIONS, 2002, : 668 - 673
[48] Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets
Wu, J
Wu, B
Stojmenovic, I
WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2003, 3 (04): : 425 - 438
[49] Distributed Generation of a Family of Connected Dominating Sets in Wireless Sensor Networks
Islam, Kamrul
Akl, Selim G.
Meijer, Henk
DISTRIBUTED COMPUTING IN SENSOR SYSTEMS, PROCEEDINGS, 2009, 5516 : 343 - 355
[50] An Improved Greedy Construction of Minimum Connected Dominating Sets in Wireless Networks
Das, Ariyam
Mandal, Chittaranjan
Reade, Chris
Aasawat, Manish
2011 IEEE WIRELESS COMMUNICATIONS AND NETWORKING CONFERENCE (WCNC), 2011, : 790 - 795

← 1 2 3 4 5 →