基于功能脆弱性的空中交通相依网络流量分配

2020-06-08王兴隆齐雁楠潘维煌

航空学报 2020年4期

王兴隆，齐雁楠，潘维煌

中国民航大学空中交通管理学院天津 300300

安全有序的空中交通系统，依靠机场、航路和管制扇区网络协同运行。在系统内部或外部受到扰动时会引发脆弱性，造成空中交通延误，严重时还带来系统安全风险。采用相依网络理论，识别脆弱源并实施合理航班流量分配，是解决上述问题的一种有效方法。

相依网络是一种多层复杂网络，适用于刻画各层网络间的影响关系与耦合方式[1]。相依网络脆弱性是当下的研究热点，在理论方面，文献[2]分析在不同空间嵌入与攻击模式下，网络性能的变化，并提出了恢复策略；文献[3]则深入研究了相依网络的级联失效，指出在受到攻击时容易破坏网络结构和功能的完整性，引发网络脆弱性。相依网络脆弱性在电力、交通、航空等领域已有初步应用；文献[4]分析了电力、通信网络的脆弱性，研究了网络级联失效的阈值，并探索影响网络脆弱性的关键节点；文献[5]采用启发式算法分析道路网络交通流模式，分析交通流传播过程，辨识不同时刻网络脆弱性；文献[6-7]建立了空中交通相依网络模型；文献[8-9]研究了网络抗毁性和脆弱性。在流量分配方面，文献[10-13]研究了轨道交通网络的客流、列车流的优化；文献[14-16]研究电力网络的电流控制，实现整个网络输送性能最优化。在航空领域，空中交通流量管理是一个经典问题[17-19]，模型与算法都有较多研究。近期，文献[20]提出一种基于航班起飞与计划到达时间差最小的优化策略，综合考虑航路、容量、航空器速度等多约束条件，建立了航班时刻分配策略；文献[21] 针对空域拥堵的问题，采用多目标规划方法，实施航班地面等待、盘旋、改航等策略；文献[22] 提出一种控制航班延误分布、减少联程航班延误的方法，采用混合整数规划优化模型解决航路上交通需求与容量平衡问题，实现缩短起飞间隔、减少延误的目标。

但空中交通脆弱性研究只是刚刚开始，缺乏应用场景，空中交通流量分配是个网络化、系统化问题，尚未发现以全局视角、不同网络层次协同的方式，采用相依网络方法进行研究。网络脆弱性一般分为结构脆弱性和功能脆弱性，本文主要研究空中交通网络功能脆弱性，在研究脆弱性发生规律基础上，以机场、航路和管制扇区网络的流量熵值之和最小为目标，对各层网络实施流量分配，降低相依网络脆弱性，使得空中交通流趋于有序。

1 空中交通相依网络功能脆弱性识别

以空中交通组织为依据，建立空中交通相依网络G0，由机场网络G1、航路网络G2、管制扇区网络G3组成。G1以机场为点，机场间的备降关系为边；G2以航路点为点，航路的航段为边；G3以管制扇区为点，扇区间航班交接关系为边。G1与G2的连边表示飞机的进离场；G1与G3的连边表示扇区对机场飞机起降的管制；G2与G3的连边表示扇区对飞机航路飞行的管制。

1.1 网络功能脆弱性指标

空中交通相依网络节点在受到扰动而失效后，一方面会造成节点与边的连接失效而破坏网络结构，另一方面也会引起网络功能的混乱，触发网络功能脆弱性。本文采用文献[6]中的方法，建立网络脆弱性的基本特征指标，如表1所示。

表1 网络功能脆弱性指标

对于不同层网络流量熵计算中，当网络中所有节点的流量不均衡时，网络流量熵最大；所有节点的流量均衡时，网络流量熵最小。为了分析不同层网络的流量熵，进行归一化处理：

(1)

本文通过分析上述功能脆弱性指标变化率，识别网络功能脆弱性表现规律。指标变化率计算为[23]

(2)

式中：Δφ为指标变化率；φ(q)为q比例节点失效时功能脆弱性指标值；φ(q-1)为q-1比例节点失效时功能脆弱性指标值。

1.2 功能脆弱性识别方法

在分析空中交通相依网络功能脆弱性过程中，需要考虑不同层网络间相互影响关系，采用扰动节点的方法使其失效。扰动方式分为随机扰动和蓄意扰动，随机扰动是从相依网络中等概率删除节点，蓄意扰动则是按节点的空中交通流量大小将网络节点排序(流量相同时等概率)删除节点。

为了展示节点失效如何影响网络脆弱性，依据空中交通管理规则，建立节点失效对功能脆弱性的影响规则。

1) 层网络内的交通流转移规则

① G1层网络节点失效，其失效节点的交通流将被转移至层网络内相邻机场节点。

② G2节层网络点失效，其失效节点交通流被转移至相邻航路点。交通流转移的过程中，受到相连的G3层网络节点容量约束，若转移量超过G3层网络节点的容量，则以G3层网络节点最大裕度作为交通流转移最大量。

③ G3层网络节点失效，其失效节点交通流被转移至相邻管制扇区节点。交通流转移的过程中，交通流转移受相连的G2层网络节点的容量约束，若转移量超过航路节点的容量，则以航路节点裕度作为交通流转移最大量。

2) 层网络间的交通流转移规则

① G1层网络节点失效，相连的G3层网络节点和G2层网络节点不发生交通流转移。

② G2层网络节点失效，相连的G1、G3层网络节点发生交通流转移。

③ G3层网络节点失效，相连的G1、G2层网络节点发生交通流转移。

节点裕度为节点容量与流量的差值。在不同比例节点失效情况下，分别采用随机与蓄意2种扰动方式，计算网络功能脆弱性指标，分析指标变化率。

2 网络流量协同分配

空中交通网络流就是航空器由机场起降、空中沿航路飞行形成的航班流量。当网络形成持续大量的航班流量，尤其是流量达到或接近容量时，扰动网络会造成大范围航班延误，网络功能脆弱性增大。据此，参照实际运行，对机场、航路、管制扇区网络的航班流量进行合理、协同分配，改善空中交通相依网络功能脆弱性更具实际意义。在流量熵归一化的前提下，协同流量分配的目标是各层网络流量熵值的和最小，网络内部交通流更有序。

2.1 目标函数

空中交通相依网络流量分配的目标函数为

(3)

结合实际空中交通流量管理工作，在流量分配过程中对各层网络的流量进行约束:

0.8tai≤t′ai≤Caia∈1,2,3

(4)

式中：t′ai为Ga层网络中节点i在流量分配过程中的流量；tai为Ga层网络中节点i的流量；Cai为Ga层网络中节点i在流量分配过程中的容量。

在约束条件下，使空中交通相依网络的3层网络的流量匹配，同时流量熵值总和最小，此时网络内部交通流较为有序，具有较强的抗干扰能力，能改进空中交通相依网络脆弱性。

2.2 求解算法

在网络节点数量较多的情况下，为了产生最优解，计算量很大。遗传算法是一种成熟且通用性强的优化算法，约束条件少，具备并行性和全局搜索能力，适合解决组合优化问题。流量分配，是在网络最小总熵值的目标下，根据约束条件进行各个节点流量匹配，是典型的组合优化问题。本文将网络总流量熵作为适应度，对遗传算法进行改进，实现网络流量分配优化。

1) 编码与初始种群生成

采用明码编码方式，将需要分配流量的层网络节点形成N元数组作为染色体λ=(λi)N，第i个节点分配的流量λi代表染色体基因。其他层根据流量分配策略分别形成染色体。

以原始流量串作为种子染色体，根据2.1节的流量约束条件，对每个流量值进行随机变化[80%，120%]，生成初始种群P。

2) 遗传算子

① 选择。对初始种群P进行随机排序，为了保留精英且扩大搜索范围，将随机排序后的种群进行分组(m个为一组)，留下m条中的最优解，其他进行交叉、变异操作。

② 交叉。采用段交叉方式，随机选择(m-1个中)2个个体进行配对，随机设置交叉段，依照概率pc交换2个个体部分染色体，形成新个体。

③ 变异。采用基因段变异操作，随机选择(m-1个中)个体按照变异概率pm随机改变某段基因位的编码。为了在迭代前期扩大搜索范围，后期提高精英解保留概率，pm根据迭代次数而改变，前期大后期小，其表达式为

pm=(L-Iter)/L

(5)

式中：L为总迭代次数；Iter为当前迭代次数。

基于上述遗传算法，通过改变层网络节点流量进行网络流量协同分配，具体策略步骤如表2所示。

表2 网络流量协同分配策略

3 算例分析

采用中国北京、天津、河北、山西、内蒙古区域的民航数据，构建中国华北空中交通相依网络，其中，机场网络G1共计28个机场，79对备降关系；航路网络G2共计41个航路点，90条航段；管制扇区网络G3共计20个扇区，43条扇区移交关系，见图1。结合空中交通相依网络模型、节点扰动方式和失效规则，计算节点失效后网络脆弱性指标，分析指标变化率识别脆弱性表现规律。

3.1 功能脆弱性识别分析

1) 网络流量熵变化率分析

采用式(1)计算网络流量熵，利用式(2)分析指标变化率和失效阈值，结果如图2所示。图中：R(Gb)=fM(Ga)表示对Ga网络中的节点进行扰动， Gb网络的指标变化。M代表扰动方式，M=R、 D分别表示随机扰动和蓄意扰动。

图1 华北空中交通层网络

图2(a)表明，G1层网络节点随机扰动，G1流量熵的变化率波动幅度较小，蓄意扰动G1层网络节点，G1流量熵的值波动幅度也较小，其他情形也都未引发网络的级联失效。图2(b)表明，G2层网络节点蓄意扰动，G1的流量熵在扰动节点为30%熵值有明显上升，幅度较大，此时G1内部因交通流转移分配而混乱，网络节点间的交通流相互影响，产生级联失效现象，其他情形造成G1、G3的熵值的波动，但是并未造成熵值持续上升，所以没有引发网络的级联失效。图2(c)表明，G3层网络节点随机扰动，G1、G2、G3的流量熵都未出现熵增的持续上涨，未引发网络的级联失效；蓄意扰动G3的节点，10%的节点扰动比例造成G1的熵值开始大幅度波动，熵值变化很大，网络的交通流转移分配造成网络内部混乱，引发G1的级联失效，其他情形未引发网络的级联失效。

图2 网络流量熵变化率

2) 网络交通流损失比变化率分析

利用式(2)对网络最大连通度变化率进行分析，结果如图3所示。图3(a)表明，G1层网络节点随机或蓄意扰动，G1没有出现级联失效现象。随机扰动G2层网络节点，扰动比例达5%时，G2的交通流损失开始快速增长，损失量迅速达200%，此时G2内部出现级联失效现象，扰动比例达10%，G1的交通流损失达到1000%，网络内出现了级联失效现象。其他情形都未引发网络的级联失效。由图3(b)可知，随机扰动G3层网络节点，G2网络在节点扰动比例达10%时，网络的交通流损失值快速达到247%，此时G2网络产生级联失效现象；G3层网络节点的随机扰动比例达15%时，G1的交通流损失值快速达到184%，此时G1产生级联失效现象，其他情形都未引发网络的级联失效。

图3 网络交通流损失比变化率

综上，网络功能脆弱性表现规律为：扰动G1的交通流，3层网络并未表现出相应的脆弱性；随机扰动G2、G3的交通流，G1、G2都会表现出脆弱性，说明G1、G2更容易受到扰动的影响，但蓄意扰动下各网络并未表现脆弱性。

3.2 层网络流量分配

采用2.2节中的分配算法，产生初始种群个数100个，总迭代次数10 000次，为了防止快速收敛，取pc为固定值0.8，适应度变化曲线见图4。

1) 对空中交通相依网络的G1进行交通流量分配，在目标函数与约束条件下，机场网络的各节点流量分配见表3，节点编号对应图1(a)。

图4 各层网络流量优化适应度

G1网络交通流量分配中，网络的流量熵值和由分配前的8.602 7降为分配后的8.283 3。结合空中交通系统运行实际，对G1的节点的流量在约束范围内进行分配，使空中交通相依网络的3个层网络间的流量熵值总和最小，网络趋于有序，在各种干扰下仍能拥有较好的抗扰动能力，机场网络的流量分配能降低网络的脆弱性。

2) 对空中交通相依网络的G2进行交通流量分配，在目标函数与约束条件下，航路网络的各节点流量分配见表4，节点编号对应图1(b)。