（信息与通信工程专业论文）面向位置服务的移动对象索引与查询处理技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 位置服务是通过移动终端和无线网络的配合，确定出移动用户的实际地理位置， 从而提供用户需要的与位置相关的信息服务。位置服务技术融合了卫星导航、移动通 信、i i l t e n l e t 和数据库等当今i t 行业的各种技术，形成一个独具特色、前景无限的新 兴产业。随着全球定位系统、无线通信网络等基础设施的飞速发展和普及，面向位置 服务的移动数据库技术已远不能满足用户不断增长的应用需求，面临着许多新的挑战。 移动环境下，支持位置服务的移动对象数据库负责管理移动对象如汽车、飞机、舰船 等位置信息，并提供相关查询服务。目前移动对象数据库领域的研究处于初步阶段， 在理论和实际应用上还不成熟，存在许多问题和技术需要解决。 针对移动对象当前和未来位置的索引技术和移动环境下的查询处理技术得到了国 内外研究者的广泛关注，是充满挑战性的研究方向。论文研究目的是针对目前移动对 象数据库领域中的研究难点和热点，在全面总结和分析国内外数据库领域相关工作的 基础上，面向遥感卫星监视系统应用需要，对移动对象数据库系统的关键技术：移动 对象索引技术、连续七近邻查询处理技术和预测范围聚集查询处理技术进行研究，力 图进行创新，并将相关研究成果应用于实际系统中。本文的主要工作和创新点包括下 面几个方面： ( 1 ) 针对目前广泛使用的t p r 树移动对象当前和未来位置索引在频繁更新应用中 更新性能低下的问题，借鉴了r 树b u 算法思想，提出一种支持频繁更新的移动对象 混合索引结构h t p r - 他e ，并给出了扩展的自底向上更新算法和更新代价模型。 ( 2 ) 深入分析t p r 树索引查询性能随着时间变化急遽下降的问题，提出了一种基 于速度分布的移动对象混合索引h v t p r 树索引。 r v t p r 树索引综合考虑移动对象在 速度域和空间域中的分布进行构建，具有良好的预测查询性能。 ( 3 ) 针对连续七近邻查询，引入了一种新的时空距离度量最小最大距离函数作为 t p r 树索引搜索时节点剪枝上界。提出了一种采用最优优先搜索策略的基于扩展时空 距离度量的连续k 近邻查询( s 1 m c n 算法。s t m c n n 算法利用最小距离函数进行 t p r 树索引节点搜索时访问排序，并使用最小最大距离函数对t p r 树索引进行剪枝界 定提高连续| j 近邻查询的搜索性能。 ( 4 ) 研究基于t p r 树索引的大量并发连续七近邻查询处理技术，提出了一种可伸 缩的增量连续七近邻查询处理s i c n n 框架，通过引入搜索区域进行裁剪以减少查询 更新的所需要的磁盘访问代价，并引入了增量结果表批量的更新查询结果集。基于 s i c n n 框架提出了一种支持更新的s i c n n 查询处理算法，基于上次查询结果增量的 更新查询且支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更 第v i i 页 国防科学技术大学研究生院博士学位论文 新操作。 ( 5 ) 研究面向移动对象的精确预测范围聚集查询处理技术，提出了一种高效预测 范围聚集查询索引( a t p r 骶e ) 方法。通过在t p r 树中间节点中加入聚集信息以减少预 测范围聚集查询所需要的节点访问代价。抑r 树索引增加了一个建于叶节点之上的 h a s h 辅助索引结构，并采用自底向上的删除搜索算法，具有很好的动态性能和并发性。 基于a t p r 树索引，提出了一种增强预测范围聚集查询( e p r a ) 算法，采用更精确的剪 枝搜索准则，大大减少了查询所需要访问的节点代价。 基于上述研究成果，论文最后构建了遥感卫星目标监视查询处理引擎原型系统和 城市应急联动位置服务实验系统，验证了移动对象索引、连续七近邻及预测范围聚集 查询技术的有效性和实用性。 主题词：位置服务，移动对象数据库，移动对象索引，连续k 近邻查询，预测范 围聚集查询 第v i i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t l 0 c a t l o n b a s e ds e n r i c e sp r 0 、，i d eu s e 巧、j l r i t hs e i c e s 他l a t e dt 0t l l e i rp o s i t i 0 璐w i l i c hc a n b e o b t a i n e d 血r o u g l lm o b i l ed e v i c e s 缸d 、h l e s s咖r ! i 【si n j 概t i l 陀 1 1 1 e l o c a t i o n - b a s e ds e r v i c e sc o m b i n et e c 埘刚屺si 1 1i ta r e 鹤s u c h 私s a 钯l l i t em v i g a t i o n ，m o b i l e c o m 删c a t i o 璐，硫e m 烈a 1 1 dd a 诅b 嬲e s ，m u sl i a v eb e e nb e c o m i i l ga 诅q l 圮趾dp r 0 血s i r l g d o m a i n w i 廿lt h er e p a i dd e v e l o p m e n to fg l o b a lp o s i t i o i l i n gs y s t e m ( g p s ) ，i r c l e s sc e l l u l a r 玳小加r k ，廿l em o v i l l go b j e c t sd a t a b 勰e st e c h i i q u e st o w a r d s1 0 c a t i o n b 弱e d i c e sc 锄0 t m e e tt l 圮i 圮e d so fu s e r sm l df a c em 龇l yc l e n g e s hd y n 疵ce n v b o 衄e n t ，t h ei n o v i l l go b j e c t sd a t a b a s e sm 觚a g e l ep o s i t i o 璐o fm o v i i l g o b j e c t ss u c h 弱v e l l i c l e s ，a i 印l a i 圮s 赳l dn e e t s ，趾dp r o v i d el o c a t i o n - d e p e n i d e n tq u e r i e s c u r r e m l y 廿l e 托s e 盯c h e s i 1 1m o v i i 唱o b j e c t sd a t a b a sa 托p r e l 抽1 i j l a 巧觚df 打丘o m m a _ t u r a t i o nb o mi i ln l e o d ra n dp m c t i c e 加1 dm e r ea r em 锄yo p e np r o b l e 刀凹t os 0 l v e t h ei 1 1 d e x i l l gr n e t l l o d sf 0 rc u n ：e m 龇l d 如t u r ep o s i t i o 邶o fm o v i n go 巧e c t sa n dq u e 巧 t e c m q u e si i ld y n a 血ce n v 的衄1 e 吐w t l i c ha r ec h a l l e n g i i l gd h 嘶。璐，h a _ v eb e e nf o c u s e do n b ym 孤yr e s e a r c h e r s i n0 r d e rt 0s t u d yt h ed i 伍吼d ta n db 航i s 吼l e si i lm o v i i 培o b j e c t s d a t a b a s e s ，t h i sp a p e r 百v e sc o m p r e h e n s i v ed i s c u s sa n da n a l y s i so nf o 肌e rw o r ki i lr e l a t e d a r e a s a n dt o w a r d st i 圮印p l i c a t i o nn e e d so f 鞠t e l l i t er e c o m l a i s s a n c e ，血i sp a p 盯s t u d i e s 也e k e yt e c h i q u e si i lm o v i n go b j e c t sd a t a b a s e si i l c l u d i r 冯i i l d e x i i l gm e t h o d so nm o v i n go b j e c t s ， t e c q u e so fc o n t i l l u o l i skn e a r e s tn e i g h b o r sq u e d r 舡l dp r e d i c t e d 瑚g ea g g r e g a t eq u e 巧， 龇l da p p l yo u ra c m e v e m e n t st op r a c t i c a la p p l i c a t i o n s t h em 血、o r k 趾1 dm o v a t i o 璐黜 d e t 蔚l e d 勰f o l l o w s ： 1 ah y b mi 1 1 d e x i i 唱m e 也( ) d ，h t p r - 仃e e ，w k c hi sb a s e do nt p i h r e e 锄d s u p p l e m e m e db ya1 1 习曲i i l d e x ，i sp r e s e m e dt 0i m p r 0 v et l l el o w e rp e r f i o 皿a 1 1 c eo ft p r - n e e 晰也舶q u e n tu p d a t e s m o t i v a t eb ym eb o 怕m - u ps 仃a t e g ) ro fr 击e e ，趾e x t e n d e db 0 们m u p u p d a t ea l g o r i t l li sd e v e l o p e df o rh t p r - t r e e 町l di t sc o s tm o d e l i sa l s og i v e n 2 b a s e do nt h o r o u g h 锄 1 a l y s i so n 位q u e d rp e 响n i l a n c ed e 伊a d eo ft p 脚e e ，w e p r e s e n tah y b r i dv e l o c i t ) ，d i s t r i b u t i o nb a s e dt i r i 坨- p a 均m e t e r i z e d1 0 t r e e ( h v t p r - 臼e ) ，w m c h t a k e si 1 1 t 0 c o 呲t t l ed i $ t r i b u t i o no fb o mv e l o c i 锣d o m 咖觚ds p a c ed o m a i n 趾dm 吣h a v e ag o o dq u e 巧p e d o 肌龃c e 3 i no r d e rt 0p r o c e s sc o n t i i l u o l l skn e a r e s tn e i g l l b o r sq u c r yb a s e d9 nt p r - 臼e e e f ! f i c i e n t l y ，、ep r e s e n tan e ws p a t i o - t e m p o r a ld i s 伽em e t r i c sm i 锄a x d i s t ( t ) a sap m l l i n g 第页 国防科学技术大学研究生院博士学位论文 u p p e rb o m l d 刖s o aq u e 巧 a l g o r i t l l m b a l s e do ne x t e n d e d s p a t i o t e 瑚【p o r a j m e t r i c s ( s t m - c n n ) ，s e a r c h i n gi 1 1b e s t - f i r s tm a i l n e r ，i sd e v e l o p e d s 刑a l g o r i t h mv i s i t s t p r - 骶en o d e sa c c o r d i i 培t 0m i i l d i s t ( t ) o r d e r ，a j l dp 九l n j n gm en o d e s 丽t 1 1n 血】匝a 】【d i s t ( t ) t o 证1 p r 0 v et l l eq u e 巧p e r f 0 吼a n c e 4 t oe v a l u a t el a r g ec o l l e c t i o no fc o n c u r r e n tc o n t i n u o i l skm a r e s tn e i g l l b o r sq u e r i e s c o m i i l u o u s l y ，w ep r o p o as c a l a b l ep r o c e s s i i l go fi i l c r e m e n t a lc o n t i n u o u sk - n e a r e s t n e i 曲b o r ( s i c n n ) 丘锄e w o r kb ym o d u c i n gs e a r c m n gr e 百o nt 0f i l t e rm ev i s i t 吨 t p r 慨en o d e s s i c n n 丘锄e w o r ke x p l o i t s 血r e m e n c a lr e s u l t s 诅b l et 0b u 虢rc a l l d i d a t e o b j e c t s 锄dn u s h e st 1 1 eo b j e c t si i l t oq u e d rr e s u l t s 洫b u 【w em p r e 辩n t 觚i 1 1 c r e m e n t a l s i c n nq u e d ru p d a t ea i g o 删 l i l l ，w 1 1 i c he v a l u a t e s 洫c r e m e n t a l l yb a l s e d0 nf o m e rq u e 巧 a n s w e r s 趾ds u p p o n si l l s e r t i o no rd e l e t i o no f b o t l lq u e r yc 0 1 l e c t i o n 纽di n 0 v i i l go b j e c t s 5 t oi i n p r o v et 1 1 eq u e d rp e r f o 衄a n c eo fa c c u r a t ep r e d i c t i v er a n g ea g g r e g a t e ( p r a ) q u e r i e s ，、ep r e s e m 锄e m c i e mp r e d i c t e da g 伊e g a t et i l l l e - p a r 锄e t e r i z e dr 仃e e ( a t p r - t r e e ) ， w h i c hi sb a s e do nt p r - 缸l e e 蛐r u c t u r ea n da d d e d 、i t l la g 伊e g a t ei i l f o 衄a t i o ni i li 1 1 t e 加1 e d i a t e n o d e st 0r e d u c et h ed i s ka c c e s s e so fp r a q u e r i e s n ea t p r 仃e ei ss u p p l e m e m e db yah 私h i 1 1 d e xo nl e a fn o d e s ，锄du s e s b o t t o m u pd e l e t ea l g o r i t h m ，t l l u sh a v i r 培ag o o du p d a t e p e o m a n c e 趾dc o n c u r r e n c y 灿s oa j le i l l l a n c e dp r e d i c t i v er a n g ea g g r e g a t e ( e p r a ) q u e r y a l g o r i t l u i lw 1 1 i c hu s e sam o r ep r e c i s eb r 锄c ha n db o 硼【ds e a r c l l i n gs 缸a t e g ) ri sd e v e l o p e df o r a t p r - n e e ，r e d u c 血g 也en o d e c e s s e s 笋e a t l y b a s e do nt h ea b o v ea c l l i e v e m e m s ，、e d e s i g nar e m o t es e n s i n gs a t e l l i t et a 唱e t s r e c o i u l a i s s a n c eq u e r ye n g i l l ep r o t o 咖e 趾dal o c a t i o n - b 嬲e ds e n ，i c e se x p e 血e n t a ls y s t e m f o rc i t ) ，e m e r g e n c yl i l l l ( a g et 0v a l i d a t et l l e e f j f i c i e n c ya n dp r t i c eo fo u rp r e s e n t e d t e c m q u e si n c l u d i n gm o v i n go b j e c t sm d e x i i 培m e t l l o d s ，c o m i i m o u s 七m a r e s tn e i 曲b o rq u e d r a n d p r e d i c t e dr a n g ea g g r e g a t eq u e 巧 k e yw o r d s ：l o c a t i o n - b a s e ds e n ，i c e s m o v i n go b j e c t sd a t a b a s e s ，m o v i n go b j e c t s i n d e x e s ，c o n t j n u o u sn e a r e s tn e i g h b o rq u e 吖，p r e d i c t e dr a n g ea g g r e g a t eq u e 吖 第x 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 位置服务系统典型应用模型3 图2 1t p r 树矩形包围框一2 2 图2 2 支持e b u u 算法的t p r t r e e 索引结构2 6 图2 3 动态更新性能比较3 5 图2 4 动态查询性能比较3 5 图3 1h v t p r 树索引速度桶划分3 8 图3 2h v t p r 树索引结构4 0 图3 3 插入及删除算法流程4 3 图3 4 查询区域与矩形包围框相交情况4 4 图3 5 预测范围窗口查询性能比较4 9 图3 6 索引更新及查询性能比较4 9 图3 - 7 速度桶数目对更新及查询性能影响：5 0 图4 1 最小距离及最小最大距离度量5 5 图4 2 二维欧式空间m 仃d s f 与m 仃m a x d s 删5 8 图4 3 最小距离函数及最小最大距离函数5 9 图4 4 最近邻距离与搜索半径6 4 图4 5 单近邻连续查询搜索区域_ 6 4 图4 6s i c n n 系统框架6 6 图4 7o i d e n b u r g 的道路图及移动对象分布图7 1 图4 8c k n n 查询计算性能比较7 2 图4 9c k n n 查询更新性能比较7 4 图4 1 0 增量结果表大小的影响一7 5 图5 1 聚集r 树索引结构：7 8 图5 2 聚集t p r 树索引结构- 8 1 图5 3 运动矩形尺与查询区域q 之间的拓扑关系8 4 图5 4 预测范围聚集查询性能比较8 7 图5 5 索引更新及查询性能比较8 8 图6 1 道路网络的移动对象生成器运行界面9 1 图6 2k 近邻查询处理设置与显示界面9 2 图6 3 预测窗口查询设置与结果显示界面一9 3 图6 4 预测范围查询设置与结果显示界面9 3 第1 v 页 国防科学技术大学研究生院博士学位论文 图6 5 遥感卫星目标监视原型系统结构9 4 图6 6 查询处理引擎系统框架设计9 6 图6 7 遥感卫星目标监视原型系统运行界面9 8 第v 页 国防科学技术大学研究生院博士学位论文 表目录 表1 1 国内位置服务业务应用情况2 表2 1 常用标识3 1 表3 1h v t p r 树索引参数4 8 表4 1 实验参数描述7 2 表5 1 聚集t p r 树索引参数8 7 表6 1 移动对象相关描述信息9 2 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特另0 加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献已在论文中作了明确的说明并表示谢意 学位论文作者签名：查丞 日期 刎年夕月勿日 学位论文版权使用授权书 本文完全了解国防科学技术大学有关保留、使用学位论文的规定。本文授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名： 作者指导教师签名： b 凝柳年夕只；。甚 b 熟知弼年尹其如b 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 课题背景及研究意义 随着近年来无线通信、g p s 等空间定位技术及移动计算技术的发展，在许多应用 如交通调度控制、气象监控、数字战场以及个人位置服务等领域往往需要对移动终端 的位置进行追踪管理以提供相关查询服务。位置服务( l b s ，l 0 c a t i o n - b 硒e ds e r v i c e ) j 是指通过移动终端和无线或卫星通信网络的配合，确定出移动用户的实际地理位置， 从而提供用户需要的与位置相关的信息服务。通过位置服务，公众用户可以获知自己 的位置，获取其它移动用户的位置，获取导航服务，查询附近各种场所的最新信息， 查询公交换乘信息等；行业用户可以开展各种监控、监护、防盗、跟踪、管理业务等 服务。另外，位置服务技术在军事上也得到了广泛应用，如数字动态战场环境下作战 单元的监控和管理、航天侦察中对海上或陆地大型移动目标的跟踪与监视等。位置服 务技术融合了卫星导航、移动通信、i n t e m e t 和数据库等当今i t 行业的各种技术，形 成一个独具特色、前景无限的新兴产业1 2 j 。 1 1 1 位置服务应用背景 人们的日常生活中大部分信息都与位置相关，位置信息也因此成为人们最渴求的 信息之一。位置信息通常可以归纳为两大类：移动位置信息，主要指运动车辆和人的 实时位置，通常以平面坐标方式给出；固定位置信息，也称为地图类信息，是指重要 或明显地物、建筑、机构的详细属性( 方位、距离、到达路线等) 。调查发现，用户 对移动位置信息的需求远远超过了对固定位置信息的需求，甚至在寻求固定位置服务 时也需要借助移动位置信息完成，这也就决定了位置服务技术的主要发展方向是面向 移动位置的信息服务u 】。 位置服务最初来源于北美。2 0 世纪9 0 年代中期，美国联邦通信委员会( f c c ， f e d e r a lc o n u n u l l i c a t i o i l sc o 舢【l l i s s i o 曲于1 9 9 6 年6 月正式将移动电话定位列为其增强型 应急救急系统( e 9 1 1 ) 实施的强制规范，它能够定位呼叫者以提供用户及时救援。1 9 9 8 年1 2 月，f c c 对它的规定进行了补充，允许网络运营商采用基于终端或基于网络的 定位技术。2 0 0 0 年5 月，美国政府将g p s 全球定位系统完全开放给商业应用，使得定 位精度达到5 至5 0 米，大大促进了位置服务技术的推广应用。此后在日本，德国，法 国，瑞典等国家位置服务得到了广泛的关注。 中国基本上是从2 0 0 0 年开始，中国联通、中国移动等公司通过引入国外的成功的 应用和概念在不断的尝试和推广这方面的应用，中国联通利用其兴建的c d m a 网络优 第l 页 国防科学技术大学研究生院博士学位论文 势，大力推动g p s o n e 设备进行定位服务。中国移动则直接利用c e l l i d 方法初步开始 了移动位置服务业务，并计划对其网络稍许进行改造，提供a g p s 的移动位置服务模 式。其中北京移动已于2 0 0 4 年正式推动位置服务业务，随着国内一些地区位置服务业 务的开通，位置服务已经从概念开始转向实用。表1 1 给出了近年来中国位置服务业 务的发展情况1 4 j 。 表1 1 国内位置服务业务应用情况 运营商l b s 业务时间 面向用户 压莒阔 中国移动2 0 0 1 年试验 中国联通 定位之星 2 0 0 3 年初行业用户 中国联通关爱之星2 0 0 4 年2 月个人用户 中国移动亲子通 2 0 0 4 年 个人用户 中国联通汽车g p s 导航服务2 0 0 5 年个人行业用户 中国移动手机地图2 0 0 6 年1 月个行业用户 目前商用的l b s 应用系统主要包括如下p j ：顶级l b s 服务提供商t e l c o n t a r 公司 推出的地理空间软件开发平台d r i l ld o w r i ls e r v e r ，w e b 服务接口h o s t c dw e bs e r v i c e s 及l b s 运行支撑库融c hm a pe n g i n e ，可以满足地图服务、导航服务、随身黄页等大 部分l b s 应用；m a p i n f o 公司提供的集成软件、数据、服务的位置智能( 1 0 c a t i o n i m e l l i g e n c e ) 解决方案，为企业和政府部门提供分析和决策；o r a c l e 公司提供的o r a c l e s p a t i a l & o r a c l el o c a t o r ，内建空间数据模型，支持空间地图服务及s q l 查询等；e s 公司面向移动开发者提供的地理空间服务软件和w e b 服务接口等。 位置服务技术在许多领域中展现了广阔的应用前景【6 】。在军事领域，位置服务技 术可以回答传统数据库所无法回答的查询，如查询离作战单元最近的友做军代号及方 位，查询未来十分钟之内将处于区域a 的所有直升飞机，以及对移动目标未来位置进 行预测等；在民用领域，利用位置服务技术可以实现智能运输系统、出租车警员自动 派遣系统、智能社会保障系统以及高智能的物流配送系统；此外，位置服务技术还在 电子商务领域中展现出了极为广阔的应用前景。具体来讲包括如下： ( 1 ) 地图资源服务：l b s 业务服务平台首先定出用户所处的位置，然后再根据 数据库或互联网提供的信息选出用户所在地的相关信息，供用户查询。例如，要查询 3 公里内的意大利餐馆信息，则l b s 业务服务平台可按照远近标准列出在这一范围内 的意大利餐馆名称返回给用户。资料可以文本的格式( 餐馆名称、地址、电话号码) 或以地图格式( 显示用户位置和餐馆的地图) 显示。 ( 2 )数字战场：在战场环境中，作战单元往往需要知道特定区域内移动目标( 坦 克、直升机、战士等) 的位置信息或需要对重要移动目标位置进行跟踪监视。战场管 第2 页 国防科学技术大学研究生院博士学位论文 理系统位置服务平台负责管理战场环境中的各种移动目标并实时回答作战单元的各种 查询服务。战场环境中的移动目标位置通过无线通信网络、传感器网络或卫星侦察定 位等方式向位置服务平台提交位置信息。例如，查询在x 地区内有多少友军坦克，查 询距离战士y 最近的直升机等，位置服务平台则从服务器数据库中获取移动目标的相 关信息并返回给用户。 ( 3 ) 交通调度与管理：在交通管理系统中，位置服务平台管理移动用户的位置 信息，并回答移动用户的各种查询请求。例如，当用户在驾车行驶过程中需要查询距 离其位置最近的加油站，或交通管理部门需要预测估计在未来十分钟内通过火车站的 汽车数量等。 ( 4 ) 位置广告：l b s 服务业务平台根据移动电话用户所处的位置发送附近商业 企业的广告。例如，当顾客经过某时装商店的商业圈范围时，移动电话中将播放时装 店的广告和商品目录，甚至可以提供电子优惠券等。 ( 5 ) 紧急救援服务：如美国的e 9 1 l 和欧洲的e 1 1 2 等。电信服务商基于移动电 话网络或g p s 定位为公众用户提供紧急救援服务。例如在交通事故或野外事故时，用 户可以利用移动电话呼叫救援，从而可以定位求援者位置并确定最佳的救援方式。 ( 6 ) 导航服务：无线用户可以随时随地知道自己的准确位置。这种信息可以是 文字、声音、图形方式。以此为基础，l b s 系统可以处理用户的各种导航需求，例如 提供用户所在地附近的饭店和宾馆信息，相关的交通路线查询服务，以及最优路径查 询等。这一服务还包括传统的车辆监控服务，交通信息服务。交通信息服务包括向在 交通干线上的用户提供诸如交通阻塞情况、平均车流、车库存车量等相关交通信息。 通常而言，位置服务应用系统应该由数据库服务器、移动基站、位置应用服务器 和大量的移动终端组成，图1 1 给出了位置服务系统的典型应用模式【7 1 。其中，数据库 服务器管理移动终端的位置信息；位置应用服务器则负责收集移动终端的位置更新信 息并发送给数据库服务器，并负责处理移动终端用户提交的各种查询。移动终端与基 站之间通过无线网络进行通信，基站将移动终端位置和提交查询发送给位置应用服务 器，并将查询结果返回给移动终端用户。 r e s u l t suo d a t e a p p c a t i o ns e r v e r d a t a b a s es e r v er 图1 1 位置服务系统典型应用模型 第3 页 融季m 今 旧 ， c 一 e 、 一 、 一一 o ， m 回囱 国防科学技术大学研究生院博士学位论文 位置服务应用系统软件平台可分为三个层次，其中，基础层主要是用于系统平台 正常运行的软硬件资源，以及操作系统及网络环境：数据层是指系统中涉及的各种数 据资源及其数据组织形式，包括电子地图数据、移动目标的位置数据、移动目标的属 性数据等；应用服务层负责完成与用户交互的各种位置查询服务功能。 位置服务应用系统中涉及了空间定位技术、无线通信技术、位置数据管理与查询 处理技术等。随着全球定位系统、g s m 通信网络等基础设施的飞速发展和普及，目前 位置服务系统的瓶颈在于位置数据管理与查询处理技术远不能满足实际应用，现有产 品和技术仅仅满足了用户基本的应用需求。而且随着用户需求不断增长与新兴应用的 出现，移动环境下的位置数据管理与查询处理技术面临着许多新的挑斟引。 1 1 2 课题研究意义 在移动环境下，支持位置服务查询的数据管理与查询处理技术主要包括移动对象 数据库( m o v i n go b j e c t sd a t a b 嬲e ，简称m o d ) 技术、空间数据库技术，以及位置相关 数据的处理技术【9 。12 1 。空间数据库主要用于管理静态的空间对象，如山脉、道路、河 流、地区等；移动对象数据库则主要管理移动对象，如汽车、飞机、舰船等；位置相 关的数据管理技术主要用于处理带有位置属性的普通数据。在上述三项技术中，按照 位置服务查询类型及查询对象的不同可以具有以下组合，即静态查询静态数据、静态 查询动态数据、动态查询动态数据、动态查询静态数据。 ( 1 ) 静态查询静态数据 这类查询属于传统静态空间数据库研究领域，理论和技术研究都已比较成熟。典 型查询包括范围查询即查找给定区域之内的所有静态空间对象，k 近邻查询即查找离 给定查询对象最近的k 个静态空间对象等。 ( 2 ) 静态查询动态数据 这类查询由固定位置用户查询移动对象的位置，因此它属于移动对象数据库的研 究范畴。典型的例子包括查询1 0 分钟内经过长沙的飞机航班、查询未来l o 分钟内穿 过某个区域内车辆数目等。 ( 3 ) 动态查询动态数据 这类查询由移动用户提出，用以查询其它移动对象的位置，它属于移动对象数据 库研究的主要类型。如移动用户查询距离其当前位置最近的警车，查询1 0 分钟内与之 相遇的维修车辆等。 ( 4 ) 动态查询静态数据 这类查询由移动用户提出，用以查询静态空间数据及位置相关数据，因此它属于 空间数据库及位置相关数据处理的范畴。这类查询的例子包括移动用户查询所处位置 的天气预报信息、查询离其最近的医院、餐馆信息等。 第4 页 国防科学技术大学研究生院博士学位论文 上述四类查询中，静态查询静态数据和动态查询静态数据属于传统空间数据库研 究领域，近年来相关理论和技术已非常成熟。而针对静态查询动态数据和动态查询动 态数据查询处理的移动对象数据库领域研究还处于初步阶段，目前在理论和实际应用 上还不成熟，存在许多问题和技术需要解决【9 ，1 1 1 。为了具有更好的针对性，本文仅仅 重点研究面向位置服务的移动对象数据库关键技术。 移动对象数据库是指对移动对象的位置及其它相关信息进行存储与管理的数据库 u 毛1 4 ，l 引，是属于时空数据库的研究范畴。在移动对象数据库中通常管理着大量的移动 对象，这些移动对象的位置是不断变化的，如汽车、飞机、移动用户等。移动对象数 据库技术涉及数据库技术、分布式计算技术、以及移动通信技术等多个学科领域，具 有较高的学术起点。移动对象数据库研究的主要领域包括：移动对象位置的表示与建 模、移动对象索引技术、移动环境下的查询处理技术、以及移动对象位置不确定性的 表示与处理等等1 1 6 j 。 ( 1 )移动对象位置的表示与建榭1 7 彩】f 为了对移动对象的位置进行有效的管理，移动对象数据库系统必须能够准确地获 取移动对象的当前位置信息。而定位技术和无线通信技术的发展使得跟踪和记录移动 对象的位置成为可能。为了方便叙述且不失一般性，我们假设移动用户的当前位置通 过g p s 设备得到【l7 ，埔j 。 有了移动对象的当前位置信息之后，我们就可以处理与当前位置相关的查询请求， 如查询目前处于a 街区的所有警车等，但这仅仅是一类最为简单的应用。在有些更为 复杂的应用中，我们不仅需要查询移动对象的当前位置，而且还要查询移动对象的过 去位置或者预测移动对象未来位置，因此需要提供更为复杂的数据类型以准确地描述 移动对象的位置信息1 1 9 捌。 移动对象的轨迹随着时间不断延伸，假若在数据库中存储移动对象的实际位置， 那么当移动对象位置连续变化时，必须定时的向数据库发出更新请求，而数据库则记 下每次更新时移动对象的空间位置。为了保持移动对象位置信息的有效性，一种简单 的方法就是周期性地刷新数据库，但这种方法效率非常低下：如果周期选择过短，则 会给系统带来严重的计算及通讯开销；反之，又会造成较大的误差。显然，利用这种 简单的快照数据模型来描述移动对象历史和当前轨迹，会造成数据库存储随着时间变 化线性增长，在实际应用中是不可行的。为了减少数据库中移动对象历史轨迹的空间 存储开销，人们提出了两种解决方法：( 1 ) 抽样方式，将移动对象历史轨迹按照某种 采样时间间隔( 或在特殊时间片上) 进行抽样存储，然后对抽样点之间的轨迹则用线 性插值进行拟合；( 2 ) 存储移动对象的运动行为，即在数据库中存储描述移动对象运 动的参量信息( 如起始位置、速度矢量等) ，只有当移动对象的某个运动参量发生变 化时才对数据库进行更新【2 1 盈，2 3 1 。 第5 页 国防科学技术大学研究生院博士学位论文 针对移动对象当前和未来位置的建模通常是将移动对象的位置抽象为关于时间的 函数。系统可根据时间函数计算出移动对象在未来任意时刻的位置。这样一来，移动 对象就不再需要周期性地向服务器报告自己的当前位置，而只有当实际位置与计算位 置的偏差达到一定的阈值或速度矢量发生变化时，才需要发出位置更新请求并对数据 库进行更新。这种方法极大地降低了数据库的计算及通讯代价，己经成为目前移动对 象数据库研究领域中位置建模的主要方法【2 4 ，2 5 ，2 6 1 ，目前较为通用的建模方法是利用线 性时间方程对移动对象轨迹进行拟合，另外国内外许多学者也提出了利用多项式时间 方程对移动对象轨迹进行建模的方法。 ( 2 ) 移动对象索引技术 移动对象数据库中通常管理着数量非常庞大的移动对象集合。在查询处理时如果 扫描所有的移动对象记录将会极大地影响系统的性能。为了减小数据库搜索空间，就 必须对移动对象位置进行索引。 移动对象索引方法通常借鉴于传统空间数据索引技术，不同之处在于移动对象索 引中有一维必然是时间维。在空间数据索引方面人们已经提出了许多方法【2 7 3 0 】，如r 树【3 1 】及其变种r 宰树【3 2 】、x 树【3 3 1 、g d 文件3 4 1 等。这些方法对移动对象的索引具有很 好的借鉴意义，但是它们并不能直接用于移动对象的索引。这是因为上述方法更多地 考虑的是空间查询效率，而没有着重考虑索引的更新代价。在移动对象数据库中，移 动对象的位置更新会引起索引结构的频繁动态变化，因此必须考虑索引查询性能随着 时间下降以及索引更新性能的问题。 移动对象索引技术根据查询时间窗口范围可以分为三类：检索移动对象历史轨迹 信息、检索移动对象当前位置信息以及移动对象未来趋势预测。目前国内外许多学者 针对不同的应用提出了各种移动对象索引技术，但总体来说移动对象索引技术方面的 研究仍然处于初步阶段，大量的研究尚有待进一步深入。其中移动对象未来趋势预测 技术由于更适合在智能交通调度、位置服务等领域的应用而得到了广泛的关注，是一 个充满挑战性的研究方向【3 5 】。 ( 3 ) 移动环境下的查询处理技术。 传统空间数据库中得到广泛研究的各种查询如窗口( 范围) 查询、k 近邻查询以及 聚集查询等等在移动环境下有着相应的查询类型。与传统空间数据库不同，由于移动 环境下查询对象( 移动对象) 及查询本身的动态性，上述查询结果有着很强的时态语 义。例如查询“根据我当前的运动速度和方向，在未来5 分钟内距离我最近的两个加 油站”，其结果表示为 ， ，含义为移动对象a 和移动对象 b 在1 分钟内距离查询对象最近，而随后的1 分钟到5 分钟之间则是移动对象b 和移 动对象c 。显然，在移动环境下，瞬态查询如“现在距离我最近的加油站”是没有意 义的，一旦查询对象和或查询本身位置发生变化，查询结果很快变为无效。移动环境 第6 页 国防科学技术大学研究生院博士学位论文 下查询结束条件依赖于用户应用，如时间条件( 未来5 分钟) ，基于结果( 直到有满 足查询谓词的结果出现) 等等。 移动环境下查询通常表现为连续查询，即使查询对象是静态的，但是由于查询本 身的动态性，查询结果也会发生变化( 如运动的窗口查询) 。因