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

魏振春，孙仁浩，吕增威，韩江洪，石雷，徐俊逸



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

魏振春1,2,3，孙仁浩1，吕增威1，韩江洪1,2,3，石雷1,2,3，徐俊逸1

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

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

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

1 引言

数据收集是无线传感器网络（WSN, wireless sensor network）的核心任务，而能量问题是该领域研究的热点问题之一。传统的WSN中传感器节点数据传输以多跳的方式会造成“能量空洞”问题[1-2]，距离固定基站较近的传感器节点承担更多的数据转发任务，具有更大的通信负载，以至于这些节点因能耗过大而过早死亡，“能量空洞”问题一直是无线传感器网络研究领域中的关键问题。目前，解决该问题的方法主要有3种：1) 采用节流的思想，即引入移动sink节点节省传感器节点的能量消耗；2) 采用开源的思想，即利用可移动的充电设备为传感器节点补充能量；3) 则是结合节流和开源的思想，利用可移动的无线充电设备为节点补充能量，同时可以收集节点数据。

从节流的角度来考虑，引入移动sink节点在WSN中游走，移动收集传感器节点的数据，降低了节点数据传输过程中的通信负载，可以有效避免“能量空洞”问题，延长了网络的寿命。文献[3]提出了一种基于移动sink节点的WSN数据采集方案，利用量子遗传算法求解出遍历所有采集点的最短回路，均衡了网络中传感器节点的负载，延长了网络的寿命。文献[4]设计了一种时延受限的移动sink节点数据收集算法，在有限的时间内利用sink节点的移动性来提升WSN的数据收集性能，提高了网络数据的采集量，降低了部分节点的能耗，延长了网络生命周期。文献[5]提出了一种基于树的节能策略，以减少带有移动sink节点的无线传感器网络的能耗，利用移动sink节点收集传感器节点的数据，平衡了网络负载，降低了传感器节点的能量消耗，延长了网络的寿命。文献[6]针对野外环境下大规模的无线传感器网络，提出了一种用于移动sink节点的数据收集策略以避免靠近固定sink的传感器节点比其他节点能量消耗的更快，有效地解决了“能量空洞”问题，延长了网络的寿命。

从开源角度来考虑，无线充电技术[7]的引入利用可移动的WCE在WSN中游走，通过无线充电的方式为网络中的传感器节点补充能量，这种网络称为无线可充电传感器网络（WRSN, wireless rechargeable sensor network）[8]，利用WCE保证网络中的节点不会因能耗问题而死亡，避免了WSN中的“能量空洞”问题，延长了网络的寿命。文献[9]认为WCE自身携带的能量是无限的，证明了WCE采用最短哈密尔顿回路的方式为网络中的传感器节点充电可使网络生命周期无限延长，同时能够获得最大的驻站比。文献[10-11]假设WCE自身携带的能量是无限的，采用按需充电方式为传感器节点补充能量，选择以“最近工作优先”为模型，用排队论方法求解该充电路径规划问题，保证网络不会因为节点能量不足而停止工作。文献[12]在WCE自身携带能量有限的情况下，提出了一种网络中传感器节点剩余生命时间均衡化的充电策略，研究WCE的行驶路径以及为传感器节点充电的时间，以最小化WCE总能耗的开销为目标，尽量延长网络的寿命。文献[13]在文献[12]的基础上，设计了一种WCE能量受限的WRSN周期性充电规划策略，在最大化充电周期的同时最小化WCE总能量的消耗，以保证网络永久性地工作下去，利用混沌粒子群算法求解优化问题得到WCE充电路径以及在节点处的充电时间。

结合节流和开源两个角度考虑，目前学者在这方面的研究还比较少，主要是利用WCE在网络中游走为节点补充能量和收集节点数据，延长网络的寿命，提高网络数据传输的性能。文献[14]利用WCE为节点补充能量以及收集节点数据，以最大化设备驻站时间比为目标，保证了网络永久运作，提高了网络数据传输的性能。文献[15]提出了一种联合移动充电和数据收集的框架，研究WCE在网络中游走的路径以及充电和数据收集的策略，在保证网络寿命的前提下，提高网络的性能。文献[16]采用一个可移动的无线充电设备、多个数据收集装置为节点充电以及收集数据，提出了基于充电补给和数据收集的设备调度策略，以平衡网络节点的能量消耗，降低网络数据传输的延时。文献[17]将可移动的WCE既作为移动充电设备，又作为移动sink，在为节点充电的同时收集数据，由移动设备收集数据带回到基站附近再上传，以最大化传感器网络效用值为目标，提出了一种分布式算法，在保证网络数据正常传输的前提下尽量延长网络的寿命。文献[18]提出了WCE可为节点充电以及收集数据，在保证数据正常传输的同时，避免固定基站带来的节点剩余能量不均衡问题，延长了网络的寿命。在上述的研究中学者只考虑单目标的情况，有些是考虑如何在保证网络永久运作的前提下提高网络数据传输的性能，有些是考虑如何在保证网络数据传输性能的约束下延长网络寿命，并没有将两者综合考虑。

在前人研究的基础上，本文研究在联合移动充电和数据收集策略下的WCE多目标路经规划问题，WCE在其携带行驶能量和充电能量均有限的情况下，既为传感器节点补充能量又收集节点数据，因此，WCE行驶路径的选择以及在节点处充电时间的多少不仅影响网络的寿命，同时还影响网络中节点数据传输的性能，这是一个多目标问题。针对该问题，本文建立了多目标WCE路径规划模型，提出了基于精英策略的多目标蚁群优化算法（ES-MOAC, multi-objective ant colony optimization algorithm based on elitist strategy），最终求得该问题的Pareto最优解集。本文的贡献如下。

1) 首次建立了联合移动充电和数据收集策略下的以最大化WCE总能量的利用率和最小化网络中节点数据传输的平均时延为目标的WCE路径规划模型，分析了WCE行驶路径的选择以及在节点处的充电时间对上述2个目标的影响。

2) 首次通过多目标优化算法解决WCE路径规划问题，提出了一种基于精英策略的多目标蚁群优化算法，设计了蚂蚁状态转移策略和信息素更新策略。

2 网络结构和问题描述

2.1 WRSN的结构

在一个被监测区域D内部署有无线可充电传感器网络，该网络具有如下性质。

4) 网络中有一个服务站S，该服务站S是WCE在执行完充电和数据收集任务后，为其提供能量补给和停留的场所。

具有上述性质的无线可充电传感器网络模型如图1所示。

图1 带有移动WCE的无线可充电传感器网络示意

2.2 问题的描述

本文研究的问题是联合充电和数据收集下的WCE多目标路径规划问题，其中，WCE的初始行驶能量和充电能量是分开且有限的，因此在设计WCE的路径规划时需要考虑以下几点。

1) 由于WCE的行驶能量是有限的，而且网络的传感器节点分布是稀疏的，WCE不一定能在一个哈密尔顿回路中遍历网络中所有节点，如何设计和规划WCE的行驶路径使其遍历网络中所有节点是本文研究的问题之一。

2) 由于WCE的充电能量是有限的，WCE不能保证网络永久运作，设计什么样的充电策略以延长网络的寿命是十分重要的。

3) 考虑到WCE不仅为节点充电，还对节点进行数据收集，因此，WCE的行驶路径的选择以及WCE在节点处充电时间的多少既影响网络的寿命，又影响网络中数据传输的性能，这是一个多目标问题。

在建立和分析WCE多目标路径规划模型之前，先给出以下2个定义。

图2 WCE在一个工作周期内经过多个工作轮的行驶路径示意

由于WCE在服务站S中的能量补给是通过更换电池实现的，可以瞬时完成，故WCE在服务站S进行能量补给的时间可以忽略不计。因此，一个工作周期仅由若干个工作轮组成。

3 模型的建立

3.1 WCE的行驶路径和工作周期

3.2 WCE的充电模型

3.3 WCE的充电策略

为了尽量延长网络的寿命，本文设计了一种能量均衡化的充电策略。该策略利用WCE选择合适的节点进行充电，均衡网络内所有节点的剩余生命时间，使节点的剩余生命时间不为0且方差最小，方差最小意味着节点的剩余生命时间趋于某个值，平均剩余生命时间均衡化。

3.4 WCE的数据收集策略

WCE在网络中不仅为传感器节点补充能量，还可以收集节点数据，所以在WCE的路径规划的过程中还要考虑网络中节点数据传输的时延，尽量降低其时延，保证网络中节点数据传输的性能。

3.5 多目标优化问题模型

根据上面的描述可知WCE工作的时间轴如图3所示，其中，包括WCE的驻站时间和工作周期。

图3 WCE为WRSN服务的时间轴的示意

s.t.式(2), 式(4), 式(6)~式(8), 式(13)~式(16), 式(18)

4 基于精英策略的多目标蚁群优化算法

在WCE充电策略和数据收集策略的条件下，本文提出的多目标优化问题模型实际上是求解WCE的路径规划，即WCE的行驶路径以及WCE在节点处的充电时间，这是一个NP-hard问题。根据文献[12]可知，蚁群算法模拟了自然界中蚂蚁的觅食行为，是寻找最优路径的一种元启发式优化算法，相比于粒子群算法、遗传算法等优化算法，蚁群算法更适合解决路径规划问题。因此，本文采用蚁群优化算法进行求解，提出了一种基于精英策略的多目标蚁群优化算法ES-MOAC。

在ES-MOAC算法的设计中需要对蚂蚁状态转移策略和信息素更新策略进行设计。在蚂蚁状态转移策略的设计中，当符合判断条件时，算法采用考虑信息素浓度、节点之间的距离以及节点的剩余生命时间等因素影响下确定蚂蚁状态转移策略；否则采用随机性蚂蚁状态转移策略随机选择一个未被访问的传感器节点，避免了ES-MOAC算法陷入局部最优。在信息素更新策略设计中，采用全局信息素更新策略，本轮的信息素是根据上一轮的信息素挥发之后残留的信息素和计算多目标优化问题求得的Pareto解集对应的精英蚂蚁在路径上产生新的信息素进行更改的，该策略是一种改进的精英策略，对于求得本问题的Pareto最优解集以及WCE行驶路径的选择具有引导作用。

4.1 蚂蚁状态转移策略

4.2 信息素更新策略

4.3 算法描述

基于上述改进的蚂蚁状态转移策略和信息素更新策略，在一个工作周期内，利用基于精英策略的多目标蚁群优化算法可以求得本文多目标路径规划问题的Pareto最优解集和每个解对应的WCE的行驶路径以及WCE在节点处的充电时间，ES-MOAC算法的具体步骤如下。

算法1 ES-MOAC算法

输入 网络基本参数, 充电系统和蚂蚁系统相关参数。

输出 Pareto最优解集和每个解对应WCE的行驶路径以及WCE在传感器节点处的充电时间。

9) end

10) 根据信息素更新策略对应的式(20)和式(21)对信息素浓度进行更新。

12) end

5 仿真实验

5.1 蚂蚁系统参数对ES-MOAC算法的影响

实验结果表明，算法至少执行120次之后，Pareto最优解的个数的平均值才趋于某一个定值，曲线开始收敛。蚂蚁个数大于或等于15时，蚂蚁个数对本算法的结果影响很小。

图4 不同蚂蚁个数下本文算法Pareto最优解的个数随迭代次数的影响

图5 蚂蚁状态转移策略中选择因子q0的取值对本算法的影响

5.2 ES-MOAC算法求解本问题的结果与分析

表1 20个传感器节点的位置坐标

图6 信息素更新策略中信息素挥发系数的取值对本算法的影响

从图7中可以看出，ES-MOAC算法求解本问题能很好地逼近Pareto前沿，当算法迭代150次时，能够得到本问题的Pareto前沿。其中，WCE总能量的利用率最高和网络中数据传输的平均时延最低这2个解对应的WCE在一个工作周期的多轮能量开销如表2和表3所示，0代表的是服务站S。对比表2和表3可知，在一个周期内网络中数据传输的平均时延最低的解对应的工作轮数小于WCE总能量的利用率最高的解的工作轮数，这意味着WCE在路上的行驶时间较少，网络中数据传输的平均时延较低。WCE总能量的利用率最高的解的工作轮数虽然较高，能量的开销大，一个工作周期花费的时间长，但为了均衡化网络中节点的能量，充电能量的开销较多，总能量的利用率高。

图7 ES-MOAC算法求解本问题在不同迭代次数下的Pareto前沿

表2 WCE完成一个工作周期的多轮能量开销（WCE总能量的利用率最高的解）

表3 WCE完成一个工作周期的多轮能量开销（数据传输的平均时延最低的解）

5.3 ES-MOAC算法与NSGA-II算法的比较

图8 ES-MOAC算法和NSGA-II算法的Pareto前沿对比

在多目标优化分析中，除了分析算法的收敛性，还需要对算法的多样性进行分析，算法多样性的分析主要考虑以下几个指标。

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

图9 ES-MOAC算法和NSGA-II算法关于指标统计值的盒状图

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

6 结束语

在WCE的行驶能量和充电能量分开且有限的非理想情况下，本文首次提出了联合充电和数据收集的多目标路径规划模型，在保证了网络中能量均衡化以及尽量延长网络寿命的前提下，本文给出了WCE充电路径的构造规则，以最大化WCE总能量的利用率为目标，同时，WCE可以收集节点数据，将网络中所有节点的平均数据传输时延作为另一个优化目标，提高网络中数据传输的性能。本文提出了一种基于精英策略的多目标蚁群算法ES-MOAC，设计了算法的蚂蚁状态转移策略和信息素更新策略，求得了该问题的Pareto最优解集。通过实验分析了蚂蚁系统中最大迭代次数、蚂蚁个数、蚂蚁状态转移策略中选择因子和信息素更新策略中信息素挥发系数等参数对本算法的影响。进行实验仿真，针对ES-MOAC算法求解本问题的结果进行分析，验证了模型的正确性。在同等条件下，本文针对ES-MOAC算法与NSGA-II算法做了对比实验，实验结果表明了本文算法的优越性。

本文研究的无线可充电传感器网络覆盖范围内只存在单个可移动的WCE。然而，在某些特殊环境下，单个WCE无法完成任务时，如何安排和调度多个WCE协同工作还有待进一步研究。另外，该网络中可能存在瓶颈节点，瓶颈节点的存在并不利于网络的稳定工作，能否通过提高WCE对这种节点进行能量补充的频率从而消除瓶颈节点对网络的影响，也亟待研究。

[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-Verlag, 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.

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

WEI Zhenchun1,2,3, SUN Renhao1, LYU Zengwei1, HAN Jianghong1,2,3, SHI Lei1,2,3, XU Junyi1

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

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.

wireless rechargeable sensor network, joint energy replenishment and data collection, path planning, multi-objective ant colony optimization algorithm

TP393

A

10.11959/j.issn.1000−436x.2018216

魏振春（1978−），男，宁夏青铜峡人，博士，合肥工业大学副教授、硕士生导师，主要研究方向为物联网、无线传感器网络、智能计算。

孙仁浩（1992−），男，吉林扶余人，合肥工业大学硕士生，主要研究方向为无线传感器网络、智能优化算法。

吕增威（1989−），男，山东烟台人，合肥工业大学博士生，主要研究方向为物联网、智能计算、机器学习。

韩江洪（1954−），男，江苏南京人，合肥工业大学教授、博士生导师，主要研究方向为计算机控制、物联网、无线网络。

石雷（1980−），男，安徽合肥人，博士，合肥工业大学副教授、硕士生导师，主要研究方向为无线网络、干扰管理。

徐俊逸（1990−），男，江苏常州人，合肥工业大学博士生，主要研究方向为物联网、软件定义网络、网络功能虚拟化。

2017−11−06；

2018−08−22

石雷，thunder10@163.com

国家自然科学基金资助项目（No.61502142, No.61501161, No.61370088）

The National Natural Science Foundation of China (No.61502142, No.61501161, No.61370088)