吳衛(wèi)祖 劉利群 謝冬青

1(廣東海洋大學(xué)信息學(xué)院 廣東 湛江 524088) 2(廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院 廣東 廣州 510006)

?

基于道路段評(píng)價(jià)機(jī)制低延時(shí)VANETs路由算法

吳衛(wèi)祖1劉利群1謝冬青2

1(廣東海洋大學(xué)信息學(xué)院 廣東 湛江 524088)2(廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院 廣東 廣州 510006)

針對(duì)城市車(chē)輛自組織網(wǎng)絡(luò)應(yīng)用需求，提出一種低延時(shí)路由協(xié)議。該路由協(xié)議以城市交通網(wǎng)絡(luò)模型為基礎(chǔ)，首先從各道路段上尋找顯著節(jié)點(diǎn)，然后估計(jì)顯著節(jié)點(diǎn)之間的鏈路生存時(shí)間，接著從交叉口區(qū)域?qū)ふ易顑?yōu)的中繼節(jié)點(diǎn)。一旦找到中繼節(jié)點(diǎn)便開(kāi)始廣播道路段評(píng)價(jià)數(shù)據(jù)包，依據(jù)傳輸延時(shí)計(jì)算每一個(gè)道路段的權(quán)重值，最后在路由構(gòu)建階段依據(jù)道路段權(quán)重和有效期選取最優(yōu)傳輸路徑，實(shí)現(xiàn)數(shù)據(jù)的低延時(shí)傳輸。大量的仿真實(shí)驗(yàn)結(jié)果表明，與常用的GPSR和GPSR-R路由協(xié)議相比，該路由協(xié)議不僅端到端平均延時(shí)大幅降低，而且報(bào)文送達(dá)率高、網(wǎng)絡(luò)開(kāi)銷(xiāo)小。

車(chē)輛自組織網(wǎng)絡(luò) 路由協(xié)議 傳輸延時(shí) 鏈路生存時(shí)間 顯著節(jié)點(diǎn)

0 引 言

車(chē)輛自組織網(wǎng)絡(luò)VANETs是無(wú)線自組織網(wǎng)絡(luò)的一種，采用攜帶無(wú)線通信設(shè)備的車(chē)輛作為通信節(jié)點(diǎn)，組建自由、靈活的無(wú)線通信網(wǎng)絡(luò)[1]。目前城市交通環(huán)境中運(yùn)行的車(chē)輛非常多，大部分車(chē)輛裝配了無(wú)線通信和定位裝置，為車(chē)輛自組織網(wǎng)絡(luò)的構(gòu)建提供了便利條件。通過(guò)構(gòu)建車(chē)輛自組織網(wǎng)絡(luò)，可以為車(chē)輛駕駛員或乘客提供許多便捷服務(wù)(如媒體共享)[2～4]。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，車(chē)輛自組織網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛。在實(shí)際應(yīng)用過(guò)程中，許多應(yīng)用場(chǎng)合對(duì)數(shù)據(jù)傳輸延時(shí)提出了更高的要求，如網(wǎng)絡(luò)接入、媒體共享和廣告服務(wù)等應(yīng)用場(chǎng)合，用戶(hù)希望數(shù)據(jù)傳輸延時(shí)盡可能低[5]。然而，在城市交通網(wǎng)絡(luò)中，這些需求難以得到較好滿(mǎn)足。因?yàn)楣烙?jì)道路段上的車(chē)輛數(shù)量是非常復(fù)雜的，不同時(shí)段不同區(qū)域的車(chē)流密度變化很快，車(chē)輛在道路上的空間分布也不均勻，而且城市環(huán)境中障礙物也比較多，這些都會(huì)導(dǎo)致數(shù)據(jù)傳輸延時(shí)增加[6～8]。為了解決這些問(wèn)題，目前也提出了有意義的路由協(xié)議，如GPSR[9]、GSR[10]、GPSR-R[11]等路由協(xié)議通過(guò)選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的最短傳輸路徑來(lái)降低數(shù)據(jù)傳輸延時(shí)。然而，單純依靠距離最短準(zhǔn)則難以大幅降低數(shù)據(jù)傳輸延時(shí)，而且此類(lèi)準(zhǔn)則在選擇最優(yōu)路由時(shí)容易陷入局部最優(yōu)問(wèn)題。

為了進(jìn)一步降低面向城市車(chē)輛自組織網(wǎng)絡(luò)的數(shù)據(jù)傳輸延時(shí)，本文提出了一種基于道路段評(píng)價(jià)機(jī)制的低延時(shí)路由協(xié)議?；舅悸肥且罁?jù)數(shù)據(jù)傳輸延時(shí)對(duì)每一個(gè)道路段進(jìn)行評(píng)價(jià)，依據(jù)評(píng)價(jià)結(jié)果選擇數(shù)據(jù)傳輸延時(shí)小的道路段進(jìn)行數(shù)據(jù)傳輸，從而大幅降低數(shù)據(jù)傳輸?shù)亩说蕉搜訒r(shí)。

1 城市交通網(wǎng)絡(luò)模型

典型的城市交通環(huán)境常采用道路段和交叉口組成的網(wǎng)絡(luò)模型來(lái)模擬。每?jī)蓚€(gè)交叉口之間存在一個(gè)道路段，每一個(gè)道路段都包含道路長(zhǎng)度、道路寬度、車(chē)道數(shù)量、交通密度等特征。道路段上行駛的車(chē)輛組成網(wǎng)絡(luò)的通信節(jié)點(diǎn)。本文假定每一臺(tái)車(chē)輛都裝配了GPS定位裝置，可以提供車(chē)輛的位置、速度、方向以及一個(gè)包含道路段及交叉口等細(xì)節(jié)信息的數(shù)字地圖。在轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，源節(jié)點(diǎn)可以通過(guò)查詢(xún)定位服務(wù)去獲取目的節(jié)點(diǎn)的位置。

無(wú)線自組織網(wǎng)絡(luò)常采用無(wú)向圖模型G(V,E)來(lái)描述，其中，V表示無(wú)向圖模型中的頂點(diǎn)集合，也即網(wǎng)絡(luò)中的車(chē)輛節(jié)點(diǎn)。E表示無(wú)向圖模型中的邊的結(jié)合，也即兩臺(tái)車(chē)輛之間的無(wú)線通信鏈路。

P=Vi→V1→…→Vn→Vj

(1)

2 本文方法

本文方法的設(shè)計(jì)目標(biāo)是降低數(shù)據(jù)傳輸?shù)亩说蕉搜訒r(shí)，以便在車(chē)輛自組織網(wǎng)絡(luò)中快速傳輸數(shù)據(jù)，主要用于對(duì)延時(shí)比較敏感的場(chǎng)合，如網(wǎng)絡(luò)接入、媒體共享和廣告服務(wù)等。本文方法主要包括五個(gè)部分，分別是顯著節(jié)點(diǎn)生成、鏈路生存時(shí)間估計(jì)、中繼節(jié)點(diǎn)選擇、道路段評(píng)價(jià)和路由構(gòu)建，詳細(xì)描述如下。

2.1 顯著節(jié)點(diǎn)生成

每一條道路段可能存在很多車(chē)輛，這些車(chē)輛有些是在數(shù)據(jù)傳輸過(guò)程中作用重大的顯著車(chē)輛，有些是對(duì)數(shù)據(jù)傳輸作用不大的普通車(chē)輛。那么，我們需要尋找每一條道路段的顯著車(chē)輛，生成顯著節(jié)點(diǎn)。在這一過(guò)程中，車(chē)輛通過(guò)信標(biāo)服務(wù)交互信息，交互信息內(nèi)容為:

M=ID,x,y,v,θ,c,f

(2)

其中，ID為車(chē)輛的唯一標(biāo)識(shí)符，(x,y)表示車(chē)輛的位置坐標(biāo)，v表示車(chē)輛的速度，θ表示車(chē)輛的方向，c表示車(chē)輛的顯著屬性，如果車(chē)輛為顯著車(chē)輛，則c=1，否則c=0。f是一個(gè)穩(wěn)定因子，計(jì)算方式為:

(3)

其中，vn和dn分別表示當(dāng)前車(chē)輛的所有一跳鄰居車(chē)輛的平均速度和平均距離，R表示車(chē)輛的通信范圍。

在式(3)中，第一項(xiàng)反映了當(dāng)前車(chē)輛的一跳鄰居車(chē)輛與其相對(duì)速度值，該值越大，說(shuō)明當(dāng)前車(chē)輛的速度相對(duì)于其鄰居車(chē)輛的速度越小，這樣車(chē)輛在行駛過(guò)程中通信鏈路中斷的可能性越小，穩(wěn)定性越好。第二項(xiàng)反映了車(chē)輛的相對(duì)位置關(guān)系，當(dāng)前車(chē)輛與一跳鄰居車(chē)輛的相對(duì)距離越小，通信鏈路中斷的可能性越小。

當(dāng)車(chē)輛接收到信標(biāo)消息之后，建立一個(gè)一跳鄰居列表。列表的每一個(gè)入口包含了從信標(biāo)中獲取的信息。一旦發(fā)現(xiàn)一個(gè)新的鄰居，就增加一個(gè)新的入口。一臺(tái)車(chē)輛需要等待兩個(gè)連續(xù)的信標(biāo)間隔來(lái)監(jiān)聽(tīng)其鄰居。如果沒(méi)有接收到消息，將刪除對(duì)應(yīng)的鄰居入口。一旦建立了鄰居列表，每一個(gè)通信節(jié)點(diǎn)都要計(jì)算穩(wěn)定因子f，并與其鄰居節(jié)點(diǎn)的穩(wěn)定因子進(jìn)行比較。然后選取穩(wěn)定因子最大的節(jié)點(diǎn)作為顯著節(jié)點(diǎn)，并將對(duì)應(yīng)的顯著屬性c置為1。

2.2 鏈路生存時(shí)間估算

本節(jié)所述的鏈路生存時(shí)間是指兩個(gè)顯著節(jié)點(diǎn)之間的鏈路生存時(shí)間，估算該時(shí)間的目的是預(yù)測(cè)該鏈路發(fā)生中斷的時(shí)間。

令Vi(d)和Vj(d)表示兩個(gè)連續(xù)的顯著節(jié)點(diǎn)。首先，我們比較兩臺(tái)車(chē)輛的行駛方向，如果它們的行駛方向相同，則鏈路中斷會(huì)發(fā)生在兩者的距離超過(guò)車(chē)輛通信范圍R之后，因此，鏈路生存時(shí)間應(yīng)為:

(4)

其中，Di,j表示節(jié)點(diǎn)Vi(d)和Vj(d)之間的歐氏距離，也即:

(5)

如果節(jié)點(diǎn)Vi(d)和Vj(d)的行駛方向不同，則需要考慮兩種情況：

第一種情況是節(jié)點(diǎn)Vi(d)和Vj(d)相互接近。這樣，鏈路中斷發(fā)生在兩臺(tái)車(chē)輛相交叉且距離超過(guò)車(chē)輛通信范圍，此時(shí)鏈路的生存時(shí)間為:

(6)

第二種情況是節(jié)點(diǎn)Vi(d)和Vj(d)背向行駛，越離越遠(yuǎn)。這種情況下，鏈路中斷發(fā)生在兩臺(tái)車(chē)輛的相對(duì)距離超過(guò)車(chē)輛通信范圍，此時(shí)鏈路的生存時(shí)間為:

(7)

需要說(shuō)明的是，鏈路的生存時(shí)間也存儲(chǔ)在車(chē)輛的鄰居列表中，在每一次信標(biāo)服務(wù)過(guò)程中計(jì)算和更新。

2.3 中繼節(jié)點(diǎn)選擇

前面所述的顯著節(jié)點(diǎn)都定義在道路段上，而不同道路段上的顯著節(jié)點(diǎn)之間無(wú)法連通。為了連通這些節(jié)點(diǎn)，本文在兩道路段的交叉口定義一個(gè)中繼節(jié)點(diǎn)。中繼節(jié)點(diǎn)的選擇方法是：

Step1尋找道路段交叉口區(qū)域的所有車(chē)輛，將其作為候選的中繼節(jié)點(diǎn)；

Step2剔除那些已經(jīng)駛過(guò)交叉口中心的車(chē)輛，因?yàn)檫@些車(chē)輛即將離開(kāi)交叉口，不適合作為中繼節(jié)點(diǎn)；

Step3從剩余節(jié)點(diǎn)中篩選出顯著屬性為1的節(jié)點(diǎn)，如果沒(méi)有，則保留所有剩余節(jié)點(diǎn)；

Step4從余下的節(jié)點(diǎn)中選擇行駛速度最慢的節(jié)點(diǎn)，因?yàn)樗俣仍铰墓?jié)點(diǎn)在交叉口停留的時(shí)間越長(zhǎng)。

當(dāng)一個(gè)中繼節(jié)點(diǎn)即將離開(kāi)交叉口區(qū)域時(shí)，需要為其尋找一個(gè)替代者。方法是：

首先，計(jì)算每一個(gè)與當(dāng)前中繼節(jié)點(diǎn)相鄰的顯著節(jié)點(diǎn)通過(guò)交叉區(qū)域的時(shí)間t1；

然后，計(jì)算當(dāng)前綠燈的剩余時(shí)間t2，表示為:

t2=tg-[tα%tC-(tC-tg)]

(8)

其中，tα表示車(chē)輛到達(dá)紅綠燈的時(shí)間，tg表示綠燈持續(xù)時(shí)間，tC表示綠燈的循環(huán)間隔。“%”表示整除運(yùn)算。

如果t2>t1，我們選取t1最大的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。否則，我們?cè)诩t燈亮?xí)r從顯著節(jié)點(diǎn)集合中已經(jīng)停止的車(chē)輛中選取一個(gè)距離交叉區(qū)域邊界最近的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。

2.4 道路段評(píng)價(jià)

在交叉口區(qū)域，一旦選定了中繼節(jié)點(diǎn)，就開(kāi)始進(jìn)行道路段評(píng)價(jià)。道路段評(píng)價(jià)是后續(xù)路由構(gòu)建的依據(jù)，用于評(píng)價(jià)該道路段作為路由路徑的優(yōu)先級(jí)。道路段評(píng)價(jià)的方法是：

首先，在中繼節(jié)點(diǎn)處建立路由表，便于數(shù)據(jù)轉(zhuǎn)發(fā)。

然后，中繼節(jié)點(diǎn)生成一個(gè)道路評(píng)價(jià)數(shù)據(jù)包并在所有道路段上進(jìn)行廣播。道路評(píng)價(jià)數(shù)據(jù)包用于收集道路段的相關(guān)信息，如數(shù)據(jù)包延時(shí)和跳數(shù)量，數(shù)據(jù)包格式如圖1所示。

圖1 道路評(píng)價(jià)數(shù)據(jù)包格式

在圖1中，時(shí)間戳指明了道路評(píng)價(jià)數(shù)據(jù)包的創(chuàng)建時(shí)間，delay表示數(shù)據(jù)包延時(shí)，具體為:

(9)

其中，n為一個(gè)道路段上的顯著節(jié)點(diǎn)數(shù)量，delayVi表示第i個(gè)顯著節(jié)點(diǎn)vi的數(shù)據(jù)包延時(shí)。

每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)包延時(shí)都包含兩個(gè)部分，一是數(shù)據(jù)的傳輸延時(shí)，二是隊(duì)列延時(shí)。

當(dāng)某一個(gè)顯著節(jié)點(diǎn)接收到道路評(píng)價(jià)數(shù)據(jù)包之后，它對(duì)道路評(píng)價(jià)數(shù)據(jù)包進(jìn)行修改，修改內(nèi)容包括兩個(gè)部分，一是在跳數(shù)量子項(xiàng)中加入該節(jié)點(diǎn)，二是更新數(shù)據(jù)包延時(shí)，即在原有延時(shí)的基礎(chǔ)上增加該節(jié)點(diǎn)的數(shù)據(jù)包延時(shí)。更新之后，再將道路評(píng)價(jià)數(shù)據(jù)包轉(zhuǎn)發(fā)給下一個(gè)顯著節(jié)點(diǎn)，直至到達(dá)下一個(gè)中繼節(jié)點(diǎn)。

中繼節(jié)點(diǎn)在接收到道路評(píng)價(jià)數(shù)據(jù)包之后，計(jì)算道路評(píng)價(jià)數(shù)據(jù)包的傳輸延時(shí)t3，計(jì)算方法是用該中繼節(jié)點(diǎn)接收到道路評(píng)價(jià)數(shù)據(jù)包的時(shí)間減去道路評(píng)價(jià)數(shù)據(jù)包上的時(shí)間戳。

記道路評(píng)價(jià)數(shù)據(jù)包的傳輸延時(shí)上限和下限分別為T(mén)up和Tdown。對(duì)于一個(gè)長(zhǎng)度為L(zhǎng)的道路段，其可以容納的最大顯著節(jié)點(diǎn)數(shù)量為:

(10)

其中，Int()表示取整數(shù)運(yùn)算。

那么，數(shù)據(jù)包延時(shí)下限Tdown可以表示為:

(11)

其中，Tt表示節(jié)點(diǎn)的傳輸延時(shí)。

數(shù)據(jù)包傳送延時(shí)上限Tup可以表示為:

Tup=Tdown-t1

(12)

如果t3Tup，中繼節(jié)點(diǎn)可以認(rèn)定該道路段已經(jīng)完全無(wú)法連接。基于這一思路，中繼節(jié)點(diǎn)為不同的道路段分配不同的權(quán)重，第i個(gè)道路段的權(quán)重可以表示為:

(13)其中，t4表示該道路段的平均車(chē)輛通過(guò)時(shí)間，可以由該道路段的長(zhǎng)度除以該道路段上所有車(chē)輛的平均速度計(jì)算。

考慮到權(quán)重與延時(shí)相關(guān)，需要為其計(jì)算一個(gè)有效期，用于描述該權(quán)重是否有效。第i個(gè)道路段權(quán)重的有效期可以由該道路段上所有鏈路的最小生存時(shí)間來(lái)表示，即:

Validi=min(lf1,lf2,…,lfk)

(14)

其中，k為該道路段上的鏈路數(shù)量。

在得到所有道路段的權(quán)重之后，每一個(gè)中繼節(jié)點(diǎn)構(gòu)建一個(gè)路由表，用于后續(xù)的路由構(gòu)建。

2.5 路由構(gòu)建

當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)時(shí)，它生成一個(gè)路由請(qǐng)求數(shù)據(jù)包，該數(shù)據(jù)包一般包含源節(jié)點(diǎn)ID、目的節(jié)點(diǎn)ID和目的節(jié)點(diǎn)位置。源節(jié)點(diǎn)轉(zhuǎn)發(fā)該路由請(qǐng)求包給其所在道路段上的所有中繼節(jié)點(diǎn)。對(duì)于每一個(gè)中繼節(jié)點(diǎn)，當(dāng)其接收到源節(jié)點(diǎn)發(fā)送的路由請(qǐng)求包之后，首先檢查其路由表，查看該中繼節(jié)點(diǎn)是否可以將數(shù)據(jù)送達(dá)目的節(jié)點(diǎn)，如果可以，它將從其路由表中選擇一個(gè)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的權(quán)重最大的路徑，將路由請(qǐng)求數(shù)據(jù)包轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。

路由路徑的權(quán)重可以表示為:

(15)

其中，m為該路徑所經(jīng)過(guò)的道路段數(shù)量，Wi表示第i個(gè)道路段的權(quán)重，依據(jù)式(13)計(jì)算。路徑上所有道路段的權(quán)重之和越大，數(shù)據(jù)傳輸?shù)亩说蕉搜訒r(shí)越小。

由于中繼節(jié)點(diǎn)不止一個(gè)，因此目的節(jié)點(diǎn)可能接收到多個(gè)路由請(qǐng)求數(shù)據(jù)包，也即存在多條數(shù)據(jù)傳輸路徑。這種情況下，目的節(jié)點(diǎn)將所有路徑存儲(chǔ)在路由表中，同時(shí)存儲(chǔ)路徑所對(duì)應(yīng)的有效期，路徑有效期的計(jì)算公式為:

(16)

其中，Validi表示第i個(gè)道路段權(quán)重的有效期，依據(jù)式(14)計(jì)算。

然后，目的節(jié)點(diǎn)選擇權(quán)重最大的路徑，將其放進(jìn)路由應(yīng)答數(shù)據(jù)包，回傳給源節(jié)點(diǎn)。當(dāng)源節(jié)點(diǎn)收到路由應(yīng)答數(shù)據(jù)包之后，即可開(kāi)始發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)。

在數(shù)據(jù)發(fā)送過(guò)程中，中繼節(jié)點(diǎn)在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中更新傳輸路徑的權(quán)重，路徑權(quán)重會(huì)逐漸降低，當(dāng)路由的有效期結(jié)束或者路徑的權(quán)重低于閾值WT時(shí)，源節(jié)點(diǎn)重新發(fā)起路由請(qǐng)求，建立新的路由。

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

車(chē)輛自組織網(wǎng)絡(luò)常用的仿真軟件是Network Simulator[12]軟件，本文在該軟件上仿真本文路由協(xié)議和常用的GPSR、GPSR-R路由協(xié)議，測(cè)試常用的端到端平均延時(shí)、報(bào)文送達(dá)率和網(wǎng)絡(luò)開(kāi)銷(xiāo)三個(gè)指標(biāo)[13]，依據(jù)這三個(gè)指標(biāo)評(píng)測(cè)三種路由協(xié)議的性能，仿真軟件的相關(guān)參數(shù)見(jiàn)表1所示。下面首先分析本文路由協(xié)議的參數(shù)取值，然后再對(duì)比不同路由協(xié)議的性能指標(biāo)。

表1 仿真軟件相關(guān)參數(shù)

3.1 參數(shù)分析

本文路由協(xié)議涉及一個(gè)閾值參數(shù)，為權(quán)重閾值WT。當(dāng)該參數(shù)取值不同時(shí)，數(shù)據(jù)傳輸?shù)亩说蕉似骄訒r(shí)是不同的。圖2給出了本文路由協(xié)議的端到端平均延時(shí)隨權(quán)重閾值WT的變化曲線，其中數(shù)據(jù)包產(chǎn)生速率為5個(gè)/s。

圖2 端到端平均延時(shí)隨權(quán)重閾值的變化曲線

由圖2可見(jiàn)，權(quán)重閾值WT太小或者太大時(shí)都會(huì)導(dǎo)致端到端平均延時(shí)增加。因?yàn)闄?quán)重閾值WT太大時(shí)，在數(shù)據(jù)傳輸過(guò)程中路由路徑的權(quán)重會(huì)很快下降到權(quán)重閾值WT之下，這樣就需要重新發(fā)起路由請(qǐng)求，盡管數(shù)據(jù)在路由路徑上的傳輸延時(shí)較小，但由于頻繁構(gòu)建路由，導(dǎo)致整體的端到端平均延時(shí)增大。而當(dāng)權(quán)重閾值WT太小時(shí)，盡管路由請(qǐng)求次數(shù)較少，但是，在數(shù)據(jù)傳輸過(guò)程中路由路徑上的權(quán)重越來(lái)越小，導(dǎo)致數(shù)據(jù)傳輸延時(shí)越來(lái)越大，從而也會(huì)導(dǎo)致整體的端到端平均延時(shí)增大。由圖2可見(jiàn)，當(dāng)WT=120(ms)時(shí)，數(shù)據(jù)傳輸?shù)亩说蕉似骄訒r(shí)最小。因此，本文取權(quán)重閾值WT=120(ms)。

3.2 性能對(duì)比

本文路由協(xié)議的設(shè)計(jì)目標(biāo)是盡可能降低數(shù)據(jù)傳輸?shù)亩说蕉似骄訒r(shí)，用于服務(wù)媒體共享、廣告接入等低延時(shí)需求的應(yīng)用。因此，本文路由性能最關(guān)注的性能指標(biāo)是數(shù)據(jù)傳輸?shù)亩说蕉似骄訒r(shí)。但同時(shí)，報(bào)文送達(dá)率和網(wǎng)絡(luò)開(kāi)銷(xiāo)也是車(chē)輛自組織網(wǎng)絡(luò)服務(wù)質(zhì)量的重要評(píng)價(jià)指標(biāo)。因此，這里對(duì)這三項(xiàng)指標(biāo)分別進(jìn)行評(píng)價(jià)(如圖3-圖5所示)，然后給出綜合評(píng)價(jià)結(jié)果。

圖3 端到端平均延時(shí)隨數(shù)據(jù)包產(chǎn)生速率的變化曲線

圖3給出了數(shù)據(jù)包產(chǎn)生速率不同時(shí)三種路由協(xié)議的端到端平均延時(shí)指標(biāo)?？梢?jiàn)，盡管本文路由協(xié)議的端到端平均延時(shí)指標(biāo)也會(huì)像其他兩種方法一樣隨著數(shù)據(jù)包產(chǎn)生速率的增加而增加。但是很明顯本文路由協(xié)議的端到端平均延時(shí)指標(biāo)隨著數(shù)據(jù)包產(chǎn)生速率增加的上升速率較低，而且在同等條件下的端到端平均延時(shí)都遠(yuǎn)小于其他兩種路由協(xié)議。這是因?yàn)楸疚穆酚蓞f(xié)議以路由路徑的傳輸延時(shí)最小(也即路由路徑的權(quán)重最大)為路由選擇依據(jù)，因此本文路由協(xié)議的端到端傳輸延時(shí)要明顯小于其他兩種路由協(xié)議。

圖4 報(bào)文送達(dá)率隨數(shù)據(jù)包產(chǎn)生速率的變化曲線

圖4給出了三種路由協(xié)議的報(bào)文送達(dá)率指標(biāo)隨數(shù)據(jù)包產(chǎn)生速率的變化曲線，可見(jiàn)在同等條件下本文路由協(xié)議的報(bào)文送達(dá)率指標(biāo)也高于其他兩種路由協(xié)議。這是因?yàn)楸疚穆酚蓞f(xié)議在各道路段有效期結(jié)束后會(huì)重新構(gòu)建路由，路由穩(wěn)定性好。因此在大幅降低端到端平均延時(shí)的情況下，還能夠提高報(bào)文送達(dá)率指標(biāo)。

圖5 路由開(kāi)銷(xiāo)隨數(shù)據(jù)包產(chǎn)生速率的變化曲線

圖5給出了三種路由協(xié)議的路由開(kāi)銷(xiāo)指標(biāo)隨數(shù)據(jù)包產(chǎn)生速率的變化曲線。同樣，相同條件下本文路由協(xié)議的路由開(kāi)銷(xiāo)要小于其他兩種路由協(xié)議，數(shù)據(jù)包產(chǎn)生速率越大，本文路由協(xié)議的優(yōu)勢(shì)越明顯。這是因?yàn)楸疚穆酚蓞f(xié)議在數(shù)據(jù)傳輸過(guò)程中路由請(qǐng)求次數(shù)較少，路由穩(wěn)定性較好。

綜合分析端到端平均延時(shí)、報(bào)文送達(dá)率和路由開(kāi)銷(xiāo)三個(gè)指標(biāo)，本文路由協(xié)議在大幅降低端到端平均延時(shí)的情況下，路由開(kāi)銷(xiāo)也隨之降低，報(bào)文送達(dá)率指標(biāo)也有提高，優(yōu)于其他兩種常用的車(chē)輛自組織網(wǎng)絡(luò)路由協(xié)議。

4 結(jié) 語(yǔ)

針對(duì)城市交通場(chǎng)景下網(wǎng)絡(luò)接入、媒體共享和廣告服務(wù)等對(duì)延時(shí)比較敏感的應(yīng)用場(chǎng)合，本文提出了一種基于道路段評(píng)價(jià)機(jī)制的車(chē)輛自組織網(wǎng)絡(luò)路由協(xié)議。該協(xié)議通過(guò)顯著節(jié)點(diǎn)生成、鏈路生存時(shí)間估計(jì)、中繼節(jié)點(diǎn)選擇、道路段評(píng)價(jià)和路由構(gòu)建五個(gè)階段，實(shí)現(xiàn)低延時(shí)路由的構(gòu)建。實(shí)驗(yàn)表明，本文提出的路由協(xié)議可以大幅降低數(shù)據(jù)傳輸?shù)亩说蕉搜訒r(shí)，同時(shí)路由開(kāi)銷(xiāo)小、報(bào)文送達(dá)率高，是一種低延時(shí)的城市車(chē)輛自組織網(wǎng)絡(luò)路由協(xié)議。

[1] 吳怡, 沈穎祺, 沈連豐,等. 基于協(xié)議序列的車(chē)輛自組織網(wǎng)絡(luò)信道接入控制算法[J].電子學(xué)報(bào), 2012, 40(4):826-831.

[2] Wang S S, Lin Y S. PassCAR: A passive clustering aided routing protocol for vehicular ad hoc networks[J]. Computer Communications, 2013, 36(2):170-179.

[3] 姚宏, 滕超, 叢磊,等. 車(chē)輛自組織網(wǎng)絡(luò)中使用公交車(chē)輛協(xié)助的數(shù)據(jù)分發(fā)[J]. 計(jì)算機(jī)工程與科學(xué), 2014, 36(11):2114-2118.

[4] Li Y, Boukerche A. QuGu: A Quality Guaranteed Video Dissemination Protocol Over Urban Vehicular Ad Hoc Networks[J].Acm Transactions on Multimedia Computing Communications & Applications, 2015,11(4):1-23.

[5] Campolo C, Molinaro A. Multi-channel communications in Vehicular Ad hoc NETworks: A Survey[J].IEEE Communications Magazine, 2013,51(5):158-169.

[6] Dua A, Kumar N, Bawa S. A systematic review on routing protocols for Vehicular Ad Hoc Networks[J]. Vehicular Communications, 2014,1(1):33-52.

[7] Li Y, Jin D, Hui P, et al. Revealing contact interval patterns in large scale urban vehicular ad hoc networks[J].Acm Sigcomm Computer Communication Review, 2012,42(4):299-300.

[8] Villas L A, Boukerche A, Maia G, et al. DRIVE: An efficient and robust data dissemination protocol for highway and urban vehicular ad hoc networks[J].Computer Networks, 2014,75:381-394.

[9] Ding X T, Peng X G. An energy balancing routing based on GPSR protocol[J]. Transducer & Microsystem Technologies, 2013,32(4):12-15.

[10] Behera A, Panigrahi A. Determining the network throughput and flow rate using GSR And AAL2R[J]. International Journal of Oncology, 2015, 43(2):661-669.

[11] 李超, 韓江洪, 魏振春,等. VANET 場(chǎng)景下的 GPSR-R 路由算法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版, 2015(2):181-185.

[12] The Network Simulator-ns-2[EB/OL]. 2011. http://www.isi.edu/nsnam/ns/.

[13] Daraghmi Y A, Yi C W, Stojmenovic I. Forwarding methods in data dissemination and routing protocols for vehicular Ad Hoc networks[J].IEEE Network, 2013,27(27):74-79.

ALOW-DELAYROUTINGALGORITHMFORVANETSBASEDONROAD-SECTIONEVALUATIONMECHANISM

Wu Weizu1Liu Liqun1Xie Dongqing2
1(SchoolofInformation,GuangdongOceanUniversity,Zhanjiang524088,Guangdong,China)2(SchoolofComputerScienceandEducationSoftware,GuangzhouUniversity，Guangzhou510006,Guangdong,China)

A low-delay routing protocol is proposed for application demand of city vehicle ad hoc networks. Based on the model of city traffic network, the new routing protocol look for the significant nodes on each road-section firstly, then it estimated the lifetime of links between two significant nodes, and found the optimal relay nodes on intersection. Once finding the relay node, the algorithm will begin broadcasting the road-section evaluation packet and calculate a weight value for every road-section according to transmission delay. In the end, it selects the optimal transmission path according to weight and validity of road-sections in routing building stage and achieve low-delay transmission for data. Experiments show that the new routing protocol can not only reduce the average end-to-end transmission delay significantly, but also obtain high packet delivery rate and low network overhead compared with the commonly used GPSR and GPSR-R routing protocols.

Vehicle ad hoc networks Routing protocol Transmission delay Link lifetime Significant node

2016-08-16。國(guó)家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2009AA012420)；廣東省科技計(jì)劃項(xiàng)目(2014A020218016)。吳衛(wèi)祖，副教授，主研領(lǐng)域：信息系統(tǒng)，網(wǎng)絡(luò)安全，物聯(lián)網(wǎng)，北斗通信及應(yīng)用。劉利群，副教授。謝冬青，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.08.048