基于混合信息的復(fù)雜網(wǎng)絡(luò)路由策略研究

劉倩星，張達(dá)敏（貴州大學(xué) 計算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽550025）

0 引 言

在現(xiàn)實(shí)世界中復(fù)雜系統(tǒng)無處不在，復(fù)雜網(wǎng)絡(luò)能夠很全面地描述復(fù)雜系統(tǒng)，因此復(fù)雜網(wǎng)絡(luò)已經(jīng)成為一種廣泛用于分析復(fù)雜系統(tǒng)的重要工具［1］。自從 Watt－Strogatz提出小世界模型和Barabási－Albert提出無標(biāo)度模型開始，研究者對復(fù)雜網(wǎng)絡(luò)產(chǎn)生了濃厚興趣，自此掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮［2－3］。近年來，復(fù)雜網(wǎng)絡(luò)在各個領(lǐng)域都取得了很大進(jìn)展，如信息傳輸，疾病傳播，交通，能源等方面［4－16］。

現(xiàn)代社會中，互聯(lián)網(wǎng)、萬維網(wǎng)、點(diǎn)對點(diǎn)網(wǎng)絡(luò)和其它通信網(wǎng)絡(luò)發(fā)揮著越來越重要的作用。隨著人們對這些大規(guī)模甚至超大規(guī)模網(wǎng)絡(luò)依賴性的不斷增強(qiáng)，網(wǎng)絡(luò)中的交通動力學(xué)特性逐漸引起人們的關(guān)注。為了使通訊網(wǎng)絡(luò)更有效的發(fā)揮其功能，必須保證信息流處于自由通暢狀態(tài)。因此，緩解網(wǎng)絡(luò)中信息交通擁塞和提高通訊網(wǎng)絡(luò)的效率成為研究的重點(diǎn)。該領(lǐng)域的研究工作則主要圍繞著兩個方面展開，一是改變通訊網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，二是研究更優(yōu)化的路由策略。由于改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的成本較高且不易實(shí)現(xiàn)，所以研究者在尋找更優(yōu)化的路由策略方面投入了更多精力。目前，在路由策略方面已經(jīng)取得了較大進(jìn)展，研究人員提出了不少優(yōu)良的路由策略，如隨機(jī)路由策略［4－5］、最短路徑策略［6］、有效路徑策略［7－8］、鄰域搜索和次近鄰搜索策略［9－12］等。臧海娟等人對這些路由策略進(jìn)行了總結(jié)。大致分為3類：基于全局信息的路由方法，基于局域信息的路由方法和基于混合信息的路由方法［13］。這些路由策略在一定程度上提高了通訊網(wǎng)絡(luò)的路由效率，然而由于通訊網(wǎng)絡(luò)的規(guī)模不斷增大采用全局信息的路由策略愈加難以實(shí)現(xiàn)，基于局部路由策略的信息雖適用于大規(guī)模網(wǎng)路，但是沒有充分利用網(wǎng)絡(luò)中各種信息，因此為了更好地提高通訊網(wǎng)絡(luò)的路由效率，研究人員又將網(wǎng)絡(luò)中各種特性信息進(jìn)行綜合考慮，提出了混合路由策略。

對于一個通訊網(wǎng)絡(luò)，提高路由效率，保持網(wǎng)絡(luò)中的信息流處于通暢狀態(tài)至關(guān)重要。由于網(wǎng)絡(luò)規(guī)模的不斷增大和網(wǎng)絡(luò)中的信息量的增大可能會導(dǎo)致網(wǎng)絡(luò)交通擁塞甚至網(wǎng)絡(luò)系統(tǒng)的崩潰，因此研究如何緩解網(wǎng)絡(luò)交通擁塞具有重要意義?；谶@個思想，本文以無標(biāo)度網(wǎng)絡(luò)為模型建立了一種新的混合路由策略。該策略中假定結(jié)點(diǎn)傳遞能力等于結(jié)點(diǎn)的度，將局域結(jié)構(gòu)的靜態(tài)信息與交通擁塞的動態(tài)信息結(jié)合在一起綜合考慮，并以優(yōu)化的信息包傳遞概率向鄰域結(jié)點(diǎn)傳遞。文章對這一新的混合路由策略進(jìn)行研究，仿真結(jié)果表明通訊網(wǎng)絡(luò)的交通路由效率得到了顯著提高，有效緩解了交通壓力。

1 路由策略

1.1 BA無標(biāo)度模型

近年來，大量研究證明INTERNET、WWW等通訊網(wǎng)絡(luò)并不是像隨機(jī)網(wǎng)和規(guī)則網(wǎng)那樣均勻，而是度分布遵循冪律分布P （k）～k－r的非均勻系統(tǒng)［3］。Barabási－Albert提出的BA無標(biāo)度模型對此進(jìn)行了很好的闡述。與其它模型相比，BA無標(biāo)度網(wǎng)絡(luò)最大的特點(diǎn)是：網(wǎng)絡(luò)增長和優(yōu)先連接特性［3］。其構(gòu)造算法如下：

（1）增長：從一個具有m0個節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個新的結(jié)點(diǎn)并且連接到m個已存在的結(jié)點(diǎn)上，且m＜m0。

（2）優(yōu)先連接：一個新結(jié)點(diǎn)與一個已經(jīng)存在的結(jié)點(diǎn)i相連接的概率Pi與結(jié)點(diǎn)i的度ki、結(jié)點(diǎn)j的度kj之間滿足

BA無標(biāo)度網(wǎng)絡(luò)模型具有較短平均路徑長度和較低聚類系數(shù)，其度分布可以由冪指數(shù)為3的冪律函數(shù)來近似描述，如圖1所示為網(wǎng)絡(luò)規(guī)模為N＝5＊104的BA無標(biāo)度網(wǎng)絡(luò)的度分布。

圖1 BA無標(biāo)度網(wǎng)絡(luò)的度分布 （N＝5×104）

1.2 混合路由動力學(xué)模型

為了使網(wǎng)絡(luò)模型能夠反映真實(shí)通訊網(wǎng)絡(luò)的特性，本文采用初始網(wǎng)絡(luò)中結(jié)點(diǎn)個數(shù)m0＝5、網(wǎng)絡(luò)規(guī)模N＝1000的BA無標(biāo)度網(wǎng)絡(luò)為通訊網(wǎng)絡(luò)的模型。具體路由策略如下：

（1）在每一時步，網(wǎng)絡(luò)中有R個信息包產(chǎn)生，并需要從其源結(jié)點(diǎn)傳送到目的結(jié)點(diǎn)。其中，源結(jié)點(diǎn)和目的結(jié)點(diǎn)都是隨機(jī)選取的，但是一經(jīng)選定就不能再改變。每一結(jié)點(diǎn)既是產(chǎn)生信息和接收信息的服務(wù)器終端，又是中介傳遞信息的路由器。

（2）在每一時步，每個結(jié)點(diǎn)向其鄰域結(jié)點(diǎn)傳遞的信息包個數(shù)最多為Ci。由于現(xiàn)實(shí)網(wǎng)絡(luò)中各結(jié)點(diǎn)的傳遞能力是不同的，因此假定每一結(jié)點(diǎn)的傳遞能力為：Ci＝ki。ki是結(jié)點(diǎn)i的連接度。而不是僅僅將Ci設(shè)定為某一常數(shù)。采用變化的Ci能更好的體現(xiàn)真實(shí)網(wǎng)絡(luò)的特點(diǎn)。

（3）采用對每一結(jié)點(diǎn)的最鄰近鄰域結(jié)點(diǎn)進(jìn)行局域搜索的策略，如果在直接鄰域結(jié)點(diǎn)范圍內(nèi)搜索出信息包的目的地，則將信息包直接傳遞到該目的地，否則，以優(yōu)先概率

將信息包傳送到其鄰域結(jié)點(diǎn)。這里ki是結(jié)點(diǎn)i的連接度，α是一個可調(diào)的參數(shù)，Ni是結(jié)點(diǎn)i的排隊(duì)隊(duì)列長度，Ci是結(jié)點(diǎn)i的傳遞能力。Ni＋1是為了保證結(jié)點(diǎn)處信息包個數(shù)不為0。

（4）為了避免網(wǎng)絡(luò)中的信息包無目的的游蕩，采用路徑重復(fù)避免規(guī)則 （path iteration avoidance，PIA），即任何一對結(jié)點(diǎn)之間的連邊不能夠被同一個信息包訪問二次以上。采用這種規(guī)則能夠避免同一信息包在同一連邊上毫無必要地反復(fù)訪問多次而使網(wǎng)絡(luò)的通訊能力變的極低。

（5）該路由策略中假定每一結(jié)點(diǎn)處等待傳遞的隊(duì)列長度可以為無限長。也就是等候發(fā)送的信息包數(shù)目可以是無限的。這些排隊(duì)的信息包按照先進(jìn)先出 （first in first out，F(xiàn)IFO）的規(guī)則按次序傳遞［14－16］。

通訊網(wǎng)絡(luò)最重要的是整個網(wǎng)絡(luò)對于信息包的處理和傳遞能力。在這個新的路由策略中，設(shè)定單個結(jié)點(diǎn)的通訊能力為Ci，且令Ci等于其連接度ki。而整個通訊網(wǎng)絡(luò)的通訊能力用臨界的信息產(chǎn)生率Rc來度量。Rc是網(wǎng)絡(luò)從自由交通態(tài)到擁塞交通態(tài)的臨界點(diǎn)。當(dāng)R＜Rc時，網(wǎng)絡(luò)處于自由交通態(tài)。而當(dāng)R＞Rc時，網(wǎng)絡(luò)處于擁塞交通態(tài)。

為了更準(zhǔn)確的描述網(wǎng)絡(luò)狀態(tài)變化，本文采用如下序參數(shù)［16］

式中：C——結(jié)點(diǎn)的平均傳遞能力，R——網(wǎng)絡(luò)的信息包產(chǎn)生率，ΔNp＝Np（t＋Δt）－Np（t），表示從t時刻到t＋Δt時刻系統(tǒng)中增加的信息包數(shù)目。＜…＞表示對于時間窗口Δt求平均。當(dāng)R＜Rc時，＜ΔNp＞＝0且η＝0，即網(wǎng)絡(luò)處于自由交通態(tài)。而當(dāng)R＞Rc時，＜ΔNp＞＞0且η＞0，即網(wǎng)絡(luò)處于擁塞交通態(tài)。所以當(dāng)R＝Rc時，網(wǎng)絡(luò)通信能力最大。顯然臨界信息包產(chǎn)生率Rc能很好的度量網(wǎng)絡(luò)的最大通訊能力。η從0到大于0的突變，說明網(wǎng)絡(luò)從自由態(tài)進(jìn)入了交通擁塞態(tài)。

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

2.1 通訊網(wǎng)絡(luò)的路由效率分析

通訊網(wǎng)絡(luò)的路由效率可以用網(wǎng)絡(luò)的通訊能力和信息包的平均傳輸時間度量。首先，在這一新的路由策略下對通訊網(wǎng)絡(luò)的通訊能力進(jìn)行了研究。從圖2中可以看出當(dāng)R＜Rc時，對于不同的α序參數(shù)η＝0。隨著R不斷增大到R＝Rc時，序參數(shù)η驟然變?yōu)橐粋€大于0的常數(shù)。這一相變反映了網(wǎng)絡(luò)從自由交通態(tài)進(jìn)入了擁塞交通態(tài)。圖3表明：在不同的搜索策略值α下，網(wǎng)絡(luò)的通訊能力Rc是不同的。在新的路由策略下，網(wǎng)絡(luò)的最大通訊能力Rc在117左右且此時α＝－4。當(dāng)α從1減小到－4的過程中，網(wǎng)絡(luò)的通訊能力Rc逐漸增大且當(dāng)α＝－4時達(dá)到最大值。然而α繼續(xù)減小，網(wǎng)絡(luò)的通訊能力Rc則減小且逐漸趨近于某一特定值。在以往的路由策略中往往設(shè)定結(jié)點(diǎn)的傳遞能力Ci為某一常數(shù)。例如文獻(xiàn) ［15］中令Ci＝10，此時網(wǎng)絡(luò)的通訊能力Rc近似為30。采用新的路由策略，網(wǎng)絡(luò)的通訊能力最大值在117左右，可見網(wǎng)絡(luò)的通訊能力得到了明顯提高。

在圖4中可以看到網(wǎng)絡(luò)中的信息包總數(shù)Np（t）隨著α的減小而逐漸增大。而在圖3中，當(dāng)α＜－4時臨界信息產(chǎn)生率Rc逐漸減小到一個特定值，所以當(dāng)網(wǎng)絡(luò)中的信息包數(shù)目較少且網(wǎng)絡(luò)通訊能力較大時整個網(wǎng)絡(luò)中達(dá)到平衡態(tài)所用時間最少。對圖3和圖4進(jìn)行綜合考慮可以得出當(dāng)α＝－4時通訊網(wǎng)絡(luò)達(dá)到自由穩(wěn)態(tài)用時最少。由于通訊網(wǎng)絡(luò)的交通路由效率同時反映在網(wǎng)絡(luò)通訊能力和信息包的平均傳輸時間兩個關(guān)鍵度量。綜上所述，可以得到當(dāng)α＝－4時通訊網(wǎng)絡(luò)的交通路由效率達(dá)到最大。

圖4 網(wǎng)絡(luò)中的信息包數(shù)目Np（t）與α的關(guān)系，N＝1000

2.2 自由態(tài)動力學(xué)分析

自由交通態(tài)是在通訊網(wǎng)絡(luò)中同一時步內(nèi)新產(chǎn)生的信息包數(shù)目與到達(dá)目的結(jié)點(diǎn)被移除網(wǎng)絡(luò)的信息包數(shù)目相抵消，最終達(dá)到穩(wěn)定狀態(tài)。圖5中可以看出R＜Rc時，開始時信息包處于增長狀態(tài)，但是經(jīng)過足夠長的時間，網(wǎng)絡(luò)中產(chǎn)生的信息包和到達(dá)目的結(jié)點(diǎn)被移除網(wǎng)絡(luò)的信息包相抵消，最終達(dá)到穩(wěn)定狀態(tài)，系統(tǒng)處于自由穩(wěn)態(tài)。從圖6（a）中可以看出當(dāng)系統(tǒng)處于穩(wěn)態(tài)時，度k較小的結(jié)點(diǎn)處聚集著較多的信息包，而當(dāng)k繼續(xù)增大，則網(wǎng)絡(luò)中的信息包分布較均勻，這樣在一定程度上可以減少網(wǎng)絡(luò)擁塞的發(fā)生。

圖5 R＜Rc時不同α下網(wǎng)絡(luò)中信息包數(shù)目變化

2.3 擁塞態(tài)動力學(xué)分析

當(dāng)信息包產(chǎn)生率R等于臨界值Rc時，序參數(shù)η發(fā)生一個明顯相變，通訊網(wǎng)絡(luò)由自由交通態(tài)轉(zhuǎn)為擁塞交通態(tài)。擁塞交通態(tài)是指存在于網(wǎng)絡(luò)中的信息包數(shù)量處于持續(xù)增長狀態(tài)，網(wǎng)絡(luò)中大部分信息包不斷滯留積累于系統(tǒng)中，最終導(dǎo)致系統(tǒng)的交通擁塞甚至癱瘓。圖7中可以看出當(dāng)R＞Rc時，無論時間如何增加，處于網(wǎng)絡(luò)中的信息包數(shù)目一直處于增長狀態(tài)，大量信息包滯留于系統(tǒng)中，網(wǎng)絡(luò)此時處于擁塞交通態(tài)。當(dāng)α＞0時，圖8（a）顯示度較小的結(jié)點(diǎn)承擔(dān)著巨大的信息包，由于結(jié)點(diǎn)的傳遞能力又與其度相等，所以網(wǎng)絡(luò)中的信息包不能及時得到傳遞，容易造成信息包滯留積累于網(wǎng)絡(luò)中，最終將導(dǎo)致網(wǎng)絡(luò)擁塞。而當(dāng)α≤0時，從圖8（b）中可以看到連接度大的結(jié)點(diǎn)承擔(dān)著較大的信息包數(shù)目，由于結(jié)點(diǎn)傳遞能力有一定限度，所以少數(shù)連接度大的結(jié)點(diǎn)處會首先出現(xiàn)過度的信息包積累，從而造成系統(tǒng)擁塞。因此為了有效緩解通訊網(wǎng)絡(luò)的交通擁塞可以提高結(jié)點(diǎn)的傳遞能力。從圖9中可以看到在某一α下，已經(jīng)處于擁塞態(tài)的網(wǎng)絡(luò)中信息包變化率ΔNp/Δt與信息產(chǎn)生率R近似成正比關(guān)系，網(wǎng)絡(luò)的路由效率也受到信息包產(chǎn)生率的影響。但是為了更加清楚的體現(xiàn)其規(guī)律，本文對ΔNp/Δt與臨界值偏離R－Rc的關(guān)系進(jìn)行了研究，圖10是將所有曲線平移到一個近似的起點(diǎn)得到的二者的關(guān)系。從圖中可以發(fā)現(xiàn)，正的α值的交通負(fù)荷增長速度明顯高于負(fù)的α值，α越大網(wǎng)絡(luò)中的信息包數(shù)量就增長的越快。而處于擁塞態(tài)的通訊網(wǎng)絡(luò)最大通訊能力逐漸減小到固定值107，網(wǎng)絡(luò)的路由效率會隨信息包產(chǎn)生率的增加而減小。因此當(dāng)信息包產(chǎn)生率R逐漸增大到Rc時網(wǎng)絡(luò)的通訊能力最大。

圖6 R＜Rc時度為k的結(jié)點(diǎn)處平均信息包數(shù)目變化

圖7 R＞Rc時不同α下網(wǎng)絡(luò)中信息包數(shù)目變化

3 結(jié)束語

本文提出了一種基于混合信息的路由策略，該策略充分利用了網(wǎng)絡(luò)中的動態(tài)和靜態(tài)信息，將結(jié)點(diǎn)傳遞能力Ci設(shè)定為與結(jié)點(diǎn)度成正比關(guān)系的變量，而不是單純固定為某一特定值，這樣更加接近現(xiàn)實(shí)的網(wǎng)絡(luò)，同時以更加優(yōu)化的信息包傳遞概率向下一結(jié)點(diǎn)傳遞信息。經(jīng)過仿真實(shí)驗(yàn)證實(shí)該路由策略明顯的提高了通訊網(wǎng)絡(luò)的路由效率。同時對自由和擁塞態(tài)下的交通動力學(xué)進(jìn)行了研究，仿真結(jié)果表明：對于同一α處于擁塞態(tài)的網(wǎng)絡(luò)中ΔNp/Δt與信息產(chǎn)生率R近似成正比關(guān)系，正的α值的交通負(fù)荷增長速度明顯高于負(fù)的α值且α越大網(wǎng)絡(luò)中的信息包數(shù)量就增長的越快，較大的結(jié)點(diǎn)傳遞能力及合理的信息產(chǎn)生率可以有效緩解通訊網(wǎng)絡(luò)的交通擁塞。

圖10 R＞Rc時不同α下ΔNp/Δt與R－Rc的關(guān)系

［1］L Lin yuan，JIN Ci hang，ZHOU Tao.Similarity index based on local paths for link prediction of complex networks［J］.Physical Review E，2009，80 （4）：046122.

［2］LI Guo，GAO Jianmin，GAO Zhiyong.Safety analysis of complex system based on small world topological model ［J］.Chinese Journal of Mechanical Engingeering，2008，44 （5）：86－91（in Chinese）.［李果，高建民，高智勇.基于小世界拓?fù)淠Ｐ偷膹?fù)雜系統(tǒng)安全分析 ［J］.機(jī)械工程學(xué)報，2008，44（5）：86－91.］

［3］Michele Catanzaro，Marián Bogu á，Romualdo Pastor－Satorras［J］.Physical Review E，2005，71：027103.

［4］Alessandro de Moura P S.statistics and traffic in complex networks［J］.Physical Review E，2005，71 （6）：066114.

［5］ZHANG Yingbin，SHI Haomin，LU Xuanmin.Risk Indexbased stochastic routing strategy ［J］.Computer Engineering and Applications，2005，41 （29）：130－133 （in Chinese）.［張迎賓，史浩山，盧選民.基于風(fēng)險指數(shù)的隨機(jī)路由策略［J］.計算機(jī)工程與應(yīng)用，2005，41 （29）：130－133.］

［6］ZHAO Liang，LAI Ying cheng，YE Nong，et al.Onset of traffic congestion in complex networks ［J］.Physical Review E，2005，71 （2）：026125.

［7］YAN Gang，ZHOU Tao，HU Bo，et al.Efficient routing on complex networks ［J］.Physical Review E，2006，73（4）：046108.

［8］YU Gang，WANG Xianpeng，LU Hongtao.Efficient routing strategy on scale－free networks ［J］.Modern Physics Letters B，2009，23 （11）：1377

［9］HU Maobing，WANG Wenxu，JIANG Rui，et al.Phase transition and hysteresis in scale－free network traffic ［J］.Physical Review E，2007，75 （3）：036102.

［10］WANG Wenxu，WANG Binghong，ZHOU Tao.Traffic dynamics based on local routing protocol on a scale－free network［J］.Physical Review E，2006，73 （2）：026111.

［11］ZHAO Han，LIU Feng，LI Ming.Local routing strategy for scale－free networks based on degree－load joint preference ［J］.Journal of University of Shanghai for Science and Technology，2008，30 （3）：264－270 （in Chinese）. ［趙寒，劉峰，李明.基于度－負(fù)載聯(lián)合偏好的無標(biāo)度網(wǎng)絡(luò)局部路由策略 ［J］.上海理工大學(xué)學(xué)報，2008，30 （3）：264－270.］

［12］WANG Binghong，WANG Wenxu.Routing strategies in traffic network and phase transition in network traffic flow ［J］.Indian Academy of Sciences，2008，71 （2）：353－358.

［13］ZANG Haijuan，REN Yan，XUE Xiaoping.The routing strategy study on complex networks ［J］.Journal of Computer Applications，2010，30 （8）：2210－2213 （in Chinese）. ［臧海娟，任彥，薛小平.復(fù)雜網(wǎng)絡(luò)環(huán)境下的路由方法研究 ［J］.計算機(jī)應(yīng)用，2010，30 （8）：2210－2213.］

［14］WANG Xianpeng，YU Gang，LU Hongtao.A local information based routing strategy on the scale－free network ［J］.Modern Physics Letters B，2009，23 （10）：1291.

［15］WANG Wenxu，YIN Chuanyang，YAN Gang.Integrating local static and dynamic information for routing traffic ［J］.Physical Review E，2006，74 （1）：016101.

［16］YIN Chuanyang，WANG Binghong，WANG Wenxu.Efficient routing on scale－free networks based on local information［J］.Physics Letters A，2006，351 （4－5）：220－224.