车载GPS定位系统与地图匹配.docx
《车载GPS定位系统与地图匹配.docx》由会员分享，可在线阅读，更多相关《车载GPS定位系统与地图匹配.docx（27页珍藏版）》请在冰点文库上搜索。
车载GPS定位系统与地图匹配
首都师范大学本科毕业论文
车载GPS定位系统与地图匹配
——路径规划
VehicleGPSpositioningsystemandmap-matching
——PathPlanning
论文作者
院系信息工程学院
专业计算机科学与技术
学号
指导老师
完成日期
中文提要
车辆作为人类活动的工具，它在人们的日常生活中起着越来越重要的作用，其发展速度也越来越快。
如何有效地指挥和管理各种车辆调配问题已成为交通运输和安全管理部门面临的一个重要问题。
本设计使用VisualC++开发工具以及GIS控件MapX，开发了GPS路径规划及其图形化显示的模块，在此平台上实现绘制地图以及GPS路径规划等功能。
最短路径分析是地理信息系统（GIS）网络分析的基础，拓扑关系是最短路径分析的关键。
由于MapX不支持空间数据的拓扑结构，因此对于采用MapX进行二次开发的用户来说，最短路径分析就成为一个难点。
为此讨论了基于MapX的Dijkstra算法，并在此基础上实现了基于MapX的局部最短路径搜索方法。
关键词:
GPS定位，MapX，路径规划
Abstract
Vehiclesasatoolofhumanactivitiesinpeople'sdailylifeplayanincreasinglyimportantrole,anditsspeedofdevelopmentisincreasinglyrapid.Howtoeffectivelycommandandmanagementofvehiclesdeploymenthasbecomeamajorproblemfacedwiththetransportandsafetymanagementdepartments.ThisdesignusingVisualC++developmenttoolsandGIScontrolMapXdevelopsaGPSpathplanningandgraphicaldisplaymodules,andachievemappingandGPSrouteplanninginthisplatform.Theshortestpathofgeographicinformationsystem（GIS）isthefoundationofthenetworkanalysis；Thetopologyisthekeyoftheanalysisoftheshortestpath.BecauseMapXdonotsupportthetopologyofspatialdata,theshortestpathanalysishasbecomeadifficultquestionforMapXuserswhodevelopsystemsecondly.ThisdesigndiscussesandrealizesthealgorithmbasedontheMapXDijkstra.
Keywords:
GPSpositioning，MapX，pathplanning
目录
第一章绪论1
1.1研究背景1
1.2研究的意义与主要工作2
第二章GPS系统定位原理与MapX控件4
2.1GPS系统定位原理4
2.2GPS数据传送方式5
2.3NEMA0183数据格式6
2.4MapX简介6
第三章路径规划算法8
3.1路径规划8
3.2最短路径算法8
3.2.1启发式搜索算法8
3.2.2动态规划算法9
3.2.3神经网络算法9
3.3最短路径与Dijkstra算法10
第四章GPS路径规划的设计13
4.1设计内容及功能简介13
4.2程序功能设计15
4.2.1程序主界面设计15
4.2.2地图显示15
4.2.3路径规划19
第五章总结与展望22
致谢23
参考文献24
第一章绪论
1.1研究背景
GPS“全球定位系统”（GlobalPositioningSystem），它通过分布在6个轨道上的24颗GPS卫星以全球覆盖的方式向地面发射测距信号和导航电文，保证在地球上天顶开阔的位置在任何时刻可以接收到4颗以上的GPS卫星信号，并通过导航电文解算出该时刻GPS卫星的空间坐标，它可以提供陆地、海洋、航空等实时性的导航、定位、定时甚至速度测量等功能。
全球定位系统共由三部分构成：
1、地面控制部分，地面控制部分由一个主控站，5个全球监测站和3个地面控制站组成。
监测站均配装有精密的铯钟和能够连续测量到所有可见卫星的接收机。
监测站将取得的卫星观测数据,包括电离层和气象数据,经过初步处理后,传送到主控站。
主控站从各监测站收集跟踪数据,计算出卫星的轨道和时钟参数,然后将结果送到3个地面控制站。
2、空间部分，GPS的空间部分是由24颗工作卫星组成,它位于距地表20200km的上空,均匀分布在6个轨道面上（每个轨道面4颗）,轨道倾角为55°。
此外,还有4颗有源备份卫星在轨运行。
卫星的分布使得在全球任何地方、任何时间都可观测到4颗以上的卫星,并能保持良好定位解算精度的几何图像。
这就提供了在时间上连续的全球导航能力。
3、用户装置部分，用户设备部分即GPS信号接收机。
其主要功能是能够捕获到按一定卫星截止角所选择的待测卫星,并跟踪这些卫星的运行。
当接收机捕获到跟踪的卫星信号后,即可测量出接收天线至卫星的伪距离和距离的变化率,解调出卫星轨道参数等数据。
根据这些数据,接收机中的微处理计算机就可按定位解算方法进行定位计算,计算出用户所在地理位置的经纬度、高度、速度、时间等信息。
全球定位系统的主要特点：
（1）全天候；
（2）全球覆盖；（3）三维定速定时高精度；（4）快速省时高效率：
（5）应用广泛多功能。
全球定位系统的主要用途：
（1）陆地应用，主要包括车辆导航、应急反应、大气物理观测、地球物理资源勘探、工程测量、变形监测、地壳运动监测、市政规划控制等；
（2）海洋应用，包括远洋船最佳航程航线测定、船只实时调度与导航、海洋救援、海洋探宝、水文地质测量以及海洋平台定位、海平面升降监测等；（3）航空航天应用，包括飞机导航、航空遥感姿态控制、低轨卫星定轨、导弹制导、航空救援和载人航天器防护探测等。
GPS的基本定位原理：
卫星不间断地发送自身的星历参数和时间信息，用户接收到这些信息后，经过计算求出接收机的三维位置，三维方向以及运动速度和时间信息。
经过大量的实践证明，GPS定位系统是一个高精度、全天候和全球性的无线电导航、定位和定时的多功能系统。
GPS技术已经发展成为多领域、多模式、多用途、多机型的高新技术国际性产业。
作为先进的测量手段和新的生产力，已经融入了国民经济建设、国防建设和社会发展的各个应用领域。
随着冷战结束和全球经济的蓬勃发展，美国政府宣布2000年至2006期间，在保证美国国家安全不受威胁的前提下，取消SA政策，GPS民用信号精度在全球范围内得到改善，利用C/A码进行单点定位的精度由100米提高到20米，这将进一步推动GPS技术的应用，提高生产力、作业效率、科学水平以及人们的生活质量，刺激GPS市场的增长。
据有关专家预测，在美国，单单是汽车GPS导航系统，2000年后的市场将达到30亿美元，而在我国，汽车导航的市场也将达到50亿元人民币。
可见，GPS技术市场的应用前景非常可观。
GPS在现代军事中的作用，美国提出GPS现代化的基本目的是满足和适应21世纪美国国防现代化发展的需要，这是GPS现代化中第一位的。
具体地说，GPS现代化是为了更好地支持和保障军事行动。
在军事行动的，或有危险的，或有威胁的环境下，要求GPS能对作战成员的战斗力提供更好的支持，对他们的生命提供更安全的保障，能有助于各类武器发挥更有效的作用。
在今后“信息战”“电子战”的背景下，GPS必须要有更好的抗电子干扰能力；要有安全的GPS使用范围，这包括两方面的含义，一是GPS用户能安全使用，二是对不同类型GPS用户要有不同使用范围，要区别对待；GPS用户要有更短的首次初始化时间；和其他军事导航系统和各类武器装备要相互配适。
使用美国GPS精码P（Y）的除美国军方以外，目前美国军方授权所在国家和地区的军方使用的有27个。
其中主要是北约国家的军方，在授权亚太地区军方使用的国家和地区主要有：
韩国、中国台湾、日本、新加坡、沙特阿拉伯、科威特、泰国等。
GPS除了在各类运载器（包括载人和火器）的导航和定位方面发挥了巨大作用外，在对战斗人员的支持、援助中发挥了关键性作用，因此评价极高。
1.2研究的意义与主要工作
GPS全球定位系统是近年来开发的最具有开创意义的高新技术之一，其全球性、全能性、全天候性的导航定位、定时、测速优势必然会在诸多领域中得到越来越广泛的应用。
在发达国家，GPS技术已经开始应用于交通运输和道路工程之中。
目前，GPS技术在我国道路工程和交通管理中的应用还刚刚起步，相信随着我国经济的发展，高等级公路的快速修建和GPS技术应用研究的逐步深入，其在道路工程中的应用也会更加广泛和深入，并发挥更大的作用。
目前用于GIS应用软件开发的模式有很多，其中组件式GIS开发既可以充分利用GIS工具软件对空间数据库的管理分析功能，又可以利用其它可视化开发工具所具有的高效、方便等优点，因此得到了广泛的应用。
在车辆定位与导航系统中，路径规划与导航系统负责完成车辆导航功能，包括提供由出发地到目的地的行车路线规划和旅行途中的动态驾驶引导。
由于MapInfo公司的MapX组件不支持空间数据的拓扑结构，因此对于MapX二次开发的用户来说，最短路径分析成为一个难点。
本文以路径规划，最短路径算法为核心，在分析路径规划系统组成和工作原理基础上，分析了MapX的特点。
详细介绍了路径规划算法的各种优缺点。
着重讨论了道路网的拓扑结构和数据组织形式、空间信息和属性信息的关键以及路径规划的算法实现，采用VC++、MapX控件技术实现了GPS路径规划系统。
第1章为全文的绪论部分，该章首先阐述本论文研究的背景与意义，概述本文主要的工作，描述本文的主要结构与内容安排。
第2章介绍了GPS定位信息接收系统，介绍了GPS通信标准NEMA0183数据格式，并提出了一种在VC下实现对GPS全球定位系统定位信息的接收以及对各定位参数数据的提取方法，最后简单介绍了MapX控件。
第3章详细介绍了GPS路径规划的各种算法，并着重分析了Dijkstra算法在路经规划中的应用与程序的实现。
第4章使用MapX和VC++相结合开发了一个小型的路径规划程序，用高亮线表示行进线路，并使用Dijkstra算法实现最短路径的搜索，进行路径规划。
第5章总结与展望。
第二章GPS系统定位原理与MapX控件
2.1GPS系统定位原理
全球卫星定位系统GPS（GlobalPositioningSystem）是由美国政府所发展，整个系统约分成下列三个部份：
太空卫星部份：
由24颗绕极卫星所组成，分成六个轨道，运行于约20200公里的高空，绕行地球一周约12小时。
每个卫星均持续着发射载有卫星轨道数据及时间的无线电波，提供地球上的各种接收机来应用。
地面管制部份：
这是为了追踪及控制上述卫星运转，所设置的地面管制站，主要工作为负责修正与维护每个卫星能保持正常运转的各项参数数据，以确保每个卫星都能提供正确的信息给使用者接收机来接收。
使用者接收机：
追踪所有的GPS卫星，并实时地计算出接收机所在位置的坐标、移动速度及时间，GARMINGPS即属于此部份。
我们一般民用的GPS功能为使用接收机，其计算原理：
每个太空卫星在运行时，任意时刻都有一个坐标值来代表其所在位置，接收机所在的位置坐标为未知值，而太空卫星的信息在传送过程中，所需耗费的时间，可经由比对卫星时钟与接收机内的时钟计算，将时间差值乘以电波传送速度（一般定为光速），就可计算出太空卫星与使用者接收机间的距离。
GPS的工作概念是基于卫星的距离修正。
用户通过测量到太空各可视卫星的距离来计算他们的当前位置，卫星的左右相当于精确的已知参考点。
每颗GPS卫星时刻发布其位置和时间数据信号，用户接收机可以测量每颗卫星信号到接收机的时间延迟，根据信号传输的速度就可以计算出接收机到不同卫星的距离。
同时收集到至少四颗卫星的数据时就可以解算出三维坐标、速度和时间。
GPS接收机可接收到可用于授时的准确至纳秒级；用于预报未来几个月内卫星所处概略位置的预报星历；用于计算定位时所需卫星坐标的广播星历，精度为几米至几十米；以及GPS系统信息，如卫星状况等。
GPS接收机对码的量测就可得到卫星到接收机的距离，由于含有接收机卫星钟的误差及大气传播误差，故称为伪距。
对0A码测得的伪距称为UA码伪距，精度约为20米左右，对P码测得的伪距称为P码伪距，精度约为2米左右。
GPS接收机对收到的卫星信号，进行解码或采用其它技术，将调制在载波上的信息去掉后，就可以恢复载波。
严格而言，载波相位应被称为载波拍频相位，它是收到的受多普勒频移影响的卫星信号载波相位与接收机本机振荡产生信号相位之差。
一般在接收机钟确定的历元时刻量测，保持对卫星信号的跟踪，就可记录下相位的变化值，但开始观测时的接收机和卫星振荡器的相位初值是不知道的，起始历元的相位整数也是不知道的，即整周模糊度，只能在数据处理中作为参数解算。
相位观测值的精度高至毫米，但前提是解出整周模糊度，因此只有在相对定位、并有一段连续观测值时才能使用相位观测值，而要达到优于米级的定位精度也只能采用相位观测值。
按定位方式，GPS定位分为单点定位和相对定位（差分定位）。
单点定位就是根据一台接收机的观测数据来确定接收机位置的方式，它只能采用伪距观测量，可用于车船等的概略导航定位。
相对定位（差分定位）是根据两台以上接收机的观测数据来确定观测点之间的相对位置的方法，它既可采用伪距观测量也可采用相位观测量，大地测量或工程测量均应采用相位观测值进行相对定位。
在GPS观测量中包含了卫星和接收机的钟差、大气传播延迟、多路径效应等误差，在定位计算时还要受到卫星广播星历误差的影响，在进行相对定位时大部分公共误差被抵消或削弱，因此定位精度将大大提高，双频接收机可以根据两个频率的观测量抵消大气中电离层误差的主要部分，在精度要求高，接收机间距离较远时（大气有明显差别），应选用双频接收机。
在定位观测时，若接收机相对于地球表面运动，则称为动态定位，如用于车船等概略导航定位的精度为30——100米的伪距单点定位，或用于城市车辆导航定位的米级精度的伪距差分定位，或用于测量放样等的厘米级的相位差分定位（RTK），实时差分定位需要数据链将两个或多个站的观测数据实时传输到一起计算。
在定位观测时，若接收机相对于地球表面静止，则称为静态定位，在进行控制网观测时，一般均采用这种方式由几台接收机同时观测，它能最太限度地发挥GPS的定位精度，专用于这种目的的接收机被称为大地型接收机，是接收机中性能最好的一类。
目前，GPS已经能够达到地壳形变观测的精度要求，IGS的常年观测台站已经能构成毫米级的全球坐标框架。
2.2GPS数据传送方式
通常GPS定位信息接收系统主要由GPS接收天线、变频器、信号通道、微处理器、存储器以及电源等部分组成。
由于GPS定位信息内容较少，因此多用RS-232串口将定位信息（NEMA0183语句）从GPS接收机传送到计算机中进行信息提取处理。
计算机与GPS通信进行数据传送采用异步串行传送方式，GPS作为数据终端设备（DTE）与计算机数据通信设备（DCE）之间利用RS-232接口进行数据交换。
GPS接收机的串口配置参数是：
数据传输率4800bit/s，数据位8bit，启动位1bit，停止位1bit，无奇偶校验。
GPS信号输出时间间隔通常在0～2s范围内，若实时性要求不高，每隔1s采样一次就足够。
2.3NEMA0183数据格式
NEMA01832.0协议是为了在不同的GPS导航设备中建立统一的RTCM标准。
此标准定义了通信所需要的传输协议，传输时间，并且指明了通信所需要使用一个4800b/s的串行数据接口，其发送到计算机的数据主要由帧头、帧尾和帧内数据组成，根据数据帧类型的不同，帧头也不相同，如下表所示。
波特率
每秒传输数
语句
最大字符
1200
120
GPGGA
72
2400
240
GPGSA
65
4800
480
GPGSV
210
9600
960
GPRMC
70
在读取输出语句时，数据之间最好用“，”区分，不要按位读取，以保证应用程序的兼容性，有几种GPS数据的含义，本系统主要使用输出GPS定位数据的GPGGA格式，其具体格式为：
1、GPGGA
$GPGGA、<1>、<2>、<3>、<4>、<5>、<6>、<7>、<8>、<9>、M,<11>、<12>*hh
<1>UTC时间，hhmmss格式（定位它的）
<2>纬度ddmmmmmm格式（非0）
<3>纬度方向N或S
<4>经度dddmmmmmm格式（非0）
<5>经度方向E或W
<6>GPS状态批示0—未定位、1—无差分定位信息、2—带差分定位信息
<7>使用卫星号（00~08）
<8>精度百分比
<9>海平面高度
<10>*大地随球面相对海平面的高度
<11>差分GPS信息
<12>差分站ID号0000-123
2.4MapX简介
MapX是一个基于ActiveX（OCX）技术的可编程控件。
MapX为开发人员提供了一个快速、易用、功能强大的地图化组件。
在VB，Delphi，PowerBuilder，VC等可视化开发环境中，只需在设计阶段将MapX控件放入窗体中，并对其进行编程，设置属性或调用方法或相应事件，即可实现数据可视化，专题分析，地理查询，地理编码等丰富的地图信息系统功能。
MapInfoMapX是一个用来做地图化工作的OCX控件，它可以很容易地在您的应用程序中加入强大的制图功能。
它可以把您的数据用地图的形式显示出来，更易于理解。
地图形式可以比简单的图表、图形提供更多的信息，而且描述地图比描述数据表更加简单迅速。
通过MapX，可以完全按照你的意愿在应用程序中加入强大的制图功能。
你可以按点、按专题渲染区域、按饼图或直方图等等来显示数据。
启用MapX的分析功能，可以分组和组织数据、执行搜索或在一个指定的半径、矩形区域或指定的点的周围选择地图图元。
第三章路径规划算法
3.1路径规划
随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广。
路径规划问题作为地理学中一个重要问题，其在GIS中的应用无疑占有重要的地位，路径规划是指,在具有障碍物的环境中,按照一定的评价标准,寻找一条从起始状态到目标状态的最优路径。
下面将介绍一些路径规划的相关算法。
3.2最短路径算法
网络模型中的最短路径问题作为在许多领域中选择最优问题的基础，在交通网络的分析中占有重要地位。
在如何解决这个问题方面各国学者已经做了大量的研究，其中迪杰斯特拉（Dijkstra）算法是最适合拓扑网络中两节点间最短路径搜索的算法之一，后人在此算法的基础上进行了大量的改进算法。
主要用拓扑结构的知识和地理信息的知识来解决问题，在交通网络的路径规划系统中，通常将两者结合起来使用。
在路径规划时，根据用户选用的起始点和终止点，首先根据起始点和终止点的经纬度坐标选取适当的关键节点对，计算从起始点到首关键节点和末关键节点到终止点之间的路径。
这样避免了大范围的搜索，节省了计算时间。
3.2.1启发式搜索算法
何谓启发式搜索算法，在说它之前先提提状态空间搜索。
状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。
通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果。
由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。
问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。
这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序，查找完一个分支，再查找另一个分支，以至找到目标为止。
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。
这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。
他的效率实在太低，甚至不可完成。
在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
这样可以省略大量无畏的搜索路径，提到了效率。
在启发式搜索中，对位置的估价是十分重要的。
采用了不同的估价可以有不同的效果。
先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f（n）=g（n）+h（n）
其中f（n）是节点n的估价函数，g（n）实在状态空间中从初始节点到n节点的实际代价，h（n）是从n到目标节点最佳路径的估计代价。
在这里主要是h（n）体现了搜索的启发信息，因为g（n）是已知的。
说详细点，g（n）代表了搜索的广度的优先趋势。
但是当h（n）>>g（n）时，可以省略g（n），而提高效率。
3.2.2动态规划算法
动态规划算法是求解最优问题的一种高效率的算法。
其使用的原则是优化原则，即整体的最优解可以通过局部的最优解获得。
问题求解的过程可以概括成两句话：
自顶向下的分析，自下向上的计算。
动态规划（dynamicprogramming）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。
利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。
动态规划算法的基本思想是：
将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。
动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：
最优子结构性质和子问题重叠性质。
3.2.3神经网络算法
“神经网络”这个词实际是来自于生物学，而我们所指的神经网络正确的名称应该是“人工神经网络（ANNs）”。
神经网络算法是指模拟生物的神经结构以及其处理信息的方式来进行计算的一种算法。
神经网络在这个领域中有很多优点，使得它越来越流行。
它在类型分类/识别方面非常出色。
神经网络可以处理例外及不正常的输入数据，这对于很多系统都很重要。
网格计算是伴随着互联网技术而迅速发展起来的，专门针对复杂科学计算的新型计算模式。
这种计算模式是利用互联网把分散在不同地理位置的电脑组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算是由成千上万个“节点”组成的“一张网格”，所以这种计
升级会员 