摘要
无线传感器网络栅栏被破坏后,重建栅栏是延长其生存周期的重要手段之一,因此提出一种低能耗的wsn栅栏重建方法BRMLE(Barrier Reconstruction Method with the Low Energy consumption),在充分利用静态节点的基础上,派遣可移动节点完成栅栏的重建工作。首先在栅栏重建区域构建静态传感器节点的全连接拓扑图,然后计算拓扑图中每条边被感知范围完全覆盖所需的节点数量,接着利用KSP(Top-k-Shortest Path)算法寻找拓扑图中k条重建路径,最后利用匈牙利算法选择最佳重建路径并派遣可移动节点完成栅栏重建。BRMLE方法综合考虑了栅栏的重建路径和可移动节点的派遣优化,使得重建栅栏的能耗最低。仿真实验与Optimal方法对比,证明了BRMLE方法需要的可移动节点数量更少,节点的平均移动距离更短,消耗的能量更低。
Reconstruction of fences is one of the important means to extend the life cycle of wireless sensor network barriers. Therefore,a barrier reconstruction method with the low energy consumption( BRMLE) is proposed. Based on the static node,the mobile node is dispatched to complete the reconstruction of the fence. Firstly,construct a fully connected topology map of static sensor nodes in the fence reconstruction area,and then calculate the number of nodes required for each edge of the topology map to be completely covered by the sensing range,and then use the Top-k-shortest path( KSP) algorithm to find the topology map. k reconstruction paths,and finally use the Hungarian algorithm to select the best reconstruction path and dispatch the movable node to complete the fence reconstruction.The BRMLE method takes into account the reconstruction path of the fence and the dispatch optimization of the movable node,so that the energy consumption of the reconstruction fence is the lowest. The comparison between the simulation experiment and the Optimal method proves that the BRMLE method requires fewer mobile nodes,the average moving distance of the nodes is shorter,and the energy consumed is lower.
引文
[1]班冬松,温俊,蒋杰,等.移动无线传感器网络k-栅栏覆盖构建算法[J].软件学报,2011,22(9):2089-2103.
[2]范兴刚,徐俊超,车志聪,等.一种概率栅栏覆盖模型及其构建算法[J].计算机研究与发展,2017,54(5):969-978.
[3]Liu B,Dousse O,Wang J,et al.Strong Barrier Coverage of Wireless Sensor Networks[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.ACM,2008,32(9):411-420.
[4]Zhang Y,Sun X,Wang B.Efficient Algorithm for k-Barrier Coverage Based on Integer Linear Programming[J].China Communications,2016,13(7):16-23.
[5]Akbas M I,Erolkantarci M,Turgut D.Localization for Wireless Sensor and Actor Networks with Meandering Mobility[J].Computers IEEE Transactions on,2015,64(4):1015-1028.
[6]Saipulla A,Westphal C,Liu B,et al.Barrier Coverage with LineBased Deployed Mobile Sensors[J].Ad Hoc Networks,2013,11(4):1381-1391.
[7]戴光麟,方凯,方飞,等.基于集合最大流算法的WSN栅栏修复方法研究[J].传感技术学报,2016,29(11):1742-1747.
[8]Xu B,Zhu Y,Kim D,et al.Strengthening Barrier-Coverage of Static Sensor Network with Mobile Sensor Nodes[J].Wireless Networks,2016,22(1):1-10.
[9]Deng X,Wang B,Wang C,et al.Mending Barrier Gaps via Mobile Sensor Nodes with adjustable Sensing Ranges[C]//Wireless Communications and Networking Conference.IEEE,2013,16(8):1493-1497.
[10]Chen J,Wang B,Liu W,et al.Rotating Directional Sensors to Mend Barrier Gaps in a Line-Based Deployed Directional Sensor Network[J].IEEE Systems Journal,2017,11(2):1027-1038.
[11]Dash D,Dasgupta A.Distributed Restoring of Barrier Coverage in Wireless Sensor Networks Using Limited Mobility Sensors[J].IETWireless Sensor Systems,2017,7(6):198-207.
[12]Xu H,Lai Z,Liu C.Energy Efficient Movement of Wireless Sensors with Adjustable Sensing Ranges for Mending Barrier Gaps[C]//Computing,Networking and Communications(ICNC),2016 International Conference on.IEEE,2016,13(6):1-5.
[13]Tian J,Liang X,Wang G.Deployment and Reallocation in Mobile Survivability-Heterogeneous Wireless Sensor Networks for Barrier Coverage[J].Ad Hoc Networks,2016,36(5):321-331.
[14]Dantu K,Rahimi M,Shah H,et al.Robomote:Enabling Mobility in Sensor Networks[C]//International Symposium on Information Processing in Sensor Networks.IEEE,2005:404-409.
[15]Guvensan M A,Yavuz A G.Hybrid Movement Strategy in SelfOrienting Directional Sensor Networks[M].Elsevier Science Publishers B.V.2013.
[16]Akiba T,Hayashi T,Nori N,et al.Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling[C]//AAAI.2015,15:25-30.
[17]Liu H,Jin C,Yang B.Finding Top-k Shortest Paths with Diversity[J].IEEE Transactions on Knowledge and Data Engineering,2017,21(6):125-131.
[18]Wen Q,Chen R,Nai L,et al.Finding Top K Shortest Simple Paths with Improved Space Efficiency[C]//Proceedings of the Fifth International Workshop on Graph Data-management Experiences&Systems.ACM,2017:13.
[19]Date K,Nagi R.GPU-Accelerated Hungarian Algorithms for the Linear Assignment Problem[J].Parallel Computing,2016,57(8):52-72.
[20]李廷鹏,钱彦岭,李岳.基于改进匈牙利算法的多技能人员调度方法[J].国防科技大学学报,2016,38(2):144-149.