基于GPS车辆跟踪系统的移动对象数据库应用研究

摘 要 本文结合GPS车辆实时跟踪应用系统，利用移动对象数据库技术，对移动车辆的运动空间及时间进行分割，建立了移动目标数据库的数据模型、数据结构以及索引结构，实现实时更新车辆位置信息，有效地回放移动车辆的历史行驶轨迹，预测车辆将来的运动路线。

关键词 移动对象数据库；数据模型；数据结构；索引结构；片断树

近年来移动对象数据库成为一个研究热点，许多的应用中提出了对连续移动对象的存储、查询和处理需求，如：交通管理，运输和供应链管理等。移动对象数据库主要针对移动目标（比如运动车辆），实现实时更新车辆位置信息，有效地回放移动车辆的历史行驶轨迹路线，预测车辆将来的运动,提供车辆行驶目的地的信息。为了建立一个实时跟踪大量移动车辆以及查询移动车辆的历史运动路线的应用，利用它们通常运动在城市公路网上这一特点，本文研究了移动对象数据库在车辆交通管理中的应用，提出了一种对车辆当前和将来位置的索引方法和基于此索引方法的查询。该方法以时间片断（采样时间间隔）与空间块片断（公路网段）的移动对象数据模型和索引方法为基础，为连续的移动对象建立索引结构，对交通路段网络中的移动车辆,设计以及实现车辆位置信息的数据库系统。

1 数据模型

GPS车辆位置信息实时跟踪系统主要包括：已经注册过的车辆，数据处理中心，终端用户或用户服务器以及通讯路径。电子地图是将地图以数字形式存储于计算机中，利用电子地图将 GPS 得来的坐标通过地图匹配找到对象所在的路径。系统的工作原理为：车辆是行驶在公交网中的现实存在的车辆。车辆接受来自GPS卫星的GPS信号，从而确定它的物理位置，物理位置被转换为UTM系统数据库中的坐标，通过无线网络周期性的更新位置信息。数据中心存储车辆的静态属性和车辆的实时位置信息，同时保存着每辆车的历史数据，数据中心还提供在线客户的应用以及用户处理查询得到的数据。

该方法提出一种全新的数据模型，车辆用点来表示,忽略其形状及大小，公交网由一系列的相互交叉的公路段表示,每个公路段都有唯一的编号。车辆的行驶轨迹通过一系列的点表示,表示格式为( t， R_id，d ，v )：

t 表示车辆在给定位置的时间

R_id 表示车辆所在公路段的编号

d表示车辆当前位置到起始位置的距离

v 表示车辆的当前行驶速度

空间被划分为互不重叠的区域单元,并采用适当的空间索引进行索引化,移动对象在每个区域运动中运动的时间间隔被采集并索引化。 在应用了该方法的移动车辆数据库中，空间被分为公路段。公路段采用片断树结构进行索引。移动车辆在公路段产生的时间间隔采用平衡间隔树来进行索引。采用这种索引方案的移动车辆数据库系统会更灵活，便于系统升级，因为公路段，时间间隔以及这些索引结构能够很简单的分配给不同的处理器，内存以及服务器进行处理。

汽车的运动是连续的，将汽车的位置与速度信息化为一些具体的采样点。数据的精度与系统的承载量是相互平衡的，取样的间隔越短，运动汽车的数据就越是精确，数据库中的数据也越多。

对公路网，车辆，车辆的状况以及时间建立模块，公路网由公路段组成， 公路段具备以下2个条件：任何2个公路段不相交以及公路段间的交点既是起点也是终点。

车辆的属性，分3种：静态属性，间断变化（离散）属性，连续变化属性：

（1）静态属性的数据结构：

vehicle_attributes_static{

Vid : integer;

make : string;

model : string;

year :integer;

}

（2）间断变化属性

vehicle_attributes_discrete{

ownership : {owner_i:string,t_i:time},

color : {color_i:string,t_i:time},

use : {use_i:string,t_i:time},

destination :{dest_i:location,t_i:time},

}

location{

zone : integer;

easting : real;

northing : real;

Address :string;

}

（3）连续变化属性

vehicle_attributes_dynamic {

Road_id : integer;

time : time;

velocity : real;

distance :real;

easting : real;

northing :real;

}

汽车的运动由它在各采样点上的位置，速度来定义。这些值被实时记录并更新。两个采样点之间的运动状态是这样描述的：

汽车的加速度为a，两个时间点t₁与t₂ 之间的时刻为 t，与时间点对应的为位置 p₁和 p₂,速度为 v，离路段起点的距离为 d，满足如下的计算：

把加速度考虑进来，减少了存储数据的大小。可以认为在这些采样点上，加速度在随后的采样点上是一样的，不考虑速度的变化。

汽车将其位置与运动信息以某个中心频率发送给中心站，中心站将这些数据信息收集起来，但不是每一次的更新都会记录在数据库中，只有在这些关键数据影响到了在邻近地区的运动估测时，才会被记录下来并存入数据库中。根据汽车正在行驶的路况，速度，速度的改变量，下面的两种情况下，数据更新是可以忽略的：

（1） 汽车在最后一次更新的相同路段

（2） 与最后一次更新相比，速度的改变在某个很小的变化范围内，或者加速度在某个很小的变化范围内。

在某种情况下，一个采样点必须插入到汽车两次更新之间。如果两次连续的更新表明汽车已经走出了此路段进入另外一个路段，就需要在这两个路段的交叉处计算并添加一个合适的采样点。所使用的算法与估测同一路段上两个已知样点间的运动是相似的。

2 数据结构

为了使跟踪系统高效运行，必须对路段数据模型进行不同的操作处理。 公路段的定义是这样的：

road_segment {

Road_Id :integer;

Start_easting :real;

Start_northing : real;

End_easting : real;

End_northing : real;

Length : real;

Speed_limit: real;

Time_of_birth : time;

Time_of_death : time;

Next *road_segment

}

这条记录中的每个参数要求大小一致，除了最后一个参数。最后一个参数定义了依据地图当前路段的下一个路段。大多说情况下，会有3到4个路段，直前方，左边，右边，有时候会是U形转弯。因此，给Next参数设置4个单元比较合理，每条记录的大小就是相同的了，就可以利用一个数组来存储这一条数据。在特殊情况下，多于或者少于4个单元，假设单元数为x，处理规则如下：

（1）当x小于4时，在第（x+1）到第4个单元中添0；（2）当x大于4时，前两个单元与一般情况下一样，设置第3单元为0，第4单元指向第3单元到第x单元的存储地址，最后一位设为空。

同一条路上的两个路段方向相反时，可以共享除了Next参数的所有信息。如果我们把每一个有向路段的信息都存储起来就会有数据冗余。

公路网信息可以为给定点或者街道地址定位路段。有时候还需要寻找路径，回复范围咨询，显示汽车的运动情况。选择一个片断树作为路段的索引结构。多维树结构可以跟踪历史记录以及路段当前的状况。汽车的静态以及更新的离散数据可以用一张常规表存储在数据库管理系统中。

3 索引化结构

物体的运动空间被分为基本的空间块，各个空间块互相独立。空间分割是很灵活的，主要由数据库系统所支持的各种查询类型的频率决定的。对每个对象而言，时间被分为时间间隔，在每个时间间隔内，对象属于一个空间块。根据空间块来划分形成的时间间隔组成不同的子集。根据相应的时间块对每个时间间隔的集合进行索引，对空间块的索引与对时间间隔的索引是各自单独进行的，二者索引结构互不依赖，彼此之间可以相同或相似或者完全不同。空间分割算法没有什么限制，只要空间中的每一个点被分配到唯一的一个分隔区中就行。当汽车在一条路段上运动时，时间被分成很多个间隔，空间被分割为很多个单向的路段。索引结构包括处理路段以及与路段相关的时间的结构。

对时间间隔（时间片断）和路段（空间块）的索引结构是以最开始的片断树为基础的。平衡片断树用来索引汽车在同一路段上移动的时间间隔，还有一个时间间隔树与每个路段相关。一个修改的片断树是用来索引路段的。片段树最开始是用在2维空间中一组线段的范围查询，描述如下：

给出二维空间中n条不交的直线{[(x11,y11),(x12,y12)], [(x21,y21)].....[(xi1,yi1),(xi2,yi2)]....[(xn1,yn1),(xn2,yn2)]}，片段树很适于索引静态的输入数据组，片断树不支持频繁的插入和删除操作。

在移动车辆的位置信息跟踪系统中，索引化结构分为2个方面：对公交网进行索引和对移动车辆的跟踪进行索引。

不同的汽车之间以及一辆汽车与一个静态位置之间的距离与相对位置是由汽车的地理位置和公路段的设计决定的。有些查询窗口，比如距离查询涉及地图中的给定区域，可能需要在查询回复之前就查找给定区域内的所有公路段，因为每辆汽车的移动轨迹已经为时间间隔范围查询设置好了，那么建立一个遍历所有汽车轨迹的主索引结构用于空间/位置的查询就很有意义了。为此，每辆汽车在公路段上行驶的时间间隔被设计为基本的数据单元，对应的索引结构叫做时间间隔树，它的建立与每个公路段有关。对给定空间范围与时间间隔的查询首先要进入公路网浏览查询，提取给定空间范围内的所有公路段，然后进入与这些包含公路段相关的时间片断树，得到给定时间间隔内行驶在这些公路上的所有汽车。

（1） 对公路段进行索引

系统中当有两个公路段有一个交叉点时，二者要分成两个片断存储在数据库系统中。分点就是交叉的那个点。当在3维空间中没有交叉点但在2维空间里有一个交叉点时，就可以用到分点，比如一条高速公路与本地的一条公路交叉时，在3维空间里，他们之间是没有交叉点的。

对于2个或者多个具有相同终点坐标的情况，就不需要按照前面描述的那样更改索引结构。对某一点查询时，如果查询点恰好处在交叉点时，所有以该点为交叉点的公路段都应被查询出来。对一个矩形区域范围进行查询时，只要有一个点在这个范围内的所有片断都被包括进来。对建立树结构的预处理基本上与标准片断树是相同的。建树的时间与空间复杂度需事先分析，且保持不变。

（2） 对车辆的运动进行索引

索引结构中，汽车移动的基本单元是由汽车行驶在同一路段的持续时间。片段树结构用来索引汽车行驶在同一路段的时间间隔。时间间隔对应的空间片段树叫做时间间隔树。

对汽车定位信息跟踪系统进行在线更新时间间隔树只需要一种插入操作，当进入一个路段时，时间间隔的起点要发送并记录在树中；当离开一个路段时，时间间隔要明确的加入树结构中。

插入的时间点或者时间间隔总是在x轴的右边，相对树中已经存在的数据，它们是最新的。在一个平衡时间间隔树中，数据类涉及到结点，树，以及被称为结点定位器的辅助数据结构，共同反映树中最实时的结点。

①　结点，树叶或者无叶结点，在时间间隔树中是通过从a点到b点的时间间隔来定义的，假设具有相同时间间隔[a，b]的汽车车号Vid的集合为S，表示为（[a，b],{Vid，....}）

②　时间间隔树与平衡二进制树是互相关联的，树中的每一个节点都由3个指针与它们的父结点，左结点，右结点相连。

③　结点定位器包含一个指向时间间隔树中一个结点的指针r，时间指针t，以及树中指针结点的层次为l，结点的层次是从叶结点依次向上的，叶结点的层次为0。

4 查询处理

移动对象数据库的查询类型一般包括：

(1) 实时查询所有或部分移动车辆运动信息；

(2) 查询部分移动车辆在过去,现在的运动信息或者预测将来的运动信息；

(3) 按时间段查询指定公路上的移动车辆,并将他们的运行状况显示出来；

(4) 按时间段和给定的地区范围,回放车辆的历史行驶轨迹路线；

(5) 返回在规定时间内到达规定地点的车辆信息；

(6) 预计某时间段内移动车辆的运动；

为了使查询的结果中包含将来的时间，那么预测车辆的可能移动轨迹是不可少的。在这种预测中最重要的技术就是车辆的行驶路线。

5 结论

本文主要针对移动车辆实时跟踪GPS导航系统的数据存储与处理，以行驶在公路网上的移动车辆为研究对象，建立了移动对象数据库的数据模型和索引结构，该模型可以大大提高数据的精度和查询处理的效率，不仅可以对历史数据进行挖掘，还可以更精确的预测车辆未来的运行状态。

参考文献

[1] 王惠南. GPS导航原理与应用 . 科学出版社,2003.8

[2] 于秀兰,陈滢,丁晓诚.一种基于道路网络的移动目标数据库模型. 软件学报,2003, 14 (9):1600-1607.

[3] Dongseop Kwon, Sangjun Lee, Wonik Choi, Sukho Lee .An adaptive hashing technique for indexing moving objects .Data & Knowledge Engineering 56 (2006) 287–303

[4] Wonik Choi, Bongki Moon , Sukho Lee. Adaptive cell-based index for moving objects. Data & Knowledge Engineering 48 (2004) 75–101

[5] 郭景峰，孙旭光，郝浩.一种基于车辆交通管理的移动对象索引方法.计算机工程，2005,31(7):193-196.