面向离散制造的RFID数据清洗方法研究

余 杰，王 睿

（中国航天系统科学与工程研究院，北京 100048）

0 概述

RFID（Radio Frequency Identification）技术（射频识别）是一种无需建立机械或光学联系的非接触式自动识别技术，通过无线电讯信号自动识别特定目标并读写相关数据信息。在离散制造，RFID感知涉及“人”、“机”、“料”、“环”等繁杂对象，RFID标签的智能对象将被制造过程各环节的读写器反复读取，快速自动产生海量的数据流，产生数据量非常庞大，形成大量冗余数据。制约RFID技术在制造业中进一步发展的一个关键因素就是获取到的RFID数据呈现出很强的不可靠性，为了提供高质量的RFID数据使其能够真正被企业所应用，亟需对RFID原始数据进行恰当的清洗。不同的应用领域选择的清洗策略也应该不同，国内外各领域对RFID的数据清洗已经做了一定的深入研究，也取得了一定的进展。在实际工程应用中，通常在读写器和应用程序之间部署中间件系统进行RFID数据清洗。在这些中间件系统中，一种典型的数据清洗机制就是平滑过滤，在RFID数据流中利用滑动窗口，对时间窗口的每个标签按照一定规则进行插补。Massawe[1]等研究一个更加有效的转换检测机制，在基于统计平滑窗口技术（SMURF）的基础上，提出了一种自适应清洗方案（WSTD），利用二项抽样概念来计算窗口大小，用π估计来统计标签的数量，最后通过比较两个窗口的观察值或者估计的标签数量来自适应的调整窗口大小。Shin[2]等在分析不同窗口下阅读器的功能，利用采用加权平均法来自适应动态调整平滑窗口，开发了一个智能RFID中间件系统。Liu[3]等针对大规模冗余RFID数据，提出了结合欧氏距离和自适应滑动窗口的RFID数据清洗方法，大规模减少RFID多读现象。Zhang[4]等给出了误读和漏读的两个应用场景的数学模型，并针对这两种应用模型分别提出了改进的自适应平滑和贝叶斯方法。Gonzalez[5]等考虑不同RFID数据清洗方法的成本，提出一种RFID数据清洗策略，针对不同的应用场景，综合考虑所有清洗方法的效率采用相应的清洗方法组合。秦鹏飞[6]等认为要实现对动态标签的有效清洗，需要摆脱滑动窗口清洗模式，并提出了一种基于虚拟空间粒度的清洗方法，根据不同阅读读取的实时观测数据，利用虚拟空间粒度矩阵的表示求解方法，实现虚拟空间粒度动态自适应调整。

现有国内外研究成果主要适合RFID标签固定运动的场景，难以适用于离散制造过程中标签频繁移动的应用场景，本文针对离散制造过程中RFID数据的特点，研究了基于时间和基于时间间隔的布鲁姆滤波方法，在低内存空间下实现了时间效率的大幅度提高，保障RFID数据上层应用的实时性。因此，本文探索和研究航天产品智能制造数据处理及应用方面具有较高的工程价值和一定的学术价值。

1 应用场景分析

离散制造企业生产过程，制造资源（比如托盘、小车、原材料、工人等）都将被贴上RFID标签（或者条码），从而使得它们在制造过程中成为能够实时感知外界动态变化的智能对象。但是，RFID技术在带来好处的同时也产生一个新的问题。一方面，由于RFID标签被读取时候不存在交流，只要在读写器的可读区域内既可以被读取，因此RFID标签在某个区域缓慢移动或者保持静止时，将产生大量冗余数据；另一方面，对于快速移动的标签，常常在同一检测区域布置多个读写器来保证RFID标签的读取的准确率，多个读写器读取一个标签也将产生一定的冗余数据。

图1 应用场景

RFID读写器产生的原始数据流经过服务器中的过滤模块进行冗余清洗后发送给应用程序，RFID数据格式包括EPC编码、RFID读写器的位置和读取时间，本文定义RFID数据如下：

定义1：RFID数据流S是一个集合{s1,s2,…,sn}，Si是一个三元组（TagID,Loc,Time），其中“TagID”是电子产品（EPC）编码表示每一个实体对象的唯一代码；“Loc”监测到标签的读写器位置；“Time”监测到标签的时间。

如果RFID数据流中存在数据x（≠y）满足x.TagID且x.Time-y.Time＜τ，其中τ为根据系统应用程序所设置的时间间隔值，则认为RFID数据x重复冗余数据。但是制造过程中经常一种情况，在小于或者等于τ的时间内具有相同TagID的数据将被重复读取（比如某个加工区域的加工件上的标签数据在一段时间内会被读写器重复读取），此时发现没有重复冗余的RFID数据流就比较困难了。例如，存在RFID数据流S=(s1,s2,s3)，其中s1=(tag1,locl,5)，s2=(tag1,locl,10)，s3=(tag1,locl,5)，τ=8。有以上判断方法可知，相对s1，s2是重复数据；相对s2，s3是重复数据。但是实际情况，数据流S按时间序列到达服务器，s2到达服务器时判断是重复数据将被删除，s3到达服务器时，由于s2已经被删除且τ=8，此时会判断s3为非重复数据。冗余数据判断还需要依据不同的应用程序需求。在上述情况下，本文认为非重复数据流S={s1}而不是S={s1，s3}，因为在小于等于τ的时间采集同一ID的标签得到多个重复数据往往是没用的。

RFID重复冗余数据额定义如下：

定义2：对于RFID数据流S中的数据x和y，如果存在z∈S，同时满足x.TagID=y.TagID，z.TagID=x.TagID，|x.Time-z.Time|≤τ且|z.Time-y.Time|≤τ，称数据x和y在数据流S中是相关的。如果x和z在数据流S相关，z和y在数据流S相关，也称x和y是相关的。

这里定义数据的“相关”性是为了能够有效去除一个标签在小于等于τ的时间内被多次读取所产生的重复冗余数据，如果RFID的元素具有相同的ID和时间，将后者视为重复冗余数据，在定义2的基础上，对RFID重复冗余数据进行定义如下：

定义3：对于RFID数据流S中的元素x，如果存在任意一个y（≠x）∈S，满足x.TagID=y.TagID且x.Time-y.Time≤τ或者x和y是相关且y.Time≤x.Time。

移除RFID重复数据的数据流S称之为非重复RFID数据流，同时将非重复RFID数据流视为无重复最大集合，关于无重复集合和无反复最大集合的定义如下：

定义4：在集合S′(⊂S)中，x是集合S中的一个重复元素，如果不存在x∈S′，称S′是S中为无重复集合。

定义5：在集合S′(⊂S)中，x是集合S中的一个重复元素，如果S'是S中的无重复集合，且对于任意x∈S'-S，不存在x∈S'，称S'是S中为最大无重复集合。

为了保证数据处理的实时性，想要在一个较小的内存里获取最大无重复数据集是比较困难的。由于在很多应用场合中允许数据清洗出现一定错误，所以本文设计一个既可以满足实时性又能达到错误率要求的基于时间Bloom Filter的RFID重复数据清洗方法。因此，将问题模型描述为：在给定的内存空间m情况下，从RFID海量数据流S中发现无重复数据集，满足为最小（其中S′为集合S中的最大无重复数据集）。

2 基于时间的布鲁姆滤波

布鲁姆滤波算法是一种时间和空间效率极高的海量数据处理工具，被广泛的应用于大数据的查询和过滤，如BigTable、Hbase和Hadoop等[8]。其主要思想是通过使用位数组的方式来表示一个集合，并利用构建的函数映射来对元素进行识别和查询或过滤。初始状态时，布鲁姆滤波是一个具有m个位数均为0的位数组。如图2所示，假设存在一个包含n个元素的集合S={x1，x2，…，xn}，布鲁姆滤波将集合中的每一个元素经过k个哈希函数（相互独立）映射到用0和1表示的m个二进制位数组。例如集合中元素x1，经过3个哈希函数hi(x)映射，12位位组中第2、5、9个的位置将被置为1(1≤i≤k)；集合中元素x2，经过3个哈希函数hi(x)映射，12位位组中第5、7、11个的位置将被置为1。

图2 元素x的映射

当有新的元素y进入时，需要对y是否属于这个集合进行判断。首先对元素y进行k次哈希函数映射，如果元素y映射后所对应的元组中所有的位置都是1(1≤i≤k)，则可以判定元素y属于该集合，否则认为集合中不存在元素y。如图3所示，元素y1不属于这个集，元素y2属于这个集合，因为元素y1映射后指向的位置不全为1，而元素y2映射后指向的位置全为1。

图3 元素y的映射

从定义3中可知，尽管RFID数据的TagID相同，单纯依靠时间x.Time来判断的RFID数据x有可能不是重复数据。因此，采用时间的信息来鉴别RFID重复数据。在一般的布鲁姆滤波中，每个数组单元将被置为0或者1，但是在基于时间信息的布鲁姆滤波中，每个数据单元将被置为检测到RFID数据的具体时间。换句话说，基于时间的Bloom Filters采用的整数数组而不是位数组。

基于时间的布鲁姆滤波的如图4所示。与传统的布鲁姆滤波类似，基于时间的布鲁姆使用k个独立的哈希函数(h1,h2,…,hk)映射到{1,2,…,m}的范围中，第i个单元格将被置为M[i]的值。为了能够是数组能够存储RFID数据，将h1(x.tagID)，…，hk(x.tagID)所得到的k个单元用来存放检测的RFID数据x的时间，如果这些单元已经被存放了之前的RFID数据的检测时间，那就需要用现在的时间值进行重写。

图4 基于时间的布鲁姆滤波

为了判断RFID数据x是否为重复数据，对h1(x.tagID)，…，hk(x.tagID)所映射的k单元序号存放的数组进行判断，如果x.Time-M[hi(x.TagID)]＞τ，可以判断RFID数据x不是重复数据。基于时间的布鲁姆滤波可以在很少的内存空间内求得非重复数据集，具体算法如图5所示。首先初始化，将基于时间的Bloom Filters的单元数值置为0；其次，对于第一组数据进入基于时间的Bloom Filters，将时间值存放到(h1,h2,…,hk)映k个哈希函数所映射的k单元序号对应的数组中；最后，如果判断x为重复数据，删除数据x；否则，将数据x传至应用程序，将x.Time存入

3 基于时间间隔的布鲁姆滤波

上节介绍了基于时间的布鲁姆滤波适合简单的应用场景，当检测区域具有多个不同的TagID的时候，极易出现误判。例如，某个检测区域某段时间内产生RFID数据流{(ID1,Loc1,10)，(ID1,Loc1,11)，(ID2,Loc2,14)，(ID3,Loc3,15)，(ID2,Loc4,17)，(ID2,Loc2,18)}。设置数组大小为8，哈希函数个数k=3，时间阈值为=100。其中h1(ID1)=h2(ID4)，h1(ID2)=h1(ID4)，and h3(ID3)=h3(ID4)。如图5所示，当(ID4,Loc4,20)通过基于时间间隔的布鲁姆滤波时，根据的判别方法可知20-M[h1(ID4)]≤此时可判定读取到的ID4数据为重复数据，但是实际上是第一次读取到ID4数据。

图5 基于时间的布鲁姆滤波的实例

在制造物联中，不管是仓储还是制造过程，在检测区域内的某段时间内RFID数据将被大量重复读取，RFID重复数据往往具有地域和时间集中特点；同时，在可检测区域产生的可被检测的TagID种类较多。因此，可以将相同TagID的标签被读取的时间范围看成为短时间间隔，基于时间间隔布鲁姆滤波的进行RFID数据的清洗。

如图6所示，基于时间间隔的布鲁姆滤波中第i个数据单元中分别存放着起止时间M[i].StartTime和终止时间M[i].EndTime，初值为0。当RFID数据x（TagID=1）经过基于时间间隔的布鲁姆滤波的时候，将x.Time值存放在TagID=1所映射的数组单元值，最初的时间间隔只是一个时间点。当RFID数据y（TagID=1）到达基于时间间隔的布鲁姆滤波时，只是用y.Time覆盖TagID=1所映射的数组单元中的EndTime值。因此，基于时间间隔的Bloom Filters保持的是相同的标签的时间间隔。对于RFID数据x，当X.Time-EndTime≥且X.Time-时，时间间隔是无用的，应该将StartTime和EndTime重置为x.Time。

图6 基于时间间隔的布鲁姆滤波的原理

由于一个数组可能被不同TagID的RFID数据所重置，所以每个TagID的时间间隔可能是混淆的。然而，时间间隔[StartTime，EndTime]包括了所有RFID数据的检测时间，所以为了能够判断RFID是否为重复数据，可以检查hk(x.TagID)，…，hk(x.TagID)所映射的k单元中存放的时间间隔的交集是否为空集。当TagID=x.TagID的RFID数据进入服务器的时候，所有跟x.TagID有关的时间间隔都应该包括数据的检测时间，时间间隔的交集不应该为空集。因此，当时间间隔的交集为空集的时，就可以确定TagID=x.TagID的RFID数据在时间内没有经过布鲁姆滤波。图5说明了如何判断RFID数据x是一个重复数据，如图7(a)所示，四个时间间隔的交集为[10,15]，可以判定x为重复数据；如图7(b)所示，时间间隔为空集，可以判定数据x不是重复数据。

图7 基于时间间隔的布鲁姆滤波的实例

图7中的例子采用基于时间的布鲁姆滤波，极易造成误判。采用基于时间间隔的布鲁姆滤波进行实例说明。如图7所示，当(ID4, Loc4, 20)通过基于时间间隔的布鲁姆滤波时，ID4所对应的三个时间间隔的交集为空集，因此可以判定ID4不是重复数据。

4 应用实例

本文应用.NET平台的C#语言，在Visual Studio2010环境下将SQL Server 2000作为系统数据库，初步开发了RFID数据清洗系统。该系统在中国航天某总装厂车间得到初步应用实施，并实现了与该厂数据管理系统的初步集成。在应用实施过程中，首先依照EPC Global标准对专用生产设备、原材料、零部件等物品的标识数据格式和存储方式进行分类定义，并根据各种类型物品状态记录持续性的要求，确定标识的存储容量和读写方式，为了可以更加具体的评价数据清洗的效果，在噪声环境下对1000个询问周期进行清洗算法数据错误率（其值等于错误值/真实值）的验证，获取1×107、2×107、3×107、4×107、5×107、6×107六组数据进行分析，经过清洗后，对原始数据以及经过不同种清洗方法处理后数据的错误率比较如图8、图9所示。

实验分析结果可知：在单标签情况下，如图8所示，基于时间的布鲁姆滤波和基于时间间隔的布鲁姆滤波清洗效果差不多，后者效果稍微理想一点；在多标签的情况下，如图9所示，基于时间间隔的布鲁姆滤波的

【】【】清洗效果明显要理想与基于时间的布鲁姆滤波。在这两种情况下的一般的布鲁姆滤波清洗效果均不理想。

图8 单标签情况下多种清洗方法效果比较

图9 多标签情况下多种清洗方法效果比较

5 结束语

本文针对离散制造生产过程中RFID数据的特点，面向单标签和多标签的应用场景，分别研究了基于时间和基于时间间隔的布鲁姆滤波方法，在低内存空间下大幅度提高时间效率，很好的保障了RFID数据上层应用的实时性。本文提出的RFID数据方法为目前智能制造数据处理提供了一种新的思路。数据处理是智能制造智能化应用的基础，如何从智能制造产生的海量RFID数据中进一步挖掘出有用的数据，将是未来研究的一种重点。

[1]Massawe L.V., Kinyua J.D., Vermaak H.. Reducing False Negative Reads in Rfid Data Streams Using an Adaptive Slidingwindow Approach[J].Sensors,2012,12(4): 4187-4212.

[2]Shin D., Oh D., Ryu S., et al. A Smoothing Data Cleaning Based on Adaptive Window Sliding for Intelligent Rfid Middleware Systems[J]. Intelligent Information Research,2014,20(3):1-18.

[3]Liu L., Yuan Z., Liu X., et al. Rfid Unreliable Data Filtering By Integrating Adaptive Sliding Window and Euclidean Distance[J].Advances in Manufacturing,2014,2(2):121-129.

[4]Zhang C., Li Y., Chen Y.. Application oriented data cleaning For RFID middleware[J].IEEE International Conference on Systems,Man, & Cybernetics,2011,10(1):1544-1549.

[5]Gonzalez H., Han J.,Shen X.. Cost-Conscious Cleaning of Massive RFID Data Sets[A].Data Engineering. icde[C].IEEE International Conference on. IEEE, 2007:1268-1272.

[6]秦鹏飞.基于虚拟空间粒度的RFID数据清洗方法[D].辽宁:辽宁大学,2009.

[8]Xiulong Liu, Heng Qi, Keqiu Li. Sampling Bloom Filter-Based Detection of Unknown RFID Tags[J].IEEE Transactions on Communications,63(4):1432-1442.