（计算机科学与技术专业论文）rfid数据模型研究与及其系统实现.pdf

r e a s e a r c ha n ds y s t e mi m p l e m e n t a t i o no fr f i d d a t am o d e l s at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y n i ul i j u a n ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y ) t h e s i ss u p e r v i s o r ：p r o f e s s o r c h e nr o n g j u n e 2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：壁卫墅麴堡撞型婴塞区墓丕缠塞丑：。除论文中 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开 发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：兰澉 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形 式出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密( 请在以上方框内打“，) 敝作者躲婀嫡导师签名：叩移， 日期： 弦f 年- 月2 日 中文摘要 摘要 射频识别( r f i d ) 作为一种高性价比的传感识别的使能技术，日渐在零售、 制药、医疗保健和物流管理等领域得到各种大规模应用。然而，r f i d 数据具有时 序性，动态性，数据量大，包含隐含语义等特点。这样的内在特性给r f i d 数据管 理带来了极大的挑战，而错读、误读和冗余数据等又使得问题变得更加严重。 近年来，研究者们提出了多种r f i d 数据处理和整合技术，但是在时序数据处 理、建模以及查询上，仍旧有很多研究问题亟待解决。针对此问题，本论文提出 时空数据模型，设计并实现了基于规则的框架以便支持r f i d 标签物件的高效跟踪 与监控。本文首先对r f i d 数据管理技术进行了全面详细的综述。在此基础上，本 文提出了扩展的d r e r 模型以便在集中式环境下处理大规模r f i d 数据的清洗、 整合、转换与时空管理。为了实施高效的时空查询以便跟踪与监控移动物体，本 文利用数据缓存、数据库分割与索引技术来优化提出的算法，算法有效性在真实 r f i d 数据和模拟数据上的大量实验所证实。更进一步，本文提出了一个分布式 r f i d 数据模型，此模型通过g a t e n o d e s 分布式索引多个d r e r 模型，而g a t e n o d e 利用了算术基本定理索引位于分布站点的移动物体。我们也使用提出的算法实现 了一个时态r f i d 数据管理系统。 关键词：r f i d 数据管理；时空数据模型；基于规则的系统；算法优化：分布式架 构 英文摘要 一_ _ _ _ - _ _ - _ _ _ - _ _ - 一 a b s t r a c t r f i d ( r a d i of r e q u e n c yi d e n t i f i c a t i o n ) t e c h n o l o g y i s e n a b l i n g c o s t 。e f f e c t i v e s e n s i n ga n di d e n t i f i c a t i o ni nv a r i o u sl a r g e s c a l ea p p l i c a t i o n si nr e t a i l ，p h a r m a c e u t i c a l s ， h e a l t h c a r ea n ds u p p l yc h a i nm a n a g e m e n t h o w e v e r ，t h ec h a r a c t e r i s t i c so fr f i dd a t a i n c l u d et i m e d e p e n d e n c y ，d y n a m i cc h a n g e s ，h u g ev o l u m e sa n dh o a r d o fi m p l i c i t s e m a n t i c s t h ei n h e r e n tn a t u r eo fr f i dd a t ap o s e ss i g n i f i c a n tc h a l l e n g e st or f i dd a t a m a n a g e m e n t ，p r o b l e m sb e c o m ee v e nw o r s ew h e nt h e r e a r em i s s e dr e a d i n g s ，f a l s e r e a d i n g s ，a n dr e d u n d a n tr e a d i n g s i nr e c e n ty e a r sr e s e a r c h e r sh a v ei n v e s t i g a t e dw a y so fr f i dd a t ap r o c e s s i n ga n d i n t e g r a t i o n ，b u t t h e r ei ss t i l ls p a c ef o ri m p r o v e m e n t si nt e m p o r a ld a t ap r o c e s s i n g , m o d e l i n g ，a n dq u e r y i n g i nt h i st h e s i sw ep r o p o s es p a t i o - t e m p o r a ld a t am o d e l s ，d e s i g n a n di m p l e m e n tar u l e b a s e df r a m e w o r ki ns u p p o r to fe f f i c i e n tt r a c k i n ga n dm o n i t o r i n g o fr f i dt a g g e do b j e c t s i nd o i n gt h i s ，w ef i r s tp r e s e n tac o m p r e h e n s i v es u r v e yo ft h e s t a t e o f - t h e a r ti nr f i dd a t am a n g e m e n t t h e n ，w ep r e s e n ta ne x t e n d e dd r e rm o d e l t oc e n t a l l yh a n d l em a s s i v er f i dd a t ai nt e r m so ff i l t e r i n g ，a g g r e g a t i o n ，t r a n s f o r m a t i o n ， a n ds p a t i a l t e m p o r a ld a t am a n a g e m e n t t op e r f o r me f f i c i e n tt e m p o r a lq u e r i e st ot r a c k a n dm o n i t o rm o v i n go b j e c t s ，w eu t i l i z ei n - m e m o r yc a c h i n g ，d a t a b a s ep a r t i t i o n a n d i n d e xt e c h n i q u e st oo p t i m i z et h ep r o p o s e da l g o r i t h m s t h e e f f e c t i v e n e s so fo u r a l g o r i t h m si sv a l i d a t e db ye x t e n s i v ee x p e r i m e n t st h a ta r ec o n d u c t e do nr e a lr f i d d a t a a n ds i m u l a t e dd a t a f u r t h e r m o r ew ep r o p o s ead i s t r i b u t e dr f i dd a t a m o d e lb y i n c o r p o r a t i n gm u l t i p l ed r e rm o d e l sw i t hd i s t r i b u t e di n d e x i n gt h r o u g hg a t e n o d e s ， w h i c hu t i l i z e st h ea r i t h m e t i c a lf u n d a m e n t a lt h e o r e mt o i n d e xm o v i n go b j e c t si n d i s t r i b u t e ds i t e s a l s ow eh a v ei m p l e m e n t e dat e m p o r a lr f i dd a t am a n a g e m e n ts y s t e m b yu s i n gt h ep r o p o s e da l g o r i t h m s k e yw o r d s ：r f i dd a t am a n a g e m e n t ；s p a t i o - t e m p o r a lm o d e l ；r u l e - b a s e d s y s t e m ；a l g o r i t h mo p t i m i z a t i o n ；d i s t r i b u t e da r c h i t e c t u r e 目录 目录 第1 章绪论l 1 1 课题研究背景1 1 2 论文研究内容3 1 3 论文组织结构3 第2 章r f i d 数据管理的研究现状4 2 1r f i d 数据处理概述4 2 2r f i d 数据模型6 2 3r f i d 数据缓存10 2 4r f i d 分布式数据处理的研究1 3 第3 章集中式的r f i d 数据处理1 5 3 1 移动对象的时空特性1 5 3 2r f i d 数据建模1 7 3 2 1 时空数据模型1 9 3 2 2 时空数据模型在数据库中的实现2 0 3 3 系统架构设计2 2 3 4 规则与r f i d 数据处理2 4 3 4 1 规则定义2 4 3 4 2 基于规则的数据处理2 6 3 5 本章小结2 9 第4 章算法、优化及实验对比分析3 0 4 1 规则的解析执行3 0 4 1 1 算法描述31 4 1 2m y c e p 和e s p e r 对比结果及性能分析3 5 4 2 时空模型包含关系的优化3 7 4 2 1 概念模型与集体运动分析3 7 4 2 2b u l k 和n o b u l k 对比结果及性能分析4 0 4 3 数据的更新与查询优化4 5 4 3 1 优化动机4 5 4 3 2 缓存优化算法4 6 4 - 3 3 自适应区间更新算法4 9 4 3 4c a c h e 和n o c a c h e 对比结果及性能分析4 9 4 4 本章小结5 3 第5 章分布式的r f i d 数据处理5 4 5 1 分布式数据模型5 4 5 2g a t e n o d e 以及算术基本定理的应用算法5 8 5 3d i s t r i b u t e d 与c e n t r a l 对比结果及性能分析。5 9 5 4 本章小结6 0 第6 章r f i d 数据管理系统的实现6 1 6 1 分布式架构6 1 6 2 系统模块介绍6 2 6 2 1 系统部署模块6 2 6 2 2 规则系统模块6 3 6 2 3 数据缓存模块6 4 6 2 4 数据查询模块6 6 6 2 5 分布式模块：6 6 6 3 系统功能展示6 8 第7 章总结与展望7 0 7 1 总结7 0 7 2 展望7 0 参考文献7 1 附录规则的b n f 范式7 5 攻读学位期间公开发表论文。7 7 致谢7 9 r f i d 数据模型研究及其系统实现 第1 章绪论 1 1 课题研究背景 射频识别( r a d i of r e q u e n c yi d e n t i f i c a t i o n ，r f i d ) 是一种非接触式的自动识别 技术1 1 1 ，用于对物理实物的识别、跟踪和管理。与条形码技术相比，r f i d 不需要 实际的物体接触，r f i d 技术在通信距离、可存储数据量、批量读取、数据信息修 改、环境适用性、安全性和自动性等方面更具优势。因为r f i d 技术的优越性，它 正在逐渐的被应用到更广泛的领域，诸如仓储管理与物流、航空生产制造与装配、 邮件快运包裹处理、文档与图书管理、医疗保健、宠物管理、门禁管制、车辆管 制、特种容器管理、军事等许多领域。r f i d 技术与互联网、通信等技术相结合， 可实现全球范围内物品的编号、分类、识别、监测、跟踪和信息共享，这样就可 创建一个i 溥i d 连接的网络世界，即所谓的“物联网”。 一个r f i d 系统可以由主机电脑、r f i d 读写器、标签组成。标签存储着代表物 品的标识符( d ) ，电子产品代码( e p c ) 标准定义了世界范围内物品的唯一的i d 。 当标签进入识读器检测范围内，标签将贮存在内存中的i d 等数据转化为信号发送 给识读器。识读器解码再将数据发送给后台主机。由于工作环境和无线通信的特 殊性，r f i d 数据具有不同于传统数据的特点： 1 原始数据结构简单，逻辑语义不清 由r f i d 产生的观测值具有隐含的意思，它必须根据应用场景转换和汇聚成 代表它们模型的具有语义的数据。原始数据由识读器标记，物体标记以及时间戳 组成，结构简单。每个原始数据可代表一个事件，如某物体进入某位置事件等， 只有多个元组聚集，才能构成高级的语义如偷窃商品等。 2 时态性和空间性 r f i d 数据的每个元组都有一个标识它发生的时间，多个带有时间的数据连续 起来，就形成了随时间而变化的数据流，因此r f i d 数据具有时态性。若r f i d 对象经过某地的识读器，代表物体经历了这个地方，运动的对象经过多个位置就 形成了一个曲线，代表物体运动的路径，因此r f i d 数据又具有空间性。 ， 3 数据不准确 第1 章绪论 r f i d 识读器并不是百分之百可靠的。有的时候，识读器会不正确的读取到不 存在的标签( 错误多读) 或者识读器在它可识别的范围内没有读取该读的物体( 错 误漏读) ，因此数据在传入系统之前要经过数据过滤。另外一种，识读器还可能 不止一次的读到相同的标签( 重复数据) ，这种类型的错误称为语义错误，需要 经过语义过滤。 4 连续流产生巨量数据 r f i d 数据是时序性的流数据，流量大又必须实时动态处理。射频标签的数量 是与将要被感知的物品的数量成正比的，识读器的数量是与跟踪策略中的位置 地点的数量成正比的。在某些情况下，带有标签的物品在某个位置放置的时间比 预计的时间长，识读器在这段时间内，会周期性的记录它们的存在。这些简单的 数据会不断产生，产生巨量数据需要实时性处理。 5 并发与分布 r f i d 实际应用场景中将部署多个r f i d 识读器，并且每个r f i d 识读器对应 一个r f i d 数据流。对于特定物品的跟踪和分析，需要整合多个物理上分布的数 据流。 这些特点给传统的数据管理提出了新的挑战，r f i d 数据管理面临越来越多新 的难题【2 卅。有效管理和利用r f i d 数据，就成了r f i d 数据管理研究的共同目标。 虽然学术界已认识到了研究r f i d 数据管理的重要性，但到目前为止，针对r f i d 数据管理技术的研究在国际上还不是很多，很多问题还没得到解决，比如，r f i d 复杂事件处理【7 ，8 1 ，r f i d 数据模型和r f i d 数据存储查询【9 ，1 0 1 ，以及l 讧i d 的分布 式处理【l l ，1 2 】等等，都需要做大量的研究工作。 通过阅读大量的文献，认真的研究和分析r f i d 数据处理的相关内容，本课 题针对r f i d 系统中亟待考虑的数据处理框架、通用时空数据建模、数据存储、 数据查询以及分布式架构等展开讨论和深入研究。 r f i d 数据模型研究及其系统实现 1 2 论文研究内容 本论文的目标是研究扩展的以规则框架为基础r f i d 数据模型。研究高效的 数据处理技术及优化，设计并实现一个高效的r f i d 数据管理系统。为此研究以 下内容： 一、根据r f i d 数据及应用特点，实现r f i d 时空数据模型，支持更多种类 的查询；使用数据库分区以及索引技术提高数据的存储和查询效率；对供应链环 境下的物体集体运动的模式进行了深入的研究。 二、定义和解析r f i d 数据处理规则，为了减少访问数据库的频繁更新给系 统带来的负担，设计并实现基于缓存存储临时数据的r f i d 数据处理体系结构以 便缓存支持最近数据查询。 三、实现分布式r f i d 数据模型处理。为了实现分布式环境下，组织之间的 数据共享与沟通，设计g a t e n o d e 结构，采用算术基本定理，使用素数索引物体 经过的位置。 1 3 论文组织结构 本文共分为七章，除本章外其它各章的内容概括如下： 第二章主要从r f i d 数据处理、数据模型、数据缓存、分布式四个方面介绍 r f i d 数据管理的现状，引出一些r f i d 数据处理的基本概念，并对每一部分的研 究现状做了分析与对比。 第三章主要介绍集中式的r f i d 数据处理，包括时空数据模型的构建以及使 用的规则系统。 第四章提出规则处理算法，并从时空概念模型、缓存两个方面对r f i d 数据 处理算法进行优化，并给出实验结果及分析。 第五章主要介绍分布式r f i d 数据处理，包括模型，g a t e n o d e 算法，以及实 验结果和分析。 第六章主要介绍系统包含的各部分模块，包括实现技术以及主要类图。 最后总结了作者在本课题上已完成的工作，并提出了下一步的研究内容。 第2 章r f i d 数据管理的研究现状 第2 章r f id 数据管理的研究现状 r f i d 技术出现已经5 0 余年之久了，近年来它给数据处理和管理带来了许多 新的挑战，大规模应用的不利一面是r f i d 数据漏读、读数不可靠、数据冗余、 数据泛滥以及r f i d 数据的时空管理等所造成的困难。c h a w a 廿l e 等就强调了能够 处理各种各样的r f i d 标签、识读器及其能力差异的方法是必要的，能够有效地 进行清洗、过滤和增强原始r f i d 数据的系统结构也是必要的。 2 1r fid 数据处理概述 l - r f i d 数据管理框架的研究 r f i d 数据管理需要一个有效的整体框架，整个管理过程和方法，并考虑和 协调的r f i d 数据管理的各个方面。e p cg l o b a l i 3 1 尸经为研究和应用r f i d 技术给 出了大量基础架构，提供了许多标准和白皮书，但是它不强调具体的解决办法， 不涉及r f i d 数据建模，分析和挖掘。许多大型的r r 服务供应商，如i b m 、惠普、 微软、甲骨文、s a p 、西门子和s u n 等，它们的r f i d 数据管理平台只包括r f i d 数据的获取、清洗和规范化，高一层次的r f i d 数据建模和管理是由应用程序负 责的。这些r f i d 服务器或中间件，大多都是在其原有的产品架构上设计的，实 质上没有考虑r f i d 数据的独有特性。 2 r f i d 数据清洗的研究 r f i d 数据其实是不可靠的，使用前需要进行必要的清洗处理。现有的比较 著名的r f i d 数据清洗方案有可扩展传感器数据流的处理( e s p ) 【1 4 】和s m u r f 1 5 1 。 e s p 是2 0 0 6 年伯克利大学提出的一个对r f i d 等传感器数据流进行在线清洗的通 用技术，通过引入时态与空间粒度的概念，来捕获时间和空间的应用层含义。不 过e s p 在以下两种情况是失效的：从时间粒度( 即滑动窗口) 讲，很难确定一个 合适的滑动狂口的大小，只有一个合适的滑动窗口大小才能有效解决漏读和多读 问题；从空间粒度讲，很难确定一个合适的空间过滤粒度，表示频繁运动的物体。 针对r f i d 数据的不可靠性以及窗口大小的选择，2 0 0 6 年伯克利大学提出一种适 应性的滑动窗口的清洗策略s m u r f ，此种策略通过将r f i d 数据流看成物理世界 r f i d 数据模型研究及其系统实现 中r f i d 标签的统计样本来建模。他可以在系统的整个生命周期内，基于r f i d 观察值来自动连续的调整窗口大小，并采用样本理论技术驱动r f i d 数据流的清 洗过程。然而，这个方法不能消除错误，对于运动的标签，错误率更大。在本文 中，我们假设r f i d 数据已经有足够的质量筛选，以转化成应用程序逻辑。 3 r f i d 复杂事件处理的研究 复杂事件处理技术( c e p ) 是原始的物理数据归约成有含义的逻辑事件的技 术【1 每1 8 1 。不同的应用系统可以通过c e p 得到不同的高级事件，如库存管理系统可 以得到出库、入库高级事件，而考勤管理系统可以得到上班、下班、迟到、早退 等高级事件。 早期的复杂事件处理主要应用在主动数据库领域1 9 ，冽。复杂事件检测方法分 为四类：基于有限状态机，基于p e t r i 网，基于图形和基于树的。 基于有限状态机的复杂事件检测方法：思想是每当一个参与复合事件发生的 基本事件到达，自动机就会从一个状态跃迁到下一个状态，当自动机进入某个可 接受的状态，则说明发生了复合事件。在文献【2 1 ，捌，作者有限自动机c a y u g a 检 测复杂事件。c a y u g a 解决了重复操作和时序限制问题，但是它增加了许多内部的 命名，这个是用户难以理解的。 基于p e t r i 网的复合事件检测方法：p c t r i 网的输入位置结点为基本事件，输 出位置结点为复合事件。通过输入t o k e n ，计算跃迁守护函数，如果成立，则引 发跃迁并标记位置结点，当序列中的最后一个位置结点被标记后，则说明复合事 件发生。复合事件的增量检测是通过p c t r i 网中标记的位置来描述的。s a m o s 系统 2 3 】，它把事件当做一个时间点，而h i f i 系统【2 4 ，2 5 1 讨论了系统结构中的大多 数问题。 基于图的复杂事件检测方法：节点是对事件的描述，边为事件复合的规则。 节点通过对相关事件的引用进行标记。除了用边表示事件合成规则，节点也带有 相应的规则，随着对应节点的事件发生，节点的规则也会被触发。s n o o p 系统【2 6 1 采用有向无环图( d a g s ) 检测复杂事件，但它还不足以表达复杂的概念。 基于树的复杂事件检测方法：思想就是如何根据复杂事件模式构件匹配树。 在匹配树种，叶子结点代表原始事件，其他结点代表事件的组合，匹配时，如果 第2 章r f i d 数据管理的研究现状 到达根节点，并且成功检测事件，则认为检测到一个复杂事件。y e a s t 系统【2 刀是 一个早期使用树结构的c e p 系统。 在复杂事件处理研究领域，处理复合事件大多数工作都与主动数据库有关， 一般是集中式处理，只有少数几个是分布式处理。大部分工作使用树做为数据结 构的基础。p e t r i 网模型非常适用构建和描述非常复杂并发的行为，然而，它的实 现太为复杂，并且相对来讲，效率不高。使用的数据结构式状态机，他的弱势是 不能够检测并发事件，不能依靠事件发生的时间对事件重新排序，而使用树作为 其数据结构的主要原因是因为树结构简单，在过去已经研究的很深，有很高效的 遍历和操作算法。下面的项目采用树表示复合事件：e v e 2 8 】是一个工作流事件检 测器；g e m l 2 9 】是分布式系统的事件检测器。在e v e 和g e m 检测系统中，每一个 请求都要重新建立一个全新的事件树，即使只有一个事件，即使这个请求需要的 事件已经被其他树的子树构建过了。 2 2r fid 数据模型 r f i d 的应用非常广泛，r f i d 数据模型是管理r f i d 数据的基础，决定着基于该 模型数据管理方法的有效性。总体上看，r f i d 应用有着共同的需求特点： 识别：r f i d 标签通常附属于某个物体，用于唯一地标识该物体，读取到一 个标签就代表了观测到它所对应的物体。 位置：一个位置可以是一个地理位置，也可以是有背景含义的特殊位置，如 仓库、超市、手术室等。r f i d 应用中的监测和跟踪是依靠r f i d 观测值保持了物 体经过不同位置的运动路径产生了轨迹。这些运动往往是通过序列观测值获得的， 关联着特定应用中的某种业务处理。 关系：r f i d 应用的另一个关键概念是聚合，即对象之间形成的关系。一种 常见聚合情况是包含关系，即在物体运动过程中，被包含的物体与外包装物体有 相同的运动路径等特性。另一个集合情况是协作，即贴有标签的物体之间有一定 的关系，比如一台笔记本电脑只有授权人员才能将其带出公司，那么电脑和授权 人员之间有协作关系。 r f i d 数据模型研究及其系统实现 将上述l 强i d 应用特点表达出来即为r f i d 数据模型。文酬5 】总结了r f i d 数 据的特点，构建数据模型需要注意的要点。目前有以下模型： 1 e p c 信息服务模型 2 0 0 3 年，a u t o i d 中心的m h e r r i s o n 提出了e p c 信息服务模型【3 0 】，这个模型 标志着开发存储e p c 接口的开始。作者将数据看做事件，减轻了保存历史信息的 负担。但是，这种模型在支持复杂的监测跟踪r f i d 物品方面还不是很有效。 2 动态关系实体关系模型d r e r 在概念层上讲，出现了很多有趣的基于e r 模型的信息系统的时序模型。e r 模型和时序模型之间最主要的差别就是，时序模型中数据变化特别快，有动态变 化的特性。在e r 模型中，所有的属性和实体都是静态的，而在典型的r f i d 系 统中，实体是静态的，但是他们之间的关系是动态的。这就是为什么时序模型更 加实用r f i d 系统。处理r f i d 数据比较典型的时序数据模型就是西门子公司提 出的动态关系e r 模型( d r e r ) 。d r e r 采用物件包含和关联等关系聚合r f i d 数据，通过基于规则的方法来解决问题【9 】。该模型是通过简单增加一个称为“动态 关系”的关系，对e r 模型进行时态扩展。有两种“动态关系”：( 1 ) 产生事件的 关系，时间戳( t i m e s t a m p ) 用来关联事件的发生时间； ( 2 ) 产生状态历史的关 系，用t s t a r t 和t e n d 两个属性关联。该模型使用规则语言处理数据转换，并提供 了强大的对象跟踪和监测功能，即查询，就是在静态表和有动态关系映射的动态 关系表上使用标准的s q l 语句就可以实现。该模型没有涉及r f i d 事件数据泛化 等问题，没有考虑由持续数据流带来的问题，也没考虑数据压缩机制。另外，该 模型被限制在只读标签和固定识读器。 3 通用时态数据模型t d m r 通用时态数据模型【i o j 扩展动态关系实体关系模型，根据r f i d 应用的特点， 标签的类型，识读器的类型以及位置的语义，建立r f i d 应用的各种场景，再对 每种场景进行数据建模，包括r f i d 和g p s ，s e n s o r 技术的结合构造的数据模型， 并给出对应的表结构。 4 位图数据类型， 第2 章r f i d 数据管理的研究现状 文献【3 l 】利用位图结构来优化r f i d 数据库。这种方法是由o r a c l e 公司的研究 人员开发的。位图数据结构是布尔值的排列，最好的情况下八个排列的元素刚好 可以储存到一个字节中，用e p cb i t m a p 的数据结构来实现o r a c l e 中r f i d 数据 的处理、查询和管理，有效地进行数据维护、转化以及运算。通过跟踪物件所属 的群组，也就是相邻( 如同一货架，同一批装运) 和具有相同属性( 如同类产品 的物件) 的物件组，可以更为有效地跟踪r f i d 物件。该模型将具有相同e p c 前 缀的元组压缩成一条记录( 而不是为每个物件存储单独的记录) ，存储e p c 后缀 开始和e p c 后缀结尾，并通过位图来描述在e p c 后缀开始和e p c 后缀结尾范围 内存在的对应物件。r f i d 位图数据类型可获得较好的数据压缩和一定的查询效 率，并且在现有的数据库系统如o r a c l e 等中较易实现。但该模型只是特别适合需 要初始批量装载和批量更新的场合。没有考虑对r f i d 事件数据的时态、数据流 等特性的支持。 5 数据立方体模型 在考虑r f i d 数据的聚合和泛化方面，r f i d 数据立方体模型及方法 3 2 , 3 3 】较为 全面且适用。文献【3 2 】针对这些问题提出了l 讧i d 数据仓库架构，充分考虑物件的 成批移动、数据泛化、部分路径的融合和展开，从三个方面进行数据的压缩，并 提出了r f i d 数据立方体。在数据立方体模型中。s t a y _ t a b l e ( 西d ，l o c ，s t a r t _ t i m e , e n dt i m e ，c o u n t ) 能够有效的存储r f i d 数据。在很多i l f i d 场景，物体都是开始 集体运动，后来分裂为小组运动的。而组内的物体有相同的运动特点，走一样的 路线，在一个位置等待同样的时间。因此将这个小组内的成员聚合为一个记录 ( t a gi d e n t i f i e rl i s t ，l o c a t i o n , s t a l tt i m e ，e n dt i m e ，t h en u m b e ro ft a g sw i t ht h es a m e l o c a t i o na n dt i m e ) 。为了高效的连接位置，对t a gi d e n t i f i e rl i s t 采用前缀编码方案。 由前缀编码方案得出的编码数值直接连接到s t a y 中的 属性。要想知道位t a b l eg i d 置a 和位置b 是否相连，只要看a 坐在的组的g i d 是不是b 所在的组的g i d 的 前缀。r f i d 数据立方体利用物品的成组移动、业务对象的层级泛化结构、物件 之间的包含关系以及路径视图和物件视图等，可在多维空间执行有效和广泛的高 层级分析。该模型包括一个由r f i d 数据在不同抽象层级上聚合而得到的高度精 简摘要的层次结构，在数据压缩、查询处理效率等方面更有优势。但该r f i d 数 r f i d 数据模型研究及其系统实现 据立方体模型及分析方法的前提一单个物件在早期倾向于成批移动和停留的假 设，在除供应链之外的许多其他应用领域中，如身份识别，并不成立。此外，因 为前缀编码使用的是字符串比较，它比数值需要跟多的对比查找时间。另外，文 献【3 4 ，3 5 】提出流立方体( f l o w c u b e ) 和流图( f l o w g r a p h ) 这两个重要概念。流立 方体是一个数据立方体模型，归纳r f i d 数据的( 路径无关的) 物件视图和路径 视图上的相关数据，其中的每个单元格所对应的度量称为流图。该流图在属于对 应单元格的路径上进行计算。流立方体模型及方法可协助发掘物件移动趋势及异 常，并可进行相关流程分析。流立方体采用概率模型建模，目前可看作r f i d 数 据挖掘的研究方向。但该模型如同数据立方体，也是基于单个物件在早期倾向于 成批移动和停留的假设，因而适用范围缩小。 6 l e e 和c h u n g 模型 文献【3 6 , 3 7 】提出一种能够处理跟踪查询和面向路径查询的路径编码方案，即对 每个位置设置两个数字( 即元素列表编码数字和顺序编数字) ，使用素数的唯一 性特点对路径中的节点进行编码，此编码方案是基于算术基本定理和中国剩余定 理的。使用这种编码方案，能够有效的满足检索路径中的查询路径的条件。为了 存储路径运动的相关时间信息，此方法将时间从跟踪记录中分离出来，使用区间 编码方案，以便有效地检索时间信息。另外，文献还为跟踪和面向路径的查询定 义了查询模板。但是，此模型只使用非实时数据处理的情况，因此数据已知，使 用中国剩余定理，对每组位置的素数集合，仅计算一遍，而在实时情况下，素数 集合在动态增加，若使用剩余定理，需要对每次变化都进行计算，计算量大。 7 r o b e r t od ev i r 西l i o 模型 文献【3 8 】利用物体集体运动的特性提出了供应链数据管理框架。这个方法提出 一个新颖的增量聚集思想，它的基础是对描述r f i d 数据的属性进行合并，适合 不同维的数据分析，不仅仅只有位置和路径分析。基于数据压缩技术，设计一个 无损，以基于关系为基础的存储模型，在这个模型中可以存储与路径相关和与路 径不相关的数据。综合来说，此模型根据r f i d 数据上的集合概念，对原始数据 进行聚合操作，保存最后聚合的结果，从而减少存储空间。 第2 章r f i d 数据管理的研究现状 为了能够表达物体之间的变化，采用了有向无环图，在图中，每个节点代表 一个位置，如果有物体从位置l 1 到位置l 2 ，那么就存在一个有向边连接l 1 和 l 2 。没有进入的边的点位源点；没有出去的边的点为目标节点，从源点到目标之 间存在几个路径，就标记几个路径p a t h l ，p a t h 2 p a t h n 。为每个点即位置设置个 t o k e n ，这个t o k e n 表示从这个位置出发，经过的路径的编号。 图2 1 供应链索引 f i g 2 1s u p p l yc h a i ni n d e x i n g 此方法的优点是能高效聚集数据，有效的支持聚集查询，采用区间编码提高 了数据的查询速度。但是这种方法是基于数据仓库的概念，处理的不是实时的数 据。数据运动的路径是已知的，采用的技术对于实时数据处理也是不适用。 2 3r fid 数据缓存 c l a u sh e i n r i c h 在文献【3 9 】中定义了现实世界意识，它定义了抽取实时信息的处 理，从而更好地了解不同的业务处理。实时商业智能应用，在决策过程中，不仅 仅依靠历史数据，同时需要最新的信息。不同于传统的数据仓库，数据的更新通 常是定期，如夜晚或者周末，而可追溯信息需要根据需要更新。一但有新的事件 到达，就会触发数据缓存。获取最新信息不仅仅对搜索物体最近位置的查询有用， 它同样对商业智能应用执行o l a p 查询中的决策的一个重要需要。业务数据的分析 处理往往应用到解决问题，而这些问题的解决需要日常基础的积累的决策支持。 r f i d 数据模型研究及其系统实现 因此，需要一个有效的可追溯数据增量更新( 数据缓存) ，以及为o l t p 和o l a p 提供可接受的查询相应时间。 r f i d 系统不仅仅要支持处理大量数据，而且必须有效地支持最近数据和历史 传感器数据的查询和分析。数据缓存结构由分布式的缓存层和数据仓库组成。数 据缓存存储了最近的r f i d 数据，以便支持o l t p 处理。过期的事件从缓存中移除， 转移到数据仓库中，在这个过程中，需要聚集相关的事件，以减少存储空间的消 耗。h a s s op l a t t n e r 在它的工作【柏】中讨论了o l l 曙和o l a p 的常用数据库方法，因为 这能使两个组件对用户更加有价值。而针对可追溯数据的处理上，有的只实现其 中一个组件，或者是o l a p ，或者是o l t p ，或者采用混合的方法即两个组件处于 不同的系统中。因为可追溯应用需要参考最新的数据从而构造更好的决策处理过 程。 在文献一i j 中，高速缓存由内存数据库组成，保持最近的r f i d 数据，以便有效 地支持o l t p 查询。过期的r f i d 事件会从缓存，经过事件聚合转移到数据仓库，以 减少存储空间。并发也是本系统的一个主要特征。传统的数据仓库定期更新，更 新的频率不频繁，而此文献中的数据缓存方法动态更新数据仓库。另外，在这个 研究中，也挖掘了物体集体运动的特性，因此在数据缓存机制中，采用元组数据 缓存和集体数据缓存，更新数据仓库中的数据。数据缓存的处理方法是：当有物 体转移到新的位置，那么就会触发数据从高速缓存转移到数据仓库的更新。这种 更新分为两类，一类是基于元组方式，另一类是基于组( 集体批处理) 方式的。 基于元组的是，一组物体有相同的特性，当这组物体转移到一个新的位置，那么 就对这组物体进行操作，将它们从高速缓存转移到数据仓库。不论是哪种更新， 转移的过程要经过大量的计算，才能从粗糙的三元组变为有意义的数据存储到数 据库中。基于元组的方法是针对每个物体，当它的状态改变，就更新数据仓库， 而集体操作的方法是针对一组物体的状态改变而出发数据仓库的更新操作。数据 库设计中，存储了大量的路径冗余信息。此方法的优点是：通过冗余信息，可以 有效地支持查询，尤其是路径查询，支持增量更新，不需要延迟。在数据量小， 处理简单的情况下，可以保持实时性。但是它存在很多缺点：第一，从原始数据 经过数据过滤、转换、聚集，再存储到数据中，这个过程中需要抽取大量的信息， 第2 章r f d 数据管理的研究现状 组成r f i d 路径的数据。这个步骤是事件处理过程中完成的，因此，增加了事件处 理的负担；第二，当数据量大的时候，在数据转化的过程中