梅玲

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

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

中圖分類號(hào)： TN915.04?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)最有前景的技術(shù)，車聯(lián)網(wǎng)（Vehicular Ad Hoc Networks，VANETs）為車間通信提供了平臺(tái)。典型的VANETs結(jié)構(gòu)如圖1所示，車間形成 （Vehicle to Vehicle，V2V）通信，車與路邊設(shè)備形成（Vehicle to Infrastructure，V2I）通信。行駛中的車輛通過(guò)V2V交互實(shí)時(shí)路狀信息，進(jìn)而提高交通安全[1?2]。

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

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

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

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

1.1 網(wǎng)絡(luò)模型

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

利用圖論將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為無(wú)向圖[GV，E]，其中[V]是節(jié)點(diǎn)集，[E]是兩節(jié)點(diǎn)間構(gòu)成的鏈接。基于圖論的道路結(jié)構(gòu)圖[9]如圖3所示。

1.2 約束條件

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

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

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

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

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

2 RCR協(xié)議

2.1 鄰居節(jié)點(diǎn)集

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

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

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

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

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

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

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

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

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

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

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

3 數(shù)值分析

3.1 仿真場(chǎng)景

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

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

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

3.2 仿真結(jié)果及分析

3.2.1 端到端傳輸時(shí)延

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

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

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

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

3.2.3 路由開(kāi)銷

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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