夏蘇，朱磊,，劉笑辰

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

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

　　關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；相繼故障,；節(jié)奏效率,；BA無標(biāo)度網(wǎng)絡(luò)

0引言

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

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

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

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

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

　　Li=Bi(1)

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

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

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

　　其中α是一個可調(diào)參數(shù),，并且α≥0，N是復(fù)雜網(wǎng)絡(luò)中最初的節(jié)點總數(shù),。

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

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

　　2網(wǎng)絡(luò)故障程度的評價指標(biāo)

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

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

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

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

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

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

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

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

3仿真結(jié)果與分析

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

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

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

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

　　3.2模型參數(shù)對相繼故障傳播的影響

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

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

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

　　為了研究提出的相繼故障模型在不同復(fù)雜網(wǎng)絡(luò)中的表現(xiàn),，將模型應(yīng)用到WS小世界網(wǎng)絡(luò)，以便與BA無標(biāo)度網(wǎng)絡(luò)中的情形進行對比,。仿真結(jié)果如圖4,、圖5所示,。可以看到,，在α與β都較小時,，WS小世界網(wǎng)絡(luò)對移除介數(shù)最大的節(jié)點十分敏感，但是當(dāng)這兩個參數(shù)的值較大時,，WS小世界　　

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

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

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

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

4結(jié)論

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

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

參考文獻

　　［1］ 汪小帆, 李翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］. 北京：清華大學(xué)出版社, 2006.

　?。?］ 丁琳, 張嗣瀛. 復(fù)雜網(wǎng)絡(luò)上相繼故障研究綜述［J］. 計算機科學(xué), 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］ 王建偉. 網(wǎng)絡(luò)上的相繼故障模型研究［D］. 大連:大連理工大學(xué), 2010.

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