基于地理位置的VENET可靠路由協議

黃弘，湯翾

（西華大學數學與計算機學院，成都 610000）

基于地理位置的VENET可靠路由協議

黃弘，湯翾

（西華大學數學與計算機學院，成都 610000）

基于城市環境下車載自組織網絡的特點，提出基于地理位置的VENET可靠路由協議GCRR。充分利用電子地圖等提供的信息，通過道路的車流密度和車流量的關系計算道路權重，進而排序出有效的數據轉發路徑，并根據節點的移動方向和移動速度，并采用擴展的貪心轉發策略，從而實現數據的高效可靠傳輸。仿真實驗驗證GCRR算法的性能優于經典算法GPSR和GSR。

車載自組織網；路由；車流量

0 引言

車載自組織網絡（VANETs）是通過車輛與車輛之間、車輛與路邊設施之間的通信的Ad Hoc的網絡，形成一個大范圍的無線移動網絡。車載自組織網絡具有不同于其他無線網絡的特征，例如，具有大量的移動節點、拓撲結構頻繁變化、節點的移動軌跡受限、可借用外部輔助信息支持和QoS需求多樣性[1]。

國內外現有的路由協議有基于拓撲的路由協議、基于位置的路由協議和基于道路設施和車載設備的路由協議。而基于位置的經典路由協議有GPSR（Greedy Perimeter Stateless Routing）[2]，其主要采用貪心轉發策略。GSR（Graphic Source Routing）[3]，其提出采用電子地圖獲取道路的拓撲結構，然后利用Dijkstra算法獲得傳輸數據的最優路徑，但它未考慮網絡的連通性。GPCR（Greedy Perimeter Coordinator Routing）[4]采用的思想和GSR相似，而不同之處是此算法利用了節點自身的位置區判斷節點是否處于岔路口。

綜上所述，已有的經典協議的主要策略是基于節點之間的物理距離，并沒有考慮道路的連通性，而結合路段的車流量信息就可以選擇有較好連通性的道路，所以，本文提出了一種城市環境下基于位置及連通性的車輛自組網可靠路由協議GCRR（Geography-based and Network Connectivity Reliable Routing），并考慮了車流量及車流密度的關系。

1 基于地理位置的路由協議

1.1 基本假設及相關術語定義

在該算法中，假設所有車輛都安裝GPS導航系統,車輛可以獲取各自的位置信息和其他車輛的位置,導航系統能為車輛提供城市街道的電子地圖等。本文中提到的節點是指車輛模型，假設處于十字路口的節點可以無線傳輸范圍內的非十字路口節點進行通信，而不在同一條道路上的非十字路口節點間不可通信。因此，數據的轉發過程,主要是從非十字路口節點向十字路口節點逼近，十字路口節點再轉發給非十字路口節點,直到數據轉發到目的節點為止。

1.2 協議設計

本文設計的路由協議主要包括兩個部分。首先，根據目的節點的位置，道路節點密度和路段長度選擇出錨節點序列；其次，錨節點之間的數據轉發基于節點的移動方向和移動速度，并采用擴展的貪心轉發策略。

（1）重要錨節點排序

根據城市街道的拓撲結構信息，將den表示為兩相鄰十字路口之間道路的車輛密度，其物理長度記為L；V表示兩相鄰十字路口的所有車輛的平均速度；T表示檢測中的短暫時間；r表示節點的無線傳輸半徑。首先根據每條路段的密度，選擇出路段密度大于下列閾值的路段：

此公式，是由車流密度公式和車流量的計算公式，且引用了水流量的計算方式，進行了積分運算，進而推導出的。根據公式（1）選擇出的道路作為數據轉發的路徑，同時提取需要經過的十字路口序列，并將此路徑信息序列存儲到數據包頭文件中。每當數據轉發到一個十字路口時，就根據數據包頭文件中的路徑序列信息選擇下一條路段進行數據的轉發。其中，當與某個十字路口相連的路段，如果有多余一條的路段滿足公式（1）的條件，則選擇接近最佳車流量的路段；當與某個十字路口相連的路段，如果沒有任何一條路段滿足公式（1），則選擇與下一個滿足條件的路段較近的路段。

如圖1所示，根據公式（1）從源節點S到目的節點D可得到的路徑為2-4-6-7，即存在數據包頭文件中的信息是2-4-6-7。

圖1 S到D數據轉發的錨節點選擇過程圖

對于車輛密度的信息，本文提供了一種估計每條路段車輛密度的方法。首先，所有節點都維護一張密度信息表，同時記錄鄰居節點信息和該路段的密度信息，每個節點廣播自身的ID。當有節點從十字路口進入路段時，該路段的密度den就加1，當該節點到達下一個十字路口時，den的值則表示剛經過路段的密度，并記時間戳為T，即在時間T內，此den有效。

（2）擴展的貪心轉發策略

同一路段上節點之間數據的傳輸，主要基于貪心模式，但由于本策略是對高級貪心算法AGF[5]的改進，故稱擴展的貪心轉發策略。首先，將十字路口也就是靜態節點作為在同一路段上的目的節點，數據在轉發給靜態節點過程中采用貪心模式；其次，該貪心策略基于節點的移動方向和移動速度轉發給滿足條件的節點，條件為公式（2）。

兩十字路口之間的直路間節點轉發方案為：首先判斷鄰居節點的運動方向是否同數據傳輸方向一致，再計算每個節點的權重，根據權重選擇下一跳節點。鄰居節點的權重依據公式（2）計算：

其中，v表示鄰居節點運動速度的大小，Dir表示節點運動方向，L表示可傳輸范圍內，離本路段目的靜態節點的距離。當Dir＞0時表示鄰居節點的運動方向與數據傳輸方向一致，Dir＜0表示相反。首先考慮Dir＞0的節點，且選擇權重大的鄰居節點作為下一跳節點，即選擇移動速度快的節點，若同向的不滿足條件，則選擇Dir＜0的方向的車輛，此方向是將數據轉發給權重小的節點，即距離目的靜態節點近的作為下一跳節點，當反方向的節點攜帶信息時，迎面遇到正方向滿足條件的節點時就立即轉發。

2 仿真實驗及結果分析

使用交通流仿真器VanetMobiSim與網絡仿真器NS-2相結合，模擬實際交通流場景，最后通過仿真結果比較、分析算法GCR與經典算法GPSR和GSR在車載自組織網中的性能。在仿真中，模擬區域范圍為4km×4km的城市環境，包括18個十字路口，節點數目分別取值（50，90，130，170，210，250），節點運動速度在30km/s～50km/s之間隨機取值，車輛的傳輸半徑200米，分組大小為512Bytes。

將GCRR與GPSR和GSR的性能比較，圖2表明GCRR的數據包投遞率明顯好于GPSR和GSR，且隨著趨近最佳車流量時，3種協議的數據投遞率都有增加趨勢。

圖2 數據包投遞率變化

圖3 吞吐量變化

圖3表明了路由協議的吞吐量變化情況，隨著趨近最佳車流量時，GCRR協議的吞吐量好于GPSR和GSR。

3 結語

隨著電子地圖等技術的發展，節點可以隨時獲取自己的地理位置，進而可改善車載自組織網的路由性能。已有基于地理位置的路由協議的主要策略是考慮節點之間的物理距離，這使得網絡不連通的情況下很難達到路由的高效與穩定。本文充分利用電子地圖等提供的信息，結合節點的位置及道路車流量信息提出了基于地理位置的VENET路由協議。該協議通過道路的車流密度公式和車流量公式的關系計算道路權重，進而排序出有效的數據轉發路徑；再根據節點的移動方向和移動速度，并采用擴展的貪心轉發策略，從而實現數據的高效可靠傳輸。仿真實驗驗證了GCRR算法的性能優于經典算法GPSR和GSR。

[1] 常促宇,向勇,史美林.車載自組網的現狀與發展.通信學報，2007，28（11）:116～126

[2] Willke T,Tientrakool P,Maxemchuk N.A Survey of Inter-Vehicle Communication Protocols and Their Applications.IEEE Communications Surveys&Tutorials，2009，11（2）:3～20

[3] Lochert C,Hartenstein H,Tian J.A Routing Strategy for Vehicular Ad Hoc Network in City Environments.In:Proc.of the IEEE Intelligent Vehicles Symposium，2003：156～161

[4] Lochert C,Mauve M,Fulbler H.Geographic Routing in City Scenarios.ACM Sigmobile Mobile Computing and Communications Review，2005，9（1）:69～72

[5] Naumov V,Baumann R,Gross T.An Evaluation of Inter-Vehicle Ad Hoc Networks Based on Realistic Vehicular Traces.In:Proc.of the ACM Int'l Symp.on Mobile Ad Hoc Networking and Computing，2006：108～119

Geography-Based and Network Connectivity Reliable Routing

HUANG Hong，TANG Xuan
（School of Mathematics and Computer Engineering,Xihua University,Chengdu 610000）

Based on the characteristics of the urban environment in VENETs network,proposes a new algorithm GCRR.Makes full use of the electronic map of road traffic density and the relationship based on the weight of the road.Sorts out the effective data forwarding path,and according to the moving direction and speed of mobile node,uses the extension of greedy forwarding strategy,so as to realize the high efficient and reliable transmission of data.Simulation shows the performance of GCRR algorithm is superior to the classic algorithms of GPSR and GSR.

VENET;Routing;Vehicle Flow

1007-1423（2015）02-0018-04

10.3969/j.issn.1007-1423.2015.02.005

黃弘（1987-），女，山東煙臺人，碩士研究生，研究方向為計算機網絡、車載自組織網絡

湯翾（1990-），女，湖北荊州人，碩士研究生，研究方向為圖形處理

2014-11-25

2014-12-16