劉笑辰，朱 磊，夏 蘇（解放軍理工大學(xué)通信工程學(xué)院，江蘇南京210007）

一種增強(qiáng)復(fù)雜網(wǎng)絡(luò)抵御相繼故障能力的路由算法研究*

劉笑辰，朱 磊，夏 蘇
（解放軍理工大學(xué)通信工程學(xué)院，江蘇南京210007）

在現(xiàn)實生活中，許多大型的通信網(wǎng)絡(luò)或電力網(wǎng)絡(luò)都可以應(yīng)用復(fù)雜網(wǎng)絡(luò)進(jìn)行刻畫。然而網(wǎng)絡(luò)中某些“關(guān)鍵節(jié)點”一旦遭到攻擊極易引發(fā)相繼故障。這種現(xiàn)象的存在極大降低了網(wǎng)絡(luò)的可靠性。為了提高網(wǎng)絡(luò)對相繼故障的抵御能力，針對現(xiàn)有基于最短路徑的路由算法加以改進(jìn)，降低“關(guān)鍵節(jié)點”在網(wǎng)絡(luò)中所起的作用，提高了網(wǎng)絡(luò)負(fù)載在各節(jié)點間分布的均衡性。通過在典型的復(fù)雜網(wǎng)絡(luò)上進(jìn)行的仿真實驗，證明了改進(jìn)的路由算法能夠大大增強(qiáng)網(wǎng)絡(luò)對相繼故障的抵御能力。

復(fù)雜網(wǎng)絡(luò)；相繼故障；路由算法；網(wǎng)絡(luò)可靠性

O 引言

現(xiàn)實生活中的諸多網(wǎng)絡(luò)比如電力網(wǎng)、通信網(wǎng)、交通網(wǎng)以及社交網(wǎng)等都可以用復(fù)雜網(wǎng)絡(luò)模型進(jìn)行描述。A1bert等人提出復(fù)雜網(wǎng)絡(luò)中的相繼故障現(xiàn)象［1］，即網(wǎng)絡(luò)中極少數(shù)所謂的“關(guān)鍵節(jié)點”遭到破壞將引起連鎖反應(yīng)，導(dǎo)致整個網(wǎng)絡(luò)呈現(xiàn)雪崩式毀壞。相繼故障的存在對社會生活的正常運(yùn)行構(gòu)成了極大的威脅。

為了減少相繼故障的危害，提高網(wǎng)絡(luò)的可靠性，許多學(xué)者進(jìn)行了卓有成效的研究。參考文獻(xiàn)［2］按照一定的規(guī)則在網(wǎng)絡(luò)中選擇某些節(jié)點執(zhí)行一次防御策略，如果被保護(hù)的節(jié)點負(fù)載超過閾值則將額外的負(fù)載分配給鄰居從而避免本身發(fā)生故障。參考文獻(xiàn)［3 -5］注重在網(wǎng)絡(luò)中發(fā)現(xiàn)在相繼故障過程中更加重要的節(jié)點。由于在現(xiàn)實中，往往多個網(wǎng)絡(luò)相互作用形成一個耦合的整體，參考文獻(xiàn)［6 -7］在耦合網(wǎng)絡(luò)中挖掘重要組成部分并且設(shè)計出負(fù)載分配策略。

在當(dāng)前復(fù)雜網(wǎng)絡(luò)相繼故障的防御策略研究中，大多數(shù)學(xué)者著眼于發(fā)現(xiàn)網(wǎng)絡(luò)中起到關(guān)鍵作用的節(jié)點或組成部分，而缺少對網(wǎng)絡(luò)中路由算法的改進(jìn)以提高網(wǎng)絡(luò)的可靠性。本文通過對現(xiàn)有基于最短路徑的路由算法加以改進(jìn)，將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響體現(xiàn)到傳輸鏈路的效率中，降低復(fù)雜網(wǎng)絡(luò)中節(jié)點負(fù)載的異質(zhì)性，進(jìn)而提高網(wǎng)絡(luò)對相繼故障的抵御能力。

1 基于最短路徑路由算法的改進(jìn)研究

在計算網(wǎng)絡(luò)中的源節(jié)點到目的節(jié)點最短路徑的過程中，節(jié)點間鏈路的傳輸耗費是一個關(guān)鍵的參數(shù)。本文通過對節(jié)點間傳輸?shù)膶嶋H耗費進(jìn)行修正得到虛擬耗費，然后根據(jù)虛擬耗費計算節(jié)點之間的最短路徑。通過虛擬耗費的計算降低經(jīng)過度數(shù)大的節(jié)點的路徑數(shù)目，從而降低這些節(jié)點的負(fù)載，進(jìn)而減少各節(jié)點負(fù)載之間的異質(zhì)性使得網(wǎng)絡(luò)更加健壯。

1.1 算法的基本思想

令網(wǎng)絡(luò)G中各節(jié)點之間的鄰接矩陣為A，其中aij為其中的一個元素，并有：

其中eij表示節(jié)點i與j之間的連邊。

假設(shè)網(wǎng)絡(luò)中的節(jié)點數(shù)為n，存在實際耗費因子向量Cr表示各節(jié)點對相鄰的邊傳輸實際耗費的影響，其中λri為節(jié)點i的實際耗費因子，根據(jù)節(jié)點的實際耗費因子可得邊eij傳輸?shù)膶嶋H耗費為：

考慮到復(fù)雜網(wǎng)絡(luò)中各節(jié)點間度數(shù)分布的異質(zhì)性，為了防止網(wǎng)絡(luò)中度數(shù)大的節(jié)點承擔(dān)過多的負(fù)載，根據(jù)節(jié)點的度數(shù)對其實際耗費因子進(jìn)行修正得到節(jié)點的虛擬耗費因子。令節(jié)點i的虛擬耗費因子為：

式（3）的計算將在下節(jié)中討論。根據(jù)式（3）可以得到虛擬耗費因子向量，從而得到eij的虛擬耗費：

根據(jù)網(wǎng)絡(luò)的虛擬耗費矩陣計算各節(jié)點之間傳輸?shù)淖疃搪窂?，可以采用F1oyd、Be11man-Ford、SPFA等算法［8］得到網(wǎng)絡(luò)間節(jié)點傳輸?shù)穆酚杀?。運(yùn)用上述方法得到的結(jié)果可以有效降低網(wǎng)絡(luò)中度數(shù)大的節(jié)點的負(fù)載，提高各節(jié)點間負(fù)載的均衡性。

1.2 節(jié)點虛擬耗費因子的計算

節(jié)點的虛擬耗費因子由該點的度數(shù)和實際耗費因子決定。在計算節(jié)點度的影響時做出如下假設(shè)：

（1）假設(shè)每個節(jié)點存在虛擬負(fù)載，節(jié)點i的負(fù)載為lvi=，其中ki為節(jié)點i的度數(shù)，表示網(wǎng)絡(luò)中節(jié)點的平均度。

（2）每個節(jié)點在單位時間內(nèi)可以處理的負(fù)載與該節(jié)點的度數(shù)成正比，并且其比例系數(shù)與節(jié)點的虛擬負(fù)載成反比。

（3）整個網(wǎng)絡(luò)在單位時間內(nèi)能夠處理掉所有節(jié)點中的虛擬負(fù)載。

對于假設(shè)（1），由于在一個完好的網(wǎng)絡(luò)中不存在孤立的節(jié)點，即所有節(jié)點的度數(shù)都大于等于1，故虛擬負(fù)載lvi可以保證有意義；對于假設(shè)（2），考慮度數(shù)大的節(jié)點能夠與更多的節(jié)點進(jìn)行交流并且算法的最終目的在于均衡節(jié)點間的虛擬耗費因子，由上述假設(shè)可以得到以下方程組：

方程①的左側(cè)表示所有節(jié)點單位時間內(nèi)處理的虛擬負(fù)載，其中1表示負(fù)載傳遞給節(jié)點本身，βi·ki表示負(fù)載傳遞給周圍的鄰居；方程的右側(cè)表示網(wǎng)絡(luò)中所有節(jié)點的虛擬負(fù)載之和。并有當(dāng)kj=0時所對應(yīng)的βj=0。

計算方程（5）可以得到：

對于節(jié)點i而言，最終該點的虛擬耗費因子為：

其中h是一個可調(diào)參數(shù)，該值越大則算法對關(guān)鍵節(jié)點作用的削弱就越大。

圖1表示了在初始實際耗費因子向量Cr（0）=（1，1，1，…，1）時3個不同的無標(biāo)度網(wǎng)絡(luò)中節(jié)點的虛擬耗費因子與度數(shù)的關(guān)系。網(wǎng)絡(luò)1中初始節(jié)點個數(shù)為7，每次新增加的節(jié)點連邊數(shù)為3，算法中h =0.2。網(wǎng)絡(luò)2中初始節(jié)點個數(shù)為8，每次新增加的節(jié)點連邊數(shù)為6，算法中h =0.2。網(wǎng)絡(luò)3中初始節(jié)點個數(shù)為8，每次新增加的節(jié)點連邊數(shù)為6，算法中h =0.6。從圖中可以看出，在各節(jié)點實際耗費因子相同的情況下，節(jié)點的度數(shù)越大其虛擬耗費因子就越大。通過網(wǎng)絡(luò)2與網(wǎng)絡(luò)3的對比可以發(fā)現(xiàn)，參數(shù)h增大，擬合曲線的斜率也相應(yīng)增大。

圖1 耗費因子計算結(jié)果

2 實驗仿真及結(jié)果研究

在仿真實驗中，本文分別在BA無標(biāo)度網(wǎng)絡(luò)［1］及WS小世界網(wǎng)絡(luò)［9］中對改進(jìn)的路由算法的效果進(jìn)行研究。本文應(yīng)用參考文獻(xiàn)［10］中的相繼故障模型，并且令對任意節(jié)點i均有（0）=1。文中采用平均傳輸效率E（G）衡量網(wǎng)絡(luò)狀態(tài)［11］。E（G）越大表示網(wǎng)絡(luò)在單位時間內(nèi)傳輸能力越強(qiáng)，即網(wǎng)絡(luò)狀態(tài)越好。

圖2是3種不同的無標(biāo)度網(wǎng)絡(luò)發(fā)生相繼故障后網(wǎng)絡(luò)的效率變化。圖中網(wǎng)絡(luò)1表示應(yīng)用基于最短路徑路由算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)2表示應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)。橫坐標(biāo)表示初始時刻網(wǎng)絡(luò)中負(fù)載最大的前n個節(jié)點發(fā)生故障，縱坐標(biāo)表示網(wǎng)絡(luò)的平均傳輸效率。圖（a）、（b）、（c）中的網(wǎng)絡(luò)初始節(jié)點數(shù)分別為4、6、8，每個新增加節(jié)點的連邊數(shù)為3、5、6。各網(wǎng)絡(luò)的節(jié)點總數(shù)均為1 000。實驗選取網(wǎng)絡(luò)中初始負(fù)載最大的若干個節(jié)點使之發(fā)生故障，并記錄發(fā)生相繼故障后經(jīng)過30個時間單位后網(wǎng)絡(luò)的平均傳輸效率E（G）。結(jié)果表明，隨著初始故障節(jié)點的增多，網(wǎng)絡(luò)的平均傳輸效率都會降低。但是在采用傳統(tǒng)的路由算法的網(wǎng)絡(luò)中，網(wǎng)絡(luò)平均效率下降的速度非?？觳⑶以?種情況下最終都接近于0，即網(wǎng)絡(luò)已經(jīng)完全崩潰。在應(yīng)用改進(jìn)后的路由算法的網(wǎng)絡(luò)中，盡管網(wǎng)絡(luò)的效率也發(fā)生了下降，但相比而言其下降速率非常緩慢，根據(jù)圖2（b）、（c），在已有15個節(jié)點發(fā)生故障的情況下，網(wǎng)絡(luò)仍然保持著相當(dāng)程度的平均效率，而與其相對的傳統(tǒng)網(wǎng)絡(luò)已經(jīng)完全崩潰。在圖2中，采用改進(jìn)路由算法的網(wǎng)絡(luò)的初始平均傳輸效率要略小于傳統(tǒng)的網(wǎng)絡(luò)，但其結(jié)果卻大大增強(qiáng)了網(wǎng)絡(luò)對相繼故障的抵抗能力。

圖2 無標(biāo)度網(wǎng)絡(luò)發(fā)生相繼故障后平均傳輸效率的變化

圖3記錄了3種不同的小世界網(wǎng)絡(luò)發(fā)生相繼故障后的變化。圖中網(wǎng)絡(luò)1表示應(yīng)用基于最短路徑路由算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)2表示應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)。圖（a）、（b）、（c）中網(wǎng)絡(luò)的平均度分別為4、6、8。各網(wǎng)絡(luò)隨機(jī)連邊的效率為0.4，節(jié)點總數(shù)均為1 000。實驗同樣使網(wǎng)絡(luò)中初始負(fù)載最大的一些節(jié)點發(fā)生故障。結(jié)果顯示在WS網(wǎng)絡(luò)中，改進(jìn)的路由算法能夠明顯增強(qiáng)網(wǎng)絡(luò)對相繼故障的抵御能力。在應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)中，數(shù)目較少的故障節(jié)點對網(wǎng)絡(luò)造成的危害非常輕微。在圖3（b）、（c）中可以看出，當(dāng)小世界網(wǎng)絡(luò)的平均度數(shù)增大時，應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)具有更強(qiáng)健壯性。

圖3 小世界網(wǎng)絡(luò)發(fā)生相繼故障后平均傳輸效率的變化

在無標(biāo)度網(wǎng)絡(luò)中將本文提出的路由改進(jìn)算法與參考文獻(xiàn)［2］中提供的方法進(jìn)行比較，兩種策略增強(qiáng)網(wǎng)絡(luò)抵御相繼故障能力的效果如圖4所示。圖中的數(shù)據(jù)均為網(wǎng)絡(luò)發(fā)生相繼故障后的結(jié)果。圖中網(wǎng)絡(luò)R表示應(yīng)用本文改進(jìn)路由算法的網(wǎng)絡(luò)；網(wǎng)絡(luò)P表示應(yīng)用參考文獻(xiàn)［2］中增強(qiáng)網(wǎng)絡(luò)健壯性方法的網(wǎng)絡(luò)，其中α表示網(wǎng)絡(luò)中采用防御策略的節(jié)點占總節(jié)點的比例。圖4（a）、（b）中的網(wǎng)絡(luò)初始節(jié)點數(shù)分別為4、8，每個新增加節(jié)點的連邊數(shù)為3、6。各網(wǎng)絡(luò)的節(jié)點總數(shù)均為1 000。

從圖4可以看出，在網(wǎng)絡(luò)中初始故障節(jié)點較少時，本文提出的算法與參考文獻(xiàn)［2］中80%的節(jié)點采取保護(hù)措施所達(dá)到的效果相當(dāng)。但是本文改進(jìn)的算法并不需要對網(wǎng)絡(luò)中的節(jié)點提出特殊的要求，從經(jīng)濟(jì)的角度來講本文算法更優(yōu)。值得注意的是，隨著網(wǎng)絡(luò)中故障節(jié)點的增多，應(yīng)用本文所提算法的網(wǎng)絡(luò)對相繼故障抵抗能力下降較快，其在這一點上表現(xiàn)不如參考文獻(xiàn)［2］中的策略。

在小世界網(wǎng)絡(luò)中將本文提出的路由改進(jìn)算法與參考文獻(xiàn)［2］中提供的方法進(jìn)行比較，圖5記錄了兩種策略增強(qiáng)網(wǎng)絡(luò)抵御相繼故障能力的效果。圖中的數(shù)據(jù)均為網(wǎng)絡(luò)發(fā)生相繼故障后的結(jié)果。網(wǎng)絡(luò)R表示應(yīng)用本文改進(jìn)路由算法的網(wǎng)絡(luò)；網(wǎng)絡(luò)P表示應(yīng)用參考文獻(xiàn)［2］中增強(qiáng)網(wǎng)絡(luò)健壯性方法的網(wǎng)絡(luò)，α表示網(wǎng)絡(luò)中采用防御策略的節(jié)點占總節(jié)點的比例。圖5（a）、（b）中的網(wǎng)絡(luò)的平均度分別為4、 6。各網(wǎng)絡(luò)隨機(jī)連邊的概率為0.4，網(wǎng)絡(luò)中的節(jié)點總數(shù)為1 000。從圖中可以看出在小世界網(wǎng)絡(luò)中與參考文獻(xiàn)［2］中的方法比較，本文所提出的改進(jìn)路由策略同樣能得到良好的效果。

圖4 無標(biāo)度網(wǎng)絡(luò)本文算法與參考文獻(xiàn)［2］中算法效果比較

圖5 小世界網(wǎng)絡(luò)中本文算法與參考文獻(xiàn)［2］算法比較

3 結(jié)論

在復(fù)雜網(wǎng)絡(luò)中存在若干“關(guān)鍵節(jié)點”，這些節(jié)點對網(wǎng)絡(luò)的正常運(yùn)行發(fā)揮著重要的作用。然而一旦這些節(jié)點遭受攻擊則極易引發(fā)相繼故障。為了減少相繼故障的發(fā)生，提高網(wǎng)絡(luò)的可靠性，本文對現(xiàn)有的路由算法加以改進(jìn)。通過降低網(wǎng)絡(luò)中度數(shù)大的節(jié)點的重要性，使得網(wǎng)絡(luò)中各節(jié)點的負(fù)載分布更加均衡，從而減少了“關(guān)鍵節(jié)點”在網(wǎng)絡(luò)中發(fā)揮的作用，進(jìn)而增強(qiáng)了網(wǎng)絡(luò)對蓄意攻擊的抵御性能。通過在BA無標(biāo)度網(wǎng)絡(luò)及WS小世界網(wǎng)絡(luò)中進(jìn)行的實驗，驗證了在故障節(jié)點數(shù)不多的情況下改進(jìn)的路由算法能夠大大提高網(wǎng)絡(luò)對相繼故障的抵御能力。但是當(dāng)網(wǎng)絡(luò)中初始故障節(jié)點數(shù)增多時改進(jìn)路由算法的效果下降比較明顯，同時由于改進(jìn)路由算法的應(yīng)用，致使網(wǎng)絡(luò)的初始傳輸效率有所降低，這也體現(xiàn)了網(wǎng)絡(luò)的可靠性與有效性之間的辯證關(guān)系。

［1］BARABáAIA L，ALBERT R.Emergence of sca1ing in random networks［J］.Science，1999，286（5439）：509-512.

［2］WANG J.M itigation strategies on sca1e-free networks against cascading fai1ures［J］.Physica A：Statistica1Mechanics and Its APP1ications，2013，392（9）：2257-2264.

［3］CHEN D，LV L，SHANG M S，et a1.Identifying inf1uentia1 nodes in comP1ex networks［J］.Physica A：Statistica1Mechanics and Its APP1ications，2012，391（4）：1777-1787.

［4］任卓明，邵鳳，劉建國，等.基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究［J］.物理學(xué)報，2013（12）：522-526.

［5］ZHANG X，ZHU J，WANG Q，et a1.Identifying inf1uentia1 nodes in comP1ex networks with community structure［J］. Know1edge-Based Systems，2013，42（2）：74-84.

［6］SCHNEIDER C M，YAZDANI N，ARAUJO N A，et a1.Towards designing robust couP1ed networks［J］.Scientific Re-Ports，2011，3（24）：1-7.

［7］BRUMM ITT C D，D'SOUZA R M，LEICHT E A.SuPPressing cascades of 1oad in interdePendent networks［J］.Proceedings of he Nationa1Academy of Sciences，2012，109（12）：680-689.

［8］ALBERTO L G，INDRA W.Communication networks：fundamenta1 concePts and key architectures［M］.New York：Mc GrawHi11，2000.

［9］WATTS D J，STROGATZ S H.Co11ective dynamics of‘sma11-wor1d'networks［J］.Nature，1998（393）：440-442.

［10］MOTTER A E，LAIY C.Cascade-based attacks on comP1ex networks［J］.Physica1Review E，2002，66（6）：114-129.［11］LATORA V，MARCHIORI M.Efficient behavior of sma11-wor1d networks［J］. Physica1 Review Letters，2001，87 （19）：198701-1-4.

劉笑辰（1990 -），通信作者，男，碩士在讀，主要研究方向：通信網(wǎng)、復(fù)雜網(wǎng)絡(luò)。E-mai1：1iuxiaochenyt@163.com。

朱磊（1973 -），男，博士，教授，主要研究方向：網(wǎng)絡(luò)管理、復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)工程。

夏蘇（1990 -），女，碩士在讀，主要研究方向：通信網(wǎng)、復(fù)雜網(wǎng)絡(luò)。

An imProved routing a1gorithm for enhancing the resistance to cascading fai1ures in comP1ex networks

Liu Xiaochen，Zhu Lei，Xia Su
（Co11age of Communications Engineering，PLA University of Science and Techno1ogy，Nanjing 210007，China）

There are usua11y some critica1nodes in comP1ex networks，which wi11 cause cascading fai1ures quite easi1y when these nodes suffer de1iberate attacks.This Phenomenon great1y reduces the re1iabi1ity of the networks.Many researches Pay attention to enhance the resistance of critica1nodes.In order to imProve the resistance of networks to cascading fai1ures we imProve the existing routing a1gorithm.We reduce the ro1e of critica1nodes and try to ba1ance the 1oad distribution.The exPeriments in tyPica1networks show that the imProved routing a1gorithm can enhance the resistance of networks to cascading fai1ures significant1y.

comP1ex network；cascading fai1ure；routing a1gorithm；network re1iabi1ity

TN915

A

10.19358 /j.issn.1674-7720.2016.09.021

劉笑辰，朱磊，夏蘇.一種增強(qiáng)復(fù)雜網(wǎng)絡(luò)抵御相繼故障能力的路由算法研究［J］.微型機(jī)與應(yīng)用，2016，35（9）：70-73，77.

江蘇省自然科學(xué)基金（BK20141071）

2016-01-14）