BA網(wǎng)絡(luò)中一種基于節(jié)點動態(tài)權(quán)值的局部路由策略*

孫雅倩，張達敏，曾成，徐玉珠

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

BA網(wǎng)絡(luò)中一種基于節(jié)點動態(tài)權(quán)值的局部路由策略*

孫雅倩，張達敏，曾成，徐玉珠

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

為適應(yīng)大規(guī)模通信網(wǎng)絡(luò)的路由需求，提出了一種基于BA網(wǎng)絡(luò)的局部路由策略?；舅枷胧窃跀?shù)據(jù)包轉(zhuǎn)發(fā)過程中，將鄰居節(jié)點的度和發(fā)送能力以一定比例加和得到的值作為權(quán)值，根據(jù)權(quán)值大小選擇下一站點。其中，節(jié)點的發(fā)送能力由節(jié)點的數(shù)據(jù)包隊列長度，節(jié)點的度及一個調(diào)節(jié)系數(shù)組成，節(jié)點的發(fā)送能力可根據(jù)實時數(shù)據(jù)包產(chǎn)生率進行調(diào)節(jié)。仿真結(jié)果表明，該路由策略有較好的通訊能力，通過改變加權(quán)算法中的比例系數(shù)可以調(diào)節(jié)網(wǎng)絡(luò)的臨界負載量，達到該算法下的最優(yōu)路由方法，使節(jié)點的處理能力得到合理利用，為實際大規(guī)模通訊網(wǎng)絡(luò)中利用局部路由實現(xiàn)數(shù)據(jù)傳輸提供了有效可靠的方法。

BA網(wǎng)絡(luò);局部路由;度；介數(shù)

0 引 言

近些年，隨著通信網(wǎng)絡(luò)的日益發(fā)展，各種類型的路由策略相繼被提出，目的都是為了獲得較高的路由效率,提高通訊質(zhì)量。這些路由策略歸納起來有3種，基于全局信息的路由策略，基于局部信息的路由策略和基于混合信息的路由策略[1]。

基于全局信息的路由策略需要知道整個網(wǎng)絡(luò)的拓撲信息，經(jīng)典的最短路徑路由就是全局路由策略，優(yōu)點是擁有最短平均路徑長度，數(shù)據(jù)包能以最小的代價到達目的地[2]。缺點是容易在中心度較大的節(jié)點處發(fā)生擁塞，數(shù)據(jù)包長時間無法到達目的地而導(dǎo)致路由效率降低。由于要知道整個網(wǎng)絡(luò)的信息，導(dǎo)致在大型網(wǎng)絡(luò)中實現(xiàn)起來較困難。

基于局部信息的路由策略是指依靠網(wǎng)絡(luò)的局部信息來建立路由，常用的局部信息有鄰居節(jié)點的緩存隊列和度的大小、本地路由信息等。局部路由策略在建立過程中只需要考慮局部信息不需要知道整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，在實現(xiàn)上較容易。

混合路由策略是綜合考慮全局信息和局部信息建立路由。常見的有，將節(jié)點之間的最短路徑及節(jié)點的度或緩存隊列等因素相結(jié)合[3]。

如今，隨著各種基礎(chǔ)設(shè)施的網(wǎng)絡(luò)規(guī)模不斷擴大，人們對網(wǎng)絡(luò)性能的要求不斷提高，局部路由策略的優(yōu)勢日益凸顯。本文是在復(fù)雜網(wǎng)絡(luò)模型的基礎(chǔ)上提出一種局部路由策略，在轉(zhuǎn)發(fā)數(shù)據(jù)包時，可根據(jù)當(dāng)前網(wǎng)絡(luò)的數(shù)據(jù)包產(chǎn)生率可調(diào)節(jié)節(jié)點的發(fā)送能力，把鄰居節(jié)點的度及發(fā)送能力以比例系數(shù)加和，選擇權(quán)值最小的節(jié)點作為下一站點。從而增大網(wǎng)絡(luò)吞吐量，合理利用網(wǎng)絡(luò)節(jié)點資源。

1 基于節(jié)點權(quán)值的混合路由策略

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

通過多年的研究，學(xué)者們發(fā)現(xiàn)許多復(fù)雜網(wǎng)絡(luò)的連接度分布函數(shù)具有冪律形式。為了揭示冪律分布的產(chǎn)生機理, Barabás和Albert 提出了無標(biāo)度網(wǎng)絡(luò)模型(BA 模型)[4]。與均勻網(wǎng)絡(luò)不同，BA網(wǎng)絡(luò)具有增長特性和優(yōu)先連接特性，生成的網(wǎng)絡(luò)模型更符合實際網(wǎng)絡(luò)的特點，更具研究價值。其構(gòu)造算法如下[4-6]：

(1)網(wǎng)絡(luò)的初始規(guī)模為m0，網(wǎng)絡(luò)不斷增長擴大，直至達到所需規(guī)模N。在網(wǎng)絡(luò)增長過程中，每次引入一個新節(jié)點并依次與網(wǎng)絡(luò)中已經(jīng)存在的m個舊節(jié)點相連接,m

(2)新引入的節(jié)點與舊節(jié)點連接時，每個舊節(jié)點被選中的概率為Pi：

(1)

1.2 路由策略動力學(xué)模型

節(jié)點介數(shù)是指網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該節(jié)點的路徑的數(shù)目占最短路徑總數(shù)的比例。網(wǎng)絡(luò)節(jié)點的介數(shù)能準(zhǔn)確描述網(wǎng)絡(luò)節(jié)點在整個網(wǎng)絡(luò)中的重要性。計算BA無標(biāo)度網(wǎng)絡(luò)每個節(jié)點的介數(shù)，得到介數(shù)分布如圖1所示，網(wǎng)絡(luò)中只有很少一部分節(jié)點有大介數(shù)值，而大部分節(jié)點介數(shù)值非常小。在通訊過程中，數(shù)據(jù)包為了尋求最短路徑，導(dǎo)致個別介數(shù)大的節(jié)點承擔(dān)大量數(shù)據(jù)包，當(dāng)數(shù)據(jù)包產(chǎn)生率過大時，網(wǎng)絡(luò)會在介數(shù)大的節(jié)點處發(fā)生擁塞。因此，當(dāng)介數(shù)大的節(jié)點負載過量時，需要其他節(jié)點分擔(dān)數(shù)據(jù)包從而緩解擁塞。

但是，要得到每個節(jié)點的介數(shù)需要了解整個網(wǎng)絡(luò)的拓撲，當(dāng)網(wǎng)絡(luò)規(guī)模巨大并且不斷增長時，實現(xiàn)起來較困難。圖2的結(jié)果顯示，網(wǎng)絡(luò)節(jié)點的度和介數(shù)成正比關(guān)系。本文中用度代替介數(shù)的功能制定路由策略，因為度的大小可以作為局部路由信息，并不需要知道整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。

圖1 BA網(wǎng)絡(luò)的節(jié)點介數(shù)分布

圖2 節(jié)點度和介數(shù)關(guān)系

路由策略具體實現(xiàn)方法如下：

(1)每一個時間步產(chǎn)生R個數(shù)據(jù)包，每個數(shù)據(jù)包的初始信息包括源節(jié)點和目的節(jié)點，源節(jié)點和目的節(jié)點是隨機選取的。根據(jù)數(shù)據(jù)包中的信息，需要將其從源節(jié)點發(fā)送到目的節(jié)點。網(wǎng)絡(luò)中的每個節(jié)點既有接收數(shù)據(jù)包的功能，也有轉(zhuǎn)發(fā)的功能。即每一個節(jié)點既是服務(wù)器終端，又是中介傳遞信息的路由器[7-8]。

(2)實際網(wǎng)絡(luò)中，節(jié)點的信息處理能力往往與該點在網(wǎng)絡(luò)中的重要性呈正比。因此，本文假設(shè)節(jié)點的處理能力與節(jié)點的度呈正相關(guān)，即在一個時間步內(nèi)能處理的數(shù)據(jù)包個數(shù)等于該節(jié)點度的大小。

(3)在轉(zhuǎn)發(fā)數(shù)據(jù)包時，先遍歷鄰居節(jié)點，如果鄰居節(jié)點中有該數(shù)據(jù)包的目的節(jié)點，則將數(shù)據(jù)包直接傳送給該鄰居節(jié)點，否則，計算鄰居節(jié)點權(quán)值Wi的大小，選擇權(quán)值最小的鄰居節(jié)點作為傳送數(shù)據(jù)包的下一節(jié)點。如果有多個鄰居節(jié)點權(quán)值大小相等并同為最小值，則從中隨機選一個節(jié)點。鄰居節(jié)點的權(quán)值Wi定義如下：

(2)

(4)每個節(jié)點處排隊等待的數(shù)據(jù)包按照先進先出(FIFO)的原則依次傳遞[11]。任何節(jié)點只能被同一個數(shù)據(jù)包訪問一次。

在上述動力學(xué)模型中，存在一個臨界新增負載量Rc，當(dāng)單位時間內(nèi)新增數(shù)據(jù)包負載量R=Rc時，網(wǎng)絡(luò)將從流通的平穩(wěn)態(tài)變成擁塞態(tài)，網(wǎng)絡(luò)中的數(shù)據(jù)包總量將持續(xù)上升。本文利用參數(shù)η(R)來描述該網(wǎng)絡(luò)狀態(tài)的變化[7]：

(3)

式中，η(R)是網(wǎng)絡(luò)中數(shù)據(jù)包總量的變化率，該算法中的C是節(jié)點在單位時間內(nèi)傳送數(shù)據(jù)包個數(shù)的平均值。

ΔNp=Np(t+Δt)-Np(t)

Np(t)表示t時刻網(wǎng)絡(luò)的總負載量。<ΔNp>是對ΔNp取平均。當(dāng)單位時間內(nèi)新增負載量P>Rc時，η(R)的值大于0。R

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

在仿真實驗中，BA網(wǎng)絡(luò)的規(guī)模取N=1 000。

網(wǎng)絡(luò)臨界數(shù)據(jù)包發(fā)送量的大小是衡量路由效率的重要因素。在此，利用仿真實驗對網(wǎng)絡(luò)的臨界數(shù)據(jù)發(fā)送率進行研究。圖3是系數(shù)α與臨界新增負載量Rc的關(guān)系。

圖3 系數(shù)a與臨界新增負載量Rc的關(guān)系

圖3表明：最大臨界新增負載量Rc的值在120 左右，0<α<0.5時的網(wǎng)絡(luò)吞吐量較為理想，α=0.1時吞吐量最高。原因是α代表度在權(quán)重計算中的比例，α越大則度大的節(jié)點被選中的概率越大，除非度大的節(jié)點處實時隊列很長，導(dǎo)致其動態(tài)權(quán)值變大，否則其很有可能被選中當(dāng)作數(shù)據(jù)包的傳輸節(jié)點，α=1時，網(wǎng)絡(luò)的臨界數(shù)據(jù)包發(fā)送率最低，在傳輸數(shù)據(jù)包的過程中將完全不考慮當(dāng)前節(jié)點的隊列情況，導(dǎo)致數(shù)據(jù)包只選擇個別度大的節(jié)點傳輸數(shù)據(jù)，導(dǎo)致度大的節(jié)點處迅速擁塞，其他節(jié)點得不到利用，浪費網(wǎng)絡(luò)資源，路由效率降低。

圖4是以α=0.5和α=0.1為例，R

圖4 R

圖5是α=0.5，R

圖5 α=0.5,R< RC時β對數(shù)據(jù)傳輸效率的影響

圖6是在α=0.1，R

圖6 α=0.1 R

圖7是500個時間步內(nèi)得到的節(jié)點介數(shù)和平均數(shù)據(jù)包關(guān)系圖，α越小，數(shù)據(jù)包在網(wǎng)絡(luò)中的分布越均勻?？偟膩碚f，介數(shù)大的節(jié)點會承擔(dān)著較多數(shù)據(jù)包，原因是介數(shù)較大的節(jié)點發(fā)送能力相對較強，一次能夠傳輸多個數(shù)據(jù)包，當(dāng)這些節(jié)點的數(shù)據(jù)包隊列長度小于其每個時間步能發(fā)送的數(shù)據(jù)包數(shù)時，它們會被優(yōu)先選擇。之前的實驗結(jié)果表明，α=1時網(wǎng)絡(luò)臨界數(shù)據(jù)包發(fā)送率最小，因為該路由方法使網(wǎng)絡(luò)數(shù)據(jù)包分配極不均勻，個別介數(shù)大的節(jié)點承擔(dān)幾乎所有數(shù)據(jù)包，使網(wǎng)絡(luò)在大介數(shù)節(jié)點處迅速擁塞。在α<0.5時，通訊過程中“能力較強”的節(jié)點得到充分利用，其他的節(jié)點根據(jù)其發(fā)送能力承擔(dān)一部分數(shù)據(jù)包，數(shù)據(jù)包分配均勻且合理。

圖7 R< RC時介數(shù)為B的節(jié)點處平均數(shù)據(jù)包變化趨勢

圖8與圖7的分布情況類似，但當(dāng)R>Rc,α=0.1時，雖然網(wǎng)絡(luò)中數(shù)據(jù)包的分布較均勻，但由于每個節(jié)點的發(fā)送能力有限，每個時間步產(chǎn)生大量數(shù)據(jù)包，信息包會出現(xiàn)過度累積。

圖8 R>Rc時介數(shù)為B的節(jié)點處平均數(shù)據(jù)包變化趨勢

綜合以上實驗數(shù)據(jù)得知，當(dāng)α<0.5 時,路由策略效率較高, 網(wǎng)絡(luò)節(jié)點的發(fā)送能力得到充分利用。α=0.1時路由方法最優(yōu)，在不是最優(yōu)路由策略的前提下，通過增大β值，也可以提高網(wǎng)絡(luò)路由效率。

3 結(jié) 語

本文提出了一個利用局部信息給鄰居節(jié)點動態(tài)加權(quán)的路由策略。在當(dāng)前節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包時，計算其每一個鄰居節(jié)點的權(quán)值，權(quán)值大小由節(jié)點的實時動態(tài)信息和靜態(tài)信息共同決定，而不是單純的考慮網(wǎng)絡(luò)固有的靜態(tài)信息，這更有益于為數(shù)據(jù)包選擇合適的傳送路徑，充分利用網(wǎng)絡(luò)中每個節(jié)點的發(fā)送能力。另外，該算法不需要知道整個網(wǎng)絡(luò)的拓撲信息，較易實現(xiàn)。經(jīng)過仿真證實，該路由算法運用靈活。β固定時，通過改變比例系數(shù)α可以調(diào)節(jié)臨界數(shù)據(jù)包產(chǎn)生量Rc的值。α固定時，通過改變β值也可以提高路有效率，得到該算法下較優(yōu)路由方法。總之，合理控制數(shù)據(jù)包產(chǎn)生率，結(jié)合實時信息和節(jié)點的發(fā)送能力，尋找當(dāng)前較優(yōu)的轉(zhuǎn)發(fā)路徑，可以使網(wǎng)絡(luò)處于平穩(wěn)狀態(tài)防止擁塞發(fā)生，適用于當(dāng)今規(guī)模日益增大的通訊網(wǎng)絡(luò)。

本文若有不妥之處，望各位專家和學(xué)者批評指正。

[1] 陳華良，劉忠信，陳增強等.復(fù)雜網(wǎng)絡(luò)的一種加權(quán)路由策略研究[J].物理學(xué)報,2009,55(09):6068-6073. CHEN Hua-liang ,LIU Zhong-xin, CHEN Zeng-qiang，et al. Research on One Weighted Routing Dtrategy for Complex Networks. [J] Acta Physica Sinica,2009,55(09):6068-6073.

[2] 劉偉彥，劉斌.基于局部路由策略的復(fù)雜網(wǎng)絡(luò)擁塞控制[J].物理學(xué)報，2014,63(24)：248901. LIU Wei-yan, LIU Bin. Congestion in Complex Network based on Local Routing Strategy[J].Acta Phys.sin. Vol.63, No.24(2014) 248901.

[3] 臧海娟，任彥，薛小平等.復(fù)雜網(wǎng)絡(luò)環(huán)境下的路由方法研究[J].計算機應(yīng)用，2010,30(08)：2210. ZANG Hai-juan, REN Yan, XUE Xiao-ping, TAN Yun-tian.Study of Routing Strategy on Complex Networks[J]. Journal of Computer Applications,2010,30(08):2210.

[4] 楊珉，張家玥，張達敏. 復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)的網(wǎng)絡(luò)模型研究綜述[J].通信技術(shù)，2014,47(12):1354-1359. YANG Min, ZHANG Jia-yue, ZHANG Da-min. Review of Complex Networks Topology Structure and Network Models Research[J]. Communications Technology, 2014, 47(12): 1354-1359.

[5] 王翠君,王紅. 復(fù)雜網(wǎng)絡(luò)的研究進展綜述[J].計算機與信息技術(shù),2007,31:417-418.

WANG Cui-jun, WANG Hong. Research Progress Out-Line of the Complex Network[J]. Science & Technology Information. 2007, 31: 417-418.

[6] 王小凡.基于復(fù)雜網(wǎng)絡(luò)的擁塞避免策略研究[D].西安：西安電子科技大學(xué) ,2013. WANG Xiao-fan. Rasearch of Congestion Control based on Complex Networks[D].Xi’an: Xidian University,2013.

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

[8] 卓越. 兩層復(fù)雜網(wǎng)絡(luò)上的動態(tài)權(quán)重路由策略研究[J]. 計算機應(yīng)用研究,2011,28(09):3411. ZHUO Yue. Study of Dynamic Weighted Routing Strategy for Two-Layer Comlex Networks[J].Application Research of Computer, 2011, 28(09): 3411.

[9] 王丹.復(fù)雜網(wǎng)絡(luò)擁塞分析與路由策略研究[D].遼寧：東北大學(xué),2002. WANG Dan. Analysis of Congestions and Rounting Strategies of Complex Networks[D].Liaoning: Northeastern University,2002.

[10] 文宏，樊曉平，張會福等.無標(biāo)度網(wǎng)絡(luò)上的動態(tài)局部路由策略設(shè)計[J].計算機工程與應(yīng)用，2014,50(20):10-14. WEN Hong, FAN Xiao-ping, ZHANG Hui-fu, et al. Dynamic Local Routing Strategy Design on Scale-Free Networks. Computer Engineering and Applications, 2014, 50(20):10-14.

[11] 趙寒，劉峰，李明.基于度—負載聯(lián)合偏好的無標(biāo)度網(wǎng)絡(luò)局部路由策略[J].上海理工大學(xué)學(xué)報，2008,30(03)：264-270. ZHAO Han, LIU Feng, LI Ming. Local Routing Strategy for Scale-Free Networks based on Degree-Load Joint Preference[J].University of Shanghai for Science and Technology, 2008,30(03): 264-270.

A Local Routing Strategy based on Nodes Dynamic Weights in BA Networks

SUN Ya-qian, ZHANG Da-min, ZENG Cheng, XU Yu-zhu

(School of Big Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025, China)

In order to meet the demand of large-scale communication network, a routing strategy based on local information strategy is proposed. The basic idea is that during the forwarding process of data package, the degree and capacity of neighbor node is added in a certain proportion to obtain the weight, and the next node is selected according to the weight value. Foruarding capacity of the node is composed of queue length and degree of the node and an adjustment coefficient, and the forwarding capacity could be adjusted in accordance with the generation rate of real-time data package. Simulation results indicate that this routing strategy is of fairly good communication capacity, and by changing the proportionality coefficient,the critical capacity of network could be adjusted, thus to achieve the optimal routing method. Therefore, the node processing capability is in reasonable utilization,and an effective and reliable method for data transmission by local routing in large-scale actual network also provided.

BA network; local routing; degree; betweenness

10.3969/j.issn.1002-0802.2015.11.014

2015-06-08；

2015-09-21 Received date:2015-06-08；Revised date：2015-09-21

貴州省省委組織部項目(TZJF-2011-37)；貴州省合作計劃項目([2012]7002號)；貴州大學(xué)研究生創(chuàng)新基金項目(研理工2015078)

Foundation Item:Cooperative Project of Guizhou Province(TZJF-2011-37);Cooperative Project of Guizhou Province([2012]7002);Graduate Student Innovation Foundation of Guizhou Univerity

TP393

A

1002-0802(2015)11-1275-05

孫雅倩(1990—)，女，碩士研究生，主要研究方向為復(fù)雜網(wǎng)絡(luò)；

張達敏(1967—)，男，教授，主要研究方向為計算機應(yīng)用技術(shù)、網(wǎng)絡(luò)擁塞控制、病毒傳播機制;

曾 成(1989—)，男，碩士研究生，主要研究方向為復(fù)雜網(wǎng)絡(luò)；

徐玉珠(1992—)，女，碩士研究生，主要研究方向為復(fù)雜網(wǎng)絡(luò)。