1、城市交通網絡單向擁堵分流算法的設計與實現唐俊勇郝海燕2(1.西安工業大學計算機科學與工程學院，陜西西安710032； 2.咸陽師范學院物理與 電子工程學院，陜西咸陽712000)摘要：城市交通流的信息具有實時性特點，傳統道路擁堵的預報都是在堵塞事件發生后進行發布，擇路分流也是憑著駕 駛人員的經驗，準確率很低。本文提出一種實時計算道路信息流并選擇最優道路進行分流的算法，具有實時性、智能化高的特 點。該其法設計了一個五維向量作為輸入信息，采用向量組優先級比較的方法，通過對道路端口計算來生成最優化路徑。本文 最后給出一個實際計算實例，擁堵分流算法生成其他最優備選道路，從而有效的實現了擁堵分流，使城市

2、交通性能得到優化。關鍵詞：城市交通；擁堵分流；向量優先級中圖分類號:tp 393.1文獻標志碼：a引言隨著城市交通網絡的建設和應用，城市交通道 路越來越多地連接城市不同的地點。城市交通網的 特點是冗余性設計被采用，即通過多條鏈路連接同 一地點形成網絡環路，確保某條鏈路擁堵后城市交 通網絡仍能保持通暢。這些冗余鏈路對交通管理帶 來一個新問題，即當某條或者若干條城市交通鏈路 發生擁堵，如何選擇若干條交通量最小，或者通行 效率最優的道路來連接整個城市，即能保證城市正 常的交通運力，乂能緩解擁堵路段的壓力進行分流, 有效提高了道路運行效率。1擁堵分流算法1. 1算法概述本算法的思想就是要在整個城市屮形

3、成連接到 各個地點的樹形道路，各個地點的道路連接點處(道 路匯聚點)通過交通流量采集設備獲得道路流量信 息，道路匯聚點通過信息數據包(idu)的交換來進行 計算，選定城市交通網屮的根匯聚點(root convergence point) 1 和指定匯聚點(designated convergence point)，確定道路端口的角色是根端門 (root port)、指定端u (designated port、或者備 用端口 (alternate port、。經過計算后，生成了一個 無環路的“樹”型交通通行率最小的道路結構。1.2算法信息數據單元(idu)的構成城市交通m絡內各個道路匯聚點(co

4、nvergence point根據每個道路端口優先級向量決定每個道路 端口角色。這些角色分別為：root port “designatedport,alternate port, alternate 'port 0(1) 城市交通m絡中匯聚點不是根匯聚點，且該匯 聚點的某個端u優先向量來源于根匯聚點，那么該 端口是根端口 krootport)。(2) 道路路徑端口優先向w:來源于指定向it則該 端口是交通網絡屮的道路指定端口( designated port)<>(3) 城市交通網屮，除了根端口外，匯聚點某個端 口的端口優先向量是從其他匯聚點接收來的，該端 口是替代端口(

5、alternated port、。1.3向量組優先級比較每個道路端口將參與運算的關鍵參數字段構成 一個五維向量： root convergence point, root path cost， designated convergence point，designated port， rcvport ,匯聚點各個道路端口通過比較彼此交換的 idu包中的五元向量組進行優先級確定，優先級比 較順序是從左至右，如果靠前的向量值小，則表明 為優先向量組。五維向量組的比較過程如卜：(1) 計算 root convergence point-.在道路交 通網絡屮各個匯聚點首先推舉一個匯聚點作為樹形 道路的

6、根匯聚點，推舉依據是各個匯聚點的優先值， 優先值的選擇根據匯聚點在城市交通中重要程度和 沒計標準選擇，位范圍為0，1,計算公式如(1) 所示.root convergence point =priority (convergence point n)(1 )(2) 計算累積擁堵因子root path cosh如果匯聚點本身是根匯聚點，則到根匯聚點路徑開銷為0，否則就為其他匯聚點所收到的腳的root path cb沖值與收到該配置消息的道路端口擁堵因子 (port cost)之和。擁堵因子root path cost計算公式 如(2)所示：root path cost=root path cos

7、t(recejve)+port cost(receive)(2)(3) 確定指定匯聚點和條 道路路徑分別連接到兩個不同的匯聚點，根據公式(1)和公成(2)的計算結果，root path cost最優 先，即擁堵因子值最小的匯聚點為指定匯聚點。一 條道路鏈路中所屬指定匯聚點的端口為指定端口 (designated port)。(4) 確定根端口 qroot port、和替代端口(alternate port):非根匯聚點上接收的最優五元量紐的端口為根端口。除了根端口和指定端口，其 余的端口都是替代端口，這樣就構成了一個邏輯樹 形結構的最低擁堵交通網絡。2算法實現根據上節提到的向呈組優先級比較以確

8、定最終 的匯聚端n優先向量，根據端n優先向量的內容確 定端u角色，這樣可以實時計算整個城市交通網中 存在一條通過花費最小的道路。當道路發生堵塞觸 發重新計算進程，從而找到其他備份的最優道路。 下面以一實例說明：如圖1所示，所在城市有四個主 要道路匯聚點，根據重要性匯聚點賦值分別為：0.65, 0.97, 0.86和0.78。以第二個匯聚點為例，其有叫個 port連接到城市交通網，67.2代表第二個端口的花費 值為67,其余匯聚點和端口均為此表示方法。使用 向量優先比較，以下計算為第二個匯聚點，權重值 為0.97的端口角色。(1) 第二個匯聚點各個道路端口接收的道路對 端端口發來的五維消息向量組

9、與初始化時本匯聚點 各個端口的優先叫:u:，根據優先級得到根匯聚點為 權值是0.65的匯聚點和各個端口的更新累積擁堵因 子值的端口向量組：，().6500.6520.31).9700.9745.11 >0.6500.6567.220.9700.9767.220.7803.84100.230.9700.97100.33,0.8600.86100.10.97v00.97100.44jroot path cost vector <0.65450.6520.31 "0.65670.6567.220.781000.78 100.230.861000.86 100.14；priori

10、ty(2) 從root path cost vector中找到fi優向量作為 指定匯聚點向量，再根據根匯聚點的權值和接收端 口的擁堵因子位進行更新，生成指定端口。root path cos z vector "0.65450.6520.310.65670.6567.220.78100 0.78100.23k0.86100 0.86 100.14designated vector(0.65 45 0.65 20.3 l)r23 desinatedport4 )desinatedportport priority vector z0.65 45 0.65 20.3 0.65 67 0.6

11、5 67.2 0.65 45 0.65 20.3 0.65 45 0.65 20.3port priority vector<0.65450.652030.65670.6567.220.65450.6520.33desinatedport<0.65450.652034zdesignatedport/xrr/nfey(3) 在更新過的端口優先向量組中，1端門與2 端u的向量都來自其本省的擁堵因子累積向量，端 口1的擁堵花費為45,而端口2為67,端口 1由于端口 2為最優路徑端口。端口角色被定義后，port priority vector參與下一輪運算。0.65450.6520.30

12、.65670.6567.20.65450.6520.30.65450.6520.3port priority vector1234priority port alternated port desinatedport designatedport分析：經過以上算法，算出權值0.97的匯聚點的 端口優先向量，端口 1和2的優先14量表明，根匯聚 點和上游匯聚點均為0.65，由于端口 2到根匯聚點開 銷比端口 1大，所以端口2為替代端口 &為端口 1的冗 余。端 i 13、4 的戸"7 priority v漢仍，味自 designated vector,所以為指定端口。當計算完成

13、后可以定時重復運算，通過道路流 :w:監測在只改變端口擁堵因子值的條件下重新計算 單向通道花費值，找到a優的覆蓋所有匯聚點的道 路。其他匯聚點以相同算法運算，這樣在城市交通 網絡總形成了一條單向最優道路。如圖2所示，其中 實線為最優道路，虛線為擁堵道路。2 de sousa. improving load balance and resilience of ethernet carrier networks with ieee 802. id spanning tree protocol z. mauritius islands: 5th int conference on networkin

14、g, 2006.3 zhang yin-di, lt kai tai. the error estimates of the characteristic finite element method for nonlinear ad-vection-diffusion equation j. journal of changpan university: natural science edition, 2004, 24 (6) : 106-110.4 王輝.一種基于mstp的負載均衡算法設計jj.電子設計工程，2011，19(215):83-86.5 呂俏，劉啟文，石冰心.stp協議原理的算

15、法與實 現j.華中理工大學學報，2008, 28(1): 38-41.6 g ibanez, garci-marti, azcorra. bridges: scalable, self-configuring ethernet campus networks j/ol. computer networks, 2008, 52 (3): 630-649.7 關積珍，鄭長青，朱雪良，等.北京奧運交通誘導vms 信息發布研究j1.交通運輸系統工程與信息，2008,8(6):115-120.8 mei zhen-yu,xiang y-i qiang，chen jun,et al.op-timizati

16、on method of configuration of traffic flow guid-ance information board in urban j. journal of traf-fic and transportation engineering, 2007, 7(5 ): 88-92.i【收稿日期】2015-10-08圖2城市交通網最優道路選擇3結束語【基金項目】西安工北大學校長基金(xagdxjj1216)【作者簡介】唐俊勇(1975 )，男，講師，研究方向： 計算機叼絡，網絡協議與分析。現代城市交通網中，道路擁堵現象非常普遍。 本文以通過比較叫量優先的方法構造了一個五維叫 :w:紐，使得在擁堵發生后通過計算快速找到最優疏 散道路，有效緩解交通壓力，并且避免了傳統憑經