夏蘇，朱磊，劉笑辰

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

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

　　關鍵詞：復雜網絡；相繼故障；節奏效率；BA無標度網絡

0引言

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

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

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

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

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

　　Li=Bi(1)

　　其中Bi為節點i的介數：

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

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

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

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

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

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

　　在以往的相繼故障研究中，節點的狀態往往只有正常或者失效一種，但是在現實生活中，復雜網絡中的節點狀態有時可以介于正常和失效兩種狀態之間。因此用節點效率來描述節點所處的狀態，并用較高的效率來表示節點工作于一種更好的狀態。

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

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

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

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

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

　　E(G)=1N∑i∈Nei(7)

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

3仿真結果與分析

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

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

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

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

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

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

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

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

　　為了研究提出的相繼故障模型在不同復雜網絡中的表現，將模型應用到WS小世界網絡，以便與BA無標度網絡中的情形進行對比。仿真結果如圖4、圖5所示?？梢钥吹?，在α與β都較小時，WS小世界網絡對移除介數最大的節點十分敏感，但是當這兩個參數的值較大時，WS小世界　　

　　圖5WS小世界網絡中網絡效率隨β的變化情況網絡對隨機攻擊和蓄意攻擊均表現出了較強的抵御能力。且通過對比圖2與圖4以及圖3與圖5可以看到，為使網絡保持較高的效率，WS小世界網絡所需的α與β值比BA無標度網絡要小得多，這意味著WS網絡比BA無標度網絡具有更好的抵御相繼故障的能力，且通過合理增加α與β的值，可以使WS小世界網絡對相繼故障有較強的免疫力。

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

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

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

4結論

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

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

參考文獻

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

　?。?］ 丁琳, 張嗣瀛. 復雜網絡上相繼故障研究綜述［J］. 計算機科學, 2012, 39(8):813.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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 .

　?。?］ 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.

　?。?］ 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.

　?。?1］ 王建偉, 榮莉莉, 王鐸. 基于節點局域特征的復雜網絡上相繼故障模型［J］. 管理科學學報, 2010, 13(8): 4250.