相繼故障模型的一種改進

張 昕， 孫江輝， 劉建華

(1.西安郵電大學 信息中心,陜西 西安 710121;2.西安郵電大學 通信與信息工程學院,陜西 西安 710121)

相繼故障模型的一種改進

張 昕1， 孫江輝2， 劉建華1

(1.西安郵電大學 信息中心,陜西 西安 710121;2.西安郵電大學 通信與信息工程學院,陜西 西安 710121)

針對復雜網(wǎng)絡中存在的相繼故障問題，給出一個改進的相繼故障模型。在基于耦合映像格子的相繼故障模型中引入影響因子，將節(jié)點間的相互影響反映在節(jié)點的狀態(tài)變化中，并在兩種典型網(wǎng)絡中進行仿真分析，結(jié)果表明具有較大影響因子的節(jié)點易引發(fā)相繼故障，應作為網(wǎng)絡風險控制的重要節(jié)點。

復雜網(wǎng)絡;相繼故障;耦合映像格子；影響因子

網(wǎng)絡中的節(jié)點間存在耦合關(guān)系，當節(jié)點發(fā)生故障時會引起連鎖反應，從而導致其他節(jié)點也隨之出現(xiàn)故障，甚至進一步惡化導致整個網(wǎng)絡癱瘓，這種現(xiàn)象稱為相繼故障，也叫雪崩[1]。在Internet中，對一些路由器進行攻擊會導致系統(tǒng)過載，當網(wǎng)絡對流量進行重新路由時，則會引起其他路由器接連過載，繼而引發(fā)相繼故障。因此，基于相繼故障模型研究網(wǎng)絡節(jié)點對周圍節(jié)點的影響，能夠?qū)W(wǎng)絡風險進行評估。

研究復雜網(wǎng)絡相繼故障常見的模型是基于負荷-容量的模型和基于耦合映像格子的模型。目前主要從網(wǎng)絡負載以及網(wǎng)絡冗余對網(wǎng)絡魯棒性的影響[2]、邊級聯(lián)故障蔓延的動力學演化機制[3]、網(wǎng)絡初始負荷的分布與失效后節(jié)點負荷的分配規(guī)則對相繼故障的影響[4]、有向網(wǎng)絡耦合映像格子的相繼故障模型[5]等方面進行了研究，取得了一些成效。但負荷-容量模型僅研究節(jié)點負荷與容量的關(guān)系[6-8]，適用范圍有限；基于耦合映像格子的模型[9]能反映某一節(jié)點失效后對周圍節(jié)點的影響，但是對于具有同樣度分布的節(jié)點，卻不能反映所引起的相繼故障的差異。

根據(jù)網(wǎng)絡在發(fā)生故障時節(jié)點的狀態(tài)變化不僅與自身的度有關(guān)，同時還與節(jié)點的負載有關(guān)，本文在基于耦合映像格子的相繼故障模型中引入影響因子，將互相連接的網(wǎng)絡節(jié)點間的負載關(guān)系反應在節(jié)點狀態(tài)的變化中，建立一個改進的模型；此外還通過將閾值倒數(shù)定義為風險指標，對網(wǎng)絡產(chǎn)出相繼故障的風險進行研究。

1 基于耦合映像格子的相繼故障模型

對于一個包含N個節(jié)點的網(wǎng)絡，基于耦合映像格子(Coupled Map Lattice，CML)的相繼故障模型[9]為

(1)

其中xi(t)表示第i個節(jié)點在t時刻的狀態(tài)，i=1,2,…,N。k(i)是節(jié)點i的度，ε∈(0,1)表示耦合強度，絕對值符號則保證各節(jié)點的狀態(tài)非負。設矩陣A=(aij)N×N表示N個節(jié)點的連接信息。若節(jié)點i和j之間有邊相連，則aij=aji=1；否則aij=aji=0。規(guī)定任意不同的兩個節(jié)點最多只能有一條邊相連，且節(jié)點不能與自身相連。這樣矩陣A就成為一個對稱陣，且只有0,1兩種元素，其對角線取值均為0。選擇混沌Logistic映射f(x)=4x(1-x)作為非線性函數(shù)，用以表征節(jié)點自身的動態(tài)行為。當0≤x≤1時，0≤f(x)≤1。

對于節(jié)點i的狀態(tài)，如果在m個時序內(nèi)始終滿足0m)。

一個有N個節(jié)點的網(wǎng)絡，其節(jié)點狀態(tài)按式(1)迭代演化，如果所有節(jié)點的初始狀態(tài)都在(0，1)范圍內(nèi)，并且不發(fā)生外部擾動，那么網(wǎng)絡中的全部節(jié)點都將始終維持在正常狀態(tài)。如果某節(jié)點在時刻m受到?jīng)_擊，即對節(jié)點c施加一個外部擾動R≥1,節(jié)點狀態(tài)為

(2)

在這種情況下，節(jié)點c的狀態(tài)xc(m)將滿足xc(m)>1，即發(fā)生故障，進而對于所有的t>m有xc(t)≡0，即節(jié)點不可用。在m+1時刻，所有節(jié)點c的鄰居節(jié)點，都會受到xc(m)的影響，這些節(jié)點的狀態(tài)值可由式(1)得出，此時節(jié)點狀態(tài)值可能大于1而發(fā)生故障，從而引起局部或全局相繼故障。

2 一種改進的相繼故障模型

依據(jù)現(xiàn)實計算機風險網(wǎng)絡模型，對計算機網(wǎng)絡節(jié)點的評估不僅要考慮節(jié)點自身存在的漏洞等風險，還要考慮該節(jié)點對周圍節(jié)點的影響即考慮相鄰兩節(jié)點之間的互相作用產(chǎn)生的風險，由此給出一種改進的模型。給出如下定義。

定義1 影響因子：相連的兩計算機設備節(jié)點i和j，在某一時間t，由i發(fā)出至j的數(shù)據(jù)總量與由j發(fā)出至i的數(shù)據(jù)總量的比例定義為節(jié)點i對節(jié)點j的影響因子，記為σi,j(t)，σi,j(t)>0，反之為σj,i(t)。顯然σi,j(t)σj,i(t)=1，并令σi,i(t)≡0。N個節(jié)點的動態(tài)影響矩陣為Σ(t)=(σi,j(t))N×N。

對于式(1)，改進的模型為

xi(t+1)=

i=1,2,…,N

(3)

對于節(jié)點i，在t+1時刻的狀態(tài)xi(t+1)由當前t時刻的本身狀態(tài)xi(t)和與節(jié)點i相連的所有節(jié)點狀態(tài)共同影響。其中σj,i(t)為t時刻節(jié)點j對節(jié)點i的影響因子，ε∈(0,1)表示耦合強度，非線性函數(shù)f(x)為節(jié)點自身動態(tài)行為。這里依舊選擇混沌Logistic映射f(x)=4x(1-x)。當0≤x≤1時，0≤f(x)≤1。

式(3)中(1-ε)f(xi(t))反應了節(jié)點對自身狀態(tài)的影響，相對于式(1)只考慮了節(jié)點間是否有相互連接關(guān)系(即節(jié)點i的度k(i))對節(jié)點狀態(tài)產(chǎn)生的影響，式(3)中的影響因子σi,j(t)不僅能反映節(jié)點間的連接關(guān)系，還能量化表示節(jié)點j和節(jié)點i之間的負荷關(guān)系，從而能更好的描述節(jié)點的狀態(tài)變化。

在第m時刻，對某個節(jié)點c施加一個外部擾動因子R≥1后，節(jié)點狀態(tài)為

此時xi(m)>1，即節(jié)點c發(fā)生故障，對于所有的t>m有xc(t)≡0。在第m+1時刻，所有節(jié)點c的鄰居節(jié)點，都將受到xc(m)的影響，其狀態(tài)值可由式(3)得出。

對于不同的Σ(t)，Rc1和Rc2的值不同，說明了不同的節(jié)點出現(xiàn)故障，雖然其出入度情況相同，但其在整個網(wǎng)絡中作用不同，因而造成的風險也不同。

3 仿真分析

全耦合網(wǎng)絡中的任意兩個節(jié)點之間都存在連接，是一種理想的網(wǎng)絡拓撲，用于研究理想網(wǎng)絡狀態(tài)下的相繼故障。而現(xiàn)實中，考慮到系統(tǒng)性能、安全、成本等因素，不可能真正實現(xiàn)全耦合連接。許多網(wǎng)絡包括Internet、WWW以及新陳代謝網(wǎng)絡等的連接度分布函數(shù)具有冪律形式[1,10]，符合無標度網(wǎng)絡的特征。冪律分布特性對于 Internet 網(wǎng)絡拓撲結(jié)構(gòu)生成以及網(wǎng)絡性能改進影響很大，BA 模型從動態(tài)增長觀點研究復雜網(wǎng)絡具有冪律度分布特性的模型,拓撲建模研究中普遍將其作為無標度網(wǎng)絡基本模型。BA無標度網(wǎng)絡中大部分節(jié)點的度很小，同時也存在少量度非常大的節(jié)點，這與Internet的拓撲情況十分相似。故將改進模型應用于全耦合網(wǎng)絡和BA無標度網(wǎng)絡進行仿真。

實驗平臺為Windows XP Professional，仿真工具使用NetLogo 4.0.4和Matlab 7.0。

3.1 全耦合風險網(wǎng)絡

將改進模型應用于具有全耦合性質(zhì)的風險網(wǎng)絡中。

假設一個N=2 000,ε=0.6的全局耦合映像格子(CML)，其影響因子矩陣Σ(t)(關(guān)于矩陣主對角線互為倒數(shù))為

其中第一列表示所有節(jié)點對第一個節(jié)點的影響因子向量，以此類推。

對于給定的網(wǎng)絡規(guī)模N和耦合強度ε∈(0,1)，節(jié)點C存在兩個閾值Rc1、Rc2(Rc1

隨機選擇一個設備節(jié)點，施加一個擾動R≥1，重復進行100次實驗，平均相繼故障規(guī)模如圖1所示。

圖1 隨機對一個節(jié)點擾動產(chǎn)生的相繼故障

由于改進模型中采用影響因子作為權(quán)重，因此不同節(jié)點抵御相繼故障的能力不同。圖2所示為對節(jié)點943進行擾動，產(chǎn)生相繼故障的規(guī)模。

圖2 對節(jié)點943擾動產(chǎn)生的相繼故障

對于給定的Σ(t)，計算機設備節(jié)點943被攻擊或意外而出現(xiàn)故障，節(jié)點943對其他節(jié)點的影響因子向量為

可計算得出，向量各分量所表示前942個節(jié)點的閾值比后1 057個節(jié)點閾值大，且前后兩組節(jié)點的閾值依次遞增。從圖2中可看出，在RRc2=44.7后，出現(xiàn)全局相繼故障。節(jié)點943的風險可記為 [1/30.76,1/44.7]。

圖3為對節(jié)點1357進行擾動，產(chǎn)生相繼故障的規(guī)模。

圖3 對節(jié)點1357擾動產(chǎn)生的相繼故障

與圖2所示相比，只是選取的擾動節(jié)點不同，而該節(jié)點對其他節(jié)點的影響因子向量為

顯然∑σ1 357,x<∑σ943,x，因此其它節(jié)點抗相繼故障的能力增加，說明節(jié)點1 357的風險影響較小。由圖3可知，兩閾值分別為Rc1=34.6，Rc2=51.7，節(jié)點1 357風險為[1/34.6,1/51.7]。

由實驗可知，在改進模型中度相同的節(jié)點由于其對周圍節(jié)點影響因子的不同，產(chǎn)生相繼故障規(guī)模也就不同。對于影響因子向量大的節(jié)點應重點采取安全防御措施，因為這些節(jié)點使得其他節(jié)點的抗相繼故障能力下降，造成的相繼故障規(guī)模較大，因而風險大，而對于影響因子小的節(jié)點，由于造成的風險小，則可節(jié)約成本而采取相應的防御措施。

3.2 BA無標度風險網(wǎng)絡

將改進模型應用于具有冪律分布的BA無標度網(wǎng)絡中。

根據(jù)BA無標度網(wǎng)絡生成算法，取m0=2，m=2生成一個BA無標度網(wǎng)絡，生成的網(wǎng)絡如圖4所示。

圖4 N=2 000的風險網(wǎng)絡

檢測生成的網(wǎng)絡節(jié)點度的分布，其節(jié)點度分布p(k)∝1/k3，與BA網(wǎng)絡度分布函數(shù)2m2k-3接近。

基于BA無標度網(wǎng)絡中度分布的非均勻性，引入隨機故障和蓄意攻擊這兩種引發(fā)相繼故障的策略。前者模擬網(wǎng)絡中隨機發(fā)生的節(jié)點故障，初始的擾動施加給隨機選擇的一個節(jié)點；后者模擬網(wǎng)絡遭受攻擊，攻擊者一般總會選擇那些相對重要的節(jié)點，因此把擾動施加給網(wǎng)絡中度最大的節(jié)點。

選擇度最大的節(jié)點對其施加擾動，其影響因子Σ(t)為

影響因子為0表示節(jié)點之間沒有連接。其相繼故障規(guī)模如圖5所示,Rc1≈1.0，Rc2≈1.5。

圖5 過載度最大的節(jié)點產(chǎn)生相繼故障規(guī)模

選擇一個一般節(jié)點施加擾動，其相繼故障規(guī)模如圖6所示，其中Rc1≈25.0，Rc2≈28.0。由圖5和圖6可知，其對應的Rc1和Rc2兩個閾值小于全耦合網(wǎng)絡，并且兩閾值之差也較小，說明BA無標度網(wǎng)絡抗相繼故障的能力比全耦合網(wǎng)絡的能力要低很多，因此各個節(jié)點所產(chǎn)生的風險相應較大。連接越多，承擔較大負荷的節(jié)點一旦發(fā)生故障，發(fā)生相繼故障的概率就越大，產(chǎn)生的風險影響就越大。

圖6 過載一般節(jié)點產(chǎn)生相繼故障規(guī)模

4 結(jié)束語

通過引入反映網(wǎng)絡節(jié)點間相互作用的影響因子，對基于耦合映像格子的相繼故障模型進行了改進，同時也在網(wǎng)絡系統(tǒng)中定義了計算機設備節(jié)點的風險大小，并在全耦合網(wǎng)絡和BA無標度網(wǎng)絡中對該改進模型進行了仿真。結(jié)果表明，在度相同的情況下，對具有不同影響因子的節(jié)點施加擾動，產(chǎn)生的相繼故障規(guī)模也不相同。同時模型給出的風險指標可用于對網(wǎng)絡風險進行評估。

[1] 汪小帆,李翔,陳關(guān)榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社，2006:72-130.

[2] 徐野,王瑤.復雜網(wǎng)絡相繼故障的節(jié)點動態(tài)分析[J].沈陽理工大學學報,2015,34(1):17-21.

[3] 王建偉,蔣晨,孫恩慧.耦合網(wǎng)絡邊相繼故障模型研究[J].管理科學,2014,27(6):132-142.

[4] 段東立.基于負載最近鄰偏好分配的復雜網(wǎng)絡連鎖效應[J].復雜系統(tǒng)與復雜性科學,2015,12(1):33-39.

[5] 馬秀娟,馬福祥,趙海興.基于耦合映像格子的有向網(wǎng)絡相繼故障[J].計算機應用,2011,31(7):1952-1955.

[6] 郭遲,王麗娜,李玉，等.基于負荷-容量模型的網(wǎng)絡相繼故障研究[J].計算機研究與發(fā)展,2012,49(12):2529- 2538.

[7] Moreno Y, Gómez J B, Pacheco A F. Instability of scale-free networks under node-breaking avalanches [J]. Epl, 2002, 58(4):630-636.

[8] Moreno Y, Pastor-Satorras R, Vazquez A, et al. Critical load and congestion instabilities in scale-free networks[J]. Epl, 2002, 62(2):292-298.

[9] Wang X F, Xu J. Cascading failures in coupled map lattices [J]. Physical Review E, 2004, 70(5):056113.

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

[責任編輯：祝劍]

An improvement of the cascading failure model

ZHANG Xin1， SUN Jianghui2， LIU Jianhua1

(1. Information Center, Xi’an University of Posts and Telecommunications, Xi’an 710121, China; 2. School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

An improved cascading failure model in complex networks is proposed in this paper. Some impact factors are introduced into the cascading failure model based on coupled map lattices, thus, the interrelationship of various nodes can be drawn from their status changing. Simulation analysis in two typical networks shows that, the node with greater impact factor is easier to suffer cascading failure, and must be paid more attentions to in networks risk management.

complex network, cascading failure, coupled map lattice(CML)，influence factor

10.13682/j.issn.2095-6533.2015.04.004

2015-04-23

工業(yè)與信息化部軟科學研究計劃資助項目(2014-R-31)

張昕(1979-)，男，碩士，工程師，從事網(wǎng)絡管理和網(wǎng)絡安全研究。 E-mail: zhxin@xupt.edu.cn 孫江輝(1990-)，男,碩士研究生，研究方向為移動終端的可信計算。E-mail:960259591@qq.com

TP393.0

A

2095-6533(2015)04-0019-05