Reconstruction of Virtual Backbones in Heterogeneous Wireless Sensor Networks

doi:10.19678/j.issn.1000-3428.0066831

Abstract

Abstract:

A Wireless Sensor Network(WSN) relies on a Virtual Backbone(VB), which comprises a subset of nodes solely responsible for routing tasks. In the event of failure within a heterogeneous WSN, the original VB's functionality may be compromised. However, existing fault-tolerant VBs only address node failures and do not account for scenarios involving link failures without node failures.Moreover, their size increases disproportionately with the number of faulty nodes. Therefore, to address the drawbacks associated with existing fault-tolerant VBs, this study investigates the challenge of reconstructing a VB for heterogeneous WSNs with faulty links.For a given heterogeneous WSN with faulty links, an approximation algorithm(ZREA22) is designed for VB reconstruction. The algorithm first selects the set comprising nodes that remain unaffected by the original connected dominating set. Next, it constructs a maximal independent set derived from the induced subgraph of the obtained set. Finally, additional nodes are added into both the maximal independent set and the original connected dominating set, thereby shaping the reconstructed connected dominating set.Experimental results confirm that ZREA22 can effectively generate a new VB with a predetermined upper bound on its size.Comparative analysis against benchmarks WFSK09 and SHLO14 reveal that ZREA22 achieves a reduction in VB size of no less than 9% and 31%, respectively.Furthermore, ZREA22 demonstrates superior performance in terms of runtime efficiency.

Key words: Virtual Backbone(VB), connected dominating set, approximation algorithm, Wireless Sensor Network(WSN), Disk Graph with Bidirectional links(DGB)

摘要：

无线传感器网络的虚拟骨干是承担网络路由任务的结点组成的子集。当一个异质无线传感器网络故障时，原有的虚拟骨干可能就会失去部分功能，然而现有的容错虚拟骨干只能容纳顶点故障，无法解决只有链路故障但没有顶点故障的问题，且虚拟骨干大小会随故障顶点数量的增加呈超线性增加。针对上述问题，研究在异质无线传感器网络链路发生故障时的虚拟骨干重构问题。对于一个只有链路故障的异质无线传感器网络，设计一个虚拟骨干重构近似算法(ZREA22)，寻找一个未被控制的点组成的集合，在该集合导出的子图中构造一个极大独立集，并向该极大独立集和原连通控制集中添加结点以形成一个重构的连通控制集。实验结果表明，ZREA22算法能够产生一个大小有界的连通控制集，且虚拟骨干大小相比于WFSK09和SHLO14算法至少减少了9%和31%，同时算法运行时间更短。

关键词: 虚拟骨干, 连通控制集, 近似算法, 无线传感器网络, 双向链路圆盘图

Feng HE, Jiarong LIANG, Changzhen LI. Reconstruction of Virtual Backbones in Heterogeneous Wireless Sensor Networks[J]. Computer Engineering, 2023, 49(9): 191-198.

何峰, 梁家荣, 黎昌珍. 异质无线传感器网络虚拟骨干重构[J]. 计算机工程, 2023, 49(9): 191-198.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0066831

http://www.ecice06.com/EN/Y2023/V49/I9/191

Figures/Tables 5

References 25

1	朱晓娟, 何勇男. 能量有效的无线传感器网络动态任务调度算法. 计算机工程与设计, 2020, 41 (2): 313- 318. doi: 10.16208/j.issn1000-7024.2020.02.003
	ZHU X J, HE Y N. Energy-efficiency dynamic task scheduling in wireless sensor networks. Computer Engineering and Design, 2020, 41 (2): 313- 318. doi: 10.16208/j.issn1000-7024.2020.02.003
2	张清国, 张勇, 张伟, 等. 基于蜂窝结构的改进混合无线传感器网络覆盖优化算法. 计算机工程, 2022, 48 (12): 172- 179. URL
	ZHANG Q G, ZHANG Y, ZHANG W, et al. Improved coverage optimization algorithm for hybrid wireless sensor networks based on cellular structure. Computer Engineering, 2022, 48 (12): 172- 179. URL
3	GOPE P, DAS A K, KUMAR N, et al. Lightweight and physically secure anonymous mutual authentication protocol for real-time data access in industrial wireless sensor networks. IEEE Transactions on Industrial Informatics, 2019, 15 (9): 4957- 4968. doi: 10.1109/TII.2019.2895030
4	COHEN A, COHEN A, GUREWITZ O. Efficient data collection over multiple access wireless sensors network. IEEE/ACM Transactions on Networking, 2020, 28 (2): 491- 504. doi: 10.1109/TNET.2020.2964764
5	EPHREMIDES A, WIESELTHIER J E, BAKER D J. A design concept for reliable mobile radio networks with frequency hopping signaling. Proceedings of the IEEE, 1987, 75 (1): 56- 73. doi: 10.1109/PROC.1987.13705
6	WANG B W, SUN Y J, DO-DUY T, et al. Adaptive d-hop connected dominating set in highly dynamic flying ad-hoc networks. IEEE Transactions on Network Science and Engineering, 2021, 8 (3): 2651- 2664. doi: 10.1109/TNSE.2021.3103873
7	DU Y L, DU H W. A new bound on maximum independent set and minimum connected dominating set in unit disk graphs. Journal of Combinatorial Optimization, 2015, 30 (4): 1173- 1179. doi: 10.1007/s10878-013-9690-0
8	YANG Z S, SHI M J, WANG W. Greedy approximation for the minimum connected dominating set with labeling. Optimization Letters, 2021, 15 (2): 685- 700. doi: 10.1007/s11590-020-01628-6
9	FUKUNAGA T. Approximation algorithms for highly connected multi-dominating sets in unit disk graphs. Algorithmica, 2018, 80 (11): 3270- 3292. doi: 10.1007/s00453-017-0385-2
10	FUKUNAGA T. Adaptive algorithm for finding connected dominating sets in uncertain graphs. IEEE/ACM Transactions on Networking, 2020, 28 (1): 387- 398. doi: 10.1109/TNET.2019.2963361
11	GAO X F, ZHU X D, LI J, et al. A novel approximation for multi-hop connected clustering problem in wireless networks. IEEE/ACM Transactions on Networking, 2017, 25 (4): 2223- 2234. doi: 10.1109/TNET.2017.2690359
12	HONG Y, LI D Y, CHEN Z B. Constructing virtual backbone with guaranteed routing cost in wireless sensor networks. Ad Hoc Networks, 2021, 116, 102500. doi: 10.1016/j.adhoc.2021.102500
13	THAI M T, WANG F, LIU D, et al. Connected dominating sets in wireless networks with different transmission ranges. IEEE Transactions on Mobile Computing, 2007, 6 (7): 721- 730. doi: 10.1109/TMC.2007.1034
14	BAI S, CHE X J, BAI X, et al. Maximal independent sets in heterogeneous wireless ad hoc networks. IEEE Transactions on Mobile Computing, 2016, 15 (8): 2023- 2033. doi: 10.1109/TMC.2015.2508805
15	ZHANG Z, ZHOU J, MO Y C, et al. Performance-guaranteed approximation algorithm for fault-tolerant connected dominating set in wireless networks[C]//Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Washington D. C., USA: IEEE Press, 2016: 1-8.
16	WANG W, LIU B, KIM D, et al. A new constant factor approximation to construct highly fault-tolerant connected dominating set in unit disk graph. IEEE/ACM Transactions on Networking, 2017, 25 (1): 18- 28. doi: 10.1109/TNET.2016.2561901
17	LIU B, WANG W, KIM D, et al. On practical construction of quality fault-tolerant virtual backbone in homogeneous wireless networks. IEEE/ACM Transactions on Networking, 2018, 26 (1): 412- 421. doi: 10.1109/TNET.2017.2780262
18	ZHOU J, ZHANG Z, TANG S J, et al. Fault-tolerant virtual backbone in heterogeneous wireless sensor network. IEEE/ACM Transactions on Networking, 2017, 25 (6): 3487- 3499. doi: 10.1109/TNET.2017.2740328
19	ZHANG Z, ZHOU J A, TANG S J, et al. Computing minimum k-connected m-fold dominating set in general graphs. INFORMS Journal on Computing, 2018, 30 (2): 217- 224. doi: 10.1287/ijoc.2017.0776
20	DASH D. Restoring virtual backbone of Wireless Sensor Network on sensor failure[C]//Proceedings of the 3rd International Conference on Recent Advances in Information Technology. Washington D. C., USA: IEEE Press, 2016: 29-34.
21	DAS A, AASAWAT M, MANDAL C, et al. An improved greedy construction of minimum connected dominating sets in wireless networks[C]//Proceedings of IEEE Wireless Communications and Networking Conference. Washington D. C., USA: IEEE Press, 2011: 790-795.
22	KIM D, WANG W, LI X Y, et al. A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks[C]//Proceedings IEEE INFOCOM. Washington D. C., USA: IEEE Press, 2010: 1-9.
23	WANG F, THAI M T, DU D Z. On the construction of 2-connected virtual backbone in wireless networks. IEEE Transactions on Wireless Communications, 2009, 8 (3): 1230- 1237. doi: 10.1109/TWC.2009.051053
24	SHI Y, ZHANG Y, ZHANG Z, et al. A greedy algorithm for the minimum 2-connected m-fold dominating set problem. Journal of Combinatorial Optimization, 2016, 31 (1): 136- 151. doi: 10.1007/s10878-014-9720-6
25	SHANG W P, YAO F, WAN P J, et al. On minimum m-connected k-dominating set problem in unit disc graphs. Journal of Combinatorial Optimization, 2008, 16 (2): 99- 106. doi: 10.1007/s10878-007-9124-y

[1]	Zongsheng HU, Kai XING, Jing XU. Spatio-Temporal Coding Method for Wireless Sensor Networks Based on Transcendence Number Theory [J]. Computer Engineering, 2023, 49(9): 172-182.
[2]	Min YANG, Linghua ZHANG. Improved AODV Routing Protocol Based on Region Awareness in WSN [J]. Computer Engineering, 2023, 49(8): 130-136.
[3]	ZHOU Wenkang, WANG Xingfu. A Routing Algorithm for WSN Based on AHP and FIS [J]. Computer Engineering, 2022, 48(3): 131-138,161.
[4]	WANG Hailang, ZHANG Linghua. Improvement of Routing Protocol for Wireless Sensor Networks Based on PEGASIS [J]. Computer Engineering, 2022, 48(12): 165-171,179.
[5]	MIAO Yisheng, ZHAO Chunjiang, WU Huarui. Farmland WSN Routing Optimization Method Based on Improved Particle Swarm Optimization [J]. Computer Engineering, 2022, 48(10): 218-223.
[6]	HAN Youjia, HU Huangshui, YAO Meiqin. Trust-Aware Secure Routing Protocol for Wireless Sensor Networks [J]. Computer Engineering, 2021, 47(9): 145-152.
[7]	YU Jizhe, BAI Leqiang, CAO Keyan. Perpendicular-Based Algorithm for the Protection of Sink Location Privacy in WSN [J]. Computer Engineering, 2021, 47(8): 170-176,182.
[8]	JIANG Baoqing, CHEN Hongbin. Trajectory Planning for Unmanned Aerial Vehicle Assisted WSN Data Collection Based on Q-Learning [J]. Computer Engineering, 2021, 47(4): 127-134,165.
[9]	LIU Yanan, ZHANG Zheng, QIU Shuo, CHENG Yuan. Intra-Cluster Key Distribution Based on Physical Unclonable Functions in WSN [J]. Computer Engineering, 2020, 46(9): 163-171.
[10]	LI Cuiran, LI Ang. Energy Efficient Routing Algorithm for Linear WSN with Solar Energy Harvesting [J]. Computer Engineering, 2020, 46(9): 178-185.
[11]	HAO Zhanjun, HOU Jiaojiao, DANG Xiaochao, QU Nanjiang. A Node Coverage Optimization Method for Strip Area in WSN [J]. Computer Engineering, 2020, 46(7): 165-172.
[12]	HAO Zhanjun, XU Hongwen, DANG Xiaochao, DUAN Yu. A Dynamic Detection and Repair Algorithm for Three-Dimensional Coverage Holes in WSN [J]. Computer Engineering, 2020, 46(6): 178-186.
[13]	SONG Lei, REN Xiuli. A Data Fusion Algorithm with Low Energy Consumption and High Accuracy in WSN [J]. Computer Engineering, 2020, 46(6): 172-177.
[14]	LI Hongbing, LIU Zilu, CHEN Qiang, LIU Sha, LI Xiaolong, LIANG Yuqiao, YANG Zhen, CHEN Liwan. Clustering Routing Algorithm for Wireless Sensor Network Based on Hierarchical Neighboring Nodes [J]. Computer Engineering, 2020, 46(6): 187-195.
[15]	LIU Yang, JIANG Haibo, WANG Zheng, PANG Zhenjiang, LIU Zhenyao, GAO Chao, HU Chengbo, LU Yongling, SUN Haiquan, XU Jiangtao. Access Control and Routing Optimization Strategy for Energy-Saving Aware Wireless Sensor Network [J]. Computer Engineering, 2020, 46(5): 230-239.

Please choose a citation manager

Content to export