作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (12): 172-179. doi: 10.19678/j.issn.1000-3428.0063758

• 移动互联与通信技术 • 上一篇    下一篇

基于蜂窝结构的改进混合无线传感器网络覆盖优化算法

张清国1, 张勇1, 张伟1, 席瑞洁2   

  1. 1. 华中师范大学 计算机学院, 武汉 430079;
    2. 华中科技大学 计算机科学与技术学院, 武汉 430074
  • 收稿日期:2022-01-14 修回日期:2022-04-12 发布日期:2022-08-31
  • 作者简介:张清国(1977—),男,副教授、博士,主研方向为无线传感器网络、人工智能;张勇,副教授、博士;张伟,讲师、博士;席瑞杰,硕士研究生。
  • 基金资助:
    国家自然科学基金(61977032);中央高校基本科研业务费专项资金(CCNU20QN021)。

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

ZHANG Qingguo1, ZHANG Yong1, ZHANG Wei1, XI Ruijie2   

  1. 1. School of Computer Science, Central China Normal University, Wuhan 430079, China;
    2. School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
  • Received:2022-01-14 Revised:2022-04-12 Published:2022-08-31

摘要: 基于蜂窝结构的混合无线传感器网络(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算法, 移动节点

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

中图分类号: