康 瑞,牟睿聆,李凌海,周裕川
(中國民用航空飛行學院空中交通管理學院,四川 廣漢 618307)
隨著航空運輸業的快速發展,機場構型布局更加復雜,場面路網持續保持較高負荷運行。若其中關鍵路段出現損毀或擁堵,不僅會拉低路網的總體通行能力,影響航班正常運行,還可能誘發航空器地面運行安全風險,造成嚴重的航空地面事故。在區域路段容量受限的情況下,管制員需要迅速調整航空器地面滑行路線,及時引導分流,緩解交通擁堵。而實現這一目標的基礎是重要路段識別和重要性排序,通過分級調控減少“范圍蔓延”,以此提升擁塞風險控制能力,確保機場安全運行平穩可控。
關鍵節點識別是復雜網絡理論研究的核心技術。從20世紀90年代起,很多學者針對復雜網絡的關鍵節點識別等問題進行了深入研究,取得了大量研究成果。在識別算法方面,Ma等[1]將牛頓地球引力定理與復雜網絡的拓撲結構相結合,提出牛頓引力中心性。Zhang等[2]采用VoteRank方法識別網絡中具有較強傳播能力的節點。Liu等[3]針對常用算法無法對橋梁節點進行識別的問題,構建了基于線的度值及其重要性的關鍵節點識別方法DIL。在運用方面,高潔[4]總結了交通運輸領域的節點重要度挖掘指標,提出該領域下的指標運用方向。鄧紅星等[5]將大型客流集散點作為網絡節點,通過主成分分析法對區位因素、交通特性和路徑選擇等屬性進行指標權重分析,構建評價體系。近年來,復雜網絡關鍵節點識別技術開始應用于民航領域[6-9],主要用于解決機場群航線網絡的優化問題。吳明功等[10]提出構建飛行狀態網絡,運用層次分析法和熵權法結合的思想確定指標權重,為確定關鍵沖突飛機創造條件。丁建立等[11]構建加權航空運輸網絡,設計基于邊權重和集聚系數的節點重要性評估辦法。
當面對突發故障時,網絡可能無法正常運轉,極易造成經濟效率損失,由此,衡量網絡抗毀性的研究應運而生??箽缘陌l展始于對網絡遭受破壞后的對比研究,由Albert等[12]提出并研究。之后,學者常通過隨機攻擊和蓄意攻擊的方式對網絡進行抗毀性實驗,楊景峰等[13]基于軌道交通建立復雜網絡,以網絡效率和最大連通子圖比例作為評價指標,采取多種攻擊策略驗證網絡的抗毀性。趙瑞琳等[14]嘗試對軌道交通網絡進行隨機以及累計蓄意攻擊,通過改進網絡效率的方式衡量網絡抗毀性,得到網絡關鍵點和路網失效臨界值。Sun等[15]從乘客角度分析全球航空運輸網絡面對不同的攻擊策略后,移除某機場對整個網絡的影響。胡小兵等[16]采取隨機、加權度中心性、加權介數中心性、暴雨和沙塵暴的攻擊策略方式,針對多家航空公司的無向加權航線網絡進行抗毀性研究。
綜上所述,當前復雜網絡節點重要度研究較少涉及機場活動區方向,對網絡運行特點把握不足,導致節點挖掘角度不全面,且相關抗毀性測度也較為單一。鑒于此,構建機場活動區道路交通網絡,從多種角度評估節點重要性,并定義適于進離場運行規則的航空器地面滑行關鍵路徑識別方法,以此獲取關鍵節點排序的樣例?;谏鲜龉濣c序列開展抗毀性測試,建立綜合抗毀性衡量指標,對以網絡效率和最大連通子圖節點比例為性能水平的網絡曲線進行結果對比,識別對機場活動區影響較大的路段集合,為獲取場面滑行關鍵路徑提供新的理論依據和思路。
定義機場活動區交通網絡為G,其表達式為
式中:V={vi,i∈N}為網絡G的節點集,代表航空器在跑道、滑行道和停機坪內的滑行路段;E={eij,i≠j,i,j∈N}為網絡G的連邊集,代表航空器在滑行道交匯口的轉向軌跡,其中eij=(vi,vj),表明邊為有向邊。
復雜網絡特征指標包含節點度、平均路徑長度、度度相關性、簇系數與度相關性等[17]。度ki代表節點i與鄰接節點的連邊數量。平均度表示網絡節點之間的連通程度。網絡直徑D為網絡中任意兩節點間的最短路徑邊數的最大值[18]。平均最短距離表示網絡中任意兩節點之間的最短路徑邊數的平均值。平均集聚系數是用以表述網絡緊密程度的指標。
經典的節點重要性評估方法多從節點近鄰、全局路徑、特征向量和網絡位置4個角度挖掘節點的重要程度[19]。從每個角度選取一種方法,對關鍵節點進行識別。
1)度中心性:網絡中節點中心性最簡單的指標。度中心性值越大代表其連通性即關鍵路段通行順暢能力越佳,記為DC。
式中:ki代表與節點i相連的邊數;N代表節點個數。
2)介數中心性:網絡中涉及最短路徑的節點重要度評價指標,記為BC。
3)PageRank:網絡中與隨機游走模型有關的指標,起初用于篩選網頁搜索結果,記為PR。
式中:PR(i)代表節點i的PageRank值;PR(Tk)代表能指向節點i的節點集合Tk的PageRank值;L(Tk)代表能指向節點i的節點集合Tk的出鏈數;k代表迭代次數。
4)基于K-shell的復雜網絡關鍵節點識別方法:考慮網絡分層、鄰居節點和次鄰居節點影響的節點重要度評價指標。該算法采用K-shell方法對網絡進行分層,得到各個節點的K殼值Ks,結合綜合度C(i)得到最終排序,算法記為KBKNR[20],其表達式為
其中,μi和D(i)的表達式為
式中:K(i)代表節點i的度;N(i)代表節點i兩步鄰域內的節點數。
目前,復雜網絡研究采用的模型大部分為理論生成模型,節點介數定義為網絡中所有最短路徑中經過該節點的路徑的數目占最短路徑數的比例。而在實際的機場活動區交通網絡結構中,只考慮所有進離港滑行路線上任意兩點間的最短路徑經過目標節點的比例情況。針對航空器地面運行特點,定義一種全新的改進介數中心性指標,記為IBC。
當關鍵路段遭受損毀或擁堵時,路網通行能力下降,抗毀性是研究網絡在這種條件下維持及恢復自身效能到一個可接受程度的能力[17]。將網絡效率和最大連通子圖節點比例作為衡量系統性能水平的指標,并將其歸一化,使其在固定范圍內變動,從而繪制出以時間為橫坐標,網絡性能為縱坐標的圖像。圖1為網絡受損過程的示意圖,其中ts為網絡初始受擾時刻,te為最低性能值時刻,ts<t<te表示網絡受擾階段,通常,網絡破壞模式包括蓄意攻擊和隨機攻擊。本文中以5種蓄意攻擊方式下的關鍵節點集合進行連續移除,模擬蓄意攻擊下的網絡抗毀性;同時隨機選取網絡中的20個節點進行連續移除,模擬隨機攻擊下的網絡抗毀性,為消除隨機影響,每次實驗100次并取均值。最終比較綜合抗毀性衡量指標,找出關鍵節點集合。
圖1 系統性能受損過程曲線
根據網絡性能變化曲線,定義魯棒性、性能下降速率和單位時間性能損失作為衡量網絡性能變化的指標。當魯棒性越強,性能下降速率越小,單位時間性能損失越小,整個網絡的抗毀性越強。
1)網絡效率:一種與運輸性能相關的指標,由節點之間最短路徑長度dij的倒數表示。關于單節點網絡效率的表達式為
整個網絡的網絡效率為所有節點網絡效率的平均值,關于整個網絡的網絡效率表達式為
2)最大連通子圖節點比例:一種與連通能力相關的指標,即剩余節點最多的子網絡所含節點數量占總節點數量的比例,表達式為
式中:δ(m)代表刪除m個節點后剩余網絡中最大連通子圖的節點數量。
3)魯棒性:網絡遭受擾動后,仍能維持基本性能的能力,記為R,表達式為
式中:NP(t)表示t時的網絡性能,如網絡效率E和最大連通子圖節點比例Cr。
4)性能下降速率:網絡受擾后,衡量性能損失快慢的指標,即性能曲線的平均下降斜率,記為PDR,表達式為
式中:num表示性能下降曲線中的線段個數。
5)單位時間性能損失:衡量網絡性能的時間平均損失程度,記為TAPL,表達式為
式中:NP(t0)表示初始網絡性能。
較多學者采用擾動后的性能變化速率對抗毀性效果進行對比,然而單一的衡量指標無法進行全面評估。從魯棒性、下降速率以及單位時間性能損失3個角度進行數據分析,利用其正反比特性對結果進行完善,建立一種綜合抗毀性衡量指標CDI,表達式為
以華北地區某機場為例,對場面關鍵滑行路徑及抗毀性進行實證研究。跑滑構型如圖2所示。
圖2 機場跑滑構型
網絡模型中,集合V含有元素的個數為107,集合E含有元素的個數為203,如圖3所示。
圖3 機場活動區交通復雜網絡圖
網絡G平均度為2.23,即任意一個滑行道平均與周圍2.23個相鄰滑行道之間存在聯系。從節點度分布可以看出,度為2的節點范圍廣,關于機場活動區節點度分布如圖4所示;機場活動區交通網絡的網絡直徑為8,說明網絡中任意兩滑行道之間最多需要經過8個滑行道;網絡G的平均最短距離為3.35,意味著航空器從任意一個滑行道出發平均要經過3.35個滑行道才能到達目的滑行道;網絡G的平均集聚系數為0.033,說明路段較為稀疏,整體表現不夠緊密。
根據文獻[16]中提出的KBKNR算法對節點進行排序,表1列舉了部分節點的K殼值Ks、綜合度C(i)以及中間結果。
表1 KBKNR方法的計算結果
根據上述結果數據,優先選取Ks大的節點,若存在Ks相同的情況,較大C(i)的節點先輸出,率先輸出的節點重要程度越高,最終結果如表2所示。
表2 KBKNR算法重要度排序
按照重要度由大到小的方式,對5種評價指標進行排序,關于各指標的重要度前20個節點數據如表3所示,其中,每一列為該指標的重要點集序列。
表3 不同方法得到的節點重要性排序
關于機場活動區交通網絡的失效規則如下。
1)當網絡面對干擾時,設定單位時間失效1個節點,直至失效到20個節點結束。
2)網絡的擾動方式分為隨機擾動和蓄意擾動,隨機擾動是指在機場活動區交通網絡G中表現為突發性的航空器備降、通訊失效等導致滑行道臨時關閉的情況,蓄意擾動主要為關鍵滑行路段擁堵現象?;械拦濣c失效后,與其相連的節點被刪除,由此可得到更新后的網絡及相應的網絡性能。
3)蓄意攻擊的節點為上述每個指標的重要點集序列,需對其進行依次移除。
將機場活動區交通網絡面對隨機攻擊和蓄意攻擊時的網絡效率、最大連通子圖節點比例變化曲線進行對比分析。如圖5和圖6所示,當網絡面對隨機攻擊時,相對于蓄意攻擊,網絡性能的下降速率較為緩慢,即蓄意攻擊方式對網絡G的破壞程度明顯大于隨機攻擊,說明網絡在隨機攻擊下具有一定的魯棒性。
圖5 不同攻擊策略下的網絡效率曲線
可以看出,在t=0時,網絡開始受到干擾,攻擊20個節點后,即t=20時,網絡性能達到最低值。網絡初始效率為0.295,最大連通子圖節點比例為0.907,受擾結束后,2種網絡性能降低到最低值,基于度中心性節點序列下的攻擊性能為0.000 5和0.010 3,基于介數節點序列的攻擊為0.012 2和0.082 5,基于改進介數節點序列的攻擊為0.015 1和0.082 5,基于PageRank節點序列的攻擊為0.000 5和0.010 3,基于KBKNR節點序列的攻擊為0.042 1和0.092 8?;诙戎岛蚉ageRank節點序列的攻擊對機場活動區交通網絡的影響較大,在實際運行中,需重點保護這2個節點序列下排名靠前的路段,保證其交通暢通。
為準確識別出較優的機場活動區關鍵路段,通過魯棒性、下降速率以及單位時間性能損失構成的綜合抗毀性衡量指標CDI進行數據分析,計算的機場活動區網絡綜合抗毀性指標值如表4、表5所示??梢钥闯?,隨機攻擊的抗毀性較強,面對擾動的性能損失最小?;赑ageRank節點序列的CDI為0.010和0.240,基于度中心性節點序列的CDI為0.009和0.238,相比直觀判斷,CDI方法更能準確判斷其抗毀性程度。結果表明,基于度中心性節點序列下的擾動對網絡的破壞性最強,此關鍵節點序列是需要重點進行流量調配的路段。
表4 基于網絡效率的綜合抗毀性衡量指標
表5 基于最大連通子圖節點比例的綜合抗毀性衡量指標
1)抗毀性實驗表明,航空器滑行關鍵路徑所包含的節點集合多數情況可以通過度中心性、介數中心性、PageRank、KBKNR和改進介數中心性得到節點重要性排序。
2)網絡面對隨機攻擊時更具抗毀性?;诙戎行男院蚉ageRank節點序列的攻擊,其抗毀能力較為接近,但基于度中心性的節點序列抗毀性更差,因此,需重點監測C、B、A、C1、H、K1、C2、RWY、K、C3等路段,降低擁堵發生率,確保網絡正常運行。
3)復雜網絡特性的實證研究表明,滑行道平均與周圍2.23個相鄰滑行道之間存在聯系,任意兩滑行道之間最少經過3.35個路段,最多需經過8個滑行道,且路段在網絡中連接不夠緊密。