联合充电和数据收集的WCE多目标路径规划算法

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

通信学报 ›› 2018, Vol. 39 ›› Issue (10): 22-33.doi: 10.11959/j.issn.1000-436x.2018216

联合充电和数据收集的WCE多目标路径规划算法

魏振春^1,^2,³,孙仁浩¹,吕增威¹,韩江洪^1,^2,³,石雷^1,^2,³(),徐俊逸¹

¹ 合肥工业大学计算机与信息学院，安徽合肥 230009
² 安全关键工业测控技术教育部工程研究中心，安徽合肥 230009
³ 工业安全与应急技术安徽省重点实验室，安徽合肥 230009

修回日期:2018-08-22 出版日期:2018-10-01 发布日期:2018-11-23
作者简介:魏振春（1978-），男，宁夏青铜峡人，博士，合肥工业大学副教授、硕士生导师，主要研究方向为物联网、无线传感器网络、智能计算。|孙仁浩（1992-），男，吉林扶余人，合肥工业大学硕士生，主要研究方向为无线传感器网络、智能优化算法。|吕增威（1989-），男，山东烟台人，合肥工业大学博士生，主要研究方向为物联网、智能计算、机器学习。|韩江洪（1954-），男，江苏南京人，合肥工业大学教授、博士生导师，主要研究方向为计算机控制、物联网、无线网络。|石雷（1980-），男，安徽合肥人，博士，合肥工业大学副教授、硕士生导师，主要研究方向为无线网络、干扰管理。|徐俊逸（1990-），男，江苏常州人，合肥工业大学博士生，主要研究方向为物联网、软件定义网络、网络功能虚拟化。
基金资助:
国家自然科学基金资助项目(61502142);国家自然科学基金资助项目(61501161);国家自然科学基金资助项目(61370088)

Path planning algorithm for WCE with joint energy replenishment and data collection based on multi-objective optimization

Zhenchun WEI^1,^2,³,Renhao SUN¹,Zengwei LYU¹,Jianghong HAN^1,^2,³,Lei SHI^1,^2,³(),Junyi XU¹

¹ School of Computer and Information,Hefei University of Technology,Hefei 230009,China
² Engineering Research Center of Safety-Critical Industry Measure and Control Technology of Ministry of Education,Hefei 230009,China
³ Anhui Province Key Laboratory of Industry Safety and Emergency Technology,Hefei 230009,China

Revised:2018-08-22 Online:2018-10-01 Published:2018-11-23
Supported by:
The National Natural Science Foundation of China(61502142);The National Natural Science Foundation of China(61501161);The National Natural Science Foundation of China(61370088)

摘要/Abstract

摘要：

在无线可充电传感器网络中的可移动的无线充电设备（WCE，wireless charging equipment）自身携带的能量有限的情况下，设计了 WCE 的充电策略和数据收集策略，并在此基础上以最大化 WCE 总能量的利用率和最小化网络中节点数据传输的平均时延为目标建立了联合充电和数据收集的WCE多目标路径规划模型，提出了一种基于精英策略的多目标蚁群优化算法，改进了蚂蚁状态转移策略和信息素更新策略，求得了该多目标问题的Pareto最优解集。以20个传感器节点为例，通过仿真实验分析了蚁群系统参数对ES-MOAC算法的影响，50组对比实验表明ES-MOAC算法在求解该问题上得到的能量利用率的平均值比NSGA-II算法增加了4.53%，网络中所有节点数据传输的平均时延的平均值比NSGA-II算法缩短了5.12%。

关键词: 无线可充电传感器网络, 联合充电和数据收集, 路径规划, 多目标蚁群优化算法

Abstract:

Considering limited energy of the wireless charging equipment (WCE) in wireless rechargeable sensor network,an energy replenishment strategy and a data collection strategy are designed.On the basis of these,a path planning model for WCE with functions of joint energy replenishment and data collection based on multi-objective optimization is constructed with two optimization objectives,maximizing the total energy utility of WCE and minimizing the average delay of data transmission of all the sensor nodes in the network.To deal with it,a multi-objective ant colony optimization algorithm based on elitist strategy was proposed,where the state transition strategy and the pheromone updating strategy were improved.Then,the Pareto set was obtained in terms of this multi-objective optimization problem.The parameter setting of ant colony algorithm’s effects on the proposed algorithm were analyzed under 20 sensor nodes.50 groups of contrastive experiments show that the average number of energy utilization obtained by ES-MOAC algorithm is 4.53% higher than that of NSGA-II algorithm.The average number of average delay of all node data transmission obtained by ES-MOAC algorithm is 5.12% lower than that of NSGA-II algorithm.

Key words: wireless rechargeable sensor network, joint energy replenishment and data collection, path planning

中图分类号:

TP393

魏振春,孙仁浩,吕增威,韩江洪,石雷,徐俊逸. 联合充电和数据收集的WCE多目标路径规划算法[J]. 通信学报, 2018, 39(10): 22-33.

Zhenchun WEI,Renhao SUN,Zengwei LYU,Jianghong HAN,Lei SHI,Junyi XU. Path planning algorithm for WCE with joint energy replenishment and data collection based on multi-objective optimization[J]. Journal on Communications, 2018, 39(10): 22-33.

图/表 14

图1

图2

图3

图4

图5

表1

图6

图7

表2

表3

图8

表4

20个节点下ES-MOAC算法和NSGA-II算法计算结果比较"

指标	算法	最优值	最差值	平均值	中间值
Φ	ES-MOAC	86.19%	56.02%	71.28%	71.43%
	NSGA-II	85.42%	52.21%	68.19%	67.28%
$\bar{Δ τ} / s$	ES-MOAC	1 380.42	8 971.85	4 404.85	4 411.43
	NSGA-II	1 541.12	9 341.52	4 642.56	4 566.49
ER	ES-MOAC	49	25	36	35
	NSGA-II	34	15	26	26
SP	ES-MOAC	2 416.57	25.41	765.86	487.96
	NSGA-II	2 845.11	60.43	1 025.25	833.30
$M_{3}^{*}$	ES-MOAC	5 655.37	8.98	512.88	121.83
	NSGA-II	6 520.66	9.82	539.42	129.01

表4

图9

表5

50个节点下ES-MOAC算法和NSGA-II算法计算结果比较"

指标	算法	最优值	最差值	平均值	中间值
Φ	ES-MOAC	94.02%	75.83%	84.56%	84.76%
	NSGA-II	92.56%	73.60%	82.61%	83.58%
$\bar{Δ τ} / s$	ES-MOAC	3 631.86	9 962.58	6 021.37	6 268.39
	NSGA-II	3 858.73	9 968.41	6 356.45	6 243.50
ER	ES-MOAC	43	28	37	41
	NSGA-II	29	15	20	21
SP	ES-MOAC	40.31	765.63	367.54	540.51
	NSGA-II	43.06	876.50	502.47	685.70
$M_{3}^{*}$	ES-MOACNSGA-II	348.59356.08	11.7212.45	138.63142.45	159.40163.84

表5

参考文献 19

[1]	LIAN J , NAIK K , AGNEW G B . Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J]. International Journal of Distributed Sensor Networks, 2006,2(2): 121-145.
[2]	OLARIU S , STOJMENOVIC I . Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]// IEEE International Conference on Computer Communications. 2006: 2505-2516.
[3]	郭剑, 孙力娟, 许文君 ,等. 基于移动 sink 的无线传感器网络数据采集方案[J]. 通信学报, 2012,33(9): 176-184.
	GUO J , SUN L J , XU W J ,et al. Mobile sink-based data collection scheme for wireless sensor networks[J]. Journal on Communications, 2012,33(9): 176-184.
[4]	卢先领, 王莹莹 . 时延受限的移动sink数据收集算法[J]. 通信学报, 2014,35(10): 107-116.
	LU X L , WANG Y Y . Data collection algorithm for mobile sink in delay-constrained network[J]. Journal on Communications, 2014,35(10): 107-116.
[5]	CHANG J Y , SHEN T H . An efficient tree-based power saving scheme for wireless sensor networks with mobile sink[J]. IEEE Sensors Journal, 2016,16(20): 7545-7557.
[6]	IWATA M , TANG S H , OBANA S . Sink-based centralized transmission scheduling by using asymmetric communication and wake-up radio[C]// IEEE Wireless Communications and Networking Conference. 2017: 1-6.
[7]	XIE L G , SHI Y , HOU Y T ,et al. Wireless power transfer and applications to sensor networks[J]. Wireless Communications, 2013,20(4): 140-145.
[8]	YANG Y Y , WANG C . Wireless rechargeable sensor networks[M]. Heidelberg: Springer-VerlagPress, 2015.
[9]	SHI Y , XIE L G , HOU Y T ,et al. On renewable sensor networks with wireless energy transfer[C]// IEEE International Conference on Computer Communications. 2012: 1350-1358.
[10]	HE L , GU Y , PAN J P ,et al. On-demand charging in wireless sensor networks:theories and applications[C]// International Conference on Mobile Ad-Hoc and Sensor Systems. 2013: 28-36.
[11]	HE L , KONG L H , GU Y ,et al. Evaluating the on-demand mobile charging in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2015,14(9): 1861-1875.
[12]	XU J Y , YUAN X H , WEI Z C ,et al. A wireless sensor network recharging strategy by balancing lifespan of sensor nodes[C]// IEEE Wireless Communications and Networking Conference. 2017: 1-6.
[13]	陈花, 魏振春, 韩江洪 ,等. 无线充电设备能量受限的 WRSNs 周期性充电规划[J]. 电子测量与仪器学报, 2017,31(7): 1031-1039.
	CHENG H , WEI Z C , HAN J H ,et al. Periodic charging strategy of energy-constrained wireless charging equipment in WRSNs[J]. Journal of Electronic Measurement and Instrumentation, 2017,31(7): 1031-1039.
[14]	丁煦, 韩江洪, 石雷 ,等. 可充电无线传感器网络动态拓扑问题研究[J]. 通信学报, 2015,36(1): 133-145.
	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): 133-145.
[15]	XIE L , SHI Y , HOU Y T ,et al. A mobile platform for wireless charging and data collection in sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2015,33(8): 1521-1533.
[16]	WANG C , LI J , YE F ,et al. A mobile data gathering framework for wireless rechargeable sensor networks with vehicle movement costs and capacity constraints[J]. IEEE Transactions on Computers, 2016,65(8): 2411-2427.
[17]	GUO S T , WANG C , YANG Y Y . Mobile data gathering with wireless energy replenishment in rechargeable sensor networks[C]// IEEE International Conference on Computer Communications. 2013: 1932-1940.
[18]	ZHAO M , LI J , YANG Y Y . A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2014,13(12): 2689-2705.
[19]	DEB K , PRATAP A , AGARWAL S ,et al. A fast and elitist multi-objective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2): 182-197.

节点序号	坐标/m	节点序号	坐标/m
1	（342,112）	11	（609,579）
2	（198,192）	12	（827,504）
3	（758,119）	13	（757,734）
4	（921,320）	14	（287,643）
5	（946,742）	15	（253,922）
6	（854,847）	16	（103,777）
7	（680,979）	17	（559,490）
8	（656,769）	18	（277,396）
9	（128,490）	19	（54,489）
10	（486,813）	20	（465,280）

单轮行驶路径	WCE行驶能量开销/J	WCE充电能量开销/J
0-1-13-4-12-0	18 098.38	13 574.76
0-2-20-17-11-8-0	18 469.46	15 462.04
0-18-16-10-7-0	18 783.94	16 601.46
0-3-6-5-0	17 503.66	16 945.39
0-19-9-14-15-0	17 462.01	17 492.82

单轮行驶路径	WCE行驶能量开销/J	WCE充电能量开销/J
0-19-9-16-15-10-14-18-2-0	19 982.67	5 487.37
0-1-20-17-11-8-7-0	19 540.78	5 647.44
0-3-4-12-5-6-13-0	19 734.08	5 782.05

联合充电和数据收集的WCE多目标路径规划算法

Path planning algorithm for WCE with joint energy replenishment and data collection based on multi-objective optimization

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 19

相关文章 4

Metrics

推荐阅读 0

[1]	付澍, 杨祥月, 张海君, 陈晨, 喻鹏, 简鑫, 刘敏. 物联网数据收集中无人机路径智能规划[J]. 通信学报, 2021, 42(2): 124-133.
[2]	王楠,周红磊,李金宝,黎玲利. 基于用户需求的景点路线利益规划算法[J]. 通信学报, 2018, 39(5): 189-198.
[3]	何灏,陈永锐,易卫东,李鸣. 无线可充电传感器网络中固定充电器的部署策略[J]. 通信学报, 2017, 38(Z1): 156-164.
[4]	崔焕庆,王英龙,郭强,吕家亮. 多移动信标辅助的分布式节点定位方法[J]. 通信学报, 2012, 33(3): 103-111.