城市場(chǎng)景車用自組織網(wǎng)絡(luò)有效路由

譚文虎，周寶定，范綠蓉

（1.華中師范大學(xué)物理科學(xué)與技術(shù)學(xué)院，湖北武漢430079；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430079）

0 引 言

由于車輛移動(dòng)性和網(wǎng)絡(luò)高動(dòng)態(tài)性，數(shù)據(jù)的有效傳輸一直是車用自組織網(wǎng)絡(luò)（vehicular Ad hoc networks，VANETs）研究的重要主題之一［1］。穩(wěn)定可靠的路由是保證VANETs有效通信的重要前提。由于VANETs的特殊性，傳統(tǒng)應(yīng)用于MANETs路由協(xié)議并不能有效的適合于VANETs［2］。相對(duì)于高速公路場(chǎng)景來說，城市交通環(huán)境由于道路網(wǎng)絡(luò)復(fù)雜，干擾因素多且車輛行駛狀態(tài)多變，其路由設(shè)計(jì)面臨更大的挑戰(zhàn)。

針對(duì)以上出現(xiàn)的問題，本文提出應(yīng)用于城市環(huán)境的基于交叉路口地理路由協(xié)議。協(xié)議基于道路網(wǎng)絡(luò)連通概率模型為源節(jié)點(diǎn)與目的節(jié)點(diǎn)選擇最優(yōu)連續(xù)交叉道路段，數(shù)據(jù)包沿著這些道路段傳輸；道路段內(nèi)采用地理轉(zhuǎn)發(fā)策略的數(shù)據(jù)包到達(dá)交叉路口附近后，選擇車輛隊(duì)列的最佳隊(duì)列頭負(fù)責(zé)數(shù)據(jù)包在拐角處的轉(zhuǎn)發(fā)。通過仿真實(shí)驗(yàn)驗(yàn)證了所提出路由協(xié)議的穩(wěn)定性和可靠性。

1 城市車載網(wǎng)路由研究的現(xiàn)狀

可靠路由是網(wǎng)絡(luò)有效通信的先決條件，其相關(guān)的研究是VANETs中的熱點(diǎn)。Tarik Taleb將交叉路口附近的車輛基于移動(dòng)信息進(jìn)行分組，選擇同一組的節(jié)點(diǎn)建立路由，同時(shí)引入路由失效周期（LET）概念［3，4］。Moez Jerbi等研究城市環(huán)境基于交通路口的可靠路由協(xié)議［2，5，6］，采用優(yōu)化的存儲(chǔ)轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)交叉路口數(shù)據(jù)。當(dāng)前針對(duì)城市環(huán)境車載網(wǎng)的路由協(xié)議通常利用交叉路口車輛速度矢量和位置等移動(dòng)信息，預(yù)測(cè)車輛運(yùn)行狀態(tài)［7－9］，評(píng)估車輛連通周期建立地理路由。一方面這些路由很少考慮交通流對(duì)道路連通性的影響；另一方面忽略數(shù)據(jù)包在經(jīng)過交叉路口拐角處時(shí)，由于無線信號(hào)功率的急劇衰減引起大量數(shù)據(jù)包丟失。

2 城市環(huán)境道路網(wǎng)絡(luò)模型

城市道路交通網(wǎng)絡(luò)的道路段通過交叉路口實(shí)現(xiàn)連接。車輛通過GPS接收器或位置服務(wù)（location service，LS）［10，11］獲取地理位置信息；通過車載導(dǎo)航系統(tǒng)數(shù)字地圖，車輛獲取由交叉路口和道路組成的城市環(huán)境交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。并且當(dāng)前能夠提供道路密度、車輛速度等實(shí)時(shí)交通信息的數(shù)字地圖已經(jīng)得到應(yīng)用［12］。

將道路網(wǎng)路抽象成是由邊和點(diǎn)組成的圖G＝（V，E）。其中V表示交通路口集合，E表示道路段集合。若Ia∈V，Ib∈V，且Ia、Ib之間存在車輛能夠行駛的道路段，則道路段（Ia，Ib）∈E。交通路口安裝交通控制設(shè)施，車輛根據(jù)交通規(guī)則行駛。定義行駛于道路網(wǎng)絡(luò)的車輛為節(jié)點(diǎn)，并且節(jié)點(diǎn)雙向行駛。

3 路由協(xié)議

所提出路由協(xié)議IRPU（intersection－based routing proto－col for urban）基于本節(jié)提出的交通道路網(wǎng)絡(luò)連通概率模型選擇最優(yōu)路由；當(dāng)數(shù)據(jù)包到達(dá)交叉路口附近時(shí)，當(dāng)前節(jié)點(diǎn)選擇合適的隊(duì)列頭，負(fù)責(zé)數(shù)據(jù)包在交叉路口拐角處的有效轉(zhuǎn)發(fā)。

3.1 最優(yōu)路徑選擇

圖1所示li為道路網(wǎng)絡(luò)任意一條雙向車道道路i長(zhǎng)度，通信半徑為的r車輛在交通路口排隊(duì)長(zhǎng)度分別為li1、li2；道路段li－li1－li2自由流范圍車輛密度為λi且服從泊松分布。隨機(jī)變量xi表示自由流范圍車輛出現(xiàn)的數(shù)目，則概率質(zhì)量函數(shù)

于是車輛通信范圍內(nèi)至少存在一個(gè)鄰居的概率為Pr（xi＞0）＝1－f（xi＝0）＝1－e－λir。處于車輛隊(duì)列狀況（如li1、li2范圍）的車輛由于節(jié)點(diǎn)之間的距離皆小于通信范圍，物理上是完全連通的，于是道路段i連通概率即

令源節(jié)點(diǎn)與目的節(jié)點(diǎn)所在道路分別為rds、rdd，兩條道路通過（rd00，rd01，…）、（rd10，rd11，…）、（rd20，rd21，…）等連接，則rds與rdd連通概率為

最佳路由具有最大的連通概率Psd，Psd＝max（Psdm）。如圖1所示，rds＝（I5，I6），rdd＝（I3，I4）源節(jié)點(diǎn)s與目的節(jié)點(diǎn)d可能的路由為I6→I1→I2→I3→I4，I6→I5→I2→I3→I4，I6→I5→I4→I3和I6→I1→I2→I5→I4→I3。從式（2）可知有（I1，I6）、（I4，I5）車輛數(shù)據(jù)幾乎為零，因此連通概率趨于0，通過圖1和式（3）看出I6→I5→I2→I3→I4為s、d的導(dǎo)向路由，數(shù)據(jù)包沿著該導(dǎo)向路由傳輸，道路段內(nèi)數(shù)據(jù)采用地理轉(zhuǎn)發(fā)策略。

圖1 城市場(chǎng)景道路交通網(wǎng)絡(luò)

3.2 道路段內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)

節(jié)點(diǎn)離開交通路口行駛于道路段內(nèi)，定義該節(jié)點(diǎn)為段內(nèi)節(jié)點(diǎn)。段內(nèi)節(jié)點(diǎn)采用基于生命周期的地理轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)數(shù)據(jù)包。令Dm表示當(dāng)前轉(zhuǎn)發(fā)節(jié)點(diǎn)，Dn是Dm通信范圍內(nèi)的任意一個(gè)節(jié)點(diǎn)，d（Dm，Iν）與d（Dn，Iv）分別表示Dm、Dn與下一跳交通路口Iν的距離。

Dm，n＝表示兩節(jié)點(diǎn)間距離。其中（xm，ym）與（xn，yn）分別為Dm、Dn當(dāng)前坐標(biāo)。節(jié)點(diǎn)Dm與Dn的路徑生命周期

當(dāng)兩節(jié)點(diǎn)互相接近時(shí)δ＝1；節(jié)點(diǎn)相對(duì)離開則δ＝－1。節(jié)點(diǎn)同向行駛η＝1，節(jié)點(diǎn)反方向行駛則η＝－1。珗vm、珗vn表示Dm、Dn速度矢量。a和b是影響因子，當(dāng)a＝0，b＝0時(shí)，表示忽略道路寬度等影響因素。Dm所選擇的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)需要滿足以下兩個(gè)條件:

例圖1的轉(zhuǎn)發(fā)節(jié)點(diǎn)D1選擇接近于下一跳交通路口I2即滿足條件（a），并滿足條件（b）的節(jié)點(diǎn)D2為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

3.3 交叉路口數(shù)據(jù)轉(zhuǎn)發(fā)

研究表明［13］無線電磁波信號(hào)在通過交叉路口角落后，信號(hào)功率強(qiáng)度急劇衰減約40dB左右。這意味著數(shù)據(jù)包在經(jīng)過十字路口拐角處后，在很短的通信距離范圍內(nèi)，由于無線通信信號(hào)的急劇衰減引起通信鏈路的斷裂，從而引起數(shù)據(jù)包的大量丟失，進(jìn)一步影響網(wǎng)絡(luò)的通信性能。

當(dāng)車輛在交叉路口遇到紅燈時(shí)，將以隊(duì)列的形式依次排隊(duì)等待放行。IRPU選擇輛隊(duì)列中距離十字交叉路口中心最近的車輛為隊(duì)列頭負(fù)責(zé)拐角處數(shù)據(jù)的投遞，一方面該車輛節(jié)點(diǎn)具有最佳的數(shù)據(jù)傳遞性能，其次處于靜止等待的時(shí)間最長(zhǎng)，因此運(yùn)動(dòng)狀態(tài)最穩(wěn)定。假設(shè)交叉路口紅燈維持的時(shí)間為tr，從圖2中可以看出節(jié)點(diǎn)A4相對(duì)于十字路口隊(duì)列的節(jié)點(diǎn)A1，A2，A3，A5和A6來說，距離交叉路口Iα中心最近，具有最佳的網(wǎng)絡(luò)通信質(zhì)量，并且由于A4排隊(duì)等待而處于靜止穩(wěn)定狀態(tài)的時(shí)間最長(zhǎng)為tr。并且A4具有最佳的信息傳遞位置和最長(zhǎng)的穩(wěn)定狀態(tài)，于是節(jié)點(diǎn)A4被選舉為隊(duì)列頭，用來轉(zhuǎn)發(fā)經(jīng)過十字路口拐角處的數(shù)據(jù)包，從而避免由于信號(hào)強(qiáng)度的迅速衰減而引起數(shù)據(jù)包的大量丟失。

車輛與車輛間的相對(duì)位置可以分為視距（line－of－sight，LOS）和非視距（nonline－of－sight，NLOS）兩種情況。為了減輕隊(duì)列頭的通信負(fù)載，當(dāng)接收節(jié)點(diǎn)處于發(fā)送節(jié)點(diǎn)的通信范圍并且相對(duì)位置為L(zhǎng)OS，當(dāng)數(shù)據(jù)包跨過交叉路口到達(dá)節(jié)點(diǎn)，兩節(jié)點(diǎn)的通信不必需要隊(duì)列頭的參與數(shù)據(jù)轉(zhuǎn)發(fā)。例圖2車輛節(jié)點(diǎn)A2在交叉路口Iα直接向節(jié)點(diǎn)A5發(fā)送數(shù)據(jù)包而不需要隊(duì)列頭A4的參與。若發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)在物理上處理通信范圍內(nèi)，但處于NLOS狀態(tài)，數(shù)據(jù)包通過隊(duì)列頭中繼實(shí)現(xiàn)交叉路口的順利轉(zhuǎn)發(fā)。例圖2的車輛節(jié)點(diǎn)A8物理上處于A7的通信范圍內(nèi)，由于A8位于交叉路口的拐角處，A7如果直接向A8發(fā)送數(shù)據(jù)包，由于無線信號(hào)繞過拐角處會(huì)急劇衰減，很容易引起數(shù)據(jù)包的丟失。A7首先把數(shù)據(jù)包轉(zhuǎn)寄給隊(duì)列頭A4，然后A4中繼數(shù)據(jù)包給A8。由于節(jié)點(diǎn)A4良好的通信性能，保證了數(shù)據(jù)包經(jīng)過交叉路口拐角處能夠被順利接收。

圖2 交叉路口數(shù)據(jù)轉(zhuǎn)發(fā)

3.4 IRPU描述

（1）節(jié)點(diǎn)通過周期性廣播hello信息建立鄰居表，通過周期接收到的hello包，記錄和更新鄰居節(jié)點(diǎn)的ID、位置、速度、時(shí)間戳等交通信息；

（2）源節(jié)點(diǎn)通過LS和電子地圖獲取道路交通信息，IRPU采用3.1節(jié)道路連通概率模型建立數(shù)據(jù)包最優(yōu)路徑，數(shù)據(jù)包存儲(chǔ)連續(xù)交通路口組成的導(dǎo)向路由信息；

（3）節(jié)點(diǎn)當(dāng)前所在的道路由交通路口Iα和Iβ決定；節(jié)點(diǎn)收到數(shù)據(jù)包后，檢測(cè)數(shù)據(jù)包的導(dǎo)向路由；若數(shù)據(jù)包下一跳交通路口為Iα或Iβ，則節(jié)點(diǎn)查詢鄰居表，使用3.2節(jié)方法選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)；若不存在合適下一跳節(jié)點(diǎn)，該節(jié)點(diǎn)暫時(shí)存儲(chǔ)該數(shù)據(jù)包；若Id｛Iα，Iβ｝，節(jié)點(diǎn)直接丟棄該數(shù)據(jù)包。

（4）協(xié)議采用存儲(chǔ)轉(zhuǎn)發(fā)的方式，節(jié)點(diǎn)在沒有鄰居的情況下，緩存不能轉(zhuǎn)發(fā)的數(shù)據(jù)；節(jié)點(diǎn)周期查詢緩存區(qū)的數(shù)據(jù)，并選擇合適的鄰居轉(zhuǎn)發(fā)這些數(shù)據(jù)；當(dāng)節(jié)點(diǎn)從當(dāng)前道路段移動(dòng)到其它道路段后，若數(shù)據(jù)包的下一跳交通路口與節(jié)點(diǎn)的下一跳交通路口不一致，意味著節(jié)點(diǎn)的行駛路徑偏離了數(shù)據(jù)包的導(dǎo)向路由，節(jié)點(diǎn)使用3.1節(jié)方法為這些數(shù)據(jù)包重新建立導(dǎo)向路由，并基于3.2節(jié)選擇合適的鄰居轉(zhuǎn)發(fā)數(shù)據(jù)包。

（5）當(dāng)數(shù)據(jù)包到達(dá)交叉路口附近，基于3.3節(jié)利用隊(duì)列頭可靠的數(shù)據(jù)包投遞性能，實(shí)現(xiàn)數(shù)據(jù)包在交叉路口的有效順利轉(zhuǎn)發(fā)。

4 仿真與分析

4.1 場(chǎng)景設(shè)置

本節(jié)對(duì)IRPU與GSR、ROMSGP、Gy TAR協(xié)議進(jìn)行性能仿真比較。在每個(gè)路口附近對(duì)稱合理位置設(shè)置障礙物，用以模擬真實(shí)交通場(chǎng)景高大建筑等障礙物對(duì)通信影響。節(jié)點(diǎn)使用全向天線通信，通信半徑為r＝200m；地圖大小2500×2500m2，仿真時(shí)間為60min，交通網(wǎng)絡(luò)公設(shè)置22條道路段，8個(gè)交叉路口；數(shù)據(jù)包尺寸設(shè)置為512bytes，車輛平均速度為24－88km/h；采用交通信號(hào)燈控制交通路口車流的通行；采用仿真軟件Vanet Mobisim［14］生成NS2［15］模擬器的節(jié)點(diǎn)移動(dòng)軌跡場(chǎng)景輸入文件，實(shí)現(xiàn)模擬仿真分析。CBR流的取值范圍為1包/s－10包/s，分別分析100、150、200、250和300車輛的網(wǎng)絡(luò)數(shù)據(jù)包投遞率和端到端平均延遲。

4.2 仿真結(jié)果及性能分析

由圖3可以看出隨著數(shù)據(jù)包速率的增加，4種協(xié)議的數(shù)據(jù)包投遞率皆隨之降低。這主要是由于較高的數(shù)據(jù)發(fā)送速率，需要網(wǎng)絡(luò)對(duì)數(shù)據(jù)包做出更迅速的反應(yīng)。IRPU相比較其它3種協(xié)議而言，具有最高的數(shù)據(jù)包投遞率。這主要是因?yàn)镮RPU通過選擇最優(yōu)導(dǎo)向路徑，保證數(shù)據(jù)包沿著連通性最佳的路徑轉(zhuǎn)發(fā)；當(dāng)數(shù)據(jù)包在交叉路口拐角處附近時(shí)，隊(duì)列頭保證他們的順利轉(zhuǎn)發(fā)。

圖3 數(shù)據(jù)投遞率對(duì)比

Gy TAR協(xié)議雖然在路由過程中，考慮了通信路徑連通性對(duì)數(shù)據(jù)包投遞性能的影響，但由于沒有充分考慮交叉路口數(shù)據(jù)包投遞的有效性，因此數(shù)據(jù)包投遞率相對(duì)于IRPU協(xié)議性能要差。并且IRPU隨著數(shù)據(jù)包速率的增加，數(shù)據(jù)投遞率保持比較穩(wěn)定，表明IRPU協(xié)議能夠維持更為穩(wěn)定的路由路徑。

圖4 平均延遲對(duì)比

圖4顯示不同協(xié)議的端到端平均延遲。隨著節(jié)點(diǎn)數(shù)目的增加，協(xié)議網(wǎng)絡(luò)的端到端延遲逐漸減小。足夠的節(jié)點(diǎn)數(shù)目保證網(wǎng)絡(luò)具有較好的連通性，從而使得數(shù)據(jù)包能夠較及時(shí)的被目的節(jié)點(diǎn)接收。其中IRPU延遲小于GSR、ROMSGP和Gy TAR。這是由于一方面IRPU道路段內(nèi)的優(yōu)化地理轉(zhuǎn)發(fā)減少數(shù)據(jù)包投遞的節(jié)點(diǎn)跳數(shù)，另一方面最優(yōu)連通性的導(dǎo)向路由和隊(duì)列頭參與交叉路口數(shù)據(jù)的轉(zhuǎn)發(fā)，避免數(shù)據(jù)包發(fā)送過程中的通信阻塞。

5 結(jié)束語

本文提出了應(yīng)用于城市環(huán)境的車用自組織網(wǎng)絡(luò)的路由協(xié)議IRPU。該協(xié)議基于道路連通概率模型為源和目的節(jié)點(diǎn)選擇連續(xù)道路段交叉路口組成最佳路徑，數(shù)據(jù)包沿著這條導(dǎo)向路徑傳輸。為了應(yīng)對(duì)交叉路口拐角處無線信號(hào)功率的急劇衰減引起的鏈路突然斷裂，進(jìn)而引起數(shù)據(jù)包的大量丟失，IRPU通過選擇最優(yōu)的隊(duì)列頭負(fù)責(zé)交叉路口拐角處數(shù)據(jù)包的有效轉(zhuǎn)發(fā)。仿真實(shí)驗(yàn)通過比較驗(yàn)證所設(shè)計(jì)路由協(xié)議性能的優(yōu)越性。

［1］Jaehoon（Paul）Jeong，Shuo Guo.Trajectory－based data forwarding for light－traffic vehicular Ad Hoc networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22（5）:743－757.

［2］Moez Jerbi，Sidi－Mohammed Senouci.Towards efficient geographic routing in urban vehicular networks［J］.IEEE Transactions on Vehicular Technology，2009，58（9）:5048－5059.

［3］Tarik Taleb，Ehssan Sakhaee.A stable routing protocol to support its services in VANET networks［J］.IEEE Transactions on Vehicular Technology，2007，56（6）:3337－3347.

［4］Vinod Namboodiri，Lixin Gao.Prediction－based routing for vehicular Ad Hoc networks［J］.IEEE Transactions on Vehicular Technology，2007，56（4）:2332－2345.

［5］TEE C A T H，LEE A.A novel routing protocol－junction based adaptive reactive routing（JARR）for VANET in city environments［C］//European Wireless Conference，2010:1－3.

［6］Pham Thi Hong，Hyunhee Park.A road and traffic－aware routing protocol in vehicular ad hoc networks［C］//The 13th International Conference on Advanced Communication Technology，2011:24－28.

［7］Qing Yang，Alvin Lim.Connectivity aware routing in vehicular networks［C］//WCNC Proceedings，2008:2218－2223.

［8］Wang Wenjing，Xie Fei.Small－scale and large－scale routing in vehicular Ad Hoc networks［J］.IEEE Transactions on Vehicular Technology，2009，58（9）:5200－5213.

［9］Kaveh Shafiee，Victor C M Leung.Connectivity－aware minimum－delay geographic routing with vehicle tracking in VANETs［J］.Ad Hoc Networks，2011（9）:131－141.

［10］Zhang Guoqing，Mu Dejun，Xu Zhong，et al.A survey on the routing schemes of urban vehicular Ad Hoc networks［C］//Proceedings of the 27th Chinese Control Conference，2008.

［11］Saleet H，BASIR O，Langar R.Region－based location servicemanagement protocol for VANETs［J］.IEEE Trans Veh Technol，2010，9（2）:917－931.

［12］Smart view［EB/OL］.http:www.yahoo.com.

［13］Eugenio Giordano，Raphael Frank.CORNER:A radio propagation model for VANETs in urban scenarios［J］.Proceedings of the IEEE，2011，99（7）:1280－1294.

［14］Vanet MobiSim［DB/OL］.http://vanet.eurecom.fr，2012.

［15］The network simulator－ns2［DB/OL］.http://www.isi.edu/nsnam/ns，2011.