齐雁楠,高经东
1. 中国民航大学 空中交通管理学院,天津 300300 2. 中国电子科技集团公司第二十八研究所 空中交通管理系统与技术国家重点实验室,南京 210014 3. 中国国际航空股份有限公司 运行控制中心, 北京 101312
随着中国民航业的迅速发展,空中交通拥堵问题日益严重。一个扇区容量下降或者失效可能导致大片空域发生拥堵,进而引发大范围的航班延误。2015年8月15日,美国弗吉尼亚州区管中心由于电脑技术故障,导致所辖高空交通管制扇区失效,美国东北部各大城市包括华盛顿、纽约、波士顿和费城等机场航班延误,后续延误波及到整个美国东部海岸。复杂网络理论具有丰富的分析理论和成熟的方法体系,可以系统科学地研究空域扇区网络,为减少扇区失效影响提供有效途径。
抗毁性是复杂网络的重要方向,最早由Albert等[1]提出并开始研究,主要是对网络的抗破坏能力测度评估。前期对复杂网络抗毁性的研究大都是静态分析网络结构性能变化。网络受到攻击后,不仅结构性能发生了变化,网络节点负载也发生了分配转移,其他节点的状态也会随之改变,可能会导致部分节点失效,引发新一轮负载分配,这就是级联失效现象[2]。2001年,Moreno等[3]首先提出级联失效模型,对无标度网络的级联失效过程展开研究。2004年,Crucitti等[4]提出了基于边上传输效率动态更新的级联失效(CLM)模型,将节点和边在失效传播过程的动态变化考虑在内。目前常用的级联失效模型主要有:二值模型、沙堆模型、容量-负载模型、耦合映像格子模型等[5]。其中,容量-负载模型在电力系统、交通运输系统、信息通信系统等实际网络的使用最为广泛。2014年,种鹏云和帅斌[6]构建危险品运输网络,提出了危险品运输网络级联失效模型。2017年, Wang等[7]探讨了网络修复和自愈,对自愈的有效性和效率进行了研究;贾承丰等[8]研究了具有模体特征的网络抗毁性,提出了模体攻击策略;周添杰[9]提出基于节点最大剩余容量的负载再分配策略以提高网络对级联失效的抵抗能力。级联失效模型同样适用于航空复杂网络研究,2013年,徐伟举[10]对美国航空机场网络进行级联失效抗毁性分析。2017年,武喜萍等[11]建立了空中交通延误传播模型,重点分析机场航班延误发生和传播规律;傅超琦等[12]从能量的角度分析了航空网络的功能自愈机理。综上,在航空网络中应用复杂网络抗毁性及联级失效理论已具备一定的成果。但从空中交通管制的角度出发,系统地分析空域扇区网络的级联失效及抗毁性,以此制定空中交通拥堵优化策略是没有的。
本文依据传统容量-负载模型方法,建立适用于空域扇区网络的级联失效抗毁性模型,定义扇区节点容量、节点负载等相关参数和变量,构建空域扇区网络级联失效过程模型,确定级联失效抗毁性测度指标。结合空管实际工作,提出空域扇区相邻负载再分配和局部负载再分配策略,并进行了仿真验证。
民航空域按照规则划分为若干个扇区,扇区是实施航班飞行管制的基本空域单元。扇区之间在地理空间上紧密相连,航班飞行时交互信息,这些相互联系的多个扇区形成空域扇区网络。该网络是以扇区为节点,依据扇区间的航班流量数据设边,如果航班在两扇区之间飞行时不经过其他扇区,则在两扇区之间设边,将一定范围的空域内的扇区联系成一个整体网络系统。用邻接矩阵[aij]N×N表示有N个扇区的空域扇区网络,如果扇区i与扇区j直接存在航班联系,邻接矩阵元素aij=aji=1;否则,aij=aji=0。
恶劣天气、军方活动、设备失效等突发情况可能会导致网络节点失效,空域扇区网络进入非正常状态,处于该扇区或者正在飞往该扇区的航班必须进行返航、备降或绕飞,被重新分配至周边扇区,而当再分配后的航班流量大于周边扇区的容量时,周边扇区就会发生拥堵,继而引发新的失效。此现象会引发整个空域扇区网络航班流量的重新分配,导致多个扇区拥堵,甚至造成整个扇区网络失效,这个过程就是空域扇区网络级联失效。
空域扇区网络级联失效抗毁性是扇区网络在发生级联失效后,管制员可以通过疏导航班流量来缓解拥堵,使网络性能仍维持空管运行可接受程度的能力。
本文采用改进的容量-负载(ML)模型[13]对空域扇区网络级联失效进行研究。与民航传统意义的扇区容量和管制员工作负荷定义不同,空域扇区网络中的扇区节点负载和容量不仅仅是单个扇区的管制员的实际工作负荷和扇区所能容纳的航班流量,还要考虑扇区在整个网络系统的重要性及影响。
扇区的强度代表航班流量,体现了本扇区的繁忙程度,是研究空中交通拥堵问题最重要的指标。度ki是与扇区i有航班直接联系的扇区个数,反映扇区在网络中的重要性。经过相关性分析证明,扇区强度主要受到地区经济水平(旅客需求)及航路布局的影响,与度值无关,二者可共同作为影响扇区网络节点负载的参数。将网络拓扑结构同管制实际工作相结合,定义空域扇区网络正常状态下扇区节点i的负载Li为
Li=kiSi
(1)
式中:ki为扇区节点i的度;Si为扇区节点i的强度。
网络节点的容量是该节点能处理的最大负载。扇区的容量为管制员的工作达到某种较高负荷状态可处理的航班架次,在正常运行状态下实际流量小于容量。本文用正常状态扇区节点的负载再加上一定的额外裕度定义扇区节点容量Ci,代表管制员在该时段正常情况下可处理负载的能力。
(2)
式中:α为0到1之间的额外裕度差异化参数,是Li的指数;β为大于0的额外裕度参数。扇区的容量严重受空域结构、导航设备、管制员工作负荷等多种因素限制。负载较小的扇区节点,往往具有较大的额外裕度;而负载较大扇区节点的空域利用率及管制员的工作负荷很大,负载接近容量。在改进的ML模型中,通过调节额外裕度差异化参数α,可以实现不同负载扇区节点的额外裕度差异化,α越小,负载大的扇区节点的额外裕度越小,其负载越接近容量。
对于网络级联失效模型的研究,大多以正常和失效来判定网络中节点的状态[14],若节点失效,则将该节点直接从网络中移除。但对于空域扇区网络,由于航班流量过大导致扇区完全失效的情况极少,通常只会造成管制扇区拥堵,可接收航班架次减少。因此,本文定义扇区网络节点在级联失效过程中共有3种状态:正常、失效、拥堵。正常状态的扇区节点负载小于容量,可以完全行使其管制功能;失效状态的扇区节点是引发级联失效的源头,该扇区节点容量下降为0,原有负载全部向周边扇区重新分配;当扇区网络节点的负载大于等于其容量时,在网络中保留该扇区,进入第3种状态——拥堵状态,无法继续接收其他扇区节点的再分配负载,只允许内部的负载向其他扇区流出,流出过程持续到该扇区负载等于容量。失效和拥堵状态统称为非正常状态。
本文对空域扇区网络级联失效现象做出如下假设:
1) 扇区进入失效和拥堵状态直至结束,不再改变状态。
2) 扇区的容量固定。
3) 空域扇区网络负载分配方式为平均再分配,即超过扇区节点容量的负载平均分配至相邻扇区节点。
在以上分析和假设的基础上,本文将空域扇区网络级联失效过程分为以下4个阶段:
1) 正常阶段:空域扇区网络中各扇区节点负载均小于容量,全部处于正常状态。
2) 失效开始阶段:当突发情况发生致使某扇区临时关闭,对应的扇区网络节点进入失效状态。该扇区的航班流量及其在扇区网络中所承担的功能被分配到周边的扇区,即扇区节点负载分配到相邻扇区节点。
3) 失效扩散阶段:新增加的负载可能会造成部分周边扇区节点负载大于等于其容量,这些扇区节点由正常变为拥堵。进入拥堵状态的扇区节点,将超过自身容量的负载分配到相邻的处于正常状态的扇区节点。之后再开始新一轮的失效扩散。
4) 失效结束阶段:失效扩散时,出现以下情况则终止:① 所有扇区节点负载均不大于容量,网络达到平衡状态;② 某扇区节点负载超过其容量,且相邻扇区都处于非正常状态,超过其容量的负载无法再分配至其他扇区,判定网络处于崩溃状态。
根据级联失效过程的假设和分析,构建空域扇区网络级联失效过程为
步骤1在空域正常阶段,空域扇区网络中各扇区节点负载和容量满足Li
步骤2某扇区进入失效状态。
步骤3依据负载平均再分配方式,失效扇区节点负载Lu全部平均分配到相邻所有扇区,失效扇区节点负载和容量均下降为0。
步骤4进入失效扩散阶段,找出由正常状态转为拥堵状态的扇区节点,将超过其容量的负载平均再分配给相邻的处于正常状态的扇区节点,这些扇区节点均增加负载ΔL为
(3)
根据扇区节点负载和容量的关系,当α一定时,β可以反映扇区节点处理负载的能力,β越大,级联失效的影响越小。通过调节β参数,可以找到临界阈值βt,当β≥βt时,负载最大的扇区节点失效不会造成整个网络崩溃;当β<βt时,由负载最大的扇区节点失效引发的级联失效会导致网络崩溃。
在空中交通系统中整体扇区崩溃的情况极少发生。因此,本文着重研究在级联失效没有造成网络崩溃,即β≥βt情况下的抗毁性,采用扇区非正常率来评估。扇区非正常率是空域扇区网络中处于非正常状态的扇区数和空域正常阶段总扇区数的比值,即
r=Na/N
(4)
式中:Na为非正常扇区的数目;N为扇区总数。在空域扇区网络系统处于平衡的状态下,r越小,处于正常状态的扇区越多,管制员在疏导拥堵时可利用的空域越多,网络运行越顺畅,级联失效抗毁性越强。
当空域扇区网络中某扇区节点失效时,如何减轻级联失效所带来的影响,降低网络崩溃概率,就需要对空域扇区网络级联失效抗毁性进行优化。通常,对于网络级联失效抗毁性优化主要有两大类方法:
1) 通过增加或者删除边(点)来改变网络拓扑结构。以增加边使网络结构均匀化,以减少边使传输途径定向化[15-18]。
2) 优化负载再分配策略。根据网络节点信息,以特定比例分配负载来充分利用资源[19-20]。
实时运行中,通过改变网络拓扑结构优化空域网络级联失效难以实现。因此,本文采用负载再分配策略对扇区网络级联失效抗毁性进行优化。当空域扇区出现失效或者拥堵状况时,管制员不会盲目地将航班流量平均再分配到相邻扇区,而是了解周边扇区情况,根据其他扇区的负载和容量关系,将航班按照一定比例进行分配,减少其他扇区拥堵状况的概率。本文采用基于扇区节点剩余容量的相邻负载再分配策略和局部负载再分配策略来优化空域扇区网络级联失效抗毁性。
1) 失效开始阶段,失效扇区节点容量均下降为0,按照相邻扇区节点剩余容量的比例大小将失效扇区节点负载Lu分配到相邻所有扇区,相邻扇区节点增加负载ΔLuj为
(5)
式中:Mi为失效扇区的相邻扇区集合。
2) 进入失效扩散阶段,正常状态转为拥堵状态的扇区节点,将超过其容量的负载分配给相邻的处于正常状态的扇区节点,这些扇区节点增加负载ΔLij为
(6)
相邻负载再分配策略具体实现过程,如图1所示。
图1 相邻负载再分配策略流程图Fig.1 Flow chart of adjacent load redistribution strategy
管制员不仅可以了解相邻的扇区情况,还可以通过流控中心的通告,获悉周边空域多个扇区的流量和容量状况,在周边扇区发生拥堵时,对将要进入拥堵区域的航班提前实施流控策略,从而缓解空中交通拥堵状况。
基于扇区节点剩余容量的局部负载再分配策略(以下简称局部负载再分配策略)不局限于相邻的节点,而是距失效或拥堵扇区最短路径长度不大于d的局部空域内的全部正常扇区。d为分配半径,且d≥2,即相隔一个扇区以上的扇区节点进行负载分配。局部负载再分配策略扩大了管制员协同扇区范围,对飞往或即将进入非正常扇区的部分航班提前改为绕飞或者返航备降,大大降低扇区网络级联失效,提高网络抗毁性。
由于预知能力的有限性、流量信息传递的延迟性以及绕飞成本的制约性,当扇区i进入非正常状态后,是以与距离有关的分配比例pij将额外负载分配到周边分配半径内的所有正常扇区节点,具体分配比例为
(7)
(8)
图2 局部负载再分配策略流程图Fig.2 Flow chart of local load redistribution strategy
图3 中南管制扇区网络Fig.3 Central and southern control sector network
本文选取民航中南区域管制中心所辖空域作为实证样本,根据2017年某日高峰时段航班数据,构建中南管制扇区网络,如图3所示。网络共计42个管制扇区即42个节点,共有90条边,平均度为3.95,平均路径长度为3.89即航班平均需经过4个扇区可到达目的扇区。网络的聚集系数为0.33,聚类性较差,管制员指挥与协调航班难度大。
首先计算中南管制扇区网络每个扇区的度和强度,进而获得各扇区节点的负载,如表1所示,广州05号扇区的节点负载最大,令其失效对网络产生的级联失效影响最大,研究该条件下中南管制扇区网络级联失效抗毁性。
依据空域扇区网络级联失效模型,建立仿真流程,如图4所示。
在仿真过程中,通过调节扇区节点额外裕度差异化参数α,分别取值0.9、0.8、0.7,以实现负载不同的扇区节点额外裕度差异化对级联失效过程影响的测试。用测度指标进行级联失效抗毁性分析,依次取不同的α和β,仿真计算r,结果如图5 所示。α越大,扇区节点容量越大,β值相同时,对应的r值相对较小,网络级联失效抗毁性更强。
表1 空域正常阶段中南管制扇区网络节点负载
图4 空域扇区网络级联失效仿真流程图Fig.4 Simulation flow chart of airspace sector network cascading failure
在参数β较小时,各扇区节点的额外裕度都很小,一旦负载最大的扇区节点失效,大量负载流向周边扇区节点,超出其容量并无法疏导。图5中各折线临界阈值βt对应的扇区非正常率r并不高,大多数扇区仍处于正常状态,说明由局部负载汇集无法疏导是造成空域扇区网络级联失效的主要原因。进一步分析,广州08号扇区是造成该网络级联失效崩溃的瓶颈扇区,α参数不同的各模型,随着参数β的逐渐增大,都是在满足广州08号扇区在级联失效过程中没有进入拥堵状态时,网络由崩溃状态转为平衡状态。广州08号扇区的度值和强度比较小,负载和容量很小,难以承载其他扇区节点额外负载的流入;此外其相邻扇区数目少且与失效扇区相连,容易全部进入拥堵状态,从而导致广州08号扇区节点多于容量的负载无法被疏导。可见,与大负载扇区节点距离较近,且度值和强度小的扇区节点容易成为空域扇区网络级联失效的瓶颈。
当β大于βt之后,扇区网络达到平衡,级联失效不会造成网络崩溃。随着β的增加,承载额外负载的能力也增强,拥堵扇区逐渐减少,r也相应变小。当r减小到0.095后出现一段停滞,此时广州01号扇区成为拥堵瓶颈扇区。β进一步大幅增加,广州01号扇区由拥堵状态转为正常状态,r才继续下降。
图5 中南管制扇区网络级联失效抗毁性分析图Fig.5 Analysis chart of network cascading failure invulnerability for central and southern control sector network
随着β继续增大,距离失效扇区最近且容量较小的广州04和广州05号扇区足以承载失效扇区节点所分配的额外负载,r最小,该网络不会受到级联失效影响。
扇区级联失效后通常采用扇区流量平均分配策略(平均分配策略),即当扇区失效时,将扇区流量平均分配给相邻扇区。采用相邻负载再分配和局部负载再分配2种策略模拟仿真级联失效过程,并与平均分配策略进行对比。同样令广州05号扇区失效,和3.1节仿真计算方法类似,比较采取优化策略前后网络级联失效的结果,其中局部负载再分配的参数取d=2、θ=2,如图6所示。
采取相邻和局部负载再分配策略后,改善了平均分配时局部汇集导致网络崩溃的情况,临界阈值βt都有所减小,其中局部负载再分配策略βt更小,该策略将额外负载分配至更多的周边扇区节点,可以充分利用局部空域资源。随着β大于βt,网络达到平衡,此时失效扇区负载直接分配的扇区都处于拥堵状态,在βt处更多节点拥堵才会造成崩溃,扇区非正常率相对偏高。随着β进一步增大,r迅速降低,局部负载再分配策略下降速度更快,相同β值对应的r值更小,最先进入无拥堵状态。总之,相邻和局部负载再分配比平均分配策略提升了扇区网络级联失效抗毁性,其中局部负载再分配策略效果更加明显。
图6 不同再分配策略优化图Fig.6 Map of different redistribution strategy optimizations
本文运用复杂网络理论对空域扇区网络级联失效及抗毁性优化策略进行了研究,得出以下结论:
1) 定义扇区节点有正常、失效和拥堵3种状态,对空域扇区网络级联失效过程建模,并采用实例仿真分析。
2) 扇区节点额外裕度差异化参数α越大,扇区节点容量越大,β值相同时,对应的r值相对较小,网络级联失效抗毁性更强。
3) 相邻负载再分配和局部负载再分配2种策略均能够提升网络级联失效抗毁性,随着β进一步增大,局部负载再分配策略对网络失效抗毁性提升更为有效。