陳遠(yuǎn)龍，葛劍飛，劉南杰，趙海濤

（1.南京郵電大學(xué)通信與信息工程學(xué)院 南京 210003；

2.南京郵電大學(xué)網(wǎng)絡(luò)基因工程研究所

南京 210003；3.國家電網(wǎng)上海市電力公司信息通信公司 上海 200122）

1 引言

車載自組織網(wǎng)絡(luò) （vehicular Ad Hoc network，VANET）是指道路上車輛間、車輛與固定接入點(diǎn)之間相互通信組成的開放移動Ad Hoc網(wǎng)絡(luò)，可以實(shí)現(xiàn)事故告警、輔助駕駛、道路交通信息查詢和Internet信息服務(wù)等應(yīng)用[1]。VANET中節(jié)點(diǎn)移動快、網(wǎng)絡(luò)拓?fù)渥兓杆?、車輛節(jié)點(diǎn)進(jìn)出頻繁以及車輛節(jié)點(diǎn)因緊急情況可能發(fā)生大量聚集等特點(diǎn)[2]，使得基于拓?fù)涞穆酚蓞f(xié)議[3,4]性能大大降低，而城市環(huán)境下，VANET中節(jié)點(diǎn)的移動軌跡受道路布局限制，并且通過GPS以及電子地圖等可以很方便地獲得車輛的位置和速度等信息，所以使得基于地理位置的路由協(xié)議[5～7]更適合VANET。本文將重點(diǎn)介紹VANET中的一種城市環(huán)境下的地理路由（reactivemode of road-based using vehicular traffic routing，RBVT-R[6]）協(xié)議，并針對該協(xié)議在路由建立及分組轉(zhuǎn)發(fā)模式上的缺陷，提出改進(jìn)策略，以提升RBVT-R協(xié)議在分組交付率和端到端平均時延等方面的性能。

2 現(xiàn)有RBVT-R協(xié)議

RBVT-R協(xié)議是一種城市環(huán)境下基于實(shí)時路況信息的反應(yīng)式地理路由協(xié)議。當(dāng)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時，要先尋找路由，建立數(shù)據(jù)分組的傳輸路徑。與錨路由機(jī)制[8]類似，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間建立的路由是數(shù)據(jù)分組傳輸所需經(jīng)過的所有道路交叉口組成的序列。RBVT-R協(xié)議的路由建立過程包括路由發(fā)現(xiàn)和路由回復(fù)兩個步驟，如圖1所示，具體流程如下。

（1）源節(jié)點(diǎn)產(chǎn)生一個 RD（route discovery，路由發(fā)現(xiàn)）分組，該分組的頭部包含源節(jié)點(diǎn)的名稱和位置信息、目的節(jié)點(diǎn)的名稱。因?yàn)槟康墓?jié)點(diǎn)不在源節(jié)點(diǎn)的傳輸范圍內(nèi)，所以RD分組的頭部不包含目的節(jié)點(diǎn)的位置信息。

（2）從源節(jié)點(diǎn)開始，各中間節(jié)點(diǎn)在其傳輸范圍內(nèi)依次通過改進(jìn)的洪泛機(jī)制[9]廣播該RD分組，即當(dāng)一個中間節(jié)點(diǎn)收到上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送的RD分組后，它不會立刻轉(zhuǎn)發(fā)該分組，而是等待一段時間，當(dāng)?shù)却龝r間結(jié)束，且在同一路段上沒有其他離上一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)更遠(yuǎn)的節(jié)點(diǎn)轉(zhuǎn)發(fā)該RD分組時，該中間節(jié)點(diǎn)才轉(zhuǎn)發(fā)此RD分組，如圖1（a）所示。當(dāng)RD分組經(jīng)過一個路口時，會將該路口的信息加入到RD分組的頭部。此洪泛過程重復(fù)進(jìn)行，直到RD分組達(dá)目的節(jié)點(diǎn)。

（3）當(dāng)目的節(jié)點(diǎn)接收到RD分組后，按RD分組頭部的路口序列信息，原路返回一個RR（route reply，路由回復(fù)）分組。當(dāng)源節(jié)點(diǎn)接收到RR分組后，則路由建立成功。如圖 1(b)所示，建立的路由為：I1-I6-I7-I4-I5-I8。

當(dāng)路由成功建立之后，源節(jié)點(diǎn)就開始向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。此時數(shù)據(jù)分組是按照建立的路口序列的順序依次進(jìn)行轉(zhuǎn)發(fā)。在相鄰兩個路口的一個路段上，數(shù)據(jù)分組的轉(zhuǎn)發(fā)采用改進(jìn)的地理路由機(jī)制，即每次都選擇傳輸范圍內(nèi)，距離下一個目標(biāo)路口最近的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。

圖1 RBVT-R協(xié)議的路由建立過程

3 RBVT-R協(xié)議的改進(jìn)

雖然RBVT-R協(xié)議采用改進(jìn)的洪泛機(jī)制建立路由，并且通過改進(jìn)的地理轉(zhuǎn)發(fā)機(jī)制轉(zhuǎn)發(fā)數(shù)據(jù)分組，使得路由性能在一定程度上得到了改進(jìn)，但是該路由協(xié)議也存在一些問題，主要包括以下兩方面。

·雖然RBVT-R協(xié)議在路由建立過程中采用了改進(jìn)的洪泛機(jī)制，能在一定程度上解決廣播風(fēng)暴問題，但是該機(jī)制在路由發(fā)現(xiàn)過程中沒有考慮到道路車輛密度對分組傳輸?shù)挠绊懀沟媒⒌穆酚煞€(wěn)定性不高，容易發(fā)生數(shù)據(jù)分組傳輸時延大，甚至分組丟失等情況。

·RBVT-R協(xié)議在相鄰兩個路口之間轉(zhuǎn)發(fā)數(shù)據(jù)分組時，當(dāng)前攜帶分組的節(jié)點(diǎn)選擇的是其傳輸范圍內(nèi)距離下一個目標(biāo)路口最近的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，這種轉(zhuǎn)發(fā)方式?jīng)]有考慮到車輛行駛方向和數(shù)據(jù)分組的轉(zhuǎn)發(fā)方向 （即數(shù)據(jù)分組到下一個路口的指向）之間的關(guān)系，有可能會導(dǎo)致分組在同一路段上反復(fù)傳輸，增加分組傳輸?shù)臅r延。

根據(jù)RBVT-R協(xié)議中存在的問題，提出了一種改進(jìn)算法。該算法包括兩個部分，分別是對路由建立過程的改進(jìn)和對數(shù)據(jù)分組傳輸過程的改進(jìn)。

3.1 路由建立過程的改進(jìn)

針對RBVT-R協(xié)議在路由發(fā)現(xiàn)過程中，其改進(jìn)的洪泛機(jī)制沒有考慮到道路車輛密度對路由穩(wěn)定性影響的問題，在改進(jìn)的算法中提出了一種逐段式道路車輛密度自主估算方法，并將估算出的道路車輛密度用于改善路由發(fā)現(xiàn)過程中的洪泛機(jī)制。

3.1.1 逐段式道路車輛密度自主估算方法

如圖2所示，在一個路段上，當(dāng)前的分組轉(zhuǎn)發(fā)節(jié)點(diǎn)為ni，下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)為nj，根據(jù)當(dāng)前兩個節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的數(shù)量以及它們之間的距離，估算這兩個節(jié)點(diǎn)所在區(qū)域一跳范圍內(nèi)的路段的車輛密度，計(jì)算式如下：

其中，Nij=Ni∪Nj是兩個節(jié)點(diǎn) ni和 nj的鄰居節(jié)點(diǎn)的總數(shù)，它不是鄰居節(jié)點(diǎn)數(shù)的單純相加，因?yàn)楣?jié)點(diǎn)ni和nj互為鄰居節(jié)點(diǎn)，它們之間存在共同鄰居節(jié)點(diǎn)，如圖2中三角形節(jié)點(diǎn)所示，Nij對共同的鄰居節(jié)點(diǎn)只添加一次；dij是節(jié)點(diǎn)ni和nj之間的距離，R是無線傳輸半徑。2R是因?yàn)闊o線信號是全方位傳播的，因此其鄰居節(jié)點(diǎn)分布也是全方位的。

3.1.2 RBVT-R協(xié)議洪泛機(jī)制的改進(jìn)

在RBVT-R協(xié)議采用的改進(jìn)洪泛機(jī)制中，中間節(jié)點(diǎn)在收到RD分組后會等待一段時間，直到等待時間結(jié)束才進(jìn)行判斷，決定是否轉(zhuǎn)發(fā)該RD分組，等待時間的計(jì)算如式（2）所示：

其中，dmin=min{d,Range}，d是RD分組的接收節(jié)點(diǎn)與發(fā)送節(jié)點(diǎn)之間的距離，Range是無線傳輸范圍，MaxWT是最大等待時間。

但是，這個改進(jìn)洪泛機(jī)制只考慮了RD分組接收節(jié)點(diǎn)和發(fā)送節(jié)點(diǎn)之間的距離，沒有考慮到兩節(jié)點(diǎn)所在區(qū)域一跳范圍內(nèi)的車輛密度，本質(zhì)上還是一種貪婪轉(zhuǎn)發(fā)策略，因此存在頻繁發(fā)生局部最大的問題。針對這個問題，下面結(jié)合自主獲取的道路車輛密度對此等待函數(shù)進(jìn)行了改進(jìn)。

通過GPS獲得RD分組發(fā)送節(jié)點(diǎn)ni和接收節(jié)點(diǎn)nj之間的距離dij，根據(jù)式（1）獲得兩個節(jié)點(diǎn)之間的道路車輛密度ρij。根據(jù)參考文獻(xiàn)[10]中的多標(biāo)準(zhǔn)映射函數(shù)，可以得到包含距離和車輛密度這兩個參數(shù)的等待函數(shù)計(jì)算式：

3.2 數(shù)據(jù)分組傳輸過程的改進(jìn)

當(dāng)路由成功建立之后，源節(jié)點(diǎn)開始向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，此時它會把建立的路口序列保存到數(shù)據(jù)分組的頭部，數(shù)據(jù)分組就按照這個序列進(jìn)行轉(zhuǎn)發(fā)。分組從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)過程實(shí)質(zhì)上就是按照建立的路口序列中的路口順序，從一個路口轉(zhuǎn)發(fā)到下一個路口，不斷重復(fù)直到到達(dá)目的節(jié)點(diǎn)。

針對RBVT-R協(xié)議中數(shù)據(jù)分組在同一路段反復(fù)傳輸?shù)膯栴}，在改進(jìn)的算法中提出了一種基于方向和位置預(yù)測的分組轉(zhuǎn)發(fā)方法。該方法需要考慮車輛節(jié)點(diǎn)之間鏈路的有效持續(xù)時間并比較各個節(jié)點(diǎn)的轉(zhuǎn)發(fā)優(yōu)先權(quán)值，下面首先分析了上述兩個內(nèi)容，然后在此基礎(chǔ)上提出了基于方向和位置的分組轉(zhuǎn)發(fā)方法的完整方案。

3.2.1 鏈路有效持續(xù)時間

車輛之間相對方向關(guān)系有：同向行駛（其中同向行駛根據(jù)前后車輛的車速大小還分為趕超和落后兩種情況，分別如圖3、圖4所示），相向行駛?cè)鐖D5所示，背向行駛?cè)鐖D6所示。上述4種情況下，車輛之間的鏈路有效持續(xù)時間分別如式（4）～式（7）所示。

同向行駛（趕超）：

同向行駛（落后）：

相向行駛：

圖3 車輛A趕超車輛B的相對位置關(guān)系

圖4 車輛B逐漸遠(yuǎn)離車輛A的相對位置關(guān)系

圖5 A、B相向行駛的相對位置關(guān)系

圖6 A、B背向行駛的相對位置關(guān)系

背向行駛：

其中，VA、VB分別為節(jié)點(diǎn) A和 B的行駛速度，R為節(jié)點(diǎn)的傳輸半徑，dAB為節(jié)點(diǎn)A和B之間的相對距離。由以上式子可以看到，同向運(yùn)行的車輛節(jié)點(diǎn)之間的鏈路有效時間是最長的，因此在路由選擇過程中應(yīng)首先考慮在同向車輛中選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，這樣可以選擇更加穩(wěn)定的路徑，提高路由協(xié)議的性能。

3.2.2 節(jié)點(diǎn)轉(zhuǎn)發(fā)優(yōu)先權(quán)值計(jì)算

假設(shè)，當(dāng)前攜帶數(shù)據(jù)分組的節(jié)點(diǎn)為S，待選的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)為A。首先，根據(jù)節(jié)點(diǎn)S與A之間的相對關(guān)系，選擇對應(yīng)的鏈路有效持續(xù)時間計(jì)算公式計(jì)算lifetimeSA；然后，采用式（8）預(yù)測經(jīng)過Δt時間后節(jié)點(diǎn)A的位置：

其中，(xA,yA)為節(jié)點(diǎn)A的當(dāng)前位置，(vAx,vAy)為A的速度，(xA′,yA′)為經(jīng)過 Δt時間后節(jié)點(diǎn) A 的位置。

通過地圖獲得下一個將要到達(dá)的路口Ii的位置(xIi,yIi)，節(jié)點(diǎn)A在經(jīng)過Δt時間后與路口Ii之間的距離DAIi為：

根據(jù)鏈路有效持續(xù)時間lifetimeSA以及節(jié)點(diǎn)A經(jīng)過Δt時間后與下一個路口Ii的距離DAIi，計(jì)算節(jié)點(diǎn)A的優(yōu)先轉(zhuǎn)發(fā)權(quán)值為：

其中，MaxLifetime是文中設(shè)定的一個鏈路時間的上限值，用來約束在車輛同向行駛且速度很相近的情況下，鏈路時間無限大的情況，lifetimeSA不能超過該上限值；Dp=DAIi/DSIi代表了待選節(jié)點(diǎn)A距離目標(biāo)路口的遠(yuǎn)近程度，其中DSIi為節(jié)點(diǎn)S到目標(biāo)路口Ii的距離，Dp越小代表A在經(jīng)過時間Δt后距離路口Ii越近；α、β分別是鏈路有效持續(xù)時間和節(jié)點(diǎn)A到路口距離的加權(quán)值，且α+β=1，它們的取值大小代表了各參數(shù)對計(jì)算結(jié)果的影響程度，根據(jù)節(jié)點(diǎn)運(yùn)動方向和分組轉(zhuǎn)發(fā)方向之間的關(guān)系不同，α、β的取值也不同。

3.2.3 基于方向和位置預(yù)測的分組轉(zhuǎn)發(fā)

通過前面的分析，下面提出一種基于方向和位置預(yù)測的分組轉(zhuǎn)發(fā)方案，具體的分組轉(zhuǎn)發(fā)過程如下。

（1）攜帶數(shù)據(jù)分組的節(jié)點(diǎn)S在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時，首先根據(jù)鄰居列表中鄰居節(jié)點(diǎn)的位置判斷在分組轉(zhuǎn)發(fā)方向上是否有可轉(zhuǎn)發(fā)的節(jié)點(diǎn)，也就是在S和下一個路口之間是否有節(jié)點(diǎn)，若有，則進(jìn)行下一步，否則就由節(jié)點(diǎn)S暫時攜帶該數(shù)據(jù)分組，等待可轉(zhuǎn)發(fā)車輛的出現(xiàn)。

（2）首先選擇和分組轉(zhuǎn)發(fā)方向相同的節(jié)點(diǎn)，若沒有，則再選擇反方向上的節(jié)點(diǎn)，然后根據(jù)鄰居列表中鄰居節(jié)點(diǎn)的速度大小和方向等信息，計(jì)算S和它們之間鏈路的有效持續(xù)時間和這些節(jié)點(diǎn)在Δt時間后的位置，根據(jù)式（9）得到這些鄰居節(jié)點(diǎn)到下一個路口Ii的距離，再計(jì)算各節(jié)點(diǎn)的轉(zhuǎn)發(fā)優(yōu)先權(quán)值。

（3）節(jié)點(diǎn)S選擇優(yōu)先權(quán)值最大的節(jié)點(diǎn)轉(zhuǎn)發(fā)分組。

4 仿真分析

采用基于VanetMobisim和NS-2的仿真平臺。使用VanetMobisim進(jìn)行車輛移動模型的模擬，并在NS-2上實(shí)現(xiàn)了對RBVT-R協(xié)議的改進(jìn)，將改進(jìn)后的路由協(xié)議叫作IRBVT-R（improved RBVT-R）。

車輛節(jié)點(diǎn)的移動模型采用VanetMobisim中帶有路口管理的智能駕駛者模型 （intelligent driver model with intersectionmanagement，IDM-IM）。采用南京市新街口附近2 000m范圍內(nèi)的道路布局作為仿真場景，詳細(xì)的仿真參數(shù)見表1，所有道路交叉口都設(shè)有紅綠燈。仿真結(jié)果如圖7、圖8所示。

表1 仿真參數(shù)

從圖7、圖8中可以看出，隨著車輛節(jié)點(diǎn)數(shù)的增加，RBVT-R和IRBVT-R兩個協(xié)議的分組交付率都增大，并且端到端平均時延都減小。這是因?yàn)檫@兩個協(xié)議都結(jié)合了實(shí)時的道路車輛信息，在車輛節(jié)點(diǎn)數(shù)很少時，道路車輛密度小，節(jié)點(diǎn)的可連接性差，分組在轉(zhuǎn)發(fā)時會經(jīng)常因找不到下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)而被暫時攜帶，甚至被丟棄，從而導(dǎo)致端到端平均時延大，且分組交付率低；隨著車輛節(jié)點(diǎn)數(shù)的增加，道路車輛密度逐漸增大，節(jié)點(diǎn)的可連接性提高，使得分組能被及時可靠地轉(zhuǎn)發(fā)，從而提高了分組交付率，并減小了端到端平均時延。

從圖7、圖8中還可以看出，IRBVT-R協(xié)議在分組交付率和端到端平均時延這兩個指標(biāo)上，其性能都要優(yōu)于RBVT-R協(xié)議。這是因?yàn)镮RBVT-R協(xié)議在路由建立階段考慮了道路的車輛密度，選擇車輛密度大的路段作為分組傳輸?shù)穆窂剑岣吡怂酚傻姆€(wěn)定性，并且在分組傳輸階段，考慮了車輛行駛方向與分組轉(zhuǎn)發(fā)方向的關(guān)系，優(yōu)先選擇與分組轉(zhuǎn)發(fā)方向相同且轉(zhuǎn)發(fā)優(yōu)先權(quán)值最大的車輛作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，減小了分組在同一路段重復(fù)傳輸?shù)母怕?，從而減小了端到端平均時延，并提高了分組交付率。

5 結(jié)束語

VANET是由車輛節(jié)點(diǎn)組成的Ad Hoc網(wǎng)絡(luò)。VANET路由協(xié)議的最大挑戰(zhàn)就在于車輛節(jié)點(diǎn)的移動導(dǎo)致網(wǎng)絡(luò)拓?fù)涞念l繁變化以及城市環(huán)境下節(jié)點(diǎn)的移動受道路布局的限制導(dǎo)致節(jié)點(diǎn)分布不均勻。本文在現(xiàn)有的RBVT-R協(xié)議的基礎(chǔ)上，提出了一種改進(jìn)的IRBVT-R協(xié)議，該協(xié)議在路由建立階段考慮了道路的車輛密度，并且在分組傳輸階段還考慮了車輛行駛方向與分組轉(zhuǎn)發(fā)方向的關(guān)系，提高了分組傳輸?shù)目煽啃?。仿真結(jié)果表明，IRBVT-R協(xié)議在分組交付率和端到端平均時延等方面，其性能都要優(yōu)于RBVT-R協(xié)議。

1 胡云斌,夏瑋瑋,宋鐵成等.一種應(yīng)用于VANET的改進(jìn)GPSR路由協(xié)議.2009通信理論與技術(shù)新發(fā)展——第十四屆全國青年通信學(xué)術(shù)會議論文集,大連，中國，2009

2 Toor Y,Muhlethaler P,Laoriti A.Vehicle Ad Hoc networks:applications and related technical issues.IEEE Communications Surveys&Tutorials,2008,10(3):74～88

3 Pei G,Gerla M,Chen T W.Fisheye state routing:a routing scheme for Ad Hoc wireless networks.Proceedings of 2000 IEEE International Conference on ICC,New Orleans,USA,2000:70～74

4 Das S R,Belding-royer E M,Perkins C E.Ad Hoc on-demand distance vector (AODV)routing.Proceedings of WMCSA’99,New Orleans,USA,2003

5 Karp B,Kung T H.GPSR:greedy perimeter stateless routing for wireless networks.Proceedings of the 6th annual International Conference on Mobile Computing and Networking(MOBICOM’00),Boston,USA,2000:243～254

6 Nzouonta J,Rajgure N,Wang Guiling.VANET routing on city roads using real-time vehicular traffic information.IEEE Transactions on Vehicular Technology,2009,58(7):3609～3626

7 Namboodiri V,Gao L X.Prediction-based routing for Vehicular Ad Hoc networks.IEEE Transactions on Vehicular Technology,2007,56(4):2332～2345

8 Lochert C,Mauve M,Hartenstein H,et al.Geographic routing in city scenarios.ACM SIGMOBILE Mobile Computing and Communications Review,2005,9(1):69～72

9 Li D,Huang H Y,Li X,et al.A distance-based directional broadcast protocol for urban vehicular Ad Hoc network.Proceedings of IEEEWiCOM,Shanghai,China,2007:19～24

10 Egoh K,De S.A multicriteria receiverside relay election approach in wireless Ad Hoc networks.Proceedings of MILCOM,Washington DC,USA,2006:1～7