劉笑辰，朱磊,，夏蘇

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

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

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

0引言

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

　　為了減少相繼故障的危害，提高網(wǎng)絡(luò)的可靠性,，許多學(xué)者進行了卓有成效的研究,。參考文獻［2］按照一定的規(guī)則在網(wǎng)絡(luò)中選擇某些節(jié)點執(zhí)行一次防御策略，如果被保護的節(jié)點負(fù)載超過閾值則將額外的負(fù)載分配給鄰居從而避免本身發(fā)生故障,。參考文獻［3-5］注重在網(wǎng)絡(luò)中發(fā)現(xiàn)在相繼故障過程中更加重要的節(jié)點,。由于在現(xiàn)實中，往往多個網(wǎng)絡(luò)相互作用形成一個耦合的整體,，參考文獻［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ò)中路由算法的改進以提高網(wǎng)絡(luò)的可靠性,。本文通過對現(xiàn)有基于最短路徑的路由算法加以改進，將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響體現(xiàn)到傳輸鏈路的效率中,，降低復(fù)雜網(wǎng)絡(luò)中節(jié)點負(fù)載的異質(zhì)性,，進而提高網(wǎng)絡(luò)對相繼故障的抵御能力。

1基于最短路徑路由算法的改進研究

　　在計算網(wǎng)絡(luò)中的源節(jié)點到目的節(jié)點最短路徑的過程中,，節(jié)點間鏈路的傳輸耗費是一個關(guān)鍵的參數(shù),。本文通過對節(jié)點間傳輸?shù)膶嶋H耗費進行修正得到虛擬耗費，然后根據(jù)虛擬耗費計算節(jié)點之間的最短路徑,。通過虛擬耗費的計算降低經(jīng)過度數(shù)大的節(jié)點的路徑數(shù)目,，從而降低這些節(jié)點的負(fù)載，進而減少各節(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=(λr1,λr2,λr3…λrn)表示各節(jié)點對相鄰的邊傳輸實際耗費的影響，其中λri為節(jié)點i的實際耗費因子,，根據(jù)節(jié)點的實際耗費因子可得邊eij傳輸?shù)膶嶋H耗費為：

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

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

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

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

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

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

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

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

　　(1)假設(shè)每個節(jié)點存在虛擬負(fù)載,，節(jié)點i的負(fù)載為lvi  = logk ki,，其中ki為節(jié)點i的度數(shù)，k表示網(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é)點進行交流并且算法的最終目的在于均衡節(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)增大,?！?/p>

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

　　在仿真實驗中，本文分別在BA無標(biāo)度網(wǎng)絡(luò)［1］及WS小世界網(wǎng)絡(luò)［9］中對改進的路由算法的效果進行研究,。本文應(yīng)用參考文獻［10］中的相繼故障模型,，并且令對任意節(jié)點i均有λri(0)=1。文中采用平均傳輸效率E(G)衡量網(wǎng)絡(luò)狀態(tài) ［11］,。E(G)越大表示網(wǎng)絡(luò)在單位時間內(nèi)傳輸能力越強,，即網(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)用改進路由算法的網(wǎng)絡(luò)。橫坐標(biāo)表示初始時刻網(wǎng)絡(luò)中負(fù)載最大的前n個節(jié)點發(fā)生故障,，縱坐標(biāo)表示網(wǎng)絡(luò)的平均傳輸效率,。圖2無標(biāo)度網(wǎng)絡(luò)發(fā)生相繼故障后平均傳輸效率的變化

　　圖(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ò)平均效率下降的速度非常快并且在3種情況下最終都接近于0,，即網(wǎng)絡(luò)已經(jīng)完全崩潰,。在應(yīng)用改進后的路由算法的網(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中,，采用改進路由算法的網(wǎng)絡(luò)的初始平均傳輸效率要略小于傳統(tǒng)的網(wǎng)絡(luò),，但其結(jié)果卻大大增強了網(wǎng)絡(luò)對相繼故障的抵抗能力。

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

　　在無標(biāo)度網(wǎng)絡(luò)中將本文提出的路由改進算法與參考文獻［2］中提供的方法進行比較,，兩種策略增強網(wǎng)絡(luò)抵御相繼故障能力的效果如圖4所示。圖中的數(shù)據(jù)均為網(wǎng)絡(luò)發(fā)生相繼故障后的結(jié)果,。圖中網(wǎng)絡(luò)R表示應(yīng)用本文改進路由算法的網(wǎng)絡(luò),；網(wǎng)絡(luò)P表示應(yīng)用參考文獻［2］中增強網(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é)點較少時，本文提出的算法與參考文獻［2］中80%的節(jié)點采取保護措施所達到的效果相當(dāng),。但是本文改進的算法并不需要對網(wǎng)絡(luò)中的節(jié)點提出特殊的要求,，從經(jīng)濟的角度來講本文算法更優(yōu),。值得注意的是，隨著網(wǎng)絡(luò)中故障節(jié)點的增多,，應(yīng)用本文所提算法的網(wǎng)絡(luò)對相繼故障抵抗能力下降較快,，其在這一點上表現(xiàn)不如參考文獻［2］中的策略。

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

3結(jié)論

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

參考文獻

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

　　［3］ 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é)點重要性度量方法研究［J］. 物理學(xué)報, 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.

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

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