于灝 周玉成 井元偉 徐佳鶴 張星梅 馬妍3)

1)(東北大學(xué)信息科學(xué)與工程學(xué)院,沈陽 110004)

2)(中國(guó)林業(yè)科學(xué)研究院木材工業(yè)研究所,北京 100091)

3)(青島理工大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院,青島 266520)

(2012年7月17日收到;2012年12月23日收到修改稿)

1 引言

隨著小世界[1]和無標(biāo)度[2]等重要的網(wǎng)絡(luò)特性在20世紀(jì)末被陸續(xù)發(fā)現(xiàn),越來越多的科研工作者開始通過復(fù)雜網(wǎng)絡(luò)的視角來審視和研究自然和人類社會(huì)當(dāng)中的復(fù)雜系統(tǒng),投身于復(fù)雜網(wǎng)絡(luò)的研究中[3-8].復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)流研究是其中的重點(diǎn)研究方向之一.伴隨著網(wǎng)絡(luò)數(shù)據(jù)流量的不斷增加,發(fā)生傳輸擁塞是不可避免的.所以,盡可能地提升擁塞發(fā)生臨界的網(wǎng)絡(luò)負(fù)載能力便成了要解決的核心問題.許多科研工作者此前做出了大量的研究,取得了豐碩的成果.文獻(xiàn)[9]提供了一個(gè)狀態(tài)參量,為分析網(wǎng)絡(luò)自由狀態(tài)向擁塞狀態(tài)轉(zhuǎn)變提供了完美的理論描述方式;文獻(xiàn)[10—16]提出了多個(gè)能夠提高網(wǎng)絡(luò)負(fù)載的路由策略;文獻(xiàn)[17]發(fā)現(xiàn)了網(wǎng)絡(luò)數(shù)據(jù)流負(fù)載與網(wǎng)絡(luò)介數(shù)的關(guān)系,發(fā)現(xiàn)網(wǎng)絡(luò)負(fù)載與網(wǎng)絡(luò)節(jié)點(diǎn)的最大介數(shù)成反比;文獻(xiàn)[18,19]提出了通過刪除網(wǎng)絡(luò)上的一些邊,降低網(wǎng)絡(luò)節(jié)點(diǎn)最大介數(shù),能提高網(wǎng)絡(luò)負(fù)載能力的‘刪邊擴(kuò)容’方法,文獻(xiàn)[20,21]分析了勻質(zhì)化的帶寬分配下的網(wǎng)絡(luò)負(fù)載能力變化.文獻(xiàn)[22]提出了一種帶寬分配方案,針對(duì)其文中的路由策略,對(duì)相對(duì)重要的連接邊有所偏重地分配帶寬,達(dá)到了提升網(wǎng)絡(luò)性能的目的.

通常對(duì)網(wǎng)絡(luò)數(shù)據(jù)流負(fù)載提升問題的研究主要從兩方面入手：一是尋求更適合數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),二是找尋更高效的路由策略.先前的許多研究中很少把連接邊帶寬約束加以考慮,在節(jié)點(diǎn)處理能力強(qiáng)的網(wǎng)絡(luò)中,連接邊的傳輸容量限制往往成為導(dǎo)致?lián)砣l(fā)生的重要原因.科學(xué)研究和生活經(jīng)驗(yàn)證明,網(wǎng)絡(luò)中連接邊的帶寬約束往往作為制約網(wǎng)絡(luò)數(shù)據(jù)流通的一個(gè)瓶頸,既然多數(shù)的現(xiàn)實(shí)問題不能回避和忽略帶寬約束,那么把合理有效的帶寬分配作為充分利用和發(fā)揮網(wǎng)絡(luò)資源優(yōu)勢(shì),提高網(wǎng)絡(luò)數(shù)據(jù)流通效率的重要武器將更具有現(xiàn)實(shí)意義.

因此,本文在流量模型中加入了連接帶寬約束機(jī)制,從制約數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)關(guān)鍵拓?fù)涮匦猿霭l(fā),提出了一種異質(zhì)化網(wǎng)絡(luò)帶寬分配方案;并結(jié)合路由選擇策略,運(yùn)用連接帶寬的分配來調(diào)節(jié)網(wǎng)絡(luò)中數(shù)據(jù)流的流向,從而實(shí)現(xiàn)緩解網(wǎng)絡(luò)擁塞發(fā)生,提升網(wǎng)絡(luò)的負(fù)載能力;同時(shí),定性分析了流量變化的過程及其原因.本文第二部分介紹了網(wǎng)絡(luò)模型和數(shù)據(jù)流模型;第三部分介紹本文提出的帶寬分配方案;第四部分模擬并分析應(yīng)用帶寬方案的網(wǎng)絡(luò)數(shù)據(jù)流,第五部分是結(jié)論.

2 網(wǎng)絡(luò)模型與數(shù)據(jù)流量模型

2.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

2.1.1 WS小世界網(wǎng)絡(luò)

作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重大發(fā)現(xiàn)——小世界現(xiàn)象,反映了許多現(xiàn)實(shí)網(wǎng)絡(luò)中所具有的大的聚類系數(shù)和小的平均距離的特性.為了構(gòu)建能反映出這種特性的網(wǎng)絡(luò),Watts和Strogatz[1]于1998年提出了小世界網(wǎng)絡(luò)模型,稱為WS小世界模型.該模型可以看作是從規(guī)則網(wǎng)絡(luò)向隨機(jī)網(wǎng)絡(luò)的過渡過程,其構(gòu)造算法如下：給定含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò),其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連,以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每條邊.其中規(guī)定,任意兩個(gè)不同的節(jié)點(diǎn)之間至多只能連一條邊,并且每一個(gè)節(jié)點(diǎn)都不能有邊與自身相連.

在WS模型中,p=0對(duì)應(yīng)于完全規(guī)則網(wǎng)絡(luò),p=1則對(duì)應(yīng)于完全隨機(jī)網(wǎng)絡(luò),通過調(diào)節(jié)p值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過渡[6].

2.1.2 BA無標(biāo)度網(wǎng)絡(luò)

近年在復(fù)雜網(wǎng)絡(luò)研究上的另一重大發(fā)現(xiàn)就是許多復(fù)雜網(wǎng)絡(luò),包括Internet,WWW以及新陳代謝網(wǎng)絡(luò)等的連接度分布函數(shù)具有冪律形式.由于這類網(wǎng)絡(luò)節(jié)點(diǎn)的連接度沒有明顯的特征長(zhǎng)度,故稱為無標(biāo)度網(wǎng)絡(luò).為了解釋冪律分布的產(chǎn)生機(jī)理,Baraba′si和Albert[2]提出了一個(gè)無標(biāo)度網(wǎng)絡(luò)模型,被稱為BA無標(biāo)度網(wǎng)絡(luò)模型.BA模型包含著兩個(gè)主要特性：1)增長(zhǎng)(growth)特性,即網(wǎng)絡(luò)的規(guī)模是不斷擴(kuò)大的;2)優(yōu)先連接(preferential attachment)特性,即新的節(jié)點(diǎn)更傾向于與那些具有較高連接度的節(jié)點(diǎn)相連接,這種現(xiàn)象也稱為“富者更富(rich get richer)”或“馬太效應(yīng)(matthew effect)”特性.BA網(wǎng)絡(luò)模型構(gòu)建如下：

1)初始網(wǎng)絡(luò),具有m0個(gè)節(jié)點(diǎn);

2)網(wǎng)絡(luò)生長(zhǎng)過程,每一步加入一個(gè)節(jié)點(diǎn)v和m條邊(m≤m0);

2.2 數(shù)據(jù)流量模型

本文采用加入連接邊傳輸容量限制(帶寬約束)的網(wǎng)絡(luò)數(shù)據(jù)流量模型,具體描述如下.

把N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)看作主機(jī)和路由器的結(jié)合體,同時(shí)具有產(chǎn)生、轉(zhuǎn)發(fā)、接收數(shù)據(jù)包的能力;每個(gè)節(jié)點(diǎn)i的數(shù)據(jù)包處理能力為Ci,即每單位時(shí)間步節(jié)點(diǎn)i最多可以處理Ci個(gè)數(shù)據(jù)包.為簡(jiǎn)單起見,定義每個(gè)節(jié)點(diǎn)的數(shù)據(jù)包處理能力Ci都相同,且為常數(shù).節(jié)點(diǎn)擁有無限長(zhǎng)的緩沖隊(duì)列,新加入的數(shù)據(jù)包放置在隊(duì)列的尾部,并按照“先入先出”(FIFO)原則處理;新產(chǎn)生的數(shù)據(jù)包選擇源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)是隨機(jī)的;單位時(shí)間步,整個(gè)網(wǎng)絡(luò)中新數(shù)據(jù)包的產(chǎn)生率為R;網(wǎng)絡(luò)擁塞僅發(fā)生在節(jié)點(diǎn)端.

此外,每條連接邊傳遞能力定義為帶寬B,即單位時(shí)間步每條邊上單向最多可以有B個(gè)數(shù)據(jù)包在傳遞,且一條邊上同時(shí)有相向傳遞數(shù)據(jù)包時(shí)互不影響.如果帶寬使用飽和,那么數(shù)據(jù)包仍被儲(chǔ)存在發(fā)包節(jié)點(diǎn)的緩沖隊(duì)列當(dāng)中.抵達(dá)目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包將立刻從網(wǎng)絡(luò)中去除.

網(wǎng)絡(luò)上的數(shù)據(jù)包流量可以看作兩部分,一部分由新流入網(wǎng)絡(luò)中的數(shù)據(jù)包構(gòu)成,另一部分則是到達(dá)目的地從網(wǎng)絡(luò)中消失的流出數(shù)據(jù)包構(gòu)成.當(dāng)兩者流量平衡時(shí)數(shù)據(jù)流處于自由流狀態(tài),當(dāng)前者大于后者時(shí)數(shù)據(jù)包開始在網(wǎng)絡(luò)中累積,達(dá)到一定的累積程度時(shí)網(wǎng)絡(luò)擁塞開始發(fā)生.為了清晰地描述網(wǎng)絡(luò)中的自由流狀態(tài)向擁塞狀態(tài)的相變過程,這里引入一個(gè)相變參量η[9]：

其中η(R)是R的函數(shù),〈ΔW〉是相鄰時(shí)刻網(wǎng)絡(luò)中總數(shù)據(jù)包的平均增加量.當(dāng)R＜Rc時(shí),網(wǎng)絡(luò)中流入和流出的數(shù)據(jù)包能夠平衡,〈ΔW〉≈0,此時(shí)η≈0,網(wǎng)絡(luò)處于自由流狀態(tài);當(dāng)R＞Rc時(shí),〈ΔW〉隨時(shí)間的增長(zhǎng)逐漸增加,數(shù)據(jù)包開始在網(wǎng)絡(luò)中累積,此時(shí)η＞0并持續(xù)上升,數(shù)據(jù)流進(jìn)入擁塞狀態(tài),并且擁塞隨η值越大,越顯明顯.因此,擁塞轉(zhuǎn)變發(fā)生在R=Rc時(shí),Rc是使網(wǎng)絡(luò)的自由流狀態(tài)向擁塞狀態(tài)相變的臨界值,標(biāo)志此時(shí)網(wǎng)絡(luò)達(dá)到了最大的負(fù)載能力,也因此把R作為網(wǎng)絡(luò)負(fù)載的標(biāo)志,本文把Rc作為網(wǎng)絡(luò)最大負(fù)載能力.

路由選擇策略：采用一種全局信息和局部信息相結(jié)合的具有擁塞感知能力的路由算法.假設(shè)數(shù)據(jù)包從源節(jié)點(diǎn)s傳遞到目標(biāo)節(jié)點(diǎn)t.首先,對(duì)節(jié)點(diǎn)鄰居節(jié)點(diǎn)執(zhí)行局域搜索.如果發(fā)現(xiàn)了目標(biāo)節(jié)點(diǎn),則數(shù)據(jù)包被直接送達(dá)目的地,否則,就按照如下策略尋找下一投遞節(jié)點(diǎn).

首先,計(jì)算節(jié)點(diǎn)s的所有鄰居節(jié)點(diǎn)的權(quán)值ωi.對(duì)于鄰居節(jié)點(diǎn)i來說,權(quán)值ωi通過如下表達(dá)式進(jìn)行計(jì)算：

其中,Li→t是節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)t的最短路徑長(zhǎng)度,Qi是節(jié)點(diǎn)i當(dāng)前所存儲(chǔ)待處理的數(shù)據(jù)包個(gè)數(shù),相當(dāng)于路由器的緩沖隊(duì)列長(zhǎng)度,α是一個(gè)可以調(diào)節(jié)的參數(shù),其范圍位于0和1之間.當(dāng)節(jié)點(diǎn)i發(fā)生擁塞時(shí),Qi的值會(huì)非常大.

然后,選取權(quán)值最小的節(jié)點(diǎn)作為下一個(gè)路由節(jié)點(diǎn).如果權(quán)值最小的節(jié)點(diǎn)有多個(gè),那么隨機(jī)選取其中一個(gè).

依照上述過程直到找到目標(biāo)節(jié)點(diǎn)t.

當(dāng)參數(shù)α=1時(shí),或節(jié)點(diǎn)沒有累積數(shù)據(jù)包時(shí),該算法則退化為最短路徑路由算法(SPR),當(dāng)α向0靠近說明路由線路在遠(yuǎn)離最短路徑.

3 帶寬分配方案

介數(shù)(betweenness centrality or betweenness)代表了網(wǎng)絡(luò)經(jīng)過節(jié)點(diǎn)(邊)的最短路徑的數(shù)目,如果節(jié)點(diǎn)(邊)介數(shù)較高就說明通過該節(jié)點(diǎn)(邊)的最短路徑較多,所以經(jīng)過該節(jié)點(diǎn)(邊)到達(dá)其他節(jié)點(diǎn)(邊)的平均路徑長(zhǎng)度也就較短.通常一對(duì)節(jié)點(diǎn)之間進(jìn)行傳遞,經(jīng)過最短路徑無疑會(huì)使傳遞的成本最低.但在多對(duì)節(jié)點(diǎn)同時(shí)發(fā)生傳遞時(shí),就會(huì)使經(jīng)過最短路徑數(shù)目多的高介數(shù)節(jié)點(diǎn)負(fù)擔(dān)加重,產(chǎn)生擁堵的概率加大.

網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)對(duì)負(fù)載的影響起到至關(guān)重要的作用[17],存在如下關(guān)系：

即網(wǎng)絡(luò)最大負(fù)載能力Rc與網(wǎng)絡(luò)最大節(jié)點(diǎn)介數(shù)g?成反比.

理論上改變網(wǎng)絡(luò)結(jié)構(gòu),降低網(wǎng)絡(luò)節(jié)點(diǎn)的最大介數(shù)能夠提升網(wǎng)絡(luò)的負(fù)載能力.為了不破壞網(wǎng)絡(luò)現(xiàn)有結(jié)構(gòu),本文提出一個(gè)帶寬分配方案來降低高介數(shù)節(jié)點(diǎn)負(fù)載,提升網(wǎng)絡(luò)整體負(fù)載能力,可以看作改變網(wǎng)絡(luò)結(jié)構(gòu)提升負(fù)載的等效方法.

3.1 異質(zhì)化帶寬分配方案

網(wǎng)絡(luò)中的邊被劃分成“受控邊”和“非受控邊”兩部分,受控邊的帶寬為b1,非受控邊的帶寬為b2.這里,在考慮連接邊帶寬約束的網(wǎng)絡(luò)上,把整個(gè)網(wǎng)絡(luò)帶寬資源作為一個(gè)固定的總量來看待.

為了確定“受控邊”,首先計(jì)算每個(gè)節(jié)點(diǎn)的介數(shù),并為整個(gè)網(wǎng)絡(luò)勻質(zhì)化分配帶寬——每條邊分配帶寬b0,網(wǎng)絡(luò)上的帶寬總量為B=b0M,M是網(wǎng)絡(luò)總的邊數(shù);然后,給每條邊賦權(quán)σij=gi·gj;其中g(shù)i和gj分別是一條邊兩端節(jié)點(diǎn)的介數(shù),按權(quán)值從大到小的順序排列,將σij最大的那條邊刪除,在刪除邊的過程中,如權(quán)值最大的邊有多條,則隨機(jī)選取一條;同時(shí),標(biāo)記刪去的邊,作為“受控邊”放入一個(gè)“受控邊”表中;重復(fù)上述過程直到達(dá)到設(shè)定的“受控邊”比例上限 fce或網(wǎng)絡(luò)連通性遭到破壞停止,“受控邊”表中標(biāo)記的刪除邊按刪除的先后順序排列.這樣就確定了網(wǎng)絡(luò)中的“受控邊”.

為“受控邊”表中的邊分配帶寬b1,且b1?b0,即：?jiǎn)挝粫r(shí)間步只允許相對(duì)較少數(shù)據(jù)包通過該邊.這樣,保證了網(wǎng)絡(luò)的連通性,同時(shí)大大降低了這些“受控邊”的數(shù)據(jù)包傳遞能力.并為非受控邊分配帶寬當(dāng) fce=0時(shí),網(wǎng)絡(luò)帶寬為勻質(zhì)化分配b1=b2=b0.

4 仿真與分析

分別選取BA無標(biāo)度網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)作為網(wǎng)絡(luò)拓?fù)淦脚_(tái).網(wǎng)絡(luò)規(guī)模都為1000個(gè)節(jié)點(diǎn),且為無向網(wǎng)絡(luò).BA網(wǎng)絡(luò)模型初始節(jié)點(diǎn)互不相連m0=m=3,〈K〉=6;WS網(wǎng)絡(luò)模型隨機(jī)重連概率p=0.3,〈K〉=4.節(jié)點(diǎn)節(jié)點(diǎn)數(shù)據(jù)包處理能力都為100,每條連接邊的初始帶寬為b0=10,受控邊帶寬b1=1.在流量模型中,運(yùn)行5000時(shí)間步后認(rèn)為網(wǎng)絡(luò)流量達(dá)到穩(wěn)定,取后1000步的平均值來計(jì)算.仿真結(jié)果均取20次獨(dú)立實(shí)驗(yàn)的平均值.

圖1反映了在受控邊比例變化時(shí)BA網(wǎng)絡(luò)模型中網(wǎng)絡(luò)負(fù)載能力的變化.可以看出受控邊比例 fce適度增加時(shí),網(wǎng)絡(luò)的負(fù)載能力有不同程度的增加,當(dāng)受控邊比例 fce加大到一定程度時(shí),網(wǎng)絡(luò)中的負(fù)載能力開始下降,說明了受控邊比例在網(wǎng)絡(luò)中存在最優(yōu)值.α值為達(dá)到Rc時(shí)的值,可以看出,通過異質(zhì)化地分配帶寬,使得數(shù)據(jù)流向得以改變(α值改變反映了網(wǎng)絡(luò)數(shù)據(jù)流向的變化,而α具體值屬于路由算法的性質(zhì),不是本文重點(diǎn),故在后面不再討論).在圖1仿真中BA網(wǎng)絡(luò)的最優(yōu)受控邊比例 fce出現(xiàn)在0.45附近.

圖1 BA網(wǎng)絡(luò)N=1000,m0=m=3,在不同受控邊比例時(shí)η與R變化對(duì)比

在我們的流量模型中,Soiut不僅受到節(jié)點(diǎn)i處理數(shù)據(jù)包能力Ci的限制,還要受到節(jié)點(diǎn)i連接邊帶寬總量Bi的影響,即Siout=min(Ci,Bi).因此,盡量做到Ci和Bi接近是既不浪費(fèi)資源又能提升負(fù)載性能的理想狀態(tài).在我們的仿真中,BA網(wǎng)絡(luò)的節(jié)點(diǎn)度最大值為102,fce=0時(shí)節(jié)點(diǎn)i連接邊帶寬Bi=b0Ki.此時(shí),最大度節(jié)點(diǎn)總的連接邊帶寬Bi達(dá)到1020,而節(jié)點(diǎn)的處理能力是100,Ci?Bi,因此在高度數(shù)節(jié)點(diǎn)存在著帶寬資源的浪費(fèi).BA無標(biāo)度網(wǎng)絡(luò)中存在少數(shù)中心節(jié)點(diǎn),擁有非常高的度,而大部分的一般節(jié)點(diǎn)度都較小,小于網(wǎng)絡(luò)節(jié)點(diǎn)度的平均值.在本文的仿真選取的BA網(wǎng)絡(luò)中,一般節(jié)點(diǎn)的連接邊帶寬要小于60,Ci＞Bi,這些節(jié)點(diǎn)的Siout受限于帶寬,提升這些節(jié)點(diǎn)的連接邊帶寬格外重要.

從圖2中可以看出,BA無標(biāo)度網(wǎng)絡(luò)中,度數(shù)大的節(jié)點(diǎn)往往也是介數(shù)高的節(jié)點(diǎn),節(jié)點(diǎn)的度與介數(shù)之間具有正相關(guān)性,且仿真中的BA網(wǎng)絡(luò)Pearson Correlation Coeffi cients達(dá)到了0.95.因此,根據(jù)我們的帶寬分配方案,在BA網(wǎng)絡(luò)中度數(shù)高的節(jié)點(diǎn)周圍會(huì)出現(xiàn)大量受控邊.

圖2 BA網(wǎng)絡(luò)中,各個(gè)節(jié)點(diǎn)的度和介數(shù),插圖是序號(hào)1—50的節(jié)點(diǎn)相應(yīng)的度和介數(shù)

圖3 顯示了隨著網(wǎng)絡(luò)中受控邊比例的增加,中心節(jié)點(diǎn)的連接邊帶寬資源被減少,并且減少的這部分帶寬資源被均勻地分配給了帶寬資源不足的一般節(jié)點(diǎn),使得整個(gè)網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的連接邊帶寬資源分配更加趨于均衡.

圖3 BA網(wǎng)絡(luò)中,在受控邊比例 f ce=0,0.1,0.2,0.3,0.4時(shí),節(jié)點(diǎn)連接邊帶寬Bi的變化

這里,我們引入統(tǒng)計(jì)中的標(biāo)準(zhǔn)差概念來反映均衡程度和異質(zhì)程度.標(biāo)準(zhǔn)差值越小代表越均衡,反之則表明異質(zhì)性強(qiáng).

圖4是在BA網(wǎng)絡(luò)中受控邊增加時(shí),節(jié)點(diǎn)連接邊帶寬的標(biāo)準(zhǔn)差變化.隨著受控邊比例在BA網(wǎng)路中增加,帶寬標(biāo)準(zhǔn)差值是持續(xù)下降的,網(wǎng)絡(luò)中節(jié)點(diǎn)的連接邊帶寬在趨于均衡.

圖4 BA網(wǎng)絡(luò)(m0=m=3,〈K〉=6)節(jié)點(diǎn)連接邊帶寬Bi標(biāo)準(zhǔn)差在不同受控邊比例下的變化

圖5 WS網(wǎng)絡(luò)(p=0.3,〈K〉=4)節(jié)點(diǎn)連接度分布

圖5 和圖6分別是WS網(wǎng)絡(luò)節(jié)點(diǎn)度分布和介數(shù)分布,可以看出WS網(wǎng)絡(luò)的度分布較為均勻,而介數(shù)分布異質(zhì)性較大.在對(duì)WS網(wǎng)絡(luò)平臺(tái)仿真中,圖7反映了WS網(wǎng)絡(luò)節(jié)點(diǎn)連接邊帶寬Bi的標(biāo)準(zhǔn)差和網(wǎng)絡(luò)最大負(fù)載能力Rc隨受控邊比例增加的變化.發(fā)現(xiàn) fce為0.1(±0.01),帶寬標(biāo)準(zhǔn)差出現(xiàn)最小值時(shí),網(wǎng)絡(luò)帶寬分布最優(yōu),同時(shí)負(fù)載能力最大.再加入受控邊的過程中,計(jì)算節(jié)點(diǎn)連接邊帶寬Bi標(biāo)準(zhǔn)差與網(wǎng)絡(luò)負(fù)載能力Rc的Pearson Correlation Coeffi cients為-0.87,可以看出,在WS小世界網(wǎng)絡(luò)中節(jié)點(diǎn)的連接邊帶寬分布得越均衡,網(wǎng)絡(luò)整體的負(fù)載能力越強(qiáng).

由于WS小世界網(wǎng)絡(luò)中,雖然介數(shù)分布異質(zhì),但度分布均勻,在為負(fù)載重的節(jié)點(diǎn)周圍加入相對(duì)較少的受控邊就能使得網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的負(fù)載和帶寬相對(duì)均衡,使得負(fù)載和帶寬具有較強(qiáng)的相關(guān)性;而BA網(wǎng)絡(luò)中,無論是節(jié)點(diǎn)介數(shù)還是連接度,中心節(jié)點(diǎn)與一般節(jié)點(diǎn)的差異性很大.所以,達(dá)到網(wǎng)絡(luò)最大負(fù)載能力時(shí),各個(gè)節(jié)點(diǎn)間的節(jié)點(diǎn)連接邊帶寬Bi仍然存在較大異質(zhì)性.

圖6 WS網(wǎng)絡(luò)(p=0.3,〈K〉=4)節(jié)點(diǎn)介數(shù)分布

圖7 WS網(wǎng)絡(luò)(p=0.3,〈K〉=4)節(jié)點(diǎn)連接邊帶寬Bi標(biāo)準(zhǔn)差和網(wǎng)絡(luò)最大負(fù)載能力R c在不同受控邊比例下的變化

圖 8 WS 網(wǎng)絡(luò) (N=1000,p=0.1,0.2,0.3,0.4,0.5,〈K〉=4)節(jié)點(diǎn)度的標(biāo)準(zhǔn)差變化

網(wǎng)絡(luò)節(jié)點(diǎn)度的標(biāo)準(zhǔn)差可以衡量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的異質(zhì)程度,標(biāo)準(zhǔn)差值越大網(wǎng)絡(luò)拓?fù)洚愘|(zhì)性越強(qiáng).從圖8可以看出,WS小世界網(wǎng)絡(luò)拓?fù)洚愘|(zhì)化程度隨著p值增大而加強(qiáng).從圖9中可見,在WS小世界網(wǎng)絡(luò)中,最優(yōu)節(jié)點(diǎn)連接邊帶寬分布和相對(duì)應(yīng)的受控邊比例都隨著網(wǎng)絡(luò)異質(zhì)性加強(qiáng)而增加.

圖 9 WS 網(wǎng)絡(luò) (N=1000,p=0.1,0.2,0.3,0.4,〈K〉=4)節(jié)點(diǎn)連接邊帶寬Bi標(biāo)準(zhǔn)差最小值和網(wǎng)絡(luò)最大負(fù)載能力R c在不同受控邊比例下的變化

5 結(jié)論

存在節(jié)點(diǎn)度或介數(shù)異質(zhì)化分布的網(wǎng)絡(luò)中,在數(shù)據(jù)包傳遞過程中存在一定量的冗余路徑.當(dāng)一些節(jié)點(diǎn)數(shù)據(jù)包負(fù)載較重時(shí),存在可以繞開這些節(jié)點(diǎn)的其他路徑.我們發(fā)現(xiàn),節(jié)點(diǎn)的處理能力相同且?guī)挿峙鋭蛸|(zhì)時(shí),負(fù)載重的中心節(jié)點(diǎn)受限于自身的數(shù)據(jù)處理能力,其周圍連接邊占據(jù)著大量過剩帶寬資源;而具有同樣數(shù)據(jù)處理能力的一般節(jié)點(diǎn)通常都是帶寬較少,在需要一般節(jié)點(diǎn)為中心節(jié)點(diǎn)分擔(dān)負(fù)載的時(shí)候往往又受限于連接邊的帶寬.根據(jù)這一發(fā)現(xiàn),提出了帶寬分配方案,通過合理地釋放一些節(jié)點(diǎn)過剩的帶寬資源,把部分中心節(jié)點(diǎn)周圍的連接邊變成“受控邊”,減少“受控邊”的帶寬,在不破壞網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí)釋放出“受控邊”的帶寬資源分給其他一般節(jié)點(diǎn)周圍的連接邊,以此來提高帶寬資源的利用效率,提升網(wǎng)絡(luò)的負(fù)載性能.在相同類型和規(guī)模的WS網(wǎng)絡(luò)中,異質(zhì)化程度越高,相應(yīng)網(wǎng)絡(luò)中冗余邊存在的比例就越高,也因此需要加入的受控邊比例也越高.我們也對(duì)相同規(guī)模不同網(wǎng)絡(luò)做了仿真,發(fā)現(xiàn)異質(zhì)化程度高的網(wǎng)絡(luò),達(dá)到最優(yōu)負(fù)載時(shí)需要加入的受控邊比例相應(yīng)也高.

引入異質(zhì)化帶寬分配方案使得BA網(wǎng)絡(luò)負(fù)載性能提升主要來自于兩部分貢獻(xiàn),其一是異質(zhì)化帶寬分配方案有效地限制了涌向中心節(jié)點(diǎn)數(shù)據(jù)流量,有效緩解了中心節(jié)點(diǎn)擁塞,將部分負(fù)載轉(zhuǎn)向一般節(jié)點(diǎn),相對(duì)平衡了各個(gè)節(jié)點(diǎn)的負(fù)載;其二是將中心節(jié)點(diǎn)的過剩的連接邊帶寬分配給連接邊帶寬不足的一般節(jié)點(diǎn),使得大多數(shù)節(jié)點(diǎn)連接邊的傳遞能力增強(qiáng),同時(shí)更好地消化轉(zhuǎn)移過來的負(fù)載.

對(duì)于WS小世界網(wǎng)絡(luò),由于節(jié)點(diǎn)度分布均勻,帶寬約束對(duì)所有節(jié)點(diǎn)的數(shù)據(jù)流量都起到了制約作用.加入少量受控邊就會(huì)使得各個(gè)節(jié)點(diǎn)的連接邊帶寬達(dá)到最佳狀態(tài),同時(shí)實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載能力的最優(yōu).

本文中,帶寬分配方案是與感知節(jié)點(diǎn)擁塞的路由算法配合應(yīng)用的.在特殊情況下,受控邊的帶寬為0時(shí),本套方案仍然有效.值得注意的是,如果使用最短路徑路由時(shí),加入受控邊帶寬為0則需要重新考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),按照刪除受控邊后新的網(wǎng)絡(luò)結(jié)構(gòu)重新計(jì)算最短路徑,否則會(huì)造成數(shù)據(jù)包在原來最短路徑上的節(jié)點(diǎn)處大量累積,大大降低網(wǎng)絡(luò)負(fù)載能力.

總之,本文提出的異質(zhì)化帶寬分配方案,優(yōu)化了網(wǎng)絡(luò)上帶寬資源的分配,有效調(diào)節(jié)網(wǎng)絡(luò)流量走向,使得網(wǎng)絡(luò)總體負(fù)載能力較勻質(zhì)分配帶寬時(shí)有較大提升,為提高網(wǎng)絡(luò)負(fù)載性能研究提供了一個(gè)新思路.

感謝中國(guó)科學(xué)研究院計(jì)算所(北京)的張國(guó)清副研究員對(duì)于刪邊擴(kuò)容效應(yīng)以及算法實(shí)現(xiàn)上的熱情討論和幫助.

[1]Watts D,Strogatz S 1998 Nature 393 440

[2]Barab′asi A L,Albert R 1999 Science 286 509

[3]Ohira T,Sawatari R 1998 Phys.Rev.E 58 193

[4]Faloutsos M,Faloutsos P,Faloutsos C 1999 Comp.Commun.Rev.29 251

[5]Albert R,Barab′asi A L 2002 Rev.Mod.Phys.74 47

[6]Newman M EJ2003 SIAM Rev.45 167

[7]Wang X F,Chen G R 2003 IEEETrans.Circuits Syst.3 6

[8]Hao B B,Yu H,Jing Y W,Zhang SY 2009 Physica A 388 1939

[9]Arenas A,Diaz-Guilera A,Guimera R 2001 Phys.Rev.Lett.86 3196

[10]Wang W X,Wang B H,Yin CY,Xie Y B,Zhou T 2006 Phys.Rev.E 73 026111

[11]Yan G,Zhou T,Hu B,Fu ZQ 2006 Phys.Rev.E 73 046108

[12]Chen Z Y,Wang X F 2006 Physica A 364 595

[13]Wang D,Jing Y W,Zhang SY 2008 Physica A 387 3001

[14]Pu CL,Pei W J2010 Acta Phys.Sin.59 3841(in Chinese)[濮存來,裴文江2010物理學(xué)報(bào)59 3841]

[15]Danila B,Yu Y,Marsh JA,Bassler K E 2006 Phys.Rev.E 74 046106

[16]Wang D,Yu H,Jing Y W,Jiang N,Zhang SY 2009 Acta Phys.Sin.58 6802(in Chinese)[王丹,于灝,井元偉,姜囡,張嗣贏2009物理學(xué)報(bào)58 6802]

[17]Guimer`a R,D′?az-Guilera A,Vega-Redondo F,Cabrales A,Arenas A 2002 Phys.Rev.Lett.89 248701

[18]Zhang GQ,Wang D,Li GJ2007 Phys.Rev.E 76 017101

[19]Zhang G Q,Cheng S Q 2012 Sci.Sin.Infom.42 151(in Chinese)[張國(guó)清,程蘇琦2012中國(guó)科學(xué)(信息科學(xué))42 151]

[20]Hu M B,Wang W X,Jiang R,Wu Q S,Wu Y H 2007 Euro.Phys.Lett.79 14003

[21]Yu H,Jing Y W,Zhou Y C,Ma Y 2010 Journal of Northeastern University(Nat.Sci.)31 1226(in Chinese)[于灝,井元偉,周玉成,馬妍2010東北大學(xué)學(xué)報(bào)(自然科學(xué)版)31 1226]

[22]Ling X,Hu M B,Du WB,Jiang R,Wu Y H,Wu QS2010 Phys.Lett.A 374 4825