（通信与信息系统专业论文）基于agps混合定位的车载定位导航系统路径规划研究与应用实现.pdf

北京邮电大学硕士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：垒鎏纽 日期： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名：皇望筮 日期： 导师签名：日期： 北京邮电大学硕士学位论文 基于a - g p s 混合定位的车载定位导航系统 路径规划研究与应用实现 摘要 随着社会经济的发展，城市化进程的加快以及机动车数量的大幅 增长，交通问题在社会生活中日益突出，智能交通系统越来越受到人 们的重视。车载定位导航系统是智能交通系统的一个重要组成部分， 它综合应用定位技术、地理信息系统( g i s ) 技术、计算机技术、通 信技术等现代科技，有助于实现交通流量整个交通路网上的合理分 配，使交通路网能够得到最合理、有效的利用。 目前我国市场上的车载定位导航系统，大多为自主式系统，而本 文所研究的系统是引入服务器端的、中心式的定位导航系统。本文主 要研究车载定位导航系统的导航部分，即对车辆的路径规划的研究和 实现。与一般的路径规划研究不同的是，这里研究的路径规划的涵义 广泛，不但包括一般意义上的路径规划，还包括规划之前对车辆当前 位置的道路匹配，以及对整个路网的道路交通状态的判断和实时更新 部分。 通过对常见的一些地理信息系统( g i s ) 开发软件、地图格式的 比较，本文选取了m a p i n f o 格式的电子地图，通过将地图数据导出为 可与外界交换数据的m i f 格式，来选取本文所需的数据信息，批量存 入数据库作为路网数据源。 北京邮电大学硕士学位论文 首先，本文介绍了项目研究的车载定位导航系统的组成架构、各 部分功能，并详细说明了交通信息处理与导航服务器在系统中的作 用、与其它模块的通信方式以及工作流程。然后，文章具体介绍了交 通信息处理与导航服务器数据库表的设计以及算法的实现，包括道路 匹配模块、道路状态判断模块以及路径规划模块的研究和实现。其中， 不需要安装硬件设备，而由本项目所研发的导航终端作为探测车提供 交通信息来判断道路状态，是本文的一个优点。 实验结果表明，本课题中实现的交通信息处理与导航服务器，能 够满足车载定位导航系统的实时性、有效性的要求，且能很好地融合 到整个项目产品中，具有一定实用性。 关键词：车载定位导航系统路径规划道路匹配道路状态 北京邮电大学硕士学位论文 a p p u c a n o nr e s e a r c ho nb 气：mp l a n n i n g i nv e h i c l el o c a n 0 na n dn a v i g a n 0 ns y s t e m b a s e d0 na g p sh y b r i dp o s i t l 0 n i n g a b s t r a c t w i t ht h ea c c e l e r a t i o no fu r b a n i z a t i o np r o c e s s ，t r a f f i cp r o b l e m sa r e b e c o m i n gi n c r e a s i n g l yp r o m i n e n ti no u rw o r ka n dl i f e ，m o r ea n dm o r e a t t e n t i o n sa r ep a i dt oi n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s v e h i c l el o c a t i o n a n dn a v i g a t i o ns y s t e mi sa ni m p o r t a n tc o m p o n e n to fi t s ，m a n ya d v a n c e d t e c h n o l o g i e s a r e a p p l i e d i n i t ，s u c ha sp o s i t i o n i n gt e c h n o l o g y , g i s t e c h n o l o g y , c o m p u t e rt e c h n o l o g ya n d c o m m u n i c a t i o nt e c h n o l o g y v e h i c l e l o c a t i o na n dn a v i g a t i o ns y s t e mi sab e n e f i to fb e t t e ra l l o c a t i o no ft r a f f i c r e s o u r c e sa n du s eo fr o a d s c u r r e n t l y , m o s to ft h ev e h i c l el o c a t i o na n dn a v i g a t i o ns y s t e m sa r e a u t o n o m o u s ，i nt h i sp a p e r , ac e n t r a lv e h i c l el o c a t i o na n dn a v i g a t i o n s y s t e mw h i c hb r i n g s i nas e r v e rs i d ei st a l k e da b o u t t h i sp a p e r r e s e a r c h e do nt h en a v i g a t i o np a r to ft h i ss y s t e m ，n a m e l y , t h ep a t h p l a n n i n gp a r t c o m p a r e d t og e n e r a lp a t hp l a n n i n gm e t h o d ，t h em e a n i n go f p a t hp l a n n i n gh e r eh a saw i d er a n g e ，i n c l u d e sn o to n l yg e n e r f ls e n s eo f p a t hp l a n n i n g ，b u ta l s ot h er o a dm a t c h i n go ft e r m i n a l sc u r r e n tl o c a t i o n a n dt h ed e t e r m i n a t i o no fr o a dt r a f f i cs t a t u s i i i 北京邮电大学硕士学位论文 i nt h i sp a p e r e l e c t r o n i cm a po fm a p l n f of o r m a ti su s e da st h es o u r c e d a t a f i r s t l y , t h i sp a p e r i n t r o d u c e st h e s y s t e m a r c h i t e c t u r ea n d f u n c t i o n a l i t i e so fa l lp a n s i ta l s od e s c r i b e st h en a v i g a t i o ns e r v e ri ni t s f u n c t i o n a l i t y , c o m m u n i c a t i o nm e t h o dw i t ho t h e rm o d u l e s ，a n di t so w n w o r k f l o w t h e n ，t h ed a t a b a s ed e s i g na n da l g o r i t h mi m p l e m e n t a t i o na r e d e t a i l e dd e s c r i b e d ，i n c l u d i n gr e s e a r c ha n di m p l e m e n t a t i o no nt h er o a d m a t c h i n gm o d u l e ，t h er o a ds t a t u sd e t e r m i n a t i o nm o d u l ea n dt h ep a t h p l a n n i n gm o d u l e i nt h i sp a p e r , o u rt e r m i n a li su s e da st h ep r o b ec a rt o p r o v i d ei n f o r m a t i o nf o rt h er o a ds t a t u sd e t e r m i n a t i o n ，t h a t sag o o dp o i n t i nt h i sp a p e r t h er e s u l t ss h o wt h a t ，t h en a v i g a t i o ns e r v e ri nt h i sp a p e rc a nm e e tt h e r e q u i r e m e n t so fv e h i c l el o c a t i o na n dn a v i g a t i o ns y s t e m ，a n dc a nw o r k w e l lw i t ht h eo t h e rm o d u l e si nt h es y s t e m t h i sp a p e rh a sap r a c t i c a l i t y k e yw o r d s ：v e h i c l el o c a t i o na n dn a v i g a t i o ns y s t e m ；p a t hp l a n n i n g ； r o a dm a t c h i n g ；r o a ds t a t u s i v 北京邮电大学硕士学位论文 目录 第一章引言。1 1 1研究背景1 1 2 车载定位导航系统2 1 2 1 车载定位导航系统组成2 1 2 2 车载定位导航系统研究现状4 1 2 3 车载定位导航系统的关键技术6 1 3 路径规划研究综述7 1 4本课题研究目的及意义。8 1 5 主要内容与结构安排9 1 5 1主要内容9 1 5 2结构安排1 0 1 6 本章小结1 1 第二章项目介绍与课题设计1 2 2 1项目研究内容1 2 2 1 1a - g p s 定位技术概述1 3 2 1 2 系统架构1 4 2 2 课题研究内容1 7 2 3 本章小结2 1 第三章道路匹配模块的实现2 2 3 1 道路匹配模块的总体设计2 2 3 1 1 道路匹配模块的概念2 2 3 1 2道路匹配模块的原理2 3 3 2道路匹配模块的数据库设计2 4 3 3道路匹配模块的实现2 6 3 4道路匹配模块存在的问题。2 8 3 5本章小结2 9 第四章道路状态判断模块的实现3 0 4 1道路状态判断模块总体设计3 0 4 1 1基于探测车的移动交通流检测技术3 0 4 1 2多级模糊识别方法3 1 4 1 3 道路状态判断模块原理3 2 4 2 道路状态判断模块的数据库表设计3 5 4 3 道路状态判断模块的实现3 7 4 4 道路状态判断模块存在的问题3 8 4 5 本章小结3 8 v 北京邮电大学硕士学位论文 第五章路径规划模块的实理4 0 5 1 路径规划算法研究。4 0 5 1 1 路径规划4 0 5 1 2 常用路径规划算法4 1 5 1 3 路径规划模块原理4 3 5 2 路径规划算法的数据库设计4 4 5 3 路径规划算法的实现4 5 5 3 1 路网的存储结构4 5 5 3 2 路径规划的实现。4 8 5 4 路径规划模块存在的问题5 1 5 5 本章小结5 1 第六章总结与展望5 2 6 1 总2 2 ；5 2 6 2 展望。5 3 参考文献5 4 缩略语。5 6 致谢5 7 攻读学位期间发表的学术论文5 8 v i 北京邮电大学硕士学位论文 1 1研究背景 第一章引言 随着我国城市的经济贸易和社会活动日益繁忙，交通事业的发展关系到我国 社会主义现代化建设，对人们的日常生活影响巨大。车辆的使用提高了人们的生 活质量，给人们的生活和工作带来了很大的方便。然而，随着经济的发展、城市 化进程的推动以及车辆数目的大幅度增长，交通问题在社会生活中日益突出起 来。当前交通问题是一个全世界都面临的问题，交通拥堵、交通事故等社会问题 严重影响到社会正常秩序，无论是发达国家，还是发展中国家，都毫不例外地承 受着不断加剧的交通问题的困扰。解决交通问题的传统办法是修建道路，但修建 道路需要投入高昂的成本，而且交通系统是一个巨大复杂的系统，仅通过扩建道 路这种粗放式手段来考虑提高路网通行能力，是无法从根本上解决交通问题的。 为了缓解交通问题，从上世纪6 0 年代起，发达国家开始着手研究解决交通 问题的可行办法。制定交通规划、使用信号灯等措施缓解了交通问题，但仍然无 法满足日益增长的车辆需要。交通问题是一个系统问题，只能从系统观点整体上 综合考虑解决，单从道路方面考虑解决问题的效果有限。在此背景下，把交通基 础设施，交通运载工具和交通参与者综合起来系统考虑，充分利用高新技术解决 交通问题的思想便自然的产生，这就是智能交通系统( i t s ：i n t e l l i g e n t t r a n s p o r t s y s t e m ) 【1 l 。它是一个综合交通管理系统，综合考虑车辆和道路等因素的影响， 用科学管理和现代技术手段系统解决交通问题。智能交通系统为解决道路交通问 题提供了新的思路，不仅要改善交通基础设施，而且要采用先进的电子、通信、 计算机和系统工程等高科技手段来对交通信息网络以及车辆进行更合理、有效的 管理和控制，这样才能更大限度发挥交通系统的作用。 随着计算机、通信、自动控制和传感器等技术的发展，智能交通系统先后在 经济发达国家首先研究并投入使用，并且逐渐向着更高效、更智能的方向发展。 这个系统将现代信息技术、通讯技术、管理理论综合应用于交通系统，将卫星和 地面监控中心，交通路网中的检测设备、车载导航计算机及交通路网中的控制系 统等综合起来，促进交通相关因素之间的协调与优化配置，经济高效地解决交通 问题。在智能交通系统中，最关键问题是要对车辆进行准确的定位和导航。 北京邮电大学硕：t 学位论文 车载定位导航技术【2 j 是综合应用定位技术、地理信息系统( g i s ：g e o g r a p h i c i n f o r m a t i o ns y s t e m ) 技术、计算机技术、通信技术等现代科技的城市交通引导系 统，它是智能交通系统的组成部分之一，是其他交通管理功能的基础。它利用全 球定位系统对行驶的车辆进行定位，运用传感器设备检测车辆的行驶状态，并借 助电子地图，多媒体信息处理、通信技术等技术手段，使交通控制中心和驾驶员 可以准确的掌握车辆所处的位置。车载定位导航系统可以显示车辆所在位置、交 通路网以及路况信息，并为驾驶员找到从始发地到目的地的最优行车路径，避开 交通拥塞，减少交通意外，有助于实现交通流量在整个交通路网上的合理分配， 使交通路网能够得到最合理、有效的利用。车载定位导航技术将驾驶员、车辆和 交通路网紧紧的联系在一起，形成了交通系统中三大主体“人、车、路 有机结 合的智能交通系统，因此车载定位导航技术在智能交通系统中起着不可替代的作 用，研究车载定位导航技术十分必要。 1 2 车载定位导航系统 1 2 1 车载定位导航系统组成 车载定位导航系统利用全球定位系统、地理信息系统、电子地图、计算机技 术、现代通信技术等高新技术，使车载导航计算机可以自动确定并显示车辆的当 前位置以及实时交通路网信息。车载定位导航系统可以最大限度减少驾驶强度， 为驾驶员寻找从当前位置到目的地的最优行车路径，并以声音或者图像的形式提 供路径引导功能，协助其顺利到达目的地。车载定位导航系统通过引导驾驶员的 驾驶行为改善路网的交通状况，因此，车载定位导航系统对实现整个交通系统智 能化、合理化、高效化有着至关重要的作用。 对于现代的车载定位导航系统，按照功能可以划分为定位模块、数字电子地 图、地理信息引擎、路径规划、路径引导、地图匹配、人机交互界面、无线通信 八个模块【3 j ，如图1 - 1 所示： 2 确定车辆目前行驶的路段，以及正在接近的路口。 数字电子地图包含以预定格式存储的数字化导航电子地图，为车辆导航提供 诸如道路位置及坐标、交通路段限制、房屋建筑、兴趣点等重要信息。 地理信息引擎按照预设的格式存储与路网有关的数字电子地图信息，是操作 电子地图数据库的接口，是整个车辆导航系统的基础。 路径规划模块帮助驾驶员在旅行前或旅途中选择合适的出行路线。它根据存 储于电子地图的道路信息，采用特定的算法，确定起始点与目的地之间最优行车 路径。 路径引导模块帮助驾驶员沿着路径规划中预定的路线行驶，从而顺利到达目 的地。 地图匹配模块将定位模块输出的定位信息与电子地图数据库提供的道路信 息进行实时比较，修正车辆行驶路径与地图显示路径之间的误差，通过适当的匹 配模式和软件方法确定车辆当前的行驶路段以及所处的准确位置。 人机交互界面是用户与车载终端之间的交互接口，用户可通过人机交互界面 向车载终端输入信息查询、路径规划及引导等请求指令，车载终端可通过人机交 互界面向用户显示结果。 无线通信模块可通过无线通信网络接收交通信息广播等信息，并完成车辆及 3 北京邮电大学硕士学位论文 其用户与交通管理系统之间的信息交换过程。 一般来说，从导航功能实现的角度来看，车辆导航系统可分为两类，一类是 自主式车辆导航系统，其定位和导航功能完全由车载导航计算机独立实现。对于 自主式车辆导航系统，车载导航计算机都具有全球定位系统( g p s ：g l o b a l p o s i t i o n i n gs y s t e m ) 定位和电子地图的存储设备，并且能够独立完成地图匹配、 路径规划和路径引导等功能。另一类是中心决定式导航系统，此类系统对车载导 航计算机要求较高，需要无线通信网络支持以保证车载导航计算机能够实时与中 心站进行通信，中心站结合实时交通信息对车辆进行导航，这类系统的定位和导 航过程都可由中心站来实现。 1 2 2 车载定位导航系统研究现状 从卫星定位上来说，为满足军事部门和民用部门对连续实时和三维导航的迫 切要求，1 9 7 3 年美国国防部制定了g p s 计划。美国1 9 9 4 年宣布在1 0 年内向全 世界免费提供g p s 全球定位系统的使用权，使世界各国争相利用这一系统。1 9 9 6 年2 月2 9 日，美国政府正式宣布将g p s 开放为军民两用系统，但仍实行s a ( s e l e c t a v a i l a b i l i t y ，可用性选择) 政策，故意劣化定位精度，使民用用户的应用受到限 制【4 1 。 美国为了充分利用g p s 系统的商业价值，独霸全球的导航定位市场，近年来 对g p s 系统进行了一系列的更新。首先，从2 0 0 0 年5 月2 日起，停止实施“s a 政策，并将在g p s 卫星l 2 频率信号上增设c a 码。2 0 0 5 年前，在g p s 新型工 作卫星b l o c ki if 上增设第三频率1 1 7 6 4 5 m h z ，以提高g p s 动态和静态定位精 度。g p si i l 计划除了继承g p s 更新计划外，重点是放弃现有2 4 颗中高轨道卫 星星座方案，采用全新的3 3 颗高椭圆倾角轨道卫星以及在赤道上空的静止卫星 所构成的卫星星座，除采用更稳定的频标和提高信号可靠性等措施外，g p si i i 卫星将采用新的m 码以增强保密和抗干扰功能。g p s i i i 预计在2 0 1 5 , - 一2 0 2 0 年投 入运行，计划将对军用平台提供2 5 年的卫星导航服纠5 1 。 为打破美国全球定位系统独霸天下的局面，开创欧盟空间大地测量和航天事 业的新阶段，2 0 0 2 年3 月2 6 日，欧盟1 5 个成员国的交通部长在布鲁塞尔决定 开始启动伽利略卫星导航定位系统计划。伽利略系统并不是重复g p s 或者是 g l o n a s s ( 原苏联卫星导航系统) 系统，它由民问组织控制，保证服务的连续 性和完好性；系统本身提供了比“定位 更多的服务，侧重于导航，卫星的覆盖 度更高，定位精度更高( 更好的星座设计) ，提供系统完备性参数和系统错误警 告等信息；和g p s 、g l o n a s s 系统兼容，为用户提供多样的服务【5 1 。 4 北京邮电大学硕士学位论文 我国早在6 0 年代末就开展了卫星导航系统的研制工作，但由于多种原因而 夭折。在自行研制“子午仪 定位设备方面起步较晚，以致后来使用的大量设备 中，基本上依赖进口。7 0 年代后期以来，国内开展了探讨适合国情的卫星导航 定位系统的体制研究。在1 9 8 3 年，我国提出了北斗导航系统的方案，突出特点 是构成系统的空间卫星数目少、用户终端设备简单、一切复杂性均集中于地面中 心处理站。北斗导航又称双星快速定位通讯系统，双星定位法是一种根据时间 测距原理的定位方法。这种方法能利用定点于赤道上不同经度位置上空的2 颗地 球静止轨道卫星和一些辅助手段，为工作区内用户提供连续、实时的定位信息。 自2 0 0 0 年以来，我国已成功发射了3 颗“北斗导航试验卫星，建成了北斗导 航试验系统。该系统可在服务区域内任何时间、任何地点，为用户确定其所在的 地理经纬度信息，并提供双向短报文通信和精密授时服务。目前，系统已在军事、 测绘、交通运输、国家安全等领域逐步发挥重要作用1 6 i 。 北斗导航系统虽然和g p s 全球定位系统相比有一定的差距，但是它具有卫 星数量少、投资小、用户设备简单价廉、能实现一定区域的导航定位、通讯等多 用途，可满足当前我国陆、海、空运输导航定位的需求。更重要的是，北斗卫星 导航系统是我国独立自主建立的卫星导航系统，它的研制成功标志着我国打破了 美、俄在此领域的垄断地位，解决了中国自主卫星导航系统的有无问题。此外， 该系统并不排斥国内民用市场对g p s 的广泛使用。相反，在此基础上还可建立 中国的g p s 广域差分系统。可以使g p s 民用码接收机的定位精度由百米级修 正到数米级，可以更好的促进g p s 在民间的利用【6 j 。 从车辆导航上来讲，西方发达国家对车辆导航系统的研究较早，技术比较先 进，并且开发出了许多高性能的导航产品推向市场。从2 0 世纪8 0 年代以后，车 辆导航技术逐步受到世界各国政府、企业及科研机构的高度重视，许多发达国家 都把车辆导航技术列入国家研究计划之中，投入了大量的人力、物力和财力进行 研究、试验和开发。目前，车辆导航系统的研究以美国、日本和欧洲为代表，它 们的导航技术代表了本领域研究和应用的发展方向，尤其是日本的导航技术更是 处于全面的领先地位，其国内的自主式导航设备市场化水平很高，并且建立了以 动态路径引导系统为基础的通用交通管理系统。从日本智能交通系统的发展年鉴 来看，日本从1 9 9 2 年开始大规模应用车辆导航系统，从1 9 9 6 年开始，车辆导航 系统就进入快速发展期。目前年销售量维持在几百万套，超过6 0 的新车出厂时 就已安装了车辆导航系鲥7 。 我国在车辆导航系统方面的研究开始较晚，9 0 年代初，一些高校和交通研究 机构率先开始了一些尝试性的研究，但一直没有成熟的、可以广泛普及和推广的 车辆导航产品。近年来，随着越来越多的高科技企业进入到车辆导航研究领域， 5 北京邮电大学硕士学位论文 我国的车辆导航技术迅速发展起来，相应的产品不断进入导航市场。不过，我国 市场上还仅限于自主式的车载导航产品，中心决定式的车辆导航系统及其相应车 载导航产品还没有问世。 对于自主式车辆导航系统，导航计算机受车载条件、技术瓶颈以及成本限制， 实时处理能力和存储资源有限，而车辆导航系统对路径规划的实时性要求很高， 因此，利用中心站强大的处理能力，而进一步减轻终端负担的中心决定式车辆导 航系统，可以使得车载定位导航系统向着更微型化、智能化的方向发展，将是未 来车辆导航市场的生力军。另一方面，通过车载导航系统与中心站的通信，可为 用户提供更多的服务内容，如与手机连接、接入计算机网络等，易于服务的多样 性和可扩展性。因此，对于中心决定式的车辆导航系统的研究和实现，对我国未 来的车载导航系统具有必要的意义【8 1 。 1 2 3 车载定位导航系统的关键技术 1 、车辆定位技术 由图1 1 可见，定位模块是车载定位导航系统中最基本的模块。常用的定位 技术包括卫星定位、无线电定位、网络独立定位等。由于网络、环境因素，有时 采用一种定位技术的系统难以满足实际需求，因此陆续出现了基于组合定位方式 的定位技术，即联合定位。联合定位的典型代表，就是将g p s 卫星定位技术与 移动通信网络技术相结合的a - g p s ( a s s i s t e dg l o b a lp o s i t i o n i n gs y s t e m ，辅助全 球定位系统) 技术。 2 、电子地图技术【9 j 一 由图1 - 1 可见，电子地图技术，不但包括以预定格式存储的数字化导航电子 地图，还包括操作电子地图的接口等。它的制作需要涉及计算机图形学、数据库、 地理信息系统等技术的综合应用，需要将空间数据和相关属性数据通过一定的组 织手段结合成为地图数据库，来达到数据的有效管理，能以图形的方式输出信息， 并能借助其空间分析能力和可视化表达，进行各种辅助决策。 3 、地图匹配技术【1 0 】 在车辆导航系统中，地图匹配是一种基于软件实现的定位修正方法。依靠软 件方法，车辆定位轨迹与数字地图中的道路网信息联系起来，以高精度的道路网 数据作为先验信息，将车辆的定位结果匹配到车辆行驶所在的道路上，实现车辆 位置的实时显示。这一技术极大地改善了车载定位导航系统的定位精度，并为实 现路径引导提供可靠依据。地图匹配技术大大提高了车辆行驶到路段上的正确 率。 6 北京邮电大学硕士学位论文 4 、城市交通流状态分析技术 能否实时、准确地分析出城市交通流状态，得到道路网络的动态交通状态， 不但是车载定位导航系统的关键技术，同样也是实现智能交通系统的关键技术之 一。目前，能够进行交通流分析的方法主要有：基于感应线圈的方法、使用车辆 电子标签的方法，和较为传统的基于视频检测、红外检测、微波检测的方法等。 但这些方法大多需投入大量的硬件设旋；或是只能用于快速道路的交通流分析， 而无法用于情况更为复杂的城市道路，因此，近年来提出的基于具有定位功能的 探测车提供的信息，对道路交通状态进行评估的城市交通流状态分析技术，不但 提高交通设施和道路的利用率，减少交通阻塞，提高行车的安全性，而且减少了 导航系统在硬件上的投入，因此越来越多地受到人们的关注。 5 、路径规划技术 路径规划技术是导航系统智能化的重要体现，城市路网信息是完成路径规划 的前提，路径规划算法是完成路径规划的基础。一般来说，经典的路径规划算法 有d i j k s t r a 算法、b e l l m a n f o r d 算法、f l o y d 算法、启发式搜索算法等。一个高 效的路径规划算法必须要保证运算速度和存储开销方面都比较合适。为了满足车 辆导航系统的实时性要求，改进已有路径规划算法以及研究新算法一直是国内外 专家和学者关注的热点。 1 3路径规划研究综述 路径规划是车辆导航系统帮助驾驶员按照某种策略找到从出发点到目的地 的最优行车路径的过程。路径规划可分为单车辆路径规划和多车辆路径规划，单 车辆路径规划是在一个特定的道路网上根据一个车辆的当前位置和目标给出单 个路径规划，属于用户优化问题；多车辆路径规划是在一个特定的道路网上为所 有的车辆规划各自的目标路径，属于系统优化问题。在这里，我们主要讨论的是 单车辆路径规划问题。 针对一个特定的应用，在进行路径规划时可以采用多种标准来优化路线，如 距离最短、行车时间最少、费用最低等，这取决于系统的设计和用户的意愿。一 条路径的好坏取决于许多因素，如图1 2 所示。但无论采用何种标准，都可将路 径规划问题看作是在给定道路网络中寻找具有最小代价的最短路径问题。按照图 论的相关理论，可以把道路网络转化为带权的有向图，因此计算道路网中的两点 之间的最优路径问题都可以归结为求解带权有向图的最短路径问题【1 。 7 北京邮电大学硕士学位论文 图1 - 2路径好坏制约因素示意图 在车辆导航系统中，不仅有利用静态地图数据计算出最优路径的静态路径规 划算法，也可以采用动态路径规划算法，通过实时获得交通信息，结合静态地图， 计算出最优行车路径。不过，在当前车辆导航领域，用于车辆导航的路径规划算 法多集中在静态路径规划方面。常见的算法包括适用于非负权值网络的d i j k s t r a 算法、可求解所有节点对之间最短路径的f l o y d 算法、基于知识的搜索策略启发 式搜索算法等。各种算法的适用情况和执行效率各不相同，在不同的导航请求下， 选择何种算法能使车辆导航系统的效率最高也是目前正在研究的问题，这不仅要 对算法进行理论上的分析，还要进行大量的试验进行比较才能得出最终结论。 目前，在国内有不少学者对路径规划进行了深入的研究，从国内来说，同济 大学晏克非提出了动态k - 最短路径改进的a 奎算法【1 2 l ，在最短路径算法中融入了 动态行程的时间计算模型；吉林大学的姜桂艳在路径选择模型方面，提出了基于 流体神经网络的路径规划算法【1 3 l ；另外，周浩华等分析了启发式搜索算法a 算 法的优点和不足，提出自动寻径算法【1 4 l ，该算法通过将统计量引入估价函数的 方法克服了传统算法运算速度慢、实用性差的缺点。同时，国外学者也对路径规 划算法进行了大量研究，提出了许多新算法。如j e f f r e yl a d l e r 的b 晕算法【1 5 1 ， 虽然增加了算法的计算时间，但提高了a 拳算法的搜索速度；此外，还有u p a p e 的增广图算法、e g l o v e r 提出的阈算法【1 6 】等。 本课题中所研究的路径规划算法为动态路径规划，需要实时获得交通信息， 即道路拥堵情况。这里的路径规划并不仅仅是最短路径的计算，还包括对车辆定 位点的道路匹配、通过对移动交通流的检测进行的道路状态判断，因此，本文讨 论的路径规划为广义的路径规划。 1 4本课题研究目的及意义 近年来，车辆数量的急剧增加导致交通拥堵现象日益严重，这已经成为困扰 8 北京邮电大学硕士学位论文 人们日常生活与工作的严重问题。智能交通系统能够合理分配交通流量，减少交 通堵塞，对城市车辆进行有效的交通引导和管理。因此，将卫星定位技术与车辆 导航技术相结合，利用电子地图数据库的道路信息、实时定位信息以及实时交通 信息实现车载定位导航已成为智能交通系统研究的重要内容。 目前，尽管我国的车载定位导航技术发展迅速，但目前进入导航市场的，还 仅限于自主式的车载定位导航产品，中心决定式的车载定位导航系统及其相应车 载导航产品还没有问世。从定位方面来说，目前a g p s 定位技术由于需要由移 动网络进行辅助，因此还主要应用于手机定位，而市场上大部分的车载定位导航 系统，都采用了基于g p s 卫星的自主定位。 本课题所研究的车载定位导航系统，基于a - g p s 定位技术，在网络侧设有 a - g p s 定位服务器，同时采用基于中心站的导航技术，设有交通信息处理与导 航服务器，来存储和处理城市电子地图数据、提供导航服务。因此，本课题中所 研究的，是一种中心决定式的车载定位导航系统。 另外，目前的车载定位导航系统中，大多采用路边交通流检测设备来获取城 市交通流状态信息，这些方法大多需投入大量的硬件设施，或是只能用于快速道 路的交通流分析，而无法用于情况更为复杂的城市道路。由于本课题中引入了交 通信息处理与导航服务器作为中心站，来进行导航过程的处理，那么可以将车载 终端作为探测车，中心站可通过移动通信网络实时地获取探测车上报的数据源， 并利用多级模糊模式识别的技术对城市道路交通状态进行评估和判断。这种利用 探测车技术和多级模糊模式识别技术的城市交通流状态分析的方法，对于车载定 位导航系统的动态实时导航很有意义。 实验结果表明，本课题中实现的交通信息处理与导航服务器，能够满足车载 定位导航系统的实时性要求，且能很好地融合到整个项目产品中，具有一定实用 性。 1 5主要内容与结构安排 1 5 1主要内容 本课题主要研究内容是作为导航中心站的交通信息处理与导航服务器的实 现。基于对现有路径规划服务的一些研究，本课题对路径规划的内容进行了扩展。 9 北京邮电大学硕上学位论文 由于在本项目中，导航功能与a - g p s 定位技术相结合，路径规划的起始点为车 辆的定位结果，因此首先要进行地图匹配，将车辆的定位结果匹配到相应的道路 上去；其次，本课题中综合考虑行驶距离和时间来作为路径规划标准，因此还需 要对道路交通状态进行判断。 由此，我们的交通信息处理与导航服务器共有三大功能，一是道路匹配功能， 即将车辆的定位结果匹配到车辆行驶的道路上；二是道路状态判断功能，即根据 探测车数据源判断城市道路交通流状态；三是路径规划功能，即根据城市交通流 状态，规划出从车辆当前位置到目的位置的最佳参考路径来。其中，道路匹配功 能是路径规划的基础，道路状态判断功能是路径规划的根据，三个模块共同构成 路径规划的功能。 1 5 2 结构安排 论文共分为六章，其中二、三、四、五章为论文的重点部分。具体结构安排 如下t 第一章是引言部分。本章首先介绍了课题研究背景、车载定位导航系统的模 块组成和关键技术。然后，概述了车载定位导航系统以及路径规划技术的研究现 状。最后，说明了本课题的研究目的和意义，并概要提出了本文主要内容和结构 安排。 第二章为项目介绍与课题设计。本章首先介绍项目研究内容，概述了项目中 所运用到的a - g p s 定位技术。然后对项目研发的产品系统架构进行描述和说明， 介绍本课题所研究的交通信息处理与导航服务器在产品系统中所处的位置和实 现的功能，简要介绍其交通信息数据部分和算法部分，引出道路匹配、道路状态 判断、路径规划三个模块，介绍交通信息处理与导航服务器的工作流程。 第三章为道路匹配模块的实现。本章首先结合m a p l n f o 电子地图，介绍道路 匹配模块的概念和原理，然后详细说明道路匹配模块数据库表的设计思路和结 果，描述道路匹配模块的处理流程和详细设计，最后指出道路匹配过程中存在的 问题。 第四章为道路状态判断模块的实现。本章首先介绍常见道路状态判断技术， 然后介绍了基于探测车、利用多级模糊识别方法的移动交通流检测技术，详细说 明基于此技术的道路状态判断模块原理，介绍道路状态判断模块数据库表的设计 思路和结果，描述道路状态判断模块的处理流程与详细设计。最后指出了模块存 在的问题。 第五章为路径规划模块的实现。本章首先介绍路径规划常用算法，对其中的 1 0 1 1 北京邮电大学硕士学位论文 第二章项目介绍与课题设计 2 1 项目研究内容 本项目研究的是一个由服务器端和定位导航终端共同组成的产品系统。与一 般的车载定位导航系统相比，本项目研究的产品系统的不同之处在于： 1 、一般的车载定位导航系统中，车辆采用g p s 技术进行自主定位，定位时 间较长，精度较低。在本项目研究的产品系统中，采用a - g p s 定位技术，由服 务器端完成核心定位算法，定位更快速、更精确。 2 、一般的车载定位导航系统中，车辆进行自主导航，导航处理过程在终端 侧进行，负责路径规划的导航计算机系统受车载环境和成本制约，处理能力和存 储资料十分有限，而在实际应用中的道路数据库往往规模庞大，这就影响了路径 规划的时效性。在本项目研究的产品系统中，终端不需要存储路径规划算法相关 的矢量地图以及属性数据，关于最佳路径的规划算法完全由服务器端完成，终端 通过与服务器端建立g p r s ( g e n e r a lp a c k e tr a d i os e r v i c e ，通用无线分组业务) 连接，发起导航请求，并获取路径信息，使路径规划效率大大提高。 3 、一般的车载定位导航系统中，道路交通信息一般来自交通信息提供商。 除了传统的地下感应线圈、路口监控摄像系统等政府数据以外，浮动车、手机信 号等商业公司所掌握的原始数据也开始作为重要的交通信息源。在本项目研究的 产品系统中，由于终端可与服务器端进行实时通信，因此可将获得定位导航服务 的终端同时看作浮动车，即道路交通信息的提供者，通过终端向服务器端实时上 报的信息，来维护服务器端的道路拥堵状态信息。 4 、一般的车载定位导航系统中，用户需要与终端物理位置一致，从导航终 端上查看定位导航信息。在本项目研究的产品系统中，由于引入了服务器端，用 户可与终端在位置上分离，而通过短信或网页( w 曲) 方式获取定位导航服务， 并且通过对服务器端的功能扩展，用户也可定制个性化服务。 1 2 北京邮电大学硕士学位论文 2 1 1a - g p s 定位技术概述 1 、g p s ( g l o b a lp o s i t i o n i n gs y s t e m ，全球定位系统) 系统1 1 7 j g p s 系统即g p s 全球卫星定位系统，它由三大部分构成：g p s 卫星星座( 空 间部分) ，地面监控部分( 控制部分) 和g p s 信号接收机( 用户部分) 。g p s 卫 星星座由2 1 颗工作卫星和3 颗在轨备用卫星组成。2 4 颗卫星均匀分布在6 个轨 道平面内，轨道倾角为5 5 度，各个轨道平面之间相距6 0 度，即轨道的升交点赤 经各相差6 0 度。地面监控系统提供每颗g p s 卫星所播发的星历，并且保持各颗 卫星处于同一时间标准g p s 时间系统。卫星上的各种设备是否正常工作，以及 卫星是否一直沿着预定轨道运行，都要由地面设备进行监测和控制。g p s 信号接 收机能够捕获到按一定卫星高度截止角所选择的待测卫星的信号，并跟踪这些卫 星的运行，对所接收到的g p s 信号进行变换、放大和处理以