VANETs路由協議綜述*

呂代剛，王靜蕾，李英豪

(1.鄭州職業技術學院，河南 鄭州450121；2.鄭州大學 電子信息工程學院，河南 鄭州451150；3.成都理工大學 地球物理學院，四川 成都610059)

VANETs路由協議綜述*

呂代剛1，王靜蕾2，李英豪3

(1.鄭州職業技術學院，河南 鄭州450121；2.鄭州大學 電子信息工程學院，河南 鄭州451150；3.成都理工大學 地球物理學院，四川 成都610059)

隨著車聯網VANETs(Vehicular Ad hoc Networks)應用日益受到關注,研究者對VANETs路由協議進行了深入研究。為此，首先總結VANETs的特點及應用，再介紹了基于位置的、基于拓撲以及基于廣播路由的概念，并著重分析和總結了近期路由協議的核心思想以及特點，此外，還從應用場景、前提條件、虛擬設備要求、電子地圖需求、路由恢復策略以及轉發模式六個方面對路由協議進行全面比較，最后，展望了VANETs路由技術的未來研究方向。

車聯網；路由協議；位置；廣播；拓撲；魯棒性

0 引言

隨著汽車技術的發展，城市車輛日益增長，交通壓力迅速上升[1]，交通事故頻頻發生。為此，迫切需要將現代技術引入交通系統，使得行駛人更安全、出行更便捷，交通更暢通。移動自組織網絡 MANET(Mobile Ad hoc Network)屬于無線通信網絡的一類，該網絡可以不需要基礎設施，或者僅需很少的基礎設施，形成完全移動的網絡。MANETs(Mobile Ad hoc Networks)具有一些顯著的特性，如動態拓撲、有限的帶寬、有限的能量等。

車聯網VANETs(Vehicular Ad hoc Networks)屬MANETs中的特例，具有一些獨特的特性。VANETs主要由兩部分組成：車與車（Vehicle to Vehicle，V2V）和車與設施（Vehicle to Infrastructure，V2I），如圖1所示。VANETs作為一種特殊的自組織網，它依靠無線通信技術實現V2V以及V2I的通信，使駕駛者能實時地知曉其他車輛部分信息和路況信息，并預先采取適當的措施，減少和避免交通事故[2]。

與MANETs不同，VANETs具有無限能量供應、移動受道路模型限制以及定位等特性。這些獨特的特性，為實施VANETs內的車間通信V2V和車與基礎設施V2I通信提出了挑戰。車輛的快速移動是VANETs網絡的最

顯著特性之一。節點的快速移動，導致拓撲結構變化不定，這為部署VANETs帶來許多技術挑戰[3]。尤其路由技術面臨著諸多問題。由于節點的移動，使得節點間的通信鏈路持續時間短、穩定性差，從而增加數據的丟失率，增大了數據傳輸時延。

為此，本文在介紹VANETs特性和應用研究的基礎上，綜述了現有 VANETs路由技術的特點，并分析路由協議的未來發展方向。

圖1 VANETs的網絡模型

1 VANETs的特性和應用

1.1 VANETs的特性

與傳統的移動自組織網絡MANET相比，VANETs具有如下特性：

(1)車輛頻繁的移動性

在VANETs中，車輛一直在移動，除了偶爾的臨時停車外。在不同的節點移動模型(Mobility model)中，即便是相同的VANETs算法，其性能也會迥然不同。

(2)車輛運動模式局限性

在VANETs中，車輛的運動模式受道路拓撲結構、周邊的環境以及交通規則等多個客觀因素影響。從另一個角度來說，受限的運動模式使得車輛的運動軌跡具有一定的規律性和預測性。

(3)車輛移動的高速性

在高速公路行駛的車輛其速度近 100 km/h；當兩車相向而行時，他們的相對速度就近200 km/h。因此，車輛間的交互時間非常短，通信窗口就很短。

(4)通信數據的多樣性

由于車輛裝載的傳感器型號的多樣化，促使通信數據種類豐富多樣。這也為各類數據間進行數據融合提供了條件。同時，各類的傳感數據使得系統設計具有更大的靈活性。

(5)計算、存儲能力的強大性

與傳統的無線傳感器網絡相比，VANETs的車輛均裝載了許多硬件設備，實現密鑰的存儲、加密解密的計算，并且可以記錄車輛位置、速度和加速度等行駛信息。這些特殊硬件設備為車輛提供了強大的計算能力以及大容量的存儲空間。

(6)基礎設施的輔助性

在構建VANETs網絡時，經常在某些地區或重要位置區域設立一定數量功能的路邊基礎設施，承擔網絡接入點的功能，為VANETs中的車輛提供服務。通常，隨著網絡建設的發展以及其覆蓋區域面積的擴大，基礎設施的數量也隨之增加。

1.2 VANETs應用

作為智能交通系統應用之一的VANETs，隨著系統功能不斷完善以及基礎設施的逐步加強，其應用研究范圍也隨之不斷延深，如圖2所示。從最初的保障車輛行駛安全到現在的改善交通管理、提升駕車環境，其應用在不斷地拓展。

圖2 VANETs的應用分類

VANETs應用可分以下兩類：

(1)安全相關的應用，如碰撞避免、輔助駕駛和交通流量優化等。如利用車輛間相互交換狀態信息提前通知司機，使得司機能根據情況做出及時、適當的駕駛行為，尤其是得知前面的車輛發生了事故后面的車輛來不及緊急剎車，造成一系列的連鎖碰撞現象，可通過VANETs中的安全應用進行有效避免。輔助駕駛是指幫助駕駛員快速、安全地通過“盲區”，如高速公路出入口、交通十字路口等。交通流量優化是指通過VANETs獲取實時的交通信息，綜合出與自身相關的車流量狀況，從而更高效地決定路徑規劃。

(2)其他應用，如支付服務(如自動計費系統)、位置相關的服務(如路徑規劃、找到最近的加油站)、信息服務(如Internet訪問)等。這類應用其主要目的是為乘客提供附加服務，享受娛樂、視頻點播、汽車會議等，如在線游戲和Internet接入等。

2 VANETs消息傳播機制

目前，現有的 VANETs消息傳播機制可分為三類：(1)基于地理位置(Position based)的消息傳播機制；(2)基于拓撲(Topology based)的消息傳播機制；(3)基于廣播(Broadcast based)的消息傳播機制。圖3列舉三類典型的路由方案，并將各協議進行歸類。

接下來，分別分析這三類消息傳播機制的特點。

圖3 典型的VANETs路由協議

2.1 基于位置的消息傳播機制

基于位置的消息傳播機制，源節點和目的節點利用它們的位置進行通信，根據數據包的目的節點位置以及鄰居節點的位置選擇轉發路徑。無需網絡內的全局信息。在實施過程中，可通過周期廣播的 beacons進行傳遞，也可通過位置服務請求獲取。該類機制需利用全球定位系統GPS獲取節點的位置信息，典型的基于位置的消息傳播機制有GPSR、DREAM[6-7]。

KARP B等人于 2000年首次提出 GPSR（Greedy Perimeter Stateless Routing）[5]消息傳播機制。在 GPSR機制中，源節點利用鄰居節點的位置計算鄰居節點離目標節點距離，并依據距離信息決策下一跳轉發節點。離目標節點最近的節點作為下一跳轉發節點，如圖4所示，源節點S向目標節點D發送消息。為此，源節點S向鄰居節點A、C、B發送轉發請求，鄰居節點A、C、B收到后，回復自己的位置信息。源節點S收到來自鄰居節點的消息后，依據鄰居節點的位置，計算離目標節點的距離，選擇離目標節點最近的節點作為下一跳轉發節點，即節點B。

圖4 GPRS消息傳播機制

基于位置的消息傳播機制在消息傳播過程中，無需網絡拓撲，僅基于鄰居節點及目標節點的位置信息。該類機制的優/缺點如下。

(1)優點：在節點高速移動的環境中，具有高的性能。能夠應對車輛的快速移動；無需源節點至目的節點的全局路由，降低了系統的處理開銷；更適應節點分布式環境。

(2)缺點：需要GPS提供位置，一旦 GPS不能正常工作，可能會導致消息傳播機制失效；道路障礙物影響距離的計算；需beacon包。

2.2 基于拓撲的消息傳播機制

基于拓撲的消息傳播機制在決策路由時，主要利用鏈路信息選擇從源節點至目的節點的消息傳播路徑。如 DSDV(Destination-Sequenced Distance-Vector)[8]、OLSR(Optimized Link State Routing)[9]屬典型的基于拓撲路由。依據工作方式，基于拓撲的路由協議可進一步分為先應式(Proactive)和反應式(Reactive)兩類。

在先應式路由協議中，每個節點先建立到網絡內其他節點的路由表，并且實時對路由表進行維護。先應式路由協議采用預先建立路由表的策略，當需要進行傳遞數據包時，只需進行查表，無需再進行路由發現，降低數據傳遞時延。但是，在拓撲動態變化的VANETs中，預先建立路由表是非常困難的，開銷很大。此外，維護路由表的開銷也不容忽視。

與先應式路由協議相比，反應式路由協議不是預先建立路由表，而是當節點需要數據傳輸時，才啟動路由發現工作，并且節點只需建立到其他部分節點的路由表，而不是像先應式路由協議要建立所有網絡內節點的路由表。

DSR(Dynamic Source Routing)[11]和AODV(Ad-hoc Ondemand Distance Vector)[13]屬經典的基于拓撲路由協議。然而，經研究實證，DSR和AODV難以應對VANETs內節點的高速移動。當節點高速移動，產生動態的拓撲，延緩DSR和AODV收斂速度，產生了大量的不可靠路由，由此產生的開銷無法容忍。為此，研究者提出一些改進協議。文獻 [9]提出基于AODV的改進路由協議PGB (Preferred Group Broadcasting)。盡管PGB方案通過降低轉發數量提高路由的穩定性，降低因路由發現所產生的開銷，但是轉發數量的減少會增加延時。一旦PG為空時，路由發現失敗。

概括來說，基于拓撲優/缺點如下：

(1)優點：依據拓撲信息，提供從源節點至目的節點路由表，降低了數據包傳遞時延；能夠發送單播、組播及廣播類消息；無需beacon包。

(2)缺點：由于需要路由發現和路由維護，增加了額外開銷；由于依據拓撲信息建立路由，難以應對高速移動的車輛環境；會出現不必要的路由泛洪。

2.3 基于廣播路由協議

廣播路由協議就是將數據包向通信范圍內的所有節點進行傳遞。最簡單的廣播方式就是泛洪。泛洪機制只適合節點數量較少的情況，一旦節點數量較多時，多個節點同時廣播數據，相互競爭信道，導致廣播風暴問題。為此，研究者提出眾多的基于泛洪的改進策略。

文獻[18]提出面向城市的多跳廣播UMB(Urban Multi-Hop)協議。UMB首先利用節點通信范圍及密度對道路分段，并采用兩種模式傳遞數據：定向廣播交叉口廣播。在定向廣播模式中，首先引用鏈路層的RTB/CTB握手機制尋找道路中最遠的鄰居節點，再將此節點作為下一跳

轉發節點。而在交叉口廣播模式中，先在交叉口裝設轉發器，利用轉發器向不同路段的鄰居節點進行定向廣播?？梢?，UMB方案的實施是以電子地圖、轉發器為前提條件。

文獻[19]提出了REAR(Receipt Estimation Alarm Routing)方案。REAR方案先利用信標消息實現節點間信息的交互。一旦收到廣播數據包后，節點與鄰居節點進行比較，判決自己是否是最佳的轉發節點，若是，則繼續廣播數據包，否則由鄰居節點承擔數據包的轉發任務。

文獻[20]提出基于退火算法的多跳車輛廣播MHVB (Multi-Hop Vehicular Broadcast)方案。MHVB首先利用退火算法計算退火區域。處于退火區域內的節點無需繼續廣播數據包。接收到數據包的節點采用交通擁塞檢測算法計算需等待多久方可轉發數據包，在時間未到之前，就處于等待狀態。如果交通擁塞，需延長等待時間。

文獻[21]針對緊急消息廣播，提出了BROADCOMM方案。BROADCOMM先依據MAC層協議的傳輸距離將高速公路劃分多個虛擬的區域。處于區域中心位置或臨近中心位置的節點作為該區域的Reflector節點。Reflector節點承擔與鄰居Reflector節點的通信，控制數據包的廣播，并管理區域內節點數據包的接收、發送。

文獻[22]提出CAID方案。在CAID方案中，持有數據包的節點在選擇下一跳轉發節點時，先計算鄰居節點與數據包的相關性，將具有最大相關性的節點作為最佳下一跳轉發節點。相關性包括數據包的相關性(如產生時間)、車輛相關性(如車速)以及信息相關性。

上述廣播方案的特點總結如表1所示。

表1 廣播路由協議總結

此外，在設計廣播協議時，應考慮到達率Reachability、時延 Delay、平均開銷 Overhead以及碰撞率 Collison 4個參數，可分別按式(1)～式(4)進行計算。

其中N為網絡內節點數，L為最大傳輸距離，R為廣播次數。Ri表示第i輪廣播。、分別表示源節點在第i輪廣播產生數據包的時刻、網絡中最后一個節點收到數據包的時刻。Mi表示在第i輪廣播中轉發了數據包的節點數，Ki表示在第i輪廣播中收到數據包的節點數，Ci表示在第i輪廣播中發生數據包碰撞的次數。

3 總結與展望

表2分別從應用場景、電子地圖需求、路由恢復策略以及轉發模式四個方面對路由協議進行總結和比較。從表2可知，不同的路由協議應用場景不一，解決問題的出發點也各不相同。

表2 不同路由協議對比

從分析結果可知，VANETs中的路由協議應對車輛的快速移動具有魯棒性，必須具有自適應能力，同時控制開銷少、可擴展性強。下面在分析各類路由協議的基礎上，預測VANETs路由協議的發展方向。

(1)魯棒性

現有的路由協議的前提條件過于理想化，在實際環境中，難以實現這些條件。此外，VANETs內一些不確定因素對路由協議的穩定性提出挑戰。因此，路由協議的魯棒性必須考慮。

(2)安全性

現有的路由協議僅追求路由性能，未考慮路由協議的安全需求，包括用戶數據授權、隱私保護以及通信安全。因此，如何在路由協議中引入安全保障是亟待解決的問題。

(3)仿真平臺統一性

現有的VANETs路由協議實驗仿真平臺各不相同，未統一，并且一些路由協議的道路結構、車輛移動模型過于簡單，設定的實驗仿真場景與實際場景差異較大。因此，需進一步研究VANETs路由協議的仿真平臺。

總體之言，國內外的研究人員針對VANETs不同場景提出了眾多的VANETs路由協議，然而，在VANETs路由協議研究領域中，仍存在許多問題需解決。

[1]ZEADALLY S，HUNT R，CHEN Y S，et al.Vehicular ad hoc networks(VANETS)：status，results and challenges[J]. Science Business Media，2010，3(6)：23-39.

[2]李元振，廖建新，李彤紅.城市場景車載 Ad Hoc網絡競爭轉發關鍵參數分析[J].電子學報，2011，38(5)：1154-1158.

[3]LEE J H，CHILMAKURTI N.Performance analysis of PMIPv6 based network mobility for intelligent transportation systems[J]. IEEE Transaction on Vehicular Technology，2011：23-32.[4]CHAN E，LI W.Two-step joint scheduling scheme for road side units(RSUs)-based Vehicular Ad Hoc Networks (VANETs)[C].Databse System for Advanced Application (DAS-FAA’2011)，2011：569-574.

[5]KARP B，KUNG H.Greedy perimeter stateless routing for wireless networks[C].Proceedings of ACM International Conference on Mobile Computing and Networking，2000：243-254.

[6]BASAGNI S，CHLAMTAC I，SYROTIUK V，et al.A distance routing effect algorithm for mobility(DREAM)[C].In Proceedings of ACM International Conference on Mobile Computing and Networking，2008：76-84.

[7]HAAS Z，PEARLMAN M.The performance of query control schemes for the zone routing protocol[J].ACM/IEEE Trans. Net.，2012，9(4)：427-438.

[8]PERKINS C，BHAGWAT P.Highly dynamic destination sequenced distance vector routing(dsdv)for mobile computers[C]. Comp.Commun.Rev.，Oct.2010：234-244.

[9]WEI R，DONG Y N，ZHAO H T.Improvement on locationbased routing protocols in wireless mesh networks[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science),2012，32(1)：75-82.

[10]LI X，CUTHBERT L.On-demand node-disjoint multipath routing in wireless ad hoc network[C].In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks(LCN04).Washington,DC,USA：IEEE Computer Society,2004,419-420.

[11]JOHNSON D B，MALTZ D A，HU Y C.The dynamic source routing protocol for mobile ad hoc networks[C]. IETF MANET Working Group,Tech.Rep,February 2007：34-42.

[12]CHAN E，LI W.Two-step joint scheduling scheme for road side units(RSUs)-based Vehicular Ad Hoc Networks (VANETs)[C].Databse system for Advanced Application (DAS-FAA’2011),2014：569-574.

[13]PERKINS C E，BELDING E M，DAS S R.Ad hoc ondemand distance vector(aodv)routing.RFC Experimental 3561[EB/OL].(2013-07)[2014-11-10]：http：//rfc.net/ rfc3561.txt.

[14]李昕，李剛.基于網關信息素更新的 MANET接人 Internet開銷控制方法[J]．電子學報，2010,38(4)：870-874.

[15]徐會彬,夏超.VANETs路由綜述[J].計算機應用研究, 2013,30(1)：1-6.

[16]LIU K，LEE V C.RSU-based real-time data access in dynamic vehicular systems[J].Vehicular Technology,IEEE Transactions on,2010,56(6)：3337-3347.

[17]RAHBAR H,NAIK K,NAYAK A.Dynamic time-stable geocast routing in vehicular ad hoc networks[C].Proceedings of the 9th IFIP Annual Mediterranean,2010：1-7.

[18]KORKMAZ G，EKICI E，OZGIINER F，et a1．Urban multi-hop broadcast protocol for inter-vehicular communication systems[C]．Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Network，Philadelphia：ACM Press，2004：76-85．

[19]JIANG H,GUO H,CHEN L.Reliable and efficient alarm message routing in VANET[C]．Proceedings of the 28th International Conference on Distributed Computing Systems Workshops，Beijing，2008：186-191.

[20]OSAFUNE T，LENARDI M．Multi-hop vehicular broadcast (MHvB)[C]．Proceedings of the 6th International Conference on Telecommunications．Chengdu，2005：757-760．

[21]DURRESI M，DURRESI A，BAROLLI L．Emergency broadcast protocol for inter-vehicle communications[C]．Proceedings of the 11th International Conference on Parallel and Distributed Systems，Fukuoka，2005：402-406.

[22]ADLER C，EICHLER S，KOSCH T，et a1．Serf-organized and context adaptive information diffusion in vehicular ad hoc networks[C]．Proceedings of the 3rd International Symposium on Wireless Comunication Systems，Valencia，2006：307-311.

VANETs routing protocols：issues and challenges

Lv Daigang1，Wang Jinglei2，Li Yinghao3
(1.Zhengzhou Technical College，Zhengzhou 450121，China；2.Department of Electronically and Information Engineering,Zhengzhou University，Zhengzhou 451150，China；3.College of Geophysics,Chengdu University of Technology，Chengdu 610059，China)

With the development of vehicular ad hoc networks(VANETs)application,VANETs routing protocols is in-depth studied by researcher.Firstly,the characteristic features and application of VANETs are described.Then this paper introduces the conception of position-based routing,topology-based routing and broadcast-based routing,and emphatically analyzes and summarizes the core thoughts and characteristics of recent routing protocols.Moreover,a qualitative comparison of these routing protocols in terms of application environment,recovery strategy,forwarding method and digital map requirement is given in this paper.Finally,this paper discusses the directions for further for researchers of VANETs routing protocols.

vehicular ad hoc networks；routing protocol；position；broadcast；topology；robustness

TP393

A

0258-7998(2015)04-0016-04

10.16157/j.issn.0258-7998.2015.04.001

2014-11-10)

呂代剛（1975-），男，碩士，講師，主要研究方向：計算機應用技術，信息處理，電子器件設計。

王靜蕾（1979-），女，碩士，講師，主要研究方向：計算機網絡，數據挖掘，集成架構。

李英豪（1980-），男，博士，講師，主要研究方向：圖形圖像處理及地理信息系統。

2013年河南省科技廳重點科技攻關項目（132102210181）