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

邱偉迪　蔣華

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

【關(guān)鍵詞】復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)擁塞；路由策略

【中圖分類號(hào)】TP393.01 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688（2018）09-0047-06

0 引言

許多現(xiàn)實(shí)中的網(wǎng)絡(luò)都可以用復(fù)雜網(wǎng)絡(luò)加以描述[1-5]。復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)特性的典型表現(xiàn)之一就是網(wǎng)絡(luò)的通信。在網(wǎng)絡(luò)通信的過(guò)程中，產(chǎn)生了大量并發(fā)的數(shù)據(jù)包，這些數(shù)據(jù)包如果不能被及時(shí)傳遞出去，就會(huì)導(dǎo)致網(wǎng)絡(luò)的整體性能急劇下降，我們把這種現(xiàn)象稱為網(wǎng)絡(luò)擁塞。網(wǎng)絡(luò)的擁塞控制與路由策略有著密切的關(guān)系。路由策略的主要作用是為網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包選擇從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由路徑。從本質(zhì)上說(shuō)，路由策略不會(huì)使網(wǎng)絡(luò)產(chǎn)生擁塞，但是卻能影響網(wǎng)絡(luò)的整體性能。當(dāng)網(wǎng)絡(luò)處于擁塞時(shí)，一個(gè)有效的路由策略能夠及時(shí)將數(shù)據(jù)包分流到其他空閑的線路上，從而緩解了網(wǎng)絡(luò)的擁塞，使得網(wǎng)絡(luò)的整體性能得到改善。但是一個(gè)無(wú)效的路由策略則不能及時(shí)將數(shù)據(jù)包分流到其他空閑的線路上，甚至?xí)觿【W(wǎng)絡(luò)的擁塞，最終導(dǎo)致網(wǎng)絡(luò)完全癱瘓。

在復(fù)雜網(wǎng)絡(luò)環(huán)境下，研究者們已經(jīng)提出了許多經(jīng)過(guò)優(yōu)化的路由策略，這些路由策略歸納起來(lái)主要有3類[6-14]：基于全局信息的路由策略、基于局部信息的路由策略和基于混合信息的路由策略。

常見的基于全局信息的路由策略主要有最短路徑路由策略和有效路徑路由策略。在這類路由策略中每個(gè)節(jié)點(diǎn)都要了解整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，因此?shù)據(jù)包在進(jìn)行路由選擇時(shí)需要進(jìn)行大量的計(jì)算，在實(shí)時(shí)性要求高的情況下，這樣耗時(shí)巨大的計(jì)算是不能被接受的。為此，研究人員設(shè)計(jì)了基于局部信息的路由策略來(lái)解決這一問(wèn)題。

基于局部信息的路由策略通常采用網(wǎng)絡(luò)的局部拓?fù)湫畔?、鄰居?jié)點(diǎn)的負(fù)載情況和鄰居節(jié)點(diǎn)的數(shù)據(jù)包遞送能力等局部信息來(lái)建立路由，在實(shí)現(xiàn)上較為容易。常見的這類路由策略主要有最大度路由策略、局部可見度路由策略和基于節(jié)點(diǎn)度的路由策略。然而，由于這類路由策略在建立路由時(shí)使用的是局部信息，網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的實(shí)際路徑通常會(huì)偏離這兩個(gè)節(jié)點(diǎn)之間的最短路徑，因此這類路由策略通常是以犧牲節(jié)點(diǎn)間的實(shí)際路徑為代價(jià)的。為此，研究者們提出了基于混合信息的路由策略。

基于混合信息的路由策略是指將一個(gè)節(jié)點(diǎn)的度或負(fù)載、擁塞等因素及其到達(dá)其他節(jié)點(diǎn)的距離綜合考慮，它是全局信息與局部信息相互結(jié)合的一種策略。

本文以BA無(wú)標(biāo)度網(wǎng)絡(luò)為模型，在基于節(jié)點(diǎn)度的路由策略的基礎(chǔ)上提出一種新的路由策略?；诠?jié)點(diǎn)度的路由策略是一種基于局部信息的路由策略，數(shù)據(jù)包在進(jìn)行路由選擇時(shí)考慮了節(jié)點(diǎn)的度，實(shí)現(xiàn)了將數(shù)據(jù)包分流到度小的節(jié)點(diǎn)上，在一定程度上緩解了度大的節(jié)點(diǎn)的擁塞，但是這是以犧牲數(shù)據(jù)包的實(shí)際路徑為代價(jià)的。本文提出的路由策略是一種基于混合信息的路由策略，將一個(gè)節(jié)點(diǎn)的度及其到達(dá)目的節(jié)點(diǎn)的距離綜合考慮，實(shí)現(xiàn)了不但能將數(shù)據(jù)包在度大的中心節(jié)點(diǎn)與度小的節(jié)點(diǎn)間進(jìn)行合理分配，而且能使數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度接近于最短路徑長(zhǎng)度，從而提高了網(wǎng)絡(luò)的整體性能，減少了網(wǎng)絡(luò)擁塞產(chǎn)生的可能性。

1 基于節(jié)點(diǎn)度的路由策略的改進(jìn)

1.1 網(wǎng)絡(luò)模型

許多現(xiàn)實(shí)中的網(wǎng)絡(luò)都具有兩個(gè)重要的特性：增長(zhǎng)和優(yōu)先連接。在這兩個(gè)特性的影響下，這些現(xiàn)實(shí)中的網(wǎng)絡(luò)的度分布都遵從冪律分布，這與BA無(wú)標(biāo)度網(wǎng)絡(luò)所呈現(xiàn)出來(lái)的特性一致。于是本文按照BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法建立本文路由策略研究的基礎(chǔ)網(wǎng)絡(luò)模型[15-17]。

BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法可以描述如下。

（1）增長(zhǎng)：在最初的時(shí)候，已經(jīng)有m0個(gè)節(jié)點(diǎn)存在于網(wǎng)絡(luò)中，以后每一步都有一個(gè)新的節(jié)點(diǎn)加入到網(wǎng)絡(luò)中，這個(gè)新加入的節(jié)點(diǎn)與m（m≤m0）個(gè)已經(jīng)存在的節(jié)點(diǎn)相連，m可以稱為網(wǎng)絡(luò)的連接密度。

（2）優(yōu)先連接：如果用∏i來(lái)表示一個(gè)新加入的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i的連接概率，用ki、kj作為節(jié)點(diǎn)i和節(jié)點(diǎn)j的度，則∏i與ki、kj之間滿足以下關(guān)系：

■（1）

根據(jù)公式（1），在經(jīng)過(guò)t個(gè)時(shí)步后，一個(gè)BA無(wú)標(biāo)度網(wǎng)絡(luò)就會(huì)形成，而且這個(gè)網(wǎng)絡(luò)擁有N=m0+t個(gè)節(jié)點(diǎn)、mt條邊。當(dāng)t趨向于無(wú)窮大時(shí)，BA無(wú)標(biāo)度網(wǎng)絡(luò)的平均度=2mt/t=2m，且每個(gè)節(jié)點(diǎn)的度k≥m。

在本文構(gòu)建的網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N=1 000，m=m0=5。在這個(gè)網(wǎng)絡(luò)模型中，節(jié)點(diǎn)的度分布服從冪律分布，滿足P（k）：k-3，網(wǎng)絡(luò)平均度

（2）在任意t（t>t0）時(shí)刻，網(wǎng)絡(luò)開始傳遞將數(shù)據(jù)包從源節(jié)點(diǎn)傳遞到目的節(jié)點(diǎn)。如果數(shù)據(jù)包被傳遞到其目的節(jié)點(diǎn)，則被從網(wǎng)絡(luò)中刪除。每一個(gè)節(jié)點(diǎn)都要擔(dān)當(dāng)服務(wù)器終端和路由器的角色，負(fù)責(zé)產(chǎn)生新的數(shù)據(jù)包、傳遞已經(jīng)存在的數(shù)據(jù)包和接收被傳遞過(guò)來(lái)的數(shù)據(jù)包。

（3）假定每個(gè)節(jié)點(diǎn)的數(shù)據(jù)包隊(duì)列是無(wú)限長(zhǎng)的，且每個(gè)節(jié)點(diǎn)的數(shù)據(jù)包遞送能力都一樣，等于網(wǎng)絡(luò)的平均度。當(dāng)在一個(gè)節(jié)點(diǎn)處等待傳遞的數(shù)據(jù)包數(shù)目超過(guò)這個(gè)節(jié)點(diǎn)的數(shù)據(jù)包遞送能力時(shí)，則未被傳遞的數(shù)據(jù)包就要在該節(jié)點(diǎn)處排隊(duì)等待，在下一時(shí)刻按照先進(jìn)先出（FiFO，fiRst iN fiRst out）的原則進(jìn)行傳遞。

（4）在任意t（t>t0）時(shí)刻，當(dāng)RRc時(shí)，網(wǎng)絡(luò)所產(chǎn)生的數(shù)據(jù)包數(shù)目大于被從網(wǎng)絡(luò)中刪除的數(shù)據(jù)包數(shù)目，在網(wǎng)絡(luò)中排隊(duì)等待傳遞的數(shù)據(jù)包數(shù)目就會(huì)積累得越來(lái)越多，網(wǎng)絡(luò)就會(huì)逐漸處于擁塞狀態(tài)。

1.2 路由策略設(shè)計(jì)

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

在改進(jìn)的路由策略中，數(shù)據(jù)包在進(jìn)行路由選擇時(shí)，首先查詢目的節(jié)點(diǎn)是否包含在當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中，如果包含，則數(shù)據(jù)包被直接傳遞到目的節(jié)點(diǎn)，完成此次路由選擇。如果當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中不包含目的節(jié)點(diǎn)，則數(shù)據(jù)包被傳遞到根據(jù)一定的優(yōu)先概率選取的鄰居節(jié)點(diǎn)，該鄰居節(jié)點(diǎn)重復(fù)以上過(guò)程，一直到找到目的節(jié)點(diǎn)為止。優(yōu)先概率如公式（2）所示：

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

在公式（2）中，ki表示節(jié)點(diǎn)i的度，di表示節(jié)點(diǎn)i到目的節(jié)點(diǎn)的距離，α、β是可調(diào)參數(shù)，這里的求和符號(hào)則是對(duì)查詢范圍內(nèi)的所有鄰居節(jié)點(diǎn)進(jìn)行求和?？烧{(diào)參數(shù)α、β的取值不同，公式（2）計(jì)算出的優(yōu)先概率也不同，數(shù)據(jù)包選擇的鄰居節(jié)點(diǎn)也就不同。根據(jù)公式（2）可以看出，當(dāng)α>0，β>0時(shí)，ki越大、di越大的鄰居節(jié)點(diǎn)被選中的概率比較大；當(dāng)α>0，β<0時(shí)，ki越大、di越小的鄰居節(jié)點(diǎn)被選中的概率比較大；當(dāng)α<0，β>0時(shí)，ki越小、di越大的鄰居節(jié)點(diǎn)被選中的概率比較大；當(dāng)α<0，β<0時(shí)，ki越小、di越小的鄰居節(jié)點(diǎn)被選中的概率比較大。因此在改進(jìn)的路由策略中，我們希望能找到α和β的最優(yōu)組合值，使網(wǎng)絡(luò)的通信能力得到提高，從而減少網(wǎng)絡(luò)擁塞產(chǎn)生的可能性。

2 仿真結(jié)果及分析

在經(jīng)過(guò)大量的仿真實(shí)驗(yàn)，我們將在網(wǎng)絡(luò)的通信能力和數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度兩個(gè)方面來(lái)驗(yàn)證改進(jìn)的路由策略的有效性。在對(duì)改進(jìn)的路由策略進(jìn)行仿真時(shí)，我們規(guī)定了網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N=1 000，網(wǎng)絡(luò)的連接密度m=5，網(wǎng)絡(luò)平均度

在圖2中，可調(diào)參數(shù)α的取值范圍為[-3，1]，可調(diào)參數(shù)β的取值范圍為[-8，-3]，橫坐標(biāo)是可調(diào)參數(shù)β，縱坐標(biāo)是網(wǎng)絡(luò)的通信能力Rc。從圖2中我們可以發(fā)現(xiàn)：①α為負(fù)值時(shí)的Rc要大于α為正值時(shí)的Rc，如圖2中黑色三角、紅色方塊和藍(lán)色菱形所示的曲線都在黑色×和紫色星號(hào)所示的曲線之上。②α=-1時(shí)的Rc要大于α取其他值時(shí)的Rc，如圖2中黑色三角所示的曲線位于其他曲線之上。③對(duì)應(yīng)不同的α值，Rc都在β=-6時(shí)最優(yōu)，如圖2所示，不管什么顏色的曲線的最高點(diǎn)都停留在β=-6的位置上。④在α=-1，β=-6時(shí)，Rc=141，達(dá)到最大值，如圖2中所有曲線的最高點(diǎn)所示。

為了驗(yàn)證經(jīng)過(guò)改進(jìn)的路由策略能夠?qū)崿F(xiàn)將數(shù)據(jù)包分流到度小的節(jié)點(diǎn)上，本文研究了節(jié)點(diǎn)的度與節(jié)點(diǎn)的平均數(shù)據(jù)包數(shù)目之間的對(duì)應(yīng)關(guān)系。在不同的α和β的組合值下，我們首先對(duì)度為k的節(jié)點(diǎn)上的數(shù)據(jù)包數(shù)目進(jìn)行求和，然后再計(jì)算度為k的節(jié)點(diǎn)的數(shù)據(jù)包平均數(shù)目。

在圖3中，可調(diào)參數(shù)α的取值范圍為[-2，0]，可調(diào)參數(shù)β的取值為-6，橫坐標(biāo)為節(jié)點(diǎn)的度，縱坐標(biāo)為度為k的節(jié)點(diǎn)的數(shù)據(jù)包平均數(shù)目。從圖3中我們可以看出：①在α=0、β=-6時(shí)，數(shù)據(jù)包的平均數(shù)目取值范圍為（0，8]，如圖3中藍(lán)色的點(diǎn)所示；在α=-1、β=-6時(shí)，數(shù)據(jù)包的平均數(shù)目取值范圍為（0，6]，如圖3中大紅色的點(diǎn)所示；在α=1、β=-6時(shí)，數(shù)據(jù)包的平均數(shù)目取值范圍為（0，16]，如圖中黑色的點(diǎn)所示；在α=-2、β=-6時(shí)，數(shù)據(jù)包的平均數(shù)目取值范圍為（0，3]，如圖中藍(lán)色的點(diǎn)所示。②當(dāng)α<0、β=-6時(shí)，節(jié)點(diǎn)間的平均數(shù)據(jù)包數(shù)目相差不大，數(shù)據(jù)包比較均勻地分布在度不同的節(jié)點(diǎn)上，這意味著數(shù)據(jù)包被比較均勻的分不到度小的節(jié)點(diǎn)和度大的節(jié)點(diǎn)上，從而緩解了度大的節(jié)點(diǎn)上的擁塞。當(dāng)α≥0、β=-6時(shí)，度大的節(jié)點(diǎn)上的平均數(shù)據(jù)包數(shù)目與度小的節(jié)點(diǎn)上的平均數(shù)據(jù)包數(shù)目相差較大，這意味著數(shù)據(jù)包過(guò)多的通過(guò)度大的節(jié)點(diǎn)，網(wǎng)絡(luò)中度大的節(jié)點(diǎn)上容易產(chǎn)生擁塞，因此，通過(guò)對(duì)α值的調(diào)節(jié)，可以將一部分?jǐn)?shù)據(jù)包分流到度小的節(jié)點(diǎn)上，分?jǐn)偭硕却蟮墓?jié)點(diǎn)上的數(shù)據(jù)包流，降低了在度大的節(jié)點(diǎn)上產(chǎn)生擁塞的可能性，并且α為負(fù)值時(shí)的網(wǎng)絡(luò)的通信能力要比α為正值時(shí)的網(wǎng)絡(luò)的通信能力強(qiáng)。

接下來(lái)，本文還研究了網(wǎng)絡(luò)處于通暢狀態(tài)下和擁塞狀態(tài)下的性質(zhì)。在圖4和圖5中，可調(diào)參數(shù)α的取值為-3、-1、1，可調(diào)參數(shù)β的取值為-6，橫坐標(biāo)為時(shí)間t，縱坐標(biāo)為網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)目NP（t）。圖4顯示了在通暢狀態(tài)下對(duì)于不同的α和β的組合值，網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)目NP（t）隨時(shí)間的增長(zhǎng)變化情況，相應(yīng)的，圖5顯示了在擁塞狀態(tài)下對(duì)于不同的α和β的組合值，網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)目NP（t）隨時(shí)間的增長(zhǎng)變化情況。

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

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

對(duì)于不同的網(wǎng)絡(luò)連接密，我們還比較了基于節(jié)點(diǎn)度的路由策略在α=-1時(shí)和經(jīng)過(guò)改進(jìn)的路由策略在α=-1、β=-6時(shí)的網(wǎng)絡(luò)的通信能力Rc，比較結(jié)果如圖7所示。在圖7中，可調(diào)參數(shù)α=-1，可調(diào)參數(shù)β=-6，橫坐標(biāo)是網(wǎng)絡(luò)連接密度m，縱坐標(biāo)是網(wǎng)絡(luò)的通信能力Rc。紅色方塊標(biāo)記的是在本文提出的路由策略下的網(wǎng)絡(luò)通信能力，藍(lán)色菱形所標(biāo)記的是基于節(jié)點(diǎn)度的路由策略下的網(wǎng)絡(luò)通信能力。從圖7中可以看出，紅色方塊標(biāo)記的曲線始終位于藍(lán)色菱形所標(biāo)記的曲線之上，也就是說(shuō)，對(duì)于任意的網(wǎng)絡(luò)連接密度m，經(jīng)過(guò)改進(jìn)的路由策略的網(wǎng)絡(luò)通信能力Rc始終優(yōu)于基于節(jié)點(diǎn)度的路由策略的網(wǎng)絡(luò)通信能力Rc。

2.2 數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度

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

為了驗(yàn)證經(jīng)過(guò)改進(jìn)的路由策略能使數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度能接近最短路徑長(zhǎng)度，本文研究了在不同的α和β的組合值下，數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度與最短路徑長(zhǎng)度之間的關(guān)系。本文提出參數(shù)s，它定義為數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度與最短路徑長(zhǎng)度的比值：

s=h/d（4）

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

本文還將改進(jìn)的路由策略的數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度與最短路徑長(zhǎng)度的比值s與基于節(jié)點(diǎn)度的路由策略的比值s進(jìn)行了比較。圖9給出了在基于節(jié)點(diǎn)度的路由策略下，可調(diào)參數(shù)α與s的關(guān)系，在圖9中，可調(diào)參數(shù)α范圍為[-4，3]，橫坐標(biāo)表示α的取值，縱坐標(biāo)表示s的取值。從圖9可以看出，基于節(jié)點(diǎn)度的路由策略隨著可調(diào)參數(shù)α的值不斷減小，其數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度與最短路徑長(zhǎng)度的比值s不斷增大，這說(shuō)明該路由策略在進(jìn)行數(shù)據(jù)包分流的時(shí)候，選擇的節(jié)點(diǎn)的度越小，數(shù)據(jù)包所走的實(shí)際路徑越偏離最短路徑，也就是說(shuō)，該路由策略能夠進(jìn)行數(shù)據(jù)包分流以犧牲數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度為前提條件的?；诠?jié)點(diǎn)度的路由策略在α=-1時(shí)，網(wǎng)絡(luò)的通信能力Rc達(dá)到最大值，但其數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度與最短路徑長(zhǎng)度的比值s的值近似等于30，遠(yuǎn)遠(yuǎn)大于本文提出的路由策略在α=-1，β=-6時(shí)的值。

3 結(jié)語(yǔ)

本文針對(duì)基于節(jié)點(diǎn)度的路由策略中存在的數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度偏離最短路徑長(zhǎng)度的問(wèn)題，提出了一種改進(jìn)的路由策略，這種路由策略綜合考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)的度和距離，帶有兩個(gè)可調(diào)的參數(shù)，通過(guò)對(duì)可調(diào)參數(shù)的調(diào)節(jié)，能夠使數(shù)據(jù)包分散到度小的節(jié)點(diǎn)上，從而降低了在度大的節(jié)點(diǎn)上產(chǎn)生擁塞的可能性，并使數(shù)據(jù)包的實(shí)際路徑長(zhǎng)度接近于最短路徑長(zhǎng)度，從而提高了數(shù)據(jù)包的傳輸效率和網(wǎng)絡(luò)的通信能力。

參 考 文 獻(xiàn)

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

[2]李季，汪秉宏，蔣品群，等.節(jié)點(diǎn)數(shù)加速增長(zhǎng)的復(fù)雜網(wǎng)絡(luò)生長(zhǎng)模型[J].物理學(xué)報(bào)，2006，55（8）：4051.

[3]許丹，李翔，汪小帆.復(fù)雜網(wǎng)絡(luò)病毒傳播的局域控制研究[J].物理學(xué)報(bào)，2007，56（3）：1313.

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

[5]楊珉，張家玥，張達(dá)敏.復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)模型研究綜述[J].通信技術(shù)，2014，47（12）：1354-1359.

[6]臧海娟，任彥，薛小平，等.復(fù)雜網(wǎng)絡(luò)環(huán)境下的路由方法研究[J].計(jì)算機(jī)應(yīng)用，2010，8（30）：2210-2213.

[7]胡耀光，王圣軍，金濤，等.度關(guān)聯(lián)無(wú)標(biāo)度網(wǎng)絡(luò)上的有傾向隨機(jī)行走[J].物理學(xué)報(bào)，2015，64（2）：028901.

[8]劉偉彥，劉斌.基于加權(quán)路由策略的復(fù)雜網(wǎng)絡(luò)擁塞控制研究[J].系統(tǒng)工程理論與實(shí)踐，2015，35（4）.

[9]羅開田，劉剛.基于交通引力場(chǎng)的復(fù)雜網(wǎng)絡(luò)路由選擇方法[J].計(jì)算機(jī)應(yīng)用研究，2017，34（1）.

[10]楊先霞，濮存來(lái)，許忠奇，等.無(wú)標(biāo)度網(wǎng)絡(luò)中基于能量的混合路由策略[J].物理學(xué)報(bào)，2016，65（24）：24-

29.

[11]姜彬彬.一種用于復(fù)雜移動(dòng)網(wǎng)絡(luò)的安全路由協(xié)議設(shè)計(jì)[J].科學(xué)技術(shù)與工程，2016（5）：1671-1815.

[12]劉倩星，張達(dá)敏.基于混合信息的復(fù)雜網(wǎng)絡(luò)路由策略研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（3）：880-884.

[13]張帥.復(fù)雜網(wǎng)絡(luò)理論分析傳輸容量及其有效性改進(jìn)策略研究[D].北京：北京交通大學(xué)，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，F(xiàn)ronczak 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]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[責(zé)任編輯：鐘聲賢]