自組織車聯網中GPSR路由協議的研究進展

黃文靜

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

綜述與評論

自組織車聯網中GPSR路由協議的研究進展

黃文靜

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

由于貪婪周邊無狀態路由(GPSR)對于拓撲結構頻繁變化的自組織車聯網(VANETs)具有最適性，為此，針對GPSR提出了許多改進協議。首先對VANETs網絡層路由協議進行分類比較，然后分析和總結近年來基于位置路由協議的核心路由機制和優缺點，重點分析典型的基于位置的路由協議GPSR在城市場景中存在的問題。最后，提出了GPSR未來可能的研究策略和發展方向。

自組織車聯網； 路由協議； 貪婪周邊無狀態路由

0 引 言

近年來，由于無線網絡技術的迅猛發展和交通智能化的需求，自組織車聯網(VANETs)這一專門為汽車間通信設計的自組織網絡受到了廣泛的關注。該網絡不僅有助于改善交通擁塞問題，還能進行緊急事件處理、輔助駕駛、交通信息共享、娛樂等。在VANETs發揮巨大作用的同時VANETs路由協議為其提供重要的數據通信支持，因此，路由協議很大程度上決定了VANETs的性能[1]。基于地理位置貪婪周邊無狀態路由(GPSR)協議算法較為簡單,不需要儲存維護路由表,網絡開銷小,且對于車輛高速移動的拓撲網絡具有更好的可擴展性和適應性。但是在城市交通環境應用中，GPSR仍然存在很多不足和缺陷。總之，針對GPSR路由協議在城市交通環境下的研究是一個挑戰與機遇的共存的過程，受到了廣大學者的關注。

本文主要是對典型的VANETs層路由協議進行歸納分類，總結基于位置路由協議的優缺點，并重點對基于位置的GPSR協議在城市交通環境下存在的問題進行分類，同時指出可能研究的策略和未來發展方向，為GPSR協議在城市交通環境下的應用研究提供廣闊的視角。

1 VANETs協議分類

VANETs路由協議根據數據包目的節點數的不同可分為單播路由、廣播路由、多播路由三類,其具體分類如圖1。單播路由協議是將數據包一對一地從源節點轉發到目的節點。目前，大體可分為基于拓撲的路由協議、基于位置的路由協議和基于電子地圖的路由協議三類。早期的自組織網絡路由基本上都是基于拓撲的路由協議，網絡中的節點通過周期性地交互信息得到其他節點的信息，進而轉發數據包。這類路由協議大體可以分為先應式、反應式和混合式路由協議。先應式路由中無論當前是否要求通信，每個節點都會周期性地廣播路由分組、交換路由信息、維護路由表。典型的先應式路由代表是DSDV協議。相對于先應式路由，按需路由協議根據源節點是否需要獲得目的節點路由才進行洪泛廣播請求分組，因此，降低了路由開銷。按需路由協議的典型代表是AODV，DSR。文獻[2]中通過對3種路由協議(DSDV,AOMDV,AODV)在搭建的真實場景中進行仿真和性能分析，得到DSDV這類先應式路由協議周期性地廣播信息，占用帶寬過多，影響數據的傳輸，而AODV使用洪泛發現路由將產生大量的冗余，對于規模越大的網絡，冗余現象越明顯。因此，效果良好的傳統自組織網路由協議不一定適宜拓撲頻繁變化的VANETs。

圖1 VANETs路由協議分類Fig 1 Classification of VANETs routing protocol

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

根據VANETs的網絡特點，未來的VANETs路由協議的方向應該是位置與電子地圖相結合的基于地圖的路由協議，根據電子地圖獲取整個網絡的交通情況做出合理、高效的路由選擇。

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

2 城市交通環境下GPSR協議存在問題

基于位置的典型路由協議GPSR使用地理位置信息，通過貪婪算法獲得局部最優解，同時采用邊界轉發機制來解決貪婪算法引起的最佳主機問題，其主要流程如圖2。

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

雖然GPSR協議具有算法簡單、不需要儲存和維護路由表開銷小等優點，但是在城市交通環境中仍然存在著一些問題。針對基于位置典型的GPSR協議存在的問題，國內外學者都提出的一些相應的改進方案。

2.1 解決空洞問題時右手法則開銷大

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

2.2 自適應性差

針對GPSR在不同場景中無法采取正確的轉發模式導致數據包丟失的問題，文獻[15]根據車流密度自適應采取不同轉發機制，在稀疏模式下，容易出現空洞問題，從而采用基于穩定的路由協議機制。文獻[16]根據格林布爾茨的速度—密度線性關系式，通過計算車輛的平均速度得到實時車流量密度信息，從而選擇最佳路徑。基于自適應選路策略的VANETs路由協議ASVP[17]針對 VANETs的鏈路頻斷性，提出了一種自適應路由協議,該協議引入攜帶—轉發機制使協議能夠適用于間歇性連接的延遲容忍網絡，通過對道路模型分析計算，獲得路段連通性度量指標用于選取最優路徑。

2.3 容錯性差

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

2.4 無法感知障礙物

在真實的城市交通場景中，存在著大量的建筑物和樹木等障礙物，然而GPSR協議沒有障礙物感知能力，仍然根據固有的機制轉發數據包，導致數據包無法成功發送。如圖3所示，源節點S要向目的節點D發送數據包，根據貪婪轉發S先把數據包轉發給A，由于存在障礙物,A將無法轉發數據包給D，導致轉發失敗。

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

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

2.5 節點位置不定和分布不均引起的鏈路斷裂問題

GPSR協議中每個數據分組中都攜帶一個被稱作標志位的位置信息，用M表示。在數據從源節點向目的節點傳遞過程中，目的節點的位置信息始終保持不變同時轉發給每個中間節點，而在這個過程中VANETs中的目的節點是移動的。因此，每個中間節點可能是按照錯誤的目的節點位置進行轉發，導致數據包丟失。

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

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

3 結束語

結合國內外對GPSR協議的改進研究現狀，存在的主要問題有以下幾個方面：

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

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

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

4)許多路由協議的仿真車輛運動模型過于簡單，試驗場景和現實場景之間的巨大差異可能導致路由協議的失效，路由協議的實驗仿真平臺還有待進一步研究和開發。

理想的路由協議的應該具有以下幾個方面：算法簡單、自適應能力強、控制開銷少、普適度高、時延小。通過對當前各類協議的分析比較，基于位置的路由協議對于VANETs頻繁變化的拓撲結構具有最適性。而其中典型的路由協議GPSR具有算法簡單、開銷小等優點，但在城市交通環境下仍存在著一些缺陷，對于它的普遍應用有一定阻礙作用。因此，針對其存在的問題進行改進設計高性能的GPSR是一個研究的重點。目前，許多國內外學者針對GPSR不足進行單一的改進，而沒有根據其不足進行綜合有效地改進，因此，在真實場景中改進的效果往往差強人意。總的來說，GPSR在VANETs中的有效應用仍在研究階段，仍然有很多問題亟需解決，許多新的研究課題有待發現。

[1] 徐會彬, 夏 超.VANETs路由綜述[J].計算機應用研究,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] 喻 嘉,聞英友,趙 宏.無線傳感器網絡中分段貪婪地理路由算法[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] 錢 釗,劉宏偉,左德承,等.移動自組網中基于位置信息的路徑優化路由算法[J].哈爾濱工程大學學報,2013(3):345-349.

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

[17] 王美琛,唐 倫.基于自適應選路策略的VANETs路由協議[J].計算機應用于軟件,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] 李洪兵,熊慶宇.無線傳感器網絡中網絡層故障容錯技術研究進展[J].計算機應用研究,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] 李金寶,郭曉行,張守娟.無線傳感器網絡中一種躲避障礙物的地理路由算法[J].黑龍江大學工程學報,2010(1):97-103.

[23] 張 帆.城市場景下車載自組網中GPSR路由協議的研究[D].長春：吉林大學,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-)，女，重慶人，碩士研究生，研究方向為寬帶無線網絡。