蔡 菁，朱余兵

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）HELLO分組格式。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（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ù)流下的性能

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

5 結(jié)束語

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

附中文參考文獻(xiàn)：

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

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

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