4.6.RFID海量数据压缩与存储算法的实现

4.6.1.问题的提出

在物品跟踪和供应链管理系统中，RFID的应用将发挥重要的作用。像世界零售巨头沃尔玛这样的大型零售商已经开始在他们的物品仓库和配货中心部署RFID系统。一些研究机构估测，沃尔玛的RFID系统每天将会产生大约7兆兆字节的数据。因此，如何存储和检索海量RFID数据就成了一个迫切需要解决的问题。

传统的关系数据库技术已经不能完全应对如此巨大的数据量以及基于海量数据的检索。文献[1]中提出了一种新的数据仓库结构RFID-Cuboids。这种新的数据仓库结构RFID-Cuboids主要利用大量物品的成批移动，数据泛化和部分路径的融合等特性来进行数据压缩和存储，极大地减少了存储空间，提高了查询效率。本文我们参照文献[1]用C#语言实现了RFID-Cuboids结构。

4.6.2.RFID-Cuboids数据压缩的主要思想

l 基于大量物品的成批移动

在不同的阶段有大量的物品成批地移动或停留在相同的位置上，因此我们没

有必要存储所有的记录，我们可以用一个单一的元组来表示这些物品，不管这些物品有多少。例如：假设有1000盒牛奶在（t1，t2）的时间间隔内停留在位置A上，我们不需要存储1000个（prod-list，A，t1，t2）这样的四元组记录，只需用一个五元组（pro-list，A，t1，t2）来代替，大大的节省了存储空间。

l 数据泛化

许多用户仅仅对一些较高抽象级别的数据感兴趣，因此我们可以采用数据泛

化技术来进行压缩。例如：如果最小的时间间隔粒度为hour，那么在相同的hour内大量物品的移动可以看作是一起移动，可以合并为一次移动。同样的，如果location的最小粒度是shelf，那么大量物品移动到不同的shelf可以看成是移动到同一位置，也可以合并为一个记录。

l 部分路径的融合

在许多分析工作中，特定的路径段可以被忽略或者合并成一个简单的路径。

例如在特定的分析中一些不必要的物品的移动，比如从一个shelf移动到另一个，可以完全被忽略。在不影响整体分析结构的条件下，一些部分路径可以合并在一起。这些路径段的合并可以实质上减少数据的总量并加快数据分析的速度。

4.6.3.RFID数据的结构

l Raw RFID Records

我们用（EPC，location，time）这样一个三元组来表示输入的原始RFID数据记录，其中EPC表示物品被RFID阅读器读到的唯一标识，也称为tag id。

location表示物品所在的位置。time表示RFID阅读器读取数据的时间。

l Cleansed RFID Records

在固定的时间间隔内，在相同的位置上可能存在同一物品被RFID阅读器读

取多次，存在大量的冗余数据。因此，Raw RFID Records这种数据结构需要改进。例如：假设一个RFID阅读器每分钟对shelf上的物品扫描一次，那么该物品一天将有1440个（EPC，loc，time）这样的元组产生，显然我们可以对这些元组进行时间上的压缩，用一个记录（EPC，location，time_in，time_out）来表示输入的数据。其中time_in表示物品进入location的时间，time_out表示物品离开location的时间。我们称这样的记录为Cleansed RFID Records。

表4-1：Cleansed RFID Records

4.6.4.数据仓库模型RFID-Cuboids的组成

   （1）Information Table

Info table 中保存了一些和路径无关的物品信息，例如：产品名，制造商，产品价格等。Info table存在的意义在于每个物品有很多属性，我们在进行数据压缩的时候没有必要将所有属性都带上 ，将这些与压缩无关的属性单独用info table存储节省了每个记录的空间，需要查询这些属性的时候通过主关键字在info table中查找即可。

（2）Stay Table

基于大量物品的成品移动这个特性，在Cleansed RFID Records中，会有大量的物品在某个相同的时间间隔内存在于同一位置上，如果我们对关键字epc进行压缩，就可以用一个记录（epc-list，locA，time_in，time_out）来表示上述多个记录。其中epc-list中存放了多个相同时间在同一位置的epc值。

 在Stay Table 中我们用gid来代替epc-list，即用（gid，loc，time_in，time_out）来表示上述元组，其中gid表示物品当然所处的阶段或者说是层次，它指向更低层次的gid或者是epc-list的列表。

 例如：假设刚开始时有50盒牛奶放在locA，接下来有20盒放到了locB，另外30盒放到了locC，那么这时若locA的gid为0，则locB的gid为0.0，locC的gid为0.1，gid:0 指向gid:0.0和gid:0.1，而gid:0.0则指向epc-list即20喝牛奶的epc值，同理gid:0.1指向30盒牛奶的epc值。

 用gid带替epc-list的好处就是它不仅表示了epc-list中的内容，同时也将物品移动的路径连接了起来。

（3）Map Table

Map table是RFID-Cuboids区别于传统的关系数据库模型最关键的部分，它记录了物品的移动方向，将一个路径上的不同阶段连接起来。Map table中的元组用（gid，gids）来表示，gid表示物品当前所在的层次，gids是gid所指向的低层次gid或者是epc-list列表。

4.6.5.构造RFID-Cuboids数据仓库结构

   （1）将输入的Raw RFID Records转换成Cleansed RFID Records

    将Raw RFID Records先按关键字epc排序分成若干组，然后再对每个小组按关键字time排序，最后将某个时间间隔内在同一位置的元组合并。

（2）将Cleansed RFID Records作为输入，构造RFID-Cuboids，即构造Stay Table和Map Table。

首先，根据输入构造初始的Path_Tree。

l 然后层次遍历初始的Path_Tree，将某个时间间隔内在同一位置的记录

合并在一起。

l 层次遍历合并后的Path_Tree , 构造各个结点的gid分量。

l 构造Stay table

层次遍历Path_Tree中各个结点，将（gid，loc，t_in，t_out）作为table

的记录输入，需要注意的是根据部分路径融合的原理，如果叶子结点中有若干个结点的loc，t_in，t_out属性相同，可以将它们的gid合并在一起，作为一个记录输入。

表4-2：Stay Table

l 构造Map table

同样层次遍历Path_Tree中的各个结点，将结点的gid作为table中gid

的属性值，将结点孩子的gid值作为该结点的gids属性值。如果孩子结点epc_list中epc的总数小于该结点的epc数，那么在孩子结点中没有出现的epc值也作为该结点的gids属性值。如果结点为叶子结点，那么结点的epc值即为gids值。

4.6.6.基于RFID-Cuboids的数据查询

传统的数据仓库结构能够实现物品在某一给定位置的数据查询操作，如果某些查询需要将物品移动的各个阶段连接起来，那么传统的数据仓库结构就显得力不从心。RFID-Cuboids结构对上述查询有着很好的效率，我们将基于RFID-Cuboids的相关查询称为Path Selection。

假设根据所给的RFID原始数据我们构造的RFID-Cuboids（Stay table，Map table）如上表所示。

使用RFID-Cuboids进行查询的示例如下：

Query：查询经过路径l1->l3->l4的无物品。（1）首先在Stay table中查找所有loc=l1的所有记录的gid列表<0>。

（2）在Stay table中查找loc=l4的所有记录<0.1.0>,即<0,0.1.0> 。

（3）查找loc=l3的记录中的gid列表<0.1>

（4）因为0.1介于<0,0.1.0>之间，所以<0,0.1,0.1.0>构成完整路径。

（5）在Map table 中查询0.1.0所对应的gids为r3，所以经过路径l1->l3->l4的物品epc值为r3。最后在info table中查询epc值为r3的物品的相关信息。

4.6.7.程序运行结果演示

输入的Cleansed RFID Records如下图所示：

程序运行后，所得的Stay Table和Map Table如下：

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=1240

• 4.5.4.基于RFID的仓储管理系统功能模块的具体实现2019-04-10 12:04
• 4.5.1.基于RFID的仓储管理系统的流程设计2019-04-10 12:11
• 第二章 RFID技术概述2019-04-10 12:18
• 4.5.2.基于RFID的仓储管理系统的功能模块设计2019-04-10 12:10