鄧少聞 羅代升

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

關(guān)鍵詞： 車聯(lián)網(wǎng)； 按需距離矢量； 鏈路質(zhì)量； 移動方向； 路徑判據(jù)； 降低傳輸時(shí)延

中圖分類號： TN915?34； TPT393 文獻(xiàn)標(biāo)識碼： 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 引 言

車聯(lián)網(wǎng)（Vehicle Ad Hoc Networks，VANETs）有望成為智能交通系統(tǒng)的實(shí)現(xiàn)技術(shù)[1]，已受到廣泛關(guān)注。VANETs為車輛間的信息交互提供了平臺，進(jìn)而提高了車輛行駛安全。然而，與移動自組織網(wǎng)絡(luò)不同，VANETs具有鮮明特性，如車輛的快速移動、拓?fù)鋭討B(tài)變化、車輛分布不均勻等。這些特性給VANETs的路由技術(shù)提出了挑戰(zhàn)[2]。

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

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

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

1 相關(guān)工作

按需距離矢量（Ad Hoc On?demand Distance Vector，AODV）路由屬于反應(yīng)式路由。AODV允許在多個(gè)移動節(jié)點(diǎn)間實(shí)現(xiàn)動態(tài)、自發(fā)式多跳通信連通。當(dāng)需要建立一條路由傳輸數(shù)據(jù)包時(shí)，節(jié)點(diǎn)（源節(jié)點(diǎn)）就向下一跳鄰居節(jié)點(diǎn)廣播請求數(shù)據(jù)包（Route Request，RREQ），觸發(fā)路由發(fā)現(xiàn)過程。一旦接收了RREQ包，節(jié)點(diǎn)就轉(zhuǎn)發(fā)RREQ包，直到RREQ包被傳遞至目的節(jié)點(diǎn)。

一旦目的節(jié)點(diǎn)接收了RREQ包，它就沿著此路徑向源節(jié)點(diǎn)回復(fù)（Route Replay，RREP），并且忽略隨后所接收的RREQ包。換而言之，目的節(jié)點(diǎn)選擇第一條到達(dá)的路徑作為數(shù)據(jù)傳輸路徑。AODV的路由發(fā)現(xiàn)過程如圖1所示。圖1a）中，源節(jié)點(diǎn)1廣播RREQ控制包，其鄰居節(jié)點(diǎn)通過廣播將RREQ傳輸?shù)侥康墓?jié)點(diǎn)8。

2 PA?AODV協(xié)議

PA?AODV協(xié)議利用節(jié)點(diǎn)的方向以鏈路質(zhì)量選擇路徑。先通過物理層和MAC層傳遞鏈路信息以及節(jié)點(diǎn)信息，再估計(jì)路徑質(zhì)量、移動方向因子，最終計(jì)算路徑判據(jù)權(quán)值。

2.1 路徑質(zhì)量因子

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

為此，先引用文獻(xiàn)[11]中指標(biāo)（Link Quality Indicator，LQI）表征鏈路質(zhì)量，然后再依據(jù)數(shù)據(jù)包傳遞率（Packet Delivery Ratio，PDR）[12]設(shè)置鏈路質(zhì)量門限值[LQIth]。當(dāng)某條鏈路質(zhì)量LQI低于[LQIth]，則說明此鏈路質(zhì)量較差。最后統(tǒng)計(jì)每條路徑中的低質(zhì)量鏈路數(shù)[QL]。

接下來，設(shè)定鏈路質(zhì)量門限值[LQIth]。為了更好地設(shè)置[LQIth]，利用實(shí)驗(yàn)測量LQI和PDR。當(dāng)鏈路的PDR大于80%，則認(rèn)為該條鏈路是穩(wěn)定的，并取其對應(yīng)的LQI作為門限值。通過實(shí)際的室內(nèi)場景，利用芯片CC2420作為節(jié)點(diǎn)，獲取LQI和PDR的數(shù)據(jù)關(guān)系，如圖2所示。在LQI=220時(shí)，LQI開始達(dá)到80%。因此，[LQIth=][80%]。

2.2 移動方向因子

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

車輛移動方向?qū)囕v間的通信連通時(shí)間有直接影響。為此，在選擇路徑時(shí)，也需考慮組建路徑的節(jié)點(diǎn)的移動方向。為了表述簡單，將構(gòu)成路徑的節(jié)點(diǎn)（除源節(jié)點(diǎn)和目的節(jié)點(diǎn)外）稱為中間節(jié)點(diǎn)。若鏈路的中間節(jié)點(diǎn)的移動方向與源節(jié)點(diǎn)和目的節(jié)點(diǎn)的連線方向的夾角一致（所謂的移動方向一致是指它們的夾解小于門限值），則它們的鏈路穩(wěn)定性得到提高，相應(yīng)地增加路徑的持續(xù)時(shí)間。

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

2.3 路由判據(jù)權(quán)值

在傳統(tǒng)的AODV路由協(xié)議中，目的節(jié)點(diǎn)只選擇第一時(shí)間到達(dá)的RREQ包所傳輸?shù)穆窂健ｏ@然，首次到達(dá)的RREQ的傳輸路徑未必是最穩(wěn)定的。為此，PA?AODV協(xié)議考慮多條路徑，并計(jì)算每條路徑的路徑判據(jù)權(quán)值，再選擇權(quán)值最小的路徑傳輸數(shù)據(jù)包。

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

2.4 數(shù)據(jù)包傳輸流程

一旦節(jié)點(diǎn)需要傳輸數(shù)據(jù)包，它就向鄰居節(jié)點(diǎn)傳輸RREQ包。由于PA?AODV協(xié)議需要計(jì)算路徑判據(jù)，在傳統(tǒng)的RREQ包中添加了鏈路質(zhì)量和方向變量。RREQ包的格式如圖4所示。

每個(gè)接收節(jié)點(diǎn)將自己的鏈路質(zhì)量和方向變量加入RREQ包再傳輸。當(dāng)目的節(jié)點(diǎn)接收后，計(jì)算每條路徑判據(jù)權(quán)重，并選擇路徑權(quán)重最小的路徑回復(fù)RREP。

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

3 實(shí)驗(yàn)分析

3.1 仿真模型

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

選擇3 968 m×1 251 m的矩形區(qū)域道路區(qū)域，其中道路有370條、十字路口124個(gè)。同時(shí)利用STRAW（Street Random Way）產(chǎn)生車輛移動數(shù)據(jù)。

仿真區(qū)域內(nèi)車輛數(shù)從100～350變化，車輛運(yùn)行速度從40～70 km/h變化，車輛通信范圍為300 m。數(shù)據(jù)包產(chǎn)生率為6 packet/s，數(shù)據(jù)包大小為512 B，信道帶寬為2 Mb/s，仿真時(shí)間為350 s。每次實(shí)驗(yàn)獨(dú)立重復(fù)100次，取平均值作為實(shí)驗(yàn)數(shù)據(jù)。

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

3.2 仿真結(jié)果及分析

1） 數(shù)據(jù)包傳遞率

本次實(shí)驗(yàn)主要考查車輛數(shù)對數(shù)據(jù)包傳遞率的影響。車輛數(shù)從100～350變化，且步長為50，車速為50 km/h。三個(gè)協(xié)議的數(shù)據(jù)包傳遞率隨車輛數(shù)的變化曲線如圖7所示。

依據(jù)圖7的數(shù)據(jù)可知，PA?AODV協(xié)議的數(shù)據(jù)包傳遞率較高，優(yōu)于GPCR和AODV協(xié)議。隨著車輛數(shù)的增加，優(yōu)勢越發(fā)明顯。而GPCR路由的數(shù)據(jù)包傳遞率最低，尤其是在低密度區(qū)域。當(dāng)車輛數(shù)小于200時(shí)，數(shù)據(jù)包傳遞率不到55%。原因在于GPCR協(xié)議在選擇轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，只依據(jù)節(jié)點(diǎn)的距離選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，并沒有考慮到鏈路質(zhì)量信息，導(dǎo)致路徑不穩(wěn)定，降低了數(shù)據(jù)包傳遞率。而相比于GPCR協(xié)議，AODV協(xié)議的數(shù)據(jù)包傳遞率較高，但它仍低于PA?AODV協(xié)議。這主要是因?yàn)椋篜A?AODV協(xié)議在選擇傳輸路徑時(shí)，充分考慮了每條鏈路的質(zhì)量，增加了路徑的穩(wěn)定性，最終提高了數(shù)據(jù)包傳遞率。

2） 平均端到端傳輸時(shí)延

三個(gè)協(xié)議的平均端到端傳輸時(shí)延隨節(jié)點(diǎn)數(shù)的變化曲線如圖8所示。PA?AODV協(xié)議的平均端到端傳輸時(shí)延最低，且較平穩(wěn)，并沒有隨節(jié)點(diǎn)數(shù)變化而波動。而AODV協(xié)議的平均端到端傳輸時(shí)延較高，高于GPCR協(xié)議。這主要是因?yàn)锳ODV協(xié)議在進(jìn)行路由發(fā)現(xiàn)階段采取了RREQ和RREP控制包，增加了一定的時(shí)延。而GPCR協(xié)議的端到端傳輸時(shí)延略低于AODV，這主要?dú)w結(jié)于GPCR協(xié)議總是選擇離目的節(jié)點(diǎn)近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，降低了傳輸跳數(shù)，進(jìn)而減少了一定的傳輸時(shí)延。

3） 平均傳輸跳數(shù)

三個(gè)協(xié)議的平均傳輸跳數(shù)隨節(jié)點(diǎn)數(shù)的變化曲線如圖9所示。

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

4 結(jié) 語

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

參考文獻(xiàn)

[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ìn)算法研究[J].傳感技術(shù)學(xué)報(bào)，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] 曹文君，薛善良.一種適用于城市車聯(lián)網(wǎng)的改進(jìn)的AODV協(xié)議[J].計(jì)算機(jī)與現(xiàn)代化，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的農(nóng)田無線傳感器網(wǎng)絡(luò)路由和休眠算法[J].微電子學(xué)與計(jì)算機(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ìn)的城市車載自組網(wǎng)絡(luò)路由協(xié)議研究[J].計(jì)算機(jī)工程與科學(xué)，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.