面向VANETs城市环境的基于道路连通路由协议

梅玲

摘 要： 路由协议是车联网VANETs的研究焦点，特别是在城市环境中，复杂路况给VANETs 的路由提出挑战。为此，提出面向VANETs城市环境基于道路连通的路由RCR协议。考虑道路是静态的，建立以道路连通为基础的路由协议。RCR协议先利用数字地图知识将道路划分为不同路段，再依据车辆的位置选择网关，建立包含路段信息的路由表，最后，采用反应式路由策略建立路由。仿真结果表明，提出的RCR协议降低了端到端传输时延、提高了数据包的传递率，与GYTAR协议相比，RCR协议的端到端传输时延下降了32%。

关键词： 车联网； 路由； 连通； 十字路口； 网关

中图分类号： 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 引 言

作为智能交通系统最有前景的技术，车联网（Vehicular Ad Hoc Networks，VANETs）为车间通信提供了平台。典型的VANETs结构如图1所示，车间形成 （Vehicle to Vehicle，V2V）通信，车与路边设备形成（Vehicle to Infrastructure，V2I）通信。行驶中的车辆通过V2V交互实时路状信息，进而提高交通安全[1?2]。

与其他自组织网络不同，VANETs具有鲜明的特性[3]。如节点快速移动，拓扑动态变化，网络断裂频繁，这就使得传统Ad Hoc网络路由协议不再适用于VANETs。同时，VANETs的独特特性给数据传输协议提出机会和挑战[4]。

目前，研究人员对路由协议进行了深入的研究，并提出了不同的路由方案。多数路由方案是基于贪婪算法，如GYTAR[5]，GPCR[6]选择源节点与目的节点间最短路径作为数据传输通道。而GYTAR[4]，A?STAR[7]，DBD[8]是利用已连接的路段传输数据。但是这些路由方案主要存在局部最大化和数据拥塞两个问题。当没有连通的路段比当前路段更靠近于目的地时，就产生局部最大化问题，在这种情况下，通常采用存储转发，这必然增加时延。

为此，本文提出基于道路连通的路由RCR协议。RCR协议以静态的道路为研究对象，并引用位于或邻近于十字路口的车辆作为网关。这些网关节点为路段车辆的连通提供保障。仿真结果表明，提出的RCR协议能够有效地提高数据包传递率，降低了端到端传输时延。

1 网络模型及约束条件

1.1 网络模型

考虑典型的城市场景，如图2所示。建立由道路和十字路口组成的道路模型。[Ii]表示第[i]个十字路口。两十字路口间的路段为直线路段，将十字路口[Ii]和[Ij]间路段表示为[Si，j。]每个路段均有自己的属性，如长度、宽度、车道数和车流密度。

利用图论将网络拓扑结构转化为无向图[GV，E]，其中[V]是节点集，[E]是两节点间构成的链接。基于图论的道路结构图[9]如图3所示。

1.2 约束条件

提出的RCR协议基于以下约束条件：

（1） 在VANETs中，每个节点具有GPS，能获取自身的位置信息，包括车辆坐标、速度信息。同时具有数字地图功能，能查询节点所在区域的道路结構信息；

（2） 每个节点具有一定的计算存储能力，能记录数据包处理负载信息；

（3） 采用IEEE 802.11p协议，节点的通信半径为[R=300 ]m；endprint

（4） 每个节点具有数据包的接收、转发能力，且每个节点周期性地广播Beacon。

2 RCR协议

2.1 邻居节点集

RCR协议将道路划分为不同的路段，且每个路段具有不同的编号ID。每个节点先周期广播Beacon包，RCR协议将传统的Beacon包字段进行扩充，增加了节点所在路段号ID。Beacon包格式如下：

其中，NodeID为节点的ID；RoadID为节点的路段ID，Location为节点位置；Speed为节点移动速度；Direction为节点移动方向。节点依据接收的Beacon包先确定自己的一跳邻居节点集[N]。

一旦接收了Beacon包，节点就从此包中提取信息，并建立自己一跳邻居节点集[N]。通过这种方式，节点能够得到邻近节点的信息。如图4所示，在一个四路交叉十字路口，这些车辆通过交互Beacon包获取自己的邻居信息。这些车辆的邻居节点集如表1所示。

值得注意的是，在建立一跳邻居节点集时，需考虑位于十字路口的特殊节点。如图4所示，节点H，G，E，S可能接收到来自不同路段的Beacon包。由于这些节点的特殊位置[10]，它们有助于十字路口的数据转发。为此，RCR协议将这些节点称为网关节点GN（Gateway Node）。

只要节点收到来自两个或两个以上的路段号的Beacon包，该节点就称为网关节点GN。假定节点[?i，]其邻居节点集为[Ni=?1，?2，…，?Ni]。如果[Ni]内的节点具有不同的路段号[11]，即[Ni]内所有节点的路段号不相同，则节点[i]为网关节点。引入二值变量flag表征节点是否为网关节点GN，若flag=1，称为网关节点GN，反之，非网关节点GN，具体如式（3）所示：

当邻居节点集内有节点是GN，则将GN节点邻近的路段号也记录在邻居节点集中。如表2所示，节点E有邻居节点S，D。由于节点S是GN节点，它与位于路段2的节点G是邻居节点。因此将路段2也记入其邻居集内。类似地，节点S的邻居节点集内除了节点C，D，E外，还有路段2，3。

2.2 路径发现

当源节点需要向目的节点传输数据时，首先需要寻找通往目的节点的路径。RCR算法采用反应式路由发现策略，通过传输RREQ和RREP控制包发现路由。

在发送RREQ控制包之前，源节点先判断目的节点与自己是否属于同一个路段。如果属于同一路段，源节点只需通过同一路段的邻居节点转发RREQ数据包。反之，源节点需要选择一个网关节点转发RREQ控制包[12?14]。仍以图4为例，源节点依据目的节点的不同，可建立如表2所示的路由表。

源节点依据自己的路由表向目的节点传输RREQ。图5显示了RREQ和RREP的传输过程。目的节点可能收到来自不同路径的RREQ包，为了提高数据传输效率，降低传输时延，目的节点最先将RREQ包传输至自己的路径，并没着该路径以单播形式回复RREP包。源节点接收了RREP包后，就沿着该路径向目的节点传输数据。

图5以简图的形式表述了RREQ和RREP的传输过程。在图5（a）中，源节点1以三种路径将RREQ传输至目的节点。目的节点接收后，选择最优的路径向源节点回复RREP包。最终，源节点沿着该路径传输数据包。

3 数值分析

3.1 仿真场景

利用NS3.3.18仿真软件建立仿真平台[15]，引用7 500 m×7 500 m的双向道路数字地图，含有165个十字路口，仿真场景如图6所示，车辆行驶速度范围为18～120 km/h，车辆通信距离为250 m。数据包大小为512 B。

在仿真过程中，考虑三种不同的车流密度：低车流密度，每千米少于20辆车；中车流密度，每千米30～40辆车；高车流密度，每千米超过50辆车。

为了更好地评估RCR协议的平均端到端传输时延E2ED（End?to?End Delay）、数据包传递率PDR（Packet Delivery Ratio）和路由开销，选择同类协议AODV和 GYTAR进行同步仿真，并进行性能对比分析。

3.2 仿真结果及分析

3.2.1 端到端传输时延

图7描述了路由协议在三种不同车流密度环境下的端到端传输时延。从图7可知，AODV和GYTAR协议的端到端传输时延远高于RCR协议。在RCR协议中，网关节点有效地进行移动车辆间的通信连接，降低了传输时延。而GYTAR协议容易陷入局部最大化的困境。一旦路径断裂，AODV协议需重新建立从源节点至目的节点的路径，这额外引入了时延。而RCR协议通过网关很容易维护通信连接。

此外，低车流密度环境的端到端传输时延较高，原因在于车辆数越少，建立通信連接越困难。

3.2.2 数据包传递率

图8绘制了数据包传递率随车流密度的变化情况。从图8可知，在三个不同的车流密度环境中，AODV协议的数据包传递率均最低。在低车流密度环境中，AODV协议的数据包传递率只有12%～13%。而GYTAR协议的数据包传递率略高于AODV，可达到约21%。但是，GYTAR协议的数据包传递率远低于RCR协议。在低车流密度环境下，RCR协议的数据包传递率可达到约68%，而在高车流密度环境下，高达85%。

3.2.3 路由开销

最后分析了S?CDSR协议的路由开销。采用归一化路由开销，即每传一个数据包所需的控制包个数，实验结果如图9所示。

从图9可知，AODV协议的路由开销低于GYTAR协议。原因在于AODV协议的路由开销主要在目的节点发现过程，而GYTAR协议需要周期地交互Beacon包，这引入了额外的路由开销。而RCR协议在路由发现阶段并未采取广播策略，减少了控制开销。此外，由于RCR协议通过网关节点能够有效提高路径的稳定性，有利于控制路由开销。而AODV，GYTAR协议需要频繁地重新发现路径，增加了路由开销。endprint

4 结 语

有效的数据传输是VANETs应用的基石，为此，本文面向VANETs城市应用环境，提出基于道路连通的路由协议RCR。考虑到车辆的快速移动，选择静态道路构建路由，并依据车辆的特殊位置选择位于十字路口的车辆作为网关，并利用网关车辆连通车间的通信链接。仿真结果表明，提出的RCR协议提高了数据包的传递率，也降低了端到端的传输时延。

参考文献

[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