基于節點狀態的中南地區民航網絡級聯失效

謝本凱， 黃龔迪， 李 琴， 林睿浚

(1.鄭州航空工業管理學院管理工程學院, 鄭州 450046； 2.鄭州航空工業管理學院信息管理學院， 鄭州 450046)

隨著中國城市化進程的加快，各類自然災害、事故災難、公共衛生事件日益頻繁發生。民用航空作為中國主要的交通運輸方式，在各類突發事件的影響下如何保持民航網絡的有效運轉，已逐漸成為研究熱點問題。

Albert等[1]最先開始分析網絡中的級聯失效現象，通過定義節點和邊的失效狀態去分析網絡的抗毀性。在此之后大量針對級聯失效的研究涌現出來。王興隆等[2]根據航空網絡拓撲結構和節點流量特點，建立航空網絡模型，以便識別航空網絡中的影響力節點；楊新湦等[3]通過復雜網絡理論對中國航線網絡的基本性質以及近年來的演化進行了分析，并在此基礎上探討了網絡抗毀性問題；王興隆等[4]構建了由機場網絡、航路網絡、管制網絡互相連接而形成的航空相依網絡模型，并結合華北地區的實際數據，對網絡的特性以及網絡的魯棒性進行研究。

其他網絡方面，Pu等[5]通過不斷刪除網絡中的最短路徑引發級聯失效現象，從而分析復雜網絡系統的脆弱性；吳潤澤等[6]針對電力網路提出了一種考慮級聯失效現象的耦合網絡節點重要度的評估方法；種鵬云等[7]以危險品運輸網絡為樣本，研究了在受到恐怖襲擊以后的級聯失效發生和傳播視為過程與性質；劉偉等[8]、李成兵等[9]和何祥等[10]均針對道路運輸網絡的級聯失效進行了不同方向的研究。以上研究方法是結合復雜網絡的拓撲結構或通過分析網絡關鍵節點來識別網絡的魯棒性，沒有將網絡節點在動態交通流量分配過程中的狀態因素進行細化考慮。

基于復雜網絡理論建立民航網絡路網模型，以網絡節點容量-負載的級聯失效標準來仿真交通流量的動態分配，從而建立交通流量動態分配模型，并建立不同攻擊策略下的網絡級聯失效模型，以中南地區民航網絡為例，對其網絡魯棒性進行研究。

1 理論概述

1.1 級聯失效現象

級聯失效現象就像是復雜網絡中的“多米諾骨牌”，概括地說是指在網絡中當節點受到攻擊或突發狀況使得其無法正常工作或者徹底癱瘓后，它的負載量便會按一定原則重新分配給與其相連的節點，從而可能導致部分節點的負載超過自身的承受范圍，隨之也發生故障的一個連續故障過程。當失效狀況過于嚴重時，可能會導致某個地區甚至整個網絡陷入癱瘓。在分析級聯失效現象時，節點可分為正常、暫停和失效三種狀態。正常狀態是指節點可以正常運行；失效狀態是指節點完全喪失功能，相當于節點移除；而暫停狀態是指節點功能受損或者超負荷運行，在一定時間內可以恢復到正常狀態。

研究將整個網絡的級聯失效過程分為正常運轉，失效傳播和傳播終止三個階段，其級聯失效過程如圖1所示。

圖1 網絡級聯失效過程Fig.1 Network cascade failure process

1.2 負載分配原則

現今的負載重分策略有許多種，如平均分配策略、局部擇優分配等，由于現實網絡的情況復雜，許多分配策略并不適用于民航網絡。設定失效節點為a，與其連接的節點分別為b,c, …，n，則設定負載分配的原則如下。

(1)統計a-b,a-c,…，a-n等航線的日航班數，分別記為X1,X2,…,Xn；將航班數相加求和記為X。

(2)每條邊的權值為該邊航班數占a節點總航班數的比重，即X1/X,X2/X，…，Xn/X，當節點a失效后，其負載按權值分別流向節點b,c，…，n。

(3)若連接節點b暫停，則超出b承受范圍的負載按上述步驟分別流向除a以外與b相連接的其他節點。

1.3 級聯失效過程概述

現選用動態級聯失效中的負載容量模型去分析級聯失效現象，依據已有數據和參數給予網絡中每一個節點初始負載量以及它的最大容量值。在未進行破壞前每一個節點所承擔的負載量都小于它的最大容量值，但當隨機攻擊或者蓄意攻擊致使某個節點移除后，它的負載量便依據設置的分配原則重新分配給其他節點，這便可能導致部分節點的負載超出它的最大容量值，又產生下一層的負載分配，直至影響結束。

失效傳播過程概述如下：選擇攻擊某一節點，那么該節點處于移除狀態，其出入的負載均以出量分攤；負載按一定分配原則分別分配給與失效節點有連接的節點，對于這些節點來說分配量按入量進入；如果有因此暫停的節點，則找出新的暫停點并將其超出量按出量繼續向下分配，直至傳播停止，級聯失效現象結束。

2 級聯失效現象仿真流程

2.1 中南地區民航網絡

由于人口狀況和經濟發展等原因，中南地區民航網絡的人流量和貨運量在全國范圍內均占據了較大比重。以中南地區民航網絡作為研究的對象，將它的28個機場作為節點進行建模。相較其他類型的網絡，中南地區民航網絡有較大的特殊性，包括開放性、魯棒性和演化性等。由此在構建模型前特做出如下假設。

(1)不考慮選取范圍以外的節點和邊。

(2)該民航網絡視為無向加權網絡，并且在攻擊后負載量將按權值進行分配。

(3)攻擊僅進行一次，不考慮多次攻擊且節點視為不可自我修復。

用G=(V,E)來描述中南地區的民航網絡圖，其中V為點集，節點數m為28；E為邊集，邊數n為132。網絡中邊的權值用r表示，它由a機場和b機場之間的航班數占其中一個機場總航班數的比率來決定。圖2為中南地區民航網絡的仿真模型圖。

圖2 中南地區民航網絡圖Fig.2 Civil aviation network map of Central and Southern China

2.2 級聯失效仿真實驗過程

(1)在網絡模型G中，設定初始各個機場節點的正常日負載量為l(vi)?！?017年民航機場生產統計公報》中顯示，中南地區占全國旅客吞吐量的24.2%，則可得出各機場在中南地區的平均日負載量如表1所示。

表1 中南地區各節點日負載量

(2)節點i的最大容量記為Cimax，記為

Cimax=αl(vi) (1)

式(1)中：α為節點的容量系數；l(vi)為i節點的日負載量。

(3)對節點進行隨機攻擊，求出中南地區民航網絡中28個節點的介數和度值以后進行排序，蓄意攻擊介數值最大和度值最大的節點。

(4)將失效節點的正常日負載量按權值大小分配給與其連接的各個節點，隨后與失效節點相連的節點負載lt+1(vi)變為

lt+1(vi)=l(vi)+ril(v失效) (2)

式(2)中：ri為當前節點與失效節點相連邊的權值；l(v失效)為失效節點的日負載量。

隨后將處于暫停狀態的節點k的多余負載再次按權值大小分配給除失效和暫停以外的與其連接的節點lt+2(vj)，即

lt+2(vj)=[lt+1(vk)-Ckmax]rj(3)

式(3)中：lt+1(vk)為暫停節點k的日負載量；Ckmax為暫停節點k的最大容量；rj為節點k到節點j相連邊的權值。

在判斷它們是否超過最大容載量后統計暫停節點數，繼續進行計算。將失效和所有暫停狀態的節點集合記為FP。

(5)當出現以下兩種情況時，均表示蓄意攻擊對該網絡的級聯失效影響結束：一是除了FP集合外，所有節點都保證節點負載量小于最大容量時，級聯失效影響結束；二是網絡中所有節點的最大容量均小于負載量，整個網絡癱瘓。

(6)對不同攻擊策略的數值結果進行統計，并對中南地區民航網絡仿真模型的級聯失效現象進行分析，研究樣本網絡的穩定性并分析其魯棒性。

3 隨機攻擊模式下級聯失效現象分析

在隨機攻擊模式中，民航網絡一般不易發生級聯失效現象。主要是因為如果沒有攻擊到重要的節點，負載量很輕易地就可以分攤到整個網絡，對于網絡來說不構成較大影響。在本節中，選擇進行五次隨機攻擊，綜合幾次的結果進行分析。

3.1 隨機攻擊下級聯失效仿真流程

隨機攻擊下級聯失效仿真流程如圖3所示。

圖3 隨機攻擊下級聯失效仿真流程Fig.3 Random attack on subordinate failure simulation process

3.2 隨機攻擊結果分析

基于民航網絡的特殊性，即節點的度固定不變且節點的位置不會發生變化，將節點容量系數α的大小作為仿真實驗的變量。利用軟件進行隨機取點，隨后去除相應點并模擬隨機攻擊，最后進行統計。隨機攻擊的節點分別為7(三亞)、9(桂林)、12(張家界)、14(湛江)和20(惠州)。由表1可知每個被攻擊節點的負載量，攻擊網絡中某一節點后其負載會按權值分配給與其連接的節點，當節點的現負載量剛好等于當時的最大負載量時，節點處于臨界值歸為正常狀態。圖4為不同容量系數下五次隨機攻擊對網絡的影響。

圖4 五次隨機攻擊的網絡級聯失效現象Fig.4 Network cascade failure of five random attacks

在對節點14[圖4(d)]和節點20[圖4(e)]攻擊后，產生的級聯失效現象是完全相同的，即當α=1.1時，只有一個節點暫停并且隨后這個節點進行了恢復，而當α=1.2和α=1.3時，均未導致任何節點喪失功能；攻擊節點9[圖4(b)]后的狀況與上述兩個節點類似，隨著α的增大，第一次迭代隨之暫停的節點在不斷減少，并且第二次迭代開始均再沒有節點繼續暫停；攻擊節點7[圖4(a)]后，當α=1.1時第一次迭代有7個節點暫停，隨后的迭代中穩定在5個并沒有新的節點繼續暫停，當α=1.2時前8次迭代均只有2個節點暫停，而后將負載分配結束后也逐漸恢復正常，α=1.3的現象與其類似；在隨機攻擊中導致暫停節點最多的是節點12[圖4(c)]，當α=1.1時兩次迭代即導致9個節點暫停，當α=1.3時則暫停節點明顯變少。

3.3 分析隨機攻擊模式下級聯失效現象

(1)當隨機攻擊的對象不同時導致的結果可能會有很大的差別，也可能極為相似。

(2)節點7和節點12的負載量比其他節點的負載量大，導致暫停的節點也更多，可推測攻擊負載量大的節點比攻擊負載量小的節點更有效。

(3)容量系數的改變對結果有很大影響，當節點容量不斷增大時，對于該網絡來說隨機攻擊產生的影響會越來越小，即節點容量增加至一定數值時網絡很難發生級聯失效現象。

4 蓄意攻擊模式下級聯失效現象分析

在蓄意攻擊中民航網絡極易發生級聯失效現象，究其原因基本在于兩點：一是中國各個機場的人流量每年都在增加，這也不斷挑戰著機場的負載能力，當蓄意攻擊網絡中重要節點時，巨大的人流量被分配給其他相連機場，極易使其他相連機場進入暫停狀態；二是部分機場為了接納更大的人流量會進行擴容重建，使得民航網絡中節點之間的容量差值日益增大，當容量較小的機場被分配過多的負載時也極易導致其不能正常運行。所以基于蓄意攻擊這一模式，可以對民航網絡的級聯失效現象進行更深入研究。

4.1 蓄意攻擊級聯失效仿真流程

蓄意攻擊與隨機攻擊的仿真過程基本一致，但攻擊對象有了針對性，即在實驗中選擇網絡中的重要節點進行攻擊。分別選擇蓄意攻擊介數值最高和度數最大的節點，綜合兩類的結果進行級聯失效現象分析。

4.2 對介數值最大的節點蓄意攻擊結果分析

蓄意攻擊中將節點容量系數α的大小作為仿真實驗的變量。經過計算得出介數值最大的是節點5，利用單個節點失效的方法進行分析。其結果如圖5所示。

圖5 蓄意攻擊介數值最大的節點Fig.5 Deliberately attack the node with the largest interface value

當α=1.1時，網絡在第1次迭代時有13個節點變成暫停狀態，第2次迭代則有3個節點暫停，直到第10次迭代則20個節點處于暫停狀態，這是因為節點最大容載量過小，整個網絡非常脆弱；當α=1.2時，第1次迭代時有7個節點暫停，隨后的迭代沒有導致其他的節點轉變為暫停狀態，網絡同樣比較脆弱；當α=1.3時，網絡在第1次迭代時只有1個節點暫停，隨后暫停節點將超出負載分配后則又恢復正常，再沒有節點暫停。通過圖5可以發現，當容量系數增大，迭代次數相同時節點的存活率也隨之提高。并且特別的是，當容量系數α=1.3時候，網絡在暫停了1個節點后便在沒有節點繼續暫停。

4.3 對度值最大的節點蓄意攻擊的結果分析

經過統計發現網絡中度值最大的是節點2，攻擊該節點后其負載會按權值分配給與其連接的節點，其結果如圖6所示。

圖6 蓄意攻擊度值最大的節點Fig.6 Deliberately attack the node with the highest degree value

當α=1.1時，網絡在第1次迭代時則有25個節點暫停，第2次迭代后全網的所有節點便處于暫停狀態，顯而易見整個網絡非常脆弱；當α=1.2時，第1次迭代時22個節點處于暫停狀態，隨后的第2次到第5次迭代陸續有節點暫停，直至第6次迭代后依然是全面暫停狀態，網絡依然比較脆弱；當α=1.3時，網絡在第1次迭代時有14個節點處于暫停狀態，第2次迭代后暫停的節點數增加至20個，隨后經過不斷迭代，暫停的節點數穩定在了25個節點，并沒有導致全網暫停。通過圖6可以發現，盡管容量系數不斷增加，但當攻擊網絡中度值最大的節點2時，網絡都是處于全面暫停和瀕臨暫停的狀態。

4.4 綜合蓄意攻擊結果分析級聯失效現象

由兩個策略進行蓄意攻擊的過程和級聯失效的結果可以得到以下幾個推論。

(1)當容量系數增大時，節點的承受能力也會相應增大，級聯失效對該網絡的影響會相應減小，網絡也擁有更高的穩定性。

(2)當移除節點的負載越大，則會導致網絡中暫停的節點越多。

(3)在級聯失效現象中網絡的穩定性與暫停節點數量無關，而與暫停節點的負載量密切相關。

(4)當節點容量足夠大時，蓄意攻擊介數值最大的節點對網絡基本不產生影響；若蓄意攻擊度值最大的節點，則會對整個網絡帶來較大影響。

(5)對于中南地區民航網絡來說，攻擊度值最大的節點比攻擊介數值最大的節點更容易造成網絡癱瘓。

5 結論

分別從隨機攻擊和蓄意攻擊這兩個角度分析中南地區民航網絡的級聯失效現象，通過仿真實驗發現蓄意攻擊比隨機攻擊產生的破壞更嚴重。

通過級聯失效現象的仿真結果可以分析出當節點的最大容量在日吞吐量的1.3倍以上時，節點的承受能力增強，緩解或抑制了中南地區民航網絡的級聯失效現象，使得面對隨機攻擊有較強的魯棒性，當蓄意攻擊介數值最大的節點時也會具有良好的魯棒性，不過面對蓄意攻擊度值最大的節點時魯棒性依然較差；其次，重視加強發展中小型機場，擴建的同時增加更多的航線，對它們加強建設也可以降低蓄意攻擊時級聯失效現象對該網絡魯棒性的影響；同樣要注重對大型機場的維護和更全面先進的建設?？傮w來講，重點保障度值較大的核心機場正常運行與不斷完善中小型機場的航線和基礎設施相結合，才能更好地提高中南地區民航網絡的魯棒性。