BA網絡中一種基于節點動態權值的局部路由策略*

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

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

BA網絡中一種基于節點動態權值的局部路由策略*

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

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

為適應大規模通信網絡的路由需求，提出了一種基于BA網絡的局部路由策略。基本思想是在數據包轉發過程中，將鄰居節點的度和發送能力以一定比例加和得到的值作為權值，根據權值大小選擇下一站點。其中，節點的發送能力由節點的數據包隊列長度，節點的度及一個調節系數組成，節點的發送能力可根據實時數據包產生率進行調節。仿真結果表明，該路由策略有較好的通訊能力，通過改變加權算法中的比例系數可以調節網絡的臨界負載量，達到該算法下的最優路由方法，使節點的處理能力得到合理利用，為實際大規模通訊網絡中利用局部路由實現數據傳輸提供了有效可靠的方法。

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

0 引 言

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

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

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

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

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

1 基于節點權值的混合路由策略

1.1 網絡模型

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

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

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

(1)

1.2 路由策略動力學模型

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

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

圖1 BA網絡的節點介數分布

圖2 節點度和介數關系

路由策略具體實現方法如下：

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

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

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

(2)

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

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

(3)

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

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

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

2 仿真結果及分析

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

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

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

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

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

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

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

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

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

3 結 語

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

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

[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] 臧海娟，任彥，薛小平等.復雜網絡環境下的路由方法研究[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] 卓越. 兩層復雜網絡上的動態權重路由策略研究[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] 文宏，樊曉平，張會福等.無標度網絡上的動態局部路由策略設計[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] 趙寒，劉峰，李明.基于度—負載聯合偏好的無標度網絡局部路由策略[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號)；貴州大學研究生創新基金項目(研理工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—)，女，碩士研究生，主要研究方向為復雜網絡。