一種高聚類(lèi)無(wú)標(biāo)度網(wǎng)絡(luò)中的混合路由策略*

徐玉珠

（民航貴州空管分局，貴州 貴陽(yáng) 550002）

0 引 言

現(xiàn)實(shí)生活中與人們息息相關(guān)的互聯(lián)網(wǎng)、交通網(wǎng)、生物神經(jīng)網(wǎng)、通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)和社交關(guān)系網(wǎng)等大型網(wǎng)絡(luò)，都可以被模擬構(gòu)建成復(fù)雜網(wǎng)絡(luò)的模型。在復(fù)雜網(wǎng)絡(luò)的研究歷史上，Watts和Strogatz提出了“小世界網(wǎng)絡(luò)”。該模型反映了很多復(fù)雜網(wǎng)絡(luò)平均路徑短且聚類(lèi)系數(shù)高的小世界特征。之后，Barabási和Albert建立的“BA無(wú)標(biāo)度網(wǎng)絡(luò)”，揭示了復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度具有冪律分布的特性，即無(wú)標(biāo)度性質(zhì)。但是，現(xiàn)實(shí)生活中的網(wǎng)絡(luò)幾乎同時(shí)具備這兩種網(wǎng)絡(luò)的特性，因此建立一個(gè)高聚類(lèi)無(wú)標(biāo)度網(wǎng)絡(luò)十分必要[1-2]。

以現(xiàn)實(shí)通信網(wǎng)絡(luò)為例，網(wǎng)絡(luò)中超負(fù)荷的流量常常導(dǎo)致網(wǎng)絡(luò)擁塞的產(chǎn)生。良好的傳輸能力和較大的網(wǎng)絡(luò)吞吐量，能夠保證網(wǎng)絡(luò)運(yùn)行通暢，而較差的傳輸能力和較小的網(wǎng)絡(luò)吞吐量會(huì)嚴(yán)重影響網(wǎng)絡(luò)運(yùn)行的通暢。目前，可知的影響網(wǎng)絡(luò)傳輸能力和吞吐量的因素主要有兩個(gè)。一是網(wǎng)絡(luò)結(jié)構(gòu)性因素，如網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)間的連接方式、節(jié)點(diǎn)的處理能力和通信帶寬等。若是通過(guò)改變網(wǎng)絡(luò)的結(jié)構(gòu)性因素提高網(wǎng)絡(luò)傳輸能力，通常比較困難。例如，對(duì)Internet網(wǎng)絡(luò)中的某兩個(gè)路由器增加一個(gè)連接，需要在它們之間鋪設(shè)一條通信線路，費(fèi)用可能非常昂貴，且實(shí)際鋪設(shè)不一定能夠?qū)崿F(xiàn)，所以這樣的方式不現(xiàn)實(shí)。另一個(gè)是路由選擇策略因素。一個(gè)合理的路由選擇策略可以極大地提高網(wǎng)絡(luò)的傳輸能力和吞吐量，且采用良好的路由方案也較為可行。所以，在研究網(wǎng)絡(luò)擁塞問(wèn)題、傳輸能力問(wèn)題及吞吐量問(wèn)題方面，目前通常針對(duì)路由策略進(jìn)行研究[3]。

基于上述思想，本文在BA網(wǎng)絡(luò)基礎(chǔ)上，考慮加入社團(tuán)結(jié)構(gòu)，并考慮邊的演化存在于新舊節(jié)點(diǎn)同時(shí)也存在于舊節(jié)點(diǎn)之間，以此建立改進(jìn)的BA網(wǎng)絡(luò)，使之更貼近于現(xiàn)實(shí)網(wǎng)絡(luò)。同時(shí)，以改進(jìn)的模型為平臺(tái)，建立了一種混合信息路由策略。結(jié)合最短路徑路由算法和優(yōu)化的傳遞概率模型，把節(jié)點(diǎn)的介數(shù)作為其傳遞信息的能力，通過(guò)對(duì)可調(diào)參數(shù)的調(diào)節(jié)，提高路由效率，有效緩解網(wǎng)絡(luò)擁塞[3]。

1 新增社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化模型的構(gòu)建及仿真分析

1.1 網(wǎng)絡(luò)模型的構(gòu)建

Barabási和Albert建立的BA網(wǎng)絡(luò)模型中，節(jié)點(diǎn)的度具有冪律分布特性，但整個(gè)網(wǎng)絡(luò)的聚類(lèi)系數(shù)很低。現(xiàn)實(shí)生活中，網(wǎng)絡(luò)往往遵循高聚類(lèi)，且節(jié)點(diǎn)度為冪律分布。因此，建立一個(gè)高聚類(lèi)無(wú)標(biāo)度的網(wǎng)絡(luò)模型十分必要。相比其他網(wǎng)絡(luò)模型，BA網(wǎng)絡(luò)具有網(wǎng)絡(luò)規(guī)?？稍鲩L(zhǎng)和節(jié)點(diǎn)加入優(yōu)先選擇連接的優(yōu)勢(shì)。但是，網(wǎng)絡(luò)模型的增長(zhǎng)僅僅考慮了單一新節(jié)點(diǎn)的加入。類(lèi)比于現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)，某個(gè)成員加入網(wǎng)絡(luò)后，往往意味著和該成員相關(guān)的一個(gè)社團(tuán)都成為網(wǎng)絡(luò)的一個(gè)新成員[4-5]，且BA網(wǎng)絡(luò)中新邊的產(chǎn)生只存在于新節(jié)點(diǎn)和舊節(jié)點(diǎn)之間。實(shí)際上，這種邊的演化機(jī)理也同時(shí)存在于舊節(jié)點(diǎn)之間?；谏鲜鏊枷耄岢龅母倪M(jìn)網(wǎng)絡(luò)模型在網(wǎng)絡(luò)特性方面增大了BA網(wǎng)絡(luò)的聚類(lèi)系數(shù)。在網(wǎng)絡(luò)增長(zhǎng)方式上，使加入網(wǎng)絡(luò)的節(jié)點(diǎn)情況從單一節(jié)點(diǎn)加入變?yōu)樯鐖F(tuán)結(jié)構(gòu)的加入，同時(shí)使網(wǎng)絡(luò)新邊增長(zhǎng)存在與新舊節(jié)點(diǎn)和舊節(jié)點(diǎn)之間[5]。

改進(jìn)模型演化機(jī)理如下。

（1）初始網(wǎng)絡(luò)：m0個(gè)完全連接的節(jié)點(diǎn)構(gòu)成網(wǎng)絡(luò)的初始模型。

（2）網(wǎng)絡(luò)增長(zhǎng)：按照概率p(∈[0,1])，網(wǎng)絡(luò)中加入一個(gè)含有n個(gè)節(jié)點(diǎn)的小型社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)和m條新邊。

隨機(jī)選擇新加入社團(tuán)結(jié)構(gòu)中一個(gè)節(jié)點(diǎn)v，并按照擇優(yōu)概率選擇網(wǎng)絡(luò)中一個(gè)舊節(jié)點(diǎn)與節(jié)點(diǎn)v相連，使新加入節(jié)點(diǎn)v與網(wǎng)絡(luò)中的舊節(jié)點(diǎn)之間具有一條邊。連接節(jié)點(diǎn)的選擇按照如下的擇優(yōu)概率進(jìn)行，即網(wǎng)絡(luò)中一個(gè)舊節(jié)點(diǎn)i被選擇的概率(ki)為[5-6]：

其中，ki為節(jié)點(diǎn)的度。這個(gè)擇優(yōu)概率選取的連接機(jī)制代表新節(jié)點(diǎn)的加入更傾向于與網(wǎng)絡(luò)中度較大的節(jié)點(diǎn)相連接。α為可調(diào)因子，其中α∈(0,1)。因?yàn)樗尤氲纳鐖F(tuán)結(jié)構(gòu)為全連接，所以當(dāng)社團(tuán)中一個(gè)節(jié)點(diǎn)被加入網(wǎng)絡(luò)后，其余的(n-1)個(gè)節(jié)點(diǎn)也同時(shí)被加入到網(wǎng)絡(luò)。

其余(m-1)條邊，以概率(ci)做三角形連接，1-(ci)做擇優(yōu)概率，其中：

（3）網(wǎng)絡(luò)內(nèi)部演化：按照概率1-p選擇網(wǎng)絡(luò)中現(xiàn)有的節(jié)點(diǎn)做網(wǎng)絡(luò)內(nèi)部演化。隨機(jī)選擇網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)i，以擇優(yōu)概率選擇節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j，其中連接概率按照如式（3）選擇：

其中，（N(i)為選中舊節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合），再以概率1-(ci)選擇節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)k與節(jié)點(diǎn)i做連接。

當(dāng)概率p=0時(shí)，網(wǎng)絡(luò)中無(wú)新社團(tuán)結(jié)構(gòu)的加入，沒(méi)有新節(jié)點(diǎn)增長(zhǎng)機(jī)制，網(wǎng)絡(luò)的增長(zhǎng)僅發(fā)生在舊節(jié)點(diǎn)之間，然后舊節(jié)點(diǎn)之間進(jìn)行內(nèi)部演化加邊。當(dāng)0＜p＜1時(shí)，每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中既可能有新社團(tuán)的加入，增加網(wǎng)絡(luò)的節(jié)點(diǎn)與邊，也有網(wǎng)絡(luò)的內(nèi)部演化加邊，即隨著p的增加，網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的增長(zhǎng)機(jī)制所占比重越來(lái)越大。當(dāng)概率p=1時(shí)，網(wǎng)絡(luò)中舊節(jié)點(diǎn)之間不進(jìn)行內(nèi)部演化加邊，每個(gè)時(shí)間步長(zhǎng)有一個(gè)新社團(tuán)加入網(wǎng)絡(luò)。然而，概率p=1的情況在現(xiàn)實(shí)網(wǎng)絡(luò)中通常不會(huì)出現(xiàn)[7]。

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

設(shè)定固定參數(shù)，網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)m0=4，每次新增社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)連接邊的數(shù)目m=3，可調(diào)因子α=1，網(wǎng)絡(luò)規(guī)模N=1 000。通過(guò)模擬實(shí)驗(yàn)研究選擇概率p對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)度分布的影響，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 p取不同值時(shí)，改進(jìn)模型的度分布

由圖1可知，改進(jìn)模型繼承了BA模型度分布遵循冪律分布的特點(diǎn)。由于選擇概率p的不同取值，冪律分布的指數(shù)可以進(jìn)行調(diào)節(jié)，打破了BA網(wǎng)絡(luò)中節(jié)點(diǎn)度分布冪律指數(shù)固定的限制。

設(shè)定固定參數(shù)，網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)m0=4，每次新增社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)連接邊的數(shù)目m=3，選擇概率p=0.4，網(wǎng)絡(luò)規(guī)模N=1 000。通過(guò)模擬實(shí)驗(yàn)研究概率α對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)度分布的影響，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 α取不同值時(shí)，改進(jìn)模型的度分布

由圖2可知，可調(diào)參數(shù)α取不同值時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)度分布始終服從冪律分布，且冪律指數(shù)由參數(shù)α可調(diào)，更靈活，更符合實(shí)際網(wǎng)絡(luò)。

設(shè)定固定參數(shù)，網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)m0=4，每次新增社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)連接邊的數(shù)目m=3，可調(diào)因子α=1，網(wǎng)絡(luò)規(guī)模N=1 000。通過(guò)模擬實(shí)驗(yàn)研究選擇概率p對(duì)聚類(lèi)系數(shù)的影響，實(shí)驗(yàn)結(jié)果如圖3所示。

改進(jìn)模型由于選擇概率p的不同取值，網(wǎng)絡(luò)聚類(lèi)系數(shù)也不同。由圖3可知，p=0.2時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)聚類(lèi)系數(shù)平均值約為0.45；p=0.4和p=0.8時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類(lèi)系數(shù)平均值約為0.49；而p=0.6時(shí)，網(wǎng)絡(luò)聚類(lèi)系數(shù)平均值最大，約為0.52。相比BA網(wǎng)絡(luò)無(wú)明顯聚類(lèi)效應(yīng)而言，改進(jìn)的網(wǎng)絡(luò)聚類(lèi)系數(shù)大大提高了。

可調(diào)參數(shù)α取不同值時(shí)，改進(jìn)模型的聚類(lèi)系數(shù)分布也不相同，如圖4所示。由圖4可知，α=0.1和α=0.5時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)聚類(lèi)系數(shù)平均值約為0.47；α=0.7時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類(lèi)系數(shù)平均值約為0.48；而α=0.3時(shí)，網(wǎng)絡(luò)聚類(lèi)系數(shù)平均值最大，約為0.51。相比BA網(wǎng)絡(luò)無(wú)明顯聚類(lèi)效應(yīng)而言，改進(jìn)的網(wǎng)絡(luò)聚類(lèi)系數(shù)被大大提高了。

圖3 p取不同值時(shí)，改進(jìn)模型的聚類(lèi)系數(shù)分布

圖4 α取不同值時(shí)，改進(jìn)模型的聚類(lèi)系數(shù)分布

綜合考慮，在構(gòu)建改進(jìn)BA網(wǎng)絡(luò)模型時(shí)，選擇概率p設(shè)定為0.6，可調(diào)參數(shù)α設(shè)定為0.3。這種情況下構(gòu)建的網(wǎng)絡(luò)模型，度分布保持冪律分布，且整個(gè)網(wǎng)絡(luò)的聚類(lèi)系數(shù)很高，符合現(xiàn)實(shí)網(wǎng)絡(luò)特性。本文研究的混合信息路由策略以此改進(jìn)模型為平臺(tái)。

2 基于混合信息的路由策略

為了使網(wǎng)絡(luò)模型更真實(shí)地反應(yīng)現(xiàn)實(shí)網(wǎng)絡(luò)，本文采用初始網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為5、網(wǎng)絡(luò)規(guī)模N=1 000的新增社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化模型為實(shí)驗(yàn)的基礎(chǔ)模型。

具體路由算法如下：

（1）在網(wǎng)絡(luò)中，每個(gè)時(shí)間步長(zhǎng)產(chǎn)生R個(gè)數(shù)據(jù)包。隨機(jī)選取數(shù)據(jù)包的起始節(jié)點(diǎn)和數(shù)據(jù)包最終需要到達(dá)的目的節(jié)點(diǎn)。起始節(jié)點(diǎn)和目的節(jié)點(diǎn)選定后則不更改，且兩個(gè)節(jié)點(diǎn)不能相同。網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)可以作為產(chǎn)生數(shù)據(jù)包的起始節(jié)點(diǎn)、接收數(shù)據(jù)包的目的節(jié)點(diǎn)，也可以作為傳遞數(shù)據(jù)包的中間節(jié)點(diǎn)[8]。類(lèi)比于現(xiàn)實(shí)生活的互聯(lián)網(wǎng)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)可以是產(chǎn)生或接收信息的服務(wù)器，又可以是傳遞信息的路由器。

（2）假設(shè)每個(gè)節(jié)點(diǎn)的傳遞能力為該節(jié)點(diǎn)的介數(shù)。實(shí)際網(wǎng)絡(luò)中，度越大的節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要，習(xí)慣上也把度較大的節(jié)點(diǎn)稱(chēng)作網(wǎng)絡(luò)中心節(jié)點(diǎn)。這樣的節(jié)點(diǎn)更有能力處理大量的信息包，因此很多現(xiàn)有的路由策略將節(jié)點(diǎn)的數(shù)據(jù)包傳遞能力設(shè)定為該節(jié)點(diǎn)的度，即在一個(gè)時(shí)間步內(nèi)能處理的數(shù)據(jù)包個(gè)數(shù)等于該節(jié)點(diǎn)度的大小，或?qū)⒐?jié)點(diǎn)傳遞信息包的能力正比于節(jié)點(diǎn)的度。理論上，路由策略的作用是緩解擁塞節(jié)點(diǎn)的負(fù)載，而網(wǎng)絡(luò)節(jié)點(diǎn)的介數(shù)才是用來(lái)表示網(wǎng)絡(luò)相對(duì)負(fù)載的，且介數(shù)比度更能精確反應(yīng)節(jié)點(diǎn)的中心特性[8-9]。因此，本文假設(shè)每個(gè)節(jié)點(diǎn)的傳輸能力為Oi（Oi為節(jié)點(diǎn)i的介數(shù)），即在一個(gè)時(shí)間步內(nèi)，節(jié)點(diǎn)處理的數(shù)據(jù)包個(gè)數(shù)等于該節(jié)點(diǎn)介數(shù)的大小。取消節(jié)點(diǎn)傳遞能力固定的限制，能更好地反映實(shí)際網(wǎng)絡(luò)的特征。

（3）遍歷當(dāng)前數(shù)據(jù)包所在節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，若目的節(jié)點(diǎn)存在于鄰居節(jié)點(diǎn)，則直接將數(shù)據(jù)包傳遞給目的節(jié)點(diǎn)；否則，以概率1-p選擇傳統(tǒng)最短路徑路由策略。以概率p做優(yōu)先選擇，擇優(yōu)概率為[10]：

以此概率傳遞給下一個(gè)節(jié)點(diǎn)。其中，α是一個(gè)可調(diào)的參數(shù)，Ni是結(jié)點(diǎn)i的排隊(duì)隊(duì)列長(zhǎng)度，Ni+1是為了保證鄰居節(jié)點(diǎn)中空閑節(jié)點(diǎn)被選中的概率不為0。

（4）本文的路由策略假設(shè)每一節(jié)點(diǎn)處排隊(duì)的數(shù)據(jù)包個(gè)數(shù)可以為無(wú)限個(gè)，排隊(duì)等候的數(shù)據(jù)包依次傳遞時(shí)需要遵從先進(jìn)先出（FIFO）的原則[11]，且任何節(jié)點(diǎn)只能被同一個(gè)數(shù)據(jù)包訪問(wèn)一次。

網(wǎng)絡(luò)性能可以通過(guò)利用整個(gè)網(wǎng)絡(luò)對(duì)信息包的處理和傳遞能力進(jìn)行衡量。為了更準(zhǔn)確地描述網(wǎng)絡(luò)狀

該算法中的有序參數(shù)η(R)為網(wǎng)絡(luò)中數(shù)據(jù)包總量的變化率，即在數(shù)據(jù)包生成率為R的情況下，每個(gè)時(shí)刻網(wǎng)絡(luò)中數(shù)據(jù)包總量的增長(zhǎng)速率，有時(shí)也用H(R)表示。O是網(wǎng)絡(luò)中節(jié)點(diǎn)傳遞能力的平均值。其中，ΔW=W(t+Δt)-W(t)，W(t)表示t時(shí)刻網(wǎng)絡(luò)中數(shù)據(jù)包的總個(gè)數(shù)，ΔW則表示在Δt時(shí)間內(nèi)網(wǎng)絡(luò)中數(shù)據(jù)包個(gè)數(shù)的改變量。當(dāng)R＜RC時(shí)，數(shù)據(jù)包的產(chǎn)生率小于臨界負(fù)載量，η(R)大約等于0，t時(shí)間長(zhǎng)度內(nèi)網(wǎng)絡(luò)中數(shù)據(jù)包個(gè)數(shù)無(wú)變化，產(chǎn)生與到達(dá)的數(shù)據(jù)包個(gè)數(shù)相互抵消，使網(wǎng)絡(luò)中每個(gè)時(shí)間步長(zhǎng)穩(wěn)定的數(shù)據(jù)包個(gè)數(shù)低于臨界負(fù)載量，網(wǎng)絡(luò)處于無(wú)擁塞狀態(tài)；當(dāng)R＞RC時(shí)，數(shù)據(jù)包產(chǎn)生率大于負(fù)載量，η(R)＞0，有序參數(shù)為一個(gè)大于0的常數(shù)，t時(shí)間長(zhǎng)度內(nèi)產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)遠(yuǎn)大于到達(dá)的數(shù)據(jù)包個(gè)數(shù)，網(wǎng)絡(luò)中的數(shù)據(jù)包總量累計(jì)增加，促使網(wǎng)絡(luò)變?yōu)閾砣麪顟B(tài)。所以，η從0到大于0常數(shù)的突變，可以得出網(wǎng)絡(luò)從自由狀態(tài)轉(zhuǎn)變?yōu)閾砣麪顟B(tài)[13]。態(tài)變化，設(shè)定每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中隨機(jī)產(chǎn)生R個(gè)數(shù)據(jù)包（即數(shù)據(jù)包的生產(chǎn)率為R，有時(shí)也用來(lái)表示），臨界信息負(fù)載量RC。RC是整個(gè)網(wǎng)絡(luò)從自由態(tài)到擁塞態(tài)的變化的臨界值。當(dāng)R＜RC時(shí)，每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中新增的數(shù)據(jù)包個(gè)數(shù)小于網(wǎng)絡(luò)的臨界負(fù)載量，網(wǎng)絡(luò)狀態(tài)為自由通暢狀態(tài)；當(dāng)R=RC時(shí)，每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)恰好等于網(wǎng)絡(luò)的臨界負(fù)載量，網(wǎng)絡(luò)通信能力達(dá)到臨界值，為最大通信能力；當(dāng)R＞RC時(shí)，每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)大于網(wǎng)絡(luò)的臨界負(fù)載量，網(wǎng)絡(luò)狀態(tài)為擁塞狀態(tài)。所以，RC為使得網(wǎng)絡(luò)處于無(wú)擁塞狀態(tài)時(shí)的最大值，即網(wǎng)絡(luò)傳輸容量。同時(shí)，本文也利用參數(shù)η(R)來(lái)描述該網(wǎng)絡(luò)狀態(tài)的變化[12]：

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

3.1 路由效率分析

優(yōu)先選擇概率中，α為可調(diào)參數(shù)。不同的搜索策略值α下，網(wǎng)絡(luò)的通信能力不同。圖5表明，不同α下，每個(gè)時(shí)間步長(zhǎng)，網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)對(duì)η的影響?？梢钥闯觯總€(gè)時(shí)間步長(zhǎng)，產(chǎn)生數(shù)據(jù)包的個(gè)數(shù)小于臨界負(fù)載量。R＜RC時(shí)，η為0；當(dāng)新增數(shù)據(jù)包個(gè)數(shù)超過(guò)臨界負(fù)載量R＞RC時(shí)，η驟變成大于0的常數(shù)；R=RC時(shí)，網(wǎng)絡(luò)通信量達(dá)到臨界值?？梢?jiàn)，α取不同值時(shí)，臨界負(fù)載量RC不同，即網(wǎng)絡(luò)的最大通信量不同。

圖5 不同α?xí)r，η的參數(shù)統(tǒng)計(jì)

對(duì)α取不同值時(shí)的網(wǎng)絡(luò)臨界負(fù)載量做統(tǒng)計(jì)，如圖6所示。當(dāng)α=0.2時(shí)，網(wǎng)絡(luò)臨界負(fù)載量達(dá)到最大值，RC=250。所以，本實(shí)驗(yàn)中α的值取0.2。

圖6 不同α?xí)r，RC的參數(shù)統(tǒng)計(jì)

改進(jìn)的路由策略規(guī)定，路由選擇時(shí)，以概率1-p選擇傳統(tǒng)最短路徑路由策略，并以概率p做優(yōu)先概率選擇。圖7為固定參數(shù)α=0.2，p取不同值時(shí)，網(wǎng)絡(luò)產(chǎn)生數(shù)據(jù)包個(gè)數(shù)對(duì)η的影響。同樣，由圖7可知，每個(gè)時(shí)間步長(zhǎng)，產(chǎn)生數(shù)據(jù)包的個(gè)數(shù)小于臨界負(fù)載量時(shí)，η為0；當(dāng)產(chǎn)生數(shù)據(jù)包個(gè)數(shù)超過(guò)臨界負(fù)載量RC時(shí)，η驟變?yōu)榇笥?的常數(shù)。

對(duì)p取不同值時(shí)的網(wǎng)絡(luò)臨界負(fù)載量RC做統(tǒng)計(jì)，由圖8可知，p取0.2時(shí)，路由效率最高，臨界負(fù)載量RC=300，則實(shí)驗(yàn)設(shè)p=0.2。

3.2 網(wǎng)絡(luò)自由態(tài)分析

網(wǎng)絡(luò)的自由通暢狀態(tài)是指，網(wǎng)絡(luò)中每個(gè)時(shí)間步長(zhǎng)產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)能夠和網(wǎng)絡(luò)中被移除的數(shù)據(jù)包個(gè)數(shù)相互抵消，使網(wǎng)絡(luò)中每個(gè)時(shí)間步長(zhǎng)穩(wěn)定的數(shù)據(jù)包個(gè)數(shù)低于或等于網(wǎng)絡(luò)臨界負(fù)載量，網(wǎng)絡(luò)即處于通暢狀態(tài)[14]。設(shè)定R=40，R小于不同α取值時(shí)RC的平均值。由圖9可知，初始時(shí)間段內(nèi)，數(shù)據(jù)包個(gè)數(shù)累計(jì)增長(zhǎng)；經(jīng)過(guò)一段時(shí)間的積累，數(shù)據(jù)包的個(gè)數(shù)達(dá)到穩(wěn)定，即產(chǎn)生和移除的數(shù)據(jù)包個(gè)數(shù)達(dá)到平衡，網(wǎng)絡(luò)處于通暢穩(wěn)定狀態(tài)，即自由態(tài)?？梢缘贸觯?0.2時(shí)，隨時(shí)間的增加，網(wǎng)絡(luò)中數(shù)據(jù)包總數(shù)穩(wěn)定在200左右，效率最佳。從圖10也可得出，α=0.2時(shí)，η最穩(wěn)定，為最趨近于0的常數(shù)。

圖7 不同p時(shí)，η的參數(shù)統(tǒng)計(jì)

圖8 不同p時(shí)，RC的參數(shù)統(tǒng)計(jì)

3.3 網(wǎng)絡(luò)擁塞態(tài)分析

網(wǎng)絡(luò)的擁塞狀態(tài)是指，每個(gè)時(shí)間步長(zhǎng)產(chǎn)生的數(shù)據(jù)包個(gè)數(shù)與網(wǎng)絡(luò)中被移除的數(shù)據(jù)包個(gè)數(shù)無(wú)法完全相互抵消，導(dǎo)致網(wǎng)絡(luò)中總體數(shù)據(jù)包個(gè)數(shù)持續(xù)累計(jì)，最終穩(wěn)定的數(shù)據(jù)包個(gè)數(shù)高于臨界負(fù)載量，導(dǎo)致網(wǎng)絡(luò)擁塞。設(shè)定R=500，R大于不同α取值時(shí)RC的平均值。由圖11可知，隨著時(shí)間的增加，網(wǎng)絡(luò)中數(shù)據(jù)包的個(gè)數(shù)累積增長(zhǎng)，無(wú)趨于穩(wěn)定狀態(tài)的趨勢(shì)，導(dǎo)致大量數(shù)據(jù)包滯留于網(wǎng)絡(luò)，使得網(wǎng)絡(luò)處于擁塞狀態(tài)甚至崩潰。圖12表明，擁塞狀態(tài)下，η一直為大于0的常數(shù)。

圖9 R＜RC時(shí)，不同α下網(wǎng)絡(luò)數(shù)據(jù)包變化情況

圖10 R＜RC時(shí)，不同α下η變化情況

圖11 R＞RC時(shí)，不同α下網(wǎng)絡(luò)數(shù)據(jù)包變化情況

圖12 R＞RC時(shí)，不同α下η變化情況

4 結(jié) 語(yǔ)

針對(duì)現(xiàn)實(shí)世界中很多大規(guī)模的網(wǎng)絡(luò)都同時(shí)具有小世界與無(wú)標(biāo)度網(wǎng)絡(luò)特性，在傳統(tǒng)BA網(wǎng)絡(luò)的演化機(jī)制中加入“內(nèi)部演化”“新增社團(tuán)”演化機(jī)制，建立改進(jìn)的高聚類(lèi)無(wú)標(biāo)度網(wǎng)絡(luò)模型，同時(shí)在新建模型的基礎(chǔ)上，提出了一種混合信息路由策略，將節(jié)點(diǎn)的傳遞能力設(shè)定為節(jié)點(diǎn)的介數(shù)而不是一個(gè)固定值。路由選擇時(shí)，以概率1-p選擇傳統(tǒng)最短路徑路由策略，以概率p做優(yōu)先選擇，并提出了優(yōu)先選擇概率模型。仿真實(shí)驗(yàn)表明，混合路由策略可以顯著提高網(wǎng)絡(luò)路由的效率。實(shí)驗(yàn)中，通過(guò)對(duì)選擇概率

p和可調(diào)參數(shù)α的調(diào)節(jié)得出最優(yōu)組合，即p=0.2，

α=0.2時(shí)，在合理設(shè)置數(shù)據(jù)包產(chǎn)生率的情況下，可以有效緩解網(wǎng)絡(luò)的擁塞。

參考文獻(xiàn)：

[1] 王翠君,王紅.復(fù)雜網(wǎng)絡(luò)的研究進(jìn)展綜述[J].科技信息 ,2007,31(31)：417-418.WANG Cui-jun,WANG Hong.Summary of Research Progress on Complex Networks[J].Science,2007,31(31)：417-418.

[2] 徐玉珠,張達(dá)敏,曾成等.改進(jìn)HK網(wǎng)絡(luò)演化模型的研究 [J].電子科技 ,2016,29(03)：106-109.XU Yu-zhu,ZHANG Da-min,ZENG Cheng,et al.Research and Modeling of the Improved HK Network Model[J].Electronic Science and Technology,2016,29(03)：106-109.

[3] 劉倩星,張達(dá)敏.基于混合信息的復(fù)雜網(wǎng)絡(luò)路由策略研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(03)：880-884.LIU Qian-xing,ZHANG Da-min.Routing Strategy Research Based on Mixed Information in Complex Networks[J].Computer Engineering and Design,2012,33(03)：880-884.

[4] 王丹,金小崢.可調(diào)聚類(lèi)系數(shù)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)建模及其擁塞問(wèn)題研究[J].物理學(xué)報(bào),2012,61(22)：543-551.WANG Dan,JIN Xiao-zheng.On Weightd Scale-free Network Model with Tunable Clustering and Congesstion[J].Acta Physica Sinica,2012,61(22)：543-551.

[5] 王丹,郝彬彬.一類(lèi)高聚類(lèi)系數(shù)的加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)及其同步能力的分析[J].物理學(xué)報(bào),2013,62(22)：1-8.WANG Dan,HAO Bin-bin.A Weighted Scale-free Network Model with High Clustering and Its Synchronizability[J].Acta Physica Sinica,2013,62(22)：1-8.

[6] 濮存來(lái),裴文江.一種應(yīng)用于含權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)的全局路由算法[J].物理學(xué)報(bào),2010,59(06)：3841-3844.PU Cun-lai,PEI Wen-jiang.A Global Routing Method for Weighted Scale-free Networks[J].Acta Physica Sinica,2010,59(06)：3841-3844.

[7] 蔣忠元.復(fù)雜網(wǎng)絡(luò)傳輸容量分析與優(yōu)化策略研究[D].北京：北京交通大學(xué),2013.JIANG Zhong-yuan.Analysis and Optimization Strategies of Traffic Capacity of Complexnetworks[D].Beijing：Beijing Jiaotong University,2013.

[8] 潘灶烽,汪小帆.一種可大范圍調(diào)節(jié)聚類(lèi)系數(shù)的加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型[J].物理學(xué)報(bào),2006,55(08)：4058-4064.PAN Zao-feng,WANG Xiao-fan.A Weighted Scale-free Network Model with Large-scale Tunable Clustering [J].Acta Physica Sinica,2006,55(08)：4058-4064.

[9] 李穩(wěn)國(guó),王力虎,陳明芳.HK網(wǎng)絡(luò)演化模型的研究和改進(jìn)[J].計(jì)算機(jī)工程,2009,35(03)：121-125.LI Wen-guo,WANG Li-hu,CHENG Ming-fang.Study and Improvement on Growing HK Network Model[J].Computer Engineering,2009,35(03)：121-125.

[10] 劉建香.復(fù)雜網(wǎng)絡(luò)及其在國(guó)內(nèi)研究進(jìn)展的綜述[J].系統(tǒng)科學(xué)學(xué)報(bào) ,2009,17(4)：31-37.LIU Jian-xiang.Complex Network and Review of Domestic Research[J].Chinese Journal of Systems Science,2009,17(04)：31-37.

[11] 胡海波,王科,徐玲等.基于復(fù)雜網(wǎng)絡(luò)理論的在線社會(huì)網(wǎng)絡(luò)分析[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2008,5(02)：1-14.HU Hai-bo,WANG Ke,XU Ling,et al.Analysis of Online Social Networks Based on Complex Network Theory[J].Complex Systems and Complexity Science,2008,5(02)：1-14.

[12] 王丹,井元偉,郝彬彬.擴(kuò)展HK網(wǎng)絡(luò)結(jié)構(gòu)與同步能力的研究[J].物理學(xué)報(bào),2012,61(22)：1-8.WANG Dan,JING Yuan-wei,HAO Bin-bin.Extended Holme-Kim network model and synchronizability[J].Acta Physica Sinica,2012,61(22)：1-8.

[13] Galstyan A,Musoyan V,Cohen P.Maximizing Influence Propagation in Networks with Community Structure[J].Physical Review E,2009,79(345)：314-319.

[14] Barabási A L,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286(286)：509-512.