一种车载自组织网络高效数据分发机制研究

余玲飞，龚海刚，刘念伯，周圣二

(1. 浙江工商大学杭州商学院 杭州 310018；2. 电子科技大学计算机科学与工程学院 成都 611731)

车载自组织网络在交通安全、智能交通系统等应用方面有着广阔的前景，得到了广泛的关注。由于车辆节点的高速移动性，使网络拓扑高度动态变换，节点之间间歇连通，因此难以存在一条稳定的端到端路径。车辆移动性也受到道路的限制，并且由于路边建筑和其他障碍物的影响，车辆节点上的数据传输同样受到道路限制。使车载组织网络中的数据分发非常困难。有一些致力于车载自组织网络机会性连通的研究，并取得了一定的成果。利用VANETs网络中的基础设施[1](road side unit，RSU)无疑能提高网络连通性和路由性能，但是基础设施的建设成本高昂。文献[2]说明了路边基础设施的架构成本达到每单位5 000美元。此外，静态的路边基础设施也难以适应快速变化的交通流量，其部署需要从整体进行精巧的设计。

车载自组织网络中的数据分发机制通常将网络限制为移动的车辆节点和路边基础设施，数据分发仅在移动车辆节点之间或移动节点和基础设施之间，将静止的车辆排除在外。但是在城市环境中，人们将车辆停放在路边是一种非常常见的现象。据加拿大蒙特利尔城市的泊车报告[3]，在对5 500平方公里上的61 000个日间停车事件的统计中发现，路边停车(street parking)，路外停车(outside parking)和车库及地下停车分别占69.2%，27.1%和3.7%，并且路边停车的平均时间为6.6 h。这说明路边停车节点能够提供较长时间的辅助通信。此外，路边停车在很多城市都表现出时间和空间上的规律性，城市规划者也经常制定一些政策鼓励在每个街区建立路边停车点和停车场。在对美国ANN Arbor城市的调查中发现[4]，在商业区的路边停车点的每天平均占用率达到93%；另一项对Hattiesburg城市的调查报告[5]同样发现，停车点没有车辆停放的可能性非常小。因此，可以认为频繁占用的路边停车点经常存在一些车辆，能够提供较为稳定的通信辅助，以提高数据分发行能。

与移动车辆节点相比，停放车辆能够有效地提高通信效率。如车流量的快速变化可能会导致路段上移动车辆稀疏，分布不均匀，而长时间停放的车辆则成为天然的中继节点，能够增强网络的连通性，将不能直接通信的移动节点连通。这些路边静止车辆节点的资源同样可以用来提高网络的连通性，从而增强网络的数据分发性能。本文基于路边停放车辆的辅助，提出了一种高效数据分发机制(parked vehicle assisted data dissemination scheme, PVAD)，PVAD首先将路边停放车辆组织为簇，对来自移动车辆节点的数据进行缓存或转发，达到提高数据递交率减小数据递交延迟的目的。

1 相关工作

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

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

2 PVAD设计

2.1 系统假设

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

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

2.2 PVAD概述

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

图1 PVAD示意

2.3 路边停放车辆成簇

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

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

图2 成簇的3种场景

图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消息的响应。

2.4 数据递交延迟计算

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

图3 PVAD有限状态机

图4 节点状态转换示意

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

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

2.5 数据分发

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

2.5.1 入口模式

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

2.5.2 直路模式

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

图5 入口模式

图6 直路模式

图7 出口模式

2.5.3 出口模式

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

3 实验仿真

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

图8 仿真地图

表1 调研结果

3.1 实验参数

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

表2 仿真参数

3.2 实验结果

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

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

图9 不同移动节点密度对数据递交率的影响

图10 不同移动节点密度对数据递交延迟的影响

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

图11 重负载下不同通信半径对数据递交率的影响

图12 重负载下不同通信半径对数据递交延迟的影响

图13 轻负载下不同通信半径对数据递交率的影响

图14 轻负载下不同通信半径对数据递交延迟的影响

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

4 结束语

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

[1]TANUJA K，SUSHMA T M，BHARATHI M，et al. A survey on vanet technologies[J]. International Journal of Computer Applications, 2015, 151(15)： 1-9.

[2]JUPITER R. Municipal wireless： Partner to spread risks and costs while maximizing benefit opportunities[R]. New York,USA： Jupitermedia Corporation, 2005.

[3]MORENCY C, TR´EPANIER M. Characterizing parking spaces using travel survey data[R]. Quebec, Canada：Interuniversity Research Centre on Enterprise Networks,Logistics and Transportation, 2006.

[4]ADIV A, WANG W. On-street parking meter behavior[J].Transportation Quarterly, 1987, 41(2)： 281-307.

[5]ALBANESE B, MATLACK G. Utilization of parking lots in Hattiesburg, Mississippi, USA, and impacts on local streams[J]. Environmental Management, 1999, 24(2)：265-271.

[6]ZHANG X, NEGLIA G, KUROSE J, et al. Performance modeling of epidemic routing[J]. Computer Networks, 2007,51(10)： 2867-2891.

[7]ZHAO J, CAO G. Vadd： Vehicle-assisted data delivery in vehicular Ad hoc networks[J]. IEEE Transaction on Vehicular Technolog, 2008, 57(3)： 1901-1912.

[8]SONG C, LIU M, WEN Y, et al. Buffer and switch：road-to-road routing scheme for intermittently connected vehicular networks[J]. China Communication, 2012, 9(6)：55-70.

[9]CHUMEI M, LIU N. Traffic-aware data delivery scheme for urban vehicular sensor networks[J]. International Journal of Distributed Sensor Networks, 2013： 1-11.

[10]KUMAR N A. RS-CBAODV： an enhanced reactive routing algorithm for VANET to reduce connection breakage using remote storage concepts[J]. I J Information Technology and Computer Science, 2015(9)： 11-20.

[11]CHANG S W, LEE S S. Distance-based stable routing decision scheme in urban vehicular Ad hoc networks[J].International Journal of Distributed Sensor Networks, 2015：1-11

[12]ALI F, SHAIKH F K, ANSARI A Q, et al. Comparative analysis of VANET routing protocols： on road side unit placement strategies[J]. Wireless Personal Communications,Montreal, 2015, 85(2)： 393-406.

[13]XU L，HUANG C，WANG J，et al. An efficient traffic geographic static-node-assisted routing in VANET[J].Journal of Networks, 2014, 9(5)： 1096-1102.

[14]JEONG J, GUO S, GU Y, et al. Trajectory-based statistical forwarding for multihop infrastructure-to-vehicle data delivery[J]. IEEE Transactions on Mobile Computing,2012, 11(10)： 1523-1537.

[15]ECKHOFF D, SOMMER C, GERMAN R, et al.Cooperative awareness at low vehicle densities： how parked cars can help see through buildings[C]//Proceedings of the 54th Annual IEEE Global Telecommunications Conference. New York, USA： IEEE, 2011.

[16]LIU N, LIU M, W LOU, et al. PVA in VANETs： Stopped cars are not silent[C]//Proceedings of the IEEE International Conference on Computer Communications.New York, USA： IEEE, 2011： 431-435.

[17]BALEN J, MARTINOVIC G, PARIDEL K, et al. PVCM：assisting multi-hop communication in vehicular networks using parked vehicles[C]//Proceedings of the 4th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. New York, USA：IEEE, 2012： 119-122.

[18]SAROIU S, GUMMADI P, GRIBBLE S. Ameasurement study of peer to peer file sharing systems[C]//Proceedings of the Multimedia Computing and Networking, Citeseer.New York, USA： IEEE, 2002： 1-15.