1815一种基于城市交通网络的移动对象全时态索引

一种基于城市交通网络的移动对象全时态索引基金项目：国家自然基金项目（60073014,60273018）、国家863计划项目（2002AA116030）、教育部科学技术重点项目（03044），教育部优秀青年教师资助计划项目一种基于城市交通网络的移动对象全时态索引IndexingthePast,PresentandFuturePositionsofMovingObjectsinUrbanTrafficNetworks陈继东孟小峰胡志智李本钊肖珍（中国人民大学信息学院北京100872）（{chenjd,huzhizhi,libz,xiaozh,xfmeng}@ruc.edu.cn）Abstract:AdvanceinwirelessInternetandpositiontechnologiessuchasGPSenablenewdatamanagementapplicationsthatmonitorcontinuousstreamingdata.Intheseapplications,efficientmanagementofsuchstreamsisachallenginggoalduetothehighlydynamicnatureofthedataandtheneedforfast,on-linecomputations.Inthispaper,wepresentanovelindextechniqueforqueryingthepast,presentorfuturepositionsofmovingobjectsinurbantrafficnetworks.Inparticular,wefirstinvokeasimulationbasedpredictmodelforthevehiclesfuturetrajectorywhichismoreprecisethanthetraditionalpredictmodelinTPR-tree.Moreover,exploitingthefeatureoftrafficnetwork,wepresentadynamicstructuretermedAU(AdaptiveUnit)anddevelopittoanR-treebasedindexnamedcurrent-AU.Finally,bynaturallyextendingtheAUweproposepast-AU,whichiscapableofindexinghistoricaltrajectoryandatthesametimeavoidthedeadspacewhichisinevitableinTB-tree.EmpiricalstudiesindicatethattheAU-treeoutperformsthetraditionalTPR-treeandTB-treeinseveralaspects.KeyWords:MovingObjectdatabase,MovingObjectindexing,LocationModel1.介绍随着3G时代的到来，众多具有定位功能的无线手持设备的大量普及，促使一类基于位置的服务，称为位置相关服务（LocationBasedService）成为可能。位置相关服务包括交通管理，军事指挥，基于位置的信息服务等众多领域[1]。提供位置相关服务需要用到移动对象位置的实时数据，这些数据一般可以通过GPS（GlobalPositioningSystem）或基站定位获得。由于这些数据自身的动态特性（连续的变化）和查询的实时要求，因此如何高效的管理移动对象的位置数据成为一个具有挑战性的目标。而移动对象数据库MOD（MovingObjectDatabase）就是对移动对象的位置及其相关信息进行管理的数据库。它也是位置相关服务最重要的技术基础。MOD是数据库研究近年来发展起来的一个分支。移动对象数据库遇到的核心科学问题有以下几点：1.移动对象位置获取。即怎样在有限的无线带宽限制下获得大量的并随时间频繁更新的移动对象位置信息。2.移动对象位置建模。即当服务器收到移动对象位置信息后，用什么样的模型来表示这些原始的位置数据，以方便下一步更有效的应用这些数据。3.移动对象索引。即如何设计一种新的索引技术来索引频繁更新的移动对象位置信息，并且能够进一步适应其对历史轨迹信息的查询。在实际移动对象索引中，通常第二和第三个问题是紧密联系在一起的，移动对象索引建立的前提是有一个良好的位置模型，即对动态的数据如何进行抽象的表示。本文主要讨论这两个问题和其解决方法。到目前为止，几乎所有的移动对象都从以前的空间索引演变而来，它们考虑的是抽象的二维平面移动对象，而移动对象最主要是分布在城市的公路上的，并且公路上的移动对象运动速度较快，而且速度变化频繁，对索引更有挑战，近来越来越多MOD的工一种基于城市交通网络的移动对象全时态索引作是开展在城市交通网上的。本文首先从移动对象位置模型入手，根据城市交通的特征，率先采用国际上被广泛使用的交通模拟模型“元胞自动机（CA）”为基础，采用模拟预测的方法代替在其他索引中普遍采用的数学方法，优化了移动对象位置模型，使位置预测精度大大提高，这样就降低了索引的频繁更新程度。在基于模拟的位置模型基础上，利用交通系统的特征，我们设计了更符合路网车辆运动规律的AU索引，它以一个新的动态结构——自适应单元（AdaptiveUnit，简称为AU）为基础（索引名称也由此而来）发展而成，包括Current-AU和Past-AU两部分，分别支持移动对象当前、将来位置查询和历史轨迹查询。自适应单元AU类似于移动对象索引TPR树中的一维MBR，但AU有更好的适应性，可以避免TPR树[8]中随时间推移MBR的大量重叠，从而带来查询性能恶化的问题。另外我们在Past-AU中使用了路段容器模型，使得AU能够有效的避免其他历史索引中索引空间浪费造成大量死空间问题。本文贡献：1.引入“基于模拟预测的位置模型”，采用元胞自动机模型模拟交通路网上的移动对象运动，然后对预测出的离散点进行回归，取代传统的线性预测模型，以达到更好的预测精度，从而降低更新率。2.针对城市交通特征，提出一个混合索引AUIndex，其中AdaptiveUnit动态结构能很好的适应快速变化的移动对象运动特征，从而保证较高的查询效率。3.在此基础上拓展AUindex结构，适AU支持历史数据查询和轨迹查询，使用路段容器模型有效的避免其他历史索引中索引空间浪费造成大量死空间问题。2.相关工作位置模型方面：现有的DBMS不能很好的处理连续变化的数据，如移动对象位置。原因在于，在现有DBMS中，除非被显示修改，数据都被假设是不变的。这样，数据库中表示的移动对象以及索引，必须被不断更新，如果使用传统的索引方法，可能索引还未建好，就涉及到又一次更新。这样频繁的更新要求对移动对象的位置进行建模，其中比较著名的就是OuriWolfson[2-4]等人提出移动对象时空（MOST）模型，简单说，这种模型中的移动对象位置表示已经不是静态的点，而是一个预测函数。MOST模型首先引入动态属性概念，一个动态属性A由三个子属性A.value,A.updatetime和A.function组成，A.function是时间t的函数，在t＝0时，A.function为0，A.value表示表示A随时间变化的值，在A.updatetime时，A的值是A.value，经过t后，A的值就变成A.value＋A.function（t）。目前的移动对象模型普遍是在这个模型的基础上建立的，但函数一般都采用最简单的常数函数方法和线性函数。本文中，我们采用一种全新的基于模拟预测的位置模型，能大大提高预测精度，从而降低了更新代价。移动对象索引方面：主要集中在两个方面：1）历史信息的存储和检索；2）将来的预测。具体来说分为对移动对象过去位置或者历史轨迹的索引和对现在和预期将来位置的索引。对现在和将来位置索引的主要问题是如何处理索引的频繁更新，在传统的空间索引R/R*树[7]，quard树等基础上提出了种种改进策略，以降低更新率，提高查询性能。其中以TPR树[8]最为著名，TPR树以R*树为基础，将R*树的MBR改为时间的线性函数，这样MBR就能随着移动对象的运动动态变化，客观上降低了更新率，但TPR树的查询性能会随时间推移不断恶化，这是因为TPR树不能避免MBR的不断重叠。最近LinDan等人又提出一种Bx树[9]，这是在B树的基础上，索引节点是对时空的编码，从而获得比TPR树更好的查询性能。然而这种方法并不能降低更新的频率。在历史轨迹索引方面，对象历史轨迹的大小随着时间连续的增长，不可能记录所有更新的位置，因此需要通过由线段组成的折线来近似移动对象过去的位置。提出的索引方法通常基于R树和R*树的三维变化或者多版本来最小化存储需求和查询代价[5,6]。其中最好的工作是TB树[10]，TB树除了支持历史时态范围查询外，还要支持轨迹查一种基于城市交通网络的移动对象全时态索引询，这样TB树的结构不可避免索引空间大量重叠而无法利用，造成死空间的问题。我们根据交通系统的特性，在模拟预测模型的基础上，提出了一种全新的混和索引结构-AUIndexSchema，其上层是索引路网的R树，不涉及更新，在R树的叶节点链接AU结构，每个AU结构是活动在一条路段上的，这种结构很好的适应交通系统特征，在降低更新频率的同时，减小查询代价。由于AU索引能够完整的把移动对象的运动特征记录下来，而不会带来死空间问题，我们将其拓展，设计了基于路段的容器结构，使它可以对历史轨迹进行查询。3.基于模拟的位置表示模型由于移动对象的位置原始数据更新极快，并且数据量巨大。这就会造成存储和索引这些数据都很不方便，因此需要针对这些原始数据建立合适的模型，使移动对象位置能够适应索引的频繁更新和存储等要求。此节我们引入元胞自动机模型，用它来模拟移动对象未来的轨迹，再利用最小二乘法对模拟的轨迹进行回归，这样得到的预测轨迹方程较为准确，因此可以大大降低索引对更新的要求，同时也减少的数据存储量。3.1元胞自动机模拟由于交通系统的随机性，复杂性和动态性，加上很多人为因素的影响，构成一个复杂系统。用传统的数学模型很难描述，然而，计算机仿真可以较好的解决这个问题。近年来，元胞自动机（CA）[11,12]在交通模拟中扮演一个主要的角色。在元胞自动机中，在某一时点元胞的状态只取决于前一时点其自身状态以及与其相邻的元胞的状态。CA模型将每条路段看作连接了很多元胞的纽带，元胞的状态要么为空，要么被一个汽车主体所占据。每一个元胞的长度是两个汽车主体之间允许的最小距离。在每一个离散的时间步进中，系统将按照如下规则对所有的汽车主体进行更新（对于每个移动对象i，速度是v(i)，当前的位置是x(i)，gap(i)是位于其前方的空的元胞数,random()是一个随机减速概率）（1）如果V(i)maxV，那么V(i)++；（2）如果V(i)gapV，那么V(i)=gap(i);（3）如果V(i)并且random()dP(i)，那么V(i)――；X(i)=X(i)+V(i);图1CA交通模拟模型举例来说，图1是描述两个相邻时刻某条路段上的车辆运动情况。在t时刻，我们注意到第一辆车距离第二辆车的距离大于gap，并且速度未达到最大，因而在t＋1时刻加速到v＝5，同理，t时刻的第二辆车，因为距离前一辆车的gap为2，而其自身速度为5，需要在t＋1时刻减速到2。当一辆车进入路段时，我们就根据这条路当时的交通情况，对其未来的轨迹用元胞自动机进行一次预测，如图2所示。图2CA模拟预测模型3.2轨迹回归由于元胞自动机只能给出离散轨迹，这样既不易处理，又消耗空间，我们对这样的轨迹采用线性回归的方法将它连续化。在大多数情况下，线性回归可以得到较为满意的精确度，当要求精度更高时，这种方法可以方便的扩展到分段的线性回归。我们采用最小二乘法（OLSE）来计算回归，线性回归模型如下：一种基于城市交