BA网络中一种基于节点动态权值的局部路由策略*

2015-03-25孙雅倩张达敏曾成徐玉珠

通信技术 2015年11期

关键词：介数负载量权值

孙雅倩，张达敏，曾成，徐玉珠

(贵州大学大数据与信息工程学院，贵州贵阳 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

1002-0802(2015)11-1275-05