VANET場景下的GPSR－R路由算法

李 超， 韓江洪，2， 魏振春，2， 衛(wèi) 星，2

（1.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009；2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽 合肥 230009）

VANET場景下的GPSR－R路由算法

李 超1， 韓江洪1，2， 魏振春1，2， 衛(wèi) 星1，2

（1.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009；2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽 合肥 230009）

路由選擇是實現(xiàn)VANET的關(guān)鍵技術(shù)之一，沒有合適而高效的路由選擇算法，VANET就無法工作。由于路由在長距離通信時多跳易斷裂，通信鏈路只需滿足通信需求即可。文章對GPSR路由協(xié)議進行了改進，提出了VANET場景下的GPSR路由算法：GPSR－R。GPSR－R根據(jù)移動節(jié)點間鏈路建立的網(wǎng)絡(luò)需求進行綜合考慮，充分利用不穩(wěn)定但滿足需求的路由完成信息的傳遞。分析結(jié)果表明，GPSR－R在數(shù)據(jù)包傳遞率、丟包率方面優(yōu)于GPSR和GPSR－AD。

GPSR－R算法；通信需求；VANET場景

隨著“車聯(lián)網(wǎng)”概念的提出，在如何進一步發(fā)展智能交通系統(tǒng)ITS（intelligent transport system）應用的問題上，世界各國不約而同地將注意力集中到車載通信系統(tǒng)上。近年來，將移動ad hoc自組網(wǎng)技術(shù)應用于車輛，組成ad hoc網(wǎng)絡(luò)VANET（vehicular ad hoc networks）以實現(xiàn)車輛間的信息交互已經(jīng)成為一個研究熱點［1－4］。

路由協(xié)議處于網(wǎng)絡(luò)體系結(jié)構(gòu)的核心位置，為2個節(jié)點建立交換的路徑是網(wǎng)絡(luò)性能的重要影響因素之一。VANET作為移動自組網(wǎng)的一種特殊的形式，有其自身的特點，若直接采用傳統(tǒng)的移動自組網(wǎng)路由協(xié)議則難以取得良好的網(wǎng)絡(luò)性能。

在VANET中，研究較多的有2類：基于拓撲的路由協(xié)議和基于位置的路由協(xié)議。AODV是最具代表性的基于拓撲的路由協(xié)議；GPSR是最具代表性的基于位置的路由協(xié)議。GPSR路由算法在查找過程中，為了避免空洞的產(chǎn)生，利用右手法則沿空洞周圍傳輸來解決此問題，采用周邊鄰居節(jié)點保存路由信息，是一個無狀態(tài)的協(xié)議；在右手法則尋找路由的過程中，拋棄了備用節(jié)點，因為這些節(jié)點在鏈路和路由跳數(shù)上不是最優(yōu)節(jié)點。

在GPSR路由協(xié)議中，節(jié)點下一跳選擇采用貪婪轉(zhuǎn)發(fā)方式進行信息的傳遞。貪婪轉(zhuǎn)發(fā)方式在網(wǎng)絡(luò)節(jié)點密度很高的情況下具有傳輸時延小、轉(zhuǎn)發(fā)成功率高的特點，但是在傳遞距離長、路由需要多跳的情況下，貪婪轉(zhuǎn)發(fā)會由于通信空洞的存在而導致分組轉(zhuǎn)發(fā)失敗。

本文提出一種VANET場景下的路由選擇算法GPSR－R，在路由的尋找過程中參考節(jié)點的網(wǎng)絡(luò)需求，充分利用不穩(wěn)定信道來完成任務(wù)，既滿足了消息傳輸?shù)幕拘枰脖苊饬嗽陂L距離傳輸中路由由于多跳信息傳遞率下降的情形。

1 VANET模型

對VANET作出如下假設(shè)［7］：

（1）車輛能獲知自己的速度、加速度、位置和方位角。

（2）車輛都有無線通信接口，通信距離為300～1 000 m，VANET為一個平面網(wǎng)絡(luò)。

（3）在VANET中車輛的能量被認為是不會耗盡的，且通信消耗的能量忽略不計。

蒸發(fā)法的原理是從液態(tài)轉(zhuǎn)化為氣態(tài)，利用產(chǎn)生的熱能將液體蒸發(fā)，最后再回收冷卻水蒸汽的方法，此種方法的優(yōu)勢是得到的淡水水質(zhì)較好。目前，海水脫鹽淡化技術(shù)經(jīng)過發(fā)展演化的蒸發(fā)法脫鹽技術(shù)被廣泛應用于工業(yè)生產(chǎn)中[15]。多效蒸餾法是一項20世紀中期重要的脫鹽技術(shù)，雖然工藝比較成熟并且運行穩(wěn)定，然而存在一些問題如能耗高、設(shè)備易腐蝕結(jié)垢等缺點[16]。20世紀70年代末,以色列研發(fā)了低溫多效蒸餾技術(shù)，有效緩解了多效蒸餾法的缺點[17]。利用多效蒸餾法可以獲得較大的產(chǎn)水量，但是高效率也代表著更高的單位產(chǎn)水量的成本和投資費用。郭衛(wèi)平[18]研究表明，對于成分復雜以及污染性強的污染物，不適合用膜法脫鹽處理。

（4）在VANET中，車輛通過周期性廣播的狀態(tài)信息（如位置、速度、加速度等）實現(xiàn)對周圍車輛的感知。

以上假設(shè)反映了VANET的本質(zhì)特性。

2 問題描述

某十字路口情形如圖1所示，虛線圈表示車輛的通信范圍，車輛1為源節(jié)點，車輛2為目的節(jié)點。在圖示時刻，車輛2即將左轉(zhuǎn)，進入與車輛1行駛公路垂直的公路；一方面，車輛1和車輛2之間可以進行通信，另一方面，可以借助車輛3作為轉(zhuǎn)發(fā)節(jié)點構(gòu)建更為穩(wěn)定的路由。但是由于信息傳遞時間很短，不需要構(gòu)建很穩(wěn)定的路由，所以車輛1可以直接向車輛2發(fā)送信息。

圖1 十字路口情形

某線狀公路情形如圖2所示，虛線圈表示車的通信范圍，車輛1為源節(jié)點，車輛n為目的節(jié)點，在圖示時刻，車輛1和2中間有很多車輛，但是車輛2處于車輛1通信范圍能覆蓋到的最遠的地方，車輛1和2之間建立的通信鏈路雖然不是很穩(wěn)定，但也能滿足通信的需求；同理可以選擇車輛3作為車輛2通信的下一車輛，依次傳遞，直到消息發(fā)送到車輛n，通信完成。通過這樣的方式構(gòu)建的路由雖然不是很穩(wěn)定，但是可以滿足通信的需求。

圖2 線狀公路情形

車輛位置動態(tài)路由如圖3所示。車輛1為源節(jié)點，車輛4為目的節(jié)點，2個虛線圈分別表示車輛1和2的通信范圍。當車輛1向車輛4發(fā)送數(shù)據(jù)時有路由1→2→3→4和1→2→4可以選擇。由圖3可知，車輛4在下一時刻即將駛離車輛2的通信范圍，但是考慮到不穩(wěn)定信道能滿足通信需求即可，鏈路1→2→4可以作為選擇。

在路由選擇中，將對網(wǎng)絡(luò)通信速度和信號衰減等進行評估，以上節(jié)點在計算理論可行的最大通信速率時，可能成為最優(yōu)的路由節(jié)點。在進行上述路由選擇時均未考慮需求所要持續(xù)的時間，僅僅選擇出一條可通信的路由。

圖3 車輛位置動態(tài)路由圖

GPSR－R算法綜合考慮車輛的行駛速度、相對位置、行車方位等來評估行車路由存活時間，根據(jù)目的節(jié)點發(fā)送數(shù)據(jù)的應用需求，依靠車間通信速率得到需求時間，建立GPSR路由改進算法。

3 VANET場景下的GPSR－R算法

3.1 GPSR路由協(xié)議

GPSR路由協(xié)議使用貪婪轉(zhuǎn)發(fā)算法建立路由。貪婪轉(zhuǎn)發(fā)算法是選擇鄰居節(jié)點中距離目的節(jié)點最近的作為下一跳路由轉(zhuǎn)發(fā)節(jié)點［8］。協(xié)議流程圖如圖4所示。

3.2 鄰居路由表更新策略

源車輛把Hello數(shù)據(jù)包預先傳遞給其一跳的鄰居車輛，一方面，移動車輛能追蹤每個車輛的位置，另一方面，數(shù)據(jù)包也告訴其在鄰居路由表中當前車輛的位置，這樣就能粗略地估計出中間鄰居車輛。

Hello數(shù)據(jù)包如圖5所示。

圖5 Hello數(shù)據(jù)包格式

數(shù)據(jù)包格式中，ID為車輛的ID號；X、Y為當前車輛所處平面中的坐標位置；vx、vy為車輛在X和Y方向上的速度；F為一個標志位；θx、θy分別為車輛行駛的方位角；r為車輛的通信半徑。

經(jīng)過時間t后，車輛準確的位置信息可以通過傳遞Hello數(shù)據(jù)包進行預測。如果同樣車輛的信息被接收，那么在同一時間對應數(shù)據(jù)包中位置信息將被更新。通過速度來估計周圍鄰居車輛在一段時間以后的位置，每一輛車都能確定在通信范圍內(nèi)可通信車輛的數(shù)量；如果一輛車當前位置在源車輛通信范圍內(nèi)未被找到，那么這輛車將不會成為一個鄰居車輛。

因此，該策略用Hello數(shù)據(jù)包來幫助源車輛和下一跳鄰居車輛預先進行信息交換?；趶腍ello數(shù)據(jù)包中獲取的信息，每個車輛都能定時更新它自身鄰居路由表中的信息。

3.3 GPSR－R算法的主要思想

GPSR－R算法是基于網(wǎng)絡(luò)需求的GPSR路由選擇算法，將每個車輛作為一個移動的節(jié)點，每個節(jié)點只維護其發(fā)射范圍內(nèi)的節(jié)點的位置、行駛速度、方位角信息；通過網(wǎng)絡(luò)收斂、貪婪轉(zhuǎn)發(fā)、路徑優(yōu)化進行篩選，并將節(jié)點通信時間與路由維護時間進行比較，自動選擇出只需滿足通信需求而對鏈路穩(wěn)定性要求不高的路由。

3.3.1 路由存活時間RMT計算模型

路由存活時間RMT（routing maintenance time）是指從源車輛1到目的車輛n的路由維護時間。假設(shè)每個節(jié)點對信號的傳輸能力相同，則任意2個相鄰節(jié)點的距離小于傳輸半徑時，都可以認為節(jié)點間是保持連接的。

如果考慮2輛車i和j（1≤i≤j≤n），它們的通信半徑為r，速度分別為vi和vj，位置分別為（xi，yi）和（xj，yj），速度的方位角分別為θi和θj，則這2輛車之間鏈路維護時間為：

3.3.2 節(jié)點間通信時間T計算模型

節(jié)點通信時間是指信息從1→n傳遞所需要的時間，主要包括由節(jié)點到下一跳發(fā)送所需的時間和在每一個路由節(jié)點上的等待時間；計算這2個時間，再將從節(jié)點1→2→…→n傳遞的時間片累加，即可得到總時間。

若T（i，j）表示數(shù)據(jù)從節(jié)點i→j傳輸所需的時間，S（i，j）表示數(shù)據(jù)在j點停留等待轉(zhuǎn)發(fā)的時間，則有：

其中，S（i，j）＝j(luò)中待傳輸數(shù)據(jù)堆棧長度×獲取時間片需要等待的時間／一次發(fā)送長度。

其中，G為數(shù)據(jù)包大小；C（i，j）為i→j的傳輸速率。

信道傳輸速率C＝W lb2（1＋SINR），SINR＝Pre／N0，W 為常量，SINR為信噪比，N0為無線通信中的固有噪聲，Pre為接收節(jié)點j收到i的信號強度。

時間片等待時間由于媒體接入方式不同而有所不同，如果對此時間評估，與實際情況嚴重不符。路由選擇上采用的是按需執(zhí)行，因此在每個節(jié)點開始承擔轉(zhuǎn)發(fā)任務(wù)時，可以估計到自己能夠得到的時間片的時間，再逐步累加進行預估，作為參考數(shù)據(jù)。

3.4 GPSR－R算法描述

GPSR－R路由查找采用以下步驟：

（1）在群體節(jié)點中，一定周期Δt內(nèi)進行一次位置更新。

（2）節(jié)點1向節(jié)點n發(fā)起一個服務(wù)請求，先發(fā)送RREQ路由請求數(shù)據(jù)包，請求信息中包含發(fā)起車輛的應用請求所需的通信時間T。

（3）節(jié)點1周圍的節(jié)點收到信息后，首先要判斷本節(jié)點是否轉(zhuǎn)發(fā)過此數(shù)據(jù)包，若未轉(zhuǎn)發(fā)過，則將下一節(jié)點設(shè)置為鄰居節(jié)點，同時將自身現(xiàn)在維持的鏈路堆棧信息加入RREQ數(shù)據(jù)包中，查找自己通信范圍內(nèi)的節(jié)點位置信息，將RREQ轉(zhuǎn)發(fā)給下一節(jié)點。

（4）當查找完成后，若節(jié)點1信息傳遞到節(jié)點n所需的通信時間T小于路由維護時間RMT，則選擇該路由；否則轉(zhuǎn)至步驟（1），直到RREQ發(fā)送到目標節(jié)點得到路由，做出回應。

在路由節(jié)點選擇方向上采用以下辦法進行初步判定：① 當前節(jié)點累計的傳輸速率已經(jīng)低于預定閾值比例a，停止轉(zhuǎn)發(fā)該請求；②當前節(jié)點與上一節(jié)點鏈路維護時間低于應用需求時間的，停止轉(zhuǎn)發(fā)該請求。

GPSR－R算法路由選擇中，當節(jié)點收到一個RREQ請求時，為了避免形成循環(huán)鏈路，需解包檢驗是否接收過此請求。

為了避免形成“空洞”，路由推進路徑如圖6所示。節(jié)點A收到RREQ數(shù)據(jù)包，目的節(jié)點為D；車A坐標為（0，0），R為A的無線通信范圍；收到轉(zhuǎn)發(fā)數(shù)據(jù)包的請求后，A向通信范圍內(nèi)的車輛發(fā)送轉(zhuǎn)發(fā)請求；B、F節(jié)點首先收到，B、F再次轉(zhuǎn)發(fā)時，需要做出判斷，如果鏈路F已經(jīng)處理過此請求信息，則F對B的轉(zhuǎn)發(fā)不做任何處理。

圖6 路由推進路徑示意圖

4 仿真實驗與結(jié)果分析

本文采用臺灣交通大學研制的NCTUns軟件，它將交通仿真和網(wǎng)絡(luò)仿真緊密耦合在一個模塊中，提供單一的車輛網(wǎng)絡(luò)環(huán)境［9］。對改進算法GPSR－R和GPSR路由算法以及GPSR－AD算法進行仿真實驗，為了更準確地說明本文所提出的路由改進算法的優(yōu)勢，在實驗過程中，選取車輛間的距離作為橫坐標，對其數(shù)據(jù)包傳遞成功率以及丟包率進行比較，實驗結(jié)果表明，本文改進算法的數(shù)據(jù)包傳遞率以及丟包率要優(yōu)于GPSR路由算法和GPSR－AD算法。

仿真場景為寬50 m、長3 000 m的公路，車輛移動速度范圍為20～30 m／s，MAC層協(xié)議為802.11，車輛通信覆蓋半徑為300 m，車輛節(jié)點數(shù)為1 000，要傳遞數(shù)據(jù)包大小為512 B，仿真時間為150 s。GPSR－R和 GPSR、GPSR－AD算法性能比較如圖7所示。

由圖7a可知，隨著車輛間距的增加，3種算法的數(shù)據(jù)包傳遞成功率均逐漸減小，GPSR－R算法的數(shù)據(jù)包傳遞成功率比GPSR和GPSR－AD算法下降得更為緩慢。這是因為GPSR具有貪婪轉(zhuǎn)發(fā)的特點，路由跳數(shù)相對較少，當距離增大以后，數(shù)據(jù)包傳遞的成功率就會顯著降低；GPSRAD考慮了距離和角度的關(guān)系，所以下降并沒有GPSR算法大；而GPSR－R則考慮了路由跳數(shù)較多的因素，通過算法的改進，減小因為距離增大而對數(shù)據(jù)包傳遞成功率的影響。

由圖7b可知，隨著車輛間距的增加，3種算法在丟包率方面均逐漸上升，GPSR－R的丟包率上升緩慢，而GPSR－AD和GPSR算法則上升較快。這是因為在長距離傳輸中，GPSR－R算法考慮了滿足傳輸需求的通道也可以作為傳輸信道，減少了路由開銷，提高了效率，使得丟包率上升并不明顯。

圖7 GPSR－R和 GPSR、GPSR－AD算法性能比較

5 結(jié)束語

針對GPSR協(xié)議應用于車聯(lián)網(wǎng)實際場景時因傳輸距離長而造成數(shù)據(jù)傳遞率下降的情形，本文提出了VANET場景下的GPSR路由改進算法GPSR－R。GPSR－R算法充分利用不穩(wěn)定但滿足需求的路由完成信息的傳遞。實驗結(jié)果表明，車輛間數(shù)據(jù)在長距離傳輸情形下，GPSR－R在數(shù)據(jù)包傳遞率、丟包率方面要優(yōu)于GPSR和GPSRAD。

［1］Fang S，Luo T.A novel two－timer－based broadcast routing algorithm for vehicular Ad－h(huán)oc Networks［C］／／International Conference on Green Computing and Communications（GreenCom）and IEEE Internet of Things（iThings）and IEEE Cyber，Physical and Social Computing（CPSCom），2013：1518－1522.

［2］Sou S I，Lee Y.SCB：store－carry－broadcast scheme for message dissemination in sparse VANET［C］／／Vehicular Technology Conference（VTC Spring），Yokohama，2012：1－5.

［3］Rak J.Providing differentiated levels of service availability in VANET communications［J］.Communications Letters，IEEE，2013，17（7）：1380－1383.

［4］胡小建，王景剛.云物流服務(wù)及其協(xié)作機制研究［J］.合肥工業(yè)大學學報：自然科學版，2014，37（5）：631－635.

［5］李道全，劉海燕，曹齊光，等.基于地理位置的路由算法：GPSR－AD［J］.計算機應用，2009，29（12）：3215－3217.

［6］Dhurandher S K，Misra S，Obaidat M S，et al.Efficient angular routing protocol for inter－vehicular communication in vehicular ad hoc networks［J］.Communications，IET，2010，4（7）：826－836.

［7］陳 振，韓江洪，劉征宇.基于VANET分簇的車輛碰撞警告信息傳輸［J］.電子測量與儀器學報，2013，27（5）：396－401.

［8］Kyunghwik K，Wonjun L.MBAL：a mobile beacon－assisted localization scheme for wireless sensor networks［C］／／Proceedings of 16th International Conference on Conputer Communications and Networks，2007：57－62.

［9］王麗娟，梁海濤，秦建敏，等.貪婪周邊無狀態(tài)路由轉(zhuǎn)發(fā)算法GPSR的分析及改進［J］.太原理工大學學報，2012，43（5）：587－590.

GPSR－R routing algorithm in VANET scenario

LI Chao1， HAN Jiang－h(huán)ong1，2， WEI Zhen－chun1，2， WEI Xing1，2

（1.School of Computer and Information，Hefei University of Technology，Hefei 230009，China；2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education，Hefei 230009，China）

Routing is a key technology of vehicular ad hoc networks（VANET）.VANET will not work without appropriate and efficient routing algorithm.Because the long－distance multi－h(huán)op routing is breakable，the communication link only need to satisfy the basic need of communication.In this paper，a GPSR－R routing algorithm in VANET scenario is proposed to make an improvement in GPSR routing protocol.GPSR－R takes comprehensive consideration of network requirements which is built up by the mobile nodes，and makes full advantage of routing which is unstable but can complete transmission of information.The simulation results show that GPSR－R does better than GPSR and GPSRAD in packet delivery rate and packet loss rate.

GPSR－R algorithm；basic need of communication；vehicular ad hoc networks（VANET）scenario

TP393.02

A

1003－5060（2015）02－0181－05

10.3969／j.issn.1003－5060.2015.02.009

2014－02－17；

2014－06－01

國家自然科學基金資助項目（61370088）；高等學校博士學科點專項科研基金資助項目（20100111110004）和安徽省自然科學基金資助項目（1208085QF113）

李 超（1990－），男，浙江金華人，合肥工業(yè)大學碩士生；

韓江洪（1954－），男，安徽合肥人，合肥工業(yè)大學教授，博士生導師.

（責任編輯 胡亞敏）