一种改进的基于交通网络的移动对象索引方法.pdf

《一种改进的基于交通网络的移动对象索引方法.pdf》由会员分享，可在线阅读，更多相关《一种改进的基于交通网络的移动对象索引方法.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、书书书文章编号：!#$%&#（(%）#$#)*$#+一种改进的基于交通网络的移动对象索引方法!胡大权，邹永贵（重庆邮电学院，重庆#&%）摘+要：通过对基于交通网络（简称网络）移动对象索引方法,-.$/011 的分析，提出了一种改进的/-.$/011 方法。该方法充分利用网络信息，增大空间索引粒度，使用更合理的时间间隔，加强对轨迹的索引。性能分析说明了/-.$/011 方法较大程度地减少数据存储量和索引尺寸，提高了插入性能，并能有效地进行轨迹索引。关键词：索引；空时数据库；移动对象；交通网络；树中图分类号：/2*!3!(；4#%+文献标识码：5!引 言随着无线通信技术、定位技术以及集成电路技术的

2、发展和民用化，基于位置的服务（678）!日渐显露出美好的前景，并突显出潜在的巨大商业价值。无论是车辆监控、供应链管理、数字战场、移动电子商务等实际应用，还是战场仿真、网络游戏等虚拟环境都需要时空数据库系统（8/97:8）对大量移动对象的时空数据进行实时存储和快速检索，而索引则扮演着重要的角色。近几年，人们对时空索引做了大量的研究，针对不同的情况提出了许多索引方法，如*9.$/011(，/7$/011*，;.$/011#，:?ABC1）称作边（1DE1），多线由一系列的点!，!(，!*，表示，相邻(点!F!和!的连线称为线段（BC1 G1EH1CI）。如图!所示，移动对象只能沿着边运动，经过结点

3、再到另一条边。#移动对象索引方法$%&()*,-.$/011)是一种基于.$/011的混合索引结构，是用一棵二维（(9）.$/011 以线段为粒度索引相对固定的网络。(9.$/011 的每个叶结点对应一棵一维（!9）.$/011，索引移动对象对应线段上运动图!+交通网络,BE3!/0JKKBL C1IM?0N的时间间隔（IBH1 BCI10OJ）。由于存储在(9.$/011 中的空间对象是组成网络的线段，其叶结点数据项（PCI0A）形如（6BD，:77，Q0B1CIJIB?C），其中 6BD 为线段标识，:77 为线段的最小外接框（HBCBHRH S?RCDBCE S?T），Q0B1CIJ$I

4、B?C 表示线段的方向，每个叶结点还有一个指向!9.$/011 的指针。(9.$/011 的内部结点的数据项形如 I0，:77，其中 I0 是指向子结点的指针，:77 为覆盖 I0 所指的子结点的最小外接框。!9.$/011 的叶结点的数据项形如（:BD，6BD，#1CI0JCL1，#1TBI，9B01LIB?C），其中:BD 为移动对象标识，6BD 为线段标识，#1CI0JCL1和#1TBI分别表示移动对象进入和离开线段时刻，9B01LIB?C 表示运动方向。每当移动对象离开一条线段时执行,-.$/011 的插入算法，即以线段的起止坐标（$GIJ0I，$1CD，%GIJ0I，%1CD）为参数

5、在(9.$/011 查找包含线段的叶结点；再以运动的时间间隔（#1CI0JCL1，#1TBI）为参数，附带:BD，6BD，9B01L$IB?C 等信息，插入到所找到的(9.$/011 叶结点对应的!9.$/011 中。考虑到时间单调递增的特点，新数据项只是简单地插入到!9.$/011 最近（最右）的叶结点，而不是用.$/011 的插入算法，这样可以提高存储空间利用率。当以时空窗口（*9 间隔）为参数执行范围查找第#+卷第,期重庆邮电学院学报（自然科学版）-./0#+%.0,1!2 年 3 月4.5)67/.8 9:.6;6=?*)=AB.8 C.A 76D(*/*E.FF56=E7A=.6（%

6、7A5)7/GE=*6E*）H5;0 1!2!收稿日期：(#$!$!#+修订日期：(%$#$!作者简介：胡大权（!=#$），男，重庆垫江人，讲师，在职研究生，研究方向：UV8，时空数据库，P$HJB：WRDXY W?IHJB3 L?H。时分!步：!先在#$%&(中用$%&(的查找算法)查找空间查询窗口所包含的线段和叶结点；在查找出来的叶结点对应的*#$%&(中，用$%&(的查找算法查找时间间隔包含的数据项；#删除不符合第!步结果的数据项。+,$%&(现存在如下!方面的问题。（*）无法直接得知移动对象经过线段两端点的时刻。实际应用中，系统通常是周期性地获得移动对象的时空信息，移动对象报告位置的时

7、刻不一定恰好在线段的两端点上，如图 所示。如果通过推算来得知移动对象经过线段两端点的时刻，则计算量增大，而且某些情况（如图 的-，(所示，其中图(给出了移动对象经过此条线段，但没有报告位置）难以推算，并且，推算存在一定的误差甚至错误，从而导致检索结果不准确。图.移动对象经过线段时报告位置的/种情形+012 +03(456(6 78 9745:07;(7?(4:A730;1 7;75-6(1A(;:（）索引和存储的数据有大量冗余。如图!所示，按照传统的索引方法需要存储和索引每个样点的时空信息（!，#，$），按照+,$%&(需要存储和索引每条线段两端点的位置和时刻。而移动对象在一条边上通常以恒定的

8、状态（速度、方向等）运动，只需知道移动对象在这条边上运动的起止时刻，就可以通过一定的方法（如插值）计算在起止时刻之间的任一时刻的位置，这样，大大地减少了数据的存储量和索引尺寸。图!.移动对象经过一条边时各个抽样时刻报告的位置+012!B5A(;A730;1 7;75-（!）不能有效支持轨迹索引。为了索引轨迹，只能采用文献!给出的代价非常高的算法。其步骤分为!步：!用$%&(的范围查找算法，找出给的时空范围内的轨迹段；再查找与该轨迹段相连的其他轨迹段，即在包含该轨迹段的叶结点中查找，或者以该轨迹段的端点为参数用范围查找算法在其他叶结点中查找；#重复步骤!和，直到找出符合条件的部分轨迹段或全部轨迹

9、为止。!改进的移动索引方法#$%&#(针对上述问题，提出了一种改进的基于交通网络的移动对象索引方法&,$%&(（:58804;(:=7C$%&(）。&,$%&(基本思想和+,$%&(类似，同样使用了#$%&(和*#$%&(的混合结构。不同的是：#$%&(以边为索引粒度，*#$%&(索引移动对象在相应边上第一次和最后一次报告位置的时间间隔。为了有效地索引轨迹，利用了&D%&(的思想将*#$%&(中移动对象经过相邻 条边的数据项用双向链表链接起来。!2)索引结构如图 E 所示，上面的#$%&(索引网络和叶结点数据项为（F0-，GDD）。其中 F0-为边标识号，指向实际存放该边的记录；GDD 为对应

10、边的最小外接框，每个叶结点有一个指向*#$%&(的指针:(:。中间结点的数据项为（:，GDD），其中:指向子结点，GDD 包含子结点中所有数据项的最小外接框。*#$%&(索引移动对象在边上的运动的时间间隔。叶结点数据项为（G0-，F0-，$806:，$956:，H0;C），其中 G0-表示移动对象标识号；$+06:，$H56:分别为第一次和最后一次在边 F0-报告位置的时刻。H0;C 为移动对象从一条边运动到另一条边的 个数据项的双向链接指针。此处不再像+,$%&(那样设置一个运动方向的标记，因为运动方向是时空信息衍生出来的，可由应用系统处理，只要知道起止位置及时间的先后就可以确定运动方向。图

11、 E.&,$%&(结构+012 E&,$%&(6:I4:I(!2!插入算法创建网络索引时，以边为粒度，以边的 GDD 为参数，利用$%&(的插入算法将其插入到#$%&(的叶结点。由于网络保持相对固定，一旦网络索引创建好后就基本保持不变。移动对象每次报告位置时在#$%&(中查找并记录当前所在的边 F0-，如果是第一次出现在该.重 庆 邮 电 学 院 学 报（自然科学版）.第*J 卷边上，则记录当前时间为!#$%，如果是最后一次出现在该边上，则记录当前时间为!&$%，与()一起组成一个数据项（()，*)，!#$%，!&$%，+,-），以!#$%，!&$%为一维间隔插入到*)所在结点对应的./012

12、#33中，并与移动对象经历的前一条边的数据项用+,-建立双向连接。移动对象在边上的运动情况和图 4 所示类似，极端情况下，如果移动对象速度太快或边长太短，移动对象在边上可能只报告一次位置，类似图 4)所示，此时当作!&$%5!#$%同上对待；也有可能经过一条边但一次也没报告其位置，类似图 43 所示，此时时空数据库中没有此时空信息，索引中也就没有此信息，这种情况由应用系统来表现。由于时间的单调性，一维时间间隔总是以递增的顺序插入，因此./012#33 插入算法作了如下修改：每一个数据项简单地插入到最近（即最右）的叶结点中，如果该叶结点已满，则新建一个结点并插入数据项，再将该结点插入到最后一个叶

13、结点的父结点中。该算法类同 2612#33 的插入算法。!7 查找算法基于三维间隔（.，#.，4，#4，!.，!4）的范围查找算法步骤如下：!在 4/012#33 中执行 012#33 查找算法8找到给定空间范围内的边和相应的叶结点，保存在内存中；在步骤!中找到的每一个叶结点对应的./012#33 中执行行 012#33 查找算法，找到给定时间范围内的数据项；#用步骤!找到的边（在内存中）筛选步骤的结果。时间片（293$&:3）查找是范围查找中时间间隔为;的一种特例。由于 2012#33 中增加了连接相邻 4 段轨迹的双向链表，因此，轨迹查找非常简单高效，即先用上述范围查找算法，找到符合条件的

14、轨迹段，再沿着双向链表就可以快速地找到所有或部分轨迹。#性能分析与评估我们选择了=中的 2012#33 对比的?/012#33 为参照比较对象，进行了性能分析与评估。7$#存储和索引的数据量假设网络有$条边，每条边的平均长度为%9，每条边平均由&条线段组成。有 个移动对象平均分布在网络上以(9$的速度运动，每个移动对象每隔)$报告一次位置，共有*次。以下分别计算各种索引方法需要存储和索引的数据量（简称数据量，均以元组为单位）。（.）由于?/012#33没有考虑网络的限制，认为移动对象做自由运动，因此每返回一次位置信息就必须存储并索引元组（+，#+，!+）。?/012#33 数据量为 ,*。（4

15、）根据=012#33，除了索引固定网络外，移动对象经历每条线段还需要存储和索引 4 个元组，其数据量为$A B(B*B)%B&B4，其中$表示 4/012#33 索引网络的边的数据量，是一固定值；(B*B)表示每个移动对象*次报告位置时行驶的总距离；*B*B)%B&表示每个移动对象*次报告位置时平均经过的线段数；4 表示每经过一条线段需存储和索引 4 组数据。（?）2012#33 和=012#33 类似，但移动对象经历每条边只需存储和索引 4 个元组，其数据量为：$-,(,*,)%,4C C 以图?为例，?/012#33 应存储和索引!.D!E共E 个时刻的数据；=012#33 需存储和索引?

16、条线段和 F 个时刻的数据，而 2012#33 只需存储和索引一条边和!.，!E4 个时刻的数据。当 B*G G$时（通常如此），?/012#33，=012#33 与 2012#33 数据量的比值为：.4)(：&：.，其中%)(为移动对象平均在每条边上报告位置的次数。也就是说：移动对象平均在边上报告的次数越多，每条边包含的线段数越多，2012#33 数据量相比?/012#33 和=012#33 越少；当移动对象平均在每条边上报告的次数为 4 次时，2 9，每条边平均有H7 EI条线段。如果移动对象以 F;-9 J 的速度行驶，每?;$报告一次位置，?种索引数据量的比值为.K H7 EIK.，即

17、?/012#33 和=012#33 的数据量分别是 2012#33 的.倍和 H7 EI 倍。7!#插入性能根据前面的分析可知：移动对象每次报告位置?/012#33 都要执行一次插入操作，因此插入操作次数最多；=012#33 的插入次数与移动对象经过的线段数相关，如果=012#33 通过推算得知线段两端点的时刻，插入前还有一定的计算量；2012#33 插入操作次数只与移动对象经过的边数相关，几乎没有任何额外计算量，因此 2012#33 执行插入操作的次数最少，从而 2012#33 插入性能最优。7#查询性能由于 2012#33 同=012#33 结构和查询算法类似，2012#33 的查询性能和

18、=可知：在执行查询操作时，必须先查询其上的 4/012#33，这一部分是固定开销。当运动信息?第 I 期C C C C C C C C C C C C 胡大权，等：一种改进的基于交通网络的移动对象索引方法量较少时，!#$%&的性能较优；当运动信息量较多时，%(#$%&的性能将超过!#$%&。时间片查询（如：查询某时刻所有移动对象的位置）由于要遍历所有的)#$%&，因此效率很低。虽然%(#$%&增大了网络索引粒度会使空间重叠量有所增大，降低了*#$%&的查询性能，但%(#$%&索引的时空数据量大大减少，会使%(#$%&的结点甚至树高减少，性能又有所提高，因此总体性能变化不大。%(#$%&插入的是

19、准确的时空信息，因此查询结果必然满足查询条件，而满足查询条件时空信息有可能不在查询结果中，可以通过适当扩大查询范围来减少这种情况，但不能完全避免。类似图*所示情形，移动对象经过了这条边，但时空数据库和索引中都没有相关的时空信息，如果该时空信息满足查询条件，则该时空信息不会出现在查询结果中。事实上，+(#$%&同样会有以上情况，如果+(#$%&中线段两端的时刻通过推算得知，由于推算会存在误差或错误，查询结果反而不一定真正满足查询条件。轨迹查询时，只要先查找出轨迹的一部分，查找其余部分或全部轨迹只需沿着双向链表搜索，其工作量是微不足道的。!结 论本文中我们提出的%(#$%&较大程度减少了存储和索引

20、数据量，当运动信息量较大时，插入和查询性能较好。特别是时间跨度较大的范围查询效率较高，并且对轨迹查询也比较有效。不足的是对时间片查询效率很低。%(#$%&适合于车辆监控与管理等应用。参考文献：),夏英，葛君伟-./0 软件平台的实现技术1-重庆邮电学院学报（自然科学版），*223，)4（*）：)3$)4-*,%5677#880 9，:;，06.80%-0?ABC D AE?C&F BGHIBGJ KC&F&J ELFABE$HB?FBMABCGN;-O&CMHBGJN CK AP%PB&H8666 8GA&GABCGF QCGK&GM CG LFABEHBQCE?LABGJ GH 0RNAEN

21、 Q，5B&CNPBE，1$?G，)SS4，33)$33T-!,O+706#，16(06(Q 0，%5677#880 9-(CUF?&CMPN AC AP BGHIBGJ CK ECUBGJ CV$WMA A&WMAC&BN;-O&CMHBGJN CK AP*4AP 8G$A&GABCGF QCGK&GM CG:&R.&J AVNNQ-QB&C，6JR?A，*222，!SX$324-3,(;0Q86(%7 ;，08.:;1#7-%CY&HN PBN$AC&BMF#$A&N ;-O&CMHBGJN CK AP)!AP;Q 0RE?CNBLE CG;?FBH QCE?LABGJ（;Q$0;QZ S

22、T）Q-)SST，*!X$*32-X,%;7 9，O;O;8;0-U!#$A&：N?ABCAE$?C&F MMNN EAPCH KC&ABENAE?GH BGA&UFL&BN;-O&CMHBGJN CK AP*AP 8GA&G$ABCGF QCGK&GM CG:&R.&J AVNNQ，*22)，3!)$332-4,0;.%6(80 0，16(06(Q 0，.6%6(6=6#0%，A F-8GHIBGJ AP?CNBABCGN CK MCGABGLCLNFRECUBGJ CVWMAN ;-O&CMHBGJN CK AP)SAP;Q$08=78GA&GABCGFQCGK&GMCGGJEGA CK

23、A Q-FFN，%IN，*222，!)$!3*-,彭大芹-移动对象数据库中的索引机制 1-重庆邮电学院学报（自然科学版），*22!，)3（)）：!X$!S-T,+#6(%;(;-#$%&N：HRGEBM BGHI NA&LM$AL&KC&N?ABF N&MPBGJ;-O&CMHBGJN CKAP)!AP;NNCMBABCG KC&QCE?LABGJ MPBG&R08=7 QCGK&GM Q-)ST3，3$X-（责任编辑：龙能芬）#$%&()*+,*)-$)./0,+1$2$(+,3 45).61+,6&022+.,)67&85$LG，7 9CGJ$JLB（!#$%&$%($)*+,-.#/0#

24、,-,1$2 3*4*5#667$51-#$,，!#$%&$%32224X，08 98!$1）9416&0.6：8G APBN?&，AP%(#$%&BN?&C?CNH AC BE?&CU AP+(#$%&，YPBMP BGHIN AP ECUBGJCVWMAN BG A&KKBM GAYC&-%P%(#$%&HC?AN F&J&BGHIBGJ J&GLF&BAR GH EC&NCGVF ABE BG$A&UF GH?&CUBHN G KKBMBGA A&WMAC&R BGHIBGJ EAPCH-%P?&KC&EGM GFRNBN NPCYN APA AP%(#$%&J&AFR&HLMN AP NAC&J GH BGHI NB_，BE?&CUN BGN&A?&KC&EGM，GH?&KC&EN A&WMAC&R BG$HIBGJ KKBMBGAFR-:);7&*1：BGHI；N?ABF$AE?C&F HAVN；ECUBGJ CVWMAN；A&KKBM GAYC&；A&3,重 庆 邮 电 学 院 学 报（自然科学版）,第)卷!第 期#胡大权，等：一种改进的基于交通网络的移动对象索引方法