亢 丽，王洪玉

（大连理工大学信息与通信工程学院，辽宁 大连 116024）

0 引言

现今城市化进程越来越快，人们对于交通出行的需求不断增加，汽车行业也在迅猛发展，2013年汽车产销量已超过2000万台。汽车数量显著增加的同时也给城市交通造成了巨大压力，如何有效利用当前道路资源为出行者提供便利，已成为人们关注的焦点。在这种情况下，智能交通系统应运而生。

智能交通系统结合多种高新技术，如通信、信息处理、卫星定位、传感、控制等，应用在城市道路交通系统中，旨在建立大范围实时、准确、高效的交通运输管理系统。通过收集城市交通信息，分析出当前路况的拥堵程度并进行发布，使出行者可及时获知交通状况，进行合理的路径规划。从20世纪60年代开始，美国、欧洲、日本等国家相继开始进行智能交通系统（ITS）的研究[1]，20世纪以来，我国也大力投入智能交通系统建设，已在北京、深圳等地试点运行。

交通信息的采集和处理是智能交通系统的第一步，也是基础性、关键性的步骤。获取交通信息的方式、数量、实时性，处理数据的效率、准确度、鲁棒性，信息的流动机制、速度和可靠性等，都决定了智能交通系统性能的优劣。传统的交通信息采集方法主要为定点式采集，如地理式线圈检测器、视频检测等。而浮动车采集技术因其具有覆盖范围广、安装和维护成本低、实时性强、抗干扰性强、信息精度高等优点，已成为新兴主流的动态实时交通信息采集技术。本文中也选用浮动车数据作为道路交通信息源。

交通信息的处理，旨在将收集到的浮动车GPS点利用地图匹配技术定位至电子地图，结合道路的长度及浮动车运行的时间来估算路段行车的平均速度，判断拥堵状况。浮动车收集到的GPS信息具有GPS定位误差、坐标转换误差等系统误差，会出现地图车辆轨迹曲线与实际行驶路线不吻合的现象，因此，应使用地图匹配技术来减小匹配误差，尽可能地还原车辆运行的真实轨迹。浮动车收集到的GPS点信息数量庞大且精度不一，城市中错综复杂的路网使得电子地图也包含海量数据，要求地图匹配算法具有较高匹配精度、匹配效率和良好的鲁棒性，以面对大规模数据处理的挑战。与此同时，出行者对获取信息的实时性要求也越来越高，优化地图匹配算法仍然无法解决实际吞吐量存在的瓶颈，匹配的实时性仍需提高。

本文针对上述问题，设计实现了基于实时浮动车数据的分布式地图匹配系统[2]，增加信息处理的吞吐量，同时对地图匹配算法进一步优化，提高了浮动车数据收集和处理整个过程的实时性、有效性和可靠性。

1 信息采集和分布式处理系统设计

数据采集和处理作为智能交通系统的基础模块，对整个系统的优劣有重要影响。随着汽车数量的增多，出行量也逐渐增大，在一定时间内需要有效处理的浮动车数据显著增加，只有提高数据处理的效率和吞吐量，才能满足用户的实时性需求。优化地图匹配算法可提升处理速度，但仍然不能达到海量浮动车数据实时处理的要求，因此，建立分布式的信息处理系统，使地图匹配同时在不同PC上并行实施，消除了单一处理的性能瓶颈，解决海量数据的处理难题，使系统达到实际用户所期望的实时程度。

1.1 分布式机制分析及系统架构

浮动车上传GPS数据后存至GPS数据中心，作为采集的信息源。信息处理系统需要从GPRS数据中心获取数据统一存入中心处理器，然后分发至各分布式地图匹配节点进行地图匹配工作。分布式处理系统的框架及在智能交通系统中所处位置如图1所示。矩形框内部分即为分布式匹配系统。

图1 分布式地图匹配系统架构

地图匹配过程一般包含数据预处理、异常数据检测过滤、网格和路段筛选、GPS点匹配等步骤。因此，分布式并行处理有以下两种机制：机制①为每个节点进行某个步骤的处理，各步骤按照流水线进行；机制②为每个节点分别完成上述所有步骤，中心处理器将不同范围的数据送至不同节点进行匹配。机制①的优点是每个节点任务单一、处理效率较高，但结合各步骤的复杂度和计算量可知，数据预处理阶段数据量最大，而网格和路段筛选阶段的计算复杂度最高、耗时最长，流水处理的机制一方面会造成各个计算节点负载不均衡，另一方面如果某个节点出现问题会影响后续节点的正常工作。因此，选用机制②作为分布式处理的方法。将所有浮动车数据按照浮动车编号进行均匀划分，每个节点处理一定范围的信息。在可靠性方面，各节点独立运算，不存在顺序和数据依赖关系，可达到较好的分布式效果；在网络通信方面，中心处理器与节点只需在初始进行数据传递，减小了网络负载量以及传输误差；在负载均衡方面，每个节点的数据量和计算量几乎接近，基本可达到负载均衡；并且随着数据量的增加，可以动态增加节点个数，提高系统的效率以及可伸缩性。从上述分析可知，机制②的分布式处理方法基本满足系统对实时性、可靠性、稳定性的要求[3]。

整个系统由GPRS数据中心、中心处理器和分布式地图匹配节点PC构成。GPRS数据中心是浮动车GPS数据的来源，中心处理器负责从GPRS数据中心接收数据并进行数据的整合调度及多线程发送，分布式地图匹配PC完成地图匹配工作。

1.2 模块功能简介

在数据处理和采集系统中，GPRS数据中心、中心处理器与分布式地图匹配PC之间需要进行通信和数据传递。为保证系统的可靠性、有效性和负载均衡，在中心处理器中设置数据接收、数据分配、数据共享缓冲和线程管理四个子模块，在分布式地图匹配PC中同时设立缓冲区，进行数据格式的转化及预处理等。地图匹配处理完成的数据存放在数据库中，供后续的功能模块使用。

图2为系统模块功能框图[4]。中心处理器接收模块与GPRS数据中心建立连接，源源不断地从数据中心获取实时浮动车数据。在接收模块中，根据list链表和生产者消费者、模型建立接收缓冲区，不仅为接收模块和后续的分配模块建立统一的数据存取接口，同时保证数据接收与后续模块之间速度匹配、不产生数据溢出，提高中心处理器处理海量数据的健壮性。浮动车数据从接收缓冲区取出后，进入数据分配模块，按照要求把不同浮动车数据填入相应的数据共享区，发送至不同的地图匹配节点进行匹配操作。数据共享缓冲模块为分布式通信的缓冲区，每个分布式匹配节点在中心处理器中分别对应一个通信缓冲区，存放经过分配后的数据，缓冲区满后，将GPS数据打包发送至地图匹配节点。该缓冲区同样采用生产者消费者模型，提供数据传递接口，保证数据不产生溢出，另外便于浮动车GPS数据打包发送，提高系统通信的效率。线程管理模块管理多个线程[5]，包括浮动车数据的接收、分配、将对应数据送入分布式缓冲区、进行分布式通信传入各地图匹配节点等。该模块不仅利用多线程实现各子模块功能，同时利用线程池解决线程之间的同步和互斥问题，也为系统提供实时的子模块和节点信息。既利用多线程提高了系统效率，又能做到线程的有效管理，是分布式系统的重要环节。

图2 系统模块功能框图

分布式地图匹配节点在地图匹配之前，要接收数据存入缓冲区并进行预处理。根据配置信息的过滤条件和数据准确性判断条件，可判断GPS数据是否为有效记录、是否重复、是否为跳点坏点、是否在采样周期外、是否在经纬度误差范围和网格范围外，对不符合要求的GPS数据进行剔除，可提高后续地图匹配的精度和效率。GPS浮动车数据存入缓冲区，避免瞬时数据量过大造成溢出，还可配合地图匹配的算法，使浮动车数据积累到所需的数量开始匹配，同时按照时间戳顺序，有序插入List链表，使数据利用起来更加有效快捷。

2 地图匹配算法简介

地图匹配节点是系统工作量最大的节点，将从浮动车上获得的表示车辆当前位置的GPS点信息与电子地图上的矢量化路段相匹配，寻找浮动车行驶道路，确定相对于电子地图的车辆实际运行轨迹，并将GPS定位点投影到路段上。通过地图匹配，可获知车辆在道路上所处位置及行驶方向，再根据浮动车的时间和路段距离，进一步判断道路的实时拥堵情况，并向出行者进行发布。地图匹配算法的效果直接影响车辆定位的精度，因此要求算法有良好的匹配精度和鲁棒性。在智能交通系统中，出行者需要在尽可能短的时间内获知道路状况，这也要求地图匹配算法有较好的实时性。

2.1 常用地图匹配算法

目前，地图匹配算法主要分为位置点匹配和浮动车轨迹曲线匹配两种。

位置点匹配算法包括基于电子地图几何特性的匹配、基于电子地图拓扑结构的匹配及基于概率统计的点匹配[6]。基于地图几何特性的匹配，分为点到点的匹配、点到线的匹配和线到线的匹配三种。基于网络拓扑结构的匹配分析前一次匹配结果和当前车辆的运行方向，利用道路的网络拓扑关系，确定待匹配路段范围和GPS匹配点。基于概率统计的匹配为每一个GPS浮动车数据设置置信区域，根据历史匹配结果的概率统计确定匹配路段。浮动车轨迹曲线匹配是基于历史数据的匹配方法，将GPS定位点与实际道路路网结合，在路网上寻找与GPS点轨迹最接近的路径，作为浮动车的真实行车轨迹，并据此确定GPS匹配点。

近些年来，为了提高地图匹配算法的精度，各种先进技术被应用到地图匹配中，使匹配算法呈现出多样化的特点。如基于卡尔曼和扩展卡尔曼滤波、模糊数学模型、神经网络、概率方法、D—S证据理论、多交互模型、贝叶斯判别应用、状态空间模型和粒子滤波算法等的地图匹配算法[7]。

对比分析各种地图匹配算法可知，点到点和点到线的匹配方法算法简单、计算效率高、实时性强，但大多适于高速公路等简单结构的路网，在道路密集路况复杂的城市路网中匹配的精度较低；线到线的匹配对异常点非常敏感，且在复杂路网（如立交匝道）匹配精度不高；基于电子地图拓扑结构的匹配对电子地图的依赖性太高，且不考虑速度方向等因素，同样对异常点敏感；基于概率统计的点匹配考虑了道路的地形特性，但匹配精度仍不够高。利用卡尔曼滤波等先进技术可以较好地提高匹配精度，但复杂算法的计算量和复杂度都大幅提高，实时性差，不适用于实时数据的地图匹配[8]。以上算法主要考虑GPS定位点轨迹和路网结构的相似性，未考虑利用定位轨迹的连通性来提高匹配精度。利用浮动车轨迹曲线匹配可充分结合浮动车运行轨迹和路网信息，匹配的精度较高，但因需要调用历史数据，实时性较差。因此，在保证匹配精度的情况下尽可能地提高数据处理实时性，还需要寻求更好的算法。

2.2 综合地图匹配算法研究

本文针对智能交通系统对实时性和匹配精度的要求，提出了一种基于道路网格和最短路径的快速地图匹配算法，算法流程如图3所示。

图3 地图匹配流程图

本文的地图匹配算法利用GPS定位点轨迹，在电子地图上寻找最接近真实行车轨迹的最短路径，将GPS点投影到此路径对应路段，作为匹配点。此算法利用城市路网的拓扑特性、车辆连续运动的轨迹、浮动车运行的角度等，运算时间复杂度为O（c），大大缩短了匹配处理的时间，且能够达到智能交通系统实际运行所需的精度。

2.2.1 地图数据的读取和道路网络网格的划分

在此阶段加载电子地图数据，读取相应的路段和路口信息。由于路段信息和路口信息数量庞大且被反复引用，因此利用字典结构保存，便于查找。按照一定标准（一般300～400m）为步长，将道路网络从上到下、由左至右网格化均匀分块，将道路网络分为M×N个相同大小的网格，其中，M为网格行数，N为网格列数。M和N即为参数值的大小，直接影响地图匹配的复杂度和精度，因此，进行反复实验仿真确定最佳参数值。

2.2.2 网格候选路段的确定

划分路网网格的目的，是为了更方便地确定浮动车GPS点附近的备选路段，因此需要记录每个网格包含或相交的所有路段，将其编号作为索引值存入所在网格对应的数组中。根据2.2.1中的字典结构，可迅速查找到其他相关信息。由于需要将所有的网格和所有的路段相对应，因此，采用遍历所有路段的方式，路段的起终点或者中间点与某网格相交，则该路段就作为此网格的候选路段。在地图匹配过程中，只需要在启动时刻进行一次扫描，即可将路段与网格对应，为后续匹配工作提供了便利。

2.2.3 浮动车GPS点候选路段的确定

浮动车GPS点候选路段，指在真实路网中此GPS点可能所处的路段。根据浮动车GPS点中所包含的经纬度信息，可确定此GPS点所在的网格，如网格左下角端点坐标为(x0,y0)，网格数量为M×N，每个网格尺寸为l×l，浮动车GPS点坐标为(x1,y1)，则其所在网格为Grid([(x1-x0)/l],[(y1-y0)/l])，以此网格为中心的相邻九个网格中所包含的全部路段，即为此GPS地图匹配的候选路段。

2.2.4 GPS点轨迹最短路径的选择

在寻找最短路径时，以浮动车的一组GPS点轨迹作为一段旅程，在电子地图上寻找最符合此运动轨迹的从起点到终点的路段，最终获得的最短路径作为浮动车的真实运动轨迹。

在此算法中，地图匹配的目标函数[9]见式（1）：

式中：D为电子地图中所有路段；l为路段长度；x表示是否为候选路段，如果是，则x取值为1，非候选路段x为0；P为地图匹配路段的权重，P越高，代表所在路段成为最短路径的概率越大。

这里利用二次网格的划分和GPS点的角度[10]、路段附近GPS点的数量来修正P值，为每条候选路段计算权重总和，权重计算公式为：

P1为二次网格划分权重值，在电子地图初始化环节，一次道路网格划分之后，进行精度更大的二次网格划分（如一次划分步长为l，二次划分步长为l/10），GPS点所在网格为中心的周围9个网格包含的路段，即为高权重路段。P2为GPS角度权值，GPS点周围与GPS点行车方向夹角小于90°的路段设置较高角度权值。P3为GPS数量权值，在误差范围内某路段附近的浮动车GPS点数越多，则此路段设置越高数量权值。n为路段误差范围内GPS点的数量。权值的大小关系到最优路径选择的准确程度，因此，通过多次实验仿真确定。

候选路段和路段的权值确定完毕后，完成从起点到终点最优路径的选择。最优路径的确定采用Dijkstra算法[11]。

2.2.5 GPS点匹配

最短路径选择完成后，浮动车行驶经过的路段从而确定。GPS点的匹配采用最简单高效的投影法，将GPS点投影到对应路段上，若垂足在路段内，则垂足为GPS匹配点；若垂足在路段外，则与GPS点距离最近的路段端点作为GPS匹配点。地图匹配步骤完成后，即可进行后续的路径融合、行程时间估计等工作。

基于道路网格和最短路径的快速地图匹配算法通过对道路网格的分块处理，使地图匹配基本不受道路网络规模变化的影响，并且与整个路网相比，匹配候选路段数量非常少，极大程度地提高了匹配处理的实时性。而基于二次网格的划分、路段周围GPS点数量的判断和GPS点方向的判断对候选路段的权重进行修正，并结合Dijkstra算法确定浮动车轨迹的最短路径，又提高了地图匹配的精度。此种算法适合于智能交通系统的实际应用，兼顾实时性和匹配处理精度，可较好地处理海量的浮动车实时数据。

3 仿真结果及分析

3.1 地图匹配算法参数选择

在本文的地图匹配算法中，网格划分参数和权重值的设定对于地图匹配的精度有着至关重要的影响。因此，需采用大量实验来确定和修正权重值的取值。参数大小与算法本身、地图数据和浮动车数据均有关。在本算法中，采用大连市地图数据和大连市交管局浮动车数据进行仿真实验。

经过大量仿真对比，最终确定第一次网格划分的步长为300×300m，第二次网格划分的步长为30×30m，权重值P1、P2、P3的设定如表1、表2、表3所示。

表1 地图匹配算法权重P1取值表

表2 地图匹配算法权重P2 取值表1取值表

表3 地图匹配算法权重P3 取值表1取值表

3.2 实验仿真及结果分析

本文对信息采集和分布式处理系统进行了仿真。GPRS数据中心、中心处理器和分布式处理节点均使用2.93GHz CPU，3G内存计算机，分布式处理节点为3个。各模块之间的通信采用TCP/IP通信，socket编程[12]，利用线程池管理多个线程[13]。经统计，3个匹配节点完成大连市1000辆出租车约130万个GPS点数据需要的时间为1min37s，算法的平均正确匹配率为93.3%。

大连市实时浮动车数据数量庞大，要求地图匹配有较高的实时性，本文设计的分布式处理系统和基于道路网格、最短路径的快速地图匹配算法，能够在很大程度上提高匹配效率，保证系统实时性。同时，地图匹配的准确率能够满足实时系统的要求，适合智能交通系统中对海量数据的实时处理。

4 结论

本文在分析智能交通系统发展趋势的基础上，设计了基于实时浮动车数据的分布式地图匹配系统，并提出了基于道路网格和最短路径的快速地图匹配算法，在保证地图匹配处理精度的情况下较大程度地提高了系统的实时性。经仿真实验可知，系统可高效稳定地运行，满足大连市智能交通系统的处理要求，可应用在实际系统中。

[1]Bishop R.Floating car data projects worldwide:A selective review[C].Inidana,America:ITS America Annual Mtg,2004:192-197.

[2]王笑京，齐彤岩.智能交通系统体系框架原理与应用[M].北京：中国铁道出版社，2004.

[3]朱小东.大规模计算机系统并行仿真技术研究[D].合肥：中国科学技术大学，2013.

[4]沈斌，蒋昌俊，章昭辉，等.一种基于海量GPS数据的分布式地图匹配系统的设计与实现[J].小型微型计算机系统，2007，28（3）：479-481.

[5]Akhter S,Roberts J.Multi-core programming[M].Hills⁃boro:Intel press,2006.

[6]王美玲，程林.浮动车地图匹配算法研究[J].测绘学报，2012，41（1）：133-138.

[7]刘培.基于浮动车数据的地图匹配算法研究[D].北京：北京交通大学，2007.

[8]Quddus M A,Washington Y O,Robert B N.Integrity of map-matching algorithms[J].Transportation Research Part C,2006,14(4):283-302.

[9]Yanagisawa H An offline map matching via integer pro⁃gramming[C].Istanbul,Turkey:Pattern Recognition(ICPR),201020th International Conference on IEEE,2010:4206-4209.

[10]Miwa T,et al.Development of map matching algorithm for low frequency probe data[J].Transportation Research Part C:Emerging Technologies,2012,22(1):132-145.

[11]李元臣，刘维群.基于Dijkstra算法的网络最短路径分析[J].微型计算机应用，2004（5）：295-298.

[12]王静，曲凤娟.基于Socket的多用户并发通信的设计[J].福建电脑，2007（3）：164-165.

[13]罗亚非.基于TCP的socket多线程通信[J].电脑知识与技术，2009（9）：563-566.