基于改进混合粒子群算法的无人机充电路径规划方法

田雨露，米志超，周雁翎 ,王 海，芦方旭

( 1.陆军工程大学 通信工程学院，江苏 南京 210007;2.中国人民解放军31121部队，江苏 南京 210042)

0 引言

无线传感器网络(Wireless Rechargeable Sensor Networks，WRSNs)[1]是一个由成百上千的传感器节点所组成的无线网络，通常与基站配备进行部署，用于信息采集、处理、传输等，传感器之间能够彼此通信或者直接与基站联系。传感器节点大多数由电池进行供电，而电池电量有限，当需要传感器持久工作时，有限的电量无法满足传感器长时间续航的要求，这会导致网络中节点的工作寿命大大降低。一般情况下，解决电池电量耗尽的方法是更换电池，但是当传感器部署在地形复杂、人们不易到达的地域，人为更换电池方式极大地增加了成本[2]，所以无线传感网络节点的能量补充方式成为当前研究的重点。目前为传感器节点补充能量的方式有两种：一种是采用能量收集方式，利用自然能量(如太阳能、风能、热能等)[3-4]，但是由于自然环境多变，这种能量来源方式不够稳定，不能作为传感器节点的主要来源；另一种是进行能量补充方式，采用无线充电技术，将移动电源搭载到可移动载体上，移动到指定位置，对无线覆盖区域内所有传感器节点进行补充电能，文献[5-9]中采用的均是地面移动设备对WRSNs进行充电，但是当充电区域不易到达时，地面移动设备充电可能无法完成。

无人机(Unmanned Aerial Vehicle，UAV)作为新型携带充电设备为WRSNs补充电能的研究逐渐出现，UAV体积小、便携带，相比于移动电源车成本低，且飞行速度快，在无线充电场景中，更便于进入障碍区域对WRSNs中传感器节点进行充电，延长地面传感器的续航时间，增加WRSNs的生命周期。文献[10-12]对无人机充电路径问题进行了研究。由于无人机载重与飞行能力有限，无人机在对WRSNs中传感器节点进行周期充电时，如何缩短充电的时间，减少无人机自身能耗对于研究而言至关重要，规划合理的路径也是解决问题的重要方法。现有的解决充电路径研究中，文献[13]提出将路径距离、充电时间和车辆成本组合为新的成本目标模型,对传感器节点充电问题进行求解。文献[14]提出一种按需的无线传感器能量补给调度方案，首先在每个周期内对所有请求充电的节点进行充电路径优化，充电过程中根据紧急节点需求实时性请求结合动态插入法安排紧急需求节点充电。文献[15]提出一种基于充电效用最大化的一对多有向充电调度方案，首先筛选网络中充电增益最大的有向覆盖子集；然后根据有向覆盖子集确定充电锚点，并规划充电器的移动路径；最后在满足移动充电器能量和充电周期约束条件下优化移动充电器的充电时间。文献[16]根据单位时间内充电完成的传感器数目，对最佳悬停高度进行了推导，随后采取移动-充电的方式，无人机悬停在某一传感器上空，根据无人机最大覆盖能力，对周围覆盖范围内的传感器同时进行充电，以完成任务总时间作为优化目标，对无人机飞行路径进行规划。但以上模型均未将节点充电量考虑进去。在移动电源设备为WRSNs中传感器节点进行充电任务中，由于无人机飞行时间或者任务完成时间的限制，在周期性充电任务中，传感器节点可能由于时间限制问题导致无法使所有节点均达到充满状态，因此传感器节点的充电量也应该作为重点因素进行考虑。

综上所述，本文针对无人机周期性对WRSNs中传感器节点进行充电的路径规划问题，建立了时间限制的约束条件下，将无人机飞行能耗和节点充电量指标作为效益函数，求解飞行时间限制下效益最优的无人机充电路径模型；并提出一种改进的粒子群算法，用于对无人机WRSNs充电路径问题进行求解。

1 系统模型

1.1 问题描述

WRSNs充电系统模型如图1所示。该网络由N个可充电传感器节点、基站、无人机组成。无线传感器随机分布，由于传感器所收集的信息量有差异，消耗速率不同，所以每个传感器的剩余电量也不尽相同。无人机位于基站位置，基站对无人机进行任务调度并收集区域内所有传感器节点的信息，无人机为区域内无线传感器进行周期性充电，传感器可以在回传采集数据时捎带自己的剩余能量信息给基站，无人机充电出发时与基站通信即可获得全网节点的剩余能量，通信产生能量的消耗可忽略不计。当无人机收到基站发出指令后，携带充电模块从基站起飞到传感器节点上空，无人机悬停在节点上空为传感器节点进行充电，当某一节点充完电后，无人机飞行到下一节点继续进行充电，直至区域内节点充电任务全部完成，无人机返回基站进行补充电量。设定无人机在固定高度进行飞行，以避开地面障碍因素的干扰，携带充电模块满足当前区域全部节点所需的电量。

采用传统旅行商 (Traveling Salesman Problem,TSP)方法解决此问题时，通常以最短路径为优化目标，并没有考虑节点充电量以及无人机能耗等因素，因此无法应用到本模型的求解。

图1 系统模型图Fig.1 System model diagram

1.2 充电模型

本文无人机为WRSNs充电过程采取单一无人机供电的方式，该充电模型无人机与传感器节点之间采用磁共振耦合的无线充电技术，传感器节点接收功率与无人机的发射功率之间的关系如式(1)所示[17]：

(1)

式中，pr为传感器接收功率，pt为无人机充电发射功率，d为无人机距离传感器之间的距离，β为距离改变时的补偿参数。

在无人机进行充电任务中，引入指示函数fi(t)表示无人机在t时刻与第i个传感器节点的关系：

1.3 能耗模型

1.3.1 飞行能耗

飞行能耗主要取决于飞行路径的长度，可以表示为：

Ef=L×Q，

(2)

式中，Ef为无人机飞行能耗，L为飞行距离,Q为飞行能耗参数，以J/m为单位。

1.3.2 悬停能耗

悬停能耗表示为：

Ehv=phv×Ti，

(3)

式中，Ehv表示为无人机悬停能耗，phv为无人机在节点上空充电的悬停功率，Ti为无人机在第i个传感器节点上空的悬停时间，由于无人机到达第i个传感器时，传感器在消耗电量，其值大小取决于传感器节点开始充电时的剩余电量和最终需要充的电量。

(4)

式中，Elast为传感器节点的最终充电量，Ci表示第i个传感器节点初始状态剩余能量，在无人机到达第i个传感器节点之前，传感器节点在持续消耗电量，当前传感器节点需要充电的量为最终状态电量Elast减去初始状态电量Ci再加上无人机到达当前位置该节点持续消耗的电量。p为传感器节点耗电速率，定义ti为无人机从开始充电任务直至到达第i个传感器节点所花费的时间：

(5)

式中，v为无人机飞行速度，设定无人机匀速飞行，li-1,i为第i-1个传感器节点到第i个传感器之间飞行的距离。

在规划优化目标时，本文将充电无人机的能耗和节点充电量综合进行如下考虑：

F=ω1Ehv+ω2Ef+ω3(Efull-Elast)=

(6)

式(6)表示目标函数为悬停能耗、飞行能耗、传感器充电后距离满载电量差值加权后的和，Efull为传感器节点的最大容量，最终充电量Elast是通过仿真得到的，与设置的时间限制有关。在设置的时间限制下，要求所有传感器都要进行充电，但传感器可能由于时间不足不能够全部充至满电，所以在求目标函数最优时，Elast相当于要优化的变量。无人机对传感器充电的顺序会影响无人机的飞行距离进而影响飞行时间，由于传感器处于一直耗电状态，在设置限制时间的条件下，飞行轨迹顺序的不同，会导致飞行耗时增加，最终会由于充电时间不足，Elast的值减小。Efull为固定值，所以无人机对传感器充电顺序会影响传感器节点的最终充电量Elast，进而影响目标函数的第三项Efull-Elast。ω1,ω2,ω3为权重系数，Si为无人机充电时在第i个传感器的悬停位置，进行无人机路径规划策略时，本文考虑无人机完成任务的基础之上消耗更少的能量，传感器节点电量越充足越好，所以将这两个因素综合考虑，规划目标函数。

1.4 网络模型

无人机为WRSNS充电路径规划问题可以表示为：

(7)

(8)

(9)

Ci-pti≥Elimit∀i∈(1,N),

(10)

(11)

式(7)中，l(x)为优化变量，表示无人机充电过程中的飞行路径；式(8)表示一架无人机在任一时刻只能给一个节点进行充电；式(9)表示当时间达到一个周期时，无人机要遍历所有传感器节点进行充电；式(10)表示任一传感器节点在无人机到来为传感器节点充电之前不能低于能量的阈值，若节点电量消耗至阈值，传感器节点进入休眠状态；式(11)中Tlimit为总时间限制，考虑到无人机自身飞行和充电悬停，要在限制时间内完成所有节点一个周期的充电任务。

2 算法实现

2.1 粒子群算法

粒子群(Particle Swarm Optimization，PSO)算法是模拟鸟群随机搜寻食物的捕食行为，用于解决优化问题。在PSO算法中每个优化问题的潜在解都可以想象成搜索空间的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化函数决定的适应度值，也就是粒子的目标函数，每个粒子还有一个速度决定它们的飞行方向和距离。然后粒子就追随当前的最优粒子在解空间中搜索，算法流程首先产生一批初始解，作为当前种群，计算当前种群里每个解的适应度，更新个体最优解与群体最优解利用速度、位置更新公式对种群进行更新，重复上述步骤，计算更新后的种群里每个解的适应度，重新更新个体最优解与群体最优解，当满足迭代终止条件时，跳出迭代环节，输出搜索到的最优解，速度与位置更新公式如下：

vid=ωvid+c1r1(pid-xid)+c2r2(pgd-xid)，

(12)

xid=xid+vid。

(13)

式(12)中，pid为第i个粒子搜索到的最优位置，也称为个体极值；pgd为整个粒子群搜索到的最优位置，也称为全局极值；ω为惯性因子；c1,c2为加速因子；r1,r2为随机数，介于0,1之间；vid为第i粒子的速度；xid为第i个粒子的位置。式(13)为粒子的位置更新公式。

2.2 改进的PSO算法

PSO算法容易早熟，并经常陷入局部最优值，收敛速度慢，针对PSO算法的缺点，本文在传统PSO算法的基础上引入了线性递减权重的方法(Linearly Decreasing Weight，LDW)[18]和遗传算法(Genetic Algorithm，GA)中的交叉变异过程[19]。PSO算法中，惯性因子ω对于PSO算法的收敛性有较大的影响，惯性因子ω增大，有利于增强全局搜索能力；ω减小，有利于增强局部搜索能力；引入惯性权重递减方法，使惯性因子ω随迭代次数衰减，因而使得在搜索后期可以加速收敛，这种采用惯性权重根据迭代次数去进行自适应变化，相比于传统粒子群收敛速度更快，算法后期局部搜索能力强，权重递减公式如下：

(14)

式中，ωmax，ωmin分别为惯性权重的最大和最小值，一般将ωmax设置为0.9，ωmin设置为0.2，k为当前迭代次数，kmax为最大迭代次数。改进后的粒子群速度位置更新公式如下：

c1r1(pid-xid)+c2r2(pgd-xid)。

(15)

但LDW改进方法由于种群缺乏多样性，仍存在陷入局部最优的缺点，而遗传算法种群规模较大，通过交叉变异不断地扩大种群的多样性。交叉操作是在种群中选取较大比例的个体，对选出的个体相互之间部分结构进行交叉互换；变异操作是在种群中选出小部分个体，使个体自身中部分结构进行改变，遗传算法能够求出优化问题的全局最优解，具有较强的鲁棒性，适合于求解复杂的优化问题，应用较为广泛。但是遗传算法的收敛速度慢，局部搜索能力差。本文将两种改进方式结合，在PSO算法基础之上所改进的算法简称为LG-PSO算法，实现过程如算法1所示。

算法1 LG-PSO算法输入:染色体数量、迭代次数、种群规模、交叉概率Pc、变异概率Pm输出:充电路径初始化种群whileiter

LG-PSO算法算法具体步骤如下：

① 初始化粒子群和遗传算法参数，加速因子c1,c2设置为2，随机数r1,r2在0,1之间随机设置，遗传交叉概率设置为0.9，变异概率设置为0.1，种群规模设置为200，随机生成每个粒子的初始位置和速度。

② 根据适应度函数计算出每个粒子的适应度值，求得粒子群的全局最优和个体最优，利用线性权重递减公式来更新粒子的位置和速度。

③ 保留步骤②中最优个体，对剩下的粒子通过遗传算法的交叉、变异等方式增强粒子群多样性，最后对遗传算法获得的粒子群进行适应度值计算。

④ 将保留下来的最优个体与遗传算法获得的粒子群适应度值进行比较，去除重复路径，对粒子的适应度进行排序，按照种群规模保留较优粒子。

⑤ 重复步骤②～④，设置最大迭代次数为1 000，当达到最大迭代次数时停止搜索，输出最佳结果。

3 仿真结果和性能分析

本文对无人机的充电路径进行仿真和分析，仿真平台为Matlab2021a，假设无人机在固定高度飞行为地面传感器进行充电任务，高度设置为3 m，传感器数量为50，随机分布在100 m×100 m的目标区域内，本文所改进的LG-PSO算法对比原始PSO算法、LDW-PSO算法以及GA-PSO混合算法。部分仿真参数的设置如表1所示，无人机进行充电任务，所以重点考虑节点充电因素，将悬停能耗权重系数和飞行能耗权重系数均设置为0.1，节点电量权重系数设置为0.8,无人机飞行参数参考文献[20]，仿真中由于飞行能耗、悬停能耗以及节点电量不在一个数量级，所以对3种能量数值首先进行归一化处理，使得飞行能耗、悬停能耗、节点电量在一个数量级，然后再进行加权处理。

表1 部分仿真参数Tab.1 Partialsetting of simulation parameters

图2为4种算法下无人机充电路径，从4种算法的轨迹图可以看出LG-PSO算法的轨迹清晰简洁，相比其他3种算法轨迹路径更短、能耗更低。

(a) PSO算法下无人机充电路径

图3是在不同任务时间限制下，4种算法飞行能耗对比。由分析可得，LG-PSO算法相比于其他3种算法在飞行能耗上有明显降低，相比于PSO算法能耗平均降低57.77%，相比于LDW-PSO算法能耗平均降低52.12%，相比于GA-PSO算法能耗降低48.91%，分析其原因是因为LG-PSO算法虽然不是求最短路径，但就算法本身而言，在相同目标条件和参数设置下寻优能力仍然要优于其他几种算法。

图3 不同任务时间下4种算法飞行能耗对比图Fig.3 Comparison diagram of the flight energy consumption of the four algorithms under different Mission times

图4是所有传感器节点最终充电量Elast随限制时间Tlimit变化的曲线，可以看出，在设置相同限制时间下，LG-PSO算法在所有传感器节点最终充电量上相比于其他3种算法有明显的提升，LG-PSO算法将所有传感器节点充电至满载状态时间相比PSO算法提升3.31%，相比于LDW-PSO算法提升2.73%，相比于GA-PSO算法提升2.47%。

图4 4种算法下传感器节点电量随时间变化的曲线Fig.4 Curve of the time change of sensor nodes under the four algorithms

图5是对4种算法目标函数收敛性能进行测试，结果显示，PSO算法收敛速度较慢，较难搜索到全局最优值，迭代次数较长，寻优过程中曲线波动较大，不够稳定；LDW-PSO算法相比原始PSO算法性能有一定的提升，但仍然存在一定的问题，例如前期搜索收敛速度快，后期收敛速度变慢，存在波动较大且较难搜索到全局最优解，也有一定的可能陷入局部最优值；GA-PSO混合算法在收敛速度上比较平稳，前期在收敛速度上不如LDW-PSO算法，后期收敛效果优于LDW-PSO算法，解决了波动较大的问题，在寻优能力上较LDW-PSO和原始PSO算法也有一定的优势；LG-PSO算法融合了以上算法的优势，在算法迭代过程中收敛速度平稳，收敛速度较快，稳定性强；在寻找全局最优解时，改进后的算法在收敛值上相比传统PSO算法提升33.32%，相比LDW-PSO算法提升24.65%，相比GA-PSO算法提升22.36%。

图5 4种算法目标函数收敛对比图Fig.5 Comparison diagram of the convergence of the target function of the four algorithms

4 结束语

本文研究了对WRSNS传感器节点周期性充电任务下的无人机路径规划问题，相比较传统的无人机充电模型，将无人机的能耗和传感器节点的充电量同时进行考虑，将无人机飞行能耗、节点充电量分别作为成本目标进行加权处理，规划新的目标函数；同时，对传统PSO算法进行改进，引入线性递减权重因子，并结合遗传算法，提出一种惯性权重线性递减混合PSO算法(LG-PSO)以解决无人机路径规划问题。仿真对比了传统的PSO算法、LDW-PSO算法和GA-PSO混合算法，从实验结果可以看出本文提出的算法在收敛性能、飞行能耗以及节点充电量方面具有明显的优势。