基于復雜網絡的路由策略研究

邱偉迪　蔣華

【摘 要】隨著信息數量及用戶數量的迅速增長，網絡經常由于數據包產生速率超過了整個網絡的通信能力而產生了擁塞現象。而網絡的擁塞控制與路由策略關系密切，該領域的研究受到了學者的廣泛關注。然而，之前對于網絡上的擁塞控制和路由策略的研究多數都是基于均勻網絡的，但現實中的大規模通信網絡如Internet、萬維網卻都呈現出小世界特性和無標度特性，因此，研究這類網絡上的路由策略具有非常現實的意義。文章主要針對BA無標度網絡模型上的路由策略進行了研究。首先分析研究了BA無標度網絡模型的統計特性及構造算法，并構建了BA無標度網絡模型上的網絡流量模型。在基于節點度的路由策略中存在著數據包的實際路徑偏離最短路徑的問題。為了解決這一問題，在基于節點度的路由策略的基礎上，文章提出了一種改進的路由策略。在這個改進的路由策略中，數據包根據鄰居節點的度及其到目的節點的距離兩方面的信息來選擇路由路徑，在實現將數據包分流到度小的節點上的同時，使數據包的實際路由路徑長度接近于最短路徑長度。仿真結果表明，文章提出的路由策略的效率要比未改進的路由策略要高。

【關鍵詞】復雜網絡；網絡擁塞；路由策略

【中圖分類號】TP393.01 【文獻標識碼】A 【文章編號】1674-0688（2018）09-0047-06

0 引言

許多現實中的網絡都可以用復雜網絡加以描述[1-5]。復雜網絡動態特性的典型表現之一就是網絡的通信。在網絡通信的過程中，產生了大量并發的數據包，這些數據包如果不能被及時傳遞出去，就會導致網絡的整體性能急劇下降，我們把這種現象稱為網絡擁塞。網絡的擁塞控制與路由策略有著密切的關系。路由策略的主要作用是為網絡中產生的數據包選擇從源節點到目的節點的路由路徑。從本質上說，路由策略不會使網絡產生擁塞，但是卻能影響網絡的整體性能。當網絡處于擁塞時，一個有效的路由策略能夠及時將數據包分流到其他空閑的線路上，從而緩解了網絡的擁塞，使得網絡的整體性能得到改善。但是一個無效的路由策略則不能及時將數據包分流到其他空閑的線路上，甚至會加劇網絡的擁塞，最終導致網絡完全癱瘓。

在復雜網絡環境下，研究者們已經提出了許多經過優化的路由策略，這些路由策略歸納起來主要有3類[6-14]：基于全局信息的路由策略、基于局部信息的路由策略和基于混合信息的路由策略。

常見的基于全局信息的路由策略主要有最短路徑路由策略和有效路徑路由策略。在這類路由策略中每個節點都要了解整個網絡的拓撲信息，因此數據包在進行路由選擇時需要進行大量的計算，在實時性要求高的情況下，這樣耗時巨大的計算是不能被接受的。為此，研究人員設計了基于局部信息的路由策略來解決這一問題。

基于局部信息的路由策略通常采用網絡的局部拓撲信息、鄰居節點的負載情況和鄰居節點的數據包遞送能力等局部信息來建立路由，在實現上較為容易。常見的這類路由策略主要有最大度路由策略、局部可見度路由策略和基于節點度的路由策略。然而，由于這類路由策略在建立路由時使用的是局部信息，網絡中任意兩個節點之間的實際路徑通常會偏離這兩個節點之間的最短路徑，因此這類路由策略通常是以犧牲節點間的實際路徑為代價的。為此，研究者們提出了基于混合信息的路由策略。

基于混合信息的路由策略是指將一個節點的度或負載、擁塞等因素及其到達其他節點的距離綜合考慮，它是全局信息與局部信息相互結合的一種策略。

本文以BA無標度網絡為模型，在基于節點度的路由策略的基礎上提出一種新的路由策略。基于節點度的路由策略是一種基于局部信息的路由策略，數據包在進行路由選擇時考慮了節點的度，實現了將數據包分流到度小的節點上，在一定程度上緩解了度大的節點的擁塞，但是這是以犧牲數據包的實際路徑為代價的。本文提出的路由策略是一種基于混合信息的路由策略，將一個節點的度及其到達目的節點的距離綜合考慮，實現了不但能將數據包在度大的中心節點與度小的節點間進行合理分配，而且能使數據包的實際路徑長度接近于最短路徑長度，從而提高了網絡的整體性能，減少了網絡擁塞產生的可能性。

1 基于節點度的路由策略的改進

1.1 網絡模型

許多現實中的網絡都具有兩個重要的特性：增長和優先連接。在這兩個特性的影響下，這些現實中的網絡的度分布都遵從冪律分布，這與BA無標度網絡所呈現出來的特性一致。于是本文按照BA無標度網絡模型的構造算法建立本文路由策略研究的基礎網絡模型[15-17]。

BA無標度網絡模型的構造算法可以描述如下。

（1）增長：在最初的時候，已經有m0個節點存在于網絡中，以后每一步都有一個新的節點加入到網絡中，這個新加入的節點與m（m≤m0）個已經存在的節點相連，m可以稱為網絡的連接密度。

（2）優先連接：如果用∏i來表示一個新加入的節點與一個已經存在的節點i的連接概率，用ki、kj作為節點i和節點j的度，則∏i與ki、kj之間滿足以下關系：

■（1）

根據公式（1），在經過t個時步后，一個BA無標度網絡就會形成，而且這個網絡擁有N=m0+t個節點、mt條邊。當t趨向于無窮大時，BA無標度網絡的平均度=2mt/t=2m，且每個節點的度k≥m。

在本文構建的網絡模型中，網絡的節點數N=1 000，m=m0=5。在這個網絡模型中，節點的度分布服從冪律分布，滿足P（k）：k-3，網絡平均度

（2）在任意t（t>t0）時刻，網絡開始傳遞將數據包從源節點傳遞到目的節點。如果數據包被傳遞到其目的節點，則被從網絡中刪除。每一個節點都要擔當服務器終端和路由器的角色，負責產生新的數據包、傳遞已經存在的數據包和接收被傳遞過來的數據包。

（3）假定每個節點的數據包隊列是無限長的，且每個節點的數據包遞送能力都一樣，等于網絡的平均度。當在一個節點處等待傳遞的數據包數目超過這個節點的數據包遞送能力時，則未被傳遞的數據包就要在該節點處排隊等待，在下一時刻按照先進先出（FiFO，fiRst iN fiRst out）的原則進行傳遞。

（4）在任意t（t>t0）時刻，當RRc時，網絡所產生的數據包數目大于被從網絡中刪除的數據包數目，在網絡中排隊等待傳遞的數據包數目就會積累得越來越多，網絡就會逐漸處于擁塞狀態。

1.2 路由策略設計

文獻[18]提出的基于節點度的路由策略在進行路由選擇時，需要將網絡中的數據包分流到度小的節點上，以避免大量的數據包通過度大的節點，造成度大的節點產生擁塞。但是在現實網絡中，度大的節點通常都是網絡的核心節點，一般都處于網絡中任意2個節點之間的最短路徑上，所以，將數據包分流到度小的節點，避開度大的節點有可能會使數據包的實際路徑偏離最短路徑，使數據包的實際路徑長度遠遠大于最短路徑長度，從而造成數據包的傳輸效率及網絡的整體性能下降。為了解決這一問題，在基于節點度的路由策略的基礎上，本文提出了一種改進的路由策略。這種改進的路由策略使用了網絡的混合信息，綜合考慮了節點的度和鄰居節點到目的節點的距離，而不是只依據節點的度這一信息，它實現了在對數據包進行分流的同時使數據包的實際路徑長度盡可能接近最短路徑長度。

在改進的路由策略中，數據包在進行路由選擇時，首先查詢目的節點是否包含在當前節點的鄰居節點中，如果包含，則數據包被直接傳遞到目的節點，完成此次路由選擇。如果當前節點的鄰居節點中不包含目的節點，則數據包被傳遞到根據一定的優先概率選取的鄰居節點，該鄰居節點重復以上過程，一直到找到目的節點為止。優先概率如公式（2）所示：

∏i=kiαdi β/■kjαdj β（2）

在公式（2）中，ki表示節點i的度，di表示節點i到目的節點的距離，α、β是可調參數，這里的求和符號則是對查詢范圍內的所有鄰居節點進行求和。可調參數α、β的取值不同，公式（2）計算出的優先概率也不同，數據包選擇的鄰居節點也就不同。根據公式（2）可以看出，當α>0，β>0時，ki越大、di越大的鄰居節點被選中的概率比較大；當α>0，β<0時，ki越大、di越小的鄰居節點被選中的概率比較大；當α<0，β>0時，ki越小、di越大的鄰居節點被選中的概率比較大；當α<0，β<0時，ki越小、di越小的鄰居節點被選中的概率比較大。因此在改進的路由策略中，我們希望能找到α和β的最優組合值，使網絡的通信能力得到提高，從而減少網絡擁塞產生的可能性。

2 仿真結果及分析

在經過大量的仿真實驗，我們將在網絡的通信能力和數據包的實際路徑長度兩個方面來驗證改進的路由策略的有效性。在對改進的路由策略進行仿真時，我們規定了網絡的節點數N=1 000，網絡的連接密度m=5，網絡平均度

在圖2中，可調參數α的取值范圍為[-3，1]，可調參數β的取值范圍為[-8，-3]，橫坐標是可調參數β，縱坐標是網絡的通信能力Rc。從圖2中我們可以發現：①α為負值時的Rc要大于α為正值時的Rc，如圖2中黑色三角、紅色方塊和藍色菱形所示的曲線都在黑色×和紫色星號所示的曲線之上。②α=-1時的Rc要大于α取其他值時的Rc，如圖2中黑色三角所示的曲線位于其他曲線之上。③對應不同的α值，Rc都在β=-6時最優，如圖2所示，不管什么顏色的曲線的最高點都停留在β=-6的位置上。④在α=-1，β=-6時，Rc=141，達到最大值，如圖2中所有曲線的最高點所示。

為了驗證經過改進的路由策略能夠實現將數據包分流到度小的節點上，本文研究了節點的度與節點的平均數據包數目之間的對應關系。在不同的α和β的組合值下，我們首先對度為k的節點上的數據包數目進行求和，然后再計算度為k的節點的數據包平均數目。

在圖3中，可調參數α的取值范圍為[-2，0]，可調參數β的取值為-6，橫坐標為節點的度，縱坐標為度為k的節點的數據包平均數目。從圖3中我們可以看出：①在α=0、β=-6時，數據包的平均數目取值范圍為（0，8]，如圖3中藍色的點所示；在α=-1、β=-6時，數據包的平均數目取值范圍為（0，6]，如圖3中大紅色的點所示；在α=1、β=-6時，數據包的平均數目取值范圍為（0，16]，如圖中黑色的點所示；在α=-2、β=-6時，數據包的平均數目取值范圍為（0，3]，如圖中藍色的點所示。②當α<0、β=-6時，節點間的平均數據包數目相差不大，數據包比較均勻地分布在度不同的節點上，這意味著數據包被比較均勻的分不到度小的節點和度大的節點上，從而緩解了度大的節點上的擁塞。當α≥0、β=-6時，度大的節點上的平均數據包數目與度小的節點上的平均數據包數目相差較大，這意味著數據包過多的通過度大的節點，網絡中度大的節點上容易產生擁塞，因此，通過對α值的調節，可以將一部分數據包分流到度小的節點上，分攤了度大的節點上的數據包流，降低了在度大的節點上產生擁塞的可能性，并且α為負值時的網絡的通信能力要比α為正值時的網絡的通信能力強。

接下來，本文還研究了網絡處于通暢狀態下和擁塞狀態下的性質。在圖4和圖5中，可調參數α的取值為-3、-1、1，可調參數β的取值為-6，橫坐標為時間t，縱坐標為網絡中的數據包數目NP（t）。圖4顯示了在通暢狀態下對于不同的α和β的組合值，網絡中的數據包數目NP（t）隨時間的增長變化情況，相應的，圖5顯示了在擁塞狀態下對于不同的α和β的組合值，網絡中的數據包數目NP（t）隨時間的增長變化情況。

如圖4所示，在網絡通暢的狀態下，網絡剛開始傳遞數據包時，只有少量數據包能被及時傳遞到目的節點，從而被從網絡中刪除，大量數據包因未能被及時傳遞到目的節點而滯留于網絡中，因此我們看到圖4在t很小的時候，NP（t）的值跳躍非常大。此后，隨著時間t的不斷增長，網絡中數據包數目基本上都能被及時傳遞到目的節點，網絡中滯留的數據包數目增長緩慢，因此我們看到圖4中的曲線隨著t的增長，網絡中的數據包數目最終保持在一個恒定的范圍內。如圖5所示，在網絡擁塞的狀態下，隨著時間t的不斷增長，網絡中不斷產生新的數據包，越來越多的數據包因不能被及時傳遞到目的節點而滯留于網絡中，這些數據包都不能夠被從網絡中刪除，因此我們可以看到圖中網絡中數據包的數目NP（t）隨著時間t的增長呈線性增長。

由于網絡的通信能力Rc會受到網絡的連接密度m的影響，為此本文還研究了BA無標度網絡的連接密度與網絡通信能力之間的關系。在數據包傳遞的過程中，網絡連接密度越大，數據包就能夠越快地被傳遞到目的節點，數據包的傳輸效率就越高，網絡的通信能力也就越強。如果網絡是一個全局耦合網絡，那么在一個時步內，所有的數據包就能被直接傳遞到目的節點，所有節點的數據包的遞送能力相加之后就是整個網絡的通信能力。Rc與m的關系曲線如圖6所示，可調參數α的取值范圍為[-3，1]，可調參數β的取值范圍為[-7，-5]，橫坐標為網絡的連接密度m，縱坐標為網絡的通信能力Rc。從圖6中我們可以看出，隨著網絡連接密度m的增加，對于任意的α和β值，網絡的通信能力Rc也隨之增加。但是不管m的值如何改變，網絡的通信能力始終在α=-1，β=-6達到最大，如圖6（b）中黑色三角曲線所示。

對于不同的網絡連接密，我們還比較了基于節點度的路由策略在α=-1時和經過改進的路由策略在α=-1、β=-6時的網絡的通信能力Rc，比較結果如圖7所示。在圖7中，可調參數α=-1，可調參數β=-6，橫坐標是網絡連接密度m，縱坐標是網絡的通信能力Rc。紅色方塊標記的是在本文提出的路由策略下的網絡通信能力，藍色菱形所標記的是基于節點度的路由策略下的網絡通信能力。從圖7中可以看出，紅色方塊標記的曲線始終位于藍色菱形所標記的曲線之上，也就是說，對于任意的網絡連接密度m，經過改進的路由策略的網絡通信能力Rc始終優于基于節點度的路由策略的網絡通信能力Rc。

2.2 數據包的實際路徑長度

基于節點度的路由策略，是一種基于局部信息的路由策略。這種路由策略在進行路由選擇時優先選擇度小的鄰居節點將數據包傳遞出去，只考慮了節點的度，沒有綜合考慮節點的其他信息。在這種策略中，因為優先考慮的是度小的節點，因此數據包比較容易選擇那些距離目的節點比較遠的鄰居節點，這也就是這個路由策略為什么比較容易造成數據包的實際路徑偏離最短路徑的原因。為了解決這一問題，本文針對基于節點度的路由策略提出了改進，綜合考慮了節點的度和距離的信息，希望可以在避開那些度大的節點的同時，選擇那些到目的節點的距離比較小的鄰居節點，從而使得數據包的傳輸效率得到提高，網絡的整體性能得到改善。

為了驗證經過改進的路由策略能使數據包的實際路徑長度能接近最短路徑長度，本文研究了在不同的α和β的組合值下，數據包的實際路徑長度與最短路徑長度之間的關系。本文提出參數s，它定義為數據包的實際路徑長度與最短路徑長度的比值：

s=h/d（4）

圖8給出了α和β的組合值與s的關系。在圖8中，可調參數α的取值范圍為[-3，1]，可調參數β的取值范圍為[-14，1]，橫坐標表示β的取值，縱坐標表示s的取值，不同顏色的曲線代表在不同的α值下數據包的實際路徑長度與最短路徑長度的比值。從圖8我們可以看出：①對于任意的α，隨著β值的增長，數據包的實際路徑長度與最短路徑長度的比值s也隨之增長；②對于任意的α，當β>-6時，數據包的實際路徑長度與最短路徑長度的比值s>1；③對于任意的α，當β≤-6時，數據包的實際路徑長度與最短路徑長度的比值s≈1。也就是說，對于任意的α，通過對調節β的值可以控制數據包的實際路徑長度，且當β≤-6時，數據包的實際路徑長度近似等于最短路徑長度，因此對于任意的α，β=-6是能夠使數據包的實際路徑長度最接近最短路徑長度的最優值。

本文還將改進的路由策略的數據包的實際路徑長度與最短路徑長度的比值s與基于節點度的路由策略的比值s進行了比較。圖9給出了在基于節點度的路由策略下，可調參數α與s的關系，在圖9中，可調參數α范圍為[-4，3]，橫坐標表示α的取值，縱坐標表示s的取值。從圖9可以看出，基于節點度的路由策略隨著可調參數α的值不斷減小，其數據包的實際路徑長度與最短路徑長度的比值s不斷增大，這說明該路由策略在進行數據包分流的時候，選擇的節點的度越小，數據包所走的實際路徑越偏離最短路徑，也就是說，該路由策略能夠進行數據包分流以犧牲數據包的實際路徑長度為前提條件的。基于節點度的路由策略在α=-1時，網絡的通信能力Rc達到最大值，但其數據包的實際路徑長度與最短路徑長度的比值s的值近似等于30，遠遠大于本文提出的路由策略在α=-1，β=-6時的值。

3 結語

本文針對基于節點度的路由策略中存在的數據包的實際路徑長度偏離最短路徑長度的問題，提出了一種改進的路由策略，這種路由策略綜合考慮了網絡中節點的度和距離，帶有兩個可調的參數，通過對可調參數的調節，能夠使數據包分散到度小的節點上，從而降低了在度大的節點上產生擁塞的可能性，并使數據包的實際路徑長度接近于最短路徑長度，從而提高了數據包的傳輸效率和網絡的通信能力。

參 考 文 獻

[1]Albert R，Barabasi A.Statistical mechanics of complex network[J].Rev.mod.Phys，2002，74（2）：47-97.

[2]李季，汪秉宏，蔣品群，等.節點數加速增長的復雜網絡生長模型[J].物理學報，2006，55（8）：4051.

[3]許丹，李翔，汪小帆.復雜網絡病毒傳播的局域控制研究[J].物理學報，2007，56（3）：1313.

[4]Evans T S.Complex Networks[J].Contemporary Physics，2004（45）：455-475.

[5]楊珉，張家玥，張達敏.復雜網絡拓撲結構的網絡模型研究綜述[J].通信技術，2014，47（12）：1354-1359.

[6]臧海娟，任彥，薛小平，等.復雜網絡環境下的路由方法研究[J].計算機應用，2010，8（30）：2210-2213.

[7]胡耀光，王圣軍，金濤，等.度關聯無標度網絡上的有傾向隨機行走[J].物理學報，2015，64（2）：028901.

[8]劉偉彥，劉斌.基于加權路由策略的復雜網絡擁塞控制研究[J].系統工程理論與實踐，2015，35（4）.

[9]羅開田，劉剛.基于交通引力場的復雜網絡路由選擇方法[J].計算機應用研究，2017，34（1）.

[10]楊先霞，濮存來，許忠奇，等.無標度網絡中基于能量的混合路由策略[J].物理學報，2016，65（24）：24-

29.

[11]姜彬彬.一種用于復雜移動網絡的安全路由協議設計[J].科學技術與工程，2016（5）：1671-1815.

[12]劉倩星，張達敏.基于混合信息的復雜網絡路由策略研究[J].計算機工程與設計，2012，33（3）：880-884.

[13]張帥.復雜網絡理論分析傳輸容量及其有效性改進策略研究[D].北京：北京交通大學，2015.

[14]Yang X，Li J，Pu C，et al.Traffic congestion and the lifetime of networks with moving nodes[J].Physical Review E，2017（5）：301-309.

[15]Bollobás B，Riordan O. mathematical results on scale-free random graphs[J].In：Bornholdt S，Schuster H G（ed.）Handbook of Graphs and Networks：From the Genome to the Internet，Berlin：Wiley-VCH，2003（6）：1-34.

[16]Cohen R，Havlin S.Scale-free networks are ultrasmall[J].Phys.Rev.Lett，2003，86：3682-3685.

[17]Holyfronczak A，Fronczak P，Holyst J A. mean-field theory for clustering coefficients in Barabási-Albert networks[J].Phys. Rev. E.，2003，68：116-126.

[18]Wang W X，Wand B H.Traffic Dynamics Based on Local Routing Protocol on a Scale-free Network[J].Phys. Rev. E.，2006，73：106-111.

[19]Arenas A，Guilera A D，Guimerà R.Communication in Networks with Hierarchical Branching[J].Phys. Rev. Lett.，2001，86：3196-3199.

[20]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[責任編輯：鐘聲賢]