2.1 车辆导航系统功能
车辆导航系统通常需要向用户提供与空间、时间相关的定位信息和引导提示。具体来说，一个车辆导航系统通常需要以下功能：
定位功能，这是车辆导航系统最基本的功能。通常包括显示车辆的经纬度（以及海拔高度），并通过地理信息系统中的道路网信息，利用地图匹配算法在地图道路上显示车辆所在的位置，并且显示相关位置的道路、区域信息。
地图显示功能，用户可以通过调整显示的地图比例尺，来查看不同范围内，不同区域的道路网信息。这种功能实际上是地理信息系统在车辆导航系统上的一个简单任务实现。
兴趣点查询/显示功能，这里所说的兴趣点是指用户感兴趣的、关心的，希望获得其信息的位置对象，例如：旅馆，饭店，医院等。通常有多种查询方式，比如，对指定城市指定区域查询范围内的兴趣点并显示，还有根据输入的兴趣点名称来确定其所在的位置并显示，最常见的是显示车辆当前位置周围的兴趣点，给用户提供以需要的出行信息。
路径规划功能，通过用户输入起始位置和目的地（通常其实位置默认为当前车辆所在位置），由车辆导航系统设计最优路径并输出给用户，这里的最优有多种标准，包括时间最少，距离最短和交通状况最好等。路径规划功能不仅可以结合数据库中存储的道路信息，而且可以实时通过无线通讯获得当前的交通状况。
路径引导，路径引导功能是车辆导航系统区别于简单定位系统和GIS查询系统的最典型区别。它规划好初始位置到目标位置的路径后，在每一个路口实时提醒车辆驾驶人员接下来的行驶道路选择。以及当前距离目的地的距离和需要的时间估算等信息。
2.2车辆导航系统的组成
一个现代定位及导航系统通常由图2.1 所示的部分或所有模块来组成；换句话说，复杂的定位和导航系统需由代表不同功能和多种技术的模块来组成。
图2.1导航系统组成模块
现在，将每个独立模块的功能总结如下：
定位模块融合不同传感器的输出，利用接收到的无线电信号自动地确定车辆或机动装置的位置，辨别正在行驶的公路和所要接近的每个交叉路口。典型的独立定位技术是推算定位，而典型的无线电信号定位技术是使用全球定位系统（GPS）接收机。为了融合不同传感器的输出，现在研制出许多不同的融合方法。
数字地图数据库也就是交通矢量地图，包含预先定义好存储格式的数字地图信息，这样的存储格式有助于计算机处理与地图有关的信息，如辨别场所、公路等级、交通规则和旅行信息等等。因为地图是用来表示地球表面的几何形状的，为了开发和利用地图的各种功能，必须清楚不同地图数据库所用的相对参考坐标系。为了缓解处理不同数字地图所遇到的麻烦，人们试图制定统一的标准以引导研制和应用。
地图匹配是把测量到的或从定位模块获取到的位置（轨迹）与地图数据库所提供的基于地图的位置（路径）进行匹配来确定车辆在地图上位置的一种方法。如果数据库相当准确，这一技术能改进定位模块的精确度。对于市区来说，数字地图数据库的精度应保持在15m以内。地图匹配部分算法的改进正是这篇论文的研究对象。
路径规划是帮助司机在行驶前或运行中规划路线的过程，这个过程是根据地图数据库模块所提供的地图，如果可能的话再加上从无线通信网络收到的实时交通信息来实现的。通常采用技术是找到最小旅行代价路线，旅行代价可以是时间、距离或选择路线的复杂度等等。
路径引导是指挥司机沿着由路径规划模块计算出的路线行驶的过程。为了确定车辆当前的位置和产生适当的实时引导指令（通常是转弯接着转弯或一次转向），需要借助地图数据库和精确的定位。
人机接口允许用户与定位和导航计算机及装置进行人机交互。地图显示、路径规划、路径引导和其他活动的各种不同要求通过这个人机接口送到计算机中，然后再通过这个接口模块反馈给用户。
无线通信模块进一步改进系统的性能和增加系统的功能。通过一个或多个不同种的通信网络，车辆和它的使用者或交通管理系统能够接收实时交通信息或报告，这样就促使了车载系统或整个公路网络工作的更加安全和有效。此外，一个基于无线信息和通信技术的中央遥控设施甚至能通过它的系统去帮助车辆定位和导航。
定位模块和数字地图数据库模块是其中最基本最重要的两个模块，而地图匹配算法起着连接这两部分的作用。
2.3 车辆定位系统
定位模块是车辆定位与导航系统的重要组成部分。为了使用户获知车辆位置或者向用户提供操纵指示，必须精确确定车辆的位置。对于任何性能良好的车辆定位与导航系统来说，精确、可靠的车辆定位是必要的先决条件。在车辆导航系统中，车辆定位子系统负责实现定位模块的功能，为导航系统提供车辆的实时位置以及方向、速度等运动状态信息。
常用的定位技术有三种：独立定位技术、卫星定位技术和地面无线电定位技术[3]。推算定位（Dead reckoning）是典型的独立定位技术。卫星定位技术是把卫星定位接收器安装在车辆上来获得车辆位置。推算定位和GPS技术已广泛应用于车辆上。下面我们具体介绍各种定位技术以及其特点。
航位推算系统是根据已知位置，利用车辆运行的方向，速度，时间和距离信息来估测车辆当前位置。有一系列的传感器种类可以用来获得对象的方向信息（如陀螺仪，罗盘）和行驶距离（如里程表和加速度仪）。使用航位推测来获得位置的准确性很大程度上决定于这些传感器的性能。通常使用的这些航位推测传感器会有刻度误差（老化和制造工艺原因）和非线性误差。由于这些误差的存在，航位推测系统的位置、速度和方向信息的误差会随之时间的增加而积累。用户设备由于购买、操作和维护费用的存在，价格普遍教高。另外，航位推测系统的耗电量虽然会随着体积和重量的减小而缩减，但仍然比GPS接收器的耗电量高。综合以上因素，航位推测定位系统并不适合单独作为当前车辆导航系统的定位设备。
地面基站无线电定位系统，是通过一个信号塔向外广播其自身位置，临近的接收器获得信号后，利用接收到的信号来确定自身的位置。虽然该系统的误差不会随时间累计，但是系统的使用受到地域和信号覆盖面积的限制，而且价格比较高，当前使用的也很少。
卫星导航系统采用导航卫星对地面、海洋、空中和空间用户进行导航定位。利用太阳、月球和其他自然天体导航已有数千年历史，由人造天体导航的设想虽然早在19世纪后半期就有人提出，但直到20世纪60年代才开始实现。1964年美国建成“子午仪”卫星导航系统，并交付海军使用，1967年开始民用。1973年又开始研制“导航星”全球定位系统。苏联也建立了类似的卫星导航系统。中国、法国、日本也开展了卫星导航的研究和试验工作。卫星导航综合了传统导航系统的优点，真正实现了各种天气条件下全球高精度被动式导航定位。特别是时间测距卫星导航系统，不但能提供全球和近地空间连续立体覆盖、高精度三维定位和测速，而且抗干扰能力强。卫星导航系统由导航卫星、地面台站和用户定位设备三个部分组成。导航卫星是卫星导航系统的空间部分，由多颗导航卫星构成空间导航网。地面台站跟踪、测量和预报卫星轨道并对卫星上设备工作进行控制管理，通常包括跟踪站、遥测站、计算中心、注入站及时间统一系统等部分。跟踪站用于跟踪和测量卫星的位置坐标。遥测站接收卫星发来的遥测数据，以供地面监视和分析卫星上设备的工作情况。计算中心根据这些信息计算卫星的轨道，预报下一段时间内的轨道参数，确定需要传输给卫星的导航信息，并由注入站向卫星发送。用户定位设备：通常由接收机、定时器、数据预处理器、计算机和显示器等组成。它接收卫星发来的微弱信号，从中解调并译出卫星轨道参数和定时信息等，同时测出导航参数（距离、距离差和距离变化率等），再由计算机算出用户的位置坐标（二维坐标或三维坐标）和速度矢量分量。用户定位设备分为船载、机载、车载和单人背负等多种型式。
目前正在运行的全球卫星定位系统有美国的GPS系统和俄罗斯的GLONASS系统。欧盟1999年初正式推出“伽利略”计划，部署新一代定位卫星。该方案由27颗运行卫星和3颗预备卫星组成，可以覆盖全球，位置精度达几米，亦可与美国的GPS系统兼容，总投资为35亿欧元。该计划预计于2010年投入运行。另外，中国还独立研制了一个区域性的卫星定位系统——北斗导航系统。该系统的复盖范围限于中国及周边地区，不能在全球范围提供服务，主要用于军事用途。
GPS全称是Global Positioning System, 是美国国防部研制的一种全天候的，空间基准的导航系统，可满足位于全球任何地方或近地空间的用户连续地精确地确定三维位置和三维运动及时间的需要。它是一个中距离圆型轨道卫星导航系统。它可以为地球表面绝大部分地区（98%）提供准确的定位、测速和高精度的时间标准。该系统的组成包括太空中的24颗GPS卫星；地面上的1个主控站、3个数据注入站和5个监测站及作为用户端的GPS接收机。最少只需其中4颗卫星，就能迅速确定用户端在地球上所处的位置及海拔高度；所能收联接到的卫星数越多，解码出来的位置就越精确。该系统是由美国政府于20世纪70年代开始进行研制于1994年全面建成。使用者只需拥有GPS接收机，无需另外付费。GPS信号分为民用的标准定位服务（sps, standard positioning service)和军规的精密定位服务（pss, precisepositioning service)两类。民用讯号中加有误差（SA），其最终定位精确度大概在100米左右；军规的精度在十米以下。2000年以后，美国政府决定取消对民用信号所加的误差(SA)。因此，现在民用GPS也可以达到十米左右的定位精度。GPS系统拥有如下多种优点：全天候，不受任何天气的影响；全球覆盖（高达98%）； 三维定速定时高精度；快速、省时、高效率；应用广泛、多功能；可移动定位；不同于双星定位系统，使用过程中接收机不需要发出任何信号增加了隐蔽性，提高了其军事应用效能。
GPS导航系统的基本原理是测量出已知位置的卫星到用户接收机之间的距离，然后综合多颗卫星的数据就可知道接收机的具体位置。要达到这一目的，卫星的位置可以根据星载时钟所记录的时间在卫星星历中查出。而用户到卫星的距离则通过纪录卫星信号传播到用户所经历的时间，再将其乘以光速得到。由于大气层电离层的干扰，实际应用中这一距离并不是用户与卫星之间的真实距离，而是伪距（PR）。
当GPS卫星正常工作时，会不断地用1和0二进制码元组成的伪随机码（简称伪码）发射导航电文。GPS系统使用的伪码一共有两种，分别是民用的C/A码和军用的P(Y)码。C/A码频率1.023MHz,重复周期一毫秒，码间距1微秒，相当于300m；P码频率10.23MHz，重复周期266.4天，码间距0.1微秒，相当于30m。而
Y码是在P码的基础上形成的，保密性能更佳。导航电文包括卫星星历、工作状况、时钟改正、电离层时延修正、大气折射修正等信息。它是从卫星信号中解调制出来，以50b/s调制在载频上发射的。导航电文每个主帧中包含5个子帧每帧长6s。前三帧各10个字码；每三十秒重复一次，每小时更新一次。后两帧共15000b。导航电文中的内容主要有遥测码、转换码、第1、2、3数据块，其中最重要的则为星历数据。当用户接受到导航电文时，提取出卫星时间并将其与自己的时钟做对比便可得知卫星与用户的距离，再利用导航电文中的卫星星历数据推算出卫星发射电文时所处位置，用户在WGS-84大地坐标系中的位置速度等信息便可得知。可见GPS导航系统卫星部分的作用就是不断地发射导航电文。然而，由于用户接受机使用的时钟与卫星星载时钟不可能总是同步，所以除了用户的三维坐标x、y、z外，还要引进一个?t即卫星与接收机之间的时间差作为未知数，然后用4个方程将这4个未知数解出来。所以如果想知道接收机所处的位置，至少要能接收到4个卫星的信号。
由于GPS定位的稳定性好，精度相对较高（尤其是S/A人为干扰取消以后），GPS接收机价格低廉。通常的车载定位系统都以GPS定位为主。尽管GPS在车载导航系统中应用非常广泛，由于系统误差和随机误差的影响[3]，通过GPS接收器获得的车辆位置与车辆的实际位置还是有几十米的误差。当需要较高定位精
度时可以采用GPS结合其他定位方法的方式进行定位。最典型的是通过卡尔曼滤波器结合GPS定位系统与航位推测系统组成组合导航系统。不过，结合定位设备的价格因素和使用的精度要求，民用车载导航系统一般是采用单独的GPS接收设备进行车辆定位。这也是当前应用最广的车辆地位方式。通过独立车载
GPS接收器获得车辆位置的导航系统简称为GPS车辆导航系统。
2.4 数字地图数据库
数字地图数据库是地理信息系统的一种。地理信息系统(Geographicinformation system，简称GIS)系统，也称作地理资讯系统。 GIS是一门综合性学科，已经广泛的应用在不同的领域.，是用于输入、存储、查询、分析和显示地理数据的计算机系统。一个地理信息系统(GIS) 是一种具有信息系统空间专业形式的
数据管理系统。在严格的意义上, 这是一个具有集中, 存储, 操作, 和显示地理参考信息的计算机系统。例如，根据在数据库中的位置对数据进行识别。地理信息系统技术能够应用于科学调查,资源管理, 财产管理、发展规划、绘图和路线规划。例如, 一个.. GIS系统能使应急计划者在自然灾害的情况下较易地计算出应急反应时间, 或利用.. GIS系统来发现那些需要保护不受污染的湿地。
地理信息系统具有以下三个方面的特征：
①具有采集、管理、分析和输出多种地理空间信息的能力，具有空间性和动态性；
②以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间分析、多要素综合分析和动态预测能力，产生高层次的地理信息；
③由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规的或专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成的任务。
在交通导航应用中使用的地理信息系统主要是数字地图数据库。我们所说的GIS往往是一个比较庞大的系统，而且包含了很多各类数据管理、决策的模块，它是一种针对性比较强的系统，对于不同的用户，往往对数据有不同的操作、管理、决策。但是它毕竟是一个以地理空间分布数据为基础的系统，所以有一个因素不能少，那就是电子地图，它为系统提供最基本的地理信息。
电子地图按照其数据结构的不同，又主要分为矢量电子地图和栅格电子地图两种，栅格电子地图也就是我们平时常见的位图。矢量地图是指对点阵数据数字地图图像进行跟踪识别得到的矢量数据以后的地图，然后对地图中线状地物如河流、等高线、铁路、公路、等进行恢复，恢复的结果就是一幅矢量地图。在矢量地图上可以方便的进行放大和缩小变换。
电子地图的这两种实现，各有优缺点。栅格电子地图，主要是生成比较方便，图像比较细致，和人们日常使用的地图类似，容易被用户接受，但是，栅格电子地图数据量比较大，存储不方便，放大过程中会产生失真，数据不是很准确，很难进行全局或者局部校正，更新起来也比较费事。矢量电子地图生成相对费事，但是数据经过压缩，数据量小，地图可以随意缩放，缩放过程中不会失真，可以进行全局或者局部校正，更新起来也很方便。例如成都市地图，按照比例尺.. 1：200000（约），转化为.. 24位位图，大约.. 15M，而我们生成的矢量地图数据库，只有..137K，近.. 3000条道路（矢量边）的矢量文件大小只有约.. 61K。可见矢量电子地图的优越性。
绝大多数.. GIS系统中使用的地图是以矢量地图作为其表现形式的。如何来组 织一份矢量地图呢？数据是矢量地图的核心，电子地图可以看作由点、线、面这三种几何对象以及它们的属性数据构成的数据的集合，所以我们引入了地图矢量库和地图数据库这两个概念 [4]。矢量库是一组图形描述数据，保存了地图的几何数据；数据库则是一组描述数据，保存地图各种几何对象的属性数据，二者之间通过地物对象的序号建立索引关系，如图 2.2。
一副地图可以看成是由点、线、面三种几何图形构成的。点指的是单位之类的地物实体，线则是道路、铁路之类的实体，而区划这类的实体就可以用面来表征。依照传统的习惯，把点、线、面这三类地物按照从上到下的顺序排列。生成、编辑电子地图的过程就是生成、编辑地图矢量库和数据库的过程，下面我们来详细介绍一下这两个最重要的库。
图 2.2矢量地图的组成
2.4.1 地图矢量库
矢量地图的最大特征就是用一系列的节点来表示整个道路网和其他相关的地理对象 [5]。节点之间的拓扑连接信息是节点构成道路和其他对象的基础。若干组节点构成弧段，若干组弧段构成道路[6]。矢量地图的基本地理结构如图2.3所示对矢量道路有如下基本定义：
图2.3矢量地图道路拓扑结构定义
1) 节点集合NR
(道路)节点集合NR由线实体上所有的N个节点ni = [xni, yni]T 构成：
NR = {ni | i = 1,2,..., N} (1)
式中节点ni在矢量交通地图上代表的实际经度与纬度分别记为xni与yni。
2) 弧段集合SR
弧段集合SR由矢量地图上所有的nS 条弧段Sk构成：
SR = {Sk | k = 1,2,..., nS } (2)
第k条弧段Sk 由组成它的所有nk 个节点nik 顺序构成：
上式并隐含节点nik 之间的顺次连接关系。弧段与其它弧段的相交只可能发生在该弧段的端点处，即n1k 或 
。表示弧段端点的节点，称为大节点。弧段所包含的除端点之外的节点称为小节点。大节点实际上就是道路交叉路口的中心点(除了地图边缘的道路终端点)，车辆从一条弧段转向另一条弧段必经过大节点，并且这个大节点一定既是本条弧段的端点同时又是另一条弧段的端点。基于弧段端点在实时地图匹配中的特殊位置，本文对弧段端点例如nj将特别地记为
。
3)道路
Rk 。道路是若干条弧的集合。实时地图行驶道路匹配实际上是对组成道路的弧段的匹配。
2.4.2地图数据库
地图数据库中包含了各种地物的属性数据。
对于面地物，需要知道的属性有：类型、位置、形状、名称、颜色等；
对于点地物，需要知道的属性有：类型、位置、名称、显示图标、显示级别 等；
对于线地物，需要知道的属性有：类型、位置、形状、名称、颜色、显示宽度、显示级别等；
上面提到的各种地物的属性数据中都有一项——类型，也就是它所属的组（Group）。组，定义出了某一批地物的缺省属性，是一些具有相同或相近属性的同类地物的集合。
