段東立

（西安武警工程大學裝備工程學院，西安710008）

0 引言

連鎖故障普遍發(fā)生在各種關(guān)鍵生命線系統(tǒng)網(wǎng)絡(luò)中，大規(guī)模的連鎖故障一旦發(fā)生，往往具有極強的破壞力和影響力［1－2］，例如2008年初中國南方電力網(wǎng)絡(luò)的崩潰、北美電力網(wǎng)大崩潰事故、因特網(wǎng)阻塞、2012年印度電網(wǎng)的兩次崩潰事故以及2013年青島輸油管線的爆炸等都可以從某種程度上認為是因連鎖故障所導致的災難，這些災難造成的損失常常十分巨大。因此，網(wǎng)絡(luò)連鎖故障理論的研究非常重要且具有現(xiàn)實意義。

過載機制的復雜網(wǎng)絡(luò)連鎖故障模型主要包括3個因素：負載模型、容量模型與負載重分策略［3－8］，其中負載重分策略是關(guān)鍵［4］。2002年，Motter與Lai［5］將過載機制連鎖故障引入復雜網(wǎng)絡(luò)的研究，提出了ML模型，假設(shè)每個節(jié)點的容量正比于其初始負載，之后，Wang和Kim［9］在該模型基礎(chǔ)上，提出為初始負載較高的節(jié)點分配更多的容量，Li和Wang［10］認為節(jié)點的容量不僅與其初始負載相關(guān)，還與節(jié)點本身的能力（度）相關(guān)。這些模型的負荷分配規(guī)則為全局重新分配，主要是基于介數(shù)的概念，假設(shè)網(wǎng)絡(luò)中所有信息的傳輸都是基于最短路徑，且節(jié)點失效后網(wǎng)絡(luò)負載以非連續(xù)的方式瞬時調(diào)整到適應(yīng)新網(wǎng)絡(luò)的狀態(tài)（即新網(wǎng)絡(luò)的介數(shù)為網(wǎng)絡(luò)的更新負載），這種機制的主要特征是網(wǎng)絡(luò)中所有節(jié)點都可以瞬時掌握網(wǎng)絡(luò)的全局信息。而實際系統(tǒng)中，網(wǎng)絡(luò)中的節(jié)點很難獲取網(wǎng)絡(luò)的全面信息，例如，在交通網(wǎng)、電力網(wǎng)和計算機網(wǎng)絡(luò)中，節(jié)點之間網(wǎng)絡(luò)流的耦合機制更為廣泛的是最近鄰耦合，交通網(wǎng)絡(luò)中發(fā)生交通擁堵后，擁堵路口交通流只能選擇其最近鄰路段進行分流，Internet網(wǎng)絡(luò)中某個關(guān)鍵路由器失效后，其承擔的數(shù)據(jù)流只能通過鄰近路由器重新路由。根據(jù)該特點，Wang和Chen［11］提出了一個基于最近鄰負載重分配模型，節(jié)點失效后其負載由其最近鄰承載，Wu［12］在該模型基礎(chǔ)上考察了初始負荷強度參數(shù)與網(wǎng)絡(luò)級聯(lián)失效的關(guān)系。Wang［13－15］依據(jù)該最近鄰擇優(yōu)重分規(guī)則提出了一個局域擇優(yōu)重分配負載模型，并定義節(jié)點初始負荷為節(jié)點度數(shù)的函數(shù)以及節(jié)點度數(shù)與鄰居節(jié)點度數(shù)的函數(shù)。該類模型更加關(guān)注網(wǎng)絡(luò)初始負荷的定義及其分布，便于分析網(wǎng)絡(luò)抵御連鎖故障魯棒性與初始負荷模型的關(guān)系。但值得注意的是，該類模型通常假設(shè)初始負荷的分布參數(shù)與負荷分配的均勻性參數(shù)相等，這種假設(shè)是基于網(wǎng)絡(luò)管理與網(wǎng)絡(luò)設(shè)計完全匹配，在實際系統(tǒng)中很難完全達到，且該類模型忽略了網(wǎng)絡(luò)管理措施（負荷分配機制）與負荷分布特征對網(wǎng)絡(luò)魯棒性影響的差異性。

為了擴展上述最近鄰分配機制的連鎖故障模型并考慮上述因素的影響，本文提出了一個基于負載最近鄰偏好重分規(guī)則的復雜網(wǎng)絡(luò)連鎖故障模型。

1 負載重分配模型

過載機制連鎖故障模型可定義為：節(jié)點i失效后網(wǎng)絡(luò)中完好節(jié)點j的負載更新為F′j，判斷F′j與節(jié)點容量Cj的關(guān)系，若F′j＞Cj則節(jié)點j觸發(fā)新一輪的負載重分配，若F′j＜Cj則節(jié)點j在此時間步不失效，直至整個網(wǎng)絡(luò)中所有節(jié)點的負載不超過其本身的容量，連鎖故障過程結(jié)束。該過程中，節(jié)點i失效導致節(jié)點j的負載發(fā)生一次更新

假設(shè)負載增量ΔFj與失效節(jié)點的負載成正比

kj為節(jié)點的度數(shù)，Γi為崩潰節(jié)點i的鄰居節(jié)點集合，β用來控制崩潰節(jié)點負荷的分配均勻性，且β＝0時為均勻共享負載，β＞0時重分偏好于度大的節(jié)點。節(jié)點i的初始負荷Fi與節(jié)點本身的度數(shù)ki相關(guān)，在難以確定實際負荷時可將初始負荷定義為

其中，ρ和τ為可調(diào)參數(shù)，控制節(jié)點初始負荷的強度。根據(jù)ML模型中初始負荷與節(jié)點容量的關(guān)系，將節(jié)點的容量定義為

其中，α為網(wǎng)絡(luò)的容限系數(shù)，表示節(jié)點處理額外負荷的能力。當α足夠大時，任一節(jié)點的失效都不會觸發(fā)連鎖故障，但是受經(jīng)濟與技術(shù)因素的影響，α不可能任意大，所以，可以用臨界值αc表征網(wǎng)絡(luò)抵抗連鎖故障的能力。αc值越小，網(wǎng)絡(luò)抵制連鎖故障的魯棒性越強，當α＞αc時，移除網(wǎng)絡(luò)中的任一節(jié)點都不會觸發(fā)連鎖效應(yīng)。為了量化整個網(wǎng)絡(luò)的魯棒性，也可采用失效節(jié)點的歸一化指標［13，16－19］：

其中，CFi（0≤CFi≤N－1）為節(jié)點i失效觸發(fā)連鎖故障的節(jié)點個數(shù)。

2 理論分析

為避免連鎖故障的發(fā)生，式（6）的條件應(yīng)該被滿足

分析不等式（7），網(wǎng)絡(luò)免疫連鎖故障的容量系數(shù)下界αc可以分別考慮為式（8）的幾種情況。

其中，kmin和kmax分別為網(wǎng)絡(luò)中節(jié)點的最大度和最小度。在實際網(wǎng)絡(luò)系統(tǒng)的設(shè)計與管理中，我們關(guān)心的問題是采用何種網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)承載何種程度的負載以及單個故障時如何分配網(wǎng)絡(luò)負荷，可以使得網(wǎng)絡(luò)魯棒性最強，即αc值最小。為探討不同網(wǎng)絡(luò)拓撲結(jié)構(gòu)（度分布特征）對級聯(lián)失效行為的影響，研究中選用了在現(xiàn)實世界中具有很好的普適性和代表性的兩類網(wǎng)絡(luò)作為級聯(lián)失效的拓撲架構(gòu)，分別是具有泊松分布特征的ER隨機網(wǎng)絡(luò)和具有冪律度分布特征的BA網(wǎng)絡(luò)。

2.1 ER隨機網(wǎng)絡(luò)

ER隨機網(wǎng)絡(luò)是Erd?和Rényi提出的一種網(wǎng)絡(luò)模型，模型中參數(shù)p為兩個節(jié)點之間有邊連接的概率，平均度〈k〉＝ Np，模型度分布較為均勻。ER網(wǎng)絡(luò)可近似認為〈kβ＋1〉≈ 〈k〉β＋1，kmin≈1，kmax≈2〈k〉。因此，在ER隨機網(wǎng)絡(luò)中，網(wǎng)絡(luò)的容限系數(shù)臨界值可表示為

對式（9）進行簡單的分析可以得出以下結(jié)論：

1）當初始負荷強度參數(shù)τ固定，β＝τ可以使得網(wǎng)絡(luò)抵御連鎖故障的魯棒性最好。當β與τ不定時，根據(jù)式（7）使β＝τ可以得到：

當β＝τ＝1時，ER網(wǎng)絡(luò)抵御連鎖故障的容限系數(shù)臨界值αc是最小的，即

2）ER網(wǎng)絡(luò)的平均度數(shù)〈k〉＝Np越大，網(wǎng)絡(luò)抵御連鎖故障的能力越強。

2.2 BA無標度網(wǎng)絡(luò)

BA網(wǎng)絡(luò)是Barabási和Albert［20］提出的一個無標度網(wǎng)絡(luò)模型，其生成機制主要為增長和優(yōu)先連接。其構(gòu)造算法為：1）增長：從一個具有m0個節(jié)點的網(wǎng)絡(luò)開始，每次引入一個新的節(jié)點，并且連到m個已存在的節(jié)點上，這里m≤m0；2）優(yōu)先連接：一個新節(jié)點與一個已經(jīng)存在的節(jié)點i相連接的概率pi與節(jié)點i的度ki之間滿足pi＝根據(jù)BA模型的演化機制，其度分布近似為。因此，

1）τ＝1時，根據(jù)BA網(wǎng)絡(luò)的度分布，可以得到：

2）τ＞1時，

3）τ＜1時，

分析上述3類情形下αc隨β的變化情況，BA網(wǎng)絡(luò)在最近鄰偏好重分規(guī)則下可以得出以下結(jié)論：

1）當初始負荷強度參數(shù)τ固定，β＝τ可以使得網(wǎng)絡(luò)抵御連鎖故障的魯棒性最好。且當β＝τ時，根據(jù)式（10）可以得到

當β＝τ＝1時，抵御網(wǎng)絡(luò)上連鎖故障的容限系數(shù)臨界值αc是最小的，即

2）BA網(wǎng)絡(luò)的平均度數(shù)越大，網(wǎng)絡(luò)的規(guī)模越大，網(wǎng)絡(luò)抵御連鎖故障的能力越強。

圖1給出了ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)容量系數(shù)臨界值的解析結(jié)果。

圖1 容限系數(shù)臨界值的解析結(jié)果（β＝τ）Fig.1 Theoretical results of capacity coefficient thresholds（β＝τ）

3 數(shù)值仿真

依據(jù)負載重分配模型分別對ER網(wǎng)絡(luò)模型和BA網(wǎng)絡(luò)模型進行數(shù)值仿真。圖2給出了C FN指標隨網(wǎng)絡(luò)拓撲參數(shù)與容量系數(shù)變化的仿真結(jié)果。在ER隨機網(wǎng)絡(luò)中，網(wǎng)絡(luò)規(guī)模一定的條件下，研究CFN與〈k〉（〈k〉＝Np）的關(guān)系實際上就是研究C FN 與p的關(guān)系。由圖2a可以看出，ER隨機網(wǎng)絡(luò)中隨著網(wǎng)絡(luò)平均度數(shù)的增加，網(wǎng)絡(luò)抵御連鎖故障的魯棒性逐漸增強，且在網(wǎng)絡(luò)連接密度一定的條件下擴大網(wǎng)絡(luò)的規(guī)模對CFN 指標基本無影響。從圖2b可以看出，ER網(wǎng)絡(luò)規(guī)模一定時，隨著概率p的增大，使C FN＝0的α值逐漸減小，即相變點αc逐漸減小。BA網(wǎng)絡(luò)中，網(wǎng)絡(luò)規(guī)模的擴大和網(wǎng)絡(luò)連接密度的增加都會不同程度地抑制網(wǎng)絡(luò)連鎖故障的發(fā)生。從圖2c可以看出，BA網(wǎng)絡(luò)隨著網(wǎng)絡(luò)規(guī)模與平均度數(shù)的增加，CFN逐漸減小，而且存在使得CFN＝0的相變點；從圖2d可以看出，BA網(wǎng)絡(luò)的相變點αc隨著平均度數(shù)的增大逐漸減小。

圖2 ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)的CFN仿真結(jié)果（β＝τ＝1）Fig.2 Simulation results of CFNwith ER and BA networks（β＝τ＝1）

圖3 ER與BA網(wǎng)絡(luò)的CFN與負荷分配均勻性參數(shù)、負荷初始強度參數(shù)的關(guān)系Fig.3 Simulation results of CFNwithβandτfor ER and BA networks

圖3給出了ER網(wǎng)絡(luò)和BA網(wǎng)絡(luò)CFN指標隨初始負荷強度參數(shù)與負荷分配均勻性系數(shù)變化的仿真結(jié)果。設(shè)定初始負荷強度參數(shù)τ分別為0.7，1.0與1.3時，對比ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)不同容量系數(shù)α下的CFN，在β＝τ時，CFN取得最小值。由于網(wǎng)絡(luò)抵御連鎖故障能力的另一個度量指標容量系數(shù)臨界值αc與CFN之間的關(guān)聯(lián)性，很自然的一個問題是：實際網(wǎng)絡(luò)管理中β＝τ是不是同樣使得αc取得最小值？

圖4分別給出了（τ＜1，τ＝1與τ＞1）3種情況下，ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)αc的解析結(jié)果與仿真結(jié)果?？梢钥闯鰯?shù)值模擬較好地驗證了解析分析的結(jié)果。也證明了β＝τ可以使得αc取得極小值，即在ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)結(jié)構(gòu)中，合理地控制網(wǎng)絡(luò)的負載量以及設(shè)計合適的負載分配規(guī)則會極大地減小網(wǎng)絡(luò)連鎖故障的風險。

圖4 τ＝0.7，1.0，1.3時，ER網(wǎng)絡(luò)和BA網(wǎng)絡(luò)最近鄰分配規(guī)則下αc的解析結(jié)果與仿真結(jié)果Fig.4 Comparison of simulation results and analytic results ofαcwith ER and BA networks

4 結(jié)論

根據(jù)以往連鎖故障模型中對初始負荷分布強度與負載分配均勻性相等的假設(shè)容易忽視這兩個因素的差異性影響，本文在研究一般網(wǎng)絡(luò)級聯(lián)失效動力學行為時，假設(shè)負載偏好分配模型中初始負荷強度參數(shù)與失效節(jié)點負荷分配均勻性參數(shù)不相關(guān)，研究了ER網(wǎng)絡(luò)和BA網(wǎng)絡(luò)的級聯(lián)失效條件，分析了網(wǎng)絡(luò)抵御連鎖故障的影響因素及其影響方式。

本文研究一方面擴展了負載最近鄰偏好分配模型，便于分析現(xiàn)實世界中的一般網(wǎng)絡(luò)模型，使該模型具有更普遍意義；另一方面，解析推導了ER網(wǎng)絡(luò)和BA網(wǎng)絡(luò)的級聯(lián)失效條件，給出了網(wǎng)絡(luò)免疫連鎖故障的臨界值公式，可為網(wǎng)絡(luò)的設(shè)計和管理提供一定的指導。另外，本文的仿真結(jié)果也驗證了解析分析的結(jié)論，具體到網(wǎng)絡(luò)的設(shè)計與管理措施中，主要有以下幾個基本結(jié)論：1）提高網(wǎng)絡(luò)的連接密度與擴大網(wǎng)絡(luò)的規(guī)模有利于抑制網(wǎng)絡(luò)連鎖故障；2）網(wǎng)絡(luò)設(shè)計容量的增大會極大提高網(wǎng)絡(luò)的魯棒性，但是受成本等因素的影響，不可能無限大；3）網(wǎng)絡(luò)初始負荷的分布與失效后節(jié)點負荷的分配規(guī)則是網(wǎng)絡(luò)連鎖故障的重要因素，在網(wǎng)絡(luò)運行之初盡量使網(wǎng)絡(luò)初始負荷分布強度參數(shù)與負載分配均勻性參數(shù)都在1附近可使得網(wǎng)絡(luò)連鎖故障的概率最低，在網(wǎng)絡(luò)穩(wěn)定運行時即網(wǎng)絡(luò)負荷分布一定時，管理中盡量使負載分配均勻性參數(shù)與負荷分布強度參數(shù)一致，也可使得網(wǎng)絡(luò)連鎖故障風險最低。

需要指出的是，本文的模型和結(jié)論針對最近鄰耦合機制，而實際系統(tǒng)運行時的動力學行為也可能是全局耦合機制或介于最近鄰和全局之間的耦合機制，這種動力學機制對網(wǎng)絡(luò)連鎖故障行為也會產(chǎn)生不同的影響；而且，網(wǎng)絡(luò)的失效機理不僅僅是過載機制，網(wǎng)絡(luò)的失效行為也可能是由網(wǎng)絡(luò)個體之間的依賴、因果、控制等關(guān)系引起。因此，更為貼近實際系統(tǒng)運行機制的網(wǎng)絡(luò)動力學行為是下一步研究的重點。

［1］ Buldyrev S V，Parshani R，Paul G，et al.Catastrophic cascade of failures in interdependent networks［J］.Nature，2010，464（7291）：1025－1028.

［2］ 丁琳，張嗣瀛.復雜網(wǎng)絡(luò)上相繼故障研究綜述［J］.計算機科學，2012，39（8）：8－13.Ding Lin，Zhang Siying.Survey on cascading failures on complex networks［J］.Computer Science，2012，39（8）：8－13.

［3］ Crucitti P，Latora V，Marchiori M.Model for cascading failures in complex networks［J］.Physical Review E，2004，69（4）：045104.

［4］ 段東立，吳俊，鄧宏鐘，等.基于可調(diào)負載重分配的復雜網(wǎng)絡(luò)級聯(lián)失效模型［J］.系統(tǒng)工程理論與實踐，2013，33（1）：203－208.Duan Dongli，Wu Jun，Deng Hongzhong，et al.Cascading failure model of complex networks based on tunable load redistribution［J］.Systems Engineering Theory ＆Practice，2013，33（1）：203－208.

［5］ Motter A E，Lai Y C.Cascade－based attacks on complex networks［J］.Physical Review E，2002，66（6）：065102.

［6］ 王建偉.網(wǎng)絡(luò)上的相繼故障模型研究［D］.大連：大連理工大學，2010.Wang Jianwei.Study on cascading failure model on networks［D］.Dalian：Dalian University of Technology，2010.

［7］Zheng J F，Gao Z Y，F(xiàn)u B B，et al.Cascading failures in congested complex networks with feedback［J］.Chinese Physics B，2009，18（11）：4754－4759.

［8］ Hu K，Hu T，Tang Y.Model for cascading failures with adaptive defense in complex networks［J］.Chinese Physics B，2010，19（8）：080206.

［9］ Wang B，Kim B J.A high－robustness and low－cost model for cascading failures［J］.Europhysics Letters，2007，78（4）：48001.

［10］Li P，Wang B H，Sun H，et al.A limited resource model of fault－tolerant capability against cascading failure of complex network［J］.The European Physical Journal B，2008，62（1）：101－104.

［11］Wang W X，Chen G R.Universal robustness characteristic of weighted networks against cascading failure［J］.Physical Review E，2008，77（2）：026101.

［12］Wu Z X，Peng G，Wang W X，et al.Cascading failure spreading on weighted heterogeneous networks［J］.Journal of Statistical Mechanics：Theory and Experiment，2008，（5）：05013.

［13］王建偉，榮莉莉.基于負荷局域擇優(yōu)重新分配原則的復雜網(wǎng)絡(luò)上的相繼故障［J］.物理學報，2009，（6）：3714－3721.Wang Jianwei，Rong Lili.Cascading failures on complex networks based on the local preferential redistribution rule of the load［J］.Acta Physic Asinica，2009，（6）：3714－3721.

［14］王建偉，榮莉莉.面向相繼故障的復雜網(wǎng)絡(luò)上襲擊策略研究［J］.中國管理科學，2009，（1）：125－130.Wang Jianwei，Rong Lili.Cascade－oriented attack on complex networks［J］.Chinese Journal of Management Science，2009，（1）：125－130.

［15］王建偉，榮莉莉.基于襲擊的復雜網(wǎng)絡(luò)上的全局相繼故障 ［J］.管理科學，2009，（3）：113－120.Wang Jianwei，Rong Lili.Universal cascading failures on complex networks based on attacks［J］.Journal of Management Science，2009，（3）：113－120.

［16］Wang J W，Rong L L.A model for cascading failures in scale－free networks with a breakdown probability［J］.Physica A，2009，388（7）：1289－1298.

［17］Wang J W，Rong L L，Zhang L，et al.Attack vulnerability of scale－free networks due to cascading failures［J］.Physica A，2008，387（26）：6671－6678.

［18］Wang J W，Rong L L.Cascade－based attack vulnerability on the US power grid［J］.Safety Science，2009，47（10）：1332－1336.

［19］Wang J W，Rong L L.Robustness of the western United States power grid under edge attack strategies due to cascading failures［J］.Safety Science，2011，49（6）：807－812.

［20］Barabási A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509－512.