基于复杂网络理论的关键飞行冲突点识别
吴明功1, 王泽坤2, 甘旭升1, 杨国洲1, 温祥西1     
1. 空军工程大学 空管领航学院, 陕西 西安 710051;
2. 中国人民解放军32211部队, 陕西 榆林 719006
摘要: 随着航空事业的发展,终端区内空中交通密度大,交通态势相对复杂,给管制人员带来巨大的挑战。为充分理解空中飞行态势,给管制人员提供决策依据,提出了一种基于复杂网络理论和层次分析-熵权法的关键冲突飞机识别方法。首先以飞机为节点,机载防相撞系统(airborne collision avoidance system,ACAS)建立通信关系为连边构建飞行状态网络;在此基础上,选取节点度、点强、加权聚类系数和介数4个参数作为评估节点重要度指标,利用层次分析法确定各指标权重,并引入熵权法的思想,对结果进行修正,通过多属性决策的方法计算出节点重要度,确定关键冲突飞机。在人造网络和昆明长水机场终端区内的飞行状态网络上的仿真和实验结果:提出的方法能够确识别飞行状态网络中的关键冲突点,对选出的节点进行调配能够有效降低飞行状态网络的复杂性,可以为空中交通管制服务提供参考,降低管制人员的调配难度。
关键词: 复杂网络    飞行状态网络    关键节点    多属性决策    

近几年,民航运输行业高速发展,空中交通流量不断增加,空域环境日趋复杂,给管制人员带来巨大的调配压力。准确分析当前空中飞行态势,为管制员提供辅助决策,能够有效降低管制难度。这也成为当前空中交通态势建模与评估的热点问题。为了解决这一问题,分别利用管制员工作负荷、聚类算法、内禀属性等方法,以及图形建模分析软件(GMAS)[1]等工具来描绘空中交通态势,理解与掌握空中交通基本规律。

然而传统的分析方法偏重于挖掘空中交通的微观属性,缺乏对空中交通网络的宏观调控。随着复杂性科学的快速发展,复杂网络理论在各个领域都得到了广泛应用,利用复杂网络理论对空中交通的研究也成为空管领域关注的热点。复杂网络理论不仅可以描述空中交通的微观信息,也能够很好地体现其中的宏观特点。张进等对国外关于空中交通复杂度的方法以及理论成果进行了详细的分析,并指出各自的优缺点和以后需要解决的问题,为国内的空中交通复杂度研究奠定了基础[2]。之后,王红勇等逐渐将复杂网络理论应用于对空中交通复杂性[3-4]、空中交通流复杂性[5]的研究。这些研究主要关注对空域总体态势的评估,对飞机个体行为与空域态势间影响关系的研究比较少。本文以飞机为节点,飞机之间能够建立通信联系为连边,构建飞行状态网络,分析空中个体对整个网络的影响。

在对复杂网络研究中,人们发现少数的节点扮演着“关键节点”的作用[6],它们对网络性能发挥着不可替代的重要作用,往往能决定网络的结构和功能。例如,通过对关键节点进行完善,可以提高电网[7]、物联网等的抗毁性[8]。也可以通过故意攻击这些节点来摧毁某些网络,防止疾病传播等[9]。同样的,在飞行状态网络中,少数飞机的调整,将对当前飞行态势结构造成非常大的影响。调配这些关键节点飞机将快速缓解空中交通拥挤状况,降低空中交通复杂度。如何找出这些关键节点飞机是本文要解决的核心问题。

在复杂网络关键节点识别的研究中,目前主要的方法是根据某种评估指标对网络的节点进行排序,例如节点度[10]、接近中心性[11]、点强[12]等。但如果只使用某一种指标就显得较为单一,忽略了网络的整体特性,评价结果不够准确。为使得评价结果更加客观准确,现在学者通常采用多指标对关键节点进行识别。Wen选取网络效率、最大连通子图、网络信息量3类指标,采用“不放回”的方法[13]对航空网络关键节点进行识别,在此基础上又提出基于最小二乘支持向量机(LS-SVM)的快速识别方法[14]。Ren基于信息熵理论,结合节点的度中心性、介数中心性、接近中心性等特性对航路中影响较大的航路点进行识别[15]

以上方法从不同角度提取节点重要度评价指标,本文在现有研究基础上,基于复杂网络理论,针对飞行状态网络特征,参考现有的节点重要度评价方法,综合考虑节点的各项性能指标,利用AHP-熵权法确定指标权重,并通过多属性决策的方法确定节点重要度,对飞行状态网络节点重要度进行排序,从中找出对网络结构影响较大的关键冲突点,为空中交通管理提供战术层面上的对策建议。

1 关键节点识别方法 1.1 基于AHP的指标处理

飞行状态网络关键冲突节点识别层次结构由方案层(节点)→准则层(网络拓扑指标)→目标层(关键冲突节点)构成,如图 1所示。

图 1 飞行状态网络关键冲突节点识别层次结构

根据所选定的网络拓扑指标相对于飞行状态网络关键冲突节点的贡献程度, 本文按照九分制的取值方法构造判断矩阵, 取值越大, 重要程度越高, cij表示指标ij相比较其重要程度。

当判断矩阵通过一致性检验后, 则可计算得到各指标的权重:

(1)

x为判断矩阵的特征向量矩阵, d为最大特征值所在列, 而Wj为指标j对应的权重。

1.2 熵权法对权重修正

为克服AHP方法的主观性以及指标识别能力不足等缺陷[16], 引入熵权法对结果进行修正。熵值法是根据各项指标指标值的变异程度来确定指标权数的[17], 这是一种客观赋权法, 避免了人为因素带来的偏差。因此用熵权法对AHP计算结果作以修正, 尽量使得评价结果客观准确, 算法步骤如下:

① 建立原始指标数据矩阵

设飞行状态网络中飞机数量即节点个数为n, 节点的集合为N, N=(N1, N2, …, Nn)。评价指标的集合为S, S={S1, S2, …, Sm}, 它们共同构成的初始决策矩阵为G=(gij)n×m

(2)

式中,gij为第i个节点第j个指标的数值。

② 标准化原始指标数据矩阵

由于各数据数量级的差异, 对各指标进行min-max标准化:

(3)
(4)

通过(3)~(4)式标准化原始指标数据矩阵中各元素, 得决策矩阵C=(cij)n×m

③ 计算指标信息熵e

(5)

式中,

④ 计算差异系数q(信息效用值)

(6)

利用熵值法, 由(6)式可以计算第j(j=1, 2, …m)个评价指标的差异系数qj。差异系数越大, 表明该指标越重要, 对评价结果的影响越大。

⑤ 修正AHP评价指标权重, 并进行归一化处理后, 得到最终指标权重

(7)
(8)
1.3 基于多属性决策的节点综合评价

对于网络综合性能的变化, 本文采用多属性决策评价方法进行评估。由于研究对象是删除不同节点对网络的影响, 所以将每一个节点看作一个方案, 那么评价节点性能的多个评价指标可以看做是各方案的属性, 于是对节点性能的评价就可以转变为一个多属性决策问题, 评价各方案的综合性能就是决策准则。

由于初始决策决策矩阵G中各指标的量纲有差别, 为方便比较, 使用由(4)式得到的标准化决策矩阵:C=(cij)n×m

由(8)式可知, 第j个指标的权重为Hj(j=1, 2, …m), 其中, ∑Hj=1, 与规范化决策矩阵C构成加权规范化矩阵

(9)

基于TOPSIS方法[18], 根据矩阵Y确定正理想节点vmax, 正理想节点是各可行方案中各指标值最大者, 即删除节点后综合性能值减少最小的节点

(10)

计算每个节点vi到正理想节点vmax的距离

(11)

距离Di越大, 节点vi到正理想节点vmax的距离越大, 也就说明删除节点vi后的网络综合性能变化越大, 即节点越重要。

1.4 算法步骤

本文提出的一种飞行状态网络建模方法对关键冲突节点飞机进行快速识别, 方法步骤如图 2所示。

图 2 算法流程图

基于复杂网络分析的关键飞机节点识别方法中, 通过AHP分析初步确定各指标权重, 熵权法修正后得到最终结果, 识别出关键节点后, 通过网络鲁棒性与网络效率分析验证提出方法的有效性。主要有以下5个步骤:

Step 1  构造飞行状态加权网络。以飞机为节点, ACAS通信范围内飞机形成连边, 飞机间距离的倒数为边权。

Step 2  计算拓扑指标。选择复杂网络中静态拓扑指标反映节点重要度, 并作标准化处理。

Step 3  确定指标权重。基于AHP方法, 初步分析确定各个指标的权重, 并利用熵权法进行修正。

Step 4  确定关键冲突点。基于TOPSIS多属性决策方法确定飞行状态网络关键冲突节点。

Step 5  结果分析。分别计算节点删除后的网络鲁棒性和网络效率变化, 与单独使用AHP方法或熵权法作比较, 分析方法改进后的效果。

2 飞行状态网络建模

复杂网络理论中, 网络指的是节点与连接节点的边的集合, 节点集合V={1, 2, 3, …n}, 连边E={eij≠0, iV, jV}, 对于集合V中的任意节点ij, 存在连边时有eij=1, 反之, eij=0。节点V和连边E共同组成了网络集合G=(V, E)。如图 3a)所示, 在飞行状态网络中, 飞机被视为节点V={vi}, ACAS通信范围内(ACAS询问其他装备应答机飞机的范围为26 km)的飞机间存在连边E={eij}, 以距离的倒数为边权W={wi}。

图 3 飞行状态网络模型

网络中各节点之间的关系可以利用邻接矩阵A=(aij)n×n表示, 该矩阵对角线为0, 当飞机ij之间有连边时, aij=1, 否则aij=0。如图 3b)所示, 该网络的邻接矩阵可以表示为

(12)
3 飞行状态网络拓扑指标选取

根据现有的复杂网络关键节点识别方法以及飞行状态网络基本特征, 本文选取节点度分布、点强、加权聚类系数、节点介数这4类评价指标对飞行状态网络进行判别分析。以上指标基本反映了静态网络节点重要度的全部信息, 能够对飞行状态网络关键冲突节点作出客观评价。

1) 节点度(degree distribution, DD)

定义1  节点vi的度是指与之建立连边的节点个数。

(13)

节点度反映了与该飞机建立通信联系的飞机架次, 节点的度越大, 其在网络中的越重要, 周围的飞行环境也越复杂。

2) 点强(node weight, NW)

定义2  边权(edge weight)取决于航空器ij之间距离l

(14)

定义3  加权的节点度之和即是节点点强si

(15)

点强反映了飞机与周围飞机之间的距离信息, 点强越大, 说明距离越近, 越容易发生飞行冲突事件。

3) 加权聚类系数(clustering coefficient, CC)

定义4  节点的邻居节点间实际连边数与理论上最多连边数的比值为节点聚类系数

(16)

式中, vj, vk表示节点vi的2个相邻节点。

4) 节点介数(node betweeness, NB)

定义5  网络中所有最短路径中, 经过节点k的最短路径数占所有最短路径的比值为节点介数Bk

(17)

式中, σij(k)是节点vi与节点vj间经由节点vk的最短路径数目, σij为节点vi与节点vj间最短路径的数目。Bk的值越大说明节点vk在系统中的影响力和重要性越大。

各指标从不同角度反映了节点的重要程度, 由于CC与NB反映了节点在网络中的重要性以及地位, 其重要程度优于DD和NW, 而DD和NW反映信息较少且比较直观, 其重要度大致相同, 与CC相比, NB反映了节点对于网络结构的重要性, 更倾向体现网络的全局信息。综上, 各指标的重要性排序如下:

(18)
4 仿真验证 4.1 仿真分析

为了验证方法的有效性, 运用软件生成模拟飞行状态网络, 如图 4所示, 其中, 网络包含24个节点, 对其进行测试。

图 4 飞行状态网络

首先, 根据各指标的重要程度构造判断矩阵

(19)

由第2节中的方法可以计算得到权重向量H=(0.019, 0.0275, 0.145, 0.808), 以及各节点的重要度值, 图 5给出该模拟飞行状态网络中重要度排序靠前的5个节点删除后的网络结构图。

图 5 关键节点删除后网络结构

对比图 4图 5, 当对关键冲突节点飞机实施引导后(为简化分析过程, 本文对关键节点进行删除), 空中交通由一个相对复杂的网络几乎演化为2个独立的子网络, 仅有2对飞机之间的联系使得网络没有彻底分开。

4.2 结果分析

1) 网络鲁棒性是删除任意节点后网络中仍可连通的节点对数与网络中总节点对数之比的均值, 假设移除某个节点后, 网络中剩下的节点集合是Gk, 网络鲁棒性Rn计算公式为

(20)

式中,n表示剩余节点数量。

2) 网络效率是全部节点之间的距离倒数和的平均值

(21)

式中, N是网络中节点总数, dij为节点vivj间的测地线距离。网络效率可以反映网络复杂, LNE越大, 飞行状态网络越复杂, 潜在飞行冲突越多。

为了验证提出的关键冲突节点识别方法的有效性, 对不同方法对原网络删除节点过程中的网络鲁棒性和网络效率变化记录如图 6图 7所示。

图 6 鲁棒性分析
图 7 网络效率分析

从仿真结果可以看出, 在节点删除的整个过程中, 本文方法得到的曲线基本上位于最下方, 即网络性能的下降速度最快。因此, 该方法能够对飞行状态网络的关键节点进行有效和准确识别。

5 实例验证

图 8所示, 利用雷达数据对飞行状态网络建模基本上可以还原当前的飞行态势。本文以昆明长水机场终端区雷达数据为样本, 随机选取一个时间段的雷达数据, 每隔5分钟对飞行状态网络进行建模分析, 如图 9所示。

图 8 雷达管制实时场景
图 9 关键冲突飞机识别

图中五角星为利用本文方法得到的关键冲突飞机。各场景中的关键节点均分布在网络的中心位置, 邻居节点多, 影响网络性能的能力强。图 9a)中, 甚至出现5个节点均分布在中心位置的情况。另外少部分节点虽然不在最靠近中心的位置, 但有一个共同的特点:相邻飞机较多, 且与相邻的飞机间隔较小, 即连边的边权很大, 这些节点的特性被网络拓扑指标很好地捕捉到, 反映了本文关键冲突节点识别方法对于网络宏观尺度和个体微观尺度的考量比较全面, 验证了这一方法的有效性。

图 10给出以上6个场景中排序前5的关键冲突飞机调配后的网络结构图, 相较图 9网络结构的复杂度明显降低。其中场景2、3的网络甚至已经被分割为2个子网络, 这将极大地减轻管制员的监视以及调配压力, 利于冲突调配的进一步实施。

图 10 各场景中关键冲突飞机调配后网络结构

为进一步说明本文方法的有效性以及准确性, 使用不同方法对图 9中的飞行状态网络进行关键冲突点识别, 调配重要度排序前10的飞机后, 得到结果如表 1所示。对比各方法调配结果, 可以看出本文方法得到的关键冲突节点调配后的网络性能相较于另外2种方法下降更大, 具有一定的优势。

表 1 不同方法调配结果
场景123456
鲁棒性效率鲁棒性效率鲁棒性效率鲁棒性效率鲁棒性效率鲁棒性效率
接近度0.1680.3890.1370.2820.1220.2440.1830.3810.1750.3430.1980.389
度中心性0.1600.3430.1370.2820.1220.2440.1910.3890.1830.3580.1910.373
熵权法修正0.1600.3430.1300.2740.1220.2440.1750.3730.1600.3350.1680.358

图 11为17 min30 s(图 9d))的关键冲突飞机识别结果, 各关键节点的指标得分如表 2所示, 从表中可以得到这5架关键冲突飞机的各评价指标得分情况, 各飞机节点度都超过10, 而且加权聚类系数最小的为0.66, 最大的甚至达到了0.93。可见这5架飞机周围飞行环境非常复杂, 关键冲突飞机周围飞机数量较多, 且距离很近, 如果不注意对这几架飞机进行重点监视和调配, 很容易造成与周围其他飞机之间的冲突。从表中可以看出排序第5的飞机节点度、点强、节点介数均较小, 但是其加权聚类系数达到了0.93, 即该节点周围其他节点聚集度很高, 飞行环境比较复杂, 因此排序也较高, 这也符合管制工作实际。

图 11 关键冲突飞机识别
表 2 节点指标得分结果
重要度
排序
节点度点强加权聚类
系数
节点介数
1182.740.710.030
2182.430.710.011
3161.840.800.026
4171.220.660.020
5130.460.930.013
6 结论

本文基于复杂网络建立飞行状态网络的模型,利用AHP确定各拓扑指标权重,并经过熵权法进行修正,根据多属性决策方法识别飞行状态网络关键冲突飞机。为了验证提出方法对关键节点的识别效果,计算出按重要度顺序逐个删除节点后网络的鲁棒性和网络效率进行分析,作出变化趋势图,并与接近度方法和度中心性方法作比较,体现本文方法的优势。识别出飞行状态网络中的关键冲突飞机不仅可以帮助空中交通管理部门在日常运行中确定空中交通管制(air traffic control, ATC)的侧重点,而且在应急管理中可以帮助管制员有重点、有针对性的完成应急资源的配置,使得空中交通管理工作井然有序的进行,具有较高的实际意义。

参考文献
[1] TANG Jun, ZHU Feng, PIERA Miquelangel. A Causal Encounter Model of Traftic Collision Avoidance System Operations for Safety Assessment and Advisory Optimization in Highdensity Airspace[J]. Transportation Research Part C, 2018, 96: 347-365. DOI:10.1016/j.trc.2018.10.006
[2] 张进, 胡明华, 张晨. 空中交通管理中的复杂性研究[J]. 航空学报, 2009, 30(11): 2132-2142.
ZHANG Jin, HU Minghua, ZHANG Chen. Complexity Research in Air Traffic Management[J]. ACTA Aeronauticaet Astronautica Sinica, 2009, 30(11): 2132-2142. (in Chinese) DOI:10.3321/j.issn:1000-6893.2009.11.019
[3] WANG Hongyong, WEN Ruiying, ZHAO Yifei. Analysis of Topological Characteristics in Air Traffic Situation Networks[J]. Proceeding of the Institution of Mechanical Engineers Part G:Journal of Aerospace Engineering, 2015, 229(13): 419-425.
[4] WANG Hongyong, SONG Ziqi, WEN Ruiying. Study on Evolution Characteristics of Air Traffic Situation Complexity Based on Complex Network Theory[J]. Aerospace Science and Technology, 2016, 58: 518-528. DOI:10.1016/j.ast.2016.09.016
[5] 董兵.航空交通系统的交通复杂性研究[D].成都: 西南交通大学, 2016
DONG Bing. Research on Traffic Complexity for Air Transportation Systemsam[D]. Chengdu: Southwest Jiaotong University, 2016(in Chinese) http://cdmd.cnki.com.cn/Article/CDMD-10613-1017022318.htm
[6] MORONE F, MAKSE H A. Influence Maximization in Complex Networks Through Optimal Percolation[J]. Nature, 2015(7579): 527-544.
[7] 李昌超, 康忠健, 于洪国, 等. 基于PageRank改进算法的电力系统关键节点识别[J]. 电工技术学报, 2019, 34(9): 1952-1959.
LI Changchao, KANG Zhongjian, YU Hongguo, et al. Identification Method of Key Nodes in Power System Based on Improved Page Rank Algorithm[J]. Transactions of China Electrotechnical Society, 2019, 34(9): 1952-1959. (in Chinese)
[8] 陈雯柏, 崔晓丽, 郝翠, 等. 一种物联网系统层次型抗毁性拓扑构建方法[J]. 北京邮电大学学报, 2018, 41(5): 107-113.
CHEN Wenbai, CUI Xiaoli, HAO Cui, et al. Hierarchical Invulnerability Topology Construction Method for IoT System[J]. Journal of Beijing University of Posts and Telecommunications, 2018, 41(5): 107-113. (in Chinese)
[9] NI S J, WENG W G, ZHANG H. Modeling the Effects of Social Impact on Epidemic Spreading in Complex Networks[J]. Physica A, 2011, 390(23/24): 4528-4534.
[10] WANG Xingyuan, LI Junqiu. Detecting Communities by the Core-Vertex and Intimate Degree in Complex Networks[J]. Physica A, 2013, 392(10): 2555-2563. DOI:10.1016/j.physa.2013.01.039
[11] MAHYAR H, HASHEMINEZHAD R, GHALEBI K E. Compressive Sensing of High Betweenness Centrality Nodes in Networks[J]. Physica A, 2018(497): 166-184.
[12] 黄洋, 汤俊, 老松杨. 基于复杂网络的无人机飞行冲突解脱算法[J]. 航空学报, 2018, 39(12): 262-274.
HUANG Yang, TANG Jun, LAO Songyang. UAV Flight Conflict Resolution Method Based on Complex Network[J]. Acta Aeronautica et Astronautica Sinica, 2018, 39(12): 262-274. (in Chinese)
[13] WEN X, TU C, WU M. Node Importance Evaluation in Aviation Network Based on "No Return" Node Deletion Method[J]. Physica A, 2018(503): 546-559.
[14] WEN X, TU C, WU M. Fast Ranking Nodes Importance in Complex Networks Based on LS-SVM Method[J]. Physica A, 2018, 506: 11-23. DOI:10.1016/j.physa.2018.03.076
[15] REN G, ZHU J, LU C. A Measure of Identifying Influential Waypoints in Air Route Networks[J]. Plos One, 2018, 13(9): 1-19.
[16] BIAN T, HU J, DENG Y. Identifying Influential Nodes in Complex Networks Based on AHP[J]. Physica A, 2017, 479: 1777-1787.
[17] BIAN T, DENG Y. Identifying Influential Nodes in Complex Networks:a Node Information Dimension Approach[J]. Chaos, 2018, 28(4): 4310-4319.
[18] DUBEY R, PAUL J, THOMAS M. Supplier Selection in Blood Bages Manufacturing Industry using TOPSIS Model[J]. International Journal of Operational Research, 2015, 4(24): 461-488.
Identification of Key Flight Conflict Nodes Based on Complex Network Theory
WU Minggong1, WANG Zekun2, GAN Xusheng1, YANG Guozhou1, WEN Xiangxi1     
1. Air Traffic Control and Navigation College, Air Force Engineering University, Xi'an 710051, China;
2. Troops 32211 of the PLA, Yulin 719006, China
Abstract: The air traffic density in the terminal area is high and the traffic situation is relatively complex by the development of aviation, which brings great challenges to controller. In order to understand the flight situation and provide decision basis for controllers, this paper proposes a key flight conflict nodes identification method based on complex network theory and Analytic Hierarchy Process (AHP)-entropy weight method. Firstly, an aircraft state network is established with aircraft as nodes and Airborne Collision Avoidance System (ACAS) communication relations as connecting edges. On this basis, four parameters, node degree, node weight, clustering coefficient and betweenness, are selected as evaluation indexes of node importance, and the weight of each index is determined by using AHP. And entropy weight method is introduced to revise the results. Node importance is calculated through multi-attribute decision-making method to determine key conflict aircrafts. The simulation and experiment on the artificial network and the aircraft state network of a certain day in the terminal area of Kunming Changshui Airport show that the method proposed in this paper can identify the key flight conflict nodes in the aircraft state network, allocate the selected node deployment can effectively reduce the complexity of the aircraft state network, can provide reference for air traffic control services (ATCS), and reduce the allocation difficulty of controller.
Keywords: complex network    aircraft states network    key nodes    multi-attribute decision-making    
西北工业大学主办。
0

文章信息

吴明功, 王泽坤, 甘旭升, 杨国洲, 温祥西
WU Minggong, WANG Zekun, GAN Xusheng, YANG Guozhou, WEN Xiangxi
基于复杂网络理论的关键飞行冲突点识别
Identification of Key Flight Conflict Nodes Based on Complex Network Theory
西北工业大学学报, 2020, 38(2): 279-287.
Journal of Northwestern Polytechnical University, 2020, 38(2): 279-287.

文章历史

收稿日期: 2019-02-26

相关文章

工作空间