考慮節點過載的復雜網絡級聯失效模型

郝羽成, 李成兵, 魏 磊

(1. 北京交通大學交通運輸學院, 北京 100044; 2. 內蒙古大學交通學院, 內蒙古 呼和浩特 010070;3. 北京航空航天大學交通科學與工程學院, 北京 100191)

0 引 言

隨著網絡的規模化、復雜化,微小故障均可能會對網絡的抗毀性產生嚴重影響。由于網絡中某節點失效,造成負載重新分配使得其他節點相繼失效,如此循環易造成網絡大規模癱瘓。在交通網絡[1-2]、電力網絡[3-5]、通信網絡[6]、指揮控制網絡[7-8]、供水網絡[9-10]方面,級聯失效現象已引起學者們的關注。但是,現實中節點通常存在些許冗余能力,并非負載超過其容量就必定失效,這種情況即為節點的過載狀態。因此,如何在級聯失效過程中減少過載節點數并緩解其承擔的負載量以增強抗毀性,將成為網絡動力學中研究的重要問題。

在級聯失效模型方面,文獻[11]最早提出負載容量級聯失效模型,根據節點度為負載賦值并進行仿真。文獻[12]提出非線性容量負載模型,從網絡費用以及魯棒性兩方面對多種網絡模型進行研究。文獻[13]分別對小世界網絡與無標度網絡的級聯失效現象進行研究,發現兩種網絡在不同情況下所呈現的抗毀性相反。在加權網絡模型方面,文獻[14-15]分別以節點度、介數為依據進行加權,結果表明參數在特定值下網絡抵抗級聯失效的魯棒性最強。文獻[16]基于介數、節點度提出了一種連邊加權模型,發現特定參數組合可以增強網絡的魯棒性。文獻[17]根據節點與相鄰節點的權重提出了一種級聯失效模型。在失效節點的負載分配范圍方面,文獻[18]提出了一種負載局域分配策略的級聯失效模型,發現無標度網絡構建的參數與魯棒性相關。文獻[19-20]根據負載局域、全局分配策略進行了級聯失效仿真。在級聯失效優化方面,文獻[21-22]分別從容量及其參數兩方面對級聯抗毀性進行優化。文獻[23]以進化算法對復雜網絡進行演化,發現聚類系數、模塊化、路徑距離對于抵抗級聯失效現象存在顯著影響。在相依網絡方面,文獻[24-26]分別對小世界網絡模型與無標度網絡模型進行了級聯失效仿真。

綜上所述,既有文獻大多未考慮節點的過載狀態,失效均為確定性的模式,且缺乏對過載節點負載疏散的探討。然而在現實系統中個體均具有一定彈性。譬如,在交通網絡中交叉口的負載大于容量時,交叉口并非完全堵死,只是其運行效率降低,負載的持續增加使其更易失效。基于此,本文考慮過載狀態并進行研究,以過載系數描述節點對于負載的冗余能力,以失效概率描述失效的不確定性,以使級聯失效模型更貼近于實際網絡中失效的情況,從而研究結果具有著較強的實用價值。此外,這有助于拓展級聯失效研究的思路,對于網絡抵御級聯失效、增強抗毀性均存在著重要的理論以及現實意義。

1 考慮節點過載狀態的級聯失效模型

在既有的級聯失效模型中,初始階段所有節點的負載均小于其容量,節點處于正常狀態;若負載大于其容量,則節點為失效狀態。在此,考慮節點對于負載的冗余能力,即為節點的過載狀態。即使負載大于容量,節點也并非會一定失效,只是運行效率降低并且存在著一定的失效風險。基于此,對級聯失效模型進行如下改進:

步驟1假設網絡中節點i的容量與負載成正比,則容量ci計算如下：

ci=(1+αi)li

(1)

式中,αi為第i個節點的容忍系數,且αi>0。li為節點i的負載,li計算如下：

(2)

式中,di為節點i的節點度；β為調節負載的參數。

步驟2對節點i進行蓄意攻擊,即每次選擇負載最大的節點進行攻擊。

步驟3失效節點負載分配過程。將失效節點i的負載li以節點度策略分配至相連節點j,并且更新相連節點j的負載。

步驟4過載狀態及失效狀態判斷過程。以過載系數δ描述節點i對于額外負載的處理能力,則其可承受的最大負載為δci。當負載li大于δci時,節點必然失效;當負載li大于ci且小于δci時,節點以一定的概率失效。因此,節點的過載系數越大,網絡抗毀性在一定程度上就越強。通過以上分析可知,節點可承受的最大負載需大于其容量,則δ>1。根據式(3)判斷相連節點j的狀態。

(3)

式中,rand為0至1的隨機數；pj為節點j的失效概率。由于在實際情況中,節點對于額外的負載存在著不同的處理能力。部分情況下,節點對于小范圍的過載較為敏感,失效的概率增長較快;除此之外也存在著節點對于小范圍過載,失效概率增長緩慢的情況。因此,運用分布系數ω對該特性進行刻畫,即通過ω調節失效概率pj的分布。其中,pj計算如下:

(4)

通常情況下,負載超出容量的值越大,節點越易失效。因此,pj應是單調遞增的函數,則ω>0。

步驟5過載節點負載分配過程。由于過載節點需及時對負載進行疏散,因此以剩余系數λ描述分配負載后節點自身所承擔的負載量。當剩余系數λ=0時,過載節點j將當前所有負載進行分配;當剩余系數λ=1,過載節點j將多余的負載進行分配,以保證節點恰好處于正常狀態,則剩余系數應滿足0≤λ≤1。過載節點j分配至相連非失效節點k的分配量Δljk計算如下:

Δljk=(lj-λcj)Πjk

(5)

式中,Πjk為過載節點j對相連非失效節點k的分配比例。

步驟6判斷是否存在失效節點,若存在轉至步驟3,否則轉至步驟7。

步驟7由于節點處于過載狀態,其負載已超過容量并非與正常狀態相同,在實際情況中則該節點運行效率低下。為了更好表示過載這一狀態,運用修正后最大連通子圖的相對大小G進行抗毀性評估,計算式為

(6)

式中,N為網絡中的節點數;Φ為網絡中未失效節點的集合;若節點h為正常狀態,則sh=1;若節點h為過載狀態,則

步驟8判斷攻擊節點數是否滿足既定要求,若是則級聯失效模型結束,否則轉至步驟2。

根據以上敘述,可以發現容忍系數越大,節點可承擔的負載越多,在一定程度上網絡的抗毀性越強。但是在交通、電力等實際網絡中,出于成本因素節點的容量難以無限制增加,因此網絡的構建成本也需進行考慮。在不同的負載分配機制下,當網絡具有相同的抗毀性而能夠避免級聯失效現象時,容忍系數較小的網絡則其構建成本較小。基于此,本文運用平均容忍系數αc對網絡的構建成本進行度量。具體步驟如下:

步驟1對于給定的容忍系數增量Δα,令第t次第i個節點的容忍系數αi為增量Δα,其中i=1。

步驟2對于節點i,根據αi以及相連節點j的負載lj計算其容量cj。

步驟3攻擊節點i,并進行失效節點負載分配過程、過載狀態及失效狀態判斷過程和過載節點負載分配過程。

步驟4判斷是否存在失效節點,若存在則αi=αi+Δα,并返回步驟2;否則轉至步驟5。

2 過載節點負載分配策略

在級聯失效過程中,失效節點負載的分配策略影響著網絡的抗毀性。同樣,若未及時對過載節點的負載進行疏導,可能使其失效并造成級聯失效現象,進而也會影響著網絡的抗毀性。因此,本文從以下6個方面對過載節點的負載分配問題進行研究。

(1) 平均分配策略(average distribution,AD)

當過載節點j存在非失效節點k相連時,將負載平均分配至相連非失效節點k。則節點j分配至節點k的分配比例Πjk計算如下:

(7)

式中,m為與過載節點j相連的非失效節點數。

(2) 節點度分配策略(degree distribution,DD)

由于節點度反應了節點所連的邊數,因此節點度越大其分配的負載也就越大。則過載節點j分配至相連非失效節點k的分配比例Πjk計算如下:

(8)

式中,Γj為與過載節點j相連非失效節點的集合。

(3) 緊密度分配策略(tightness distribution,TD)

緊密度反應了節點到達其他節點的難易程度,節點的緊密度越大,越易到達其他節點,負載越易疏散。則過載節點j分配至相連非失效節點k的分配比例Πjk計算如下:

(9)

式中,tk表示節點k的緊密度。

(4) 介數分配策略(betweenness distribution,BD)

介數反應了節點在網絡中的重要程度,節點的介數越大其重要程度越高。則過載節點j分配至相連非失效節點k的分配比例Πjk計算如下:

(10)

式中,bk表示節點k的介數。

(5) 剩余負載分配策略(surplus load distribution,SLD)

在級聯失效過程中,節點的剩余負載越大,其相應可承擔的負載也就越多。則過載節點j分配至相連正常節點n的分配比例Πjn計算如下:

(11)

(6) 混合分配策略(mixed distribution,MD)

將以上幾種不同的過載分配策略進行加權組合,則可得到混合分配策略。

3 仿真實驗

鑒于實際網絡均具有著一定的無標度特性[27],因此本文構建Barabasi-Albert(BA)無標度網絡模型進行仿真。在BA無標度網絡模型中,初始狀態是m0個節點的網絡,每次迭代引入一個新節點,以節點度計算所得的概率為基礎對m(m≤m0)個節點進行連接。本文構建節點數為500的BA無標度網絡模型,令m0=5,m=5,若無特殊說明在文中容忍系數αi=1 (i=1,2,…,N),調節負載參數β=2,仿真各自獨立運行50次取平均值。分別從過載節點負載分配策略、過載系數、分布系數、剩余系數、平均容忍系數等方面展開對抗毀性的研究。

3.1 過載節點負載分配策略對網絡抗毀性的影響

為研究過載分配策略對抗毀性的影響,令過載系數δ=1.5,分布系數ω=1,剩余系數λ=1,對過載節點采取不同的分配策略。在仿真中DD、SLD策略下的抗毀性相對較優,因此MD策略采取以上兩種策略進行加權。通過測試發現當DD、SLD策略的權重分別取0.3、0.7時,MD策略相對較好,因此MD策略由DD、SLD兩種策略加權所得。不同的過載節點負載分配策略仿真結果如圖1所示。

圖1 不同過載節點負載分配策略下抗毀性對比圖Fig.1 Comparison of invulnerability under different overload node load assignment strategies

由圖1可知,未考慮過載節點負載分配策略時,由于超過容量的負載沒能被及時分擔使得節點更易失效,因此網絡的抗毀性最差。AD策略是所有分配策略中效果最不理想的;而SLD策略與MD策略下的抗毀性均較佳。這是由于AD策略忽視了相連節點的差異性,剩余負載較小的節點存在著較高的失效風險。相反,SLD策略根據剩余負載進行分配,從而失效風險降低。此外,MD策略在攻擊過程中均使得網絡保持著較強的抗毀性,這是由于該策略一方面考慮了節點的度,即分散負載的能力,另一方面考慮了節點的剩余負載,即可承受負載的能力。因此,MD策略相對較佳。綜上所述,對過載節點進行合理的疏導,能夠增強網絡的抗毀性,減少級聯失效的影響。

3.2 過載系數對網絡抗毀性的影響

為探究過載系數δ對網絡抗毀性的影響,令過載節點負載分配策略為DD策略,分布系數ω=1,剩余系數λ=1。對過載系數δ取不同的值,仿真結果如圖2所示。

圖2 不同過載系數下抗毀性對比圖Fig.2 Comparison of resistance under different overload coefficient

由圖2可知,當網絡未考慮過載狀態時,顯然級聯失效對網絡的影響是較大的,僅攻擊3次就已崩潰。但是當δ=1.5時,抗毀性相對于δ=1時有了顯著提升,攻擊9次之后才完全崩潰。隨著δ增大,抗毀性總體上也呈現出了增強的趨勢。這是由于δ越大,節點對于額外負載的處理能力也就越強,因此抗毀性有了一定提升。但是當δ=3.5,δ=4時,兩者差距不大。

綜上所述,當節點存在小范圍的過載能力時,可顯著提高抗毀性；而δ增加到一定程度時,其對抗毀性提升的貢獻降低。現實網絡中,提升節點的過載能力需考慮其構建成本,因此單純增加δ是不合理的。

3.3 分布系數對網絡抗毀性的影響

為研究分布系數ω對網絡抗毀性的影響,令過載節點負載分配策略為DD策略,過載系數δ=1.5,剩余系數λ=1。對分布系數ω取不同的值以進行研究,仿真結果如圖3所示。由圖3可知,當攻擊數少于4時,分布系數ω對抗毀性沒有存在影響。當攻擊數超過4時,ω=0.2的情況下級聯失效對網絡抗毀性所造成的影響最大,抗毀性呈現出直線下降的趨勢;而ω=2與ω=2.5時,抗毀性均相對較強。隨著ω的不斷增大,抗毀性也在增強。這是由于當ω較小時,負載即使小部分超過其容量,也會造成較高的失效概率,從而易引起級聯失效現象。因此，在實際網絡中必須對分布系數較小的情況加以重視。當ω較大時,負載在一定范圍內超過容量,節點失效概率仍可保持較小的狀態,因此可有效遏制節點的失效個數,控制了級聯失效對抗毀性的影響。

圖3 不同分布系數下抗毀性對比圖Fig.3 Comparison of damage resistance under different distribution coefficients

3.4 剩余系數對網絡抗毀性的影響

為探究剩余系數λ對網絡抗毀性的影響,令過載節點負載分配策略為DD策略,過載系數δ=1.5,分布系數ω=1,對λ取不同的值。由于在攻擊次數小于4次時G的變化相似,因此只列出攻擊次數為4～10次的圖像,仿真結果如圖4所示。

圖4 不同剩余系數下抗毀性對比圖Fig.4 Comparison of destruction resistance under different residual coefficients

由圖4可知,當剩余系數λ=0.5時，網絡的抗毀性最差,級聯失效所造成的影響較大。而λ=0.9時,在攻擊過程中抗毀性最強。這是由于λ決定著過載節點分配之后負載的剩余量。當λ較小時，過載節點分配至相連節點的負載較大,過載節點雖可變為正常狀態,但易使相連節點過載或是失效；當λ較大時,過載節點分配至相連節點的負載較少,承擔部分負載又易過載或失效。因此,λ存在某一值才能夠使得節點保留一定的冗余能力來處理負載,同時又不會對相連節點產生過多影響。

由圖4可知,在DD策略下λ=0.9時，網絡抗毀性最強。為探究在不同的過載節點分配策略中,λ=0.9時抗毀性仍能否達到最強,因此令過載系數δ=1.5,分布系數ω=1,對不同的λ、過載節點負載分配策略進行仿真,蓄意攻擊10個節點對G取平均值,仿真結果如圖5所示。

圖5 不同剩余系數、過載節點負載分配策略下抗毀性對比圖Fig.5 Invulnerability comparison of load distribution strategies with different residual coefficients and overload nodes

由圖5可知,隨著初期λ不斷增大,不同策略下的抗毀性均呈現出上升趨勢。并且當λ=0.9時,不同過載節點負載分配策略下的G取值0.6～0.9;而λ=0.1時,G僅維持在0.3～0.5。這表明對于m0=5、m=5的BA無標度網絡而言,在不同的過載節點負載分配策略中λ=0.9時，網絡的抗毀性相對較好。

3.5 過載節點負載分配策略與平均容忍系數關系

為探究不同過載節點負載分配策略與平均容忍系數的關系,令過載系數δ=1.5,分布系數ω=1,剩余系數λ=1,容忍系數增量Δα=0.01,最大迭代次數tmax=50,計算不同過載節點負載分配策略下平均容忍系數αc的值,結果如圖6所示。

圖6 不同過載節點負載分配策略下平均容忍系數對比圖Fig.6 Comparison of average tolerance coefficients under different overload node load allocation strategies

由圖6可知,在AD策略以及TD策略下網絡的平均容忍系數αc均較高。這是因為網絡中節點緊密度的值差異較小,所以兩者的結果相似。而在DD、BD、SLD、MD這4種策略中,αc的值均在0.012之下,顯著低于AD策略以及TD策略。這是由于在AD策略以及TD策略下,過載節點的負載會較為平均地分配至與其相連的節點,為了避免產生級聯失效現象,容量較小的節點需擁有較大的容忍系數,因而其他4種策略可使得網絡的構建成本較低。此外,由圖6可知，BD策略下的αc值略小于其他策略。通常,網絡的構建成本與αc存在著正相關的關系，這表明過載節點采取AD策略、TD策略,其網絡的構建成本較高,而其他4種策略均可使網絡構建成本較低。

4 結 論

本文提出了一種考慮節點過載狀態的級聯失效模型,從過載節點負載分配策略、過載系數、分布系數、剩余系數4個方面進行了研究。研究結論如下:

(1) 在單種分配策略中,SLD策略使得網絡的抗毀性較強，而MD策略兼顧了節點疏散負載以及承擔負載的能力,因此在攻擊過程中網絡始終保持著較強的抗毀性；

(2) 在一定程度內提升過載系數δ,能夠增強節點對于負載的處理能力,但過載系數增加到一定程度時,網絡抗毀性沒有顯著提高；

(3) 當分布系數ω較大時,網絡保有較強的抗毀性;分布系數ω較小時,則相反；

(4) 對于不同的過載節點負載分配策略而言,剩余系數存在某一值可使得BA無標度網絡的抗毀性達到最強；

(5) DD、BD、SLD、MD這4種過載節點負載分配策略可使得平均容忍系數αc較小,網絡的構建成本較低。