导航电子地图自适应更新算法设计与研究

摘 要：本文介绍了一种导航电子地图的自适应动态更新策略的算法设计。首先分析了当前导航系统中电子地图更新方法所存在的局限性，然后提出自适应动态地图更新方法并设计出相关算法，最后再对算法中的一些关键技术问题进行研究与讨论。

关键词：定位导航；电子地图；自适应更新；算法

由于我国经济建设的快速发展，使得城市面貌变化日新月异，汽车的保有量也呈现出快速上升的趋势，这种发展变化在改善了人们生活环境与质量的同时也给人们的出行带来了困难，即无法方便快捷地到达目的地。面对如此问题，地理信息系统（Geographic Information System， 简称GIS）作为获取、存储、分析和管理地理空间数据的重要工具、技术和学科，近年来得到了广泛的关注和迅猛的发展[1]。地理信息系统在汽车导航方面的应用也变得越来越普遍，日常生活中常见的移动电话和PDA等，由于其轻便化，易于携带等特点，成为了导航软件较好的承载平台[2]，越来越多的智能手机也附加了导航功能，手机导航服务逐渐成为广大手机用户的日常必须。在这样的大环境下，与导航相关的附加应用也日益增多，比如可以通过导航定位进行抗灾救生、获知朋友或家人的位置信息[3]以及更符合人体视觉感受的3D导航技术[4]等。

1 当前电子地图更新方式的局限性

当前定位导航系统中电子地图更新的方式主要有离线的版本式更新和在线的增量式更新两种方式。客观来讲，无论是使用这两种更新方式中的哪一种，都存在一个共同的缺陷，即地图的现势性较差。在现实世界中，尤其是在城市市区，时刻存在着大量的新道路开通和旧道路的废止、以及为适应交通流量的增加问题而进行的道路加宽或规制变更等现象。据统计，国内道路的年变化率为30%左右，而对照实际公开出版的各种标示为最新的导航电子地图，内容并不是最新的，一般情况下年度内的变化与调整很难完整地体现出来。其主要有三个方面的原因[5]：

1）更新成本高。对电子地图的实时更新需要对地面道路进行重新测绘并把测绘的结果进行数字化后才能获得最新的电子地图，为了能够及时获得最新的地图，传统的电子地图提供商需要在全国各地设置地图采集点，极大地增加了地图采集成本。

2）数据采集周期长。导航数据提供商一般按照行政区域为单位对道路信息进行数据采集，每隔数年沿着每一条道路重新跑一遍，因此无法及时获取所有道路的实时变化并提供最新的导航数据。为此，地图数据提供商正在考虑采用与往日不同的策略：等级越高的道路采集更新周期越短，如高速（国道）等主要道路的更新周期为7天，而一般道路的更新周期是1年。

3）编译周期长。以最关键的拓扑关系处理为例，当局部一些实体发生变动时，整体拓扑关系将不得不重建，这样牵一发而动全身，在数据维护和结构扩展方面需要更多的工作量。

4）用户体验差。用户无法与服务器进行交互，虽然用户对自己周边的道路非常熟悉，却无法把该信息反馈给地图提供商。比如某地新开通了一条道路，居住在周边的用户必然会知道，然而由于传统的更新机制存在缺陷，在地图被更新之前（该周期往往会很长），外地的用户却无法获得该道路的最新信息。

为保证地图更新的要求，国际导航业界的一些标准组织和企业，在增量更新的研究和开发工作中投入了核心力量。目前比较瞩目的有日本K1wI协会主导的K1w13.0和欧洲主导的PSI（PSF Standardization Initiative）体系[6]。这些增量更新体系的目标是建立一个高效的增量更新机制，实现无缝和快速更新，以满足客户对数据现势性要求，缩短更新周期，降低更新成本[7]。

本文从增量更新模式出发，提出一种自适应的动态地图更新策略。所谓增量是指上次更新后到现在新变化的数据，包括新增的数据，删除的数据和修改的数据（如新建了一条道路，道路扩建，旅店搬迁等）。所谓自适应动态地图更新是指导航软件能够及时适应路况的变化，根据现实路况信息动态的生成相应的电子地图。

2 电子地图动态更新算法设计

本文采取对多个客户端的地图数据进行融合的方式来获得最新的道路信息，客户端用户上传自己的轨迹数据，服务器端则根据所有用户的轨迹数据进行动态判别后实现电子地图的增量更新。为了保持客户端地图每次启动都是最新的，客户端启动时首先需要给服务器端发送一个更新请求，服务器端收到该更新请求后，利用数据增量探测技术[8]针对不同版本的数据文件，记录从旧版本到新版本的变化内容，并把需进行更新的增量内容发给客户端，以保持服务器端与客户端之间地图版本的初始同步。

2.1 客户端更新流程

1）道路更新。客户端主要完成道路信息的采集。地图更新模块持续地检测用户的当前位置，并根据客户端地图来判定当前是否行驶在一条新的道路上，如果是一条新的道路则记录行驶轨迹，行车结束后提示用户有新的轨迹记录，用户可以选择删除或者上传该轨迹到服务器端，流程见图-1。

2）标注更新。用户可以在软件上标注各个道路或者建筑物的名称，当一定数量的用户用同一名称标注同一个地点时，就把该地点加入到服务器端。为了方便用户把名称标注在相近的地方，虽然某个地点还未达到一定的用户数，但在用户标注的时候，软件会显示其它用户已经标注的地点和名称，方便用户判别。

2.2 服务器更新流程

1）道路更新。服务器端接收不同用户上传的道路轨迹，并判断是否已经存在足够数量的相似道路轨迹（这里足够数量是指N1-1条，N1是服务器端设定的变量数值，可以根据导航系统的推广度来确定该值的大小），如果达到一定数量，则把相似轨迹通过使用最小二乘法拟合出一条新路，更新道路数据库，并把更新信息广播给所有的用户。为了防止用户上传已存在的道路（在客户端地图没有及时更新的情况下会出现），在进入地图更新前会先检查用户上传的轨迹是否是某条已经存在的道路。总的流程如图-2所示。

2）标注更新。服务器端接收到不同用户的标注信息之后，判断在同一地点的标注量是否达到预先设定的N2值（这里的同一地点并不是绝对的地理经纬度相等，而是只要在一定范围内都算，比如相差20米，约0.0002°范围内），如果达到一定的数量，则计算所有标注信息点的几何中心，用该几何中心点作为新的标注点的地理经纬度，更新服务器端地图数据，并把该更新消息广播在所有的在线用户，提示用户及时进行更新。具体流程见图-3。

3 系统的其它关键问题

1）判断相似道路。当用户上传一条新轨迹之后，服务器需要判断该轨迹与哪些轨迹是相似的，对于两条不同的轨迹，可以通过求两条轨迹的方差来确定其"相似度"。但这只是解决两条轨迹的比对问题，如何在几万甚至几百万条轨迹中找出当前轨迹的相似轨迹？求两条轨迹的方差是比较昂贵的一种算法，因此为了加快搜索速度，服务器端在保存轨迹数据的同时提取轨迹的起点和终点另存为一张表，当一条新轨迹进来时只需要先用新轨迹的起点和终点进行查找（因为起点和终点都相同的路是比较少的），然后再对起点和终点都相同的道路求方差。

2）防止用户恶意提交。如果对用户提交的轨迹数据不加限制，当用户进行恶意提交时，服务器端数据库将会很快膨胀，并最终崩溃。因此，轨迹数据提交只对注册用户进行开放，并且考虑到道路的更新频率不会很快，每个用户每天只允许提交一次轨迹数据。另外，对于用户提交的无效轨迹，定期进行清理，比如一个轨迹在一个设定的时间周期内（比如一个月）没有其他用户提交相似轨迹，则把该条轨迹删除。

3）判断道路的性质。对于传统的电子地图，都会标注不同的道路性质，比如高速、国道、省道、县道等，对于用户上传的轨迹，如何判断其性质？一种方法是让用户来标注该道路的性质，但是实际上对于不同的道路，用户关注的是在该路上行车的速度能达到多少？而我们的导航系统恰恰拥有所有用户的速度记录，因此，可以采取所有用户的速度求一个平均速度，来对道路进行标注，这样用户可以很直观的获得该道路的路况以及自己能达到的大概速度是多少。我们还可以利用记录的所有用户的行车方向来判断该条道路是否是单行道（对于单行道，所有用户的行车方向是大致相同的）。

4 结束语

由于信息技术的高速发展，GIS在定位导航方面的应用也越来越成熟。最近，随着无线网络的快速发展，定位导航终端逐渐往便携化、智能化方向发展，人们享受其带来的巨大方便的同时也对定位导航系统提出了越来越高的要求，主要体现在精确性与实时性两个方面。本文主要针对导航电子地图的实时性方面做出一定的探讨，设计出电子地图的自适应更新算法，对将来电子地图的更新方式具有一定的指导意义。

参考文献（References）

[1] Darka Mioc. Franc ois Anton， Christopher M Gold. Map updates in a dynamic Voronoi data structure. Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering （ISVD'06）. IEEE 0-7695-2630-6/06

[2] QU Cong-shan， XU Hua-long， TAN Ying. Navigation and Positioning System Based on GPS & CDMA. Xi'an Research Inst

[3] Yuan-Cheng Lai， Yi-Hsuan Yeh， Ching-Neng Lai. A GPS Navigation System with QR Code Decoding and Friend Positioning in Smart Phones. 2010 2nd International Conference on Education Technology and Computer （ICETC）

[4] Chunhe Yu， Danping Zhang. A New 3D Map Reconstruction Based Mobile Robot Navigation. Signal Processing， 2006 8th International Conference on

[5] 黄栋. 导航电子地图增量更新机制与核心技术的研究

[6] Kyoung-Wook Min， Kyoung-Hwan An， Ju-Wan Kim. The Mobile Spatial DBMS for the Partial Map Air Update in the Navigation. 11th International IEEE

[7] Elizabeth R Stuck， Allun Manz， David A. Green， SWia Elgauar. Map updating and path planning for real-time mobile robot navigation. NRC No. 37132， the National Research Council of Canada

[8] 刘勖. 数据增量探测技术在电子地图更新中的应用.电脑与信息技术. 2OO7年8月. 第15卷.第4期