基于飞行冲突网络最优支配集的冲突调配策略

2023-03-18吴明功毕可心温祥西孙继昆

北京航空航天大学学报 2023年2期

吴明功，毕可心，温祥西，*，孙继昆

(1.空军工程大学空管领航学院，西安 710051；2.国家空管防相撞技术重点实验室，西安 710051；3.中国人民解放军93735 部队，天津 301799)

近年来，中国空中交通行业取得了空前的发展。到2019 年底，中国共建成航路、航线992 条，总里程数共计234509 km，超过3 条以上航路交汇的航路点个数有527 个[1]。与此同时，中国的空中交通系统变得越来越复杂，航空器在运行过程中面临的飞行冲突增多，空中交通管制压力巨大。采取有效的措施对航空器之间的飞行冲突进行调配，将能够缓解这一压力，保证空中交通运行的安全和顺畅性，并促进航空业的进一步发展。

飞行冲突的相关研究一般可分为2 种：一种是宏观上进行的冲突调配，另一种是针对具体问题的局部冲突解脱。宏观上的冲突调配关注空域整体的运行情况，该方法能够基于当前的空中态势，为管制员提供合理、可行的飞行冲突调配建议；而局部冲突解脱则面向具体冲突，对于既定类型的冲突事件，通过几何、概率、控制和博弈等理论分析，为航空器提供合理的机动意见[2-5]。本文主要研究宏观上的冲突调配。在这方面的研究中，Huang 等[6]提出了一种飞机流在航路交叉口的紧凑结构，以解决航空器流在交汇时的冲突问题，该方法能够保证更多的飞机安全通过固定区域，提高航路交汇处的空域容量；Hong 等[7]将冲突调配表述为航空器机动约束下的混合整数线性规划问题，采用2 层结构解决飞机之间的冲突，避免了飞机之间的冲突，并保证飞机顺利过渡到相邻空域；Valenzuela 和Rivas[8]提出了一种基于飞机意图参数化的冲突检测与解决方法，将冲突解决问题表述为有约束的参数优化问题，并据此进行调配；Cafieri 和Rey[9]采用混合整数非线性规划进行建模，以最大限度地解决冲突的数量或保证无冲突飞机数量最大为目标，通过检测两机之间的冲突进行调配，使冲突模型得以减小，同时提高了计算的效率。

航空器之间的冲突关系是复杂的、非线性的。近年来，学者们通过复杂网络理论分析和解决航空器之间的冲突问题。王红勇等[10]根据航空器之间的迫近效应确定航空器集合的内禀复杂性，并依此构建复杂网络模型；吴明功等[11]以航空器为网络节点、航空器之间的机载防相撞系统（airborne collision avoidance system,ACAS）通信为连边建立飞行状态网络，通过对网络的拓扑指标分析找到空域中关键的航空器节点，为管制员提供飞行冲突调配方案；汤俊等[12]将复杂网络用于无人机集群的冲突解脱，通过边缘权重确定关键无人机，并使其朝着能够使网络鲁棒性降低的方向实施避撞。以上方法在构建网络连边时只考虑了航空器的位置信息，不能准确反映航空器之间的冲突关系。速度障碍法能将航空器的速度、航向和保护区信息结合起来，通过几何方法，提前预知飞行冲突[13]。本文使用速度障碍法判断航空器之间的冲突关系，构建冲突网络。

冲突网络中，对航空器节点进行删除和调整，即对应实际中的飞行冲突调配，会对网络的结构和性能产生影响。通过对网络进行分析，找出调整后能快速降低空域复杂性的航空器，即关键节点，可以为管制员调配冲突提供宏观上的建议，将宏观上的冲突调配问题转化为冲突网络关键节点的识别问题。常用的复杂网络关键节点识别方法有度排序法、介数中心性或接近中心性排序法、K-shell 分解和PageRank 法等[14-16]，这些方法对识别网络中的关键节点有较高的准确性。但在进行飞行冲突调配时，单纯的节点识别方法可能会忽略紧迫的飞行冲突连边，进而影响飞行安全，因此需要同时对网络中的关键节点和连边进行识别。李佳威等[17]将最小连通支配集（m inimum connecteddominating set,MCDS）的概念用于复杂网络中，能同时识别网络中关键节点和连边，对研究网络抗毁性、构建骨干网络具有现实意义。但在实际的两机冲突中，管制员通常只需要调配其中一架航空器即可消解冲突，因此连通性在冲突调配问题中的意义是有限的。

综上，本文提出了一种基于复杂网络最优支配集(optimal dominatingset,ODS)的冲突调配方案，通过最优性能指标优化飞行冲突网络支配集的结构，为管制员进行飞行冲突调配提供合理的建议。

1 飞行冲突网络

飞行冲突网络是由航空器（节点）及航空器之间的冲突关系（连边）构成的复杂网络，表示为G=(V,E,W)。其中，V={v1,v2,···,vn}为网络中节点的集合，对应空域中的各个航空器；E={e1,e2,···,en}表示连边的集合，连边反映航空器之间的冲突关系；W={w1,w2,···,wn}为网络边权的集合，连边的权值在飞行冲突网络中反映潜在冲突的紧迫程度。

1.1 连边规则

飞行冲突网络的节点间构成连边，需要满足2 个条件：①节点对应的航空器在位置上比较临近；②通过速度障碍模型进行判定，满足速度障碍关系。如图1 所示，在进行初次判定时，划定航空器的位置探测区为圆柱形区域，半径为Dl，高为 2Dv。取Dl的值为ACAS 通信应答距离26 km，Dv的值为2 个高度层的高度600m。当有航空器进入该区域时，需进行第二次判定。

图1 位置探测区Fig.1 Position detection area

航空器在运行时要求相互保持一定的垂直间隔或水平间隔，针对空中目标建立椭球形飞行保护区（见图2），保护区的赤道半径a=b=dl，极半径c=dv。

图2 椭球形飞行保护区Fig.2 Ellipsoidal flight protection zone

设航空器B的坐标为 (XB,YB,ZB)，则保护区椭球面的表达式为

当航空器间的垂直间隔大于300m 时，不存在冲突，故取dl= 10km，dv=300m。

速度障碍法根据几何规则限定了目标在二维平面上潜在冲突的相对速度范围，当其相对于障碍物的速度处于该范围内时，判断其将会发生冲突。如图3 所示，目标A和障碍物B之间的间隔为|AB|，障碍物B在平面上的安全保护区是以B为圆心、dl为半径的圆。目标A的速度为v A，障碍物B的速度为v B，A相对B的速度为vr。过点A分别向 ⊙B两侧做切线，此时构成的区域称为速度障碍锥，当相对速度vr=v A−v B的方向在速度障碍锥内部时，认为A和B之间潜在冲突。

图3 速度障碍法Fig.3 Velocity obstacle method

由于航空器运行的空域是三维空间，将速度障碍法拓展到三维，且保护区为椭球形的一般情况。如图4 所示，相对速度vr=v A−v B可看作是航空器B处于静止时，航空器A相对于航空器B的速度。当vr方向在三维速度障碍锥的角度范围之内时，说明若按照当前的运动状态不加以调配，航空器A将进入航空器B的飞行保护区，发生飞行冲突。

图4 三维速度障碍模型Fig.4 3D velocity obstacle model

设航空器A的三维坐标为 (XA,YA,ZA)，vr的方向向量为 (vx,vy,v z)，则根据三维直线的点向式，有

联立式（1）和式（2），若方程组存在2 个解，则直线和曲面存在2个交点C1和C2，其坐标分别为(x1,y1,z1)和(x2,y2,z2)； γ表示vr与位置向量的夹角，当同时满足 γ＆lt;90◦，即 cos γ＆gt;0 时，vr的方向就在障碍锥内，2 个航空器之间潜在飞行冲突，判定节点对构成连边。

1.2 网络边权

采用预计冲突时间tc的负指数函数作为网络中节点间连边的权重。预计冲突时间tc定义为：如果航空器保持原有的飞行状态不变，预计将发生冲突的时间。用模型中的参数表示为

式中：wij为节点i和节点j之间连边的权重；|AC|为航空器节点A和点C之间的距离，表示为

其中：点C1和点C2为A在vr方向上直线lor与保护区椭球面的交点。

选取预计冲突时间tc的负指数函数作为权值有以下优点：①负指数函数在其定义域上为减函数，tc越长，权值越小，反映冲突强度较弱；②在构成连边时，tc的取值都大于0，故其负指数函数的值域为[0,1]，能够对权值起到单位化的作用；③负指数函数斜率的绝对值随着自变量的减小逐渐增大，能够反映出潜在飞行冲突的紧迫程度在tc减小的过程中变化激烈，这一特点与实际的冲突情况一致。

如图5 所示，有6 架航空器运行在三维的空域中，1 号和3 号航空器表示在上高度层内的航空器，其高度在图中表示为0.3 km，4 号和6 号航空器表示在下一高度层的航空器，2 号和5 号航空器表示处于高度层之间正在爬升或下降的航空器。从图5中得到，1 号和3 号航空器的潜在冲突数量为2 个，2 号、4 号、5 号和6 号航空器的潜在冲突数量为1 个。将航空器对在空域中的冲突关系抽象为网络，可得到其对应的飞行冲突网络。为便于表示和计算，用权值矩阵反映网络中节点和连边的关系，图5 网络所对应的权值矩阵为

图5 飞行冲突网络示意图Fig.5 Schematic of flight collision network

2 网络的最优支配集

2.1 支配集

支配集是图论中的概念，如图6（a）所示。设存在无向图G= (V,E)，其中，V表示网络中节点的集合，E表示连边的集合。在无向图G中，存在S⊆V，S≠∅，且对于 ∀x∈V−S，x都与S中的至少一个节点直接相连，此时，称S是图G的支配集。

若支配集S的任何一个真子集都不是G的支配集时，S为图G的极小支配集，如图6（b）所示。如果S为图G的支配集，且不存在其他任何支配集S′，使 |S′|＆lt;|S|，则称S是图G的最小支配集(minimum dom inant set,MDS)， |S|称为最小支配点数[18]。

图6 最小支配集示意图Fig.6 Schematic of minimum dominant set

要得到网络的MDS，实际上就是求使支配集S中的节点数目最小的节点集合，采用最优化思想，其目标函数为

该指标考虑了节点的数量，确保支配集规模最小；但其未考虑网络中连边的性质，无法反映飞行冲突的紧迫程度。定义ODS，根据现实意义确定在调配飞行冲突时具体的性能指标，拓展了MDS 的内涵。

2.2 最优支配集

假设S是网络G的支配集，ODS 是在支配集的基础上，引入最优性能指标函数J，当Sj使指标J达到最优时，有节点集合O=Sj为网络的ODS。

式中：Ci为S在网络中的第i个特征量；ki为Ci在指标中对应的权重。

对邻接矩阵B各列按位进行或运算，得到向量Q：

式中：Q为由元素0 和1 组成的n维行向量。

要使子集Zi为网络的支配集，需要满足：

式中：Zi为网络中的节点集合；Q(xi=0)为Q中0 元素位置对应节点的集合。只有Zi内的元素在Q中所对应的位置为0，其余位置均为1 时，S=Zi为网络的支配集。

因此，ODS 表示为

如图7 所示，节点v3和v5之间连边的权重为2，其余未标注的边权均为1。当性能指标考虑节点的点强时，ODS 中应包含点强更大的节点，则{v3,v5,v6} 构成网络的ODS。同时， {v4,v5,v6}是网络的MDS，但不是ODS。

图7 最优支配集Fig.7 Optimal domination set

取飞行冲突网络ODS 的最优性能指标为

式中：k1、k2、k3为权重系数；等号右侧第1 项中n表示支配集中节点的个数，节点个数越少，对于管制员的调配难度越小；第2 项中s代表支配集节点在网络中的平均点强，s越大，支配集对网络冲突的消解能力就越强；第3 项中e代表支配集的内连边数，由于工作压力，管制员在对两机冲突进行调配时，往往只对其中的单个航空器进行调配，e越小，重复的工作就越少，给管制员的工作负荷就越小。

ODS 包含了MDS 的性质和内容，对实际复杂网络更具有意义和应用价值。飞行冲突的调配中，ODS 表示冲突网络中一个可行的最优化关键航空器节点调配方案。

2.3 粒子群算法

采用粒子群（particle swa rm optimization，PSO）算法对ODS 进行优化求解，算法中，不同粒子在解空间中的位置表示了NP-hard 问题的一个可行解。假设冲突网络中存在n个节点，对应解空间的维度。粒子群个体的位置为向量空间中的点坐标，用x i表示，维度为n。由于求解ODS是对节点的选择关系，采用二进制编码表示x i，1 表示选择，0 表示不被选择。

搜索过程中，粒子的位置首先要满足支配限制，即粒子对应的节点集Z是网络的支配集。在此基础上迭代搜索，使适应度函数值更优。根据优化目标，将飞行冲突网络ODS 的最优性能指标作为PSO 算法的适应度函数：

根据向量xi可计算得到粒子在当前位置的适应度函数值，与该粒子历史最优的适应度进行比较，得到个体当前的最优位置pbest；待个体最优位置更新完成后，根据所有粒子的适应度值计算粒子种群当代整体的最优位置gbest。

粒子群的速度公式为

式中：v i,j为粒子速度；w为惯性权重；c1、c2为学习因子；rand()表示0～1 之间的随机数；x i为粒子当前位置；pi为粒子目前的个体最优位置；pg为当代种群全局的最优位置。

基于粒子的速度，其位置更新公式为

式中：s(v i,j)为速度分量的sigmoid 函数值，通过sigmoid 函数，可将速度在第j维上的分量v i,j映射在0～1 之间；r为随机变量且r∼U(0,1)，当r＆lt;s(v i,j)时，xi,j的值取1，否则取0。

设PSO 算法的种群数量为np，则每代算法的计算量为O(np)，当算法执行m代时，其时间复杂度为O(mnp)。

3 调配方案和步骤

使用基于飞行冲突网络ODS 的冲突调配策略调配冲突，存在以下合理性：①支配集节点与网络中其他的节点间都存在连接，说明支配集节点对应的航空器与其他的航空器之间均存在冲突，使其在调配飞行冲突时具有价值和现实意义。②ODS 在支配集的基础上，设置性能指标J，该指标不仅考虑了支配集中航空器节点的数量，还将节点的点强和冲突连边的数量也列入指标中，其在有限的管制资源下，相对于支配集更具有优势和现实意义，能够为管制员提供更加精准的调配意见。③在使用PSO 算法求解飞行冲突网络ODS 时，使用了二进制解空间，并引入免疫机制。二进制PSO 算法计算的复杂度远小于传统的PSO 算法；免疫机制能够优化粒子种群的初始位置，加快PSO 算法的收敛速度，保证了PSO 算法能更快、更准确地找出飞行冲突网络的ODS。

3.1 预处理

使用速度障碍法优化冲突网络的拓扑结构，构建飞行冲突网络模型，过滤了网络中的非冲突连边，因此易存在非连通图的情况，在寻找支配集时有必要对其进行预处理。方案首先对网络中的孤立节点进行处理。

根据支配集的定义，网络中的孤立节点将被识别为支配集，如图8（a）所示，在大多数的现实网络中，孤立的节点表示其与系统中的其他单元关系微弱或不存在联系，其作为支配集是不具备意义的；飞行冲突网络中，孤立节点表示其对应的航空器并不存在冲突，因此在搜索支配集之前，应先过滤掉这些孤立点，如图8（b）所示。

图8 过滤孤立节点Fig.8 Filtration of isolated nodes

实验证明，在算法运行前过滤网络的孤立节点能够降低解空间的维度，加快PSO 算法的收敛速度，同时提升算法求解质量。

3.2 免疫机制

免疫是指机体在受到抗原的刺激时会产生与之匹配的抗体，如果再次遭到同类抗原的入侵，抗体会与抗原发生特异性结合，产生免疫。PSO 算法的免疫机制便是模拟这一过程，在初始种群中注入抗原使其产生抗体，优化种群的初始位置，使算法在迭代搜索的过程中更易于收敛向适应度高的位置。实验证明，该机制能够提高PSO 算法的收敛速度和解算高维度数据的能力[19]。

在进行飞行冲突调配时，由于不安全因素会危及飞行和乘客的生命安全，管制员需优先对冲突严重的航空器和紧迫的飞行冲突实施调配。因此，在使用PSO 算法求解ODS 的过程中，也需要优先考虑关键航空器节点和高风险的飞行冲突连边。基于此，将免疫机制中的抗原分为如下2 类：

1）节点抗原。选取特定的指标（如度、点强、集聚系数或节点介数）进行排序，筛选出排名靠前的节点作为抗原；也可以对多项指标加权排序选取抗原。为了简化计算并突出免疫粒子群（immune particle swa rm optim ization，IPSO）算法的特点，选择点强为选取抗原时的指标。当节点的点强大于阈值st时，该节点作为抗原注入PSO 算法的初始种群中；如果网络中存在发生故障或不便于进行调整的航空器，也可以反向注入抗原，即在生成种群和搜索的过程中规避该节点。

2）连边抗原。网络中存在冲突紧迫，但造成该冲突的航空器均不属于节点抗原的情况，如果不进行合理的调配，会引发不安全因素。设定连边的权重阈值为wt，如果飞行冲突网络中连边的权重大于wt，且其两端的节点未被选为抗原，则将其中点强较高的节点作为抗原，注入初始种群，表示该连边对应的飞行冲突超过了预设的安全限度，需要重点关注并实施调配。

3.3 实施步骤

IPSO 算法的执行步骤如下（见图9）：

图9 冲突调配步骤Fig.9 Conflict resolution process

步骤 1收集空域中航空器的航向、位置和速度等信息，构建飞行冲突网络G(V,E,W)。

步骤 2读取网络的权值矩阵W，进行数据预处理，过滤飞行冲突网络中的孤立节点。

步骤 3初始化参数：粒子种群个体数N，解空间的维度D，最大迭代次数T，学习因子c1和c2，惯性权重g等。

步骤 4进行免疫操作，将点强高于阈值st的节点和权重高于阈值wt的连边作为抗原，注入初始种群，使种群中产生抗体，优化其初始位置。

步骤 5初始化粒子的位置x i和速度v i,j，根据适应度函数（13）计算其适应度值，获得粒子初始的个体最优值pbest和粒子群全局最优值gbest。

步骤 6分别利用速度公式（15）和位置公式（16）更新粒子的速度v和位置x，计算适应度值，更新粒子个体最优pbest和粒子群全局最优gbest。

步骤 7执行算法，直至满足终止条件，输出粒子最优位置，即对应飞行冲突网络的ODS。

4 实验与仿真

通过仿真实验验证模型和调配策略的合理性和有效性。图10 为15:00 时刻昆明长水国际机场附近空域的雷达情况。获取此刻处于高空扇区航空器的位置、速度等信息，并在MATLAB 的仿真场景中模拟管制员对空域进行管制的情景，生成40个与之相对应的节点。

图10 昆明长水国际机场空域雷达图像Fig.10 Airspace radar image of Kunming Changshui International Airport

4.1 网络性能分析

首先分析飞行冲突网络模型节点的性质。按照航空器之间的速度障碍关系构建连边，计算航空器对的预计冲突时间tc并确定边权，得到飞行冲突网络模型。

图11（a）为通过位置关系构造出的飞行状态网络，图11（b）为在同一仿真场景下，经过速度障碍优化后的飞行冲突网络。能够直观地看出，在相同的探测距离下，飞行冲突网络的连边数量明显减少，复杂度更低。

图11 网络对比Fig.11 Network comparison

节点度值反映了航空器潜在冲突的数量，一定程度上决定了网络的结构和性能。表1 和图12 对比了2 种网络中各个航空器对应的节点度值。可知：①飞行状态网络不存在孤立节点，即所有航空器都需要管制员进行关注，管制资源分配不够合理，管制压力较大；飞行冲突网络中，4,7,9,15,17,20 号节点为孤立节点，管制员可将精力适当分配至其他航空器节点，一定程度上减缓了管制员的负荷。②飞行状态网络中，度值最高的5 个节点为23,13,25,29,9 号节点，13,25,29 号节点在飞行冲突网络中仍属于高度值节点，但经过速度障碍模型判定后，飞行状态网络中度值最高的23 号节点的潜在冲突数量只有2 个，9 号节点甚至为孤立节点，不存在冲突，与直观地通过临近关系得出的判断存在偏差。

图12 两种网络节点度值的比较Fig.12 Node degree comparison of two networks

表1 两种网络中节点的度值Table 1 Node degrees in two networks

相较于飞行状态网络，飞行冲突网络中平均每个节点的虚警数量减少了2.15 个；飞行冲突网络的网络连边数为43 条，相较于飞行状态网络的129 条，虚警率降低了66.7%。因此，飞行冲突网络在拓扑结构上更加简单，其能过滤网络中的冗余信息，航空器间冲突关系更加明确，提升网络的信息价值，为管制工作提供更加精确的数据。

4.2 调配方案

4.2.1 IPSO 算法求解ODS

分别采用IPSO 算法和传统PSO 算法对飞行冲突网络的ODS 进行求解，如图13 所示。

从图13 中可以看出，IPSO 算法的初始适应度值优于传统PSO 算法，证明粒子的初始位置更优；IPSO 算法收敛于第80 代，PSO 算法收敛于第187 代，IPSO 算法的收敛速度比PSO 算法更快；从适应度函数值来看，收敛时，IPSO 算法的适应度函数值更低，故IPSO 算法解出的ODS 相对更优。

图13 两种算法的对比Fig.13 Comparison of two algorithms

通过实验，IPSO 算法多在100 代以内收敛，执行时间约为1.2 s。如图14（a）所示，IPSO 算法识别出飞行冲突网络的ODS 为：v8,v10,v13,v16,v19,v24,v25,v26,v30,v34,v36,v38,v40。

图14 从网络中移除最优支配集Fig.14 Removal of ODS from network

移除ODS 的网络如图14（b）所示。可以看到，网络被分解成了简单的子图，潜在的冲突数量明显减少，网络复杂性下降。

4.2.2 评价指标

设计评价指标对网络在移除节点后的性能进行评价。对于飞行冲突而言，在设计指标时需考虑到网络的复杂性、鲁棒性和连通程度，同时还要考虑实际实现解脱的航空器数量。使用层次分析法（analytic hierarchy process，AHP）对网络鲁棒性、冲突节点数、最大连通子图和网络效率4 项指标构造判断矩阵并进行计算，其权重向量为：[0.5222,0.1998,0.1998,0.078 1]。

式中：R表示网络的鲁棒性；NN 为网络中存在冲突的节点数；GC 为网络的最大连通子图尺寸；NE为网络效率。分析中，一致性指标CI=0.014 5，CR=CI/RI=0.016 1，通过一致性检验。

1）鲁棒性。鲁棒性反映了系统在受到攻击后保持原状态不变的能力，将飞行冲突网络的鲁棒性定义为

式中：I为网络中被剔除的节点数量；wij为权值矩阵第i行j列的元素。

飞行冲突网络中，网络鲁棒性下降表示网络完整性遭到破坏，正在瓦解。航空器节点被调配移除后，网络的鲁棒性下降越多，说明该调配对冲突网络具有毁伤作用更大。因此，调配时尽可能地降低鲁棒性对冲突的消解。在4 项指标中，网络鲁棒性相对最重要。

2）冲突节点数。衡量空域中整体运行情况的一个重要指标就是空域中无冲突运行的航空器数量，由于该值与删除的节点数成正相关关系，采用网络的冲突节点数作为指标。

式中：qi为向量Q的第i个分量。

冲突节点数反映了飞行冲突网络中仍存在冲突的节点数目，对网络的复杂性和管制员的负荷程度影响较大，属于次重要指标。

3）最大连通子图。连通子图是网络中相互可到达的节点及其连边所构成的集合，各节点间至少存在一条路径相连。子图中节点数目最多的就是网络的最大连通子图，其度量为

式中： |S1|为最大连通子图的大小。

最大连通子图中的节点越多，网络的连通性相对就越好。在飞行冲突网络中，连通子图越大，说明网络的冲突集团规模越大，给管制员造成的压力也会越大，其重要性与冲突节点数相当。

4）网络效率。网络效率是衡量网络中信息交互能力的一项指标，节点间的效率值与信息交换所需的传递消耗是负相关关系。相似权网络中，网络连边的权值越大，其连接的节点联系越紧密。网络效率的定义为

式中：dij为无权网络中节点vi与节点vj之间测地线的长度；pij为最短路径上所有连边的权值之和。

网络效率在一定程度上反映了网络的复杂性，其值越高，网络节点间整体的联系就越紧密，网络也相对更复杂。相较于前3 项指标，该指标的重要性相对较低。

4.2.3 ODS 的调配顺序

实验证明，移除网络的ODS 节点能够快速地消解网络冲突，降低其复杂性。与此同时，若对网络ODS 采取不同的移除顺序，其性能下降的速度也是存在差异的，如图15 所示。

图15 ODS移除顺序对网络性能下降速度的影响Fig.15 Effect of ODS removal order on network performance degradation rate

图15 中分别按照度值顺序、随机顺序、点强顺序和PageRank 顺序对飞行冲突网络ODS 中的节点进行删除。经过比较，按照节点的度值顺序对ODS进行调配，效果要好于基于PageRank 值和点强的删除，随机删除效果最差。这是因为在ODS 中，节点度值越高，说明该航空器节点便与更多的航空器存在冲突，对其进行调配会使大量的冲突边失效，从而同时降低网络的冲突个数和鲁棒性，使冲突网络更快消解。

最优的航空器节点调配顺序为：13→40→34→38→25→36→10→26→16→24→19→8→30。该次序按照飞行冲突网络ODS 节点的度值由大到小进行调配，当度值相同时，则根据点强排序。这一特点与实际管制员的调配习惯是相符的，即在确定飞行冲突网络的ODS 节点后，管制员只需在这些节点对应的航空器中进行符合管制习惯的操作即可。按照以冲突个数为主、冲突强度为辅的顺序进行调配，便能实现优异的调配效果。

4.3 方法比较

引入其他4 种网络节点删除方法，按照其规则对飞行冲突进行调配，并将调配过程中网络性能的变化情况同基于飞行冲突网络ODS 的冲突调配策略进行比较：①第1 种方法采用在飞行冲突网络全局对节点进行随机删除的调配方式；②第2 种方法根据二次雷达的冲突告警数量对航空器进行调配，即在ACAS 距离范围内按照邻居航空器数量的多少进行调配；③第3 种方法按照飞行冲突网络全部节点的点强由大到小顺序进行调配；④第4 种为PageRank 法，将算法的迭代次数设置为100 代，阻尼因子为0.85，计算所有节点的PageRank 值，按照PageRank 值从大到小的顺序删除节点。

对比基于飞行冲突网络ODS 的冲突调配策略与上述4 种方法在网络鲁棒性、冲突节点数、最大连通子图、网络效率和网络综合性能指标的变化情况（在综合各项指标前对其进行归一化处理），结果如图16 所示。图中：最优支配集表示基于飞行冲突网络ODS 的冲突调配策略，全局随机表示网络整体上的随机删除，邻居数量表示根据航空器的邻居数量进行调配，全局点强表示在网络全局基于点强的冲突调配，PageRank 表示所有节点使用PageRank法进行排序的调配。

图16 不同删除方法对网络性能的影响Fig.16 Impact of different deletion methods on network performance

从实验结果中可以得出，基于飞行冲突网络ODS的冲突调配策略能够使网络的单项指标和综合性能指标下降更快，相应的冲突消解速度也更快。由于考虑了更多冲突产生和消解的因素，ODS 方法的调配效果最好，PageRank 法和全局点强次之；而由于随机删除和基于邻居数量的删除考虑的信息量较少，调配效果一般。

同时注意到，在进行网络整体上的随机删除时，网络指标出现了上升情况，这是由于随机删除网络中孤立或与其他节点联系较弱的节点，会有助于网络鲁棒性和网络效率的提升，也说明了如果冲突调配不当，可能致使网络整体的冲突情况更加严重。从图16 中也能看出，进行基于邻居数量的调配时，仅通过雷达告警和个人经验判断，管制员对飞行冲突进行调配的效果是十分有限的，并且随着同一时刻待调配的航空器数量的增多，解脱效果逐渐减弱；在基于点强的调配策略中，其性能折线与ODS 方法在前期有所重合，体现了免疫机制的作用，但该方案随着调配节点数量的增加，调配效果也有所减弱，一定程度上是由飞行冲突网络的无标度特性造成的；当删除一定数量的节点集团后，PageRank 法的调配效果与ODS 方法相当，但在整个调配的过程中，ODS 方法更优，如图16（e）中，当删除的节点数达到3 个和9 个时，PageRank 法的调配效果接近ODS 方法。因此，在调配数量或管制能力有限时，ODS 方法优势相对明显。