張 昕， 孫江輝， 劉建華

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

相繼故障模型的一種改進(jìn)

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

2 一種改進(jìn)的相繼故障模型

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

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

對(duì)于式(1)，改進(jìn)的模型為

xi(t+1)=

i=1,2,…,N

(3)

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

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

在第m時(shí)刻，對(duì)某個(gè)節(jié)點(diǎn)c施加一個(gè)外部擾動(dòng)因子R≥1后，節(jié)點(diǎn)狀態(tài)為

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

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

3 仿真分析

全耦合網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)之間都存在連接，是一種理想的網(wǎng)絡(luò)拓?fù)?，用于研究理想網(wǎng)絡(luò)狀態(tài)下的相繼故障。而現(xiàn)實(shí)中，考慮到系統(tǒng)性能、安全、成本等因素，不可能真正實(shí)現(xiàn)全耦合連接。許多網(wǎng)絡(luò)包括Internet、WWW以及新陳代謝網(wǎng)絡(luò)等的連接度分布函數(shù)具有冪律形式[1,10]，符合無標(biāo)度網(wǎng)絡(luò)的特征。冪律分布特性對(duì)于 Internet 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)生成以及網(wǎng)絡(luò)性能改進(jìn)影響很大，BA 模型從動(dòng)態(tài)增長觀點(diǎn)研究復(fù)雜網(wǎng)絡(luò)具有冪律度分布特性的模型,拓?fù)浣Ｑ芯恐衅毡閷⑵渥鳛闊o標(biāo)度網(wǎng)絡(luò)基本模型。BA無標(biāo)度網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的度很小，同時(shí)也存在少量度非常大的節(jié)點(diǎn)，這與Internet的拓?fù)淝闆r十分相似。故將改進(jìn)模型應(yīng)用于全耦合網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)進(jìn)行仿真。

實(shí)驗(yàn)平臺(tái)為Windows XP Professional，仿真工具使用NetLogo 4.0.4和Matlab 7.0。

3.1 全耦合風(fēng)險(xiǎn)網(wǎng)絡(luò)

將改進(jìn)模型應(yīng)用于具有全耦合性質(zhì)的風(fēng)險(xiǎn)網(wǎng)絡(luò)中。

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

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

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

隨機(jī)選擇一個(gè)設(shè)備節(jié)點(diǎn)，施加一個(gè)擾動(dòng)R≥1，重復(fù)進(jìn)行100次實(shí)驗(yàn)，平均相繼故障規(guī)模如圖1所示。

圖1 隨機(jī)對(duì)一個(gè)節(jié)點(diǎn)擾動(dòng)產(chǎn)生的相繼故障

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

圖2 對(duì)節(jié)點(diǎn)943擾動(dòng)產(chǎn)生的相繼故障

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

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

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

圖3 對(duì)節(jié)點(diǎn)1357擾動(dòng)產(chǎn)生的相繼故障

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

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

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

3.2 BA無標(biāo)度風(fēng)險(xiǎn)網(wǎng)絡(luò)

將改進(jìn)模型應(yīng)用于具有冪律分布的BA無標(biāo)度網(wǎng)絡(luò)中。

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

圖4 N=2 000的風(fēng)險(xiǎn)網(wǎng)絡(luò)

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

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

選擇度最大的節(jié)點(diǎn)對(duì)其施加擾動(dòng)，其影響因子Σ(t)為

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

[6] 郭遲,王麗娜,李玉，等.基于負(fù)荷-容量模型的網(wǎng)絡(luò)相繼故障研究[J].計(jì)算機(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] 丁琳,張嗣瀛.復(fù)雜網(wǎng)絡(luò)上相繼故障研究綜述[J]. 計(jì)算機(jī)科學(xué),2012,39(8):8-13.

[責(zé)任編輯：祝劍]

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è)與信息化部軟科學(xué)研究計(jì)劃資助項(xiàng)目(2014-R-31)

張昕(1979-)，男，碩士，工程師，從事網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全研究。 E-mail: zhxin@xupt.edu.cn 孫江輝(1990-)，男,碩士研究生，研究方向?yàn)橐苿?dòng)終端的可信計(jì)算。E-mail:960259591@qq.com

TP393.0

A

2095-6533(2015)04-0019-05