蔡 菁，朱余兵

（武漢理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北武漢430063）

1 引言

車載自組網(wǎng)VANET（Vehicular Ad hoc NETwork）是專門為車輛間通信而設(shè)計的自組織網(wǎng)絡(luò)，它創(chuàng)造性地將移動自組網(wǎng)技術(shù)應(yīng)用于車輛間通信［1］。車載自組網(wǎng)的特點有：車輛節(jié)點沿道路移動并呈“帶”狀分布，可安裝GPS和電子地圖來準確獲得自己的位置信息等。城市車載自組網(wǎng)相對一般VANET還具有以下特點：車輛的移動速度大致在5～20 m/s，車輛的運動受紅綠燈的限制，城市道路基本上都是橫豎相交，車輛密度比較大等。

車載自組網(wǎng)作為智能交通的核心已經(jīng)成為近年來無線網(wǎng)絡(luò)及智能交通領(lǐng)域的研究熱點，但專門針對城市車載自組網(wǎng)的研究還比較少，特別是對網(wǎng)絡(luò)層路由協(xié)議的研究相對缺乏。文獻［2］對兩種按需路由協(xié)議—DSR協(xié)議和AODV協(xié)議在節(jié)點密度不同的VANET下進行了仿真分析和對比，仿真實驗結(jié)果表明，AODV協(xié)議比DSR協(xié)議更加適合車輛密度大的VANET環(huán)境。文獻［3］對DSR協(xié)議和AODV協(xié)議在城市環(huán)境下的VANET環(huán)境中進行了仿真分析和對比，仿真實驗結(jié)果表明，在城市環(huán)境下的VANET中，AODV協(xié)議優(yōu)于DSR協(xié)議。但是，在城市車載自組網(wǎng)中，AODV協(xié)議廣播式路由探測方式隨著網(wǎng)絡(luò)規(guī)模的增大，發(fā)送的冗余幀會迅速增加，極大地降低了協(xié)議的性能［4］。因此，本文針對城市環(huán)境下車載自組網(wǎng)的特點，考慮到AODV協(xié)議廣播式路由探測的不足，提出一種改進的新的AODV協(xié)議。該協(xié)議采用先單播后廣播的方式進行路由探測，以減少路由探測幀的發(fā)送，從而達到提高協(xié)議性能的目的。此外，在單播路由探測階段同時考慮貪婪轉(zhuǎn)發(fā)和路由穩(wěn)定兩個因素，使得探測到的路由穩(wěn)定性高，平均跳數(shù)少。

2 AODV協(xié)議改進的基本方案

傳統(tǒng)的貪婪轉(zhuǎn)發(fā)算法GPSR［5］（Greedy Perimeter Stateless Routing）發(fā)送數(shù)據(jù)時，下一跳都是臨時決定的，而不需要維護路由表。但是，AODV協(xié)議是需要維護路由表的。如果AODV采用貪婪轉(zhuǎn)發(fā)的思想進行路由探測，那么探測到的路由很可能是不穩(wěn)定的。因為貪婪轉(zhuǎn)發(fā)的思想是盡可能地接近目的節(jié)點，中間節(jié)點總是將路由探測發(fā)送到盡可能遠離當前節(jié)點的鄰節(jié)點，那么探測到的路由中相鄰節(jié)點之間的生存時間會比較短，也就是說，探測到的路由會經(jīng)常斷裂，這樣會降低AODV協(xié)議的性能。因此，用貪婪轉(zhuǎn)發(fā)進行路由探測還應(yīng)該考慮鏈路的生存時間。

因此，本文在用貪婪轉(zhuǎn)發(fā)進行單播路由探測時，在選擇下一跳時同時考慮投影最長和鏈路生存時間最長兩個因素，用w衡量。下一跳節(jié)點應(yīng)該是鄰節(jié)點表中w值最大的那個節(jié)點?？梢源_定按照本文思想找到的路由的跳數(shù)將比按照傳統(tǒng)貪婪轉(zhuǎn)發(fā)思想找到的路由的跳數(shù)少。

其中，Ti表示鄰節(jié)點表中節(jié)點i到本節(jié)點的鏈路生存時間；Li表示鄰節(jié)點表中節(jié)點i與本節(jié)點的連線在本節(jié)點到目的節(jié)點連線上投影的長度；Tmin表示Ti中的最小值；Tmax表示Ti中的最大值；Lmin表示Li中的最小值；Lmax表示Li中的最大值。

只要取得合適的α值，改進后的算法能夠選擇一個跳數(shù)相對較少，鏈路相對穩(wěn)定的路由。

相鄰節(jié)點i與節(jié)點j之間鏈路生存時間的計算公式為：

其中，a＝vicosθi－vjcosθj；b＝xi－xj；c＝visinθi－vjsinθj；d＝y(tǒng)i－yj，（xi，yi）為節(jié)點i的坐標；（xj，yj）為節(jié)點j的坐標；vi、vj分別為節(jié)點i和節(jié)點j的移動速度；θi、θj分別為節(jié)點i和節(jié)點j的移動方向；R為節(jié)點i和節(jié)點j之間的最大通信距離。

轉(zhuǎn)發(fā)節(jié)點A與其鄰節(jié)點B的連線在轉(zhuǎn)發(fā)節(jié)點A到目的節(jié)點D連線的投影長度的計算公式為：

其中，（x1，y1）為轉(zhuǎn)發(fā)節(jié)點A的坐標，（x2，y2）為目的節(jié)點D的坐標，（x3，y3）為鄰節(jié)點B的坐標。在鄰節(jié)點表中選擇當前節(jié)點和鄰節(jié)點的連線在當前節(jié)點和目的節(jié)點連線上的投影越長的鄰節(jié)點作為下一跳，更適合城市環(huán)境下的車載自組網(wǎng)。

3 改進協(xié)議的路由算法及關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

假設(shè)在城市環(huán)境下的車載自組網(wǎng)中，車輛節(jié)點能夠通過電子地圖和安裝的GPS系統(tǒng)獲得自己和目的車輛節(jié)點的位置信息。當源節(jié)點有數(shù)據(jù)需要發(fā)送時，如果它沒有到達目的節(jié)點的路由，那么源節(jié)點會發(fā)起路由探測。如果是第一次向該目的節(jié)點發(fā)起路由探測，則啟動單播路由探測。源節(jié)點首先按照公式（1）計算自己鄰節(jié)點表中所有鄰節(jié)點的w值，并將路由探測消息發(fā)送給w值最大的鄰節(jié)點。該鄰節(jié)點查看能否到達目的節(jié)點，如果能夠到達目的節(jié)點，則建立到達目的節(jié)點的路由，源節(jié)點將開始數(shù)據(jù)的發(fā)送。如果不能到達目的節(jié)點，則按照同樣的方式將路由請求發(fā)送給自己鄰節(jié)點表中w值最大的鄰節(jié)點。如果在一段時間內(nèi)不能探測到目的節(jié)點的路由，則將該消息報告給源節(jié)點；源節(jié)點將啟動廣播式路由探測方式進行路由探測。AODV改進協(xié)議的算法流程如圖1所示。

（1）HELLO分組格式。

按照本文的思想，必須按照公式（1）計算節(jié)點之間的鏈路生存時間，那么需要將自己的位置、速度信息通過HELLO分組發(fā)送給鄰節(jié)點。新的HELLO分組包含目的節(jié)點坐標、目的節(jié)點速度、目的節(jié)點IP地址、目的節(jié)點序列號、生存時間等主要信息。

（2）鄰節(jié)點表的數(shù)據(jù)結(jié)構(gòu)。

Figure 1 Flowchart of the improved AODV routing protocol圖1 AODV改進協(xié)議的算法流程

在經(jīng)典AODV協(xié)議中，每個節(jié)點的鄰節(jié)點表中的每個條目記錄了該節(jié)點的一個鄰節(jié)點的IP地址和鏈路失效時間。按照本文的思想，鄰節(jié)點表還應(yīng)該存儲鄰節(jié)點的位置坐標、鄰節(jié)點的速度信息。那么，新的鄰節(jié)點表的數(shù)據(jù)結(jié)構(gòu)可以使用下面的結(jié)構(gòu)體定義：

其中，nb＿ad dr表示某一個鄰節(jié)點的編號（IP地址），nb＿expire表示鄰節(jié)點的默認鏈路失效時間，next指向鄰節(jié)點表的下一個條目，x＿coordinate表示某一個鄰節(jié)點的橫坐標，y＿coordinate表示某一個鄰節(jié)點的縱坐標，d x＿coordinate表示某一個鄰節(jié)點移動方向與x軸夾角的余弦值，dy＿coordinate表示某一個鄰節(jié)點移動方向與y軸夾角的正弦值，node＿speed表示某一個鄰節(jié)點的移動速度。

4 協(xié)議仿真及分析

本文采用NS－2仿真平臺進行仿真，并采用Vanet Mobisim定義節(jié)點移動模型。仿真實驗將在不同節(jié)點密度、不同最大速度、不同CBR流數(shù)值的情況下，從平均端到端時延、丟包率、吞吐量及路由開銷四個方面比較經(jīng)典AODV協(xié)議和改進后的AODV協(xié)議的性能。主要仿真參數(shù)如表1所示。

Table 1 Primary simulation parameter settings表1 主要仿真參數(shù)設(shè)置

（1）不同節(jié)點密度下的性能比較。

在不同節(jié)點密度（50，60，70，80，90，100）、車輛速度為3.33 m/s～13.89 m/s、CBR數(shù)為5對的情況下的仿真結(jié)果如圖2所示。

改進后AODV協(xié)議在路由探測階段采用先單播后廣播的方式，隨著節(jié)點數(shù)目的增加、城市環(huán)境連通性的加強，單播方式探測到的路由的成功率增加了。改進后AODV協(xié)議由于先采用單播路由探測的方式發(fā)送request分組，如果探測成功那么目的節(jié)點只會發(fā)送一個reply分組。所以，改進后AODV協(xié)議的路由開銷會比經(jīng)典AODV協(xié)議少。由于單播方式探測到的路由考慮了路由的平均跳數(shù)和路由的穩(wěn)定性，在經(jīng)典AODV協(xié)議和改進后AODV協(xié)議探測到的路由跳數(shù)差不多相同的情況下，改進后AODV協(xié)議探測到的路由考慮了鏈路的生存時間，這樣會減少路由斷裂的次數(shù)、降低端到端的時延和丟包率、增加吞吐量，所以改進后AODV協(xié)議在平均端到端時延、丟包率、吞吐量方面會優(yōu)于經(jīng)典AODV協(xié)議。同時，隨著節(jié)點數(shù)目的增加，城市的連通性加強，網(wǎng)絡(luò)中的分組不會因為沒有從源節(jié)點到目的節(jié)點的路由而丟包，所以經(jīng)典AODV協(xié)議和改進后AODV協(xié)議的平均端到端時延呈現(xiàn)下降的趨勢，丟包率會基本呈現(xiàn)下降趨勢，吞吐量也會基本呈增長趨勢。由于網(wǎng)絡(luò)中HELLO分組會隨著節(jié)點數(shù)目的增加而增加，所以路由開銷會隨著節(jié)點數(shù)目的增加而增加。

Figure 2 Performance under different number of nodes圖2 不同節(jié)點密度下的性能

（2）不同最大速度下的性能比較。

在不同車輛最大速度（m/s）（5，9，13，17，21，25m/s）、車輛數(shù)為100輛、CBR數(shù)為5對的情況下的仿真結(jié)果如圖3所示。

Figure 3 Performance under different max speed of nodes圖3 不同最大速度下的性能

隨著節(jié)點速度的增加，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)變化加劇，路由斷裂的次數(shù)會增加。由于路由斷裂而必須重新發(fā)現(xiàn)新的路由，使得平均端到端時延升高、丟包率升高、吞吐量降低。由于仿真實驗是在比較連通的城市環(huán)境下進行（節(jié)點數(shù)目為100個），所以改進后AODV協(xié)議單播探測到的路由的成功率比較大，路由表中單播探測到的路由條目比例比較大，廣播探測到的路由條目比例相對較少。經(jīng)典AODV協(xié)議沒有考慮鏈路的生存時間，所以改進后AODV路由的穩(wěn)定性會比經(jīng)典AODV高，路由的斷裂次數(shù)會相對降低，所以改進后AODV協(xié)議會比經(jīng)典AODV協(xié)議的網(wǎng)絡(luò)時延低、丟包率低、吞吐量高。改進前后的AODV協(xié)議在節(jié)點數(shù)目相同的情況下，網(wǎng)絡(luò)中的HELLO分組數(shù)量會幾乎相同，但是由于網(wǎng)絡(luò)的連通性使得單播探測成功率增加。改進后AODV協(xié)議單播探測發(fā)送的request分組和reply分組數(shù)量會比經(jīng)典的AODV協(xié)議少，所以改進后AODV協(xié)議比經(jīng)典AODV協(xié)議的路由負載小。

（3）不同業(yè)務(wù)流下的性能比較。

在不同CBR數(shù)值（5，9，13，17，21，25）、車輛速度為3.33 m/s～13.89 m/s、車輛數(shù)為100輛的情況下的仿真結(jié)果如圖4所示。

Figure 4 Performance under different number of CBR圖4 不同業(yè)務(wù)流下的性能

改進后AODV協(xié)議探測路由時考慮了鏈路穩(wěn)定性，所以改進后AODV協(xié)議探測到的路由斷裂次數(shù)會比經(jīng)典AODV協(xié)議少。路由斷裂后改進前后的協(xié)議都會修復(fù)或者重新探測路由，這會使得網(wǎng)絡(luò)的時延增加、丟包率升高、吞吐量降低。由于仿真實驗是在比較連通的城市環(huán)境下進行（節(jié)點數(shù)目為100個），所以改進后AODV協(xié)議單播探測到的路由的成功率比較大。改進后AODV協(xié)議采用單播的方式探測到的路由的穩(wěn)定性比經(jīng)典AODV協(xié)議的高，發(fā)送的request分組和reply分組比經(jīng)典AODV協(xié)議少。所以，改進后AODV協(xié)議會比經(jīng)典AODV協(xié)議的平均端到端時延低、丟包率低、吞吐量高、路由開銷低。隨著CBR數(shù)目的增加，網(wǎng)絡(luò)的吞吐量在網(wǎng)絡(luò)未飽和之前會增加，網(wǎng)絡(luò)中的request分組和reply分組會增加，在節(jié)點數(shù)目相同的情況下，網(wǎng)絡(luò)中HELLO分組會相同，所以改進前后的AODV協(xié)議的路由開銷、吞吐量都會增加。

5 結(jié)束語

本文針對城市車載自組網(wǎng)的特點，在AODV協(xié)議的基礎(chǔ)上進行了協(xié)議的改進，改進協(xié)議采用貪婪轉(zhuǎn)發(fā)的單播式路由探測和經(jīng)典AODV的廣播式路由探測相結(jié)合的路由探測方式，且單播路由探測在選擇下一跳轉(zhuǎn)發(fā)節(jié)點時同時考慮貪婪轉(zhuǎn)發(fā)和鏈路穩(wěn)定兩個因素，減少了廣播幀的發(fā)送，提高了路由的穩(wěn)定性。本文同時利用NS－2對改進后的AODV協(xié)議和經(jīng)典AODV協(xié)議進行了仿真分析與性能對比。通過仿真實驗可以看出，改進后的AODV協(xié)議相比較經(jīng)典的AODV協(xié)議，具有平均端到端時延小、丟包率小、路由開銷小、吞吐量大的特點，更加適合城市環(huán)境下的車載自組網(wǎng)。

［1］ Chang Cu－yu，Xiang Yong，Shi Mei－lin.Development and status of vehicular ad hoc networks［J］.Journal on Communications，2007，28（11）：116－126.（in Chinese）

［2］ Zhang Yang－xiang，Yi Yu－yan，Han Peng.Simulation study of the feasibility and routing protocol of VANET［J］.Experimental Technology and Management，2009，7（26）：81－83.（in Chinese）

［3］ Paul B，Ibrahim M，Bikas M A N.Experimental analysis of AODV ＆DSR over TCP ＆CBR connections with varying speed and node density in VANET［J］.International Journal of Computer Applications，2011，24（4）：1204－1206.

［4］ Ren Jie，Yuan Dao－h(huán)ua，Zeng Xiang－h(huán)ong，et.al.Research and implementation of location aided AODV routing protocol［J］.Computer Engineering and Applications，2008，44（32）：116－119.（in Chinese）

［5］ Karp B，Kung H T.GPSR：Greedy perimeter stateless routing for wireless networks［C］∥Proc of the 6th Annual International Conference on Mobile Computing and Networking（MobiCom 2000），2000：243－254.

附中文參考文獻：

［1］ 常促宇，向勇，史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展［J］.通信學(xué)報，2007，28（11）：116－126.

［2］ 張洋祥，易玉燕，韓鵬.VANET可行性及路由協(xié)議的仿真研究［J］.實驗技術(shù)與管理，2009，7（26）：81－83.

［4］ 任杰，袁道華，曾祥洪，等.基于位置輔助的AODV路由協(xié)議的研究與實現(xiàn)［J］.計算機工程與應(yīng)用，2008，44（32）：116－119.