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

田雨露,米志超，周雁翎,王 海,路颜霞

(1.陆军工程大学 通信工程学院, 南京 210007； 2.解放军93303部队，沈阳 110000)

1 引言

无线可充电传感器网络[1](wireless rechargeable sensor networks，WRSNS)由多个可充电的无线传感器组成，具有稳定，抗干扰能力强，功耗低等优点，在许多方面有着广泛的应用，而无线传感器网络的能量补充成为了制约其发展的主要问题[2]。目前较普遍的方式是通过无人机等移动充电设备对无线传感网络进行电能的补充，这样既能节省成本，也不会导致网络失效中断。

无人机具有体积小、质量轻，飞行速度快，能够轻松的越过地面障碍到达指定区域，所以无人机携带大容量充电模块为无线传感网络进行补充能量的方式已经逐渐成为大家研究的热点[3-5]。目前主要的充电模式分为2种，一种是按需充电[6-7]，另一种是周期性充电[8]。在小规模无线可充电传感网络中，采取单移动设备为传感网络充电的情况较为普遍[9]。在大规模传感器网络中，部分传感器可能会出现长期得不到充电而失效死亡的情况。为解决大规模无线可充电网络充电问题，就需要引入多个移动充电设备，文献[10]中提出了一种多移动充电设备充电调度方法，每个设备都按照预先规划的路径对自己所分配的传感器进行周期性充电，任务结束后回到基站。文献[11]中提出将行驶距离、充电时间以及成本进行加权处理，构造新的成本目标模型，采用改进的鸽群混合遗传算法求解加权后最小成本的充电路径。文献[12]中描述多无人机对多目标进行搜索，求解完成所有任务的最短时间，首先利用K-means聚类算法将目标点进行分类，再将分好的目标点分配给多架无人机，利用改进的遗传算法对每架无人机的飞行路径分别进行求解。文献[13]中提出一种基于节点重要级别的双移动设备协同充电的路径规划算法，将节点失效率与路径能耗比总能量作为评价指标，首先将传感器与移动充电设备的距离和移动充电设备在移动充电过程所剩余的能量作为匹配的依据，根据匹配度为两个移动充电设备分配待充电的传感器，分配任务后根据传感器所剩余的时间以及与移动充电设备的距离确定传感器充电的顺序。

以上无人机协同任务方式均未考虑到无人机之间任务分配的公平性。在大规模充电网络任务背景下，本研究中建立多无人机协同充电任务模型，将整体完成任务时间最短作为优化目标，可以表示为一个最小-最大的路径覆盖(min-max tour cover,MMTC)问题[14],让所有无人机中完成任务最大的时间最小化，提出了一种路径分解算法(path decomposition algorithm，PDA)，求得一条能够覆盖所有传感器且飞行距离最短的路径，通过路径分解算法对得到的路径进行平均分解，将分解后得到的路径片段首尾连接起点形成闭合路径，在分配给每架无人机，在对每架无人机的路径重新进行规划，求整体任务的完成时间最小。

2 系统模型与问题描述

2.1 系统模型

无线传感网络充电模型如图1所示，该网络由N个可充电的无线传感器、1个可以对无人机进行调度的基站、k架无人机组成。无线传感器位置随机分布，用来收集和转发区域内传感器信息，k架无人机初始位于基站位置，基站根据无线传感器任务量以及无人机的数量对多架无人机进行任务调度同时并能够收集区域内所有无线传感器的信息，多架无人机为区域内无线传感器进行周期性充电，假设无人机在固定高度飞行。

图1 统模型图

2.2 问题描述

无人机对传感器充电时采取悬停在传感器正上方的方式，传感器接受功率与无人机的发射功率之间的关系为[15]

(1)

式中：Pr为传感器接收功率；Pt为无人机充电发射功率；d为无人机与传感器之间的距离；β为距离改变时的补偿参数。无人机完成任务的时间分为悬停充电和飞行时间，无人机全程匀速飞行，飞行时间Tf取决于无人机飞行的路径长度，计算方式为

(2)

(3)

式中：Cmax为无线传感器满载时的电量；Ci表示第i个传感器初始状态剩余能量；Si为无人机的第i悬停点,在无人机到达传感器之前，传感器在持续消耗电量；p为传感器消耗能量的速率；定义ti为无人机从开始充电任务直至到达第i个传感器所花费的时间：

(4)

式中：Li-1,i为无人机从第i-1个传感器到第i个传感器的飞行距离。在充电任务中，不同无人机负责不同的传感器，一架无人机同一时间只能对一个传感器进行充电，无人机完成总任务时间Ttotal为无人机飞行时间和悬停充电时间之和

Ttotal=Tf+Thv

(5)

(6)

式中：l(x)为无人机的飞行路径，本研究的目的是通过对k架无人机的路径规划，实现任务的平均分配，使得完成区域内所有传感器充电任务时间最短，即耗时最大的无人机时间最少。数学模型表达如下

(7)

(8)

Ci-pti≥Elimit

(9)

3 算法描述

3.1 改进的粒子群算法

粒子群算法容易早熟，并容易陷入局部最优值，收敛速度慢，针对粒子群算法的缺点，在传统粒子群算法的基础上引入了线性递减权重的方法(linearly decreasing weight，LDW)和遗传算法中的交叉变异过程(genetic algorithm，GA)。粒子群算法中惯性因子ω对于粒子群算法的收敛性有较大的影响，惯性因子ω增大，有利于增强全局搜索能力，ω减小，有利于增强局部搜索能力，引入惯性权重递减方法，使惯性因子ω随迭代次数衰减，使得在搜索后期可以加速收敛，这种采用惯性权重根据迭代次数去进行自适应变化，相比于传统粒子群收敛速度更快，算法后期局部搜索能力强，权重递减为

(10)

式(10)中：ωmax、ωmin分别为惯性因子的最大和最小值，一般将ωmax设置为0.9，ωmin设置为0.2；k为当前迭代次数，kmax为最大迭代次数。改进后的粒子群速度位置更新表达式为

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

(11)

xid=xid+vid

(12)

式(11)、式(12)是改进后的粒子速度位置更新公式，但LDW改进方法由于种群缺乏多样性，仍存在陷入局部最优的缺点，而遗传算法种群规模较大，通过交叉变异不断地扩大种群的多样性，交叉操作是在种群中选取较大比例的个体，对选出的个体相互之间部分结构进行交叉互换，变异操作是在种群中选出小部分个体，使个体自身中部分结构进行改变，遗传算法能够求出优化问题的全局最优解，具有较强的鲁棒性，适合于求解复杂的优化问题，应用较为广泛。但是遗传算法的收敛速度慢，局部搜索能力差。本文中将2种改进方式结合，在粒子群算法基础之上所改进的算法简称为LG-PSO算法。首先对染色体进行设置，将N个传感器节点从1到N进行编号，从左至右表示点被访问的顺序。一个完整的染色体就是无人机对N个传感器充电访问的次序，整个种群即为这N个传感器访问顺序的全排列。即一个完整的序列表示一个解。对适应度函数设置为

(13)

式中：fit代表适应度函数，目标函数Ttotal(max)为所有无人机路径中飞行时间的最大时间最小，即目标函数是求最小值，而适应度值是越大越好，因此设定适应度值等于目标函数值的倒数，这样适应度越大表示目标函数值越小，也就是解的质量越高，LG-PSO算法实现过程为：

输入：染色体数量、迭代次数、种群规模、交叉概率Pc、变异概率Pm、

输出：充电路径

初始化种群

whileiter

计算种群当前适应度fit

根据fit轮盘度选择2个优秀父代a,b；

ifrand(0,1)

c=cross(a,b)//选取的父代个体之间染色体交叉,交叉产生新的子代

end

ifrand(0,1)

d=meta(a)

e=meta(b)//选取的父代个体部分染色体变异,变异产生新的子代

addcde到新种群

end

选取当前最优个体作为粒子群初代个体成员；

利用粒子群算法机制进行邻域搜索；

更新种群个体；

end

Return充电路径

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

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

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

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

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

5) 重复步骤2)—4)，设置最大迭代次数为1 000次，当达到最大迭代次数时停止搜索，输出最佳结果。

3.2 路径分解算法

路径分解算法过程如图2所示，对其采用图论的方式进行描述，表示G=〈S,L〉,S中的每个节点代表无人机为传感器充电的悬停位置，S=(S0,S1,…,Si,…,SN,)，L中的每条边代表无人机在传感器之间的飞行路径,L=(L0,L1,…,Li,…,LN),定义路径分界点为B=(B1,…,Bi,…,BN-1),分界点的作用是将路径等分为k段，考虑到任务公平分配原则，将时间作为任务分配的依据，包括无人机飞行时间和为传感器充电悬停的时间。

图2 路径分解流程

算法步骤为:

2) 根据路径上累计的飞行时间和平均时间求得分界点，采用路径分解算法分解路径后分配给无人机。以第一个分界点为例，从无人机起飞点开始累计在此条路径上飞行、悬停充电的时间Tj,当Tj=Tave时，记录下在路径上无人机的位置点，作为第一个路径分界点记为B1，分界点位置存在2种情况；

情况1：当分界点位于节点Si上

图3为分界点位于节点Si上的情况。将节点Si-1以及节点Si-1之前的路径和节点分配给第1架无人机，节点Si-1作为第一架无人机的终点，删除边Li-1，得到第1架无人机的路径。将节点Si作为第2架无人机的起点，无人机从节点Si累计在此条路径上飞行、悬停充电的时间，当再次达到Tj=Tave时，判断分界点B2位于节点S还是位于边L上，若B2位于节点S上，继续按照此步骤寻找下一分界点B3，若B2位于边上，则按照情况2步骤执行。直至寻找到第k-1个分界点，将k个路径片段完全分配给无人机结束。

图3 路径分解图

情况2：分界点位于边Li上

图4为分界点位于边Li上的情况，将Si节点以及Si之前的路径和节点分配给第1架无人机，Si节点作为第1架无人机的终点，删除边Li，得到第1架无人机的路径。将节点Si+1作为第2架无人机的起点，无人机从节点Si+1累计在此条路径上飞行、悬停充电的时间，当再次达到Tj=Tave时，判断分界点B2位于节点还是位于边上，若B2位于节点上，则按照情况1步骤执行，若B2位于边上，继续按照此步骤寻找下一分界点B3，直至寻找到第k-1个分界点，将k个路径片段完全分配给无人机结束。

图4 路径分解图

3) 路径分配给k架无人机后，将路径片段连接原点形成闭合回路，利用LG-PSO算法对每架无人机闭合回路中包含的所有传感器在进行路径规划，求得每架无人机的耗时最短充电路径。

4 仿真性能和结果分析

为了验证本文中所提出算法的优越性，将最大时间、平均时间、时间方差作为评价指标，分别对比了均值聚类加改进粒子群算法(K-MEANS[12]+LG-PSO)和多旅行商遗传算法(KTSP-GA[16])，传感器初始电量在2～3 J之间随机生成，部分仿真参数的设置如表1所示。

图5为目标区域设置为200 m2，无人机数量设置为3，传感器数量设置为100，3种算法下无人机为地面传感器充电的飞行轨迹。

表1 仿真参数Table 1 Simulation parameters

图5 不同算法下无人机飞行轨迹

4.1 传感器数目的影响

目标区域设置为200 m2，无人机数量设置为3，图6、图7、图8分别为3种算法的无人机最大时间、平均时间、方差的变化，随着传感器数量增多，3种算法的无人机最大时间、平均时间也随之而增大。PDA+LG-PSO算法相比于KTSP-GA算法在最大时间上降低了5.45%～11.72%,在平均时间上降低了2.28%～7.74%，在时间方差上降低了38.15%～96.91%，相比于K-MEANS+LG-PSO算法在最大时间上降低了5.4%～29.28%，在平均时间上降低了1.21%～7.94%，在时间方差上降低了了24.14%～98.97%。PDA+LG-PSO算法在无人机最大时间、平均时间上能够稳定的增加，时间方差上变化幅度很小，基本上不受传感器数量变化的影响，体现出算法稳定的特点。KTSP-GA算法在无人机最大时间、平均时间上也能够表现出稳定的增加，但时间方差随着传感器数量的增加而增大。而K-MEANS+LG-PSO算法表现的不够稳定，在最大时间和方差上均波动更大，KTSP-GA算法在无人机最大时间增加上存在不稳定的情况，时间方差上也存在较大的波动。

图6 最大时间与传感器数量的关系

图7 平均时间与传感器数量的关系

图8 时间方差与传感器数量的关系

图9为在PDA+LG-PSO算法下，传感器数量变化时的每架无人机完成任务时间，从图9中可以看出，随着传感器数量增多，每架无人机的任务时间也随之增加，3架无人机完成任务的时间差值很小，仿真结果证明了传感器数量变化的条件下，PDA+LG-PSO算法仍然能够表现出公平性。

图9 不同传感器数量下每架无人机完成任务的时间

4.2 传感器数目的影响

目标区域设定为200 m2,传感器数量为100。图10、图11、图12分别为3种算法无人机最大时间、平均时间、方差的变化，从其中可已看出，随着无人机数量的增多，3种算法的无人机最大时间、平均时间随之而减小，PDA+LG-PSO算法相比于KTSP-GA算法在最大时间上降低了4.98%～11.72%,在平均时间上降低了1.16%～7.74%，在时间方差上降低了了4.29%～94.48%，相比于K-MEANS+LG-PSO算法在最大时间上降低了16.31%～30.91%，在时间方差上降低了了56.32%～96.72%。

图10 最大时间与无人机数量的关系

图11 平均时间与无人机数量的关系

图12 时间方差与无人机数量的关系

从图11可以看出，当无人机数量超过7架的时候，PDA+LG-PSO算法在平均时间上要高于K-MEANS+LG-PSO算法，PDA+LG-PSO算法并没有体现出优势。图12可以看出，K-MEANS+LG-PSO算法在方差上依旧表现出波动较大。KTSP-GA算法随着无人机数量的增加，时间方差变化曲线幅度较小，表现出相对比较平稳，而PDA+LG-PSO算法随着无人机数量的增加，方差也随之增加，当无人机数量为10的时候，基本上与KTSP-GA算法持平。图13为PDA+LG-PSO算法下不同无人机数量时每架无人机完成任务的时间，从图13中可以看出，随着无人机数量的增多，每架无人机完成任务的时间随之减少，但当无人机数量超过5架的时候，最后一架无人机完成任务的时间相比于其他无人机完成任务的时间有明显减少的趋势，无人机数量的增加，最后一架无人机完成任务时间相比于其他无人机完成任务时间减少得越多，原因是因为在路径分解过程中，由于部分路径片段的删除，导致分配给最后一架无人机的任务减少，所以无人机数量越多，删除的路径片段越多，最后一架无人机所分配的任务量越少，完成任务时间就会越少，这也是PDA+LG-PSO算法随着无人机数量增加时间方差随之增加的原因。当无人机数量控制在一定数量下，无人机数量变化并不影响PDA+LG-PSO算法的公平性。

图13 不同无人机数量下每架无人机完成任务的时间

4.3 目标区域大小的影响

传感器数量设置为100，无人机架数为3。图14、图15、图16分别为3种算法无人机最大时间、平均时间、方差的变化，从其中可已看出，随着传感器区域的增大，3种算法的无人机最大时间、平均时间均随之而增大。PDA+LG-PSO算法相比于KTSP-GA算法在最大时间上降低了 8.92%～11.72%,在平均时间上降低了4.86%～7.74%，在时间方差上降低了了88.16%～97.55%，相比K-MEANS+LG-PSO算法在最大时间上降低了8%～16.32%，在平均时间上降低了 2.05%～7.94%，在时间方差上降低了92.17%～98.51%。PDA+LG-PSO算法、KTSP-GA算法无论是在无人机最大时间还是平均时间上都表现出稳定上升，而K-MEANS+LG-PSO算法虽然在无人机最大时间和平均时间上整体呈增加趋势，但是仍旧表现的不够稳定，存在一定的波动，时间方差上波动更大，PDA+LG-PSO算法在时间方差上表现的仍然非常稳定，并没有随着区域的增大而引起较大的变化。

图14 最大时间与目标区域的关系

图15 平均时间与目标区域的关系

图16 时间方差与目标区域的关系

图17为采用PDA+LG-PSO算法下不同区域下每架无人机完成任务的时间，从其中可以看出，随着目标区域的增大，每架无人机的任务时间也随之增加，但3架无人机完成任务的时间差值很小，仿真结果证明了在区域变化的条件下，PDA+LG-PSO算法仍然能够表现出公平性。

图17 不同区域下每架无人机完成任务时间

4.4 无人机起点不同的影响

为了验证PDA+LG-PSO算法的优越性，设置了不同的无人机起飞点，测试当无人机起飞点不同对3种算法无人机最大时间的影响。图18为3种算法下无人机最大时间与不同起飞点坐标之间的关系，目标区域设定为200 m2，无人机架数设置为3，区域传感器节点数目设置为100个，起点坐标从(0.0)到(200.200)，测试了5组坐标下3种算法无人机的最大时间。从测试结果来看，PDA+LG-PSO算法相比于其他2种算法在无人机最大值上仍然有明显的优势，起飞点坐标的变化对并没有影响3种算法的最大时间。

图18 最大时间与起点坐标的关系

5 结论

本文中研究了大规模无线可充电传感网络充电任务下的多无人机协同路径规划问题，以无人机完成任务时间作为优化目标，针对传统多无人机路径规划任务分配不均衡的问题，提出了一种路径分解算法，在对每架无人机进行路径规划时，又对粒子群算法进行了改进，在多个方面与KTSP-GA算法和K-MEANS+LG-PSO两种算法进行了对比，根据仿真结果得出结论如下：

1) PDA+LG-PSO算法对比KTSP-GA算法和K-MEANS+LG-PSO算法，在整体完成任务时间、时间均值、方差等方面上实现了较大的性能提升。

2) 无人机起飞点的不同并不影响PDA+LG-PSO算法的性能。

3) PDA+LG-PSO算法最大限度地实现了任务的平均分配，在大规模无线可充电网络中非常适用。