随着科学技术的进步，交通网、航空网和互联网等正逐渐成为人类社会重要的组成部分.若将交通网中的信号灯^[1]、航空网中的机场^{[2, 3]}、互联网中的设备^[4]视为节点，把信号灯间的公路、机场间的航线和设备间的通信线路视为边，那么将汽车、飞机和报文分组视作数据包也会变得容易理解.实际上，在经过一定抽象后，以上网络均呈现出包交换网络性质.这些网络的规模不断增大，复杂程度也急速升高，拥塞现象时有发生.如今，拥堵的交通枢纽、繁忙的机场、高时延的节点等，正影响着人类生活的方方面面，包交换网的拥塞控制问题也受到了越来越多的关注^{[5, 6, 7, 8]}.

由于包交换网的复杂性，传统研究手段难以为继，因此采用复杂网络理论研究包交换网成为一些学者的新思路^{[2, 3, 4]}.Barabasi等^[9]提出了BA无标度网络模型，Arenas等^{[10, 11]}提出了分层网络模型，Tang等^[12]提出网络流量传输模型.在此基础上，对包交换网的拥塞问题展开研究，Yan等^[6]提出有效路径策略，Janaki等^[8]提出基于有向二维网格模型的拥塞控制策略.本文采用复杂网络相关研究方法，利用包交换网的静态属性和动态特性，在仿真环境中对包交换网路由策略进行了研究，旨在缓解网络拥塞现象，最终提升网络效率.

目前实际网络普遍采用最短路径路由策略(shortest path strategy,SPS)，在该策略中，数据包会选择源节点i和目的节点j间节点数最少的路径作为传输路径.该策略可以使数据包的转发次数最少，但会使度值较大、且有多条最短路径经过的“中心节点”^[13]被大量数据包竞争访问，为此，从网络静态属性角度对网络拥塞进行研究.

由于“中心节点”通常是对拥塞最敏感的节点，改善网络拥塞的一种有效方法是把中心化程度高的节点上的数据包转发请求分散到中心化程度低的节点上去.基于这样的思想，Yan等^[6]提出了有效路径路由策略(efficient path strategy,EPS).在该策略中，节点i和节点j之间的所有可能的传输路径定义如下：

而节点i和节点j之间的有效路径则定义为

其中：x_i为节点编号;k(x_i)为节点x_i的度值；可调参数β是不小于0的实数.该策略选择和值最小的路径.当β>0时，“中心节点”上的数据包被重新分配，降低了拥塞概率.Yan等发现，有效路径策略比最短路径策略性能更优.

本文受布雷斯悖论在传输网络中减少某些资源可能有利于流量均衡的思想启发，对“中心节点”资源和网络拥塞之间的关系进行了研究.在研究过程中，本文借鉴了张国清等^[7]的研究成果，提出了基于边权路由策略(edge weight strategy,EWS).在该策略中，数据包的传输路径由下式确定：

其中:i，j为数据包的源节点和目的节点;x_s，x_s+1为与边相关联的两个节点;k(x_s)为节点x_s的度值;0≤α≤0.9,0≤β≤1.0，两者为可调参数，其较优值在后文确定.为了突出与大度值节点相关联的边，使数据包可以更好地绕过“中心节点”，本文规定β≥α≥0.基于边权策略给与“中心节点”相连的边赋较大权值，降低了这些边被访问的概率，就如同减少了“中心节点”的访问资源，根据布雷斯悖论可知，该方法有可能提升网络的性能.在仿真实验中，将对其有效性进行验证.

本文采用BA无标度模型^[9]对实际网络进行模拟，并采用Tang等^[12]的网络流量传输模型对网络流量进行仿真.在评价指标方面，本文采用Arenas等^[11]提出的评价指标,其计算公式如下：

其中：W(t)为t时刻网络现存数据包总数；R为单位时间内新生成数据包数.若H近似为0，说明随着数据包进入网络，数据包能够被及时消化，网络没有发生拥塞；如果H>0，说明数据包不能被及时消化，网络将发生拥塞.显然，R值越大，网络拥塞的概率越高，因此存在一个临界值R_c：

1) 当R < R_c时，数据包能够被及时消化，此时H≈0，网络处于稳定状态，网络传输效率较高；

2) 当R>R_c时，数据包不能被及时消化，发生网络拥塞，平均传输时间增加，网络传输效率较低.

由此可知，R_c越大，意味着网络消化数据包的能力越强，发生拥塞的概率越小，网络效率也越高.

图1是在α,β取不同值条件下R_c的取值情况，本文采用BA模型(N=1000)进行了50组实验，每次实验中模型的拓扑结构都是不相同的，图中R_c为50组实验结果的平均值.如图所示，随着α,β的调整，R_c在图中峰顶圆环区域取得较优值.本文选取其中一组值R_c (0.5,0.7)=100作为α,β的值.

图 1(Figure 1)

Fig. 1

图 1 最优解分布图 Fig. 1 optimal values distribution

图2给出了有效路径策略和基于边权策略在不同网络规模N下的R_c.当网络规模较小时，两种路由策略的性能大致相同；随着网络规模的增大，后者比前者性能提升更加明显，可以更大程度地提高网络的传输效率.由此可知，基于边权路由策略在降低网络拥塞、提升网络传输效率方面是可行的.

图 2(Figure 2)

Fig. 2

图 2 EPS与EWS不同网络规模下Rc比较 Fig. 2 comparison of EPS and EWS in different network sizes

图3给出了两种路由策略下平均路径长度随网络规模变化情况.两者均随着网络规模的增大而增大，其中基于边权策略可以获得比有效路径策略更短的平均路径长度，这说明该策略可以在回避“中心节点”的同时用更少的跳数把数据包传送到目的节点，这有利于网络传输效率的提升.

图 3(Figure 3)

Fig. 3

图 3 EPS与EWS不同网络规模下平均路径长度比较 Fig. 3 Average path length comparison of EPS and EWS in different network sizes

基于边权策略为静态的全局路由策略，在该策略下数据包的传输路径不能进行动态调整，网络负载分布并不均衡.通常，网络负载分布越不均衡，意味着某些节点上积累的数据包数越多，网络发生拥塞的概率就越高.由此可知，网络拥塞同网络的动态特性，如负载分布情况，同样存在联系.

图4为具有1000个节点的BA无标度网络在三种策略下分别向网络持续发包至拥塞时节点负载的分布情况.图中横坐标为节点度值取对数，纵坐标为节点负载.由图可知，在最短路径策略下，数据包主要聚集在大度值节点处，经统计发现，度值最大的10个节点的负载占总量的84.0%.其他节点上负载分布则比较均匀且总量很小.这说明此时大度值节点是整个网络的传输瓶颈.

图 4(Figure 4)

Fig. 4

图 4 三种策略下数据包分布情况 Fig. 4 Packet distribution under three strategies

而在有效路径策略下，数据包在传输过程中会绕过大度值节点，如图4所示，当网络发生拥塞时，大度值节点负载下降明显，此时度值最大的10个节点的负载仅占整体的2.6%.而负载最大的10个节点的和值也仅为31.5%，两个和值均小于最短路径策略下的结果，即该策略可以使网络负载更均衡.值得注意的是，在该策略下大度值节点上的负载很小，一些本可以更快到达目的节点的数据包不得不选择绕路，对整个网络来说是一种资源浪费.

由上节可知，传统的最短路径策略使得大度值节点上的负载过大，而有效路径策略虽然提升了网络的传输效率，却使得大度值节点上的负载过小.为使网络负载更加均衡，本文利用网络的动态特性，提出了邻节点负载策略( adjacent node load strategy,ANL).在该策略中，会根据当前节点的邻居节点实际情况，动态地选择下一跳的节点，其选路规则如下：

其中：P_(i,j)表示从节点i到节点j的路径；D_(i,j)表示从i到j的最短路径条数；Q_i+1表示当前节点的邻节点负载情况.

观察图4可以发现，在该策略下，网络负载呈现出两个相对独立的区域——大度值区和小度值区.在区域内部，各节点的负载比较均衡；而在区域之间，大度值区比小度值区承担了更多的网络流量.本文统计了负载最大的10个节点的信息，其负载占总量的69.7%.与有效路径策略相比， 大度值节点得到了更合理的利用，而与最短路径策略相比， 所有大度值节点上的负载相对一致，避免了单个节点上存在大量负载的情况出现 .此时的网络负载分布情况更符合实际网络中设备的资源属性.由以上可知，邻节点负载策略可以通过邻居节点负载信息均衡网络负载，降低网络拥塞概率，提高网络的整体性能，使网络传输更加高效.

由前文可知，利用网络静态属性和动态特性可以有效缓解网络拥塞.为此将基于边权策略与邻节点负载策略相结合，提出了一种基于边权与节点负载的联合策略(united routing strategy,URS)，旨在更好解决网络拥塞问题，提升网络传输效率.

联合策略借鉴了基于边权策略，通过边加权的方式绕过拥塞概率高的“中心节点”，同时又借鉴了邻节点负载策略，解决了前者由于是静态策略而造成局部网络负载过高、出现网络拥塞的问题.基于边权与节点负载路由策略的公式化描述如下：

其中：0≤h≤1.0,0≤n≤1.0，为可调参量.式(6)由两部分组成，前半部分为边权和，与基于边权策略类似，x_s,x_s+1为与边相关联的两个节点的编号，k(x_s)为节点x_s的度值，x_s≤x_s+1，0≤α≤0.9，0≤β≤1.0，且β≥α≥0；后半部分为邻节点的负载信息，d_s+1为当前节点的邻节点负载.在联合策略中，本文选取基于边权策略确定的α,β的较优值作为α,β的值，并在此基础上，通过仿真模拟，确定h和n的值.

图5是1000个节点的BA无标度网络在h和n不同组合情况下R_c的取值.本文共进行了50组实验，图5为实验结果的平均值.

图 5(Figure 5)

Fig. 5

图 5 Rc最优解分布 Fig. 5 Rc optimal values distribution

图中横坐标为n，纵坐标为h，两个参数每次 递增0.1.矩形区域内等高线代表R_c的取值范围，在等高线110围成区域内的存在多组较优值.经过试验发现，虽然不同的h，n组合可以取得相同的R_c，但H(R)的增长速度并不相同，如图6所示，h=0.1,n=0.5和h=0.1,n=0.8两组值均能够取得较优的R_c=111，但前者的增长速度更慢，网络恶化的速度也更慢，故本文选择前者作为h，n的取值.

图 6(Figure 6)

Fig. 6

图 6 H(R)分布 Fig. 6 Distribution of H(R)

图7给出了在相同网络规模下(N=1000)，三种策略H(R)的增长情况.由图可知，最短路径策略的网络吞吐率R_c非常小，有效路径策略的R_c取值比前者提高了十几倍，这与Yan等^[11]得出的结论一致，而联合策略的R_c取值更大.这说明最短路径策略极容易导致网络拥塞，有效路径策略降低了网络拥塞概率，因而大幅提高了网络的吞吐率，而联合策略吸收了有效策略的优点，在拥塞控制、提升网络传输效率方面更优秀.此外，当R>R_c时，联合策略H(R)的增长速度最慢，这也说明网络拥塞时，采用联合策略的网络环境恶化的速度最慢.

图 7(Figure 7)

Fig. 7

图 7 三种策略下Rc比较 Fig. 7 Rc comparison under three strategies

图8为相同网络规模下(N=1000)三种策略发生拥塞时的负载分布情况.横坐标为节点度值，纵坐标为相同度值节点负载的平均值.由图可知，最短路径策略下大度值节点负载过大，并且负载与度值呈现出近似的指数关系.有效路径策略下大度值节点负载过小，大度值节点没有得到充分利用，造成了资源的浪费.与之相比，联合策略充分利用了大度值节点，使其上的负载适当，该策略使网络负载相对均衡，有利于回避网络拥塞.

图 8(Figure 8)

Fig. 8

图 8 联合策略下数据包分布 Fig. 8 Packet distribution under URS

4 结 语 本文运用复杂网络的相关研究手段，从网络的静态属性和动态特性角度对包交换网的拥塞现象进行了分析.根据网络的静态拓扑信息，提出了基于边权策略，该策略通过回避网络中的“中心节点”来降低拥塞概率；又根据节点的动态负载 信息，提出了邻节点负载策略，该策略可以在网络转发请求较多时降低拥塞的概率，同时可以使网络负载更符合设备的资源属性.在以上两种策略基础上，提出了基于边权与节点负载的路由策略.与传统策略相比，本文策略在缓解网络拥塞、提升传输效率方面更优，具有一定的实用价值.