An Efficient Data Dissemination Protocol for Vehicular Ad Hoc Networks

文献[6]提出了Epidemic Routing，两个节点相遇时，互相交换各自没有的数据。VADD^[7]则利用了车辆节点移动的可预测性，基于路段流量模式，并根据一些统计数据如路段平均速度估计各路段的数据传输延迟，从而计算一条延迟最短路径。文献[8]认为路段-路段的数据转发比节点到节点的数据转发效率要高，每个路段将缓存数据的多个副本并在路口完成数据转发。TADS^[9]则是一种流量感知的数据分发机制，在路段的直路模式上对贪婪转发进行了改进，在路口基于流量预测模型估计链路质量，从而根据链路质量和到目的节点的距离进行转发。文献[10]针对链路质量问题提出了RS-CBAODV，对传统的AODV算法进行了改进，路由信息存储在客户端以减少车辆节点间断开连接的可能性。文献[11]对基于距离的路由决策机制进行了研究，在路口引入分组碰撞避免机制，并根据自适应的等待时间做出路由决策。然而，仅靠车辆节点之间完成数据传输很难达到期望的传输效率。

为了提高通信效率，路边单元也被引入VANETs。文献[12]对路边单元的放置策略问题进行了研究，通过对几种路边单元辅助通信的机制进行了比较，认为数据应该在路口缓存并在出现最佳路径时转发。文献[13]提出了一种静态节点辅助的地理信息路由协议ETGR，静态节点放置在路口作为骨干节点，并通过中继节点将静态节点连接，从而达到提高通信效率的目的。文献[14]则利用车辆轨迹信息提高传输性能，根据轨迹信息计算更准确的期望传输延迟，以获得更好的路由决策。但是，车辆轨迹信息的分发需要依靠大量部署在路边的接入点设备。由于路边单元成本高昂，停放车辆的闲置资源逐渐引起了人们的关注。文献[15]提出了利用街角的停放车辆连通两个因建筑物阻碍通信的车辆节点；文献[16-17]也讨论了路边停放的车辆有助于车载网络的多跳通信，后者还验证了当车辆停放时间不超过80 h，无需考虑车辆电瓶的耗尽问题。但是都没有提出任何具体的数据分发策略。

假设车辆节点能够通过GPS或其他方式获得自己的位置信息，并配备城市电子地图。车辆节点通过短距离无线信道通信，通信半径为R。令r_ij表示路口I_i到I_j之间的路段，l_ij为路段r_ij的长度，ρ_ij和v_ij分别为路段r_ij上的车辆密度和车辆平均速度。

此外假设一些车辆节点在停放的时候愿意共享其资源，这可以通过一些激励机制实现。实际上，即使没有任何激励，仍然有30%的用户愿意共享资源^[18]。定义ρ_pv为愿意共享资源的停放车辆节点比例。根据文献[17]可知，无需考虑车辆节点的电瓶电量问题。

PVAD的基本思想是利用路边停放车辆的闲置资源辅助数据分发。图 1显示了6个路口(I_i、I_j、I_k、I_l、I_m和I_n)和若干路段。蓝色车辆停在路边，绿色车辆沿路段行驶，假设黄色车辆欲发送数据给目的地D。首先PVAD将路边停放的车辆组织为簇(cluster₁-cluster₇)，每个簇有1~2个簇头节点对簇进行管理并维护一些路由信息，如路段的数据传输延迟。移动节点发出的数据通过簇内通信和簇间通信转发，但是在簇间通信不可用时，移动节点仍需携带数据移动。簇头节点决定如何在簇内或簇间传输数据。如当黄色节点进入路段r_ij，将数据传输给cluster₁。cluster₁的簇头节点根据各路段的数据传输延迟计算一条到目的地D、具有最短递交延迟的路径，该数据包将在cluster₁内传递并通过簇间通信递交至cluster₅。然而cluster₅和cluster₆不连通，则数据包将分发给移动节点A，车辆A进入路段r_mn并将数据包转发给cluster₆。最后cluster₆将数据包传递给cluster₇，并最终到达目的地D。下面将从路边停放车辆的成簇策略、数据传输延迟估计以及数据分发机制等几个方面进行介绍。

如前所述，城市中每天路边停放点的占用率达到93%，即使是非高峰时期其占用率也有80%，这充分说明了路边停放点的高利用率和存在车辆的稳定性，因此可以对路边停放的车辆进行成簇管理。每条路段上的所有路边停放车辆(parked vehicles，PV)将组织成为一个虚拟簇，即使簇内有些停放车辆无法直接通信，这可以通过路段上移动的车辆节点(moving vehicles, MV)作为中继来实现两者的连通。为了实现数据分发，虚拟簇需要完成3个任务：1)簇的管理，包括簇头选举和成员管理；2)本路段和邻接路段的数据传递；3)本路段的数据递交延迟估测及向其他簇扩散本路段的数据递交延迟。

最接近路口的停放车辆可以选择作为簇头节点，3种成簇的场景如图 2所示。如果l_ij小于节点的通信半径，只需一个簇头，如图 2a所示；若l_ij大于节点通信半径但是小于2R，则在路段r_ij的两端可能各存在一个簇头，如图 2b所示；若l_ij大于2R，路段上可能存在一些孤立的停放车辆(isolated parked vehicle, IPV)，这些车辆与簇内其他成员无法直接通信，此时需要移动节点作为中继。如在图 2c中，移动节点MV1将帮助IPV节点与簇CH_i或CH_j通信。

图 3是PVAD的成簇机制的有限状态机，每个车辆节点在任何时刻处于某一个状态，并通过状态转换事件完成状态的迁移。

以图 4中的黄色车辆为例说明车辆节点各状态的转换过程：1)当黄色节点停放在路边时，将由移动状态MV转换为孤立停放状态IPV，并发送QUERY信息寻找簇头节点；2)当该节点收到ECHO或BEACON消息，则进入停放状态PV，同时发送JOIN消息，成为簇内成员，如图 4b所示；3)若该节点没有受到任何ECHO或BEACON消息，则自己成为簇头节点，如图 4c所示；随后将定期广播BEACON消息；4)如图 4d所示，当原簇头节点驶离时，将在簇内发送LEAVE消息，距该节点最近的停放车辆(图中黄色车辆)将成为新的簇头节点，并广播其BEACON消息；5)在图 4e中，蓝色车辆停放在路口，比原有簇头距离路口更近，则蓝色车辆将成为新的簇头节点，原簇头将成为簇内成员；6)若簇内成员在一段时间内收不到任何BEACON消息，则称为孤立停放节点IPV；7)无论是簇头节点、成员节点以及孤立停放节点，一旦驶离停车点，则成为移动节点。BEACON消息和ECHO消息中均包含了簇头节点信息，BEACON消息是簇头节点周期性的广播，而ECHO消息则是簇内成员节点对QUERY消息的响应。

簇头节点将负责计算其所在路段的数据递交延迟，并将数据递交延迟扩散至网络中所有的簇，这样每个簇都能获知网络中各个路段的数据递交延迟。当车辆携带数据进入路段r_ij的路口I_i时，将记录当前时间t_i，该时间保存在数据首部中；当该数据成功发送出路口I_j时，记录时间t_j，则路段r_ij的实时数据递交延迟为：

定义三元组 < r_ij, d_ij, t_j > 为路段递交延迟记录，当数据发送出路口I_j或移动节点携带该数据驶离路口I_j时，将产生路段递交延迟记录，并向其他路段广播。路段递交延迟记录的广播由各个路段上的簇来完成，当路段递交延迟记录到达新的簇后，通过簇内通信快速将记录发送到邻接的簇；若簇间不能直接通信，则转发至移动节点携带该记录至其他的簇。簇头节点收到路段递交延迟记录后将按式(2)更新该路段的递交延迟，有：

每个簇头节点维护每个路段的平均递交延迟，则可构建一张加权图G=(V, E)，其中V是路口集合，E是连接两个路口的路段，边上的权重即为平均路段递交延迟D_ij，根据这些信息，可以计算一条最优路径。

和BAS等相似，PVAD的数据分发分为3个模式，即入口模式(entrance mode)，直路模式(straightway mode)和出口模式(exit mode)。

当数据递交进入一个新的路段时，处于入口模式。进入新路段的分组有两类来源：1)移动节点携带进入路口，如图 5a所示。2)其他路段簇头节点直接递交，如图 5b所示。当新的分组产生时，在分组首部用TTL字段表示该分组的生命周期。当分组传输至其他移动节点或簇头节点时，TTL减1；但是簇内成员节点传递分组时，TTL不变化。若TTL为0，则丢弃该分组。

在直路模式中，分组在路段中传递。若路段中没有路边停放车辆存在，分组将由移动节点携带进入出口区域；否则分组将被发送至簇头节点。簇头节点知道簇内成员的分布情况，若簇内成员节点是连通的，则分组将被快速传输至出口区域，如图 6a所示；若簇内成员不连通，则分组将转发至移动节点，通过移动节点连通簇内分隔的节点，如图 6b所示。

当分组传递至出口区域，如果本路段给出口没有簇头或簇头节点无法与邻接路段的簇直接通信，同样需要移动节点携带该分组进入下一路段。如果分组由簇内成员传递，则出口处的簇头节点将决定如何将分组分发直期望的路径。簇头节点将优先将分组分发到与移动方向与期望路径相符的移动节点，如图 7a所示。如果在十字路口没有移动节点，本路段簇头节点将分组分发给与其邻接路段的簇头节点，在由邻接路段的簇头节点发送到的移动节点。如图 7c所示，簇头节点CH₁将分组发送给邻接簇的簇头CH₂和CH₃，CH₂和CH₃则将分组发送到移动节点MV₂和MV₃上。

仿真使用的地图如图 8所示，该地图是成都市区的一部分，大小约3 600 m×2 500 m，包含24个路口和35条双向车道。本文在16:00、18:00和22:00对停放在路边的车辆进行计数。通过实地调研统计，得到不同类型路段的平均节点密度，如表 1所示。在允许路边停车的路段如r₁₂、r₂₃等，路段中的平均车辆节点密度达300车辆/km；而像r₁₄、r₄₉不允许路边停车的路段平均节点密度仅20车辆/km；其他没有明确限制路边停车的路段平均节点密度则达到98车辆/km。

仿真使用VanetMobiSim^[18]产生移动车辆的移动轨迹，其产生的轨迹文件可以直接导入NS2^[19]中。停放车辆则随机部署在图 8中的每条路段上，部署密度遵循表 1的调研结果，且停放车辆的停放时间为41.4 min，停放时间的标准方差27.2 min^[4]。考虑到停放车辆贡献资源的意愿，将ρ_pv设置为10%和30%。在移动车辆中，随机选择10个节点产生分组发送到随机选择的路段中。本文将PVAD协议和BAS，TADS和Epidemic Routing在数据递交率和数据递交延迟两方面进行了比较。

本文仿真了不同移动节点的密度对协议性能的影响，如图 9和图 10所示。图 9显示了数据递交率在不同移动节点密度下的变化。显然随着移动节点密度的增加，数据递交率也随之增加，这是因为节点密度的增加提高了网络的连通性。当移动节点密度较低时，PVAD的表现比BAS和TADS好，其原因是停放车辆的加入进一步增强了网络连通性。而随着移动节点密度的增加，Epidemic的数据递交率急剧下降，这主要是冲突增多而导致的。

图 10显示了数据递交延迟随着移动节点密度的增加变化的情况。与Epidemic相比，其他数据分发机制都表现出了较低的数据递交延迟。当移动节点密度较低时，PVAD+10%PV的方案比BAS协议的数据递交延迟低10%，而PVAD+30%PV方案则低18%，这是由于簇内和簇间通信能够加快分组的传递。

随后，本文仿真了在车流量重负载和轻负载场景下网络性能受节点通信半径的影响。图 11表明了400个移动节点随着通信半径的增加，网络的连通性也随之增加，因此数据递交率也逐渐提高。但是当通信半径太大时，由于冲突的影响数据递交率将呈下降趋势。在图 11中，当通信半径很小时，BAS的性能更好。对于PVAD，由于在高密度情形下对簇管理的开销较高，因此数据递交率低于BAS。而TADS则是由于通信半径较小时，难以收集流量信息，从而降低了数据递交率。图 12则表明尽管BAS比PVAD的数据递交率略高，但是以较长的数据递交延迟为代价的。随着通信半径的增大，PVAD的数据递交延迟快速下降，这是因为路段上的簇连通性得到提高，从而加快了分组的传输。但是通信半径过大时，大量的冲突又会导致数据递交延迟的增加。

图 13和图 14显示了轻负载场景下的网络性能。在轻负载场景下，仿真中使用了100个移动节点。显然，当通信半径较小时，车辆相遇概率和冲突概率都很小，因此数据递交率随着通信半径增大而增大。图 13中，PVAD+30%的方案取得了比其他机制高约80%的数据递交率，这说明在轻负载情况下，PVAD表现得比重负载情况下要好得多。同样在轻负载场景下，PVAD的数据递交延迟也更低，如图 14所示。

由于节点的高速移动性，导致车载自组织网络的拓扑快速变化。为了处理网络中因拓扑快速变化引起的间歇连通现象，本文提出了一种多跳的高效数据分发机制PVAD。PVAD充分利用了路边停放车辆的闲置资源，将路边停放车辆组织为簇，通过簇存储或转发来自移动节点的数据，从而提高了网络的连通性和数据递交率。仿真结果表明PVAD能够获得较好的网络性能，特别是在网络中移动节点稀疏时的场景。在下一步工作中将构建一个路边停车模型，并将与节点移动模型集成在一起，使仿真场景更为真实。