Distributed construction of connected dominating set in wireless ad hoc networks
作者： Peng-Jun Wan , Khaled M. Alzoubi , Ophir Frieder
DOI: 10.1023/B:MONE.0000013625.87793.13
关键词:
摘要: Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None these constant factors. Thus cannot guarantee to generate a CDS small size. Their message complexities can be high O(n2), and time may also large O(n2) O(n3). We then present our own algorithm that outperforms existing algorithms. This an factor at most 8, O(n) complexity O(n log n) complexity. By establishing Ω(n lower bound on any nontrivial CDS, is thus message-optimal.
springer.com
acm.org
sci-hub.se 参考文章(9)
B. Das, R. Sivakumar, V. Bharghavan, Routing in ad hoc networks using a spine international conference on computer communications and networks. pp. 34- 39 ,(1997) , 10.1109/ICCCN.1997.623288
Israel Cidon, Osnat Mokryn, Propagation and Leader Election in a Multihop Broadcast Environment international symposium on distributed computing. pp. 104- 118 ,(1998) , 10.1007/BFB0056477
Jie Wu, Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks international workshop on discrete algorithms and methods for mobile computing and communications. pp. 7- 14 ,(1999) , 10.1145/313239.313261
Brent N. Clark, Charles J. Colbourn, David S. Johnson, Unit disk graphs Discrete Mathematics. ,vol. 86, pp. 165- 177 ,(1991) , 10.1016/0012-365X(90)90358-O
Mario Gerla, Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network Wireless Networks. ,vol. 1, pp. 255- 265 ,(1995) , 10.1007/BF01200845
B. Das, V. Bharghavan, Routing in ad-hoc networks using minimum connected dominating sets international conference on communications. ,vol. 1, pp. 376- 380 ,(1997) , 10.1109/ICC.1997.605303
V. Chvatal, A Greedy Heuristic for the Set-Covering Problem Mathematics of Operations Research. ,vol. 4, pp. 233- 235 ,(1979) , 10.1287/MOOR.4.3.233
C.R. Lin, M. Gerla, Adaptive clustering for mobile wireless networks IEEE Journal on Selected Areas in Communications. ,vol. 15, pp. 1265- 1275 ,(1997) , 10.1109/49.622910
I. Stojmenovic, M. Seddigh, J. Zunic, Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks IEEE Transactions on Parallel and Distributed Systems. ,vol. 13, pp. 14- 25 ,(2002) , 10.1109/71.980024