移动对象流量查询方法研究

移动对象流量查询方法研究 第 26 卷第 4 期 齐 齐 哈 尔 大 学 学 报 Vol.2,N6o.4 2010年7 月 Journal of Qiqiha rUniversity July,2010 移动对象流量查询方法研究 112李伯权，回敬齐，戴建华 (1. 齐齐哈尔医学院 附属第三医院，黑龙江 齐齐哈尔 161000;2. 齐齐哈尔市疾病防控中心，黑龙江 齐齐哈尔 161000) 摘要:针对移动对象数据库中存储有移动对象运动状态信息的特点，提出了在移动对象数据库中实现基于道路网 络的移动对象流量查询。首先，给出了利用直方图处理基于时间段的移动对象流量数据的方法;其次，基于 FNR-Tree 思想，提出了一个新的索引结构 IFNR-Tree(Improved FNR-Tree)，该索引结构增加了 hash 表和网格结构 能够对移动对象数目进行统计，从而可以实现移动对象的流量查询。 -Tree 关键词:移动对象;直方图;IFNR 中图分类号:TP311.131 文献标识码:A 文章编号:1007-984X(2010)04-0024-03 移动对象流量信息处理是一个跨越智能运输系统和移动数据库两个领域的重要研究方向，其在交通管 [1]理方面有着重要的应用，因此受到广泛的重视，国内外学者取得了许多成果，等提出利用红外技术Ernst I, [2]在 600 m 的高空拍摄, 获得交通流信息，朱江等利用视频检测技术通过检测线上的 RGB 灰度变化识别车 [3]辆，完成对车辆流量的检测，王力等提出通过 GPS/蜂窝无线定位技术对交通信息进行采集，实现了对路网 动态”实时检测，这些研究均集中于对流量的检测处理方面，对获取后的数据查 询范围内多个路段进行“ 涉及较少，由于移动对象数据库中存储有大量移动对象的运动信息，因此，在数据库中能够获得移动对 象 [1,2]的交通流量信息，并且可以实现对流量信息的查询功能，同时减少了检测设备的安装，提高了效率， 精度 [4] 上也有很大提高。本文提出通过对移动对象的数据信息进行处理，利用直方图技术，在改进的 FNR- [5]tree上实现道路网络上基于时间窗口的移动对象流量查询。 1 问描述与处理方法 本文主要讨论基于移动对象数据库的流量查询技术，下面给出本文要用到的几个概念: 定义 1(时间段):给定两个时间戳 t 和 t ，且 t ? t ，则[ t , t ]构成一个时间段，记为 T ，t , t 的值 e ss e s e s e i 称为时间段(T)的跨度，记为 T 。 定义 2 (时 间 段序列 ):设 有时 间 段 T , [t , t] ，将 T 划分 为 m ， 1 个子 时 间段， 其 中 e s [t, t],[t, t],…,[t, t] 分别表示为 ，且 T,T,…,TT ，则称 为时间段, … , TT,T,…,T , T 12 m，1 1s 1 1 2 m e m，1 1 2 m，1 2 序列，简记为 sT。 m，1 定义 3(流量):存储在数据库中的移动对象时间段 内经过某指定点的数量，简记为 。 T F由于直方图T [4]技术可以对数据进行统计分析，因此可以用来解决移动对象流量查询问题，以流量即移 动对象数目作为纵坐标，以时间段 T 作为横坐标，建立直方图。这样对流量的查询就转化为对直方图的查 询，并进一步利用直方图的离散余弦变换(Discrete Cosine Transform，DCT)实现在数据库中进行有关查询。 收稿日期:2010-04-01 基金项目:齐齐哈尔市应用技术项目基金(407275) 作者简介:李伯权(1973-),男，黑龙江齐齐哈尔人，硕士，主要从事数据库理论与应用研究，liboquan@yahoo.cn。 第 4 期 移动对象流量查询方法研究 ?25? [5]FNR-tree是目前常用的针对道路网络上移动对象的索引结构。这种索引结构存储了移动对象的轨迹信 息，能够提供范围查询、窗口查询等针对移动对象个体的查询问题，但同时存在一个问题，由于在结点中 缺乏移动对象数目信息，在执行如道路(或路口)上车流量这类以统计数量为主的查询时查询效率较低。 [6]而 MON-Tree在同一个下层 R-Tree 结点中针对同一移动对象会产生多个叶子结点，不利于移动对象的数 目统计。因此，本文基于 FNR- tree 思想提出一种新的索引结构 IFNR-tree，它除了能完成原有范围查询、 询，还可以很容易地实现聚集查询、密度查询等以统计数量为主的查询。路网模型采用边导向模型 窗口查 [6]，因为这种模型能提供经过路口(离开所在边)的移动对象，而路导向模型则不具备这种功能。 2 IFNR-tree 索引与查询处理 2.1 IFNR-tree 索引结构 IFNR-tree 的索引结构由上下两层 R 树和一个哈希结构构成。其中哈希结构由两层哈希表组成。上层 R 树对应道路网络，下层 R 树对应移动对象，在整个 IFNR-tree 生命周期内，只要路网没有变化，那么，上 层 R 树就是一棵静态树。 上层 R 树对折线对象既道路建立索引，树的叶子结点结构为，其中， mbr 指向折线对象的最小外接矩形，polypt 指向具体的折线对象， treept 指向与该折线对应的下部 R 树，非叶子结 点的结构为 mbb 是包含所有子结点数据项的最小限定盒，childpt 指向子结点。 下层 R 树用来对折线中运动的移动对象建立索引，叶子结点结构为direction，moid ，Te 为移动对象标识，polyid 为折线标识，mov 为移动对象运动速度，direction 表示移动对象运动方向，移动对 象向右运动时取 0，反之取 1，在垂直路线中向下运动取 0，反之取 1。T为移动对象离开此路段时刻。非 e 叶子结点结构为 mbb 包含所有叶子结点的最小邻接矩形，childpt 指向子结点。 对每棵下层 R 树建立如图 1 所示的两层网格结构。Direction 表示移动对象运动方向， T,T,… 表示时 1 2 间段。每个单元格包含一个计数器 counter，当有移动对象离开所在线路时，counter 增加 1。下层 R 树森林 所对应的双层网格构成层网格。为每条边建立一个 hash 表，表结构为，其中， polypt 与上层网格叶子结点中的 polypt 相同，directon0,directon1 分别指向每棵下层 R 树对应的两层网格， 如图 2。为每个路口建立路口 hash 表结构， ， cossingid 为交叉路口标识，polypt为指针，指向边 hash 表， k 为构成交叉路口边数目。i T1 T2 T3 Tm+1 7 8 6 Direction =0 polypt direction 0 direction 1 10 9 5 Direction =1 图 1 与 R 树对应的网格 图 2 边 hash 表结构 2.2 插入及更新操作 基于道路网络的时空索引涉及到两种不同类型的插入操作:道路网络中网络空间数据的插入操作和移 动目标运动状态的插入操作。在 IFNR-tree 中，对应的操作为折线插入、移动目标插入。在构建道路网络 时，在上层 R 树进行折线插入操作，而当移动目标被创建或其运动状态发生改变时在下层 R 树进行移动目 标插入操作，每个新的数据项直接插入 R 树最右边的叶子结点。如果叶子结点存储空间已满了，那么将新 创建一个叶子结点，然后将新的数据项存入新的叶子结点中，新创建的叶子结点插入最右边叶子的父结点 中。若最右边叶子结点的父结点的存储空间也已满了，那么 R 树将向上延伸和繁殖。在下层 R 树的插入算 法中，新的数据项总是插入到最右边的叶子结点中。对于网格，每当有移动对象离开(进入)R 树时，网 格当中的单元格的计数器增 1。 2.3 基于直方图技术的流量查询处理 本文提出的 IFNR-tree 树主要是在 FNR-tree 基础上改进的，并且对于下层 R 树的叶子结点的数据项进 行了修改，然后加入新设计的哈希表和网格结构，因而在范围查询方面时间片查询方面的性能与 FNR-tree ?26? 齐 齐 哈 尔 大 学 学 报 2010年 相同，但 IFNR-tree 较 FNR-tree 优越之处在于它的移动对象数目查询方面。在各个单元格存储了移动对象 之后，当要对某条道路进行某个方向流量查询时，通过 hash 表可以得到各个边对应的网格层，根据网格层 各个时间段单元格内的移动对象数目建立离开此道路的流量直方图，利用文献 4 中所给公式进行离散余弦 变换后存于主存中，当要执行查询某个交叉路口的流量时，利用文献 4 中所给公式进行反向离散余弦变换， 提取指定时间段的数值即可完成查询。要进行路口某个时间段的流量查询时，通过路口 hash 表找到能构成 路口流量边 hash 表，进而得到叠加后的离散余弦函数，再利用公式反向变换后即可得道路路口的流量查询。 3 结束语 本文主要探讨在数据库中实现移动对象流量查询，给出了直方图处理基于时间段的流量数据的方法， 该方法将流量数据利用余弦变换和反向变换后可以较方便地在主存中进行存储、提出与查询;同时，提出 一种新的索引结构 IFNR-Tree，与 FNR-Tree 相比，该索引结构增加了移动对象数目查询功能，扩大了应用 范围，与 DCT 技术结合能较好地执行道路网络上移动对象的流量查询。 参考文献 [1] Ernst I, Sujew S, Th iessenhusen K U , et al .LUMO S2 airborne traffic monitoring system[C]//The IEEE 6th International Conference n Intelligent Transportation Systems,Shanghai,China: 2003.753,759 O [2] 张汝华,郑黎黎,杨晓光,等. 基于视频技术的微观交通流信息采集系统研究[J]. 交通与计算机,2004, 22(6):33-36. [3] 王力,王川久,沈晓蓉,等. 智能交通系统中实时交通信息采集处理的新方法[J]. 系统工程.2005 23(2) :86-89. [4] Christian S. Jensen , Dan Lin , Beng Chin Ooi , Rui Zhang, Effective Density Queries on Continuously Moving Objects[C] //Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), 2006 :71.[5] Frentzos .Indexging objects moving on fixed networks[C]//Proc of the 8th Intl Sy on Spatial and Temporal atabase(SSTD)，2003: EmpD 289-305( [6] V.T.Almeida,R.H.GAuting.Indexing the trajectories of moving objects in networks[C]//:Proc.16th Int’ 1Conf.Scientific and Statistical Database.Los Alamitos.CA:IEEE Computer Society Press,2004:115-118. The research for querying of traffic in moving objects database 112LI Bo-quan，HUI Jing-qi，DAI Jian-hua (1.Third Affiliated Hospital of Qiqihar Medical College，Heilongjiang Qiqihar 161000,China; 2.Qiqihar Centers for Disease Prevention & Control, Heilongjiang Qiqihar 161000,China) Abstract: As the status of the moving objects are stored in the mobile objects database(MOD) ,this paper proposes to execute querying of traffic which stored in MOD.First,the paper gave a method of dealing with traffic flow data based on time step using histogram, Secong,based on the idea of FNR-Tree,the paper presents a new index IFNR-Tree(Improved FNR-Tree),it increased by two hash table and a grid ,so that it could execute querying of traffic in MOD. Key words:moving objects; histogram; IFNR-Tree