基于VANET的改進(jìn)型AODV路由協(xié)議研究*

邱 嵐

(江西科技學(xué)院 信息工程學(xué)院，江西 南昌 330098)

基于VANET的改進(jìn)型AODV路由協(xié)議研究*

邱 嵐

(江西科技學(xué)院 信息工程學(xué)院，江西 南昌 330098)

在車載自組織網(wǎng)絡(luò)中，常使用AODV路由協(xié)議，但是由于車載自組織網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)湟鬃冃浴⒐?jié)點運動快速性、數(shù)據(jù)交叉性、網(wǎng)絡(luò)連通間歇性等特點，傳統(tǒng)的AODV路由協(xié)議存在數(shù)據(jù)接收率低、路由重建次數(shù)多、傳輸延時時間長等問題。為此，提出一種基于車載自組織網(wǎng)絡(luò)的改進(jìn)型AODV路由協(xié)議。采用Dijkstra算法，找出源節(jié)點和目的節(jié)點之間連通概率最大的路徑，對傳統(tǒng)的AODV協(xié)議進(jìn)行改進(jìn)。然后通過仿真軟件進(jìn)行驗證和分析，證明改進(jìn)型AODV路由協(xié)議比傳統(tǒng)的AODV協(xié)議數(shù)據(jù)接收率更高、路由重建次數(shù)更少、傳輸延時更短。

車載自組織網(wǎng)絡(luò)；AODV路由協(xié)議； Dijkstra算法

0 引言

車輛自組織網(wǎng)絡(luò)(Vehicular AdHoc Network,VANET)是移動自組織網(wǎng)絡(luò)(Mobile AdHoc Network,MANET)在智能交通方面的一種應(yīng)用。在VANET中，AODV(AdHoc On-demand Distance Vector)是一種常用的按需路由協(xié)議，主要采用的是DSR(Dynamic Source Routing)中的廣播路由發(fā)現(xiàn)機(jī)制以及DSDV(Destination Sequenced Distance Vector)中的周期更新機(jī)制[1]。在AODV中節(jié)點的數(shù)據(jù)傳輸，只有在沒有有效通信鏈路時，才會啟動路由請求信息，這樣可以減少廣播量，提高效率[2]。

目前，很多學(xué)者采用AODV協(xié)議，但是對于VANET網(wǎng)絡(luò)來說，因其具有車輛數(shù)量多、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜等特性，傳統(tǒng)的AODV協(xié)議已經(jīng)不能滿足VANET網(wǎng)絡(luò)的需求。所以，國內(nèi)外很多研究者開始研究AODV協(xié)議的改進(jìn)方法，以適應(yīng)VANET網(wǎng)絡(luò)的需求，目前取得了不少的成就。例如，ASENOV H等人提出一種基于地理位置的GeoAODV協(xié)議[3]，KUMMAKASIKIT M等人提出一種MAODV路由協(xié)議[4]， AYASH M等人提出AODV_LAR和AODV_Line兩種協(xié)議[5]。和文獻(xiàn)[3]中的GeoAODV協(xié)議一樣，AODV_LAR協(xié)議和AODV_Line協(xié)議沒有考慮鏈路的網(wǎng)絡(luò)連通性。在國內(nèi)，也有不少學(xué)者對AODV協(xié)議展開研究。例如，詹巧昕提出一種緊急報警和查詢消息的改進(jìn)型路由協(xié)議EIM-AODV (Emergency warning and Inquire Message based on AODV)[6]，謝波等人提出一種位置預(yù)測算法[7]，姜飛提出一種改進(jìn)型AODV路由協(xié)議V-SARP (Stability AODV Routing Protocol for VANET)[8]。

AODV路由協(xié)議的改進(jìn)可以分為兩大方向，一是從鏈路質(zhì)量方面來改進(jìn)，二是從位置信息方面來改進(jìn)。前者可以提高數(shù)據(jù)接收率但是路由重建次數(shù)多，后者可以減少路由重建次數(shù)但是數(shù)據(jù)接收率低。為了綜合各方面的因素，本文提出一種基于VANET的改進(jìn)型AODV路由協(xié)議。選取道路長度、車輛數(shù)、車輛平均速度作為三個交通參數(shù)，建立VANET網(wǎng)絡(luò)連通性模型。根據(jù)模型，采用Dijkstra算法，找到源節(jié)點和目的節(jié)點之間的VANET網(wǎng)絡(luò)連通概率最大的路徑為最優(yōu)路徑，作為AODV協(xié)議信息轉(zhuǎn)發(fā)的控制區(qū)域，并增加節(jié)點位置信息，對傳統(tǒng)的AODV協(xié)議進(jìn)行改進(jìn)。實驗表明，這種改進(jìn)型AODV路由協(xié)議比傳統(tǒng)的AODV協(xié)議數(shù)據(jù)接收率更高、路由重建次數(shù)更少、傳輸延時更短。

1 VANET網(wǎng)絡(luò)連通性模型的建立

選取道路長度、車輛數(shù)、車輛平均速度這三個參數(shù)為主要的交通參數(shù)，采用最小二乘法[9]，找到VANET網(wǎng)絡(luò)連通性和交通參數(shù)之間的關(guān)系。設(shè)道路長度為L，車輛數(shù)為C，車輛平均速度為V，則可以通過公式(1)計算出源節(jié)點和目的節(jié)點的網(wǎng)絡(luò)連通概率。

P=f{L,C,V}

(1)

式中，f為最小二乘法的逼近函數(shù)[9]。

2 最優(yōu)路徑的選擇

2.1 Dijkstra算法簡介

Dijkstra算法是由DIJKSTRA E D在1959年提出的，因其具有完備的理論和較強的魯棒性而廣泛被使用[10]。Dijkstra算法是一種尋找最優(yōu)路徑的算法。最優(yōu)路徑是指拓?fù)浣Y(jié)構(gòu)中權(quán)值最小的節(jié)點組成的路徑集合[11]，如公式(2)所示：

(2)

式中，D為源節(jié)點到目的節(jié)點的一條路徑，F(xiàn)(Di)為D的權(quán)，N為從源節(jié)點到目的節(jié)點的路徑個數(shù)，Dmin為所有路徑D中權(quán)值最小的路徑。

2.2 最優(yōu)路徑的尋找方法

根據(jù)前面建立的VANET網(wǎng)絡(luò)連通性模型，采用Dijkstra算法，求出源節(jié)點和目的節(jié)點之間的VANET網(wǎng)絡(luò)連通概率乘積最大的路徑集合。具體的方法如下：

(1)通過車載設(shè)備采集道路長度L、車輛數(shù)C、車輛平均速度V。

(2)根據(jù)VANET網(wǎng)絡(luò)連通性模型求出源節(jié)點到目的節(jié)點之間所有路徑的網(wǎng)絡(luò)連通概率。

(3)各路徑的權(quán)值是網(wǎng)絡(luò)連通概率的對數(shù)的絕對值。

(4)采用Dijkstra算法尋找到最優(yōu)路徑。

3 基于VANET的改進(jìn)型AODV路由協(xié)議

假設(shè)道路長度、車輛數(shù)、車輛平均速度三個交通參數(shù)可以通過車載設(shè)備獲得。另外，各個節(jié)點的位置信息已經(jīng)被采集到。

3.1 設(shè)計思路

在VANET中，傳統(tǒng)的AODV路由協(xié)議存在數(shù)據(jù)接收率低、路由重建次數(shù)多、傳輸延時長等缺點[12]。本文針對這些缺點，提出了一種基于VANET的改進(jìn)型AODV路由協(xié)議。具體的設(shè)計思路如下：

(1)在建立路由之前，可以通過車載設(shè)備事先獲得道路長度、車輛數(shù)、車輛平均速度等信息，源節(jié)點到目的節(jié)點之間所有路徑的網(wǎng)絡(luò)連通概率由VANET網(wǎng)絡(luò)連通性模型求出，并且采用Dijkstra算法尋找到最優(yōu)路徑。

(2)在路由請求的過程中，首先由源節(jié)點向與之相連的節(jié)點發(fā)送路由請求分組(RREQ)報文，然后根據(jù)路由表，接收到報文的節(jié)點可以判斷自己是否在最優(yōu)路徑中。如果不在，則丟棄RREQ報文；如果在，則轉(zhuǎn)發(fā)RREQ報文。重復(fù)上述步驟，直到要傳送的信息到達(dá)目的節(jié)點為止。

(3)在路由應(yīng)答的過程中，目的節(jié)點若收到RREQ報文，則將路由應(yīng)答RREP報文送回給源節(jié)點。若中間節(jié)點收到RREP報文，它會先判斷自己是否處于最優(yōu)路徑中。如果在，還要確定路由表中有沒有源節(jié)點的反向路由。若有，則轉(zhuǎn)發(fā)RREP消息給源節(jié)點并建立反向路由；若沒有，則只建立反向路由。

3.2 設(shè)計方法

3.2.1 報文格式

在路由請求階段，源節(jié)點所發(fā)送的改進(jìn)型RREQ的報文格式如圖1所示。在傳統(tǒng)的RREQ報文基礎(chǔ)上增加了最優(yōu)路徑集合(ROAD_IDs)，是源節(jié)點和目的節(jié)點之間的VANET網(wǎng)絡(luò)連通概率乘積最大的路徑集合。在路由應(yīng)答階段，目的節(jié)點發(fā)送回源節(jié)點的路由應(yīng)答RREP報文的格式如圖2所示。

圖1 改進(jìn)型RREQ的報文格式

圖2 改進(jìn)型RREP的報文格式

3.2.2 路由請求流程

路由請求流程如下：

(1)節(jié)點收到路由請求分組(RREQ)報文。

(2)查看路由表，判斷ROAD_IDs中是否包含本節(jié)點。

(3)如果沒有，則丟棄RREQ報文；如果有，則進(jìn)一步判斷目的節(jié)點路由是否存在，是否有效。

(4)若目的節(jié)點路由存在并有效，則設(shè)置RREQ_ID和目的節(jié)點的序號，增加自身序號的條數(shù)，最后發(fā)送RREQ報文信息。

3.2.3 路由應(yīng)答流程

路由應(yīng)答流程如下：

(1)節(jié)點收到路由請求RREQ報文。

(2)更新路由表，設(shè)置路由應(yīng)答RREP報文信息，并將該信息發(fā)送回源節(jié)點。

(3)收到RREP報文的節(jié)點首先需要先判斷是否包含在ROAD_IDs中。

(4)如果在，就繼續(xù)確定路由表有沒有源節(jié)點的反向路由。

(5)若有，則轉(zhuǎn)發(fā)RREP消息給源節(jié)點并建立反向路由；若沒有，則只建立反向路由。

4 仿真驗證與結(jié)果分析

本文采用VanetMobiSim仿真軟件模擬真實的交通路況，選取車輛數(shù)為100～400，車輛的平均速度為5～30 m/s，并采用NS2仿真軟件仿真網(wǎng)絡(luò)性能。從數(shù)據(jù)接收率、路由重建次數(shù)和傳輸延遲時間三個方面來對基于VANET的改進(jìn)型AODV路由協(xié)議的優(yōu)勢進(jìn)行分析和驗證。

4.1 數(shù)據(jù)接收率的分析

數(shù)據(jù)接收率指的是目的節(jié)點接收的數(shù)據(jù)量和源節(jié)點發(fā)出的數(shù)據(jù)量的百分比。

從圖3和圖4所示的仿真結(jié)果可以看出，不管是在不同速度還是在不同車輛數(shù)的情況下，本文所設(shè)計的改進(jìn)型AODV路由協(xié)議的數(shù)據(jù)接收率明顯要高于傳統(tǒng)的AODV協(xié)議。可見，利用網(wǎng)絡(luò)連通性模型和Dijkstra算法找最優(yōu)路徑的這種改進(jìn)方法是可行的，不僅提高了鏈路質(zhì)量，也提高了數(shù)據(jù)接收率。

圖3 不同速度時的數(shù)據(jù)接收率

圖4 不同車輛數(shù)時的數(shù)據(jù)接收率

4.2 路由重建次數(shù)的分析

路由重建次數(shù)主要反映的是網(wǎng)絡(luò)的擁塞程度。

從圖5和圖6所示的仿真結(jié)果中可以看出，車輛平均速度越快，車輛數(shù)越多，路由重建次數(shù)越多。這是因為車輛平均速度越快，鏈路斷裂就會越頻繁，而車輛數(shù)的增多，意味著從源節(jié)點到目的節(jié)點的轉(zhuǎn)發(fā)點也會增多，所以增加了路由的重建次數(shù)。不過，本文所設(shè)計的改進(jìn)AODV協(xié)議比傳統(tǒng)AODV協(xié)議的路由重建次數(shù)少。因為傳統(tǒng)的AODV協(xié)議采用的是洪泛廣播的方式，只要接收到數(shù)據(jù)的節(jié)點都會進(jìn)行轉(zhuǎn)發(fā)，產(chǎn)生大量的浪費。而基于VANET的改進(jìn)型AODV協(xié)議只有在最優(yōu)路徑上的節(jié)點才會轉(zhuǎn)發(fā)信息，所以可以減少路由重建次數(shù)，避免不必要的浪費。

圖5 不同速度時的路由重建次數(shù)

圖6 不同車輛數(shù)時的路由重建次數(shù)

4.3 傳輸延遲時間的分析

傳輸延遲時間指的是接收信息的時間和發(fā)送信息的時間之差。

從圖7和圖8所示的仿真結(jié)果中可以看出，速度越快，車輛數(shù)越少，延遲時間越長。因為節(jié)點的移動速度越快，路由重建次數(shù)越多，所以傳輸延遲時間越長。而車輛數(shù)越多，路由的有效時間越長，所以傳輸延遲時間越短。不過，從圖中可以看出，本文所設(shè)計的改進(jìn)型AODV路由協(xié)議的傳輸延遲時間明顯要小于傳統(tǒng)的AODV協(xié)議。因為改進(jìn)型AODV路由協(xié)議選取的是連通概率最大的路徑，減少了路由重建次數(shù)，從而減少了傳輸延遲時間。

圖7 不同速度時的傳輸延遲時間

圖8 不同車輛數(shù)時的傳輸延遲時間

5 結(jié)論

由于傳統(tǒng)的AODV路由協(xié)議存在數(shù)據(jù)接收率低、路由重建次數(shù)多、傳輸延遲時間長等問題，本文提出了一種基于VANET的改進(jìn)型AODV路由協(xié)議。采用Dijkstra算法，找到源節(jié)點和目的節(jié)點之間的VANET網(wǎng)絡(luò)連通概率最大的路徑為最優(yōu)路徑，作為AODV協(xié)議信息轉(zhuǎn)發(fā)的控制區(qū)域，并增加節(jié)點位置信息，對傳統(tǒng)的AODV協(xié)議進(jìn)行改進(jìn)。實驗結(jié)果表明，基于VANET的改進(jìn)型AODV路由協(xié)議比傳統(tǒng)的AODV協(xié)議數(shù)據(jù)接收率更高，路由重建次數(shù)更少、傳輸延時更短。當(dāng)然，本文中的設(shè)計還存在一些不足，例如采用Dijkstra算法所得到的最優(yōu)路徑無法判斷路徑中的每一個節(jié)點是否是最優(yōu)，后續(xù)的研究將對這一部分進(jìn)行優(yōu)化，使AODV路由協(xié)議更加適應(yīng)VANET網(wǎng)絡(luò)。

[1] 葉波. 面向車載網(wǎng)的基于AODV優(yōu)化路由協(xié)議的研究[J].電子技術(shù)應(yīng)用,2014,40(12):110-114.

[2] 沈永增,姚敏杰,李曉鳳.基于城市路網(wǎng)的VANET按需路由策略研究[J].計算機(jī)應(yīng)用軟件,2012,29(6):236-238.297.

[3] HOSSEINI-POZVEH M, NEMATBAKHSH M A, MOVAHHEDINIA H. GPS-enhanced AODV routing[C].International Conference on Wireless Networks, 2009: 651-656.

[4] KUIMNAKASIKIT M, THIPCHAKSURAT S, VARAKULSIRIPHUNTH R. Performance improvement of associativity-based routing protocol for mobile ad hoc networks[C].Fifth International Conference on Information, 2005:16-20.

[5] AYASH M, MIKKI M, YIM K B. Improved AODV routing prcrtocol to cope with high overhead in high mobility[C].2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, 2012:244-251.

[6] 詹巧昕.適用于高速公路車輛預(yù)警信息傳遞的改進(jìn)型VANET路由協(xié)議[J].第八屆中國智能交通年會優(yōu)秀論文集,2012:838-845.

[7] 謝波,肖曉強,徐明,等.基于速度向量的VANET位置預(yù)測路由協(xié)議[J].計算機(jī)工程,2009,35(23):112-114.

[8] 姜飛.車載AdHoc網(wǎng)絡(luò)按需路由協(xié)議的改進(jìn)及仿真[D].北京:北京郵電大學(xué),2010.

[9] 吳宗敏.散亂數(shù)據(jù)擬合的模型、方法和理論[M].北京:科學(xué)出版社,2007.

[10] 馮欣欣.Dijkstra算法在嵌入式GIS中的優(yōu)化實現(xiàn)[J].北京理工大學(xué)學(xué)報,2009,29(10):873-876.

[11] 夏梓峻,劉春風(fēng),趙増華,等.基于鏈路預(yù)測的VANET路由算法[J].計算機(jī)工程,2012，38(4):110-111.

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

The improvement AODV routing procol based on VANET

Qiu Lan

(Department of Information Engineering, Jiangxi University of Technology, Nanchang 330098, China)

In VANET, AODV routing protocol is often used. But because of the characteristics of network topology change ability, node movement celerity, data intersectionality, and VANET network connectivity intermittence, the traditional AODV routing protocol has problems such as the data receiving rate is low, the number of rerouting is high and transmission delay time is long etc. This paper proposes an improved AODV routing protocol based on VANET. Dijkstra algorithm is used to find the path between the source node and the destination node, and the traditional AODV protocol is improved. Then through the simulation software to verify and analyze, it is proved that compared to the traditional AODV protocol, the improved AODV routing protocol has leigher data receiving rate, less routing reconstruction times, and shorter transmission delay time.

VANET; AODV routing protocol; Dijkstra algorithm

江西省教育廳科學(xué)技術(shù)研究項目(GJJ151149)

TN929.5

A

10.19358/j.issn.1674- 7720.2017.16.018

邱嵐.基于VANET的改進(jìn)型AODV路由協(xié)議研究[J].微型機(jī)與應(yīng)用，2017,36(16)：63-66.

2017-02-16)

邱嵐(1984-)，通信作者，女，碩士研究生，講師，主要研究方向：無線通信、車聯(lián)網(wǎng)技術(shù)。E-mail:79041684@qq.com。