自适应ANP-CRITIC的无人机集群网络优化算法*

党元章，华 翔，张金金，石成泷，蒋天启

(1.西安工业大学 电子信息工程学院,西安 710021;西安工业大学 兵器科学与技术学院,西安 710021;3.西安工业大学 机电工程学院,西安 710021)

随着通信及其相关技术快速发展,相比于单个无人机,无人机集群在态势感知、临场决策和干扰对抗等方面有质的提升[1-4]。而无人机集群以编队形式执行任务是当前研究的热点[5],由于无人机集群在编队飞行过程中节点随机失效和任务场景复杂多变,导致网络拓扑结构频繁变化,网络管理变得尤为困难,而分簇是优化网络管理的有效手段。无人机集群网络采用分簇结构有许多优点,诸如减少路由开销、避免簇内冲突、便于网络管理以及延长网络寿命等[6-8]。

目前针对不同的应用环境和组网要求已存在许多类型的分簇算法,包括最小ID分簇算法(Low ID Clustering Algorithm,LID)[9]、最高连通度分簇算法[10]和加权分簇算法(Weighted Clustering Algorithm,WCA)[11],前两种算法的不足在于簇首选取判定依据的参数单一,基于最小ID和节点最大连通度为依据导致簇首选取缺乏准确性;而加权分簇算法则加入了多方面的因素指标,具有很强的可塑性。因此,许多学者在加权分簇算法的基础上进行改进,提出新的算法。文献[12]提出了一种智能的多参数无人机集群组网算法,该算法首先将节点位置信息和剩余能量作为适应度函数来选取簇首,接着提出簇首重选机制,以实现稳定的集群维护和拓扑管理。文献[13]提出了一种基于改进灰狼算法的分簇算法,首先通过节点相对移动性和距离进行簇范围划分,接着选取簇内节点的剩余能量、节点度、通信情况、任务种类等多个参数指标选取簇首,实现了簇首位置的均匀分布。文献[14]提出的一种基于权值优化的分簇算法,该算法综合考量节点度、节点通信距离、剩余能量和节点移动性等指标,并动态调整簇的规模。文献[15]提出了一种基于层次分析法(Analytic Hierarchy Process,AHP)-熵权的分簇算法,通过运用AHP与熵权法计算各因素指标的主客观权重,接着综合分析并计算组合权重,提高了权重的可靠性。由此可见,分簇算法在集群组网领域应用已久,簇首选取对于分簇网络的性能至关重要。上述研究在簇首选取过程中仍存在指标权重适应性差、分簇规模差异性大等问题。

因此,文中提出一种基于自适应ANP-CRITIC的无人机集群网络优化算法(Adaptive ANP-CRITIC Weighted Clustering Algorithm,AAC-WCA),拟加入节点负载失衡度指标均衡成簇规模,结合五个关键因素指标,设置安全阈值区间并采用Z-Score法对指标数据进行标准化以提高簇首选取客观性;针对编队飞行场景与执行任务种类设计ANP法对各因素指标主观权重进行预求解,无人机集群在编队飞行过程中采用CRITIC法对各指标客观权重实时求解;引入博弈论将实现纳什均衡作为协调主客观权重的优化目标,获得自适应簇首权值;根据簇首权值选取最优簇首。以期提高簇首选取自适应性,均衡分簇规模,增强整个网络的性能的同时也延长无人机集群网络寿命。

1 场景和指标分析

1.1 应用场景

无人机集群在组成编队执行任务过程中会受到各种各样外界因素的干扰,影响一个无人机节点能否可以成为簇首的影响因素有很多,针对不同的应用场景,因素指标的重要程度也不同[16]。

文中的应用场景为无人机集群编队飞行穿过某区域执行侦查探测任务,从出发点穿过任务区的飞行过程中存在已探查的威胁干扰以及可能遭受的不确定因素干扰,出发前需要对集群网络进行分簇以优化网络管理,在飞行过程中需要根据实际的飞行状况对网络进行调整,确保集群始终保持着良好的飞行状态。无人机集群在飞行过程以编队形式自主飞行,编队内无人机节点模型应保持移动特性和群体的飞行态势,簇结构在高速移动状态下相对动态平衡。在充分考虑编队网络拓扑变化对分簇结构的影响后,文中拟选取节点连通度、节点负载失衡度[17]、节点平均通信距离、节点剩余能量和节点相对移动性作为影响无人机集群网络分簇的性能指标。

1.2 因素指标

1.2.1 因素指标计算

节点连通度指标。节点连通度是指节点与网络中所有其它节点建立一跳与两跳通信链路数的和。连通度表示分簇网络中节点建立通信连接的能力,当编队网络中节点总个数为n,邻接矩阵的幂次为v,节点i与节点j一跳路径条数表示为Nij,则节点i的连通度Ci表示为

(1)

节点负载失衡度指标。节点负载失衡度是指本节点的连通度与网络中其它节点的连通度的均值之差。该指标可以将分簇规模控制在较优范围,节点负载失衡度Li表示为

(2)

节点平均通信距离指标。节点平均通信距离是指节点与所有可以建立一跳通信链路邻居节点的通信距离之和的平均值。该指标与分簇网络中节点间的通信能耗和网络开销密切相关,当与节点i可建立通信连接的邻居节点总数为t,节点i与第j个邻居节点的通信距离为dij,则节点i的平均通信距离Di表示为

(3)

节点剩余能量指标。节点剩余能量是衡量节点是否能充当簇首的重要指标。节点剩余能量与分簇网络生存寿命密切相关,节点i的剩余能量Ei表示为

Ei=Eires,

(4)

节点相对移动性指标。节点相对移动性指节点与邻居节点在连续两次数据传输时通信距离的差异。编队形式自主飞行过程中节点间相对移动,移动性越小分簇结构就越稳定,当节点i的与邻居节点j的相对移动性为mij,则通信范围内有k个邻居节点数据交互的节点i的相对移动性Mi表示为

(5)

1.2.2 因素指标标准化

文中根据具体任务场景,定义各因素指标的阈值区间[ymin,ymax],当节点指标数据值不在阈值区间内,则该节点退出簇首的竞选,节点的各项指标值满足ymin<|yi|≤ymax条件。

综合考虑以上各因素指标的计算维度差异,文中采用Z-Score法对指标数据进标准化,使得各指标数据应对外界干扰时鲁棒性更强,可以更好的适用于网络中存在异常节点或孤立节点的情况。

假设所有节点的某一项因素指标数据组成一个序列为x1,x2,…,xn,对其进行变换得

(6)

2 基于自适应ANP-CRITIC的无人机集群网络优化

2.1 主观权重计算

网络层次分析法(Analytic Network Process,ANP)是一种适应非独立的递阶层次结构的决策方法,可以反映因素指标间相互依赖性和反馈关系的过程,并准确的对复杂网络系统进行评价,计算的主观权重更符合实际场景。执行本次任务之前,根据无人机集群执行任务种类与已知的应用场景,用ANP法评估无人机集群网络中各因素指标的重要程度,通过构造判别矩阵得出因素指标间的依赖与反馈关系,对各指标的主观权重进行分析预求解。根据ANP法设计改进步骤如下:

① 将节点连通度Ci、节点负载失衡度Li、节点平均通信距离Di、节点剩余能量Ei和节点相对移动性Mi五个因素指标用集合T={Ci,Li,Di,Ei,Mi}来表示。根据Satty给出的重要性定量对因素指标进行缩放,其中Scale=1表示比较对象同等重要,Scale=9表示比较对象极端重要,反之用倒数表示,见表1。

表1 Satty标度

② 将各个因素指标间的依赖反馈关系转换为从1到9的定量尺度范围。根据已知飞行场景信息分别将第i行和第j列对应的因素指标进行比较赋值来创建判别矩阵。判别矩阵A表示为

(7)

对判别矩阵进行归一化处理,求出每个元素占相对应列总和的比例。相应位置元素bij为

(8)

归一化矩阵B为

(9)

相对重要性是通过比较矩阵的特征值和特征向量计算的。元素的权重是在元素规范化时获得的。

③ 对归一化矩阵的每一行进行求和,求得均值获得特征向量矩阵EV表示为

EV=(EV1,EV2,…,EVn)-1。

(10)

为了验证所得判别矩阵的可靠性,引入一致性指标进行评估,包括一致性度量CM、一致性指数CI和一致性比率CR。一致性度量CM表示为

(11)

一致性指数CI表示为

(12)

ANP法中的九阶平均随机一致性系数RI对应表见表2。

表2 九阶平均随机一致性系数

一致性比率CR为

(13)

当CR≤0.1时说明权重评估准确,否则需要对矩阵中的参数进行调整。

④ 重复上述步骤,计算出所有因素指标的特征向量矩阵EV,并确保判别矩阵的一致性比率小于0.1。并将所有特征向量矩阵构造为未加权超矩阵,进行加权处理获得极限超矩阵[18]。得到各因素指标的主观权重向量w1j=(w11,w12,w13,w14,w15)。

本节通过特定场景下无人机集群各因素指标的重要度差异来分析计算得到因素指标的主观权重,表明了各因素指标之间、因素指标与备选节点之间都存在依赖或反馈关系。ANP法的总体结构关系如图1所示。

图1 簇首节点选择ANP结构关系图

2.2 客观权重计算

CRITIC法是一种基于指标数据相关性和指标信息变异程度的客观赋权法,该方法会综合考虑了指标所含信息量的大小、指标数据的波动性与相关关系对权重结果的影响以及对比强度与各指标间的冲突性。

计算指标间对比强度为

(14)

求解相关系数和冲突性量化指标值,第i项指标与第j项指标间的相关系数rij为

(15)

式中:Cov(i,j)为因素指标i与j之间的协方差,Var[i],Var[j]为因素指标i与j的方差。第j个因素指标冲突量化指标值Rj为

(16)

计算指标信息量和归一化权重,各指标的客观权重是根据对比强度和冲突性来综合衡量的。若Cj表示第j个因素指标所包含的信息量,则第j个指标的信息量Cj可以表示为

(17)

式中:Vj为第j个指标与其它指标间的标准差,Cj越大表示第j个指标所包含的信息量越大,即指标的相对重要程度越高,权重也越大。第j个指标的客观权重w2j为

(18)

客观权重不需要考虑无人机节点在特定环境下的主观影响,网络中的所有节点都使用统一标准去计算客观权重,各因素指标客观权重向量为

w2j=(w21,w22,w23,w24,w25)。

2.3 自适应ANP-CRITIC权重计算

ANP法和CRITIC法在求解过程中都充分考虑了指标间的关联性和影响程度,可以有效提升簇首选取过程中权值评估准确度。文中引入博弈论的思想修正主客观权重,优化权重组合系数,将实现纳什均衡[19]作为协调主客观权重的优化目标,在各项权重之间尽可能的寻找某个均衡点,使得最终修正的组合权重与基础权重间偏差最小,以获得最优综合权重。具体步骤如下:

① 设采用D种方法确定了m个指标因素的权重,则得到基础组合权重为Wnj={w1j,w2j,…,wnj},(n=1,2,…D) ,式中wnj表示在第n种方法中第j项指标的权重,文中D=2。设线性组合系数向量δ={δ1,δ2},则综合权重向量W的线性组合表示为

(19)

② 按照博弈论聚合模型原理,以W与Wnj之间的最小化偏差为目标得到最佳权重。目标函数Z为

(20)

根据矩阵的微分性质,确保目标函数Z最小时其最佳一阶导数条件方程为

(21)

③ 对上式中获得优化的线性组合系数δ={δ1,δ2}归一化处理为

(22)

计算综合权重向量W为

(23)

④ 将计算得到的各因素指标综合权重带入如下权重公式得到第i个节点簇首权值为

weight(i)=W1·Ci+W2·Li+W3·Di+W4·Ei+W5·Mi,

(24)

从式(24)得到每个备选节点的簇首权值,从而选出最优的簇首。本章簇首权值计算过程的伪代码为

输入:

网络拓扑信息

网络中n个节点自身信息

阈值参数[ymin,ymax]

ANP方法与CRITIC方法参数

输出:

节点簇首权值

Begin

网络拓扑与节点状态初始化

For节点i=1到ndo:

计算节点i连通度指标Ci

计算节点i负载失衡度指标Li

计算节点i平均通信距离指标Di

计算节点i剩余能量指标Ei

计算节点i相对移动性指标Mi

约束和标准化各项指标值yi

End for

While (网络中节点的综合簇首权值未全被计算) do:

基于ANP法计算主观权重w1j

基于CRITIC法计算客观权重w2j

基于博弈论方法计算自适应综合权重Wj

计算节点i的综合簇首权值weight(i)

End while

Return网络中所有节点簇首权值weight(i)

End

2.4 网络分簇

在编队网络分簇过程中,网络进行初始化,邻居节点交互信息,根据飞行过程中的节点各因素指标数据和自适应ANP-CRITIC权重求得簇首权值,根据权值选出簇首,节点优先选择通信距离更近的簇首并加入该簇[20]。其中网络中节点负载失衡度指标可以有效均衡分簇规模,算法初始化阶段可能需要进行多次迭代,无人机集群网络初始化与分簇结果示意如图2所示。

图2 网络初始化与分簇示意图

3 仿真与分析

文中采用MATLAB仿真软件环境中对AAC-WCA算法的性能进行仿真验证。并与最小标识分簇算法LID、加权分簇算法WCA和改进的加权分簇算法(Improved Weighted Clustering Algorithm,IWCA)[21]对比文中算法的性能差异。通过随机成簇规模控制、簇内平均通信距离、网络生存寿命、节点间通信质量、节点平均重入簇次数5个网络性能指标验证AAC-WCA算法的有效性。无人机集群采用编队形式自主飞行,在1 000 m2区域范围内起飞100架无人机节点,节点运动模型为RWP(Random Waypoint Model)[22],且各节点初始能量相同,簇首权值计算过程中各指标权重之和为1,具体仿真实验参数见表3,为了降低实验随机性干扰导致的实验误差,最终结果为10次仿真实验均值。

表3 仿真参数

如图3仿真结果表明,4种算法的簇首数目都随着节点通信距离的增加而减少,最佳簇首数目σ=10,由于文中AAC-WCA算法引入节点负载失衡度指标对簇首数目有限制作用,自适应选取簇首使得整个网络结构的簇首数目变化趋势更加平稳,随着节点通信距离的增加,整体簇首数目更加接近最优值,工作能耗更小;文中综合了多种指标因素,并求得自适应权重,最优簇首的选取可以使得每一轮网络能量消耗降到最小,极大的减少网络维护的次数。

图3 簇首数目随节点传输距离的变化

如图4仿真结果所示,表明了簇内平均通信距离随节点传输距离的关系。在相同节点通信距离的前提下,簇内平均通信距离越小,簇首的能量消耗就越少,从而簇维护次数也越小,它也能反应网络中簇分布的相对均衡程度。由图得4种算法的簇内平均通信距离都随着节点通信距离增加而增加,由于文中AAC-WCA算法的簇首选取时考虑了节点通信距离指标,并定义阈值对簇首与簇成员节点间的距离进行限制,将簇内平均通信距离控制在合理范围内,尽可能的达到簇分布最优与降低簇首能量损耗。相比于其它3种算法,文中算法中无人机集群分簇网络的簇分布与簇首能量下降速度得到了明显的优化。

图4 簇内平均通信距离随节点传输距离的变化

图5表示在特定实验环境下,LID、WCA、IWCA以及ACC-WCA的节点存活数量随运行轮次变化的情况。仿真可以看出,在整个过程中,四种算法网络中出现第一个节点失效对应运行轮次分别大约在1 015轮、1 294轮、1 628轮、1 834轮;网络中节点失效比例为20%时,四种算法对应运行轮次分别在大约1 612轮、2 271轮、2 886轮、3 379轮;网络中节点失效比例为50%时,四种算法对应运行轮次分别在大约2 408轮、3 219轮、4 381轮、4 825轮。通过计算可得AAC-WCA分别在节点失效率为1%、20%、50%的情况下,节点平均运行轮数比WCA、LID、IWCA分别提高了约99.36%、47.97%和12.85%,可见AAC-WCA很大程度上均衡了节点能量损耗。同时,在约7 500轮其它3种算法的节点相继全部死亡,而 AAC-WCA的节点在约8 600轮才全部死亡。由此表明,文中所提的AAC-WCA的网络寿命最长。

图5 节点存活数量与运行轮次的关系

图6表示在特定实验环境下,LID、WCA、IWCA以及ACC-WCA的簇首累计接收数据包数量随运行轮次变化的情况。可以看出,随着运行轮次的增加,LID与WCA算法的簇首接收数据包数量增长更为平缓,分别在4 300轮与5 500轮左右停止增长,这表明此时网络中节点都已经失效,簇首接收数据包数量分别为0.4×105个,0.85×105个左右;运行至大约7 500轮时,IWCA网络簇首接收数据包数量不再增长,大约为1.6×105个;而文中的AAC-WCA网络簇首接收的数据包在8 600轮时大约为2.1×105个,通过计算可得较WCA,LID,IWCA簇首累计接收数据包数量分别提高了约425%,147%和31%;可见文中所提的AAC-WCA算法大大提高了无人机集群编队飞行时节点的通信质量。

图6 簇首累计接收数据包数量与运行轮次的关系

图7表示在特定实验环境下,LID,WCA,IWCA以及ACC-WCA的节点平均重入簇次数随运行轮次变化的情况。对比4种算法在未出现死亡节点时运行至1 000轮的情况,随着运行轮次的增加,节点平均重入簇次数逐渐增加。节点平均重入簇次数是评估网络分簇结构性能的重要指标,当无人机节点受到自身或外界因素影响时,部分节点会脱离原来的簇并重新加入其他簇,平均重入簇次数越少,表明分簇网络管理的效果更好。由图可见文中算法相比于其它3种算法的平均重入簇次数更少,分簇网络的稳定性更强,可以实现对网络的更优管理。

图7 节点平均重入簇次数与运行轮次的关系

综上所述,文中提出的AAC-WCA算法相较于其它3种算法对比,使无人机集群在编队飞行过程中的主要性能参数如网络分簇规模、簇内通信距离、网络整体寿命、节点通信质量以及分簇网络稳定性得到了明显的优化。

4 结 论

1) 文中针对无人机集群编队飞行过程中网络管理问题,提出了一种基于自适应ANP-CRITIC的无人机集群网络优化算法。引入节点负载失衡度指标来均衡成簇规模,增加安全阈值以及采用Z-Score法对指标数据进标准化,提高簇首选取客观性;根据不同的实际应用场景与任务种类,设计ANP-CRITIC自适应机制,通过ANP法预先求解因素指标主观权重,在编队飞行过程中根据CRITIC法求解客观权重;引入博弈论的思想,将实现纳什均衡作为协调主客观权重的优化目标,获得自适应综合簇首权值;根据簇首权值选取簇首。

2) 通过仿真验证,在特定的网络仿真环境中,文中所提AAC-WCA算法与LID、WCA、IWCA算法相比,控制了成簇规模与簇内平均通信距离,降低了网络通信过程中的能量损耗,延长了网络寿命的同时提升了网络的通信质量,从而实现对无人机集群网络的更优管理。