于 灝，馬 妍，王新華，井元偉，周玉成，王 丹

（1.山東科技大學(xué)經(jīng)濟(jì)管理學(xué)院，山東 青島266590；2.青島理工大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院，山東 青島266520；3.東北大學(xué)a.工商管理學(xué)院；b.信息科學(xué)與工程學(xué)院，遼寧 沈陽110819；4.中國林業(yè)科學(xué)院木材工業(yè)研究所，北京100091；5.沈陽大學(xué)裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽110044）

0 引言

研究任何現(xiàn)實(shí)系統(tǒng)時(shí)都不能忽略的一個(gè)重要問題，就是資源的有限性，在復(fù)雜網(wǎng)絡(luò)傳輸問題研究上也不例外?，F(xiàn)實(shí)網(wǎng)絡(luò)傳輸系統(tǒng)發(fā)生擁堵的主要原因來自于網(wǎng)絡(luò)資源方面的限制，通常在網(wǎng)絡(luò)傳輸中的資源限制主要包括兩個(gè)方面：一是網(wǎng)絡(luò)節(jié)點(diǎn)資源的有限性，例如：通信網(wǎng)絡(luò)路由器的轉(zhuǎn)發(fā)能力和緩沖區(qū)的隊(duì)列長度限制，交通網(wǎng)絡(luò)中的交通樞紐站點(diǎn)的轉(zhuǎn)運(yùn)能力和容納能力等；二是網(wǎng)絡(luò)中連接邊的容量（帶寬）資源的有限性，它主要是指網(wǎng)絡(luò)中連接邊在單位時(shí)間運(yùn)送數(shù)據(jù)包的能力，例如：通信網(wǎng)絡(luò)的傳輸帶寬限制，交通道路上承載車流量的能力等等。除了提高網(wǎng)絡(luò)資源供給之外，制定有效的資源分配策略是提高網(wǎng)絡(luò)傳輸性能的必要手段。在考慮連接邊帶寬資源限制下的復(fù)雜網(wǎng)絡(luò)傳輸問題的研究中，文獻(xiàn)［1］分析了平均分配帶寬時(shí)，帶寬限制對(duì)網(wǎng)絡(luò)傳輸性能的影響。文獻(xiàn)［2］提出了一種“反直覺”的帶寬分配方案，通過引入“受控邊”優(yōu)化了帶寬資源的利用效率，使得網(wǎng)絡(luò)負(fù)載性能較勻質(zhì)化分配帶寬有了很大提升，文獻(xiàn)［3］設(shè)計(jì)了帶寬分配方案，有效地改善了網(wǎng)絡(luò)負(fù)載性能。本文通過設(shè)計(jì)異質(zhì)化隨機(jī)帶寬分配方案來分析帶寬分配對(duì)網(wǎng)絡(luò)傳輸性能的影響。

1 傳輸流量模型

在本文傳輸流量模型中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)被看作是主機(jī)和路由器的結(jié)合體，具有產(chǎn)生、儲(chǔ)存、傳遞數(shù)據(jù)包的功能。每個(gè)節(jié)點(diǎn)的處理數(shù)據(jù)包能力為Ci，規(guī)定每個(gè)節(jié)點(diǎn)的處理能力Ci相同且為常數(shù)。每個(gè)節(jié)點(diǎn)容量為無限大，且每個(gè)節(jié)點(diǎn)緩沖隊(duì)列中等待發(fā)送的數(shù)據(jù)包都是按照先入先出的規(guī)則按順序進(jìn)行處理。連接邊只具有傳遞功能。如發(fā)生網(wǎng)絡(luò)擁塞僅出現(xiàn)在節(jié)點(diǎn)處。R為數(shù)據(jù)包產(chǎn)生率，即：單位時(shí)間內(nèi)新加入R個(gè)數(shù)據(jù)包。數(shù)據(jù)包的出發(fā)節(jié)點(diǎn)和目的節(jié)點(diǎn)隨機(jī)選取，到達(dá)目的節(jié)點(diǎn)后的數(shù)據(jù)包自動(dòng)從網(wǎng)絡(luò)上移除。數(shù)據(jù)包的傳遞依照路由策略進(jìn)行。其中路由策略以文獻(xiàn)［4－6］中的路由策略方案為基礎(chǔ)，并加以改進(jìn)得到——G－L路由策略。

G－L路由策略中的節(jié)點(diǎn)權(quán)值為

其中，Li→t為節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)t的最短路徑長度，Qi為節(jié)點(diǎn)i當(dāng)前所存儲(chǔ)待處理的數(shù)據(jù)包個(gè)數(shù)，相當(dāng)于路由器的緩沖隊(duì)列長度，α為一個(gè)可以調(diào)節(jié)的參數(shù)，其范圍位于0和1之間。Bi為節(jié)點(diǎn)i的連接邊帶寬，即節(jié)點(diǎn)i所有相鄰連接邊帶寬的總和。

路由選擇策略中，選取相鄰連接節(jié)點(diǎn)權(quán)值最小的節(jié)點(diǎn)作為下一路由節(jié)點(diǎn)，進(jìn)行傳遞。如遇到最小權(quán)值節(jié)點(diǎn)不唯一的情況，則隨機(jī)選擇一個(gè)作為下一路由節(jié)點(diǎn)。

為了更好描述網(wǎng)絡(luò)傳輸中流量狀態(tài)變化過程，引入狀態(tài)相變參數(shù)η來進(jìn)行描述［7－9］：

其中，〈ΔW（t）〉為相鄰時(shí)刻網(wǎng)絡(luò)中總的數(shù)據(jù)包變化量。Rc作為網(wǎng)絡(luò)流量由自由流狀態(tài)向擁塞狀態(tài)轉(zhuǎn)變過程中數(shù)據(jù)包產(chǎn)生率的臨界值。當(dāng)R＜Rc時(shí)，網(wǎng)絡(luò)系統(tǒng)中產(chǎn)生的數(shù)據(jù)包和到達(dá)目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包數(shù)量維持均衡，此時(shí)η值近似為零，網(wǎng)絡(luò)傳輸系統(tǒng)處于穩(wěn)定的自由流狀態(tài)；當(dāng)R＞Rc時(shí)，網(wǎng)絡(luò)傳輸系統(tǒng)不能及時(shí)地、完全地消化新產(chǎn)生的數(shù)據(jù)包，數(shù)據(jù)包在網(wǎng)絡(luò)中開始累積，此時(shí)系統(tǒng)進(jìn)入擁塞狀態(tài)，且η值伴隨著R的增加而增大，同時(shí)η值越大，表示擁塞程度越高。最終η＝1時(shí)，網(wǎng)絡(luò)傳輸系統(tǒng)處于完全堵塞狀態(tài)，此時(shí)代表網(wǎng)絡(luò)中新產(chǎn)生的數(shù)據(jù)包一個(gè)都不能傳出，全部滯留在網(wǎng)絡(luò)中。本文中把傳輸效率最高時(shí)的狀態(tài)相變臨界值Rc作為網(wǎng)絡(luò)最大負(fù)載能力的標(biāo)志進(jìn)行研究。

2 隨機(jī)帶寬分配方案設(shè)計(jì)

為了通過帶寬隨機(jī)分配對(duì)網(wǎng)絡(luò)傳輸?shù)挠绊?，探索合理的分配方案制定依?jù)，本文設(shè)計(jì)了兩種隨機(jī)帶寬分配方案：完全隨機(jī)帶寬分配方案和分類隨機(jī)帶寬分配方案來進(jìn)行研究。

完全隨機(jī)帶寬分配方案：為每條連接邊隨機(jī)分配帶寬集合B∈［a －b］，1≤a＜b中的帶寬值。為了使得每次隨機(jī)分配帶寬的網(wǎng)絡(luò)傳輸之間能夠進(jìn)行性能比較，這里規(guī)定網(wǎng)絡(luò)的連接邊帶寬資源總量固定為常數(shù)BT。

分類隨機(jī)帶寬分配方案：為網(wǎng)絡(luò)中的每條邊分配權(quán)值σij＝gi＊gj，其中g(shù)i和gj分別為連接邊兩端節(jié)點(diǎn)i和節(jié)點(diǎn)j的介數(shù)，網(wǎng)絡(luò)邊的平均權(quán)值為。網(wǎng)絡(luò)的邊被分成兩組E1和E2。E1中，所有連接邊權(quán)值小于或等于平均邊權(quán)值；E2中，所有連接邊權(quán)值大于平均邊權(quán)值。網(wǎng)絡(luò)連接邊的平均帶寬，選取兩個(gè)帶寬集合B1∈［a～］，1≤a＜和B2∈分別為兩組邊隨機(jī)分配帶寬集B1，B2中的帶寬值。規(guī)定網(wǎng)絡(luò)的連接邊帶寬資源總量固定為常數(shù)BT。

3 隨機(jī)帶寬分配網(wǎng)絡(luò)流量仿真與分析

選取HK－BA無標(biāo)度網(wǎng)絡(luò)［10］作為網(wǎng)絡(luò)拓?fù)淦脚_(tái)。網(wǎng)絡(luò)規(guī)模為1 000個(gè)節(jié)點(diǎn)。網(wǎng)絡(luò)模型初始節(jié)點(diǎn)互不相連m0＝m＝3，調(diào)節(jié)概率為0.5。

應(yīng)用完全隨機(jī)帶寬分配方案，帶寬集B∈ ［1 ～ 10］。使用最短路徑路由策略（SPR）（α＝1）和G－L路由策略

既然完全隨機(jī)帶寬分配不是實(shí)用有效的帶寬分配方式，為了進(jìn)一步探求帶寬的“合理”或接近“合理”的分配方案，下面討論研究本文提出的另一種帶寬分配方式——分類隨機(jī)帶寬分配方案。仿真中，網(wǎng)絡(luò)平均帶寬帶寬集B1∈［1～5］，B2∈（5～10］。網(wǎng)絡(luò)的連接邊帶寬資源總量固定。

為了清晰比較，選取4種帶寬分配與路由策略的組合進(jìn)行網(wǎng)絡(luò)傳輸性能的對(duì)比。4種組合及對(duì)比關(guān)系如圖2所示，方框中標(biāo)明了帶寬分配與路由策略的組合方式，雙向箭頭代表組合間進(jìn)行對(duì)比。每種組合分別進(jìn)行20次試驗(yàn)，其結(jié)果的平均值呈現(xiàn)在圖3～圖6。在各組合采用的路由策略下，平均分配帶寬（每條邊的帶寬都相等，為5）的網(wǎng)絡(luò)最大負(fù)載作為對(duì)比中間值。（α＝0.7）選取了20組流量試驗(yàn)得到的各自最大負(fù)載（每組20次試驗(yàn)的平均結(jié)果）（見圖1），所有試驗(yàn)中網(wǎng)絡(luò)節(jié)點(diǎn)處理能力相同Ci＝50。圖1中縱坐標(biāo)是代表網(wǎng)絡(luò)最大負(fù)載能力的Rc值，橫坐標(biāo)是試驗(yàn)組序號(hào)，圓形標(biāo)示是最短路徑路由策略下網(wǎng)絡(luò)帶寬完全隨機(jī)分配時(shí)的網(wǎng)絡(luò)最大負(fù)載值，方形標(biāo)示是G－L路由策略下網(wǎng)絡(luò)帶寬完全隨機(jī)分配時(shí)的網(wǎng)絡(luò)最大負(fù)載值。通過圖1發(fā)現(xiàn)：1）在應(yīng)用同一路由策略網(wǎng)絡(luò)時(shí)，隨機(jī)分配連接邊帶寬產(chǎn)生了不同的網(wǎng)絡(luò)最大負(fù)載能力，且無法判斷其中規(guī)律；2）在相同帶寬分配的網(wǎng)絡(luò)中，應(yīng)用G－L路由策略所產(chǎn)生的網(wǎng)絡(luò)最大負(fù)載都要高于應(yīng)用最短路由策略時(shí)的網(wǎng)絡(luò)最大負(fù)載；3）相對(duì)于最短路徑路由策略，G－L路由策略在不同帶寬分配時(shí)，對(duì)網(wǎng)絡(luò)最大負(fù)載影響方面表現(xiàn)出較強(qiáng)的魯棒性。

從以上對(duì)完全隨機(jī)分配帶寬方案的研究，可以看出，完全隨機(jī)地分配網(wǎng)絡(luò)連接邊帶寬對(duì)網(wǎng)絡(luò)負(fù)載的影響帶有不確定性，因此，這種方案不是一種實(shí)用有效的帶寬分配方案，但同時(shí)也發(fā)現(xiàn)不同帶寬分配時(shí)，不同路由策略對(duì)網(wǎng)絡(luò)性能的影響情況是不盡相同的。

文獻(xiàn)［4－6］對(duì)路由策略的性能的分析比較可以說明圖1發(fā)現(xiàn)中的第2點(diǎn)。下面來分析圖1中的第3點(diǎn)發(fā)現(xiàn)。網(wǎng)絡(luò)連接邊的介數(shù)反映了某條邊在網(wǎng)絡(luò)中的重要性，邊介數(shù)高代表網(wǎng)絡(luò)中通過這些邊的最短路徑數(shù)量較多。在應(yīng)用最短路徑路由時(shí)，數(shù)據(jù)包傳輸路徑嚴(yán)格遵循著由拓?fù)浣Y(jié)構(gòu)決定的最短拓?fù)渚嚯x線路，此時(shí)，通過高介數(shù)邊的數(shù)據(jù)包相應(yīng)較多，并且整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)包流向也是向著最高介數(shù)邊方向聚集，如果隨機(jī)分配帶寬時(shí)，分配到這些重要的介數(shù)高的邊的帶寬值很小，就會(huì)造成數(shù)據(jù)包在這些邊附近的節(jié)點(diǎn)大量累積，造成傳輸流量放緩，并很快擁堵，降低網(wǎng)絡(luò)傳輸性能。G－L路由策略本身能夠根據(jù)網(wǎng)絡(luò)局部節(jié)點(diǎn)數(shù)據(jù)包的擁塞程度的動(dòng)態(tài)信息而選擇調(diào)整流向，離開最短路徑傳輸線路，這使得部分?jǐn)?shù)據(jù)流避免涌向數(shù)據(jù)包最聚集的地方，能夠一定程度上緩解擁塞的發(fā)生，因此，使得G－L路由策略在遭遇上面所述高介數(shù)邊被分配小帶寬時(shí)，網(wǎng)絡(luò)性能表現(xiàn)不會(huì)像最短路徑策略時(shí)那么糟糕。而當(dāng)網(wǎng)絡(luò)上連接邊帶寬的分配較為合理時(shí)，最短路徑策略路由下的網(wǎng)絡(luò)負(fù)載能力得到提升，此時(shí)，采用GL路由策略的路由線路也會(huì)靠近最短路徑線路。因此，G－L路由策略可以根據(jù)網(wǎng)絡(luò)不同帶寬分配情況，通過調(diào)節(jié)遠(yuǎn)離或靠近最短路徑線路，來保持隨機(jī)性分配對(duì)網(wǎng)絡(luò)最大負(fù)載影響方面的魯棒性。

圖1 完全隨機(jī)異質(zhì)化帶寬分配時(shí)，SPR與G－L路由策略下網(wǎng)絡(luò)最大負(fù)載Fig.1 Maximum load with SPR and G－L routing strategy with complete random heterogeneous bandwidth allocation

圖2 帶寬分配與路由策略組合對(duì)比關(guān)系Fig.2 Correlation of bandwidth allocations and routing strategies

圖3 采用組合1時(shí)，網(wǎng)絡(luò)流量狀態(tài)Fig.3 The network traffic with group 1

圖4 采用組合2時(shí)，網(wǎng)絡(luò)流量狀態(tài)Fig.4 The network traffic with group 2

圖5 采用組合3時(shí)，網(wǎng)絡(luò)流量狀態(tài)Fig.5 The network traffic with group 3

圖6 采用組合4時(shí)，網(wǎng)絡(luò)流量狀態(tài)Fig.6 The network traffic with group 4

由圖3與圖4可以看出，采用組合1方式分配帶寬時(shí)網(wǎng)絡(luò)的最大負(fù)載能力Rc要高于組合2帶寬分配方式下的。對(duì)比圖5與圖6可以看出，采用組合3方式分配帶寬時(shí)網(wǎng)絡(luò)的最大負(fù)載能力Rc要高于組合4帶寬分配方式下的。并且，組合1、組合2仿真得到的網(wǎng)絡(luò)最大負(fù)載分別優(yōu)于組合3、組合4的。

節(jié)點(diǎn)介數(shù)可以表示理論上通過某一節(jié)點(diǎn)的最短路徑的數(shù)量，也就是說在網(wǎng)絡(luò)傳輸中節(jié)點(diǎn)的介數(shù)越高代表了數(shù)據(jù)包通過它的概率越高。在分類隨機(jī)帶寬分配方案中，這里為網(wǎng)絡(luò)中的每條邊分配權(quán)值σij＝gi＊gj，其中，gi和gj分別為連接邊兩端節(jié)點(diǎn)i和節(jié)點(diǎn)j的介數(shù)。此時(shí)，網(wǎng)絡(luò)中邊的權(quán)值σij高的邊意味著在網(wǎng)絡(luò)傳輸中占據(jù)著重要的位置，這些邊會(huì)是網(wǎng)絡(luò)上數(shù)據(jù)包流經(jīng)量很高的邊，肩負(fù)的傳遞負(fù)擔(dān)也重。因此，在帶有帶寬約束限制的網(wǎng)絡(luò)中，為權(quán)值高的連接邊分配的帶寬量對(duì)網(wǎng)絡(luò)傳輸性能會(huì)產(chǎn)生重大的影響。

組合2、組合3中，為低權(quán)值的邊（E1）分配低帶寬值（B1），相應(yīng)權(quán)值高的邊（E2）分配高帶寬值（B2），這種分配方式下的網(wǎng)絡(luò)最大負(fù)載均高于各自網(wǎng)絡(luò)帶寬均分時(shí)產(chǎn)生的網(wǎng)絡(luò)最大負(fù)載。因此，在網(wǎng)絡(luò)總帶寬資源固定情況下，負(fù)載較重的高權(quán)值邊得到相應(yīng)較高的帶寬分配會(huì)得到較好的網(wǎng)絡(luò)傳輸性能。

組合2、組合4中，為低權(quán)值的邊（E1）分配高帶寬值（B2），相應(yīng)權(quán)值高的邊（E2）分配較低帶寬值（B1），這種分配方式下的網(wǎng)絡(luò)負(fù)載性能均劣于各自網(wǎng)絡(luò)帶寬均分時(shí)產(chǎn)生的網(wǎng)絡(luò)負(fù)載性能。此時(shí)，由于網(wǎng)絡(luò)傳輸中總的帶寬資源是固定不變的，為傳輸負(fù)載較重的邊分配較小帶寬會(huì)帶來網(wǎng)絡(luò)傳輸抑制數(shù)據(jù)包傳遞過程，而分配傳輸負(fù)載較輕的邊較多帶寬存在帶寬的浪費(fèi)，從而影響到網(wǎng)絡(luò)負(fù)載性能，造成整個(gè)網(wǎng)絡(luò)負(fù)載能力降低。

此外，采用G－L路由策略的組合1、組合2帶寬分配下網(wǎng)絡(luò)傳輸性能分別優(yōu)于采用最短路由策略的組合3、組合4，說明文中的分類隨機(jī)帶寬分配方案沒有影響到路由策略本身對(duì)網(wǎng)絡(luò)傳輸性能的作用效果。

4 結(jié)論

設(shè)計(jì)了完全隨機(jī)帶寬分配方案和分類隨機(jī)帶寬分配方案。通過仿真試驗(yàn)發(fā)現(xiàn)，完全隨機(jī)地分配網(wǎng)絡(luò)連接邊帶寬對(duì)網(wǎng)絡(luò)負(fù)載的影響帶有不確定性，因此，這種方案不是一種實(shí)用有效的帶寬分配方案，同時(shí)還發(fā)現(xiàn)，G－L路由策略相對(duì)于最短路由策略在保持帶寬隨機(jī)分配對(duì)網(wǎng)絡(luò)最大負(fù)載影響方面具有較好的魯棒性。在對(duì)分類隨機(jī)帶寬分配方案的研究中發(fā)現(xiàn)，在介數(shù)存在異質(zhì)性分布的復(fù)雜網(wǎng)絡(luò)中，為依據(jù)介數(shù)由高到低的邊集分派相應(yīng)由高到低的帶寬集，有利于提升網(wǎng)絡(luò)負(fù)載性能。

［1］ 于灝，井元偉，周玉成，等.固定帶寬下的無標(biāo)度網(wǎng)絡(luò)數(shù)據(jù)傳輸流量分析 ［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，31（9）：1226－1229.Yu Hao，Jing Yuanwei，Zhou Yucheng，et al.Dynamic analysis of scale－free network traffic with fixed bandwidth［J］.Journal of Northeastern University（Natural Science），2010，31（9）：1226－1229.

［2］ 于灝，周玉成，井元偉，等.異質(zhì)化帶寬分配下的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)流負(fù)載問題研究 ［J］.物理學(xué)報(bào)，2013，62（8）：080502.Yu Hao，Zhou Yucheng，Jing Yuanwei，et al.Traffic dynamics of the complex networks with the heterogeneous bandwidth allocation［J］.Acta Phys Sin，2013，62（8）：080502.

［3］ Ling X，Hu M B，Du W B，et al.Bandwidth allocation strategy for traffic systems of scale－free network［J］.Physics Letters A，2010，374（48）：4825－4830.

［4］ Echenique Pablo，Oacute，Garde Mez，et al.improved routing strategies for internet traffic delivery［J］.Physical Review E，2004，70（5）：056105.

［5］ Chen Z Y，Wang X F.A congestion awareness routing strategy for scale－free networks with tunable clustering［J］.Physica A－Statistical Me－chanics and Its Applications，2006，364：595－602.

［6］ 王丹，于灝，井元偉，等.無標(biāo)度網(wǎng)絡(luò)中擁塞轉(zhuǎn)變的動(dòng)態(tài)分析 ［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，30（4）：462－465.Wang Dan，Yu Hao，Jing Yuanwei，et al.Dynamics of jamming transitions in scale－free networks［J］.Journal of Northeastern University（Natural Science），2009，30（4）：462－465.

［7］ Arenas A，Danon，Diaz G A，et al.Local search with congestion in complex communication networks［J］.Lecture Notes in Computer Science，2004，3038：1078－1085.

［8］ Wang D，Jing Y W，Zhang S Y.Traffic dynamics based on a traffic awareness routing strategy on scale－free networks［J］.Physica A－Statistical Mechanics and Its Applications，2008，387：3001－3007.

［9］ 王丹，于灝，井元偉，等.基于感知流量算法的復(fù)雜網(wǎng)絡(luò)擁塞問題研究 ［J］.物理學(xué)報(bào)，2009，58（10）：6802－6808.Wang Dan，Yu Hao，Jing Yuanwei，et al.Study on the congestion in complex network based on traffic awareness algorithm［J］.Acta Phys Sin，2009，58（10）：6802－6808.

［10］Holme P，Kim B J.Growing scale－free networks with tunable clustering［J］.Physical Review E，2002，65：026107.