郝羽成, 李成兵, 魏 磊

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

0 引 言

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

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

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

1 考慮節(jié)點過載狀態(tài)的級聯(lián)失效模型

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

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

ci=(1+αi)li

(1)

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

(2)

式中,di為節(jié)點i的節(jié)點度；β為調(diào)節(jié)負載的參數(shù)。

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

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

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

(3)

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

(4)

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

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

Δljk=(lj-λcj)Πjk

(5)

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

步驟6判斷是否存在失效節(jié)點,若存在轉(zhuǎn)至步驟3,否則轉(zhuǎn)至步驟7。

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

(6)

式中,N為網(wǎng)絡中的節(jié)點數(shù);Φ為網(wǎng)絡中未失效節(jié)點的集合;若節(jié)點h為正常狀態(tài),則sh=1;若節(jié)點h為過載狀態(tài),則

步驟8判斷攻擊節(jié)點數(shù)是否滿足既定要求,若是則級聯(lián)失效模型結(jié)束,否則轉(zhuǎn)至步驟2。

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

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

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

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

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

2 過載節(jié)點負載分配策略

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

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

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

(7)

式中,m為與過載節(jié)點j相連的非失效節(jié)點數(shù)。

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

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

(8)

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

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

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

(9)

式中,tk表示節(jié)點k的緊密度。

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

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

(10)

式中,bk表示節(jié)點k的介數(shù)。

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

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

(11)

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

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

3 仿真實驗

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

3.1 過載節(jié)點負載分配策略對網(wǎng)絡抗毀性的影響

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

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

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

3.2 過載系數(shù)對網(wǎng)絡抗毀性的影響

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

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

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

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

3.3 分布系數(shù)對網(wǎng)絡抗毀性的影響

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

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

3.4 剩余系數(shù)對網(wǎng)絡抗毀性的影響

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

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

由圖4可知,當剩余系數(shù)λ=0.5時，網(wǎng)絡的抗毀性最差,級聯(lián)失效所造成的影響較大。而λ=0.9時,在攻擊過程中抗毀性最強。這是由于λ決定著過載節(jié)點分配之后負載的剩余量。當λ較小時，過載節(jié)點分配至相連節(jié)點的負載較大,過載節(jié)點雖可變?yōu)檎顟B(tài),但易使相連節(jié)點過載或是失效；當λ較大時,過載節(jié)點分配至相連節(jié)點的負載較少,承擔部分負載又易過載或失效。因此,λ存在某一值才能夠使得節(jié)點保留一定的冗余能力來處理負載,同時又不會對相連節(jié)點產(chǎn)生過多影響。

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

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

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

3.5 過載節(jié)點負載分配策略與平均容忍系數(shù)關系

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

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

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

4 結(jié) 論

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

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

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

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

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

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