带时间窗的无线可充电传感器网络多目标路径规划算法

doi:10.12263/DZXB.20211319

电子学报 ›› 2022, Vol. 50 ›› Issue (8): 1819-1829.DOI: 10.12263/DZXB.20211319

带时间窗的无线可充电传感器网络多目标路径规划算法

魏振春¹^,²^,³, 傅宇¹, 马仲军¹, 吕增威¹^,²^,³, 石雷¹^,²^,³, 张本宏¹^,²^,³

^1.合肥工业大学计算机与信息学院, 安徽合肥 230009
^2.安全关键工业测控技术教育部工程研究中心, 安徽合肥 230009
^3.工业安全与应急技术安徽省重点实验室, 安徽合肥 230009

收稿日期:2021-09-26 修回日期:2021-12-29 出版日期:2022-08-25
- 通讯作者:
- 吕增威
- 作者简介:
- 魏振春男，1978年生，宁夏青铜峡人.合肥工业大学副教授、研究生导师.主要研究方向为物联网、边缘计算、分布智能.E-mail: weicz@hfut.edu.cn
  傅宇男，1997年生，安徽安庆人.合肥工业大学硕士研究生.主要研究方向为物联网、边缘计算.E-mail: 1036824760@qq.com
  马仲军男，1997年生，安徽合肥人.合肥工业大学硕士研究生.主要研究方向为物联网、边缘计算.E-mail: 1242089794@qq.com
  吕增威男，1989年生，山东烟台人.合肥工业大学讲师.主要研究方向为物联网、智能计算、机器学习.E-mail: lzw@hfut.edu.cn
  石雷男，1980年生，安徽合肥人.合肥工业大学副教授、研究生导师.主要研究方向为边缘智能、物联网、无线网络.E-mail: thunder10@163.com
  张本宏男，1972年生，安徽无为人.合肥工业大学副教授、研究生导师.主要研究方向为车联网、边缘计算.E-mail: zhangbh@hfut.edu.cn
- 基金资助:
- 国家自然科学基金(62002097);安徽省科技重大专项(201903a05020049);安徽省自然科学基金(2108085MF202)

Multi-Objective Path Planning Algorithm for WRSN with Time Window

WEI Zhen-chun¹^,²^,³, FU Yu¹, MA Zhong-jun¹, LYU Zeng-wei¹^,²^,³, SHI Lei¹^,²^,³, ZHANG Ben-hong¹^,²^,³

^1.School of Computer and Information, Hefei University of Technology, Hefei, Anhui 230009, China
^2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei, Anhui 230009, China
^3.Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei, Anhui 230009, China

Received:2021-09-26 Revised:2021-12-29 Online:2022-08-25 Published:2022-09-08
- Corresponding author:
- LYU Zeng-wei
- Supported by:
- National Natural Science Foundation of China(62002097);Science and Technology Major Project of Anhui Province(201903a05020049);Natural Science Foundation of Anhui Province(2108085MF202)

摘要/Abstract

摘要：

现阶段无线可充电传感器网络的研究中，充电规划问题往往只考虑单一目标，没有考虑能量空洞问题对无线充电设备（Wireless Charging Equipment，WCE）路径规划以及网络整体性能的影响.基于充电时间窗和惩罚函数，以最大化网络中WCE的能量利用率和最小化节点惩罚值为目标，提出了带时间窗的多目标路径规划模型，优化WCE对节点的充电时间并提高WCE的能量利用率.为求解多目标优化问题，在多目标连续烟花算法的基础上，提出了一种多目标离散烟花算法，通过烟花爆炸操作加快收敛速度并防止陷入局部最优.仿真结果表明，相较于传统算法，本文提出的算法所求得的Pareto最优解的分布均匀性提升22.5%以上，分布范围性能提升14.5%以上.

关键词: 无线可充电传感器网络, 时间窗, 移动充电规划, 多目标优化, 离散烟花算法

Abstract:

In the current research of wireless rechargeable sensor networks, the charging planning problem often considers a single goal only, without considering the impact of the energy hole problem on the path planning of the wireless harging equipment(WCE) and the performance of the entire network. Based on the charging time window and penalty function, to maximize the energy utilization of WCE in the network and minimize the node penalty value, a multi-objective path planning model with time window is proposed to optimize the charging time of WCE to nodes and improve the energy utilization of WCE. To solve the multi-objective optimization problem, based on the multi-objective continuous firework algorithm, a multi-objective discrete firework algorithm is proposed, which speeds up the convergence speed and avoids falling into the local optimum through the firework explosion operation. The simulation results show that compared with the traditional algorithm, the Pareto optimal solution obtained by the algorithm proposed in this paper has at least 22.5% improvement in the distribution uniformity and 14.5% improvement in the performance of distribution range.

Key words: wireless rechargeable sensor network, time window, mobile charging planning, multi-objective optimization, discrete firework algorithm

中图分类号:

TP393

魏振春, 傅宇, 马仲军, 等. 带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829.

Zhen-chun WEI, Yu FU, Zhong-jun MA, et al. Multi-Objective Path Planning Algorithm for WRSN with Time Window[J]. Acta Electronica Sinica, 2022, 50(8): 1819-1829.

图/表 13

图1 网络模型示意图

表1 本文的符号及含义

符号	定义	符号	定义
WCE	无线充电设备	$E l$	节点充电能量下限
$S$	固定充电服务站	$U$	WCE的充电功率
$E m a x$	节点充电容量最大值	$v$	WCE的平均移动速度
$E m i n$	节点充电容量最小值	$E M$	WCE携带的最大移动能量
$E h$	节点充电能量上限	$E C$	WCE携带的最大充电能量

表1 本文的符号及含义

符号	定义	符号	定义
WCE	无线充电设备	$E l$	节点充电能量下限
$S$	固定充电服务站	$U$	WCE的充电功率
$E m a x$	节点充电容量最大值	$v$	WCE的平均移动速度
$E m i n$	节点充电容量最小值	$E M$	WCE携带的最大移动能量
$E h$	节点充电能量上限	$E C$	WCE携带的最大充电能量

图2 系统充电流程时间组成示意图

图3 违反充电时间窗的惩罚函数(a) 线性惩罚函数 (b) 非线性惩罚函数

图4 WCE带时间窗的充电规划示意图

图5 4种情况下的充电规划

图6 3种规模网络的节点分布(a) 节点规模为20的节点分布图 (b) 节点规模为30的节点分布图 (c) 节点规模为40的节点分布图

图7 行驶能量与充电能量均充足情况下的Pareto前沿图

(a) Net-1 (b) Net-5 (c) Net-9

图8 充电能量不足,行驶能量充足情况下的Pareto前沿图

(a) Net-2 (b) Net-6 (c) Net-10

图9 行驶能量不足,充电能量充足情况下的Pareto前沿图

(a) Net-3 (b) Net-7 (c) Net-11

图10 行驶能量与充电能量均不足情况下的Pareto前沿图

(a) Net-4 (b) Net-8 (c) Net-12

表2 四种算法各性能指标的比较结果

节点数	算法	$P N$			$S P$			$M 3 *$
节点数	算法	最差值	最好值	平均值	最差值	最好值	平均值	最差值	最好值	平均值
20	MODFA	103	122	114	0.026 7	0.001 4	0.008 6	0.191 0	0.385 3	0.113 8
	MOEA/D	7	14	10.2	0.016 3	0.004 3	0.011 1	0.002 0	0.238 2	0.087 9
	NSGA-2	31	41	36.9	0.052 2	0.001 9	0.012 6	0.023 8	0.304 0	0.104 2
	SPEA-2	50	67	59.3	0.048 0	0.001 4	0.012 7	0.021 9	0.248 1	0.099 1
30	MODFA	94	109	100.7	0.026 8	0.001 3	0.010 9	0.024 5	0.424 8	0.158 2
	MOEA/D	8	12	10.4	0.024 3	0.003 7	0.012 8	0.015 4	0.192 1	0.074 8
	NSGA-2	34	44	39.1	0.033 4	0.001 3	0.012 7	0.025 3	0.333 3	0.120 9
	SPEA-2	45	56	50.8	0.029 8	0.001 1	0.012 1	0.030 9	0.348 0	0.138 1
40	MODFA	102	107	109.5	0.050 0	0.002 5	0.013 4	0.072 5	0.905 7	0.373 9
	MOEA/D	7	10	8.3	0.052 5	0.002 0	0.019 6	0.016 7	0.558 1	0.221 7
	NSGA-2	24	32	28.9	0.035 3	0.001 3	0.014 5	0.013 1	0.436 8	0.170 2
	SPEA-2	39	51	44	0.038 0	0.001 4	0.016 0	0.017 7	0.591 1	0.208 6

表2 四种算法各性能指标的比较结果

节点数	算法	$P N$			$S P$			$M 3 *$
节点数	算法	最差值	最好值	平均值	最差值	最好值	平均值	最差值	最好值	平均值
20	MODFA	103	122	114	0.026 7	0.001 4	0.008 6	0.191 0	0.385 3	0.113 8
	MOEA/D	7	14	10.2	0.016 3	0.004 3	0.011 1	0.002 0	0.238 2	0.087 9
	NSGA-2	31	41	36.9	0.052 2	0.001 9	0.012 6	0.023 8	0.304 0	0.104 2
	SPEA-2	50	67	59.3	0.048 0	0.001 4	0.012 7	0.021 9	0.248 1	0.099 1
30	MODFA	94	109	100.7	0.026 8	0.001 3	0.010 9	0.024 5	0.424 8	0.158 2
	MOEA/D	8	12	10.4	0.024 3	0.003 7	0.012 8	0.015 4	0.192 1	0.074 8
	NSGA-2	34	44	39.1	0.033 4	0.001 3	0.012 7	0.025 3	0.333 3	0.120 9
	SPEA-2	45	56	50.8	0.029 8	0.001 1	0.012 1	0.030 9	0.348 0	0.138 1
40	MODFA	102	107	109.5	0.050 0	0.002 5	0.013 4	0.072 5	0.905 7	0.373 9
	MOEA/D	7	10	8.3	0.052 5	0.002 0	0.019 6	0.016 7	0.558 1	0.221 7
	NSGA-2	24	32	28.9	0.035 3	0.001 3	0.014 5	0.013 1	0.436 8	0.170 2
	SPEA-2	39	51	44	0.038 0	0.001 4	0.016 0	0.017 7	0.591 1	0.208 6

图11 四种算法性能指标箱型图

参考文献 19

1	QIUT, QIAOR X, HANM, et al. A lifetime-enhanced data collecting scheme for the internet of things[J]. IEEE Communications Magazine, 2017, 55(11): 132-137.
2	XUW Z, LIANGW F, JIAX H, et al. Minimizing the maximum charging delay of multiple mobile chargers under the multi-node energy charging scheme[J]. IEEE Transactions on Mobile Computing, 2021, 20(5): 1846-1861.
3	LIUT, WUB J, ZHANGS H, et al. An effective multi-node charging scheme for wireless rechargeable sensor networks[C]//IEEE INFOCOM 2020-IEEE Conference on Computer Communications. Toronto: IEEE, 2020: 2026-2035.
4	KURSA, KARALISA, MOFFATTR, et al. Wireless power transfer via strongly coupled magnetic resonances[J]. Science, 2007,317(5834): 83-86.
5	JIAR H, LUJ F, WUJ H, et al. Geometric analysis of energy saving for directional charging in WRSNs[J]. IEEE Internet of Things Journal, 2021, 8(6): 4697-4710.
6	JIANGX, POLASTREJ, CULLERD. Perpetual environmentally powered sensor networks[C]//IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks. Los Angeles: IEEE, 2005: 463-468.
7	KANSALA, HSUJ, ZAHEDIS, et al. Power management in energy harvesting sensor networks[J]. ACM Transactions on Embedded Computing Systems, 2007, 6(4): 32-es.
8	HANG J, YANGX, LIUL, et al. A joint energy replenishment and data collection algorithm in wireless rechargeable sensor networks[J]. IEEE Internet of Things Journal, 2018, 5(4): 2596-2604.
9	LINC, ZHOUY H, MAF L, et al. Minimizing charging delay for directional charging in wireless rechargeable sensor networks[C]//IEEE INFOCOM 2019-IEEE Conference on Computer Communications. Paris: IEEE, 2019: 1819-1827.
10	田贤忠, 祝驿楠, 何佳存, 等. 一种射频能量捕获网络移动能量源均衡化充电策略[J]. 电子学报, 2018, 46(12): 2985-2992.
	TIANX Z, ZHUY N, HEJ C, et al. A balanced charging scheme for mobile energy transmitter in RF energy harvesting network[J]. Acta Electronica Sinica, 2018, 46(12): 2985-2992. (in Chinese)
11	FUL K, CHENGP, GUY, et al. Optimal charging in wireless rechargeable sensor networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(1): 278-291.
12	SHAC, SONGD, MEALEKIANR. A periodic and distributed energy supplement method based on maximum recharging benefit in sensor networks[J]. IEEE Internet of Things Journal, 2021, 8(4): 2649-2669.
13	WUT, YANGP, DAIH, et al. Joint sensor selection and energy allocation for tasks-driven mobile charging in wireless rechargeable sensor networks[J]. IEEE Internet of Things Journal, 2020, 7(12): 11505-11523.
14	YANGM Y, LIUN B, ZUOL, et al. Dynamic charging scheme problem with actor-critic reinforcement learning[J]. IEEE Internet of Things Journal, 2021, 8(1): 370-380.
15	ASLAMN, XIAK W, HADIM U. Optimal wireless charging inclusive of intellectual routing based on SARSA learning in renewable wireless sensor networks[J]. IEEE Sensors Journal, 2019, 19(18): 8340-8351.
16	LINC, ZHOUY H, SONGH B, et al. OPPC: An optimal path planning charging scheme based on schedule ability evaluation for WRSNs[J]. ACM Transactions on Embedded Computing Systems, 2017, 17(1).
17	LINC, WANGZ, DENGJ, et al. mTS: Temporal-and spatial-collaborative charging for wireless rechargeable sensor networks with multiple vehicles[C]//IEEE INFOCOM 2018-IEEE Conference on Computer Communications. Honolulu: IEEE, 2018: 99-107.
18	DAIH P, MAQ, WUX B, et al. CHASE: Charging and scheduling scheme for stochastic event capture in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2020, 19(1): 44-59.
19	水九生, 徐向华. 一种基于多节点充电模型的按需顺带充电方案[J]. 电子学报, 2021, 49(2): 346-353.
	SHUIJ S, XUX H. An on-demand passer-by charging scheme based on multi-node charging model[J]. Acta Electronica Sinica, 2021, 49(2): 346-353. (in Chinese)

[1]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[2]	李纪三, 纪彦星, 曹鼎, 刘溶, 任渊. 基于广义时间窗的旋转相控阵雷达资源调度算法[J]. 电子学报, 2022, 50(5): 1050-1057.
[3]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[4]	张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.
[5]	王蔚龙, 李勇军, 赵尚弘, 辛宁, 赵海燕, 张泰江. 基于两阶段帕累托优化的卫星下行链路功率分配方法[J]. 电子学报, 2021, 49(6): 1101-1107.
[6]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[7]	王亚良, 倪晨迪, 金寿松. 基于多邻居结构的自适应元胞差分算法[J]. 电子学报, 2021, 49(3): 578-585.
[8]	水九生, 徐向华. 一种基于多节点充电模型的按需顺带充电方案[J]. 电子学报, 2021, 49(2): 346-353.
[9]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[10]	崔玉亚, 张德干, 张婷, 杨鹏, 朱浩丽. 一种面向移动边缘计算的多用户细粒度任务卸载调度方法[J]. 电子学报, 2021, 49(11): 2202-2207.
[11]	刘冰洁, 毕晓君. 一种基于角度信息的约束高维多目标进化算法[J]. 电子学报, 2021, 49(11): 2208-2216.
[12]	郭荣梅, 胡小兵. 求解时间窗口网络中前k条最短路径的方法[J]. 电子学报, 2020, 48(7): 1387-1395.
[13]	王海东, 刘云敬, 康琳, 武迎春. 射频能量捕获传感网移动能量源的布置策略研究[J]. 电子学报, 2020, 48(12): 2367-2375.
[14]	黎明, 黄珊, 陈昊, 李军华. 基于类圆映射的高维多目标可视化方法[J]. 电子学报, 2019, 47(6): 1185-1193.
[15]	谢承旺, 张飞龙, 陆建波, 肖驰, 龙广林. 一种多策略协同的多目标萤火虫算法[J]. 电子学报, 2019, 47(11): 2359-2367.

带时间窗的无线可充电传感器网络多目标路径规划算法

Multi-Objective Path Planning Algorithm for WRSN with Time Window

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 19

相关文章 15

编辑推荐

Metrics