基于Bloom过滤器的RFID数据流滤重策略分析

惠霓 周俊 吴锐 廖国琼

江西财经大学信息管理学院

基于Bloom过滤器的RFID数据流滤重策略分析

惠霓 周俊 吴锐 廖国琼

江西财经大学信息管理学院

随着现代通信技术的快速发展，RFID技术已广泛应用于物流、供应链、图书馆、交通运输等多个领域。但是，由于标签在某位置停留较长时间或经过多个读写器的重叠探测区域等原因，导致RFID系统会产生大量冗余数据。为了提高RFID应用的处理效率及减少资源消耗，需对这些冗余数据进行滤重处理。本文首先简要介绍Bloom过滤器的滤重原理，然后，对基于Bloom过滤器的RFID数据流滤重策略进行分析和比较，并指出该领域未来研究方向。

Bloom过滤器 RFID 数据流滤重

1 引言

无线射频识别技术（radio frequency identification, RFID）是20世纪90年代开始兴起的一种非接触式识别技术。该技术凭借标签体积小、成本低、无需接触、多目标同时识别等特征，已广泛应用在物流与供应链、图书管理、交通等领域。然而，由于标签在某位置停留时间较长或多阅读器监控重叠区域等原因，导致RFID系统可能会产生大量冗余数据，即重复出现但不会给系统带来有价值信息的数据。如果不对这些冗余数据进行滤重处理，则会浪费系统资源和降低系统处理效率。因此，开展RFID冗余数据滤重策略研究对提高RFID系统的可用性具有重要意义。

RFID冗余数据过滤是最早是采用硬件方法，如冗余阅读器消除方法(Redundant Reader Elimination，RRE)，分层消除优化方法(Layered Elimination Optimization, LEO)等。但是由于硬件方法的成本较高，基于Bloom过滤器的RFID数据过滤策略近年来得到重视。Bloom过滤器是Burton Bloom于70年代提出的一种近似滤重策略，它具有无需存储实际数据，占用存储空间少，元素更新及查询时间不随数据量大小变化而变化等优点。虽然Bloom过滤器可能导致假阳性（False Positive）错误，但在误差容忍范围内仍然具有重要实用价值。

2 Bloom过滤器原理

标准Bloom过滤器（bloom filter, BF）是采用具有m位的位数组表示数据集合。当需存储具有n个元素的集合S={x1, x2,…,xn}时，元素本身不会存储到过滤器中，而是通过使用k个互相独立的哈希函数，将集合中的每个元素映射到位数组中。

初始时，全部位数组的初始状态都置为0。对任意一个元素xÎS，若被第i(1≤i≤k)个哈希函数映射的位置hi(x)，则将其值置为1。如图1所示，设m=10，k=2，元素x1和x2分别映射到单元1和4、5和 9，则相应位都置为1。

布隆过滤器滤重原理为：若一个元素经过k个哈希函数映射，全部对应单元的值都为1，则x为冗余数据，进行滤重处理；否则，x为非冗余数据。

由于标准布隆过滤器是用有限的位数表示无限的对象，故可能出现假阳性错误，即将非冗余数据判断为冗余数据。在图1中，元素y被映射到第1和第5号单元，分别与元素x1、x2的一个单元重叠。由于这两个单元的值都为1，故y判断为冗余数据，出现了误判。

图1 BF原理及假阳性错误示例

由于Bloom Filter具有哈希查找时间固定且能较大程度节省存储空间等优点，因此在数据滤重方面得到了广泛应用。

3 基于Bloom过滤器的RFID数据流滤重策略分析

与其它来源数据不同，RFID数据流具有以下特征：

①流特性。来自阅读器的数据通常是按一定阅读周期以数据流方式持续不断到达系统。显然，传统“先存储后判断”滤重策略已不能有效应用于RFID数据的滤重处理；

②海量性。RFID系统产生的数据量非常庞大，在一些应用系统中，每天产生的数据量通常达到GB以上级别，很容易导致过滤器单元空间变“满”；

③位置移动性。标签对象的位置可能随时发生变化。如果一个标签对象在较近时间内被不同阅读器探测到，则不能判断为冗余数据。

因此，对RFID数据进行滤重处理不能简单根据标签对象是否重复出现，而应综合考虑上述特征。

3.1 面向一般数据流的Bloom过滤器

在数据流应用中，Bloom过滤器所分配的空间远小于流的大小。当越来越多的元素到达后，Bloom过滤器中零的位数不断下降，假阳性率会不断增加。当每一位都被置为1时（变“满”），每一个元素都将被报告为重复元素，导致BF失效。因此,需要在错误率达到自定义的阈值之前，删除bloom filter 中的过期元素。主要有以下方法：

文献[4]提出了一种衰减布隆过滤器(Decaying Bloom Filter，DBF)。每当插入一个新数据时，需扫描过滤器的所有非零单元，并将其值减1。由于每插入一个新数据都需遍历所有单元，故算法效率不高。文献[5]提出一种稳定布隆过滤器(Stable Bloom Filter, SBF)，随机选择一定数量的单元进行过期元素删除。该过滤器的优点是使用固定空间，假阳性率可以控制在常数范围内，但其除了存在假阳性错误之外，还存在假阴性错误，而参数设置复杂。为较好解决过期元素删除问题，考虑到新到达的元素比旧元素重要，文献[6]提出了一种时间衰减布隆过滤器（Time-Decaying Bloom Filter，TDBF），利用时间衰减函数动态维护元素权值，保证元素重要性随时间流逝逐渐降低。考虑对象的价值不同，文献[7]提出了一种按需时间衰减布隆过滤器（On-demand Time-decaying Bloom Filter,On-demand TDBF）。每当新元素到达滑动窗口，通过时间衰减函数计算其在窗口内的价值。该方法在TDBF的基础上增加了对元素权重的考虑。考虑数据的不确定性，文献[8]提出了一种浮点计数Bloom过滤器（Floating Counter Bloom Filter，FCBF），用概率值代替计数Bloom过滤器中的整数，并给出了概率更新策略。但是，为保证正确消除过期元素的影响，该方法需要空间保存窗口中全部未过期的元素，这违背了Bloom过滤器无需保存元素值的初衷。

上述面向一般数据流的BF过滤器均未考虑RFID数据流的位置特性及移动特性，故不能直接应用于RFID数据流滤重。

3.2 面向RFID数据流的Bloom过滤器

近年来，基于Bloom过滤器的RFID滤重策略得到越来越多关注，主要有以下策略：

3.2.1 时间布隆过滤器

文献[9]提出了一种时间布隆过滤器（Time Bloom Filters，TBF）。与传统布隆过滤器不同，TBF将位数组改为整形数组，直接在过滤器单元中存储探测时间(time)。当需判断探测数据是否为冗余数据时，算法将该数据的标签ID(TID)哈希到对应的k个单元。如果存在至少一个单元中的时间与数据的探测时间之差超过阈值t，则认为该数据为非冗余数据；否则判断为冗余数据。为了解决时间变长导致过滤器存储空间变大的问题，文献[9]进一步提出了一种时间间隔布隆过滤器（Time Interval Bloom Filter，TIBF），在每个单元存储标签对象的开始时间与结束时间之差，即时间间隔。在判断冗余时，需检查到达数据的探测时间与所对应的全部k个单元中时间间隔的交叉域是否为空。若为空，则新到达数据判断为非冗余数据。

TBF和TIBF都是由标准布隆过滤器改进而来的，它们通过时间更新保证过滤器中的元组不会存满，可以过滤时间冗余。但是它们只适用于多个阅读器检测同一区域内静态标签的情形(如仓库管理)，而不能应用于对象位置发生变化的动态情形(如智能超市)。而且，它们没有考虑数据流的窗口概念，在数据量比较小时尚可应对，当数据量变得很大时就难以处理，不能有效应用于具有大量RFID对象的真实应用环境。

3.2.2 时空布隆过滤器（Time-Space Bloom Filter，TSBF）

在一些应用中，如智能超市，标签对象的位置随时可能发生变化。因此在进行数据过滤时，除了考虑数据的时间特征之外，还应考虑数据的位置特征，即阅读器信息。文献[10]提出了一种时空布隆过滤器（TSBF）。TSBF每个单元表示为一个二维整型数组，第一列存储观测值的阅读器ID(RID, 记录标签的位置信息)，第二列存储观测时间信息(time)。过滤器的第i个单元的值可表示为Mi[RID][time]。当有新数据x到达时，对标签ID进行k次哈希，同时使用存储在k个单元中的RID和时间信息进行判断是否冗余。设w为滑动窗口大小，冗余判断原理为：若存在一个存储单元i，满足Mi[time]=0，或者x.RID!=Mi[RID]，或者x.time-Mi[time]>w，则x不是冗余数据，否则，x为冗余数据。

TSBF可很好地解决多个阅读器探测范围不重叠情形下的时间冗余及位置发生变化时的滤重问题，但其不能应用于阅读器探测范围重叠的情形。

3.2.3 两阶段过滤（Two-phase Filtering,TPF）框架

为了解决阅读器探测区域重叠的问题。文献[11]中提出了一种两阶段过滤（Two-phase Filtering,TPF）框架，即当阅读器读取到标签数据后，首先在阅读器上进行本地过滤，将关于相同标签的数据进行时间冗余过滤，然后将本地过滤后的数据发给服务器，由中间件进行全局过滤，将来自不同阅读器关于相同标签的数据进行空间冗余过滤。在本地过滤时，对新到达数据的TID进行哈希，如果映射到的单元中有一个的count为0，则不为冗余数据，并将该位置的count值加1，如果全部单元的count都不为0，则判断为冗余数据。在全局过滤时，对新到达数据的TID进行哈希，如果映射到的单元中有一个的time为0，则不为冗余信息。如果time不为0，则判断数据的探测时间是否小于过滤器中保存的时间。若是，则为冗余数据，反之不为冗余数据。

3.2.4 副本滤重哈希模型（Duplicate Filter Hash，DFH）

为支持阅读器探测区域重叠及节省过滤器存储空间，文献[12]提出了一种副本滤重哈希模型（Duplicate Filter Hash，DFH）。

DFH由两个数组构成，在一个阅读周期内，对于每个新到的元素x用一个哈希函数进行哈希处理，哈希到的位置h(x)存储元素标签TID，如果第一个数组Arry1[h(x)]=0，则将Arry1[h(x)]置为x的TID，否则，如果第二个数组Arry2[h(x)]=0， 则 将Arry2[h(x)值 置 为x的TID。 若Arry1h(x)]和Arry2[h(x)]均不为0，则发生假阳性错误。

DFH过滤器使用两个数组进行冗余数据判断，处理效率较高。但每个数据只对应过滤器数组中的一位，假阳性率较高。

4 全文总结

由于RFID数据具有流特性、海量性和位置移动性等特征，传统“先存储后判断”滤重策略和一般数据流滤重策略已不能直接应用于RFID数据流滤重。本文对Bloom过滤器的RFID数据流滤重原理进行了介绍、分析和比较。可以看出，已有RFID数据流滤重策略能够在一定程度解决时间冗余和空间冗余，并且考虑了位置移动及多个探测器区域重叠等情形，有效地提高了RFID系统效率。但是，由于RFID技术易受外界环境的干扰，存在漏读、多读和错读现象，导致RFID数据具有不确定性。因此，针对RFID不确定RFID数据流的滤重策略将是将来研究方向之一。另外，由于RFID应用场景较为复杂，差异较大，因此，针对不同应用场景研究特殊的RFID数据滤重策略也将得到关注。

[1]Carbunar B, Ramanathan M K, Koyuturk M, et al. Redundant-reader elimination in RFID systems. in: Proceedings of the 2nd Communications Society Conference

on Sensor and Ad Hoc Communications and Networks. Santa Clara, USA. 2005. 176~184

[2]Hsu C H, Chen Y M, Yang C T. A layered optimization approach for redundant reader elimination in wireless rfid networks[C] // Proceedings of the 2nd IEEE International Conference on Asia-Pacific Service Computing Conference, 2007, 138-145

[3]Bloom B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426

[4]Wang X, Shen H. Notice of Retraction Improved Decaying Bloom Filter for duplicate detection in data streams over sliding windows[C] //Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology, 2010, 348-353

[5]Deng F, Rafiei D. Approximately detecting duplicates for streaming data using stable bloom filters[C]// Proceedings of the ACM SIGMOD International Conference on Management of data, 2006: 25-36

[6]Cheng K, Xiang L, Iwaihara M. Time-decaying bloom filters for data streams with skewed distributions[C] // Proceedings of 5th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications, 2005, 63-69

[7]Bianchi G, D’Heureuse N, and Niccolini S. Ondemand time-decaying bloom filters for telemarketer detection. ACM SIGCOMM Computer Communication Review, 2011, 41(5): 5-12

[8]Wang X, Shen H. Approximately detecting duplicates for probabilistic data streams over sliding windows[C]// Proceedings of the 3rd IEEE International Conference on Parallel Architectures, Algorithms and Programming, 2010, 263-268

[9]Lee C H, Chung C W. An approximate duplicate elimination in RFID data streams[J]. Data & Knowledge Engineering, 2011, 70(12): 1070-1087

[10]Liao Guoqiong, Wu Rui, Di Guoqiang, etc. Approximate filtering of redundant RFID data streams in mobile environment. Technique Gazette, 2016, 23(2): 415-423

[11]吴锐. 基于滑动窗口的 RFID 冗余数据滤重研究[D]. 江西财经大学, 2014

[12]Kamaludin H, Mahdin H, Abawajy J. H. Filtering Redundant Data from RFID Data Streams[J]. Journal of Sensors, 2016, 2016(1):1-7

本文受国家级大学生创新创业训练计划项目、江西省自然科学基金项目(20151122040083)资助 。