基于負(fù)載最近鄰偏好分配的復(fù)雜網(wǎng)絡(luò)連鎖效應(yīng)

段東立

（西安武警工程大學(xué)裝備工程學(xué)院，西安710008）

0 引言

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

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

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

1 負(fù)載重分配模型

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

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

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

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

其中，α為網(wǎng)絡(luò)的容限系數(shù)，表示節(jié)點處理額外負(fù)荷的能力。當(dāng)α足夠大時，任一節(jié)點的失效都不會觸發(fā)連鎖故障，但是受經(jīng)濟(jì)與技術(shù)因素的影響，α不可能任意大，所以，可以用臨界值αc表征網(wǎng)絡(luò)抵抗連鎖故障的能力。αc值越小，網(wǎng)絡(luò)抵制連鎖故障的魯棒性越強(qiáng)，當(dāng)α＞αc時，移除網(wǎng)絡(luò)中的任一節(jié)點都不會觸發(fā)連鎖效應(yīng)。為了量化整個網(wǎng)絡(luò)的魯棒性，也可采用失效節(jié)點的歸一化指標(biāo)［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ò)承載何種程度的負(fù)載以及單個故障時如何分配網(wǎng)絡(luò)負(fù)荷，可以使得網(wǎng)絡(luò)魯棒性最強(qiáng)，即αc值最小。為探討不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（度分布特征）對級聯(lián)失效行為的影響，研究中選用了在現(xiàn)實世界中具有很好的普適性和代表性的兩類網(wǎng)絡(luò)作為級聯(lián)失效的拓?fù)浼軜?gòu)，分別是具有泊松分布特征的ER隨機(jī)網(wǎng)絡(luò)和具有冪律度分布特征的BA網(wǎng)絡(luò)。

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

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

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

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

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

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

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

BA網(wǎng)絡(luò)是Barabási和Albert［20］提出的一個無標(biāo)度網(wǎng)絡(luò)模型，其生成機(jī)制主要為增長和優(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模型的演化機(jī)制，其度分布近似為。因此，

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

2）τ＞1時，

3）τ＜1時，

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

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

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

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

圖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ù)負(fù)載重分配模型分別對ER網(wǎng)絡(luò)模型和BA網(wǎng)絡(luò)模型進(jìn)行數(shù)值仿真。圖2給出了C FN指標(biāo)隨網(wǎng)絡(luò)拓?fù)鋮?shù)與容量系數(shù)變化的仿真結(jié)果。在ER隨機(jī)網(wǎng)絡(luò)中，網(wǎng)絡(luò)規(guī)模一定的條件下，研究CFN與〈k〉（〈k〉＝Np）的關(guān)系實際上就是研究C FN 與p的關(guān)系。由圖2a可以看出，ER隨機(jī)網(wǎng)絡(luò)中隨著網(wǎng)絡(luò)平均度數(shù)的增加，網(wǎng)絡(luò)抵御連鎖故障的魯棒性逐漸增強(qiáng)，且在網(wǎng)絡(luò)連接密度一定的條件下擴(kuò)大網(wǎng)絡(luò)的規(guī)模對CFN 指標(biāo)基本無影響。從圖2b可以看出，ER網(wǎng)絡(luò)規(guī)模一定時，隨著概率p的增大，使C FN＝0的α值逐漸減小，即相變點αc逐漸減小。BA網(wǎng)絡(luò)中，網(wǎng)絡(luò)規(guī)模的擴(kuò)大和網(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與負(fù)荷分配均勻性參數(shù)、負(fù)荷初始強(qiáng)度參數(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指標(biāo)隨初始負(fù)荷強(qiáng)度參數(shù)與負(fù)荷分配均勻性系數(shù)變化的仿真結(jié)果。設(shè)定初始負(fù)荷強(qiáng)度參數(shù)τ分別為0.7，1.0與1.3時，對比ER網(wǎng)絡(luò)與BA網(wǎng)絡(luò)不同容量系數(shù)α下的CFN，在β＝τ時，CFN取得最小值。由于網(wǎng)絡(luò)抵御連鎖故障能力的另一個度量指標(biāo)容量系數(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ò)的負(fù)載量以及設(shè)計合適的負(fù)載分配規(guī)則會極大地減小網(wǎng)絡(luò)連鎖故障的風(fēng)險。

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

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

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

［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］ 丁琳，張嗣瀛.復(fù)雜網(wǎng)絡(luò)上相繼故障研究綜述［J］.計算機(jī)科學(xué)，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)負(fù)載重分配的復(fù)雜網(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］.大連：大連理工大學(xué)，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］王建偉，榮莉莉.基于負(fù)荷局域擇優(yōu)重新分配原則的復(fù)雜網(wǎng)絡(luò)上的相繼故障［J］.物理學(xué)報，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］王建偉，榮莉莉.面向相繼故障的復(fù)雜網(wǎng)絡(luò)上襲擊策略研究［J］.中國管理科學(xué)，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］王建偉，榮莉莉.基于襲擊的復(fù)雜網(wǎng)絡(luò)上的全局相繼故障 ［J］.管理科學(xué)，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.