无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略

doi:10.11959/j.issn.1000-436x.2017070

通信学报 ›› 2017, Vol. 38 ›› Issue (3): 112-123.doi: 10.11959/j.issn.1000-436x.2017070

无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略

俸皓^1,^2,³,罗蕾¹,王勇^2,⁴,叶苗^3,⁴()

¹ 电子科技大学计算机学院，四川成都 611731
² 桂林电子科技大学计算机与信息安全学院，广西桂林 541004
³ 桂林电子科技大学自动检测技术与仪器重点实验室，广西桂林 541004
⁴ 桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验室，广西桂林 541004

修回日期:2017-02-07 出版日期:2017-03-01 发布日期:2017-04-13
作者简介:俸皓（1978-），男，广西桂林人，电子科技大学博士生，主要研究方向为无线传感器网络、物联网、嵌入式实时系统、计算智能。|罗蕾（1967-），女，四川成都人，电子科技大学教授、博士生导师，主要研究方向为嵌入式实时系统及基础软件、网络计算、移动计算等。|王勇（1964-），男，四川南充人，博士，桂林电子科技大学教授，主要研究方向为智能计算、泛在网研究及应用、计算机网络技术。|叶苗（1977-），男，广西桂林人，博士，桂林电子科技大学教授、硕士生导师，主要研究方向为无线传感器网络、进化计算、人工智能。
基金资助:
国家自然科学基金资助项目(61662018);国家自然科学基金资助项目(61163058);国家自然科学基金资助项目(61363070);中国博士后科学基金资助项目(2016M602922XB);广西省自然科学基金资助项目(2016GXNSFAA380153);广西自动检测技术与仪器重点实验室基金资助项目(YQ17205)

Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm

Hao FENG^1,^2,³,Lei LUO¹,Yong WANG^2,⁴,Miao YE^3,⁴()

¹ School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
² School of Computer Science and Information Security,Guilin University of Electronic Technology,Guilin 541004,China
³ Key Laboratory of Automatic Detecting Technology and Instruments ,Guilin University of Electronic Technology,Guilin 541004,China
⁴ Key Laboratory of Cognitive Radio and Information Processing,Guilin University of Electronic Technology,Guilin 541004,China

Revised:2017-02-07 Online:2017-03-01 Published:2017-04-13
Supported by:
The National Natural Science Foundation of China(61662018);The National Natural Science Foundation of China(61163058);The National Natural Science Foundation of China(61363070);Project Funded by China Postdoctoral Science Foundation(2016M602922XB);The Natural Science Foundation of Guangxi(2016GXNSFAA380153);Guangxi Key Laboratory of Automatic Detecting Technology and Instruments Fund Project(YQ17205)

摘要/Abstract

摘要：

相比传统数据路由的数据采集技术，无线移动节点技术逐步成为近年来无线传感网中数据采集的另一种新技术。由于其中对静态节点遍历次序的求解本身是一个NP难问题，提出了一种更为通用的基于多移动节点的多目标数据采集策略，将此问题建模为一种时变多旅行商问题模型。考虑到其属于NP难的离散优化问题模型，设计了一种针对问题特点的混合遗传算法来求解多个移动节点的规划路径，并对设计的算法给出了收敛性证明。通过对公开数据集的测试证实，所提基于多移动节点采集数据的时变旅行商问题模型和设计的求解算法确实能有效地提高数据采集的效率和实时性。

关键词: 无线传感器网络, 数据采集, 时变旅行商, 多移动节点, 遗传算法, 多目标优化

Abstract:

Comparing to the traditional data collecting method with data route,the technology of wireless mobile nodes has gradually became a new technique in the wireless sensor network.As the solution to the visiting order of the static nodes was an intrinsic NP-hard problem,a more general multi-objective data colleting strategies based on multi-mobile nodes was proposed.The proposed data collecting technique was abstracted as a model of time variable multiple traveling salesman problem.Belonging to a discrete optimal problem,the proposed model was solved by with a proposed hybrid genetic algorithm to determine the paths of the multi-mobile nodes.The convergence analysis of the proposed algorithm was given.With the experiment of open dataset,the proposed model based on the time variable multiple traveling salesman problem and the proposed hybrid genetic algorithm certify a certain improvement to the efficiency and real-time ability.

Key words: wireless sensor network, data collecting, time variable traveling salesman, multi-mobile nodes, genetic algorithm, multi-objective optimization

中图分类号:

TP393
TP212

俸皓,罗蕾,王勇,叶苗. 无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略[J]. 通信学报, 2017, 38(3): 112-123.

Hao FENG,Lei LUO,Yong WANG,Miao YE. Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm[J]. Journal on Communications, 2017, 38(3): 112-123.

图/表 10

图1

图2

图3

图4

表1

图5

表2

表3

图6

图7

参考文献 32

[1]	AKYILDIZ I F , SU W , SANKARASUBRAMANIAM Y ,et al. Wireless sensor networks:a survey[J]. Computer Networks, 2002,38(4): 393-422.
[2]	OLARIU S , STOJMENOVIC I . Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]// The IEEE INFOCOM. 2006: 1-12.
[3]	XU X , LUO J , ZHANG Q . Delay tolerant event collection in sensor networks with mobile sink[C]// Proc IEEE INFOCOM. 2010.
[4]	PANICHPAPIBOON S , FERRARI G , TONGUZ O . Optimal transmit power in wireless sensor networks[J]. IEEE Trans Mobile Computing, 2006,5(10): 1432-1447.
[5]	WU X B , CHEN G H , DAS S K . Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2008,19(5): 710-720.
[6]	ZHUANG Y , PAN J , CAI L . Minimizing energy consumption with probabilistic distance models in wireless sensor networks[C]// IEEE INFOCOM. 2010.
[7]	XUE Y , CHANG X , ZHONG S ,et al. An efficient energy hole alleviating algorithm for wireless sensor networks[J]. IEEE Transactions on Consumer Electronics, 2014,60(3): 347-355.
[8]	DANTU K , RAHIMI M , SHAH H ,et al. Robomote:enabling mobility in sensor networks[C]// The IEEE IPSN. 2005: 404-409.
[9]	SOMASUNDARA A , KANSAL A , JEA D D ,et al. Controllably mobile infrastructure for low energy embedded networks[J]. IEEE Trans on Mobile Computing, 2006,5(8): 958-973.
[10]	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,38(3): 1-30.
[11]	TODD M , MASCARENAS D , FLYNN E ,et al. A different approach to sensor networking for SHM:remote powering and interrogation with unmanned aerial vehicles[C]// Sixth International Workshop Structural Health Monitoring(IWSHM’07). 2007.
[12]	MAHDI C , NAOMI K , YASUAKI Y ,et al. Development and operation of underwater robot for autonomous tracking and monitoring of subsea plumes after oil spill and gas leak from seabed and analyses of measured data.applications to marine disaster prevention[M]. Springer, 2016: 17-93.
[13]	MA M , YANG Y Y , ZHAO M . Tour planning for mobile data-gathering mechanisms in wireless sensor networks[J]. IEEE Trans on Vehicular Technology, 2013,62(4): 1472-1483.
[14]	SUGIHARA R , GUPTA R K . Path planning of data mules in sensor networks[J]. ACM Transactions on Sensor Networks, 2011,8(1): 1-27.
[15]	YE M , WANG Y , DAI C ,et al. A hybrid genetic algorithm for the minimum exposure path problem of wireless sensor networks based on a numerical functional extreme model[J]. IEEE Transactions on Veh Technol, 2016,65(10): 8644-8657.
[16]	BEKTAS T . The multiple traveling salesman problem:an overview of formulations and solution procedures[J]. Omega, 2006,34(3): 209-219.
[17]	YE M , WANG Y P , DAI C ,et al. A hybrid genetic algorithm for the minimum exposure path problem of wireless sensor networks based on a numerical functional extreme model[J]. IEEE Transactions on Vehicular Technology, 2016,65(10): 8644-8657.
[18]	VENKATESH P , SINGH A . Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing, 2015,26: 74-89.
[19]	CARTER A E , RAGSDALE C T . A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J]. European Journal of Operational Research, 2006,175(1): 246-257.
[20]	SINGH A , BAGHEL A S . A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]. Soft Computing, 2009,13(1): 95-101.
[21]	LI K , DEB K , ZHANG Q F ,et al. Efficient nondomination level update method for steady-state evolutionary multiobjective optimization[J]. IEEE Transactions on Cybernetics, 2016(99).
[22]	LEUNG Y W , WANG Y P . Multiobjective programming using uniform design and genetic algorithm[J]. IEEE Transactions on Systems,Man,and Cybernetics,Part C Application & Reviews, 2000,30(3): 293-304.
[23]	DIWOLD K , ANDREJ A , ALEXANDER S ,et al. Performance evaluation of artificial bee colony optimization and new selection schemes[J]. Memetic Comp, 2011,3: 149-162.
[24]	WANG H , WU Z J , RAHNAMAYAN S ,et al. Multi-strategy ensemble aritificial bee colony algorithm[J]. Information Sciences, 2014,279: 587-603.
[25]	HELSGAUN K . General k-opt submoves for the Lin-Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009,1(2-3): 119-163.
[26]	B?CK T . Evolutionary algorithms in theory and practice[M]. New York: Oxford University PressPress, 1994.
[27]	丁煦, 韩江洪, 石雷 ,等. 可充电无线传感器网络动态拓扑问题研究[J]. 通信学报, 2015,36(1): 45-52.
	DING X , HAN J H , SHI L ,et al. Problem of the dynamic topology architecture of rechargeable wireless sensor networks[J]. Journal on Communications, 2015,36(1): 45-52.
[28]	B?CK T . Evolutionary algorithms in theory and practice:evolution strategies,evdutionary programming,genetic algorithms[M]. New York: Oxford University PressPress, 1998: 26-27.
[29]	HE L , PAN J P , XU J D . A progressive approach to reducing data collection latency in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing, 2013,12(7): 1308-1320.
[30]	APPLEGATE D L , BIXBY R E,CHVáTAL V ,et al. Certification of an optimal TSP tour through 85,900 cities[J]. Operations Research Letters, 2009,37(1): 11-15.
[31]	MA M , YANG Y Y . SenCar:an energy-efficient data gathering mechanism forlarge-scale multihop sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2007,18(10): 1476-1488.
[32]	GAO S , ZHANG H , DAS S K . Efficient data collection in wireless sensor networks with path-constrained mobile sinks[J]. Mobile Computing, 2011,10(4): 592-608.

速度/(m·s^?1)	移动路径	采集时间/s	采集数据量/KB
1	11→14→2→6→8→15→5→9→20→13→3→12→18→1→16→7→4→19→17→10	6 016	15 145
3	16→7→4→19→10→17→11→14→9→13→5→3→12→1→18→15→8→6→20→2	2 042	12 946
5	19→10→17→14→11→13→9→5→18→3→15→12→1→16→8→2→20→6→7→4	1 535	13 641
10	17→14→11→20→6→8→2→13→9→15→5→18→12→3→1→16→7→19→10→4	916	12 112
20	16→5→9→15→6→2→8→20→11→14→13→18→12→3→1→7→4→10→17→19	715	12 349

速度/(m·s^?1)	移动路径1	移动路径2	采集时间/s	采集数据量/KB
1	8→6→15→18→12→3→5→9→13→20→14→11→2	1→16→7→4→19→10→17	3 587	14 107
3	8→15→13→5→9→6→14→10→17	19→4→2→20→11→18→3→12→1→16→7	1 469	14 263
5	8→6→2→10→19→4→7→16→1→2	15→18→3→5→13→9→20→14→11→17	865	12 358
10	18→12→1→3→6→8→20→2→11	16→7→15→5→9→13→14→17→19→10→ 4	573	13 179
20	5→15→18→12→6→20→14→17→19→4	7→16→1→3→13→9→2→8→11→10	375	12 134

无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略

Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 32

相关文章 15

Metrics

推荐阅读 0

节点编号	坐标	R_i/(kbit·s^?1)	g_i,0/KB
1	(50,950)	18	24
2	(590,480)	19	5
3	(450,900)	17	25
4	(100,200)	19	27
5	(650,750)	20	11
6	(560,560)	12	2
7	(100,500)	12	27
8	(520,540)	18	25
9	(800,700)	19	0
10	(300,100)	17	5
11	(750,150)	8	25
12	(360,900)	17	23
13	(850,700)	20	4
14	(980,50)	19	2
15	(470,700)	10	27
16	(100,600)	17	4
17	(420,20)	17	15
18	(400,750)	17	4
19	(200,50)	19	12
20	(800,480)	17	2

[1]	赵越, 李赞, 李冰, 郝本建. TDoA定位盲区分析与节点部署策略研究[J]. 通信学报, 2023, 44(1): 1-13.
[2]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.
[3]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[4]	邱航, 汤红波, 游伟, 赵宇, 柏溢. NFV中基于量子遗传算法的网络服务扩展算法[J]. 通信学报, 2022, 43(11): 44-52.
[5]	丛玉良, 孙闻晞, 薛科, 钱志鸿, 陈绵书. 基于改进的混合遗传算法的车联网任务卸载策略研究[J]. 通信学报, 2022, 43(10): 77-85.
[6]	杜秀娟, 王丽娟, 刘静萍, 金龙. 基于归零神经动力学的水下无线传感器网络节点测距定位方法[J]. 通信学报, 2022, 43(10): 177-185.
[7]	苏新, 薛淏阳, 周一青, 朱金秀. 面向海洋观监测传感网的计算卸载方法研究[J]. 通信学报, 2021, 42(5): 149-163.
[8]	孙爱晶, 李世昌, 张艺才. 基于PSO优化模糊C均值的WSN分簇路由算法[J]. 通信学报, 2021, 42(3): 91-99.
[9]	黄小红, 张勇, 闪德胜, 钱叶魁, 韩璐, 李丹丹, 丛群. 基于多目标效用优化的分布式数据交易算法[J]. 通信学报, 2021, 42(2): 52-63.
[10]	诸天逸,李凤华,金伟,郭云川,房梁,成林. 互操作性与自治性平衡的跨域访问控制策略映射[J]. 通信学报, 2020, 41(9): 29-48.
[11]	张沛,刘帅军,马治国,王晓晖,宋俊德. 基于深度增强学习和多目标优化改进的卫星资源分配算法[J]. 通信学报, 2020, 41(6): 51-60.
[12]	卢毅,徐梦颖,周杰. 基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究[J]. 通信学报, 2020, 41(5): 141-149.
[13]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[14]	苏命峰,王国军,李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115.
[15]	李凤华,李子孚,李凌,张铭,耿魁,郭云川. 复杂网络环境下面向威胁监测的采集策略精化方法[J]. 通信学报, 2019, 40(4): 49-61.