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

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

Abstract

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

CLC Number:

TP393
TP212

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.

Figures/Tables 10

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

Metrics

Recommended 0

No Suggested Reading articles found!

速度/(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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 32

Related Articles 15

Metrics

Recommended 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]	Yue ZHAO, Zan LI, Bing LI, Benjian HAO. TDoA localization-refused area analysis and node placement strategy research [J]. Journal on Communications, 2023, 44(1): 1-13.
[2]	Sifeng ZHU, Jianghao CAI, Zhengyi CHAI, Enlin SUN. Multi-objective optimal offloading decision for cloud-edge collaborative computing scenario in Internet of vehicles [J]. Journal on Communications, 2022, 43(6): 223-234.
[3]	Cuiran LI, Xuejie WANG, Jianli XIE, Anqi LYU. Routing algorithm for railway monitoring linear WSN based on improved PSO [J]. Journal on Communications, 2022, 43(5): 155-165.
[4]	Hang QIU, Hongbo TANG, Wei YOU, Yu ZHAO, Yi BAI. QGA-based network service extension algorithm in NFV [J]. Journal on Communications, 2022, 43(11): 44-52.
[5]	Yuliang CONG, Wenxi SUN, Ke XUE, Zhihong QIAN, Mianshu CHEN. Research on task offloading strategy of Internet of vehicles based on improved hybrid genetic algorithm [J]. Journal on Communications, 2022, 43(10): 77-85.
[6]	Xiujuan DU, Lijuan WANG, Jingping LIU, Long JIN. Ranging localization method for nodes in underwater wireless sensor network based on zeroing neural dynamics [J]. Journal on Communications, 2022, 43(10): 177-185.
[7]	Xin SU, Haoyang XUE, Yiqing ZHOU, Jinxiu ZHU. Research on computing offloading method for maritime observation monitoring sensor network [J]. Journal on Communications, 2021, 42(5): 149-163.
[8]	Aijing SUN, Shichang LI, Yicai ZHANG. WSN clustering routing algorithm based on PSO optimized fuzzy C-means [J]. Journal on Communications, 2021, 42(3): 91-99.
[9]	Tianyi ZHU,Fenghua LI,Wei JIN,Yunchuan GUO,Liang FANG,Lin CHENG. Cross-domain access control policy mapping mechanism for balancing interoperability and autonomy [J]. Journal on Communications, 2020, 41(9): 29-48.
[10]	Pei ZHANG,Shuaijun LIU,Zhiguo MA,Xiaohui WANG,Junde SONG. Improved satellite resource allocation algorithm based on DRL and MOP [J]. Journal on Communications, 2020, 41(6): 51-60.
[11]	Yi LU,Mengying XU,Jie ZHOU. Multi-constraints QoS routing optimization based on improved immune clonal shuffled frog leaping algorithm [J]. Journal on Communications, 2020, 41(5): 141-149.
[12]	Tianjing WANG,Xiuqin LI,Guangwei BAI,Hang SHEN. Multi-target localization algorithm based on adaptive grid in wireless sensor network [J]. Journal on Communications, 2019, 40(7): 197-207.
[13]	SU Mingfeng,WANG Guojun,LI Renfa. Multidimensional QoS cloud computing resource scheduling method based on stakeholder perspective [J]. Journal on Communications, 2019, 40(6): 102-115.
[14]	Xiaochen HAO,Ning YAO,Lixia XIE,Jiaojiao WANG,Liyuan WANG. Research on WSN lifetime optimization game algorithm combined power and channel [J]. Journal on Communications, 2019, 40(4): 62-70.
[15]	Linlan LIU,Shengrong GAO,Jian SHU. Link quality prediction based on random forest [J]. Journal on Communications, 2019, 40(4): 202-211.