基于按需距離矢量修正的車聯網穩定路由

鄧少聞 羅代升

摘 要： 車輛的高速移動以及城市場景中的障礙物使得車輛間的通信路徑變得異常脆弱。為此，提出基于路徑判據的按需距離矢量（AODV）的路由算法（PA?AODV），進而增強路徑的穩定性。PA?AODV路由首先計算路徑質量因子、移動方向因子，然后再計算路徑判據權值，最后擇優選擇權重小路徑傳輸數據。仿真結果表明，提出的PA?AODV路由提高了數據包傳遞率，并降低了端到端傳輸時延。

關鍵詞： 車聯網； 按需距離矢量； 鏈路質量； 移動方向； 路徑判據； 降低傳輸時延

中圖分類號： TN915?34； TPT393 文獻標識碼： A 文章編號： 1004?373X（2018）19?0031?05

Abstract： The high?speed mobility of vehicles and obstacles existing in urban area make the communication path between vehicles unreliable. Therefore， the path weight based Ad Hoc on?demand distance vector （PA?AODV） routing algorithm is proposed to enhance the path stability. In PA?AODV routing， the path quality factor and moving direction factor are computed， then the weight of path criterion is calculated， and the transmission data with light path weight is selected optimally. The simulation results show that the PA?AODV routing can improve the packet transfer ratio， and shorten the end?to?end transmission delay.

Keywords： VANET； on?demand distance vector； link quality； moving direction； path weight； transmission delay reduction

0 引 言

車聯網（Vehicle Ad Hoc Networks，VANETs）有望成為智能交通系統的實現技術[1]，已受到廣泛關注。VANETs為車輛間的信息交互提供了平臺，進而提高了車輛行駛安全。然而，與移動自組織網絡不同，VANETs具有鮮明特性，如車輛的快速移動、拓撲動態變化、車輛分布不均勻等。這些特性給VANETs的路由技術提出了挑戰[2]。

典型的路由協議有地理信息路由、表格驅動型路由、按需式路由。其中，地理信息路由常引用貪婪轉發策略，選擇離目的節點近的節點作為下一跳轉發節點。它無需全局網絡拓撲信息，只需依據節點的位置信息決策路由，易實現。但地理信息路由常存在路由空洞問題。為此，文獻[3]提出了地理信息路由的改進協議GPCR。一旦節點遭遇路由空洞，就不再采用貪婪轉發，而是引用邊界轉發策略。節點引用右手規則，搜索轉發節點。此外，文獻[4]也提出基于地理路由的改進協議：基于感知空洞形狀的分段貪婪路由（Easy Modeling Greedy Routing，EMGR）。EMGR協議先利用探測包收集邊界信息，然后再依據空洞形狀決策路由。而典型表格驅動型路由有OLSR[5]，DSDV[6]。與表格驅動型路由相比，按需路由協議（如AODV[7]，ABR[8]）。只有需要傳輸數據時，才進行路由發現。因此按需路由受到廣泛關注。然而傳統的AODV協議也存在不足。

文獻[9]提出了基于鏈路生存時間的改進路由協議（Enhanced Routing Protocol on Ad Hoc On?demand Distance Vector with Speed Variance，SV_AODV）。SV_AODV路由協議計算每條鏈路的速度方差，再選擇速度方差最小的路徑傳輸數據，提高了鏈路的穩定性。此外，文獻[10]也提出了AODV路由的改進協議AODV_D。AODV_D協議考慮了MAC層的節點競爭信息和接口隊列時延，降低了傳輸時延。而文獻[11]也提出AODV的優化協議。先基于單播和廣播結合策略，實現路由探測，并通過降低廣播幀數量，增強路由穩定性。

本文針對車載自組織網絡VANETs的城市場景，并結合AODV協議，提出基于路徑判據的AODV的路由協議PA?AODV（Path?weight?AODV）。PA?AODV協議引用跨層設計，利用物理層和MAC層獲取鏈路質量信息，并修改AODV協議的路由發現機制。具體而言，先計算鏈路質量，進而估計路徑判據權重，最終選擇權重最小的路徑傳輸數據包。仿真結果表明，提出的PA?AODV協議能夠有效提高數據包傳遞率，并降低端到端傳輸時延。

1 相關工作

按需距離矢量（Ad Hoc On?demand Distance Vector，AODV）路由屬于反應式路由。AODV允許在多個移動節點間實現動態、自發式多跳通信連通。當需要建立一條路由傳輸數據包時，節點（源節點）就向下一跳鄰居節點廣播請求數據包（Route Request，RREQ），觸發路由發現過程。一旦接收了RREQ包，節點就轉發RREQ包，直到RREQ包被傳遞至目的節點。

一旦目的節點接收了RREQ包，它就沿著此路徑向源節點回復（Route Replay，RREP），并且忽略隨后所接收的RREQ包。換而言之，目的節點選擇第一條到達的路徑作為數據傳輸路徑。AODV的路由發現過程如圖1所示。圖1a）中，源節點1廣播RREQ控制包，其鄰居節點通過廣播將RREQ傳輸到目的節點8。

2 PA?AODV協議

PA?AODV協議利用節點的方向以鏈路質量選擇路徑。先通過物理層和MAC層傳遞鏈路信息以及節點信息，再估計路徑質量、移動方向因子，最終計算路徑判據權值。

2.1 路徑質量因子

一條路徑可能有多邊鏈路構成。路徑的質量取決于鏈路質量，若某條鏈路斷裂，則該條路徑也將斷裂，無法完成數據的傳輸。因此，對于每條路徑而言，其低質量的鏈路數越多，該條路徑質量越差。

為此，先引用文獻[11]中指標（Link Quality Indicator，LQI）表征鏈路質量，然后再依據數據包傳遞率（Packet Delivery Ratio，PDR）[12]設置鏈路質量門限值[LQIth]。當某條鏈路質量LQI低于[LQIth]，則說明此鏈路質量較差。最后統計每條路徑中的低質量鏈路數[QL]。

接下來，設定鏈路質量門限值[LQIth]。為了更好地設置[LQIth]，利用實驗測量LQI和PDR。當鏈路的PDR大于80%，則認為該條鏈路是穩定的，并取其對應的LQI作為門限值。通過實際的室內場景，利用芯片CC2420作為節點，獲取LQI和PDR的數據關系，如圖2所示。在LQI=220時，LQI開始達到80%。因此，[LQIth=][80%]。

2.2 移動方向因子

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

車輛移動方向對車輛間的通信連通時間有直接影響。為此，在選擇路徑時，也需考慮組建路徑的節點的移動方向。為了表述簡單，將構成路徑的節點（除源節點和目的節點外）稱為中間節點。若鏈路的中間節點的移動方向與源節點和目的節點的連線方向的夾角一致（所謂的移動方向一致是指它們的夾解小于門限值），則它們的鏈路穩定性得到提高，相應地增加路徑的持續時間。

如圖3所示，設定節點[i]在[t1]時刻的位置為[（x1，y1）]，在[t2]時刻它移動到了位置[（x2，y2）]。擁有數據包的節點[C]的位置是[（xc，yc）]，目標節點[D]的位置為[（xd，yd）]。在這種情況下，鄰居節點[i]的移動速度，數據包轉發方向與節點移動方向之間的切角由式（4）和（5）計算得到：

2.3 路由判據權值

在傳統的AODV路由協議中，目的節點只選擇第一時間到達的RREQ包所傳輸的路徑。顯然，首次到達的RREQ的傳輸路徑未必是最穩定的。為此，PA?AODV協議考慮多條路徑，并計算每條路徑的路徑判據權值，再選擇權值最小的路徑傳輸數據包。

具體而言，路徑[P]的判據權值融合了路由質量因子和移動方向因子，如式（8）所示：

2.4 數據包傳輸流程

一旦節點需要傳輸數據包，它就向鄰居節點傳輸RREQ包。由于PA?AODV協議需要計算路徑判據，在傳統的RREQ包中添加了鏈路質量和方向變量。RREQ包的格式如圖4所示。

每個接收節點將自己的鏈路質量和方向變量加入RREQ包再傳輸。當目的節點接收后，計算每條路徑判據權重，并選擇路徑權重最小的路徑回復RREP。

RREQ和RREP的傳輸流程如圖5所示。一旦接收到RREQ包，節點首先判斷之前是否已接收過同樣ID的數據包，若是，則丟棄。再判斷自己是否為目的節點，若是，則計算路徑判據權重，并選擇權重最小的路徑回復RREP。否則，就將自己的鏈路質量和方向變量信息加入RREQ，并轉發。

3 實驗分析

3.1 仿真模型

利用OMNET++，SUMO建立仿真平臺。OMNET++[13]是一款基于離散事件仿真器的開放源代碼，可用于模擬通信網絡和分布式系統。而SUMO[14]可用于模擬大型的交通網絡以及車輛移動模型。因此，OMNET++用于網絡仿真，而SUMO用于道路交通仿真，并利用Manhattan計量法產生網格狀的城市道路，選取[3×2]道路網格以及十字路口模型，如圖6所示。

選擇3 968 m×1 251 m的矩形區域道路區域，其中道路有370條、十字路口124個。同時利用STRAW（Street Random Way）產生車輛移動數據。

仿真區域內車輛數從100～350變化，車輛運行速度從40～70 km/h變化，車輛通信范圍為300 m。數據包產生率為6 packet/s，數據包大小為512 B，信道帶寬為2 Mb/s，仿真時間為350 s。每次實驗獨立重復100次，取平均值作為實驗數據。

此外，為了更好地分析PA?AODV協議性能，選擇AODV，GPCR路由協議進行同步仿真，并與PA?AODV協議進行比較。同時，選擇數據包傳遞率、平均路由跳數以及端到端傳輸時延作為路由性能指標。

3.2 仿真結果及分析

1） 數據包傳遞率

本次實驗主要考查車輛數對數據包傳遞率的影響。車輛數從100～350變化，且步長為50，車速為50 km/h。三個協議的數據包傳遞率隨車輛數的變化曲線如圖7所示。

依據圖7的數據可知，PA?AODV協議的數據包傳遞率較高，優于GPCR和AODV協議。隨著車輛數的增加，優勢越發明顯。而GPCR路由的數據包傳遞率最低，尤其是在低密度區域。當車輛數小于200時，數據包傳遞率不到55%。原因在于GPCR協議在選擇轉發數據包時，只依據節點的距離選擇轉發節點，并沒有考慮到鏈路質量信息，導致路徑不穩定，降低了數據包傳遞率。而相比于GPCR協議，AODV協議的數據包傳遞率較高，但它仍低于PA?AODV協議。這主要是因為：PA?AODV協議在選擇傳輸路徑時，充分考慮了每條鏈路的質量，增加了路徑的穩定性，最終提高了數據包傳遞率。

2） 平均端到端傳輸時延

三個協議的平均端到端傳輸時延隨節點數的變化曲線如圖8所示。PA?AODV協議的平均端到端傳輸時延最低，且較平穩，并沒有隨節點數變化而波動。而AODV協議的平均端到端傳輸時延較高，高于GPCR協議。這主要是因為AODV協議在進行路由發現階段采取了RREQ和RREP控制包，增加了一定的時延。而GPCR協議的端到端傳輸時延略低于AODV，這主要歸結于GPCR協議總是選擇離目的節點近的節點作為轉發節點，降低了傳輸跳數，進而減少了一定的傳輸時延。

3） 平均傳輸跳數

三個協議的平均傳輸跳數隨節點數的變化曲線如圖9所示。

從圖9可知，GPCR協議的平均傳輸跳數最低，這也符合GPCR路由選擇策略。而PA?AODV協議的平均傳輸跳數略高于AODV協議。原因在于：AODV協議只考慮第一時間的到達傳輸路徑傳輸數據，既然是第一時間到達的路徑，相應地它的跳數較少。而提出的PA?AODV協議并沒有從到達路徑的順序選擇路由，而是從路徑質量方面考慮，因此增加了平均傳輸路數。

4 結 語

本文針對VANETs的路由問題，提出基于路徑判據的按需距離矢量PA?AODV路由算法。PA?AODV路由算法充分利用AODV路由的特性，并對其路由決策進行了改進。通過計算路徑判據權重，并擇優選擇權重小的路徑傳輸數據，進而提高路徑穩定性。實驗數據表明，提出的PA?AODV路由減少了數據包丟失率，也縮短了端到端的傳輸時延。

參考文獻

[1] MISRA S， KRISHNA P V， SARITHA V. LACAV： an energy?efficient channel assignment mechanism for vehicular Ad Hoc networks [J]. Journal of supercomputing， 2012， 62（3）： 1241?1262.

[2] GHAFOOR K， BAKAR K. A novel delay and reliability aware inter vehicle routing protocol [J]. Network protocols and algorithms， 2014， 2（2）， 66?88.

[3] LOCHERT C， MAUVE M， HARTENSTEIN H. Geographic routing in city scenarios [J]. Mobile computing and communications review， 2015， 9（1）： 69?72.

[4] 范敏，謝思佳，石為人，等.基于空洞模型的地理位置路由改進算法研究[J].傳感技術學報，2012，25（11）：1556?1561.

FAN Min， XIE Sijia， SHI Weiren， et al. Research on improved algorithm of geographical route based on cavity model [J]. Journal of transduction technology， 2012， 25（11）： 1556?1561.

[5] EI W， BEN G， SAFA H. MOLSR： mobile?agent based optimized link state routing protocol [C]// Proceedings of 2015 International Wireless Communications and Mobile Computing Conference. Dubrovnik， Croatia： IEEE， 2015： 355?360.

[6] PERKINS C E， BHAGWAT P. Highly dynamic （DSDV） for mobile computers routing [C]// Proceedings of 1994 ACM Conference on Communications Architectures， Protocols and Applications. London： ACM， 2014： 234?244.

[7] LEE S J， BELDING E M， PERKINS C E. Ad Hoc on demand distance?vector routing scalability [J]. ACM sigmobile mobile computing and communications review， 2012， 6（3）： 94?104.

[8] TOH C K. Associativity?based routing for Ad Hoc mobile networks [J]. Wireless personal communications， 1997， 4（2）： 103?139.

[9] 曹文君，薛善良.一種適用于城市車聯網的改進的AODV協議[J].計算機與現代化，2016，23（7）：98?103.

CAO Wenjun， XUE Shanliang. An improved AODV protocol for urban vehicle network [J]. Computer and modernization， 2016， 23（7）： 98?103.

[10] 劉大勇，趙春江.基于AODV的農田無線傳感器網絡路由和休眠算法[J].微電子學與計算機，2015，32（10）：115?120.

LIU Dayong， ZHAO Chunjiang. A route and sleep algorithm for farmland wireless sensor networks based on AODV [J]. Microelectronics & computer， 2015， 32（10）： 115?120.

[11] 蔡菁，朱余兵.一種基于AODV改進的城市車載自組網絡路由協議研究[J].計算機工程與科學，2013，35（1）：61?66.

CAI Jing， ZHU Yubing. Research on a routing protocol based on AODV improvement for urban vehicle?borne network [J]. Computer engineering and science， 2013， 35（1）： 61?66.

[12] MAMMU A S， HERNANDEX J U， SAINZ N. Cross?layer cluster?based energy?efficient protocol for wireless sensor networks [J]. Sensors， 2015， 15（4）： 8314?8336.

[13] IEEE Computer Society. Wireless medium access control and physical layer specifications for low?rate wireless personal area networks [S]. New York： IEEE， 2010.

[14] SAMUNDISWAY P， BHARDWAJ H. Performance analysis of energy aware AODV routing protocol for IEEE 802.15.4 enabled WSN [J]. International journal of computer applications， 2013， 63（19）： 43?46.

[15] OpenSim Ltd. OMNeT++ discrete event simulator [EB/OL]. [2017?03?11]. http：//www.omnetpp.org/.

[16] KRAJZEWICZ D， ERDMANN J， BEHRISCH M. Recent development and applications of SUMO： simulation of urban mobility [J]. International journal on advances in systems and measurements， 2012， 5（3）： 128?138.