无人机集群网络节点重要性的多属性决策

左嘉娴，华 翔

(1.西安工业大学 兵器科学与技术学院，西安 710021；2.西安工业大学 电子信息工程学院，西安 710021)

无人机集群网络是一种特殊的复杂网络，网络中5%～10%的节点死亡失效时，会引起整个网络的瘫痪[1]，尤其是网络重要节点失效会引起整个网络的级联失效，因此对无人机集群网络各节点的重要性进行评估有着现实意义[2]。目前国内外对于无人机集群网络节点重要性评估的研究还处于起步阶段。目前，诸多学者针对复杂网络中各个节点的重要性评估的研究已经有了初步进展。但是大多采取单一属性指标，单个节点重要度指标在网络中进行节点重要度评估时存在很大局限性，会忽略节点间的相关作用等因素，不够全面，或者即使采取了多指标评判也没有深入考虑网络全局。文献[3]基于邻接矩阵定义了节点重要度贡献矩阵，将所有节点对邻节点的重要度贡献比例值用矩阵的形式表现出来，结果表明，此算法更适用于大型网络的关键节点识别；文献[4]考虑到在不同拓扑结构下邻居节点对节点的影响程度不同，提出了主要考虑节点邻居数量和与邻居节点亲密程度的节点重要性评估KI算法，结果表明，KI算法具有高准确性，但是需要较多的网络拓扑信息；文献[5]考虑到节点重要度与最优路径长度，最优路径数目及信息传播率密切相关，提出将重要度传输矩阵作为节点重要性评估的重要依据；文献[6]提出将节点冗余度作为唯一的评价指标来评价网络中各节点的重要性；文献[7]依据网络中节点与其一跳邻节点与两跳邻节点范围内的关系提出了邻接信息熵的概念，并将信息熵作为节点重要性评估的主要判据。基于以上考虑，文中提出了基于复杂网络理论的无人机集群网络节点重要性评估算法。

1 理论基础

无人机集群网络具有复杂的网络拓扑结构，无人节点间通过自组织的方式进行通信连接[8]。首先对无人机集群网络进行建模，一般表示为G(V,E)，其中G(·)为无向无权图，V={v1,v2,v3,…,vn}为网络节点集合，vi(i=1,2,…,n)为网络中的单个节点，E={e1,e2,e3,…,em}为节点间的连边，ei(i=1,2,…,m)为节点间相互通信的无线链路，n为节点个数，m为链路条数。对于无人机集群网络，节点的重要性指标包括度中心性、介数中心性、归一化紧密度、节点相对重要性。

设复杂网络中有n个节点，则节点vi的度中心性为

(1)

其中ki为节点vi的节点度。

网络中不相邻的节点vi和vj之间的最短路径会途经某些节点，某个节点vi被其他最短路径经过，则表示该节点在网络中很重要，其重要性或影响力可用节点的介数来表征。节点vi的介数中心性为

CB(vi)=2Bi/[(n-1)(n-2)]，

(2)

其中Bi为节点介数。

节点vi的归一化紧密度为

(3)

其中dij为节点vi到节点vj的距离。

节点vi的相对重要性为

(4)

其中μm(vi)为以节点为起点经m个连边回到节点vi的回路数目。

2 节点重要性综合评估

选取度中心性、介数中心性、归一化紧密度、节点相对重要性等指标进行综合评估。采用变异系数法为各个属性指标赋权。通过指标变异系数计算，忽略指标量纲的影响，可得各项指标的差异程度。具体的算法流程如下：

① 节点属性矩阵构造

设无人机集群网络中有n个待评价的无人机节点，对应的重要节点方案集为{A1,A2,…,An}，有k个节点重要性评估指标，即方案属性有k种，文中k=4，构造初始决策矩阵P，即

(5)

式中：Ai(fr)(i=1,2,…,n;r=1,2,3,4)为节点方案；fr(r=1,2,3,4)为方案属性。

② 加权规范化矩阵构造

采用变异系数法确定各个属性指标的归一化权重向量wT=[w1,w2,w3,w4]，各项指标的权重wi(i=1,2,3,4)为

(6)

其中Vi为第i项指标的变异系数，且

(7)

③ 综合评价指标计算

根据初始化决策矩阵以及选取的度中心性、介数中心性、归一化紧密度、节点相对重要性等指标的权重，进行综合评价指标计算，即

(8)

式中：M为决策系数矩阵；pij(i=1,2,…,n;j=1,2,3,4)为初始决策矩阵元素。

3 实验分析

近年来，国内外多采用ARPA网进行网络节点重要性分析[9]，为此文中采用ARPA网来验证所提算法的有效性。ARPA网由21个节点和23条连边构成[10]，其拓扑结构如图1所示[11]。其中vi(i=1，2，3,…,21)为网络节点。

图1 ARPA网络拓扑结构

将文中所提多属性决策(Multiple Attribute Decision Making，MADM)算法与其他算法运用在ARPA网络拓扑上[12]，ARPA网节点重要性计算结果见表1。

表1 ARPA网各节点重要性

根据节点重要性计算结果，得到ARPA网前5个重要节点，见表2。

表2 ARPA网前5个重要节点

由表2可见，不同算法得到的ARPA网前5个重要节点不一致。定义前5个重要节点为vc,i(i=1,2,3,4,5)，按重要性对其进行排序，排序结果依次为vc,1,vc,2,vc,3,vc,4,vc,5。为分析重要节点失效对网络性能的影响，需对重要节点进行删除，以得出子图数与子图最大规模。重要节点有以下几种删除方式：① 删除vc，1，记为方式1；② 删除vc，1，vc，2，记为方式2；③ 删除vc，1，vc，2，vc,3，记为方式3；④ 删除vc，1，vc，2，vc,3，vc,4，记为方式4；⑤ 删除vc，1，vc，2，vc,3，vc,4，vc,5，记为方式5。不删除任何重要节点，记为方式0。

为比较不同算法在网络重要节点识别上的性能差异，按以上几种方式对重要节点进行删除，生成的子图数与子图最大规模如图2所示。其中，子图数表示网络重要节点失效对网络连通性的破坏情况，子图最大规模表示网络重要节点失效对网络的分割情况。

从图2可以看出，删除前5个重要节点后，MADM算法对应的子图数较其他算法大，对应的子图最大规模较其他算法小。相较于其他方法，MADM算法计算得到的重要节点的失效对网络连通性的破坏程度较大，对网络的分割更为均匀。

图2 子图数与子图最大规模

4 结 论

从局部网络、全局网络、节点相对重要性三个角度出发选取节点重要性评价指标，采用变异系数法确定各项指标权重，在ARPA网络上对节点进行定量的重要性排序。相较于信息熵算法、重要度评价矩阵算法、贡献矩阵算法，MADM算法所选出的重要节点的失效对网络连通性的破坏程度较大，对网络的分割更为均匀，实现了对无人机集群网络节点重要性的评估。有向有权网络节点重要性评估、网络中不同指标间的关联性有待进一步研究。