城市汽车导航中一种改进的D－S证据理论地图匹配算法

李 珂，杨 杨，邱雪松

北京邮电大学 网络与交换技术国家重点实验室，北京100876

1 引 言

地图匹配［1］是将定位装置获得的定位轨迹通过一定的算法，与电子地图的道路信息进行匹配，由此确定车辆在地图上的实际位置。它借助GIS电子地图库中的高精度道路信息作为模板来进行模式识别，根据识别的结果来纠正GPS接收数据的定位误差［2］。现有的地图匹配算法的基本思想都是按照一定条件筛选候选道路，再通过具体判断规则得到最佳的匹配道路［3－4］。文献［5］采用基于模糊理论的地图匹配算法，利用车辆行驶信息不同方面权重的设计，对模糊性作出合理的评判，从而得出匹配道路。文献［6］结合卡尔曼滤波及其相关技术，利用其在误差处理方面的优势来改善地图匹配结果的可靠性。文献［7］提出一种基于地图识别和图形识别的方法来研究路径匹配，通过比较车辆行驶时旋转变化度量与地图路径的几何区别实现地图匹配的目的。文献［8］提出一种基于预测的不确定性推理组合地图匹配算法，利用云模型对车辆行驶信息的不确定性进行推理，并利用隐马尔科夫模型预测驾驶员出行路径，结合二者的信息实现地图匹配。这些算法都有一定的匹配精度，但对于道路网较为密集的城市而言，误差率高，匹配精度无法满足车联网的需求。

利用D－S证据理论［9］决策者可以根据不完备、不精确或不完全可靠的证据，通过对一些事件的概率加以约束以建立信任函数，并通过证据融合，挑选出问题的正确答案。文献［10］根据D－S证据理论的基本原理，给出车辆行驶位置和方向信息的基本概率分配函数的设计方法，通过D－S合成公式对二者进行融合，得出融合结果选择匹配道路。相比其他算法，由于增加了逻辑复杂度而具有较高的匹配精度，但仍无法满足城市汽车导航的需求。为获得更高的匹配精度，适应当今复杂的交通网，本文设计了一种改进的D－S证据理论地图匹配算法，对车辆的可达性证据加以考察，并根据城市中不同道路拓扑结构使用最优的可靠性参数值，综合考虑城市路网的复杂性和车辆行驶特性进行地图匹配。

2 基于D－S证据理论的地图匹配算法介绍［11］

根据 D－S证据理论［12－14］，识别框 Θ 描述所有候选道路的集合：Θ＝｛A1，A2，…，An｝，设i＝1，2，…，n，Ai表示车辆在第i号道路上行驶。设j＝1，2，…，n表示第j号证据，用车辆GPS定位点P的位置信息和行驶方向信息作为D－S证据理论中的两个证据，设证据函数为cj，i。当j＝1时，c1，i为位置信息证据函数，令

式中，di表示定位点P到第i号道路的投影距离，投影距离越小，位置信息证据越可信。当j＝2时，令

式中，αi表示正北方向顺时针旋转与第i号道路的夹角；α表示正北方向顺时针旋转与车辆在P点的行驶方向的夹角；βi表示车辆行驶角度的变化值，车辆行驶角度与道路角度差值越小，方向信息证据越可信。考虑到在实际系统中的易实现性，基本概率分配函数构造如下

式中，mj（Ai）表示证据j对命题“道路Ai是匹配道路”的精确信任程度，即m1（Ai）是位置信息证据的基本概率分配函数，m2（Ai）是方向信息证据的基本概率分配函数；mj（Θ）表示当前时刻由于证据的不可靠和不准确而不能确定车辆在哪条道路上；kj表示证据j的可靠性参数，即k1为位置信息证据的可靠性参数，k2为方向信息证据的可靠性参数。

再得出信任函数Bel（Ai）＝m（Ai）和似然函数Pl（Ai）＝m（Ai）＋m（Θ）。其中，信任函数表示该证据下有理由相信Ai为候匹配道路的程度，似然函数表示不反对Ai为匹配道路的程度。

根据 D－S合成公式［12－14］，将得到的位置信息和方向信息在识别框Θ上的基本概率分配函数m1和m2融合为一个m函数，表示命题“道路Ai是匹配道路”的精确信任程度

根据以上条件，可以得出命题“道路Ai是匹配道路”的类概率函数

对于不同的道路Ai，式中的m（Θ）／n值是不变的，考察f（Ai）的值就相当于考察m（Ai）的值，即 max｛m（A1），m（A2），…，m（An）｝，得对应的道路即可判定为车辆当前行驶的道路。

3 算法的改进策略

3.1 城市环境不同路段的可靠性参数取值研究

车辆在城市环境行驶的过程中会遇到平行路段、交叉路口以及立交桥等特殊路段［15］，对于这些路段的处理是目前匹配算法面对的难点。文献［16—17］考虑车辆轨迹曲线与路网路径的曲线相似性等约束条件，通过一系列规则以实现地图匹配。基于D－S证据理论的地图匹配算法则是通过改变证据的可靠性参数值以适应不同的路段，文献［10—14］等对可靠性参数k1和k2的取值固定为0.8，虽都提及两参数对结果影响较大，但并未就此展开研究。

因此，本文遵循可靠性参数选择中适用性和针对性原则，根据实际道路拓扑结构的特点，选取相应的可靠性参数值。由式（3）可知，证据的可靠性参数值越大，表示其证据参考的价值越可靠。首先定义算法的可靠性参数默认值为0.8；取值时考虑车辆定位点所处路网，当某种道路环境下位置或方向信息证据更为可靠时参数值取0.9。分为“位置信息证据较可靠”（k1＝0.9，k2＝0.8）、“方向信息证据较可靠”（k1＝0.8，k2＝0.9）和默认取值（k1＝0.8，k2＝0.8）3种情况。以此思路，本文针对平行路段、交叉路口和立交桥等分口较多的路段进行仿真分析，考察位置信息和方向信息证据的可靠性程度，得出可靠性参数的最优取值。

平行路段是指两条或以上路段平行的道路，车辆的定位数据有可能连续落在n条道路之间。此时n条道路的方向角是相等的，方向信息证据的可靠性相对较弱，应当选取“位置信息证据较可靠”的取值方案。模拟实际环境中平行路段的情况，进行仿真试验，并对结果分析，得出的结果对方案的验证完全统一。选取一仿真实例，如图1所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m（Ai）与k1和k2大小关系的曲线图。可以直观地看出：当k1＞k2时，m（A1）和m（A2）的值相差最大，此时匹配结果的误差范围最大，完成了平行路段时采用“位置信息证据较可靠”的取值方案的验证，即k1＝0.9，k2＝0.8。

图1 城市路网平行路段的可靠性参数分析Fig.1 Reliability parameters of the parallel sections in city road network

当车辆驶入交叉路口时，定位点有可能在各条道路之间，由于道路之间的方向角相差较大，因此相对位置证据而言，方向信息证据的可靠性较强，应当选取“方向信息证据较可靠”的取值方案。通过Java编程模拟实际环境，考察城市不同类型的交叉路口，进行仿真试验，并对结果分析，得出的仿真结果对方案的验证完全统一。选取仿真过程中的一则代表性实例，如图2所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m（Ai）与k1和k2大小关系的曲线图。可以看出：当k1＜k2时，m（A1）和m（A2）的值相差最大，此时匹配结果的误差范围最大，错误率最小；而当k1≥k2时，支持正确结果的证据函数值逐渐下降而支持错误结果的证据逐渐上升，误差范围最小，仿真完成了对交叉路口路段使用“方向信息证据较可靠”的取值方案的验证，即k1＝0.8，k2＝0.9。

图2 城市路网交叉路口路段的可靠性参数分析Fig.2 Reliability parameters of the intersection sections in city road network

当车辆驶入立交桥等分口较多的路段时，是地图匹配中最为复杂的情况，此时GPS定位点有可能在n条较为密集的道路间，可靠性参数细微的变化将直接影响匹配结果。此种情况与交叉路口类似，因此相对位置证据而言，方向信息证据的可靠性较强，应当选取“方向信息证据较可靠”的取值方案。通过Java编程模拟实际环境对立交桥复杂路口进行匹配模拟，仿真结果通过一则实例来说明。如图3所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m（Ai）与k1和k2大小关系的曲线图。可以看出：当k1＜k2时，m（A1）和m（A2）的值相差最大，此时匹配结果的误差范围最大，错误率最小；随着k1的增大和k2的减小，支持正确结果的证据逐渐下降而支持错误结果的证据逐渐上升，最终出现错误的匹配结果，论证了立交桥等分口较多的路段应采用“方向信息证据较可靠”的取值方案，即k1＝0.8，k2＝0.9。

3.2 可达性信息证据的考察

将从GPS等定位设备获取到的车辆定位点分别投影到候选道路上，视做假如车辆行驶在该道路上的位置点，称此投影点为该候选路段的虚拟匹配点。可达性信息是指匹配过程中车辆从上一匹配点到虚拟匹配点的连通性、行驶距离、行驶时间等信息［18］。改进算法考察可达性信息证据，通过计算行驶至各候选道路虚拟匹配点需要的速度，即虚拟速度，与从定位设备获取的车辆实际行驶速度信息比较，以考察虚拟匹配点的可达性信息证据。

图3 城市路网立交桥路段的可靠性参数分析Fig.3 Reliability parameters of the overpass sections in city road network

在传统D－S证据理论的地图匹配算法的基础上，对于式（3），当j＝3时，m3（Ai）是可达性信息证据的基本概率分配函数，令可达性信息证据函数

式中，Di表示车辆从上匹配点到第i号道路的虚拟匹配点的行驶距离；t表示定位设备的定位周期；v表示车辆的瞬时速度；vi表示车辆行驶到第i号道路虚拟速度与实际速度的差值。由于城市路网中的车辆行驶有一定规律性，且在交通规则的约束下行驶速度近似均匀，瞬时刹车的可能性较低，因此本算法中车辆虚拟行驶速度按照匀速计算。在此前提下，此式考察车辆在位置点P到第i号道路的虚拟匹配点的可达性信息的证据强度，车辆虚拟行驶到第i号道路所需的速度与实际行驶速度的差值越小，证据越可信。这样，就得到了位置、方向和连通性3个基本概率分配函数供D－S证据融合以得出最为精确的结果。

接下来探讨 D－S证据融合［19—20］的问题。由文献［19—20］所述，目前D－S证据理论在多证据融合中所需面临的主要两大问题，一是如何将采集到的证据信息转换为基本概率分配函数；二是如何将这些基本概率分配函数按照同一识别框架进行证据融合。文献［19］将多证据融合大致分为集中式证据融合模型和分布式证据融合模型。其中分布式证据融合模型采用递归式D－S证据融合的方式，证据1与证据2融合的结果作为新的证据与证据3进行二次融合，以此类推直至融合所有证据。这种模型适用于事先对各证据的可信程度有所倾向的情况，可以弱化人为证据的可信程度，增强客观证据的可信程度，并且当证据量较少时计算过程更为简便。由于地图匹配算法实际运用中，实际弯曲的道路在电子地图中要用一系列直线段来逼近，并且每个司机的驾车习惯导致经过相同拐角的车行轨迹不同，所以方向信息证据受到人为证据的影响；而从定位设备中获取的可达性信息证据和位置信息证据较为客观，因此改进算法中采用分布式证据融合模型，如图4所示。

图4 改进算法中D－S证据的融合过程Fig.4 Improved fusion process of D－S evidence theory

运用分布式证据融合模型，将式（4）中位置信息和方向信息融合得到的m（Ai）函数作为一个新的基本概率分配函数，再次运用D－S合成公式，与可达性信息证据的基本概率函数m3（Ai）融合为一个新的m函数m′（Ai）

最后，max｛m′（A1），m′（A2），…，m′（An）｝，所对应的道路即为车辆当前行驶的道路。

3.3 改进的D－S证据理论地图匹配算法流程

综合以上讨论，总结得到图5所示的改进的D－S证据理论地图匹配算法流程。

图5 改进的D－S证据理论地图匹配算法流程图Fig.5 Flow chart of the improved map matching algorithm based on D－S evidence theory

4 算法的仿真与结论

为了验证上述改进算法的可行性，将该算法用Java编程实现，集成到一套地图匹配算法测试系统中。该系统可以调用嵌入的地图匹配算法，获取电子地图中的定位数据进行匹配并在地图中显示匹配结果。仿真所用的数据为MapInfo格式北京市2011年电子地图“北四环－安慧桥”路段的数据（1∶50 000，50m），车辆的行驶路段包含直行、平行路段、交叉路口和立交桥等城市复杂道路，可以有效地检验算法的可行性，考察算法的匹配精度与稳定性。通过对基于D－S证据理论的地图匹配算法和改进算法依次进行仿真分析，并将改进算法与其他地图匹配算法的结果数据进行比较，验证算法改进后匹配精度和稳定性的提高。

4.1 算法的仿真实例说明

仿真模拟车辆行驶路线（图6箭头表示），全长约8.7km，车辆行驶路线包括直行路段、平行路段、交叉路口和立交桥等，其中复杂路口41个，平行路段12个。仿真默认车辆匀速行驶，设定行驶速度为30km／h，GPS数据采样周期为5s，对获取到的226个GPS定位点使用传统的基于D－S证据理论的地图匹配算法进行地图匹配，如图6所示。匹配后，车辆行驶226个定位点中有211个点匹配正确，匹配准确率为93.36%。

图6 使用传统的基于D－S证据理论的地图匹配算法匹配后结果Fig.6 Results of the traditional map matching algorithm based on D－S evidence theory

使用改进的算法对GPS定位点进行匹配，如图7所示。其中，在地图匹配算法测试系统中设定可达性信息证据k3＝0.8，车辆在定位点的瞬时行驶速度v＝30km／h。匹配后，226个定位点中有221个点匹配正确，匹配准确率为97.79%，比传统算法有较大的提高。

图7 使用改进的基于D－S证据理论地图匹配算法匹配后结果Fig.7 Results of the improved map matching algorithm based on D－S evidence theory

4.2 仿真结果分析

为了更好地验证本文提出的改进算法的匹配效果，又在地图匹配算法测试系统中分别使用文献［18］提出的基于浮动车数据的地图匹配算法和文献［16］提出的基于GPS轨迹数据的地图匹配算法，对上例进行匹配，并对各算法匹配结果进行分析，如表1所示。

表1 匹配结果比较Tab.1 Comparison of matching results（%）

可以看出，4种匹配算法错误的匹配点都出现在城市的复杂道路段中。仿真过程中的226个GPS定位点，有116个定位点在上述道路网络中。在这116个点中，基于D－S证据理论的地图匹配算法有15个错误匹配点匹配到了错误路线上，错误率为12.93%；而改进后的算法有5个错误匹配点，其余的错误点在第二次D－S证据融合后都得以正确匹配，使错误率降低到了4.31%，并且在整个仿真过程中考虑了实际情况中GPS数据漂移、无效等情况，算法仍然能准确、有效地定位车辆的实际行驶路段。在与基于浮动车数据的地图匹配算法和基于GPS轨迹数据的地图匹配算法比较中，平均匹配率和复杂区域匹配率也都有了一定的提高，可以很好地适用于城市中日益复杂的道路网络环境。

5 结 论

本文针对基于D－S证据理论的地图匹配算法存在的问题，提出了一种适用于城市复杂网络环境的改进算法。改进算法使用研究得出的可靠性参数将第一次证据融合结果精度提高，再与车辆的可达性信息证据进行D－S证据的二次融合，进一步确保了匹配结果的准确性和稳定性。通过仿真实例与其他匹配算法的横向比较，证实了改进算法进一步提高了匹配精度，更好地适用于复杂的城市路网。但算法增加了逻辑复杂度，所以实时性方面有所降低，因此，研究出一种实时性较好且适用各种路网环境的匹配算法将是下一步的完善方向。

［1］ SUN Dihua，WEN Cunting.Research of Map－matching Technology for Moving Fleet［J］.Computer Engineering and Applications，2011，47（22）：149－152.（孙棣华，温存霆.行进车队的地图匹配技术研究［J］.计算机工程与应用，2011，47（22）：149－152.）

［2］ SU Jie，ZHOU Dongfang，YUE Chunsheng.Real－time Mapmatching Algorithm in GPS Navigation System for Vehicles［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：252－256.（苏洁，周东方，岳春生.GPS车辆导航中的实时地图匹配算法［J］.测绘学报，2001，30（3）：252－256.）

［3］ SAAB S S.A Map Matching Approach for Train Positioning Part I：Development and Analysis［J］.IEEE Transactions on Vehicular Technology，2001，49（2）：467－475.

［4］ WANG Z J，YANG Z S.Research on the Map Matching of Typical Region Based on the Topological Analysis［C］∥IEEE Second International Conference on Intelligent Computation Technology and Automation.［S.l.］：IEEE，2009：629－632.

［5］ SU H B，TANG J S，HOU C.A Integrated Map Matching Algorithm Based on Fuzzy Theory for Vehicle Navigation System ［C］∥ Proceedings of IEEE International Conference on Computational Intelligence and Security.［S.l.］：IEEE，2006：916－919.

［6］ GAO Jian.Application of Kalman Filtering in Map－matching［D］.Shandong：Shandong University of Science and Technology，2008.（高建.卡尔曼滤波在地图匹配中的应用［D］.山东：山东科技大学，2008.）

［7］ JOSHI R R.A New Approach to Map Matching for In－vehicle Navigation Systems：The Rotational Variation Metric［C］∥Proceedings of the Conference on Intelligent Transportation Systems.［S.l.］：ITSC，2001：33－38.

［8］ TANG Jinjun，LIU Fang.A Driver Route Prediction Based Mapmatching Algorithm Integrating Uncertain Reasoning［J］.Acta Geodaetica et Cartographica Sinica，2010，39（2）：207－212.（唐进君，刘芳.基于路径预测的不确定性推理组合地图匹配算法［J］.测绘学报，2010，39（2）：207－212.）

［9］ XU Congfu，GENG Weidong，PAN Yunhe.Review of Theory and Applications of Dempster－Shafer Evidential Reasoning Method ［J］. Pattern Recognition and Artificial Intelligence，1999，12（4）：424－430.（徐从富，耿卫东，潘云鹤.Dempster－Shafer证据推理方法理论与应用的综述［J］.模式识别与人工智能，1999，12（4）：424－430.）

［10］ BI Jun，FU Mengyin，ZHANG Yuhe.A Map Matching Algorithm for Vehicle Navigation Systems Based on Dead Reckoning（D－S）Evidence Reasoning［J］.Journal of Beijing Institute of Technology，2002，22（3）：393－396.（毕军，付梦印，张宇河.基于D－S证据推理的车辆导航系统地图匹配算法［J］.北京理工大学学报，2002，22（3）：393－396.）

［11］ SUN Shibo.GPS Vehicle Positioning System Based on GPRS and Evidence Reasoning Map Matching Arithmetic［D］.Harbin：Harbin Institute of Technology，2006.（孙世博.基于GPRS的GPS车辆定位系统及其证据推理地图匹配算法［D］.哈尔滨：哈尔滨工业大学，2006.）

［12］ JUN Bi，LU Wang，YUE Liu.Traffic Data Collection System for Floating Car Based on GPS／GPRS／MM［C］∥Proceedings of Intelligent Systems（GCIS）Second WRI Global Congress.Wuhan：IEEE，2010：66－69.

［13］ YUAN Y M，GUAN W，QIU W.Map Matching of Mobile Probes Based on Handover Location Technology［C］∥Proceedings of IEEE International Conference on Networking，Sensing and Control.Chicago ：IEEE，2010：587－592.

［14］ HU Lin，GU Zhengqi，YANG Yi，et al.Map Matching in Vehicle Navigation Based on Weighted D－S Evidence Theory［J］.China Journal of Highway and Transport，2008，21（3）：116－120.（胡林，谷正气，杨易，黄晶.基于权值D－S证据理论的车辆导航地图匹配［J］.中国公路学报，2008，21（3）：116－120.）

［15］ LI Pei.Research of Map Matching in Vehicle Navigation System［D］.Beijing：Beijing Jiaotong University，2008.（李沛.车辆导航系统中地图匹配的研究［D］.北京：北京交通大学，2008.）

［16］ LI Qingquan，HUANG Lian.A Map Matching Algorithm for GPS Tracking Data［J］.Acta Geodaetica et Cartographica Sinica，2010，39（2）：207－212.（李清泉，黄练.基于GPS轨迹数据的地图匹配算法［J］.测绘学报，2010，39（2）：207－212.）

［17］ TANG Jinjun，CAO Kai.An Adaptive Trajectory Curves Map－matching Algorithm ［J］. Acta Geodaetica et Cartographica Sinica，2008，37（3）：308－315.（唐进君，曹凯.一种自适应轨迹曲线地图匹配算法［J］.测绘学报，2008，37（3）：308－315.）

［18］ WANG Meiling，CHENG Lin.Study on Map－matching Algorithm for Floating Car ［J］.Acta Geodaetica et Cartographica Sinica，2012，41（1）：133－138.（王美玲，程林.浮动车地图匹配算法研究［J］.测绘学报，2012，41（1）：133－138.）

［19］ CHEN X H，YANG Y X.Conflict Problems of D－S Evidence in Multi－sensor Information Fusion Technology ［C］∥Proceedings of IEEE International Conference on Computer Application and System Modeling，2010：314－318.

［20］ TIAN J F，ZHAO W D，DU R Z，et al.D－S Evidence Theory and Its Data Fusion Application in Intrusion Detection［C］∥Proceedings of IEEE International Conference on Parallel and Distributed Computing，Applications and Technologies.［S.l.］：IEEE，2005：115－119.