Approximation algorithm for minimum weight fault-tolerant virtual backbone in homogeneous wireless sensor network
作者： Zhao Zhang , Yishuo Shi
DOI: 10.1109/INFOCOM.2015.7218481
关键词:
摘要: In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that fault-tolerant. Such consideration leads problem of finding minimum weight k-connected m-fold dominating set ((k, m)-MWCDS for short). this paper, we give (α + 2.5ρ)-approximation (2, with m ≥ 2 in unit disk graph, where α performance ratio problem, and ρ {0,1,2}-Steiner Network Design problem. view currently best known ratios ρ, has (9 e)-approximation 3 (8 =2, e arbitrary positive real number.
sci-hub.se 参考文章(39)
Weili Wu, Hongwei Du, Xiaohua Jia, Yingshu Li, Scott C.-H. Huang, Minimum connected dominating sets and maximal independent sets in unit disk graphs Theoretical Computer Science. ,vol. 352, pp. 1- 7 ,(2006) , 10.1016/J.TCS.2005.08.037
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
Feng Wang, My T. Thai, Ding-Zhu Du, On the construction of 2-connected virtual backbone in wireless networks IEEE Transactions on Wireless Communications. ,vol. 8, pp. 1230- 1237 ,(2009) , 10.1109/TWC.2009.051053
Sudipto Guha, Samir Khuller, Approximation Algorithms for Connected Dominating Sets european symposium on algorithms. pp. 179- 193 ,(1996) , 10.1007/3-540-61680-2_55
P. Berman, G. Calinescu, C. Shah, A. Zelikovsky, Power efficient monitoring management in sensor networks wireless communications and networking conference. ,vol. 4, pp. 2329- 2334 ,(2004) , 10.1109/WCNC.2004.1311452
XIAOFENG GAO, YUEXUAN WANG, XIANYUE LI, WEILI WU, ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS Discrete Mathematics, Algorithms and Applications. ,vol. 01, pp. 71- 84 ,(2009) , 10.1142/S1793830909000105
Fei Dai, Jie Wu, On constructing k -connected k -dominating set in wireless ad hoc and sensor networks international parallel and distributed processing symposium. ,vol. 66, pp. 947- 958 ,(2006) , 10.1016/J.JPDC.2005.12.010
Feng Zou, Yuexuan Wang, Xiao-Hua Xu, Xianyue Li, Hongwei Du, Pengjun Wan, Weili Wu, New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs Theoretical Computer Science. ,vol. 412, pp. 198- 208 ,(2011) , 10.1016/J.TCS.2009.06.022
Peng-Jun Wan, Lixin Wang, Frances Yao, Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks international conference on distributed computing systems. pp. 337- 344 ,(2008) , 10.1109/ICDCS.2008.15
N. Garg, J. Konemann, Faster and simpler algorithms for multicommodity flow and other fractional packing problems foundations of computer science. pp. 300- 309 ,(1998) , 10.1109/SFCS.1998.743463