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

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

BA網絡中一種基于節(jié)點動態(tài)權值的局部路由策略*

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

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

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

BA網絡;局部路由;度；介數

0 引 言

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

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

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

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

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

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

1.1 網絡模型

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

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

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

(1)

1.2 路由策略動力學模型

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

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

圖1 BA網絡的節(jié)點介數分布

圖2 節(jié)點度和介數關系

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

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

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

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

(2)

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

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

(3)

式中，η(R)是網絡中數據包總量的變化率，該算法中的C是節(jié)點在單位時間內傳送數據包個數的平均值。

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

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

2 仿真結果及分析

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

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

圖3 系數a與臨界新增負載量Rc的關系

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

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

圖4 R

圖5是α=0.5，R

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

圖6是在α=0.1，R

圖6 α=0.1 R

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

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

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

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

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

3 結 語

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

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

[1] 陳華良，劉忠信，陳增強等.復雜網絡的一種加權路由策略研究[J].物理學報,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] 劉偉彥，劉斌.基于局部路由策略的復雜網絡擁塞控制[J].物理學報，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] 臧海娟，任彥，薛小平等.復雜網絡環(huán)境下的路由方法研究[J].計算機應用，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] 楊珉，張家玥，張達敏. 復雜網絡拓撲結構的網絡模型研究綜述[J].通信技術，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] 王翠君,王紅. 復雜網絡的研究進展綜述[J].計算機與信息技術,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] 王小凡.基于復雜網絡的擁塞避免策略研究[D].西安：西安電子科技大學 ,2013. WANG Xiao-fan. Rasearch of Congestion Control based on Complex Networks[D].Xi’an: Xidian University,2013.

[7] 劉倩星，張達敏.基于混合信息的復雜網絡路由策略研究[J].計算機工程與設計，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] 卓越. 兩層復雜網絡上的動態(tài)權重路由策略研究[J]. 計算機應用研究,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] 王丹.復雜網絡擁塞分析與路由策略研究[D].遼寧：東北大學,2002. WANG Dan. Analysis of Congestions and Rounting Strategies of Complex Networks[D].Liaoning: Northeastern University,2002.

[10] 文宏，樊曉平，張會福等.無標度網絡上的動態(tài)局部路由策略設計[J].計算機工程與應用，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)合偏好的無標度網絡局部路由策略[J].上海理工大學學報，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號)；貴州大學研究生創(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—)，女，碩士研究生，主要研究方向為復雜網絡；

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

曾 成(1989—)，男，碩士研究生，主要研究方向為復雜網絡；

徐玉珠(1992—)，女，碩士研究生，主要研究方向為復雜網絡。