基于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)資助 。