一种基于Hadoop的分布式地图匹配算法

郭淑琴,薛益赵,徐步汇

(1.浙江工业大学 信息工程学院，浙江 杭州 310023；2.浙江工业大学 机械工程学院，浙江 杭州 310014)

一种基于Hadoop的分布式地图匹配算法

郭淑琴1,薛益赵1,徐步汇2

(1.浙江工业大学 信息工程学院，浙江 杭州 310023；2.浙江工业大学 机械工程学院，浙江 杭州 310014)

摘要：浮动车数据是重要的交通数据之一,能为相关部门提供实时交通状况信息.传统地图匹配算法难以直接适用于海量的浮动车数据匹配.因此在Hadoop的基础上，设计了一种分布式并行地图匹配系统，该系统加入了HashMap网格索引算法，能够加快匹配初筛速度，达到并行处理的效果,同时结合海拔高程信息和道路模糊化函数提升匹配准确度.实验结果表明所提算法具备较好的高效性和准确性.

关键词：地图匹配；浮动车；智能交通系统；云计算

Research on distributed map-matching algorithm based on Hadoop

GUO Shuqin1, XUE Yizhao1, XU Buhui2

(1.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China；

2.College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:Floating car data is one of the most important traffic data, which can provide real-time traffic information for relevant departments. Traditional map-matching algorithm is difficult to directly apply to the numerous floating car. Based on the Hadoop, one kind of distributed parallel map-matching system is designed. It adds the HashMap grid index algorithm in order to accelerate the speed of matching screening and achieve the effect of parallel processing. At the same time, it can enhance matching accuracy through combining elevation information and road fuzzy matching function. The experimental result shows that the proposed method has higher efficiency and higher accuracy.

Keywords:map-matching; floatingvehicles; intelligent transportation system; Hadoop

随着社会的发展和经济的增长，城市交通拥堵现象愈发严重.浮动车技术作为一种新型的城市出行规划方式和路况信息获取方式,已经逐步成为研究热点[1].地图匹配技术是浮动车数据处理中最关键的内容之一,只有判断出车辆在哪条道路上行驶,才能将GPS数据转化为有效的道路交通状态信息[2].由于浮动车自身特点，在传统的MPI和OpenMP分布式并行模型下,编程难度大，可扩展性差，浮动车数据进行地图匹配耗费大量的计算时间，因此很难应用于海量浮动车数据处理.

笔者将从两个方面改进匹配效果：1) 鉴于传统并行方法编程难度大，可扩展性差的问题，设计一种能应用于Hadoop分布式平台的地图匹配方法提升匹配效率；2) 通过合理应用海拔高程信息提升匹配准确度，改进传统方法在处理高架和地面道路重叠时的不足.

1基本算法

1.1建立HashMap网格索引

城市道路是错综复杂，同时也是分散在城市的各个区域上.当对一个待匹配点进行匹配计算时，如果将几公里以外的道路也纳入匹配范围，可想而知将会严重影响整体的匹配效率，所以建立一个高效的索引算法对加快匹配速度显得格外重要[3-4].传统的网格索引和四叉树索引的时间复杂度均为对数时间级，考虑到分布式环境下的高并发性要求，笔者设计一种新型的HashMap网格索引[5].

HashMap网格索引比起传统的四叉树索引优势在于：传统四叉树索引采用地理空间递归的方法划分不同层次的树结构，但空间对象分布不均匀时，随着地理空间对象的不断插入，将形成一棵严重不平衡的四叉树，从而导致查询效率的急剧下降，在理想情况下时间开销也是对数时间级，而HashMap索引通过数组Hash映射，将查找时间开销降低到O(1)时间量级.HashMap网格索引同时将网格区域所对应的道路节点信息提前存储到Hadoop分布式缓存上，而不是采用传统的方法根据待匹配点为中心建立网格匹配区，通过改进这两点大大的提高了算法在Hadoop分布式平台上的高并发性.

如图1(a)所示，根据城市最大外包矩形划分网格，同时依据Taylor提出的在GPS定位中,以距原始定位点100 m内的道路为计算路段,车辆位于这些路段的置信度为95%[6],将单个网格的长和高设置为100 m.对于待匹配点P，只需根据P点的经度减去左上角顶点的经度，以杭州为例左上角顶点经度为119.698，然后除以100 m所对应的经度范围0.000 9后向下取整就可得到P点所在网格的列号.同理，P点的行号可以确定.当计算出行号和列号后，通过Hash映射就可以确定P点所在网格的确切位置[7].

图1　HashMap网格索引示意图Fig.1　Schematic diagram of the Hashmap grid index

在对待匹配点P进行匹配时发现,当P点处在网格的边缘，就有可能造成与P点相匹配的道路位于相邻的其它网格内，从而无法准确匹配.所以对单个网格内部再进行了一次划分，如图1(b)所示，分成1区，2区，3区，4区.对于待匹配点P需要计算的网格包括P点所在的网格，以及该网格相邻上方网格的4区，右上角网格的3区和右相邻网格的1区.通过二次划分大大提升了匹配的准确度.

1.2归一模糊化的非高架/高架匹配算法

图2为匹配算法的总流程图，将匹配算法分为非高架匹配法和高架匹配法两部分，因为高架匹配算法的计算量大于非高架匹配算法，所以通过判断待匹配点所在网格缓冲区内是否包含高架来提高匹配效率，并且能很好的解决高架与地面重叠、交叠、平行的情形.

非高架匹配算法采用车头方向与路段方向之间夹角，待匹配点到路段垂直投影距离两种因素的归一模糊匹配系统.高架匹配算法在此基础上加入了高程差.归一模糊系统框架如图3所示.

在该框架内我们引入归一模糊化值函数λ：归一模糊化值是描述浮动车GPS坐标位置与一条道路的匹配程度，使用(0,1)区间的浮点数进行归一模糊化，归一模糊化值越接近1，代表该待匹配点越有可能位于这条道路[8].

图2　匹配算法总流程图Fig.2　Flow chart of matching algorithm

图3　归一模糊系统框架Fig.3　Normalized fuzzy system framework

非高架归一模糊化值函数为

(1)

式中：ΔGPS为GPS的平均误差值；d为待匹配点到路段的垂直距离；θ为车头方向与路段方向之间的夹角；μ1和μ2分别为距离和夹角在归一模糊化值中的权重,且满足μ1+μ2=1.

高架归一模糊化值函数为

(2)

式中：h为待匹配点的高程；H为路网信息的高程；μ1，μ2和μ3分别为距离、夹角和高程在归一模糊化值中的权重,且满足μ1+μ2+μ3=1.

1.3候选匹配道路集合R

为了满足Hadoop分布式平台的高并发性，减少归一模糊化值的计算量，在计算归一模糊化值之前笔者引入候选匹配道路集合R，在候选道路集合R中定义阀值Κ，且Κ=ΔGPS，当待匹配点到道路的投影距离d-Κ<0时，就认为该道路是有可能的正确匹配路段，因此将该道路加入到候选匹配道路集合R中.当不满足上述条件时，果断抛弃该条道路，不在继续计算夹角度量和高程差度量.

2Hadoop分布式平台搭建

MPI，OpenMP和Hadoop是当前并行计算领域三个主流的并行系统框架，笔者采用Hadoop系统框架和map/reduce处理模式，Hadoop框架具有可扩展性好，编程难度低的特点，同时也是近年来研究的热点.在三台配置为Core i5-3320双核2.60ghz CPUS，8G内存，1T硬盘，Ubuntu系统上搭建小型Hadoop集群，该集群配有一个Namenode节点和两个Datanode节点[9].NameNode节点相当于一个管理者，将输入数据进行切片分块，然后分发给下面的DataNode节点进行处理.DataNode节点相当于一个执行者，它调用Map函数将接收到的数据块进行匹配运算.

Map/Reduce过程是Hadoop框架的主要工作模式，在负责完成海量浮动车数据的地图匹配计算任务图4中，Map过程主要包括：1) 接收系统分发下来的浮动车数据块；2) 解析出浮动车数据对应的哈希码；3) 从系统分布式缓存中调取相应哈希码的网格中的道路节点信息；4) 根据匹配规则进行归一模糊化匹配计算；5) 将匹配结果输出到Reduce过程.

Reduce过程主要包括：1) 接收从Map过程中计算后的匹配数据；2) 将匹配数据进行快速排序，输出最大值作为最终匹配结果.

图4　Map/Reduce处理过程Fig.4　Map/Reduce processing procedure

3算法评估及系统验证

使用的浮动车数据来源于杭州市8 000多辆装备有GPS设备的出租车(2012.06-2013.05)，以每20 s时间间隔向主服务器发送一次GPS数据.数据的主要结构包括车辆编号、地理位置、发送时间、经度、纬度、行驶速度、行驶方向、高程及载客状态.路网数据来源于浙江银江某研究院提供的杭州市GPS路网坐标信息，其中包括道路路段编号、道路起始点经纬度坐标、道路终止点经纬度坐标.

3.1同一浮动车的连续匹配评估举例

笔者方法在对同一浮动车的连续匹配时有明显的效果.由于考虑了车头方向与路段方向之间的夹角，点到路段的垂直距离两种因素，可以有效地避免在交叉路口处的错误匹配.图5(a)为服务器对同一浮动车接收到的原始定位信息，从图5中可以看出：原始定位信息不准确，大多数都偏离了道路.图5(b)为经过匹配算法矫正后的定位信息，相较与图5(a)精确度大大提高，定位点基本位于道路的中心线上.

3.2地面道路与高架交叠情况下的匹配评估举例

笔者方法在对地面道路与高架交叠情况下时有较准确的匹配效果.图6(a)为处于地面道路与高架交叠路段时浮动车的原始定位信息，H表示高程值，通过合理利用浮动车高程信息将待匹配点准确的匹配到高架与地面道路上，如图6(b)所示.

图5　同一浮动车的连续匹配效果图Fig.5　Continuous matching of the same floating car

图6　地面道路与高架交叠情况下匹配效果图Fig.6　Matching with the ground road and overhead road overlapping

3.3大批量浮动车数据的匹配评估举例

笔者选取1 万个原始浮动车数据输入到Hadoop分布式平台进行匹配计算，图7为匹配前后某道路的对比图，图7(a)为原始浮动车数据，图7(b)为匹配后的浮动车数据.从图7中看出：当该系统处理大批量浮动车数据时，依旧保持较高的准确度.

图7　对1万个数据点进行匹配前后部分对比图Fig.7　Effect diagramof matching the ten thousand data points

同时，选取10 万和20 万个原始点分别输入到Hadoop平台和单机串行平台中做比较，具体测试结果如表1所示.从表1看出：当数据量小时，单机串行平台匹配效率更高.这是因为整个分布式平台前期对网格索引的初始化处理和内存的加载耗时，JobTracker会根据任务配置要求TaskTacker启动JVM来处理map子任务或者reduce子任务耗时造成.但随着数据量的增大，Hadoop平台的优势将逐渐体现.总体来说原本任务在单机上运行的计算量，通过Hadoop的Mapreduce机制进行有效的分摊.

表1Hadoop平台和单机串行平台性能比较

Table 1The comparison of the performance of Hadoop and single machine

浮动车数据量/万条Hadoop分台处理时间/s单机串行处理时间/s137.2516.001056.4977.322077.13132.26

4结论

针对海量浮动车数据的匹配环境，设计了一种基于Hadoop的分布式算法，达到并行处理的效果；设计了Hashmap网格索引方法，改进了传统方法下实时性低的问题；通过合理利用高程信息，设计了高架/非高架算法，改进了传统方法下处理高架与地面重叠、交叠、平行情形下的不足.实验结果表明：笔者的算法在处理海量浮动车数据时具备较好的高效性和准确性.

参考文献：

[1]章威，徐建闽，林绵峰.基于大规模浮动车数据的地图匹配算法[J].智能交通系统与信息技术,2007,7(2)：39-40.

[2]罗元，谢波，彭卫兵，等.基于Vega Prime的虚拟现实车辆智能运动模拟[J].浙江工业大学学报，2013，41(4)：158-163.

[3]郭海锋，方良君，俞立.基于模糊卡尔曼滤波的短时交通流量预测方法[J].浙江工业大学学报，2013，41(2)：218-221.

[4]辛飞飞，陈小鸿，林航飞.浮动车数据路网时空分布特征研究[J].中国公路报,2008,21(4):106.

[5]王为，姚明海.基于计算机视觉的智能交通监控系统[J].浙江工业大学学报，2010，38(5)：174-179.

[6]朱丽云，郭继孚，温慧敏,等.一种适用于复杂城市路网的浮动车实时地图匹配技术[J].交通与计算机，2007,25(6)：82.

[7]TAYLOR G, BLEWITT G. Road reduction filtering using GPS[C]// AGILE.The 3rd AGILE Conference on Geographic Information Science. Helsinki: AGILE,2000:114-120.

[8]吴伟.分布式并行地图匹配系统研究与实现[D].广州：中山大学，2012.

[9]XIA Yingjie, LI Yuncai.Quadtree-based domain decomposition for parallel map-matching on GPS data[C]//IEEE.InternationalIEEE Conference on Intelligent Transportation Systems. Anchorage:IEEE,2012：810-812.

(责任编辑：陈石平)

中图分类号：U12

文献标志码：A

文章编号：1006-4303(2015)03-0332-04

作者简介：郭淑琴(1970—)，女，山西夏县人，教授，研究方向为光通信技术，E-mail：guosq@zjut.edu.cn.

收稿日期：2014-12-12