王植

（西安航空职业技术学院 陕西 西安 710089）

如今轨迹数据管理[1]在现实中的应用十分广泛，在军事、经济、金融、交通、公安等都有着广泛的应用，轨迹数据管理的作用显得越来越突出。在上世纪末以及本世纪初的短短几十年里，全球定位技术和无线通信技术迅速发展，这使管理移动对象轨迹信息成为可能，同时也使得移动对象轨迹的其他研究诸如查询和管理得到人们广泛而深入的研究。一些传统的轨迹数据管理仍仅致力于有效处理非时空属性的移动对象，但移动对象的移动是不间断动态的，即移动对象[2]的位置是随着时间的变化而连续变化的，那么在变化过程中更新数据库时就与非时空属性的情况不一样。因此，在移动对象轨迹数据管理中，轨迹模型[3]的建立以及移动对象的信息更新都需要重新考虑。而轨迹数据管理的查询是轨迹数据管理的重要部分，它的设计对整个轨迹数据管理有着至关重要的作用。近几年又出现了时空棱镜的相关研究，这对于时空移动对象的不确定范围查询有着重大的意义。

1 轨迹数据及不确定范围查询模型

在不确定范围查询中，从数据方面分类，主要包括不确定数据查询和确定数据查询以及连续轨迹数据查询和离散轨迹数据查询，本文在路网空间轨迹数据较为精准且采样频率较低的前提下，主要研究确定的离散轨迹数据。由于采用离散轨迹数据，因此轨迹在离散点之间存在很大的不确定性，而轨迹数据的不确定模型对于查询算法的设计有着很大的影响。早期诸多研究采用的是气瓶来表示两点间的不确定时空空间，但这种方法增加了很多开销。在近几年的研究中开始采取时空棱镜来表示不确定时空空间，它更加精确、更加接近于现实情况，从而大大减小了算法的开销。一个时空棱镜[4]指一个向上的指向锥和一个向下的指向锥的交叉时空空间，它能够表示在两个连续时空点间的运动物体的所有可能的轨迹，确定可达的时空空间，如图1所示。

图1 时空棱镜Fig.1 Space prism

图1 中左示例即为时空棱镜的一种较为普遍的情况，右示例为由多个时空棱镜所组成的生命线项链，生命线项链使时空棱镜的研究更加接近于现实情况，而且在路网空间的研究中也有着很重要的作用。

轨迹数据的不确定模型能够较准确地确定移动对象的移动范围，而轨迹的不确定范围查询指移动对象在某一时空点发生重大事件后，以所得有限条件所做的范围查询。由于轨迹数据条件限制，其查询结果具有很大的不确定性，是一个时空范围。时空棱镜模型是在轨迹样本点之间对移动对象位置的不确定性建模，因此可以在以路口为基本采样点的路网上延伸时空棱镜做不确定范围查询。

2 轨迹数据管理中不确定范围查询算法的思想

2.1 轨迹模型的构造

一个轨迹样本尽管已经对原有轨迹进行了采样处理，大大减小了开销，但是当包含大量的轨迹点时，如果不进行分类，也会使实验处理增加困难。轨迹样本作为轨迹数据存储后，轨迹数据管理就会根据所要进行的操作对轨迹数据进行处理，如果轨迹数据很繁杂，比如有不同移动对象的轨迹数据，不同时间段的轨迹数据，如果再以遍历方式查询的话，将会大大增加系统开销，因此，提出标签这一概念，在原有轨迹模型上加入标签，这样不仅可以直接区分不同的轨迹样本，而且在进行查询的时候，也可以大大减小开销。

定义1（轨迹样本关系）如果该轨迹是一段连续完整的轨迹，则Ti可以用分段函数等方式表示。如果这段轨迹并非一段连续完整的轨迹，则关系R称之为轨迹样本关系，且R是一个有限元组。

定义2（路口区域）轨迹的样本点为路口时，路口区域可表示为：

其中id表示路口编号，t表示经过此路口区域的时间，x表示此路口的横坐标，y表示此路口的竖坐标，v表示通过此路口的速度。 那么轨迹样本关系可以表示为（ai， idi，j， ti，j，xi，j， yi，j， vi，j），在进行不确定范围查询时，可以根据轨迹样本关系得出其所经路口顺序。

为实现本文中的查询算法，使用轨迹生成器生成了某一城市中的具体轨迹信息，包括各路段以及各路口的坐标信息等。在存储路口信息的时候则是首先读取其横竖坐标并存储，建立的路口模型如图2所示。

图2 路口模型Fig.2 Crossing model

在此基础上读取所给文件中的相应信息。一般文件信息中包括路口的很多信息，但本文主要存储路口对于查询比较重要的信息，主要包括路口的id以及路口的横坐标以及竖坐标。根据路口的id以及路段文件，可疑判断出哪些路口之间有路段，哪些路口之间是不可达的，对于可达的两个路口根据其横竖坐标可以计算出其长度，为计算最短距离做准备。

由于本文主要侧重于研究不确定范围的查询，因此对于路网上的路段不作深入研究，本文假设路网的路段皆为直线段，并在两个路口之间。路段可以包括很多信息，路段上移动车辆的平均速度，以及连接的路口，路段长度等。

定义3（路段区域）路段区域定义为如下形式：

其中id表示路段的编号，node1、node2表示路段所连接的2个路口，length表示路段的长度，v表示经过此路段时的速度。

本算法的路段模型如图3所示。

图3 路段模型Fig.3 Section model

图3 给出了路段的简化模型，包括路段编号、路段连接的路口、路口坐标、速度等。根据这些信息，可以计算出在后续查询中所要使用的信息，包括路段长度、路段平均时间等。

在所给数据集中，每个路段的这些信息应该被提取出来，为其建立R树索引[5]，并建立相应的数组存储一些信息。数据集中根据所给路段模型可完成对信息的提取。路段长度可由路段所连接的两个路口的位置并根据距离公式计算得出。在轨迹模型建立完成之后，即可为轨迹数据建立索引。建立索引完成后，即可根据本文设计的查询算法完成相关的查询内容。

2.2 轨迹数据的索引

在诸多索引结构中，R树索引是近年来采用最为普遍的一种，适用于建立路网空间的索引。本文的研究即采用R树索引，并将基于R树做进一步的改进。

在R树叶子结点中，选择一个合适的叶子结点并将路段的不确定矩形框插入之。对于R树合适的评价标准是插入下一个路段的不确定矩形框后，MBR面积增加最少。如果这个叶子结点还能容纳不确定矩形框，则直接插入；否则，将该叶子结点分裂成两个叶子结点，且这两个叶子结点包含要输入的矩形框和原来含有的矩形框。分裂时，使得这两个叶子结点对应的矩形区域之和最小。分裂之后，从叶子结点向根结点进行调整。如此直至将路段的矩形框都插入到R树中。路段的R树结构如图4所示。

图4 路段的R树结构Fig.4 Section of the R tree structure

对路网空间路段的不确定矩形框建立一棵R树，并通过对其搜索区域的范围查询来实现对路段的查找。通过路段的不确定矩形框建立R树[6]，可以在很大程度上提高查询速度。

在轨迹生成的大量信息中，根据建立的轨迹模型，应该筛选轨迹信息。其中路口的信息主要包括路网路口的编号以及横竖坐标。其基本算法思想为读取相应时空数据文件中的有效信息并存储，在进一步的运算中，可以根据路口编号得到其横竖坐标以及速度信息等。在计算路段的距离时，可以建立动态二维数组，根据所连接的两路口计算并存储路段的长度。同时可以存储路段的平均速度等信息，本文主要采用数组完成。

2.3 MBR的改进

前面提到了MBR的改进，所要查询的路段其范围比原MBR增加的长度为最大可能移动距离。如图5所示。

图5 MBR的改进Fig.5 Improvement of MBR

图中有 A、B、C、D、E、F 6个路口， 路口之间存在连线表示两路口之间存在路口，是可达的。如图所示，6个路口之间共存在 6 个路段：AD、BD、BC、CE、DE、EF， 以路段为单位建立R树索引并建立MBR，如图所示，以各路段的路口为断点并平行于坐标轴建立MBR，如果所要做的查询不确定范围在BD路段，则根据速度以及时间间隔计算出的最大可能移动距离为BD路段建立改进后的MBR，如图5所示。为轨迹数据建立MBR的算法思想基本如下：

由轨迹数据集计算出各路口以及路段的信息，并根据已知轨迹信息建立路段模型；

建立路段的R树索引，建立各路段的MBR[7]；

根据所要查询的路网中路段的最大速度以及时间间隔计算出最大可能移动距离l；

根据l建立不确定范围路段的MBR。

而在具体实现建立不确定范围所在路段的MBR时，需根据两路口的坐标大小以及最大可能移动距离确定插入的MBR位置。

2.4 查询算法的改进与实现

路网空间不确定范围查询的总体处理流程包括基于路口的查询流程以及基于可移动对象的查询流程，在对这两种查询流程的简单评估后，选择基于路口的查询流程继续深入研究。

根据前文所示，流程如图6所示。根据流程图所示，在得到路网空间传感器的数据集后，建立各路口以及各路段的R树索引，建立索引完成后，根据所要查询的不确定范围所在的路口或者路段的最大移动速度以及查询时刻与犯罪时刻的时间间隔计以及时空棱镜的相关知识计算出最大可能移动距离，以改进的MBR建立该路段的R树索引。

图6 基于路口以及改进MBR的一般查询流程Fig.6 Based on the intersection and improved MBR general query process

与不确定范围查询对象所在路段的MBR重叠的路口或者路段列入可疑结果集，并作进一步的判断，若可疑路口与不确定范围所在路段连接的路口的最短距离小于最大可能移动距离，则该路口为可疑路口。最后根据速度、时间进行线性插值，得到移动对象的位置范围。

按照上述流程，路网空间中基于路口的不确定范围查询基本完成。需要注意的是，在进行查询一次后，如果需要重新进行查询，则需要将原R树索引中查询路段的改进MBR删除，并建立新查询路段的改进MBR。

根据上述流程，可以得出不确定范围查询的算法。算法首先根据所得结果集得出路口以及路段集，并建立R树索引，在此基础上对所要查询的路段E1的MBR做了修改，为其建立改进的MBR，并根据所查询路段MBR与其他路段MBR的重叠情况初步得到路口结果集，缩小了路口node的查询范围。在所得node集上作进一步判断，计算与E1所在路口node1的最短距离S1，并将S1与最大可能移动距离l相比，根据比较结果，如果S1小于1，则该路口为可疑路口，加入到结果集中。最后根据速度以及所在路段、路口、时间，利用线性插值法，计算最大可能移动范围的坐标。

3 实验评估

本文主要验证轨迹数据管理不确定范围查询处理中的查询效率和查询准确率。实验结果的分析主要根据CPU计算时间以及返回的结果集。实验硬件环境是：处理器为Core Intel（R）CPU i3-2310M@2.10 GHz 2.10 GHz， 内存为 2GB RAM。实验的软件环境：Windows 7操作系统和Visual Studio 2008集成开发环境。

实验数据由生成路网空间交通信息的generator模拟传感器而生成的数据，包括路口信息以及路段信息。其中路口信息包括路口坐标、路口id以及路口监测速度v。路段信息主要包括路段所连接的路口以及路段id。

实验过程中，针对使用改进后的MBR以及未改进的MBR进行对比并分析结果。

首先对比基于R树索引的一般查询以及基于改进MBR的查询，在不同大小的数据集的情况下的查询效率。

图7 查询效率的对比Fig.7 Query efficiency comparison

图中横坐标为路口数据集大小，纵坐标为时间，单位为秒。数据集为generator生成的路网空间数据，时间为建立R树索引以及输入查询路口到查询结束的时间。数据分为40、80、120、160个路口4种情况，查询时间为10次查询时间的平均值。

在此基础上，对比两种查询的准确率，数据为在路网约束的条件在所设计的空间移动对象。

图8 查准率的对比Fig.8 Precision comparison

图中横坐标为路口数据集大小，纵坐标为查询准确率百分比。查准率的计算方式为根据路网中在某一时刻经过某路段的移动对象经过一段时间所在的位置确实在查询结果范围中的比例得出，路口数据与查询效率中的数据一致，并预设车辆在3个查询路段，最后计算3个路段准确率的平均值得出。

根据实验结果分析可以得知，在基于R树索引的一般查询，当数据较大时，其查询时间会大幅增长。而使用改进MBR的查询，不仅在查询时间上大幅降低，而且在查询准确率上较原有情况也略有提高。

4 结束语

文中侧重于轨迹数据管理中的查询算法的分析与实现，并详细研究了不确定范围的查询实现。主要分为以下四部分：轨迹数据的读取与计算、R树索引的建立、MBR的改进、基于时空棱镜的二步查询。

在建立轨迹模型的过程中，改进了轨迹模型，加入了其他的轨迹信息，方便查询实现。在查询阶段，使用了改进的MBR，并分为两步查询，减少了查询对象并减少了系统开销。

由于考虑到设备条件限制，研究重要侧重于路口以及路段的平均情况，在以后的工作中，可以在本文基础上对移动对象进行查询，并且对移动车辆建立TPR*树索引，这样可以大大提高查准率。

[1]Goce Trajcevski，Alok Choudhary，Ouri Wolfson，et al.Uncertain range queries for necklaces[J].In Mobile Data Management（MDM），2010：199-208．

[2]Kuijpers B.Dealing with Uncertainty in Trajectory Databases[C]//In 2010 17th International Symposium on Temporal Representation and Reasoning，2010：7-8.

[3]Kuijpers B，Moelans B，Othman W，et al.Analyzing trajectories using uncertainty and background information[J].In Lecture Notes in Computer Science，2009:135-152.

[4]Kuijpers B，Othman W.Trajectory databases:Data models，uncertainty and complete query languages[J].In Journal of Computer and System Sciences，2010，76（7）：538-560.

[5]ZHANG Wen-jie.Indexing and Querying Techniques for the Past，the Present and the Future Information of Moving Objects[M].In Master theses of Harbin Institute of Technology，2006.

[6]刘文闳，熊伟，吴烨，等.空间索引并行批量加载算法研究[J].现代电子技术，2011，34（22）：90-94.LIU Wen-hong，XIONG Wei，WU Ye，et al.Research on parallel bulk-loading algorithm for spatial index[J].Modern Electronics Technique，2011，34（22）：90-94.

[7]肖金城，王恩泉，胡特彧.三维地理信息应急指挥系统设计[J].测绘科学，2011（2）：181-183.XIAO Jin-cheng，WANG En-quan，HU Te-yu.Design of 3D geographic information emergency commanding system[J].Science of Surveying and Mapping，2011（2）：181-183.