譚文虎，周寶定，范綠蓉

（1.華中師范大學物理科學與技術學院，湖北武漢430079；2.武漢大學測繪遙感信息工程國家重點實驗室，湖北武漢430079）

0 引 言

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

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

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

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

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

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

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

3 路由協(xié)議

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

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

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

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

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

最佳路由具有最大的連通概率Psd，Psd＝max（Psdm）。如圖1所示，rds＝（I5，I6），rdd＝（I3，I4）源節(jié)點s與目的節(jié)點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的導向路由，數(shù)據(jù)包沿著該導向路由傳輸，道路段內(nèi)數(shù)據(jù)采用地理轉發(fā)策略。

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

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

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

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

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

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

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

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

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

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

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

3.4 IRPU描述

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

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

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

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

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

4 仿真與分析

4.1 場景設置

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

4.2 仿真結果及性能分析

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

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

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

圖4 平均延遲對比

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

5 結束語

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