基于負載最近鄰偏好分配的復雜網絡連鎖效應

段東立

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

0 引言

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

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

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

1 負載重分配模型

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

假設負載增量ΔFj與失效節點的負載成正比

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

其中，ρ和τ為可調參數，控制節點初始負荷的強度。根據ML模型中初始負荷與節點容量的關系，將節點的容量定義為

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

其中，CFi（0≤CFi≤N－1）為節點i失效觸發連鎖故障的節點個數。

2 理論分析

為避免連鎖故障的發生，式（6）的條件應該被滿足

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

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

2.1 ER隨機網絡

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

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

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

當β＝τ＝1時，ER網絡抵御連鎖故障的容限系數臨界值αc是最小的，即

2）ER網絡的平均度數〈k〉＝Np越大，網絡抵御連鎖故障的能力越強。

2.2 BA無標度網絡

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

1）τ＝1時，根據BA網絡的度分布，可以得到：

2）τ＞1時，

3）τ＜1時，

分析上述3類情形下αc隨β的變化情況，BA網絡在最近鄰偏好重分規則下可以得出以下結論：

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

當β＝τ＝1時，抵御網絡上連鎖故障的容限系數臨界值αc是最小的，即

2）BA網絡的平均度數越大，網絡的規模越大，網絡抵御連鎖故障的能力越強。

圖1給出了ER網絡與BA網絡容量系數臨界值的解析結果。

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

3 數值仿真

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

圖2 ER網絡與BA網絡的CFN仿真結果（β＝τ＝1）Fig.2 Simulation results of CFNwith ER and BA networks（β＝τ＝1）

圖3 ER與BA網絡的CFN與負荷分配均勻性參數、負荷初始強度參數的關系Fig.3 Simulation results of CFNwithβandτfor ER and BA networks

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

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

圖4 τ＝0.7，1.0，1.3時，ER網絡和BA網絡最近鄰分配規則下αc的解析結果與仿真結果Fig.4 Comparison of simulation results and analytic results ofαcwith ER and BA networks

4 結論

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

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

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

［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］ 丁琳，張嗣瀛.復雜網絡上相繼故障研究綜述［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］ 段東立，吳俊，鄧宏鐘，等.基于可調負載重分配的復雜網絡級聯失效模型［J］.系統工程理論與實踐，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］ 王建偉.網絡上的相繼故障模型研究［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，Fu 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］王建偉，榮莉莉.基于負荷局域擇優重新分配原則的復雜網絡上的相繼故障［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］王建偉，榮莉莉.面向相繼故障的復雜網絡上襲擊策略研究［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］王建偉，榮莉莉.基于襲擊的復雜網絡上的全局相繼故障 ［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.