随着信息技术的飞速发展，人们的生活被各种网络包围着，包括e-mail网络^[1]、电话网络^[2]、电力网络^[3]、飞机航线网络^[4]、交通网络^[5]、因特网和万维网^[6-7]等。1998年，文献[3]提出了小世界网络模型，进一步，文献[8]提出了无标度网络的模型，对实际的复杂系统进行网络建模。现代社会处在一个大数据、大流量的时代，高度依赖于这些网络系统的正常高效运行。然而，在处于拥塞的情况下，这些网络的传输效率会大大降低并可能造成网络系统的瘫痪，极大地影响人们的工作与生活。所以，研究如何提高这些网络的传输效率从而避免拥塞，具有很重要的现实意义。

以计算机网络中的信息传递为例，通常，当网络中节点(边)的负荷超过了它们的容量(带宽)时，信息拥塞就会发生。学者们通过研究网络中的路由传输策略对网络进行优化，进而提高网络的传输效率。根据目前的研究，学者们首先从宏观角度将路由传输策略分为基于网络结构和基于动力学的路由策略两大类。进一步，根据网络结构的类型，基于网络结构的路由策略又可被划分为基于节点和边信息的路由策略以及改变拓扑结构的路由策略。同时，基于动力学的路由策略又可以按照是否改变传播路径细分为路径选择策略以及排队策略。目前的路由策略中有一些具有重要影响，例如，文献[9]首次提出按度分配节点的容量，开启了容量分配策略的先例，学者们自此开始考虑赋予各节点不同的传输数据包的能力。文献[10]提出了改变拓扑结构的路由策略，通过删减网络中的关键连边实现网络的优化。这类策略虽然操作简单，但有时实用性不高。文献[11]首次提出了一种高效的路径选择策略，主张数据包应尽量避开hub节点而选择边缘节点进行传输。在这个策略的启发下，学者们开始关注到边缘节点的重要性，但hub节点本身具有的很高的传输能力没有得到充分利用。文献[12-13]认为网络吞吐量的大小取决于网络中节点的最大介数，因此提出了一种路径选择策略使网络中节点的最大介数值达到最小。虽然这种策略下网络的吞吐量得以提高，但是计算复杂度却很高。文献[14-15]提出了基于局部信息的路径选择策略，只需要了解网络的局部信息即可实现优化，因此对于一些实际的大型网络更具有实用价值。学者们还从节点处数据包传递顺序的角度出发，提出了一系列排队策略，使节点处的数据包按照一定规则有序传递，降低了网络中数据包的平均传输时间。

理解并研究复杂网络上的路由策略、控制网络拥塞，是急需处理的重要问题之一。因此有必要对网络中的路由传输策略进行全面回顾与分析。目前关于网络路由传输的综述中，文献[16]通过模拟和仿真无标度网络和均匀网络上的交通状况，系统地研究了网络传输的一系列统计特性与网络结构之间的关系；文献[17]从整体和局部分别出发，回顾了具有重要意义的路由策略；文献[18]将路由策略划分为“硬策略”与“软策略”，主要回顾了路径选择策略以及网络拓扑结构改变的路由策略。本文对网络的路由传输策略进行了更系统的回顾与分析，对于路由策略的划分更具体细致，介绍更详细全面。本文首先介绍了与这项研究相关的一些基本指标，然后回顾了提高网络传输效率的四类路由策略——基于节点和边信息的策略，改变拓扑结构的策略，路径选择策略以及排队策略，最后提出了网络路由传输策略未来可能的研究方向。

1 基本指标介绍

在网络路由传输策略的研究中，不失一般性，网络中的节点同时被视作主机和路由器，即每个节点都可以产生、传送并且接受数据包。网络中的边可以看作是数据包传递的可能的路径。每单位时间内网络中有$R$个新的数据包产生，这些数据包都随机地选择出发点和终点。到达终点的数据包将会从网络中移除。

以下是网络中的路由传输策略所涉及到的一些基本指标，包括容量、介数、临界值以及序参数，它们可以衡量网络的吞吐状况。

节点$i$的容量${C_i}$是指节点$i$在单位时间内能够传递的数据包的最大数量。以节点$i$和节点$j$为端点的边${l_{ij}}$的容量(也称带宽)${D_{ij}}$是指单位时间内能通过这条边的数据包的最大数量。类似地，一个网络的容量(也称吞吐量)是指这个网络在没有拥塞的情况下所能顺利流通的数据包的最大数量。

介数${g_i}$表征节点$i$在整个网络中的作用和影响力。节点$i$的介数${g_i}$是指网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例^[19]：

${g_i} = \sum\limits_{s \ne t} {\frac{{{\sigma _{st}}(i)}}{{{\sigma _{st}}}}} $

(1)

式中，${\sigma _{st}}$是网络中以$s$为起点，$t$为终点的最短路径的数目；${\sigma _{st}}(i)$是以$s$为起点，$t$为终点并且经过节点$i$的最短路径的数目。

临界值${R_c}$表征一个网络的最大吞吐量。每一单位时间内网络中产生$R$个新的数据包并且当它们到达终点后会被移出网络。在这个过程中存在一个临界值${R_c}$，当$R$ < ${R_c}$时，新产生的数据包和被移出网络的数据包达到动态平衡，使整个网络处于自由流通的状态；当$R$ > ${R_c}$时，由于网络的吞吐量是一定的，新产生的数据包的数量超过了网络本身的流通能力，于是一些数据包会逐渐堆积在节点处，致使网络中出现拥塞的现象。所以，临界值${R_c}$能反映一个网络的最大吞吐量，它是衡量网络吞吐量的直接指标^[11]。而堵塞一般最先出现在网络中介数最大的节点处，因此一个网络的${R_c}$为^{[9, 20]}：

${R_c} = \frac{{CN(N - 1)}}{{{g_{\max }}}}$

(2)

式中，$C$表示节点的容量；$N$指一个网络中所包含的节点的个数；${g_{\max }}$是网络中所有节点的最大介数。

序参数$\eta $表征运输流量状态的转变，当每单位时间内网络中生成$R$个数据包时，$\eta $的定义为^[21]：

$\eta (R) = \mathop {\lim }\limits_{t \to \infty } \frac{C}{R}\frac{{\left\langle {\mathit{\Delta} {N_P}} \right\rangle }}{{\Delta t}}$

(3)

式中，$\Delta {N_p} = {N_p}(t + \Delta t) - {N_p}(t)$，${N_p}(t)$是$t$时刻网络中的数据包的总数量，$\left\langle {\Delta {N_p}} \right\rangle $是$\Delta t$时间内网络中数据包平均增加的数量。当$R$ < ${R_c}$时，网络处于自由流通的状态，$\left\langle {\Delta {N_p}} \right\rangle = 0$，即$\eta = 0$；当$R$ > ${R_c}$时，网络出现拥塞的现象，$\eta > 0$。因此，通过$\eta $可以判断一个网络的临界值${R_c}$的大小。同时，$\eta $还可以作为一个指标来衡量一个网络处理拥塞问题的能力。$\eta $增长越慢，网络对于阻塞的处理能力越强。

网络的传输效率有两个衡量指标，网络的吞吐量以及平均传输时间。网络的吞吐量越大，平均传输时间越短，网络的传输效率就越高。因此，所有的路由传输策略都旨在扩大网络吞吐量和减少数据包的平均传输时间。

2 基于节点和边信息的路由策略

当节点处的数据包数量超过了节点的容量，或者连边处的数据包数量超过了边的带宽时，网络会出现拥塞现象。在广泛应用的最短路径路由策略^[22](shortest path routing strategy)下，阻塞总是首先出现在hub节点处然后再扩散至整个网络。因此，当整个网络的节点总容量一定时，只要分配给hub节点更大的容量就能有效缓解拥塞进而提高网络的最大吞吐量。类似地，当网络中边的总带宽一定时，分配给关键连边更大的带宽也能提高网络的传输效率。

2.1 改变节点处理能力的分配策略

文献[23]提出了按节点度的大小分配容量的模型，即${C_i} = 1 + \beta {k_i}$，其中${C_i}$是节点$i$的容量，${k_i}$指节点$i$的度。在这个模型下，度越大的节点被分配越大的容量。无标度网络上的实验结果表明，与分配给每个节点相同的容量相比，这个模型以较低的成本实现了较大的网络吞吐量。

文献[9]提出了另外两个模型，分别是按节点度的大小以及介数的大小来分配容量。

$模型1: {C_i} = 1 + \operatorname{int} [\beta {k_i}]$

(4)

$模型2: {C_i} = 1 + \operatorname{int} \left[ {\frac{{\beta {g_i}}}{N}} \right]$

(5)

式中，${k_i}$和${g_i}$分别是节点$i$的度和介数；$0 < \beta < 1$是一个控制参量；$N$是网络中节点的个数；$\operatorname{int} [\beta {k_i}]$是指$\beta {k_i}$的整数部分。实验表明，模型1能进一步提高无标度网络和随机网络的传输效率；而模型2能极大地提高树状网络和规则网络的传输效率。

文献[24]提出了一个有限的数据包容量传输模型。在这个模型中，节点$i$的容量${C_i}$与度${k_i}$之间呈线性关系，即节点$i$的容量${C_i}$为：

${C_i} = N\left\langle C \right\rangle \frac{{k_i^\phi }}{{\sum\limits_{j = 1}^N {k_j^\phi } }}$

(6)

式中，$\left\langle C \right\rangle $是网络中所有节点的平均传输容量；$N$是指网络中节点的数量；${k_i}$是节点$i$的度；$\phi $是一个可调参数；$j$遍历了网络中所有的节点。当$\phi = 0$，所有节点的传输容量都相同；当$\phi $＞0时，度数较大的节点可能被分配更高的容量；类似地，当$\phi $＜0，度数小的节点倾向于被分配更高的容量。最短路径路由策略和局部路由策略(local routing strategy)下的一系列实验表明，对于每种路由策略总存在一个$\phi $＞0，使网络的总吞吐量达到最大。

文献[25]表明，在平均分配容量(每个节点的容量均为$\left\langle C \right\rangle $)、根据度的大小和介数的大小分配容量这三种策略中，按照介数的大小来分配节点容量的方法可以使网络达到最大的吞吐量。即节点$i$的容量为：

${C_i} = \frac{{{g_i}}}{{\sum\limits_{j = 1}^N {{g_j}} }}N\left\langle C \right\rangle $

(7)

式中，${g_i}$和${g_j}$分别指节点$i$和$j$的介数的大小，$j$遍历了网络中所有的节点。

文献[26]进一步提出了一个适应性的容量传输机制。在这个机制下，节点$i$的容量${C_i}$与排队长度${n_i}$呈线性关系，即：

${C_i}(t) = N\left\langle C \right\rangle \frac{{{{[{n_i}(t - 1)]}^\phi }}}{{\sum\limits_j {{{[{n_j}(t - 1)]}^\phi }} }}$

(8)

式中，${C_i}(t)$指在$t$时刻节点$i$的容量；${n_i}(t - 1)$是指在$t - 1$时刻节点$i$的排队长度；$\phi \geqslant 0$是一个可调参数；$j$遍历了网络中所有的节点。经过在BA网络^[8]上的一系列实验，发现网络的传输效率随着$\phi $的增加而先增后减，当$\phi $=1时，网络的传输效率达到最优。但鉴于这是一个动态模型，需要引入一个时间差来充分了解每个节点上的排队长度，因此每个数据包的平均传输时间不会大幅度减少。

2.2 带宽的重新分配策略

在相同的路由策略下，若两个网络采用不同的带宽分配策略，网络的吞吐量也会不同^[27]。因此可以通过重新分配各连边的带宽来增加网络的总容量。文献[28]引入了可调参数$\alpha $，并根据连边的重要性分配带宽。每条连边的重要性由它两端节点的度的乘积来衡量。连接节点$i$和$j$的连边${l_{ij}}$的带宽${D_{ij}}$为：

${D_{ij}} = \frac{{({k_i}{k_j})_{}^\alpha }}{{\sum\limits_{i = 1, j = 1, i \ne j}^N {{a_{ij}}({k_i}{k_j})_{}^\alpha } }}D$

(9)

式中，${a_{ij}}$是节点$i$与$j$的邻接矩阵A的元素，若节点$i$与$j$相连，则${a_{ij}} = 1$，否则${a_{ij}} = 0$；$D$是网络的总带宽资源，当$\alpha = 0$，网络中所有边的带宽都相同，当$\alpha > 0$，在这个模型下，拥有更大${k_i}{k_j}$的边倾向于被分配到更多的带宽。通过仿真模拟，在最短路径策略和局部路由策略下，$\alpha $分别等于0.35和0.5时，网络达到最高传输效率。

文献[29]同样也引入了可调参数$\alpha $，提出了一个基于介数的带宽分配策略，根据边两端节点的介数乘积$(1 + {g_i})_{}^\alpha (1 + {g_j})_{}^\alpha $来分配带宽。经过一系列的模拟仿真发现，与基于度的分配策略相比，基于介数的带宽分配策略可以进一步提高网络的吞吐量。

文献[30]进一步提出了一个基于排队长度的动态带宽分配策略，即按照每个时间点处每条边的排队长度来分配带宽：

${D_{ij}}(t) = \frac{{{n_{ij}}(t - 1)}}{{\sum\limits_{i = 1, j = 1, i \ne j}^N {{n_{ij}}(t - 1)} }}D$

(10)

式中，${D_{ij}}(t)$是在$t$时刻以节点$i$和$j$为端点的边的带宽；${n_{ij}}(t - 1)$指在$t - 1$时刻边的排队长度(即等待通过这条边的数据包的个数)；$D$是整个网络的总带宽。BA无标度网络上的一系列实验表明，在这种策略下，网络传输数据的能力得到充分利用，并且总的吞吐量进一步提高。同样，这个动态策略需要引入一个时滞才能获得每个时间段内每条边上的排队长度的信息。因此，虽然网络的吞吐量有所增加，网络的传输效率不一定提高。

目前的研究还只是停留在研究节点的总容量一定或者连边的总带宽一定的情况下的最优分配策略。然而在实际网络中，这两个限制往往同时发生。因此，有必要在未来的工作中研究在容量和带宽都有限时的最佳分配策略。

3 改变拓扑结构

改变网络的拓扑结构是可以提高网络传输效率的另一路由策略。研究表明交通动力学很大程度上取决于网络的拓扑结构^{[21, 31]}，因此通过在网络中删减或增加一些边也能提高网络的吞吐量。文献[20]证明了同构网络(homogeneous network)比异构网络(heterogeneous network)能承载更多的数据包，因为介数很大的节点在均匀网络中的数量相对较少。文献[16]通过对无标度网络和均匀网络上的交通状况进行模拟仿真，也证明了这个结论。文献[10]进而提出一种按照边两端节点的介数乘积进行删边扩容的方法(high-betweenness-first link removal strategy)，以减少网络中介数较大的节点的个数。即计算网络中每条边两端点的乘积${g_i}{g_j}$的值并按从大到小的顺序进行删减。结果证明，删减一定数量的边有利于扩大网络的吞吐量，删减过多的边则会适得其反。文献[32]从度的角度出发，提出了按照边两端节点度的大小进行删边的策略(high- degree-first link removal strategy)。具体的实施步骤如下：计算网络中每条边的两端点的乘积${k_i}{k_j}$的值并按从大到小的顺序进行删减，每次删边后计算网络的吞吐量并通过比较得到最大值。在非均匀网络中，hub节点一般要承载更多的信息负荷，导致它们周围的边很容易发生堵塞，移除一些易发生堵塞的边能够使网络中的信息负荷重新分配，从而提高网络的吞吐量。但这两种方法都会增加平均路径的长度，导致传输效率不会大幅度提高。

另外，一些学者从算法的角度出发，也提出了一些改变拓扑结构的路由策略。例如，基于模拟退火算法(simulated annealing)中得出的最优结果^[33]，文献[34]提出了VNDR策略。该策略的主要步骤如下：

1) 随机选出$H$条边并将它们从网络中移出，计算这时网络的吞吐量${R_c}$，并将其设为最优值${R_{{\rm{opt}}}}$；

2) 随机恢复$H$条边中的一条并随机从剩余的$E - H$($E$是网络中总边数)条边中移除一条，计算这时的吞吐量，若比之前的大，就将它设为新的${R_{{\rm{opt}}}}$；否则${R_{{\rm{opt}}}}$保持不变；

3) 重复步骤1)和2)，直到达到预设的重复次数。

无标度网络上的一系列实验表明，在该策略下网络能达到的最大吞吐量优于采用按度或介质删边扩容所得到的结果。当同时采用最短路径路由策略时，VNDR策略在没有大幅度提高平均路径长度的情况下，同时达到了扩大网络吞吐量和减少平均路由时间的目标。

文献[35]还提出了一种在无标度网络中增加节点和连边的有效方法。考虑到通过两个节点之间的最短路径很有可能经过hub节点，并且最短路径越长，通过的可能性越大，他们主张在拥有最长的最短路径的节点之间连接一条边，使数据包可以直接在它们之间传递而不需要经过hub节点，从而提高网络的传输效率。增加节点也运用同样的方法，即增加的节点选择两个拥有最长的最短路径的节点进行连边。

改变网络拓扑结构的路由策略具有高效、简洁的特点。在高峰期时，实际交通网络系统中暂时关闭一些拥挤路段、实际通讯网络中关闭一些链路即可实现优化，缓解拥塞现象，提高网络传输效率。但另一方面，采用这种策略的实用性不高。例如，在航空网络中，由于客流量的需求很大，因此在高峰期时取消一些重要航班是不可行的。另外，增加一些重要城市的机场数量是另一种改变拓扑结构的策略，然而这需要花费大量的人力、物力以及时间。所以，此类策略虽然操作简单，但在一些实际网络中可行性不高。

4 路径选择策略

根据文献[18]的研究，前面提到的两类提高运输效率的路由策略被称为“硬策略”(hard strategy)。一般情况下，这类策略的成本比较高，实用性不强。事实上，之前的研究已经证明，即使在异构网络中，网络动力学也可以被同质化(homogenized)，这已经在提高网络同步性(network synchronization)方面得到了运用^[36]。因此，目前在提高网络运输效率方面的大多数研究都集中于寻找新的路径选择策略，即所谓的“软策略”(soft strategy)^[18]。虽然找到全局最优的路径选择策略是一个NP难题^[37]，此前的研究中还是涌现出不少优秀策略，它们很大程度上提高了网络的传输效率，包括静态的全局^{[11-13, 22, 38-41]}和局部策略^[14-15]以及一系列动态策略^[42-49]。

4.1 静态路径选择策略(static routing strategy)

最早的路径选择策略是随机游走(random walk)，由于它在网络的传输和搜索机制中广泛应用^{[20, 50]}，因此被学者们普遍研究^[51-52]。但是它的过程太简单以至于无法准确反映出一个真实交通运输或信息传输系统的情况。经典的最短路径路由策略^[22]是指每个数据包都沿着从起点到终点最短的那条路径进行传输，由于它的经济成本和技术成本较低，因此被广泛应用于交通和通讯网络中^{[9, 53-55]}。然而，若采用最短路径路由策略，hub节点会承受很重的信息负荷，进而造成严重的拥塞。

为缓解hub节点处的拥塞问题，文献[11]提出了一种高效的路由策略(efficient routing strategy)，又称为ER策略，通过引入一个可调参数$\beta $，使负荷从中心节点处重新分配一部分到边缘节点处。对于起点为$i$，终点为$j$，经过节点${x_0}, {x_1}, \cdots , {x_n}$的路径${{\rm path}} = $ $(i \to j)$，定义为：

$L({\rm{path}}(i \to j):\beta ) = \sum\limits_{m = 0}^{n - 1} {k({x_m})_{}^\beta } $

(11)

式中，$k({x_m})$是节点${x_m}$的度。在此路径下，数据包会选择拥有最小$L$值的路径作为最佳运输路径。当$\beta $=0，此策略即为最短路径策略；当$\beta $ > 0，数据包在选择最佳路径时会同时考虑度的因素和路径长度因素。随着$\beta $的不同，数据包避开hub节点的程度不同。实验结果表明，对于$N = 1{\rm{ }}225$，$\left\langle k \right\rangle = 4$的BA网络，$\beta \approx 1$时，网络的吞吐量达到最大，并且超过最短路径路由策略下网络吞吐量的10倍。文献[38]提出了类似的基于介数的路径选择方法，将介数较大的节点处的负荷重新分配到边缘节点处，结果取得了很高的网络吞吐量，甚至超过了ER策略。为了更充分地利用各类节点的容量并进一步提高网络的容量，文献[39]在ER策略的基础上，提出了一种杂交路由策略(hybrid routing strategy)，使一个网络中存在两个不同的ER策略，即他们同时引入了两个可调变量${\beta _1}$和${\beta _2}$，使数据包在${\beta _1}$和${\beta _2}$这两个路径表上选择路径的概率分别是$p$和$1 - p$($0 < p < 1$)。因此，节点$i$的介数的定义是：

${g_i}({\beta _1}, {\beta _2}, p) = p \cdot {g_i}({\beta _1}) + (1 - p) \cdot {g_i}({\beta _2})$

(12)

当整个网络的最大介数${g_{\max }}$达到最小，此时$p$的值即为最优杂交率。文献[39]通过改变$p$的大小得到不同的路径选择策略，与ER策略相比，发现杂交路由策略能进一步有效利用各节点的容量并提高网络吞吐量，但同时也增加了计算的复杂度。

考虑到ER策略忽略了很多中心节点，使它们的运输能力没有得到充分利用，造成很大浪费，文献[40]对ER策略进行了改进，提出了一种积极的路由策略(active routing strategy)，进一步对网络动态进行同质化。在这个策略中，对于起点为$i$，终点为$j$，经过节点${x_0}, {x_1}, \cdots , {x_{n - 1}}, {x_n}$的路径${\rm path} = (i \to j)$，定义为：

$L'({\rm{path}}(i \to j):\beta ) = \sum\limits_{m = 0}^{n - 1} {(\log (\log k({x_m})))_{}^\beta } $

(13)

在此路径下，数据包会选择拥有最小$L'$值的路径进行传递。与ER策略相比，积极路由策略将$k{({x_m})_{}}$换成$\log (\log (k({x_m})))$，使函数对于度大的节点的敏感度降低，从而当数据包选择最优路径时也会考虑度大的节点，更充分利用它们的运输能力。

文献[41]平衡了最短路径策略和ER策略，提出了一种概率路由策略(probability routing strategy)，使hub节点得到更高效的利用。通过找到从$i$到$j$的所有路径中使$Y$达到最大的路径作为最优路径，$Y$的定义为：

$Y(\alpha , {\rm{path}}(i \to j)) = \prod\limits_{x \in {\rm{path}}(i \to j)} {\left[ {\frac{1}{{\ln (1 + {k_x})}}} \right]_{}^{\ln (1 + \alpha {k_x})}} $

(14)

式中，$\left[ {\frac{1}{{\ln ((1 + {k_x})}}} \right]_{}^{\ln (1 + \alpha {k_x})}$是数据包通过节点$x$的可能性，它随$k$的递增而递减，$\alpha $＞0是一个可调参数。在这个策略下，数据包会尽可能避免经过度大的节点，同时也保证路径的长度最短。无标度网络上的实验结果表明，该策略使网络达到的最大吞吐量优于在最短路径策略和ER策略下网络的最大吞吐量。

文献[12-13]认为网络吞吐量的大小取决于网络中节点的最大介数。假设各节点的容量相等，那么堵塞一定首先发生在介数最大的节点上。因此，他们提出了一种最优路由策略(optimal routing strategy)，即设计了一个算法使数据包尽量避免经过介数较大的节点，从而使网络中最大介数的值降到最低。在这种情况下，网络吞吐量得以提高，并且超过了文献[56]对于网络可达到的最大容量的理论预测。同时，BA网络上的实验表明，网络处于拥塞状态时，最优路由策略下的数据包的平均传输时间小于在最短路径策略下的传输时间。

上面提到的路径选择策略都是基于全局信息的方法，然而针对大型网络，全局信息很难把握，因此这些策略有时并不实用。文献[14-15]提出了基于局部拓扑信息的路由策略(local routing strategy)，即每个节点都对与它最近的邻居节点进行局部搜索，若数据包的终点在搜索范围内，则直接传输到终点；若不在范围内，则按照一种偏好概率${ {\mathit \Pi} _i}$传递数据包：

${{\mathit \Pi} _i} = \frac{{k_i^\alpha }}{{\sum\limits_j {k_j^\alpha } }}$

(15)

式中，${{\mathit \Pi} _i}$表示数据包传输到节点$i$的概率；$\alpha $是一个可调变量。当$\alpha = 0$时，数据包到每个节点的概率都相等；若$\alpha > 0$，则数据包倾向于传递给度大的节点；反之，若$\alpha < 0$，数据包更倾向于经过度小的节点。无标度网络上的实验结果证明当$\alpha = - 1$时，网络达到最大吞吐量。通过局部路由传输策略，只需要了解网络的局部信息就可以实现优化，尤其有利于提高大型实际网络的传输效率。

另外，文献[57]针对节点生成率不断变化的网络提出了一种混合路由策略(mixed routing strategy)。即当节点生成率较低时，使用最短路径策略；生成率较高时采用局部路由策略。无标度网络上的实验结果表明该策略下网络的传输效率超过了单独使用两策略中的任意一个。

4.2 动态路径选择策略(dynamic routing strategy)

之前提到的一系列静态路径选择策略都是基于静态信息的路由策略。在这些策略下，一旦网络建立，每个数据包的最佳路径同时也是确定的。为了更充分利用网络静态的拓扑结构信息以及动态的路由信息，学者们提出了一系列动态路径选择策略。动态路径选择策略同样也是考虑局部的网络结构信息，但不同于局部路由策略，它会综合考虑局部静态网络结构以及动态网络结构(例如节点处的排队长度等)。

文献[42-43]综合考虑了最短路径和在节点处的等待时间，提出了一种适应性的局部动态路由方法，即数据包在选择邻居节点进行传递时要同时考虑该节点到终点的距离以及在该节点处的等待时间。等待时间的长短由节点处的排队长度来决定，队列越长，等待时间也越长。进一步，文献[44]对此方法进行了改进，即数据包在传递时不仅要考虑邻居节点的排队长度，同时还要考虑整个路径上所有节点的排队长度。文献[45]也同样综合考虑了路径的长度以及整条路径上的节点处的等待时间，但从不同角度出发，提出了一种全局动态路由策略：

${{\rm path}_{i \to j}} = \min \sum\limits_{m = 0}^s {[1 + n({x_m})]} $

(16)

式中，$n({x_m})$是指节点${x_m}$处的排队长度；$s$是整个路径的长度。即以节点$i$为起点，$j$为终点的数据包在选择传输路径时会同时考虑整条路径上节点的排队长度以及路径的长度。这个方法仍然倾向于使用hub节点传输数据包，并且比ER策略取得了更大的网络吞吐量。

文献[46]引入一个可调参数，整合了局部静态信息和动力学信息，提出了一种局部动态路由策略，即数据包从节点$x$传递到节点$i$的概率${p_{x \to i}}$为：

${p_{x \to i}} = \frac{{{k_i}{{({n_i} + 1)}^\beta }}}{{\sum\limits_j {{k_j}{{({n_j} + 1)}^\beta }} }}$

(17)

式中，${k_i}$是节点$i$的度；${n_i}$为节点$i$处的排队长度；$j$遍历了节点$x$的所有邻居节点；$\beta \leqslant 0$是可调变量。数据包在选择节点进行传输时会同时考虑在节点处的等待时间以及传输路径的长度(通过度大的节点的概率越大，路径可能越短)。这个模型可以通过改变$\beta $的大小来调节这两个因素的比重，$\beta $越大，数据包会更偏向于选择队列较短的节点进行传输。文献[47]通过引入了两个可调参数$\alpha $和$\beta $，以一定比例整合了全局最短路径信息和局部度信息，使数据包在传递时尽可能避开度大的节点并且使路径最短，也提高了网络传输效率。文献[48]同时考虑了局部的度和介数信息以及全局的最短路径信息，提出了一种增加式的路径选择策略(incremental routing strategy)，将整个路由过程分为$N$步，每一步中设定一个起点$s$，并且设每一步中以$i$和$j$为两端点的边的权重为${(g_i^s{k_i})^\beta } + {(g_j^s{k_j})^\beta }$，其中$\beta $是一个可调参数，$g_i^s$是以$s$为起点的循环中节点$i$的介数，${k_i}$指节点$i$的度。以路径权重和最小为原则计算节点$s$到每个终点的最优路径。初始的$g_i^s = 1$，随后每次循环对节点的介数进行累加。循环$N$步后分别找出从每一个起点到各终点的最优路径。文献[49]综合考虑了节点的度分布和排队长度，根据这些指标赋予每个节点一个权重：

${w_i}(t) = 1 + \frac{{{n_i}(t)}}{{{C_i}}} + k_i^{\alpha (t)}$

(18)

式中，0＜$\alpha (t)$＜1是一个时间函数；${n_i}(t)$指节点$i$在$t$时刻的排队长度。这个策略是以路径中所有节点的权重和最小为目标求出最佳路径。

对于动态路由策略，往往需要一个时间差来更新动力学信息，因此虽然网络的吞吐量提高了，运输时间却可能增加，结果对于提高实际网络的传输效率只能提供很有限的帮助。因此如何降低这个时间差是未来研究工作中的一大挑战。

5 排队策略

上面提到的所有方法大多都遵循先进先出(FIFO)原则，即先到达某个节点的数据包优先被传递到下一节点。另外，后进先出(LIFO)原则在研究网络拓扑结构与交通流量的统计特性之间的相互影响方面有所应用^{[16, 58-59]}。然而，有时抛弃这些经典原则、设计新颖高效的排队策略也能提高网络的传输效率。

文献[60]摒弃了FIFO策略，对数据包的传递设定条件，即如果数据包的传递要经过的连边没有发生拥塞，那么它们会按顺序传输；反之，将会留在节点处。在这种策略下，可以顺畅流通的数据包便不会被耽搁，节省了整个网络中数据包的传输时间，提高了效率。

文献[61]提出了一种最短剩余路径优先的排队策略(shortest-remaining-path-first strategy)，又称为SRPF策略，即那些终点距离目前所在节点的路径最短的数据包优先被传递。为避免拥有较长路径的数据包的等待时间过长，他们同时也设置了一个时间值，一旦数据包等待的时间超过了这个值便会被优先传递。由于数据包的路由路径没有改变，所以SRPF策略下的整个网络的吞吐量并没有改变，但是整个过程的运输时间减少了。相应地，网络的传输效率也得到提高。

文献[62]对一定比例的数据包提前设定一个优先级，使它们无论进入节点的时间如何，都能优先被传递，然后对于同一优先级的数据包再遵循FIFO原则。无标度网络上的实验结果表明，在网络发生拥塞时，这种排队策略能很大程度上缩短数据包的平均传输时间，进而提高网络的传输效率，然而当网络处于自由流通状态时则会恶化传输状况。在这种优先级排队策略的启发下，文献[63]提出了一种全局动态排队策略，对于拥塞节点处的每个数据包赋予一个优先参数$V$：

$V = {n_r}\frac{{{f_r}}}{{{C_r}}}$

(19)

式中，${f_r}$是指数据包$r$的最短剩余路径；${n_r}$是数据包$r$的最短剩余路径上所有节点的排队长度的和；${C_r}$是指这条路径上所有节点的容量的和。在这个策略下，拥有较小$V$的数据包优先传递。

由于排队策略并没有改变数据包的传输路径，也没有对网络的拓扑结构做任何改变，因此网络的吞吐量不会增加，只有数据包的传输时间可能缩短。所以，虽然排队策略操作容易，但此类策略对于提高网络的传输效率只能提供有限的帮助。

6 其他方法

之前回顾的提高网络传输效率的四类路由策略都是基于一个前提假设的，即网络中的所有节点都可以同时生成、传递并接受数据包。然而，现实网络中的路由规则并不是完全一致的，相反，它们之间存在很大差异。很多实际网络中的每个节点都有特定功能。例如物流网络中顾客只能接受包裹，配送中心只能发出包裹，中转站只能传递包裹等。所以，在这个课题中，有些方法是基于特定结构的网络的，例如中间节点只能发出包裹，边缘节点可以传递和接收^[64]；有些特定节点只能生成包裹，其他只能传递、接收^[65-68]。研究这些具有特定结构的网络上的路由策略有利于解决特定的实际问题。例如，文献[68]的方法对于物流配送中心的选择问题很有实际意义，通过选择合理的物流配送中心节点的位置实现了整个网络的传输效率的优化。

现实生活中的很多网络都具有无标度特性。因此，为了更好地解决实际网络上的拥塞问题，大部分路由传输策略都是基于无标度网络做模拟仿真。不失一般性，这些无标度网络上的路由策略是本文回顾和总结的重点。另外，学者们对于少部分其他网络上的路由策略也有一定研究，例如随机网络^{[9, 25]}、小世界网络^{[25, 69]}、规则网络^[9]、树状网络^[9]、平面网络^[70]等。

7 总结与展望

近些年来，随着互联网的高速发展，网络信息量呈现爆炸式增长；随着工业发展和经济繁荣，车流量成倍增加；随着家用电器和工业用电量的迅猛增加，电力传输网络承载的负荷持续上升。这些变化造成了各网络传输系统的高强度负载，极易导致网络系统传输拥塞。而研究网络的路由传输策略可以有效改善拥塞问题，提高网络系统的传输效率，进而有效地提高网络的负载能力，节省传输时间，方便人们的生活。从这个角度出发，研究网络的传输策略具有很重要的现实意义。

总结起来，本文主要回顾了提高网络传输效率的四类路由传输策略并对其中有重大影响的策略进行了具体介绍。尽管科研工作者们在此课题上已投入很多工作并做出一定的成绩，这其中仍然存在一些问题还未解决并可能成为未来的研究方向。本文认为网络传输效率还可以在以下几方面进行提高。

1) 相依网络上的路由策略研究。现实生活中的各类复杂网络系统之间往往是相互作用、相互依赖的^[71]。例如，航空线路网络、城市交通网络以及铁道线路网络已经达到高度耦合，形成多式联运的运输网络；铁道线路网络系统需要电力网络系统的供电支持；电力系统与通信网络系统相互依赖。目前，虽然学者们对于相依网络上的路由策略有一定研究，例如，文献[72]以铁道线路以及火车流量的耦合双层网络为例，对铁路站点之间相依强度的统计特性进行了研究；文献[73]以交通网络为例，提出了一种相依网络模型，对网络上的协同路由进行了研究；文献[74]对相依网络中子网络之间的拓扑结构关系进行了研究，然而大多数路由策略的研究还仅仅局限于单侧网络，进一步研究相依网络上的路由策略具有很重要的现实意义。

2) 传输动力学诱导的网络演化研究。网络拓扑结构会影响网络传播动力学^[58]，相应地，网络传播动力学也可能会诱导网络的演化。例如，对于城市交通网络，人们会尽量避免高峰时期经过一些拥挤路段，从而这些原本拥挤路段上的车流量会扩散到其它非中心路段。在实际网络中总会存在网络同步的现象，即相邻的节点之间的动力学系统之间会相互影响^[75-76]，而动力学系统与网络结构之间也必然存在着相互影响和作用^[75]。然而目前的工作仅集中于研究网络的结构如何影响传播动力学，却较少对传输动力学诱导的网络演化给予重视，这是以后研究的重要工作之一。

3) 时变网络的路由传输策略。现实网络总是随着时间不断演化的^[77]。城市公交网络、轨道交通网络、航空航线网络等都在不断扩充站点和路线；通信网络中节点间的通信状态只持续有限的时间；万维网中的网站个数不断呈现迅猛增加的状态。因此考虑现实网络的时变性，研究时变网络上提高网络传输效率的路由策略是一项很有前景的工作。

4) 路由策略的数学模型构建。现阶段对于网络路由传输策略的研究仅限于对具体路由方法的运作机制进行描述，但并未进行严谨的理论数学证明，导致这些策略的内部运行原理无法进行深入的理论解释。因此，未来需要对路由策略的数学模型的构建给予高度重视。

5) 有向网络以及加权网络的进一步关注。本文介绍的度量指标以及路由传输策略大多是用来处理无向网络及无权网络的。这是最简单的情况，但是实际复杂网络很多都是有向和加权的，例如电力网络，因特网等，所以对有向网络以及加权网络的研究需要给予更多关注。

6) 动态路径选择策略优化。本文回顾了几种动态路径选择策略。这些策略同时整合了网络拓扑结构信息和局部动力学信息，对提高网络吞吐量有很大帮助。然而，总是需要一个时间差来更新局部动力学信息，导致数据包的传输时间不会大幅度缩短，只能有限地提高网络传输效率。因此，目前很棘手的一个问题就是研究如何将时滞降到最低，从而使动态策略更高效也更实用。