Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network

doi:10.11772/j.issn.1001-9081.2017.08.2150

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (8): 2150-2156.DOI: 10.11772/j.issn.1001-9081.2017.08.2150

Previous Articles Next Articles

Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network

MO Wenjie^1,2, ZHENG Lin^1,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

Received:2017-02-08 Revised:2017-02-26 Online:2017-08-10 Published:2017-08-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61371107),the Foundation of Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL061501).

优化网络生命周期和最短化路径的WSN移动sink路径规划算法

莫文杰^1,2, 郑霖^1,2

1. 广西无线宽带通信与信号处理重点实验室(桂林电子科技大学), 广西桂林 541004;
2. 桂林电子科技大学信息与通信学院, 广西桂林 541004

通讯作者: 郑霖
作者简介:莫文杰(1990-),男,广西柳州人,硕士研究生,主要研究方向:无线传感器网络、路由协议;郑霖(1973-),男,广西桂林人,教授,博士,主要研究方向:无线超宽带通信、无线传感器网络、移动通信、自适应信号处理、扩频通信、分组无线网络。
基金资助:
国家自然科学基金资助项目（61371107）；广西无线宽带通信与信号处理重点实验室基金资助项目（GXKL061501）。

Abstract

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.

Key words: Wireless Sensor Network (WSN), mobile sink, data collection, double-stranded genetic algorithm, path planning, network lifetime

摘要： 为了缓解无线传感器网络（WSN）中传感器节点分布不均匀、传感器节点感知数据量不同而造成能耗不均衡、"热区"等问题，提出一种优化网络生命周期和最短化路径的WSN移动sink路径规划算法（MSPPA）。首先，通过监测区域网格化，在每个网格内分布若干个移动sink候选访问站点，sink在每个网格中选择一个站点停留收集网格中节点数据；然后，分析所有传感器节点的生命周期与sink站点选择的关系，建立权衡网络生命周期和sink移动路径的优化模型；最后，使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点，得到移动sink节点遍历所有网格收集数据的路径。仿真结果显示，与已有的低功耗自适应分簇（LEACH）算法与基于移动sink节点与集合节点（RN）的优化LEACH分簇算法（MS-LEACH-RN）相比，MSPPA在网络生命周期方面提高了60%，且具有良好的能耗均衡性。实验结果表明，MSPPA能有效缓解能量不均衡、"热区"问题，延长网络生命周期。

关键词: 无线传感器网络, 移动sink, 数据收集, 双链遗传算法, 路径规划, 网络生命周期

CLC Number:

TN926

MO Wenjie, ZHENG Lin. Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network[J]. Journal of Computer Applications, 2017, 37(8): 2150-2156.

莫文杰, 郑霖. 优化网络生命周期和最短化路径的WSN移动sink路径规划算法[J]. 计算机应用, 2017, 37(8): 2150-2156.

References

[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.

Path planning algorithm for mobile sink with optimized network lifetime and shortest path in wireless sensor network

优化网络生命周期和最短化路径的WSN移动sink路径规划算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[2]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[3]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.
[4]	HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm [J]. Journal of Computer Applications, 2021, 41(2): 390-397.
[5]	SUN Huan, CHEN Hongbin. Node redeployment strategy based on firefly algorithm for wireless sensor network [J]. Journal of Computer Applications, 2021, 41(2): 492-497.
[6]	WANG Jialiang, LI Shuhua, ZHANG Haitao. Obstacle avoidance path planning algorithm of quad-rotor helicopter based on Bayesian estimation and region division traversal [J]. Journal of Computer Applications, 2021, 41(2): 384-389.
[7]	WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383.
[8]	LI Wei, JIN Shijun. Optimal path convergence method based on artificial potential field method and informed sampling [J]. Journal of Computer Applications, 2021, 41(10): 2912-2918.
[9]	LIU Sijia, TONG Xiangrong. Urban transportation path planning based on reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 185-190.
[10]	HAN Yulao, FANG Dingyi. Lightweight coverage hole detection algorithm based on relative position of link intersections [J]. Journal of Computer Applications, 2020, 40(9): 2698-2705.
[11]	HU Runyan, LI Cuiran. Clustering algorithm of energy harvesting wireless sensor network based on fuzzy control [J]. Journal of Computer Applications, 2020, 40(9): 2691-2697.
[12]	XU Xiaoqiang, QIN Pinle, ZENG Jianchao. Orthodontic path planning based on improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2020, 40(7): 1938-1943.
[13]	QI Xuanxuan, HUANG Jiajun, CAO Jian'an. Path planning for unmanned vehicle based on improved A^* algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2021-2027.
[14]	HAN Yulao, FANG Dingyi. Multi-objective path planning algorithm for mobile charging devices jointing wireless charging and data collection [J]. Journal of Computer Applications, 2020, 40(6): 1745-1750.
[15]	LU Guangyue, ZHOU Liang, LYU Shaoqing, SHI Cong, SU Keke. Outlier node detection algorithm in wireless sensor networks based ongraph signal processing [J]. Journal of Computer Applications, 2020, 40(3): 783-787.