基于級聯失效的復雜保障網絡抗毀性仿真分析

（國防科學技術大學 信息系統與管理學院， 長沙 410073）



摘要：通過引入流量強度指數α和流量分布指數β，建立了不同網絡流量下的復雜負載網絡級聯失效抗毀性模型。基于該模型比較分析了無標度網絡、隨機網絡和介于這兩種網絡之間的特定復雜保障網絡在不同流量強度和流量分布下對單個節點的隨機失效與故意攻擊的抗毀性。結果表明，在考慮級聯失效的條件下，復雜保障網絡的抗毀性隨著流量強度的增加急劇下降。此外，流量分布對復雜保障網絡的抗毀性也具有顯著影響，在流量強度一定的條件下改變網絡的流量分布能有效提高網絡的抗毀性。

關鍵詞：保障網絡；級聯失效；抗毀性；流量強度

中圖分類號：TP39308文獻標志碼：A

文章編號：1001-3695(2008)11-3451-04



Invulnerability simulation analysis of complex logistics networksbased on cascading failure

LI Yong，DENG Hong-zhong，WU Jun，LV Xin，LIU Bin，TAN Yue-jin

(School of Information Systems Management， National University of Defense Technology， Changsha 410073， China)

Abstract:By the analysis of characteristics of complex logistics networks， a simulation model based on cascading failure for its invulnerability was proposed.In this model， the intensity and distribution of network traffic was controlled by an α-index and a β-index， respectively. The variety of invulnerability was simulated under random failures and intentional attacks on different networks. Result shows that the invulnerability performance declines rapidly when the network traffic is increased. Furthermore， the distribution of network traffic also has a strong impact on the invulnerability performance. 

Key words:logistics networks; cascading failure; invulnerability; network traffic

0引言

幾乎所有的復雜系統均可以抽象成網絡模型，這些網絡往往具有大量的節點，節點之間有著復雜的連接關系。復雜網絡不僅僅指無標度網絡，它還包括介于隨機網絡與無標度網絡間的其他網絡，把它們統稱為復雜網絡。隨著人們對網絡的依賴程度日益增高，一個廣受關注的問題逐漸凸現出來：這些網絡到底有多可靠？

日常生活中所涉及的大量網絡，如何降低它們的失效概率，提高它們的抗毀性具有重要意義。例如，在2008年的奧運會期間，在高負載、出現突發事件情況下，如何提高北京市的物資運輸和人流輸送網絡的抗毀性、高效性，對于確保奧運會的正常進行，以及提高我國的形象和地位就具有極其重要的意義；對于生活中人們天天用到的通信網絡，提高其抗毀性對確保人民的正常生活秩序，確保經濟系統的正常運行，節約經濟成本，提高經濟效率與效益就有其重要的意義和實際的價值；對于大型企業的銷售業務網，提高抗毀性就是提高企業的競爭力。生物領域也存在同樣的問題，基因網絡中的一些核心基因的故障會帶來災難性的后果。

以往的復雜網絡抗毀性研究^[1，2]主要關注的是靜態的抗毀性，不考慮節點（邊）失效的動態關聯，即總是假設一個節點（邊）的失效不會導致其他節點（邊）的失效。這方面研究最重要的成果就是無標度網絡的雙重性：面對隨機性的損傷，無標度網絡比隨機網絡有著更好的抗毀性，但面對選擇性打擊，無標度網絡卻顯得異常脆弱^[2]。在這種假設下，少數幾個節點的失效不會導致整個網絡的崩潰，而事實并非如此。實際上大多數網絡上是有負載的^[3]，這些負載可以是物質、信息或能量，可以是具體的，也可以是抽象的。網絡上的負載是動態變化的，特別是當網絡結構發生改變，如節點的加入、移除，網絡上的負載將重新分配。一般來說，網絡中節點承受負載的能力是有限的，即節點的容量是有限的。有限的容量和負載的重新分配使得負載網絡的抗毀性問題變得更加復雜：一個節點的失效導致網絡負載的重分配，負載的重分配可能使得某些節點上的負載超過其容量而失效，這些節點的失效又可能導致其他節點的級聯失效（cascading failure）^[4]。如果開始移除的是一個重要的關鍵節點，它的移除可能觸發整個網絡的崩潰，稱之為級聯崩潰（cascading breakdown）。這種現象^[5，6]比故意攻擊網絡的后果更嚴重^[2]。最典型的一個例子是2003年北美電力網大崩潰事故。北美電力網就因為頻率異動瞬間波及全網，導致級聯崩潰。同樣的問題也存在于因特網^[7，8]、通信網^[9]、交通物流網以及其他社會經濟系統網絡中^[10]。例如，2008年奧運會期間，突發事件就有可能造成北京交通網絡的級聯崩潰，即交通癱瘓。級聯失效的本質是一種相關失效^[11]，而網絡安全中的相關失效行為一直是一個非常棘手的問題，這源于對網絡中相關失效機理知之甚少，特別是定量分析方法非常缺乏。復雜網絡上的級聯失效研究近年來得到了很大關注。2002年，Watts給出了一個級聯失效過程的簡單模型^[5]，它能轉換到一類滲流模型之上，從而可以利用與針對簡單頂點刪除過程而言類似的生成函數方法來解。2002年，Holme等人^[4，10]研究了演化網絡上的級聯失效，提出了一個基于負載重分配的級聯失效模型，Motter等人^[3]研究發現非同質拓撲結構中級聯失效對選擇性打擊的敏感性，Moreno^[12]；2004年，Zhao Liang等人^[13]研究了級聯失效中的臨界現象，Motter^[14]研究了級聯失效的防御和控制，Dobson等人^[7~9]研究了電力網中的級聯失效問題， Wang Xiao-fan等人^[15]研究了耦合映像格子中的級聯失效；2006年，Wu和Zhao等人^[16]研究了具有群落結構的無標度網絡的級聯失效問題，并提出了一種新的路由規則來控制無標度網絡的級聯失效^[17]。

這些已有的基于級聯失效的網絡抗毀性模型并不適合復雜保障網絡：模型不能反映網絡不同節點對之間發送不同的物資量；不同環境下的網絡流量強度不同，模型不能反映這種不同的網絡流量強度對抗毀性的影響。本文通過引入運載函數和流量強度指數等對網絡流量強度、節點容量等進行了定義，建立了基于級聯失效的復雜保障網絡抗毀性模型，分析了復雜保障網絡在不同流量強度和不同流量分布下的抗毀性。

1基于級聯失效的復雜保障網絡抗毀性模型

復雜網絡抗毀性研究中，用圖G=(V，E)來表示網絡。假設G是一個無向的加權連通圖，有n個節點，m條邊。其中：V={v1，v2，v3，…，vn}代表節點集合；E={e1，e2，e3，…，em}V×V代表邊的集合。

11網絡的節點和邊

在復雜保障網絡中，把所有的保障實體、交通樞紐抽象為節點。將連接節點間的公路、鐵路、水路、航線、管線等抽象成網絡的邊。假設所有不同類型的節點都用vi(i=1，2，…，n)表示，所有不同類型的邊都用ej(j=1，2，…，n)表示。

12流量強度與流量分布

本模型中，定義網絡流量強度為某一時刻進入網絡的物資量總和，即在某一時刻所有節點發送物資量的總和。定義網絡流量分布為網絡中所有節點對之間發送物資量的空間分布。

網絡流矩陣為

U=f11…f1k…f1n



fj1…fjk…fjn



fn1…fnk…fnn(1)



其中：fjk為運載函數，表示節點vj發送給節點vk的物資量。

流量強度NF=fjk，表示所有發送物資量的總和。

定義

fjk=α×(dβj/2+dβk/2)×n/nj=1dβj(j≠k，0≤α≤1)

0(j=k)(2)

其中：dj和dk分別表示節點vj、vk的度；α為流量強度指數，用來調節發送物資量的多少，當α=1，fjk=fmaxjk表示節點對vj、vk之間發送最大物資量；β為流量分布指數，用來表示運載函數和度的關聯程度。這樣可以得到

NF=fjk=α×n(n-1)(3)

流量強度NF由網絡的大小n和流量強度指數α決定，與β無關。這樣改變α的大小就可以改變流量強度。

當β＞0時，表示fjk與節點的度正相關，節點的度越大，該節點越重要，發送的物資量越多；當β＜0時，表示fjk與節點的度負相關，節點的度越大，該節點越不重要，發送的物資量越少；當β=0，α=1時，表示所有節點對之間發送的物資量都為一個單位，與已有模型的假設一致。本模型中，在流量強度NF不變（α值不變）的條件下，改變β值，可以改變網絡的流量分布。

13節點的負載量

本模型中，定義節點vi的負載量Fi(i=1，2，3，…，n)，為所有節點對vj、vk之間按照最短路（如時間最短、距離最短）原則發送的物資，經過節點vi的流量和

Fi=j≠kfjk(i)(i=1，2，3，…，n)(4)

其中： fjk(i)為節點對vj、vk之間發送fjk的物資經過節點vi的流量。

14節點的容量

節點的容量表示節點可以承受的最大負載量。本模型中，定義節點vi的容量

Ci=Fmaxi=j≠kfmaxjk(i)(i=1，2，3，…，n)(5)

fmaxjk(i)表示所有節點對vj、vk之間發送最大物資量fmaxj，k(α=1)時經過節點vi的流量。

15負載的重分配策略

基于級聯失效的抗毀性模型的負載重分配策略有很多形式，在本模型中，假設當某個節點或（和）邊出現故障時，經過這些損壞節點或邊的運輸物資將按重新計算出來的新的最短路運輸，實現了網絡負載重分配。

16級聯失效過程

在本模型中，節點的初始攻擊（initial damage）被處理為刪除一個節點，初始節點的刪除導致網絡負載的重分配，因網絡中節點的最大容量是確定的，重分配的負載可能會超過某些節點的容量，從而導致這些節點出現級聯故障。這些故障節點也從網絡中刪除。這些級聯故障節點的刪除又可能產生下一輪的負載重分配，可能出現新的級聯故障，該級聯過程可延續到沒有新的級聯故障節點出現才停止。在剩余網絡（節點刪除以后的網絡）中，網絡可能被分割成一些不連通的子網和孤立節點，子網內部可實現相互間的物資發送，而孤立節點則不具備物資的發送和接收能力。

17抗毀性的度量

在本文中，用級聯失效后網絡的最大連通片尺寸與網絡尺寸之比^[14]來度量復雜保障網絡的抗毀性，即

R=N′/N(6)

其中：N表示復雜保障網絡在攻擊以前網絡節點的數目；N′表示在攻擊以后最大連通尺寸中節點的數目。

2仿真分析

21仿真設計

仿真設計主要包括網絡結構、攻擊形式的設計，以及對網絡在不同流量強度和不同流量分布下抗毀性的比較分析。

1)網絡結構復雜保障網絡是介于無標度網絡和隨機網絡之間的一種網絡。本文分別以Barabasi的BA模型^[18]生成的無標度網絡、ER模型^[19]生成的隨機網絡和某保障網絡作為研究對象。為了進行對比分析，三種網絡的節點數均為100，每種網絡產生10個。在本文中，BA網絡初始節點n0=2，每個時間步增加一個節點和m=2條邊，平均度dk=4。ER隨機網絡中任意兩節點的連接概率p=0.04，平均度dj=4。保障網絡由保障系統中的交通網絡、存儲網絡和中轉網絡抽象而成，平均度di=38。

2)攻擊形式本文主要研究復雜保障網絡在故意攻擊和隨機失效兩種條件下的抗毀性。在仿真過程中故意攻擊是指移除網絡中負載量最大的單個節點；隨機失效是指隨機的移除網絡中的單個節點。

3)比較設計首先比較分析不同的流量強度下（不同α）每種網絡對于單個節點移除的抗毀性；然后比較分析不同的流量分布下（不同β）每種網絡對于單個節點移除的抗毀性。

22仿真結果

1)不同流量強度下網絡的抗毀性不同流量強度下網絡的抗毀性需要研究的是在網絡流量分布均勻（β=0）的條件下不同的流量強度對于抗毀性的影響。圖1（a）表示ER隨機網絡在不同的流量強度下對于單個節點移除的抗毀性；圖1（b）表示BA網絡在不同流量強度下對于單個節點移除的抗毀性；圖1（c）表示復雜保障網絡在不同流量強度下對于單個節點移除的抗毀性。其中，空心圓表示故意攻擊（intentional attacks）；實心圓表示隨機失效（random failure）。圖的橫軸表示α，用來度量流量強度；圖的縱軸表示最大連通片比R，用來度量網絡的抗毀性。每種網絡都對10個具體網絡的仿真結果進行平均，每一個網絡都仿真10次。

通過仿真結果分析發現：ER隨機網絡（圖1（a））在流量強度不大時對單個節點的移除表現出很強的抗毀性，在α的一段變化區間內（α＜0.5），網絡隨著α的變化，抗毀性曲線幾乎沒有變化；隨機失效和故意攻擊都存在一個α臨界點α*，當α＜α*，網絡完好；當α＞α*，網絡開始級聯失效，隨機失效中α*≈0.7，故意攻擊中α*≈0.5。BA網絡（圖1（b））中，網絡對于隨機失效和故意攻擊的抗毀性差異很大，隨機失效在α=0.7時網絡的抗毀性仍然很好（R＞0.9），甚至在網絡接近飽和狀態時（α=0.9），網絡的抗毀性指標還可以達到70%以上；相反，故意攻擊在流量強度很小時就出現級聯失效（α*=02），在α=0.7時，網絡幾乎崩潰（R＜0.15）。復雜保障網絡（圖1（c））中，故意攻擊的α臨界點在α很小時就出現了（α*≈01），在α=0.4時，網絡抗毀性指標（R）已經降到40%以下；隨機失效的α臨界點為α*≈0.7，在流量強度達到滿負荷時（α≈1），保障網絡對于隨機失效的抗毀性指標（R）依然能達到50%以上，這說明復雜保障網絡對于隨機失效有較好的抗毀性，對于故意攻擊的抗毀性很差。

2)不同流量分布下的抗毀性在復雜保障網絡中，節點對之間發送的物資量與節點的重要性有關。模型中以度的函數（運載函數fjk）來表示這種關系，通過改變β，可以改變網絡流量分布。圖2（a）表示ER隨機網絡在不同流量分布（不同β）下對于故意攻擊的抗毀性；圖2（b）表示ER隨機網絡在不同流量分布（不同β）下對于隨機失效的抗毀性；圖2（c）表示BA網絡在不同流量分布（不同β）下對于故意攻擊的抗毀性；圖2（d）表示BA網絡在不同流量分布（不同β）下對于隨機失效的抗毀性；圖2（e）表示復雜保障網絡在不同流量分布（不同β）下對于故意攻擊的抗毀性；圖2（f）表示復雜保障網絡在不同流量分布（不同β）下對于隨機失效的抗毀性。圖的橫軸表示流量強度指數α，用來度量流量強度，圖的縱軸表示最大連通片比R，用來度量網絡的抗毀性。每種網絡都對10個具體網絡的仿真結果進行平均，每一個網絡都仿真10次。

仿真結果表明，在ER隨機網絡（圖2（a）（b））中，在流量強度很小時（α＜0.5），無論是故意攻擊還是隨機失效，網絡的抗毀性都很好（R＞0.9）；隨機網絡對于故意攻擊和隨機失效的抗毀性曲線很相似，只是α臨界點（α*）有些差異，隨機失效的α*比故意攻擊的α*稍大，網絡的抗毀性都隨著β的減小而遞增，當β=-3時，網絡的抗毀性最好，即使網絡滿負荷運行（α=1），網絡的抗毀性指標（R）均可以達到80%以上。

在BA網絡中（圖2（c）），存在一個故意攻擊臨界點（α′≈0.5），當α＜α′時，網絡抗毀性隨β遞增，β越大，網絡抗毀性越好；當α＞α′時，網絡抗毀性隨β遞減，β越小，網絡抗毀性越好；并且對于β＜0，網絡抗毀性在流量強度未飽和時存在一個極小值點（用α#表示流量強度未飽和點），如β=-1時，極小值為R=0.15， α#=0.8；β=-3時，極小值為R=0.4，α#=07，在流量強度小于α#以前網絡的抗毀性隨著流量強度遞增而變差，而在流量強度大于α#時網絡的抗毀性隨著流量強度的遞增而變好。BA網絡的隨機失效（圖2（d）），在流量強度較小時（α＜0.6），抗毀性指標（R）在80%以上，在β=0時，抗毀性最好，即使流量強度接近滿負荷（α=0.9），抗毀性指標仍然能達到70%以上。

復雜保障網絡對于故意攻擊（圖2（e））的抗毀性在流量強度很小時(α=0.1)就出現了級聯失效。隨著流量強度的增加，網絡的抗毀性不斷下降。并且，發現網絡的抗毀性隨著β的減小而增加，當β=-3時，在α變化的大部分區間內（α＜0.85），網絡的抗毀性指標均能保持在50%以上。復雜保障網絡（圖2（f））對于隨機失效的抗毀性較好，在α=0.6時，網絡的抗毀性指標（R）可以達到80%以上，網絡的抗毀性對于β的變化不明顯，當β=0時，網絡的抗毀性最好。從圖2（e）與（f）比較可知，復雜保障網絡對于隨機失效有較好的抗毀性，而對于故意攻擊的抗毀性較差，通過改變網絡的流量分布（β=-3），可以提高復雜保障網絡的抗毀性。

3結束語

本文提出了基于級聯失效的復雜保障網絡抗毀性模型，仿真分析了復雜保障網絡在不同流量強度和不同流量分布條件下的網絡抗毀性，發現復雜保障網絡對于故意攻擊在流量強度很小時就出現級聯失效。在流量強度較大時，更可能使得網絡整體崩潰，而對于隨機失效卻表現出很好的抗毀性，即使在網絡滿負荷運行時，網絡抗毀性也能達到50％以上。不同的流量分布也能使得網絡的抗毀性發生變化，找到合適的流量分布，可以提高網絡的抗毀性。

參考文獻：

［1］

BROADBENT S R，HAMMERSLEY J M. Percolation processes: I.crystals and mazes [J].Proc Cambridge Philos Soc，1957，53:629-641.

［2］ALBERT R，JEONG H，BARABSI A L.Error and attack tolerance of complex networks [J].Nature，2000，406(6794):378-382.

［3］MOTTER A E，LAI Y C.Cascade-based attacks on complex networks [J].Phys Rev E，2002，66(6):065102.

［4］HOLME P.Edge overload breakdown in evolving networks[J].Phys Rev E，2002，66(3):036119.

［5］WATTS D J.A simple model of global cascades on random networks [J].Proc Natl Acad Sci，2002，99(9):5766-5771.

［6］MORENO Y，GMEZ J B，PACHECO A F.Instability of scale-free networks under node-breaking avalanches[J].Europhys Lett，2002，58(4):630-636.

［7］DOBSON I，CARRERAS B A，LYNCH V E，et al.Estimating failure propagation in models of cascading lackouts[C]//Proc of Internatio-nal Conference on Probabilistic Methods Applied to Power Systems.2004.

［8］DOBSON I，CARRERAS B A，NEWMAN D E.A probabilistic loading-dependent model of cascading failure and possible implications for blackouts[C]//Proc of the 36th Hawaii International Confe-rence on System Sciences.Hawaii:IEEE Computer Society，2003.

［9］DOBSON I，CARRERAS B A，NEWMAN D E.Probabilistic load-dependent cascading failure with limited component interactions[C]//Proc of International Symposium on Circuits and Systems.2004.

［10］HOLME P，KIM B J.Vertex overload breakdown in evolving networks [J].Phys Rev E，2002，65(6):066109.

［11］李翠玲，謝里陽.相關失效分析方法評述與探討[J].機械設計與制造，2003(3):1-3.

［12］MORENO Y，PASTOR-SATORRAS R，VZQUEZ A，et al.Critical load and congestion instabilities in scale-free networks[J].Europhys Lett，2003，62(2): 292-298.

［13］ZHAO Liang，KWANGHO P，LAI Y C.Attack vulnerability of scale-free networks due to cascading breakdown[J].Phys Rev E，2004，70(3):035101.

［14］MOTTER A E.Cascade control and defense in complex networks[J].Phys Rev Lett，2004，93(9):098701.

［15］WANG Xiao-fan，XU J.Cascading failures in coupled map lattices[J].Phys Rev E，2004，70(5):056113.

［16］WU Jian-jun，GAO Zi-you.Cascade and breakdown in scale-free networks with community structure [J].Phys Rev E，2006，74(6):066111.

［17］ZHAO Hui，GAO Zi-you.Cascade defense via navigation in scale free networks [J].Eur Phys J B，2007，57:95-101.

［18］BARABSI A L，ALBERT R，JEONG H.Mean-field theory for scale-free random networks [J].Physica A，1999，272:173-187.

［19］ERDS P，RNYI A.On the evolution of random graphs[J].Publ Math Inst Hung Acad Sci，1960，5:17-60.