车载自组织网络中车辆路径预测序列模式数据挖掘方法＊

张宏

（1.内蒙古大学，呼和浩特 010070；2.内蒙古自治区城市交通数据科学及应用工程技术研究中心，呼和浩特 010070）

主题词：车辆路径预测 车辆行驶路径序列 序列模式 车载自组织网络 数据挖掘

1 前言

车辆行驶期间获得车辆的预计行驶路径和目的地是避免事故发生的有效手段之一[1]，为此，国内外学者开展了车辆路径预测研究。路径预测主要方法有线性函数、贝叶斯网络模型、马尔科夫链模型、高斯混合模型等。Pan 等人[2]借助多变元正态分布提出线性预测方法，但该模型预测有时间延迟，无法实时监控交通流环境；Li等人[3]提出了改进贝叶斯推理方法，将历史轨迹分解，构建更精确的马尔科夫模型，提高了预测精度和算法效率；Jing Yuan 等人[4]利用马尔科夫概率模型构建了车辆路径预测算法模型，短距离预测准确率较高，但不适用于远距离车载自组织网络交通信息服务；Qiao 等人[5]提出了基于马尔科夫模型的自适应动态轨迹预测算法，该模型通过不同类型轨迹预测最优路线，但未考虑大数据环境下算法的运行效率；Dai 等人[6]基于高斯混合模型和最短路径算法，考虑轨迹大数据中个性化行驶偏好概率问题，提出了带权重的轨迹图，使用该算法对多模式运动路径进行预测，但不适用于复杂场景。由上述分析可知，大多数算法对单一车辆运动模式预测准确性较好，针对大量复杂历史轨迹数据挖掘频繁模式，需多次扫描数据库，效率和准确性不能兼顾，所以需构建新型数据频繁模式挖掘算法，提高数据挖掘的准确性和效率。

车载自组织网络（Vehicular Ad-hoc Networks，VANET）涉及移动车辆信息交换，是车联网技术的基础，在VANET 中，利用序列模式进行车辆路径预测，需要收集车辆历史移动轨迹数据。序列模式数据挖掘方法主要收集事件集的时间序列[7-8]，事件集为车辆驶过的路段。本文通过建立车辆历史序列模式数据库，利用数据挖掘技术，实时跟踪车辆，建立行驶档案，以预测车辆未来行驶轨迹。

2 车载自组织网络体系结构

车载自组织网络由安装了车载单元（On Board Unit，OBU）的一组车辆和路侧单元（Road Side Unit，RSU）组成，如图1 所示。部分RSU 还可连接其他网络（例如Internet），OBU 利用无线网络在有效连通范围内直接连接到其他车辆和RSU。车载自组织网络可支持道路安全、信息娱乐、道路交通优化等各种应用[9]。

图1 车载自组织网络体系结构

VANET有3种连接方式，如图2所示。自组织模式下，车对车（Vehicle to Vehicle，V2V）连接在车辆与车辆间提供通讯，发送、接收或交换有价值的交通信息，如交通拥堵、交通事故等。车辆对基础设施（Vehicle to Infrastructure，V2I）连接用于在网络基础设施与车辆之间广播关键信息，也可用于道路条件和安全问题等重要信息的传达，在这种通讯类型中，车辆与RSU 创建连接，并可连接到Internet等外部网络。V2I连接不易受到攻击，较V2V连接需更大带宽[10]。在VANET中，车内连接可确认车辆性能和驾驶员行为，对公共安全至关重要。在车辆对宽带（Vehicle to Broadband，V2B）连接中，车辆可以通过4G、5G网络与无线宽带系统连接。因宽带云包含更多交通信息、监控数据和娱乐信息，所以V2B连接对主动驾驶辅助和车辆跟踪作用较大。

图2 车载自组网中的连接类型

3 运动模式描述与定义

序列模式挖掘算法最早由Agrawal和Srikant提出[11]。时序模型在很多不同领域已有应用，为将时序模型应用于车载自组织网络，需对VANET 中车辆移动行为进行描述和定义。基于文献[12]，描述和定义如下：

a.M={M1,M2,…,Mi,…}为道路节点集合，一条路段可表示为2个连续的道路节点之间的单项边。本文中，交叉口也被认为是道路路段的一部分，还可表示道路的末端、出口等，交叉口可连接2个或多个路段。

b.V={V1,V2,…,Vi,…}表示给定地理区域内行驶一定时间的一组车辆。Y=[M1Mi…Mn]表示车辆运动序列模式，即车辆Vi在特定地理区域内行驶期间所经过的路段节点。建立车辆移动数据库，将其行驶路段以运动模式存储在数据库中。若Y′模式包含Y中路段元素，顺序也相同，则Y称为Y′的子模式。如运动模式[M4M5M7]为[M2M4M5M7]和[M1M4M5M7M9]的子模式，但因运动模式顺序不同，所以不是[M2M4M5M6M7]的子模式。运动模式Y的支持度用S(Y)表示，定义为移动数据库中运动模式Y及含有子模式Y′的运动模式的数量。

c.运动规则R定义为关联规则Y1⇒Y2，设R的支持度为S(Y1⇒Y2)，Y1和Y2是Y的子模式，且二者间没有共同的路段，则运动规则R的置信度c(R)定义为：

规则由数据库中的运动模式生成，如运动模式Y=[M2M3M4M5]的规则集可能为[M2]⇒[M3M4M5]、[M2M3]⇒[M4M5]、[M2M3M4]⇒[M5]。

若c([M1M2]⇒[M3])=2/3，则表示正在路段M1M2上的车辆有2/3的概率到达路段M2M3。

4 车辆路径数据收集及分析

首先收集车辆行为，建立移动数据库，生成移动模式。常用运动模式提取依赖于一段时间内收集的历史移动信息。在收集全部车辆路径并确定最小支持阈值后，可提取行驶最频繁的车辆路径，将其作为车辆运动模式。通信方式有基于RSU和车辆两种方案。基于车辆收集路径信息方案也称为全路径方案，分为广播模式和发现模式。在方案实施过程中，RSU分布在各地理区域内，互相组合连通，增加网络拓扑的连通性，使信号覆盖所有路段。每辆车可使用地图匹配技术检测新路段，每个RSU负责跟踪附近车辆发送的部分路径。

车辆作为移动节点，利用车载网络进行数据传递，可减少RSU部署数量和网络开销，如图3所示。

图3 方案场景示意

在混合交通中，数据传输执行效率与环境密切相关，传递随机性较强，而有目的的数据传输存在时间较长和数据抖动问题，可能导致信息传输失败，为提高数据传输到达率和准确性，需在热点位置部署少量RSU，由RSU存储关键数据并传递给目标车辆。

车辆路径选择会受到驾驶员主观能动性影响，驾驶员在选择出行路径时会综合考虑道路条件、交通状态、出行目的等多种因素，本文通过前期问卷调查，统计分析车辆轨迹信息，结果表明，私家车动态运动轨迹遵循一定规律，可预测性为89%，并且行驶路径与距离无关。

私家车、出租车和公交车对车流量的贡献较大，对其进行轨迹预测能较好地掌握车流量及行驶方向。本文的数据来源于“中国工况”项目组内蒙古地区私家车、出租车和公交车共94辆车记录的GPS移动信息[13-14]。

5 车辆路径预测与方案评估

5.1 车辆路径预测

根据车辆序列模式特点，相邻两项为道路节点，对呼和浩特市路段进行整理和划分，用复杂网络理论将路段抽象为边，交叉口抽象为点，生成城市道路网络拓扑图，如图4所示。

图4 呼和浩特市主干路网

车辆路径序列具有典型的时间特征，根据期望的最小延迟进行车辆路径预测，可采用广义序列模式（Generalized Sequential Pattern，GSP）算法对序列模式进行挖掘。其核心思想为反复扫描直到满足预先设置的最小支持度，为加快循环进程和避免死循环，需对所有子序列均不满足最小支持度的候选序列进行修剪。

车辆路径预测具有规律性，将数据库中车辆历史路径序列作为规则前件，预测车辆行驶路径序列作为规则后件。前件与后件的路径关联规则由具有方向性的路径序列模式决定。

为简化说明计算原理，建立模拟交通网络图，并进行编号，示例如图5 所示，构建相应的车辆行驶路径数据库如表1所示。

图5 呼和浩特市中心城区部分主干路路网

以表1所示数据库为例，首先扫描数据序列获得序列1 的模式Y1，通过序列模式函数继续扫描由序列k的模式Yk生成序列(k+1)的候选模式Hk+1，计算其支持度，若满足要求，则Yk+1=Hk+1，继续循环扫描，直至无新的序列模式产生。设最小支持度为3，符合最小支持度的车辆行驶路径序列1 的模式及相应的支持度为[A]（5）、[B]（6）、[C]（7）、[E]（3）、[F]（8）、[G]（9）、[H]（3）、[K]（3）。由序列1的模式生成序列2的候选模式时，因支持度较小、序列较多，会生成大量候选序列和冗余序列，大幅增加了扫描时间，所以考虑交通网络实际意义和提高算法的性能，仅连接交叉路口的相邻路段，如图5 中[C]路径模式仅与[B]、[G]、[D]连接，生成候选模式为[CB]、[CG]和[CD]。

表1 车辆行驶数据库示例

对长度大于3的路径模式生成关联规则，计算置信度，建立关联规则数据库。

本文使用NS-2（Network Simulator 2）环境，在尺寸为800 m×800 m 的2D 网格地图上进行仿真，RSU 安装场景如图2所示。使用不同路径定义车辆行驶轨迹，为符合实际场景，保证数据收集有效性，在某些场景中需手动生成移动车辆，路径大小表示车辆驶过的路段数量。为在密集场景中确保方案精确，随机生成的路径执行其余仿真。仿真参数如表2所示。

表2 模拟参数

仿真过程中对通信开销进行评估，在不同路径大小和车辆数量下进行测量。对于路径大小，逐渐增加路段数量，将若干车辆设置为逐渐驶过这些路段。收集仿真过程中交换的信息数量，并将其视为与路径大小相关的通信开销。由于数据收集过程中主要收集车辆路径，而路径中的路段数量会发生变化，因此需要评估方案效率。针对车辆数量进行研究的目的是测量只有车辆密度变化的情况下发生的开销。针对路径大小，每次增加5段路径，直至20段，针对车辆数量，每次增加10辆车，直至60 辆，测量不同路径大小和车辆数量下车辆与RSU之间相互发送消息的总量，结果如图6、图7所示。

图6 不同路径大小和车辆数量下的网络开销

图7 不同车辆数量下的RSU 通信开销和车辆通信开销（路径大小为10）

由图6 可知，通信开销随路径的增加而增加，由于其取决于RSU 发送的消息数量，所以开销较大。不论附近是否有移动车辆，RSU每隔10 s均会广播一次信标消息，造成了大量无效通信开销。

由图7 可知，随着车辆数量的增加，多个路段中通信开销逐渐增大，RSU 开销占比较大，车辆发送的消息明显较RSU少，因此需对RSU增加的开销进行分析。

为检验结果，多次试验取平均值，并进行方差分析。路径大小和车辆密度的通信开销平均值如图8 所示。本文对路段、车辆每个变量运行10次后提取结果，并计算平均值，经方差分析检验，其差异显著性＜0.05。

图8 平均通信开销

实际使用中，采用V2V 方式时必须保证目标车辆与上一跳车辆恰好相遇才能传递数据，出租车和私家车行驶路线不固定，需要部署在交叉口的RSU帮助传递，否则车辆行驶路线和运行时间的不确定性难以保证数据及时交换。

5.2 支持度和置信度评估

车辆路径数据按时间排列事件的形式进行收集，即顺序模式，按照序列属性进行分类分析，支持度和置信度是其重要指标。

为挖掘序列模式，首先需设定最小支持度。对车辆行驶过程中可能行驶的路径定义一组最小支持度，并记录最小支持度在所收集运动模式中出现的次数。分析运动模式数据库，最小支持度为1、2、3、4和5运动模式出现的次数分别为12513、10657、59264、35782、89。随最小支持度的增加，运动模式数据库中作为子模式出现的运动模式的次数降低。为在预测和检测阶段提高准确性，可分别设置最小支持度，以便发现非常频繁运动模式，但会忽略一些对车辆路径预测有利的非常频繁模式。

挖掘序列模式时也需考虑与生成规则相关的置信度。此规则定义为基于已发生的特定事件序列而产生的不同序列模式事件集。在提取频繁序列模式后，需为所有可能的子模式生成运动模式，通过计算某一运动规则的置信度，得到基于前序序列事件发生某一事件的概率。例如：在图5 所示的EF路段，在F十字路口，会产生4条规则：

规则1：[MEMF]⇒[MB]（向左转）；

规则2：[MEMF]⇒[MJ]（向右转）；

规则3：[MEMF]⇒[MG]（直行）；

规则4：[MEMF]⇒[MF]（在交叉口停留）。

计算4 条规则的置信度，结果为分别13.32%、37.93%、41.14%、7.61%。规则1 的置信度为13.32%，表示在数据库的模式中，记录了13.32%的车辆从EF路段左转弯的情况。

6 结束语

本文将车载自组织网络拓扑与实际道路车辆运动路径相结合，提出一些VANET环境下序列模式定义，采用基于路侧单元和基于车辆两种方案收集车辆路径信息，通过历史车辆路径数据进行序列模式数据挖掘，对未来车辆路径预测提供准确支持。仿真过程中在不同路径大小和车辆数量下评估了网络通信开销，随着路径大小和车辆数量的增加，通信开销逐渐增大，其中RSU开销占比较大。评估了由频繁运动模式生成的运动规则置信度，并可计算出每个规则的概率。然而本文车载自组织网络数据传递延迟较高，需进一步挖掘对交通有重要影响的车辆时空特性，找出其稳定规律。