移动环境下的在线轨迹匹配和压缩方法及实现

摘要

交通大数据是实现城市智慧交通服务的数据基石，时空轨迹是其中一种重要类型。近年来，得益于移动互联网和定位等技术的广泛普及和成熟，车辆的时空轨迹通过车载GPS设备很容易地被实时采集、传输并保存至云端数据中心。然而“海量”时空轨迹数据也一定程度为城市交通智慧化带来了挑战，如严重耗费带宽资源、极大占用存储空间、阻碍数据可视化与挖掘等。在线轨迹压缩技术是一种解决以上问题的有效方法。为减少移动时空轨迹，现有系统或方法只是简单地降低GPS设备的采样频率，但这种做法无疑增加了轨迹的“稀疏性”和“不确定性”。更糟糕的是，城市路网的复杂特性以及GPS设备的定位误差使推断车辆行驶轨迹变得更加困难。为此，本文设计了一套轨迹匹配与压缩的系统框架。具体而言：首先，基于SD-Matching((S)patial-(D)irectional Matching)算法，本文将轨迹映射在广泛易得的路网以克服定位误差及实现轨迹语义丰富化；然后，基于 HCC ((H)eading-(C)hange-(C)ompression)算法和DAVT ((D)istance-(A)cceleration-(V)elocity-(T)imestamp)算法，本文在空间和时间两个维度分别实现移动轨迹的压缩，以减少传输和存储移动空间轨迹数据带来的代价。移动环境对在线轨迹匹配和压缩系统的计算能力、时间延迟和量级大小提出了严格要求，这意味着计算能力有限的GPS设备无法负担计算任务（也即轨迹匹配与压缩）。受移动边缘计算的启发，本文创新地将繁重的计算任务（也即轨迹匹配与压缩）迁移至GPS设备附近的智能设备，如司机的智能手机。　　概括而言，本文主要成果包括以下几个方面：　　① 在轨迹匹配上，本文探索车辆航向的可用性，并在地图匹配的各个阶段巧妙地利用该信息，以提高轨迹匹配的效率与质量。　　② 在空间轨迹压缩上，本文探索交叉路口车辆航向变化在压缩轨迹的可用性，并基于此设计高质量的压缩算法，以更好地平衡压缩率和效率。　　③ 在时间轨迹压缩上，本文提出一种全新的轨迹表示，它包含三个部分，即距离序列（D）、加速度和瞬时速度序列（AV）和时间序列（T）。针对它们分别设计了三种不同的压缩器。另外，我们是保存并压缩时变速度信息的先驱，该信息对理解驾驶风格和掌握城市交通状态至关重要。　　④ 本文将算法部署在真实移动环境。受边缘计算的启发，本文创新地将繁重计算任务从计算能力弱的GPS设备迁移到附近手机端。这一举措不仅能解决算力不足，还能释放对GPS设备采样频率的限制。　　⑤ 无论是轨迹匹配还是压缩，或真实移动环境下的系统，我们都利用真实数据集对它们进行了广泛评估，实验结果证明它们在性能（如准确度、压缩率和效率等）上均优于同类算法或系统。

目录

1 绪论

1.1引言

1.2 国内外研究现状

1.2.1 轨迹匹配的国内外研究现状

1.2.2 轨迹压缩的国内外研究现状

1.3 论文的组织结构

2 在线轨迹匹配算法

2.1 前言

2.2 主要概念和算法概述

2.3 SD-Matching算法

2.3.1 识别候选边

2.3.2 寻找路径

2.3.3 筛选路径

2.4 实验评估

2.4.1 实验设置

2.4.2 有效性评估

2.4.3 效率评估

2.4.4 其他性能评估

2.5 半自动标记软件TLabel

2.6 章节小结

3 轨迹压缩：空间维度

3.1 前言

3.2 主要概念

3.3.1 算法设计动机

3.3.2 算法细节

3.3.3 轨迹解压

3.4 实验评估

3.4.1 实验设置

3.4.2 有效性评估

3.4.3 效率评估

3.4.4 边界选择

3.4.5 其他性能评估

3.5 章节小结

4 轨迹压缩：时间维度

4.1 前言

4.2 主要概念和算法概述

4.3 DAVT轨迹表示及优点

4.4 DAVT压缩算法及解压

4.4.1 D压缩器

4.4.2 AV压缩器

4.4.3 T压缩器

4.4.4 DAVT解压器

4.5误差边界的理论分析

4.6.1 实验设置

4.6.2 训练DAVT压缩器

4.6.3 信息损失研究

4.6.4 评估DT压缩器的性能

4.6.5 DT压缩器VS DAVT压缩器

4.7 章节小结

5 移动环境下在线轨迹压缩的实现

5.1 前言

5.2 系统概述

5.3 优化系统效率的两种策略

5.4 实验评估

5.4.1 实验设置

5.4.2 有效性评估

5.4.3 效率评估

5.4.4 案例研究

5.5 章节小结

6 总结与展望

参考文献

附录

A. 攻读硕士学位期间的主要研究成果（#共同一作）

B. 攻读硕士学位期间的主要科研项目

C. 学位论文数据集

致谢