VANET城市場景下一種優化的地理信息路由協議

趙博龍，楊 潔

(中國航空計算技術研究所，陜西 西安710119)

0 引言

車聯網 VANETs(Vehicle Ad Hoc Networks)已成為研究熱點，車聯網的實施有利于提高行駛安全性[1-2]。車輛的快速移動及車輛分布的不均勻性，給VANETs路由協議設計提出了挑戰。相比于基于拓撲路由，地理信息路由更適合應用于拓撲動態變化的車聯網中，能更好地適應拓撲結構變化，具有簡單高效、低負載等特點。因此受到更廣泛的關注[3-6]。

地理信息路由常采用貪婪轉發策略，其是從鄰居節點中選擇離目的節點最近的節點作為下一跳轉發節點。該策略復雜度低、易實現，適用于動態變化的網絡[7]。然而，真實環境中，僅利用鄰居節點和目的節點位置信息決策路由的地理信息路由并不具有良好的路由性能。因為，隨著源節點與下一跳轉發節點間距離的增加，信號衰減和數據包丟失率也隨之增加[8-9]，這就降低了數據包傳輸成功率，并增加了路由開銷。

在2000年，B.Karp等人提出基于地理信息路由協議 GPSR（Greedy Perimeter Stateless Routing）[10]。 GPSR 協議實施貪婪轉發策略，通過距離值選擇下一跳節點，離目標節點最近節點作為下一跳節點。然而，僅采用簡單的貪婪轉發策略，很容易陷入局部最小化，即路由空洞。

文獻[11]提出了基于GPSR的改進協議GPCR。當遭遇局部最小化(空洞)時，采用邊界轉發，數據包攜帶節點引用右手規則進行尋找下一跳轉發節點。此外，文獻[7]提出一種基于感知空洞形狀的分段貪婪路由EMCG(Easy Modeling Greedy Routing)協議。EMGR協議采用了空洞邊界探測包，通過這些探測包收集位于邊界節點的信息，并依據這些信息，獲取空洞形狀，最后依據形狀，尋找最合適的轉發節點。然而，該協議需要耗盡過多資源收集邊界節點信息。

文獻[12]提出了基于在線導航系統的RBVT-R協議。通過一系列高網絡連接率的十字路口建立源節點與目的節點間的路徑。然而，由于路由決策過程中需要使用實時的交通信息，致使節點能夠感知城市地圖，增加了復雜度，提高了RBVT-R路由對網絡條件的適應能力。

上述的路由協議均在強調如何提高數據包轉發率問題，但是這些路由協議并沒有考慮到城市環境下，長距離傳輸數據包的成功與否受多方面因素影響。特別是，這些協議均沒有考慮節點間的移動的相對方向以及鏈路質量。為此，本文提出面向VANETs城市場景下一種優化的地理信息路由協議，記為IGR(Improved geographical)。IGR協議在選擇下一跳轉發節點時，不再使用貪婪轉發策略，而是結合節點的位置、無線鏈路質量以及節點的移動方向這三方面信息，并將這些信息融合成競爭資本，最后，依據競爭資本選擇下一跳轉發節點。仿真結果表明，提出的IGR協議能夠有效地提高數據包傳遞率、縮短了端到端傳輸時延，減少了平均跳數。

1 IGR協議

在動態拓撲網絡中，僅基于單一指標選擇從源節點至目的節點的路由可能是次優解。眾多的因素影響了車輛間無線鏈路，如車輛行駛方向、距離以及鏈路質量。當數據包攜帶車輛需要尋找下一跳轉發節點時，該車輛應該依據鄰近車輛離目的節點的距離、行駛的相對方向以及鏈路質量等信息決策路由，進而選擇最優的數據包轉發節點。為此，提出的IGR協議將距離、行駛相對方向以及鏈路質量三項信息融合成一個競爭資本函數，源節點就通過競爭資本函數擇優選擇下一跳轉發節點。

1.1 臨近率

數據包攜帶車輛計算鄰居車輛的臨近率AR(Approaching the destination Ratio)，其反映了鄰居車輛離目的節點距離的遠近。假定車輛i的臨近率ARi定義如式(1)所示。

其中Ds表示源車輛離目的車輛的距離、Di表示車輛i離目的車輛的距離。從式(1)可知，臨近率AR反映了距離信息。AR越大，車輛離目的車輛越近，具有成為下一跳數據包轉發節點的優先權越大。

1.2 相對方向

不失一般性，可認為兩車輛之間要么以相同方向行駛，要么以相反方向行駛，并且車輛行駛方向受限于街道和十字路口。由于車輛行駛方向的兩極性，相比于反方向車輛間的路由，處于同方向行駛的車輛間的路由更趨于穩定[13]。

因此，將車輛行駛方向納入選擇下一跳數據包轉發的指標，將同方向的行駛車輛給予更高的轉發優先權。需要指明的是，同方向不是指兩車輛方向夾角為0°，而方向夾角小于預設的值，就認為兩車輛同向。下面計算方向夾角。

如圖 1所示，設定節點i在t1時刻的位置為(x1，y1)，在t2時刻它移動到了位置(x2，y2)。擁有數據包的節點C的位置是(xC，yC)，目標節點 d 的位置為(xd，yd)。在這種情況下，鄰居節點i的移動速度，數據包轉發方向vi與節點移動方向之間的切角φi由式(2)和式(3)計算得到。

圖1 方向計算示意圖

當 0≤φi≤π/2時，節點i與源節點同向行駛，否則逆向行駛，由于安全消息傳遞的后向性，只需要向同向行駛的后方車輛發送安全消息。因此，定義節點i的方向變量DRi：

除了考慮方向因素之處，在數據轉發過程中還需考慮無線信道質量。

1.3 Beacon接收率

假定車輛i，其一跳鄰居車輛集為Ni，則車輛i的Beacon接收率 BRR(Beacon Reception Rate)：

其中，表示第k個鄰居車輛在RRI時區內所接收到的beacon包的數量；|Ni|表示一跳鄰居集內含有的節點數目；T為周期，車輛周期性地發送 beacon包，例如，當T=0.5 s、RRI=7 s，接收了 10個 beacon包，則該車輛的 BRR等于0.714。

1.4 競爭資本函數

其中，Γ為評價函數，SPmax表示評價函數最大時的選擇概率，β為變量，其標識了路由指標的最大值 α1、α2、α3為三個指標的權值系統。

當式(7)的導數等于零時，Γi達到最大。因此，β為：

式(7)中各項分別取最大值時，可計算β值。ARmax值可依據車輛無線通信范圍以及仿真進行估計，可得ARmax=10，而方向最大值DRmax=1。beacon接收率BRR在0～1間取值，因此 BRRmax=1。SPmax為概率，SPmax=1。

2 性能分析

2.1 仿真模型

利用MATLAB軟件以及NS2建立仿真平臺，對提出的IGR協議進行仿真，并與GPCR和RBVT-R協議進行比較。主要考查數據包傳遞率PDR(Packet Delivery Ratio)、端到端傳輸時延EED(End to end delay)以及跳數HC(Hop Count)三方面的路由性能。

仿真區域選取上海市大小為3 968 m×1 251 m的矩形區域，含有370條道路、124個十字路口。在仿真過程中，利用STRAW(STreet RAndom Way)建立車輛隨機移動模型。

在仿真區域內，車輛數從100～350變化。每個車輛產生beacon包的周期為0.5 s，產生的數據包大小為512 B。詳細的仿真參數如表1所示。

表1 仿真參數

2.2 仿真結果及分析

本次實驗目的在于考查交通密度對IGR協議的性能影響。通過實驗，能夠觀察三個協議應對交通密度的性能。實驗中，車輛的速度設為50 km/h，數據包源車輛數為15個，密度數從100～350變化。仿真結果如圖2所示。

從圖2可知，GPCR協議的PDR性能最差，特別是在低密度區域。這主要是因為GPCR利用貪婪轉發策略去選擇下一跳數據包轉發車輛，即選擇離目的車輛最短路徑的車輛作為下一跳轉發車輛。由于車輛的快速移動，車輛間的鏈路是非常脆弱的，這就導致轉發至目的車輛的數據包非常少。然而，隨著車輛密度的增加，GPCR協議向目的節點成功轉發的數據包也隨之增加。此外，RBVT-R協議在車輛數增加時具有更好的性能，這是由于車輛數增加，網絡連接概率隨之提高，促進了更多的數據包轉發。相比于GPCR、RBVT-R，提出的IGR協議具有較好的性能，因為IGR協議從鏈路質量、方向以及距離三方面信息選擇下一跳轉發節點。

圖2 數據包傳遞率隨節點數的變化曲線

3個協議的數據包平均傳輸時延隨節點密度變化曲線如圖3所示。從圖3可知，提出的IGR協議的EED最小。原因在于IGR協議向目的節點傳輸數據包時選擇了最優鏈路的路徑，降低了因鏈路不穩定而引起的數據包丟失概率。然而，隨著車輛密度的增加，時延也隨之增加。由于車輛密度的增加，使得IGR協議需要消耗更多時間去決策下一跳數據包轉發節點。此外，從圖3可知，RBVT-R協議的EED隨車輛密度增加而呈下降趨勢，原因在于已建立的路由在較長時間內仍保持穩定，避免了頻繁建立路由，進而縮短了傳輸時延。

圖3 平均傳輸時延隨節點數的變化曲線

圖4描述了傳輸的平均跳數隨車輛密度的變化曲線。與GPCR協議相比，提出的IGR協議在向目的節點傳輸數據包時，需要更多的跳數，傳輸路徑更長。IGR協議在數據包傳遞率和平均時延方面優于GPCR協議。

3 總結

圖4 平均跳數隨節點數的變化曲線

為了滿足VANET城市場景下路由協議的性能要求，提出了一種地理信息路由的優化協議。提出的IGR協議在數據包轉發過程中，不再考慮傳統地理信息路由協議的基于地理位置貪婪轉發策略，而是利用源車輛離候選車輛間的相對移動方向、候選車輛離目的車輛間的距離以及beacon接收率三方面信息選擇下一跳轉發節點。仿真數據證實了IGR協議在降低數據包傳輸時延，提高數據包傳輸率方面的優越性。

[1]MISRA S，Venkata Krishna，SARITHA V.LACAV：an energyefficient channel assignment mechanism for vehicular ad hoc networks[J].J.Supercomput.，2012，62(3)：1241-1262.

[2]AKYIDIZ I F，MELODIA T，CHOWDHURY K R.A survey on wireless multimedia sensor networks[J].Comput.Netw.，2007，51(4)：921-960.

[3]CHEN Y，LIN Y.Dir：diagonal-intersection-based routing protocol for vehicular adhoc networks[J].Telecommunication systems，2010，3(5)：1-18.

[4]CHENG P，LEE K，GERLA M.Geodtn+nav：geographic dtn routing with navigator prediction for urban vehicular environments[J].Mobile Networks and Applications，2010，15(1)：61-82.

[5]DJAHEL S，GHAMRI-DOUDANE Y.Arobust congestion control scheme for fast and reliable dissemination of safety messages in vanets[C].In Proceeding of the 2012 IEEE conference wireless communications and networking，2012：2264-2269.

[6]GHAFOOR K，BAKAR K.A novel delay and reliability aware inter vehicle routing protocol[J].Network Protocols and Algorithms，2014，2(2)：66-88.

[7]范敏，謝思佳.基于空洞模型的地理位置路由改進算法研究[J].傳感技術學報，2012，25(11)：1556-1561.

[8]LEE K，LEE U，GERLA M.To-go：topology-assist geoopportunistic routing in urban vehicular grids[C].In Proceedings of the 2009 IEEE international conference on wireless on-demand network systems and services，Snowbird，2013：11-18.

[9]YAN G，OLARIU S.A probabilistic analysis of link duration in vehicular ad hoc networks[J].IEEE Transactions on Intelligent Transportation Systems，2012，12(4)：1227-1236.

[10]Ghafoor K Z，Mohammed M A.Routing protocols in vehicular ad hoc networks:Survey and research challenges[J].Network Protocols and Algorithms，2013，5(4)：39-83.

[11]LOCHERT C，MAUVE M，HARTENSTEIN H.Geographic routing in city scenarios[J].Mobile Computing and Communications Review，2015，9(1)：69-72.

[12]NZOUONTA J，RAJGURE N.Vanet routing on city roads using real-time vehicular traffic information[J].IEEE Transactions on Vehicular Technology，2009，58(7)：3609-3626.

[13]徐會彬.關于VANETs關鍵理論技術研究[D].博士學位論文，2014.

[14]SADIQ A，ABU BAKAR K.A fuzzy logic approach for reducing andover latency in wireless networks[J].Network Protocols and lgorithms，2011，2(4)：61-87.

[15]KAYHAN Z G，JAIME L，ALI S S.Improved geographical routing in vehicular Ad Hoc networks[J].Wireless Pers ommun，2015，80：785-804.