車載自組織網絡RBVT-R協議的改進*

陳遠龍，葛劍飛，劉南杰，趙海濤

（1.南京郵電大學通信與信息工程學院 南京 210003；

2.南京郵電大學網絡基因工程研究所

南京 210003；3.國家電網上海市電力公司信息通信公司 上海 200122）

1 引言

車載自組織網絡 （vehicular Ad Hoc network，VANET）是指道路上車輛間、車輛與固定接入點之間相互通信組成的開放移動Ad Hoc網絡，可以實現事故告警、輔助駕駛、道路交通信息查詢和Internet信息服務等應用[1]。VANET中節點移動快、網絡拓撲變化迅速、車輛節點進出頻繁以及車輛節點因緊急情況可能發生大量聚集等特點[2]，使得基于拓撲的路由協議[3,4]性能大大降低，而城市環境下，VANET中節點的移動軌跡受道路布局限制，并且通過GPS以及電子地圖等可以很方便地獲得車輛的位置和速度等信息，所以使得基于地理位置的路由協議[5～7]更適合VANET。本文將重點介紹VANET中的一種城市環境下的地理路由（reactivemode of road-based using vehicular traffic routing，RBVT-R[6]）協議，并針對該協議在路由建立及分組轉發模式上的缺陷，提出改進策略，以提升RBVT-R協議在分組交付率和端到端平均時延等方面的性能。

2 現有RBVT-R協議

RBVT-R協議是一種城市環境下基于實時路況信息的反應式地理路由協議。當源節點向目的節點發送數據時，要先尋找路由，建立數據分組的傳輸路徑。與錨路由機制[8]類似，源節點與目的節點之間建立的路由是數據分組傳輸所需經過的所有道路交叉口組成的序列。RBVT-R協議的路由建立過程包括路由發現和路由回復兩個步驟，如圖1所示，具體流程如下。

（1）源節點產生一個 RD（route discovery，路由發現）分組，該分組的頭部包含源節點的名稱和位置信息、目的節點的名稱。因為目的節點不在源節點的傳輸范圍內，所以RD分組的頭部不包含目的節點的位置信息。

（2）從源節點開始，各中間節點在其傳輸范圍內依次通過改進的洪泛機制[9]廣播該RD分組，即當一個中間節點收到上一跳轉發節點發送的RD分組后，它不會立刻轉發該分組，而是等待一段時間，當等待時間結束，且在同一路段上沒有其他離上一跳轉發節點更遠的節點轉發該RD分組時，該中間節點才轉發此RD分組，如圖1（a）所示。當RD分組經過一個路口時，會將該路口的信息加入到RD分組的頭部。此洪泛過程重復進行，直到RD分組達目的節點。

（3）當目的節點接收到RD分組后，按RD分組頭部的路口序列信息，原路返回一個RR（route reply，路由回復）分組。當源節點接收到RR分組后，則路由建立成功。如圖 1(b)所示，建立的路由為：I1-I6-I7-I4-I5-I8。

當路由成功建立之后，源節點就開始向目的節點發送數據。此時數據分組是按照建立的路口序列的順序依次進行轉發。在相鄰兩個路口的一個路段上，數據分組的轉發采用改進的地理路由機制，即每次都選擇傳輸范圍內，距離下一個目標路口最近的節點進行轉發。

圖1 RBVT-R協議的路由建立過程

3 RBVT-R協議的改進

雖然RBVT-R協議采用改進的洪泛機制建立路由，并且通過改進的地理轉發機制轉發數據分組，使得路由性能在一定程度上得到了改進，但是該路由協議也存在一些問題，主要包括以下兩方面。

·雖然RBVT-R協議在路由建立過程中采用了改進的洪泛機制，能在一定程度上解決廣播風暴問題，但是該機制在路由發現過程中沒有考慮到道路車輛密度對分組傳輸的影響，使得建立的路由穩定性不高，容易發生數據分組傳輸時延大，甚至分組丟失等情況。

·RBVT-R協議在相鄰兩個路口之間轉發數據分組時，當前攜帶分組的節點選擇的是其傳輸范圍內距離下一個目標路口最近的節點作為下一跳轉發節點，這種轉發方式沒有考慮到車輛行駛方向和數據分組的轉發方向 （即數據分組到下一個路口的指向）之間的關系，有可能會導致分組在同一路段上反復傳輸，增加分組傳輸的時延。

根據RBVT-R協議中存在的問題，提出了一種改進算法。該算法包括兩個部分，分別是對路由建立過程的改進和對數據分組傳輸過程的改進。

3.1 路由建立過程的改進

針對RBVT-R協議在路由發現過程中，其改進的洪泛機制沒有考慮到道路車輛密度對路由穩定性影響的問題，在改進的算法中提出了一種逐段式道路車輛密度自主估算方法，并將估算出的道路車輛密度用于改善路由發現過程中的洪泛機制。

3.1.1 逐段式道路車輛密度自主估算方法

如圖2所示，在一個路段上，當前的分組轉發節點為ni，下一跳轉發節點為nj，根據當前兩個節點的鄰居節點的數量以及它們之間的距離，估算這兩個節點所在區域一跳范圍內的路段的車輛密度，計算式如下：

其中，Nij=Ni∪Nj是兩個節點 ni和 nj的鄰居節點的總數，它不是鄰居節點數的單純相加，因為節點ni和nj互為鄰居節點，它們之間存在共同鄰居節點，如圖2中三角形節點所示，Nij對共同的鄰居節點只添加一次；dij是節點ni和nj之間的距離，R是無線傳輸半徑。2R是因為無線信號是全方位傳播的，因此其鄰居節點分布也是全方位的。

3.1.2 RBVT-R協議洪泛機制的改進

在RBVT-R協議采用的改進洪泛機制中，中間節點在收到RD分組后會等待一段時間，直到等待時間結束才進行判斷，決定是否轉發該RD分組，等待時間的計算如式（2）所示：

其中，dmin=min{d,Range}，d是RD分組的接收節點與發送節點之間的距離，Range是無線傳輸范圍，MaxWT是最大等待時間。

但是，這個改進洪泛機制只考慮了RD分組接收節點和發送節點之間的距離，沒有考慮到兩節點所在區域一跳范圍內的車輛密度，本質上還是一種貪婪轉發策略，因此存在頻繁發生局部最大的問題。針對這個問題，下面結合自主獲取的道路車輛密度對此等待函數進行了改進。

通過GPS獲得RD分組發送節點ni和接收節點nj之間的距離dij，根據式（1）獲得兩個節點之間的道路車輛密度ρij。根據參考文獻[10]中的多標準映射函數，可以得到包含距離和車輛密度這兩個參數的等待函數計算式：

3.2 數據分組傳輸過程的改進

當路由成功建立之后，源節點開始向目的節點發送數據，此時它會把建立的路口序列保存到數據分組的頭部，數據分組就按照這個序列進行轉發。分組從源節點到目的節點的轉發過程實質上就是按照建立的路口序列中的路口順序，從一個路口轉發到下一個路口，不斷重復直到到達目的節點。

針對RBVT-R協議中數據分組在同一路段反復傳輸的問題，在改進的算法中提出了一種基于方向和位置預測的分組轉發方法。該方法需要考慮車輛節點之間鏈路的有效持續時間并比較各個節點的轉發優先權值，下面首先分析了上述兩個內容，然后在此基礎上提出了基于方向和位置的分組轉發方法的完整方案。

3.2.1 鏈路有效持續時間

車輛之間相對方向關系有：同向行駛（其中同向行駛根據前后車輛的車速大小還分為趕超和落后兩種情況，分別如圖3、圖4所示），相向行駛如圖5所示，背向行駛如圖6所示。上述4種情況下，車輛之間的鏈路有效持續時間分別如式（4）～式（7）所示。

同向行駛（趕超）：

同向行駛（落后）：

相向行駛：

圖3 車輛A趕超車輛B的相對位置關系

圖4 車輛B逐漸遠離車輛A的相對位置關系

圖5 A、B相向行駛的相對位置關系

圖6 A、B背向行駛的相對位置關系

背向行駛：

其中，VA、VB分別為節點 A和 B的行駛速度，R為節點的傳輸半徑，dAB為節點A和B之間的相對距離。由以上式子可以看到，同向運行的車輛節點之間的鏈路有效時間是最長的，因此在路由選擇過程中應首先考慮在同向車輛中選擇下一跳轉發節點，這樣可以選擇更加穩定的路徑，提高路由協議的性能。

3.2.2 節點轉發優先權值計算

假設，當前攜帶數據分組的節點為S，待選的下一跳轉發節點為A。首先，根據節點S與A之間的相對關系，選擇對應的鏈路有效持續時間計算公式計算lifetimeSA；然后，采用式（8）預測經過Δt時間后節點A的位置：

其中，(xA,yA)為節點A的當前位置，(vAx,vAy)為A的速度，(xA′,yA′)為經過 Δt時間后節點 A 的位置。

通過地圖獲得下一個將要到達的路口Ii的位置(xIi,yIi)，節點A在經過Δt時間后與路口Ii之間的距離DAIi為：

根據鏈路有效持續時間lifetimeSA以及節點A經過Δt時間后與下一個路口Ii的距離DAIi，計算節點A的優先轉發權值為：

其中，MaxLifetime是文中設定的一個鏈路時間的上限值，用來約束在車輛同向行駛且速度很相近的情況下，鏈路時間無限大的情況，lifetimeSA不能超過該上限值；Dp=DAIi/DSIi代表了待選節點A距離目標路口的遠近程度，其中DSIi為節點S到目標路口Ii的距離，Dp越小代表A在經過時間Δt后距離路口Ii越近；α、β分別是鏈路有效持續時間和節點A到路口距離的加權值，且α+β=1，它們的取值大小代表了各參數對計算結果的影響程度，根據節點運動方向和分組轉發方向之間的關系不同，α、β的取值也不同。

3.2.3 基于方向和位置預測的分組轉發

通過前面的分析，下面提出一種基于方向和位置預測的分組轉發方案，具體的分組轉發過程如下。

（1）攜帶數據分組的節點S在選擇下一跳轉發節點時，首先根據鄰居列表中鄰居節點的位置判斷在分組轉發方向上是否有可轉發的節點，也就是在S和下一個路口之間是否有節點，若有，則進行下一步，否則就由節點S暫時攜帶該數據分組，等待可轉發車輛的出現。

（2）首先選擇和分組轉發方向相同的節點，若沒有，則再選擇反方向上的節點，然后根據鄰居列表中鄰居節點的速度大小和方向等信息，計算S和它們之間鏈路的有效持續時間和這些節點在Δt時間后的位置，根據式（9）得到這些鄰居節點到下一個路口Ii的距離，再計算各節點的轉發優先權值。

（3）節點S選擇優先權值最大的節點轉發分組。

4 仿真分析

采用基于VanetMobisim和NS-2的仿真平臺。使用VanetMobisim進行車輛移動模型的模擬，并在NS-2上實現了對RBVT-R協議的改進，將改進后的路由協議叫作IRBVT-R（improved RBVT-R）。

車輛節點的移動模型采用VanetMobisim中帶有路口管理的智能駕駛者模型 （intelligent driver model with intersectionmanagement，IDM-IM）。采用南京市新街口附近2 000m范圍內的道路布局作為仿真場景，詳細的仿真參數見表1，所有道路交叉口都設有紅綠燈。仿真結果如圖7、圖8所示。

表1 仿真參數

從圖7、圖8中可以看出，隨著車輛節點數的增加，RBVT-R和IRBVT-R兩個協議的分組交付率都增大，并且端到端平均時延都減小。這是因為這兩個協議都結合了實時的道路車輛信息，在車輛節點數很少時，道路車輛密度小，節點的可連接性差，分組在轉發時會經常因找不到下一跳轉發節點而被暫時攜帶，甚至被丟棄，從而導致端到端平均時延大，且分組交付率低；隨著車輛節點數的增加，道路車輛密度逐漸增大，節點的可連接性提高，使得分組能被及時可靠地轉發，從而提高了分組交付率，并減小了端到端平均時延。

從圖7、圖8中還可以看出，IRBVT-R協議在分組交付率和端到端平均時延這兩個指標上，其性能都要優于RBVT-R協議。這是因為IRBVT-R協議在路由建立階段考慮了道路的車輛密度，選擇車輛密度大的路段作為分組傳輸的路徑，提高了所建路由的穩定性，并且在分組傳輸階段，考慮了車輛行駛方向與分組轉發方向的關系，優先選擇與分組轉發方向相同且轉發優先權值最大的車輛作為下一跳轉發節點，減小了分組在同一路段重復傳輸的概率，從而減小了端到端平均時延，并提高了分組交付率。

5 結束語

VANET是由車輛節點組成的Ad Hoc網絡。VANET路由協議的最大挑戰就在于車輛節點的移動導致網絡拓撲的頻繁變化以及城市環境下節點的移動受道路布局的限制導致節點分布不均勻。本文在現有的RBVT-R協議的基礎上，提出了一種改進的IRBVT-R協議，該協議在路由建立階段考慮了道路的車輛密度，并且在分組傳輸階段還考慮了車輛行駛方向與分組轉發方向的關系，提高了分組傳輸的可靠性。仿真結果表明，IRBVT-R協議在分組交付率和端到端平均時延等方面，其性能都要優于RBVT-R協議。

1 胡云斌,夏瑋瑋,宋鐵成等.一種應用于VANET的改進GPSR路由協議.2009通信理論與技術新發展——第十四屆全國青年通信學術會議論文集,大連，中國，2009

2 Toor Y,Muhlethaler P,Laoriti A.Vehicle Ad Hoc networks:applications and related technical issues.IEEE Communications Surveys&Tutorials,2008,10(3):74～88

3 Pei G,Gerla M,Chen T W.Fisheye state routing:a routing scheme for Ad Hoc wireless networks.Proceedings of 2000 IEEE International Conference on ICC,New Orleans,USA,2000:70～74

4 Das S R,Belding-royer E M,Perkins C E.Ad Hoc on-demand distance vector (AODV)routing.Proceedings of WMCSA’99,New Orleans,USA,2003

5 Karp B,Kung T H.GPSR:greedy perimeter stateless routing for wireless networks.Proceedings of the 6th annual International Conference on Mobile Computing and Networking(MOBICOM’00),Boston,USA,2000:243～254

6 Nzouonta J,Rajgure N,Wang Guiling.VANET routing on city roads using real-time vehicular traffic information.IEEE Transactions on Vehicular Technology,2009,58(7):3609～3626

7 Namboodiri V,Gao L X.Prediction-based routing for Vehicular Ad Hoc networks.IEEE Transactions on Vehicular Technology,2007,56(4):2332～2345

8 Lochert C,Mauve M,Hartenstein H,et al.Geographic routing in city scenarios.ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(1):69～72

9 Li D,Huang H Y,Li X,et al.A distance-based directional broadcast protocol for urban vehicular Ad Hoc network.Proceedings of IEEEWiCOM,Shanghai,China,2007:19～24

10 Egoh K,De S.A multicriteria receiverside relay election approach in wireless Ad Hoc networks.Proceedings of MILCOM,Washington DC,USA,2006:1～7