一種基于負載局域分配的相繼故障模型*

夏　蘇，朱　磊，劉笑辰

(中國人民解放軍理工大學 通信工程學院, 江蘇 南京 210007)

?

一種基于負載局域分配的相繼故障模型*

夏蘇，朱磊，劉笑辰

(中國人民解放軍理工大學 通信工程學院, 江蘇 南京 210007)

為了更好地研究復雜網絡抵制相繼故障的魯棒性，在經典的負載-容量模型基礎上，提出了一種基于負載局域分配的相繼故障模型。結合現(xiàn)實網絡特點定義了衡量相繼故障程度的指標——網絡效率，提出節(jié)點對超出負載具有一定的容忍能力。將所提出的相繼故障模型應用于經典復雜網絡模型均觀察到發(fā)生了相繼故障現(xiàn)象，且通過仿真研究了相繼故障傳播的影響因素。實驗結果表明，不同的節(jié)點失效方式、模型參數值以及網絡的介數分布都會影響相繼故障的傳播。

復雜網絡；相繼故障；節(jié)奏效率；BA無標度網絡

引用格式：夏蘇，朱磊，劉笑辰. 一種基于負載局域分配的相繼故障模型[J].微型機與應用，2016,35(11)：56-59.

0　引言

復雜網絡[1]中的相繼故障是指一個或者幾個節(jié)點(或邊)發(fā)生的故障會通過節(jié)點之間的相互關系引起其他節(jié)點發(fā)生故障，產生連鎖效應并最終導致部分或整個網絡的崩潰[2]。相繼故障是復雜網絡系統(tǒng)中一種常見的現(xiàn)象，一旦發(fā)生對系統(tǒng)的危害極大?，F(xiàn)實生活中，發(fā)生相繼故障的潛在可能性普遍存在于基礎設施網絡中，如電力網、供水網、交通網和通信網等[3-5]。2003年8月14日，由美國俄亥俄州克利夫蘭市的3條超高壓輸電線路相繼過載燒斷引起的北美大停電事故，其影響區(qū)域包括美國東北部、中西部和加拿大東部，造成的損失高達數百億美元，該事件的發(fā)生震驚了全世界。2007年，美國次貸危機除席卷了美國本土之外還影響了歐盟、日本等世界主要金融市場。類似的事件還有大規(guī)模的交通網阻塞、發(fā)生在因特網上的病毒傳播等，這些都可以看作由相繼故障導致的災難性后果。

現(xiàn)實生活中的許多網絡都可以看作為復雜網絡，在以往的研究中，復雜網絡的靜態(tài)特性吸引了很多學者的注意[6]。然而，隨著相繼故障這一現(xiàn)象的出現(xiàn)，人們開始意識到復雜網絡的動態(tài)特征也十分重要，因此越來越多的研究人員開始把目光聚焦到復雜網絡的動態(tài)特征研究上。在此后的針對相繼故障的研究中，陸續(xù)有人提出了復雜網絡上的相繼故障傳播模型，并嘗試提出減輕相繼故障給復雜網絡帶來的不良影響的方法[7]。參考文獻[8]考慮節(jié)點的動態(tài)特性提出了經典的ML模型，參考文獻[9]綜合考慮節(jié)點和邊的動態(tài)特性提出了CLM模型。這兩種經典模型都假設當一個節(jié)點失效時，其承載的負載會重新分配給網絡中剩下的節(jié)點，這種全局分配的方式要求網絡中所有節(jié)點實時了解全局信息。然而在現(xiàn)實生活中，復雜網絡中的所有節(jié)點實時獲取全局信息較為困難，并且這種方式的成本也較高。此外，在經典的ML模型中，節(jié)點的負載一旦超出它的容量，將被立即從網絡中移除。但是現(xiàn)實網絡中的一些節(jié)點，例如路由器，具備一定的擁塞承受能力，并且可以在一定范圍內處于超負載工作狀態(tài)。

本文提出了一種基于負載局域分配的相繼故障模型，并給予每個節(jié)點一個初始的效率，當復雜網絡中單個節(jié)點的負載超過它的容量，并且超出的比例在一定范圍內時，假設這個節(jié)點不立即失效而是可以繼續(xù)工作，同時，節(jié)點的效率將會大幅度降低。當節(jié)點負載超過節(jié)點可以容忍的閾值時，節(jié)點的效率降為0，其承擔的負載將會分配給與其直接相連的鄰居節(jié)點。

1　基于負載局域分配的相繼故障模型

在大多數的復雜網絡中，節(jié)點都承擔著一定的負載。對于一個給定的網絡，信息或者能量通過最短路徑在節(jié)點對之間進行交換，因此有理由認為節(jié)點的初始負載與經過它的最短路徑條數有關，由此定義節(jié)點的初始負載等于其介數——網絡中所有最短路徑中經過該節(jié)點的路徑數目占最短路徑總數的比例，則節(jié)點i的初始負載用式(1)表示：

Li=Bi

(1)

其中Bi為節(jié)點i的介數：

(2)

式(2)中，Sjk表示節(jié)點j到節(jié)點k的最短路徑條數，Sjik表示節(jié)點j到節(jié)點k的最短路徑中經過節(jié)點i的條數。這里所使用的介數定義中，將最短路徑中處于兩端位置的節(jié)點也考慮在內，這樣就避免了有些節(jié)點的介數為0導致其在網絡中不承擔任何負載這一問題。本文提出的模型中，節(jié)點i的容量Ci表示節(jié)點保持最高效率正常工作時可以承擔的最大負載。在現(xiàn)實生活中，節(jié)點的容量受成本的限制而不可能無限大。節(jié)點的容量反映了節(jié)點高效率處理負載的能力，因此很自然地假設節(jié)點的容量與節(jié)點的初始負載正相關，即：

Ci=(1+α)Li,i=1,2,...,N

(3)

其中α是一個可調參數，并且α≥0，N是復雜網絡中最初的節(jié)點總數。

考慮到本文關注的是單個節(jié)點從網絡中被移除所帶來的影響，因此此處假設網絡中故障最開始只由一個節(jié)點的移除(節(jié)點失效)引起，并且節(jié)點失效后，該節(jié)點所承擔的負載將會重新分配給網絡中的其他節(jié)點。對于負載的重新分配，目前主流的方法有兩類：一類是全局分配，即由網絡中剩下的所有節(jié)點參與失效節(jié)點的負載的重新分配[10]；另一類是局域分配，即由該失效節(jié)點的鄰居節(jié)點參與負載的重新分配[11]。但是在復雜網絡中，相比于獲取鄰居節(jié)點的信息，獲取全局信息要更加困難，并且保證所有節(jié)點實時獲取網絡中全局信息的成本也更高?；谝陨峡紤]，本文采用局域分配的方法來重新分配失效節(jié)點的負載。這就意味著最開始時如果節(jié)點i從復雜網絡中被移除，其承擔的負載將會分配給與其直接相連的鄰居節(jié)點。假設節(jié)點j是節(jié)點i的一個鄰居節(jié)點，則節(jié)點j在負載重新分配后承擔的負載用式(4)計算：

(4)

其中Ljd表示節(jié)點j的新負載，Li、Lj分別表示節(jié)點i和節(jié)點j在移除節(jié)點i之前各自承擔的負載，此處由于節(jié)點i是網絡中第一個失效的節(jié)點，因此也是它們的初始負載。ej是節(jié)點j的效率，將在下一節(jié)討論。

2　網絡故障程度的評價指標

在以往的相繼故障研究中，節(jié)點的狀態(tài)往往只有正?；蛘呤б环N，但是在現(xiàn)實生活中，復雜網絡中的節(jié)點狀態(tài)有時可以介于正常和失效兩種狀態(tài)之間。因此用節(jié)點效率來描述節(jié)點所處的狀態(tài)，并用較高的效率來表示節(jié)點工作于一種更好的狀態(tài)。

定義節(jié)點的初始效率為一個定值，節(jié)點i的初始效率用ei0表示，本文中令所有節(jié)點的初始效率都為1，即ei0=1，此時網絡中所有節(jié)點都正常工作。當首個從網絡中被移除的節(jié)點為節(jié)點i時，節(jié)點i的效率ei=0，且節(jié)點i的負載將會按照式(4)進行分配，其鄰居節(jié)點接受節(jié)點i分配的負載后需按照式(5)重新計算各自的效率，即：

(5)

其中節(jié)點j為節(jié)點i直接相連的鄰居節(jié)點。β為容忍參數，使得節(jié)點的負載在超出節(jié)點容量一定范圍內時可以工作于一個較低的效率而不是立即失效，1<β≤2。容忍參數的存在使得當節(jié)點的負載超過其容量不是很多時不至于立即從網絡中移除，這個機制也使得相繼故障模型更加貼合實際，例如通信網絡中的路由器，當其需要處理的流量超出路由器的容量時，路由器往往不會立即失效無法工作，而是使得丟失一部分數據包的概率變大，路由器的這種丟包行為就可以視為路由器工作于一種效率較低的狀態(tài)。值得注意的是，雖然容忍參數β的值越大，意味著節(jié)點忍受超負載工作的能力越強，但是這也意味著在建設網絡時要付出的成本更高，因此β的值并不能太大。

式(5)描述了第一個節(jié)點故障時(此時也為故障的第一個步長)的情形，將這個結論推廣到第t個步長，將會得到故障第t次傳播時各節(jié)點的效率，即：

(6)

當節(jié)點的效率降為0時，該節(jié)點的負載將會分配給其鄰居節(jié)點，此時該節(jié)點失效且其所有的鄰居節(jié)點將會重新計算各自的效率。如果負載重新分配這一過程導致了新的節(jié)點發(fā)生故障，即發(fā)生了相繼故障現(xiàn)象，新失效節(jié)點的負載將會繼續(xù)分配給仍在工作的節(jié)點，因此又將引發(fā)新一輪的節(jié)點效率的計算。這個過程不斷重復直至不再有新的節(jié)點故障，或者網絡中所有的節(jié)點都出現(xiàn)故障。

當最終網絡處于一種穩(wěn)定狀態(tài)時，用網絡效率E(G)來衡量相繼故障對復雜網絡帶來的損害程度。

(7)

其中N是復雜網絡的初始節(jié)點總數。網絡效率E(G)反映了相繼故障給復雜網絡帶來的不良影響，E(G)的值越小，表示整個網絡的故障程度越高，對網絡造成的傷害越大，當E(G)為0時，表示整個復雜網絡中的所有節(jié)點都因故障失效而無法工作。同時，當最后網絡穩(wěn)定時，網絡效率E(G)的值越大，可以在一定程度上反映網絡在當時條件下有越好的抵御相繼故障的能力。

3　仿真結果與分析

3.1不同節(jié)點失效方式對相繼故障傳播的影響

為了研究在本文提出的模型下，故障在復雜網絡上的傳播情況，首先在BA無標度網絡中進行實驗。初始時節(jié)點總數N=1 000。首個節(jié)點失效采用兩種方式——隨機攻擊和蓄意攻擊。

當網絡的其他參數一樣，只有首個節(jié)點失效的方式不同時，通過仿真比較隨機從網絡中移除一個節(jié)點與有選擇地移除網絡中介數最大節(jié)點對網絡效率的影響，仿真結果如圖1所示。

圖1　BA無標度網絡中不同失效方式對網絡效率的影響

從圖1可以看出，在BA無標度網絡中，如果最先失效的節(jié)點是隨機選取的普通節(jié)點，則由該節(jié)點引起的故障程度很?。欢绻钕仁У墓?jié)點是網絡中介數最大的節(jié)點，則隨著故障的不斷傳播，最終會引起相當多的節(jié)點失效。這也可以理解為BA無標度網絡對隨機攻擊表現(xiàn)出相當強的免疫能力，但是在蓄意攻擊面前卻顯得十分脆弱。

3.2模型參數對相繼故障傳播的影響

在研究網絡中的可調參數α對相繼故障傳播的影響時，通過仿真研究了在β值一定時，最終的網絡效率隨α值的改變而變化的情況。仿真的網絡選擇BA無標度網絡，首個節(jié)點失效的方式分別采用隨機攻擊和蓄意攻擊的方法，仿真結果如圖2所示。

圖2　BA無標度網絡中網絡效率隨α的變化情況

從圖2中可以看到，BA無標度網絡在隨機攻擊時，網絡效率一直很高，但是效率值呈現(xiàn)出震蕩的走勢；在首先移除介數最大節(jié)點時(蓄意攻擊)，在α大到一定程度時，網絡效率隨α的增大而增大。

考慮到網絡的容忍參數在相繼故障模型中起著同樣重要的作用，通過仿真研究了在α值一定時，最終的網絡效率隨著β值的改變而變化的情況。仿真條件與圖2中相同，仿真結果如圖3所示。通過對仿真曲線的對比分析可以發(fā)現(xiàn)，當隨機選擇最先失效的節(jié)點時，雖然網絡效率隨β有一定的波動，但整體上保持了一個較高的值，而當介數最大節(jié)點最先失效時，最終網絡效率的值在β=1.7以后才隨著β的增大而增大，并且即使β=2時，網絡的效率也才在0.7左右。這也從側面反映了介數最大節(jié)點對BA無標度網絡中相繼故障的傳播有重要作用。

為了研究提出的相繼故障模型在不同復雜網絡中的表現(xiàn)，將模型應用到WS小世界網絡，以便與BA無標度網絡中的情形進行對比。仿真結果如圖4、圖5所示?？梢钥吹?，在α與β都較小時，WS小世界網絡對移除介數最大的節(jié)點十分敏感，但是當這兩個參數的值較大時，WS小世界網絡對隨機攻擊和蓄意攻擊均表現(xiàn)出了較強的抵御能力。且通過對比圖2與圖4以及圖3與圖5可以看到，為使網絡保持較高的效率，WS小世界網絡所需的α與β值比BA無標度網絡要小得多，這意味著WS網絡比BA無標度網絡具有更好的抵御相繼故障的能力，且通過合理增加α與β的值，可以使WS小世界網絡對相繼故障有較強的免疫力。

圖4　WS小世界網絡中網絡效率隨α的變化情況

圖5　WS小世界網絡中網絡效率隨β的變化情況

3.3改變節(jié)點介數分布對相繼故障傳播的影響

本文提出的相繼故障模型定義的節(jié)點初始負載等于節(jié)點的介數，且節(jié)點的容量與節(jié)點初始負載正相關，因此節(jié)點的介數在模型中有著十分重要的作用，值得進一步研究。考慮在BA無標度網絡中，在不改變節(jié)點之間連接關系的條件下，人為改變網絡中節(jié)點的介數分布情況，使網絡的介數分布更為均勻。仿真結果分別如圖6、圖7所示。

圖6　介數最大節(jié)點最先失效時BA網絡中介數對網絡效率的影響

圖7　隨機攻擊時BA網絡中介數對網絡效率的影響

從圖中可以看出，在BA無標度網絡中，隨機攻擊時介數的改變對相繼故障的傳播影響不大。但是當介數最大的節(jié)點最先失效時，對于介數分布均勻的網絡，相繼故障對其造成的破壞程度要小。

4　結論

本文通過建立相繼故障模型，展示了一個很小的初始擾動可能導致網絡中相當多的節(jié)點甚至整個網絡崩潰。在本文提出的模型中，節(jié)點失效后采用了負載局域分配這一策略，考慮到節(jié)點對超出負載具備一定容忍能力，提出了相應的相繼故障規(guī)模評價指標——網絡效率。相關的仿真表明，節(jié)點的移除策略對相繼故障的傳播有著重要影響，即網絡對網絡中介數最大的節(jié)點失效更為敏感。同時，模型中參數α與β的大小也影響著網絡相繼故障的傳播和最終的網絡效率E(G)，并且合適的參數值在一定程度上可提高網絡對相繼故障的抵御能力。通過對仿真結果的分析可以發(fā)現(xiàn)，復雜網絡的統(tǒng)計特征量如介數也可以影響到相繼故障的傳播。

本文的結論可以幫助理解相繼故障的傳播機理，并且對在建設網絡之初參數的選擇起到輔助決策的作用。雖然選擇合適的參數并用于網絡構建可以在一定程度上提高復雜網絡的可靠性，但是對于已經存在的固有參數不那么合適的復雜網絡，如何減小網絡發(fā)生相繼故障的概率，或者在故障已經出現(xiàn)時如何減小相繼故障規(guī)模還有待深入的研究。

[1] 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用[M]. 北京：清華大學出版社, 2006.

[2] 丁琳, 張嗣瀛. 復雜網絡上相繼故障研究綜述[J]. 計算機科學, 2012, 39(8):8-13.

[3] Zhang Guidong, Li Zhong, Zhang Bo, et al. Understanding the cascading failures in Indian power grids with complex networks theory[J]. Physica A: Statistical Mechanics & its Applications, 2013, 392(15):3273-3280.

[4] Shuang Qing, Zhang Mingyuan, Yuan Yongbo. Node vulnerability of water distribution networks under cascading failures[J]. Reliability Engineering & System Safety, 2014, 124(4):132-141.

[5] CHONG P Y, SHUAI B. Model of cascading failure in hazardous materials transportation network under series of terrorist attacks[J]. Systems Engineering-Theory & Practice, 2014, 34(4):1059-1065.

[6] KASTHURIRATHNA D, PIRAVEENAN M, THEDCHANAMOORTHY G. On the influence of topological characteristics on robustness of complex networks[J]. Journal of Artificial Intelligence & Soft Computing Research, 2014, 63(2):89-100.

[7] TRAN H A Q, NAMATAME A. Mitigating cascading failure with adaptive networking[J]. New Mathematics and Natural Computation, 2015, 11(2): 151-163 .

[8] MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2002, 66(2):114-129.

[9] CRUCITTI P, LATORA V, MARCHIORI M. Model for cascading failures in complex networks[J]. Physical Review E, 2004, 69(4):266-289.

[10] 王建偉. 網絡上的相繼故障模型研究[D]. 大連:大連理工大學, 2010.

[11] 王建偉, 榮莉莉, 王鐸. 基于節(jié)點局域特征的復雜網絡上相繼故障模型[J]. 管理科學學報, 2010, 13(8): 42-50.

Cascading failures model based on load distributing in local area

Xia Su，Zhu Lei，Liu Xiaochen

(College of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China)

In order to study the complex network robustness to resist the cascading failures, on the basis of classical load-capacity model, we put forward a kind of cascading failures model based on load distributing in local area. Combining with the characteristics of real network, the network efficiency which is a measure of complex network was defined, and the node was supposed to have a certain tolerance to the excess load. The cascading failures phenomenon happens when the model was applied to the classical complex network models, and the influence factors of complex network propagation are studied by simulation. The experiments on different networks show that different node failure patterns, the model parameter values as well as the betweenness distribution of the complex network can affect the transmission of the cascading failures.

complex network; cascading failures; node efficiency; BA scale-free network

江蘇省自然科學基金項目(BK20141071)

TN915

A

10.19358/j.issn.1674- 7720.2016.11.018

2016-03-03)

夏蘇(1990-)，通信作者，女，碩士研究生，主要研究方向：網絡規(guī)劃與管理。E-mail：xiasu163@163.com。

朱磊(1973-)，男，博士，教授，主要研究方向：網絡規(guī)劃與管理。

劉笑辰(1990-)，男，碩士研究生，主要研究方向：網絡規(guī)劃與管理。