（计算机应用技术专业论文）路径规划算法研究与其在车载导航系统中的应用.pdf

摘要 摘要 随着中国越来越多的人拥有私人汽车，车载导航系统逐渐进入人们日常生活。 虽然目前国内使用车载导航系统还不是太多，但其巨大的市场潜力引起了广泛重 视。车辆导航系统具有巨大的社会效益和经济效益，受到社会和政府部门的关注 和大力支持。 嵌入式车载导航系统是智能交通系统的重要组成部分。它是计算机技术、定位 技术和g i s 技术集成在一起的一种嵌入式应用系统。它引导驾驶员在正确的道路 上行使，是一种智能辅助驾驶系统。 本文介绍了车载导航系统的发展历史和国内外研究现状，提出了车载导航系统 的逻辑框架设计、具体功能设计与实现，对嵌入式g i s 的主要概念、系统构成等 作了概括性的介绍。对这些关键技术的分析和研究基础上，采用面向对象的系统 分析和设计方法，设计并部分实现了一套嵌入式车载导航系统。 在系统的逻辑结构基础上，分析研究系统设计与开发的问题，包括应达到的目 标、系统的开发环境及系统的功能模块等。文中详细分析和设计了嵌入式g i s 空 间索引技术，重点研究适于车载导航的路径规划算法，引入新颖的蚁群算法，以 及作为其基础的路网表达方法与存储结构。 关键字：导航系统，蚁群算法，最短路径，空间索引 a b s t r a c t a b s t r a c t a sp r i v a t ec a r sb e c o m i n gp o p u l a ri nc h i n a ，v e h i c l en a v i g a t i o ns y s t e mg r a d u a l l y b e c o m eo n ep a r to fo u rd a i l yl i f e t h o u g hv e h i c l en a v i g a t i o ns y s t e mi s n tu s e d f i e q u e n t l yi nc h i n a ，p e o p l eh a v es e e nt h eh u g em a r k e tp o t e n t i a l v e h i c l en a v i g a t i o n s y s t e mw h i c hh a sal a r g eb e n e f i to fs o c i e t ya n de c o n o m y i ss u p p o r t e db yg o v e r n m e n t e m b e d d e dn a v i g a t i o ns y s t e mi so n e p a r to fg e o g r a p h i ci n f o r m a t i o ns y s t e m i ti sa n e m b e d d e ds y s t e mw h i c hi n t e g r a t e st h ec o m p u t e rt e c h n o l o g y , l o c a t i o nt e c h n o l o g ya n d g i st e c h n o l o g y i ti sa ni n t e l l i g e n ta s s i s td r i v es y s t e m ，w h i c hg u i d et h ev e h i c l er u n n i n g o nt h er i g h tw a y ab r i e fh i s t o r ya n dr e s e a r c hs t a t u so fv e h i c l en a v i g a t i o ns y s t e ma r ei n t r o d u c e d t h e l o g i c a lf r a m e w o r ko fv e h i c l en a v i g a t i o ns y s t e mi sc o n s t r u c t e d t h eb a s i cf u n c t i o na n d t h es o l u t i o n sf o rv e h i c l en a v i g a t i o ns y s t e ma r ei m p l e m e n t e d t h ec o n c e p ta n ds t r u c t u r e o ft h ee m b e d d e dg i si sa l s od i s c u s s e d e v e n t u a l l yo nt h eb a s i so fi i l t r o d u c t i o na n d a n a l y s i sa b o u tt h e s ek e yt e c h n o l o g i e sa ne m b e d d e dv e h i c l en a v i g a t i o ns y s t e mi s d e s i g n e da n dp a r t i a l l yr e a l i z e db yu s i n gt h eo b j e e to r i e n t e dp r o g r a m i n gm e t h o d t h ed e v e l o p i n gt a r g e t , e n v i r o m e n ta n dt h ef u n c t i o np a t t e r no ft h es y s t e ma r e d i s c u s s e db a s eo nt h el o g i c a ls y s t e ms t r u c t u r e t h es p a t i f li n d e x i n gt e c h n i q u ei s p a r t i c u l a r l ya n a l y z e da n dr e a l i z e d t h er o u t ep l a n n i n gm o d u l ei m p l e m e n t sa na l g o r i t h m o fo p t i m a lr o u t ep l a nf u l f i l l i n gt h er u l e so ft r a n s p o r t a t i o nb a s e0 1 1a n tc o l o n ya l g o r i t h m t h e r e p r e s e n t a t i o na n ds t o r a g es t r u c t u r ef o rr o a dn e t w o r ka r ea l s or e l a t e d k e y w o r d s ：n a v i g a t i o ns y s t e m ，a n tc o l o n ya l g o r i t h m ，s h o r t e s tp a t h ，s p a t i a li n d e x 图目录 图目录 图2 1 中心式车辆定位导航系统结构9 图2 - 2 自主式车载定位导航系统结构l o 图2 3v n s 的基本结构。l l 图2 - 4 蚂蚁寻找最短路径示意图1 9 幽3 1 系统结构。2 5 图3 2 导航系统功能逻辑结构2 8 图3 3 导航系统功能菜单3 0 图3 4 空间对象的层次结构3 2 图3 5g i s 对象层次结构。3 3 图4 1 路网示意图3 5 图4 2 邻接矩阵示意图3 5 图4 3 邻接表示意图3 6 图4 4 前向关联边结构示意图3 8 图4 5 算法搜索范围图示4 0 图4 - 6 蚁群算法求解最短路径流程图4 l 图4 - 7 模拟道路示意图4 3 图4 8 地图数据库道路节点表4 3 图4 9 地图道路信息表。4 4 图4 - 1 0d ij k s t r a 算法和蚁群算法性能对比4 6 图4 1 l 成都地图测试算法有效性。4 9 图5 1r 树索引示意图5l v i 表目录 表目录 表2 1p c - g i g 与嵌入式g i s 比较l2 表3 1 嵌入式处理器比较2 6 表3 - 2 嵌入式l i n u x 与其它嵌入式操作系统比较2 7 表4 - l 邻接矩阵和邻接表常用操作复杂度比较。3 7 表4 2o i j k s t r a 算法求解的仿真结果4 5 表4 - 3 利用蚁群算法求解的仿真结果4 5 表4 4p 参数选择的仿真结果4 8 v 缩略语目录 缩略语目录 英文缩写英文全称中文释义 i t s i n t e l l i g e n tt r a n s p o r ts y s t e m 智能交通系统 v n sv e h i c l en a v i g a t o rs y s t e m车载导航系统 g i s g e o g r a p h i ci n f o r m a t i o ns y s t e m 地理信息系统 g p sg l o b a lp o s i t i o n i n gs y s t e m全球定位系统 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：盈盛 日期： 2 。7 年彳月f 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：逡蕴导师签名：弛 日期：2 7 年占月1 日 第一章引言 1 1 研究背景 第一章引言 交通事业的发展关系到我国社会主义现代化建设，对人们的日常生活影响巨 大。车辆的使用一方面促进了社会经济的快速发展，另一方面不断改善着人们的 生活，提高着人们的生活质量。然而，机动车数量的大幅增长，使交通问题在社 会生活中日益突出。交通拥堵、交通事故等社会问题严重影响到社会正常次序。 当前交通问题是一个全世界都面临的问题，发达国家和发展中国家都深受其害。 以投入巨大资源修建道路这种高昂成本的方式解决交通拥挤问题杯水车薪。资金、 环境、历史原因等因素使改善道路交通成本更加高昂问题更加复杂。所以以新建 道路这种粗放式手段效果很有限，无法从根本上解决交通问题i i l 。 为了缓解交通问题，从上世纪6 0 年代起，发达国家开始着手研究解决交通问 题的可行办法。制定交通规划、使用信号灯等措施缓解了交通问题，不足以高效 的方法解决交通问题，仍然无法满足日益增长的车辆需要。交通问题是一个系统 问题，只能从系统观点整体上综合考虑解决，单从道路方面考虑解决问题的效果 有限。 为解决交通问题，人们从系统的角度提出了智能交通系统( 1 1 r s ，i n t e l l i g e n t t r a n s p o r ts y s t 锄) 的概念【2 l 。它是一个交通综合管理系统，综合考虑车辆和道路等 因素的影响，用科学管理和现代技术手段系统解决交通问题。i t s 先后在经济发 达国家首先研究并投入使用。这个系统将现代信息技术、通讯技术、管理理论综 合应用于交通系统，促进交通相关因素之间的协调与优化配置，经济高效地解决 交通问题。 社会发展，城市不断扩大，新修道路如雨后春笋般出现；单行线等交通管理 措施广泛应用于城市交通p l 。这提供了丰富的交通路线选择，提高了路网的健壮 性，却增大了道路网路的复杂性，增加了道路记忆的难道。于是，人们需要个 交通服务平台，提供实时交通信息服务，能够绕开拥堵路段，降低路网识别的复 杂性，提高驾车安全性；交通职能部门为提高道路效益也希望能平衡车流，充分 挖掘道路的交通容量潜力。作为有效解决交通问题的的i t s 核心部分的车辆导航 电子科技大学硕士学位论文 系统v n s 受到社会和政府部门广泛关注和重视。它无疑会改善人们的生活，具有 巨大的应用前景。 车载导航系统综合应用定位技术、g i s 技术、计算机技术、通信技术等现代 科技的城市交通引导系统，它是智能交通系统的组成部分之一，是其他交通管理 功能的基础【4 1 。车载导航系统为驾驶者提供辅助驾驶功能，引导驾驶者在正确、 快捷的道路上行使，减少不必要的出行路程。车载导航系统能够实时定位，通过 语音、电子地图等手段引导驾驶员在正确的路线上行使【5 】。 上世纪九十年代车辆定位导航逐渐发展成熟，开始大量投放市场。在发达国 家，车载导航系统逐渐普及，市场化运作的便捷高效的交通信息系统已出现【6 l 。 我国在车载导航领域起步晚，相关信息服务还不完善，交通管理信息化程度不高。 这一现状促使我国必需加快车载导航系统的研究与推广，提高我国交通事业现代 化程度，促进社会经济效益的提高。 1 2 车载导航系统的发展和趋势 1 2 1 车载导航系统的历史 导航技术在很早就开始应用。指南车和计里鼓车等古代导航设备被认为是现 代磁罗盘和差分里程计的原型，是已知的最早的导航工具。 上世纪6 0 年代末，依靠短距离信标作为通信媒介的电子路径引导系统e r g s 【7 】开始研制。它提出的中心导航思想意义重大，为以后中心式导航系统体系结构 的研究奠定了理论基石。 从8 0 年代后期开始，智能交通系统在世界范围内发展迅速，相关系统特别是 定位导航系统在世界范围内得到广泛应用。 日本于1 9 7 1 年开始研制综合车辆交通控制系统c a c s 【3 】。它的出现促进了车 辆导航系统在智能交通系统中的应用，为智能交通系统的发展奠定了基础。8 0 年 代，使用彩屏显示技术，配备c d r o m 数字地图的自主式导航系统f 9 j 首先在同本 诞生。9 0 年后，随着先锋公司商业导航产品进入消费市场，其它厂商各式各样的 车载导航产品陆续跟进。全球定位技术、语音引导等最新技术被广泛应用，导航 产品技术升级越来越快，性能越来越好。车载导航设备的广泛使用，使同本智能 交通系统的发展处于领先地位。 2 第一章引言 与日本智能交通系统同时开始的还有欧洲智能交通系统，项目命名为a l l 。 八十年代，先后有c a r i n 和e v a 项目的车辆导航系统出现。c a r i n 是一种较为 实用的导航定位系统。它依赖推算定位、地图匹配技术使定位更精确，彩屏显示 提供了友好的用户接口，自带数字地图存储在c d r o m 中。e v a 除了应用以上 技术外，它还提供合成语音，用语音方式引导司机驾驶【1 0 】。 美国最具影响的导航系统是在1 9 9 4 年推出的自主导航系统g u i d e s t a r 。它配备 g p s 接收机的，提供全天候更精确的定位，在车载导航发展史上具有划时代的里 程碑意义。 由于历史原因，我国车载导航研究较其他国家晚，但发展迅速。进入9 0 年代 后，虽然国外产品在技术方面领先，但由于国内外在交通规则和交通设施等方面 存在差异，国外导航产品并不适合在我国的交通环境下应用。因此国外厂商通过 技术合作，与国内企业共同研制适合中国国情的车载导航产品，实现产品本地化。 1 2 2 车载导航技术的发展趋势 目前我国政府对交通事业投入巨大，非常重视对有效缓解交通问题的i t s 与 相关技术的应用。北京奥运会为所有服务车辆配备卫星定位系统。2 0 1 0 年世博会 前，上海所有公共交通车辆都将配备全球卫星定位系统】。各种实用技术不断涌 现，并应用于导航产品，使得导航产品不断升级，适应用户日益提升的需求。当 前导航技术发展趋势主要体现在以下多个方面： 1 平台丰富 技术进步使硬件性能不断提升，成本却不断下降。而硬件技术的快速发展推 动着导航产品的更新升级，为车载导航产品提供了丰富低廉的硬件平台。目前导 航技术己经广泛应用于车载电子、掌上电脑等多种硬件平台，满足用户不同的应 用环境与应用需求。 2 定位技术多样化 定位功能是实现其他功能的基础。当前广泛应用的定位技术主要有：独立定 位技术、卫星定位技术和无线电定位技术。为了提高定位准确度，需要多种定位 技术配合。但集成多种定位技术降低了系统可靠性，增加了复杂性，所以必须针 对不同应用的需要决定定位技术。 3 电子地图标准化 地理空间数据本身就是一种财富，有效利用这种财富会带来巨大经济和社会 3 电子科技人学硕士学位论文 效益。地理空间数据的共享能够节约大量测绘成本，促进不同机构之间的信息交 流共享，有利用地理信息产品的推广。日本k i w i 、欧盟国家g d f 电子地图标准 为地理数据共享提供了基础。它使不同用户、不同应用、不同系统之间共享地理 信息成为可能。中国国家基础地理信息中心广泛听取意见，正在制定适合中国国 情的国家电子地图标准。地理信息数据国家标准的出台必将促进中国车载导航产 业的发展。 4 与智能交通系统结合 智能交通系统从系统出发，综合交通各方面信息，实时有效地管理交通系统。 车载导航设备只有与i t s 相结合，共享交通信息，才能为驾车人提供更优质的出 行服务。随着智能交通系统的发展，作为i t s 的重要组成部分车载导航将逐渐普 及并得到不断升级。 5 融合无线通信技术 将无线通信技术与导航系统集成，使导航系统具有通讯功能。它可以与城市 交通信息系统连接，实时查询交通信息，获得更全面专业的交通服务。 6 语音识别与合成技术 语音是最自然便捷的人机接口。操纵方向盘的驾驶员来说，语音操控是一种 便捷的操作方式，可以大大降低安全事故。语音导航必然要采用语音合成技术。 它可以大大减少语音文件存储空间。 7 地图表现形式 可以推断平面地图必将被更具表现力的三维地图所取代，未来电子地图将更 加美观。 1 3 地理信息系统g i s 动态 1 3 1 国外的g i s 地理信息系统g i s 是上世纪6 0 年代开始发展起来的具有交叉学科的新兴技 术。它最初是为解决地理相关问题而提出的，而现在已广泛应用在环境保护、资 源勘探、土地管理、人口普查等社会和经济领域。1 9 6 3 年加拿大测量学家首先提 出地理信息系统这一术语。在加拿大建成世界上第一个地理信息系统加拿大 地理信息系统。当时由于计算机硬件水平限制，g i s 功能相当简单，这可以看做 4 第一章引言 地理信息系统的起步阶段。6 0 年代，许多地理信息组织机构陆续成立。这些g i s 组织机构的建立，大大推动了地理信息系统的推广。 7 0 年代以后，由于计算机科学技术的发展，相关配套软硬件技术的提高，g i s 功能逐步强大，g i s 开始朝着实用方向发展。许多专用的地理信息系统在许多国 家应用，在与地理相关的自然资源规划和土地管理方面做出了巨大贡献。许多商 业公司开始进入该领域，商业g i s 开始应用于相关领域。许多大学和科研机构也 开始重视g i s 的开发及应用，相关课程也开始出现在大学课堂上。 8 0 年代g i s 开始普及和推广，许多先进国家在同常工作大量应用地理信息系 统。由于高性能个人电脑的发展，使得地理信息系统在各行业广泛应用。同时计 算机网络技术的发展，加快了地理信息系统的共享与推广。g i s 应用范围扩展到 更复杂的区域开发和规划，如土地管理、自然资源规划、环境保护、产业布局等， 它为相关部门制定政策提供了决策依据。 上世纪9 0 年代以来，由于互联网技术的广泛应用，地理信息产业已经逐步成 熟。数字化地理信息产品在全世界迅速推广，在科学、社会、经济和政府管理部 门得到了全面发展和推广应用，其主要标志有： ( 1 ) g i s 系统使用增长迅速，g i s 市场的年增长率在百分之三十以上。 ( 2 ) 越来越多国际学术会议以g i s 为主题，涉及g i s 理论、相关技术以及应 用领域。 ( 3 ) 越来越多的学科引入g i s 相关应用，把g i s 作为学科新内容加以调整。 大学增设了g i s 相关课程，大力培养g i s 专家人才。 ( 4 ) 国际性和区域性的g i s 研究中心在美国等西方国家建立起来。 当前g i s 越来越受到关注，相关行业发展迅速，g i s 在国民经济中的作用越 来越大，社会和经济效益无法估量。 1 3 2 国内的g i s 相对于其它发达国家，我国g i s 起步稍晚，进入改革开放后发展迅速。我国 g i s 发展进程主要经历了4 个阶段，即起步阶段( 1 9 7 0 - 1 9 8 0 ) 、准备阶段( 1 9 8 0 - 1 9 8 5 ) 、 发展阶段( 19 8 5 1 9 9 5 ) 、产业化阶段0 9 9 6 年以后) 。 上世纪9 0 年代起，我国地理信息系统研究开始高速发展。研究朝着遥感和 g i s 一体化，朝着实用化和产业化方向发展，逐步完善全国性的基础地理数据库。 这期问一批国产g i s 软件开始服务于各行各业，为国民经济发展提供相关分析和 5 电子科技人学硕士学位论文 决策依据。由于政府相关部门重视和推广，g i s 在许多部门和领域得到广泛应用； 在高校g i s 相关的专业学科逐步开设；g i s 相关企业相继成立。 1 3 3 嵌入式g i s 嵌入式系统是计算机技术向小型化集成化发展到一定程度后的产物。它在信 息家电时代广泛应用。它是以应用为中心，以计算机技术为基础，软硬件可剪裁， 适应应用系统对功能、成本、体积、可靠性、功耗严格要求的专用计算机系统。 在智能移动设备，车载电子等应用领域，由于产品体积、成本等的限制，通常需 要将智能控制部分放置在设备内部尽可能小的空间中。这些设备的操作系统和应 用软件都是装在有限的内存( r o m ) q h 。这些设备的内部应用环境都属于嵌入式系 统环境。运行在嵌入式计算机系统上的地理信息系统是一个高度精简、高度优化 的g i s 软件系统，通常叫做嵌入式g i s e g i s 。 现有大型g i s 软件功能全面，但是对软硬件的要求较高，不适合应用到嵌入 式系统环境。而e g i s 具有很多大型g i s 所不具备的优势，它在满足对数据进行 实时准确处理的同时，对软硬件平台要求也比较低，可以很好的运行在嵌入式操 作系统上，针对不同应用具有可剪裁的优点。因此对嵌入式g i s 的研究和开发具 有广阔的应用前景。 1 4 课题研究意义 在经济发展的推动下，交通事业突飞猛进发展。随着新建道路和各种交通设 施的增多，新的交通管理措施也被广泛使用到城市交通中。这些在为人们提供多 种方便的同时也增加了出行的复杂性。此外机动车的增长远大于道路设施的增加， 交通拥堵形势严峻。调查显示：每年由于交通拥堵，造成美国的主要城市的经济 损失达4 7 5 亿美元【1 2 】。另一份调查【1 3 】表明：由于美国人口持续增长，导致城郊区 域交通恶化，每年损失达到5 0 0 亿美元。此外，据美国联邦公路局的研究【4 】表明： 由于缺乏良好的路径规划，车辆行驶的里程和行驶时白j 很大部分被浪费掉。这无 疑增加了交通堵塞，而且加重了能源浪费和环境污染。针对这些情况，人们迫切 需要一个信息服务系统能使其避免拥堵和有效驾驶。交管部门出于有效管理，充 分挖掘道路潜力，也希望交通流量均衡。 为了解决以上问题，智能交通系统重要组成部分的的车辆导航技术应运而生。 6 第章引言 车辆导航系统的研究意义主要表现在以下方面： ( 1 ) 为出行提供最优路线，节约了出行时间，减少了无效出行，为人们提供极 大的便利。 ( 2 ) 为驾驶员提供实时的道路引导，及时纠正错误路线；让驾驶员的注意力集 中到驾驶操作上，从而极大的降低交通事故率。 ( 3 ) 减少道路拥堵情况，降低了尾气排放，提高了环境效益，是解决交通问题 的一种可持续发展思路。 ( 4 ) 道路的通畅可以显著提高物流的速度，从而使企业的运输效率和经济效益 得到提高。有利于促进社会经济的发展。 ( 5 ) 车载导航系统具有广阔的市场前景。随着经济的发展，我国政府管理部门 的支持，车载导航系统具有广阔的市场需求，蕴含着巨大的经济效益。 ( 6 ) 车载导航技术作为多种学科多种技术交叉的新领域，对其研究会促进综合 学科的研究与发展。i t s 的重要研究方向之一就是车载导航。加快开展车载导航 的研究和应用对完善我国i t s 框架体系研究也是必要的。 总之，无论从满足市场需求、社会和经济效益的角度，还是从赶超国外先进 技术水平和完善我国i t s 技术架构体系的角度来看，在我国开展车载导航系统的 研究都具有很重要的意义 1 5 论文的主要研究内容及研究成果 1 5 1 论文主要研究内容与论文结构 根据作者所从事的工作，确定论文的主要研究内容有以下几个方面： ( 1 ) 分析设计自主式车载导航系统的基本框架 ( 2 ) 研究嵌入式g i s 的基本框架，实现其部分功能 ( 3 ) 空间查询模块的关键技术空问索引技术 ( 4 ) 路网表达方法与存储结构研究 ( 5 ) 研究改进蚁群算法应用于路径规划 本论文主要有六章： 第一章：介绍了车辆导航系统、g i s 发展过程和国内外研究现状，说明其研 究背景和课题意义，并对本论文的主要研究工作和论文组织结构进行了说明。 7 电子科技大学硕+ 学位论文 第二章：简要介绍了车载导航系统一般结构；比较分析了车载导航系统核心 部分嵌入式g i s 和通用g i s 的差异，通过分析嵌入式g i s 的特点提出了嵌入式 g i s 的一般设计原则；介绍路径规划常用的一些算法和它们的优点和不足；对模 拟仿生算法蚁群算法的原理进行了简单的介绍，并对其用于路径规划的可行性进 行了分析。 第三章：根据系统需求提出了自主式车载导航系统的总体设计方案：考虑各 方面因素，分析了相关可选平台，综合选择了合适的软硬件平台；建立了车载导 航系统的基本系统框架，通过面向对象的设计方法设计实现嵌入式g i s 引擎的对 象层次结构，从这些对象映射出导航系统基本功能。 第四章：重点研究了路径规划中的关键问题最优路径问题，包括如何描述路 网，路网的一般表达方法与适合的路网存储结构；着重研究改进蚁群算法求解最 短路径问题，并对其进行仿真比较，得到了较满意的性能；对于蚁群算法的参数 组合问题给出了实验分析方法。 第五章：实现空间查询模块，着重分析空间索引技术，实现了主要的操作算 法。 第六章：总结了论文所做工作，并对未来工作进行了展望。 1 5 2 论文主要研究成果 本论文的主要研究成果表现在以下几个方面： ( 1 ) 设计并实现自助式车载导航系统的基本框架。 ( 2 ) 提出了推荐使用的适合车载导航的路网表达方法和存储结构。 ( 3 ) 实现路径规划模块，并提出了新颖的最优路径算法，应用改进的蚁群算法 求解最短路径。 ( 4 ) 实现空间查询模块，对空间查询的关键技术空间索引技术进行了分析，并 实现了主要的操作算法。 8 第章午载导航系统相戈技术的研究 第二章车载导航系统相关技术的研究 2 1 车载导航系统一般结构和组成 2 1 1 车载导航系统一般结构 固一 一凰 凰 电子科技大学硕士学位论文 自主式车载定位导航系统把大部分应用功能集成到车辆终端上，它在系统的 集成度、技术复杂性和中心式导航系统相比有较大区别。图2 2 为自主式车载导 航系统结构。 导航应用系统 g p s 模块g i s 引擎地图数据 嵌入式系统 图2 2 自主式车载定位导航系统结构 通过比较，我们可以看出这两种体系面向的消费群体不同，实现方式上也存 在较大差异。 中心式定位导航系统，主要应用于应急车辆调度、公共交通管理、警用专用 车辆服务等方面。它更多的是面向集团客户。在我国大多数城市并未建立实时交 通信息中心，应用环境还不成熟，所以中心式定位导航系统还不适合我国国情， 并不是很通用。 自主式定位导航系统对车载终端的软硬件要求较高。自主式导航系统本身存 储有详细的地图数据，能自主导航。并且由于地图数据都在本地，地图读取实时 性较强。自主式导航系统有着更广阔的市场空间，如私人轿车市场等。考虑到当 前我国交通设施及设备通用性，自主式车载定位导航系统更适合在我国应用。 2 1 2 自主式车载导航系统的组成 车载导航系统是综合应用计算机技术、定位技术、g i s 技术等构成的车辆辅 助驾驶系统。它是智能交通系统的重要组成部分之一。车载导航系统的基本构成 如图2 3 所示。其中，地图数据库存储数字地图信息。这些信息表示方式便于计 算机处理与地图有关的信息，如路网拓扑、交通规则和空间位置信息等【1 7 1 。 l o 第二章车载导航系统相关技术的研究 图2 - 3v n s 的基本结构 定位模块利用定位设备实时获取车辆位置信息。目前定位技术主要有：自主 定位、陆基定位和星基定位【哺l 。 车载导航系统中地图匹配模块利用地图匹配算法，使定位系统更精确。利用 g p s 和d r 技术检测到的车辆坐标位置数据、路线轨迹与前进方向在电子地图上 都存在一定的误差。地图匹配通过相关技术匹配车辆行驶路线与电子地图道路， 。 及时修正它们间的误差。 在自主式导航系统中无线通信模块是一个可选模块。它的主要功能是实现车 辆与实时交通信息源问的通信。在智能交通系统发达的国家，由于拥有比较完善 的实时交通信息服务系统，可以通过无线网络获取相关交通信息。但是在国内， 还没有建立起有效的交通信息中心，对交通信息的实时采集、发布都比较困难。 因此，当前我国的车载导航系统通信模块应用还不充分。 路径规划功能是导航系统的基本功能。路径规划的基本策略通常是找出最小 出行代价( 时间、距离) 的路线。在条件允许的情况下，路径规划可以利用实时 路况信息综合规划最优路径。 路线引导主要为驾驶员提供实时的导航信息，纠正其错误的行车路线。导航 信息通常以图像或音频的方式输出。以定位信息和路径规划系统的输出信息为依 据，在电子地图上作路径引导。车辆行进中，系统为了判断车辆是否偏离航迹， 需要将车辆当前位置与规划路线进行不断的匹配，并不断纠正航向，引导车辆驶 向目的地。 电子科技大学硕十学位论文 2 2 嵌入式g i s 2 2 1 嵌入式g i s 特征分析 嵌入式g i s 软件平台包括运行平台和开发平台。运行平台是指嵌入式g i s 软 件运行的硬件环境和软件环境。开发平台是指运行在通用计算机上，针对某种特 定嵌入式系统的一系列软件开发调试工具软件。本文主要讨论嵌入式g i s 运行平 台，它的环境要求与通用计算机的g i s 软件平台( p c - g i s ) 有着明显的差异，如 表2 1 所示。 ( 1 ) 为了提高程序执行速度和系统整体可靠性，e g i s 软件一般都固化在r o m 或f l a s h 存储器中。而p c g i s 程序大都存放在磁盘等大容量存储设备中。 ( 2 ) 尽管嵌入式处理器性能不断提高，片上存储器容量也不断增加，但嵌入式 环境的存储空间仍然紧张，时间上存在一定的实时性要求。因此要求程序编写精 炼，编译工具高效，优化执行速度，同时要求具有很好的可靠性。 表2 - 1p c - g i s 与嵌入式g i s 比较 软件特性嵌入式g i s p c g i s 程序数据存储方式固化在r o m硬盘 程序数据量 小大 代码限制有较大限制基本无限制 程序升级不容易容易 程序通用性不好好 程序容错程度不允许有错可以容忍 程序可靠性高低 可以采用面向对象的程序设计方法来具体实现嵌入式g i s 与p c g i s 。它们在 对象模型的实现方式没有区别，但对象模型的复杂程度不同。p c g i s 要求功能全 面，具有强大的地理分析能力。而嵌入式g i s 要求的是精练、可裁减、实时性。 可以看到，嵌入式g i s 的设计实现要求更加苛刻严格，难道更加大，需要更高的 技术手段解决。 2 2 2 嵌入式g i s 的一般设计原则 尽管半导体芯片技术的高速发展使片上存储器容量不断增加，但嵌入式环境 1 2 第二章车载导航系统相关技术的研究 的存储空间仍然紧张。虽然处理器性能也在不断提高，但嵌入式应用常常有实时 性的要求。然而g i s 空间数据数据量巨大，所需存储空间也相应很大，因此应该 重视存储需求问题。正确处理这一问题应遵循一些一般原则。 1 对于海量的空间数据，在保证精度的前提下应该尽量压缩数据量。空间数据一 般通过将整数代替浮点坐标、稀疏密集采样点等方法压缩数据。 一幅地图很多参数和属性数据或者相同或者为空。因此可以只存储那些不同 的参数数据和属性数据，然后对其建立索引。这样可以更大程度的压缩参数数据 和属性数据。 2 在内存中对空间对象分层分块进行组织和管理。其属性数据单独管理，通过双 向索引与空间对象对应。地图分层分块调入内存，只加载所需图层数据，减少内 存开销。 3 由于成本、体积的限制，嵌入式设备内存有限，因此必须保证嵌入式g i s 应用 程序适应嵌入式设备的低内存环境要求。设计适合的算法，减少实体的内存占用 空间；保持静态变量的数量尽可能少；集中分配应用程序的内存【1 9 】。 2 3 路径规划研究 2 3 1 路径规划一般方法 路径规划是车载导航系统的最基本的功能之一。路径规划速度与质量是车载 导航系统的重要性能指标为了适应嵌入式系统苛刻的运行环境，路径规划算法 需要选择低时间复杂度算法来求解最优路径。 车辆导航的基本功能是引导驾驶员行驶在正确线路上。该导航引导功能的实 现是以路径规划的结果为基础的。最优路径规划问题本质上是图论中带权图求解 最短路径问题。图论中经典的最短路径求解算法是迪杰斯特拉( d i j k s t r a ) 最短路径 算法。但本文将提出一种新颖的基于蚁群算法的最短路径求解算法。 路径规划的一般求解过程是将出行距离、出行时间等最优问题的求解转换为 图论中带权图最短路径问题的求解。其本质是在依据不同因素定义的权重下，求 解最短路径的过程，求解一般过程如下： ( 1 ) 抽象路网拓扑 将道路抽象为线段，道路的交叉口或端点抽象为节点。这样真实道路网被抽 1 3 电子科技大学硕十学位论文 象为图论中的有向图。 ( 2 ) 分配路段权重 考虑不同的权重因素，可以得到不同的全局优化结果。权重的选择对于路径 规划的质量非常重要。 ( 3 ) 应用算法求解最短路径 选择算法复杂度和准确性性能都好的路径规划算法。算法能够扩展，能够参 考实时交通信息做出路径规划。 ( 4 ) 规划路径还原为实际道路 通过地图中道路和抽象路网对应关系，将计算得到的最优路径还原显示在地 图上。 2 3 2d i j k s t r a 算法 上世纪5 0 年代未，迪杰斯特拉( d i j k s t r a ) 算法被首先提出。它是求解图论中非 负权值最短路径问题的一个经典算法。它从起点开始，以该起点作为根节点，构 造一棵最优路径树。从而可以得到从该起点到其它所有节点的最短路径。算法主 要思想：已得到最短路径的节点放入集合s 。算法初始时，只有一个起点在集合s 中。只要有一条终点为节点的最短路径求出，就将加入到集合s 中。算法 完成时，所有节点都加入到s 中，表明最优路径树构造完成，求得起点到其它所 有节点的最短路径，算法结束。下面描述其具体数学模型。 当前找到的从起点到节点的已知的最短路径长度用向量数组分量西表示。 初始化向量数组西：若起点与坼有弧连接，则破取v o v i 上的权值；否则西取 一个很大值，表示无直接相连的边。算法求到的第一条最短路径的终点节点一定 是在与起点直接相连的邻接节点集中。假如( ，) 是算法中首个得到的最短路 径，则满足公式( 2 1 ) 的约束条件，即与起点直接相连的邻接节点中具有最小权值 弧的一对节点。 以= m i n 4l m y 一匕) ( 2 - 1 ) 得到首条最短路径后，并将首条最短路径节点加入集合s 中。以后的最短 路径树加入的弧要么是与起点直接相连的一条弧( ，m ) ，要么是具有中间节点的 一条路径( ，) ，并且中问节点，是集合s 中的节点。其长度为： 4 = m i n d , i k v s ) ( 2 2 ) 1 4 第二章车载导航系统相关技术的研究 得到一条最短路径后，将对应这条最短路径的终点m 放入s ，对其它节点 m r - s ) 根据公式( 2 3 ) 的约束更新西。 4 = r m d , ，哝+ c ( 咋，) ) ( 2 3 ) 公式( 2 3 ) 中，表示存在于s 中已求出最短路径的节点。c ( v k ，v i ) 是对应弧的 权值。重复以上过程将产生从起点到其它各节点的最短路径树。对于求解指定节 点对的一条最短路径，当发现指定节点归入集合s 时，则表明指定节点对的最短 路径已求出，算法可以提前停止。 对于带权图g ，哦功表示从起点到v 当前的最短路径长度：氟叻表示节点v 是否加入到集合s 即是否求出最短路径；p ( 功表示1 ，为终点的路径轨迹指针；c ( t 7 c i 是节点i 到节点，的非负权值。对于起点j 到终点t ，求解具有最小权值和的最 短路径，具体算法描述如下： 步骤l ：算法开始时，根据公式( 2 4 ) 初始化节点相关变量； d ( v ) ： oy _ j ；七( ，) ：f a l s e ；烈d ： ) ( 2 - 4 ) 【 ，j 步骤2 ：根据公式( 2 5 ) 约束，从钉叻= f a l s e 还未找到最短路径的节点中选择 一个具有最小权值的节点y ，节点1 ，即是第一条最短路径的一个端点，标记节点 v 为已找到最短路径的节点； d ( y ) = m i n d ( v , ) i 七( k ) - - - f a l s e ，一y ) ( 2 5 ) 步骤3 ：根据公式( 2 - 6 ) 对于每一个坳= f a l s e 的节点，与权沪t r u e 的节点构 成的节点对计算并更新d e ) ，并将放入p 们链，令坳= t r u e ； d ( j ) = m i n d ( j ) ，d ( f ) + “f ，) )( 2 - 6 ) 步骤4 ：重复执行步骤3 ，逐步构造一棵最优路径树，当指定的终点t 的氟0 = t r u e 时，即指定终点加入s ，表明求到起点s 到终点t 的最短路径： 步骤5 ： 由终点t 到起点s 的p 指针链，即为最短路径轨迹； 迪杰斯特拉算法优点是，具有算法稳定性，即只要两点间连通，存在最短路 径就能通过算法找到。其缺点是，算法在所有方向上进行搜索，并没有考虑路网 的空白j 分布特性，当路网节点很多时，搜索开销会很大，效率很低，时间复杂度 为o ( n 2 ) 。 电子科技大学硕十学位论文 2 3 3a 。算法 2 3 3 1a 算法基本思想 启发式搜索是利用现有信息，对搜索过程给予一定提示，指导优先搜索可能 性较大的目标。目前最有效的启发式搜索算法是h a r t 等人提出的a 算法【2 0 1 。该 算法主要思想是利用已知的全局信息指导选择下一个候选节点。这个信息是一个 估计，估计当前节点距终点的距离。这个启发信息作为衡量该节点处于最优路线 上的可能性程度。对于可能性大的节点给予优先搜索，从而有针对性的搜索，提 高了算法的效率。 建立a 。算法数学模型，假设估计函数r ，当前节点y 的估计函数定义为： f(y)=g(v)+h(v)(2-7) 颤功表示起点到当前节点1 ，的实际费用。h ( v ) 表示节点1 ，到终点费用的一种 估计。若h 。( ，) = 0 表示没有利用启发信息，这时a 。算法就蜕变为迪杰斯特拉算法。 这说明迪杰斯特拉算法是a 算法的一种特例。 在选择估计函数h 。( ，) 的具体形式时应当依据实际情况选择合适的估计函数。 同时估计函数h 。( v ) 要满足其估计值不能大于节点1 ，到终点的实际费用这一相容 性条件。可以证明，若问题同时满足相容性条件并存在最优解，则最优路径一定 能够被求出。 在实际路网中可以考虑出行距离最短的估计函数，其定义为： f 。( v ) = s - ( ，) = g ( v ) + h 。( ，) = d ( v ) + d 。( v )( 2 8 ) s 。( 1 ，) 表示出行距离；d ( y ) 表示起点到节点，的实际距离；d 。( v ) 表示节点 ， 与终点间的直线距离，它是所有可能中的最短距离，满足相容性条件。 2 3 3 2a 算法描述 辅助链表p 为已经生成但未扩展的节点集合链表，即已经创建节点的数据结 构的集合。辅助链表e 为己经扩展的节点集合链表，即产生该特定节点的所有后 继节点的集合。在算法完成后，链表e 就是已求到的最短路径的节点集合