EDP Sciences logo
Submit your paper
Search
Menu
All issues Volume 38 / No 2 (April 2020) JNWPU, 38 2 (2020) 279-287 Full HTML
Open Access
Issue
JNWPU
Volume 38, Number 2, April 2020
Page(s) 279 - 287
DOI https://doi.org/10.1051/jnwpu/20203820279
Published online 17 July 2020

© 2019 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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

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

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

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

thumbnail 图1

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

1.2 熵权法对权重修正

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

① 建立原始指标数据矩阵

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

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

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

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

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

③ 计算指标信息熵e

式中，。

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

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

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

1.3 基于多属性决策的节点综合评价

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

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

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

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

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

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

1.4 算法步骤

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

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

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

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

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

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

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

thumbnail 图2

算法流程图

2 飞行状态网络建模

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

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

thumbnail 图3

飞行状态网络模型

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

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

1) 节点度(degree distribution, DD)

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

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

2) 点强(node weight, NW)

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

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

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

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

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

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

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

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

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

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

4 仿真验证

4.1 仿真分析

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

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

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

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

thumbnail 图4

飞行状态网络
thumbnail 图5

关键节点删除后网络结构

4.2 结果分析

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

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

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

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

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

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

thumbnail 图6

鲁棒性分析
thumbnail 图7

网络效率分析

5 实例验证

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

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

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

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

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

thumbnail 图8

雷达管制实时场景
thumbnail 图9

关键冲突飞机识别
thumbnail 图10

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

不同方法调配结果

thumbnail 图11

关键冲突飞机识别
表2

节点指标得分结果

6 结论

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

References

  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 [Article] [CrossRef] [Google Scholar]
  2. Zhang Jin, Hu Minghua, Zhang Chen. Complexity Research in Air Traffic Management[J]. ACTA Aeronauticaet Astronautica Sinica, 2009, 30 (11): 2132– 2142 [Article] [Google Scholar]
  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 [Article] [CrossRef] [Google Scholar]
  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 [Article] [CrossRef] [Google Scholar]
  5. Dong Bing. Research on Traffic Complexity for Air Transportation Systemsam[D]. Chengdu: Southwest Jiaotong University, 2016(in Chinese)

    DONG Bing. Research on Traffic Complexity for Air Transportation Systemsam[D]. Chengdu: Southwest Jiaotong University, 2016(in Chinese)

    [Google Scholar]
  6. Morone F, Makse H A. Influence Maximization in Complex Networks Through Optimal Percolation[J]. Nature, 2015, (7579): 527– 544 [Article] [Google Scholar]
  7. 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 [Article] [Google Scholar]
  8. 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 [Article] [Google Scholar]
  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 [Article] [NASA ADS] [CrossRef] [Google Scholar]
  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 [Article] [NASA ADS] [CrossRef] [Google Scholar]
  11. Mahyar H, Hasheminezhad R, Ghalebi K E. Compressive Sensing of High Betweenness Centrality Nodes in Networks[J]. Physica A, 2018, (497): 166– 184 [Article] [NASA ADS] [CrossRef] [Google Scholar]
  12. 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 [Article] [Google Scholar]
  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 [Article] [NASA ADS] [CrossRef] [Google Scholar]
  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 [Article] [Google Scholar]
  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 [Article] [Google Scholar]
  16. Bian T, Hu J, Deng Y. Identifying Influential Nodes in Complex Networks Based on AHP[J]. Physica A, 2017, 479: 1777– 1787 [Article] [CrossRef] [Google Scholar]
  17. Bian T, Deng Y. Identifying Influential Nodes in Complex Networks:a Node Information Dimension Approach[J]. Chaos, 2018, 28 (4): 4310– 4319 [Article] [Google Scholar]
  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 [Article] [Google Scholar]

All Tables

表1

不同方法调配结果

In the text
表2

节点指标得分结果

In the text

All Figures

thumbnail 图1

飞行状态网络关键冲突节点识别层次结构
In the text
thumbnail 图2

算法流程图
In the text
thumbnail 图3

飞行状态网络模型
In the text
thumbnail 图4

飞行状态网络
In the text
thumbnail 图5

关键节点删除后网络结构
In the text
thumbnail 图6

鲁棒性分析
In the text
thumbnail 图7

网络效率分析
In the text
thumbnail 图8

雷达管制实时场景
In the text
thumbnail 图9

关键冲突飞机识别
In the text
thumbnail 图10

各场景中关键冲突飞机调配后网络结构
In the text
thumbnail 图11

关键冲突飞机识别
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.