Constructing a self-stabilizing CDS with bounded diameter in wireless networks under SINR
作者： Jiguo Yu , Xueli Ning , Yunchuan Sun , Shengling Wang , Wang
DOI: 10.1109/INFOCOM.2017.8057225
关键词: Distributed algorithm 、 Topology control 、 Signal-to-interference-plus-noise ratio 、 Approximation algorithm 、 Algorithm design 、 Asymptotically optimal algorithm 、 Wireless sensor network 、 Mathematical optimization 、 Wireless network 、 Computer science 、 Topology
摘要: As a virtual backbone structure, connected dominating sets (CDSs) play an important role in topology control for wireless networks. In this paper, we develop distributed self-stabilizing CDS construction algorithm under the SINR model (also known as physical interference model), more practical yet challenging design. Specifically, propose randomized that can construct O (log n) timeslots with high probability, where n is total number of nodes network. The constructed achieves constant approximation both density and diameter. To best our knowledge, first asymptotically optimal result terms diameter model.
sci-hub.se 参考文章(29)
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
SAYAKA KAMEI, HIROTSUGU KAKUGAWA, A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET International Journal of Foundations of Computer Science. ,vol. 21, pp. 459- 476 ,(2010) , 10.1142/S0129054110007362
Devdatt Dubhashi, Jaikumar Radhakrishnan, Arvind Srinivasan, Alessandro Mei, Alessandro Panconesi, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons symposium on discrete algorithms. ,vol. 2003, pp. 717- 724 ,(2003) , 10.5555/644108.644226
Austin Buchanan, Je Sang Sung, Vladimir Boginski, Sergiy Butenko, On connected dominating sets of restricted diameter European Journal of Operational Research. ,vol. 236, pp. 410- 418 ,(2014) , 10.1016/J.EJOR.2013.11.036
Magnus M. Halldorsson, Yuexuan Wang, Dongxiao Yu, Leveraging Multiple Channels in Ad Hoc Networks principles of distributed computing. pp. 431- 440 ,(2015) , 10.1145/2767386.2767437
Christian Scheideler, Andrea Richa, Paolo Santi, An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing - MobiHoc '08. pp. 91- 100 ,(2008) , 10.1145/1374618.1374632
Zeng Yuanyuan, Xiaohua Jia, He Yanxiang, Energy efficient distributed connected dominating sets construction in wireless sensor networks international conference on wireless communications and mobile computing. pp. 797- 802 ,(2006) , 10.1145/1143549.1143709
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
Peng-Jun Wan, K.M. Alzoubi, O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks international conference on computer communications. ,vol. 3, pp. 1597- 1604 ,(2002) , 10.1109/INFCOM.2002.1019411
Jie Wu, Fei Dai, Ming Gao, Ivan Stojmenovic, On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks Journal of Communications and Networks. ,vol. 4, pp. 59- 70 ,(2002) , 10.1109/JCN.2002.6596934