劉笑辰,，朱磊,，夏蘇

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

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

　　關(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)雪崩式毀壞,。相繼故障的存在對社會生活的正常運(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ù)載超過閾值則將額外的負(fù)載分配給鄰居從而避免本身發(fā)生故障,。參考文獻(xiàn)［3-5］注重在網(wǎng)絡(luò)中發(fā)現(xiàn)在相繼故障過程中更加重要的節(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)或組成部分,，而缺少對網(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é)點(diǎn)負(fù)載的異質(zhì)性，進(jìn)而提高網(wǎng)絡(luò)對相繼故障的抵御能力,。

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

　　在計(jì)算網(wǎng)絡(luò)中的源節(jié)點(diǎn)到目的節(jié)點(diǎn)最短路徑的過程中,，節(jié)點(diǎn)間鏈路的傳輸耗費(fèi)是一個(gè)關(guān)鍵的參數(shù)。本文通過對節(jié)點(diǎn)間傳輸?shù)膶?shí)際耗費(fèi)進(jìn)行修正得到虛擬耗費(fèi),，然后根據(jù)虛擬耗費(fèi)計(jì)算節(jié)點(diǎn)之間的最短路徑,。通過虛擬耗費(fèi)的計(jì)算降低經(jīng)過度數(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)對相鄰的邊傳輸實(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)過多的負(fù)載,，根據(jù)節(jié)點(diǎn)的度數(shù)對其實(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ù)載。

　　對于假設(shè)(1),，由于在一個(gè)完好的網(wǎng)絡(luò)中不存在孤立的節(jié)點(diǎn),，即所有節(jié)點(diǎn)的度數(shù)都大于等于1，故虛擬負(fù)載lvi可以保證有意義,；對于假設(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ù)載傳遞給周圍的鄰居；方程的右側(cè)表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的虛擬負(fù)載之和,。并有當(dāng)kj=0時(shí)所對應(yīng)的βj=0,。

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

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

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

　　圖1表示了在初始實(shí)際耗費(fèi)因子向量Cr(0)=(1,1,1,…,1)時(shí)3個(gè)不同的無標(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)因子就越大。通過網(wǎng)絡(luò)2與網(wǎng)絡(luò)3的對比可以發(fā)現(xiàn),，參數(shù)h增大,，擬合曲線的斜率也相應(yīng)增大?！?/p>

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

　　在仿真實(shí)驗(yàn)中,，本文分別在BA無標(biāo)度網(wǎng)絡(luò)［1］及WS小世界網(wǎng)絡(luò)［9］中對改進(jìn)的路由算法的效果進(jìn)行研究,。本文應(yīng)用參考文獻(xiàn)［10］中的相繼故障模型，并且令對任意節(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種不同的無標(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無標(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)過30個(gè)時(shí)間單位后網(wǎng)絡(luò)的平均傳輸效率E(G),。結(jié)果表明，隨著初始故障節(jié)點(diǎn)的增多,，網(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個(gè)節(jié)點(diǎn)發(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ò)對相繼故障的抵抗能力,。

　　圖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ò)對相繼故障的抵御能力。在應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)中,，數(shù)目較少的故障節(jié)點(diǎn)對網(wǎng)絡(luò)造成的危害非常輕微,。在圖3(b)、(c)中可以看出,，當(dāng)小世界網(wǎng)絡(luò)的平均度數(shù)增大時(shí),，應(yīng)用改進(jìn)路由算法的網(wǎng)絡(luò)具有更強(qiáng)健壯性。

　　在無標(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)的算法并不需要對網(wǎng)絡(luò)中的節(jié)點(diǎn)提出特殊的要求,，從經(jīng)濟(jì)的角度來講本文算法更優(yōu),。值得注意的是，隨著網(wǎng)絡(luò)中故障節(jié)點(diǎn)的增多,，應(yīng)用本文所提算法的網(wǎng)絡(luò)對相繼故障抵抗能力下降較快,，其在這一點(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)對網(wǎng)絡(luò)的正常運(yùn)行發(fā)揮著重要的作用,。然而一旦這些節(jié)點(diǎn)遭受攻擊則極易引發(fā)相繼故障。為了減少相繼故障的發(fā)生,，提高網(wǎng)絡(luò)的可靠性,，本文對現(xiàn)有的路由算法加以改進(jìn)。通過降低網(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ò)對蓄意攻擊的抵御性能,。通過在BA無標(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ò)對相繼故障的抵御能力。但是當(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)

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

　　［2］ 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.

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

　?。?］ 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.

　?。?］ 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.

　　［9］ 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.