VANET中路由協議分析

吳振華，胡鵬

（南昌航空大學 軟件學院，江西 南昌 330000）

1 引言

車聯網在智能交通（ITS）上有著重要的意義。通過車聯網的研究，將會改善擁擠的路況，對車輛安全、交通事故偵查等都有很大幫助。在城市發展智能交通研討會中指出車聯網技術可使交通堵塞減少約60%；短途運輸效率提高近70%；現有道路網的通行能力提高2～3倍[1]。同時車聯網技術為現有的車輛定期檢查、排放控制、走私車及套牌車查處、盜搶車追蹤等管理工作，提供了更加簡單、快速、高效的手段。車聯網技術也在協助駕駛、交通信息收集、輔助交通管理、用戶通信管理等領域應用廣泛。隨著車聯網的應用需求近年興起了很多相關項目，如歐盟CarTalk2000、SAFESPOT、CVIS；美國PATH、EEE P1609、ISO TC204 WG16/CALM等。

VANET（vehicle ad-hoc network）是一種以汽車為節點的多跳自組織系統，是移動自組織網絡（MANET）在交通上的應用。由于車輛的移動速度快，拓撲結構易變，無線信道不穩定等特點，使通信中的多普勒效應較之其他慢速移動和靜態無線網絡嚴重。并且在真實道路環境中，無線信號受到復雜環境影響，易發生多徑衰落現象[2]。這些原因使傳統的物理層無線傳輸協議，在VANET中有一定的局限性。針對VANET的特殊環境，2010年IEEE提出了新的標準體系結構[3～5]。如圖1所示，包括1609協議棧和802.11p協議。1609.1規定應用層界面接口標準；1609.2針對車聯網的安全做出規定；1609.3規定網絡層的標準；1609.4規定LLC、MAC、PHY層標準，并且美國聯邦通信委員會(FCC)將通信頻率在5.855～5.925 GHz之間的頻譜分配于車聯網通信。其中包括7個信道，每個信道帶寬為10 MHz，數據率能達到3～27 Mbit/s[6]。802.11p通信協議規定通信距離達到1km，能夠滿足達到33 m/s移動速度的節點[7]。

圖1 IEEE車聯網體系結構

2 VANET路由面臨的問題

VANET通信主要表現在車與車（V2V, vehicle-to-vehicle）之間的通信以及車與路邊基礎設施(V2I, vehicle-to-infrastructure)之間通信。V2I的通信一般通過RFID（radio frequency identification）或Wi-Fi來實現。對于V2I不在一跳通信范圍內的，則需要通過V2V進行轉發，V2V的通信則較為復雜。由于 V2V通信中的節點是高速移動的汽車，其移動方向、速度和地理位置都不斷發生變化，以及VANET的運動場景復雜，節點分布不均勻，這些特性使路由存在以下問題。

1) 路由表有效期短。在拓撲結構頻繁變化的VANET中。中繼節點在通信范圍內的時間很短，使鏈路斷裂頻繁，路由表有效期極短。目前緩解這類問題的方法是基于位置的貪婪算法，該算法能有效地降低對中繼節點的敏感性，但仍不能從根本上解決路由表的有效期問題。

2) 路由發現開銷大。由于路由表的有效期短，使路由發現變得頻繁，增加了路由發現開銷。目前在優化路由發現開銷的算法中，基于簇的路由算法較為普遍，分簇能夠有效地降低路由發現過程中冗余數據分組，但是分簇的策略和簇維護的開銷也將成為新的問題。

3) 鏈路質量不穩定。由于車輛快速頻繁移動導致通信中的多普勒效應嚴重，在復雜的城市場景中，信號多徑衰落現象也將增加，這些使鏈路質量變得很不穩定。通過車輛移動規律，基于街道進行路由數據傳輸，可以有效地降低鏈路不穩定，但街道中車輛信息的實時獲取將成為新的問題。

4) 數據分組存儲攜帶時間長。城市場景中，車輛移動在不同時間段，移動具有不同的規律，如在上班高峰期，車輛集中于產業區，而下班高峰期車輛則集中于居民區，這使節點分布很不均勻，網絡分區現象嚴重，導致數據分組存儲攜帶時間長，增大數據分組交付延遲，并且降低數據分組的交付率。

如何保證源節點和目的節點間的有效通信是待解決的關鍵問題之一。因此，VANET的路由問題得到了學術界和工業界的普遍關注。本文對現有具有代表性的多數VANET路由協議進行分類分析和實驗對比。實驗結果表明，它們在適用場景、性能側重等方面具有各自的特點。

3 VANET路由協議分類

近年來，國內外在對MANET路由問題的研究基礎上，結合VANET自身特點，已經提出了很多具有實用價值的思想和方案。

范存群等提出一種提供高吞吐量的路由算法CRCN[8]，通過對 DSR[9]路由協議改進，提高數據的交付率和網絡吞吐量。但是在密集的VANET網絡中，這種利用其他節點進行數據分組多重轉發，顯著增加數據分組碰撞率和節點負載，將導致網路阻塞。 文獻[10]中提出的QLAODV路由算法，是AODV的改進算法。通過添加Q_Learing算法來確保路由的穩定性。該算法在拓撲表的維護上有所改進，但增加了拓撲維護的開銷。在AODV上改進的路由算法還有 DAODV(基于位置和移動方向)，AODV-DHCP(在鏈路斷裂上改進)路由算法，它們在鏈路質量上都有優化，但是在路由開銷和維護上沒有改善。CAREFOR[11]算法利用ping協議獲取節點的密集度，并通過車輛密集度度量數據分組的碰撞率，實現降低數據分組的碰撞，提高數據分組交付率的目的。

盡管上述算法已經針對VANET的特點做了相應改進，但在完全適應VANET上還存在較多不足：如拓撲結構不穩定、路由表有效時間短、鏈路斷裂頻繁、路由開銷大等。

針對VANET提出的路由算法也越來越多，從不同的角度可以將路由算法進行不同的分類。根據VANET的應用需求，可分為延遲容忍路由和非延遲容忍 2類路由算法[12]。延遲容忍路由有CMGR[13]、 SADV[14]、 D-greey 和 D-MinCost[15]等。非延遲容忍路由有 GPSR_L[16]、VRP[17]、LOUVR[18]等。本文根據VANET路由算法的特點，將現有協議分成以下 4類：1）基于位置貪婪路由算法（LGBRP）；2）基于為簇路由算法（CBRP）；3）基于錨節點路由算法（ABRP）；4）基于街道集路由算法（SBRP）。

3.1 基于位置的貪婪路由算法

在VANET中，通過GPS獲取位置信息更加準確，因此通過目的節點的位置去尋找路由，可以在一定程度上降低對中繼節點移動的敏感性，提高路由表的有效期。

Bilal M等[19]提出FMHR算法，是GPSR優化版。該算法在基于貪婪算法選擇最遠的下一跳同時，還考慮到下一跳的運行速度和運行方向，增加了鏈路的相對穩定性。但文獻[20]中指出車輛的運行方向很難精確確定，這也將大大增加計算負載和額外開銷。KMCT[21]也是基于位置的貪婪路由算法，但它們的策略不同，KMCT是通過車速和方向預測中繼車輛與目標車輛可保持最大的通信時間來選擇下一跳，它們優化了基于貪婪算法在鏈路質量上的缺點。

羅濤等在文獻[22]中提出ACR-BA廣播路由協議。該協議通過地理位置劃分候選節點集，通過RTF/ATF 2種控制分組和貪婪算法選舉唯一廣播轉發節點。該算法利用節點集的劃分，降低了冗余廣播分組的數量。但是在選舉唯一中繼節點時采用退避等待策略以及2次握手等策略，將增加廣播的延遲，并且該協議只適用于簡單的直道場景，對于復雜的城市街道難以實現。

RRMLI[23]是在路由恢復中改進的路由算法，在源節點和目的節點連接斷開時，利用已知的目的節點位置信息，利用貪婪算法沿著源到目的節點方向發送RREQ消息分組，進行路由修復。替代廣播泛洪尋找路由的算法，降低了路由修復開銷。文獻[24]中MOVE和文獻[25]中Geopps都是通過預測下一刻節點的位置，選擇更合適的下一跳攜帶轉發數據分組。在文獻[26]的 GFG、GOAFR 和文獻[10]的EBGR都是基于位置的貪婪路由協議。

單純基于位置的貪婪路由協議，不適用于稀疏的網絡場景與復雜的VANET場景，由于復雜的街道和建筑群嚴重阻擋了信號的傳輸，這些都將導致路由空洞或路由環路現象。也有很多文獻提到解決這些問題的方案，如右手規則、DFS(深度優先遍歷)[26]、PBR(基于預測路由)[27]，但是這些都不能很好地解決稀疏場景下的數據分組交付率和延時問題。

3.2 基于分簇路由算法

分簇路由是依據簇進行節點管理和數據轉發，降低路由發現開銷和廣播風暴風險，同時增加了網絡有效吞吐量。

胡升澤等在文獻[28]中提到的 LEACH算法是經典的分簇算法，為降低單個簇首的負擔，周期性地選擇簇首。由于VANET中節點移動的頻繁，簇首也在不斷更換中，因此該算法在VANET中將增加簇首的震蕩，增加網絡開銷。在VANET中基于分簇的路由算法簇劃分是研究的重要方向。APROVE[29]分簇算法，利用相似傳播算法，將移動相似的節點劃分一組，優化了分組的有效時間。ROMSGP[30]路由算法，同樣是利用了移動相似性進行簇劃分，通過將場景中節點移動方向歸類為4種，周期更新節點的移動方向，對于方向一致的鄰居節點歸類為同一個簇。以上2類算法優化了簇的有效時間，但是在動態的VANET中，簇成員變換頻繁，簇維護開銷相對增加。CBDRP[31]和 GvGrid[32]利用網格進行簇劃分。簇位置相對靜止，優化了簇維護開銷復雜度。而CBDRP是針對高速公路場景設計的；GvGrid是為固定源節點的城市場景設計的，它們可擴展性差。還有一些針對特殊場景提出的分簇算法，如MOHANMODE[33]提出一種應用于荒漠場景的 CBVRP分簇路由算法。文獻[34]中提出一種對能耗問題進行了優化的MLCRA分簇算法。

在簇的形成過程中，如何有效地適應網絡連通性是分簇路由協議需要解決的一個重要問題。如果簇首之間不可達，將可能導致網絡分離現象。對于拓撲結構易變的 VANET，維護簇穩定使網絡額外開銷增加。同時基于簇的路由算法在對簇首的依賴性較強，如何有效地組建穩固的簇和選擇合適的簇首是當前許多學者研究的焦點。

3.3 基于街道集的路由算法

在VANET中，節點移動的規律主要是沿著街道移動，具有可預測性。因此數據基于街道轉發，可以增加鏈路的穩定性，減少鏈路中斷率。

在文獻[35]中提出VADD路由算法利用街道地圖，去預測分組的交付延時。選擇合適的街道集作為路由路徑。該算法對路段信息沒有實時和準確的分析，存在路由空洞風險。而實時獲得路段信息是VANET中的一個難點，Nzouonta J等在文獻[26]中提出RBVT-P和RBVT-R根據路段中節點密集度和交通流等信息，選擇最優的路徑作為數據轉發路徑。在RBVT-P中，通過節點周期廣播獲取路段中節點信息；而RBVT-R則是在節點需要發送數據分組時，利用廣播分組搜集路段中節點信息。這些算法對路段信息進行了實時獲取，增加了網絡額外開銷問題。Yang Q等[24]提出ACAR，通過數據分組轉發過程中動態記錄街道集的信息，選擇最佳傳輸質量的路段作為路由路段。該算法中對路段信息獲取的準確和實時性依賴于場景中數據分組數量和傳輸方向。不適用于稀疏場景下。在文獻[36]提出CBRF和 CLGF，根據在路由發現的過程中統計街道密度選擇轉發路徑。由于路由發現過程中記錄的信息維持時間短，導致生成的路由表有效期短，進而增加路由發現開銷。

基于街道集路由算法，需要實時準確地獲取街道信息，否則單純的基于街道集去轉發數據，可能因為空洞現象使數據不可達。在拓撲結構易變的VANET環境中，對于街道情況難以實時掌握。因此準確實時地獲取街道信息是一個難題。

3.4 基于錨節點的路由算法

基于錨節點的路由算法是一種依靠路邊單元或具有簡單移動規律的節點進行數據存儲攜帶轉發的算法，該類節點在下文中被稱為錨節點。通過錨節點進行數據分組轉發能夠改善在稀疏場景中由于網絡分離導致的數據不可達的問題。

Saleet H等[37]提出IGRP協議，通過在路口設置網關，由網關利用RLSMP(基于區域的本地服務管理協議)對附近的車輛信息進行管理。在源節點不能和目的節點通信時，將數據交付于附近網關，由網關進行存儲轉發。Naumov V等在文獻[38]中提出CAR，利用貪婪算法和路口的錨節點進行數據分組的轉發。這些基于錨節點分布式路由算法，對錨節點依賴性強，在一個區域中若錨節點損壞或阻塞，將導致整個區域網絡癱瘓。文獻[27]中BBRP同樣通過在路口錨節點進行數據存儲轉發，該算法運用PBR協議機制，去預測候選節點，確保路徑穩固。文獻[12]中提出 ABCAR協議，應用于稀疏和密集網絡場景。在密集網絡中，假設網絡是全連接的，利用路口錨節點進行數據轉發；而在稀疏場景中，將通過公交等固定車輛路線，選擇合適的車輛作為錨節點，利用公交車存儲攜帶數據分組。這類算法還有文獻[24]中提到SKVR也是利用公交車的已知路線，對數據進行攜帶轉發。

張扶桑等在文獻[39]中提出一種公交車車自組織網絡的路由機制Vela，利用公交車的歷史移動軌跡挖掘公交車運行的時空規律。移動車輛利用公交車網絡進行數據傳輸，數據首先被交付于公交車，然后由公交車利用Dijkstra算法將數據交付于目的路段上的公交車，目的路段為目的車輛可能經過的路段，最后交付于目的車輛。該機制有效地利用了公交車移動規律性，對數據分組進行了存儲攜帶轉發，然而該算法只適用于靜態的源或目的車輛，因為在動態的VANET中，利用公交車存儲攜帶數據分組無疑增加了數據分組交付延遲。在數據分組轉發過程中，目的車輛可能已經離開目的路段，導致數據分組無法交付。

該類算法對錨節點依賴性大，易產生路由空洞和網絡阻塞，這種先選擇錨節點，再選擇下一跳的分布式路由算法，將增加路由跳數和時延。

4 典型算法設計

算法中的主要變量說明如表1所示。

表1 變量說明

綜上節所述，目前路由算法設計主要包括基于位置的貪婪路由算法、基于分簇路由算法、基于街道集路由算法、基于錨節點路由算法。

本文將針對于這些基本特點，提出分別代表這4種策略的路由算法。通過對這4種算法實驗仿真結果進行研究分析，提出目前基于這4類算法的路由協議研究趨勢。

4.1 基于位置的貪婪路由算法設計

該算法的路由發現過程與AODV的相同，在請求分組和回復分組中添加節點位置信息。

數據在轉發過程中，將目的節點的 ID與位置信息添加在數據分組頭，中繼節點在收到數據分組之后，根據分組頭中目標節點位置，利用貪婪算法尋找下一跳。由于目的節點位置是在不斷變換，且路由表的有效期會保持一段時間，因此會導致一段時刻過后，目的節點已經不在路由表所指示的目的位置，而下一跳的選擇中還需要預測目的節點是否已在目的范圍內。

默認路由表的有效時間rt_expire=now_time+，在下節的實驗中α取0.5。通過式(1)預測當前自己位置與路由表中指示的目的位置最大距離d，若d

4.2 基于分簇的路由算法設計

1) 簇劃分

根據攜帶的城市電子地圖，沿著街道每間隔wm劃分為一個簇。街道不足wm的，以實際街道長度為簇大小。在對整個場景劃分完成后，所有簇大小都是小于wm，鄰居簇之間的所有節點間距離小于R，因此鄰居簇之間可以直接通信。

2) 簇首選擇與維護

初始化過程中，所有節點發送一個hello分組，分組中攜帶預測自己在該簇中的時間tc（如式(2)所示）；然后所有節點根據在簇中時間最久的原則，選舉出簇首。初始化結束，簇首會周期發送 leader分組，通告簇成員和鄰居簇成員，該簇首仍然有效。并且簇成員周期發送hello分組，周期hello_intval如式(3)所示。發送 leader和 hello分組的周期send_intval式(4)所示。

其中，d為節點距離簇邊界距離，在下節中MIN_TIME為7.5 s，MAX_TIME為15 s。

若簇首在周期刷新自己位置時發現自己離開了原簇，則在簇成員中選舉出在該簇中有效期最久的節點作為下一任簇首，并將自己的路由表轉發到該節點，然后單跳廣播 leave分組，宣告自己不再是簇首，和下一任簇首信息。

3) 路由發現與數據轉發

當有節點需要發送數據分組時，首先將數據交付簇首，如果自己是簇首，則查找路由表，若沒有路由，則啟動路由發現過程。在中繼節點接收到RREQ分組，只有簇首處理該分組，處理過程與AODV相似，若簇首中含有目的節點信息，則直接回復RREP分組。

回復RREP與轉發數據分組過程相同，基于貪婪算法，優先選擇簇首，如果沒有合適的簇首，則選擇合適的鄰居節點，直到數據分組或RREP交付于目的節點。

4) 路由表維護

由于鄰居簇之間可以直接通信，因此當數據分組被交付于目的簇中，即使目的節點已經離開了原簇，但還在鄰居簇中，也可以通過一跳到達。因此路由表的時間rt_expire為目的節點在原簇中的時間t1加上在鄰居簇中的時間t2，如式(5)所示。路由表失效之后，將重新啟動路由發現過程。

其中，d表示當前節點距離簇邊界距離。

4.3 基于街道集的路由算法設計

1) 路由發現

同樣，路由發現過程與AODV相似。不同的是在請求分組中攜帶了源節點所在路段信息，以及預測源節點在該路段上的有效時間，預測機制見4)。在目的節點接收到請求分組之后，將目的節點信息存儲到路由表中，然后生成RREP回復分組，利用3)對RREP分組進行轉發。

2) 鄰居預測

將雨課堂用于《模擬電子技術》課程教學中，經過一年教學實踐，在課堂中運用任務驅動法和翻轉課堂的教學模式，減少了教師講授時間，增加了學生討論、交流、自主學習時間，學生在討論時注意力不夠集中，有時會出現討論的話題偏離課程主題情況。

由于鄰居節點的位置在不斷變化，因此通過周期hello分組，交換鄰居信息，并通過式(6)對鄰居位置進行預測，以降低下一跳鏈路斷裂和路由環路的概率。

若D>R，則認為該鄰居失效，離開了通信范圍，將該鄰居移出鄰居表。

3) 數據分組轉發

首先根據路由表中目的節點路段信息，利用Dijkstra算法生成最短路徑。該路徑是由最短街道集組成，然后分布式選擇每條路段上鄰居節點作為下一跳，下一跳選擇根據貪婪算法，從鄰居列表中選擇距離下一段街道最近的鄰居節點作為下一跳。

4) 路由表維護

路由表生命期rt_expire是通過預測目的節點在目的路段時間。

其中，d表示節點到達路口的距離。

通過周期刷新路由表，若路由表有效時間過期，則將該路由表設置為無效，在下次需要發送數據分組時，重新啟動路由發現過程。

4.4 基于錨節點路由算法設計

假設在道路場景中，每個路口都存在一個錨節點。

1) 路由發現

路由發現過程同樣是基于泛洪方式進行，在請求分組和回復分組中，添加該節點的位置信息，以及在4)中提到的路由表生命期信息。

2) 鄰居表維護

鄰居表中信息通過周期廣播單跳 hello分組獲得，分組中攜帶該節點位置信息以及節點標識（錨節點/車輛節點），鄰居表有效期nb_expire預測為

其中，n表示鄰居和自己屬于錨節點的個數；d為當前與鄰居的歐式幾何距離。

通過周期刷新鄰居表，如果nb_expire大于當前時間，則將該鄰居移出鄰居表。

3) 數據轉發

數據轉發分為2個步驟：①根據目的節點位置信息，選擇距離目的位置最近的錨節點作為目的區域；②在鄰居表中優先尋找距離目的區域最近的錨節點作為下一跳轉發節點。若沒有該錨節點，則利用貪婪算法選擇其他鄰居節點作為下一跳，直到數據分組被交付于目的區域的錨節點，再由該錨節點交付于目的節點。

4) 路由表維護

由于數據傳輸是經過錨節點到達，則路由表有效時間為目的節點在錨節點通信范圍內的時間。利用節點移動的有規律性，節點的移動一定是在2個錨節點之間。通過預測該節點在該路段上的時間t1與離開路段并還在錨節點通信范圍內的時間t2之和作為路由表的有效時間rt_expire。

其中，d為節點即將到達下一錨節點的距離。

5 典型算法性能分析比較

實驗場景是模擬南昌市紅谷灘新區部分地圖。模型如圖2所示，其余參數設置如表2所示。

圖2 仿真場景模型

在cbr數據分組大小為512 byte，發分組頻率為5 packet/s的場景下，對隨著節點數量的增加，分組的交付率、延時、跳數、路由開銷進行性能評估分析如下。

5.1 數據交付率

所有算法都沒有進行存儲攜帶，因此在初始階段是沒有路由表信息，導致開始過程會有數據分組丟失。如圖3所示，所有算法的交付率都不能達到100%。節點數量在300～700時，這4個路由算法交付率達到相對穩定。在節點數量較低時，由于網絡分離，導致大量數據分組不能被交付，因此數據分組交付率下降，其中基于街道集的路由協議 SBRP影響最大。因為SBRP算法對街道鏈路質量預測十分重要，若沒有選擇合適的街道進行數據轉發，容易導致路由空洞現象，在稀疏場景中這種現象將更加明顯，但隨著節點數量的增加，可以看出 SBRP的交付率會越來越高。因為在密度大的情況下，網絡趨向于全連通狀態，因此，此時對數據分組交付率影響主要因素是單跳鏈路質量。SBRP通過街道進行數據傳輸，鏈路質量相對穩定，而其他3個路由協議，隨著節點數量超過700時，交付率都開始出現下降趨勢。這是由于節點數量的增加，信號的干擾嚴重，導致鏈路中斷現象嚴重，因此數據分組不能正確交付。隨著節點數量的增加，CBRP的簇維護開銷急劇增加，網絡阻塞嚴重，簇首負載也相應增加，嚴重影響數據分組交付，可以看出CBRP的交付率下降最快。而LGBRP利用貪婪算法選擇最遠的距離傳輸，在節點數量增加的情況下，距離越遠，信號干擾衰減的越嚴重，鏈路質量越差，因此數據交付也有明顯的下降。基于錨節點的路由ABRP，相對于其他算法交付率較高。由于通過錨節點進行數據傳輸減少了路由空洞的現象，并且錨節點相對靜止，鏈路質量穩定，所以分組丟失率會較低。

綜上所述，基于位置的貪婪路由算法，在交付率上主要影響因子是鏈路質量，利用最遠距離的節點傳輸數據分組，在密集場景下，反而增大了鏈路中斷的風險，因此在基于位置的基礎上，優化鏈路質量，是該類算法的發展趨勢。而基于簇的路由協議，在節點密集度增加的情況下，交付率同樣下降明顯，由于節點數目的增加，簇首負載增加，有效地控制簇維護開銷，降低網路負載，對數據分組的交付率將有很大改善。基于街道集的路由算法，對街道中節點信息要求苛刻，實時準確地獲得街道中節點信息，將對數據交付起到至關重要的作用，基于錨節點的路由算法主要弊端就是RSU(路邊單元)開銷大。

表2 仿真環境參數設計

圖3 數據交付率

5.2 數據交付延時與平均跳數

在非存儲攜帶的路由算法中，數據分組的延時主要取決于數據分組傳輸過程中的跳數以及單跳的時間。從圖4和圖5中可以看出，時延與平均跳數基本保持一致。

在圖5中，可以看出基于簇的路由協議CBRP延時最大。由于CBRP在數據轉發過程中首先選擇簇首，增加了數據傳輸的跳數；其次是基于街道集的路由協議 SBRP要求數據分組沿著街道進行傳輸，雖然提升了鏈路質量，但是每一條的距離變得更小，增加了跳數，導致時延增加。基于貪婪算法的LGBRP和ABRP的時延會相對較小，由于貪婪算法總是尋找歐式距離最短路徑進行數據轉發，因此跳數最少，時延最小。ABRP基于錨節點進行數據轉發，由于錨節點的輔助轉發，增加了更多合適的下一跳，減少了跳數和時延，并且降低了路由環路和空洞的風險，使跳數和時延比LGBRP更低。

由于CBRP和SBRP是優先選擇簇首和距離下一街道上更近的節點，若無這類節點，則會根據貪婪算法選擇其他更遠的鄰居節點。隨著節點數量的增加，鄰居表中可供選擇的簇首和合適的下一跳增多，利用貪婪算法的概率將降低，因此在節點數量增加的情況下，改善了鏈路質量，但增加了跳數和時延。

圖4 端到端平均跳數

圖5 端到端延時

綜上所述，基于簇和街道集的路由算法，跳數相對較大，從而導致延遲也增加，但這也增加了鏈路質量的穩定性，而基于位置的貪婪算法在犧牲鏈路質量的情況下降低了延遲。這些問題表明通過預測鄰居節點的位置或移動趨勢，來選擇合適下一跳，將是這些算法的研究方向之一。

5.3 路由發現開銷

從圖6整個趨勢來看，隨著節點密度不斷增加，參與路由發現的節點數量會不斷增加，因此路由開銷也會不斷增加。

CBRP是基于簇首進行路由發現，減少了參與路由發現過程中的節點數量，因此降低了網絡中路由發現分組最多，路由開銷最小。由于SBRP是基于街道進行路由轉發，節點在街道上的有效時間較短，導致路由表有效期較短，需要頻繁地更新路由表，執行路由發現過程，增加路由開銷。ABRP中，路由表有效時間不僅僅是節點在路段上時間，還添加了離開街道但仍在錨節點的通信范圍內的時間，因此路由表有效期相對更長，路由更新頻率相對下降，相比 SBRP協議降低了路由開銷。同理在LGBRP中，假設節點最大移動速度在20 m/s的情況下，要離開初始位置1 km，至少需要50 s，因此路由表的有效期能維持50 s。但是在同樣網絡場景下，LGBRP的節點數量比ABRP要少，因為ABRP中存在額外的錨節點，增加了網絡開銷，因此LGBRP的路由開銷比ABRP的要小。

圖6 路由開銷

綜上所述，基于簇的路由算法有效降低了路由發現冗余分組。為降低網絡負載，其他3類路由算法如何有效地降低廣播分組的冗余將是研究趨勢。同時，增加路由表的有效期，將減少路由發現過程，預測目的節點的移動規律將是VANET路由研究的重要方向之一。

5.4 中斷率和交付率

在CBR分組大小為512 byte，300個節點場景中，隨著發分組速率的增加，對AODV、LGBRP、ABRP的中斷率和交付率分析如下。

由圖7可以看出，傳統AODV路由協議在隨著發分組率增加，中斷率明顯上升，且由圖8看出交付率急劇下降，這是由于在AODV中，并沒有對下一跳的選擇進行優化和預測。在節點移動頻繁的VANET環境中，鏈路中斷現象更加劇烈，而在LGBRP和ABRP協議中都對鄰居進行了預測和管理，優化了下一跳的選擇。因此在稀疏的場景中，中斷率很低。但是實驗表明，在密集場景下，由于LGBRP和ABRP為管理鄰居表而增加網絡開銷，也可能導致中斷現象發生。在圖 6中可以看出LGBRP和ABRP隨著發分組率的不斷上升，交付率是先上升后下降。這是由于隨著網絡中數據分組的增加，網絡吞吐量逐漸達到飽和狀態，而導致數據分組丟失。在發送分組率低于 50 packet/s時，AODV的路由協議是比LGBRP優越，因為在300個節點的稀疏場景中，基于位置的貪婪算法易發生路由空洞現象，導致數據分組不可達，降低了數據分組交付率，而ABRP一直是很優越。

圖7 鏈路中斷次數

圖8 數據交付率

6 結束語

基于位置的貪婪算法是降低時延的一種有效算法，但是在節點分布不均勻的車聯網中，很容易發生路由空洞和環路，且節點移動速度快，場景復雜，增大了鏈路的不穩定性，因此對鏈路質量的評估將是該類算法研究趨勢。基于街道集的路由算法，在密集場景下，對下一跳的選擇鏈路質量交為穩定。但是同樣由于節點分布的不均勻以及拓撲變換頻繁，及時準確地獲取街道集信息是一難點。如何實時有效地獲取路段信息將是今后該類算法研究的主要方向。基于簇的路由發現算法，在廣播過程中有效地降低了冗余分組的開銷，但是對簇的組建與維護開銷仍然是一個瓶頸。基于錨節點的路由算法在路由性能上是最為有效，但對輔助設備要求高，依賴性大。每綜合各種路由協議的優點，設計切實可行的高QoS的路由協議，將是后期研究的主要內容。

綜上所述，VANET比MANET的拓撲結構更不穩定，節點移動速度更快，實際場景更加復雜等特點，在今后在車聯網路由方面研究的主要方向側重于以下4個方面。

1) 鏈路質量預測研究。使在高速和復雜的移動場景中，數據分組丟失和鏈路中斷的可能性更小。

2) VANET的拓撲結構變化研究。由于節點的移動是沿街道行駛，具有規律可循，通過節點的移動規律，預測拓撲結構的變化，降低在路由維護和發現過程中，所需的額外開銷。

3) 分簇算法研究。通過分簇算法的研究，能夠有效降低簇維護和廣播開銷。

4) 輔助設備和基礎設施的建設部署研究。大多車內都裝有各種傳感器、GPS定位等輔助設備，充分利用輔助設備和路邊單元在數據交付延遲和交付率等網絡性能上有很大幫助。

目前車聯網路由算法大多數都是基于傳統的路由算法改進而來，在確保數據交付率和延遲的情況下，如何有效利用車節點輔助設備，對網絡拓撲結構實時把握，使路由表和鄰居表信息有效時間更久，網絡額外開銷更小，將是今后VANET路由發展的趨勢。

[1] HE W, LI Z, XIE G. Research and development trends of car networking[J]. Communications in Computer & Information Science, 2010,(134): 296-301.

[2] WANG Q, QIAN H Y. VANET architecture and key techniques of perception layer research [J]. Telecom Science, 2012, 28(12):1-9.

[3] BIDDLESTONE S, REDMILL K A. A GNU Radio based testbed implementation with IEEE 1609 WAVE functionality[A]. Vehicular Networking Conference(VNC)[C]. 2009.1-7.

[4] GRAFLING S, MAHONEN P, RIIHIJARVI J. Performance evaluation of IEEE 1609 WAVE and IEEE 802.11p for vehicular communications[A]. Ubiquitous and Future Networks (ICUFN), 2010 Second International Conference on. IEEE[C]. 2010.344-348.

[5] HO K, KANG P, HSU C. Implementation of WAVE/DSRC devices for vehicular communications[J]. International Symposium on Computer,2010, (2):522-525.

[6] SUKUVAARA T, YLITALO R, KATZ M. IEEE 802.11p based vehicular networking operational pilot field measurement[J]. IEEE Journal on Selected Areas in Communications, 2013 (9):409-417.

[7] 劉業, 吳國新. 基于 802.11p/WAVE的車聯網連通性模型及其應用研究[J]. 通信學報, 2013, 34(6):85-91.LIU Y, WU G X. Study on the connectivity model of VANET based on 802.11p/WAVE and its application [J]. Journal on Communications,2013, (6):85-91.

[8] 范存群,王尚廣,谷文哲. 車聯網下基于網絡編碼的高吞吐量多徑路由算法[J]. 通信學報,2013,34(Z1):133-141.FAN C Q,WANG S G,GU W Z. Enhanced-throughput multipath routing algorithm based on network coding in IoVs [J]. Journal on Communications,2013(S1):133-141.

[9] KORI P, SHARMA S. An effect of route caching scheme in dsr for vehicular adhoc networks[J]. International Journal on Computer Science & Engineering, 2012,(1):35-39.

[10] WU C, KUMEKAWA K, KATO T. Distributed reinforcement learning approach for vehicular ad hoc networks[J]. IEICE Transactions on Communications, 2010,93-B(6) :1431-1442.

[11] MOSTAFA A, VEGNI A M, AGRAWAL D P. A probabilistic routing by using multi-hop retransmission forecast with packet collision -aware constraints in vehicular networks[J]. Ad Hoc Networks,2014,14(3):118-129.

[12] GHAFOOR H, KOO I, GOHAR N. Neighboring and connectivity-aware routing in VANETs[J]. The Scientific World Journal,2014.789247.

[13] SHAFIEE K, LEUNG V C M. Connectivity- aware minimum-delay geographic routing with vehicle tracking in VANETs[J]. Lecture Notes of the Institute for Computer Sciences Social Informatics & Telecommunications Engineering, 2010, 9(2): 131-141.

[14] DING Y, WANG C, XIAO L. A static-node assisted adaptive routing protocol in vehicular networks[A]. Proceedings of the fourth ACM international workshop on Vehicular ad hoc networks[C]. ACM, 2007.59-68.

[15] SKORDYLIS A, TRIGONI N. Delay-bounded routing in vehicular ad-hoc networks[J]. Mobihoc Proceedings of Acm International Symposium on Mobile Ad Hoc Networking & Compu, 2008, 5346:341-350.

[16] RAO S A, PAI M, BOUSSEDJRA M. GPSR-L: Greedy perimeter stateless routing with lifetime for VANETS[A]. International Conference on Its Telecommunications[C]. 2008. 299-304.

[17] WU E H, SAHU P K, SAHOO J. Destination discovery oriented position based routing in VANET[A]. Asia-pacific Conference on Services Computing IEEE[C]. 2008.1606-1610.

[18] LEE K C, LE M, HARRI J. Louvre: landmark overlays for urban vehicular routing environments[A]. Vehicular Technology Conference[C]. 2008. 1-5.

[19] BILAL M, CHAN P M L, PILLAI P. A fastest multi-hop routing scheme for information dissemination in vehicular communication systems[A]. Softcom International Conference on Software Telecommunications and Computer Networks[C]. IEEE, 2010. 35-41.

[20] BOHLOOLI A, JAMSHIDI K. Detecting the vehicle direction changes for routing algorithms and applications of vehicular ad hoc networks[J].IEE Transactions on Electrical and Electronic Engineering, 2012,7(3):329-333.

[21] ZHANG J Y, YANG B. A routing algorithm for car-to-car communication in wireless access vehicular environment[J]. Communications Technology, 2013, (9).

[22] LUO T, LI J T, LIU R L. A fast and reliable broadcast routing algorithm for safety related information in VANET[J]. Chinese Journal of Computers, 2015, 38(3): 663-672.

[23] LIU G T, YANG Y J, LIU Z Y. A route recovery method based on location information in vehicular ad hoc networks[J]. Jourmal of Electronic Measurement and Instrument, 2012, 26(8):716-720.

[24] YANG Q, LIM A, LI S. ACAR: Adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios[J]. Mobile Networks and Applications, 2010, 15(1):10.

[25] RASHEED A, AJMAL S, QAYYUM A. Protocol independent adaptive route update for VANET[J]. Scientific World Journal, 2014(1):18-18.

[26] NZOUONTA J, RAJGURE N, WANG G. VANET routing on city roads using real-time vehicular traffic information[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7):3609-3626.

[27] KIM J, LEE S. Reliable routing protocol for vehicular ad hoc networks[J]. AEU International Journal of Electronics and Communications, 2011, 65(3):268-271.

[28] HU S Z, BAO W D, WANG B. Clusering data gathering algorithm based on multiple cluster heads for wireless sensor networks [J]. Journal of Electronics & Information Technology, 2014,(2):403-408.

[29] HASSANABADI B, SHEA C, ZHANG L. Clustering in vehicular ad hoc networks using affinity propagation[J]. Ad Hoc Networks, 2014,13(1):535–548.

[30] TALEB T, SAKHAEE E, JAMALIPOUR A,et al. A stable routing protocol to support its services in VANET networks[J]. IEEE Transactions on Vehicular Technology, 2007, 56(6):3337 - 3347.

[31] SONG T, XIA W, SONG T. A cluster-based directional routing protocol in VANET[A]. IEEE International Conference on Communication Technology[C]. 2010. 1172- 1175.

[32] SUN W, YAMAGUCHI H, YUKIMASA K. GVGrid: a QoS routing protocol for vehicular ad hoc networks[A]. Quality of Service, 2006.IWQoS 2006 14th IEEE International Workshop on IEEE[C]. 2006.130 -139.

[33] MOHANMODE M S, XU K K, XIA W W. Vehicular ad hoc network and clusering routing algorithm applied in wilderness scenarios[J].Journal on Communications, 2012, (10):166-174.

[34] LIU Y, XIONG N, ZHAO Y. Multi-layer clustering routing algorithm for wireless vehicular sensor networks[J]. IET Communications, 2010,4(7):810 - 816.

[35] ZHAO J. CAO G, VADD: Vehicle-assisted data delivery in vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2008,57(3):1910 - 1922.

[36] WANG W, XIE F, CHATTERJEE M. Small-scale and large-scale routing in vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(9): 5200-5213.

[37] SALEET H, LANGAR R, NAIK K. Intersection-based geographical routing protocol for VANETs: a proposal and analysis[J]. IEEE Transactions on Vehicular Technology, 2011, 60(9):4560 - 4574.

[38] NAUMOV V, GROSS T R. Connectivity- aware routing (car) in vehicular ad-hoc networks[A]. Infocom IEEE International Conference on Computer Communications IEEE[C]. 2007.1919 - 1927.

[39] ZHANG F S, JING B H, WANG Z Y. A routing mechanism over bus-based VANETs by mining trajectories[J]. Chinese Journal of Computers, 2015, 38(3): 648-662.