留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

大规模浮动车流数据并行地图匹配方法

谢金运 涂伟 李清泉 常晓猛 马承林 李追日 黄练

谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
引用本文: 谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
XIE Jinyun, TU Wei, LI Qingquan, CAHNG Xiaomeng, MA Chenglin, LI Zhuiri, HUANG Lian. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
Citation: XIE Jinyun, TU Wei, LI Qingquan, CAHNG Xiaomeng, MA Chenglin, LI Zhuiri, HUANG Lian. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847

大规模浮动车流数据并行地图匹配方法

doi: 10.13203/j.whugis20140847
基金项目: 

国家自然科学基金 41401444

国家自然科学基金 41371377

深圳市战略性新兴产业发展专项资金 JCYJ20121019111128765

深圳市基础研究计划 JCYJ20140828163633980

中国博士后科学基金面上项目 2014M560671

测绘遥感信息工程国家重点实验室开放基金 13S02

详细信息
    作者简介:

    谢金运, 硕士, 主要从事时空大数据分析方法和应用研究。jinyunx@foxmail.com

    通讯作者: 涂伟, 博士, 讲师。tuwei@szu.edu.cn
  • 中图分类号: P208;P283.1

A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data

Funds: 

The National Natural Science Foundation of China 41401444

The National Natural Science Foundation of China 41371377

Shenzhen Dedicated Funding of Strategic Emerging Industry Development Program JCYJ20121019111128765

Shenzhen Basic Research Program JCYJ20140828163633980

the China Postdoctoral Science Foundation Funded Project 2014M560671

the Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensin 13S02

More Information
    Author Bio:

    XIE Jinyun, master, specializes in spatial-temporal big data mining. E-mail: jinyunx@foxmail.com

    Corresponding author: TU Wei, PhD, lecturer. E-mail:tuwei@szu.edu.cn
图(7) / 表(3)
计量
  • 文章访问数:  1167
  • HTML全文浏览量:  31
  • PDF下载量:  810
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-07-13
  • 刊出日期:  2017-05-05

大规模浮动车流数据并行地图匹配方法

doi: 10.13203/j.whugis20140847
    基金项目:

    国家自然科学基金 41401444

    国家自然科学基金 41371377

    深圳市战略性新兴产业发展专项资金 JCYJ20121019111128765

    深圳市基础研究计划 JCYJ20140828163633980

    中国博士后科学基金面上项目 2014M560671

    测绘遥感信息工程国家重点实验室开放基金 13S02

    作者简介:

    谢金运, 硕士, 主要从事时空大数据分析方法和应用研究。jinyunx@foxmail.com

    通讯作者: 涂伟, 博士, 讲师。tuwei@szu.edu.cn
  • 中图分类号: P208;P283.1

摘要: 提出了一种并行地图匹配方法,高效处理海量浮动车流数据。该方法顾及交通网络拓扑,指出网格过滤、距离过滤和方向过滤等策略减少邻近候选节点的数量,利用预先生成的最短路径列表减少最短路径计算量。基于非关系型分布式数据库实现了高效率的浮动车流数据并行地图匹配,利用武汉市的浮动车流数据进行了实验。实验结果表明,本文方法正确率为90.6%,计算效率能满足大规模浮动车流数据实时处理的需要。

English Abstract

谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
引用本文: 谢金运, 涂伟, 李清泉, 常晓猛, 马承林, 李追日, 黄练. 大规模浮动车流数据并行地图匹配方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
XIE Jinyun, TU Wei, LI Qingquan, CAHNG Xiaomeng, MA Chenglin, LI Zhuiri, HUANG Lian. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
Citation: XIE Jinyun, TU Wei, LI Qingquan, CAHNG Xiaomeng, MA Chenglin, LI Zhuiri, HUANG Lian. A Parallel Map-Matching Approach for Large Volume Floating Car Stream Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 697-703. doi: 10.13203/j.whugis20140847
  • 卫星定位和移动通信技术的发展与融合带来了位置大数据的爆发[1]。浮动车技术是利用GPS设备采集大量车辆的实时位置的新型信息采集技术。浮动车数据相关研究广泛见诸于城市道路状态实时监测[2]、车辆实时导航、城市商圈探测[3]、关键交通设施利用模式分析[4]、都市物流配送优化[5]等应用中。高效的数据处理是其基础[6-7]。由于存在GPS定位误差,浮动车数据会偏离道路,需要进行地图匹配。

    地图匹配就是将带有误差的定位记录校正到正确位置,从而实现离散定位记录之间的连续轨迹还原[8-9]。常见的匹配准则包括几何距离、拓扑关系、曲线相似度等。基于上述准则,发展了几何匹配、拓扑匹配、投票法等地图匹配方法[2, 10-12]。这些方法充分利用了行驶速度、行驶方向、GPS轨迹、道路拓扑等整体信息,在后处理地图匹配中取得了较好的效果。实时地图匹配利用少量定位记录,将其准确匹配到道路段,包括权重匹配法、模糊逻辑、卡尔曼滤波、基于隐马尔可夫模型的匹配方法等[8, 13]。这些方法流程较为复杂,计算复杂度较高,通常只能处理少量车辆定位数据,无法支撑海量浮动车流数据分析的快速响应[8]

    并行计算方法速度快,计算效率高,是大数据分析的重要途径,广泛应用于遥感图像处理、空间数据查询、DEM分析等[14-15]。针对历史浮动车数据,文献[2, 16]设计了基于MapReduce并行编程模型的地图匹配方法,实现了高效的海量浮动车数据分析。但是,浮动车流数据实时更新,不确定性大、附加信息少、采样频率不一致。MapReduce并行编程模型一般针对预先收集数据,难以处理实时流数据。

    针对大规模浮动车流数据 (floating car stream data, FCSD),本文提出了一种并行地图匹配算法,利用MongoDB分布式数据库[17]实现高效率的浮动车数据处理。该方法将浮动车流数据映射到多个计算节点,利用高效过滤规则和最短路径列表快速进行地图匹配,显著提升了浮动车流数据地图匹配的效率。本文的并行地图匹配方法可广泛应用于交通状态实时监控、异常交通事件检测和群体行为监测等相关的时空大数据分析应用中。

    • 浮动车流数据是浮动车记录的时间序列。浮动车记录采集车辆在某个时刻的空间位置与状态,其数学定义为:

      $$ F\equiv \left\langle \text{id},\left( x,y \right),t,\text{status} \right\rangle \ $$ (1)

      式中,F为浮动车记录;id为浮动车的编号;t为时刻;(x, y) 为时刻t浮动车的空间位置;status为浮动车状态。在浮动车系统中,车辆上的数据采集设备不断将浮动车记录发回至服务器,以便进行数据分析。

      本文采用滑动时间窗口,即选取n个最新到达的浮动车记录进行地图实时匹配。图 1(a)给出了一个长度为3的时间窗,其中v1为最新记录,v2为待匹配记录,v3为已经匹配好的记录。随着当前时间的更新,滑动窗口沿着时间维度向前移动,其包含数据依次被更新。如图 1(b)所示,在时刻t′,车辆的最新记录为v0,待匹配记录为v1v2为已经匹配好的记录,v3则被移出滑动窗口。本文中,滑动时间窗口的长度n=3,其中v3用于提供行驶方向信息,提升地图匹配的效率与准确性。

      图  1  滑动时间窗口及其移动

      Figure 1.  Moving Time Window and Its Move

    • 并行计算一般分为数据并行和任务并行两种形式。本文采用数据并行模式,利用序号分割方法将浮动车流数据映射到对应计算单元。

      $$ k = i\;\% \;M $$ (2)

      式中,i为浮动车编号;M为计算单元数量;k为分配给浮动车记录i的计算单元;%为取余运算。由于不需要对浮动车流数据排序,该映射规则的操作速度非常快。同时,由于浮动车编号是连续的,该规则分配给每个计算单元的浮动车数量相同或者相差为1,计算负载基本相同。

      本文利用MongoDB分布式数据库,实现大规模浮动车流数据的并行地图匹配方法。MongoDB是一个非关系型数据库,按键-值对方式存储数据,特别适合处理高并发的流数据。并行地图匹配算法流程如图 2所示,利用映射规则将实时接收的浮动车流数据转发给相应的计算单元,并将其压入时间窗口,进行浮动车流数据实时地图匹配。地图匹配完成后,即时将匹配结果转发给后续的复杂实时分析。每个计算单元为一个MongoDB节点,按顺序执行时间滑动窗口内浮动车记录的地图匹配算法。

      图  2  基于MongoDB的并行地图匹配方法

      Figure 2.  Flowchart of Parallel Map-Matching Approach Using MongoDB

    • 本文采用多层次过滤策略和最短路径列表加速地图匹配,分为节点匹配和轨迹恢复两步。

    • 节点匹配确定偏离浮动车记录的候选位置集。本文采用格网过滤、距离过滤和方向过滤3个策略,尽量减少浮动车记录的候选位置数量,提高地图匹配速度。

      1) 格网过滤。格网过滤选取浮动车记录邻近的路段作为候选位置。首先将研究区域划分为矩形格网,将每个格网包含或邻接的路段编号压入对应路段列表。然后,在实时地图匹配时,格网过滤计算浮动车记录的格网索引,将对应格网及其八邻域格网作为命中格网。提取所有命中格网的路段列表,将其并集作为初始候选路段。本文中网格大小设定为500 m。

      2) 距离过滤。距离过滤利用准则进一步减少候选集合的大小。距离过滤准则为:

      $$ S=\left\{ x\left| \left| x-P \right| < {{\varepsilon }_{\max }} \right. \right\} $$ (3)

      式中,x为候选路段;|x-P|为候选路段与观察坐标P之间的直线距离;εmax为误差最大值,一般取值为均方误差的2~3倍,本文统计浮动车的定位误差分布,设定εmax=200 m。

      3) 方向过滤。格网过滤和距离过滤后,候选集包含一些空间邻近上的路段。但是,其中仍然存在一些明显的错误路段,如与行驶方向完全相反的候选位置。本文利用候选位置形成的方向进行过滤。过滤规则为:

      $$ \beta =\left\{ \begin{align} & \left| \theta -{{\theta }_{R}} \right|,\left| \theta -{{\theta }_{R}} \right|\le 180{}^\circ \\ & 360{}^\circ -\left| \theta -{{\theta }_{R}} \right|,其他 \\ \end{align} \right. $$ (4)

      式中,v0v1v2为时间窗口中的节点;θ代表行车方向与X轴的夹角;θR代表邻近路段方向与X轴的夹角;β则表示行车方向与路段方向的夹角。β越大表明行车方向与路段方向偏离越大。图 3为方向过滤的示意图,由于行车方向v2-v1-v0和路段L2方向相差较小,节点v1的候选位置M3M2可以排除,M1更为合理。

      图  3  方向过滤

      Figure 3.  Direction Filtering

      经过格网过滤、距离过滤和方向过滤后,节点匹配快速选定了邻近区域内少量位置作为候选位置。

    • 轨迹恢复选定最佳的候选位置,并恢复节点之间的轨迹。通常利用Dijkstra算法计算匹配位置与候选位置间的最短路径,耗时较长。本文采用最短路径列表加速轨迹恢复过程。最短路径列表是从道路节点出发,不超过α m的最短路径集合。

      在地图匹配算法的启动阶段,本文预先利用Dijkstra算法计算所有道路节点的最短路径集合,填充最短路径列表。其中,最短路径阈值α根据浮动车记录的采样间隔和车辆的平均行驶速度确定:

      $$ \alpha =3t\times \bar{V} $$

      式中,t为平均采样间隔 (单位s); V为平均通行速度。

      实时地图匹配时, 首先查找时间窗口中节点v2的最短路径列表,然后检查节点v1的候选位置是否在该最短路径列表中。如果是,直接读取最短路径距离;否则,调用Dijkstra算法实时计算两点间的最短路径距离。选择v2-v1距离最短的路径作为恢复轨迹。据地图匹配实验统计,采样间隔为t=68 s,平均通行速度V= 10 m/s,α=2 040 m时,约96.2%的路径在最短路径列表中。由于避免了大量的最短路径计算,该策略显著提升了轨迹恢复速度。

      最后,将距离最小的候选位置点作为匹配节点,并跟踪最短路径作为两点之间的轨迹,完成了时间窗口内的地图匹配。将时间窗向前滑动,进行下一个节点的地图匹配。

    • 本文利用武汉市浮动车数据模拟浮动车流数据进行实验,测试并行地图方法性能。浮动车数据采集时段为2009-03-08~2009-03-14。实验数据的基本信息如表 1所示。实验中的武汉市道路网络共有26 438条边,19 354个节点。

      表 1  武汉市浮动车数据集的基本信息

      Table 1.  Detail of Floating Car Data

      名称 日期 浮动车数量 浮动车记录总量 采样平均间隔/s
      S1 03-08 11 217 14 302 141 66.9
      S2 03-09 11 262 14 031 791 68.2
      S3 03-10 11 255 13 924 850 68.6
      S4 03-11 11 293 13 950 847 68.8
      S5 03-12 11 305 14 133 391 67.8
      S6 03-13 11 298 14 329 828 67.2
      S7 03-14 11 279 14 704 493 65.3

      实验环境为华为Tecal RH2288H V2服务器,内装XenServer,生成9台相同配置虚拟机。每个虚拟机的内存为4G,CPU@2.0GHz 2.0 GHz,,操作系统环境为64位CentOS release 5.5,linux版本为2.6.18-194.el5xen,部署MongoDB的版本为2.4.8。采用C++语言实现本文算法。

    • 本文从地图匹配质量和计算效率两个方面分析并行地图算法的性能。

    • 地图匹配质量分析从S1~S7中随机抽取10辆浮动车数据,利用§2的算法进行地图匹配,恢复浮动车的轨迹。人工检视地图匹配结果,发现错误匹配记录,计算地图匹配的正确率r=nright/(nright+nerror),其中nright为正确匹配记录数量,nerror为错误匹配记录数量。

      表 2为地图匹配质量分析的实验结果。由表 2可知,地图匹配结果的质量较高。在S1-S7中,随机抽样数据中的正确率都超过了90%。图 4以某辆车900~1 220 s的地图匹配为例,给出了本文算法的计算结果。由图 4可知,本文算法能够较好地克服平行道路的影响和一般交叉路口的影响,给出正确的匹配结果。但是,其地图匹配结果仍然存在一些错误。图 5以复杂路口为例,给出了地图匹配的错误情形。由于定位误差更加偏向辅道,匹配结果M3-N2-N1-M0会绕行,而正确结果M3-M2-M1-M0是直行。

      表 2  地图匹配质量分析结果

      Table 2.  Detail of Map-Matching Results

      名称 浮动车数量 浮动车记录数量 正确率/%
      S1 10 11 860 90.92
      S2 10 11 435 90.68
      S3 10 12 585 90.62
      S4 10 12 587 91.00
      S5 10 12 163 90.96
      S6 10 12 149 91.23
      S7 10 11 243 90.95

      图  4  正确的地图匹配结果示例

      Figure 4.  Right Map-Matching Case

      图  5  错误的地图匹配结果

      Figure 5.  Wrong Map-Matching Case

      表 2可知,在S1~S7这7个数据集中,并行地图匹配方法的正确率在90.62%~91.23%之间波动,差异较小,表明本文算法的鲁棒性较好。相比于文献[6]中的低采样率浮动车数据地图匹配算法 (a multi-criteria dynamic programming map-matching, MDP-MM)(采样间隔60 s, 正确率为89.29%),本文算法的结果质量略好。相比于文献[10]中的高采样率浮动车数据地图匹配算法,本文算法的正确率较低。这是因为本文算法为了适应流数据,采用了较短的时间窗口,过滤规则也相对简单。

    • 算法效率用计算时间度量。为了测试本文算法的效率,执行时逐个时间片内处理浮动车数据,记录其地图匹配时间。本文设计了4种时间片长度,分别为150、300、450、600 s,进行浮动车流数据地图匹配。

      图 6给出了不同时间片下的地图匹配串行算法的计算时间 (不包括I/O时间)。由图 6可知,随着时间片长度从150 s增长到600 s,地图匹配时间从20.89 s增长到46.51 s,基本上呈线性增长,表明该方法具有良好的扩展性。地图匹配算法的时间约占时间片的7.5%~14.0%,能够满足浮动车数据处理的基本需求。

      图  6  地图匹配方法的计算时间

      Figure 6.  Computing Time of the Sequential Map-Matching Algorithm

      并行地图匹配效率以加速比定义:

      $$ S={{T}_{0}}/{{T}_{n}} $$ (5)

      式中,T0为串行地图匹配方法的计算时间;Tnn个计算节点下的并行地图匹配时间。本文中,计算时间均不包括I/O时间。

      实验中采用一个台虚拟机作为主节点,不断增加计算单元数量,测试不同配置并行计算平台下的地图匹配效率。图 7为不同时间片下地图匹配并行方法的计算时间与加速比。由图 7可知,随着计算节点的增加,计算时间均快速递减。如图 7(d)所示,时间片为600 s时,在8个计算单元的并行计算平台下,地图匹配完成时间不超过6 s,约为时间片时长的1%,可以满足浮动车流数据分析的需要。与文献[16]中基于MapReduce并行框架的浮动车数据处理相比 (8个计算单元,相同计算平台下计算时间约5.7 s),由于最短路径列表加速了地图匹配的速度,本文计算时间约为其66%。同时,本文的数据分割方法较好地实现了负载均衡,算法加速比随着计算单元的增加同步增长,近似正比于计算单元数量。表 3给出了各并行配置下计算负载的统计结果,各计算单元的负载中误差不高于0.5%。因此,本文算法具有良好的可扩展性,能够取得近似线性的加速比。

      图  7  并行地图匹配方法的计算时间与加速比

      Figure 7.  Computing Time and Speedup of Parallel Map-Matching Algorithm

      表 3  并行地图匹配算法的负载统计

      Table 3.  Load of Parallel Map-Matching Algorithm

      计算单元数量 负载平均值/个 负载中误差/个 百分比/%
      2 49 669 146.5 139 518.5 0.28
      4 24 834 573.3 96 698.5 0.39
      6 16 556 382.2 76 155.1 0.46
      8 12 417 286.6 61 431.3 0.50
        注:负载以每个计算单元处理的浮动车记录数量度量。

      综上所述,本文的地图匹配并行算法效果良好,能够满足大规模浮动车流数据实时分析的需要。

    • 浮动车数据处理是时空大数据分析的重要内容。针对大规模浮动车流数据,本文提出了基于MongoDB分布式数据库的并行地图匹配方法,实现了实时浮动车数据预处理。该方法将浮动车流数据实时映射到多个计算节点,保持负载均衡;设计了邻近候选集的过滤规则,减少候选位置的数量;利用局部最短路径列表,加快了地图匹配的速度。利用武汉市浮动车流数据进行实验,实验结果表明,并行地图匹配方法能够快速完成上万辆浮动车流数据处理,能够支撑大体量浮动车流数据实时分析。本文的后续工作可以进一步延伸为复杂的交通状态分析、交通异常监测和城市交通状态的实时可视化等,服务于智慧交通和智慧城市。

参考文献 (17)

目录

    /

    返回文章
    返回