CN100542330C - 基于交通网络和gps的移动对象位置更新方法 - Google Patents

Abstract

为了使中心服务器能够跟踪移动对象过去及现在的位置，本发明提供了一种基于交通道路网络和GPS的移动对象位置更新方法：移动对象利用GPS设备不断地测得其最新运行参数，通过与交通路网的匹配，将其中的经纬度位置及方向数据转换为基于路网的数据表示形式，然后根据“惯性原理”，比较当前运行矢量与上次位置更新时提交的运行矢量，并判断位置更新的条件，只有当移动对象不再保持惯性运行规则时才向中心服务器报告当前的运行矢量。此外，本发明还针对交叉路口对位置更新进行了优化，使得移动对象在交叉路口区域内最多仅进行一次位置更新。与已有的位置更新方法相比，该方法能够在保证处理精度的前提下，减少通信频率，提高数据处理的效率。

Description

基于交通网络和GPS的移动对象位置更新方法

技术领域

本发明涉及移动计算领域中移动对象个体向中心服务器报告自身位置、速度、方向等信息，并使中心服务器能够全程跟踪移动对象过去及当前位置的方法。

背景技术

在过去的十多年时间里，移动计算技术得到了飞速的发展。越来越多的应用要求对移动对象(例如汽车、飞机、轮船、移动用户等)的动态位置进行管理，其中需要解决的一个核心问题就是中心服务器如何能够高效、准确、及时地获取移动对象的最新位置信息。位置跟踪机制通常是在移动对象上安装某种定位设备(如全球定位系统GPS)，通过无线通讯接口和一定的位置更新方法，每个移动对象不断地向中心服务器报告自己的位置、速度、方向等信息，中心服务器收到这些信息后可以对移动对象进行统一的监控、管理和查询。

现有的移动对象位置更新方法主要包括三大类：基于固定时间间隔的方法、基于固定空间间隔的方法、以及基于运行矢量的方法。基于固定时间间隔或基于固定空间间隔的方法都是每隔一个固定的时间间隔或一个固定的运行距离，移动对象就向中心服务器发送一次位置更新消息。这两类方法的主要优点是实现简单，但很难确定合理的时间或距离间隔值。如果间隔值设置的太大，将导致位置更新的频率过低，这样移动对象在进行两次位置信息报告之间，有可能已经跨越了复杂的道路网络，仅根据两个数据点，中心服务器无法确定具体的行驶路线，因此影响了处理的精度；如果间隔值设置的太小，将导致位置更新的频率过高，从而增大了通信和计算代价，同时过多的冗余数据将会影响中心服务器处理数据的效率。

基于运行矢量的方法通常是比较移动对象最新的运行矢量和最后一次报告的运行矢量，如果满足某种变化条件则触发一次位置更新。运行矢量主要包括位置、速度、方向等运行参数。通过这些参数，系统能够计算出移动对象在当前时刻的位置。当移动对象大致沿着上次提交的运行矢量行驶时就不需要进行位置更新；相反，如果移动对象的运行状态发生了改变从而导致其实际位置偏离了原先的运行矢量就需要进行位置更新。与基于固定时间间隔或空间间隔的位置更新方法相比，基于运行矢量的方法能够降低位置更新的代价，并具有较好的位置跟踪精度。但是目前的大多数基于位置矢量的方法在表示运行矢量时均采用基于Euclidean空间的方法，即直接以(X，Y)地理坐标上的参数形式表示，这样当移动对象改变方向时将会触发频繁的位置更新。

为了进一步提高基于运行矢量的位置更新方法的效率，近年来人们对基于交通网络的移动对象位置更新方法进行了研究。代表性的成果包括美国Illinois大学Chicago分校Wolfson教授提出的基于道路网络的移动对象位置更新方法以及丹麦Aalborg大学Jensen教授提出的网络受限移动对象位置更新方法。其中，Wolfson的方法在触发位置更新时只对位置偏移条件进行判断，当移动对象转换到另外一条道路时不能及时地触发位置更新，因此影响了位置跟踪的精度；Jensen的方法需要对大量的历史GPS日志数据进行预处理，以便将较短的道路路段连接成较长的人工道路。由于人工道路不同于自然道路，从而给查询的表示与处理带来了不便。此外，上述两种方法共同的严重缺陷在于没有对降低交叉路口的位置更新代价进行特殊的处理。在我国的大中型城市中，交叉路口通常非常拥挤，极少有车辆能够不经过几轮的走走停停而直接通过的。所有上述基于运行矢量的方法均会导致在交叉路口产生多次不必要的位置更新，从而增加了通讯和计算的代价。

通过上述分析可以看出，几乎目前所有的位置更新方法均没有充分考虑移动对象与交通网络之间的交互作用关系，难以克服处理精度和通信代价以及处理效率之间的矛盾，从而给移动对象的管理带来了困难。

发明内容

针对上述现有移动对象位置更新方法所存在的问题和不足，本发明的目的是提出一种能在保证一定处理精度的前提下尽量减少通信次数，并提高处理效率的移动对象位置更新方法。

为了实现上述目的，本发明所采用的技术方案是：

第一步：在每个需要跟踪其位置的移动对象上安装GPS定位设备和无线通讯设备，并配备实际的交通道路网络数据。

其中，交通道路网络数据类似于一张电子地图，可以通过对GIS地图进行数据转换处理而得到，它包含交通网络中的每条道路的信息和每个交叉路口的信息。其中道路的信息包括：道路的标识、道路的地理几何形状、道路的长度；交叉路口的信息包括：路口的标识、路口的地理位置、路口的区域范围、路口所连接的道路、路口中交通流的转接关系。

道路的标识即道路ID，通常用字母、数字、或者字母与数字的组合来表示，如图1所示的道路交通网络中共有5条道路，对应的道路ID分别为r1、r2、r3、r4、r5。每条道路的地理几何形状用一条折线表示，即每条道路都由若干个点来描述，将这些点依次连接形成的折线即刻画了道路的形状。

交叉路口的标识与道路ID的表示方式相同，其地理位置用其经纬度坐标表示，其连接的道路用道路ID的集合表示。例如：在图1中用小方框表示交叉路口，共有8个交叉路口，分别用j1、j2.....j8代表；交叉路口j2连接道路r1，r2，r3，因此其连接的道路为集合{r1，r2，r3}；同理，交叉路口j3连接的道路为集合{r2，r5}。另外，用一个数据结构如矩阵(称为交叉路口的连接矩阵)来表示该交叉路口所连接的各条道路上的交通流之间的转接关系，交通流用道路的ID与正负号的组合来表示，“+”表示从道路起点到终点的交通流，而“-”表示从道路终点到起点的交通流，用不同的数值或符号来表示是否允许移动对象从某一进入交叉路口的交通流(称为“进入流”)切换到某一离开交叉路口的交通流(称为“离开流”)。图2给出了交叉路口j3的连接矩阵的例子。在图2中，道路r2是双向道路，因此它拥有两个交通流，r2+和r2-；道路r5是单行道路且只有一个交通流r5-。这三个交通流在连接矩阵中可以有9种不同的组合，而矩阵元素的值1表示该交叉路口允许移动对象从对应的“进入流”经过该交叉路口切换到“离开流”，0则表示不允许。

第二步：移动对象个体在运行的过程中，不断地将GPS所测得的运行参数(如位置、速度、方向等)与上述交通道路网络数据进行匹配，从而得到在路网中的运行矢量。运行矢量的形式为：(t，(rid，pos)，v，fd)，其中t表示该运行矢量所对应的时间；(rid，pos)表示移动对象在t时刻在路网中的位置(见下面步骤2解释)；v表示移动对象在t时刻的运行速度；fd表示移动对象所属的交通流方向(见步骤2)。然后将匹配的结果和上次位置更新所提交的运行矢量进行比较，当二者之间的变化满足一定的条件时，就需要向中心服务器发送新的运行矢量，进行一次位置更新，具体流程如图5所示，包括下列步骤：

步骤1.移动对象在运行过程中，利用自身的GPS设备不断地测得其最新的运行参数，包括当前时间、当前经纬度位置(以(X，Y)地理坐标形式表示)、当前速度、以及当前方向。

步骤2.将上述GPS测得的位置及方向数据与实际的交通道路网络进行匹配，得到移动对象在交通网络中的相对数据，即网络位置(rid，pos)和道路交通流方向fd，其中，rid为移动对象所在的道路的标识；pos是移动对象在道路rid中的相对位置。设每条道路的长度为1，则道路rid中的任意一个位置可用一个实数pos表示，0≤pos≤1；fd为移动对象在道路rid中的运行方向，用“+”表示由道路rid的起点向终点运行，“-”表示由终点向起点运行，即fd∈{+，-}。

具体的计算过程如下：

●计算对应的rid：由于每条道路都是由一条折线来刻画的，通过计算(X，Y)坐标点位于哪条折线上，即可得出对应的道路ID，即rid值；

●计算对应的pos：对于交通网络中每一条道路的两个端点，可以设定X坐标值小的一端为起点，另外一端为终点；当两个端点的X坐标相等时，设定Y坐标值小的一端为起点，另外一端为终点。定义起点的pos值为0，终点的pos值为1，(X，Y)坐标点到起点沿道路的距离与该道路的长度的比值即为该坐标点对应的pos值，显然地，pos的取值范围是0和1之间，即pos∈[0，1]。

●计算移动对象所属的交通流方向fd：比较GPS所测得的移动对象运行方向和道路rid在pos处的走向，如果运行方向是朝向道路终点的，则fd为“+”；若运行方向是朝向道路起点的，则fd为“-”。

经过上述转换后，可以得到移动对象在当前时刻的运行矢量(t，(rid，pos)，v，fd)。

步骤3.移动对象将上述转换后的运行矢量与其最近一次位置更新时发送给服务器的运行矢量相比，考察两个运行矢量是否满足一定的位置更新条件。如果满足以下任何一种条件，就需要向中心服务器发送当前运行矢量(即t，(rid，pos)，v，fd)；否则不向中心服务器发送当前运行矢量，并转步骤1.进行下一轮处理。移动对象将始终保存最后一次位置更新时的运行矢量数据。

具体来说，本发明考察以下三种运行矢量的变化：

(1)rid发生了变化：即该移动对象当前所在的道路不同于上一次位置更新时所在的道路，即移动对象已经从一条道路运行到另外一条道路；

(2)rid没有变化，但是移动对象的运行方向fd发生了变化，或者运行速度v发生了较大的变化：即该移动对象的运行方向由正方向变为负方向或由负方向变为正方向；或者运行方向没变，但是该移动对象的当前速度与上一次位置更新时的速度相比，其偏差超过了一个指定的阀值ψ(例如，10公里/小时)；

(3)rid和v均没有发生上面描述的变化，但是该移动对象的当前位置与预测位置发生了变化：即移动对象的当前位置(记为(rid，pos_now))与根据上次位置更新信息预测的位置(记为(rid，pos_evl))相比，距离偏差超过了一个指定的阀值ξ(例如500米)。

其中，pos_evl的计算方法如下：设该移动对象上次位置更新时的运行矢量为(t_o，(rid_o，pos_o)，v_o，fd_o)，道路rid_o的长度为len，当前时间为t_now，则

${\mathrm{pos}}_{\mathrm{evl}}={\mathrm{pos}}_o+\mathrm{fd}\×\frac{v_o\×(t_{\mathrm{now}}-t_o)}{\mathrm{len}}$ (公式1)

根据pos_evl和pos_now，可以得到预测位置与实际位置之间的距离偏差为

|pos_evl-pos_now|×len            (公式2)

如果该值大于ξ则触发一次位置更新。

在判断上述三种位置更新条件时，需要对移动对象的当前位置处于交叉路口区域的特殊情况进行处理。因为在实际的交通道路网络中，交叉路口是一个区域范围(可以在交通网络数据中为每个交叉路口指定一个区域半径γ)，在该区域内移动对象的运行矢量可能发生非常频繁的变化，但实际的位置偏移却并不大，所以在交叉路口区域中没有必要将所有的位置更新信息都发送给服务器。具体措施是：a)当移动对象处于交叉路口区域中时，视为其仍然在原来的道路上行驶，从而保证了移动对象在交叉路口区域中不发生换路位置更新(见上述判断条件(1))；b)当移动对象位于交叉口区域中时，如果其运行矢量发生了以上(2)、(3)中描述的任意一种变化，则首先检查该移动对象在当前交叉路口区域范围内是否已经向服务器发送过一次位置更新信息，如果已经发送过，则不再发送当前的运行矢量，否则将向服务器发送最新的运行矢量。上述方法保证了移动对象在交叉口区域内最多只发送一次位置更新信息，如图3所示。

第三步：中心服务器接收到移动对象发送来的位置更新消息之后，将相应的运行矢量附加(append)到对应的移动对象时空轨迹中。每个移动对象的时空轨迹是由该移动对象提交的一组运行矢量组成的，描述其完整的运行过程，因此可以提供对移动对象过去及当前时刻连续动态位置的查询，如图4所示。

本发明是基于“惯性原理”实现的，即系统假设移动对象将沿着当前的道路、以大致稳定的速度继续行进一段时间。一旦该假设条件不成立则向中心服务器报告一次最新的位置数据。根据上述方法，当中心服务器没有得到一个移动对象的最新位置更新信息时，则可以认为其仍然在原有道路上近似保持原有的速度运行，且其当前位置可以通过最近一次的位置更新信息(包括位置、速度、方向和时间)近似地估算出来，而预测偏差在指定的允许范围内。

从位置跟踪精度来看，本发明可以从下面几方面保证所采集的数据的准确性：a)移动对象在任一时刻所在的道路能够通过所采集的数据唯一确定；b)移动对象在任意时刻的位置可以通过所采集的数据进行精确计算，且计算误差必然小于设定的距离阀值；c)移动对象在任意时刻的速度可以通过该时刻之前采集的运行矢量获得，且误差必然小于设定的速度阀值。

此外，由于本发明提出的位置更新方法考虑了移动对象和道路网络之间的关系，所以移动对象不需要周期性地报告位置信息，中心服务器也能够通过预测技术较准确地确定出移动对象在任意时间点的位置，从而在保证数据采集精度的前提下，减少了数据采集频率，降低了通信代价。特别地，本发明对交叉路口处的位置更新进行了特殊处理，使得移动对象在交叉路口区域内最多仅发生一次位置更新，从而降低了位置更新的代价。

最后，本发明采用的这种基于路网的位置表示方法避免了中心服务器进行数据处理时从(X，Y)形式的坐标位置到具体道路之间的映射，降低了查询处理时数据处理的复杂度。

综合上述分析，与现有的基于固定周期的位置更新方法相比，本发明在保证数据处理精度的前提下，减少通信次数，提高查询处理的效率。本发明可以应用到移动对象数据采集设备上，持续跟踪移动对象的位置，为移动对象的管理、查询、以及位置相关类应用提供原始数据。

附图说明

图1是实例1中交通道路网络和一个移动对象的运行轨迹示意图。

图2中，(a)是实例1的交通道路网络中交叉路口j3的交通流转接关系示意图，(b)是对应的连接矩阵。

图3是实例2中移动对象位置更新在交叉路口的特殊处理示意图。

图4是实例1中服务器根据移动对象的位置更新消息生成该移动对象的时空轨迹(右)的示意图。

图5是本发明的移动对象位置更新方法的流程图。

具体实施方式

下面结合附图，通过实例来进一步说明本发明，但不以任何方式限制本发明的范围。实例1：

以图1所示的交通道路网络和一个移动对象m1的运行轨迹为例，服务器所生成的移动对象轨迹用图4中右边框中数据(运行矢量)表示。图1中的折线表示道路，共有5条道路，对应的道路ID分别为r1、r2、r3、r4、r5；小方框表示交叉路口，共有8个交叉口，分别用j1、j2.....j8代表；pos1、pos2......pos5表示移动对象m1在时刻t1、t2、......t5(其中t5为当前时刻)的位置，五角星表示在此刻进行了位置更新。

假设在t1时刻，移动对象m1的运行矢量为(t1，(r4，pos1)，55，-)。在t2时刻，移动对象m1利用GPS设备得到其运行状态，其中位置坐标为(96，57)，速度为54公里/小时，运行方向为正方向，即为+。根据交通道路网络数据，可知坐标位置(96，57)位于道路r2上，然后从交通道路网络数据中获取r2的长度及其起点和终点坐标，依据坐标转换方法(见第二步中的步骤2)即可得到对应的pos值为pos2，则m1在时刻t2的运行矢量为(t2，(r2，pos2)，54，+)。由于m1已经从道路r4运行到了一条新的道路r2上，所以此时要将当前运行矢量(t2，(r2，pos2)，54，+)发送给服务器。

移动对象m1继续运行，如果在t3时刻其运行矢量为(t3，(r2，pos3)，30，+)，表明m1仍沿原先的道路r2运行，但是与上次位置更新时的运行速度相比，当前速度发生了较大的变化，即超出了指定的速度阈值(设为10公里/小时)，所以此时将向中心服务器报告当前的运行矢量(t3，(r2，pos3)，30，+)。

同样地，如果移动对象m1在t4时刻的运行矢量为(t4，(r2，pos4)，38，+)，则表示m1仍沿原先的道路运行，且其运行速度的变化不大，即没有超出指定阈值(即10公里/小时)，但是，根据上次位置更新时的运行矢量数据和公式(1)估计出其当前位置为(r4，pos4’)，然后根据公式(2)计算知该点到当前实际位置(r4，pos4)的距离为1000米，超出了指定的距离阈值(设为500米)，所以此时也需要向中心服务器报告当前的运行矢量(t4，(r2，pos4)，38，+)。

移动对象m1继续沿着道路r2前行，如果在当前时刻(即t5时刻)它的运行矢量为(t5，(r2，pos5)，40，+)，则表示m1虽然穿过了交叉口j2，但仍沿原先的道路r2运行，且其运行速度的变化不大，即没有超出指定阈值(设为10公里/小时)，另外估算出来的当前位置和实际位置的偏差没有超过指定的距离阈值(设为500米)，所以此时不需要向中心服务器报告当前的运行矢量。

实例2：

下面再举一个例子，说明本发明对交叉路口的位置更新的特殊处理。如图3所示，道路r1和r2的交叉路口区域是虚线圈定的半径为γ的圆形区域。移动对象mo1穿越交叉路口从道路r2运行到道路r1，在其刚进入交叉路口区域时进行了一次位置更新(见图3中“上一次位置更新”)，由于在交叉路口区域内仅允许最多发送一个位置更新消息，此后，在它处于交叉路口中时，即使满足其他位置更新的条件，也不再发送位置更新信息(见图3中白底黑边的五角星)，直至其驶出了交叉路口区域才发送一次新的位置更新信息(见图3中“新的位置更新”)。

在图3中，移动对象mo2穿过交叉路口时以比较平稳的速度顺利通过，由于它仍然在原道路上行驶，且速度和距离均没有发生偏差，因此不需要触发任何位置更新。事实上，如果移动对象沿着一条道路大致平稳地行进，可以跨越多个交叉路口而不触发任何位置更新。因此总体上讲，本发明具有较好的通讯及计算性能。

Claims (6)

1.一种移动对象位置更新方法，首先，在每个移动对象上安装GPS定位设备和无线通讯设备，并配备实际的交通道路网络数据，所述的交通道路网络数据包含交通网络中每条道路的标识、地理几何形状和长度，以及每个交叉路口的标识、地理位置、路口的区域范围、路口所连接的道路、路口中交通流的转接关系；移动对象个体在运行过程中，依据下列步骤1)～3)的先后次序循环执行，并向中心服务器报告自身位置更新信息：

1)利用GPS设备不断地测得当前运行参数，包括当前时间t、当前经纬度位置(X，Y)、当前速度v及当前方向；

2)将GPS测得的位置及方向数据与实际的交通道路网络数据进行匹配，得到移动对象在交通网络中的相对数据，即网络位置(rid，pos)和道路交通流方向fd，从而得到移动对象当前的运行矢量(t，(rid，pos)，v，fd)，其中：rid为移动对象所在道路的标识；pos是移动对象在道路rid中的相对位置，fd为移动对象在道路rid中所属交通流方向；

3)将经过步骤2)转换的当前运行矢量与其上次位置更新时发送给服务器的运行矢量相比，首先判断是否发生了下列三种情况之一：

a.rid改变；

b.rid没变，但fd改变或者v与上次位置更新时的速度相比，其偏差超过了一个指定的阀值；

c.rid、fd和v没变，但当前位置(rid，pos_now)与根据上次位置更新时的运行矢量预测的位置(rid，pos_evl)相比，距离偏差超过了一个指定的阀值；如果上述三种情况均未发生，则不向中心服务器发送当前运行矢量；如果发生了上述情况a，则直接向中心服务器发送当前运行矢量；如果发生了上述情况b或c，则再判断是否当前位置处于交叉路口的区域范围内且上次位置更新也在该区域内，是则不向中心服务器发送当前运行矢量，否则发送；

当移动对象个体在运行过程中，依据上述步骤1)～3)的先后次序循环执行并向中心服务器报告自身位置更新信息后，中心服务器接收到移动对象发送来的运行矢量，中心服务器将该运行矢量附加到对应的移动对象时空轨迹中。

2.根据权利要求1所述的移动对象位置更新方法，其特征在于：在所述的交通道路网络数据中设定每条道路的两个端点中一个为起点，另一个为终点，定义起点的pos值为0，终点的pos值为1，则在所述步骤2)中首先通过计算经纬度位置(X，Y)位于哪条道路上，得到rid值，然后计算位置(X，Y)到起点的距离与该道路的长度的比值得到该位置对应的pos值，pos∈[0，1]。

3.根据权利要求2所述的移动对象位置更新方法，其特征在于：对于每条道路，当两个端点的X坐标不同时，设定X坐标值小的端点为起点，另外一端为终点；当两个端点的X坐标相等时，设定Y坐标值小的一端为起点，另外一端为终点。

4.根据权利要求2所述的移动对象位置更新方法，其特征在于：移动对象在道路rid中所属交通流方向fd∈{+，-}，其中：“+”表示由道路rid的起点向终点运行，“-”表示由终点向起点运行。

5.根据权利要求4所述的移动对象位置更新方法，其特征在于：在所述c情况下，设上次位置更新时的运行矢量为(t_o，(rid_o，pos_o)，v_o，fd_o)，道路rid_o的长度为len，当前时间为t_now，则：

${\mathrm{pos}}_{\mathrm{evl}}={\mathrm{pos}}_o+\mathrm{fd}\×\frac{v_o\×(t_{\mathrm{now}}-t_o)}{\mathrm{len}}$

根据pos_evl和pos_now，可以得到预测位置与实际位置之间的距离偏差为

|pos_evl-pos_now|×len。

6.根据权利要求1所述的移动对象位置更新方法，其特征在于：在交通道路网络数据中为每个交叉路口指定一个区域半径γ，该路口的区域范围指与交叉路口中心的距离≤γ的区域。

Images