黃文靜

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074)

綜述與評(píng)論

自組織車(chē)聯(lián)網(wǎng)中GPSR路由協(xié)議的研究進(jìn)展

黃文靜

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074)

由于貪婪周邊無(wú)狀態(tài)路由(GPSR)對(duì)于拓?fù)浣Y(jié)構(gòu)頻繁變化的自組織車(chē)聯(lián)網(wǎng)(VANETs)具有最適性，為此，針對(duì)GPSR提出了許多改進(jìn)協(xié)議。首先對(duì)VANETs網(wǎng)絡(luò)層路由協(xié)議進(jìn)行分類(lèi)比較，然后分析和總結(jié)近年來(lái)基于位置路由協(xié)議的核心路由機(jī)制和優(yōu)缺點(diǎn)，重點(diǎn)分析典型的基于位置的路由協(xié)議GPSR在城市場(chǎng)景中存在的問(wèn)題。最后，提出了GPSR未來(lái)可能的研究策略和發(fā)展方向。

自組織車(chē)聯(lián)網(wǎng)； 路由協(xié)議； 貪婪周邊無(wú)狀態(tài)路由

0 引 言

近年來(lái)，由于無(wú)線(xiàn)網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展和交通智能化的需求，自組織車(chē)聯(lián)網(wǎng)(VANETs)這一專(zhuān)門(mén)為汽車(chē)間通信設(shè)計(jì)的自組織網(wǎng)絡(luò)受到了廣泛的關(guān)注。該網(wǎng)絡(luò)不僅有助于改善交通擁塞問(wèn)題，還能進(jìn)行緊急事件處理、輔助駕駛、交通信息共享、娛樂(lè)等。在VANETs發(fā)揮巨大作用的同時(shí)VANETs路由協(xié)議為其提供重要的數(shù)據(jù)通信支持，因此，路由協(xié)議很大程度上決定了VANETs的性能[1]?；诘乩砦恢秘澙分苓厽o(wú)狀態(tài)路由(GPSR)協(xié)議算法較為簡(jiǎn)單,不需要儲(chǔ)存維護(hù)路由表,網(wǎng)絡(luò)開(kāi)銷(xiāo)小,且對(duì)于車(chē)輛高速移動(dòng)的拓?fù)渚W(wǎng)絡(luò)具有更好的可擴(kuò)展性和適應(yīng)性。但是在城市交通環(huán)境應(yīng)用中，GPSR仍然存在很多不足和缺陷?？傊?，針對(duì)GPSR路由協(xié)議在城市交通環(huán)境下的研究是一個(gè)挑戰(zhàn)與機(jī)遇的共存的過(guò)程，受到了廣大學(xué)者的關(guān)注。

本文主要是對(duì)典型的VANETs層路由協(xié)議進(jìn)行歸納分類(lèi)，總結(jié)基于位置路由協(xié)議的優(yōu)缺點(diǎn)，并重點(diǎn)對(duì)基于位置的GPSR協(xié)議在城市交通環(huán)境下存在的問(wèn)題進(jìn)行分類(lèi)，同時(shí)指出可能研究的策略和未來(lái)發(fā)展方向，為GPSR協(xié)議在城市交通環(huán)境下的應(yīng)用研究提供廣闊的視角。

1 VANETs協(xié)議分類(lèi)

VANETs路由協(xié)議根據(jù)數(shù)據(jù)包目的節(jié)點(diǎn)數(shù)的不同可分為單播路由、廣播路由、多播路由三類(lèi),其具體分類(lèi)如圖1。單播路由協(xié)議是將數(shù)據(jù)包一對(duì)一地從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。目前，大體可分為基于拓?fù)涞穆酚蓞f(xié)議、基于位置的路由協(xié)議和基于電子地圖的路由協(xié)議三類(lèi)。早期的自組織網(wǎng)絡(luò)路由基本上都是基于拓?fù)涞穆酚蓞f(xié)議，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)周期性地交互信息得到其他節(jié)點(diǎn)的信息，進(jìn)而轉(zhuǎn)發(fā)數(shù)據(jù)包。這類(lèi)路由協(xié)議大體可以分為先應(yīng)式、反應(yīng)式和混合式路由協(xié)議。先應(yīng)式路由中無(wú)論當(dāng)前是否要求通信，每個(gè)節(jié)點(diǎn)都會(huì)周期性地廣播路由分組、交換路由信息、維護(hù)路由表。典型的先應(yīng)式路由代表是DSDV協(xié)議。相對(duì)于先應(yīng)式路由，按需路由協(xié)議根據(jù)源節(jié)點(diǎn)是否需要獲得目的節(jié)點(diǎn)路由才進(jìn)行洪泛廣播請(qǐng)求分組，因此，降低了路由開(kāi)銷(xiāo)。按需路由協(xié)議的典型代表是AODV，DSR。文獻(xiàn)[2]中通過(guò)對(duì)3種路由協(xié)議(DSDV,AOMDV,AODV)在搭建的真實(shí)場(chǎng)景中進(jìn)行仿真和性能分析，得到DSDV這類(lèi)先應(yīng)式路由協(xié)議周期性地廣播信息，占用帶寬過(guò)多，影響數(shù)據(jù)的傳輸，而AODV使用洪泛發(fā)現(xiàn)路由將產(chǎn)生大量的冗余，對(duì)于規(guī)模越大的網(wǎng)絡(luò)，冗余現(xiàn)象越明顯。因此，效果良好的傳統(tǒng)自組織網(wǎng)路由協(xié)議不一定適宜拓?fù)漕l繁變化的VANETs。

圖1 VANETs路由協(xié)議分類(lèi)Fig 1 Classification of VANETs routing protocol

與傳統(tǒng)的自組織路由協(xié)議相比，基于位置的路由協(xié)議不需要儲(chǔ)存和維護(hù)路由，節(jié)點(diǎn)利用GPS等方法獲取自己的位置，通過(guò)“位置服務(wù)”和分組轉(zhuǎn)發(fā)策略來(lái)獲取信宿節(jié)點(diǎn)的位置和選擇下一跳。針對(duì)高速移動(dòng)的城市場(chǎng)景，基于位置的路由協(xié)議具有較好的性能。其中基于位置路由協(xié)議的典型代表是由Karp Brad, Kung H T 于2000年提出的GPSR協(xié)議[3],該協(xié)議初始化是根據(jù)貪婪法則轉(zhuǎn)發(fā)數(shù)據(jù)包，當(dāng)貪婪轉(zhuǎn)發(fā)陷入局部?jī)?yōu)化時(shí)采用邊界轉(zhuǎn)發(fā)。文獻(xiàn)[4]對(duì)GPSR基于NS3進(jìn)行深入的研究分析，并分別對(duì)貪婪模型和恢復(fù)模型進(jìn)行仿真，驗(yàn)證該算法確實(shí)能夠選擇正確的路徑。文獻(xiàn)[5]提出了通過(guò)計(jì)算源、目的節(jié)點(diǎn)之間的距離，根據(jù)Dijkstra算法選擇最小路徑的路由協(xié)議GSR。雖然GSR減少了網(wǎng)絡(luò)開(kāi)銷(xiāo)和路徑，但是沒(méi)有考慮實(shí)際的交通環(huán)境中的速度和車(chē)流密度。Lochert C，Mauve M 于2005年提出了改進(jìn)的GPCR[6],該協(xié)議將GPSR的貪婪轉(zhuǎn)發(fā)方式改進(jìn)為受限的貪婪轉(zhuǎn)發(fā)，當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)現(xiàn)轉(zhuǎn)發(fā)方向存在節(jié)點(diǎn)處于十字路口時(shí)，直接將數(shù)據(jù)包轉(zhuǎn)發(fā)給該節(jié)點(diǎn)，而不執(zhí)行貪婪轉(zhuǎn)發(fā)；反之，仍然進(jìn)行貪婪轉(zhuǎn)發(fā)。雖然GPCR更適應(yīng)于城市交通環(huán)境，具有較高的交付率，但是路徑和延遲有所增加。Seet B C，Liu G等人在2004年提出的A-STAR路由協(xié)議為每條路徑分配一個(gè)與公交線(xiàn)路數(shù)量呈反比的權(quán)值，根據(jù)Dijkstra算法選擇最短路徑，當(dāng)出現(xiàn)局部?jī)?yōu)化時(shí)，重新計(jì)算新的最短路徑和地理標(biāo)識(shí)該點(diǎn)不參與計(jì)算。該協(xié)議在選擇路徑時(shí)參考了車(chē)輛密度因素，提高了數(shù)據(jù)投遞率，但是這里的車(chē)輛密度是統(tǒng)計(jì)值而不是實(shí)時(shí)的，因此，不具有實(shí)時(shí)性和準(zhǔn)確性[7]。針對(duì)A-STAR實(shí)時(shí)性差的問(wèn)題進(jìn)行改進(jìn)提出了GyTAR路由協(xié)議，根據(jù)各個(gè)路段實(shí)時(shí)車(chē)流密度選取路徑，進(jìn)而通過(guò)速度向量預(yù)測(cè)下一跳的位置進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)包。該協(xié)議有效地解決了實(shí)時(shí)性問(wèn)題，而且進(jìn)一步提高了數(shù)據(jù)投遞率，但是對(duì)外界提高車(chē)流信息服務(wù)要求較高，較適宜于城市場(chǎng)景[8，9]?；谖恢玫穆酚蓞f(xié)議的分析比較如表1。

根據(jù)VANETs的網(wǎng)絡(luò)特點(diǎn)，未來(lái)的VANETs路由協(xié)議的方向應(yīng)該是位置與電子地圖相結(jié)合的基于地圖的路由協(xié)議，根據(jù)電子地圖獲取整個(gè)網(wǎng)絡(luò)的交通情況做出合理、高效的路由選擇。

表1 VANETs基于地理位置路由協(xié)議的分析比較Tab 1 Analysis and comparison of routing protocol based on geographic location for VANETs

2 城市交通環(huán)境下GPSR協(xié)議存在問(wèn)題

基于位置的典型路由協(xié)議GPSR使用地理位置信息，通過(guò)貪婪算法獲得局部最優(yōu)解，同時(shí)采用邊界轉(zhuǎn)發(fā)機(jī)制來(lái)解決貪婪算法引起的最佳主機(jī)問(wèn)題，其主要流程如圖2。

圖2 GPSR流程圖Fig 2 Flow chart of GPSR

雖然GPSR協(xié)議具有算法簡(jiǎn)單、不需要儲(chǔ)存和維護(hù)路由表開(kāi)銷(xiāo)小等優(yōu)點(diǎn)，但是在城市交通環(huán)境中仍然存在著一些問(wèn)題。針對(duì)基于位置典型的GPSR協(xié)議存在的問(wèn)題，國(guó)內(nèi)外學(xué)者都提出的一些相應(yīng)的改進(jìn)方案。

2.1 解決空洞問(wèn)題時(shí)右手法則開(kāi)銷(xiāo)大

在遇到空洞問(wèn)題時(shí)，GPSR協(xié)議會(huì)啟動(dòng)邊界轉(zhuǎn)發(fā)模式，根據(jù)右手法則會(huì)出現(xiàn)盲目繞路和三角形問(wèn)題。文獻(xiàn)[10]提出了分段貪婪路由算法，該算法選取一個(gè)與目標(biāo)節(jié)點(diǎn)之間直接貪婪可達(dá)的節(jié)點(diǎn)作為一個(gè)中間目標(biāo)節(jié)點(diǎn)，不斷迭代直到找到某個(gè)中間節(jié)點(diǎn)使得源節(jié)點(diǎn)到該中間目標(biāo)節(jié)點(diǎn)之間是直接貪婪可達(dá)的。它克服了周邊轉(zhuǎn)發(fā)引起的繞路和三角形問(wèn)題，減少了路由和開(kāi)銷(xiāo)。文獻(xiàn)[11]提出了一種新的路由協(xié)議，該協(xié)議將每個(gè)路段分成不同的塊并在每個(gè)交叉路口設(shè)置錨點(diǎn)，當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)當(dāng)前路徑上存在空洞則通過(guò)錨點(diǎn)選擇剩下塊中相對(duì)目的節(jié)點(diǎn)最近的塊內(nèi)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，在塊內(nèi)則根據(jù)節(jié)點(diǎn)的速度和位置選擇下一跳，它同時(shí)解決了空洞問(wèn)題和鏈路穩(wěn)定的問(wèn)題。針對(duì)右手法則開(kāi)銷(xiāo)大，文獻(xiàn)[12]提出了雙手法則，該法則分別根據(jù)左手和右手選擇2個(gè)節(jié)點(diǎn)，若兩節(jié)點(diǎn)是同一節(jié)點(diǎn)，則直接轉(zhuǎn)發(fā)給該節(jié)點(diǎn)；否則，選擇距離目的節(jié)點(diǎn)近的節(jié)點(diǎn)作為下一跳。針對(duì)文獻(xiàn)[12]在處理空洞問(wèn)題采取左、右手法則引起的繞路和開(kāi)銷(xiāo)較大問(wèn)題，提出了基于節(jié)點(diǎn)權(quán)重的機(jī)制，該機(jī)制通過(guò)選擇由該節(jié)點(diǎn)的距離、丟包率和轉(zhuǎn)發(fā)成功率共同決定的節(jié)點(diǎn)權(quán)重值大的作為下一跳。雖然該機(jī)制提高了交付率，但計(jì)算量太大，需要的信息繁多[13]。文獻(xiàn)[14]提出了另一種解決問(wèn)題的思想，在面對(duì)空洞問(wèn)題時(shí)不是立即平面化采用邊界轉(zhuǎn)發(fā)，而是將節(jié)點(diǎn)退回前一個(gè)轉(zhuǎn)發(fā)點(diǎn)在剩下的節(jié)點(diǎn)中重新選擇下一跳，直至沒(méi)有遇到空洞。

2.2 自適應(yīng)性差

針對(duì)GPSR在不同場(chǎng)景中無(wú)法采取正確的轉(zhuǎn)發(fā)模式導(dǎo)致數(shù)據(jù)包丟失的問(wèn)題，文獻(xiàn)[15]根據(jù)車(chē)流密度自適應(yīng)采取不同轉(zhuǎn)發(fā)機(jī)制，在稀疏模式下，容易出現(xiàn)空洞問(wèn)題，從而采用基于穩(wěn)定的路由協(xié)議機(jī)制。文獻(xiàn)[16]根據(jù)格林布爾茨的速度—密度線(xiàn)性關(guān)系式，通過(guò)計(jì)算車(chē)輛的平均速度得到實(shí)時(shí)車(chē)流量密度信息，從而選擇最佳路徑?；谧赃m應(yīng)選路策略的VANETs路由協(xié)議ASVP[17]針對(duì) VANETs的鏈路頻斷性，提出了一種自適應(yīng)路由協(xié)議,該協(xié)議引入攜帶—轉(zhuǎn)發(fā)機(jī)制使協(xié)議能夠適用于間歇性連接的延遲容忍網(wǎng)絡(luò)，通過(guò)對(duì)道路模型分析計(jì)算，獲得路段連通性度量指標(biāo)用于選取最優(yōu)路徑。

2.3 容錯(cuò)性差

文獻(xiàn)[18]提到GPSR協(xié)議是在假設(shè)每個(gè)節(jié)點(diǎn)都是無(wú)故障的情況下，但是在實(shí)際交通情況下是不可能的，而容錯(cuò)處理有助于減少能量消耗、維持穩(wěn)定路徑。因此，針對(duì)GPSR協(xié)議進(jìn)行了改進(jìn)，得到了EFGPSR，該協(xié)議主要分為錯(cuò)誤檢測(cè)、平面化、高效貪婪轉(zhuǎn)發(fā)和高效周邊轉(zhuǎn)發(fā)4個(gè)階段。改進(jìn)的協(xié)議在網(wǎng)絡(luò)壽命、成功交付率方面都有所改善。文獻(xiàn)[19]介紹的故障容錯(cuò)能提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的穩(wěn)定性和可靠性，并總結(jié)網(wǎng)絡(luò)層容錯(cuò)技術(shù)主要分為多路由傳輸、糾刪編碼/網(wǎng)絡(luò)編碼、數(shù)據(jù)重傳機(jī)制、跨層協(xié)同優(yōu)化與復(fù)合容錯(cuò)和仿生智能容錯(cuò)等。文獻(xiàn)[20]指出引起鏈路斷裂的因素主要有鄰居節(jié)點(diǎn)位置不定移動(dòng)出了傳播范圍或者中間節(jié)點(diǎn)出現(xiàn)故障。而目前針對(duì)鏈路斷裂的處理方法包括計(jì)算鏈路穩(wěn)定度、多條路徑等。針對(duì)大多數(shù)基于穩(wěn)定的路由算法都沒(méi)有考慮對(duì)節(jié)點(diǎn)的保護(hù)，本文提出了一種將節(jié)點(diǎn)和鏈路保護(hù)相結(jié)合提高穩(wěn)定度的多路徑節(jié)點(diǎn)保護(hù)路由協(xié)議GBR-NP。該協(xié)議在貪婪后備路由協(xié)議的基礎(chǔ)上增加了節(jié)點(diǎn)保護(hù)，每一個(gè)節(jié)點(diǎn)在原路徑中繞過(guò)出現(xiàn)故障的節(jié)點(diǎn)生成新的后備路徑。

2.4 無(wú)法感知障礙物

在真實(shí)的城市交通場(chǎng)景中，存在著大量的建筑物和樹(shù)木等障礙物，然而GPSR協(xié)議沒(méi)有障礙物感知能力，仍然根據(jù)固有的機(jī)制轉(zhuǎn)發(fā)數(shù)據(jù)包，導(dǎo)致數(shù)據(jù)包無(wú)法成功發(fā)送。如圖3所示，源節(jié)點(diǎn)S要向目的節(jié)點(diǎn)D發(fā)送數(shù)據(jù)包，根據(jù)貪婪轉(zhuǎn)發(fā)S先把數(shù)據(jù)包轉(zhuǎn)發(fā)給A，由于存在障礙物,A將無(wú)法轉(zhuǎn)發(fā)數(shù)據(jù)包給D，導(dǎo)致轉(zhuǎn)發(fā)失敗。

圖3 無(wú)法感知障礙物效果圖Fig 3 Effect diagram of lack of obstacle-aware ability

文獻(xiàn)[21]中指出在真實(shí)城市場(chǎng)景中存在著障礙物和受限的道路，而大多數(shù)移動(dòng)模型節(jié)點(diǎn)都是自由移動(dòng)的，因此不適宜真實(shí)場(chǎng)景的仿真。針對(duì)這一問(wèn)題，作者提出了一種新的基于錨點(diǎn)的移動(dòng)模型(AMM)，該模型將錨點(diǎn)設(shè)置在障礙物每個(gè)凸面的角落，這樣就能形成一個(gè)曲線(xiàn)圖，節(jié)點(diǎn)可以通過(guò)選擇任意的錨點(diǎn)作為下一跳。通過(guò)將GPSR協(xié)議在AMM中進(jìn)行仿真得到該模型更接近于真實(shí)場(chǎng)景，得到的仿真數(shù)據(jù)更有效，但該方法需要大量外界硬件的支持。文獻(xiàn)[22]設(shè)計(jì)了一種躲避障礙物的分布式地理路由算法GRdo，在使用該算法前，首先提出一種建立虛擬坐標(biāo)的方法并引入可見(jiàn)圖，通過(guò)該圖輔助路由沿著障礙物的凸點(diǎn)建立路徑?jīng)Q策，通過(guò)該方法能夠較準(zhǔn)確地判斷兩點(diǎn)之間是否存在障礙物并以較短的路徑繞開(kāi)障礙物。針對(duì)文獻(xiàn)[21，22]需要大量的外界硬件支持，以及建立虛擬坐標(biāo)較復(fù)雜等問(wèn)題，文獻(xiàn)[23]提出了將障礙物的信息設(shè)置在路網(wǎng)屬性中，根據(jù)障礙物的坐標(biāo)和兩節(jié)點(diǎn)連接之間是否存在交點(diǎn)，即可感知節(jié)點(diǎn)之間是否存在障礙物，進(jìn)而根據(jù)障礙物的障礙度與閾值比較判斷是否轉(zhuǎn)發(fā)數(shù)據(jù)包。該算法能夠使協(xié)議更適應(yīng)真實(shí)的城市場(chǎng)景，但門(mén)限值的選取有一定難度。

2.5 節(jié)點(diǎn)位置不定和分布不均引起的鏈路斷裂問(wèn)題

GPSR協(xié)議中每個(gè)數(shù)據(jù)分組中都攜帶一個(gè)被稱(chēng)作標(biāo)志位的位置信息，用M表示。在數(shù)據(jù)從源節(jié)點(diǎn)向目的節(jié)點(diǎn)傳遞過(guò)程中，目的節(jié)點(diǎn)的位置信息始終保持不變同時(shí)轉(zhuǎn)發(fā)給每個(gè)中間節(jié)點(diǎn)，而在這個(gè)過(guò)程中VANETs中的目的節(jié)點(diǎn)是移動(dòng)的。因此，每個(gè)中間節(jié)點(diǎn)可能是按照錯(cuò)誤的目的節(jié)點(diǎn)位置進(jìn)行轉(zhuǎn)發(fā)，導(dǎo)致數(shù)據(jù)包丟失。

如圖4(a)所示，S是源節(jié)點(diǎn)，D是目的節(jié)點(diǎn)，A,B,C都在S的通信范圍內(nèi)，根據(jù)GPSR路由協(xié)議的貪婪法則，S節(jié)點(diǎn)應(yīng)該選擇A節(jié)點(diǎn)作為下一跳。由于在VANETs中，每個(gè)節(jié)點(diǎn)都在移動(dòng)，且方向和速度不同，在更新鄰居節(jié)點(diǎn)表的時(shí)間段里，節(jié)點(diǎn)的位置發(fā)生了劇烈的變化。如圖4(b)，B已經(jīng)移動(dòng)出S的通信范圍，A,C雖然仍在通信范圍內(nèi)，但A不斷遠(yuǎn)離目的節(jié)點(diǎn)D。如果仍然堅(jiān)持選擇A作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，那么成功轉(zhuǎn)發(fā)的幾率就會(huì)大大降低。文獻(xiàn)[24]針對(duì)GPSR協(xié)議中貪婪轉(zhuǎn)發(fā)選擇離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)作為下一跳，當(dāng)選擇好下一跳準(zhǔn)備轉(zhuǎn)發(fā)時(shí)，該節(jié)點(diǎn)已經(jīng)運(yùn)動(dòng)出了源節(jié)點(diǎn)的轉(zhuǎn)發(fā)范圍，導(dǎo)致數(shù)據(jù)包丟失的問(wèn)題,即鄰居無(wú)線(xiàn)鏈路斷裂(neighbor wireless link break,NWLB)，提出影響NWLB的網(wǎng)絡(luò)因素有間隔時(shí)間、節(jié)點(diǎn)運(yùn)動(dòng)速度、網(wǎng)絡(luò)密度、節(jié)點(diǎn)轉(zhuǎn)發(fā)范圍和網(wǎng)絡(luò)的大小。綜合上述因素，文中基于GPSR提出了一種NWLBP預(yù)測(cè)模型，該模型對(duì)端到端延遲和丟包率有很大的改善。但是該模型沒(méi)有考慮運(yùn)動(dòng)方向，加速度對(duì)NWLB問(wèn)題的影響。文獻(xiàn)[25]在文獻(xiàn)[24]的基礎(chǔ)上提出了將車(chē)流速度、移動(dòng)方向、車(chē)輛密度的加入選擇下一跳的影響因素，針對(duì)車(chē)輛的運(yùn)動(dòng)方向和速度設(shè)置優(yōu)先權(quán)，并在具有優(yōu)先權(quán)的節(jié)點(diǎn)中根據(jù)距離和速度概率選擇下一跳從而減少NWLB問(wèn)題。文獻(xiàn)[26]通過(guò)鏈路穩(wěn)定性地進(jìn)行路由決策，它首先根據(jù)鄰居節(jié)點(diǎn)的成功交付率選擇交付率較高的作為候選節(jié)點(diǎn)，再跟據(jù)節(jié)點(diǎn)的方向和所處的狀態(tài)是靜止還是移動(dòng)選擇下一跳。該方法能夠有效地提高數(shù)據(jù)包的成功交付率，但是計(jì)算每一個(gè)鄰居節(jié)點(diǎn)的交付率工作量太大，特別是在拓?fù)渥兓l繁和車(chē)流密集的情況下。文獻(xiàn)[27]提出了一種新的基于鏈路生存時(shí)間選擇下一跳的方法，該方法與文獻(xiàn)[26]的不同在于，它根據(jù)節(jié)點(diǎn)位置和速度方向與大小的信息計(jì)算出鏈路的生存時(shí)間，并通過(guò)選擇由加權(quán)的生存時(shí)間和中間節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的距離綜合決定的度量值大的作為下一跳進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)包。文獻(xiàn)[28]介紹到車(chē)輛流密度小，表明區(qū)域速度高，拓?fù)渥兓l繁容易產(chǎn)生NWLB問(wèn)題。因此，提出了一種改進(jìn)的貪婪轉(zhuǎn)發(fā)路由協(xié)議，該協(xié)議根據(jù)車(chē)流密度大小選擇距離遠(yuǎn)、中、近三區(qū)域中的鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，也就是車(chē)流密度大(小)就選遠(yuǎn)(近)區(qū)域中鄰居節(jié)點(diǎn)。

圖4 鏈路斷裂效果圖Fig 4 Effect diagram of link break

3 結(jié)束語(yǔ)

結(jié)合國(guó)內(nèi)外對(duì)GPSR協(xié)議的改進(jìn)研究現(xiàn)狀，存在的主要問(wèn)題有以下幾個(gè)方面：

1) 目前許多研究把引起鏈路斷裂的主要因素歸結(jié)于節(jié)點(diǎn)位置不定和節(jié)點(diǎn)分布不均勻，忽略了障礙物的阻擋因素。

2)對(duì)于鏈路斷裂這個(gè)問(wèn)題，大多解決策略忽略了影響鏈路斷裂的根本因素到底是速度方向、速度大小還是車(chē)流密度，而是一味地將方向作為首要因素選擇下一跳。

3)目前，解決無(wú)法感知障礙物的方法往往計(jì)算量較大且需要外接硬件支持，在此基礎(chǔ)上基于障礙物的路徑選擇計(jì)算繁雜，不適用于真實(shí)場(chǎng)景。

4)許多路由協(xié)議的仿真車(chē)輛運(yùn)動(dòng)模型過(guò)于簡(jiǎn)單，試驗(yàn)場(chǎng)景和現(xiàn)實(shí)場(chǎng)景之間的巨大差異可能導(dǎo)致路由協(xié)議的失效，路由協(xié)議的實(shí)驗(yàn)仿真平臺(tái)還有待進(jìn)一步研究和開(kāi)發(fā)。

理想的路由協(xié)議的應(yīng)該具有以下幾個(gè)方面：算法簡(jiǎn)單、自適應(yīng)能力強(qiáng)、控制開(kāi)銷(xiāo)少、普適度高、時(shí)延小。通過(guò)對(duì)當(dāng)前各類(lèi)協(xié)議的分析比較，基于位置的路由協(xié)議對(duì)于VANETs頻繁變化的拓?fù)浣Y(jié)構(gòu)具有最適性。而其中典型的路由協(xié)議GPSR具有算法簡(jiǎn)單、開(kāi)銷(xiāo)小等優(yōu)點(diǎn)，但在城市交通環(huán)境下仍存在著一些缺陷，對(duì)于它的普遍應(yīng)用有一定阻礙作用。因此，針對(duì)其存在的問(wèn)題進(jìn)行改進(jìn)設(shè)計(jì)高性能的GPSR是一個(gè)研究的重點(diǎn)。目前，許多國(guó)內(nèi)外學(xué)者針對(duì)GPSR不足進(jìn)行單一的改進(jìn)，而沒(méi)有根據(jù)其不足進(jìn)行綜合有效地改進(jìn)，因此，在真實(shí)場(chǎng)景中改進(jìn)的效果往往差強(qiáng)人意。總的來(lái)說(shuō)，GPSR在VANETs中的有效應(yīng)用仍在研究階段，仍然有很多問(wèn)題亟需解決，許多新的研究課題有待發(fā)現(xiàn)。

[1] 徐會(huì)彬, 夏 超.VANETs路由綜述[J].計(jì)算機(jī)應(yīng)用研究,2013 (30):1-6.

[2] Vidhale B,Dorle S S.Performance analysis of routing protocols in realistic environment for vehicular Ad Hoc networks[C]∥Proceedings of 2011 21st International Conference on Systems Engineering (ICSEng),2011:267-272.

[3] Karp Brad,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceedings of the Annual International Conference on Mobile Computing and Networking,2000:243-254.

[4] Fonseca António,Cam?es André.Geographical routing implementation in NS3[C]∥Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques,2012:353-358.

[5] Lochert C,Hartenstein H.A routing strategy for vehicular Ad Hoc networks in city environment[C]∥Proceedings of IEEE Intelligent Vehicles Symposium,2003:156-161.

[6] Lochert C,Mauve M.Geographic routing in city scenarios[J].ACM SIGMOBILE Mobile Computing and Computing and Communications Review,2005(1):69-72.

[7] Seet Boon Chong,Liu Genping,Lee Bu Sung,et al.A-STAR:A mobile Ad Hoc routing strategy for metropolis vehicular communications[J].Lecture Notes in Computer Science,2004 (3042):989-999.

[8] Jerbi M,Meraihi R.GyTAR：Improved greedy traffic aware routing protocol for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Network,2006:88-89.

[9] Yang Q,Lim A.ACAR ：Adaptive connectivity aware routing protocol for vehicular Ad Hoc networks[C]∥Proceedings of 17th International Conference on Computer Communications and Networks,2008:1-9.

[10] 喻 嘉,聞?dòng)⒂?趙 宏.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中分段貪婪地理路由算法[J].控制與決策,2011(2):196-206.

[11] Kim Jung Hun,Lee Su Kyoung.Reliable routing protocol for vehicular Ad Hoc networks[J].International Journal of Electronics and Communications，2011 (65):268-271.

[12] Lai Liangli,Wang Qianping.Research on one kind of improved GPSR algorithm[C]∥International Conference on Computer Science and Electronics Engineering,2012:715-718.

[13] Xu Huibin,Zhou Lijie.An improved greedy perimeter stateless routing protocol for VANETs[J].International Journal of Advancements in Computing Technology (IJACT),2012(4):442-448.

[14] Wang Lijuan,Liang Haitao.Research and improvement of the wireless sensor network routing algorithm GPSR[J].Computer Society,2012(22):83-86.

[15] 錢(qián) 釗,劉宏偉,左德承,等.移動(dòng)自組網(wǎng)中基于位置信息的路徑優(yōu)化路由算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2013(3):345-349.

[16] 李 新,吳學(xué)文.一種基于實(shí)時(shí)車(chē)流密度信息的VANET路由協(xié)議[J].電子設(shè)計(jì)工程,2013(9):69-72.

[17] 王美琛,唐 倫.基于自適應(yīng)選路策略的VANETs路由協(xié)議[J].計(jì)算機(jī)應(yīng)用于軟件,2013(30):62-66.

[18] Jaiswal Jyotsana,Khilar Pabitra Mohan.Energy efficient and fault tolerant GPSR in Ad Hoc wireless network[J].Trends in Computer Science,Engineering and Information Technology Communications in Computer and Information Science,2011(204):683-692.

[19] 李洪兵,熊慶宇.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中網(wǎng)絡(luò)層故障容錯(cuò)技術(shù)研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2013 (7):1921-1928.

[20] Zadin bedalmotaleb,Fevens Thomas.Maintaining path stability with node failure in mobile Ad Hoc networks[J].Procedia Computer Science,2013 (19):1068-1073.

[21] Ahmed Sabbir,Karmakar Gour C.An environment-aware mobility model for wireless Ad Hoc network[J].Computer Networks,2010(54):1470-1489.

[22] 李金寶,郭曉行,張守娟.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中一種躲避障礙物的地理路由算法[J].黑龍江大學(xué)工程學(xué)報(bào),2010(1):97-103.

[23] 張 帆.城市場(chǎng)景下車(chē)載自組網(wǎng)中GPSR路由協(xié)議的研究[D].長(zhǎng)春：吉林大學(xué),2011.

[24] Alsaqour Raed A,Abdelhaq Maha S.Effect of network parameters on neighbor wireless link breaks in GPSR protocol and enhancement using mobility prediction model[J].Wireless Communications and Networking,2012 (171):1-15.

[25] Hu Lili,Ding Zhizhong,Shi Huijing.An improved GPSR routing strategy in VANET[C]∥2012 8th International Conference on Wireless Communications,Networking and Mobile Computing,2012:1-4.

[26] Wang Hao,Tan Guozhen,Yang Jixiang.An improved VANET intelligent forward decision-making routing algorithm[J].Journal of Networks,2012 (7):1546-1553.

[27] Noureddine Hadi,Ni Qiang,Min Geyong,et al.A new link lifetime estimation method for greedy and contention-based routing in mobile Ad Hoc networks[J].Telecommunication Systems,2013(69):269-284.

[28] Wen Huaqing,Rhee Kyung Hyune.An improved greedy forwar-ding routing protocol for cooperative VANETs[J].Information and Communication Technology Lecture Notes in Computer Science,2013 (7804):502-506.

Research progress of GPSR routing protocol in VANETs

HUANG Wen-jing

(School of Information Science & Engineering，Chongqing Jiaotong University，Chongqing 400074，China)

Because greedy perimeter stateless routing(GPSR) adapts to frequent changes of topological structure，many improved GPSR routing protocol are presented aiming at VANETs.Firstly, classify and compare network layer routing protocol in VANETs.Then,analyze and summarize core routing scheme of routing protocol based on position and advantages and disadvantages,analyze existing problems of typical GPSR based on position in cityscape.Finally, present research strategy and development directions of GPSR in future.

VANETs； routing protocol； GPSR

2014—01—14

TN 919.2

A

1000—9787(2014)04—0001—05

黃文靜(1989-)，女，重慶人，碩士研究生，研究方向?yàn)閷拵o(wú)線(xiàn)網(wǎng)絡(luò)。