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

俸皓; 罗蕾; 王勇; 叶苗

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略
- Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm
- 通信学报 2017年38卷第3期页码：112-123
- 作者机构：
  
  1. 电子科技大学计算机学院，四川成都 611731
  2. 桂林电子科技大学计算机与信息安全学院，广西桂林 541004
  3. 桂林电子科技大学自动检测技术与仪器重点实验室，广西桂林 541004
  4. 桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验室，广西桂林 541004
- 作者简介：
  
  [ "俸皓（1978-），男，广西桂林人，电子科技大学博士生，主要研究方向为无线传感器网络、物联网、嵌入式实时系统、计算智能。" ]
  [ "罗蕾（1967-），女，四川成都人，电子科技大学教授、博士生导师，主要研究方向为嵌入式实时系统及基础软件、网络计算、移动计算等。" ]
  [ "王勇（1964-），男，四川南充人，博士，桂林电子科技大学教授，主要研究方向为智能计算、泛在网研究及应用、计算机网络技术。" ]
  [ "叶苗（1977-），男，广西桂林人，博士，桂林电子科技大学教授、硕士生导师，主要研究方向为无线传感器网络、进化计算、人工智能。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61662018);国家自然科学基金资助项目(61163058);国家自然科学基金资助项目(61363070);中国博士后科学基金资助项目(2016M602922XB);广西省自然科学基金资助项目(2016GXNSFAA380153);广西自动检测技术与仪器重点实验室基金资助项目(YQ17205)
- DOI：10.11959/j.issn.1000-436x.2017070
  中图分类号： TP393; TP212
- 网络出版日期：2017-03，
  
  纸质出版日期：2017-03-15
- 稿件说明：
移动端阅览
俸皓, 罗蕾, 王勇, 等. 无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略[J]. 通信学报, 2017,38(3):112-123.

Hao FENG, Lei LUO, Yong WANG, et al. 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.
俸皓, 罗蕾, 王勇, 等. 无线传感网中基于时变多旅行商和遗传算法的多目标数据采集策略[J]. 通信学报, 2017,38(3):112-123. DOI： 10.11959/j.issn.1000-436x.2017070.

Hao FENG, Lei LUO, Yong WANG, et al. 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. DOI： 10.11959/j.issn.1000-436x.2017070.

摘要

相比传统数据路由的数据采集技术，无线移动节点技术逐步成为近年来无线传感网中数据采集的另一种新技术。由于其中对静态节点遍历次序的求解本身是一个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.

关键词

Keywords

references

AKYILDIZ I F , SU W , SANKARASUBRAMANIAM Y , et al . Wireless sensor networks:a survey [J ] . Computer Networks , 2002 , 38 ( 4 ): 393 - 422 .

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 .

XU X , LUO J , ZHANG Q . Delay tolerant event collection in sensor networks with mobile sink [C ] // Proc IEEE INFOCOM . 2010 .

PANICHPAPIBOON S , FERRARI G , TONGUZ O . Optimal transmit power in wireless sensor networks [J ] . IEEE Trans Mobile Computing , 2006 , 5 ( 10 ): 1432 - 1447 .

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 .

ZHUANG Y , PAN J , CAI L . Minimizing energy consumption with probabilistic distance models in wireless sensor networks [C ] // IEEE INFOCOM . 2010 .

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 .

DANTU K , RAHIMI M , SHAH H , et al . Robomote:enabling mobility in sensor networks [C ] // The IEEE IPSN . 2005 : 404 - 409 .

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 .

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 .

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 .

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 .

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 .

SUGIHARA R , GUPTA R K . Path planning of data mules in sensor networks [J ] . ACM Transactions on Sensor Networks , 2011 , 8 ( 1 ): 1 - 27 .

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 .

BEKTAS T . The multiple traveling salesman problem:an overview of formulations and solution procedures [J ] . Omega , 2006 , 34 ( 3 ): 209 - 219 .

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 .

VENKATESH P , SINGH A . Two metaheuristic approaches for the multiple traveling salesperson problem [J ] . Applied Soft Computing , 2015 , 26 : 74 - 89 .

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 .

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 .

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

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 .

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 .

WANG H , WU Z J , RAHNAMAYAN S , et al . Multi-strategy ensemble aritificial bee colony algorithm [J ] . Information Sciences , 2014 , 279 : 587 - 603 .

HELSGAUN K . General k-opt submoves for the Lin-Kernighan TSP heuristic [J ] . Mathematical Programming Computation , 2009 , 1 ( 2-3 ): 119 - 163 .

BÄCK T . Evolutionary algorithms in theory and practice [M ] . New York : Oxford University PressPress , 1994 .

丁煦 , 韩江洪 , 石雷 , 等 . 可充电无线传感器网络动态拓扑问题研究 [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 .

BÄCK T . Evolutionary algorithms in theory and practice:evolution strategies,evdutionary programming,genetic algorithms [M ] . New York : Oxford University PressPress , 1998 : 26 - 27 .

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 .

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 .

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 .

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 .

浏览量

1056

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向WSN异常节点检测的融合重构机制与对比学习方法

无等待与时隙映射复用结合的时间触发流调度方法

基于决策性能评估的多波束低地球轨道卫星网络资源分配算法

基于半固定分簇的无线传感器网络节能分簇路由算法

面向非地面网络多QoS保障的低地球轨道卫星星座设计