規則網絡上提高交通處理能力不同路由策略研究

摘 要:針對交通擁擠問題，提出了一個基于隨機選擇最短路徑的簡單交通流模型，并研究了這個模型的動力學行為。為了提高規則網絡上的相變點的值，提出了幾種改進的路由策略，并作了詳細的仿真對比研究。最后，給出了更好的提高網絡整體性能的路由策略，并提出了應對交通問題的一些合理性建議。 結果顯示，規則網絡上交通流存在一個從自由相到擁塞相的相變。相變點的值可以用來衡量網絡處理交通流的能力。

關鍵詞:規則網絡; 交通流; 相變; 路由策略

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3455-03

doi:10.3969/j.issn.1001-3695.2009.09.071

Different routing strategies to enhance traffic capacity for regular networks

WANG Jian-wei， RONG Li-li

(Institute of Systems Engineering， Dalian University of Technology， Dalian Liaoning 116024， China)

Abstract:For the traffic congestion problem， firstly this paper proposed a simple model for traffic network based on randomly choosing the shortest path and further explore its dynamics behavior. Secondly， presented and discussed three different routing tactics in order to increase the value of the phrase transition. Finally， according to the simulation results， further proposed some reasonable suggestions to tackle some traffic problems. The simulation results show that there exists a phase transition from the free phrase to congested phrase on the regular network and the value of the phrase transition can be used to measure the capacity of network to deal with traffic flow.

Key words:regular network; traffic dynamics; phase transition; routing strategies

近年來，隨著經濟的發展和城市化進程的加快，城市機動車擁有量急劇增加，交通擁擠現象越來越嚴重。為了更好地解決交通擁擠問題，很多學者從不同的角度研究網絡上交通動力學[1～3]。20世紀30年代，國外就有人用概率論方法研究交通流問題。到目前為止，交通流模型大體分為三類，即基于自驅動粒子分析的微觀模型[4～6]、基于氣體動力論的介觀模型[7～9]和基于流體力學的宏觀模型[10～12]。不同的理論描述方法所建立的模型各有千秋，彼此間存在一定的關聯。然而在交通流建模中，至今還不存在普適的模型，原因在于復雜的交通系統難以用統一的模式加以描述。

以往對交通網絡的大部分研究都是基于規則網絡是隨機圖，并在此基礎上分析交通網絡擁擠現象的演變規律，得出了很多有價值的結論[13～15]。近年來，為了提高交通效率，有效地緩解交通擁擠現象，尋求網絡上好的路由策略[16，17]已成為研究的主流方向。與改變網絡基礎設施相比，對于擴展交通網絡的處理能力，比較好的路由策略更可取。

在這樣的背景下，本文提出了一個基于隨機選擇最短路徑的簡單交通流模型，并研究了這個模型的動力學行為。結果表明，通過定義網絡最大吞吐量作為衡量網絡處理交通能力的指標，規則網絡上交通流隨著交通流生成速率的增加存在一個相變點，即從自由相到擁塞相的轉變。在假定交通流分布均勻的前提下，發現隨機選擇最短路徑的路由策略所求得的相變點與理論分析的結果存在一定的差距。為了提高規則網絡上的相變點的值，本文進一步提出了三種不同的路由策略，并對網絡的相變點及交通流的生存時間分別進行了研究。實驗結果驗證了存在比較好的路由策略，能更有效地提高網絡的最大吞吐量，并能夠有效地縮短交通流的生存周期。因此，根據不同的交通情況，選擇不同的路由策略對于提高交通網絡的整體性能是十分必要的。

1 模型

本文研究的是城市道路網絡上的交通流問題。但需要強調的是，研究的相關理論成果能夠類似地推廣和應用到其他的網絡中，如Internet網絡。

針對現實交通網絡的特性，同時為了更好地研究網絡上的交通流的動力學演化過程，提出如下假設:a)模型中研究的網絡是二維正方晶格規則網絡，網絡中除了邊界上的節點的連邊為3，其余節點的連邊均為4;b)網絡中交通流的產生是隨機的;c)假定網絡中每一個節點處理交通流的能力是相同的。

在假設的前提下，交通流模型描述為:a)每一個時間步內，規模為N的網絡中隨機產生M個交通流;b)每一個交通流均隨機給定起點和終點，并按照最短路徑的方式從起點向終點傳輸，如果最短路徑存在多條，它將隨機進行選擇;c)當交通流到達終點時，它將從網絡中消失;d)如果一個交通流到達的節點上有其他的交通流正等待傳送，那么這個交通流將排在隊列的末尾，依據先進先出的原則。

2 模型的相變研究

對于一個交通網絡而言，最為關心的應是這個網絡的最大吞吐量，即網絡能夠自由地處理最大交通流量。網絡的最大吞吐量可以由交通流的生成速率V來衡量。當網絡中的生成速率V逐漸增大時，達到一個臨界值Vc時，網絡會出現從自由相到擁塞相的相變。也就是說，當交通流的生成速率VVc時，由于網絡中每個節點的處理能力是有限的，網絡將出現阻塞，并迅速擴散到整個網絡，使大量的交通流處于停滯狀態。

2.1 模型描述

假設模型中任意一個節點x處理信息的能力均為c(x)。為了更好地研究相變點Vc與網絡規模N之間的關系，筆者考察了在時間t時，網絡中沒有處理完的流量與網絡總共生成的流量之間的比值，設為R(t)。令R=limt→∞ R(t)，從上述的分析得知:limV→∞R=1，limV→0 R=0。從理論上講，當R>0時，網絡發生相變，處于擁擠相;當R=0時，網絡處于自由相。

圖1顯示了t=10 000時，網絡中R(t)與V的關系曲線。圖1中的取值為20次獨立實驗模擬的結果。顯然，對于網絡規模N為400的規則網絡，可以近似(實驗中t只能夠取得有限值)地認為存在相變點Vc=11。

2.2 模型分析

從網絡拓撲的角度看，在t時刻，網絡中所產生的交通流在規則網絡節點上量的分布存在著不均勻性，如網絡中越接近中心的節點，交通的流量相對來說會越大。這樣，中心上的一些節點將成為整個網絡處理交通流量的瓶頸。因此，在上述的模型下所求得相變點Vc一定與網絡本身的最大吞吐量所對應的相變點的值之間存在一定的差距。筆者先從理論的角度分析一下規則網絡上的最大吞吐量與網絡規模之間的關系。

對于網絡而言，一個交通流從誕生到消失都會經過一段路徑。設一個交通流經歷的路徑中包含節點x的概率為ρ(x)，如果網絡能夠處理所生成的交通流，那么網絡中的所有節點都應符合條件:

V*ρ(x)≤c(x)，即 V≤c(x)/ρ(x)(1)

其中:V為交通流的生成速率;c(x)為節點x在一個時間步上處理交通流的個數。所以，只要找到最大的ρ(x)，則可求得c(x)/max ρ(x)的值。當交通流的生成速率V≤c(x)/max ρ(x)時，網絡能夠自由地處理交通流;當V>c(x)/max ρ(x)時，網絡將出現從自由相到阻塞相的相變，而這里的V就是網絡最大吞吐量所對應的相變點Vc。

在網絡規模為N的模型中，網絡中的交通流是隨機產生的，每一個交通流均按照最短路徑的方式從起點到達終點，所以交通流在網絡上的平均最短距離為N-1。這里的平均最短距離定義為交通流所經過的節點數目，即交通流在網絡中所經過的邊數。此外，假定在這種機制下，網絡中流的分布是均勻的(這種前提不太現實，但可以求得相變點的理論上限)，那么網絡中隨機產生的每一交通流在網絡上走的路徑長度為N-1，所經過的節點數為N-1，每一時間步上，一個交通流覆蓋整個網絡的密度比為N-1/N。在網絡中每一節點處理能力為1的情況下，通過式(1)求得網絡規模為N的規則網絡上相變點的理論上限為N/N-1。

圖2為不同網絡規模N上相變點的理論分析與模擬結果對比。由圖2可以看出，在網絡上所有的節點均處于同等地位的前提下，所得到的理論上的相變點與模擬的結果之間存在很大的差距。這種差距可以解釋為:當網絡規模在增大的情況下，隨著網絡中交通流生成速率V的增加，網絡中節點在選擇自身最短路徑的條件下，并不一定使得交通流量平均地分配到網絡的各個節點上，如網絡中越接近中心的節點，交通的流量相對來說會越大，這必然會使所求得的相變點Vc與網絡本身的最大吞吐量所對應的相變點的值之間存在一定的差距。因此，為了更好地提高網絡的最大吞吐量，尋求有效的路由策略均勻化網絡中的交通流，是一個很有效且可行的方法之一，也是現實交通領域中亟待解決的關鍵問題。

3 模型中路由策略的改進

規則網絡上，除了邊界上的節點，任何節點的度均為4。所以，當網絡中的交通流處于非邊界上的節點時，如果按照最短路徑的原則選擇下一個要到達的節點，一定存在兩個方向可以選擇，如圖3所示。

本文模型中，采用的游走規則是隨機地選擇最短路徑的策略。但在現實交通網絡中，當一個節點發生嚴重交通阻塞時，往往大部分的司機將會繞道，并再次選擇自己的交通路線。那么，當網絡中的一部分節點發生阻塞的情況下，采用什么樣的策略將更有效地提高交通效率，是解決當前交通擁擠問題的重要手段。

3.1 三種不同的路由策略方法

假定網絡中的交通流具有獲得局部信息的能力，現實的交通網絡中，可以通過即時的交通信息獲得。

在t時刻，處于網絡中i節點上的交通流v，按照最短路徑的原則，將有兩個節點可以作為下一步目的地選擇，設為j1和j2，如圖3所示。同時用參數vti表示為t時刻節點i上沒有處理完的交通流量。

路由策略1 在t時刻，對比交通流v的下一步目的地選擇節點上交通流量的值，即Vtj1和Vtj2，選擇小的值作為下一步目的地節點。這在現實的交通中最為常見。

路由策略2 t時刻，處于節點i上的交通流v，在最短路徑的原則下，如果節點j1是v在隨機原則下選擇的下一步要到達的節點，那么在離開節點i時，交通流v會判斷Vtj1與Vtj2的值。當Vtj1-Vtj2>n(n的取值為1、2、3，這里的最大值，考慮了i+1時刻j2節點除了交通v，最多能夠增加三個交通流，除去新生的交通流，如圖4所示)時，v將選擇j2作為下一個節點;否則為j1。

對比了n的不同取值對網絡相變點的影響，結果為20次獨立實驗基礎上的平均值，如圖5所示。

結果表明:當n=3時，效果更好一些。

路由策略3 設節點i的四個鄰居為i1、i2、i3、i4。t時刻，處于節點i上的交通流v，如果節點i1是v在隨機原則下選擇的下一步要到達的節點，那么在離開節點i時，交通流v會用Vi1值與其他三個鄰居上的Vi2、Vi3、Vi4值進行對比。當Vi1-min{Vi2，Vi3，Vi4}>n(n=1，2，3，…)時，v將選擇三個鄰居中沒有處理完的交通流量最小值作為下一個節點(這種情況可能背離最短路徑的原則，但在一定程度上可以提高網絡的整體吞吐量);否則為i。

在路由策略3中，選取了不同的n值，20次模擬實驗結果如圖6所示。結果顯示:n的取值從5～6有一定的差距，但6～8差距不大。

3.2 路由策略對比研究

模擬實驗中的所有結果都是在20次獨立實驗結果基礎上的平均。三種路由策略模擬結果與隨機選擇最短路徑模擬結果的對比如圖7所示。

路由策略2中n的取值為3，路由策略3中n的值為6。從實驗對比中發現，隨機選擇最短路徑的路由策略并不是最優的策略。在三種改進的路由策略中，路由策略2是最優的，使得網絡的相變點值增加2。在現實網絡交通中，也能夠很好地解釋這種現象:t時刻，車輛v在最短路徑路由的情況下會選擇節點i作為下一個節點，但根據交通訊息的獲得，它首先對比節點i和它可以選擇另一個最短路徑上的節點j上沒有處理完的交通流量的值Vtj1和Vtj2，當Vtj1-Vtj2>3，j2上路徑的選擇一定是從局域角度上使得網絡處理節點更均勻化的節點，因為i+1時刻j2節點除了交通v，最多能夠增加三個交通流。

筆者還對四種路由策略上交通流的平均生存時間進行了對比，如圖8所示。將一個交通流從誕生到消失的時間步，作為這個交通流的生存時間。那么規則網絡上，交通流的平均生存時間可以衡量網絡中交通的成本信息，即它的值越小，交通流在網絡上浪費的時間越少。

從數據分析可知，當交通流生成速率在[8，18]時，路由策略3都要優于隨機選擇最短路徑;而當V在[8，16]時，路由策略2要優越一些。該結論的啟示為:在現實交通中，在交通流生成速率的一定范圍內，按照一定的路由策略選擇最短路徑不失為一個很好的選擇。

本文同時對不同的網絡規模N下的相變點變化情況進行了仿真實驗。實驗結果發現，與隨機策略對比，路由策略2在提高網絡相變點的大小方面與網絡規模N正相關，如圖9所示。

4 結束語

在規則網絡上隨機產生交通流，并隨機給定起點和終點，每一交通均按照最短路徑的方式從起點向終點傳輸。這種前提下，不同的路由策略對于網絡的最大吞吐量有著不同程度的影響。本文對所提出的幾種路由策略作了詳細的仿真對比研究，得出如下結論:在交通網絡中，要想提高網絡的整體吞吐量，隨機地選擇最短路徑并不是最好的選擇，最好的路由策略應該是在對比下一時間步可選擇的節點上未處理的交通流量的基礎上，更進一步地考察這些可選擇節點上的交通流量的具體差別，也就是路由策略2所對應的思想。

參考文獻:

[1]CHANDRA A K. Jamming of directed traffic on a square lattice[J]. J Stat Mech， 2006(8):P08005.

[2]JIANG Rui， HU Mao-bin， WANG wen-xu. Traffic dynamics of packets generated with non-homogeneously selected sources and destinations in scale-free networks[Z]. 2007.

[3]嚴鋼，汪秉宏，傅忠謙，等. 復雜網絡上的交通動力學[J]. ITS通訊，2006， 8(2): 11-13.

[4]PIPES L A. An operational analysis of traffic dynamics[J]. Journal of App Phys， 1953， 24: 274-281.

[5]NAGEL K， SCHRECKENBERY M. A cellular automation model for freeway traffic[J]. Journal Phys I， 1992，2(12): 2221-2229.

[6]BIHAM O， MIDDLETON A A， LEVINE D A. Self-organization and a dynamical transition in traffic flow models[J]. Phys Rev A， 1992， 46: 6124-6127.

[7]HELBING D. Derivation and empirical validation of a refined traffic flow model[J]. Physica A， 1996， 233(1-2): 253-282.

[8]HOOGENDOORN S P， BOVY P H L. Continuum modeling of multiclass traffic flow[J]. Trans on Res B， 2000， 34(2): 123-146.

[9]HELBING D， HENNECKE A， SHVETSOV V， et al. MASTER: macroscopic traffic simulation based on gas-kinetic， nonlocal traffic model[J]. Trans on Res B， 2001， 35(2): 183-211.

[10]DAGANZO C F. Requiem for second-order fluid approximation of traffic flow[J]. Trans on Res B， 1995， 29(4): 277-286.

[11]HEIDEMANN D. Some critical remarks on a class of traffic flow models[J]. Trans on Res B， 1999， 33(2): 153-155.

[12]ZHANG H M. Anisotropic property revisited: does it hold in multi-lane traffic[J]. Trans on Res B， 2003， 37(6):561-577.

[13]ARENAS A， DIAZ-GUILER A， GUIMER R. Communication in networks with hierarchical branching[J]. Phys Rev Lett， 2001， 86(14): 3196-3199.

[14]GUIMER R， ARENAS A， DiAZ-GUILERA A， et al. Dynamical properties of model communication networks[J]. Phys Rev E， 2002， 66(2): 026704.

[15]GUIMER R， DiAZ-GUILER A， VEGA-REDONDO F， et al. Optimal network topologies for local search with congestion[J]. Phys Rev Lett， 2002， 89(24): 248701.1-248701.4.

[16]GOH K I， KAHNG B， KIM D. Universal behavior of load distribution in scale-free networks[J]. Phys Rev Lett， 2001， 87(27): 278701.

[17]ZHAO Liang， PARK K， LAI Ying-cheng， et al. Tolerance of scale-free networks against attack-induced cascades[J]. Phys Rev E， 2005， 72(2): 025104.q