基于路径规划的无人机加权高效分簇方法

严 磊,雷 磊,蔡圣所,路志勇

(1.南京航空航天大学 电子信息工程学院,南京 210016; 2.中国电子科技集团公司第五十四研究所,石家庄 050081)

0 概述

无人机编队网络不依赖任何固定的基础设施,由具有无线收发功能的无人机节点组成。为了提高编队网络的可扩展性,无人机编队网络普遍采用分级式的网络结构,即对网络实施分簇管理[1]。

均衡网络中无人机节点的负载和能耗,延长网络的最大生存周期是无人机分簇算法的一个重要实现目标。在网络中,簇首负责簇内成员之间的通信和簇内成员与其他簇成员之间的通信服务,因此,实现分簇算法的关键在于选择合理的无人机节点担任簇首[2]。

文献[3]提出的最小ID号算法通过节点的ID号对网络进行分簇。在分簇过程中,选取相邻节点中ID号最小的节点担任簇首,簇首的一跳范围内还未加入其他簇的邻居节点加入该簇;在剩余未确定身份的节点中,重复以上步骤,直至每个无人机节点获得自己的身份。虽然该算法具有实现方便,计算量小等优点,但是由于较小ID号的节点频繁地被最小ID号算法选择担当簇首,而簇首需要负责簇内成员以及簇间成员通信任务,因此电池能耗远大于簇成员。可能会因为簇首的电量迅速耗尽,导致网络的生命周期[4]被严重的缩短。

文献[5]提出的加权分簇算法(WCA)。在最小ID号算法的基础上,综合考虑了节点的相对移动性、理想节点度[6]及电池电量[7]等因素,对每一种影响因素分别赋予不同的权重比例,从而生成最终的权重,以此评价节点担任簇首的能力。在该算法中,优先选择相对移动性低,剩余电量较多且节点度合理的节点担任簇首,实现节点间的负载均衡,延长了网络的生命周期。

最小ID号算法和WCA虽然在一定程度上延长了网络的生命周期,但是它们都没有充分考虑到网络中无人机编队的拓扑变化对分簇结构的影响。在现有的无人机分簇算法中,无人机普遍采用自由运动模型实现无人机的飞行运动,而这并不符合无人机飞行的实际情况。事实上,由于无人机飞行一般都携带任务,它们的航线轨迹都是被提前规划好的。所以在无人机的高效分簇算法的设计中,为了实现网络的负载均衡[8],达到延长网络的生命周期的目的,还必须同时考虑无人机编队拓扑变化带来的影响[9]。

本文通过无人机路径规划算法实现对无人机编队飞行线路的设计,同时充分考虑在路径规划条件下无人机编队网络拓扑变化对分簇结构的影响。在此基础上,提出基于路径规划的簇首加权选举算法(Weighted Head Election Algorithm based on Path-planning,WHEA-P)和基于路径规划的簇成员加权调整算法 (Weighted Hluster Adjustment Algorithm based on Path-planning,WCAA-P)。

1 基于路径规划的无人机网络加权高效分簇

针对现有的无人机分簇算法没有充分考虑路径规划条件下,无人编队网络拓扑变化对分簇结构的影响带来的弊端,本文在基于粒子群算法(POS)的无人机路径规划的基础上,实现了2种基于路径规划的无人机网络加权高效分簇方法(WHEA-P和WCAA-P)。

1.1 基于POS的无人机路径规划

POS[10]是一种受到飞鸟集群活动规律启发而提出的进化算法,已广泛应用于无人机网络部署[11]。本文采用文献[12]提出的POS实现了无人机在多障碍物的环境下的路径规划。POS相比遗传算法而言,没有变异和交叉运算,仅仅借助于粒子的速度完成搜索,因此具有搜索速度快、实现简单等优点。此外它还拥有记忆性,记忆粒子群体的历史最好位置并且将它传递给其他粒子,优化粒子的迭代结果,提高粒子的适应度。在该算法中,首先在无人机初始位置放置一群随机粒子,然后通过计算每个粒子的适应度[13]进行迭代,直至找到最终目标。在生成的所有粒子路径轨迹中,找到一条远离威胁区且距离最短的路线,即为无人机的最佳飞行线路。图1给出了在20 km×20 km的仿真监控区域中3架无人机的路径规划,其中小圆圈代表无人机的起点,x代表无人机的终点,大圆圈代表威胁区。

图1 在20 km×20 km的仿真监控区域中3架无人机的路径规划

1.2 WHEA-P原理

WHEA-P在簇首选举阶段考虑了相对移动速率这一指标的弊端,用稳定度S替代相对移动速率,作为分簇的重要权重指标进行考虑。稳定度S反映了每个竞选簇首的节点拥有的稳定的邻居节点的个数。稳定的邻居节点是竞选簇首的节点的邻居节点,并且在分簇周期内到竞选簇首的节点的距离始终小于最大传输距离。竞选簇首的节点拥有的稳定的邻居节点的数目越多,则它的稳定度越高,当选簇首的概率也就越大。此外,选举节点担任簇首还需要考虑节点的剩余能量P和节点的节点度d。簇成员的能耗要远低于簇首的能耗,因此应当优先选择电量充足的节点担任簇首。簇首节点拥有的成员节点的数量超出所能承受的门限值,会带来网络性能下降和簇首节点能耗的大幅提高等弊端,严重情况下会导致网络的瘫痪。因此,在簇首选举时,节点的理想节点度D和节点度d的差值也是一个重要的影响因素。

1.2.1 相对移动速率的弊端

在WCA中,无人机的相对移动速率是评判无人机能否成为簇首的一个重要指标。文献[14]提出可以根据计算各节点的平均运动速度计算节点的相对移动性。假设节点u的邻居节点集合为Nu,节点u相对邻居节点v的速度为V(u-v),则节点u相对于所有邻居节点的平均运动速度定义为:

(1)

节点的相对移动速率越小,担任簇首的概率越大。但在实际情况下,无人机相对移动速率这一指标很难客观准确地评定无人机之间的相对移动性。[t,t+Δt]时刻簇内无人机运动情况如图2所示。

图2 [t,t+Δt]时刻簇内无人机的运动情况

由图2观察可以看出,邻居节点v1、v2朝向簇首u运动,邻居节点v3、v4远离簇首u运动。虽然根据式(1)计算得出的在t+Δt时刻无人机的相对移动速率减小,但是由于邻居节点v3、v4到簇首u的距离超过最大传输距离R,导致簇首u的簇成员反而减少,因此簇首u不适合继续担任簇首。

1.2.2 稳定度计算

在[t,t+Δt]分簇周期内,在选举t时刻的簇首时,需要计算t时刻每个竞选簇首的节点i的稳定度Si(t)。借助路径规划获取的无人机飞行路线,可以计算[t,t+Δt]分簇周期内t时刻节点i的稳定度Si(t)。Nnbr,i(t)是t时刻竞选簇头的节点i的邻居节点的集合,Si(t)初始化为Nnbr,i(t)集合中邻居节点的数目。在[t,t+Δt]分簇周期内,选取n个均匀离散的时间点,在每个离散的时间点分别计算Nnbr,i(t)集合中的每个邻居节点到竞选簇首节点i的距离,如果它们的距离超过传输距离R,那么就将当前邻居节点从Nnbr,i(t)集合中移除,同时Si(t)做减1处理。最终就可以求得t时刻节点i的稳定度Si(t)。计算稳定度的伪代码如下所示。

算法1t时刻节点i的稳定度Si(t)

Si(t):Stability of node i at t moment

Nnbr,i(t):Set of nodes at range of cluster head’s transmission distance R at t moment

BEGIN

1.initial Si(t) which equals the number of neighbor nodes in Nnbr,i(t)

2.initial ttemp←t,r←0

3.while ttemp

4. for each neighbor node j in Nnbr,i(t)

5.if distance between neighbor node j and node i >transmission distance R then

6.Si(t)←Si(t)-1

7.remove neighbor node j from Nnbr,i(t)

8.end if

9.end

10.r←r+1

11.ttemp←t+r*Δt/n

12.end while

1.2.3 WHEA-P具体步骤

WHEA-P步骤如下:

步骤1开始阶段,依次给每个无人机节点按照从小到大分配ID号,然后利用最小ID号算法对无人机网络进行初始分簇。

步骤2每个簇首选举周期,各节点根据其剩余电量、稳定度及节点度计算权值W:

W=wpP+wsS+wd|d-D|

(2)

其中,wp、ws、wd为权值系数,权值大小可以根据实际情况进行设定,但是必须满足wp+ws+wd=1,d为邻居一跳范围内无人机节点的个数,D为理想节点度,可以考虑无人机的架数除以仿真范围内簇的数目求得,当然也可以根据实际情况动态调整,S为无人机节点的稳定度,P为无人机节点的剩余能量。

步骤3簇首获取簇内簇成员的权值W。

步骤4簇首将接收到的权值按照从大到小的顺序进行排序,然后重新向簇内成员分配ID号。分配原则如下:拥有最大权值W的节点获得最小ID号,拥有最小权值W的节点获得最大ID号。若存在拥有相同W值的2个节点,则簇首随机选择一个节点,使它获得较小的ID号。

步骤5簇首向其成员节点发送新的ID号。

步骤6成员节点用新的ID号替换旧的ID号,然后调用最小ID号算法进行重新分簇。

1.3 WCAA-P原理

WCAA-P分为簇首选举和簇成员调整2个阶段,其中簇成员调整阶段是WCAA-P的主要创新之处。簇首选举阶段通过WCA确定簇首;簇成员调整阶段每个簇成员节点借助无人机路径规划生成的飞行线路,分别考虑与每个簇首的飞行线路的接近程度和该簇首的簇内成员个数。计算簇成员到每个簇首的飞行线路的接近程度,可以通过在簇成员飞行线路上选取n个有代表性的离散点,再计算出簇成员到簇首的平均欧拉距离,用来反映飞行线路的接近程度。此外为了避免簇内成员过多导致负载不均衡,还须要考虑簇成员选择加入的簇,它的簇内成员个数与理想节点度D的差值的情况。最终求出权值,综合考虑后选择最合适的簇首,加入该簇。每个簇成员依次重复上面的过程,计算出到每个簇首的权值,然后选择最合适的簇首,加入该簇。该算法确保每个簇成员都能选择合适的簇首,并且保证每个簇首拥有合理的簇成员数。

1.3.1 WCAA-P具体步骤

WCAA-P步骤如下:

步骤1开始阶段,依次给每个无人机节点按照从小到大分配ID号,然后利用最小ID号算法对无人机网络进行初始分簇。

步骤2每个簇首选举周期,各节点根据WCA计算出的权值W进行分簇,确定簇首。

步骤3借助路径规划获得的无人机编队的拓扑结构和飞行线路,计算每个簇成员到每个簇首节点i平均欧拉距离Li和对应簇首i的节点度di。

例如,在t时刻进行分簇,执行完步骤2确定簇首后,在[t,t+Δt]分簇周期内选取n个均匀的离散时间点并且根据路径规划中[t,t+Δt]时间内的无人机编队的飞行线路,求出每个簇成员到每个簇首节点i的n个时刻平均欧拉距离Li和对应簇首i的节点度di。

(3)

其中,Li,j为j时刻簇成员到簇首i的欧拉距离,j为[t,t+Δt]分簇周期内取得的n个均匀离散的时间点,i=1,2,…,N且i为簇首。

步骤4簇成员根据平均欧拉距离Li和节点度di计算到每个簇首的权值Wi,每个簇成员依次选取权重值最大的簇首,加入该簇,成为簇成员。

Wi=εLi+(1-ε)|di-D|

(4)

其中,i=1,2,…,N且i为簇首,ε为权重系数,可以根据实际需求进行设定,Wi为当前簇成员到簇首i的权值,Li当前簇成员到簇首i的平均欧拉距离,di为簇首i的节点度,D为理想节点度。

1.3.2 WHEA-P和WCAA-P比较分析

WHEA-P和WCAA-P分别在簇首选举阶段和簇成员调整阶段考虑无人机编队的拓扑结构和飞行线路的影响,实现节点的负载均衡,达到延长网络生存时间的目的。相比较而言,WHEA-P选择稳定度高的节点担任簇首,簇内稳定的簇成员数目较多。因此簇首相比WCAA-P变动频率更低,簇首结构更加稳定,很少存在簇首由于簇内没有任何簇成员而寻求加入其他簇成为簇成员的情况。而WCAA-P中簇成员相比WHEA-P更加稳定,变动频率更低,这是因为每个簇成员依照自己的飞行线路,优先选择与自身飞行线路最为接近的簇首,并加入该簇。因此簇成员脱离原有簇的概率大大降低,簇结构更加稳定。

2 仿真与结果分析

本文在Matlab环境中实现了2种无人机加权分簇的改进算法(WHEA-P和WCAA-P),并且对2种改进算法与最小ID号算法和WCA的性能进行了对比和分析。在无人机分簇算法中,网络生存时间是重要的性能指标。网络生存时间定义为从无人机网络初始化到网络中首个节点死亡的时间[15]。主要仿真参数如表1所示。

表1 仿真参数

2.1 WHEA-P中稳定度的权重系数取值

本文通过改变WHEA-P中稳定度的权重大小ws,研究该算法中网络生存周期(算法执行周期数)与稳定度的权重大小的关系。图3指出了无人机网络生存周期与稳定度的权重在不同仿真实验环境下的变化关系。由图3所示的仿真结果可知,在20 km×20 km的仿真监控区域中,当稳定度的权重系数ws接近0.5时,网络生存周期取得最大值。因为当算法中稳定度的权重系数过小,无法充分体现出路径规划条件下,无人机编队网络拓扑变化对分簇结构的影响;而当稳定度权重系数过大,也不能充分反映WHEA-P中其他因素(例如节点剩余能量和无人机节点度与理想节点度的差)带来的影响。本文给出参数ws的建议取值区间为:

ws∈[0.45,0.55]

(5)

图3 稳定度的权重系数ws对网络生存周期的影响

2.2 基于路径规划的无人机分簇算法仿真

假定每个簇成员节点的能耗与该节点到其簇首节点的距离成正比,簇首的能耗与簇内成员节点的数目成正比。设置无人机的初始能量值为2 000。本文借助于路径规划,对最小ID号算法(本文所有图中标为LeastID)、WCA及2种改进的无人机加权分簇算法(WHEA-P和WCAA-P)的性能进行了详细的仿真实验与对比分析。图4展示了在20 km×20 km的仿真实验区域中无人机节点的数量由20到100架的情况下,基于路径规划的4种算法的仿真对比结果。

图4 基于路径规划的4种算法仿真结果对比

由图4可以看出,根据WHEA-P和WCAA-P获得的网络生存时间比最小ID号算法和WCA的网络生存时间长。无人机的网络生存时间会随着无人机的架数的增多而减小。产生这种变化的原因在于随着无人机架数的增多,簇内簇成员的数目不断增加,由于簇首的能耗与其成员节点的个数成比例,簇首的能量会急剧损耗,最终导致整个网络生存周期的缩短。但是随着无人机架数的增加,WHEA-P和WCAA-P性能要远远优于最小ID号算法和WCA。当无人机架数等于100的时候,WHEA-P和WCAA-P的网络生存时间要比WCA延长50%左右。

网络终止时无人机的平均剩余能量也是反映网络生命周期的一个重要指标。网络终止时,无人机的平均剩余能量越多,则网络负载越不均衡,网络的生存周期越短。结合图5可以看出,当无人机架数大于60架时,WHEA-P和WCAA-P的平均剩余能量要远小于最小ID号算法和WCA。

图5 网络终止后无人机的平均剩余能量

无人机平均重入簇次数是评价簇结构稳定性的一个重要指标。无人机节点重新加入其他簇的次数越少,那么簇的结构越稳定。如图6所示,单位时间内节点重入簇次数随节点的传输距离增大而减小。因为传输范围越大,簇的统治范围越大,节点脱离原有簇的概率减小。由于WCAA-P在簇成员调整阶段,每个簇成员根据拓扑结构的变化,选择飞行线路与自身最为接近的簇首,并加入该簇,因此相对其他3种算法而言性能最好,簇的稳定性最强。

图6 单位周期内平均重入簇次数

无人机簇统治集更新次数[16]也可以用来评价簇结构的稳定性。本算法规定当节点脱离原来的簇,而无法加入其他簇,则自己成为簇首,并触发统治集更新。图7反映了单位周期内无人机簇统治集更新次数随无人机传输距离变化的情况。随着传输距离的增大,无人机簇统治集更新次数变少。同样也是因为随着传输范围变大,簇的统治范围变大,节点脱离原有簇的概率变小。相比较而言,由于WHEA-P在簇首选举阶段选取的簇首节点具有邻居节点数目多,变动频率低和稳定性强的优点,因此很少存在簇首节点由于簇内没有任何簇成员节点而寻求加入其他簇,成为簇成员的情况。可以看出,WHEA-P簇首结构稳定度高,性能要略优于其他3种算法。

图7 单位周期内无人机簇统治集更新次数

WHEA-P和WCAA-P性能要优于最小ID号算法和WCA,它们的仿真指标曲线都非常接近。这是因为WHEA-P和WCAA-P分别在簇首选举阶段和簇成员调整阶段考虑无人机编队网络的拓扑变化对分簇结构的影响。WHEA-P中通过稳定度S这一参数,选择最合适的无人机节点担任簇首,保证了无人机簇内簇成员的个数的稳定和数量的合理,实现了负载均衡,降低了簇首的能耗负担,从而增大了网络的生存周期。而WCAA-P在确定簇首后,每个簇成员借助于路径规划获得的飞行线路,通过比较自身与每个簇首的飞行线路的接近程度,并考虑每个簇首的簇内成员个数,选择最合适的簇首,成为其簇成员,也实现了网络的负载均衡和节点能耗的降低,延长了网络的生存周期。

3 结束语

本文针对现有的无人机分簇算法在没有充分考虑路径规划条件下,无人编队网络拓扑变化对分簇结构的影响所带来的弊端,采用基于PSO的无人机路径规划,实现了2种基于路径规划的无人机加权高效分簇方法(WHEA-P和WCAA-P)。WHEA-P和WCAA-P分别在簇首选举阶段和簇成员调整阶段考虑无人机编队网络的拓扑结构变化带来的影响,从而实现均衡节点负载,延长网络生存时间的设计目标。仿真结果表明,WHEA-P和WCAA-P的性能要优于最小ID号算法和WCA,它们的网络生存周期更长并且负载更加均衡。在今后的研究工作中,将会继续考虑通信方式、服务质量、网络安全对无人机编队网络能耗的影响,进一步改进分簇方法,延长网络生存周期。