周子騰，王　開，裴文江

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

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

周子騰，王開，裴文江

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

將式2帶入式3中可得：

p(l:vs→vd)=

(4)

從式4可以看出，當(dāng)r=0時(shí)：

(5)

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

(6)

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

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

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

p(l:vs→vd) =

(7)

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

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

(8)

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

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

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

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

2.1r→-∞時(shí)的仿真結(jié)果

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

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

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

2.2r=0時(shí)的仿真結(jié)果

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

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

2.3r=1時(shí)的仿真結(jié)果

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

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

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

3結(jié)語

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

參考文獻(xiàn)

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

責(zé)任編輯李思文

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-)，男 ,碩士研究生，主要從事復(fù)雜網(wǎng)絡(luò)等方面的研究。

中圖分類號：TP 393

文獻(xiàn)標(biāo)志碼：A