车载网中面向高速场景的路由算法

臧冠男+沈继伟+林洋

摘 要： 有效地传输数据是提高车联网应用性能的关键。而动态的拓扑结构，给车联网的数据传输提出了挑战。为此，提出基于路径连通概率的车联网路由算法CPB。首先，依据高速公路场景，建立一维车辆移动模型，然后再计算链路的连通概率，最后，计算路径的连通概率，并选择连通概率最高的路径传输数据。仿真结果表明，提出的CPB算法能够有效地提高数据包传递率、端到端传输时延以及吞吐量性能。

关键词： 连通概率； 路由； 移动模型； 路径； 时延； 车联网

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）04?0164?05

Abstract： Effective data transmission is the key to improving the application performance of vehicular ad hoc networks （VANETs）. However， dynamic topology is a great challenge for VANETs′ data transmission. Therefore， a path connection probability based routing algorithm for VANETs is proposed. The one?dimensional vehicle mobility model is established according to the highway scenario. The link connection probability is computed. The path connection probability is computed， and the path with maximum connection probability is selected to transmit data. The simulation results show that the proposed CPB algorithm can effectively improve the performance in delivery ratio of data packet， end?to?end transmission delay and throughput.

Keywords： connection probability； routing； mobility model； path； delay； VANETs

目前，汽车已成为民众出行的首选交通工具，汽车便捷民众的日常出行，然而，随着汽车数量的增加，道路拥塞、交通安全问题也日益突出。据不完全统计，交通事故已成第二大杀手。世界卫生组织WMO指出每年约130万人死于交通事故，约5 000万人受伤[1]。据此，政府部门以及科研机构开始商讨、并提出利用智能交通概念，提高交通安全。作为智能交通系统的最有前景技术，车联网 （Vehicular Ad hoc Networks，VANETs）受到广泛关注。典型的车联网结构如图1所示。装有OBU模块的车辆能够与其他车辆、路边设施进行通信。其中车与车之间的通信称为车间通信V2V（Vehicle to Vehicle），而车与路旁设备通信称为车?旁通信V2R（Vehicle to Roadside unit）。车辆间通过实时交互路状信息，实现对事故的预警以及避让，进而提高交通管理效率以及交通安全。据美国交通局统计，通过车联网技术平台，能够将交通事故率降低82%。从技术层面而言，车联网VANETs属于移动自组织网络，但VANETs具有鲜明的特性，如动态的拓扑、受限的移动模型、车辆的高速移动。这些特性给VANETs的消息传输提出了挑战。据此，众多研究学者关注VANETs中的路由技术[2?4]。

值得注意的是，车辆移动受限于道路的拓扑结构，并且道路的拓扑结构是静态，至少在短时间内道路结构是不会变化的，这一特性给车辆移动预测提供了基础。通过对车辆移动的预测，可有效地计算链路的连通特性，包括连通概率、连通持续时间等。

文献[5]提出基于链路连接概率的路由协议。先计算链路连接概率，并由此估算链路连通时间，从而选择最稳定、可靠的路径作为数据传输通道。文献[6]提出面向高速道路场景的车辆移动预测模型。此外，文献[7]也提出基于移动预测的MOPR路由协议。MOPR协议先预测车辆的下一时刻位置，然后再估算数据传输至此位置所需的时间。随后，检测链路在数据传输时间内是否一直保持连接状态。

本文基于上述文献的分析，考虑到VANETs的移动区域局限性、移动信息的可预测性，提出基于路径连通概率的VANETs路由算法CPB（Connected Probability?Based routing）。CPB算法通过路径连通概率决策路由可提高路由应对动态拓扑的鲁棒性。

1 网络模型

本文以高速公路为研究对象，并建立相应的网络模型。依据IEEE 802.p的标准，车辆的一跳通信半径为300 m，其远大于道路宽度。据此，可将高速公路场景模拟成一维的网络模型。

2 CPB协议

CPB协议在传输数据时，总是选择连通概率最高的路径作为数据传输路由。

2.1 连通概率

当源节点（车辆）需要向目的节点传输数据时，源节点首先需要计算自己与下一跳节点间连通概率，换而言之，选择连通概率最高的节点作为下一跳转发节点，如图2所示。

由图2可知，源节点A与目的节点C均沿左向右行驶。假定节点A，B和B，C间距离表示为[dAB]，[dBC]。相应地，[dAC]表示节点A，C间的距离。如果距离[dAC]小于通信范围[R]，则直接通信。反之，节点A需要选择下一跳节点作为转发节点。接下来，以图2为例，分析选择下一跳节点的过程。endprint

若节点A在时刻[t=0]进入系统，而在时刻[t=t1]节点A的位置为[x]，且[x∈-2R，2R]。此时节点A与目的节点C构建了数据传输路径。由于它们彼此不在一跳邻域通信范围内，需要通过中间转发节点进行转发数据。转发区域为图2所示的阴影区域，即在[-R，x+R]区域为它们的转发区域[10]。若在该区域内存在节点，则这些节点可成为转发节点。

最后，源节点选择连通概率最大的路径作为数据传输通道。

以图3为例，描述CPB协议的路由决策过程。源节点A首先发送路径请求消息[Mes_req]，接收节点B先计算与节点A的连接概率，再将此概率值载入[Mes_req]，并转发。每个接收节点均重复上述过程，直到目的节点F接收到此消息[Mes_req]。

由图3可知，由[A→B→C→E→F]和[A→B→D→E→F]两条路径到节点F，并且这两条路径的连通概率[PPathl]分别为0.028 8，0.048。这表明路径[A→B→D→E→F]比路径[A→B→C→E→F]的連接时间更短，路径更趋于稳定。因此，节点F选择路径[A→B→D→E→F]，并沿着该路径的反方向向源节点A回复ACK消息，如图3b）所示。

3 性能分析

3.1 仿真场景

考虑长为[L=4 000 m]的三车道的高速场景，车辆通信半径为300 m，如图4所示，具体仿真参数见表1。

在仿真过程中，选择VADD[12]和AODV[13]路由算法作为参考，并与CPB算法进行比较。AODV路由是经典的车联网路由协议，而VADD路由也是以提高数据传输率为目的路由协议。这两个路由与CPB路由具有可比性。此外，从吞吐量、数据传输的端到端传输时延以及数据包传递率三方面分析路由算法的性能。

3.2 数值分析

接下来，分析车辆速度对端到端传输时延（E2E）、吞吐量（Throughput）以及数据包传输率的影响。

3.2.1 端到端传输时延

平均速度越高，端到端时延越大。原因在于车速的提高，加剧了拓扑结构的动态变化，降低了路径的连通率，使得路由不稳定。最终，就增加传输时延。相比于AODV和VADD路由算法，CPB算法的时延得到有效的缩减。这归功于CPB算法依据路径的连通率决策路由，避免了连通率的路径作为数据传输，提高了路由的稳定性。平均时延随平均车速的影响如图5所示。

3.2.2 数据包传递率

数据包传递率随车速变化情况如图6所示。平均车速越大，数据包传递率越低，这与图5的数据相类似。车速越大，路径越不稳定，数据传输效率越低，最终降低了数据包传递率。所以本文提出的CPB算法数据包传递率优于AODV和VADD路由算法。

吞吐量随车速的增加而下降，这主要是因为车速的提高增加传输时延（如图5所示），降低了传输效率，同时，又减少了数据包传递率（如图6所示），最终导致数据吞吐量的下降。然而，由于CPB路由算法依据路径连通率选择路由，提高了应对动态拓扑变化的能力。

4 总 结

本文针对车联网的数据传输问题，提出基于路径连通概率的路由算法CPB。CPB算法考虑了车辆的高速移动对路由稳定性的影响，可计算链路的连通率，并估算路径的连通概率。在决策路由时，总是选择连通概率最高的路径作为数据传输通道，进而提高数据的传输效率。仿真结果验证了路由算法的性能。与AODV和VADD路由算法相比，CPB路由算法的端到端传输时延、吞吐量以及数据传递率性能均得到有效的提高。

参考文献

[1] CASTEIGTS A， NAYAK A， STOJMENOVIC I. Communication protocols for vehicular ad hoc networks [J]. Wireless communications & mobile computing， 2011， 11（5）： 567?582.

[2] SHAFIEE K， LEUNG V C M. Connectivity?aware minimum?delay geographic routing with vehicle tracking in VANETs [J]. Ad hoc networks， 2011， 9（2）： 131?141.

[3] BISWAS S， MORRIS R. Opportunistic routing in multi?hop wireless networks [J]. ACM SIGCOMM computer communications review ， 2004， 34（1）： 69?74.

[4] HARRI J， FIORE M， FILALI F. Vehicular mobility simulation with VantMobiSim [J]. Simulation， 2011， 87（4）： 275?300.

[5] LI Y， CHEN W， ZHANG Z L. Optimal forwarder list selection in opportunistic routing [C]// Proceedings of the IEEE international conference on mobile ad hoc & sensor systems. Macau： IEEE， 2009， 62（124）： 670?675.

[6] NAMBOODIRI V， GAO L. Prediction?based routing for vehicular ad hoc networks [J]. IEEE transactions on vehicular technology， 2012， 56（4）： 2332?2345.

[7] MENOUAR H， LENARDI M， FILALI F. A movement prediction?based routing protocol for vehicle?to?vehicle communications [C]// Proceedings of International V2V Communications Workshop. San Diego： [s. n.]， 2005： 1?7.

[8] Hafeez K， Zhao L， Liao Z， et al. Impact of mobility on VANETs′ safety applications [C]// Proceedings of Global Telecommunications Conference. Miami： IEEE， 2010： 1?5.

[9] ZHAO M， LI Y， WANG W. Modeling and analytical study of link properties in multi?hop wireless networks [J]. IEEE transactions on communications， 2012， 60（2）： 445?455.

[10] 王佩雪，罗菁.VANETs中基于链路的可持续时间路由方案[J].科学技术与工程，2014，14（25）：267?271.

WANG Peixue， LUO Jing. Link?sustainable time?based routing in vehicular ad hoc networks [J]. Science technology and engineering， 2014， 14（25）： 267?271.

[11] 张莉华，张得生.基于连接概率的VANETs路由协议研究[J].现代电子技术，2016，39（7）：19?23.

ZHANG Lihua， ZHANG Desheng. Research on VANETs routing protocol based on connection probability [J]. Modern electronics technique， 2016， 39（7）： 19?23.

[12] ZHAO J， CAO G. VADD： vehicle?assisted data delivery in vehicular ad hoc networks [J]. IEEE transactions on vehicular technology， 2011， 57（3）： 1910?1922.

[13] XIA Zijun， LIU Chunfeng， ZHAO Zenghua. Routing algorithm in vehicular ad hoc network based on link prediction [J]. Computer engineering， 2012， 38（4）： 110?111.endprint