基于混合信息的复杂网络路由策略研究

刘倩星，张达敏（贵州大学 计算机科学与信息学院，贵州 贵阳550025）

0 引 言

在现实世界中复杂系统无处不在，复杂网络能够很全面地描述复杂系统，因此复杂网络已经成为一种广泛用于分析复杂系统的重要工具［1］。自从 Watt－Strogatz提出小世界模型和Barabási－Albert提出无标度模型开始，研究者对复杂网络产生了浓厚兴趣，自此掀起了研究复杂网络的热潮［2－3］。近年来，复杂网络在各个领域都取得了很大进展，如信息传输，疾病传播，交通，能源等方面［4－16］。

现代社会中，互联网、万维网、点对点网络和其它通信网络发挥着越来越重要的作用。随着人们对这些大规模甚至超大规模网络依赖性的不断增强，网络中的交通动力学特性逐渐引起人们的关注。为了使通讯网络更有效的发挥其功能，必须保证信息流处于自由通畅状态。因此，缓解网络中信息交通拥塞和提高通讯网络的效率成为研究的重点。该领域的研究工作则主要围绕着两个方面展开，一是改变通讯网络的网络拓扑结构，二是研究更优化的路由策略。由于改变网络拓扑结构的成本较高且不易实现，所以研究者在寻找更优化的路由策略方面投入了更多精力。目前，在路由策略方面已经取得了较大进展，研究人员提出了不少优良的路由策略，如随机路由策略［4－5］、最短路径策略［6］、有效路径策略［7－8］、邻域搜索和次近邻搜索策略［9－12］等。臧海娟等人对这些路由策略进行了总结。大致分为3类：基于全局信息的路由方法，基于局域信息的路由方法和基于混合信息的路由方法［13］。这些路由策略在一定程度上提高了通讯网络的路由效率，然而由于通讯网络的规模不断增大采用全局信息的路由策略愈加难以实现，基于局部路由策略的信息虽适用于大规模网路，但是没有充分利用网络中各种信息，因此为了更好地提高通讯网络的路由效率，研究人员又将网络中各种特性信息进行综合考虑，提出了混合路由策略。

对于一个通讯网络，提高路由效率，保持网络中的信息流处于通畅状态至关重要。由于网络规模的不断增大和网络中的信息量的增大可能会导致网络交通拥塞甚至网络系统的崩溃，因此研究如何缓解网络交通拥塞具有重要意义。基于这个思想，本文以无标度网络为模型建立了一种新的混合路由策略。该策略中假定结点传递能力等于结点的度，将局域结构的静态信息与交通拥塞的动态信息结合在一起综合考虑，并以优化的信息包传递概率向邻域结点传递。文章对这一新的混合路由策略进行研究，仿真结果表明通讯网络的交通路由效率得到了显著提高，有效缓解了交通压力。

1 路由策略

1.1 BA无标度模型

近年来，大量研究证明INTERNET、WWW等通讯网络并不是像随机网和规则网那样均匀，而是度分布遵循幂律分布P （k）～k－r的非均匀系统［3］。Barabási－Albert提出的BA无标度模型对此进行了很好的阐述。与其它模型相比，BA无标度网络最大的特点是：网络增长和优先连接特性［3］。其构造算法如下：

（1）增长：从一个具有m0个节点的网络开始，每次引入一个新的结点并且连接到m个已存在的结点上，且m＜m0。

（2）优先连接：一个新结点与一个已经存在的结点i相连接的概率Pi与结点i的度ki、结点j的度kj之间满足

BA无标度网络模型具有较短平均路径长度和较低聚类系数，其度分布可以由幂指数为3的幂律函数来近似描述，如图1所示为网络规模为N＝5＊104的BA无标度网络的度分布。

图1 BA无标度网络的度分布 （N＝5×104）

1.2 混合路由动力学模型

为了使网络模型能够反映真实通讯网络的特性，本文采用初始网络中结点个数m0＝5、网络规模N＝1000的BA无标度网络为通讯网络的模型。具体路由策略如下：

（1）在每一时步，网络中有R个信息包产生，并需要从其源结点传送到目的结点。其中，源结点和目的结点都是随机选取的，但是一经选定就不能再改变。每一结点既是产生信息和接收信息的服务器终端，又是中介传递信息的路由器。

（2）在每一时步，每个结点向其邻域结点传递的信息包个数最多为Ci。由于现实网络中各结点的传递能力是不同的，因此假定每一结点的传递能力为：Ci＝ki。ki是结点i的连接度。而不是仅仅将Ci设定为某一常数。采用变化的Ci能更好的体现真实网络的特点。

（3）采用对每一结点的最邻近邻域结点进行局域搜索的策略，如果在直接邻域结点范围内搜索出信息包的目的地，则将信息包直接传递到该目的地，否则，以优先概率

将信息包传送到其邻域结点。这里ki是结点i的连接度，α是一个可调的参数，Ni是结点i的排队队列长度，Ci是结点i的传递能力。Ni＋1是为了保证结点处信息包个数不为0。

（4）为了避免网络中的信息包无目的的游荡，采用路径重复避免规则 （path iteration avoidance，PIA），即任何一对结点之间的连边不能够被同一个信息包访问二次以上。采用这种规则能够避免同一信息包在同一连边上毫无必要地反复访问多次而使网络的通讯能力变的极低。

（5）该路由策略中假定每一结点处等待传递的队列长度可以为无限长。也就是等候发送的信息包数目可以是无限的。这些排队的信息包按照先进先出 （first in first out，FIFO）的规则按次序传递［14－16］。

通讯网络最重要的是整个网络对于信息包的处理和传递能力。在这个新的路由策略中，设定单个结点的通讯能力为Ci，且令Ci等于其连接度ki。而整个通讯网络的通讯能力用临界的信息产生率Rc来度量。Rc是网络从自由交通态到拥塞交通态的临界点。当R＜Rc时，网络处于自由交通态。而当R＞Rc时，网络处于拥塞交通态。

为了更准确的描述网络状态变化，本文采用如下序参数［16］

式中：C——结点的平均传递能力，R——网络的信息包产生率，ΔNp＝Np（t＋Δt）－Np（t），表示从t时刻到t＋Δt时刻系统中增加的信息包数目。＜…＞表示对于时间窗口Δt求平均。当R＜Rc时，＜ΔNp＞＝0且η＝0，即网络处于自由交通态。而当R＞Rc时，＜ΔNp＞＞0且η＞0，即网络处于拥塞交通态。所以当R＝Rc时，网络通信能力最大。显然临界信息包产生率Rc能很好的度量网络的最大通讯能力。η从0到大于0的突变，说明网络从自由态进入了交通拥塞态。

2 仿真实验及结果分析

2.1 通讯网络的路由效率分析

通讯网络的路由效率可以用网络的通讯能力和信息包的平均传输时间度量。首先，在这一新的路由策略下对通讯网络的通讯能力进行了研究。从图2中可以看出当R＜Rc时，对于不同的α序参数η＝0。随着R不断增大到R＝Rc时，序参数η骤然变为一个大于0的常数。这一相变反映了网络从自由交通态进入了拥塞交通态。图3表明：在不同的搜索策略值α下，网络的通讯能力Rc是不同的。在新的路由策略下，网络的最大通讯能力Rc在117左右且此时α＝－4。当α从1减小到－4的过程中，网络的通讯能力Rc逐渐增大且当α＝－4时达到最大值。然而α继续减小，网络的通讯能力Rc则减小且逐渐趋近于某一特定值。在以往的路由策略中往往设定结点的传递能力Ci为某一常数。例如文献 ［15］中令Ci＝10，此时网络的通讯能力Rc近似为30。采用新的路由策略，网络的通讯能力最大值在117左右，可见网络的通讯能力得到了明显提高。

在图4中可以看到网络中的信息包总数Np（t）随着α的减小而逐渐增大。而在图3中，当α＜－4时临界信息产生率Rc逐渐减小到一个特定值，所以当网络中的信息包数目较少且网络通讯能力较大时整个网络中达到平衡态所用时间最少。对图3和图4进行综合考虑可以得出当α＝－4时通讯网络达到自由稳态用时最少。由于通讯网络的交通路由效率同时反映在网络通讯能力和信息包的平均传输时间两个关键度量。综上所述，可以得到当α＝－4时通讯网络的交通路由效率达到最大。

图4 网络中的信息包数目Np（t）与α的关系，N＝1000

2.2 自由态动力学分析

自由交通态是在通讯网络中同一时步内新产生的信息包数目与到达目的结点被移除网络的信息包数目相抵消，最终达到稳定状态。图5中可以看出R＜Rc时，开始时信息包处于增长状态，但是经过足够长的时间，网络中产生的信息包和到达目的结点被移除网络的信息包相抵消，最终达到稳定状态，系统处于自由稳态。从图6（a）中可以看出当系统处于稳态时，度k较小的结点处聚集着较多的信息包，而当k继续增大，则网络中的信息包分布较均匀，这样在一定程度上可以减少网络拥塞的发生。

图5 R＜Rc时不同α下网络中信息包数目变化

2.3 拥塞态动力学分析

当信息包产生率R等于临界值Rc时，序参数η发生一个明显相变，通讯网络由自由交通态转为拥塞交通态。拥塞交通态是指存在于网络中的信息包数量处于持续增长状态，网络中大部分信息包不断滞留积累于系统中，最终导致系统的交通拥塞甚至瘫痪。图7中可以看出当R＞Rc时，无论时间如何增加，处于网络中的信息包数目一直处于增长状态，大量信息包滞留于系统中，网络此时处于拥塞交通态。当α＞0时，图8（a）显示度较小的结点承担着巨大的信息包，由于结点的传递能力又与其度相等，所以网络中的信息包不能及时得到传递，容易造成信息包滞留积累于网络中，最终将导致网络拥塞。而当α≤0时，从图8（b）中可以看到连接度大的结点承担着较大的信息包数目，由于结点传递能力有一定限度，所以少数连接度大的结点处会首先出现过度的信息包积累，从而造成系统拥塞。因此为了有效缓解通讯网络的交通拥塞可以提高结点的传递能力。从图9中可以看到在某一α下，已经处于拥塞态的网络中信息包变化率ΔNp/Δt与信息产生率R近似成正比关系，网络的路由效率也受到信息包产生率的影响。但是为了更加清楚的体现其规律，本文对ΔNp/Δt与临界值偏离R－Rc的关系进行了研究，图10是将所有曲线平移到一个近似的起点得到的二者的关系。从图中可以发现，正的α值的交通负荷增长速度明显高于负的α值，α越大网络中的信息包数量就增长的越快。而处于拥塞态的通讯网络最大通讯能力逐渐减小到固定值107，网络的路由效率会随信息包产生率的增加而减小。因此当信息包产生率R逐渐增大到Rc时网络的通讯能力最大。

图6 R＜Rc时度为k的结点处平均信息包数目变化

图7 R＞Rc时不同α下网络中信息包数目变化

3 结束语

本文提出了一种基于混合信息的路由策略，该策略充分利用了网络中的动态和静态信息，将结点传递能力Ci设定为与结点度成正比关系的变量，而不是单纯固定为某一特定值，这样更加接近现实的网络，同时以更加优化的信息包传递概率向下一结点传递信息。经过仿真实验证实该路由策略明显的提高了通讯网络的路由效率。同时对自由和拥塞态下的交通动力学进行了研究，仿真结果表明：对于同一α处于拥塞态的网络中ΔNp/Δt与信息产生率R近似成正比关系，正的α值的交通负荷增长速度明显高于负的α值且α越大网络中的信息包数量就增长的越快，较大的结点传递能力及合理的信息产生率可以有效缓解通讯网络的交通拥塞。

图10 R＞Rc时不同α下ΔNp/Δt与R－Rc的关系

［1］L Lin yuan，JIN Ci hang，ZHOU Tao.Similarity index based on local paths for link prediction of complex networks［J］.Physical Review E，2009，80 （4）：046122.

［2］LI Guo，GAO Jianmin，GAO Zhiyong.Safety analysis of complex system based on small world topological model ［J］.Chinese Journal of Mechanical Engingeering，2008，44 （5）：86－91（in Chinese）.［李果，高建民，高智勇.基于小世界拓扑模型的复杂系统安全分析 ［J］.机械工程学报，2008，44（5）：86－91.］

［3］Michele Catanzaro，Marián Bogu á，Romualdo Pastor－Satorras［J］.Physical Review E，2005，71：027103.

［4］Alessandro de Moura P S.statistics and traffic in complex networks［J］.Physical Review E，2005，71 （6）：066114.

［5］ZHANG Yingbin，SHI Haomin，LU Xuanmin.Risk Indexbased stochastic routing strategy ［J］.Computer Engineering and Applications，2005，41 （29）：130－133 （in Chinese）.［张迎宾，史浩山，卢选民.基于风险指数的随机路由策略［J］.计算机工程与应用，2005，41 （29）：130－133.］

［6］ZHAO Liang，LAI Ying cheng，YE Nong，et al.Onset of traffic congestion in complex networks ［J］.Physical Review E，2005，71 （2）：026125.

［7］YAN Gang，ZHOU Tao，HU Bo，et al.Efficient routing on complex networks ［J］.Physical Review E，2006，73（4）：046108.

［8］YU Gang，WANG Xianpeng，LU Hongtao.Efficient routing strategy on scale－free networks ［J］.Modern Physics Letters B，2009，23 （11）：1377

［9］HU Maobing，WANG Wenxu，JIANG Rui，et al.Phase transition and hysteresis in scale－free network traffic ［J］.Physical Review E，2007，75 （3）：036102.

［10］WANG Wenxu，WANG Binghong，ZHOU Tao.Traffic dynamics based on local routing protocol on a scale－free network［J］.Physical Review E，2006，73 （2）：026111.

［11］ZHAO Han，LIU Feng，LI Ming.Local routing strategy for scale－free networks based on degree－load joint preference ［J］.Journal of University of Shanghai for Science and Technology，2008，30 （3）：264－270 （in Chinese）. ［赵寒，刘峰，李明.基于度－负载联合偏好的无标度网络局部路由策略 ［J］.上海理工大学学报，2008，30 （3）：264－270.］

［12］WANG Binghong，WANG Wenxu.Routing strategies in traffic network and phase transition in network traffic flow ［J］.Indian Academy of Sciences，2008，71 （2）：353－358.

［13］ZANG Haijuan，REN Yan，XUE Xiaoping.The routing strategy study on complex networks ［J］.Journal of Computer Applications，2010，30 （8）：2210－2213 （in Chinese）. ［臧海娟，任彦，薛小平.复杂网络环境下的路由方法研究 ［J］.计算机应用，2010，30 （8）：2210－2213.］

［14］WANG Xianpeng，YU Gang，LU Hongtao.A local information based routing strategy on the scale－free network ［J］.Modern Physics Letters B，2009，23 （10）：1291.

［15］WANG Wenxu，YIN Chuanyang，YAN Gang.Integrating local static and dynamic information for routing traffic ［J］.Physical Review E，2006，74 （1）：016101.

［16］YIN Chuanyang，WANG Binghong，WANG Wenxu.Efficient routing on scale－free networks based on local information［J］.Physics Letters A，2006，351 （4－5）：220－224.