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

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

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

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

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

1 引言

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

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

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

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

2.1 網(wǎng)絡拓撲模型

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

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

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

2.1.2 BA無標度網(wǎng)絡

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

1)初始網(wǎng)絡,具有m0個節(jié)點;

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

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

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

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

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

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

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

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

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

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

然后,選取權值最小的節(jié)點作為下一個路由節(jié)點.如果權值最小的節(jié)點有多個,那么隨機選取其中一個.

依照上述過程直到找到目標節(jié)點t.

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

3 帶寬分配方案

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

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

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

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

圖2 BA網(wǎng)絡中,各個節(jié)點的度和介數(shù),插圖是序號1—50的節(jié)點相應的度和介數(shù)

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

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

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

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

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

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

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

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

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

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

圖 8 WS 網(wǎng)絡 (N=1000,p=0.1,0.2,0.3,0.4,0.5,〈K〉=4)節(jié)點度的標準差變化

網(wǎng)絡節(jié)點度的標準差可以衡量網(wǎng)絡拓撲結構的異質(zhì)程度,標準差值越大網(wǎng)絡拓撲異質(zhì)性越強.從圖8可以看出,WS小世界網(wǎng)絡拓撲異質(zhì)化程度隨著p值增大而加強.從圖9中可見,在WS小世界網(wǎng)絡中,最優(yōu)節(jié)點連接邊帶寬分布和相對應的受控邊比例都隨著網(wǎng)絡異質(zhì)性加強而增加.

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

5 結論

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

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

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

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

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

感謝中國科學研究院計算所(北京)的張國清副研究員對于刪邊擴容效應以及算法實現(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物理學報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物理學報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)[張國清,程蘇琦2012中國科學(信息科學)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東北大學學報(自然科學版)31 1226]

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