基于三层存储模型的RFID数据压缩存储方法

　　0 引言

　　所谓物联网就是物物相连的互联网,是指通过射频识别、红外感应器等信息传感设备把物品与互联网相连接,进行信息交互和通信的一种网络[1-3]。物联网这个概念在1999年被提出之后,并没有引起人们广泛的关注,由于其包含技术的复杂性,社会普遍质疑物联网大规模实施的可行性。但随着构建物联网的电子芯片费用的不断降低与电子标签(Electronic Product Code, EPC)技术的日渐成熟[4-5],物联网的普及逐渐变得切实可行。

　　普遍认为,射频识别(Radio Frequency IDentification, RFID)的特性为:时空关联性、海量性、不确定性、实时性等[6-7]。随着物联网技术的日益发展,如何有效并快速地存储与查询RFID数据逐渐引起人们的重视。如果电子标签被放置在每个物品上,那么类似于沃尔玛这样的大型超市将会在一天之内得到7TB左右的数据,所以像Oracle、IBM、Teradata和一些其他的数据库公司不得不考虑将RFID信息整合到企业级数据库中[8]。

　　在物联网被广泛应用的背景下,RFID数据存储与管理逐渐成为物联网技术的研究方向之一[9-10]。之前的研究工作主要采用单一数据层的方式存储RFID数据,较少涉及压缩存储与历史数据的处理。如文献[11]首次给出了一般意义上的RFID数据存储结构与数据管理的体系结构,但是其结构并不能完全适应当前的RFID应用系统;文献[12]提出了一个以位置为关键字的RFID数据存储模型,并给出了在这个模型之上的查询语句,但是对于历史数据却并没有进行处理;文献[8]提出了一个简单的RFID数据压缩方法,其主要思想是将一个固定的编号来代表一连串情境相关的EPC编号(如一箱牛奶等),但是对于这个编号的尚未完成的划分方式却是实施这一方法的阻碍;文献[13]提出了一个RFID数据压缩方法,该方法的主要思想是通过合并与连接那些用户不感兴趣的路径片段进行路径的语义压缩,但是如何确定哪些路径用户不感兴趣是一个很大的难题。

　　故本文根据RFID数据的特点,提出了RFID三层数据存储模型,并给出了相应数据层的数据汇总算法。

　　1 RFID数据压缩存储模型

　　为了更好地区别与阐述当前数据与历史数据,给出RFID历史数据的定义。

　　定义1RFID历史数据。RFID历史数据为在某一特定事件驱动前的RFID数据,该特定事件与具体的RFID系统应用相关。

　　例如在一个超市RFID系统之中,一个物品在被卖给消费者之后,它之前被阅读器扫描得到的数据被称为历史数据。而在一个物流监控系统当中,在物品离开物流系统最终到达零售商店中之后,之前它在物流中产生的数据称为历史数据。如图1所示。

图片图1RFID历史数据的产生

　　本文采用了三层存储结构,并给出了相应的数据汇总方法,以达到数据压缩的目的。本文的存储模型结构如图2所示。

图片图2三层存储模型结构

　　图2中各层之间通过相应的数据汇总算法进行数据的汇总。本文RFID数据流的传递顺序是:阅读器层→当前数据层→临时数据层→历史数据层，并且高层数据层的数据量比低层数据层的数据量小。

　　在一个RFID系统中,将从阅读器得到的原始数据的集合称为观测数据集。其数据形式为Observation{E,L,T},其中E表示被扫描的物品的EPC编码,L表示物品被扫描的地点,T表示物品被扫描的时间。其具体形式如表1所示。

　　随着时间的推移,观测数据集中的数据量将异常庞大,这时需要将观测数据向当前数据层进行汇总。当前数据层的数据形式为CurrentData{EL,LocID,TS,TE,Count},其中TS与TE分别表示该物品在这个位置第一次被扫描到的时间与最后一次被扫描到的时间,Count代表该物品在TS到TE这个时间段内在该位置出现的次数。

　　当观测数据集向当前数据集进行汇总时,首先会进行EPC编号的匹配。如果在CurrentData集中不存在这个EPC编号,则将这条信息存入CurrentData集中;否则将会进行位置信息的匹配,即查找该信息的LocID是否存在于CurrentData集中,如果存在则将计数增加,否则同样将这条信息存入CurrentData集中。

　　下面给出当前数据层的汇总算法:

　　算法1当前数据集(Current Data Gather, CDG)汇总算法。

　　输入最低粒度集Observation{E,L,T}。

　　输出当前数据集CurrentData{EL,LocID, TS, TE,Count}。

　　例1在一个物联网系统中,实体epc1的标签在分别在时刻t1、t2、t3在loc1被读取到,t4、t5、t6在loc2被读取到,epc2的标签在时刻t7、t8在loc1被读取到,此时Observation集的内容如表1所示。则当运行完CDG算法之后,CurrentData集合中的内容如表2所示。

　　通过这个例子可看出：经过CDG算法之后得到的数据集要比原始的RFID数据集的数据量小,即有效地进行了数据压缩。

　　1.2临时数据层模型

　　临时数据层是中间数据层,其主要工作是将当前数据层中的位置点信息转化为路径信息进行存储,以达到压缩存储的目的。为了便于描述,下面给出RFID数据路径的定义。

　　定义2RFID数据路径。RFID数据路径是一串有序的位置点编号的集合,形如PathIDi{locIDj|j∈N},其中,PathIDi表示路径的编号,locIDj表示出现在这条路径上的位置点。

　　为了更好地阐述路径之间的关系,下面给出RFID数据子路径与主路径的定义。

　　定义3RFID数据子路径。对于两条路径tracex与tracey,如果对于任意按序的loci∈tracex(其中i∈N),loci∈tracey,则说明tracex为tracey的子路径,记为tracex→tracey。

　　定义4RFID数据主路径。RFID数据主路径是指不包含父路径的路径,即如果tracei为主路径,则不存在tracej∈Trace,使得tracei→tracej。反之,我们称不是RFID数据主路径的路径为RFID非主路径。

　　对于路径的编号采用改进的二进制哈夫曼编码,其主要思想是将路径的前n/2个码位置为其父路径编码的前n/2个码位,而后n/2个码位为其自身的自然序号。一条RFID非主路径编号编码如式(1)所示。

　　例4对例3中的TempData集合执行HDG算法之后,History集中的内容如表5所示。

　　本部分对该三层存储模型及其数据汇总算法进行实验验证。本文的硬件环境是:2.1GHz的Intel Core 2 Duo CPU,2.0GB的主存,160GB的硬盘。软件环境是:操作系统为Windows XP,编程环境为JDK1.6,数据汇总算法采用Java语言编写。实验主要分析算法的时间性能、数据压缩率、数据的失真率以及查询的响应时间。

　　2.1实验数据

　　由于场地与应用的限制,本文采用了模拟的数据集,即通过程序模拟了物品跟踪系统产生的105条RFID数据。为了更全面地验证算法的可靠性,将这105条数据划分为4个子集,分别包含1×104,2×104,3×104和4×104条数据,分别记为数据集1、数据集2、数据集3和数据集4。

　　2.2算法的时间性能

　　本文分别针对上述4个数据集进行3层数据汇总算法,实验得到算法消耗时间如图3所示。

　　通过图3可看出：随着数据集数据量的增大,时间消耗将随之增加,并且大部分的时间均消耗在第3层数据汇总即HDG算法之中,因此可以考虑改进该算法以进一步降低时间开销。

　　2.3算法的数据压缩率

　　数据的压缩率是指每个算法运行结束之后得到的数据集的大小与原始数据集的大小之比。本实验的数据压缩率如图4所示。

　　图片图4数据压缩率

　　通过图4可看出：HDG算法的数据压缩率最高,TDG算法次之,而CDG算法的数据压缩率最低。同时,随着数据集的不断增大,这3个算法的数据压缩率变化不大,即这3个算法的数据压缩率趋于固定值。

　　2.4数据的失真率

　　由于只有第3层数据汇总即HDG算法采用的是有损压缩方法,所以本实验过程只考虑HDG算法的失真率。RFID数据失真率(Data Lost, DL)的计算公式为:

　　DL=lost_colums/N(3)

　　其中:lost_colums表示已经失效的数据条数,N表示总的数据条数。

　　通过在4个数据集上运行3层汇总算法之后,实验得到HDG算法的失真率如图5所示。

图片图5数据的失真率

　　从图5可看出：随着数据集数量的增大,HDG算法的失真率将会变小,这是由于主路径数量的增加随着数据集的增大而趋于缓慢所造成的。该实验数据表明,随着主路径数据量的增加,使用主路径替代原始路径将使数据更加真实。

　　2.5查询的响应时间

　　分别在本文提出的三层模型与原始数据集下运行1000条标准查询语句来检验模型的查询响应时间,实验结果如图6所示。

图片图6查询的响应时间

　　从图6可看出：随着数据集数据量的不断增加,查询的响应时间也相应增大。但是在不同的数据集中,运行在原始数据之上的查询响应时间与运行在本文提出的模型数据之上的查询响应时间基本相同,说明本文数据的压缩存储结构对数据的查询影响并不明显。

　　3 结语

　　本文建立了一种针对RFID数据的三层压缩存储模型,并给出了相应的数据层的数据汇总算法。对数据汇总算法的复杂度分析及实验数据分析,表明本文提出的三层数据存储结构可以有效地压缩数据,具有较低的时间复杂度和较少的查询响应时间,同时,存储模型的第三层压缩数据具有较低的数据失真率,说明该模型可适应大规模RFID数据集。

　　参考文献:

　　[1]GUSTAVO R, MARIO M, CARLOS D. Early infrastructure of an Internet of things in spaces for learning [C]// Proceedings of the 8th IEEE International Conference on Advanced Learning Technologies. Piscataway, NJ: IEEE Press,2008:381-383.

　　[2]HU YING, SUNDARA S, CHORMA T, et al. Supporting RFID-based item tracking applications in Oracle DBMS using a bitmap datatype [C]// Proceedings of the 31st International Conference on Very Large Data Bases. New York: ACM

　　[3]COCCI R, TRAN T, DIAO Y, et al. Efficient data interpretation and compression over RFID streams [C]// Proceedings of the 24th International Conference on Data Engineering. Piscataway, NJ: IEEE Press, 2008:1445-1447.