基于广义对数函数的统一路由策略

周子腾，王　开，裴文江

(东南大学 信息科学与工程学院，江苏 南京 210096)

基于广义对数函数的统一路由策略

周子腾，王开，裴文江

(东南大学 信息科学与工程学院，江苏 南京 210096)

摘要：通过对最短路径路由策略、有效路由策略、最小信息路径路由策略的算法以及对广义对数函数进行研究发现，将广义对数函数内的变量进行部分修改可实现上述3种算法的统一，并且通过对此种统一算法进行改进和仿真得出，在此统一算法变量连续变化的同时，某些路由策略在复杂网络中的表现同样具有连续性。该算法可以将3种路由策略进行完美的统一，同时可以根据所需的某种路由策略效果在可变化的连续范围内进行参数选择，大大增加了路由策略的可操作性。

关键词：统一路由策略；复杂网络；负载传输；网络容量

现实生活中存在各种各样的复杂网络，它们无处不在，由各种实体间的错综复杂的关系构成，其既可以是有形的，也可以是无形的[1]；同时，具有多种特性。近几年来，随着因特网等各种大规模复杂网络的出现，社会对于网络的依赖性不断增强，因此，如何提高现实复杂网络的传输性能以及实现负载的高效传递已经成为研究领域里的一个重要课题。尽管现实复杂网络的形式多种多样，但均可将其看作节点间的联系的集合，这时信息在节点间如何传递关系到网络的传播速度与效率；因此，复杂网络最佳路由策略问题在复杂网络研究领域占有重要的地位。

普遍从2个方面对如何提高复杂网络的传输性能进行研究，分别是最大限度地优化网络拓扑结构以及提出更好的路由策略，但是，对于现实生活中已知的复杂网络来说，改变其拓扑结构需要比较大的开销；因此，研究工作更倾向于如何寻找更加合适的路由策略来增加复杂网络的传输效率。其中，最短路径路由策略(SP)、有效路由策略(ER)和最小信息路径路由策略(MIP)为当前使用率较大的3种路由策略。最短路径路由策略具有传输时间短和效率高的特点，但研究发现，在此种路由策略下，无标度网络节点度的异构性导致节点介数的强异构性，容易使部分高介数节点出现信息拥塞现象；有关文献提出有效路由策略，即在节点处理能力相同的情况下，将网络中负载从核心节点分散给网络的边缘节点，虽然平均传输路径有所提高，但网络的传输负载能力提高10倍以上；最小信息路径路由策略则中和了前2种路由策略的优点，在相对于SP路由策略减少对网络中度值大的节点的使用率的同时，相对于ER路由策略降低了其网络平均路径长度，在增大网络容量的同时提高了网络的传输效率。

通过对上述3种路由策略算法的研究以及对广义对数函数的研究发现，将广义对数函数进行一些变化，可实现这3种路由策略算法的统一，同时发现，此统一算法中的变量在某一范围内变化时，同样表现出相同的路由效果，且此种变化效果具有连续性。

1统一路由策略

现实生活中有许多复杂网络，研究者发明了多种网络模型对现实中的网络进行仿真，有随机ER网络、小世界WS网络，无标度BA网络等，同时，为了实现复杂网络中数据的有效快速传输，多种路由策略又被相继提出，其中基于广义对数函数的统一路由策略将各个路由策略进行了统一。

1.1基于广义对数函数的统一路由策略

广义对数函数的表达式如下

(1)

当将式1中的w用网络节点的度ki替换后可得：

(2)

式中，ki是复杂网络中节点的度，假设vs≡v0,v1,…,vn-1≡vd为从源节点vs到目的节点vd之间的任意一条路径，则统一路由策略如下：

(3)

将式2带入式3中可得：

p(l:vs→vd)=

(4)

从式4可以看出，当r=0时：

(5)

式5为求从源节点vs到目的节点vd路径之间所经过节点的度值连乘积的最小值，即为最小信息路径路由策略；而当|r|=1时有：

(6)

由此可见，此种基于广义对数函数的统一路由策略是将最小信息路径路由与有效路由策略有效地结合到一起，当r=0时，为最小信息路径路由策略；当|r|=1时，为网络传输效率较高的有效路由策略。

1.2改进的统一路由策略

对式4进行分析得出，式4是最小信息路径路由策略与有效路由策略的集合，但此时|r|的取值范围为0≤|r|≤1，若将|r|的取值范围变为|r|≥0，式4变为如下形式：

p(l:vs→vd) =

(7)

式中，ki是复杂网络中节点的度，vs≡v0,v1,…,vn-1≡vd为从源节点vs到目的节点vd之间的任意一条路径，式7即为改进的统一路由策略。

当r=0时，为最小信息路径路由策略；当|r|=1时，为网络传输效率较高的有效路由策略；对于式7，当r→-∞时，设存在值-A，-A足够小，即A取值足够大时可得：

(8)

此时，由于A为某一足够大的定值，同样可以将1/A看作某一定值，策略变为求路径所经边数的1/A倍的最小值，所以当r取某趋向于负无穷的值A时，统一路由策略变为最短路径路由策略，目的是为了寻找从源节点到目的节点间跳数最少的路径。

由此可见，经过改进的基于广义对数函数的统一路由策略更好的将最短路径路由(SP)策略、有效路径(ER)路由策略、最小路径信息(MIP)路由策略统一在一起，并且当r=0时，为最小信息路径路由策略；当|r|=1时，为网络传输效率较高的有效路由策略；当r→-∞时，为最小路径策略。

2统一路由策略的离散特征

上述介绍了基于广义对数函数的统一路由策略、改进的统一路由策略以及策略的具体实现方法，本节通过对式7中r值的变化进行仿真，主要探索在r=-20、r=0和r=1时统一路由策略所表现出的特征以及当统一路由策略表现为各种不同的路由策略时，这些特征有何区别以及有何意义。

2.1r→-∞时的仿真结果

对于统一路由策略，当r→-∞时，表现为最短路径路由策略特征，在此处取r=-20，经过计算路由表仿真得到此时网络的平均路径长度为4.16，路由计算时间为12分2秒，图1所示为此时统一路由策略下网络中节点度与度平均介数之间的关系，图中横坐标为网络中的不同度值，纵坐标为网络度值对应的度平均介数。

图1　r=-20条件下节点度与度平均介数之间的关系图

通过仿真得出的结果与之前研究者发现的最短路径路由策略下网络的表现一致，这充分说明了统一路由策略在r=-20时可看作最短路径路由策略。

2.2r=0时的仿真结果

对于统一路由策略，当r=0时，表现为最小信息路径路由策略，经过路由表仿真得到此时网络的平均路径长度为4.7，路由计算时间为8分34秒。

经仿真发现网络中的节点度值与度平均介数成正比关系，网络在r=0时的统一路由策略下的表现与之前最小信息路径路由策略一致，这表明统一路由策略在r=0可以看作最小信息路径路由策略，且传输效率以及网络容量均高于r=-21时的统一路由策略。

2.3r=1时的仿真结果

对于统一路由策略，当r=1时，表现为有效路由策略，经过路由表仿真得到此时网络的平均路径长度为7.15，路由计算时间为12分2秒，图2所示为此时统一路由策略下网络中节点度与度平均介数之间的关系，图中横坐标为网络中的不同度值，纵坐标为网络度值对应的度平均介数。从仿真结果可以看出，根据实现方法计算得出的平均路径长度为7.15，比r取-20和0时明显增大，这是因为此种策略大大提高了边缘节点的利用率，同时减少了度值大的节点的使用，使得网络中的路由路径大都在网络边缘行走，使整个网络的平均路径长度大大提高，路由计算时间为12分钟2秒，此路由时间与r取-20时一样，这是因为在r≠0时，路由策略使用的计算方法为同一公式，这使2种方法计算时间一样，与当初预想一致，从图2还可以看出，此时路由策略对度值小于12的节点的利用率逐渐提高，在12左右达到最大利用率，然后随着度值的增大，利用率逐渐减小。

图2　2r=1条件下节点度与度平均介数之间的关系图

经仿真分析可知，网络在r=1时的统一路由策略下的表现与之前分析的有效路由策略一致，这表明统一路由策略在r=1可以看作有效路由策略，且在约束复杂网络中节点度的最大值的情况下，网络容量要低于r=0时的统一路由策略下的网络容量。

3结语

此种统一策略实现了SP路由策略、MIP路由策略以及ER路由策略的完美统一。仿真发现，当r→-∞时，统一路由策略表现为最短路径(SP)路由策略；当r=0时，网络表现与最小信息路径(MIP)路由策略的表现一致，网络中的节点度与节点度平均介数呈现正比关系；当r=1时，统一路由策略下的复杂网络表现出有效路由(ER)策略控制下的特点，此时网络加强了对边缘小度值节点的使用，有效保护了度值较大的节点，网络的平均路径长度最小，网络传输性能最佳。

参考文献

[1] 李艳芳.多层网络中基于资源优化的配置方式[J].新技术新工艺，2014(9)：91-93.

责任编辑李思文

Unified Routing Strategy based on Generalized Logarithmic Function

ZHOU Ziteng, WANG Kai, PEI Wenjiang

(School of Information Science and Engineering, Southeast University, Nanjing 210096, China)

Abstract:From the research of the shortest path routing strategy, efficient routing strategy, the minimum information path routing strategy and generalized logarithmic function, it was found that if modified the variables of generalized logarithmic function, the function can be the unity of the mentioned routing strategy algorithms before, and it was also found that by improving and simulating the unified algorithm, when the variables in the algorithm changed, the performance of some routing strategies changed at the same time. This Phenomenon showed that the unified routing strategy can not only combine the three routing strategy, but also can provide the function that made it possible to choose the appropriate parameters to get the expectant results, in other words, it enhanced the maneuverability of routing strategies.

Key words:unified routing strategy, complex networks, traffic transmission, network capacity

收稿日期：2014-12-03

作者简介：周子腾(1990-)，男 ,硕士研究生，主要从事复杂网络等方面的研究。

中图分类号：TP 393

文献标志码：A