基于車流密度的VANETs路由協議*

周美麗, 余 敏

(江西師范大學 計算機信息工程學院,江西 南昌 330022)

基于車流密度的VANETs路由協議*

周美麗, 余 敏

(江西師范大學 計算機信息工程學院,江西 南昌 330022)

在節點高速移動的車載自組織網絡(VANETs)中，道路交通狀況極大地影響著網絡中的數據傳輸性能。在貪婪周邊無狀態路由(GPSR)協議的基礎上加以改進，提出了基于車流密度的VANETs由協議。考慮了車流密度以及節點運動速度、方向等影響因素，設計車流密度的計算方法，利用新的轉發策略替代GPSR的貪婪轉發策略，能夠選擇車流密度較好的路徑進行數據轉發，避免因車流密度分布不均勻而產生的局部最大現象。同時能夠對由于節點高速運動引起的鏈路中斷進行預測，提出有效的修復機制，從而建立鏈路穩健的VANETs路由。采用Matlab仿真平臺進行仿真實驗，與已有的GPSR，GPCR協議進行比較分析。仿真結果表明:提出的路由協議相比于其它2種路由協議在時延和分組轉發率方面得到顯著改善，性能優越，非常適合在城市場景中。

車載自組織網絡； 車流密度； 鏈路中斷

0 引 言

車載自組織網絡(vehicle Ad-Hoc networks,VANETs), 是移動自組織多跳網路中極具應用價值的研究方向。利用 VANETs可以實現事故告警、輔助駕駛、道路交通信息查詢、車輛間通信、自動繳費和Internet 信息服務等應用，不僅能提高交通效率，還為司機的通行提供可靠安全的支持和多重便利。由于VANETs網絡拓撲結構的高度動態變化在傳輸數據時很具有挑戰性，越來越受到工業界和學術界的高度關注，因此,VANETs路由協議的研究成為了當前的熱點方向。

在VANETs的路由協議中，基于地理位置信息的路由協議是最為普遍采用的設計思想。以貪婪周邊無狀態路由(GPSR)[1]為代表的基于地理位置的路由協議采用貪婪轉發的思想，選擇離目標節點最近的下一跳進行路由轉發，能迅速發現和建立路由，具有高效、低路由開銷和良好的可擴展性等特點，特別適合于節點移動速度較快的VANETs。但是在城市道路中，道路兩邊的建筑物阻擋無線信號的傳播，造成空洞的形成，嚴重影響已有的基于位置的路由協議的性能, 文獻[2,3]中對該問題已有介紹。Lochert C等人提出了貪婪周邊協調器路由(greedy perimeter coordinator routing，GPCR)[4]協議，通過在十字路口部署固定節點做出數據轉發決策，解決了建筑物對無線信號的屏蔽作用。但該協議沒有考慮道路上車輛稀少、密度分布不均勻而產生的局部最大現象，路由時可能發生中斷，而自動回退，增大時延和跳數，降低路由效率。2008 年，Lee K C等人提出了城市VANETs環境下的地標覆蓋路由(LOUVRE)[5]協議。利用車輛自主發現密度的方式輔助路由選擇，提出了車輛自主發現道路密度的算法。通過“洪泛”方式傳播道路密度的評估值，使全網的所有車輛都能建立起各路段是否具有傳輸通路的認識，如此眾多的洪泛消息極易引起網絡擁塞，產生較大的發送時延。除此之外，在VANETs中由于節點的快速移動的特性，會使得已經建立的路由鏈路發生中斷，出現鏈路不穩定等問題[6～10]。因此，本文在GPSR協議的基礎上加以改進，提出了基于車流密度的VANETs路由協議。仿真實驗結果表明：該路由協議在時延和分組轉發率方面得到顯著改善。

1 基于車流密度的VANETs路由協議

1.1 3種類型節點

為了避開建筑物對無線信號的屏蔽效應，在十字路口部署固定的節點稱為十字路口節點。在此假設每輛車(節點)都安裝了GPS，除了獲得位置信息還能獲得節點所在的路段信息。對于路段的劃分，以十字路口的節點為分界點，2個十字路口的連線即為同一路段。每個節點需要廣播自己的位置和所在路段(記為ID)，對于十字路口節點信標的廣播信息將會“+”號來表示十字路口。節點可劃分為三類：

1)普通節點

該節點的信標廣播的ID與所有鄰居節點的ID號一致，即為普通節點。

2)預測節點

該節點的鄰居表中存在一個十字路口節點，即為預測節點。

3)十字路口節點

該節點鄰居表中各個路段的ID都有，自身ID標記為“+”，即為十字路口節點。每個十字路口節點存儲并維護一張與其相鄰的各個十字路口節點所組成的路段的車流密度表。

1.2 計算道路車流密度的算法

十字路口節點廣播Query查詢信息至與之相連路段的所有節點，節點將返回自身的節點號和鄰居節點數到十字路口節點。十字路口節點通過返回的信息包，計算路段中響應的節點數和所有節點的鄰居數之和。

假設路段的長度為L，有n個節點響應十字路口節點的Query查詢信息,節點的通信半徑為r,n個節點的鄰居數之和為m(十字路口節點不作為鄰居節點數計算)，那么該路段連通必須滿足n≥L/2r;否則,數據經此路段無法成功傳輸。原理如圖1所示。

圖1 原理圖Fig 1 Principle diagram

圖1中路段長度為8r,節點通信半徑為r,可看出此路段數據要經過路段兩端成功傳輸至少保證有4個節點。車流密度ρ的計算公式如下

(1)

如圖2所示的十字路口節點a維護的車流密度表可表示為：

1)a—b路段：{nodes:3,ρ:4/3},十字路口節點不作為鄰居節點數計算，A,B,C的鄰居節點數分別為1，2，1；

2)a—f路段：{nodes:0;ρ:0}；

3)a—e路段：{nodes:0;ρ:0}；

4)a—d路段：{nodes:2;ρ:1} 。

其中,nodes表示路段中的節點數，ρ為節點密度。由于a—f路段和a—e路段均只有一個節點,會出現傳輸中斷，可判斷此路段車流密度稀疏，不適宜進行路由傳輸。這種情況將nodes和ρ均設為0。

圖2 車流密度示意圖Fig 2 Diagram of vehicle density

1.3 設計路由轉發機制

在新協議中，針對定義的3種不同節點采用新的轉發機制替代GPSR的貪婪轉發策略，如下：

1)普通貪婪轉發模式

普通節點仍采取貪婪轉發模式。

2)受限的貪婪轉發模式

當數據包轉發至預測節點時，通過判斷預測節點與目的節點的位置關系。如果在同一路段則執行貪婪轉發模式，則無需經過十字路口節點;否則，將數據包傳給十字路口的節點進行路由選擇。

3)決策轉發模式

當數據包轉發至十字路口節點時，決策轉發策略如下：

(1)若目的節點在十字路口所相連的路段，則選擇與目的節點在同一路段的下一跳節點進行貪婪轉發。

(2)若目的節點不在十字路口所處路段，則采取如下步驟：

a.首先，十字路口節點根據自身坐標和目的節點的坐標，判斷目的節點在十字路口節點的哪個方位(將方位分為左上、左下、右上、右下)。每一個方位對應2個路段(如圖3所示，目的節點H在十字路口節點a左上方位對應a—b，a—d2個路段)。

b.十字路口節點根據步驟(a)判斷的方位所對應的2條路段進行選擇，查找車流密度表，選擇車流密度ρ較大連通性好的路段進行貪婪轉發。

c.若這2條路段的車流密度ρ均為0，則等待一個時間T。如果T時間后可以傳輸，則轉到步驟(b)；如果T時間后ρ仍然為0，則采用GPSR經典的右手周邊轉發模式。

如圖3所示，A為源節點，H為目的節點。根據本文的路由協議，源節點A將數據包傳輸到十字路口節點a時，節點a進行決策轉發，選擇車流密度大的a—b路段進行傳輸，傳輸路徑為A—a—C—D—b—F—G—h—H。如果按照GPSR貪婪轉發，十字路口節點會選擇離目的節點最近的節點E，傳輸路徑為選擇A—a—E,由于沒有下一跳可進行選擇，發生中斷，而自動回退，大大降低了傳輸效率。從圖3中可以看出：基于車流密度的VANETs協議考慮了車流密度對數據傳輸的影響，通過十字路口節點選擇車流密度大、局部最優的路段進行數據轉發，達到全局較優，明顯減少了跳數和傳輸時延，提高了傳輸效率。

圖3 新協議中的決策轉發Fig 3 Decision making and forwarding in new protocol

1.4 鏈路中斷預測和局部路由修復機制

由于VANETs中節點高速移動的特點，可能會發生鏈路中斷。傳統的路由協議中，都是在鏈路中斷發生以后再重新進行路由發現，這肯定會對數據的傳輸帶來一定的延時，尤其是對時間要求比較嚴格的系統，如碰撞避免系統，帶來的嚴重后果不堪設想，為了避免由于鏈路中斷而重新進行路由發現時帶來的延時，本文提出一種鏈路中斷預測和修復機制。

當節點處于某路段中時，以十字路口節點為標桿，節點根據自身的位置移動可判斷自己的運動方向，將包含自身位置信息的信標信息中加入方向信息廣播給鄰居節點，因此，節點可以預測自己與鄰居節點間的相對距離，是否超出了通信半徑，可對鏈路中斷進行提前預測。當一條鏈路即將發生中斷，開始局部修復過程。該協議中，對鏈路中斷分為2種情況，因此，修復過程也分為2種：

1)有可以選擇的下一跳節點：此時，則根據動態源路由(dynamic source routing,DSR)[6]算法，選擇合適的下一跳，并向源節點發送一個包含中斷鏈路信息的路由錯誤信息，源節點在路由表中將此路由刪除。

2)沒有可以選擇的下一跳節點：但如果發生中斷的節點距離源節點的跳數少于m，則發回一個包含鏈路中斷信息數據包給源節點，重新進行路由發現；否則，在中斷處進行 2 跳范圍內廣播，進行局部修復處理，并將包含錯誤鏈路信息的數據包轉發回給源節點，讓源節點刪除此路由信息，以免在下一次路由選擇時再選擇此路徑。

2 實驗仿真

本文采用Matlab對改進后的基于車流密度的VANETs路由協議和GPSR,GPCR協議進行大量仿真實驗，在傳輸延遲和分組投遞成功率性能方面進行比較分析。應用VanetMobiSim來產生接近現實交通情況的拓撲結構仿真模型。設置場景大小為1 000 m×1 000 m，選擇節點數從40～180個隨機分布，隨機選擇一對節點進行通信。節點間的最大有效通信距離為250 m，信道容量為2 MB/s。節點的最大運動速度為50 m/s，仿真持續時間為600 s。

從圖4中可以看出:當節點個數增加時，3種協議平均端到端時延變化的比較。當節點個數增多時，節點連通性更好，平均時延均在減小。本文所研究的路由協議，由于考慮到車流密度即連通性對路由的影響，在數據轉發時選擇連通性好的路徑轉發，傳輸時延大大減少。比GPSR的平均時延減少40 %，與GPCR比較也減少了25 %，實時性好。圖5顯示了數據分組成功投遞率的比較情況，相比之下，可以看出：采用本文的協議的數據分組成功投遞率基本持續在90 %以上較高水平，在節點較少時仍能保持較高成功率，且較穩定。因此，從實驗結果可以看出：本文所研究的基于車流密度的VANETs路由協議在數據分組的成功轉發率基本高達90 %多，時延也明顯減少，實時性強，遠遠優于GPSR和GPCR協議，整體性能顯著提高。

圖4 平均端到端時延比較Fig 4 Comparison of average end-to-end time delay

圖5 數據分組成功投遞率比較Fig 5 Comparison of data packet successful delivery rate

3 結 論

為了解決道路交通狀況極大地影響VANETs路由傳輸性能和鏈路穩定性的問題，提出了基于車流密度的VANETs路由協議。充分考慮了車流密度和節點運動速度、方向等因素，能夠根據車流密度信息，選擇車流密度較好、局部最優的路徑進行數據轉發，達到全局較優，避免由于道路稀疏引起路由中斷而自動回退的問題，大大減少時延和跳數。同時對由于節點高速運動引起的鏈路中斷進行預測，及時有效地修復，保證了鏈路的實時性和穩定性。通過仿真實驗驗證：該協議在數據傳輸中在性能方面得到顯著提高，具有高實時性和可靠性。

[1] Karp B,Kung T H.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceedings of the 6th Annual Internatio-nal Conference on Mobile Computing and Networking(MOBICOM’00),Boston,MA,USA:ACM,2000:243-254.

[2] Lochert C,Hartenstein H,Tian J,et al.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the IEEE Intelligent Vehicles Symposium，IVS’03,Columbus,OH,USA,2003:156-161.

[3] Shu Zhengzheng,Yu Min,Zou Chengwu.An improved clockwise grid routing protocol based on geographic location information[C]∥2012 Second International Conference on Electric Information and Control Engineering，ICEICE 2012,Lushan,China,2012.

[4] Lochert C,Mauve M,Fussler H,et al.Geographic routing in city scenarios[J].ACM SIGMOBLE Mobile Computing and Communications Review,2005,9(1):69-72.

[5] Lee C K,Le M,Harri J.LOUVRE:Landmark overlays for urban vehicular routing environments[C]∥Proceedings of the 68th IEEE Vehicular Technology Conference，VTC-Fall’08,Calgary,Canada:2008-5.

[6] 符媛柯，唐 倫.車載自組織網絡路由協議及研究進展[J].計算機應用，2013，33(7)：1793-1797，1801.

[7] Kouah Riad,Moussaoui Samira,Aissani Mohamed. Direction-based greedy forwarding in mobile wireless sensor networks[C]∥The Eighth Advanced International Conference on Telecommunications,AICT 2012,2012:69-74.

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

[9] Singh Pranav Kumar, Lego Kapang, Tuithung Dr Themrichon. Simulation-based analysis of Ad Hoc routing protocol in urban and highway scenario of VANET[J].International Journal of Compu-ter Application,2011,12(10):42-49.

[10] 徐會彬,夏 超.VANETs路由綜述[J].計算機應用研究,2013(1):1-6.

Routing protocol based on vehicle density in VANETs*

ZHOU Mei-li, YU Min

(School of Computer and Information Engineering,Jiangxi Normal University,Nanchang 330022,China)

In the VANETs of high-speed movement of nodes,road traffic conditions greatly affect the performance of data transmission in the network.On the basis of greedy perimeter stateless routing(GPSR) routing protocol,propose a routing protocol based on vehicle density in VANETs.The new protocol considers the factor of vehicle density and speed and direction of node movement,then designs the calculation method of vehicle density and makes new forwarding strategy instead of the greedy forwarding strategy of GPSR,which can select the path of better vehicle density to forwarding data to avoid phenomena of local maxima caused by uneven distribution of vehicle density.And can predict about link interruption caused by high-speed movement of nodes,then proposes effective repair mechanism to establish a stable VENETs routing of robust link.The performance of GPSR,and GPCR is compared by simulation using Matlab.The simulation results show that the capability of the new protocol is improved significantly compared with the other two routing protocols on delay time and forwarding rate and it is suitable to be applied in city scenes.

VANETs； vehicle density； link interruption

2013—08—15

國家自然科學基金資助項目(41164001)；國際科技合作專項項目(35—14)

TP 393

A

1000—9787(2014)04—0118—04

周美麗(1990-)，女，江西撫州人，碩士研究生，研究方向為無線傳感器網絡。