基于VANET的按需路由協議研究

江西科技學院信息工程學院 邱 嵐

基于VANET的按需路由協議研究

江西科技學院信息工程學院 邱 嵐

近年來，智能交通系統在改善交通問題方面發揮了關鍵作用。作為一種新形式的無線網絡， VANET已經成為新的研究熱點。在城市場景中，由于現有的VANET路由協議在交通信息查詢方面存在不足，本文提出了一種新的按需路由協議，稱為TQOR協議。該協議采用Dijkstra算法，建立一個由道路交叉口序列組成的按需路徑，并限定轉發區域。同時，為了提高數據轉發的效率，該協議利用方向鄰居列表執行優化的貪婪轉發機制。最后，通過仿真實驗驗證，該協議具有很高的數據轉發效率。

按需路由協議；TQOR協議；交通信息查詢；數據轉發效率

1 引言

作為一種新形式的無線網絡，車載自組織網絡（vehicular Ad Hoc networks，VANET），已經成為一種新的研究熱點，它主要是用來構建成本低、部署簡單、結構開放的自組織車輛間通信網絡[1]。VANET具有一般移動自組網（Mobile Ad hoc Networking，MANET）的固有問題，如隱藏點，暴露點，信息缺乏等[2]。然而，VANET又是非常特殊的，有其自身的特點。例如，拓撲結構變化迅速，無線信道不穩定，鏈路不可靠等[3]。這些特性直接影響VANET信息分配性能，使得它的研究與MANET不同。在單播模式下，車輛行駛速度快而且拓撲結構變化也快，使得一些傳統的MANET路由協議無法適應這樣的特性，數據轉發效率低。

在VANET中，有兩種信息傳輸模式：拉模式和推模式[4]。VANET中用于交通信息查詢的通信方式主要是廣播通信和單播通信。廣播通信以拉模式為主，而單播通信則采用推模式。在交通信息的采集和傳輸的研究中，有學者認為廣播通信比單播通信更適合。因此，在VANET中，主要使用廣播通信來獲取交通信息。然而，在城市環境下，由于車輛密度過高，若采用廣播方式發布交通信息，會產生大量的冗余信息，降低數據的轉發效率。這種情況下，廣播通信不再適用，而應使用單播通信。因此，在本文中，重點研究如何采用單播通信方式實現對于不同路段的交通信息查詢，而單播通信中的路由協議是信息查詢成功的重要因素。

2 VANET單播路由協議分析

目前，主要的VANET路由協議可以分為基于拓撲的路由和基于位置的路由等。

2.1 AODV協議分析

基于拓撲的路由是一種傳統的、最基本的自組織網絡路由，有兩種類型：表驅動路由協議和按需路由協議[5]。所謂按需路由協議，也可稱之為反應式路由協議，應用廣泛[6]。這種路由協議的代表是按需距離矢量協議（Ad Hoc on-demand Distance Vector Protocol，AODV）。

T1時刻按S-a-D建立了一條源節點S到目的節點D的路徑。但是在T2時刻，由于節點a的快速移動，超出了與S的通信范圍，使得S-a的路徑斷裂，T1時刻所建立的S-a-D的路徑失效。當然，通過局部修復機制，AODV路由協議可以重發RREQ和RREP消息。然而，這樣增加了數據包的傳輸延遲。在城市環境中，頻繁的鏈路斷裂，嚴重影響了AODV協議的傳輸質量。

2.2 GPSR協議分析

基于位置的路由是使用地理位置信息。在VANET中，車輛節點的位置信息由配備的GPS定位設備采集。因此，VANET中基于位置的路由協議也是值得研究的。例如，貪婪周邊無狀態路由（Greedy Perimeter Stateless Routing，GPSR）協議使用一個貪婪轉發模式[7]。所謂貪婪轉發，是選擇距離目的節點最近的節點作為下一跳節點，然而，就會出現這樣一個問題：比起節點自身來說，當所有相鄰節點距離目標節點都更遠，貪婪轉發不能進行[8]。

GPSR協議是一種無狀態路由，在數據傳輸之前不需要建立路徑[9]。因此，沒有路徑失效的問題。適用于快速變化的網絡拓撲和較大的網絡規模環境中。在高速公路上GPSR的性能很好，但在城市環境中仍有許多問題。

根據GPSR貪婪轉發的原理，源節點S選擇的下一跳節點應該是距離目的節點D最近的b節點，但是在城市環境中，b節點到D節點道路是不通的，導致貪婪轉發失敗。GPSR的貪婪轉發失敗，它會切換到周邊轉發模式。然而，這可能會加重網絡負擔，增加數據包傳輸延時，甚至可能發送失敗。

3 用于交通信息查詢的TQOR協議

前面詳細分析了AODV和GPSR路由協議在VANET城市場景下的不足之外。結合它們的優缺點，本文提出了一種新的單播路由協議——用于交通信息查詢的按需路由（Traffic-information Query Ondemand Routing (TQOR)）協議，其目的是為了提高數據傳輸率。

3.1 TQOR的基本思想

TQOR協議借鑒了AODV，它也是按需建立路徑。然而，它又不同于AODV。AODV是用節點組成路徑，而TQOR是用十字路口交叉點組成。節點是移動的，但十字路口交叉點卻是靜止的，由十字路口交叉點組成的路徑就是穩定的。而前面所說的AODV協議中節點的快速移動會產生路徑斷裂，使得傳輸效率降低的缺陷，在TQOR中就不會出現。同時，TQOR協議還結合GPSR的貪婪轉發機制，實現的是十字路口交叉點之間的轉發，這樣可以避免在前面描述的GPSR協議的問題。

圖1 轉發區域限定

3.2 轉發區域限定

轉發區域的限定也就是路徑建立的過程。在本文中，轉發區域限定為兩個圓的外接矩形。如圖1所示，交叉點9是距離源節點S最近的交叉口，作為起點，交叉點19是距離目的節點D最近的交叉口，作為終點，它們就是兩個圓的圓心。然后找到距離圓心最遠的交叉口，也就是圖中的交叉點10和交叉點16，它們和圓心的距離為半徑，作兩個圓。這兩個圓的外接矩形，如圖1中的虛線框，即為轉發區域。采用這種算法，有可能在轉發區域內搜索不到最短路徑，這時，可以通過層層擴大圓的半徑來解決。

3.3 貪婪轉發

在上一節所建立的限制區域中執行貪婪轉發策略，為了提高轉發性能，本文使用同向和反向兩個鄰居列表。

本文中的貪婪轉發與GPSR不同。在GPSR中，貪婪轉發選擇的下一跳節點是在鄰居列表中距離目的節點最近的節點。而在TQOR中，選擇的是鄰居列表中最接近下一個路口的節點，如圖2所示。

a是轉發節點，I1是節點剛離開的路口、I2是節點即將到達的路口。圖中圓圈為通信范圍，它和以I2為圓心的圓圈相交的共同區域，即圖中的陰影部分，是下一跳選擇區域。我們可以選擇最接近I2的節點c作為該區域的下一跳節點。

圖2 TQOR的貪婪轉發

4 TQOR性能仿真

本文采用NCTUns6.0仿真軟件進行仿真實驗，PC操作系統是fedora12。NCTUns6.0是一種結合交通仿真和網絡仿真的VANET仿真軟件，可以為實驗提供一個單一的車載網絡環境。實驗性能指標包括分組投遞率、平均跳數和分組傳輸延時。分組投遞率是指接收方接收到的和發送方發送的數據包總數之比；平均跳數是分組傳送過程中重新建立路由的次數，取平均值；分組傳輸延時是數據傳輸的延時時間。通過這三個指標，對AODV、GPSR和TQOR協議的性能進行比較。

源節點和目的節點的道路距離為：400米，800米，1200米，1600米，2000米，2400米，和2800米，進行了10次實驗，取平均值。仿真結果如圖3、4、5所示。

圖3 分組投遞率

在圖3中，隨著距離的增加，TQOR協議的分組投遞率優于其他兩個協議。AODV協議在距離增加時，會不斷的出現鏈路斷裂、修復失敗的現象，導致分組投遞率低。而對于GPSR協議來說，在城市環境中，距離的增加、道路網絡、建筑物等對GPSR的性能有很大的影響。比方說它會出現貪婪轉發失敗頻繁，切換到周邊轉發模式的現象。更甚至于在城市的場景中，網絡拓撲結構的切斷使得周邊轉發模式也會失敗。因此，從圖3中可以看出，GPSR的分組投遞率隨距離的增加而迅速下降。在圖4中，GPSR協議由于貪婪轉發的特點，它的平均跳數相對較少，而TQOR協議的平均跳數最多，可見TQOR協議是以犧牲跳數為代價，以維持一個相對穩定的分組投遞率，減少距離對它的影響。此外，圖5顯示三種協議的傳輸延時是在可容忍的范圍內。

圖4 平均跳數

圖5 分組傳輸延時

5 結束語

本文分析了VANET中AODV和GPSR協議在城市場景下存在的不足和缺陷并提出了一種新的單播路由協議TQOR。TQOR采用Dijkstra算法，建立一個由道路交叉口序列組成的路徑，限定轉發區域，并在限定區內執行貪婪轉發機制。TQOR充分考慮車輛行駛的特點，建立鄰居列表時，用同向和反向的節點來構造同向和反向的鄰居列表，以提高貪婪轉發性能。然后，通過仿真實驗對TQOR和AODV、GPSR的性能進行比較。結果表明，新協議具有相對穩定的分組投遞率和較高的數據傳輸效率。

[1]王慧敏,趙海濤．車載自組織網絡中連通概率的預測與建模[J]．電信科學,2016,(3)：118-121．

[2]向勇．基于車載自組網的動態交通信息的挖掘和利用[J]．中興通訊技術,2011,17(3)：29-34．

[3]王保林,張琦．基于車車通信的路況信息采集算法的研究[J]．現代電子技術,2011,34(7)： 202-204．

[4]丁四景．VANET中基于網絡連通性的改進AODV路由協議[D]．山東大學2015．

[5]夏梓峻,劉春風,趙増華,舒炎篆．基于鏈路預測的VANET路由算法[J]．計算機工程,2012,38(4)：110-111．

[6]熊煒,李清泉．高速公路場景中車用自組織網絡連通的必要條件[J]．軟件學報,2010,21(11)：2906-2919．

[7]于海寧,張宏莉．VANETs路由協議的研究進展[J]．電子學報,2011,39(12)：2868-2879．

[8]沈永增,姚敏杰,李曉鳳．基于城市路網的VANET按需路由策略研究[J]．計算機應用與軟件,2011,29(6)：236-238．

[9]姚敏杰．基于車輛聯網的實時路況信息系統研究[D]．浙江工業大學,2012．

邱嵐（1984—），女，湖北武漢人，工學碩士，江西科技學院講師，研究方向：無線通信、車聯網。

江西省教育廳科學技術研究項目“基于VANET的實時路況信息系統研究”（No．GJJ151149）。