（计算机应用技术专业论文）面向智能交通系统的时空索引方法研究.pdf

河海大学硕士研究生论文 摘要 摘要 随着无线通信技术与全球定位技术的发展，基于位置的服务 ( l d c a t i o n b a s e ds e r v i c e ) 逐渐兴起，旨在通过跟踪与管理空间移动对象提供位置 服务：如服务端在路网中利用g p s 设备跟踪移动对象，客户端通过对服务端查 询了解移动对象分布状况，并由此得到相关路况信息，做出合理的道路选择，避 免交通堵塞。为此，必须建立一个c s 结构的移动对象跟踪系统。并且，为了支 持上述功能，必须为移动对象建立相关的数据库，以提高信息收集时数据库更新 效率以及存储和访问效率。 以往有关移动对象跟踪问题的研究主要从跟踪策略出发，研究如何通过策略 的优化减少移动对象信息在数据库中更新的频率，却忽略了信息存取管理技术的 研究。与此同时，以往空间数据库索引技术的研究也主要集中在无限制运动空间 领域，其代表结构有空间索引r t r e e ，时空索引t p r t r e e 。而对于像城市路网 这样的限制空间中的对象运动研究不多。 本文从现有移动对象跟踪策略出发，比较其优劣，提出不同跟踪策略下数据 库中可以应用的索引结构。同时，借鉴r t r e e 与t p r t r e e 结构特点，针对基于 路段的跟踪策略设计出一种路网移动对象的时空间索引结构此结构将路网 与移动对象关联，通过定位技术将路网上对象的运动描述为一维空间的运动，有 效简化了空间运动的表示方式，也减少了空间占用，提高了查询效率。本文给出 此结构的插入和查询算法描述，并通过实验比较其与t p r t r e e 在索引占用空间、 插入、查询效率这三方面的性能优劣，验证了此索引结构的可行性与优越性。 关键词：基于位置服务，跟踪，时空索引，r t r e e ，t p r t r e e 河海大学硕士研究生沦文 摘要 a b s t r a c t w i t ht h ec o n t i n u e da d v a n c e si nw i r c l e s sc o m m u n i c a “o n s ，g e o p o s j t i o n i n 吕a n d n s u m e re l e c t r o n i c s ，a ni n f r a s t 兀l c t u r ei se m e r g i n gw h i c he n a b l e s1 0 c a t i o n _ b a s e d s e i c e st h a tr e l yo nt h et r a c k i n go f t h ec o n t j n u o u s l yc h a n g i n gp o s i t i o n so fe n t i r e p o p u l a t i o n so fs e r v i c eu s e r s ，t e n n e dm o v i n go b j e c t s t h i ss c e n a r i oi sc h a r a c t e r i z e db y h 唱ev o i u m e so fu p d a t e s ，f o rw h j c hr c a s o nl o c a t j o nu p d a t 。t e c b n 0 1 0 9 i e sb e c o m e i m p o r t a n t t h em a i ni s s u ec o n s i d e r e di sh o wt or e p r e s e n tt h el o c a t i o no fam o v i n g o b j e c ti nad a t a b a s es ot h a tt r a c k i n gc a nb ed o n ew i t ha sf e wu p d a t e sa sp o s s i b l e p r e v j o u sw o r k sf b c u st h e i rr e s e a r c ho nu p d a t ea p p r o a c h e s ，w i t hb e t t e ra p p r o a c h e s c o u l dr e d u c eu p d a t ea n di m p r o v es y s t e mp e b 肌a n b u ta l t h o u g ht h e s er e s e a r c h e s ， t h e yd i d n t 百v ep r o p e ri n d e xs t 兀l c t u r et os u s t a i nt h e i ru p d a t ea p p r o a c h e s o nt h e o t h e rh a n d ，t h er e s e a r c h e so nt h es p a t i o t e m p o r a la c c e s sm e t h o d sf o 册a l l yb a s et h e i r p r e c o n d j t i o no nt 王l ef r e em o v e m e n t ( s u c ha sr t r e ea j l dt p r - t r e c ) ，n o tc o n s i d c rr o a d n e “v o d ( s t h i sp a p e rf i r s ti n t r o d u c e sl b s ，t h e nd e s c r i b e st h r e ee x i s t i n gt r a c k i n ga p p r o a c h e s ， o f ：f i e r se m p i r i c a le v a l u a t i o n sa n dc o m p a r i s o n sa r n o n gt h e m ，a n dp r e s e n t sp f o p e ra c c e s s m e t h o df o re a c ho n e s p e c i a l l y ， i t p r e s e n t s an e wa c c e s ss t n i c t u r ef o r t h e s e g m e n t - b a s e dt r a c l 【i n ga p p r o a c h e s a n di t s o p t i m i z a t i o n w h i c hi n d e x e sm o v i n g o b j e c t sn o to n l yb yt h e i ra b s o l u t ep o s i t i o nb u ta l s ob yt h er o a d st h e yd r i v e t h ep a p e rg i v e st h es t r i l c t u r ed e s c r i p t i o n ，j n s e r t i o na n ds e a r c ha l g o r i t h m s ，t h e n c o m p a r e st h i ss t m c t u r ew i t he x i s t i n gs p a t j o t e m p o r a l a c c e s sm e t h o dt p r t r e ei n s i r u c t u r es i z e ，i n s e n i o na n dq u e r ye f f i c i e n c y ，w h i c hp r o v e si th 培h p o w e rf o ri n d e x i n g m o v i n go b j e c t si nr o a dn e t w o r k s k e yw o r d s ：l o c a t i o nb a s e ds e r v i c e ( l b s ) ，t r a c m n g ，s p a t i o t e m p o r a la c c e s s m e t h o d ，r - t r e e ，t p r t r e e 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者c 签? ，：芦u s 年z 月一日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ： j 三i 塑i口( 年；月阻日 河海火学坝一l 研究生论文 第一章绪论 在我国，随着社会经济的迅速发展，城市交通压力日渐增大，智能化交通 ( i n t e l l j g e n tt r a n s p o r ts y s t e m s ，i t s ) 的研究开渐兴起。智能交通系统最初是在以 监控为主体的交通工程( 包括交通管理) 基础上发展起来的，开始只进行道路和 车辆智能化的研究，目前其研究范围已逐渐涉及到铁路、水运及航空等各种交通 方式，旨在形成一整套为用户及交通管理部门提供道路交通信恩的新型交通系 统。i t s 的“智能化”体现在以下3 个方面： ( 1 ) 车辆依靠自身的智能在道路上安全自由地行驶在陌生地方不致迷失方向。 ( 2 ) 道路依靠自身的智能将交通流调整至最佳状态，缩短行车时唰，减少阻塞。 ( 3 ) 交通控制管理中心依靠系统的智能对道路和车辆的状态进行实时监控，及时 处理事故，保障道路畅通。 这其中，车辆自主导航和监控技术的应用正在形成热潮，实际上车辆导航和 监控将逐步被新兴的基于位置的服务( l 0 c a t i o nb a s e ds c r v i c e ，l b s ) 所替代。 因为从技术上看，u l s 是以移动通信、定位技术对车辆导航和髓控技术的提升。 从应用角度看，u 强可为各用户间的关系管理提供先进的技术支持。 移动通信技术与定位技术的发展促进了l b s 的兴起。l b s 是建立在定位基 础上的服务，其工作原理是：用户终端( 如手机、p d a 、车载电脑等多种移动终 端) 采用卫星定位等手段获取用户位置，实时地把这一位置信息通过移动通信刚 上传至服务器i 服务器根据用户发出的服务请求做出响应，并把响应的服务信息 ( 如地图、文本等) 通过移动通信网发布至用户终端。l b s 是卫星导航技术、 g l s 技术和无线通信网络技术等相集成的产物，它通过无线通信技术为用户提供 基于位置的信息服务。 空间数据库的存储和管理是l b s 服务平台的关键部分。l b s 的应用依赖其 对空间数据的收集、分析处理，而如何存储与管理这些数据就必须建立相应的数 据库。一方面，空间数据可以在大型商用关系数据库管理系统的基础上构建，以 便实现卒间实体几何数据和属性数据的体化存储，充分利用数据库本身的管理 能力实现海量空间数据的存储和管理。另一方面，空问数据由于其数据分布的特 河海大学硕士研究生论文 点( 如数据的多维分布、动态性等) 以及区别于普通数据库的操作( 如历史轨迹 查询，预测区域查询等) ，必须研究新的基于空问数据的数据管理结构，这其中 包括空间数据索引结构，空间数据查询方法的研究。 1 1 研究背景 l b s 对车辆提供各类导航服务必须跟踪车辆的地理位置：如系统对于局部地 区是否存在交通堵塞可以通过对此区域车辆分布以及其运动特性判断得出；而对 于参与到l b s 服务的车辆来讲，可以通过对其位置轨迹的跟踪来确定系统需向其 发送怎样的路况信息。 赳m i 衄s 2 等人2 0 0 4 年在m o b i l e 柚du b i q u i t o u ss y s t e m s ：n e t w o r k i n ga l l d s e j c e 会议上中提出了一种c s 结构的跟踪系统：设置客户端与服务端。其中， 客户端相当于用户，其准确位置可通过g p s 定位得知；服务端储存了每个用户 的位置信息，为了得到每个用户的实时位置，其数据库信息必然动态更新。即要 对客户端进行跟踪。为了避免错误的用户位置影响应用服务，跟踪的误差必须控 制在个可设定范围之内：每个客户端监视其准确位置( g p s 设备定时向用户发 送其位置信息) ，并将其与服务端中心数据库对其跟踪位置的比较。当差值超出 了限定值时就触发对中心数据库系统的更新。 服务端数据库存放了移动对象前一次更新的位置信息以及采用的数据更新 方式。而跟踪策略的不同导致更新方式也不同。在此情况下，服务端通过网络发 送给客户端其数据库中所用跟踪策略，客户端根据其前一次发送给服务端的位置 更新信息与跟踪策略计算出其当前在服务端数据库中的位置信息。而如何在数据 库中表示、跟踪移动对象的位置，以达到最小的更新频率是一个技术上难题，减 少了更新频率就意味着减少通信与更新的代价。 常见的对于移动对象跟踪的策略包括：基于点的跟踪，基于向量的跟踪，和 基于路段的跟踪 3 ，4 】。在【2 】中，研究者介绍了这些不同跟踪策略以及其性能的 比较。从结果来看，基于点的跟踪方式简单，但更新频率较高。基于路段的跟踪 与基于向量跟踪更新频率相当，但考虑路段的可延伸性，通过对于底层路网的改 造之后，基于路段的跟踪策略可以使得系统数据库更新频率大幅度下降。 采用传统关系数据库存放移动对象位置信息固然可行，但其不能支持区域查 河海大学硕士研究生论文 找功能。如对于指定区域当前移动对象分布情况、某个区域未来将有哪些物体经 过之类查找，传统数据库无能为力，必须依赖空间数据库的支持。因而需要一种 能够适应此类跟踪技术的索引结构来高效管理移动对象信息。 本文主要研究空间数据库的索引结构。拟研究l b s 中移动对象跟踪系统下 数据的存区管理问题，提出一种新的适应于道路网移动对象的时空索引，给出其 结构以及操作描述，并通过试验证明这种索引结构的正确性与优越性。 1 2 研究现状 索引是用来提供快速、有选择性的存取数据库的一种机制，它相当于一个映 射机构，将属性的值转换为相应记录的地址或地址集。一个数据库系统需要一种 索引机制帮助它根据数据的空间定位迅速地检索数据项目。早在关系数据库系统 中，b t r e e 的成功应用就让我们认识到索引技术的重要。在空间数据库中，空间 数据索引作为一种辅助性的空间数据结构，其介于空间操作算法和地理对象之 间，它通过筛选，排除大量与特定空间操作无关的地理对象，从而缩小了空间数 据的操作范围，提高了空间操作的速度和效率。 目前，国内外对空间索引结构的研究很多，主要有两个方向：一个是对静态 物体的索引，用于对空间中静态物体( 如道路、建筑物) 的方位信息进行索引。 另一个是对动态物体的索引，用于对空间中移动对象( 如车辆、飞机) 的方位以 及运动信息进行索引。 一般来讲，空间静态索引方法自上而下、逐级地划分地理空间，从而形成各 种树状空间索引结构。比较常见的包括对空间划分的网格方式，如q u a d t r e e 、 b s p t r e e 、k d b t r e e ；基于对象的分割方式，典型的有r t r e e 5 ，以及其变体 r + - 1 r e e 6 】、r 一t r e e 【7 】等。 空间动态索引结构是在静态结构中考虑了时间因素，用于索引空间中移动对 象。这里，根据时间特性划分为对移动对象历史位置信息的索引和当前位置信息 的索引。其中对移动对象历史数据的索引有助于快速查询移动对象的历史运动轨 迹，对其运动特性进行统计分析。此类典型结构有r t i r e e 【8 、3 dr t r e e 【9 s t r t r e e 【1 0 】、m r ，t r e e 【8 】等。 对移动对象当前数据的索引有助于对运动物体未来运动趋势进行分析，即预 河海大学硕士研究生论文 测物体的运动趋势。由于其独特的预测查询功能( 如：查询在未来时刻f 区域5 中可能存在的物体) 为许多l b s 服务提供基础支持，因而此类索引结构是现在研 究的热点。由于不同概念的引入，这类索引结构呈现出不同的研究方向：如 p m r q u a d t r e e f l l l 在原有q u a d l r e e 的结构基础上引入时间维，用于索引移动对象。 而s t r i p e s 1 2 】结构更是将二重转换空间【1 3 ( d u a l t 珀n s f o 加e ds p a c e ) 概念带入 q u a d t r e e ，将时间与空间转换到新的空间中加以描述。而最为成功并得到广泛关 注发展的当属t p r t r e e 【1 4 ，它借鉴了r t r e e 的索引结构，并引入速度矩形框 ( v e l o c i t yb o u n d i n gr e c t a n g l e ，v b r ) 来描述物体的运动信息。其变体t p r 8 一t r e e 在结构不变的基础上引入重插队列，提高了其插入以及分裂算法的效率。 一： l ? 口 7 b i 坳m _ u p d a 略g t 0 伊船。， v b 血 e 蛐l t i e e l 汁t n ；下? 下 ： 拙r 枷p e d l t 皿 m v 3 茁不e ： 2 | r _ t 碓e 。： 2 j t r - t 忡e 一 。9 ： ln 文 o dr 扭 墨劈簿e 。i 田一乜 j s t r _ 血 ；b 。t 弛e r t - t 矗e ( h t l阳p p e dq w 岬e e 陀e 、黛= - 一 6 一_ 巴_ k ) s v 面上。! ”o i l 2 ”啦b e d p 丑l 坶 ；0 e 8 0 8 99 09 1 9 59 6 9 7 9 89 9 o oo l0 2 0 3 历史位首索引o 当前位置索引0 未来位置索引 空间索引方法口时间索引方法基于路网限制索引 图1 1 时空索引结构的发展及其联系 图1 1 显示了当前主要的时空索引结构的发展及其联系 3 3 】，包括了空间， 时间的静态、动态索引结构以及它们问的脉络关系。从图中可以看出，随着时间 的推移，基于预测目的的未来位置索引研究越来越受到重视，如t p r t r e e ，其变 河海大学硕士研究生论文 体就有六种之多，但纵观目前对于移动对象索引的研究，其索引的运动物体均为 无限制运动的，即认为物体在所预测的时间内其状态可以是任意的，此时一般的 做法是预测索引的物体沿原有方向做直线运动。但实际应用中物体运动却是受限 的：如飞机必须沿航线飞行，运动的车辆必须沿道路行驶，行人必须沿人行道行 走。因而，研究基于限制的运动正越来越成为一个热点【1 5 ，1 6 。 1 3 本文的主要工作 本文以a l m i n a s 等人在【2 】中所描述的移动对象跟踪系统为基础，分析其所用 的几种跟踪策略的特点，并从这些跟踪策略出发，提出服务端中心数据库中适合 此类跟踪策略的空间移动对象的索引结构。其中，我们重点分析基于路段的跟踪 策略，提出种针对路网移动对象跟踪系统的索引结构：n c o t r e ef n e t w o r k c o n s t r a i n e do b i e c t t r e e ) 。本文所做工作如下： 1 在 2 中提出的移动跟踪系统框架下，分析其采用的移动对象跟踪策略。 并通过实验比较了不同策略下系统的更新负担，并指出本文研究重点一 不同跟踪策略下的移动对象的索引结构。 2 描述r t r e e 、t p r t r e e 索引结构，并指出它们可分别应用于不同跟踪策略 下的跟踪系统服务端数据库。 3 提出一种针对路段跟踪策略的数据索引n c o t r e e ，并给出其结构以及基 本操作算法的描述。 4 实验比较了此索引与当前主流时空索引结构t p r 1 r e e 性能上的优劣。验 证了其可用性与优越性。 1 4 论文的章节安排 本论文以下内容安排如下： 第二章介绍基于位置服务系统、移动跟踪平台、现有跟踪技术。重点讨论不 同跟踪策略以及其对数据更新的影响，并通过实验比较了现有三种跟踪策略的性 能，以及基于路段跟踪策略的优化结果。 第三章介绍时空索引技术并讨论其在跟踪系统中的应用。提出分别用r t r e e ， 河海大学硕士研究生论文 t p r ，t r e e 结构管理基于点跟踪策略与基于向量跟踪策略下移动对象。根据路网移 动特点，提出一种针对路网移动对象跟踪的时空间索引结构：n c 0 t r e e ，给出其 更新与查询算法描述，以及采用此索引下的系统体系结构。 第四章给出实验结果及评价。重点比较n c o t r e e 与t p r t r e e 结构在索引占 用空间大小、索引生成速度、查询效率上的比较。指出其优势与缺陷。 第五章给出总结与展望。 河海大学硕士研究生论文基于位置服务与跟踪技术 第二章基于位置服务与跟踪技术 在现代人类生活中，有许多信息属于具有空间位置特性的地理相关信息。如 移动用户迫切想知道他当时所处环境的信息，比如：“我在哪儿? ”，“我怎么到达 目的地? ”，“我要找的人现在何处? ”等等，如何提供这类服务，是定位和移动服 务技术面对的重要问题。 基于位置服务( l d c a t i o n b a s e ds e r v i c c ，l b s ) 正是在这一背景下产生的。 l b s 是建立在定位基础上的服务，其工作原理是：用户终端( 如手机、p d a 、 c a r p c 等多种移动终端) 采用卫星定位等手段获取用户位置，并实时地把这一位 置信息通过移动通信网上传至服务器，服务器根据用户发出的服务请求做出响 应，并把响应的服务信息( 如地图、文本等) 通过移动通信网发布至用户终端。 这种通过移动终端而获得的定位服务称为狭义的l b s 【1 。而广义的l b s 是指任何 通过有线和( 或) 无线网络，基于用户当前的位置，扩展空间信息操作或g i s 功能 到终端用户的服务和应用。 l b s 是卫星导航技术、g i s 技术和通信网络技术等相集成的产物，它实现了 互联网与各类定位终端之间点对点、端对端的互动应用，它通过通信技术为用户 提供基于位置的信息服务。l b s 定义了未来地理空间信息( 含定位信息) 移动服 务的蓝图，即当用户与现实世界的一个模型交互时，在不同时间、不同地点，这 个模型会动态的向不同用户提供不同的信息服务。其巨大魅力在于通过固定或移 动网络发送g i s 功能和基于位置的信息，从而在任何时间应用到任何人、任何位 置和任何设备上。 2 1l b s 系统框架 个完整的l b s 系统是由定位系统、移动服务中心、通信网络、移动智能终 端4 部分组成 1 7 】，其体系结构如图2 1 所示： 河海大学硕士研究生论文基于位置服务与跟踪技术 俳 图2 1 【b s 系统框架 、 定位系统由全球卫星定位系统和基站定位系统两部分组成。空间定位技术是 整个l b s 系统得以实现的核心技术，这一部分正在不断的完善当中，移动运营 商可以选基于网络的定位技术或基于移动终端的定位技术或者它们的组合定位 技术，来获得适当的定位精度，开展位置服务。 移动服务中心是定位服务系统的核心，负责与移动智能终端的信息交互和各 个分中心f 定位服务器，内容提供商1 的网络互连，完成各种信息的分类、记录 和转发以及分中心之间业务信息的流动，并对整个网络进行监控。 通信网络是连接用户和服务中心的，要求能实时准确地传送用户请求及服务 中心的应答，通常可选用g s m 、c d m a 、g p r s 和c d p d 等无线通讯手段，在 此基础上依托l b s 体系发展无线增值服务。 移动智能终端是用户唯一接触的部分，手机、p d a 均有可能成为l b s 的用 户终端。但是在信息化的现代社会，出于更完善的考虑，它要求有完善的图形显 示能力，良好的通讯端口，友好的用户界面，完善的输入方式( 键盘控制输入、 手写板输入、语音控制输入等) ，因此p d a 以及某些型号的手机将成为个人l b s 终端的首选。 2 2l b s 的工作流程 l b s 系统工作的主要流程是：用户通过移动终端发出位置服务申请，该申 请经过移动运营商的各种通信网关以后，为移动定位服务中心所接受；经过审核 认证后，服务中心调用定位系统获得用户的位置信息( 另一种情况是用户配有 g p s 等主动定位设备，这时可以通过无线网络主动将位置参数发送给服务中 心1 ，服务中心根据用户的位置，对服务内容进行响应，如发送路线图等，具体 圈圈， 博 僻 一统一 口恻曰卫避 静 匡 圜固 河海大学硕士研究生论文基于位匿服务与跟踪技术 的服务内容由提供商提供。图2 2 展示了l b s 系统工作流程。 一i 有线或无1 。 一i 线通讯l 一 2 2l b s 系统工作流程 由此可见，建立l b s 的技术基础应该包括以下4 个方面： ( 1 ) 有效的、易使用的l b s 终端设备：手机、个人电子手簿等。 ( 2 ) 稳定的、精确的定位技术：应用g p s 及移动通讯设备定位，例如e o t d 、 t d o a 、以及蜂窝小区信息等。 ( 3 ) 客户端的整体应用方案：实现l b s 需要空间数据库和相应的工具及应用平 台，通过g i s 在时空间数据库建模、处理和应用方面的经验，l b s 可以向用 户提供范围更广的有意义的个性化的应用和信息服务。 ( 4 ) 支持数据传输的高速通讯网络：移动设备用户已可以通过w a p 或s m s 来获 取信息，通讯的发展也进一步提高了l b s 的服务质量，尤其是需要传输大量 信息的服务。 2 3l b s 建立的关键技术 2 3 1 空间定位技术 l b s 需要通过移动终端和无线网络的配合，确定出移动用户的实际地理位置， 从而提供用户需要的与位置有关的信息服务。u 3 s 定位的过程大致包括测量和计算 两个方面。根据测量和计算的实体不同，定位技术可以分为基于网络的定位技术和 基于移动终端的定位技术。 河海大学硕士研究生论文基于位置服务与跟踪技术 2 3 1 1 基于网络的定位技术 在基于网络的定位技术中，位置解算功能由网络实现，主要有以下两种定位 技术： ( 1 ) c o o ( c e l lo fo r 皤n ) 定位技术。c o o 定位技术即基于c e l l i d ( 小区识别号) 的定位技术。它通过采集移动台所处的小区识别号来确定用户的位置。这种 技术的定位精度取决于所在小区的半径，如在市区，基站密度较高，c o o 定 位精度可以达到2 0 0 米左右；而在郊区，基站密度较低，c o o 定位精度只能 达到一两公里。 ( 2 ) 增强观测时差技术( e n h a n c e do b s e n ，e dt i m ed i 廿e r e n c e ，e ot d ) 。e ot d 是 通过放置位置接收器或参考点实现的，这些参考点分布在较广的区域内的许多 站点上，作为位置测量单元( i d c a t i o nm e a s u r e m e n tu n i t ) 以覆盖无线网络。每 个参考点都有一个精确的定时源，当具有e ot d 功能的手机和位置测量单元 接收到来自至少3 个基站信号时，从每个基站到达手机和位置测量单元的时问 差将被计算出来，这些差值可以被用来产生几组交叉双曲线，并由此估计出手 机的位置。e ot d 方案可以提供比c o o 高得多的定位精度。但这种方案对 手机和网络的要求较高，实现也比较复杂。 2 3 1 2 基于移动终端的定位技术 在这种定位系统中，定位解算的功能由移动终端来实现。用户通过接收机来 接收空中卫星的导航信号，接收机内置有位置解算软件，定位过程不需要网络参 与，这种定位解决方案特别适合于导航应用。最常用的是辅助g p s ( a s s i s t e d g p s ， a g p s ) 。a - g p s 直接采用g p s 接收机定位，在市区内或建筑物内一般很难收 到卫星发射的g p s 定位信号，无法实现定位，而a g p s 的实现基本思想是通过 在卫星信号接收效果较好的位置上设置若干参考g p s 接收机，并利用g s m 网把 接收到的辅助g p s 信号发给手机；同时配有g p s 计算：邕：片的手机根据g s m 网 传来的g p s 定位数据计算手机位罱。a g p s 方案可以提供的定位精度在1 0 米 以内。但这种方案与e - 0t d 类似，对网络和手机的要求都很高( 手机需配置g p s 计算模块，移动网络也需添加许多额外的硬件单元1 。以上三种选位技术的精度 河海大学硕士研究生论文基于位置服务与跟踪技术 比较如表2 1 所示【1 8 】。 表2 1 几种定位技术的对用户端和网络要求及精度的比较 定位方法用户端修改网络修改精度 c e l l d 否 是3 0 0 米以上 e o t d 是是 5 0 一1 5 0 米 a g p s 是 是 1 0 2 0 米 2 3 2 地理信息服务系统 地理信息服务系统包括不同区域和城市的基础的地图数据，以及对这些数据 的管理和发布、地理分析、地理编码、路径搜索等模块。地理信息服务系统可由 l b s 运营商自己搭建( 一般对于行业l b s 运营商而言，通常需要自己搭建地理信 息平台) 或者由u ；s 运营商以外的供应商提供。一个l b s 运营商可以与多个地 理信息服务平台连接，可以有多个地图发布，地理编码与路径搜索引擎。 2 。3 2 1 地理信息系统服务框架 地理信息服务系统负责地理信息服务的数据分析、查询、获取、发布等功能。 系统分为数据库管理、地理信息引擎、地理信息服务3 个层次。其中数据库管理 负责管理运营平台的所有数据。地理信息引擎实现对底层数据库的管理、操作。 并支持基于平台的二次开发，般采用成熟的地理信息平台软件和功能软件。地 理信息服务分为地理信息核心服务和地理信息应用服务框架两个部分，其中核心 服务是在地理信息引擎的基础上提供的地理信息发布、地理信息分析、路径搜索、 地理编码等核心服务功能；应用服务框架是在综合各种地理信息核心服务的基础 上提供的应用服务框架，包括城市黄页服务、个人导航服务、公交换乘服务、朋 友位置查找服务、地址查找服务等。 2 3 2 2 地理信息系统核心功能 ( 1 ) 地图发布引擎：根据用户的需要生成适用于不同终端的地图。所发布的地图 河海大学硕士研究生论文基于位置服务与跟踪技术 有矢量、栅格或混合模式。 ( 2 ) 地理分析引擎：根据经纬度定位地图及相关查询功能。例如可以根据经纬度 查出一定范围内地图的基本信息( 区、街道、大厦) ；可以根据2 个点的经纬 度给出距离信息及乘车信息；可以根据经纬度查询到一些基本的黄页信息 ( 如a t m 机、餐馆、卡拉o k 、银行等1 。 ( 3 ) 地理编码引擎：地理编码服务器转换基于字符串的地址( 如门牌号码) ，使之 成为地图上准确的经纬度点。要提供上述服务，l b s 空间数据库除了包含 电子地图数据库外，还必须提供地理编码数据库。 ( 4 ) 路径搜索引擎：根据给定的2 个点的位置寻找两点问距离最短路径或者时间 最短路径，并产生描述推荐路线的街道图形和包括预计路程长度及时间在内 的文字描述，该服务可用于个人导航和车载导航以及其它行业的应用。根据 用户的请求，服务引擎能够在图形路线介绍和文字指南中重点标示出娱乐场 所、路标、交通事故和道路状况( 施工、天气影响、路面状况等) 。 2 3 3 空间数据库技术 空间数据库存储和管理是l b s 服务平台的关键部分。l b s 空间数据可以在 大型商用关系数据库管理系统的基础上构建，以便实现空间实体几何数据和属性 数据的一体化存储，充分利用数据库本身的管理能力实现海量空间数据的存储和 管理。如中国联通的l b s 服务平台采用了o r a c l es d a t i a l 来管理和存储空间数据。 除了空间数据存储、空间分析、空间查询等基本功能外，空间数据库系统还必须 实现以下功能。 ( 1 ) 多比例尺图库管理即建立金字塔型的多级比例尺区域索引和图层索引表。 ( 2 ) 元数据管理通过元数据管理实现分布在各个场所的信息资源的有效管理与 共享。 ( 3 ) 数据安全管理数据中心能够在数据交换时保障数据安全。 ( 4 ) 数据远程协同工作管理与数据同步重点解决多级服务器之间的动态数据复 制问题与数据远程调用问题，实现空间数据操作的主要功能，数据版本控制。 河海大学硕：匕研究生论文基于位簧服务与跟踪技术 2 4 跟踪技术 前面我们说过，l b s 是建立在定位基础上的服务。这就需要对移动对象进 行跟踪，得出其实时的位置信息。在【2 】中描述了一种c s 结构的跟踪服务系统： 假设用户持有无线移动设备( 如移动电话) ，而且用户的位置是可通过a g p s 设 备得知。为了达到跟踪物体的目的，将其误差控制在一个设定范围之内，每个移 动设备监视其准确位置，并采用不同策略将其与中心数据库的预测位置比较。当 其差值超出了限定值时就触发对中心数据库系统的更新。其中，数据库对于移动 对象的位置信息的预测策略有几种不同方式，一般情况下，数据库需要明白的告 诉移动设备其位置更新的方式，而如何在数据库中表示、预测移动对象的位置， 来尽量少的更新数据信息是技术上的一个难点。同时，减少了更新频率就意味着 减少通信与更新的代价，优化了跟踪服务系统的运行性能。 这一节，我们首先描述移动跟踪系统，接着重点分析当前的跟踪技术，包括 基于点的跟踪( p o i n t _ b a s e d t r a c k i n g ) 、基于向量的跟踪路段的跟踪，最后，我们 比较这些策略并指出论文的研究方向。 2 4 1 移动跟踪系统 图2 - 3 画出了跟踪过程的流程图：客户端首先从g p s 设备获得其位置信息， 然后与服务端建立联系并将其位置信息发送给服务端。服务端得到这个位置信息 后根据其特点决定使用哪种更新策略以及精度要求，并将接收的a g p s 信息存 放在数据库中。如果跟踪策略是基于路段的策略，服务端需通过定位技术来决定 其所在的路段，然后将此表示方式发送给客户端。客户端同时通过a g p s 设备 获得其真实的位置信息，然后利用其从服务端得到的跟踪策略计算其预测位置， 并与其得到的真实位置相比较。如果这两个位置差超出了给定的精度要求，客户 端产生一更新请求给服务端，如果没有，等待下一个比较时刻的到来。这个过程 一直进行直到客户端终止跟踪服务为止。 河海大学硕士研究生论文基于位置服务与跟踪技术 2 4 2 移动跟踪策略 图2 3 跟踪过程流程 常见移动对象的跟踪策略主要有三种：基于点的跟踪( p o i n t - b a s e dt r a c k i n g ) 4 】；基于向量的跟踪( v c c t o 卜b a s e dt r a c k i n 曲 3 】；基于路段的跟踪( s e g m e n t - b a s e d t r a c k i n 曲【4 】。这些跟踪策略对数据的更新过程与图2 3 描述的跟踪过程是一致 的，但他们对物体运动轨迹的预测不同。 2 4 2 1 基于点的跟踪 基于点的跟踪策略认为跟踪对象总是处于静止状态。使用这样的策略，服务 端对客户端的预测位置总保持其前一次的更新位置。以图2 3 系统为例：服务端 认为客户端始终处于上一更新的位置。这样，由于客户端运动的关系，当其真实 位置与服务端预测位置( 即上一次更新位置) 偏离超过预测精度时，便触发服务 端中心数据库更新客户端对象位置信息。用公式表示为： 河海大学硕士研究生论文基于位置服务与跟踪技术 pm 。降( i 异一引c l e 月m ) “尸1 p ( i 昂一只i l 明。) ( 式2 1 ) 其中巴。为预测位置，昂为前一次更新时刻对象位置( 即服务端数据库存 储的对象位置) ，卑为时刻f 时跟踪对象的实际位置( 即其g p s 位置) ，l e h 。为 预测精度。其跟踪轨迹如图2 4a 所示：圆圈半径表示预测精度，实心点表示客 户端对象预测位置与其实际位置偏差大于预测精度时触发数据更新时物体的实 际位置，两粗线条表示路网上相连的两条路段。 a 2 4 2 2 基于向量的跟踪 b 图2 4 ：跟踪策略轨迹图 c 基于向量的跟踪策略预测物体做匀速直线运动。以图2 3 系统为例：假设服 务端存储的某客户端位置为晶，y 。) ，速度k ( v 。v ，。) ，则服务端认为客户端以 r 为起始点，k 为速度做匀速直线运动，即客户端位置由函数 只。；昂+ ( f 一气) 决定。同样，由于客户端对象运动变化的关系( 如速度，方 向的改变) ，当其真实位置与服务端预测位置偏离超过预测精度时，触发服务端 中心数据库更新客户端对象位置信息。用公式表示为： 啪，= 。“：乏：矩凌j c 河海大学硕士研究生论文 基于位置服务与跟踪技术 其中已。为预测位置，只为前一次更新时刻对象位置( 即服务端数据库存储的 对象位置) ，k 前一更新时刻对象速度( 服务端数据库存储的对象速度) ，p 为时 刻f 时跟踪对象的实际位置( 即其g p s 位置) ，跏。为预测精度。跟踪轨迹如 图2 + 4 b 所示：其中实心点表示客户端对象预测位置与其实际位置偏差大于预测 精度时触发数据更新时物体的实际位置，空心点表示更新时刻服务端存储的对象 位置，即预测位置，两条粗线表示路网上相连的路段。 2 - 4 _ 2 3 基于路段的跟踪 基于路段的跟踪策略认为路网中物体的运动必须遵循路网限制。此策略预测 物体沿物体当前路段做匀速运动。以图2 3 系统为例：假设服务端存储的某客户 端位置为p 。( & g b ，p d s 。) ，速度k ，时间为f 。则服务端认为客户端以尸撕。为 起始点，为速度在路段鹕上作匀速运动，即客户端位置由函数 p 。= p 。+ o 一气) 决定。同样，由于物体运动的变化的关系( 如速度，方向 的改变) ，当其真实位置与服务端预测此物体位置偏离值超过限定值，或移动对 象改变其运行路段时触发服务端中心数据库更新物体位置信息，并同时更新物体 所在路段信息。用公式表示为： f 只碣+ k ( f 一岛)a p h 一r 鹞i c z 口。) n ( - 5 z ；g 血z = 5 e g 觋) f b s “( f ) 一 p b s0 。p 魄一啊i i 口k ) n ( s ：g 皿一l s e g 皿毛) ( 式2 3 ) i 啦( 吕田一s 学觋) 为了区别前面用绝对坐标p ( x ，y ) 表示空间位置，这里用p ( 5 喀，d ，p d s ) 表示基于路段的位置。其中g 为对象所在路段编号，p o s 表示所在位置相对 于路段起始位置的偏移位置。其跟踪轨迹如图2 4 c 所示：其中黑点表示客户端 对象更新时刻的位置，白点表示更新时刻服务端存储的客户端对象的位置。 在基于路段的跟踪策略下，移动对象的未来位置由其所在的路段以及其速度 决定。当预测的位置到达了这个路段尽头，便认为其将来位嚣不变，即预测策略 由基于路段的预测到基于点的预测。 基于路段的预测对路网的精确度要求很高。如果因为某种原因，定位技术没 河海大学硎士研究生论文基于位置服务与跟踪技术 有能够得到运动对象所在的路段( 这可能时由于电子地图的精确度不高，或者是 地图未能够覆盖运动对象所在区域) ，预测策略改变为基于向量的预测。在下一 个更新来临时，服务端将继续寻找其所在路段。 举个例子： 假设个出租车在路网上移动，它在下午2 ：0 0 出发，其起始位置为( ，y 0 ) ， 起始速度为5 0 k m 1 跟踪预测精度为1 0 0 m ，即我们需要跟踪误差在1 0 0 m 内的出 租车位置。如果采用基于点的跟踪，当出租车运动距离每超过1 0 0 m 时，便触发 一个服务端的数据库中对此出租车的位置更新，其运动轨迹情况如图2 4 a 所示。 如果使用基于向量的跟踪策略，便需要考虑出租车运动方向和运动速度，其运动 轨迹情况如图2 4 b 所示，可以看出采用基于向量的跟踪策略减小了更新频率。 如果我们有一个相关路网的电子地图( 用于定位移动对象所在路段) ，就可以做 基于路段的跟踪( 如图2 4 c ) ，与基于点的跟踪策略相比，这种策略也减少了跟 踪的更新频率。 2 4 3 跟踪策略的实验比较 我们对这三种跟踪策略作了实验比较，实验采用g e o g r a p h i cd a t a t e c h n o l o g yi n c1 9 9 9 1 年根据美国加利福尼亚州公共交通网所采集的路网的部分 数据，通过道路网移动数据生成平台生成了一系列移动数据。实验截取了在精度 分别为2 0 、5 0 、1 0 0 、2 0 0 、5 0 0 、1 0 0 0 个单位长度内的移动对象更新比例图，即 分别在这几个跟踪精度下移动单位时间内( 这里单位时间即为两个快照之间的时 间间隔) 更新对象所占总移动对象的比例( 如图2 5 ) 。我们对其结果加以分析： 6 1 4 2 0 0 岳一 1 注：h t t p ：l i b r a r i e s m i t e d u g i s d a t a f i n d i n g a i d s e