优化网络生命周期和最短化路径的WSN移动sink路径规划算法
|
摘要
为了缓解无线传感器网络(WSN)中传感器节点分布不均匀、传感器节点感知数据量不同而造成能耗不均衡、"热区"等问题,提出一种优化网络生命周期和最短化路径的WSN移动sink路径规划算法(MSPPA)。首先,通过监测区域网格化,在每个网格内分布若干个移动sink候选访问站点,sink在每个网格中选择一个站点停留收集网格中节点数据;然后,分析所有传感器节点的生命周期与sink站点选择的关系,建立权衡网络生命周期和sink移动路径的优化模型;最后,使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点,得到移动sink节点遍历所有网格收集数据的路径。仿真结果显示,与已有的低功耗自适应分簇(LEACH)算法与基于移动sink节点与集合节点(RN)的优化LEACH分簇算法(MS-LEACH-RN)相比,MSPPA在网络生命周期方面提高了60%,且具有良好的能耗均衡性。实验结果表明,MSPPA能有效缓解能量不均衡、"热区"问题,延长网络生命周期。
In order to alleviate the problem of the imbalance energy consumption and hotspot due to the uneven distribution of nodes and the different amount of perception data in the Wireless Sensor Network( WSN), a Path Planning Algorithm of Mobile Sink named MSPPA was proposed to optimize network lifetime and shortest path in WSN. Firstly, by defining the grids in the network area, several candidate sites of mobile sink were distributed in each grid, and then sink node selected a site for sojourning and collecting data of nodes in each grid. Secondly, based on the relationship between network lifetime and the selection of sink sites, an optimization model was established to weigh network lifetime and mobile journey of sink. Finally, the double-stranded genetic algorithm was proposed to plan the order of mobile sink traversing grids and selecting site of the mobile sink in each grid, then the optimal path of mobile sink was obtained. The simulation results show that, compared with Low-Energy Adaptive Clustering Hierarchy( LEACH) algorithm and optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes( MS-LEACH-RN), the network lifetime of MSPPA was increased by 60%.The proposed MSPPA has a good balance of energy consumption as well. The experimental results indicate that the proposed MSPPA can effectively alleviate the imbalance of energy consumption and the hotspot problems, prolonging the network lifetime.
In order to alleviate the problem of the imbalance energy consumption and hotspot due to the uneven distribution of nodes and the different amount of perception data in the Wireless Sensor Network( WSN), a Path Planning Algorithm of Mobile Sink named MSPPA was proposed to optimize network lifetime and shortest path in WSN. Firstly, by defining the grids in the network area, several candidate sites of mobile sink were distributed in each grid, and then sink node selected a site for sojourning and collecting data of nodes in each grid. Secondly, based on the relationship between network lifetime and the selection of sink sites, an optimization model was established to weigh network lifetime and mobile journey of sink. Finally, the double-stranded genetic algorithm was proposed to plan the order of mobile sink traversing grids and selecting site of the mobile sink in each grid, then the optimal path of mobile sink was obtained. The simulation results show that, compared with Low-Energy Adaptive Clustering Hierarchy( LEACH) algorithm and optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes( MS-LEACH-RN), the network lifetime of MSPPA was increased by 60%.The proposed MSPPA has a good balance of energy consumption as well. The experimental results indicate that the proposed MSPPA can effectively alleviate the imbalance of energy consumption and the hotspot problems, prolonging the network lifetime.
引文
[1]XING G,WANG T,XIE Z,et al.Rendezvous planning in wireless sensor networks with mobile elements[J].IEEE Transactions on Mobile Computing,2008,7(12):1430-1443.
[2]CHATZIGIANNAKIS I,KINALIS A,NIKOLETSEAS S.Efficient data propagation strategies in wireless sensor networks using a single mobile sink[J].Computer Communications,2008,31(5):896-914.
[3]KHAN A W,ABDULLAH A H,ANISI M H,et al.A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[J].Sensors,2014,14(2):2510-2548.
[4]SUN W,YANG Z,ZHANG X,et al.Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks:a survey[J].IEEE Communications Surveys&Tutorials,2014,16(3):1448-1459.
[5]张惠麒,林志贵,李敏,等.基于移动sink节点的路由协议的比较与分析[J].计算机科学,2014,41(S1):276-280.(ZHANG HQ,LIN Z G,LI M,et al.Comparison and analysis of routing protocol based on mobile sink[J].Computer Science,2014,41(S1):276-280.)
[6]GU Y,REN F,JI Y,et al.The evolution of sink mobility management in wireless sensor networks:a survey[J].IEEE Communications Surveys&Tutorials,2016,18(1):507-524.
[7]LIN C-J,CHOU P-L,CHOU C-F.HCDD:hierarchical clusterbased data dissemination in wireless sensor networks with mobile sink[C]//IWCMC'06:Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing.New York:ACM,2006:1189-1194.
[8]HAMIDA E B,CHELIUS G.A line-based data dissemination protocol for wireless sensor networks with mobile sink[C]//ICC'08:Proceedings of the 2008 IEEE International Conference on Communications.Piscataway,NJ:IEEE,2008:2201-2205.
[9]MOTTAGHI S,ZAHABI M R.Optimizing LEACH clustering algorithm with mobile sink and rendezvous nodes[J].AEU-International Journal of Electronics and Communications,2015,69(2):507-514.
[10]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNANH.Energy-efficient communication protocols for wireless microsensor networks[C]//HICSS'00:Proceedings of the 33rd Hawaii International Conference on Systems Sciences.Washington,DC:IEEE Computer Society,2000,8:8020.
[11]BHATTI R,KAUR G.Virtual grid based energy efficient mobile sink routing algorithm for WSN[C]//Proceedings of the 11th International Conference on Intelligent Systems and Control.Piscataway,NJ:IEEE,2017:30-33.
[12]梁青,焦峰.WSN中基于二分法与移动Sink的数据收集协议[J].计算机工程,2016,42(12):39-43.(LIANG Q,JIAO F.Data collection protocol for WSN based on dichotomy and mobile sink[J].Computer Engineering,2016,42(12):39-43.)
[13]YUN Y,XIA Y.Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications[J].IEEETransactions on Mobile Computing,2010,9(9):1308-1318.
[14]林德钰,王泉,刘伎昭.无线传感网的移动与静态sink相结合的节能策略[J].哈尔滨工业大学学报,2016,48(11):162-168.(LIN D Y,WANG Q,LIU J Z.Energy-saving strategy by combining mobile and static sink schemes for wireless sensor networks[J].Journal of Harbin Institute of Technology,2016,48(11):162-168.)
[15]王章权,陈友荣,任条娟,等.数据传输时延和跳数受限的Sink节点移动路径选择算法[J].传感技术学报,2016,29(4):583-592.(WANG Z Q,CHEN Y R,REN T J,et al.Sink node moving path selection algorithm limited by data transmission delay and hops[J].Chinese Journal of Sensor and Actuators,2016,29(4):583-592.)
[16]PAVITHRA H,SHIVASHANKAR,POORNIMA G R.An efficient mobile sink path selection approach for WSN's[C]//Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics Information Communication Technology.Piscataway,NJ:IEEE,2016:151-155.
[17]王薇,史浩山,黄鹏宇,等.基于二次栅格划分的移动sink最小路径构建算法[J].西北工业大学学报,2016,34(6):1016-1021.(WANG W,SHI H S,HUANG P Y,et al.A constructing mobile path minimal path algorithm based on quadratic grid[J].Journal of Northwestern Polytechnical University,2016,34(6):1016-1021.)
[18]于志博,孔祥雪,裴金金.移动Sink的传感器网络路径优化策略[J].传感器与微系统,2016,35(11):44-46.(YU Z B,KONG X X,PEI J J.Mobile sink-based path optimization strategy in wireless sensor networks[J].Transducer and Microsystem Technologies,2016,35(11):44-46.)
[19]陶志勇,蒋守凤.基于簇首移动的无线传感器网络路由算法[J].计算机工程与应用,2016,52(5):75-78.(TAO Z Y,JIANG S F.Clustering algorithm for wireless sensor networks with mobile cluster heads[J].Computer Engineering and Applications,2016,52(5):75-78.)
[20]SHI Y,HOU Y T.Theoretical results on base station movement problem for sensor network[C]//INFOCOM 2008:Proceedings of the 27th Conference on Computer Communications.Piscataway,NJ:IEEE,2008:1-5.
[21]HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNANH.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2000,1(4):660-670.
[22]TASHTARIAN F,MOGHADDAM M H Y,SOHRABY K,et al.ODT:optimal deadline-based trajectory for mobile sinks in WSN:a decision tree and dynamic programming approach[J].Computer Networks,2015,77:128-143.
[23]TASHTARIAN F,HOSSEIN Y M M,SOHRABY K,et al.On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks[J].IEEE Transactions on Vehicular Technology,2015,64(7):3177-3189.
[24]王章权,陈友荣,尉理哲,等.优化网络生存时间的Sink节点移动路径选择算法[J].传感技术学报,2014,27(3):409-415.(WANG Z Q,CHEN Y R,YU L Z,et al.Mobile path selection algorithm of sink node for optimizing network lifetime[J].Chinese Journal of Sensor and Actuators,2014,27(3):409-415.)
[25]曾又姣,金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统,2004,10(2):205-208.(ZENG Y J,JIN Y.Optimization of placement order of placement machine based on genetic algorithm[J].Computer Integrated Manufacturing Systems,2004,10(2):205-208.)
[26]ZENG K,REN K,LOU W,et al.Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply[J].Wireless Networks,2009,15(1):39-51.
[2]CHATZIGIANNAKIS I,KINALIS A,NIKOLETSEAS S.Efficient data propagation strategies in wireless sensor networks using a single mobile sink[J].Computer Communications,2008,31(5):896-914.
[3]KHAN A W,ABDULLAH A H,ANISI M H,et al.A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[J].Sensors,2014,14(2):2510-2548.
[4]SUN W,YANG Z,ZHANG X,et al.Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks:a survey[J].IEEE Communications Surveys&Tutorials,2014,16(3):1448-1459.
[5]张惠麒,林志贵,李敏,等.基于移动sink节点的路由协议的比较与分析[J].计算机科学,2014,41(S1):276-280.(ZHANG HQ,LIN Z G,LI M,et al.Comparison and analysis of routing protocol based on mobile sink[J].Computer Science,2014,41(S1):276-280.)
[6]GU Y,REN F,JI Y,et al.The evolution of sink mobility management in wireless sensor networks:a survey[J].IEEE Communications Surveys&Tutorials,2016,18(1):507-524.
[7]LIN C-J,CHOU P-L,CHOU C-F.HCDD:hierarchical clusterbased data dissemination in wireless sensor networks with mobile sink[C]//IWCMC'06:Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing.New York:ACM,2006:1189-1194.
[8]HAMIDA E B,CHELIUS G.A line-based data dissemination protocol for wireless sensor networks with mobile sink[C]//ICC'08:Proceedings of the 2008 IEEE International Conference on Communications.Piscataway,NJ:IEEE,2008:2201-2205.
[9]MOTTAGHI S,ZAHABI M R.Optimizing LEACH clustering algorithm with mobile sink and rendezvous nodes[J].AEU-International Journal of Electronics and Communications,2015,69(2):507-514.
[10]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNANH.Energy-efficient communication protocols for wireless microsensor networks[C]//HICSS'00:Proceedings of the 33rd Hawaii International Conference on Systems Sciences.Washington,DC:IEEE Computer Society,2000,8:8020.
[11]BHATTI R,KAUR G.Virtual grid based energy efficient mobile sink routing algorithm for WSN[C]//Proceedings of the 11th International Conference on Intelligent Systems and Control.Piscataway,NJ:IEEE,2017:30-33.
[12]梁青,焦峰.WSN中基于二分法与移动Sink的数据收集协议[J].计算机工程,2016,42(12):39-43.(LIANG Q,JIAO F.Data collection protocol for WSN based on dichotomy and mobile sink[J].Computer Engineering,2016,42(12):39-43.)
[13]YUN Y,XIA Y.Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications[J].IEEETransactions on Mobile Computing,2010,9(9):1308-1318.
[14]林德钰,王泉,刘伎昭.无线传感网的移动与静态sink相结合的节能策略[J].哈尔滨工业大学学报,2016,48(11):162-168.(LIN D Y,WANG Q,LIU J Z.Energy-saving strategy by combining mobile and static sink schemes for wireless sensor networks[J].Journal of Harbin Institute of Technology,2016,48(11):162-168.)
[15]王章权,陈友荣,任条娟,等.数据传输时延和跳数受限的Sink节点移动路径选择算法[J].传感技术学报,2016,29(4):583-592.(WANG Z Q,CHEN Y R,REN T J,et al.Sink node moving path selection algorithm limited by data transmission delay and hops[J].Chinese Journal of Sensor and Actuators,2016,29(4):583-592.)
[16]PAVITHRA H,SHIVASHANKAR,POORNIMA G R.An efficient mobile sink path selection approach for WSN's[C]//Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics Information Communication Technology.Piscataway,NJ:IEEE,2016:151-155.
[17]王薇,史浩山,黄鹏宇,等.基于二次栅格划分的移动sink最小路径构建算法[J].西北工业大学学报,2016,34(6):1016-1021.(WANG W,SHI H S,HUANG P Y,et al.A constructing mobile path minimal path algorithm based on quadratic grid[J].Journal of Northwestern Polytechnical University,2016,34(6):1016-1021.)
[18]于志博,孔祥雪,裴金金.移动Sink的传感器网络路径优化策略[J].传感器与微系统,2016,35(11):44-46.(YU Z B,KONG X X,PEI J J.Mobile sink-based path optimization strategy in wireless sensor networks[J].Transducer and Microsystem Technologies,2016,35(11):44-46.)
[19]陶志勇,蒋守凤.基于簇首移动的无线传感器网络路由算法[J].计算机工程与应用,2016,52(5):75-78.(TAO Z Y,JIANG S F.Clustering algorithm for wireless sensor networks with mobile cluster heads[J].Computer Engineering and Applications,2016,52(5):75-78.)
[20]SHI Y,HOU Y T.Theoretical results on base station movement problem for sensor network[C]//INFOCOM 2008:Proceedings of the 27th Conference on Computer Communications.Piscataway,NJ:IEEE,2008:1-5.
[21]HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNANH.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2000,1(4):660-670.
[22]TASHTARIAN F,MOGHADDAM M H Y,SOHRABY K,et al.ODT:optimal deadline-based trajectory for mobile sinks in WSN:a decision tree and dynamic programming approach[J].Computer Networks,2015,77:128-143.
[23]TASHTARIAN F,HOSSEIN Y M M,SOHRABY K,et al.On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks[J].IEEE Transactions on Vehicular Technology,2015,64(7):3177-3189.
[24]王章权,陈友荣,尉理哲,等.优化网络生存时间的Sink节点移动路径选择算法[J].传感技术学报,2014,27(3):409-415.(WANG Z Q,CHEN Y R,YU L Z,et al.Mobile path selection algorithm of sink node for optimizing network lifetime[J].Chinese Journal of Sensor and Actuators,2014,27(3):409-415.)
[25]曾又姣,金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统,2004,10(2):205-208.(ZENG Y J,JIN Y.Optimization of placement order of placement machine based on genetic algorithm[J].Computer Integrated Manufacturing Systems,2004,10(2):205-208.)
[26]ZENG K,REN K,LOU W,et al.Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply[J].Wireless Networks,2009,15(1):39-51.