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

Hao FENG; Lei LUO; Yong WANG; Miao YE

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- Multi-objective data collecting strategies for wireless sensor network based on the time variable multi-salesman problem and genetic algorithm
- Journal on Communications Vol. 38, Issue 3, Pages: 112-123(2017)
- 作者机构：
  
  1. 电子科技大学计算机学院，四川成都 611731
  2. 桂林电子科技大学计算机与信息安全学院，广西桂林 541004
  3. 桂林电子科技大学自动检测技术与仪器重点实验室，广西桂林 541004
  4. 桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验室，广西桂林 541004
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.11959/j.issn.1000-436x.2017070
  CLC： TP393; TP212
- Online First：2017-03，
  
  Published：15 March 2017
- 稿件说明：
移动端阅览
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：

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 .

Views

1553

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimization of air-ground cooperative communication performance for UAV-mounted STAR-RIS

GPS-independent lightweight reflective collaborative false data filtering scheme for sensor networks

Anomaly detection method for spatio-temporal correlation of WSN nodes based on graph prompt fine-tuning

Research on scenario recognition for THz channels based on mRMR-GA

Low-power-consumption road side unit deployment strategy for urban 2-D 5G Internet of vehicles

Related Author

Han Zhengjiang

Zhou Tao

Wang Erfu

Liu Zhixiong

Yin Hui

YE Miao

CUI Jing

HUANG Yuan

Related Institution

Electronic Engineering College, Heilongjiang University

School of Computer Science and Engineering, Changsha University

Guangxi Wireless Broadband Communication and Signal Processing Key Laboratory, Guilin University of Electronic Technology

School of Electronic Engineering and Automation, Guilin University of Electronic Technology

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications

AI问答

⁰