GPS车辆监控系统道路匹配算法研究与实现＊

吴 昊，刘 岩，吴北平

（1.中国地质大学（武汉）信息工程学院，湖北 武汉430074；2.北京都宜环球科技发展有限公司，北京100081）

0 引 言

目前，随着3S技术和无线通信技术的发展，GPS技术被广泛地应用到交通运输、物流配送、出租车服务、公交车调度、公共卫生应急、消防、安保等领域，为各行各业提供定位、跟踪、导航等服务。GPS车辆监控系统是一种结合了GPS技术、GIS技术和无线通信技术的新一代车辆管理调度系统，具有较好的经济和社会效益。其工作原理是根据接收到的车载GPS定位信息确定监控车辆的实际运行位置，再通过3G无线通信网络将定位信息发送到监控中心，监控中心在后台将信息解析、提取后，在电子地图上实时地绘制、显示出车辆的行驶轨迹，以便监控中心清晰直观地掌握监控车辆的动态位置，实现对车辆的监控[1－2]。但是，由于车载GPS定位信息和导航电子地图本身都存在着一些误差，这些误差将导致监控车辆的实际行驶轨迹偏离电子地图上对应道路的中心线。因此，如果要实现对车辆的监控，首先需解决GPS定位信息与电子地图数据匹配的问题，地图匹配的效果将直接关系到车辆监控效果。利用VB.NET语言设计了一种综合考虑道路拓扑关系和连通性的直接投影匹配算法，纠正了道路匹配中产生的异常问题，提高了GPS车辆监控系统道路匹配的精度。

1 GPS通讯协议解析

1.1 通讯协议语句说明

GPS接收机都遵守由美国国家海洋电子协会NMEA制定的一套通讯协议。该协议采用ASCII码格式，规定了海用和陆用GPS接收机输出的经纬度、时间、卫星状态、接收机状态等信息。协议有三种：0181、0182和0183，其中，NMEA－0183是目前使用最广泛的行业标准[3]。

NMEA－0183协议定义了很多语句，常见的类型有：＄GPGGA、＄GPGSA、＄GPRMC、＄GPGSV以及＄GPGLL等。这些数据主要由帧头、帧尾、帧内数据组成，通过帧头来识别帧内数据的结构，处理数据时可通过“＄”来判断是否为帧头，判定后则通过读取逗号个数进行判断当前处理的是哪一部分的导航参数，并做出相应的提取处理。每帧数据均以回车符（＜CR＞）和换行符（＜LF＞）作为帧尾的结束，每行语句最多包含82个字符。车辆监控系统中通常使用的经纬度、速度、时间等信息均可以从＄GPRMC中提取，该帧的结构如下：

其具体含义如表1所示。

表1 GPRMC数据结构

以＄GPRMC解析算法为例，具体的导航信息提取代码如下：

If nTemp＝5Then

dL＝StrToDeg（sCurstr）／／提取经度信息

If nTemp＝6Then

dB＝StrToDeg（sCurstr）／／提取纬度信息

End If

……

If nTemp＝ 8Then

dSpeed ＝ Format（sCurstr ＊ 1.151 ＊1.609，"0.000"） ／／提取速度信息

End If

If nTemp＝ 9Then

nHeartRate＝sCurstr

dHeading＝sCurstr ／／提取方向信息

End If

1.2 GPS定位信息的接收与提取

基于对GPS定位语句结构的分析，利用VB.NET语言进行基本信息的提取，具体实现方法是利用VS2008中的MSComm控件进行数据解析。由于GPS接收机每一秒钟输出一次数据，因此，只需要触发MSComm控件的Timer事件就可以来接收GPS定位信息。根据GPS接收机传输数据的特点，需要将Timer事件的时间间隔设置为Timer1.Interval＝1 000，即每秒钟接收一次数据，在接收数据的同时，需要将数据保存到数据存储文件中[3]。利用MSComm控件提取GPS数据的算法流程图如图1所示。

图1 GPS定位信息提取流程图

2 道路匹配算法研究

2.1 道路匹配原理

道路匹配的基本思想是把某一时间内车辆的位置或行驶轨迹同系统电子地图中的道路网相比较，按照一定的算法判断、推理，搜索出与行驶轨迹最相近的道路和车辆在道路中的可能位置，并把车辆定位到该道路的中心线上[4]。其基本原理是将接收到的GPS定位数据与系统数据库中的电子地图数据进行比对，在电子地图数据库中搜索出对应的道路线，并将其作为车辆轨迹曲线的待匹配样本。依据一定的搜索法则，在匹配样本附件搜索出满足一定条件的道路，并将搜索出的路线作为最为匹配的模板。根据采用的道路匹配算法法则，依次计算出待匹配样本和所有匹配模板之间的匹配相似度，最终选取匹配相似度最高的道路曲线模本作为该段道路的最终匹配结果，获取车辆正确的行驶轨迹[5]。

2.2 相关算法研究

目前道路匹配的方法有很多种，如直接投影法、相关性法、半确定性法、概率统计法和基于拓扑关系的匹配法等，但是各个匹配算法都有一定的局限性。例如应用较多的直接投影匹配算法，其匹配思想是根据点到线的最短垂直距离进行道路匹配，这种方法计算方法简单，匹配复杂度低，能较好地满足道路匹配实时性的要求，但由于直接投影算法是将最短距离作为匹配因子，从而导致可靠性并不是很高[6－7]。因此，结合道路拓扑关系和连通性的直接投影算法更适合于GPS移动车辆的轨迹匹配。该算法的实现步骤为：

1）读取GPS定位点数据，对每个定位点逐个进行缓冲区分析，获取每个定位点可能的匹配道路集。为每个GPS定位点建立圆形缓冲区，采用分级的方法将缓冲区半径划分成一系列特定的值，如5m、10m、15m等。按照设定的缓冲区半径的大小，逐级建立缓冲区，最后依据道路匹配的约束条件查询对应的缓冲区内的可能匹配道路，组成待匹配道路的集合；

2）对在第一步中确定的待匹配道路的集合进行处理，建立道路的拓扑关系，确定与对应道路具有几何拓扑关系的道路集合，选取两个集合的交集，得到GPS定位点所有的备选道路集合；

3）根据直接投影算法，计算GPS定位点到所有备选道路的最短距离，选取所有最短距离中的最小值对应的道路作为匹配道路。

算法流程图如图2所示。

图2 道路匹配算法流程图

3 道路匹配误差处理

GPS接收机接收到的定位信息精度受外部环境影响较大，例如当卫星信号被遮挡会导致接收数据丢失，遇见高楼阻挡会出现跳点，车辆速度过小会产生静态漂移等问题，这些都会影响GPS定位的精度，甚至出现不能定位的情况。因此，为了提高定位的精度，在进行道路匹配前需对GPS数据进行预处理。

3.1 信号中断处理

当车辆行驶到隧道、高楼间、或者桥下这些特殊环境中时会出现GPS接收机信号暂时中断的现象，这样会使车辆轨迹数据出现跳点，即当前点与上一点的距离超过最大可能运动距离。采用的处理方法是过滤掉跳点，不进行匹配，并利用线性插值预测的方法模拟出下一个GPS定位点，当前后两点的相对距离在允许范围内，没有速度异常时，即停止插值。线性插值模型为

式中：gx（n），gy（n）为预测点的坐标；v（n－1）为车辆的瞬时速度；d（n－1）为前一个点的上一点的行驶方向。线性插值的方法可以较好地解决由信号中断产生的问题，但是由于误差的相关性，容易造成误差的积累。这种方法适用低速行驶的情况，当车辆行驶速度过快时，会使道路匹配变得复杂。

3.2 数据漂移处理

当车辆行驶到道路交叉口或等红灯时，会处于低速行驶或静止状态，此时的GPS定位点不是沿着行驶轨迹缓慢移动或静止不动，而是位于以车辆实际位置为中心的一个较大圆内[8－9]。这将导致GPS定位信号产生漂移，使导航定位出现较大误差。为了保证地图匹配的精度，将发生漂移的定位数据视为无效数据，不进行地图匹配，直到接收到正常的定位点。

4 实验分析

2012年8月在湖北省武汉市进行了部分道路数据采集实验，共采集了鲁磨路、民族大道、珞瑜路和武珞路4条线路的实测数据，并对实测数据进行了数据统计分析，结果如表2所示。

表2 实验道路地图匹配结果

实验结果表明4条实验道路的地图匹配率均大于97%，证明该算法的地图匹配效果较好，道路轨迹生成和道路匹配准确性较高。

在异常情况处理方面，当车辆在行驶过程中遇到了红灯，如图3圆圈部分所示，车辆静止时定位点并不是固定不变，而是在以车辆实际位置为圆心的范围内不断跳动，呈不规则分布，这就是GPS信号漂移现象。经过系统道路匹配算法处理后，生成了连续、光滑的轨迹曲线（深色曲线），与实际道路基本吻合。图4中，车辆经过环岛区域，由于路况较复杂，可以看出车辆实际定位点（浅色部分）呈不规则分布，与道路实际位置存在一定的偏差。在经过系统道路匹配算法处理后，生成的车辆轨迹（深色曲线）与实际路线吻合较好。

图3 道路匹配效果图

图4 环岛路况匹配效果图

由以上两个实验可以明显看出：车辆行驶过程中，由于GPS信号受城市环境的影响，GPS定位点与车辆的实际位置存在着一定的偏差，在遇到特殊路况时，偏差会变大。经过系统道路匹配算法处理后形成的轨迹与车辆实际的道路曲线能很好的保持一致，由图中浅色和深色曲线可以看出。因此，以上两个实验均证实了使用的道路匹配算法在数据处理方面具有很好的效果，保证了GPS车载监控系统定位的准确性。

5 结 论

本文提出的道路匹配算法通过创建缓冲区，利用最短距离分析获取匹配道路的办法进行道路匹配。这种方法不仅综合考虑了道路的拓扑关系和连通性，还增加了道路匹配的约束条件，更有利于匹配结果的优化改进，是一种全局匹配的算法。实验证明：结合道路拓扑关系和连通性的直接投影算法能够对匹配结果进行优化改正，消除信号中断、跳点、漂移等误差带来的不良影响，能够将GPS定位点准确地匹配到电子地图上，具有较好的匹配精度和可靠性。

[1]李东江，李继远，蔡建业，等.基于 GPS／GPRS／GIS的车辆监控系统[J].全球定位系统，2007，33（01）：42－46.

[2]姚新春.GPS车辆导航系统的数据组织[J].现代测绘，2006，29（4）：34－36.

[3]刘岩，汪剑云，吴北平，等.基于 VB.NET的GPS接收机串口通信的实现[J].地理空间信息，2012，4（2）：34－37.

[4]张振辉.车辆导航中地图匹配算法与应用研究[D].郑州：信息工程大学，2006.

[5]夏 州.GPS车辆导航中的数据处理和地图匹配研究[D].北京：北京交通大学，2009.

[6]QUDDUS M A，OCHIENG W Y，NOLAND R B.Current map－matching algorithms for transport applications：State－of－the art and future research directions[J].Transportation Research Part C：Emerging Technologies，2007，15（5）：312－328.

[7]VELAGA N R，QUDDUS M A，BRISTOW A L.Developing an enhanced weight－based topological Map－matching algorithm for intelligent transport systems[J].Transportation Research Part C：Emerging Technologies，2009，17（6）：672－683.

[8]陈永刚，王更生，陈 斌.车载地图匹配技术中GPS定位数据的研究[J].工业控制计算机，2006（1）：61－62.

[9]雷东升，诸彤宇.一种基于实时路况信息的动态路径规划算法[C]／／2008中国信息技术与应用学术论坛论文集（一），2008.