黃弘，湯翾

（西華大學(xué)數(shù)學(xué)與計算機學(xué)院，成都 610000）

基于地理位置的VENET可靠路由協(xié)議

黃弘，湯翾

（西華大學(xué)數(shù)學(xué)與計算機學(xué)院，成都 610000）

基于城市環(huán)境下車載自組織網(wǎng)絡(luò)的特點，提出基于地理位置的VENET可靠路由協(xié)議GCRR。充分利用電子地圖等提供的信息，通過道路的車流密度和車流量的關(guān)系計算道路權(quán)重，進而排序出有效的數(shù)據(jù)轉(zhuǎn)發(fā)路徑，并根據(jù)節(jié)點的移動方向和移動速度，并采用擴展的貪心轉(zhuǎn)發(fā)策略，從而實現(xiàn)數(shù)據(jù)的高效可靠傳輸。仿真實驗驗證GCRR算法的性能優(yōu)于經(jīng)典算法GPSR和GSR。

車載自組織網(wǎng)；路由；車流量

0 引言

車載自組織網(wǎng)絡(luò)（VANETs）是通過車輛與車輛之間、車輛與路邊設(shè)施之間的通信的Ad Hoc的網(wǎng)絡(luò)，形成一個大范圍的無線移動網(wǎng)絡(luò)。車載自組織網(wǎng)絡(luò)具有不同于其他無線網(wǎng)絡(luò)的特征，例如，具有大量的移動節(jié)點、拓撲結(jié)構(gòu)頻繁變化、節(jié)點的移動軌跡受限、可借用外部輔助信息支持和QoS需求多樣性[1]。

國內(nèi)外現(xiàn)有的路由協(xié)議有基于拓撲的路由協(xié)議、基于位置的路由協(xié)議和基于道路設(shè)施和車載設(shè)備的路由協(xié)議。而基于位置的經(jīng)典路由協(xié)議有GPSR（Greedy Perimeter Stateless Routing）[2]，其主要采用貪心轉(zhuǎn)發(fā)策略。GSR（Graphic Source Routing）[3]，其提出采用電子地圖獲取道路的拓撲結(jié)構(gòu)，然后利用Dijkstra算法獲得傳輸數(shù)據(jù)的最優(yōu)路徑，但它未考慮網(wǎng)絡(luò)的連通性。GPCR（Greedy Perimeter Coordinator Routing）[4]采用的思想和GSR相似，而不同之處是此算法利用了節(jié)點自身的位置區(qū)判斷節(jié)點是否處于岔路口。

綜上所述，已有的經(jīng)典協(xié)議的主要策略是基于節(jié)點之間的物理距離，并沒有考慮道路的連通性，而結(jié)合路段的車流量信息就可以選擇有較好連通性的道路，所以，本文提出了一種城市環(huán)境下基于位置及連通性的車輛自組網(wǎng)可靠路由協(xié)議GCRR（Geography-based and Network Connectivity Reliable Routing），并考慮了車流量及車流密度的關(guān)系。

1 基于地理位置的路由協(xié)議

1.1 基本假設(shè)及相關(guān)術(shù)語定義

在該算法中，假設(shè)所有車輛都安裝GPS導(dǎo)航系統(tǒng),車輛可以獲取各自的位置信息和其他車輛的位置,導(dǎo)航系統(tǒng)能為車輛提供城市街道的電子地圖等。本文中提到的節(jié)點是指車輛模型，假設(shè)處于十字路口的節(jié)點可以無線傳輸范圍內(nèi)的非十字路口節(jié)點進行通信，而不在同一條道路上的非十字路口節(jié)點間不可通信。因此，數(shù)據(jù)的轉(zhuǎn)發(fā)過程,主要是從非十字路口節(jié)點向十字路口節(jié)點逼近，十字路口節(jié)點再轉(zhuǎn)發(fā)給非十字路口節(jié)點,直到數(shù)據(jù)轉(zhuǎn)發(fā)到目的節(jié)點為止。

1.2 協(xié)議設(shè)計

本文設(shè)計的路由協(xié)議主要包括兩個部分。首先，根據(jù)目的節(jié)點的位置，道路節(jié)點密度和路段長度選擇出錨節(jié)點序列；其次，錨節(jié)點之間的數(shù)據(jù)轉(zhuǎn)發(fā)基于節(jié)點的移動方向和移動速度，并采用擴展的貪心轉(zhuǎn)發(fā)策略。

（1）重要錨節(jié)點排序

根據(jù)城市街道的拓撲結(jié)構(gòu)信息，將den表示為兩相鄰十字路口之間道路的車輛密度，其物理長度記為L；V表示兩相鄰十字路口的所有車輛的平均速度；T表示檢測中的短暫時間；r表示節(jié)點的無線傳輸半徑。首先根據(jù)每條路段的密度，選擇出路段密度大于下列閾值的路段：

此公式，是由車流密度公式和車流量的計算公式，且引用了水流量的計算方式，進行了積分運算，進而推導(dǎo)出的。根據(jù)公式（1）選擇出的道路作為數(shù)據(jù)轉(zhuǎn)發(fā)的路徑，同時提取需要經(jīng)過的十字路口序列，并將此路徑信息序列存儲到數(shù)據(jù)包頭文件中。每當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)到一個十字路口時，就根據(jù)數(shù)據(jù)包頭文件中的路徑序列信息選擇下一條路段進行數(shù)據(jù)的轉(zhuǎn)發(fā)。其中，當(dāng)與某個十字路口相連的路段，如果有多余一條的路段滿足公式（1）的條件，則選擇接近最佳車流量的路段；當(dāng)與某個十字路口相連的路段，如果沒有任何一條路段滿足公式（1），則選擇與下一個滿足條件的路段較近的路段。

如圖1所示，根據(jù)公式（1）從源節(jié)點S到目的節(jié)點D可得到的路徑為2-4-6-7，即存在數(shù)據(jù)包頭文件中的信息是2-4-6-7。

圖1 S到D數(shù)據(jù)轉(zhuǎn)發(fā)的錨節(jié)點選擇過程圖

對于車輛密度的信息，本文提供了一種估計每條路段車輛密度的方法。首先，所有節(jié)點都維護一張密度信息表，同時記錄鄰居節(jié)點信息和該路段的密度信息，每個節(jié)點廣播自身的ID。當(dāng)有節(jié)點從十字路口進入路段時，該路段的密度den就加1，當(dāng)該節(jié)點到達下一個十字路口時，den的值則表示剛經(jīng)過路段的密度，并記時間戳為T，即在時間T內(nèi)，此den有效。

（2）擴展的貪心轉(zhuǎn)發(fā)策略

同一路段上節(jié)點之間數(shù)據(jù)的傳輸，主要基于貪心模式，但由于本策略是對高級貪心算法AGF[5]的改進，故稱擴展的貪心轉(zhuǎn)發(fā)策略。首先，將十字路口也就是靜態(tài)節(jié)點作為在同一路段上的目的節(jié)點，數(shù)據(jù)在轉(zhuǎn)發(fā)給靜態(tài)節(jié)點過程中采用貪心模式；其次，該貪心策略基于節(jié)點的移動方向和移動速度轉(zhuǎn)發(fā)給滿足條件的節(jié)點，條件為公式（2）。

兩十字路口之間的直路間節(jié)點轉(zhuǎn)發(fā)方案為：首先判斷鄰居節(jié)點的運動方向是否同數(shù)據(jù)傳輸方向一致，再計算每個節(jié)點的權(quán)重，根據(jù)權(quán)重選擇下一跳節(jié)點。鄰居節(jié)點的權(quán)重依據(jù)公式（2）計算：

其中，v表示鄰居節(jié)點運動速度的大小，Dir表示節(jié)點運動方向，L表示可傳輸范圍內(nèi)，離本路段目的靜態(tài)節(jié)點的距離。當(dāng)Dir＞0時表示鄰居節(jié)點的運動方向與數(shù)據(jù)傳輸方向一致，Dir＜0表示相反。首先考慮Dir＞0的節(jié)點，且選擇權(quán)重大的鄰居節(jié)點作為下一跳節(jié)點，即選擇移動速度快的節(jié)點，若同向的不滿足條件，則選擇Dir＜0的方向的車輛，此方向是將數(shù)據(jù)轉(zhuǎn)發(fā)給權(quán)重小的節(jié)點，即距離目的靜態(tài)節(jié)點近的作為下一跳節(jié)點，當(dāng)反方向的節(jié)點攜帶信息時，迎面遇到正方向滿足條件的節(jié)點時就立即轉(zhuǎn)發(fā)。

2 仿真實驗及結(jié)果分析

使用交通流仿真器VanetMobiSim與網(wǎng)絡(luò)仿真器NS-2相結(jié)合，模擬實際交通流場景，最后通過仿真結(jié)果比較、分析算法GCR與經(jīng)典算法GPSR和GSR在車載自組織網(wǎng)中的性能。在仿真中，模擬區(qū)域范圍為4km×4km的城市環(huán)境，包括18個十字路口，節(jié)點數(shù)目分別取值（50，90，130，170，210，250），節(jié)點運動速度在30km/s～50km/s之間隨機取值，車輛的傳輸半徑200米，分組大小為512Bytes。

將GCRR與GPSR和GSR的性能比較，圖2表明GCRR的數(shù)據(jù)包投遞率明顯好于GPSR和GSR，且隨著趨近最佳車流量時，3種協(xié)議的數(shù)據(jù)投遞率都有增加趨勢。

圖2 數(shù)據(jù)包投遞率變化

圖3 吞吐量變化

圖3表明了路由協(xié)議的吞吐量變化情況，隨著趨近最佳車流量時，GCRR協(xié)議的吞吐量好于GPSR和GSR。

3 結(jié)語

隨著電子地圖等技術(shù)的發(fā)展，節(jié)點可以隨時獲取自己的地理位置，進而可改善車載自組織網(wǎng)的路由性能。已有基于地理位置的路由協(xié)議的主要策略是考慮節(jié)點之間的物理距離，這使得網(wǎng)絡(luò)不連通的情況下很難達到路由的高效與穩(wěn)定。本文充分利用電子地圖等提供的信息，結(jié)合節(jié)點的位置及道路車流量信息提出了基于地理位置的VENET路由協(xié)議。該協(xié)議通過道路的車流密度公式和車流量公式的關(guān)系計算道路權(quán)重，進而排序出有效的數(shù)據(jù)轉(zhuǎn)發(fā)路徑；再根據(jù)節(jié)點的移動方向和移動速度，并采用擴展的貪心轉(zhuǎn)發(fā)策略，從而實現(xiàn)數(shù)據(jù)的高效可靠傳輸。仿真實驗驗證了GCRR算法的性能優(yōu)于經(jīng)典算法GPSR和GSR。

[1] 常促宇,向勇,史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展.通信學(xué)報，2007，28（11）:116～126

[2] Willke T,Tientrakool P,Maxemchuk N.A Survey of Inter-Vehicle Communication Protocols and Their Applications.IEEE Communications Surveys&Tutorials，2009，11（2）:3～20

[3] Lochert C,Hartenstein H,Tian J.A Routing Strategy for Vehicular Ad Hoc Network in City Environments.In:Proc.of the IEEE Intelligent Vehicles Symposium，2003：156～161

[4] Lochert C,Mauve M,Fulbler H.Geographic Routing in City Scenarios.ACM Sigmobile Mobile Computing and Communications Review，2005，9（1）:69～72

[5] Naumov V,Baumann R,Gross T.An Evaluation of Inter-Vehicle Ad Hoc Networks Based on Realistic Vehicular Traces.In:Proc.of the ACM Int'l Symp.on Mobile Ad Hoc Networking and Computing，2006：108～119

Geography-Based and Network Connectivity Reliable Routing

HUANG Hong，TANG Xuan
（School of Mathematics and Computer Engineering,Xihua University,Chengdu 610000）

Based on the characteristics of the urban environment in VENETs network,proposes a new algorithm GCRR.Makes full use of the electronic map of road traffic density and the relationship based on the weight of the road.Sorts out the effective data forwarding path,and according to the moving direction and speed of mobile node,uses the extension of greedy forwarding strategy,so as to realize the high efficient and reliable transmission of data.Simulation shows the performance of GCRR algorithm is superior to the classic algorithms of GPSR and GSR.

VENET;Routing;Vehicle Flow

1007-1423（2015）02-0018-04

10.3969/j.issn.1007-1423.2015.02.005

黃弘（1987-），女，山東煙臺人，碩士研究生，研究方向為計算機網(wǎng)絡(luò)、車載自組織網(wǎng)絡(luò)

湯翾（1990-），女，湖北荊州人，碩士研究生，研究方向為圖形處理

2014-11-25

2014-12-16