江西科技學(xué)院信息工程學(xué)院 邱 嵐

基于VANET的按需路由協(xié)議研究

江西科技學(xué)院信息工程學(xué)院 邱 嵐

近年來(lái)，智能交通系統(tǒng)在改善交通問(wèn)題方面發(fā)揮了關(guān)鍵作用。作為一種新形式的無(wú)線網(wǎng)絡(luò)， VANET已經(jīng)成為新的研究熱點(diǎn)。在城市場(chǎng)景中，由于現(xiàn)有的VANET路由協(xié)議在交通信息查詢方面存在不足，本文提出了一種新的按需路由協(xié)議，稱為T(mén)QOR協(xié)議。該協(xié)議采用Dijkstra算法，建立一個(gè)由道路交叉口序列組成的按需路徑，并限定轉(zhuǎn)發(fā)區(qū)域。同時(shí)，為了提高數(shù)據(jù)轉(zhuǎn)發(fā)的效率，該協(xié)議利用方向鄰居列表執(zhí)行優(yōu)化的貪婪轉(zhuǎn)發(fā)機(jī)制。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證，該協(xié)議具有很高的數(shù)據(jù)轉(zhuǎn)發(fā)效率。

按需路由協(xié)議；TQOR協(xié)議；交通信息查詢；數(shù)據(jù)轉(zhuǎn)發(fā)效率

1 引言

作為一種新形式的無(wú)線網(wǎng)絡(luò)，車載自組織網(wǎng)絡(luò)（vehicular Ad Hoc networks，VANET），已經(jīng)成為一種新的研究熱點(diǎn)，它主要是用來(lái)構(gòu)建成本低、部署簡(jiǎn)單、結(jié)構(gòu)開(kāi)放的自組織車輛間通信網(wǎng)絡(luò)[1]。VANET具有一般移動(dòng)自組網(wǎng)（Mobile Ad hoc Networking，MANET）的固有問(wèn)題，如隱藏點(diǎn)，暴露點(diǎn)，信息缺乏等[2]。然而，VANET又是非常特殊的，有其自身的特點(diǎn)。例如，拓?fù)浣Y(jié)構(gòu)變化迅速，無(wú)線信道不穩(wěn)定，鏈路不可靠等[3]。這些特性直接影響VANET信息分配性能，使得它的研究與MANET不同。在單播模式下，車輛行駛速度快而且拓?fù)浣Y(jié)構(gòu)變化也快，使得一些傳統(tǒng)的MANET路由協(xié)議無(wú)法適應(yīng)這樣的特性，數(shù)據(jù)轉(zhuǎn)發(fā)效率低。

在VANET中，有兩種信息傳輸模式：拉模式和推模式[4]。VANET中用于交通信息查詢的通信方式主要是廣播通信和單播通信。廣播通信以拉模式為主，而單播通信則采用推模式。在交通信息的采集和傳輸?shù)难芯恐?，有學(xué)者認(rèn)為廣播通信比單播通信更適合。因此，在VANET中，主要使用廣播通信來(lái)獲取交通信息。然而，在城市環(huán)境下，由于車輛密度過(guò)高，若采用廣播方式發(fā)布交通信息，會(huì)產(chǎn)生大量的冗余信息，降低數(shù)據(jù)的轉(zhuǎn)發(fā)效率。這種情況下，廣播通信不再適用，而應(yīng)使用單播通信。因此，在本文中，重點(diǎn)研究如何采用單播通信方式實(shí)現(xiàn)對(duì)于不同路段的交通信息查詢，而單播通信中的路由協(xié)議是信息查詢成功的重要因素。

2 VANET單播路由協(xié)議分析

目前，主要的VANET路由協(xié)議可以分為基于拓?fù)涞穆酚珊突谖恢玫穆酚傻取?/p>

2.1 AODV協(xié)議分析

基于拓?fù)涞穆酚墒且环N傳統(tǒng)的、最基本的自組織網(wǎng)絡(luò)路由，有兩種類型：表驅(qū)動(dòng)路由協(xié)議和按需路由協(xié)議[5]。所謂按需路由協(xié)議，也可稱之為反應(yīng)式路由協(xié)議，應(yīng)用廣泛[6]。這種路由協(xié)議的代表是按需距離矢量協(xié)議（Ad Hoc on-demand Distance Vector Protocol，AODV）。

T1時(shí)刻按S-a-D建立了一條源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D的路徑。但是在T2時(shí)刻，由于節(jié)點(diǎn)a的快速移動(dòng)，超出了與S的通信范圍，使得S-a的路徑斷裂，T1時(shí)刻所建立的S-a-D的路徑失效。當(dāng)然，通過(guò)局部修復(fù)機(jī)制，AODV路由協(xié)議可以重發(fā)RREQ和RREP消息。然而，這樣增加了數(shù)據(jù)包的傳輸延遲。在城市環(huán)境中，頻繁的鏈路斷裂，嚴(yán)重影響了AODV協(xié)議的傳輸質(zhì)量。

2.2 GPSR協(xié)議分析

基于位置的路由是使用地理位置信息。在VANET中，車輛節(jié)點(diǎn)的位置信息由配備的GPS定位設(shè)備采集。因此，VANET中基于位置的路由協(xié)議也是值得研究的。例如，貪婪周邊無(wú)狀態(tài)路由（Greedy Perimeter Stateless Routing，GPSR）協(xié)議使用一個(gè)貪婪轉(zhuǎn)發(fā)模式[7]。所謂貪婪轉(zhuǎn)發(fā)，是選擇距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，然而，就會(huì)出現(xiàn)這樣一個(gè)問(wèn)題：比起節(jié)點(diǎn)自身來(lái)說(shuō)，當(dāng)所有相鄰節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)都更遠(yuǎn)，貪婪轉(zhuǎn)發(fā)不能進(jìn)行[8]。

GPSR協(xié)議是一種無(wú)狀態(tài)路由，在數(shù)據(jù)傳輸之前不需要建立路徑[9]。因此，沒(méi)有路徑失效的問(wèn)題。適用于快速變化的網(wǎng)絡(luò)拓?fù)浜洼^大的網(wǎng)絡(luò)規(guī)模環(huán)境中。在高速公路上GPSR的性能很好，但在城市環(huán)境中仍有許多問(wèn)題。

根據(jù)GPSR貪婪轉(zhuǎn)發(fā)的原理，源節(jié)點(diǎn)S選擇的下一跳節(jié)點(diǎn)應(yīng)該是距離目的節(jié)點(diǎn)D最近的b節(jié)點(diǎn)，但是在城市環(huán)境中，b節(jié)點(diǎn)到D節(jié)點(diǎn)道路是不通的，導(dǎo)致貪婪轉(zhuǎn)發(fā)失敗。GPSR的貪婪轉(zhuǎn)發(fā)失敗，它會(huì)切換到周邊轉(zhuǎn)發(fā)模式。然而，這可能會(huì)加重網(wǎng)絡(luò)負(fù)擔(dān)，增加數(shù)據(jù)包傳輸延時(shí)，甚至可能發(fā)送失敗。

3 用于交通信息查詢的TQOR協(xié)議

前面詳細(xì)分析了AODV和GPSR路由協(xié)議在VANET城市場(chǎng)景下的不足之外。結(jié)合它們的優(yōu)缺點(diǎn)，本文提出了一種新的單播路由協(xié)議——用于交通信息查詢的按需路由（Traffic-information Query Ondemand Routing (TQOR)）協(xié)議，其目的是為了提高數(shù)據(jù)傳輸率。

3.1 TQOR的基本思想

TQOR協(xié)議借鑒了AODV，它也是按需建立路徑。然而，它又不同于AODV。AODV是用節(jié)點(diǎn)組成路徑，而TQOR是用十字路口交叉點(diǎn)組成。節(jié)點(diǎn)是移動(dòng)的，但十字路口交叉點(diǎn)卻是靜止的，由十字路口交叉點(diǎn)組成的路徑就是穩(wěn)定的。而前面所說(shuō)的AODV協(xié)議中節(jié)點(diǎn)的快速移動(dòng)會(huì)產(chǎn)生路徑斷裂，使得傳輸效率降低的缺陷，在TQOR中就不會(huì)出現(xiàn)。同時(shí)，TQOR協(xié)議還結(jié)合GPSR的貪婪轉(zhuǎn)發(fā)機(jī)制，實(shí)現(xiàn)的是十字路口交叉點(diǎn)之間的轉(zhuǎn)發(fā)，這樣可以避免在前面描述的GPSR協(xié)議的問(wèn)題。

圖1 轉(zhuǎn)發(fā)區(qū)域限定

3.2 轉(zhuǎn)發(fā)區(qū)域限定

轉(zhuǎn)發(fā)區(qū)域的限定也就是路徑建立的過(guò)程。在本文中，轉(zhuǎn)發(fā)區(qū)域限定為兩個(gè)圓的外接矩形。如圖1所示，交叉點(diǎn)9是距離源節(jié)點(diǎn)S最近的交叉口，作為起點(diǎn)，交叉點(diǎn)19是距離目的節(jié)點(diǎn)D最近的交叉口，作為終點(diǎn)，它們就是兩個(gè)圓的圓心。然后找到距離圓心最遠(yuǎn)的交叉口，也就是圖中的交叉點(diǎn)10和交叉點(diǎn)16，它們和圓心的距離為半徑，作兩個(gè)圓。這兩個(gè)圓的外接矩形，如圖1中的虛線框，即為轉(zhuǎn)發(fā)區(qū)域。采用這種算法，有可能在轉(zhuǎn)發(fā)區(qū)域內(nèi)搜索不到最短路徑，這時(shí)，可以通過(guò)層層擴(kuò)大圓的半徑來(lái)解決。

3.3 貪婪轉(zhuǎn)發(fā)

在上一節(jié)所建立的限制區(qū)域中執(zhí)行貪婪轉(zhuǎn)發(fā)策略，為了提高轉(zhuǎn)發(fā)性能，本文使用同向和反向兩個(gè)鄰居列表。

本文中的貪婪轉(zhuǎn)發(fā)與GPSR不同。在GPSR中，貪婪轉(zhuǎn)發(fā)選擇的下一跳節(jié)點(diǎn)是在鄰居列表中距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)。而在TQOR中，選擇的是鄰居列表中最接近下一個(gè)路口的節(jié)點(diǎn)，如圖2所示。

a是轉(zhuǎn)發(fā)節(jié)點(diǎn)，I1是節(jié)點(diǎn)剛離開(kāi)的路口、I2是節(jié)點(diǎn)即將到達(dá)的路口。圖中圓圈為通信范圍，它和以I2為圓心的圓圈相交的共同區(qū)域，即圖中的陰影部分，是下一跳選擇區(qū)域。我們可以選擇最接近I2的節(jié)點(diǎn)c作為該區(qū)域的下一跳節(jié)點(diǎn)。

圖2 TQOR的貪婪轉(zhuǎn)發(fā)

4 TQOR性能仿真

本文采用NCTUns6.0仿真軟件進(jìn)行仿真實(shí)驗(yàn)，PC操作系統(tǒng)是fedora12。NCTUns6.0是一種結(jié)合交通仿真和網(wǎng)絡(luò)仿真的VANET仿真軟件，可以為實(shí)驗(yàn)提供一個(gè)單一的車載網(wǎng)絡(luò)環(huán)境。實(shí)驗(yàn)性能指標(biāo)包括分組投遞率、平均跳數(shù)和分組傳輸延時(shí)。分組投遞率是指接收方接收到的和發(fā)送方發(fā)送的數(shù)據(jù)包總數(shù)之比；平均跳數(shù)是分組傳送過(guò)程中重新建立路由的次數(shù)，取平均值；分組傳輸延時(shí)是數(shù)據(jù)傳輸?shù)难訒r(shí)時(shí)間。通過(guò)這三個(gè)指標(biāo)，對(duì)AODV、GPSR和TQOR協(xié)議的性能進(jìn)行比較。

源節(jié)點(diǎn)和目的節(jié)點(diǎn)的道路距離為：400米，800米，1200米，1600米，2000米，2400米，和2800米，進(jìn)行了10次實(shí)驗(yàn)，取平均值。仿真結(jié)果如圖3、4、5所示。

圖3 分組投遞率

在圖3中，隨著距離的增加，TQOR協(xié)議的分組投遞率優(yōu)于其他兩個(gè)協(xié)議。AODV協(xié)議在距離增加時(shí)，會(huì)不斷的出現(xiàn)鏈路斷裂、修復(fù)失敗的現(xiàn)象，導(dǎo)致分組投遞率低。而對(duì)于GPSR協(xié)議來(lái)說(shuō)，在城市環(huán)境中，距離的增加、道路網(wǎng)絡(luò)、建筑物等對(duì)GPSR的性能有很大的影響。比方說(shuō)它會(huì)出現(xiàn)貪婪轉(zhuǎn)發(fā)失敗頻繁，切換到周邊轉(zhuǎn)發(fā)模式的現(xiàn)象。更甚至于在城市的場(chǎng)景中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的切斷使得周邊轉(zhuǎn)發(fā)模式也會(huì)失敗。因此，從圖3中可以看出，GPSR的分組投遞率隨距離的增加而迅速下降。在圖4中，GPSR協(xié)議由于貪婪轉(zhuǎn)發(fā)的特點(diǎn)，它的平均跳數(shù)相對(duì)較少，而TQOR協(xié)議的平均跳數(shù)最多，可見(jiàn)TQOR協(xié)議是以犧牲跳數(shù)為代價(jià)，以維持一個(gè)相對(duì)穩(wěn)定的分組投遞率，減少距離對(duì)它的影響。此外，圖5顯示三種協(xié)議的傳輸延時(shí)是在可容忍的范圍內(nèi)。

圖4 平均跳數(shù)

圖5 分組傳輸延時(shí)

5 結(jié)束語(yǔ)

本文分析了VANET中AODV和GPSR協(xié)議在城市場(chǎng)景下存在的不足和缺陷并提出了一種新的單播路由協(xié)議TQOR。TQOR采用Dijkstra算法，建立一個(gè)由道路交叉口序列組成的路徑，限定轉(zhuǎn)發(fā)區(qū)域，并在限定區(qū)內(nèi)執(zhí)行貪婪轉(zhuǎn)發(fā)機(jī)制。TQOR充分考慮車輛行駛的特點(diǎn)，建立鄰居列表時(shí)，用同向和反向的節(jié)點(diǎn)來(lái)構(gòu)造同向和反向的鄰居列表，以提高貪婪轉(zhuǎn)發(fā)性能。然后，通過(guò)仿真實(shí)驗(yàn)對(duì)TQOR和AODV、GPSR的性能進(jìn)行比較。結(jié)果表明，新協(xié)議具有相對(duì)穩(wěn)定的分組投遞率和較高的數(shù)據(jù)傳輸效率。

[1]王慧敏,趙海濤．車載自組織網(wǎng)絡(luò)中連通概率的預(yù)測(cè)與建模[J]．電信科學(xué),2016,(3)：118-121．

[2]向勇．基于車載自組網(wǎng)的動(dòng)態(tài)交通信息的挖掘和利用[J]．中興通訊技術(shù),2011,17(3)：29-34．

[3]王保林,張琦．基于車車通信的路況信息采集算法的研究[J]．現(xiàn)代電子技術(shù),2011,34(7)： 202-204．

[4]丁四景．VANET中基于網(wǎng)絡(luò)連通性的改進(jìn)AODV路由協(xié)議[D]．山東大學(xué)2015．

[5]夏梓峻,劉春風(fēng),趙増華,舒炎篆．基于鏈路預(yù)測(cè)的VANET路由算法[J]．計(jì)算機(jī)工程,2012,38(4)：110-111．

[6]熊煒,李清泉．高速公路場(chǎng)景中車用自組織網(wǎng)絡(luò)連通的必要條件[J]．軟件學(xué)報(bào),2010,21(11)：2906-2919．

[7]于海寧,張宏莉．VANETs路由協(xié)議的研究進(jìn)展[J]．電子學(xué)報(bào),2011,39(12)：2868-2879．

[8]沈永增,姚敏杰,李曉鳳．基于城市路網(wǎng)的VANET按需路由策略研究[J]．計(jì)算機(jī)應(yīng)用與軟件,2011,29(6)：236-238．

[9]姚敏杰．基于車輛聯(lián)網(wǎng)的實(shí)時(shí)路況信息系統(tǒng)研究[D]．浙江工業(yè)大學(xué),2012．

邱嵐（1984—），女，湖北武漢人，工學(xué)碩士，江西科技學(xué)院講師，研究方向：無(wú)線通信、車聯(lián)網(wǎng)。

江西省教育廳科學(xué)技術(shù)研究項(xiàng)目“基于VANET的實(shí)時(shí)路況信息系統(tǒng)研究”（No．GJJ151149）。