Improved Coverage-Enhancing Algorithm in Hybrid Wireless Sensor Network Based on Cellular Structure

doi:10.19678/j.issn.1000-3428.0063758

Abstract

Abstract: The coverage-enhancing algorithm of Hybrid Wireless Sensor Network(HWSN) based on cellular structure, HWSNBCS, has the problem of a large average moving distance of mobile nodes.Therefore, an improved HWSN coverage-enhancing algorithm named IHWSNBCS is proposed.To obtain the final target position of the mobile node and further optimize the average moving distance of the mobile node of the HWSNBCS algorithm, it is necessary to find the optimal matching between the initial position of the mobile sensor node and the candidate target position obtained through the HWSNBCS algorithm, transform the problem of minimizing the sum of the mobile node moving distances into the optimal matching problem of a bipartite graph, and use the weighted bipartite graph matching algorithm Kuhn-Munkres(KM) to determine the optimal solution of the matching problem.The experimental results show that the IHWSNBCS algorithm achieves the same network coverage rate as the HWSNBCS algorithm.Moreover, the average moving distance of the mobile node decreases by 38.87%-43.28%, and the maximum moving distance of a single mobile node decreases by 22.65%-66.58%, reducing the energy consumption of the system due to the mobile sensor's redeployment of nodes and the probability of failure of a single sensor node due to energy depletion.Thus, the network life cycle is extended. Simultaneously, the ΔCov-Dist performance index of IHWSNBCS is 1.64-1.76 times that of the HWSNBCS algorithm, indicating that the network coverage rate of the IHWSNBCS algorithm is improved when mobile nodes move the same distance.

Key words: Hybrid Wireless Sensor Network(HWSN), cellular structure, network coverage rate, KM algorithm, mobile node

摘要： 基于蜂窝结构的混合无线传感器网络（HWSN）覆盖优化算法HWSNBCS存在移动节点平均移动距离较大的问题，为此，提出一种改进的HWSN覆盖优化算法IHWSNBCS。寻找移动传感器节点初始位置与通过HWSNBCS算法得出的候选目标位置之间的最优匹配，将移动节点移动距离之和最小化问题转化为二分图最优匹配问题，利用带权二分图匹配算法KM寻找该匹配问题的最优解，从而得到移动节点最终的目标位置，并实现对HWSNBCS算法移动节点平均移动距离的进一步优化。实验结果表明，IHWSNBCS算法在取得与HWSNBCS算法相同网络覆盖率的前提下，移动节点的平均移动距离减少幅度达到38.87%~43.28%，单个移动节点的最大移动距离减少幅度达到22.65%~66.58%，降低了系统因重新部署移动传感器节点所产生的能耗以及单个传感器节点因能量耗尽而失效的概率，从而延长了网络生命周期，同时，IHWSNBCS的ΔCov-Dist性能指标为HWSNBCS算法的1.64~1.76倍，表明移动节点移动相同距离时IHWSNBCS算法的网络覆盖率提升更大。

关键词: 混合无线传感器网络, 蜂窝结构, 网络覆盖率, KM算法, 移动节点

CLC Number:

TP393

ZHANG Qingguo, ZHANG Yong, ZHANG Wei, XI Ruijie. Improved Coverage-Enhancing Algorithm in Hybrid Wireless Sensor Network Based on Cellular Structure[J]. Computer Engineering, 2022, 48(12): 172-179.

张清国, 张勇, 张伟, 席瑞洁. 基于蜂窝结构的改进混合无线传感器网络覆盖优化算法[J]. 计算机工程, 2022, 48(12): 172-179.

/ / Recommend / Download Citations

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

http://www.ecice06.com/EN/Y2022/V48/I12/172

Figures/Tables 13

References

[1] 陶李, 郭宇欣, 韩优佳.基于信任的WSN快速识别信任攻击模型[J].吉林大学学报(理学版), 2022, 60(6):1423-1429. TAO L, GUO Y X, HAN Y J.Fast identification model for trust attacks in WSN based on trust[J].Journal of Jilin University(Science Edition), 2022, 60(6):1423-1429.(in Chinese)
[2] 石拓, 李建中, 高宏.多等级通信半径的无源传感器网络中的覆盖问题[J].软件学报, 2021, 32(8):2580-2596. SHI T, LI J Z, GAO H.Coverage problem in battery-free sensor networks with multi-level communication radius[J].Journal of Software, 2021, 32(8):2580-2596.(in Chinese)
[3] HIREMANI N, BASAVARAJU T G.Energy efficient clustering-based routing protocol adopting enhanced cluster formation protocol in hybrid wireless sensor networks[C]//Proceedings of the 3rd International Conference on Inventive Systems and Control.Washington D.C., USA:IEEE Press, 2019:389-393.
[4] WANG Y C.A two-phase dispatch heuristic to schedule the movement of multi-attribute mobile sensors in a hybrid wireless sensor network[J].IEEE Transactions on Mobile Computing, 2014, 13(4):709-722.
[5] AKIN B, ERKMEN A, EEKMEN I.A behavior based layered, hybrid, control architecture for robot/sensor networks[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 2006:206-211.
[6] FU Z X, YOU K Y.Optimal mobile sensor scheduling for a guaranteed coverage ratio in hybrid wireless sensor networks[J].International Journal of Distributed Sensor Networks, 2013, 9(4):740841.
[7] BANIMELHEM O, MOWAFI M, ALJOBY W.Genetic algorithm based node deployment in hybrid wireless sensor networks[J].Communications and Network, 2013, 5(4):273-279.
[8] WANG Y C, PENG W C, TSENG Y C.Energy-balanced dispatch of mobile sensors in a hybrid wireless sensor network[J].IEEE Transactions on Parallel and Distributed Systems, 2010, 21(12):1836-1850.
[9] 周彤, 洪炳镕, 朴松昊.基于虚拟力的混合感知网节点部署[J].计算机研究与发展, 2007, 44(6):965-972. ZHOU T, HONG B R, PIAO S H.Hybrid sensor networks deployment based on virtual force[J].Journal of Computer Research and Development, 2007, 44(6):965-972.(in Chinese)
[10] RAINA M, KUMAR S, PATRO R.无线传感网络中使用动态代理的节点收敛算法[J].自动化学报, 2006, 32(6):915-921. RAINA M, KUMAR S, PATRO R.Node coverage algorithms in wireless sensor networks using mobile agents[J].Acta Automatica Sinica, 2006, 32(6):915-921.(in Chinese)
[11] BOUFARES N, BEN SAIED Y, SAIDANE L A.Improved distributed virtual forces algorithm for 3D terrains coverage in mobile wireless sensor networks[C]//Proceedings of IEEE/ACS International Conference on Computer Systems and Applications.Washington D.C., USA:IEEE Press, 2018:1-8.
[12] WANG Y J, QIAN K G.A coverage-enhancing algorithm based on local virtual force equilibrium for wireless sensor networks[C]//Proceedings of the 4th International Conference on Computer Engineering and Networks.Berlin, Germany:Springer, 2015:1273-1280.
[13] YE G, ZHANG B H, WEN L F, et al.Extended virtual force-based coverage scheme for heterogeneous wireless sensor networks[C]//Proceedings of the 14th International Conference on Control, Automation and Systems.Washington D.C., USA:IEEE Press, 2014:1560-1564.
[14] SLIJEPCEVIC S, POTKONJAK M.Power efficient organization of wireless sensor networks[C]//Proceedings of IEEE International Conference on Communications.Washington D.C., USA:IEEE Press, 2001:472-476.
[15] 黄瑜岳, 李克清.基于人工鱼群算法的无线传感器网络覆盖优化[J].计算机应用研究, 2013, 30(2):554-556. HUANG Y Y, LI K Q.Coverage optimization of wireless sensor networks based on artificial fish swarm algorithm[J].Application Research of Computers, 2013, 30(2):554-556.(in Chinese)
[16] DONG H L, ZHANG K, ZHU L.An algorithm of 3D directional sensor network coverage enhancing based on artificial fish-swarm optimization[C]//Proceedings of 2012 International Workshop on Microwave and Millimeter Wave Circuits and System Technology.Washington D.C., USA:IEEE Press, 2012:1-4.
[17] 李显, 刘明生, 李燕, 等.基于混沌鱼群改进算法的无线传感网覆盖优化[J].激光杂志, 2015, 36(1):98-101. LI X, LIU M S, LI Y, et al.Coverage optimization of wireless sensor networks based on improved fish swarm algorithm[J].Laser Journal, 2015, 36(1):98-101.(in Chinese)
[18] ZHOU J, QIN H, LIU Y, et al.Hybrid niche immune genetic algorithm for fault detection coverage in industry wireless sensor network[J].Journal of Sensors, 2021(4):1-13.
[19] ZHANG Q G, HE T T.A novel coverage enhancing algorithm for hybrid wireless sensor networks[J].Ad-Hoc & Sensor Wireless Networks, 2018, 40(1/2):1-22.
[20] LY D, HANH N T, BINH H, et al.An improved genetic algorithm for maximizing area coverage in wireless sensor networks[C]//Proceedings of International Symposium on Information & Communication Technology.New York, USA:ACM Press, 2015:61-66.
[21] ZHANG Q, FOK M P.A two-phase coverage-enhancing algorithm for hybrid wireless sensor networks[J].Sensors, 2017, 17(1):E117.
[22] XU Y L, WANG X H, ZHANG H.Improved differential evolution to solve the two-objective coverage problem of wireless sensor networks[C]//Proceedings of Chinese Control and Decision Conference.Washington D.C., USA:IEEE Press, 2016:2379-2384.
[23] QASIM T, ZIA M, MINHAS Q A, et al.An ant colony optimization based approach for minimum cost coverage on 3-D grid in wireless sensor networks[J].IEEE Communi-cations Letters, 2018, 22(6):1140-1143.
[24] LEE J W, CHOI B S, LEE J J.Energy-efficient coverage of wireless sensor networks using ant colony optimization with three types of pheromones[J].IEEE Transactions on Industrial Informatics, 2011, 7(3):419-427.
[25] LEE J W, LEE J J.Ant-colony-based scheduling algorithm for energy-efficient coverage of WSN[J].IEEE Sensors Journal, 2012, 12(10):3036-3046.
[26] ZHANG Y B, SHEN W M.A novel particle swarm optimization algorithm for k-coverage problems in wireless sensor networks[C]//Proceedings of IEEE International Conference on Computer Supported Cooperative Work in Design.Washington D.C., USA:IEEE Press, 2021:831-836.
[27] LIU Z Z, SHE Y H.Hybrid wireless sensor network coverage holes restoring algorithm[J].Journal of Sensors, 2016(3):1-9.
[28] SOHRABI K, GAO J, AILAWADHI V, et al.Protocols for self-organization of a wireless sensor network[J].IEEE Personal Communications, 2000, 7(5):16-27.
[29] 张清国, 李世顺, 赵甫哲, 等.基于蜂窝结构的混合无线传感器网络覆盖优化算法[J].小型微型计算机系统, 2016, 37(12):2598-2602. ZHANG Q G, LI S S, ZHAO F Z, et al.Coverage-enhancing algorithm in hybrid wireless sensor network based on cellular structure[J].Journal of Chinese Computer Systems, 2016, 37(12):2598-2602.(in Chinese)
[30] 王方洋, 刘玉铭.针对带约束匹配搜索的扩展Kuhn-Munkres算法[J].北京师范大学学报(自然科学版), 2021, 57(2):167-172. WANG F Y, LIU Y M.Extended Kuhn-Munkres algorithm for constrained matching search[J].Journal of Beijing Normal University(Natural Science), 2021, 57(2):167-172.(in Chinese)

Please choose a citation manager

Content to export