Computer Science ›› 2016, Vol. 43 ›› Issue (1): 128-132, 158.doi: 10.11896/j.issn.1002-137X.2016.01.029

Previous Articles     Next Articles

Distributed Construction for (k,m)-Fault Tolerant Connected Dominating Set in Wireless Sensor Network

MA Chen-ming, WANG Wan-liang and HONG Zhen   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Virtual backbone based on connected dominating set can prolong the lifetime of wireless sensor network.However,considering nodes are prone to failure,virtual backbone also needs to have a certain degree of fault tolerance.In this regard,a fully distributed algorithm was proposed for fault tolerance constructing k-connected m-dominated set for arbitrary k and m values.The algorithm can be extended in the heterogeneous network.It constructs connected do-minating set firstly,then makes all common nodes m-dominating with the idea of maximum independent set and greedy,and finally extends the connected dominated set k-connectivity by the common neighbor nodes in the local topology.Simulation experiments confirm that the algorithm can obtain better size k-connected m-dominating set with low message overhead.

Key words: Wireless sensor network,Fault tolerance,k-connected m-dominated set,Heterogeneity,Distributed algorithm

[1] Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks [J].IEEE Communications Surveys & Tutorials,2013,15(1):121-144
[2] Lee S,Mohamed Y.Recovery from multiple simultaneous fai-lures in wireless sensor networks using minimum Steiner tree[J].Parallel and Distributed Computing,2010,70(5):525-536
[3] Hong Zhen,Yu Li,Zhang Gui-jun,et al.Topology Construction Based on Minimum Connected Dominating Set for Wireless Sensor Networks[J].Journal of Electronics & Information Technology,2012,34(8):2000-2006(in Chinese)洪榛,俞立,张贵军,等.基于最小连通支配集的无线传感网拓扑构建研究[J].电子与信息学报,2012,4(8):2000-2006
[4] Kui Xiao-yan,Du Hua-kun,Liang Jun-bin.An energy-balanced connected dominating sets for data gathering in wireless sensor networks[J].Acta Electronica Sinica,2013,41(8):1521-1528(in Chinese)奎晓燕,杜华坤,梁俊斌.无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法[J].电子学报,2013,41(8):1521-1528
[5] Ma Chen-ming,Wang Wan-liang,Hong Zhen.A Topology Control Method based on CDS Tree in Heterogeneous Wireless Sensor Network[J].Chinese Journal of Sensors and Actuators,2014,27(6):814-820(in Chinese)马晨明,王万良,洪榛.异构无线传感器网络中基于CDS树的拓扑控制方法[J].传感技术学报,2014,7(6):814-820
[6] Das A,Mandal C,Reade C,et al.An improved greedy construction of minimum connected dominating sets in wireless networks[C]∥Proc.of IEEE Wireless Communications and Networking Conference.Cancun,Mexico,2011:790-795
[7] He Jing,Ji Shou-ling,Fan Ping-zhi,et al.Constructing a load-balanced virtual backbone in wireless sensor networks[C]∥Proc.of International Conference on Computing Networking and Communications.Maui,Hawaii,USA,2012:959-963
[8] Dai Fei,Wu Jie.On Constructing k-Connected k-Dominating Set in Wireless Networks[C]∥Proc.of the 19th IEEE International Parallel and Distributed Processing Symposium.Denver,Colorado,2005:81-90
[9] Wang Feng,Thai M T,Du Ding-zhu.On the construction of 2-connected virtual backbone in wireless networks [J].IEEE Transactions on Wireless Communications,2009,8(3):1230-1237
[10] Gao Xiao-feng,Xu Bo-sheng,Li Jun.A distributed design forminimum 2-Connected m-Dominating Set in bidirectional wireless ad-hoc networks[J].Tsinghua Science and Technology,2012,17(5):553-566
[11] Wu Yi-wei,Wang Feng,Thai M T,et al.Constructing k-Con-nected m-Dominating Sets in Wireless Sensor Networks[C]∥Proc.of Military Communications Conference.Orlando,Florida,USA,2007:29-31
[12] Kim D,Wang Wei,Li Xian-yue,et al.A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks[C]∥Proc.of the 29th IEEE International Conference on Computer Communications.San Diego,CA,USA,2010:1-9
[13] Wang Wei,Kim D,Kyung A M,et al.On Construction of Quali-ty Fault-Tolerant Virtual Backbone in Wireless Networks[J].IEEE/ACM Transactions on Networking,2013,1(5):1499-1510
[14] Schleich J,Danoy G,Bouvry P,et al.Blackbone2,an efficient deterministic algorithm for creating 2-connected m-dominating set-based backbones in ad hoc networks[C]∥Proc.of the 7th ACM International Symposium on Mobility Management and Wireless Access.New York,USA,2009:91-98
[15] Zheng Chan,Yin Ling,Sun Shi-xin.Constructing 2-connected k-dominating sets for fault-tolerant backbone in wireless sensor networks[J].Control and Decision,2013,28(5):650-656(in Chinese)郑婵,尹令,孙世新.无线传感器网络中2-连通k-支配的容错连通支配集构造[J].控制与决策,2013,8(5):650-656
[16] Li Ying-shu,Wu Yi-wei,Ai Chun-yun,et al.On the construction of k-connected m-dominating sets in wireless networks[J].Combinatorial Optimization,2012,23(1):118-139
[17] Wightman P M,Labrador M A.Atarraya:a simulation tool to teach and research topology control algorithms for wireless sensor networks[C]∥Proc.of 2nd International Conference on Simulation Tools and Techniques.Rome,Italy,2009:26-35

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .