0 引言

机动车的普及在为人们出行带来方便的同时，也带来了城市道路交通堵塞的问题。以北京为例，城市主干道平均车速较十年前降低了50%以上，且有高达60%以上的交叉路口常发生严重的交通堵塞，严重影响了人们的工作效率和社会发展^[1]。研究表明，这一情况通常与驾驶员无法及时掌握当前道路网的详细状况密切相关^[2]。本文提出的数据传输算法：一方面有助于驾驶员根据其接收到的数据包(例如：路况信息数据包)另辟蹊径躲避拥堵区域或可能的危险情况以提高行驶效率和安全性；另一方面，也有助于缓解交通堵塞。当前主流的研究热点为车辆自组网中的数据传输^{[1, 3-4]}，例如早期的流行路由，它是通过车辆间以随机交换的方式复制信息,直到车辆有每一个信息的拷贝^[5]，但是并未考虑到车辆网的车辆动态行驶过程中的各种限制条件(比如：道路区域有限、行车速度受限等)。即使将车辆网中各种限制条件纳入考虑之中，现有的相关研究比如“汽车辅助数据传输(Vehicle-Assisted Data Delivery,VADD)^[6]”“中继节点辅助(Static-node-assisted Adaptive Data Delivery,SADV)^[7-8]”等，其研究对象几乎都是从一个动态车辆向一个设施车辆的正向数据传输,不具有移动性的设施车辆作为目的地，太过理想化而现实意义并不充分。在极少数的从静态设施车辆向动态车辆之间的反向数据传输研究，比如TSF(Trajectory-Based Statistical Forwarding for Multihop Infrastructure-to-Vehicle Data Delivery)^[3]中，也是局限于务必先在数据传输过程中寻找到位于目标车辆轨迹上的一个静态设施节点作为数据包和目标车辆的交汇点，才能完成整个数据交付过程。

本算法主要针对文献^[3]中存在的车辆在静态节点处等待数据包问题，采用弱状态路由协议(Weak State Routing,WSR)实现从交通控制中心(Traffic Control Center,TCC)到一个动态车辆的数据传输。由于车辆自组网中所有车辆一直处于移动状态，更符合车辆自组网的路况信息的传输方向。在整个数据转发过程中，借助道路网中行驶的多个车辆作为数据包载体，经过多跳性传输最终将数据包传送给目标车辆。

1 经典TSF算法概述

车载网(Vehicular Ad Hoc Network,VANET)中传统的TSF数据传输算法是在TBD(Trajectory-Based Statistical Forwarding for Light-Traffic Vehicle Ad Hoc)^[9]的基础上将一个处于目标车辆行驶轨迹上的路口处的静态设施作为数据包与目标车辆的最佳交汇点，实现从静态节点到动态目标车辆的数据传输，其中目标车辆的未来行驶路线是可以预知的。为了掌握各车辆的行驶轨迹，车载网中所有车辆需要通过GPS设备及DSRC(Dedicated Short Range Communication)设备^[9]周期性地向TCC汇报轨迹信息。TSF通过统计数据分析数据包延迟和目标车辆延迟均服从Gamma分布，预测出延迟最小的路口作为最佳交汇点，暂存数据包完成数据传输。

如图 1所示：数据包首先按照物理最短路径传输到交汇点；其次数据包在交汇点处等待沿着目标轨迹反向行驶的车辆作为数据包载体；最后将数据包转发给目标车辆完成交付。实际上，在大多数道路网中，由于车辆具有高度自由移动性，车辆轨迹很难获得，且由于目标车辆轨迹路段不一致，交汇点的选择范围并不大。数据包在交汇点处等待满足条件的车辆这一环节，导致数据包传输总延时的增加，影响数据传输效率。由于交汇点设置为某个静态路口，有可能会发生数据包在目标车辆经过此路口之后才到达，导致数据包交付失败。针对这些问题，本文引入弱状态路由概念，采用了动态传输方法，避免了传输过程中的数据包等待问题，提高了数据包成功交付的概率。

2 改进思路与算法 2.1 改进思路

由于车辆自组网具有高度的动态移动性，频繁的网络分区与合并导致网络结构十分复杂。本算法针对网络的高度动态性特征，提出是一种基于WSR协议改进实现车辆自组网无结构化的数据包传输方法(Weak State Forwarding,WSFD)。在数据包传输过程中，车辆不受携带的数据包的限制仍然维持原先的移动状态。本算法不同于GPSR(Greedy Perimeter Stateless Routing)^[10]将数据转发和获取地理位置信息两个过程分离，引入WSR路由协议概念^[11]，车辆在网络中周期性地向邻近车辆传播自己的地理位置信息，数据转发和地理查询两个过程同时发生。如图 2所示，车辆控制中心T首先将收集到的路况信息以独立的数据包形式发送给邻近的接入点(Access Point,AP)，其次AP赋予数据包一个随机方向，数据包沿着此方向传输，直到被一个包含有关目标车辆D信息的车辆C₁接收，然后车辆C₂作为数据包载体重新寻找比自身更适合作为数据包载体的新车辆,(具体寻找过程会在第三节详细解释)，重复上述步骤，直到将数据包转发给目标车辆D完成交付。

2.2 改进算法 2.2.1 条件假设

本算法假设道路网无空闲路段，网络密度足够高，所有车辆可以通过GPS设备或者其他方法获取自己当前在二维平面上的位置信息和行驶速度。通过周期性的Beacon消息机制，车辆能获得通信范围内的邻居车辆的位置信息。交通TCC能够及时获取各路段交通密度和每一车辆当前的行驶状态(所处路段、行车速度及具体位置等)。

2.2.2 弱状态

1) 弱状态概念定义。

弱状态首先在文献^[11]中被提出，它是一种不同于传统的强状态路由^[12]的新概念。传统的路由状态被解释为一种确定性的信息，而弱状态是一种可能性的概率行为。在传统的强状态路由下，当数据包方向改变时，即图 3中的状态发生变化时，远程车辆B的状态信息也会随之改变，那么对应的路由表条目会随之立即变为失效，状态有效的持续性极差，而为了不断及时更新条目信息必将对当前所在的车辆网造成巨大的网络负荷。相对于强状态而言，弱状态路由协议弥补了这一缺陷。弱状态路由协议包涵“不确定”的非绝对性的概念，远程车辆B所对应的状态是一种带有置信度数值θ的信息，随着时间的延长，车辆B对应的置信度数值会从1开始逐渐减小，表示相应的状态在弱化，当车辆A改变当前状态时，车辆B会接收到控制信息随之改变自己持有的状态信息；若车辆A无状态更新，则θ一旦降到既定的阈值α以下，对应的条目信息就会变为失效，从本地系统中自动删除。

2) 弱状态的实现。

一个弱状态对应一个车辆ID集合到一个地理区域的匹配映射，映射会随着时间弱化，直到最低极限α时便从系统中自动删除，具体弱化方法会在后面详细介绍。一个远程车辆会维持多个映射，每个映射相互独立，各自的弱状态信息就是获取映射中的不确定性，以一个概率值的方式表示。将ID集合与其对应的地理区域相匹配后，可用于对数据包传输方向的修正。

如果目标车辆的ID在某个车辆ID集合中，那么将数据包的方向修正为偏向该车辆集合所对应的地区域中心。随着距离目标车辆越来越近，数据包方向的偏向会得到逐渐加强。

3) 弱化方法。

一个映射包含两个组成元素：车辆ID集合与其对应的地理区域，如图 4所示。

由于车辆都处于运动状态，因此ID集合与其地理区域的匹配程度是逐步衰减的。如图 5所示：假设远程车辆n维持两个映射，在t时刻确切知道m₁和m₂的具体位置，t+δ时刻，车辆n通过计算δ×v可确定m₁存在的区域M₁，同理在t+δ时刻，可确定m₂存在的区域M₂。从t时刻n车辆确切知道m₁和m₂的具体位置信息扩展到只能确定其存在区域的过程，便是一种状态弱化过程。若区域M₁、M₂相近即图 3中的β足够小，可将两区域合并为一区域M，它是以m₁和m₂的中点m为圆心，同时包涵M₁区域和M₂区域的最小圆。与此同时，对应的车辆集合也随之合并，此时车辆n所维持的两个映射合二为一，状态进一步弱化。

随着区域逐步合并，车辆位置的不确定性不断增大，这对于数据传输是越来越不利的。因此此时将弱化状态方法从弱化区域部分转移到弱化车辆集合部分，这需要通过弱化布隆滤波器(Bloom Filter)机制实现。每一个车辆ID集合，用一个Bloom Filter表示，通过周期性地随机将Bloom Filter中的某一比特值“1”重置为“0”，以此来达到弱化状态目的。

2.2.3 Bloom Filter

对于每一个刚创建的弱状态入口，都设置一个Bloom Filter机制表示对应的车辆集合部分。Bloom Filter是一种结构简单而空间复杂很小的随机数据结构，用来检测元素x是否是集合A的成员^[12]。假设映射车ID辆集合A={x₁,x₂,…,x_j}，Bloom Filter设置长度为u的位向量，使用k个独立的哈希函数f₁,f₂,…,f_k，将集合A中元素散列到u位上，每一个元素对应的k位均置“1”。查询元素x是否为集合A的成员时，只有元素x数组中f₁(x),f₂(x),…,f_k(x)比特位都为“1”，才表示元素x是集合A的成员。随着集合A中元素增多，Bloom Filter置“1”位数量增加，会造成将非A集合中的成员误判成属于集合A。误判率为P(error)^[13]:

$P\left( \text{error} \right)={{({{[1-(1/u)]}^{{{k}_{j}}}})}^{k}}$

为了降低误判率，本文使用弱化式的Bloom Filter，基本思想是，当映射对应的车辆ID集合Bloom Filter中“1”的数量count(B₁)≥u/2时，将已有的Bloom Filter比特位为“1”的每隔δ_t(s)随机挑选一位重置为“0”。Bloom Filter中“1”的总数会随着时间逐渐减小，目标车辆ID散列对应的“1”的数量越小，表示此映射信息越旧，状态越弱，可信度越低，目标车辆位置的确定性越小。

当Bloom Filter中某一个车辆ID散列对应的“1”位数量低于某个既定的阈值γ，则将车辆的状态从此映射中移除。

2.3 地理位置信息传播

由于Beacon消息通信距离有限，为传播远程车辆的地理位置信息，车辆周期性地通过Announcement消息机制^[8]往运动方向的四个正交方向散播自己的地理位置信息。Announcement消息包括了车辆的本地置信度、路段、位置、速度、方向等信息。Announcement消息中的变量描述如表 1所示。每一辆车都匹配一个置信度值θ，用它来决定所包涵有关目标车辆位置信息的新旧程度。RoadNo，X，Y，V，D信息都能通过GPS设备获取。

在车辆通信范围内的邻车辆，可通过Beacon消息确定相互具体位置，此时的状态置信度为1，一旦邻车辆移动超出其通信范围外，则根据移动速度和邻车辆最后所在的位置，计算确定其所在区域，此时的状态置信度也随之下降。对于较远的车辆，车辆m周期性以随机方向发送自己的位置信息，提高与数据包传输方向相交的概率。当某个车辆接收到来自车辆m的位置信息时，创建一个关于m的映射，其对应的地理区域是以m为中心、半径为0的区域，此时状态置信度为1，并判断此映射是否能够与已存在的映射合并。

2.4 置信度比较

每一个弱状态置信度数值受两个因素的影响：1) 地理区域的大小；2) BloomFilter中比特位“1”的数量。

当车辆A维持的多个映射{i_j1,i_j2,…,i_jk}都包含目标车辆D的位置信息时，首先对每个映射的Bloom Filter中，查询在总长度u中，表示目标车辆D的“1”的数量d，计算p_j=d/u，选择p(B₁)=max{p_j1,p_j2,…,p_jk}决定数据包新的修正方向。

若存在两个或多个映射的p_j相同，则分别比较筛选每一个映射的地理区域部分半径，选择R=min{R₁,R₂,…,R_k}的区域，将数据包传输方向往此区域中心方向修正。

2.5 算法流程

数据传输核心算法流程如图 6所示。

步骤1 交通控制中心TCC将数据包沿着目标车辆方向发送到附近的一个接入点上，接入点以一个随机角度ψ发送捎带目的地车辆信息p_D的数据包，发送给在其通信范围内遇到的第一辆车C_A。

步骤2 在车辆C_A所维持的所有映射中，查询是否有包含目标车辆D信息的映射：

①若车辆C_A所维持的所有映射i={i₁,i₂,…,i_k}都未包含目标车辆D的位置信息，则选择θ_A=max{θ_j1,θ_j2,…,θ_jk}的映射i_j，数据包将携带上此映射的置信度数值θ_p(θ_p←θ_A)，并将数据包传输方向往映射i_j对应的地理区域中心方向偏转；

②若车辆C_A所维持所有映射中，只有映射i_i包含目标车辆D的位置信息，数据包将携带上此映射的置信度数值θ_ii，并将数据包传输方向往映射i_i所对应的地理区域中心方向偏转；

③若车辆C_A所维持所有映射中，多个映射{i_j1,i_j2,…,i_jk}都包含了目标车辆D的位置信息，则θ_A=max{θ_j1,θ_j2,…,θ_jk}的映射i_jj，数据包将携带上此映射的置信度数值θ_A,并将数据包传输方向往映射i_jj对应的地理区域中心方向偏转。

步骤3 数据包被车辆C_A通信范围内的某一车辆C_B所接收，查询车辆C_B所维持的所有映射，重复步骤2，并将最终的θ_B与数据包所携带的θ_A对比：

①若θ_A≤θ_B，则将数据包传输方向按照θ_B对应的映射的地理区域中心修正,并更新所携带的置信度θ_p(θ_p←θ_B)；

②若θ_A>θ_B，则维持原有的数据包传输方向不变，数据包会被沿着此方向的下一个车辆C_C接收。

步骤4 对于之后每一辆接收数据包的中间车辆C_C，C_D，C_E，…,C_n，重复步骤4，直至将数据包转发给目标车辆D完成数据交付。

3 实验与性能分析 3.1 实验介绍

为了检测本算法的性能，本文将使用几个典型的路由协议测量指标，如表 2所示。

本文实现了WSFD与GPSR、TSF的性能比较，实验数据从实时交通数据得来。动态车辆分布在30 km×30 km方形区域中，车辆行驶速度最低限速20 km/h,最高限速40 km/h，每辆车每秒往其他车辆发送521 B的数据包信息，实验时间为100 s。

3.2 性能分析 3.2.1 车辆密度的影响

为了方便比较三种协议在不同车辆密度下的性能，假设当前车辆以20 km/h的速度匀速行驶。

数据包传送延迟实验结果如图 7所示。由于WSFD将数据传输和位置发现两个过程同时进行，因此受车辆数量影响最小，整个过程中数据包传送延迟都维持在5 s左右，性能最优。TSF数据包传送延迟随着车辆数量的增加逐渐降低，因为道路交通流量越大，可作为数据包载体的车辆选择性就越多。TSF协议下，数据包需要在交汇点处等待车辆，造成总体延迟的增加。GPSR需要额外进行地理位置发现过程，因此在延迟方面表现不佳。

数据包投递率实验结果如图 8所示。WSFD和TSF投递率均在0.85以上并随着车载网密度的增大逐渐提高,而TSF由于城市道路限速，降低了车辆的路口到达率，影响了数据包提前到达交汇点的概率，因此数据包投递率性能方面稍差些；由于车辆数目增加，GPSR投递率逐步减小。

数据包平均路径长度如图 9所示。随着车辆数量的增加，TSF和GPSR的数据包传播路径是逐渐下降的。在TSF协议中，目标车辆的轨迹是已知的，是一种确定性数据传输，因此传播路径方面性能良好。GPSR在GLS(Grid Location System)^[10]的帮助下，可寻找最短路径传播。由于WSFD是概率性传播方法，数据包在中间节点处以较大的概率被修正传输方向，不可避免绕远路的情况发生。

3.2.2 平均车速的影响

车辆密度维持在400辆保持不变，在平均车速不同的条件下，三种协议的性能表现也有所差异。

数据包传送延迟实验结果如图 10所示。由于车辆密度保持不变，随着平均车速的增加，三种协议均受车速影响较小。由于车辆网平均车速增加，车辆之间彼此相互通信概率增大，WSFD和TSF及GPSR总体呈下降趋势，前两者性能仍然优于后者。

数据包投递率实验结果如图 11所示。由于车载网整体速度提高导致网络动态性增强，WSFD映射信息更新加快，数据包转发方向修正率提高，因此数据包投递率逐渐提高，逐渐逼近1。随着车辆速度提高，TSF在转发数据包到交汇点的过程中，路口等待比率减小，因此数据包投递率在逐渐递增。GPSR数据包投递率随着车速增加而提高，整体性能仍不及WSFD和TSF。

数据包平均路径长度如图 12所示。随着车载网平均车速的提高，由于TSF和GPSR都是根据确定性方向转发数据包，因此受车速影响较小。而WSFD中映射维持的地理区域扩大速度会随着车速的增加而提高，使用更大的衰减概率，数据包需要多次的传输尝试才能到包含有效信息的中间节点。

4 结语

本文提出了一种基于弱状态的车载网数据传输算法，此数据传输算法通过对比筛选对于车辆位置信息确定程度最大的映射，将数据包传输方向逐步修正，渐渐逼近目标车辆所在区域，最终完成数据交付。通过使用交通数据进行网络模拟与仿真，相比TSF协议及GPSR路由协议，本算法能够以较低的路由负荷提供数据包较高的投递率和较低的传送延迟。虽然WSFD在各测试指标上显示了很高的性能，但是其对于路径的选择受到了限制，这也是将来研究的方向。