“前人栽树后人乘凉”，尝试利用以前的数据规划未来的车辆路径！

为了为出行者提供未来车流的方向，有必要对某段道路上行驶车辆的行驶轨迹进行预测。根据车辆序列模式的特点，将车辆自组网(VANET)的拓扑结构与真实道路车辆的运动轨迹联系起来。

研究者提出了与VANET环境中序列模式相关的一些新的定义。基于RSU和V2V方案，建立车辆运动数据库，进行序列模式数据挖掘。然后，评估它们的通信开销。计算由车辆路径模式生成的运动规则的支持度和置信度，提取频繁行驶轨迹的概率。本文以“Data Mining Method of Sequential Patterns for Vehicle Trajectory Prediction in VANET”为题于2020年11月22日发布于《Wireless Personal Communications》杂志上。

研究背景

5G时代即将到来。随着车联网和“互联网+”技术的逐步应用，智能化、网络化改变了人类的交通方式。与此同时，人们对出行效率、安全和环境等问题也有了更高的要求。内外部因素不断推动车联网技术发展，引起广泛关注。

近年来，车辆安全装置越来越先进，但交通事故仍然是一个严重的问题。许多研究者认为，在交通事故发生前及时向驾驶员传达预警信息可以避免60%的交通事故。车载自组织网络(VANET)是移动自组织网络(MANET)的升级版本，VANET涉及移动车辆之间的信息交换。车辆通信在VANET中非常重要，能够有效地提高交通安全性和舒适性。

可以预测，在不久的将来，几乎所有的车辆都将配备车载VANET通信设备。车辆行驶路线预测是研究的新领域之一。获得车辆的预期路线和目的地有很多优点。例如，可以在一天的特定时间预测特定地区的拥堵程度;警方可以利用车辆的路线和目的地信息追捕和抓获逃犯，并可以有效地设置路障和备份。

序列模式已被用于行为预测的许多不同领域，如客户购买行为、金融股票、医疗，甚至在移动机器人。序列模式被用作一种数据挖掘技术来发现时间对象和事件之间的相关性。通过监视这些事件的范围和重复，研究者可以根据以前的历史序列模式预测未来的行为。在VANET中，序列模式可以用来预测车辆可能选择的轨迹。为了利用序列模式预测车辆路径，车辆通过一系列路段时，需要采集车辆轨迹数据。

序列模式的数据挖掘方法主要用于收集事件集的时间序列。在这种情况下，该研究中设置的事件指的是车辆经过的片段。建立了车辆历史序列模式数据库。利用数据挖掘技术，对车辆进行实时跟踪，建立行车档案。该方法可以提供车辆未来轨迹的信息，并可以根据之前的轨迹来驱动某一特定车辆。

VANET包括一套车辆(每辆车安装了OBU装置)和与道路一起铺设的固定单元(路边单元，RSU)。一些RSU可用于连接到其他网络，如因特网。每个OBU都有一个无线网络，允许直接连接到其他车辆，RSU在有效连接范围内。通过V2V(车辆到车辆)，V2I(车辆到基础设施)，V2B(车辆到宽带)，或V2X(车辆到一切)的应用，如图所示。

图为VANET中的V2X(车载到一切)

在adhoc网络模式下，V2V提供车辆之间的通信。车辆可以发送、接收或与其他车辆交换有价值的交通信息，如交通拥堵或事故。V2I用于在基础设施和车辆之间广播和传递关键信息，如道路状况和安全问题。在这种类型的通信中，车辆和RSU建立了能够连接到外部网络(如Internet)的连接。

在VANET中，车内连接对于车辆的性能，尤其是驾驶员的行为是非常重要的，这对公共安全至关重要。在V2B连接中，车辆可以通过4G或5G网络连接到无线宽带系统。这种类型的通信对于主动驾驶辅助和车辆跟踪非常有用，因为宽带云包含更多关于交通和娱乐的监控数据和信息。

首先，收集车辆行为，建立移动数据库，生成移动模式。一般运动模式的提取依赖于一段时间收集到的历史运动信息。在采集所有车辆的行驶轨迹并确定最小支持阈值后，可以提取最频繁的车辆行驶轨迹作为车辆运动模式。有两种通信方案，一种是基于RSU的通信方案，另一种是基于V2V的通信方案.基于V2V的车辆路径信息采集，又称全路径方案，分为广播模式和RSU发现模式。

目前，项目组已收集了两年的车辆行驶数据，主要包括私家车路线数据、出租车路线数据和公交路线数据。在固定路线上行驶、停在固定车站的公共汽车，在各个公交车站设有网络接入点。

图为V2V透射波

在混合业务中，数据传输效率与环境密切相关，传输随机性强。对于有目的的数据传输，可能需要很长时间，或者数据抖动导致信息传输失败。为了提高数据传输的到达率和准确性，需要在热点地区部署少量的RSU，存储关键数据，并将数据传输给目标车辆。

根据车辆序列模式的特点，提出了点存在的道路节点。对呼和浩特市地图上的路段进行了分类和划分。根据复杂网络理论，将路段抽象为边缘，将交叉口抽象为节点。

图为呼和浩特市的驾驶轨迹

车辆路径序列具有典型的时态特征。车辆路径的预测是基于期望的最小延迟。利用GPS算法进行序列模式挖掘是非常有效的。核心思想是反复扫描，直到达到预定的最小支持度。为了加快循环过程，避免循环循环，需要对候选序列进行修剪。例如，如果序列候选的所有子序列都不满足最小支持，则应该删除序列候选。

车辆路径预测的目的是预测车辆所选择的下一个轨道，具有可预见性。数据库中车辆的历史轨迹序列是规则的先导，待行驶车辆的轨迹序列是规则的结果。利用定向轨迹序列模式确定前缘和后缘之间的轨迹关联规则。

图为呼和浩特市部分干道图

在实验中，对通信开销进行了评估，这意味着对所有节点发送的消息数量进行了评估。通信开销由每辆车的区段数和给定地图上的车辆数来衡量。对于第一个变量，分段和车辆的数量逐渐增加，若干车辆被设置为交叉路径。收集在仿真过程中交换的信息量，并将其视为与路径大小相关的通信开销。

图为不同路径大小下的网络开销

通信开销随着路径大小的增加而增加，通信开销相对较大。主要原因不是车辆本身发送的消息数量，而是RSU发送的消息数量。RSU每10s广播一次信标消息，而不考虑附近是否有移动车辆，从而导致无效的通信开销。车辆数目从10辆增加到60辆，每次模拟运行增加10辆。实验进行了800秒，测量了车辆与周围RSU之间的信息交换数量和车辆发送的消息数量，如图所示。

图为不同车辆密度下的网络通信开销和车辆通信开销

图为平均通信费用

在实际应用中，对于数据传输的到达率，V2V数据传输要求目标车辆必须满足先前车辆的要求。出租车和私家车的轨迹并不固定。需要部署在交叉口的RSU来帮助传输信息，在那里消息被快速地传送到目标车辆。另外，由于车辆轨迹和运行时间的不确定性，很难保证数据的及时交换。

研究结论

该研究将VANET拓扑与道路上的真实车辆运动路径进行了联系，并提出了与VANET环境中序列模式相关的定义。利用基于ru和基于车辆的方案，对历史车辆轨迹进行序列模式数据挖掘可以为未来车辆轨迹的准确预测提供更多的支持。

最后，通过通信开销对两种方案进行了评估。RSU方案周期性地搜索车辆并将其遍历轨迹发送给相邻的RSU，其通信开销较大。在车辆方案中，车辆根据一定的准则传输其遍历轨迹。对频繁运动模式生成的运动规则置信度进行了评价。每个规则的概率都可以计算出来。

为了减少VANET中数据传输的延迟，有必要进一步探索对交通有重要影响的车辆的时空特性，找出其稳定的规律。

参考文献：Hong Zhang & Li He Data Mining Method of Sequential Patterns for Vehicle Trajectory Prediction in VANET  Wireless Personal Communications (2020)