城市路网上基于移动对象聚簇的位置汇报和索引方法

摘要

本发明属于移动对象数据管理技术领域，公开了一种城市路网上基于相似运动聚簇的移动对象位置汇报和索引方法。路网上移动对象（如车辆）触发位置汇报后，通过免费的802.11无线通信(如Wifi)收集周围移动对象的位置和速度，然后经付费的GPRS或GSM，将汇总信息报告给数据库服务器。数据库服务器采用相似运动TPR树（Similar-movement Time Parametered R-tree,STPR）索引聚簇对象的运动，该树有两个特点：（1）每个叶子节点索引位置临近、方向相同、速度相近的移动对象；（2）索引节点的维护，即增、删、改，以批处理方式完成。这种位置汇报和索引方法不仅可以大幅度减少监控位置的付费通信代价，而且可以显著降低索引维护的磁盘I/O，满足城市中对海量移动对象的实时跟踪需求。

说明书

技术领域

本发明属于移动对象数据管理技术领域，涉及应用于城市路网上的移动对象的实时监控 和跟踪。

背景技术

城市路网上的移动对象(moving object)管理架构包括移动端、数据库服务器和客户端三 个部分。移动对象不断地向数据库服务器汇报其最新的位置和速度。数据库服务器一方面对 索引进行维护，跟踪各个移动对象的最新位置和速度；另一方面，在索引上查找以响应客户 端的查询请求。对于大中型城市，动辄几十万甚至上百万的移动对象要实时追踪，通常面临 两个性能瓶颈：一个是移动对象须频繁向服务器汇报其最新的位置和速度，带来高昂的付费 通信代价；一个是在服务器端的索引维护，即运动模式的频繁增、删、改，引起巨量的磁盘 I/O负载。

位置汇报目前主要分基于时间间隔、基于偏差阈值和基于预测区域几类方法。基于时间 间隔的方法简单稳定，但即使运动状态没有任何变化，也向服务器汇报，造成通信资源浪费。 基于偏差阈值的方法是主流的移动对象位置汇报方法，首次在期刊《distributed and  parallel databases》上的《updating and querying databases that track mobile units》 一文中提出。它包括三种更新策略，即speed dead reckoning(sdr)策略、adaptive dead  reckoning(adr)策略和disconnection detection dead reckoning(dtdr)策略。sdr策略中， 所有位置汇报根据一个固定阈值来触发；adr策略的阈值由一个代价优化函数决定，不同的位 置汇报使用不同的阈值；dtdr策略根据一个递减函数来计算阈值，不同的位置汇报采用不同 的阈值。在第一届移动和普适计算会议（international conference on mobile and  ubiquitous systems:networking and services）上发表的《efficient tracking of moving  objects with precision guarantees》中提出基于路段（segment-based）的位置汇报策略， 移动对象在已知的道路上以固定的速率行驶，超过规定阈值则触发位置汇报。基于预测区域 的方法以第36届VLDB（very large databases）会议上的《An Adaptive Updating Protocol  for Reducing Moving Object Database Workload》方法为代表。该方法根据汇报的位置和 速度，计算移动对象未来的若干个矩形区域。如果移动对象的当前位置超过矩形边界或者根 据当前的位置和速度推算其超出未来某个矩形区域，则进行位置汇报。专利《基于交通网络 和GPS的移动对象位置更新方法》（申请号:CN200710121932公开号:CN101128051A）提出 了一种基于交通道路网络和GPS的移动对象位置更新方法：移动对象利用GPS设备不断地测得 其最新运行参数，通过与交通路网的匹配，将其中的经纬度位置及方向数据转换为基于路网 的数据表示形式，然后根据“惯性原理”，比较当前运行矢量与上次位置更新时提交的运行矢 量，并判断位置更新的条件。但这些方法没有结合当前最新的无线通信技术，对道路上移动 对象位置信息预先进行聚集，以减少移动端和服务器端的付费通信代价。

在服务器端，对移动对象当前和将来位置进行索引的典型代表是TPR（Time Parametered  R-tree）树。它在2000年SIGMOD会议《Indexing the Positions of Continuously Moving  Objects》一文中被提出。在R树索引的基础上，TPR树允许最小包容矩形（MBR）包含速度和 方向等参数信息，使MBR能随时间参数进行变化，而不需要随着移动对象位置的变化频繁地修 改索引记录。TPR树提出后，人们提出了许多TPR树的变种如R^ＥＸＰ树、TPR*树、HTPR-tree等。 2012年《计算机学报》的《一种适合于频繁位置更新的网络受限移动对象轨迹索引》一文中 提出DSTR树。DSTR树将索引空间划分成等距格栅，通过格栅单元对每一条时空轨迹进行概略 化，并以概略化轨迹单元为基本索引记录单位建立Ｒ树索引。当发生位置汇报时，如果新产 生的轨迹单元没有跨越移动对象上次位置汇报时所对应的格栅单元，则不需要对索引进行任 何修改；仅当新产生的轨迹单元跨越了活动格栅单元时才需要。但这些索引没有考虑路网上 移动对象的聚簇特性来设计索引结构。专利《一种道路网络空间中车辆对象移动轨迹聚类的 方法》（申请号CN201310121194，公开号CN103246706A）提出了一种道路上移动对象的轨迹 聚类的方法，但没有涉及同向移动的聚簇移动对象的位置汇报和索引。

以上两个方面的工作或者集中于位置汇报，或者集中于索引代价，而没有将位置汇报和 索引维护两个方面结合起来设计策略减少付费通信代价和索引维护的磁盘I/O。而本发明能够 很好地解决上面的问题。

发明内容

本发明目的在于提出了一种移动对象位置汇报和索引方法，该方法很好地实现了城市路 网上大规模移动对象的追踪。

本发明解决其技术问题所采取的技术方案是：本发明提供了一种城市路网上基于相似运 动聚簇的移动对象位置汇报策略，所述方法中的路网上的移动对象在触发位置汇报时，先通 过免费的无线通信802.11（如Wifi），收集临近移动对象的位置、速度信息；然后，将汇聚 信息通过GPRS或GSM向中心服务器汇报，其包括如下步骤：

步骤1：更新触发，移动对象在路网上运动时，根据当前运动矢量（包括位置和速度） 与最近汇报的运动矢量间的偏差决定是否向中心服务器汇报；假设一个移动对象，记为TO， 触发位置汇报；

步骤2：广播询问，TO首先通过Wifi通信，向路网上临近的移动对象广播自己的运动矢 量；

步骤3：邻居响应，设O_i是接收到广播的同方向移动对象，O_i根据TO偏差策略或自身 偏差策略来决定是否响应TO的询问；TO偏差策略即，如果O_i的运动速度和TO的运动速度 的偏差小于阈值，O_i向TO发送自己的当前运动矢量，否则，不向TO作任何反馈；自身偏差 策略即，如果O_i的当前运动速度和最近汇报的运动速度的偏差大于阈值，则向TO发送自身 的运动矢量，否则，不向TO作任何反馈；

步骤4：汇报发送，TO将自身的运动矢量和收集的其它运动矢量划分成增、删、改三个 序列L^ins,L^del,L^upd后，组合成一条消息，通过付费的GPRS或GSM发送到服务器。

2、数据库服务器采用基于相似运动聚簇的TPR树（Similar-movement time-parametered  R-tree，STPR）来索引移动对象的运动，该STPR树索引的每个叶节点索引位置临近、方向相 同、速度相似的移动对象；并且，节点上的增、删、改操作以批处理方式执行，其包括如下 步骤：

步骤1：服务器端聚簇切分，服务器收到一个汇报后，对同类型的运动矢量C(如L^ins，L^del或L^upd)，按照方向、速度和位置迭代进行聚簇划分：

（a）如果C中的移动对象数目小于规定的节点大小m，则停止划分，否则转向（b）；

（b）将C按方向划分成若干个类簇｛C₁,…,C_i,…,C_M｝，每个类簇C_i包含相同方向范围的运 动矢量，对任何一个类簇C_i，如果C_i中移动对象数目小于m，则停止划分，否则转向（c）；

（c）对类簇C_i按照速率划分成若干个类簇{C_i1,…,C_ij,…,C_iN}，每个类簇C_ij包含方向相同、 速率相近的运动矢量，如果类簇C_ij中包含的移动对象数目小于m，则停止划分，否则转向(d)；

（d）对类簇C_ij进一步按照位置划分成若干类簇，每个类簇C_ijk包含方向相同、速率相近、 位置临近的若干个移动对象，它们组成一个聚簇；

步骤2：服务器端索引维护，STPR上的每个叶子节点是一个三元组(CP,L^obj,t^ref)，其中CP 是聚簇运动模式，L^obj是包含的移动对象id列表，t^ref是该节点的参照时间点；CP=([d-,d+]， [s-,s+]，mbr)，其中d-是最小方向角，d+是最大方向角，s-是最小速率，s+是最大速率，mbr 是包含的移动对象位置的最小矩形框，用左下角和右上角坐标来表征；每一个聚簇C_ijk的所 有运动矢量的增、删、改操作，在STPR上通过批理的磁盘读写完成，即从磁盘上读取叶子 节点后，将所有包含的移动对象的运动矢量修改，一次写回磁盘。

有益效果：

对比现有技术，本发明具有以下创新和优点：

（1）城市路网上的移动对象触发位置汇报后，首先利用免费的Wifi无线通信技术收集 临近移动对象的信息，组合成一条消息后用GPRS或GSM向中心服务器汇报，这可以显著 降低移动端和服务器端的高昂付费通信代价。

（2）服务器上STPR树的每个节点索引位置临近、方向相同、速度相近的聚簇移动对象， 可最大限度地减少不同节点区域的重叠，减少查询下探的节点数目；另一方面，增、删、改 操作以聚簇为单位批处理，极大地减少索引维护的磁盘I/O。

附图说明

图1为本发明的城市路网移动对象管理架构流程图。

图2为本发明的广播询问和邻居响应示意图。

图3为本发明的移动对象的运动矢量示意图。

图4为本发明的STPR树结构示意图。

具体实施方式

以下结合说明书附图对本发明创造作进一步的详细说明。

如图1所示，城市路网移动对象管理系统包括移动端、数据库服务器和客户端三个部分。 在城市路网上，移动对象不断地向数据库服务器汇报最新的位置和速度；服务器一方面对索 引进行维护，以记录各个移动对象最新的位置和速度，另一方面，在索引上查找以响应客户 端发来的查询。

如图2所示，一个移动对象TO触发了一次位置汇报请求后，它首先通过Wifi通信广播 自己的运动矢量(包括位置和速度)。每个接收到广播的对象根据TO偏差策略或自身偏差策略 来决定是否响应。自身偏差策略，即如果移动对象的当前速度和上次汇报的速度差超过规定 的阈值，则回应。TO偏差策略，即如果移动对象的当前速度和TO的速度偏差小于规定的阈 值，则回应。给定两个速度矢量v₁=(d₁,s₁)，v₂=(d₂,s₂)，其中d₁,d₂,s₁,s₂分别是方向（用弧度来 表示）和速率；速度偏差采用公式VD(v₁,v₂)=s₁-s₂*cosine(d₁,d₂)来计算。触发对象TO在等待2 秒后，汇总所有响应的移动对象的位置和速度信息，然后发给中心服务器。假定O₁触发位置 汇报后，O₂O₃O₄O₅O₆做出响应。

如图3所示，当6个移动对象C={O₁O₂O₃O₄O₅O₆}的位置和速度被汇报到服务器。假设 每STPR树索引节点大小的上限是3，聚簇按照如下过程划分：

（a）由于|C|>3，6个移动对象按照方向划分成两个聚簇C₁={O₁O₂},C₂={O₃O₄O₅O₆}。由 于|C₁|<3,|C₂|>3，C₁不再划分；C₂继续划分，转向（b）；

（b）C₂按照包含的移动对象的速率大小被划分成两个类簇C₂₁={O₃O₄}，C₂₂={O₅O₆}。

如图4所示，C₁C₂₁C₂₂三个聚簇中的移动对象被批处理地插入STPR树，最后形成一个 含三个叶子，一个根节点的树。