劉笑辰，朱磊，夏蘇

　?。?解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007）

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

　　關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；相繼故障；路由算法；網(wǎng)絡(luò)可靠性

0引言

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

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

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

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

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

　　1.1算法的基本思想

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

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

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

　　crij=λri·λrj·aij(2)

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

　　λvi=f(λri,ki)(3)

　　式(3)的計(jì)算將在下節(jié)中討論。根據(jù)式(3)可以得到虛擬耗費(fèi)因子向量Cr=(λv1,λv2,λv3…λvn)，從而得到eij的虛擬耗費(fèi)：

　　cvij=λvi·λvj·aij(4)

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

　　1.2節(jié)點(diǎn)虛擬耗費(fèi)因子的計(jì)算

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

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

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

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

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

　　方程①的左側(cè)表示所有節(jié)點(diǎn)單位時(shí)間內(nèi)處理的虛擬負(fù)載，其中1表示負(fù)載傳遞給節(jié)點(diǎn)本身，βi·ki表示負(fù)載傳遞給周?chē)泥従樱环匠痰挠覀?cè)表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的虛擬負(fù)載之和。并有當(dāng)kj=0時(shí)所對(duì)應(yīng)的βj=0。

　　計(jì)算方程(5)可以得到：

　　對(duì)于節(jié)點(diǎn)i而言，最終該點(diǎn)的虛擬耗費(fèi)因子為：

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

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

2實(shí)驗(yàn)仿真及結(jié)果研究

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

　　圖2是3種不同的無(wú)標(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)表示初始時(shí)刻網(wǎng)絡(luò)中負(fù)載最大的前n個(gè)節(jié)點(diǎn)發(fā)生故障，縱坐標(biāo)表示網(wǎng)絡(luò)的平均傳輸效率。圖2無(wú)標(biāo)度網(wǎng)絡(luò)發(fā)生相繼故障后平均傳輸效率的變化

　　圖(a)、(b)、(c)中的網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)分別為4、6、8，每個(gè)新增加節(jié)點(diǎn)的連邊數(shù)為3、5、6。各網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)均為1 000。實(shí)驗(yàn)選取網(wǎng)絡(luò)中初始負(fù)載最大的若干個(gè)節(jié)點(diǎn)使之發(fā)生故障，并記錄發(fā)生相繼故障后經(jīng)過(guò)30個(gè)時(shí)間單位后網(wǎng)絡(luò)的平均傳輸效率E(G)。結(jié)果表明，隨著初始故障節(jié)點(diǎn)的增多，網(wǎng)絡(luò)的平均傳輸效率都會(huì)降低。但是在采用傳統(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個(gè)節(jié)點(diǎn)發(fā)生故障的情況下，網(wǎng)絡(luò)仍然保持著相當(dāng)程度的平均效率，而與其相對(duì)的傳統(tǒng)網(wǎng)絡(luò)已經(jīng)完全崩潰。在圖2中，采用改進(jìn)路由算法的網(wǎng)絡(luò)的初始平均傳輸效率要略小于傳統(tǒng)的網(wǎng)絡(luò)，但其結(jié)果卻大大增強(qiáng)了網(wǎng)絡(luò)對(duì)相繼故障的抵抗能力。

　　圖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é)點(diǎn)總數(shù)均為1 000。實(shí)驗(yàn)同樣使網(wǎng)絡(luò)中初始負(fù)載最大的一些節(jié)點(diǎn)發(fā)生故障。結(jié)果顯示在WS網(wǎng)絡(luò)中，改進(jìn)的路由算法能夠明顯增強(qiáng)網(wǎng)絡(luò)對(duì)相繼故障的抵御能力。在應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)中，數(shù)目較少的故障節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)造成的危害非常輕微。在圖3(b)、(c)中可以看出，當(dāng)小世界網(wǎng)絡(luò)的平均度數(shù)增大時(shí)，應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)具有更強(qiáng)健壯性。

　　在無(wú)標(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é)點(diǎn)占總節(jié)點(diǎn)的比例。圖4(a)、(b)中的網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)分別為4、8，每個(gè)新增加節(jié)點(diǎn)的連邊數(shù)為3、6。各網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)均為1 000。

　　從圖4可以看出，在網(wǎng)絡(luò)中初始故障節(jié)點(diǎn)較少時(shí)，本文提出的算法與參考文獻(xiàn)［2］中80%的節(jié)點(diǎn)采取保護(hù)措施所達(dá)到的效果相當(dāng)。但是本文改進(jìn)的算法并不需要對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)提出特殊的要求，從經(jīng)濟(jì)的角度來(lái)講本文算法更優(yōu)。值得注意的是，隨著網(wǎng)絡(luò)中故障節(jié)點(diǎn)的增多，應(yīng)用本文所提算法的網(wǎng)絡(luò)對(duì)相繼故障抵抗能力下降較快，其在這一點(diǎn)上表現(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)路由算圖5小世界網(wǎng)絡(luò)中本文算法與參考文獻(xiàn)［2］算法比較法的網(wǎng)絡(luò)；網(wǎng)絡(luò)P表示應(yīng)用參考文獻(xiàn)［2］中增強(qiáng)網(wǎng)絡(luò)健壯性方法的網(wǎng)絡(luò)，α表示網(wǎng)絡(luò)中采用防御策略的節(jié)點(diǎn)占總節(jié)點(diǎn)的比例。圖5(a)、(b)中的網(wǎng)絡(luò)的平均度分別為4、6。各網(wǎng)絡(luò)隨機(jī)連邊的概率為0.4，網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)為1 000。從圖中可以看出在小世界網(wǎng)絡(luò)中與參考文獻(xiàn)［2］中的方法比較，本文所提出的改進(jìn)路由策略同樣能得到良好的效果。

3結(jié)論

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

參考文獻(xiàn)

　　［1］ BARABAI A L, ALBERT R. Emergence of scaling in random networks［J］. Science, 1999, 286（5439）: 509512.

　?。?］ WANG J. Mitigation strategies on scalefree networks against cascading failures［J］. Physica A: Statistical Mechanics and Its Applications, 2013, 392（9）:22572264.

　?。?］ CHEN D, LV L， SHANG M S， et al. Identifying influential nodes in complex networks［J］. Physica A: Statistical Mechanics and Its Applications,2012, 391(4): 17771787.

　?。?］ 任卓明, 邵鳳, 劉建國(guó), 等. 基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法研究［J］. 物理學(xué)報(bào), 2013（12）:522526.

　　［5］ ZHANG X, ZHU J, WANG Q, et al. Identifying influential nodes in complex networks with community structure［J］. KnowledgeBased Systems, 2013, 42(2): 7484.

　　［6］ SCHNEIDER C M, YAZDANI N, ARAU＇JO N A, et al. Towards designing robust coupled networks［J］. Scientific Reports, 2011，3(24)： 17.

　　［7］ BRUMMITT C D, D’SOUZA R M, LEICHT E A. Suppressing cascades of load in interdependent networks［J］. Proceedings of the National Academy of Sciences, 2012, 109(12):680689.

　?。?］ ALBERTO L G, INDRA W. Communication networks: fundamental concepts and key architectures［M］. New York: Mc GrawHill, 2000.

　?。?］ WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’networks［J］. Nature, 1998(393):440442.

　?。?0］ MOTTER A E, LAI Y C. Cascadebased attacks on complex networks［J］. Physical Review E, 2002, 66(6):114129.