網絡路由傳輸策略的研究進展

程 燦，郭 強，劉建國

?

網絡路由傳輸策略的研究進展

程 燦，郭 強，劉建國

(上海理工大學復雜系統(tǒng)科學研究中心 上海楊浦區(qū) 200093)

隨著復雜網絡在眾多領域的廣泛應用，如何提高網絡的傳輸效率成為了其進一步應用的瓶頸。本文分別從基于節(jié)點和邊信息的路由策略，改變拓撲結構的路由策略，路徑選擇策略以及排隊策略四個方面展開，對網絡中的路由傳輸策略進行介紹，并對其中具有重要影響的方法進行詳細闡述。最后提出了這一領域中未來可能的研究方向。本文有助于相關學者快速了解當前網絡中路由傳輸策略的研究進展，并能夠幫助網絡設計者以及管理者更好地提高網絡的傳輸效率，最大程度上避免傳輸過程中的交通擁塞。

復雜網絡; 交通擁塞; 路由策略; 傳輸效率

隨著信息技術的飛速發(fā)展，人們的生活被各種網絡包圍著，包括e-mail網絡[1]、電話網絡[2]、電力網絡[3]、飛機航線網絡[4]、交通網絡[5]、因特網和萬維網[6-7]等。1998年，文獻[3]提出了小世界網絡模型，進一步，文獻[8]提出了無標度網絡的模型，對實際的復雜系統(tǒng)進行網絡建?！，F代社會處在一個大數據、大流量的時代，高度依賴于這些網絡系統(tǒng)的正常高效運行。然而，在處于擁塞的情況下，這些網絡的傳輸效率會大大降低并可能造成網絡系統(tǒng)的癱瘓，極大地影響人們的工作與生活。所以，研究如何提高這些網絡的傳輸效率從而避免擁塞，具有很重要的現實意義。

以計算機網絡中的信息傳遞為例，通常，當網絡中節(jié)點(邊)的負荷超過了它們的容量(帶寬)時，信息擁塞就會發(fā)生。學者們通過研究網絡中的路由傳輸策略對網絡進行優(yōu)化，進而提高網絡的傳輸效率。根據目前的研究，學者們首先從宏觀角度將路由傳輸策略分為基于網絡結構和基于動力學的路由策略兩大類。進一步，根據網絡結構的類型，基于網絡結構的路由策略又可被劃分為基于節(jié)點和邊信息的路由策略以及改變拓撲結構的路由策略。同時，基于動力學的路由策略又可以按照是否改變傳播路徑細分為路徑選擇策略以及排隊策略。目前的路由策略中有一些具有重要影響，例如，文獻[9]首次提出按度分配節(jié)點的容量，開啟了容量分配策略的先例，學者們自此開始考慮賦予各節(jié)點不同的傳輸數據包的能力。文獻[10]提出了改變拓撲結構的路由策略，通過刪減網絡中的關鍵連邊實現網絡的優(yōu)化。這類策略雖然操作簡單，但有時實用性不高。文獻[11]首次提出了一種高效的路徑選擇策略，主張數據包應盡量避開hub節(jié)點而選擇邊緣節(jié)點進行傳輸。在這個策略的啟發(fā)下，學者們開始關注到邊緣節(jié)點的重要性，但hub節(jié)點本身具有的很高的傳輸能力沒有得到充分利用。文獻[12-13]認為網絡吞吐量的大小取決于網絡中節(jié)點的最大介數，因此提出了一種路徑選擇策略使網絡中節(jié)點的最大介數值達到最小。雖然這種策略下網絡的吞吐量得以提高，但是計算復雜度卻很高。文獻[14-15]提出了基于局部信息的路徑選擇策略，只需要了解網絡的局部信息即可實現優(yōu)化，因此對于一些實際的大型網絡更具有實用價值。學者們還從節(jié)點處數據包傳遞順序的角度出發(fā)，提出了一系列排隊策略，使節(jié)點處的數據包按照一定規(guī)則有序傳遞，降低了網絡中數據包的平均傳輸時間。

理解并研究復雜網絡上的路由策略、控制網絡擁塞，是急需處理的重要問題之一。因此有必要對網絡中的路由傳輸策略進行全面回顧與分析。目前關于網絡路由傳輸的綜述中，文獻[16]通過模擬和仿真無標度網絡和均勻網絡上的交通狀況，系統(tǒng)地研究了網絡傳輸的一系列統(tǒng)計特性與網絡結構之間的關系；文獻[17]從整體和局部分別出發(fā)，回顧了具有重要意義的路由策略；文獻[18]將路由策略劃分為“硬策略”與“軟策略”，主要回顧了路徑選擇策略以及網絡拓撲結構改變的路由策略。本文對網絡的路由傳輸策略進行了更系統(tǒng)的回顧與分析，對于路由策略的劃分更具體細致，介紹更詳細全面。本文首先介紹了與這項研究相關的一些基本指標，然后回顧了提高網絡傳輸效率的四類路由策略——基于節(jié)點和邊信息的策略，改變拓撲結構的策略，路徑選擇策略以及排隊策略，最后提出了網絡路由傳輸策略未來可能的研究方向。

1 基本指標介紹

在網絡路由傳輸策略的研究中，不失一般性，網絡中的節(jié)點同時被視作主機和路由器，即每個節(jié)點都可以產生、傳送并且接受數據包。網絡中的邊可以看作是數據包傳遞的可能的路徑。每單位時間內網絡中有個新的數據包產生，這些數據包都隨機地選擇出發(fā)點和終點。到達終點的數據包將會從網絡中移除。

以下是網絡中的路由傳輸策略所涉及到的一些基本指標，包括容量、介數、臨界值以及序參數，它們可以衡量網絡的吞吐狀況。

網絡的傳輸效率有兩個衡量指標，網絡的吞吐量以及平均傳輸時間。網絡的吞吐量越大，平均傳輸時間越短，網絡的傳輸效率就越高。因此，所有的路由傳輸策略都旨在擴大網絡吞吐量和減少數據包的平均傳輸時間。

2 基于節(jié)點和邊信息的路由策略

當節(jié)點處的數據包數量超過了節(jié)點的容量，或者連邊處的數據包數量超過了邊的帶寬時，網絡會出現擁塞現象。在廣泛應用的最短路徑路由策略[22](shortest path routing strategy)下，阻塞總是首先出現在hub節(jié)點處然后再擴散至整個網絡。因此，當整個網絡的節(jié)點總容量一定時，只要分配給hub節(jié)點更大的容量就能有效緩解擁塞進而提高網絡的最大吞吐量。類似地，當網絡中邊的總帶寬一定時，分配給關鍵連邊更大的帶寬也能提高網絡的傳輸效率。

2.1 改變節(jié)點處理能力的分配策略

文獻[9]提出了另外兩個模型，分別是按節(jié)點度的大小以及介數的大小來分配容量。

模型1:(4)

模型2:(5)

文獻[24]提出了一個有限的數據包容量傳輸模型。在這個模型中，節(jié)點的容量與度之間呈線性關系，即節(jié)點的容量為：

文獻[26]進一步提出了一個適應性的容量傳輸機制。在這個機制下，節(jié)點的容量與排隊長度呈線性關系，即：

2.2 帶寬的重新分配策略

在相同的路由策略下，若兩個網絡采用不同的帶寬分配策略，網絡的吞吐量也會不同[27]。因此可以通過重新分配各連邊的帶寬來增加網絡的總容量。文獻[28]引入了可調參數，并根據連邊的重要性分配帶寬。每條連邊的重要性由它兩端節(jié)點的度的乘積來衡量。連接節(jié)點和的連邊的帶寬為：

文獻[30]進一步提出了一個基于排隊長度的動態(tài)帶寬分配策略，即按照每個時間點處每條邊的排隊長度來分配帶寬：

目前的研究還只是停留在研究節(jié)點的總容量一定或者連邊的總帶寬一定的情況下的最優(yōu)分配策略。然而在實際網絡中，這兩個限制往往同時發(fā)生。因此，有必要在未來的工作中研究在容量和帶寬都有限時的最佳分配策略。

3 改變拓撲結構

改變網絡的拓撲結構是可以提高網絡傳輸效率的另一路由策略。研究表明交通動力學很大程度上取決于網絡的拓撲結構[21,31]，因此通過在網絡中刪減或增加一些邊也能提高網絡的吞吐量。文獻[20]證明了同構網絡(homogeneous network)比異構網絡(heterogeneous network)能承載更多的數據包，因為介數很大的節(jié)點在均勻網絡中的數量相對較少。文獻[16]通過對無標度網絡和均勻網絡上的交通狀況進行模擬仿真，也證明了這個結論。文獻[10]進而提出一種按照邊兩端節(jié)點的介數乘積進行刪邊擴容的方法(high-betweenness-first link removal strategy)，以減少網絡中介數較大的節(jié)點的個數。即計算網絡中每條邊兩端點的乘積的值并按從大到小的順序進行刪減。結果證明，刪減一定數量的邊有利于擴大網絡的吞吐量，刪減過多的邊則會適得其反。文獻[32]從度的角度出發(fā)，提出了按照邊兩端節(jié)點度的大小進行刪邊的策略(high- degree-first link removal strategy)。具體的實施步驟如下：計算網絡中每條邊的兩端點的乘積的值并按從大到小的順序進行刪減，每次刪邊后計算網絡的吞吐量并通過比較得到最大值。在非均勻網絡中，hub節(jié)點一般要承載更多的信息負荷，導致它們周圍的邊很容易發(fā)生堵塞，移除一些易發(fā)生堵塞的邊能夠使網絡中的信息負荷重新分配，從而提高網絡的吞吐量。但這兩種方法都會增加平均路徑的長度，導致傳輸效率不會大幅度提高。

另外，一些學者從算法的角度出發(fā)，也提出了一些改變拓撲結構的路由策略。例如，基于模擬退火算法(simulated annealing)中得出的最優(yōu)結果[33]，文獻[34]提出了VNDR策略。該策略的主要步驟如下：

3) 重復步驟1)和2)，直到達到預設的重復次數。

無標度網絡上的一系列實驗表明，在該策略下網絡能達到的最大吞吐量優(yōu)于采用按度或介質刪邊擴容所得到的結果。當同時采用最短路徑路由策略時，VNDR策略在沒有大幅度提高平均路徑長度的情況下，同時達到了擴大網絡吞吐量和減少平均路由時間的目標。

文獻[35]還提出了一種在無標度網絡中增加節(jié)點和連邊的有效方法?？紤]到通過兩個節(jié)點之間的最短路徑很有可能經過hub節(jié)點，并且最短路徑越長，通過的可能性越大，他們主張在擁有最長的最短路徑的節(jié)點之間連接一條邊，使數據包可以直接在它們之間傳遞而不需要經過hub節(jié)點，從而提高網絡的傳輸效率。增加節(jié)點也運用同樣的方法，即增加的節(jié)點選擇兩個擁有最長的最短路徑的節(jié)點進行連邊。

改變網絡拓撲結構的路由策略具有高效、簡潔的特點。在高峰期時，實際交通網絡系統(tǒng)中暫時關閉一些擁擠路段、實際通訊網絡中關閉一些鏈路即可實現優(yōu)化，緩解擁塞現象，提高網絡傳輸效率。但另一方面，采用這種策略的實用性不高。例如，在航空網絡中，由于客流量的需求很大，因此在高峰期時取消一些重要航班是不可行的。另外，增加一些重要城市的機場數量是另一種改變拓撲結構的策略，然而這需要花費大量的人力、物力以及時間。所以，此類策略雖然操作簡單，但在一些實際網絡中可行性不高。

4 路徑選擇策略

根據文獻[18]的研究，前面提到的兩類提高運輸效率的路由策略被稱為“硬策略”(hard strategy)。一般情況下，這類策略的成本比較高，實用性不強。事實上，之前的研究已經證明，即使在異構網絡中，網絡動力學也可以被同質化(homogenized)，這已經在提高網絡同步性(network synchronization)方面得到了運用[36]。因此，目前在提高網絡運輸效率方面的大多數研究都集中于尋找新的路徑選擇策略，即所謂的“軟策略”(soft strategy)[18]。雖然找到全局最優(yōu)的路徑選擇策略是一個NP難題[37]，此前的研究中還是涌現出不少優(yōu)秀策略，它們很大程度上提高了網絡的傳輸效率，包括靜態(tài)的全局[11-13,22,38-41]和局部策略[14-15]以及一系列動態(tài)策略[42-49]。

4.1 靜態(tài)路徑選擇策略(static routing strategy)

最早的路徑選擇策略是隨機游走(random walk)，由于它在網絡的傳輸和搜索機制中廣泛應用[20,50]，因此被學者們普遍研究[51-52]。但是它的過程太簡單以至于無法準確反映出一個真實交通運輸或信息傳輸系統(tǒng)的情況。經典的最短路徑路由策略[22]是指每個數據包都沿著從起點到終點最短的那條路徑進行傳輸，由于它的經濟成本和技術成本較低，因此被廣泛應用于交通和通訊網絡中[9,53-55]。然而，若采用最短路徑路由策略，hub節(jié)點會承受很重的信息負荷，進而造成嚴重的擁塞。

為緩解hub節(jié)點處的擁塞問題，文獻[11]提出了一種高效的路由策略(efficient routing strategy)，又稱為ER策略，通過引入一個可調參數，使負荷從中心節(jié)點處重新分配一部分到邊緣節(jié)點處。對于起點為，終點為，經過節(jié)點的路徑，定義為：

(12)

考慮到ER策略忽略了很多中心節(jié)點，使它們的運輸能力沒有得到充分利用，造成很大浪費，文獻[40]對ER策略進行了改進，提出了一種積極的路由策略(active routing strategy)，進一步對網絡動態(tài)進行同質化。在這個策略中，對于起點為，終點為，經過節(jié)點的路徑，定義為：

文獻[41]平衡了最短路徑策略和ER策略，提出了一種概率路由策略(probability routing strategy)，使hub節(jié)點得到更高效的利用。通過找到從到的所有路徑中使達到最大的路徑作為最優(yōu)路徑，的定義為：

文獻[12-13]認為網絡吞吐量的大小取決于網絡中節(jié)點的最大介數。假設各節(jié)點的容量相等，那么堵塞一定首先發(fā)生在介數最大的節(jié)點上。因此，他們提出了一種最優(yōu)路由策略(optimal routing strategy)，即設計了一個算法使數據包盡量避免經過介數較大的節(jié)點，從而使網絡中最大介數的值降到最低。在這種情況下，網絡吞吐量得以提高，并且超過了文獻[56]對于網絡可達到的最大容量的理論預測。同時，BA網絡上的實驗表明，網絡處于擁塞狀態(tài)時，最優(yōu)路由策略下的數據包的平均傳輸時間小于在最短路徑策略下的傳輸時間。

上面提到的路徑選擇策略都是基于全局信息的方法，然而針對大型網絡，全局信息很難把握，因此這些策略有時并不實用。文獻[14-15]提出了基于局部拓撲信息的路由策略(local routing strategy)，即每個節(jié)點都對與它最近的鄰居節(jié)點進行局部搜索，若數據包的終點在搜索范圍內，則直接傳輸到終點；若不在范圍內，則按照一種偏好概率傳遞數據包：

另外，文獻[57]針對節(jié)點生成率不斷變化的網絡提出了一種混合路由策略(mixed routing strategy)。即當節(jié)點生成率較低時，使用最短路徑策略；生成率較高時采用局部路由策略。無標度網絡上的實驗結果表明該策略下網絡的傳輸效率超過了單獨使用兩策略中的任意一個。

4.2 動態(tài)路徑選擇策略(dynamic routing strategy)

之前提到的一系列靜態(tài)路徑選擇策略都是基于靜態(tài)信息的路由策略。在這些策略下，一旦網絡建立，每個數據包的最佳路徑同時也是確定的。為了更充分利用網絡靜態(tài)的拓撲結構信息以及動態(tài)的路由信息，學者們提出了一系列動態(tài)路徑選擇策略。動態(tài)路徑選擇策略同樣也是考慮局部的網絡結構信息，但不同于局部路由策略，它會綜合考慮局部靜態(tài)網絡結構以及動態(tài)網絡結構(例如節(jié)點處的排隊長度等)。

文獻[42-43]綜合考慮了最短路徑和在節(jié)點處的等待時間，提出了一種適應性的局部動態(tài)路由方法，即數據包在選擇鄰居節(jié)點進行傳遞時要同時考慮該節(jié)點到終點的距離以及在該節(jié)點處的等待時間。等待時間的長短由節(jié)點處的排隊長度來決定，隊列越長，等待時間也越長。進一步，文獻[44]對此方法進行了改進，即數據包在傳遞時不僅要考慮鄰居節(jié)點的排隊長度，同時還要考慮整個路徑上所有節(jié)點的排隊長度。文獻[45]也同樣綜合考慮了路徑的長度以及整條路徑上的節(jié)點處的等待時間，但從不同角度出發(fā)，提出了一種全局動態(tài)路由策略：

文獻[46]引入一個可調參數，整合了局部靜態(tài)信息和動力學信息，提出了一種局部動態(tài)路由策略，即數據包從節(jié)點傳遞到節(jié)點的概率為：

(18)

對于動態(tài)路由策略，往往需要一個時間差來更新動力學信息，因此雖然網絡的吞吐量提高了，運輸時間卻可能增加，結果對于提高實際網絡的傳輸效率只能提供很有限的幫助。因此如何降低這個時間差是未來研究工作中的一大挑戰(zhàn)。

5 排隊策略

上面提到的所有方法大多都遵循先進先出(FIFO)原則，即先到達某個節(jié)點的數據包優(yōu)先被傳遞到下一節(jié)點。另外，后進先出(LIFO)原則在研究網絡拓撲結構與交通流量的統(tǒng)計特性之間的相互影響方面有所應用[16,58-59]。然而，有時拋棄這些經典原則、設計新穎高效的排隊策略也能提高網絡的傳輸效率。

文獻[60]摒棄了FIFO策略，對數據包的傳遞設定條件，即如果數據包的傳遞要經過的連邊沒有發(fā)生擁塞，那么它們會按順序傳輸；反之，將會留在節(jié)點處。在這種策略下，可以順暢流通的數據包便不會被耽擱，節(jié)省了整個網絡中數據包的傳輸時間，提高了效率。

文獻[61]提出了一種最短剩余路徑優(yōu)先的排隊策略(shortest-remaining-path-first strategy)，又稱為SRPF策略，即那些終點距離目前所在節(jié)點的路徑最短的數據包優(yōu)先被傳遞。為避免擁有較長路徑的數據包的等待時間過長，他們同時也設置了一個時間值，一旦數據包等待的時間超過了這個值便會被優(yōu)先傳遞。由于數據包的路由路徑沒有改變，所以SRPF策略下的整個網絡的吞吐量并沒有改變，但是整個過程的運輸時間減少了。相應地，網絡的傳輸效率也得到提高。

文獻[62]對一定比例的數據包提前設定一個優(yōu)先級，使它們無論進入節(jié)點的時間如何，都能優(yōu)先被傳遞，然后對于同一優(yōu)先級的數據包再遵循FIFO原則。無標度網絡上的實驗結果表明，在網絡發(fā)生擁塞時，這種排隊策略能很大程度上縮短數據包的平均傳輸時間，進而提高網絡的傳輸效率，然而當網絡處于自由流通狀態(tài)時則會惡化傳輸狀況。在這種優(yōu)先級排隊策略的啟發(fā)下，文獻[63]提出了一種全局動態(tài)排隊策略，對于擁塞節(jié)點處的每個數據包賦予一個優(yōu)先參數：

由于排隊策略并沒有改變數據包的傳輸路徑，也沒有對網絡的拓撲結構做任何改變，因此網絡的吞吐量不會增加，只有數據包的傳輸時間可能縮短。所以，雖然排隊策略操作容易，但此類策略對于提高網絡的傳輸效率只能提供有限的幫助。

6 其他方法

之前回顧的提高網絡傳輸效率的四類路由策略都是基于一個前提假設的，即網絡中的所有節(jié)點都可以同時生成、傳遞并接受數據包。然而，現實網絡中的路由規(guī)則并不是完全一致的，相反，它們之間存在很大差異。很多實際網絡中的每個節(jié)點都有特定功能。例如物流網絡中顧客只能接受包裹，配送中心只能發(fā)出包裹，中轉站只能傳遞包裹等。所以，在這個課題中，有些方法是基于特定結構的網絡的，例如中間節(jié)點只能發(fā)出包裹，邊緣節(jié)點可以傳遞和接收[64]；有些特定節(jié)點只能生成包裹，其他只能傳遞、接收[65-68]。研究這些具有特定結構的網絡上的路由策略有利于解決特定的實際問題。例如，文獻[68]的方法對于物流配送中心的選擇問題很有實際意義，通過選擇合理的物流配送中心節(jié)點的位置實現了整個網絡的傳輸效率的優(yōu)化。

現實生活中的很多網絡都具有無標度特性。因此，為了更好地解決實際網絡上的擁塞問題，大部分路由傳輸策略都是基于無標度網絡做模擬仿真。不失一般性，這些無標度網絡上的路由策略是本文回顧和總結的重點。另外，學者們對于少部分其他網絡上的路由策略也有一定研究，例如隨機網絡[9,25]、小世界網絡[25,69]、規(guī)則網絡[9]、樹狀網絡[9]、平面網絡[70]等。

7 總結與展望

近些年來，隨著互聯網的高速發(fā)展，網絡信息量呈現爆炸式增長；隨著工業(yè)發(fā)展和經濟繁榮，車流量成倍增加；隨著家用電器和工業(yè)用電量的迅猛增加，電力傳輸網絡承載的負荷持續(xù)上升。這些變化造成了各網絡傳輸系統(tǒng)的高強度負載，極易導致網絡系統(tǒng)傳輸擁塞。而研究網絡的路由傳輸策略可以有效改善擁塞問題，提高網絡系統(tǒng)的傳輸效率，進而有效地提高網絡的負載能力，節(jié)省傳輸時間，方便人們的生活。從這個角度出發(fā)，研究網絡的傳輸策略具有很重要的現實意義。

總結起來，本文主要回顧了提高網絡傳輸效率的四類路由傳輸策略并對其中有重大影響的策略進行了具體介紹。盡管科研工作者們在此課題上已投入很多工作并做出一定的成績，這其中仍然存在一些問題還未解決并可能成為未來的研究方向。本文認為網絡傳輸效率還可以在以下幾方面進行提高。

1) 相依網絡上的路由策略研究?，F實生活中的各類復雜網絡系統(tǒng)之間往往是相互作用、相互依賴的[71]。例如，航空線路網絡、城市交通網絡以及鐵道線路網絡已經達到高度耦合，形成多式聯運的運輸網絡；鐵道線路網絡系統(tǒng)需要電力網絡系統(tǒng)的供電支持；電力系統(tǒng)與通信網絡系統(tǒng)相互依賴。目前，雖然學者們對于相依網絡上的路由策略有一定研究，例如，文獻[72]以鐵道線路以及火車流量的耦合雙層網絡為例，對鐵路站點之間相依強度的統(tǒng)計特性進行了研究；文獻[73]以交通網絡為例，提出了一種相依網絡模型，對網絡上的協(xié)同路由進行了研究；文獻[74]對相依網絡中子網絡之間的拓撲結構關系進行了研究，然而大多數路由策略的研究還僅僅局限于單側網絡，進一步研究相依網絡上的路由策略具有很重要的現實意義。

2) 傳輸動力學誘導的網絡演化研究。網絡拓撲結構會影響網絡傳播動力學[58]，相應地，網絡傳播動力學也可能會誘導網絡的演化。例如，對于城市交通網絡，人們會盡量避免高峰時期經過一些擁擠路段，從而這些原本擁擠路段上的車流量會擴散到其它非中心路段。在實際網絡中總會存在網絡同步的現象，即相鄰的節(jié)點之間的動力學系統(tǒng)之間會相互影響[75-76]，而動力學系統(tǒng)與網絡結構之間也必然存在著相互影響和作用[75]。然而目前的工作僅集中于研究網絡的結構如何影響傳播動力學，卻較少對傳輸動力學誘導的網絡演化給予重視，這是以后研究的重要工作之一。

3) 時變網絡的路由傳輸策略?，F實網絡總是隨著時間不斷演化的[77]。城市公交網絡、軌道交通網絡、航空航線網絡等都在不斷擴充站點和路線；通信網絡中節(jié)點間的通信狀態(tài)只持續(xù)有限的時間；萬維網中的網站個數不斷呈現迅猛增加的狀態(tài)。因此考慮現實網絡的時變性，研究時變網絡上提高網絡傳輸效率的路由策略是一項很有前景的工作。

4) 路由策略的數學模型構建?，F階段對于網絡路由傳輸策略的研究僅限于對具體路由方法的運作機制進行描述，但并未進行嚴謹的理論數學證明，導致這些策略的內部運行原理無法進行深入的理論解釋。因此，未來需要對路由策略的數學模型的構建給予高度重視。

5) 有向網絡以及加權網絡的進一步關注。本文介紹的度量指標以及路由傳輸策略大多是用來處理無向網絡及無權網絡的。這是最簡單的情況，但是實際復雜網絡很多都是有向和加權的，例如電力網絡，因特網等，所以對有向網絡以及加權網絡的研究需要給予更多關注。

6) 動態(tài)路徑選擇策略優(yōu)化。本文回顧了幾種動態(tài)路徑選擇策略。這些策略同時整合了網絡拓撲結構信息和局部動力學信息，對提高網絡吞吐量有很大幫助。然而，總是需要一個時間差來更新局部動力學信息，導致數據包的傳輸時間不會大幅度縮短，只能有限地提高網絡傳輸效率。因此，目前很棘手的一個問題就是研究如何將時滯降到最低，從而使動態(tài)策略更高效也更實用。

[1] EBEL H, MIELSCH L I, BORNHOLDT S. Scale-free topology of e-mail networks[J]. Physical Review E, 2002, 66: 035103.

[2] AIELLO W, CHUNG F, LU L. A random graph model for massive graphs[C]//Proceedings of the thirty-second annual ACM symposium on Theory of computing. Newyork: [s.n.], 2000: 171-180.

[3] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440- 442.

[4] LI W, CAI X. Statistical analysis of airport network of China[J]. Physical Review E, 2004, 69(4): 046106.

[5] HELBING D. Traffic and related self-driven many-particle systems[J]. Reviews of Modern Physics, 2001, 73(4): 1067.

[6] ALBERT R, JEONG H, BARABASI A L. Internet: Diameter of the world-wide web[J]. Nature, 1999, 401(6749): 130-131.

[7] KAHNG B, PARK Y, JEONG H. Robustness of the in-degree exponent for the world-wide web[J]. Physical Review E, 2002, 66(4): 046107.

[8] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[9] ZHAO L, LAI Y C, PARK K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2): 026125.

[10] ZHANG G Q, WANG D, LI G J. Enhancing the transmission efficiency by edge deletion in scale-free networks[J]. Physical Review E, 2007, 76(1): 017101.

[11] YAN G, ZHOU T, HU B, et al. Efficient routing on complex networks[J]. Physical Review E, 2006, 73(4): 046108.

[12] DANILA B, YU Y, MARSH J A, et al. Optimal transport on complex networks[J]. Physical Review E, 2006, 74(4): 046106.

[13] DANILA B, YU Y, MARSH J A, et al. Transport optimization on complex networks[J]. Chaos, 2007, 17(2): 026102.

[14] WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2): 026111.

[15] YIN C Y, WANG B H, WANG W X, et al. Efficient routing on scale-free networks based on local information[J]. Physics Letters A, 2006, 351(4): 220-224.

[16] TADIC B, RODGERS G J, THURNER S. Transport on complex networks: Flow, jamming and optimization[J]. International Journal of Bifurcation and Chaos, 2007, 17(7): 2363-2385.

[17] WANG B H, ZHOU T. Traffic flow and efficient routing on scale-free networks: a survey[J]. Journal of the Korean Physical Society, 2007, 50: 134.

[18] CHEN S, HUANG W, CATTANI C, et al. Traffic dynamics on complex networks: a survey[J]. Mathematical Problems in Engineering, doi: 10.1155/2010/732698.

[19] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[20] GUIMERA R, DIAZ-GUILERA A, VEGA-REDONDO F, et al. Optimal network topologies for local search with congestion[J]. Physical Review Letters, 2002, 89(24): 248701.

[21] ARENAS A, DIAZ-GUILERA A, GUIMERA R. Communication in networks with hierarchical branching[J]. Physical Review Letters, 2001, 86(14): 3196-3199.

[22] GOH K I, KAHNG B, KIM D. Universal behavior of load distribution in scale-free networks[J]. Physical Review Letters, 2001, 87(27): 278701.

[23] LIU Z, MA W, ZHANG H, et al. An efficient approach of controlling traffic congestion in scale-free networks[J]. Physica A, 2006, 370(2): 843-853.

[24] YANG H X, WANG W X, WU Z X, et al. Traffic dynamics in scale-free networks with limited packet-delivering capacity[J]. Physica A, 2008, 387(27): 6857-6862.

[25] LING X, HU M B, LONG J C, et al. Traffic resource allocation for complex networks[J]. Chinese Physics B, 2013, 22(1): 018904.

[26] CAO X B, DU W B, CHEN C L, et al. Effect of adaptive delivery capacity on networked traffic dynamics[J]. Chinese Physics Letters, 2011, 28(5): 058902.

[27] HU M B, WANG W X, JIANG R, et al. The effect of bandwidth in scale-free network traffic[J]. Europhysics Letters, 2007, 79(1): 14003.

[28] LING X, HU M B, DU W B, et al. Bandwidth allocation strategy for traffic systems of scale-free network[J]. Physics Letters A, 2010, 374(48): 4825-4830.

[29] JIANG Z Y, LIANG M G, ZHANG S, et al. An efficient bandwidth allocation strategy for scale-free networks[J]. International Journal of Modern Physics C, 2012, 23(10): 50065.

[30] JIANG Z Y, LIANG M G, LI Q, et al. Optimal dynamic bandwidth allocation for complex networks[J]. Physica A, 2013, 392(5): 1256-1262.

[31] TOROCZKAI Z, BASSLER K E. Network dynamics: Jamming is limited in scale-free systems[J]. Nature, 2004, 428(6984): 716-716.

[32] LIU Z, HU M B, JIANG R, et al. Method to enhance traffic capacity for scale-free networks[J]. Physical Review E, 2007, 76(3): 037101.

[33] PENNA T J P. Traveling salesman problem and Tsallis statistics[J]. Physical Review E, 1995, 51(1): R1-R3.

[34] HUANG W, CHOW T W S. An efficient strategy for enhancing traffic capacity by removing links in scale-free networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010(1): P01016.

[35] HUANG W, CHOW T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos, 2010, 20(3): 033123.

[36] MOTTER A E, ZHOU C S, KURTHS J. Enhancing complex network synchronization[J]. Europhysics Letters, 2005, 69(3): 334-340.

[37] BUI T N, JONES C. Finding good approximate vertex and edge partitions is NP-hard[J]. Information Processing Letters, 1992, 42(3): 153-159.

[38] JIANG Z Y, LIANG M G. Improved efficient routing strategy on scale-free networks[J]. International Journal of Modern Physics C, 2012, 23(2): 50016.

[39] DONG J Q, HUANG Z G, ZHOU Z, et al. Enhancing transport efficiency by hybrid routing strategy[J]. Europhysics Letters, 2012, 99(2): 20007.

[40] PU C L, ZHOU S Y, WANG K, et al. Efficient and robust routing on scale-free networks[J]. Physica A, 2012, 391(3): 866-871.

[41] ZHANG X, HE Z, HE Z, et al. Probability routing strategy for scale-free networks[J]. Physica A, 2013, 392(4): 953- 958.

[42] ECHENIQUE P, GOMEZ-GARDENES J, MORENO Y. Dynamics of jamming transitions in complex networks[J]. Europhysics Letters, 2005, 71(2): 325-331.

[43] ECHENIQUE P, GOMEZ-GARDENES J, MORENO Y. Improved routing strategies for Internet traffic delivery[J]. Physical Review E, 2006, 70(5): 056105.

[44] ZHANG H, LIU Z, TANG M, et al. An adaptive routing strategy for packet delivery in complex networks[J]. Physics Letters A, 2007, 364(3): 177-182.

[45] LING X, HU M B, JIANG R, et al. Global dynamic routing for scale-free networks[J]. Physical Review E, 2010, 81(1): 016113.

[46] WANG W X, YIN C Y, YAN G, et al. Integrating local static and dynamic information for routing traffic[J]. Physical Review E, 2006, 74(1): 016101.

[47] WU Z X, PENG G, WONG W M, et al. Improved routing strategies for data traffic in scale-free networks[J]. Journal of Statistical Mechanics: Theory and experiment, 2008(11): P11002.

[48] JIANG Z Y, LIANG M G. Incremental routing strategy on scale-free networks[J]. Physica A, 2013, 392(8): 1894- 1901.

[49] TAN F, XIA Y. Hybrid routing on scale-free networks[J]. Physica A, 2013, 392(18): 4146-4153.

[50] ADAMIC L A, LUKOSE R M, PUNIYANI A R, et al. Search in power-law networks[J]. Physical Review E, 2001, 64(4): 046135.

[51] NOH J D, RIEGER H. Random walks on complex networks[J]. Physical Review Letters, 2004, 92(11): 118701.

[52] DE MOURA A P S. Fermi-dirac statistics and traffic in complex networks[J]. Physical Review E, 2005, 71(6): 066114.

[53] ZHAO L, PARK K, LAI Y C. Attack vulnerability of scale- free networks due to cascading breakdown[J]. Physical Review E, 2004, 70(3): 035101.

[54] PARK K, LAI Y C, ZHAO L, et al. Jamming in complex gradient networks[J]. Physical Review E, 2005, 71(6): 065105.

[55] WU Z X, WANG W X, YEUNG K H. Traffic dynamics in scale-free networks with limited buffers and decongestion strategy[J]. New Journal of Physics, 2008, 10(2): 023025.

[56] SREENIVASAN S, COHEN R, LOPEZ E, et al. Structural bottlenecks for communication in networks[J]. Physical Review E, 2007, 75(3): 036105.

[57] WANG D. Mixed routing strategy in scale-free networks[C]//The 25th Chinese Control and Decision Conference. Guiyang: IEEE, 2013: 5048-5051.

[58] TADIC B, THURNER S, RODGERS G J. Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations [J]. Physical Review E, 2004, 69(3): 036102.

[59] TADIC B, THURNER S. Information super-diffusion on structured networks[J]. Physica A, 2004, 332: 566-584.

[60] TANG M, ZHOU T. Efficient routing strategies in scale-free networks with limited bandwidth[J]. Physical Review E, 2011, 84(2): 026116.

[61] DU W B, WU Z X, CAI K Q. Effective usage of shortest paths promotes transportation efficiency on scale-free networks[J]. Physica A, 2013, 392(17): 3505-3512.

[62] KIM K, KAHNG B, KIM D. Jamming transition in traffic flow under the priority queuing protocol[J]. Europhysics Letters, 2009, 86(5): 58002.

[63] XU P, HONG C. A global dynamic queuing strategy on scale-free networks[C]//In Green Computing and Communications, 2013 IEEE and Internet of Things, IEEE International Conference on and IEEE Cyber, Physical and Social Computing. Beijing: [s.n.], 2013: 856-859.

[64] OHIRA T, SAWATARI R. Phase transition in a computer network traffic model[J]. Physical Review E, 1998, 58(1): 193-195.

[65] SOLE R V, VALVERDE S. Information transfer and phase transitions in a model of internet traffic[J]. Physica A, 2001, 289(3): 595-605.

[66] WOOLF M, ARROWSMITH D K, MONDRAGON-C R J, et al. Optimization and phase transitions in a chaotic model of data traffic[J]. Physical Review E, 2002, 66(4): 046106.

[67] VALVERDE S, SOLE R V. Self-organized critical traffic in parallel computer networks[J]. Physica A, 2002, 312(3): 636-648.

[68] CHEN Y H, WANG B H, ZHAO L C, et al. Optimal transport on supply-demand networks[J]. Physical Review E, 2010, 81(6): 066105.

[69] 張國清, 程蘇琦. 小世界網絡中的刪邊擴容效[J]. 中國科學: 信息科學, 2012, 42(2): 151-160.

ZHANG Guo-qing, CHENG Su-qi. Enhancing network capacity effects of edge-removal in small-world networks [J]. Scientia Sinica Informationis, 2012, 42(2): 151-160.

[70] DANILA B, SUN Y, BASSLER K E. Collectively optimal routing for congested traffic limited by link capacity[J]. Physical Review E, 2009, 80(6): 066116.

[71] KURANT M, THIRAN P. Layered complex networks[J]. Physical Review Letters, 2006, 96(13): 138701.

[72] WANG J L, ZHOU T, SHI J J, et al. Empirical Analysis of dependence between stations in Chinese railway station[J]. Physica A, 2009, 388: 2949-2955.

[73] GU C G, ZOU S R, XU X L, et al. Onset of cooperation between layered networks[J]. Physical Review E, 2011, 84: 026101.

[74] ZOU S R, ZHOU T, LIU A F, et al. Topological relation of layered complex networks[J]. Physica A, 2010, 374(43): 4406-4410.

[75] 趙明, 汪秉宏, 蔣品群, 等. 復雜網絡上動力系統(tǒng)同步的研究進展[J]. 物理學進展, 2005, 25(3): 273-295.

ZHAO Ming, WANG Bing-hong, JIANG Ping-qun, et al. Recent advancement in research of synchronization of dynamical systems on complex networks[J]. Progress In Physics, 2005, 25(3): 273-295.

[76] 趙明, 周濤, 陳關榮, 等. 復雜網絡上動力系統(tǒng)同步的研究進展Ⅱ——如何提高網絡的同步能力[J]. 物理學進展, 2008, 28(1): 22-34.

ZHAO Ming, ZHOU Tao, CHEN Guan-rong. A review on synchronization of dynamical systems on complex networksⅡ: How to enhance the network synchronizability[J]. Progress In Physics, 2008, 28(1): 22-34.

[77] HOLME P, SARAMAKI J. Temporal networks[J]. Physics Reports, 2012, 519: 97-125.

編 輯 蔣 曉

Advance in the Research on Routing Strategy of Networks

CHENG Can, GUO Qiang, and LIU Jian-guo

(Research Center of Complex Systems Science, University of Shanghai for Science & Technology Yangpu Shanghai 200093)

With the wide application of complex networks in many fields, how to improve the transportation efficiency has become the bottleneck of its further development in practice. This article classifies these routing ways from four aspects—reassigning the distribution of nodes’ capacity and links’ bandwidth, modifying network topology, designing routing strategies, and proposing queuing strategies. we also introduce some influential strategies in detail. Finally, we point out some potential directions in the future. This work is helpful for new learners and researchers to be familiar with this field and may be helpful for network designers or regulators to improve the network efficiency and avoid traffic jams.

complex networks; congestion; routing strategy; transportation efficiency

TP393

A

10.3969/j.issn.1001-0548.2015.01.001

2014-04-09；

2014-12-01

國家自然科學基金(71171136，61374177，71371125)；上海市一流學科建設項目(XTKX2012)；教育部人文社科基金(13YJA630023)；上海市大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(XJ2013120)

程燦(1993-)，女，本科生，主要從事網絡路由策略方面的研究.