面向VANETs城市環(huán)境的基于道路連通路由協(xié)議

梅玲

摘 要： 路由協(xié)議是車聯(lián)網(wǎng)VANETs的研究焦點，特別是在城市環(huán)境中，復雜路況給VANETs 的路由提出挑戰(zhàn)。為此，提出面向VANETs城市環(huán)境基于道路連通的路由RCR協(xié)議?？紤]道路是靜態(tài)的，建立以道路連通為基礎的路由協(xié)議。RCR協(xié)議先利用數(shù)字地圖知識將道路劃分為不同路段，再依據(jù)車輛的位置選擇網(wǎng)關，建立包含路段信息的路由表，最后，采用反應式路由策略建立路由。仿真結果表明，提出的RCR協(xié)議降低了端到端傳輸時延、提高了數(shù)據(jù)包的傳遞率，與GYTAR協(xié)議相比，RCR協(xié)議的端到端傳輸時延下降了32%。

關鍵詞： 車聯(lián)網(wǎng)； 路由； 連通； 十字路口； 網(wǎng)關

中圖分類號： TN915.04?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2017）23?0166?05

Abstract： Routing protocol is the research focus for vehicular Ad Hoc networks （VANETs）. The complex road conditions provide the big challenge for the routing of VANETs， especially in urban environment. Therefore， a road connectivity?based routing （RCR） protocol for urban vehicular Ad Hoc networks is proposed in this paper. Considering the static road， the routing protocol based on road connectivity is constructed. The digital map knowledge is adopted by RCR protocol to divide the road into several road segments， and select the gateway according to the location of vehicles. The routing table including road segments information is established. The proactive routing strategy is used to establish the routing. The simulation results show that the RCR protocol can reduce the end?to?end transmission delay and improve the data packet delivery ratio. Compared with GYTAR protocol， the end?to?end transmission delay of RCR protocol is reduced by 32%.

Keywords： VANETs； routing； connectivity； intersection； gateway

0 引 言

作為智能交通系統(tǒng)最有前景的技術，車聯(lián)網(wǎng)（Vehicular Ad Hoc Networks，VANETs）為車間通信提供了平臺。典型的VANETs結構如圖1所示，車間形成 （Vehicle to Vehicle，V2V）通信，車與路邊設備形成（Vehicle to Infrastructure，V2I）通信。行駛中的車輛通過V2V交互實時路狀信息，進而提高交通安全[1?2]。

與其他自組織網(wǎng)絡不同，VANETs具有鮮明的特性[3]。如節(jié)點快速移動，拓撲動態(tài)變化，網(wǎng)絡斷裂頻繁，這就使得傳統(tǒng)Ad Hoc網(wǎng)絡路由協(xié)議不再適用于VANETs。同時，VANETs的獨特特性給數(shù)據(jù)傳輸協(xié)議提出機會和挑戰(zhàn)[4]。

目前，研究人員對路由協(xié)議進行了深入的研究，并提出了不同的路由方案。多數(shù)路由方案是基于貪婪算法，如GYTAR[5]，GPCR[6]選擇源節(jié)點與目的節(jié)點間最短路徑作為數(shù)據(jù)傳輸通道。而GYTAR[4]，A?STAR[7]，DBD[8]是利用已連接的路段傳輸數(shù)據(jù)。但是這些路由方案主要存在局部最大化和數(shù)據(jù)擁塞兩個問題。當沒有連通的路段比當前路段更靠近于目的地時，就產(chǎn)生局部最大化問題，在這種情況下，通常采用存儲轉發(fā)，這必然增加時延。

為此，本文提出基于道路連通的路由RCR協(xié)議。RCR協(xié)議以靜態(tài)的道路為研究對象，并引用位于或鄰近于十字路口的車輛作為網(wǎng)關。這些網(wǎng)關節(jié)點為路段車輛的連通提供保障。仿真結果表明，提出的RCR協(xié)議能夠有效地提高數(shù)據(jù)包傳遞率，降低了端到端傳輸時延。

1 網(wǎng)絡模型及約束條件

1.1 網(wǎng)絡模型

考慮典型的城市場景，如圖2所示。建立由道路和十字路口組成的道路模型。[Ii]表示第[i]個十字路口。兩十字路口間的路段為直線路段，將十字路口[Ii]和[Ij]間路段表示為[Si，j。]每個路段均有自己的屬性，如長度、寬度、車道數(shù)和車流密度。

利用圖論將網(wǎng)絡拓撲結構轉化為無向圖[GV，E]，其中[V]是節(jié)點集，[E]是兩節(jié)點間構成的鏈接。基于圖論的道路結構圖[9]如圖3所示。

1.2 約束條件

提出的RCR協(xié)議基于以下約束條件：

（1） 在VANETs中，每個節(jié)點具有GPS，能獲取自身的位置信息，包括車輛坐標、速度信息。同時具有數(shù)字地圖功能，能查詢節(jié)點所在區(qū)域的道路結構信息；

（2） 每個節(jié)點具有一定的計算存儲能力，能記錄數(shù)據(jù)包處理負載信息；

（3） 采用IEEE 802.11p協(xié)議，節(jié)點的通信半徑為[R=300 ]m；endprint

（4） 每個節(jié)點具有數(shù)據(jù)包的接收、轉發(fā)能力，且每個節(jié)點周期性地廣播Beacon。

2 RCR協(xié)議

2.1 鄰居節(jié)點集

RCR協(xié)議將道路劃分為不同的路段，且每個路段具有不同的編號ID。每個節(jié)點先周期廣播Beacon包，RCR協(xié)議將傳統(tǒng)的Beacon包字段進行擴充，增加了節(jié)點所在路段號ID。Beacon包格式如下：

其中，NodeID為節(jié)點的ID；RoadID為節(jié)點的路段ID，Location為節(jié)點位置；Speed為節(jié)點移動速度；Direction為節(jié)點移動方向。節(jié)點依據(jù)接收的Beacon包先確定自己的一跳鄰居節(jié)點集[N]。

一旦接收了Beacon包，節(jié)點就從此包中提取信息，并建立自己一跳鄰居節(jié)點集[N]。通過這種方式，節(jié)點能夠得到鄰近節(jié)點的信息。如圖4所示，在一個四路交叉十字路口，這些車輛通過交互Beacon包獲取自己的鄰居信息。這些車輛的鄰居節(jié)點集如表1所示。

值得注意的是，在建立一跳鄰居節(jié)點集時，需考慮位于十字路口的特殊節(jié)點。如圖4所示，節(jié)點H，G，E，S可能接收到來自不同路段的Beacon包。由于這些節(jié)點的特殊位置[10]，它們有助于十字路口的數(shù)據(jù)轉發(fā)。為此，RCR協(xié)議將這些節(jié)點稱為網(wǎng)關節(jié)點GN（Gateway Node）。

只要節(jié)點收到來自兩個或兩個以上的路段號的Beacon包，該節(jié)點就稱為網(wǎng)關節(jié)點GN。假定節(jié)點[?i，]其鄰居節(jié)點集為[Ni=?1，?2，…，?Ni]。如果[Ni]內的節(jié)點具有不同的路段號[11]，即[Ni]內所有節(jié)點的路段號不相同，則節(jié)點[i]為網(wǎng)關節(jié)點。引入二值變量flag表征節(jié)點是否為網(wǎng)關節(jié)點GN，若flag=1，稱為網(wǎng)關節(jié)點GN，反之，非網(wǎng)關節(jié)點GN，具體如式（3）所示：

當鄰居節(jié)點集內有節(jié)點是GN，則將GN節(jié)點鄰近的路段號也記錄在鄰居節(jié)點集中。如表2所示，節(jié)點E有鄰居節(jié)點S，D。由于節(jié)點S是GN節(jié)點，它與位于路段2的節(jié)點G是鄰居節(jié)點。因此將路段2也記入其鄰居集內。類似地，節(jié)點S的鄰居節(jié)點集內除了節(jié)點C，D，E外，還有路段2，3。

2.2 路徑發(fā)現(xiàn)

當源節(jié)點需要向目的節(jié)點傳輸數(shù)據(jù)時，首先需要尋找通往目的節(jié)點的路徑。RCR算法采用反應式路由發(fā)現(xiàn)策略，通過傳輸RREQ和RREP控制包發(fā)現(xiàn)路由。

在發(fā)送RREQ控制包之前，源節(jié)點先判斷目的節(jié)點與自己是否屬于同一個路段。如果屬于同一路段，源節(jié)點只需通過同一路段的鄰居節(jié)點轉發(fā)RREQ數(shù)據(jù)包。反之，源節(jié)點需要選擇一個網(wǎng)關節(jié)點轉發(fā)RREQ控制包[12?14]。仍以圖4為例，源節(jié)點依據(jù)目的節(jié)點的不同，可建立如表2所示的路由表。

源節(jié)點依據(jù)自己的路由表向目的節(jié)點傳輸RREQ。圖5顯示了RREQ和RREP的傳輸過程。目的節(jié)點可能收到來自不同路徑的RREQ包，為了提高數(shù)據(jù)傳輸效率，降低傳輸時延，目的節(jié)點最先將RREQ包傳輸至自己的路徑，并沒著該路徑以單播形式回復RREP包。源節(jié)點接收了RREP包后，就沿著該路徑向目的節(jié)點傳輸數(shù)據(jù)。

圖5以簡圖的形式表述了RREQ和RREP的傳輸過程。在圖5（a）中，源節(jié)點1以三種路徑將RREQ傳輸至目的節(jié)點。目的節(jié)點接收后，選擇最優(yōu)的路徑向源節(jié)點回復RREP包。最終，源節(jié)點沿著該路徑傳輸數(shù)據(jù)包。

3 數(shù)值分析

3.1 仿真場景

利用NS3.3.18仿真軟件建立仿真平臺[15]，引用7 500 m×7 500 m的雙向道路數(shù)字地圖，含有165個十字路口，仿真場景如圖6所示，車輛行駛速度范圍為18～120 km/h，車輛通信距離為250 m。數(shù)據(jù)包大小為512 B。

在仿真過程中，考慮三種不同的車流密度：低車流密度，每千米少于20輛車；中車流密度，每千米30～40輛車；高車流密度，每千米超過50輛車。

為了更好地評估RCR協(xié)議的平均端到端傳輸時延E2ED（End?to?End Delay）、數(shù)據(jù)包傳遞率PDR（Packet Delivery Ratio）和路由開銷，選擇同類協(xié)議AODV和 GYTAR進行同步仿真，并進行性能對比分析。

3.2 仿真結果及分析

3.2.1 端到端傳輸時延

圖7描述了路由協(xié)議在三種不同車流密度環(huán)境下的端到端傳輸時延。從圖7可知，AODV和GYTAR協(xié)議的端到端傳輸時延遠高于RCR協(xié)議。在RCR協(xié)議中，網(wǎng)關節(jié)點有效地進行移動車輛間的通信連接，降低了傳輸時延。而GYTAR協(xié)議容易陷入局部最大化的困境。一旦路徑斷裂，AODV協(xié)議需重新建立從源節(jié)點至目的節(jié)點的路徑，這額外引入了時延。而RCR協(xié)議通過網(wǎng)關很容易維護通信連接。

此外，低車流密度環(huán)境的端到端傳輸時延較高，原因在于車輛數(shù)越少，建立通信連接越困難。

3.2.2 數(shù)據(jù)包傳遞率

圖8繪制了數(shù)據(jù)包傳遞率隨車流密度的變化情況。從圖8可知，在三個不同的車流密度環(huán)境中，AODV協(xié)議的數(shù)據(jù)包傳遞率均最低。在低車流密度環(huán)境中，AODV協(xié)議的數(shù)據(jù)包傳遞率只有12%～13%。而GYTAR協(xié)議的數(shù)據(jù)包傳遞率略高于AODV，可達到約21%。但是，GYTAR協(xié)議的數(shù)據(jù)包傳遞率遠低于RCR協(xié)議。在低車流密度環(huán)境下，RCR協(xié)議的數(shù)據(jù)包傳遞率可達到約68%，而在高車流密度環(huán)境下，高達85%。

3.2.3 路由開銷

最后分析了S?CDSR協(xié)議的路由開銷。采用歸一化路由開銷，即每傳一個數(shù)據(jù)包所需的控制包個數(shù)，實驗結果如圖9所示。

從圖9可知，AODV協(xié)議的路由開銷低于GYTAR協(xié)議。原因在于AODV協(xié)議的路由開銷主要在目的節(jié)點發(fā)現(xiàn)過程，而GYTAR協(xié)議需要周期地交互Beacon包，這引入了額外的路由開銷。而RCR協(xié)議在路由發(fā)現(xiàn)階段并未采取廣播策略，減少了控制開銷。此外，由于RCR協(xié)議通過網(wǎng)關節(jié)點能夠有效提高路徑的穩(wěn)定性，有利于控制路由開銷。而AODV，GYTAR協(xié)議需要頻繁地重新發(fā)現(xiàn)路徑，增加了路由開銷。endprint

4 結 語

有效的數(shù)據(jù)傳輸是VANETs應用的基石，為此，本文面向VANETs城市應用環(huán)境，提出基于道路連通的路由協(xié)議RCR?？紤]到車輛的快速移動，選擇靜態(tài)道路構建路由，并依據(jù)車輛的特殊位置選擇位于十字路口的車輛作為網(wǎng)關，并利用網(wǎng)關車輛連通車間的通信鏈接。仿真結果表明，提出的RCR協(xié)議提高了數(shù)據(jù)包的傳遞率，也降低了端到端的傳輸時延。

參考文獻

[1] RAJ Chitraxi， UPADHAYAYA Urvik， MAKWANA Twinkle， et al. Simulation of VANETS using ns?3 and SUMO [J]. International journal of advanced resources computing science software engineering， 2014， 4 （2）： 563?569.

[2] GORRIERI Andrea， FERRARI Gianluigi. Irresponsible AODV routing [J]. Vehicular communications， 2015， 3（2）： 47?57.

[3] LOCHERT C， HARTENSTEIN H， TIAN J， et al. A routing strategy for vehicular Ad Hoc networks in city environments [C]// Proceedings of 2003 IEEE Intelligent Vehicles Symposium. Columbus： IEEE， 2013： 156?161.

[4] ZHU Lina， LI Changle， XIA Bing. A hybrid routing protocol for 3?D vehicular Ad Hoc networks [J]. IEEE systems journal， 2015（10）： 23?32.

[5] TANG Guoming， XIE Yi， TANG Daquan. Divisional perimeter routing for GYTAR based on left and right hand rules [C]// Proceedings of 2011 International Conference on Computer Science and Network Technology. Harbin， China： IEEE， 2011： 726?729.

[6] LOCHERT C， MAUVE M， FUSSLER H， et al. Geographic routing in city scenarios [J]. SIGMOBILE mobile computing and communications review， 2015， 9（1）： 69?72.

[7] LIU G P， LEE B S， SEET B H， et al. A routing strategy for metropolis vehicular communications in information networking [C]// Proceedings of 2004 International Conference on Information Networking. [S.l.]： Springer， 2004： 134?143.

[8] FELICE M D， CERQUEIRA E， MELO A， et al. A distributed beaconless routing protocol for real?time video dissemination in multimedia VANETs [J]. Computer communications， 2015， 58（C）： 40?52.

[9] AMJAD Z， SONG W C， AHN K J. Two?level hierarchical routing based on road connectivity in VANETs [C]// Proceedings of 2016 IEEE International Conference on Industrial Engineering， Management Science and Application. Jeju： IEEE， 2016： 23?31.

[10] ZHANG H L， QIANG Z. A novel road topology?aware routing in VANETs [C]// Proceedings of 2014 Asia?pacific Web Techno?logies and Applications. Switzaerland： Springer， 2014： 167?176.

[11] AKAMATSU R， SUZUKI M， OKAMOTO T， et al. Adaptive delay?based geocast protocol for data dissemination in urban VANET [C]// Proceedings of 2014 the Seventh International Conference on Mobile Computing and Ubiquitous Network. Singapore： IEEE， 2014： 43?51.

[12] BOBAN M， VINHOZA T T V， BARROS J， et al. Impact of vehicles as obstacles in vehicular Ad Hoc networks [C]// Proceedings of 2014 the Seventh International Conference on Mobile Computing and Ubiquitous Network. Singapore： IEEE， 2014： 15?28.

[13] NADEMBEGA A， HAFID A， TALEB T. Mobility prediction?aware bandwidth reservation scheme for mobile networks [J]. IEEE transactions on vehicular technology， 2015， 64（6）： 2561?2576.

[14] LI H， CHENG Y， ZHOU C， et al. Routing metrics for minimizing end?to?end delay in multiradio multichannel wireless networks [J]. IEEE transactions on parallel & distributed systems， 2013， 24（11）： 2293?2303.

[15] LAN K C. MOVE： a practical simulator for mobility model in VANETS [M]// Anon. Telematics communication technologies and vehicular networks. Hershey， PA， USA： IGI Global， 2010： 355?368.endprint