基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略

周子騰，王　開，裴文江

(東南大學 信息科學與工程學院，江蘇 南京 210096)

基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略

周子騰，王開，裴文江

(東南大學 信息科學與工程學院，江蘇 南京 210096)

摘要：通過對最短路徑路由策略、有效路由策略、最小信息路徑路由策略的算法以及對廣義對數(shù)函數(shù)進行研究發(fā)現(xiàn)，將廣義對數(shù)函數(shù)內(nèi)的變量進行部分修改可實現(xiàn)上述3種算法的統(tǒng)一，并且通過對此種統(tǒng)一算法進行改進和仿真得出，在此統(tǒng)一算法變量連續(xù)變化的同時，某些路由策略在復雜網(wǎng)絡中的表現(xiàn)同樣具有連續(xù)性。該算法可以將3種路由策略進行完美的統(tǒng)一，同時可以根據(jù)所需的某種路由策略效果在可變化的連續(xù)范圍內(nèi)進行參數(shù)選擇，大大增加了路由策略的可操作性。

關鍵詞：統(tǒng)一路由策略；復雜網(wǎng)絡；負載傳輸；網(wǎng)絡容量

現(xiàn)實生活中存在各種各樣的復雜網(wǎng)絡，它們無處不在，由各種實體間的錯綜復雜的關系構成，其既可以是有形的，也可以是無形的[1]；同時，具有多種特性。近幾年來，隨著因特網(wǎng)等各種大規(guī)模復雜網(wǎng)絡的出現(xiàn)，社會對于網(wǎng)絡的依賴性不斷增強，因此，如何提高現(xiàn)實復雜網(wǎng)絡的傳輸性能以及實現(xiàn)負載的高效傳遞已經(jīng)成為研究領域里的一個重要課題。盡管現(xiàn)實復雜網(wǎng)絡的形式多種多樣，但均可將其看作節(jié)點間的聯(lián)系的集合，這時信息在節(jié)點間如何傳遞關系到網(wǎng)絡的傳播速度與效率；因此，復雜網(wǎng)絡最佳路由策略問題在復雜網(wǎng)絡研究領域占有重要的地位。

普遍從2個方面對如何提高復雜網(wǎng)絡的傳輸性能進行研究，分別是最大限度地優(yōu)化網(wǎng)絡拓撲結構以及提出更好的路由策略，但是，對于現(xiàn)實生活中已知的復雜網(wǎng)絡來說，改變其拓撲結構需要比較大的開銷；因此，研究工作更傾向于如何尋找更加合適的路由策略來增加復雜網(wǎng)絡的傳輸效率。其中，最短路徑路由策略(SP)、有效路由策略(ER)和最小信息路徑路由策略(MIP)為當前使用率較大的3種路由策略。最短路徑路由策略具有傳輸時間短和效率高的特點，但研究發(fā)現(xiàn)，在此種路由策略下，無標度網(wǎng)絡節(jié)點度的異構性導致節(jié)點介數(shù)的強異構性，容易使部分高介數(shù)節(jié)點出現(xiàn)信息擁塞現(xiàn)象；有關文獻提出有效路由策略，即在節(jié)點處理能力相同的情況下，將網(wǎng)絡中負載從核心節(jié)點分散給網(wǎng)絡的邊緣節(jié)點，雖然平均傳輸路徑有所提高，但網(wǎng)絡的傳輸負載能力提高10倍以上；最小信息路徑路由策略則中和了前2種路由策略的優(yōu)點，在相對于SP路由策略減少對網(wǎng)絡中度值大的節(jié)點的使用率的同時，相對于ER路由策略降低了其網(wǎng)絡平均路徑長度，在增大網(wǎng)絡容量的同時提高了網(wǎng)絡的傳輸效率。

通過對上述3種路由策略算法的研究以及對廣義對數(shù)函數(shù)的研究發(fā)現(xiàn)，將廣義對數(shù)函數(shù)進行一些變化，可實現(xiàn)這3種路由策略算法的統(tǒng)一，同時發(fā)現(xiàn)，此統(tǒng)一算法中的變量在某一范圍內(nèi)變化時，同樣表現(xiàn)出相同的路由效果，且此種變化效果具有連續(xù)性。

1統(tǒng)一路由策略

現(xiàn)實生活中有許多復雜網(wǎng)絡，研究者發(fā)明了多種網(wǎng)絡模型對現(xiàn)實中的網(wǎng)絡進行仿真，有隨機ER網(wǎng)絡、小世界WS網(wǎng)絡，無標度BA網(wǎng)絡等，同時，為了實現(xiàn)復雜網(wǎng)絡中數(shù)據(jù)的有效快速傳輸，多種路由策略又被相繼提出，其中基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略將各個路由策略進行了統(tǒng)一。

1.1基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略

廣義對數(shù)函數(shù)的表達式如下

(1)

當將式1中的w用網(wǎng)絡節(jié)點的度ki替換后可得：

(2)

式中，ki是復雜網(wǎng)絡中節(jié)點的度，假設vs≡v0,v1,…,vn-1≡vd為從源節(jié)點vs到目的節(jié)點vd之間的任意一條路徑，則統(tǒng)一路由策略如下：

(3)

將式2帶入式3中可得：

p(l:vs→vd)=

(4)

從式4可以看出，當r=0時：

(5)

式5為求從源節(jié)點vs到目的節(jié)點vd路徑之間所經(jīng)過節(jié)點的度值連乘積的最小值，即為最小信息路徑路由策略；而當|r|=1時有：

(6)

由此可見，此種基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略是將最小信息路徑路由與有效路由策略有效地結合到一起，當r=0時，為最小信息路徑路由策略；當|r|=1時，為網(wǎng)絡傳輸效率較高的有效路由策略。

1.2改進的統(tǒng)一路由策略

對式4進行分析得出，式4是最小信息路徑路由策略與有效路由策略的集合，但此時|r|的取值范圍為0≤|r|≤1，若將|r|的取值范圍變?yōu)閨r|≥0，式4變?yōu)槿缦滦问剑?/p>

p(l:vs→vd) =

(7)

式中，ki是復雜網(wǎng)絡中節(jié)點的度，vs≡v0,v1,…,vn-1≡vd為從源節(jié)點vs到目的節(jié)點vd之間的任意一條路徑，式7即為改進的統(tǒng)一路由策略。

當r=0時，為最小信息路徑路由策略；當|r|=1時，為網(wǎng)絡傳輸效率較高的有效路由策略；對于式7，當r→-∞時，設存在值-A，-A足夠小，即A取值足夠大時可得：

(8)

此時，由于A為某一足夠大的定值，同樣可以將1/A看作某一定值，策略變?yōu)榍舐窂剿?jīng)邊數(shù)的1/A倍的最小值，所以當r取某趨向于負無窮的值A時，統(tǒng)一路由策略變?yōu)樽疃搪窂铰酚刹呗?，目的是為了尋找從源?jié)點到目的節(jié)點間跳數(shù)最少的路徑。

由此可見，經(jīng)過改進的基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略更好的將最短路徑路由(SP)策略、有效路徑(ER)路由策略、最小路徑信息(MIP)路由策略統(tǒng)一在一起，并且當r=0時，為最小信息路徑路由策略；當|r|=1時，為網(wǎng)絡傳輸效率較高的有效路由策略；當r→-∞時，為最小路徑策略。

2統(tǒng)一路由策略的離散特征

上述介紹了基于廣義對數(shù)函數(shù)的統(tǒng)一路由策略、改進的統(tǒng)一路由策略以及策略的具體實現(xiàn)方法，本節(jié)通過對式7中r值的變化進行仿真，主要探索在r=-20、r=0和r=1時統(tǒng)一路由策略所表現(xiàn)出的特征以及當統(tǒng)一路由策略表現(xiàn)為各種不同的路由策略時，這些特征有何區(qū)別以及有何意義。

2.1r→-∞時的仿真結果

對于統(tǒng)一路由策略，當r→-∞時，表現(xiàn)為最短路徑路由策略特征，在此處取r=-20，經(jīng)過計算路由表仿真得到此時網(wǎng)絡的平均路徑長度為4.16，路由計算時間為12分2秒，圖1所示為此時統(tǒng)一路由策略下網(wǎng)絡中節(jié)點度與度平均介數(shù)之間的關系，圖中橫坐標為網(wǎng)絡中的不同度值，縱坐標為網(wǎng)絡度值對應的度平均介數(shù)。

圖1　r=-20條件下節(jié)點度與度平均介數(shù)之間的關系圖

通過仿真得出的結果與之前研究者發(fā)現(xiàn)的最短路徑路由策略下網(wǎng)絡的表現(xiàn)一致，這充分說明了統(tǒng)一路由策略在r=-20時可看作最短路徑路由策略。

2.2r=0時的仿真結果

對于統(tǒng)一路由策略，當r=0時，表現(xiàn)為最小信息路徑路由策略，經(jīng)過路由表仿真得到此時網(wǎng)絡的平均路徑長度為4.7，路由計算時間為8分34秒。

經(jīng)仿真發(fā)現(xiàn)網(wǎng)絡中的節(jié)點度值與度平均介數(shù)成正比關系，網(wǎng)絡在r=0時的統(tǒng)一路由策略下的表現(xiàn)與之前最小信息路徑路由策略一致，這表明統(tǒng)一路由策略在r=0可以看作最小信息路徑路由策略，且傳輸效率以及網(wǎng)絡容量均高于r=-21時的統(tǒng)一路由策略。

2.3r=1時的仿真結果

對于統(tǒng)一路由策略，當r=1時，表現(xiàn)為有效路由策略，經(jīng)過路由表仿真得到此時網(wǎng)絡的平均路徑長度為7.15，路由計算時間為12分2秒，圖2所示為此時統(tǒng)一路由策略下網(wǎng)絡中節(jié)點度與度平均介數(shù)之間的關系，圖中橫坐標為網(wǎng)絡中的不同度值，縱坐標為網(wǎng)絡度值對應的度平均介數(shù)。從仿真結果可以看出，根據(jù)實現(xiàn)方法計算得出的平均路徑長度為7.15，比r取-20和0時明顯增大，這是因為此種策略大大提高了邊緣節(jié)點的利用率，同時減少了度值大的節(jié)點的使用，使得網(wǎng)絡中的路由路徑大都在網(wǎng)絡邊緣行走，使整個網(wǎng)絡的平均路徑長度大大提高，路由計算時間為12分鐘2秒，此路由時間與r取-20時一樣，這是因為在r≠0時，路由策略使用的計算方法為同一公式，這使2種方法計算時間一樣，與當初預想一致，從圖2還可以看出，此時路由策略對度值小于12的節(jié)點的利用率逐漸提高，在12左右達到最大利用率，然后隨著度值的增大，利用率逐漸減小。

圖2　2r=1條件下節(jié)點度與度平均介數(shù)之間的關系圖

經(jīng)仿真分析可知，網(wǎng)絡在r=1時的統(tǒng)一路由策略下的表現(xiàn)與之前分析的有效路由策略一致，這表明統(tǒng)一路由策略在r=1可以看作有效路由策略，且在約束復雜網(wǎng)絡中節(jié)點度的最大值的情況下，網(wǎng)絡容量要低于r=0時的統(tǒng)一路由策略下的網(wǎng)絡容量。

3結語

此種統(tǒng)一策略實現(xiàn)了SP路由策略、MIP路由策略以及ER路由策略的完美統(tǒng)一。仿真發(fā)現(xiàn)，當r→-∞時，統(tǒng)一路由策略表現(xiàn)為最短路徑(SP)路由策略；當r=0時，網(wǎng)絡表現(xiàn)與最小信息路徑(MIP)路由策略的表現(xiàn)一致，網(wǎng)絡中的節(jié)點度與節(jié)點度平均介數(shù)呈現(xiàn)正比關系；當r=1時，統(tǒng)一路由策略下的復雜網(wǎng)絡表現(xiàn)出有效路由(ER)策略控制下的特點，此時網(wǎng)絡加強了對邊緣小度值節(jié)點的使用，有效保護了度值較大的節(jié)點，網(wǎng)絡的平均路徑長度最小，網(wǎng)絡傳輸性能最佳。

參考文獻

[1] 李艷芳.多層網(wǎng)絡中基于資源優(yōu)化的配置方式[J].新技術新工藝，2014(9)：91-93.

責任編輯李思文

Unified Routing Strategy based on Generalized Logarithmic Function

ZHOU Ziteng, WANG Kai, PEI Wenjiang

(School of Information Science and Engineering, Southeast University, Nanjing 210096, China)

Abstract:From the research of the shortest path routing strategy, efficient routing strategy, the minimum information path routing strategy and generalized logarithmic function, it was found that if modified the variables of generalized logarithmic function, the function can be the unity of the mentioned routing strategy algorithms before, and it was also found that by improving and simulating the unified algorithm, when the variables in the algorithm changed, the performance of some routing strategies changed at the same time. This Phenomenon showed that the unified routing strategy can not only combine the three routing strategy, but also can provide the function that made it possible to choose the appropriate parameters to get the expectant results, in other words, it enhanced the maneuverability of routing strategies.

Key words:unified routing strategy, complex networks, traffic transmission, network capacity

收稿日期：2014-12-03

作者簡介：周子騰(1990-)，男 ,碩士研究生，主要從事復雜網(wǎng)絡等方面的研究。

中圖分類號：TP 393

文獻標志碼：A