（计算机软件与理论专业论文）车辆监控导航系统若干问题的研究.pdf

y a j o r : c o m p u t e r s o f t w a r e a n d t h e o r y t o p i c : s t u d y o f 。 . .p r o b l e m s f o r v s n s a u t h o r : l u g u a n f e n g s u p e r v i s o r : p r o f e s s o r h u i q i o n g l u o a b s t r a c t t h e d e v e l o p m e n t o f v s n s ( v e h i c le s u r v e i l n a v i g a t i o n s y s t e m ) , w h i c h i s r e l a t i v e t o g p s , g i s . w i r e l e s s c o m m u n i c a t i o n , c o m p u t e r s c i e n c e a n d e l e c t r o n i c t e c h n o l o g y . i s a r e s u lt o f c o n t e m p o r a r y s c i e n t i f i c a n d t e c h n o l o g i c a l p r o g r e s s . t h o u g h it h a s o n l y b e e n in t r o d u c e d i n t o c h i n a f o r a s h o r t t i m e . i t i s n o w d e v e l o p i n g r a p i d l y . p r e s e n t l y v s n s i s a lr e a d y u s e d i n m a n y f i e l d s . s u c h a s i n p u b l i c s e c u r i t y , f i r e p r o t e c t i o n , t r a n s p o rt a t i o n a n d t o u r i s m . wit h t h e f u rt h e r d e v e l o p m e n t o f n a v i g a t i o n , l o c a t i o n t e c h n o l o g y a n d c o m p u t e r s c i e n c e . v s n s w i l l a ls o d e v e l o p q u i c k l y . t h e p r e s e n t t h e s i s i s b a s e d o n t h e e x a m i n a t i o n s o f t h e d e v e l o p m e n t a n d a p p l i c a t i o n o f v s n s i n c h i n a a n d a b r o a d . t h e n , it f i r s t p r o v i d e s f o r v s n s a s y s t e m s t r u c t u r e a n d f u n c t i o n a l m o d u l e a ft e r s t u d y i n g r e le v a n t t h e o r i e s . s e c o n d l y , it s t u d i e s t h e d a t a s t r u c t u r e , d a t a m a n a g e m e n t a n d g a i n i n g . l a s t , i t f o c u s e s o n t h e s t u d y o f s o m e b a s i c p r o b l e m s a n d p r o v i d e s s o m e n e w a l g o r i t h m s f o r t h e m k e y w o r d s : g p s , g i s , w i r e l e s s c o m m u n i c a t t on 第一章 绪论 互 1 . 1 车辆监控导航系统开发的背景和意义 车辆监控导航系统，就是利用装在车辆上的g p s( 全球 定位系统)信号接收机接收导航信息，并把其接收到的位置 信息在车辆上的g i s( 地理信息系统)上显示及处理，同时 又能把位置及其他信息通过无线通信传送到监控中心;监控 中心根据接收到的信息进行g i s 显示及处理，并可随时向车 辆发送调度信息。在此系统中，车辆能随时知道自己的位置 及周围环境信息，利用车载g i s ，可进行地理环境的查询， 并可根据指定目的位置自 动生成行车的最短或最佳路线;监 控中心能随时知道所监控车辆的位置，及其状态，可对车辆 进行跟踪、调度、管理。通过语音信道监控中心与车辆之间 可进行通话。 车辆监控导航系统应用的范围非常广泛，可以应用于公 安、交通、运输、金融、旅游等部门。 ( 一)社会背景 随着社会的发展和科学技术的进步，整个人类社会都希 望利用新的技术来为生产、生活服务，提高生活质量，减小 对人类生存环境的压力。对于交通运输来讲，如何充分的利 用现有的道路信息，改善现有的道路运输系统及其运行体系 从而大幅度提高路网的通行能力和服务质量:对于公安部门 来讲，利用车辆监控导航系统，指挥中心可以在发生突发事 件时，迅速组织警力进行处置:对于消防部门来讲，利用车 辆自导航系统，根据火场情况对消防车辆进行恰当的调度， 消防车辆可根据最佳行车路线，迅速赶赴火场扑灭火灾，最 大限度地减小火灾损失和人员伤亡。 ( 二) 技术背景 g p s ( g l o b a l p o s i t i o n i n g s y s t e m ) 即全球定位系统，是由 美国建立的一个卫星导航定位系统，利用该系统，用户可以 在全球范围内实现全天候、连续、实时的三维导航定位和测 速:另外，利用该系统，用户还能够进行高精度的时间传递 和高精度的精密定位。g p s最初是为军方提供精确定位而建 立的，至今它仍然由美国军方控制。军用 g p s产品主要用来 确定并跟踪在野外行进中的士兵和装备的坐标，给海中的军 舰导航，为军用飞机提供位置和导航信息等。g p s也广泛的 应用于商业领域，主要用在勘测制图、航空、航海导航、车 辆追踪系统、移动计算机和蜂窝电话平台等方面。一些 g p s 接收器集成了收音机、无线电话和移动数据终端来适应实际 应用的需要。近年来， g p s 在我国得到了越来越广泛的应用， 在勘探、测量、航空、航海、抢险救灾、电力、水利施工等 方面发挥着不可替代的作用，极大地提高了工作效率。在国 外，应用更加广泛，己经深入到人们的日常生活中。然而， 在一般情况下，仅是利用 g p s 接收机确定方位，很难同我们 己经掌握的信息进行综合分析，使得 g p s的深入应用受到了 阻碍，这就要求将 g p s定位信息与我们已有的信息系统有机 地结合起来。在这方面，最有优势的当属地理信息 、 系统 g i s ( g e o g r a p h y i n f o r m a t i o n s y s t e m ) 与g p s 的 综合 应用。 地理信息系统g i s 是一个采集、存储、分析和输出地理 空间数据的有力工具，具有很强的空间分析、查询能力。但 长 期以来，由于野外适时定位工具的不足，使得现有的g i s 系统只能停留在事后室内处理的水平上，使电子地图的快速 定位、处理和查询功能难以充分发挥。而g p s 恰好具有在室 外快速、精确和全天候提供定位信息的能力，但缺乏对数据 的分析处理能力，因而两者在功能上密切联系、相互补充。 g p s / g i s 的集成系统，不仅使两者的作用都得到了充分发抨， 而且还产生了更高级的功能，使 g i s 与g p s 的应用都迈 卜 了 一个新的台阶。首 先，g p s 的定位信息可 通过g i s 系统在c 1 算机上实时的、准确的 和形 象的反映。 现在， g p s / g i s 的集 成能自 动地将定位点与电子地图配准，1 卜 显示在屏幕卜 ，使 人们对自己 所处的环境有着更为全而、深刻的了解，不仅知 道自己所处的地理位置，更能了解附近的地理环境及各种专 题信息;其次，还可把gps提供的信息作为g i s 的数据源， 进行数据采集或对己有数据进行更新、修正。比如在一个地 区进行地形或专题测量，可直接根据g p s 提供的定位信息实 时生成地形图或赋于其专题属性后生成专题图;对二 j 二 与实际 情况不相符的地图可利用g i s 对其进行部分修正; 再次， g i s 可以根据g p s 的定位信息进行空间查询、分析，提供高级的 信息及导航服务。 在车辆监控导航系统 ， ，监控中心和车辆之间的无线通 信可选择常规通信、数字移动电话网 ( g s m)等，用户可根 据自己的实际需要来选择。常规通信一般专用于某单位系统 内部，无需通信费用，但作用范围小，例如城市中的公安通 信网;g s m通信网的特点是: 1 、利用g s m网，无需另建基站，因而投资少，建设周 期短。 2 . g s m网 覆盖范困大，利用该 网构建的调 度系统可实 现大范围、跨区域的调度，这是其它专用网无法比拟 的。 3 , g s m是一个开放性的系统，利用该网的调度系统必 将会获得较好的兼容性。 4 、我国频率资源相当匾乏，利用公众 g s m网，则是利 用现有频率资源，从而避免了新的频率资源的占) i . g s m技术成熟、先进，各种新的技术也在不断扣出 如:短消息、wa p( 无线应用协议)等，因此，构 筑在g s m网上的调度系统必然能与移动通信技术的 发展相同步，在技术上有较强的生命力。 市场推广潜力大。 、 ，、6 因此，可以说车辆监控导航系统是g p s , g i s ,无 线通信三种主要技术的集成。另外，汽车 _ 业、电川 j 业、通信技术、计算机技术等的快速发展也为车辆监控 导航系统的产生与发展提供了必要的技术和设备上的支 持。 ( 三) 社会意义 充分利用车辆监控导 航系统可以获得巨大的社会经济效 益。其意义主要表现在: 有利于打击和预防犯罪，快速扑火火灾和救援危急 事件等，促进社会的信息化、自 动化建设等相关户 业的发展。 2 、提高道路网的通行能力和提高汽车运输生产率和经 济效益。 3 .减小汽车运输对环境的影响 ，减少交通工具对环境 的污染，保护人类的生存环境。 4 、提高交通的安全水平 ，防止和减少交通事故，减少 阻塞，增加交通的机动性。 因此，汽车监控自 导航系统以及相关产业的的7 i 发与 应用对社会和经济建设都具有重要意义，有着巨大的社会 和市场应用价值。 互 1 .2国内 外车辆监控导航系统发 展的 现状 和趋势 自从德国宝马汽车公司在 1 9 9 4年第一个在它生产的 t , 系列高级汽车上装配了 g p s导航系统，大多数中等级别 的汽车都将把 g p s导航装置作为可选附加设备，如福特汽车 公司、通用汽车公司、丰田汽车公司等。国内的汽车厂商， 如一汽，也为其新推出的红旗 v 6 轿车上配备了 g p s导航系 统。 车辆导航和跟踪监控功能是智能公路的重要组成部分， 而 g p s定位技术又是车辆导航和跟踪系统的基本要求，在很 大程度上依赖g p s .航迹推算和数字地图匹配技术。 9 0年代后期，美国、 ! 木和欧洲等发达国家致力于开发 和应用智能公路系统来减少交通阻塞、增加车辆机动性和路 面运输效率、增强安全性、节约能源以及保护环境。它是个 世界范围内兴起的提高公路交通的频率、安全性以及改善环 境面貌的运动，其主要途径是利用信息、通信、定位和j 空 制 技术将车辆和公路集成在一个可以安装在车辆上的信息网络 中，同时，将整个公路系统的车辆流量进行优化以增加交通 容量，提高车辆的运行安全系数，改变传统的交通运输状况。 美国为防止交通堵塞，提高公路运输能力，正在试验智 能公路系统。美国芝加哥阿贡国家实验室的专家与联邦机构、 州级机构和私营公司合作，利用 g p s 、城市交通地理信息和 移动通信网，同交通管理中心联络，为司机提供实时交通和 气象信息。可以使装有 g p s接收机、传感器和车载计算机的 “ 智能” 车辆，轻松穿过交通高峰时的道路。 他们使用高效率 的计算机和大屏显示器，对行驶在芝加哥西北郊的 7 5辆“ 科 能” 车辆进行了7 个月的跟踪活动。受试车辆上装的车载导航 装置能设计策划行驶路线，避开交通阻塞的路段，指引汽车 选择最佳路线开往目的地。车上装的传感器可自 动辨别车辆 和调整车距，避免撞车。测试获得的信息，通过交通管制 卜 心传送给行使在加里芝加哥密尔沃基走廊的驾车 者。该走廊是美国政府准备优先设立智能交通系统的四条走 廊之一。 新加坡在智能公路系统上的设计采用了如下 方案: 采川 埋设在主要路口和路段的传感器来采集交通流量信息，采川 光纤通信和计算机网络技术把采集的信息传输和汇总到一个 调度中心并进行流量分析和优化计算，然后控制各相关路川 的红绿灯时间，使车辆的等待时间最短。 同时，沿主要路段 建设小功率的r f 基站，这些基站都配备g p s 接收机，调度 1 1 ， 心通过通信线路与这些基站连接，可把相关的交通信息通 过这些基站向附近车辆广播。例如，某路口出 现交通堵塞现 象，调度中心会自 动根据各基站的位置选择与该路1_ i 相关的 基站，把该信息通过基站通知到装有导航仪终端的车辆上， 终端可用语音提醒司机前面的交通状况，并自 动选出其它的 备用线路供司机参考，从而达到迅速疏散交通的日的。 微电子技术的飞速发展， 使g p s 接收机的体积越来越小， 可以嵌入到各种电子装置中，例如在车辆应用方面，可以集 成导航仪、防盗设备、移动通信装置、出租车计费装咒等等。 个人导航设备更是花样繁多，例如欧洲有些厂商7 1= 女 台 销4 ! 带 g p s功能的手表，为登山和滑雪者提供定位服务，更有手机 厂商把 g p s 接收机嵌入到手机里， 使手机用户不会迷失方向， 同时在手机j 目 户求救时可迅速确定其位置。p d a产1 ,fits 是前景 广阔的产品，g p s 技术与p d a技术和无线通信技术相结合是 将来的重要趋势。 目前国内一些院校、研究机构及企业正在进行车辆监控 导航系统方面的研究。我国虽然是一 个发展中国家，但是正 象电视、计算机和移动电话等一样，在车辆监控导航系统的 应用方面有着极为广阔的应用领域，其中每个应a 1 领域 ( 或 行业)都存在着巨大的市场潜力，因此可以预见该系统在我 国的良好的应用前景。这 一 方面是山我国经济的高速发展所 决定的，可以说是经济发展到一定程度必然出现的社会需求。 另一方面，涉及汽车导航的硬件设备和开发软件的快速发展 也为我国汽车监控自导航事业的蓬勃发展提供了可能。 本文通过对国内外车辆监控导航系统方面的发展和应川 状况的调查和分析，研究和探讨了车辆监控导航系统及相关 技术。首先给出车辆监控导航系统的系统结构及功能模块， 接着讨论了 系统的数据结构与数据组织及获取， 然后重点 研 究和探讨了车辆监控导 航系统的一些重要问题及其解决方法 或算法。 论文的组织与安抖 第一章主要说明开发车辆监控导 航系统的背景与意义， 叙述了当前国内外车辆监控导 航系统方而的应用和发展状 况，给出了车辆监控导航系统的技术理论基础。 第二章讨论了车辆监控导航系统的系统结构功能模块。 给出了车辆监控导航系统的系统结构，详细讨论了各功能模 块的功能。 第- : 讨论了车辆监控导航系统数据结构与 数据? l l 织。 对各利 ， 信息的内容、特点、格式、采集、组织进行了说明， 并给出了通信数据传输协议。 第四章讨论了 系统中儿个关键技术:最短路径、地图匹 配、信息查询、无级比例尺、车载端地理数据更新等问题的 解决方法，并提出自己的 一 些新的算法。 第五章总结一下自己在车辆自 导航软件研究开发过程i i i 的一些体会和对车辆自导 航技术发展的一些展望。 第二章 系统结构与功能模块 车辆监控导航系统是一个车辆可自 主导航、又受监控i c i 心监控、调度、指挥，集成g p s . g i s 、无线通信、计算机、 电子等技术的应用信息系统。车辆利用g p s 接收机接收到的 位置信息实现自身定位，通过无线通信单元把自身的位置及 状态信息发送到监控中心;监控中心利用无线通信单元向车 辆发送调度等信息，并可随时查询车辆的位置和状态信息。 车辆监控导航系统作为一个集成的信息系统，软件在其 ， 起 着非常重要的作用，可以说系统能否成功，主要取决 二 软件 功能的强大和完善，所以，应按照软件_位 程的观点分析和组 织系统，即按照抽象和信息隐藏、模块化和局部化的原则来 设计和实现。木章主要讨论车辆监控导航系统的系统结构、 硬件组成、软件功能模块等。 2 . 1 系统结构 系统山车载单元、iisi f 空 ， 心二大部分组成。 、车载单元工作流程如图2 . 1 所示: g p s 接收机、无线通信单元 计算机系统 无线通信中儿 发送数据信息到监控中心 图 2 2 ,监控v i， 心工作流程如n 1 2 . 2 所示 g p s接收机、无线通信单元 计算机系统 无线通信单儿 发送数据信息到车辆 图 2 . 2 互 2 . 2硬件组成: i 、 车载单元有:g p s 接收机、计算机系统、车载无 线通信设备、车载电源模块、数据线、天线等。 计算机系统可选择笔记 本电脑，其功能强大，体 积小。 i i 、监控中心部分有:g p s 接收机、计算机系统、无 线通信设备、其他相应硬件 ( 如网络硬件等)。 此处的g p s 接收机主要应用于g p s 定位数据的 差分处理，提高车辆位置的精确度。 2 .3软件功能 模块 ( 1 )车载单元有:g p s 定位数据处理软件、g i s 软 件、通信软件等。 g p s 定位数据处理软件，主要功能是把 g p s 定位数据经坐标投影和坐标变换，生成 : $ 动j 当 地坐标系数据。 g i s 软件应具有的功能有: 基本操作功能:无级放大、缩小、漫游、 图层显示自定义: z 、 定位功能:能根据指定定位点的位置 自 动生成最短行车路线。 3 , 查询功能:既可以输入地图要素名称查 询，又能根据区域进行查询，如在指定范 围内 ( 圆内、矩形内、多边形内、道路 卜 等)杳找要素 ( 如消防栓) 的数日及位,w o 4 、 导航信息提示:根据车辆的行车路线， 及时作出行车信息提示，如 “ 前行4 0 米 左拐， ， 原路”、 “ 距离目的地 5 0 0 米”等。 5 、 地图可 旋转功能:使车辆行驶方向始终 向上，同时提供指北针功能，此项功能可 选。 6 、 行车记录:对车辆的行车情况作记 录、 统计及分析，并可重现车辆运行轨迹。 7 、 地理数据导入功能:当地理信息数据而 要更新时，可方便的进行数据导入和更 新。 通信软件功能: 3 、把经过处理的g p s 车辆位置、速度数据或车 辆状态数据通过无线通信设备发送出去，到达iii 控中心。 4 、接收监控， ! ， 心传送来的信息 ( 如要赶赴日的 地的位置数据、地理数据更新信息)，山其他相 应处理模块进行处理。 在此处需要定义数据传输协议，保证通信双 方数据交换、传输的正常进行，将在后而的章节 中定义传输协议。 ( 2 )监控( i ， 心有:g p s 定位数据处理软件、g i s 软 件、通信软们 监控管理软例 、地理信息数据采集管理软件、 此处的g p s 定位数据处理软件功能同车载 单元。监控 卜b 的g i s 软件除具备土述功能外， 还要能同时监控处理多辆车。通信软件:1 .接 收车辆发送来的位置、 速度或状态信息; 2 、向 车辆发送调度信息。 地理信ft 数据采集管理软件的荃木功能是 完成地理数据的采集、编辑及处理。监控管理 软件的基本功能是完成对被监控车辆的相关数 据的维护，包括车辆的增加、删除、修改、统 计等。 第三章 数据结构与致据组织 在车辆监控导航系统中数据是多种多样的，主要的数据 是地理数据和通信数据。木章 t 要讨论了地理数据和通信数 据的特点、结构、组织及获取等。 3 . 1 地理数据 ( 一) 地理数据结构 在车辆监控导航系统 ， 最重要的数据是地理数据，如何 维护和管理好这些数据是系统运行成败的一 个关键。 地理信息属于空间信息，其位置的识别与数据联系在 起，这是地理信息区别于其它类型信息的最显著的标示。地 理信息的这种定位特征，是通过地理坐标来实现空r d 位置的 识别。因此，地理数据是一种基于空间参考的数据，它以定 点、定线或定面的方式与地球表面建立起位置关系。即地理 要素不仅包括空问位置信息和空间拓扑关系信息，而且 还包 括社会、政治、经济和文化等属性信息，这种内容的复杂性 就导 致了地理数据模型的复杂性。 1 .空间 数据和空间数据结构 在地理系统中，描述地理要素和地理现象的空g 4 数据 主要包括空间位n .打 ， 扑关系和属性三个方而的内容。地理信 息系统空间数据结构就是指这种空间数据在系统， i ， 的组织形 式，指适合于计算机系统存储、管理和处理的逻辑结构，是地 f !1! 实体的空if 时111 列方式 u 1 1 1 关关系的f lh 象描述。 描述空iih j 数据最重要的两种数据格式是矢量和栅格方式。 矢量数据是面向地理实体的数据结构，它把现实ii i_ 界的地 理实体从) l 何上 分为三类空间日 标:点、线、面，4 1: 瑕定坐标 空间为连续空间的基础_ l ，通过记录坐标方式来描述地理实体。 其中，点实体用一对 ( x ， y )坐标表示，线实休j l 一串有) i 的 ( x , y ) 坐标对来表示，而实体用一串首 尾相同的有序 ( x , y ) 坐标刘来表示。同时，根据它能否反映地理要素间的相互 关系 分为简单数据和拓扑数据。 棚格数据是面向位置的数据结构，它以规则的象元阵列来 表示空间地物或现象的分布的数据结构，其阵列中的侮个数据 表示地物或现象的属性特征。其中，点实体有一个象元表示， 线实体则表示为一定方向_ 卜 连结成串的相邻象元的集合，而实 体用聚集在一起的相邻象元的集合表示。 矢量数据和栅格数据是模拟地理信息的两种不同的方法， 在具体运用中各有优缺点。栅格数据结构虽然结构比较简单， 但需要大量的空间存贮和处理数据，才能达到与矢员数据相同 的分辨率。矢量数据存贮量比较小，结构比较复杂，在某些特 定的空间关系中处理运算比较复杂等。在本系统中采川矢量数 据结构。 2 、非空间数据 ( 属性数据) 非空间数据又叫属性数据，它表示地理物体的木质特性， 是地理实体相互区别的质r te .准绳。它和空间数据一起从木质 _ 对地理物体作相当全而的描述，可看作是多元信息的抽象， 是地理物体的静态信息模型。一个地理实体一般应具有一个 地理属性。属性数据通常可分为定性和定量两种。定性数据 包括实休的名称、类型、特征等，定r 数据包括数量和等级 等。 ( 二)地理数据的获取、组织与管理 i ) 、地理致据的获取 地理数据信息输入包括空间数据输入与属性数据输入， 以及空间数据与属性数据的连接。空间数据是指某类数据所 处的空间位置;属性数据是指这类数据所具有的特征属性。 比如，道路的空间数据是其的坐标值，而路的宽度、等级则 是道路的属性数据。空间数据与属性数据的连接可以以数据 库作基础，以特征码相连接。 空间数据输入则是图形的数字化处理过程，因为本系统采 用的是矢量数据格式，所以空间数据输入即是地图图形的数 字矢量化过程。 图形数字矢量化的一般方法有: 、手工数据输入方法 其基木原理是:手工输入矢ri . 图形数据，即把 点、线、面的地理位.坐标通过w盘输入到数据文 件中。这种力 一式较早，不需使用特殊的输入设备， 但误差较大。 2 ,跟踪数字化仪 数字化仪将点定位器的信号转换为识别位n. ,直 接读入计算机，形成数据文件。应用数字化仪输入速 度快，精度高，但设备昂贵，操作复杂 ( 需要多人) 。 3 、扫描仪 扫描仪把各种地图底图扫入计算机，形成图形文 件，在图形文件的基础 卜 ，通过人机交互实现地图的 矢量化。这种方法，矢量化速度快，操作简单 ( 取决 l . 矢量化软件设计的质量) ，日 设备价格便宜 ( 对 i - 普通扫描仪而言) 。 山于日前扫描仪技术发展迅速，性价比高，无论扫描速 度、扫描质量，都很好的满足地图的矢量化要求，所以木系 统的地理信息数据采集管理软件的数据采集主要是基于图形 扫描的。此外，地理信息数据采集管理软件的功能要求还应 包括以下内容: l ,能输入或装载其它数据格式的地理数据，比如 ma p l n f o , a r c / i n f o 的数据。 2 ,可视化的编程环境，以人机交互方式刘地理数据 ( 包括空间数据和属性数据)进行编辑和处理， 所见即所得，能对输入数据进行错误检查和处 理。 3 、能对输入和编辑后的空fiq 数据进行打 ， 扑关系的自 动处理和生成。 4 、把处理完毕后的数据存入到数据库 ( 如o r a c l e ) 文件中。同时数据可方便的导出和导入。 能同时管理多幅地图数据，处理或生成图幅问的 联系 ( 如拼接、配准)。 、地理数据的组织与管理 i2) 车辆监控导航系统地理数据具有海量的 特点， 其原囚主 要有以下儿点: 1 、 这是由导航区域的相对无限性决定的:按照车辆能 够到达的区域和g p s 定位的全球性，导航区域可以扩展到地 球上车辆可到达的任何区域，地理区域的无限扩展必然导致 海量数据的产生。 2 、这是山导航地理数据的精度所决定的:导航地理数 据要求一 定的精度，一 方而因为在进行地图匹配时，必须保 证数字化地理底图的数据精度。 这就要求我们必须存贮较大 比例尺的地理空间数据，这无疑增大了地理数据的存贮量。 3 、不同的地理区域对数据精度的要求不尽相同，使得单 一比例尺的地理数据难以满足需要，使用不同比例尺的地图 大大增加了数据量。 对地理数据管理的好坏直接影响到整个系统运行的状 况，为了使海量空间数据的得到很好的利用，必须考虑采用 一定的手段对其进行有效的管理，要求具有较小的数据冗余， 较好的灵活性以及高效性。而数据库 ( d a t a b a s e )是以 一 定 的组织方式存储在一起的相互关联的数据集合，能以最佳方 式、最小冗余为多种日的服务;3 卜 在木系统中，监控 ， 心和 车辆使用的都是计算机系统，所以，采用成熟的且使j 月 范川 最为广泛的关系数据库管理系统 ( 如o r a c l e )建立空问数招 库来管理地理数据，同时使i f 关系数据库系统来组织管理数 据对于以后系统的维护、与其它信息系统共享数据等都具有 益处。 在本系统的空间数据库系统中，属性数据单独存储，通 过关键码与空间坐标记录相联系。基于矢量数据结构的编码 方式如图3 . 1 所示: 编号类型位置坐标 点x , y 线x l , y l ; x 2 , y 2 ; . x n , y n 面x l ,y l ;x 2 , y 2 ; . x n ,y n ; x 1 ,y 1 图 3 . 1 属性格式如图3 .2 所示: 编号属性一属性二属性三属性， i 图 3 . 2 图3 . 1 和图3 . 2 中的编号 是关键码，通过编号把地图要索 的属性与空间坐标联系起来。数据结构如下: 1 )点要素 s t r u c t p o i n t i n t no ; i n t x; i n t y; c h a r * na me ; i n t t y p e ; i n t l a b e l ; p o i n t *n e x t 2 )线要素 s t r u c t l i n e i n t no ; i n t x; i n t y; c h a r * na me i n t w i d t h i n t c o l o r ; i n t l e v e l ; l i n e*n e x t 3 )111 1 要素 s t r u c t p o l y i n t o p e r a t e ; i n t no ; i n t x; i n t y i n t na me ; n t c o l o r ; i n t t y p e ; p o l y * n e x t ; 在上面的数据结构， 扫 只是给出了g i s 中三种基木要素的 一些基本属性，可根据实际应用的需要来增删。 解决大区域海量地理数据的统一管理是当前地理信息系 统面临的主要问题之一，这很大程度上与地理数据获取的特 点有关。对于目 前的地理数据的获取手段，一般还是以图幅 为单位获取数据。目前面临地理数据获取的两个基本问题及 其解决方法: ( i )由于地图信息采集工具的限制 ( 比如扫描仪的幅面 有限) ，往往一幅地图需要分割成几块，分别进行扫描入 计算机。在这种情况下，采取二种方式进行处理，以维 护地理信息的空间关系的完整性: 1 、在进行矢量化以前，先把块图进行拼接，以 组成完整的图幅 ( 可通过图形处理工具，也 可在地理数据采集管理软件中实现) ，然后 再进行矢量化。 2 、 分别对每块图进行矢量化，然后通过坐标平 移、配准，实现地理数据逻辑上的完整性。 这两种方法可根据实际情况 ( 比如计算机的配置) 同时使用，以加快地理数据数字矢量化的速度。 ( i i )由于导航地理数据的海量性，在本系统中要用到很 多图幅 ( 比例尺也可能不同) ，这些图幅在分别进行矢量 化后，需要在统一的地理坐标参照下拼接，从而形成在 逻辑上完整的地理数据。解决的方法是:以大范围的图 幅数据为基础，通过坐标平移将小范围的图幅数据叠置 于其上配准。 过程例如: 河南省地图 数据( 1 :2 0 万) 一 郑 州市地图 数据( 1 : 5 万) 一 郑州市区 地图数据 ( 1 : 1 万) 。 无论是图幅的分块矢量化过程，还是图幅的拼接过程， 都可能会产生一些位移误差，这时就需要协调图幅关系，使 误差尽量缩小，主要原则是: 1 、自 然要素不变，人工要素移位; 2 、主要地物固定，次要地物移位; 3 .稳定地物不动，易变地物移位。 3 . 2 通信数据及传输 协议 监控中心和车辆通过无线通信来传输和交换数据，数据 可分为上行和下行两部分。上行数据主要是被监控车辆的实 时位置、速度、状态;下行数据主要为g p s 差分修正数据、 时间、调度信息、地理数据更新信息等。在这里需要定义相 应的传输协议，以 达到双方都能理解数据的内容，并作相应 的处理。 ( 一) 异步方式 在本系统中，采用异步的数据传输方式，接收和发送端 不需要同步。 ( 二) 数据传输内 容 1 、上行数据格式， 车 辆 编 号一 坐 标x 如图3 . 3 坐标 y时间 车辆状态 图 3 . 3 车辆编号指被监控车辆的识别号码 ( 应唯一)，车辆 状态包括:正常、故障等 ( 可根据实际情况增减)。 此处时间指g p s 接收机接收到的卫星的时间。数据结 构为: s t r u c t ve h i c l e s t a t u s i n t no ; i n t x; i n t y; i n t r a t e ; i n t t i me i n t s t a t u s ; 2 、下行数据 下行数据内容不唯一，基本有三种内容: 1 ) g p s 差分修正信息，其格式如图3 .4 所示: 时间坐标 x坐标 y 图 3 .4 此处时间指g p s 接收机接收到的卫星的时间。因为对 于此时间，车辆和监控中心是一致的，这样被监控车 辆无论在何时收到监控中心的g p s 差分修正信息，都 能根据自己接收到的卫星时间进行坐标的修正，但具 有一定的事后性 ( 主要因为通信时延造成的) 。信息编 码是指下行数据的识别码。数据结构为: s t r u c t gp s i n t t i me ; i n t x; i n t y: 2 )车辆调度信息，其格式如图3 . 5 所示: 调度编码 调度内容 图 3 5 数据结构为: s t r u c t od e r i n t no ; c h a r * c o n t e n t ; 3 )车载端地理数据的更新信息，在第四章作详细论述。 ( 三)数据传输协议 在数据传输中，我们来定义一种协议，使得上述的每 一种数据内容都作为一完整的数据块发送出去，且任一数 据块都与其他数据块区分开来: 以 “ $ 数据块标识符5 ”作为数据块的开始标识，以 $ e n d $ ”作为数据块的结束标识，无论是标识符，还是 数据内容，它们之间都用 “ ， ”来分开。 下面是数据内容使用协议后生成的数据流: 1 ) 车辆状态数据: $ v e h i c l e s t a t u s $ , n o , x , y , r a t e , t i m e , s t a t u s , $ e n d $ , e 2 ) g p s 差分修正数据: $ g p s $ , t i m e , x , y , $ e n d $ , ” e 3 ) 车辆调度数据: $ o r d e r $ , n o , c o n t e n t , $ e n d $ , ” 。 4 ) 车载端地理数据的更新将在第四章作详细论述口 当 数据块内 容中出 现“ $ 数据块标识符 $ ” 或“ $ e n d $ ” 时， 不会引起混乱，原因是:对于每一数据块 “ $ 数据块表示符 $ ，. . . ， $ e n d $ ， 其 格式是确定的，无论在数据块的开始标识 “ $ 数据块标识符$ ”和数据块的结束标识 “ $ e n d $ ”之间出 现什么内 容，都会按照格式读入数据，这样就不会引起混乱。 监控中心同时要监控多个车辆，所以监控中心负责通信的软 件模块设计为多线程。 第四 章 基本技术的 研究 通过在第二章中对系统功能模块的讨论，可以 看出在车辆监控 导航系统中，有许多功能需要实现， 本章主要讨论一些基本的且重 要的核心问题。 包括:最短路径问题、地图匹配问题、信息查询问 题、无级比例尺问题、 车载端地理数据更新等一些关键问题。 4 . 1 最短路线问 题 线路确定是车辆监控导航系统的一个重要的子功能。该功能的 主要任务是:在一个由道路组成的交通网络中，从给定的两个道路 节点之间选取节点到节点的线路，这条线路应是根据用户的需要在 满足一定条件下的道路路段的集合。最佳线路不仅仅是地理意义上 的两点之间的距离最短，还可以有其他的度量方式，如费用、线路 容量等。 在车辆导航系统中， 线路的规划一般包括距离最短的路线、 通行最简单的路线、收费最少的路线等，也可以是上述几种方式的 组合。无论是距离最短还是费用最少，它们的核心算法都是最短路 径的算法，其差别仅仅在于在进行线路选择时赋予交通网络的链段 的权值不同而己。在系统中，不仅能确定最佳线路，而且同时生成 路线行驶的导航信息。 下面首 先给出 最短路径的经典 算法一 d ij k s t a( 迪杰施特拉) 算法在地理信息系统中的实现，并进行一定的优化分析;然后给出 求地理信息系统中最短路径的一种新算法一a算法，同时给出并 证明结论: 1 、 用a 算法找到的路径是最短路径; 2 . a 算法优于d ij k s t a 算法。 4 . 1 . 1 d ij k s t a 最 短 路 径 算 法 ( 一) d ij k s t a 算法概述: 最短路径问题一直是计算机科学、运筹学、交通工程学、 地理信息学等学科的一个研究热点，经典的图论与发展的计算 机算法的有效结合使得新的最短路径算法不断涌现。据统计， 目 前提出的最短路径算法中，使用最多、计算速度比较快，又 比较适合于计算两点之间的最短路径问题的数学模型就是经典 的d ij k s t r a ( 迪杰施 特拉) 算法。 经典d ij k s t r a 算法的 基本思想 是:各种实际意义上的网络被抽象为一个图论中的有向或无向 图，利用图的节点邻接矩阵记录点间的关联信息，同时认为两 节点间的最短路径要么是两点之间直接相连，要么是通过其它 己找到与原点的最佳路径的节点中转。其算法步骤为: ( 一) 设源节点为s 0 ， 找出与s 0 直接相连且路径长度最短的节点s l l 把s 1 归入集合p ; ( 二)然后遍历除p 中节点之外的所有节 点 ( 这些节点 集合记 为q )， 若其到s 0 的 距离大于其到s 1 的 距离与s 1 到s 0 的距离之和g ， 则修改其到s 0 的 距离为g ; ( 三) 然后在q中找到距离s 0 距离最短的节点s 1 ， 把s 1 归入集合 p : 重复二、 三， 直到找到s 0 到所有节点的最短路径。实际 应 用中各种最短路径的算法基本上大都是基于以上思想的改进。 ( 二)d ij k s t a 算法的实 现 在车辆监控导航系统中的最佳路径选择中，考虑的仍然是距离 最短路径问题，本着数据结构简洁、 存储空间小、运算速度快的原 则。在实际操作中 采用网络邻接节点表示法的思想。邻接点表示法 的基本内容是:取交通网络的节点数作为矩阵的行和列，构造邻接 节点矩阵来描述网络结构。对照邻接节点矩阵，把邻接节点矩阵中 各元素邻接关系对应的边的权值填在同一位置上，构造相应的初始 判断矩阵，如图4 . 1 所示: v i v 2 0 v i 1 0 2 0 0 v 2 1 2 0 0 0 4 0 0 0 ，4 0 0 0 图 4 . 1 因为同一地理区域的道路数可能会变化，且不同地理区域的道 路数也极可能不同，所以在程序中具体实现时，要采用动态存储的 算法， 本系统采用链表的数据结构， 利用这种结构可避免不必要的 存贮空间开销。数据结构如下: s t r u c t s h o rt p a t h i n t n o ; i n t x ; i n t y ; i n t p r e v n o ; i n t p a t h l e n ; i n t i f t e mp ; s t r u c t s h o rt p a t h * n e x t ; 关于上述数据结构的说明: 、 n 。 表示当前节点的编号，编号唯一。 2, 3、 x , y表示当前节点的坐标。 p r e v n o 表示当前节点的前一节点，即当前节点距离源 点的最短路径中必经过编号为p r e v n 。 的节点中转而求 4 , p a t h l e n 表示当前节点距离源点的最短路径的长度。 5 . i f e m p 初始值为0 ，当 最短路径己 找到时， i f t e m p 赋 值为 t o 6 , n e x t 指向下一节点。 在本系统中，计算最短路径是从终结节点t 开始，而不 从源节点s 开始。从t 到s 的最短路径与从s 到t 的最短路径 是一样的 ( 除非有几条最短路径，这样有可能出现不一样的 最短路径，但它们的距离长度是相等的)。向后搜索的理由 是每一节点用前面的节点而不用后继节点来标注，有利于程 序实现和生成道路导航信息的描述。 从实际应用的角度出发，考虑到影响道路通行的各种因 素，并据此改变路径搜索时的判断条件，使得计算出的结果 更符合客观状况。交通网络的最短路径问题需要考虑的因素 主要有:基本因素，即在一段时间内不会改变的道路状况和 交通限制，如道路的宽度、车道数、方向、是否为单行道等; 与时间相关的阶段性影响因素，如某条道路正在施工等;与 时间相关的周期性影响因素，如上下班高峰期，节假日的主 干线的拥挤程度，它与上一因素的主要区别在于它的周期性 和特定的时间段;不定因素 ( 适时交通信息)，如前方发生 了交通事故，天气状况等。在以卜 各种因素中，有些是可以 量化的，在这种情况下，就可以给出求最短路径的限制条件， 例如可限定最短路径的道路宽度要大于3 0 米等。 ( 三) d ij k s t a 算法的 优化 为加快运算速度和减小存储空间开销，可从交通网 络空间分布特性和方向入手，限制网络的搜索区域， 即在 保持一定置信度的基础上，达到减少实际装载的数据量 和缩小路径搜索范围的目的。可采用角度优先的办法， 也就是在进行计算时，首先是根据路径搜索的起始节点 和终止节点的距离和方位，计算出最佳路径的最有可能 区域，以缩减所涉及的边和节点，可大大减少运算的数 据量。 在具体实践中可使用限制区域算法，区域可以是 椭圆、矩形或多边形，交通网络越大，限制区域算法的 优越性越明显。尤其在起始点或终止点之一位于网络中 心区域，算法搜索范围可向多方向扩展时，更能体现出 运算的效率。在具体实现中，为了提高运算速度、降低 存贮空间，采取矩形区域限制搜索区域的方法 ( 因为这 种方法较椭圆、多边形计算量小)。起点和终点给出以 后，以起点和终点的直线距离为边长确定出一个把起点 和终点包含在内的矩形，只把与此矩形相交或被矩形包 容的地理数据，才被装载。这在保证路径搜索一定置信 度的条件下，有效地提高了数据的装载速度和路径搜索 的效率。 4 . 1 .2 a 算法 尽管使用d ij k s t r a 算法可以 找到g i s 中任两点间的最