（计算机应用技术专业论文）汽车导航系统中数据检索功能的研究与实现.pdf

东北大学硕士学位论文摘要 汽车帚耵漯统中数据嗡黝能白勺：研究与实现 摘要 众所周知，近年来尤其是进入2 l 世纪，汽车工业已经成为世界的支柱产业，汽车 在日常生活和工作中起的作用也越来越突出。汽车导航正是在这样的背景下发展起来的 - - i 新型技术。目前国内推出的一些导航系统还不太成熟，不能在车载系统中得到广泛 应用，尤其是其功能比较单一，不能满足用户的要求。 本文是在已有模型的基础上对导航系统中的数据检索模块进行了深入的研究。数据 检索功能的加入就是为了让汽车导航系统摆脱单一功能的缺点，这样使得汽车导航系统 看起来更像一个车载综合信息系统。 数据检索功能在汽车导航系统中占有很重要的地位，为了能提升整个检索的性能， 本文在以下几个方面进行了研究： ( 1 ) 修改了已有部分数据的存储结构，为一些数据建立了索引，使得在查找起来变 得很容易。 ( 2 ) 重新设计了一个内存管理器，解决了w i n d o w sc e 系统的很容易出现内存碎片 的问题。 ( 3 ) 修改了已有系统的检索控制方式，引入线程池机制，使得用户在检索大量数据 的时候可以先浏览部分检索结果，同时在用户浏览结果的时候后台程序可以继续执行检 索操作。 关键词：汽车导航系统：数据检索；索引；内存管理器；线程池 i i 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n d i m p l e m e n t a t i o n o fd a t as e a r c h f u n c t i o nf o rv e h i c l en a v i g a t i o ns y s t e m a b s t r a c t a se v e r y o n ek n o w s ，e s p e c i a l l ye n t e r i n g2 1 s tc e n t u r yi nr e c e n ty e a r s ，t h ea u t oi n d u s t r y h a sa l r e a d yb e c o m et h ep i l l a ri n d u s t r yo ft h ew o r l d , i ti sm o r ea n dm o r eo u t s t a n d i n gt h a tt h e a u t o m o b i l ef u n c t i o ni nt h ed a i l yl i f ea n dw o r k v e h i c l en a v i g a t i o ns y s t e mh a sg r o w nt ob ea n e wt e c h n o l o g yi ns u c hab a c k g r o u n d n o w a d a y s ，t h ev e h i c l en a v i g a t i o ns y s t e mi sn o t m a t u r e ，s ot h es y s t e md o e sn o ta p p l yw i d e l y f u n c t i o no fm a n yo ft h ev e h i c l en a v i g a t i o n s y s t e mi ss i m p l e ，s oi tc a n ts a t i s f yt h eu s e r t h i sp a p e rd o e sad e 印r e s e a r c ho ft h ed a t as e a r c hm o d u l ew h i c hi sp a r to fv e h i c l e n a v i g a t i o ns y s t e mt h a th a sb e e nu s e d t h ep u r p o s eo fa d d i n gt h ed a t as e a r c hf u n c t i o nt o v e h i c l en a v i g a t i o ns y s t e mi st og e tr i do ft h es h o r t c o m i n gt h a th a sb e e nm e n t i o n e da b o v e t h i sm a k e st h ev e h i c l en a v i g a t i o ns y s t e mt ob el o o k e dl i k eai n t e g r a t e di n f o r m a t i o ns y s t e m d a t as e a r c hm o d u l ei sam o s ti m p o r tp a r to fv e h i c l en a v i g a t i o ns y s t e m i no r d e rt o p r o m o t et h ep e r f o r m a n c eo fd a t as e a r c hm o d u l e ，t h i sp a p e rd o s es o m er e s e a r c ho ns e v e r a l a s p e c t sa sf o l l o w s ： ( 1 ) f o r m a t so fd a t as t o r a g eh a v eb e e nc h a n g e d i n d e x e sh a v eb e e ns e tu pf o rs o m ed a t a i no r d e rt os p e e dt h ed a t as e a r c h ( 2 ) an e wm e m o r ym a n a g e rh a sb e e ni m p l e m e n t e di no r d e rt og e tr i do f t h ep r o b l e mt h a t t h e r ea l ea l w a y sm e m o r yp i e c e sw h i l eu s i n gt h em e m o r ym a n a g e ro f w i n d o w sc e ( 3 ) t h em e c h a n i s mo ft h r e a dp o o lh a sb e e ni n t r o d u c e di no r d e rt oc h a n g et h ec o n t r o l m e t h o do fd a t as e a r c h s u c hc h a n g em a k e si tp o s s i b l et h a tt h es y s t e mc a ns e a r c ho n ep a r to f t h er e s u l tw h e nt h eu s e ri sr e a d i n gt h eo t h e r p a r to f t h er e s u l t k e yw o r d s ：v e h i c l en a v i g a t i o ns y s t e m ；d a t as e a r c h ；i n d e x ；m e m o r ym a n a g e r ；t h r e a d sp o o l 1 1 1 声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：匕痧 日期：z o 缉拿月乒r 日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章绪论 第一章绪论 1 1 研究背景 车辆导航系统( v e h i c l en a v i g a t i o ns y s t e m ，v n s ) 的概念最初起始于二十世纪六十年 代末。当时美国公路局提出了一种电子路径引导系统( e r g se l e c t r o nr o u t eg u i d e s y s t e m ) ，这是一种具有无线电路径引导能力的导航系统，用于控制和疏导交通。 全球定位系统( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 是美国从上个世纪7 0 年代开始研制， 于1 9 9 4 年全面建成，具有在海、陆、空进行全方位实时三维导航与定位能力的新一代 卫星导航与定位系统【1 】。汽车卫星导航系统正是基于全球定位系统( g p s ) 研制而成的用 于汽车导航的高科技电子产品。在过去的1 0 多年中，由于全球定位系统定位技术的广 泛应用，更加推进车辆定位与导航系统的发展。 车载导航系统一经问世，即显示出强大的生命力和广阔的应用前景，并产生了巨大 的社会和经济效益，调查显示，进入9 0 年代后期，随着信息技术和通信技术的发展， 以g p s 导航和地图数据匹配技术为基础的汽车导航产品开始进入市场，并高速增长 2 1 。 由于巨大的市场潜力和不可估量的发展前景，日本几乎所有的汽车生产厂家都参加 了这一高科技角逐，仅近几年投入市场的新系统就有3 0 多个。如日本的宏达、尼桑、 本田、马自达、三菱以及松下、先锋、阿尔派、健伍等公司都已开发出自己的车载导航 产品。世界其它发达国家如美国、德国、荷兰不甘落后，力图在该市场占有一席之地。 目前在欧洲，由飞利浦、西门子开发的车载导航系统1 9 9 5 年已在雷诺、菲亚特等大众 化民用车辆上使用i 奔驰- s 系列、宝马- 7 系列，从1 9 9 4 年起，出厂车辆已将g p s 车载 导航系统列在选装清单上。此外，根据( g p sw o r d 杂志千u 登的美国工业发展研究机 构的预测，到2 0 0 5 年，日本、北美和欧洲每年将有t 5 0 0 2 5 0 0 万套产品售出，在2 0 1 0 2 0 1 5 年间，约有5 0 的汽车在出厂时就已装备了车载导航系统，在以后时间里该系统的普 及率将会逐渐提高到1 0 0 吼 我国在车载导航系统方面的研究起步晚、积累少并且基础差。我们有必要借助于国 外的先进技术来发展适合中国市场的导航系统。 本课题正是基于东软a v n c 部门和日本阿尔派公司共同承担开发的车载导航系统 的基础之上进行研究的。 1 2 国内外研究现状 汽车导航及定位是在全球定位系统( g p s ) 的基础上发展起来的一门新型技术，自 1 9 9 4 年由美国国防部发布全球定位系统( g p s ) 来，其g p s 导航技术在民用市场发展迅 速，尤其是近年来，随着微电子技术的迅速发展和g p s 的芯片制造成本的迅速下降， 东北大学硕士学位论文 第一章绪论 g p s 导航技术的应用已经扩展到各个领域，进入9 0 年代后期，随着信息技术和通信技 术的发展，它在汽车上的应用获得了迅猛发展。以g p s 导航和地图数据匹配技术为基 础的汽车导航产品开始进入市场，并以高速增长，目前已成为g p s 最大的消费市场。 为了进一步提高汽车导航和定位的应用技术和促进汽车导航系统的发展，日本采用修正 式d - g p s 技术，利用f m 频道进行误差修正，提高了汽车的定位精度，可达到1 0 米精 度的定位等级【4 1 。再辅以道路交通通信技术及自导式电子地图光盘，其覆盖率已达到 8 0 的日本地区。可以看到，智能车载导航信息系统一经问世，即显示出强大的生命力 和广阔的应用前景，并产生了巨大的社会和经济效益。 汽车导航定位系统是建立在全球定位系统( g p s ) 之上的，它通过g p s 实现汽车的实 时定位 5 j 。g p s 全球定位系统主要由空间部分、地面监控部分和用户接收机三大部分组 成。空间部分使用2 4 颗高度约在2 万千米高空的卫星组成的卫星星耐6 】。2 4 颗卫星均 为近圆形轨道，运行周期约为l1 小时5 8 分，分布在6 个轨道面上( 每个轨道面4 颗1 ， 轨道倾角为5 5 度【j 7 1 。卫星的这种分布使得在全球的任何地方、任何时间都可观测到4 颗以上的卫星，并能保持良好定位解算精度的几何图形，这就提供了在时间上连续的全 球导航能力瞵j 。 g p s 信号接收机的任务是能够捕获到按一定卫星高度截止角所选择的待测卫星的 信号，并跟踪这些卫星的运行，对所接收到的g p s 信号进行变换、放大和处理，以便 测量出g p s 信号从卫星到接收机天线的传播时间，解译出g p s 卫星所发送的导航电文， 实时地计算出g p s 信号接收机的三维位置f 9 】。g p s 接收机可接收到用于校准时间的准 确至纳秒级的时间信息，用于预报未来几个月内卫星所处概略位置的预报星历，用于计 算定位时所需卫星坐标的广播星历。g p s 汽车导航定位系统由卫星定位、电子地图和 车载嵌入式系统组成。汽车导航系统接收g p s 所传送的卫星信号，透过三角定位法， 得到车辆的即时位置，再配合详尽的地理资料库和电脑运算，将车辆经过的轨迹显示在 液晶显示屏上。这套系统主要由主机、显示屏、操作键盘( 遥控器) 和天线组成。车辆在 行驶过程中可以在显示屏上实时看到自己车辆所在的位置，当驾车人把目的地输入后， 该系统会在几秒钟内计算出行驶路线，并在途中每一个路口到达前提示正确的行驶方 向。这样即使是初来乍到的驾车人也可以很方便的到达目的地。汽车卫星导航系统具有 输入目的地，快速生成最佳行驶路径，车辆高精度卫星定位，路口语音提示行驶方向， 导航画面无级缩放，导航画面随定位自动漫游，导航信息多窗口显示，地理信息多种方 式查询，目的地地址多种输入方式，上网、办公等功能。g p s 汽车卫星导航系统使用的 软件是基于w i n d o w s 2 0 0 0 和w i n d o w s c e 两种版本的系统导航软件和各城市导航数据库 ”。汽车导航和地理信息系统( g i s ，g e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 都离不开基础地理 信息和地图数据。 目前在欧洲和美国研发的智能车载导航系统，它们主要采用中央导航式，即使用地 面监控中心进行导航等多方面服务。 东北大学硕士学位论文 第一章绪论 ( 】) 它在汽车上应用的基本特点：第一，具有全天候、全球性的精确测定汽车的三 维位置，即经度、纬度和高度的能力，而基本上不受天气变化、地理环境和时间的影响； 第二，测量快捷，只需几秒钟就可准确定位；第三，它的隐蔽性强，不产生无线电干扰， 在测量定位时，只接收卫星信号而不发射任何信号。 ( 2 ) 给汽车提供出行路线规划和进行导航。提供出行路线规划是汽车导航系统的一 项重要功能，它包括自动线路规划和人工线路设计。驾驶者确定起点和目的地，由计算 机软件按要求自动设计最佳行驶路线，包括最快的路线、最简单的路线、通过高速公路 路段次数最少的路线等的计算。人工线路设计是由驾驶者根据自己的目的地设计起点、 终点和途径点等，自动建立线路数据库。线路规划完毕后，显示器能够在电子地图上显 示设计线路，并同时显示汽车运行路径和运行方法。 ( 3 ) 车辆跟踪。利用g p s 和电子地图可以实时显示出车辆的实际位置，并任意放大、 缩小、还原、换图；可随目标移动，使目标始终保持在屏幕上；还可实现多窗口、多车 辆、多屏幕同时跟踪。利用该功能可对重要车辆和货物进行跟踪运输。 ( 4 ) 对车辆实行调度指挥和紧急援助。中心可以监测区域内车辆运行状况，对被监 控车辆进行合理调度，指挥中心也可随时与跟踪目标通话，实行管理。通过g p s 定位 和监控管理系统可以对有险情或发生事故的车辆进行紧急援助。监控台的电子地图显示 求助信息和报警目标，规划最优援助方案，并以报警声光提醒值班人员进行应急处理。 ( 5 ) 在车上进行信息查询。为用户提供主要建筑物地理位置标示，如旅游景点、宾 馆、医院等建立数据库，用户能够在电子地图上根据需要进行查询，查询资料可以文字、 语言及图像的形式显示，并在电子地图上显示其位置。同时，监测中心可以利用监测控 制台对区域内的任意目标所在位置进行查询，车辆信息将以数字形式在控制中心的电子 地图上显示出来。 目前在国内，也已有部分厂商和研究单位推出了一些车载导航定位系统，但要么由 于技术简单，定位精度不够，要么由于成本昂贵，不能被一般用户接受，因而不能在实 际车载系统中得到广泛的应用。要将这种系统实用化，则必须在提高精度的同时大幅度 降低成本。 g p s 汽车导航定位系统采用了先进的导航定位技术，具有成本低、体积小和可靠性 高等特点。本系统最大特点是将两种优势互补系统( g p s 和u s b ) 组合到一起，实现高精 度连续导航定位。 在开发g p s 汽车导航定位系统时，要降低系统的成本，就必须对系统进行必要的 简化，以使用低廉的单片机实现。同时还要能达到一定的精度，有较好的重复性和机动 性等等。具体的车载装置结构目前的应用系统可分为3 个层次：自主导航系统、单向通 信系统和双向通信系统。 ( 1 ) 自主导航系统，它可以实时提供用户车辆的位置和速度，并能将用户的位置显 示在数字地图上。自主导航系统在车内装有定位装置和电子导航地图，能提供行驶中的 东北大学硕士学位论文 第一章绪论 车辆定位和静态路径引导功能。相关信息的收集、传送、处理和分析均在车上独立完成， 不需与外部进行通信联系。其缺点是不能提供动态路径引导功能，也不能向交通中心报 告当前车辆的状况。 ( 2 ) 智能可视车载g p s 汽车导航定位系统。在此系统中我们将现有的g p s 汽车导 航定位系统和地理信息系统进行整合，不但实现导航定位，而且能够实现大量城市或地 区地图的存储与自动切换，使得汽车向着智能型方向迈进。单向通信系统由交通信息中 心和车载导航设备组成，前者负责采集、分析和处理实时交通信息并向路网中行驶的车 辆广播，用户可随时通过车载信息接收装置获取最新的道路状况，以选择最佳路线。与 自主导航系统相比，单向通信系统可提供动态的实时路径引导功能，其缺点是信息中心 不能接收车辆的反馈信息，无法获取交通流量即时分布情况，同时就是必须有一个这样 集中的信息中心，这个实现起来很难。 ( 3 ) 智能汽车综合g p s 汽车导航定位接入系统。实现真正意义上的智能汽车的概念， 它将具有广阔的市场前景，它的应用领域将是每一个汽车的车主。着手建立自己的控制 中心，并在此基础上提供独有的信息或其它类型的服务。双向通信系统可在信息中心和 出行者之间实现双向信息交换，交通中心在为移动车辆提供信息服务的同时，也能获取 车辆的当前位置、目的地和预行路线等信息，因而能进行准确的拥堵预报和即时流量疏 导，从而实现对交通流的动态监控和管理，这正是智能交通系统( i t s ) 核心概念的体现。 1 3 存在的问题 目前国内少数掌握g p sg i s 的厂商基本立足于行业内应用，比如银行运钞车的定 位跟踪，电站维修车的车载定位系统，其局限性很大。近年来有部分厂商也在从事消费 类汽车自主导航产品的开发，但没有解决数据不完整和成本偏高的问题，且大多数厂商 实质上是提出了汽车自导航的解决方案，而真正一体化实用普及型的汽车自导航产品， 目前国内还没有出现。同时市场上已经出现的汽车导航功能太简单，大部分的车载汽车 导航都只有个线路引导的功能，而随着用户的要求越来越高，这个简单的功能显然是 不能满足人们的要求，用户想要获得更多的信息，这显然是目前的导航系统不能达到的。 1 4 论文研究主要问题简介 本次设计的导航系统就是为了要解决功能单一这个缺点，本次开发的导航系统可以 说已经不再是一个单的只有引导功能的车载系统，而是一个车载综合信息系统，在这 个车载综合信息系统中，可以奄到几乎所有的全国信息，同时用户还可以自己设定一些 数据信息自己管理，使这个系统变得更加人性化。在这样的一个系统中数据的处理就显 得非常重要，各个功能的实现可以说都依赖于数据。本文所研究的就是如何实现导航系 统中快速稳定的数据检索。 数据检索系统在整个导航系统中的地位如图1 1 ： 一一 东北大学硕士学位论文第一章绪论 图1 1 导航系统构造简图 f i g 1 1b r i e fs t r u c m r oo f n a v i g a t i o ns y s t e m 由上图可以看到导航系统中的几个基本模块都和数据检索模块有密切的联系。下面 介绍一下本论文的组织结构： 第一章说明选题的背景、国内外研究现状、存在的问题、论文的主题以及组织结构。 足。 第二章介绍导航系统所需要的理论知识。 第三章介绍对部分检索数据的存储结构的优化。 第四章介绍了导航系统的内存的管理器。 第五章介绍了数据检索模块的结构优化及具体检索功能的实现。 第六章对本课题进行了总结，总结了本次设计的特殊之处，同时也指出了存在的不 东北大学硕士学位论 第二章导航系统的相关理论知识 第二章导航系统的相关理论知识 2 1 嵌入式系统简介 在当前数字信息技术和网络技术高速发展的后p c ( p o s t - p c ) 时代，嵌入式系统已经 广泛地渗透到科学研究、工程设计、军事技术、各类产业和商业文化艺术以及人们的日 常生活等方方面面中。随着国内外各种嵌入式产品的进一步开发和推广，嵌入式技术越 来越和人们的生活紧密结合。1 9 7 0 年左右出现了嵌入式系统的概念，此时的嵌入式系 统很多都不采用操作系统，它们只是为了实现某个控制功能，使用一个简单的循环控制 对外界的控制请求进行处理。当应用系统越来越复杂、应用的范围越来越广泛的时候， 每添加一项新的功能，都可能需要从头开始设计，没有操作系统已成为一个最大的缺点 了。c 语言的出现使操作系统开发变得简单。从上世纪8 0 年代开始，出现了各种各样 的商用嵌入式操作系统百家争鸣的局面，比较著名的有v x w o r k s 、p s o s 和w i n d o w sc e 等，这些操作系统大部分是为专有系统而开发的。另外，源代码开放的嵌入式l i n u x ， 由于其强大的网络功能和低成本，近来也得到了越来越多的应用【l “。嵌入式导航系统就 是基于w i n d o w sc e 操作系统开发的。 嵌入式系统以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用 系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统【l m 。它一般由嵌 入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序四个部分组成，用 于实现对其他设备的控制、监视或管理等功能。嵌入式系统一般指非p c 系统，它包括 硬件和软件两部分。硬件包括处理器、微处理器、存储器及外设器件和i o 端口、图形 控制器等。软件部分包括操作系统软件( 要求实时和多任务操作) 和应用程序编程。有时 设计人员把这两种软件组合在一起。应用程序控制着系统的运作和行为，而操作系统控 制着应用程序编程与硬件的交互作用。 嵌入式系统通常包括构成软件的基本运行环境的硬件和操作系统两部分。嵌入式系 统的运行环境和应用场合决定了嵌入式系统具有区别于其它操作系统的一些特点。 ( 1 ) 嵌入式处理器 嵌入式处理器可以分为三类：嵌入式微处理器、嵌入式微控制器和嵌入式 d s p ( d i g i t a ls i g n a lp r o c e s s o r ) 。 嵌入式微处理器就是和通用计算机的微处理器对应的c p u 。在应用中，一般是将 微处理器装配在专门设计的电路板上，在母板上只保留和嵌入式相关的功能即可，这样 可以满足嵌入式系统体积小和功耗低的要求。目前的嵌入式处理器主要包括p o w e r p c 、 m o t o r o l a6 8 0 0 0 和a r m 系列等。 嵌入式微控制器又称为单片机，它将c p u 、存储器( 少量的r a m 和r o m ，或两者 都有) 和其它外设封装在同一片集成电路里，常见的有8 0 5 1 。 一6 一 东北大学硕士学位论 第二章导航系统的相关理论知识 嵌入式d s p 专门用来对离散时间信号进行极快的处理计算，提高编译效率和执行 速度。在数字滤波、f f t 、谱分析、图像处理的分析等领域，d s p 正在大量进入嵌入式 领域。 r 2 1 微内核结构 大多数操作系统至少被划分为内核层和应用层两个层次。内核只是提供基本的功 能，如建立和管理进程、提供文件系统、管理设备等，这些功能以系统调用方式提供给 用户。一些桌面操作系统，如w i n d o w s 、l i n u x 等，将许多功能引入内核，操作系统的 内核变得越来越大。使得占用的资源增多，剪裁起来很麻烦。所以这样结构不适应嵌入 式系统。 大多数嵌入式操作系统采用了微内核结构，内核只是提供基本的功能，比如任务的 调度、任务之间的通信与同步、内存管理、时钟管理等。其它的应用组件，比如网络功 能、文件系统、g u i 系统等均工作在用户态，以系统进程或函数调用的方式工作。因而 系统都是可裁减的，用户可以根据自己的需要选用相应的组件。 ( 3 ) 任务调度 在嵌入式系统中，任务即线程。大多数的嵌入式操作系统支持多任务。多任务运行 的实现实际是靠c p u 在多个任务之间切换、调度。每个任务都有其优先级，不同的任 务优先级可能相同也可能不同。任务的调度有三种方式：可抢占式调度、不可抢占式调 度和时间片轮转调度。不可抢占式调度是指一个任务一旦获得c p u 就独占c p u 运行， 除非由于某种原因，它决定放弃c p u 的使用权；可抢占式调度是基于任务优先级的， 当前正在运行的任务可以随时让位给优先级更高的处于就绪态的其它任务；当两个或两 个以上任务有同样的优先级，不同任务轮转地使用c p u ，直到系统分配的c p u 时间片 用完，这就是时间片轮转调度。 目前，大多数嵌入式操作系统对不同优先级的任务采用基于优先级的抢占式调度 法，对相同优先级的任务则采用时间片轮转调度法。 ( 4 ) 内存管理 针对有内存管理单元( m h 仉7 ) 的处理器设计的一些桌面操作系统，如w i n d o w s 和 l i n u x ，二者都使用了虚拟存储器的概念。虚拟内存地址被送到m m u 。在这里，虚拟 地址被映射为物理地址，实际存储器被分割为相同大小的页面，采用分页的方式载入进 程。一个程序在运行之前，没有必要全部装入内存，而是仅将那些当前要运行的部分页 面装入内存运行。 大多数嵌入式系统针对没有m m u 的处理器设计，不能使用处理器的虚拟内存管理 技术，采用的是实存储器管理策略。因而对于内存的访问是直接访问，它对地址的访问 不需要经过m m u ，而是直接送到地址线上输出，所有程序中访问的地址都是实际的物 理地址；而且，大多数嵌入式操作系统对内存空间没有保护，各个进程实际上共享一个 运行空间。一个进程在执行前，系统必须为它分配足够的连续地址空间，然后全部载入 一7 东北大学硕士学位论 第二章导航系统的相关理论知识 主存储器的连续空间【l ”。 由此可见，嵌入式系统的开发人员不得不参与系统的内存管理。从编译内核开始， 开发人员必须告诉系统这块开发板到底拥有多少内存；在开发应用程序时，必须考虑内 存的分配情况并关注应用程序需要运行空间的大小。另外，由于采用实存储器管理策略， 用户程序同内核以及其它用户程序在一个地址空间，程序开发时要保证不侵犯其它程序 的地址空间，以使得程序不至于破坏系统的正常工作，或导致其它程序的运行异常；因 而，嵌入式系统的开发人员对软件中的一些内存操作要格外小心。 2 2w i n d o w sc e 简介 简单地说，w i n d o w sc e 就是基于掌上型电脑类的电子设备操作系统。其中c e 中 的c 代表袖珍( c o m p a c t ) 、消费( c o n s u m e r ) 、通讯能力( c o n n e c t i v i t y ) 和伴侣( c o m p a n i o n ) ， e 代表电子产品( e l e c t r o n i c s ) 。 w i n d o w sc e 是一种新型的m i e r o s o f tw i n d o w s3 2 位操作系统，是一个轻量级、多 线程的操作系统。与w i n d o w s9 5 9 8 和w i n d o w sn t 不同的是w i n d o w sc e 所有源代码 都由微软自行开发，其操作界面虽来源于w i n d o w s 9 5 9 8 ，但w i n d o w s c e 是基于w i n 3 2 a p i 重新开发的新型信息设备平台。w i n d o w sc e 具有模块化、结构化、基于w i n 3 2 应 用程序接口和与处理器无关的特点。w i n d o w bc e 不仅继承了传统的w i n d o w s 图形界面， 并且在w i n d o w sc e 平台上可以使用w i n d o w s9 5 9 8 上的编程工具( 如v i s u a lb a s i c 、 v i s u a lc + + 等) ，可以使用同样的函数以及同样的界面风格，使绝大多数的应用软件只需 简单的修改和移植就可以在w i n d o w sc e 平台上继续使用【l 钔。 2 - 3 导航系统检索模块简介 本小节对汽车导航系统中检索模块的功能做了一个系统分析，同时为了让介绍更加 易懂，论文加入了许多图例，结合系统运行的过程来论述。 2 3 1 问题定义 在整个导航系统中，n o t e ( 导航系统的信息检索模块) 处于很重要的位置，它的功 能主要分为三种：检索、地点登陆和l i s t 生成，所有的功能都要通过函数实现。 检索是一个信息查询的过程，比如说用户想到一个不是很熟悉的地方，或是只知道 电话号码，或是只知道属于哪一类设施，或是只知道发音，如果没有检索，用户就会变 得束手无策了。因此导航系统提供了检索功能。在你到达一个陌生的地方或者不是太熟 悉的地方，想查到一些你想去的地方( 例如你出外旅游) ，你就可以利用到导航系统中的 地点查询、电话号码查询、地图上的搜索、以及自车位置的周边搜索来满足你的要求。 系统然后会根据你的要求来计算出路径，你就会按照这个路径驾车到达你想去的地方。 在你整个驾车行驶过程中，导航系统会根据g p s 计算出汽车现在所处位置，让你清楚 你现在的方位。同时可以根据这个位置随时改变自己想去的地方。导航可以说是帮助你 东北大学硕士学位论第二章导航系统的相关理论知识 正确行驶的指示器。例如会把哪条道路堵车、哪条道路不通等等信息提供给你，以便让 你有所准备。地图数据查询都会帮助你完成这些功能。 检索就是根据一定的条件( 电话号码、名称、类别等) 查询满足条件的信息的过程。 下面是这些工作以及一些术语的介绍。 所谓的地点包括目的地、u s e r m a r k 、经由地和自宅等，对于这些标记可以进行登录， 删除，变更等一系列操作。下面分别简单介绍一下： ( 1 ) 目的地 登录目的地，将指定地点设定为目的地，主要是为了计算行车路线，然后给自车行 驶以正确的指导。删除目的地很容易理解，值得一提的是在删除目的地的同时也会删除 为这个目的地所设定的所有经由地。目的地履历是所有登记过的目的地和经由地f 行车 经过的地点) 的历史，数量保持在一定范围内。在一次设定过程中，只能设定一个目的 地，经由地可以任意设定【l5 1 。如图2 1 ，图中插小旗的就是目的地。 图2 1 目的地示意图 f i g 2 1 a s k e t c h m a p o f d e s t i n a t i o n ( 2 ) u s e r m a r k u s e r m a r k 是用户在整个导航过程中自己设定的标志，此标志在沿路行驶时，可以 有提示声音( 也可以没有) 。u s e r m a r k 就是你想在地图上标明的地方。比如你经常去的地 方或你想在驾车过程中想留意的地方。对于u s e r m a r k 可以进行设定，删除，图标变更 等操作。也可以将u s e r m a r k 作为目的地或对经由地进行设定。如图2 2 ：十字光标处的 标记就是设定的m a r k 。 东北大学硕士学位论 第二章导航系统的相关理论知识 图2 2 m a r k 示意图 f i g 2 2as k e t c hm 印o f m k ( 3 ) 经由地 经由地是针对目的地而言的，在没有目的地的情况下也不可能让你设定经由地，只 有设定了目的地，在计算路线过程中才可以设定经由地，设定经由地的途径也很多，可 以通过各种检索来设定。经由地的设定，删除都不会影响目的地，只是影响计算出来的 路，而目的地的删除会把它所带的经由地全部删除。如图2 3 ，图中有个数字l ，的红色 标记就是设定的经由地。 图2 - 3 经由地示意图 f i g 2 3as k e t c hm 印o f p 如tp o i m ( 4 ) 自宅 自宅就是用户自己的住所。对自宅的操作有登录、删除、变更和自宅诱导。自宅诱 导是将自宅设定为目的地，然后开始算路，通俗的说，就是找到一条可以到家的路。一 般说来，自宅不能登录为目的地履历。 2 3 2 设计环境 第三代导航的c p u 采用n e c 公司的r i s c 处理器v 8 3 1 ，运算速度达到1 0 0 m i p ， 具有4 k bd c a c h e 和4 k bi - c a c h e 。内存为4 m bf i s hr a m 用来存储程序的执行代码， 4 至8 m b 的d r a m 用来运行程序，以及1 m b 的s r a m 用来记忆程序运行中需要记忆 一1 0 东北大学硕士学位论 第二章导航系统的相关理论知识 的各种状态。显示芯片采用n e c 公司的m p d 7 2 2 5 2 ，配备1 m b 或4 m b 的显示内存， 实现v g a 输出，显示方式为8 b i r + 3 l a y e r + c u r s o rl a y e r ，屏幕采用s h a r p 或p a n a s o n i c 的液晶显示器，显示分辨率为4 0 0 * 2 3 4 d o t ，其中8 b i t 的一般l a y e r 可以分别同屏显示 6 5 5 3 6 种颜色中2 5 6 种，而c u r s o r 可以显示分辨率为3 2 * 3 2 d o t3 种颜色的光标。地图的 存储介质是c dr o m 或者是d v dr o m ，相应采用c dr o m 驱动器和d v dr o m 驱 动器。 地图数据信息处理技术就是从d v d 上读出地图数据进行一些用户自定义的检索来 完成一些特定的操作。它是导航系统的一个小模块，所依托的是整个导航系统。离开了 导航系统这个模块就失去了它的作用。 基本地图数据信息检索数据流程图如图2 4 ： 图2 4 数据检索流程 f i g 2 4f l o wc h a r to f d a t as e a r c h 第三代导航的硬件组成如图2 5 所示： 东北大学硕士学位论第二章导航系统的相关理论知识 图2 5 硬件结构示意图 f i g 2 5s t r u c t u r eo f h a r d w a r e 导航设备通过特定的接口标准同汽车音响连接，另外还可以连接t vt u r n e r ，h f t ， r e a rc a m e r a 等相应的外围设备。 2 4 小结 本章简单介绍了嵌入式系统开发的一些特点，同时对本导航系统所依托的开发环境 w i n d o w sc e 进行了简单的介绍，在本章的最后对导航系统中检索模块进行了一个大概 的介绍。 1 2 一 东北大学硕士学位论文 第三章导航系统中的数据存储 第三章导航系统中的数据存储 3 1 导航系统中数据存储的特点 地图数据的支持是导航的基础。地图数据通过某种手段和某种格式以数字化的方式 存入磁盘中，同时将地理事物的属性与其挂接，从而保证使用者能够根据需要进行查询 和检测。而地图格式是地图数据保存的标准，我们必须按照这种格式将所需要的数据找 出以使用。所以说数据格式设计的好坏直接决定了检索的性能，数据按照什么样的格式 进行存储不是随便决定的，都是根据每种检索的特点进行设计的。 汽车导航系统所用到的数据是以文件的形式保存在d v d 光盘中，每种检索所用到 的数据不是同一个格式，这是因为每种检索都有不同的特点，比如说地址检索用到的数 据和设施检索用到的数据就不能以一种相同的格式保存。同时由于数据量巨大，如果不 对存储在d v d 光盘上的数据加以记录和组织，每进行一次查询都要扫描整个数据盘， 这样就会严重影响系统性能，检索速度会慢的让人无法接受。因此，必须将数据在d v d 光盘中位置加以记录和组织，通过在内存的一些计算来取代对光盘漫无目的的访问，以 便提高系统的效率。导航系统涉及到的数据种类很多，各种复杂的数据的大量的堆积在 一起，所以有必要为数据设计索引结构，这样能提高系统的效率。 本导航系统用到的数据的存储格式是k i w i 格式，它对以前的存储格式进行了修改， 和以前存储格式的显著不同就是对每种检索的数据都设计了不同的索引，大大加快了检 索的速度，下面将详细介绍一下这种改进了的存储格式。 3 2 地图数据的基本要素 为了能理解的更好，先介绍一下地图数据的一些基本知识。 ( 1 ) 道路：在地图数据中，我们通常用点和线表现一条道路。下面是和道路相关的 一些概念。 s h a p e l i n k ： 两个形状补间点之间的线段： 形状补间点：在一条l i n k 上的点： l i n k ：由两个n o d e 点确定的不交叉的s h a p e l i n k 列； n o d e ：两条以上的l i n k 的交叉点： l i n k 列：由同一属性的l i n k 和n o d e 组成的有限列。 ( 2 ) 背景： p o l y l i n e ：多边线。用于表示铁路，行政区边界线等。 p o l y g o n ：封闭多边形。用于表示公园，湖泊，建筑物，森林等。 东北大学硕士学位论文 第三章导航系统中的数据存储 3 3 地图数据的分层和分块存储 ( 1 ) 地图数据的分层存储 地图的分层存储可以理解为按不同的比例尺存储，地图最般的特点，是以缩小的 图形显示制图区域的物体和现象，这势必导致对其进行综合。大家都知道这样一个最简 单的事实：面积2 5 平方公里的区域在l ：1 0 万、l ：2 5 万和1 ：5 0 万比例尺地图上分别为 2 5 平方厘米、4 平方厘米和l 平方厘米。很明显，欲在上述各种比例尺地图上以相同的 详细程度显示实地2 5 平方公里范围内的信息是不可能的。即使是很大比例尺的地图f 例 如l ：1 0 0 0 或更大) ，也不可能将实地的全部信息毫无遗漏地表示出来。显然，在编制较 小比例尺地图时，不加任何选取、化筒和概括地将资料地图上的全部内容都表示到新编 地图上也是不可能的。 这样一来，当所编地图上单位面积内的地物数量过多时，就要对其进行取舍，即选 取一部分，舍去另一部分；当地物轮廓图形的弯曲太小太多时，就要予以化简，即删除 一热小弯曲：当制图物体( 现象) 的数量和质量特征过于详细时，就要减少其数量和质量 的差别。 地图比例尺标志着地图对地面的缩小程度，直接影响着地图内容表示的可能性，即 选取、化简和概括地图内容的详细程度：它决定着地图的几何精度，影响着各要素相互 关系处理的难度；它决定着地图表示的空间范围，影响着对制图物体重要性的评价。 为了满足对于不同比例尺条件下数据处理或检索的需要，把地图进行分层存储。一 般来说底层存储详细的数据，而上层逐渐进行数据的抽取。比如目前中国地图数据分为 7 层，o 到6 层，处在最高层的6 层可能就只描画整个中国的版图，中间标注主要的都 市，而到了。层就有可能详细到某个市镇的道路f m l 。 参考下面的图3 1 和图3 2 。 图3 1 表示的第6 层的数据： 东北大学硕士学位论文 第三章导航系统中的数据存储 图3 2 表示最底层数据： 图3 1 第6 层示意图 f i g 3 1s k e t c hm a po f t h es i x t hl a y e r 图3 2 最底层示意图 f i g3 2s k e t c hm a po f t h el o w e s tl a y e r 东北大学硕士学位论文 第三章导航系统中的数据存储 ( 2 ) 地图的分块存储 分层存储能够将地图数据划分为很小的单元，但是即使这样取得每层的数据也是比 较困难，因此在分层存储的基础上对每层的数据分块进行存储，这样为数据的取得和管 理也提供了很大的便利条件，因为每层的数据量不同，因此不同层的数据块的个数也是 不相同的，低层的数据量较大，划分的数据块较多，高层的数据量小，划分的数据块也 少。分层后存储结构如图3 3 ： 图3 3 分块存储示意图 f i g ，3 3s k 咖bm a po f a p a r ts t o r a g e 为了保证每一个数据块的存储量差不多相等，低层含有的数据块比高层的数据块 多。当然每个数据块可以根据需要再分割。这种按层和块存储的结构不仅使数据查找起 来很方便，同时也使数据的存储变得很简单。 3 4 检索数据的存储 上面简单介绍了地图显示数据的存储，下面将详细介绍一下检索用到的数据的存储 结构，由于本次毕业设计作者只对两种数据的存储结构重新进行了修改，下面详细介绍 一下拼音数据和周边检索数据的存储结构。 本汽车导航系统主要可以进行以下几种不同的检索： ( ”设旌拼音检索：根据输入的拼音找出所有符合的设施。 东北大学硕士学位论文 第三章导航系统中的数据存储 ( 2 ) 住所拼音检索：根据如入的拼音找出所有符合的住所记