关于VANETs路由协议的研究现状与进展*

，

(1.广州大学 机械与电气工程学院，广东 广州 510006；2.广州大学 计算机科学与教育软件学院，广东 广州 510006)

0 引 言

车载自组网络(vehicle Ad Hoc networks,VANETs)是移动网络的一个特例。VANETs可实现车与车之间、车与路边基础设施通信。该通信可实现信息共享，有助于事故预警、交通信息查询等多种应用[1]。随着各项技术日益成熟，VANETs也将成为物联网的典型应用之一[2]。

由于VANETs网络动态性强，车辆移动快速，拓扑结构变化不定，传统的路由算法难于适应VANETs。另外，由于VANETs应用环境多样化，车辆密度随时间、地点变化迅速，导致车辆间的连通性呈机会性。在上下班高峰时区，道路上的车辆较多，车辆连通性高。然而，在午夜时区，道路上的车辆稀少，车辆连通性极低。此外，高速行驶的车辆，相遇交互时间甚短，研究表明：车辆通信的窗口平均时长为15 s。VANETs的这些鲜明的特性给设计VANETs的路由协议提出挑战。

为此，研究者在设计VANETs路由时，应充分利用VANETs这些特点，可从车辆移动性、通信的连通率、路边的基础设施、节点的地理位置方面去决策路由方案。

在VANETs中，节点相互安装收发器，形成通信的连通。如经典的按需路由AODV[3]、动态源路由(DSR)[4]，其是将移动自组网(mobile Ad Hoc networks，MANETs)的路由技术扩展到VANETs。文献[5～8]均属基于连通性路由。

VANETs节点具有快速移动性、移动范围大、移动空间受限等特性(交通规则)，许多路由方案均利用这些特性去预测路由，PBR[9]，Abedi[10],NiuDe[11],文献[12]利用车辆的移动参数建立路由。

研究者也借鉴蜂窝网络的理论，利用路边基础设施辅助VANETs车辆通信，如蜂窝基站、日用的公交巴士等。特别在车辆稀疏区域，借助于路边的基础设施在实现数据包的传递，从而增强通信的健壮性、鲁棒性、安全性。如文献[13～16]。

随着全球定位系统(global positioning system,GPS)日益普及和电子地图广泛应用，这为基于地理位置路由协议应用提供了条件。基于地理位置路由利用车辆的地理位置信息而不是拓扑的连通信息去构建路由,例如：文献[17～20]。

由于VANETs节点通信呈机会性，不少学者将概率理论应用于VANETs，其充分利用节点移动信息和链路机会性。为此，研究人员提出基于概率统计理论的路由策略。文献[21～24]均利用概论理论构建路由。

本文依据VANETs网络特性将路由协议分成基于基础设施、移动预测、地理位置、概率以及连通的路由。

1 VANETs路由

1.1 基于连通路由

基于连通路由广泛采取广播的形式，如泛洪路由，通过节点不断广播传递数据包，节点收到数据包后，向邻居车辆广播，直至数据传递到目的地才停止广播，泛洪简单,易实施，操作性强。如果是单播消息，目的节点只有一个，泛洪就不再适用，因为不断地广播会增加网络负担，但如果目的节点均在一跳通信范围内，采用泛洪路由可提高路由性能，因为泛洪总是能将数据传递到目的节点。然而，在VANETs网络中，往往数据需要经多跳传递才能到达目的节点，随着多跳通信数目的增加，网络的性能快速下降，当节点的数量较大时，会引发广播风暴。

Li X等人[6]提出节点不相交的多路径路由(node-disjoint multipath routing，NDMR) 算法。NDMR结合了定向图理论，采用广播方式传递控制消息，转发节点根据控制消息决策路由，有效地降低了路由开销。Korkmaz G等人[7]采用城市多跳广播路由方案,通过电子地图获取道路信息，并针对道路交叉口、非交叉口应用不同的广播模式。交叉口广播模式应用交叉口处，而定向广播应用于非交叉口处。

在CAID[8](context-adaptive information diffusion)中，采用节点与数据包的相关性实施数据包转发,相关性大的节点具有转发数据包的权限,节点融合数据包、车辆移动信息计算相关性。此方案提高了数据包的传输效率和通信资源利用率。

1.2 基于移动预测路由

快速移动是VANETs的显著特点,这个特点加速了网络拓扑结构不稳定性，并减少了链路的使用寿命，降低了路径稳定性。

尽管节点的高速移导致VANETs路由性能下降，但节点的移动具有一定的规律性，在一定程度上可以预测其移动信息,如在高速公路上移动的节点(车辆)，其行驶轨迹局限于道路，同时速度也限定于交通规则范围内。因此，节点的移动信息具有可预见性，在设计路由协议时，应充分利用这一特点，通过预先获取节点的移动速度、方向等数据，计算潜在链路的信息，如链路的可用的时间，使路径趋于稳定,这就是基于移动预测路由的基本理论。

在决策路由时，先预测链路的生命周期，选取生命周期长的链路组建路径，并对即将断裂的链路进行了修复或替换。根据节点速度、方向、加速度等运动参数，计算链路的生命周期。

针对高速公路场景，Namboodiri V[9]提出预测移动模型。该通信模型预测链路的使用寿命，在链路未断裂前，进行维护，从而保证数据成功地传递。同时，针对节点快速移动，Abedi O[10]提出AODV的优化方案,根据方向、位置、速度等运动参数决策路由,在3个参数中，方向参数的权值最大，这主要是因为由同一方向的节点所建立的路径，比处于不同方向的节点所构建的路径更趋于稳定、路径可用持续时间更长。Niu Z等人[11]采用数学理论，提出基于链路的生命周期、交通密度信息的可靠链路数学模型。Noppakum Y等人[12]提出基于权值系数的路由算法，该方案通过电子地图获取道路拓扑结构，并结合节点速度和交通时况，计算链路的权值，只有满足条件的链路，将就此链路加入到可用路由路径表中。

1.3 基于基础设施路由

基于基础设施路由的思想就是将路边基础设施RSU作为通信的中继节点，由于RSU位置固定，可有效提高通信的稳定性。通过RSU，有助于数据的可靠传输，提高VANETs通信的连通率。基于基础设施路由常用RSU形成主干链路，一旦通信链路断裂，可实施存储—转发机制。当然，利用RSU辅助节点通信有着明显的优势，但也存在 2个问题：一是在道路边如何部署RSU，巨大的道路面积，不可能沿道路边全部部署RSU；二是即使部署了RSU，一旦RSU损坏，如地震，数据传输线路将破坏，网络将面临瘫痪。

DRR(differentiated reliable routing)[13]方案将RSU作为虚拟设备。在通信过程中，RSU与道路中的节点建立通信，实时更新节点信息,同时，节点与RSU保持同步。在文献[14]中作者针对城市环境，采用了面积的街道的路由协议SARC。该方案实施了节点隐私保护环节，分别在路由发现、数据转发2个阶段对节点的位置隐私进行保护。

文献[15]提出静态点辅助路由协议SADV方案。SADV主要由链路延时更新(link delay update,LDU)、多路径数据分发(multipath data dissemination,MPDD)以及静态点辅助转发(static node assisted routing,SNAR)组成，分别实现传输时延更新、延迟最小路径的计算、多路径数据分发。同时，SADV针对节点所在的位置，实施路段模式和交叉口模式交替的方式转发数据包。Kitani T等人[16]提出基于公交巴士消息摆渡方案,实施收集消息、存储—转发(carry and forward)的策略。

1.4 基于地理位置路由

Karp B等人[17]于2000年率先提出基于贪婪算法的地理位置路由(greedy perimeter stateless routing，GPSR)协议。在GPSR方案中，实施贪婪转发、周边转发2种模式，分别使用于不同的情况。前者通过距离值选择下一跳节点，离目标节点最近节点作为下一跳节点。一旦贪婪模式不能转发数据包时，就选用周边转发模式，与贪婪模式不同的是，其采用右手法则转发数据包。然而，GPSR具有局限性，在遇到路由空洞时，GPSR就不再适用。

如图1所示，转发节点S向目的节点D传递数据。在数据传递到节点B时，节点B采用贪婪转发无法找到下一跳节点，将这种情况称为路由空洞。为此，文献[18]提出存储—转发。在遇到路由空洞时，节点先将数据包存储，等待下一转发节点进入其通信范围。一旦有节点，将恢复原来GPSR的转发机制，将数据包传递目标节点。

图1 节点B遭遇局部最优化

Giudici F等人[19]提出STAR算法。网络中的节点建立交通流量和邻居信息表,节点在决策路由时根据表内信息、选择最短路径，并采用贪婪转发。仿真表明：STAR的路由性能优于GPSR,但是STAR是以占用更多资源为代价的。GyTAR(improved greedy traffic aware routing)[20]方案利用车辆密度信息，并在协议中设置锚点，通过锚点的数据信息决策路由。同时，锚点间通信基于贪婪算法，若遇到路由空洞，启用缓存转发机制。

1.5 基于概率路由

由于VANETs拓扑结构不断变化，节点通信呈机会性,为此，研究人员结合概率统计理论，提出基于概率路由方案。通过计算无线链接可用时间分布，或已存在的链接在一段时间后仍然未断裂的概率。基于概率路由的实施是以在一定假设为条件,其需要建立网络传播模型，通过这些模型才能统计相关变量的分布信息。

Jiang H等人[21]提出REAR(reliable and efficient alarm message routing),REAR通过计算无线信道所收到的警告信息的概率，并以此信息为依据决策路由。VADD(vehi-cle-assisted data delivery)[22]融合移动车辆的位置和方向信息，计算数据包传递到目的节点的概率。针对节点所处位置的不同，实施Straightway,Intersection以及Destination转发模式。在道路交叉口使用Intersection模式,离开道路交叉口使用Straightway模式，靠近目标的节点使用Destination模式。由于节点的快速移动，VADD所计算的数据包转发的概率往往滞后节点的移动。

Wu Z等人[25]提出DTSG(dynamic time-stable geocast)方案。将网络区域划分为相关区域(zone of relevance，ZOR)、转发区域(zone of forwarding，ZOF)。前者是指目标节点所在的区域，后者是指转发节点所在的区域。该方案首先在ZOR广播数据包，并将广播持续到预设的时间。可根据不同应用环境，设置不同的广播时长。

2 五类路由特点比较

五类路由协议特点如表1所示[23]。

表1 各类路由协议的优缺点

3 结 论

路由协议应具有适应各种环境，并将数据稳定、可靠、安全地进行传输，因此，应从以下要求设计路由：

1)稳定性：将数据可靠、稳定传输是路由协议的根本任务，特别是安全信息，路由协议的稳定性显得尤为关键。

2)自适应性：由于VANETs,所处环境复杂多变，路由协议应能适应各种环境，在不同网络环境下应具鲁棒性，面对复杂环境自我调整。另外，网络中的突变[31]如数据包的碰撞、信号误码等，严重影响路由协议性能，因此，协议的自适性是重要的参数。

3)安全性：现有的大多数路由协议在设计路由协议时，并没有考虑节点信息的保护问题，而节点的隐私信息的保护在VANETs中特别重要，为此，在路由协议中如何保护数据的安全性需要解决的问题。

参考文献:

[1] Perkins C E,Royer E M.Ad Hoc on-demand distance vector routing[C]∥Proc of IEEE Workshop on Mobile Computing Systems and Applications (WMCSA),2011:90-100.

[2] Lee J H,Chilmakurti N.Performance analysis of PMIPv6 based network mobility for intelligent transportation systems[C]∥IEEE Transaction on Vehicular Technology,2011:23-32.

[3] Lochert C,Hartenstein H,Tian J.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Intelligent Vehicles Symposium,2012:156-161.

[4] Johnson D B,Maltz D A,Hu Y C.The dynamic source routing protocol for mobile Ad Hoc networks[C]∥Published Online,IETF MANET Working Group,Tech Rep 2007：153-181.

[5] Perkins C E,Bhagwat P.Highly dynamic destination-sequenced distance-vector routing for mobile computers[J].SIGCOMM Comput Commun Rev,1994,24(4): 234-244.

[6] Li X,Cuthbert L.On-demand node-disjoint multipath routing in wireless Ad Hoc network[C]∥Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks,LCN’04,Washington DC,USA,IEEE Computer Society,2004:419-420.

[7] Korkmaz G,Ekici E,Ozguner F,et al.Urban multi-hop broadcast protocol for intervehicular communication systems [C]∥Procee-dings of the 1st ACM International Workshop on Vehicular Ad Hoc Network,2004:76-85.

[8] Adler C,Eichler S,Kosch T,et al.Self-organized and context-adaptive information diffusion in vehicular Ad Hoc network-s[C]∥Proceedings of the 3rd International Symposium on Wireless Communication Systems,2006:307-311.

[9] Namboodiri V,Gao L.Prediction-based routing for vehicular Ad Hoc networks[J].IEEE Transactions on Vehicular Technology,2007,56( 4): 2332-2345.

[10] Abedi O,Fathy M,Taghiloo J.Enhancing AODV routing protocol using mobility parameters in vanet [C]∥Proceedings of the 2008 IEEE/ACS International Conference on Computer Systems and Applications:IEEE Computer Society,2008:229-235.

[11] Niu Z,Yao W,Ni Q,et al.Dereq:A QOS routing algorithm for multimedia communications in vehicular Ad Hoc networks [C]∥Proceedings of the 2007 International Conference on Wireless Communications and Mobile Computing,New York,2007:393-398.

[12] Noppakum Y,Phongsak K.AODV improvement for vehicular networks with cross layer technique and mobility prediction[J].Intelligent Signal Processing and Communication Systems,2011,8(2):89-95.

[13] He R,Rutagemwa H,Shen X.Differentiated reliable routing in hybrid vehicular Ad Hoc networks[C]∥IEEE International Conference on Communications(ICC),2008:2353-2358.

[14] Kim H,Paik J,Lee B,et al.Sarc: A street-based anonymous vehicular Ad Hoc routing protocol for city environment[C]∥Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing,Washington,2008:324-329.

[15] Ding Y,Wang C,Xiao L.A static-node assisted adaptive routing protocol in vehicular networks[C]∥Proceedings of the Fourth ACM International Workshop on Vehicular Ad Hoc Networks,2007:59-68.

[16] Kitani T,Shinkawa T,Shibata N,et al .Efficient vanet-based tra-ffic information sharing using buses on regular routes [C]∥Vehicular Technology Conference,2008:3031-3036.

[17] Karp B,Kung H T.GPSR: Greedy perimeter stateless routing for wireless networks[C]∥Proc of 6th Annual International Confe-rence on Mobile Computing and Networking,2000:243-254.

[18] Naumov V,Gross T R.Connectivity-aware routing in vehicular Ad Hoc networks[C]∥Proc of 6th IEEE International Conference on Computer Communications,2007:1919-1927.

[19] Giudici F,Pagani E.Spatial and traffic-aware routing for vehicular systems[J].Lecture Notes in Computer Science,2005,3726:77-86.

[20] Jerbi M,Meraihi R,Senouci S M,et al.GyTAR:Improved greedy traffic aware routing protocol for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks,2006:88-89.

[21] Jiang H,Guo H,Chen L.Reliable and efficient alarm message routing in vanet[C]∥Proceedings of the 2008 International Conference on Distributed Computing Systems Workshops,ICDCSW’08,Washington DC,USA,IEEE Computer Society,2008:186-191.

[22] Zhao J,Cao G.VADD: Vehicle-assisted data delivery in vehicular Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2008,2(5):123-128.

[23] 徐会彬，夏 超.VANETs路由综述[J].计算机应用研究,2013,30(1):1-6.

[24] Junichiro F.A probabilistic protocol for multi-hop routing in VANETs[C]∥IEEE International Conference on Communications Workshops,2009:345-352.

[25] Wu Z,Yang Y,Guo X,et al.Analysis of collision probability in IEEE 802.11 based VANETs[J].Acta Electronica Sinica,2010,19(1E):187-190.