Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network
MO Wenjie1,2, ZHENG Lin1,2
1. Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing(Guilin University of Electronic Technology), Guilin Guangxi 541004, China; 2. School of Information and Communication, Guilin University of Electronic Technology, Guilin Guangxi 541004, China
Abstract：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.
莫文杰, 郑霖. 优化网络生命周期和最短化路径的WSN移动sink路径规划算法[J]. 计算机应用, 2017, 37(8): 2150-2156.
MO Wenjie, ZHENG Lin. Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network. Journal of Computer Applications, 2017, 37(8): 2150-2156.
[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 H Q, 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 cluster-based 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, BALAKRISHNAN H. 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]. IEEE Transactions 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, BALAKRISHNAN H. 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.
2017, Vol. 37 
