邓少闻 罗代升

摘 要： 车辆的高速移动以及城市场景中的障碍物使得车辆间的通信路径变得异常脆弱。为此，提出基于路径判据的按需距离矢量（AODV）的路由算法（PA?AODV），进而增强路径的稳定性。PA?AODV路由首先计算路径质量因子、移动方向因子，然后再计算路径判据权值，最后择优选择权重小路径传输数据。仿真结果表明，提出的PA?AODV路由提高了数据包传递率，并降低了端到端传输时延。

关键词： 车联网； 按需距离矢量； 链路质量； 移动方向； 路径判据； 降低传输时延

中图分类号： TN915?34； TPT393 文献标识码： A 文章编号： 1004?373X（2018）19?0031?05

Abstract： The high?speed mobility of vehicles and obstacles existing in urban area make the communication path between vehicles unreliable. Therefore， the path weight based Ad Hoc on?demand distance vector （PA?AODV） routing algorithm is proposed to enhance the path stability. In PA?AODV routing， the path quality factor and moving direction factor are computed， then the weight of path criterion is calculated， and the transmission data with light path weight is selected optimally. The simulation results show that the PA?AODV routing can improve the packet transfer ratio， and shorten the end?to?end transmission delay.

Keywords： VANET； on?demand distance vector； link quality； moving direction； path weight； transmission delay reduction

0 引 言

车联网（Vehicle Ad Hoc Networks，VANETs）有望成为智能交通系统的实现技术[1]，已受到广泛关注。VANETs为车辆间的信息交互提供了平台，进而提高了车辆行驶安全。然而，与移动自组织网络不同，VANETs具有鲜明特性，如车辆的快速移动、拓扑动态变化、车辆分布不均匀等。这些特性给VANETs的路由技术提出了挑战[2]。

典型的路由协议有地理信息路由、表格驱动型路由、按需式路由。其中，地理信息路由常引用贪婪转发策略，选择离目的节点近的节点作为下一跳转发节点。它无需全局网络拓扑信息，只需依据节点的位置信息决策路由，易实现。但地理信息路由常存在路由空洞问题。为此，文献[3]提出了地理信息路由的改进协议GPCR。一旦节点遭遇路由空洞，就不再采用贪婪转发，而是引用边界转发策略。节点引用右手规则，搜索转发节点。此外，文献[4]也提出基于地理路由的改进协议：基于感知空洞形状的分段贪婪路由（Easy Modeling Greedy Routing，EMGR）。EMGR协议先利用探测包收集边界信息，然后再依据空洞形状决策路由。而典型表格驱动型路由有OLSR[5]，DSDV[6]。与表格驱动型路由相比，按需路由协议（如AODV[7]，ABR[8]）。只有需要传输数据时，才进行路由发现。因此按需路由受到广泛关注。然而传统的AODV协议也存在不足。

文献[9]提出了基于链路生存时间的改进路由协议（Enhanced Routing Protocol on Ad Hoc On?demand Distance Vector with Speed Variance，SV_AODV）。SV_AODV路由协议计算每条链路的速度方差，再选择速度方差最小的路径传输数據，提高了链路的稳定性。此外，文献[10]也提出了AODV路由的改进协议AODV_D。AODV_D协议考虑了MAC层的节点竞争信息和接口队列时延，降低了传输时延。而文献[11]也提出AODV的优化协议。先基于单播和广播结合策略，实现路由探测，并通过降低广播帧数量，增强路由稳定性。

本文针对车载自组织网络VANETs的城市场景，并结合AODV协议，提出基于路径判据的AODV的路由协议PA?AODV（Path?weight?AODV）。PA?AODV协议引用跨层设计，利用物理层和MAC层获取链路质量信息，并修改AODV协议的路由发现机制。具体而言，先计算链路质量，进而估计路径判据权重，最终选择权重最小的路径传输数据包。仿真结果表明，提出的PA?AODV协议能够有效提高数据包传递率，并降低端到端传输时延。

1 相关工作

按需距离矢量（Ad Hoc On?demand Distance Vector，AODV）路由属于反应式路由。AODV允许在多个移动节点间实现动态、自发式多跳通信连通。当需要建立一条路由传输数据包时，节点（源节点）就向下一跳邻居节点广播请求数据包（Route Request，RREQ），触发路由发现过程。一旦接收了RREQ包，节点就转发RREQ包，直到RREQ包被传递至目的节点。

一旦目的节点接收了RREQ包，它就沿着此路径向源节点回复（Route Replay，RREP），并且忽略随后所接收的RREQ包。换而言之，目的节点选择第一条到达的路径作为数据传输路径。AODV的路由发现过程如图1所示。图1a）中，源节点1广播RREQ控制包，其邻居节点通过广播将RREQ传输到目的节点8。

2 PA?AODV协议

PA?AODV协议利用节点的方向以链路质量选择路径。先通过物理层和MAC层传递链路信息以及节点信息，再估计路径质量、移动方向因子，最终计算路径判据权值。

2.1 路径质量因子

一条路径可能有多边链路构成。路径的质量取决于链路质量，若某条链路断裂，则该条路径也将断裂，无法完成数据的传输。因此，对于每条路径而言，其低质量的链路数越多，该条路径质量越差。

为此，先引用文献[11]中指标（Link Quality Indicator，LQI）表征链路质量，然后再依据数据包传递率（Packet Delivery Ratio，PDR）[12]设置链路质量门限值[LQIth]。当某条链路质量LQI低于[LQIth]，则说明此链路质量较差。最后统计每条路径中的低质量链路数[QL]。

接下来，设定链路质量门限值[LQIth]。为了更好地设置[LQIth]，利用实验测量LQI和PDR。当链路的PDR大于80%，则认为该条链路是稳定的，并取其对应的LQI作为门限值。通过实际的室内场景，利用芯片CC2420作为节点，获取LQI和PDR的数据关系，如图2所示。在LQI=220时，LQI开始达到80%。因此，[LQIth=][80%]。

2.2 移动方向因子

不失一般性，可认为两车辆之间要么以相同方向行驶，要么以相反方向行驶，并且车辆行驶方向受限于街道和十字路口。由于车辆行驶方向的两极性，相比于反方向车辆间的路由，处于同方向行驶的车辆间的路由更趋于稳定。

车辆移动方向对车辆间的通信连通时间有直接影响。为此，在选择路径时，也需考虑组建路径的节点的移动方向。为了表述简单，将构成路径的节点（除源节点和目的节点外）称为中间节点。若链路的中间节点的移动方向与源节点和目的节点的连线方向的夹角一致（所谓的移动方向一致是指它们的夹解小于门限值），则它们的链路稳定性得到提高，相应地增加路径的持续时间。

如图3所示，设定节点[i]在[t1]时刻的位置为[（x1，y1）]，在[t2]时刻它移动到了位置[（x2，y2）]。拥有数据包的节点[C]的位置是[（xc，yc）]，目标节点[D]的位置为[（xd，yd）]。在这种情况下，邻居节点[i]的移动速度，数据包转发方向与节点移动方向之间的切角由式（4）和（5）计算得到：

2.3 路由判据权值

在传统的AODV路由协议中，目的节点只选择第一时间到达的RREQ包所传输的路径。显然，首次到达的RREQ的传输路径未必是最稳定的。为此，PA?AODV协议考虑多条路径，并计算每条路径的路径判据权值，再选择权值最小的路径传输数据包。

具体而言，路径[P]的判据权值融合了路由质量因子和移动方向因子，如式（8）所示：

2.4 数据包传输流程

一旦节点需要传输数据包，它就向邻居节点传输RREQ包。由于PA?AODV协议需要计算路径判据，在传统的RREQ包中添加了链路质量和方向变量。RREQ包的格式如图4所示。

每个接收节点将自己的链路质量和方向变量加入RREQ包再传输。当目的节点接收后，计算每条路径判据权重，并选择路径权重最小的路径回复RREP。

RREQ和RREP的传输流程如图5所示。一旦接收到RREQ包，节点首先判断之前是否已接收过同样ID的数据包，若是，则丢弃。再判断自己是否为目的节点，若是，则计算路径判据权重，并选择权重最小的路径回复RREP。否则，就将自己的链路质量和方向变量信息加入RREQ，并转发。

3 实验分析

3.1 仿真模型

利用OMNET++，SUMO建立仿真平臺。OMNET++[13]是一款基于离散事件仿真器的开放源代码，可用于模拟通信网络和分布式系统。而SUMO[14]可用于模拟大型的交通网络以及车辆移动模型。因此，OMNET++用于网络仿真，而SUMO用于道路交通仿真，并利用Manhattan计量法产生网格状的城市道路，选取[3×2]道路网格以及十字路口模型，如图6所示。

选择3 968 m×1 251 m的矩形区域道路区域，其中道路有370条、十字路口124个。同时利用STRAW（Street Random Way）产生车辆移动数据。

仿真区域内车辆数从100～350变化，车辆运行速度从40～70 km/h变化，车辆通信范围为300 m。数据包产生率为6 packet/s，数据包大小为512 B，信道带宽为2 Mb/s，仿真时间为350 s。每次实验独立重复100次，取平均值作为实验数据。

此外，为了更好地分析PA?AODV协议性能，选择AODV，GPCR路由协议进行同步仿真，并与PA?AODV协议进行比较。同时，选择数据包传递率、平均路由跳数以及端到端传输时延作为路由性能指标。

3.2 仿真结果及分析

1） 数据包传递率

本次实验主要考查车辆数对数据包传递率的影响。车辆数从100～350变化，且步长为50，车速为50 km/h。三个协议的数据包传递率随车辆数的变化曲线如图7所示。

依据图7的数据可知，PA?AODV协议的数据包传递率较高，优于GPCR和AODV协议。随着车辆数的增加，优势越发明显。而GPCR路由的数据包传递率最低，尤其是在低密度区域。当车辆数小于200时，数据包传递率不到55%。原因在于GPCR协议在选择转发数据包时，只依据节点的距离选择转发节点，并没有考虑到链路质量信息，导致路径不稳定，降低了数据包传递率。而相比于GPCR协议，AODV协议的数据包传递率较高，但它仍低于PA?AODV协议。这主要是因为：PA?AODV协议在选择传输路径时，充分考虑了每条链路的质量，增加了路径的稳定性，最终提高了数据包传递率。

2） 平均端到端传输时延

三个协议的平均端到端传输时延随节点数的变化曲线如图8所示。PA?AODV协议的平均端到端传输时延最低，且较平稳，并没有随节点数变化而波动。而AODV协议的平均端到端传输时延较高，高于GPCR协议。这主要是因为AODV协议在进行路由发现阶段采取了RREQ和RREP控制包，增加了一定的时延。而GPCR协议的端到端传输时延略低于AODV，这主要归结于GPCR协议总是选择离目的节点近的节点作为转发节点，降低了传输跳数，进而减少了一定的传输时延。

3） 平均传输跳数

三个协议的平均传输跳数随节点数的变化曲线如图9所示。

从图9可知，GPCR协议的平均传输跳数最低，这也符合GPCR路由选择策略。而PA?AODV协议的平均传输跳数略高于AODV协议。原因在于：AODV协议只考虑第一时间的到达传输路径传输数据，既然是第一时间到达的路径，相应地它的跳数较少。而提出的PA?AODV协议并没有从到达路径的顺序选择路由，而是从路径质量方面考虑，因此增加了平均传输路数。

4 结 语

本文针对VANETs的路由问题，提出基于路径判据的按需距离矢量PA?AODV路由算法。PA?AODV路由算法充分利用AODV路由的特性，并对其路由决策进行了改进。通过计算路径判据权重，并择优选择权重小的路径传输数据，进而提高路径稳定性。实验数据表明，提出的PA?AODV路由减少了数据包丢失率，也缩短了端到端的传输时延。

参考文献

[1] MISRA S， KRISHNA P V， SARITHA V. LACAV： an energy?efficient channel assignment mechanism for vehicular Ad Hoc networks [J]. Journal of supercomputing， 2012， 62（3）： 1241?1262.

[2] GHAFOOR K， BAKAR K. A novel delay and reliability aware inter vehicle routing protocol [J]. Network protocols and algorithms， 2014， 2（2）， 66?88.

[3] LOCHERT C， MAUVE M， HARTENSTEIN H. Geographic routing in city scenarios [J]. Mobile computing and communications review， 2015， 9（1）： 69?72.

[4] 范敏，谢思佳，石为人，等.基于空洞模型的地理位置路由改进算法研究[J].传感技术学报，2012，25（11）：1556?1561.

FAN Min， XIE Sijia， SHI Weiren， et al. Research on improved algorithm of geographical route based on cavity model [J]. Journal of transduction technology， 2012， 25（11）： 1556?1561.

[5] EI W， BEN G， SAFA H. MOLSR： mobile?agent based optimized link state routing protocol [C]// Proceedings of 2015 International Wireless Communications and Mobile Computing Conference. Dubrovnik， Croatia： IEEE， 2015： 355?360.

[6] PERKINS C E， BHAGWAT P. Highly dynamic （DSDV） for mobile computers routing [C]// Proceedings of 1994 ACM Conference on Communications Architectures， Protocols and Applications. London： ACM， 2014： 234?244.

[7] LEE S J， BELDING E M， PERKINS C E. Ad Hoc on demand distance?vector routing scalability [J]. ACM sigmobile mobile computing and communications review， 2012， 6（3）： 94?104.

[8] TOH C K. Associativity?based routing for Ad Hoc mobile networks [J]. Wireless personal communications， 1997， 4（2）： 103?139.

[9] 曹文君，薛善良.一种适用于城市车联网的改进的AODV协议[J].计算机与现代化，2016，23（7）：98?103.

CAO Wenjun， XUE Shanliang. An improved AODV protocol for urban vehicle network [J]. Computer and modernization， 2016， 23（7）： 98?103.

[10] 刘大勇，赵春江.基于AODV的农田无线传感器网络路由和休眠算法[J].微电子学与计算机，2015，32（10）：115?120.

LIU Dayong， ZHAO Chunjiang. A route and sleep algorithm for farmland wireless sensor networks based on AODV [J]. Microelectronics & computer， 2015， 32（10）： 115?120.

[11] 蔡菁，朱余兵.一种基于AODV改进的城市车载自组网络路由协议研究[J].计算机工程与科学，2013，35（1）：61?66.

CAI Jing， ZHU Yubing. Research on a routing protocol based on AODV improvement for urban vehicle?borne network [J]. Computer engineering and science， 2013， 35（1）： 61?66.

[12] MAMMU A S， HERNANDEX J U， SAINZ N. Cross?layer cluster?based energy?efficient protocol for wireless sensor networks [J]. Sensors， 2015， 15（4）： 8314?8336.

[13] IEEE Computer Society. Wireless medium access control and physical layer specifications for low?rate wireless personal area networks [S]. New York： IEEE， 2010.

[14] SAMUNDISWAY P， BHARDWAJ H. Performance analysis of energy aware AODV routing protocol for IEEE 802.15.4 enabled WSN [J]. International journal of computer applications， 2013， 63（19）： 43?46.

[15] OpenSim Ltd. OMNeT++ discrete event simulator [EB/OL]. [2017?03?11]. http：//www.omnetpp.org/.

[16] KRAJZEWICZ D， ERDMANN J， BEHRISCH M. Recent development and applications of SUMO： simulation of urban mobility [J]. International journal on advances in systems and measurements， 2012， 5（3）： 128?138.