劉笑辰，朱磊，夏蘇

　　（ 解放軍理工大學 通信工程學院，江蘇 南京 210007）

　　摘要：在現(xiàn)實生活中，許多大型的通信網(wǎng)絡(luò)或電力網(wǎng)絡(luò)都可以應用復雜網(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ò)負載在各節(jié)點間分布的均衡性。通過在典型的復雜網(wǎng)絡(luò)上進行的仿真實驗，證明了改進的路由算法能夠大大增強網(wǎng)絡(luò)對相繼故障的抵御能力。

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

0引言

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

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

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

　　考慮到復雜網(wǎng)絡(luò)中各節(jié)點間度數(shù)分布的異質(zhì)性，為了防止網(wǎng)絡(luò)中度數(shù)大的節(jié)點承擔過多的負載，根據(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ù)淖疃搪窂剑梢圆捎肍loyd、BellmanFord、SPFA等算法［8］得到網(wǎng)絡(luò)間節(jié)點傳輸?shù)穆酚杀?。運用上述方法得到的結(jié)果可以有效降低網(wǎng)絡(luò)中度數(shù)大的節(jié)點的負載，提高各節(jié)點間負載的均衡性。

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

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

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

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

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

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

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

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

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

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

　　圖1表示了在初始實際耗費因子向量Cr(0)=(1,1,1,…,1)時3個不同的無標度網(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增大，擬合曲線的斜率也相應增大?！?/p>

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

　　在仿真實驗中，本文分別在BA無標度網(wǎng)絡(luò)［1］及WS小世界網(wǎng)絡(luò)［9］中對改進的路由算法的效果進行研究。本文應用參考文獻［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種不同的無標度網(wǎng)絡(luò)發(fā)生相繼故障后網(wǎng)絡(luò)的效率變化。圖中網(wǎng)絡(luò)1表示應用基于最短路徑路由算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)2表示應用改進路由算法的網(wǎng)絡(luò)。橫坐標表示初始時刻網(wǎng)絡(luò)中負載最大的前n個節(jié)點發(fā)生故障，縱坐標表示網(wǎng)絡(luò)的平均傳輸效率。圖2無標度網(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ò)中初始負載最大的若干個節(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)完全崩潰。在應用改進后的路由算法的網(wǎng)絡(luò)中，盡管網(wǎng)絡(luò)的效率也發(fā)生了下降，但相比而言其下降速率非常緩慢，根據(jù)圖2(b)、(c)，在已有15個節(jié)點發(fā)生故障的情況下，網(wǎng)絡(luò)仍然保持著相當程度的平均效率，而與其相對的傳統(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表示應用基于最短路徑路由算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)2表示應用改進路由算法的網(wǎng)絡(luò)。圖(a)、(b)、(c)中網(wǎng)絡(luò)的平均度分別為4、6、8。各網(wǎng)絡(luò)隨機連邊的效率為0.4，節(jié)點總數(shù)均為1 000。實驗同樣使網(wǎng)絡(luò)中初始負載最大的一些節(jié)點發(fā)生故障。結(jié)果顯示在WS網(wǎng)絡(luò)中，改進的路由算法能夠明顯增強網(wǎng)絡(luò)對相繼故障的抵御能力。在應用改進路由算法的網(wǎng)絡(luò)中，數(shù)目較少的故障節(jié)點對網(wǎng)絡(luò)造成的危害非常輕微。在圖3(b)、(c)中可以看出，當小世界網(wǎng)絡(luò)的平均度數(shù)增大時，應用改進路由算法的網(wǎng)絡(luò)具有更強健壯性。

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

　　在復雜網(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é)點的負載分布更加均衡，從而減少了“關(guān)鍵節(jié)點”在網(wǎng)絡(luò)中發(fā)揮的作用，進而增強了網(wǎng)絡(luò)對蓄意攻擊的抵御性能。通過在BA無標度網(wǎng)絡(luò)及WS小世界網(wǎng)絡(luò)中進行的實驗，驗證了在故障節(jié)點數(shù)不多的情況下改進的路由算法能夠大大提高網(wǎng)絡(luò)對相繼故障的抵御能力。但是當網(wǎng)絡(luò)中初始故障節(jié)點數(shù)增多時改進路由算法的效果下降比較明顯，同時由于改進路由算法的應用，致使網(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.

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

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