一种RFID数据压缩算法的研究

得到的数据集要比原始的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 o