基于節(jié)點狀態(tài)的中南地區(qū)民航網(wǎng)絡級聯(lián)失效

謝本凱， 黃龔迪， 李 琴， 林?？?/p>

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

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

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

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

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

1 理論概述

1.1 級聯(lián)失效現(xiàn)象

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

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

圖1 網(wǎng)絡級聯(lián)失效過程Fig.1 Network cascade failure process

1.2 負載分配原則

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

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

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

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

1.3 級聯(lián)失效過程概述

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

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

2 級聯(lián)失效現(xiàn)象仿真流程

2.1 中南地區(qū)民航網(wǎng)絡

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

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

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

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

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

圖2 中南地區(qū)民航網(wǎng)絡圖Fig.2 Civil aviation network map of Central and Southern China

2.2 級聯(lián)失效仿真實驗過程

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

表1 中南地區(qū)各節(jié)點日負載量

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

Cimax=αl(vi) (1)

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

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

(4)將失效節(jié)點的正常日負載量按權值大小分配給與其連接的各個節(jié)點，隨后與失效節(jié)點相連的節(jié)點負載lt+1(vi)變?yōu)?/p>

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

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

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

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

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

在判斷它們是否超過最大容載量后統(tǒng)計暫停節(jié)點數(shù)，繼續(xù)進行計算。將失效和所有暫停狀態(tài)的節(jié)點集合記為FP。

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

(6)對不同攻擊策略的數(shù)值結果進行統(tǒng)計，并對中南地區(qū)民航網(wǎng)絡仿真模型的級聯(lián)失效現(xiàn)象進行分析，研究樣本網(wǎng)絡的穩(wěn)定性并分析其魯棒性。

3 隨機攻擊模式下級聯(lián)失效現(xiàn)象分析

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

3.1 隨機攻擊下級聯(lián)失效仿真流程

隨機攻擊下級聯(lián)失效仿真流程如圖3所示。

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

3.2 隨機攻擊結果分析

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

圖4 五次隨機攻擊的網(wǎng)絡級聯(lián)失效現(xiàn)象Fig.4 Network cascade failure of five random attacks

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

3.3 分析隨機攻擊模式下級聯(lián)失效現(xiàn)象

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

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

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

4 蓄意攻擊模式下級聯(lián)失效現(xiàn)象分析

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

4.1 蓄意攻擊級聯(lián)失效仿真流程

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

4.2 對介數(shù)值最大的節(jié)點蓄意攻擊結果分析

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

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

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

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

經(jīng)過統(tǒng)計發(fā)現(xiàn)網(wǎng)絡中度值最大的是節(jié)點2，攻擊該節(jié)點后其負載會按權值分配給與其連接的節(jié)點，其結果如圖6所示。

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

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

4.4 綜合蓄意攻擊結果分析級聯(lián)失效現(xiàn)象

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

(1)當容量系數(shù)增大時，節(jié)點的承受能力也會相應增大，級聯(lián)失效對該網(wǎng)絡的影響會相應減小，網(wǎng)絡也擁有更高的穩(wěn)定性。

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

(3)在級聯(lián)失效現(xiàn)象中網(wǎng)絡的穩(wěn)定性與暫停節(jié)點數(shù)量無關，而與暫停節(jié)點的負載量密切相關。

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

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

5 結論

分別從隨機攻擊和蓄意攻擊這兩個角度分析中南地區(qū)民航網(wǎng)絡的級聯(lián)失效現(xiàn)象，通過仿真實驗發(fā)現(xiàn)蓄意攻擊比隨機攻擊產生的破壞更嚴重。

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