惠霓 周俊 吳銳 廖國瓊

江西財(cái)經(jīng)大學(xué)信息管理學(xué)院

基于Bloom過濾器的RFID數(shù)據(jù)流濾重策略分析

惠霓 周俊 吳銳 廖國瓊

江西財(cái)經(jīng)大學(xué)信息管理學(xué)院

隨著現(xiàn)代通信技術(shù)的快速發(fā)展，RFID技術(shù)已廣泛應(yīng)用于物流、供應(yīng)鏈、圖書館、交通運(yùn)輸?shù)榷鄠€(gè)領(lǐng)域。但是，由于標(biāo)簽在某位置停留較長時(shí)間或經(jīng)過多個(gè)讀寫器的重疊探測區(qū)域等原因，導(dǎo)致RFID系統(tǒng)會(huì)產(chǎn)生大量冗余數(shù)據(jù)。為了提高RFID應(yīng)用的處理效率及減少資源消耗，需對(duì)這些冗余數(shù)據(jù)進(jìn)行濾重處理。本文首先簡要介紹Bloom過濾器的濾重原理，然后，對(duì)基于Bloom過濾器的RFID數(shù)據(jù)流濾重策略進(jìn)行分析和比較，并指出該領(lǐng)域未來研究方向。

Bloom過濾器 RFID 數(shù)據(jù)流濾重

1 引言

無線射頻識(shí)別技術(shù)（radio frequency identification, RFID）是20世紀(jì)90年代開始興起的一種非接觸式識(shí)別技術(shù)。該技術(shù)憑借標(biāo)簽體積小、成本低、無需接觸、多目標(biāo)同時(shí)識(shí)別等特征，已廣泛應(yīng)用在物流與供應(yīng)鏈、圖書管理、交通等領(lǐng)域。然而，由于標(biāo)簽在某位置停留時(shí)間較長或多閱讀器監(jiān)控重疊區(qū)域等原因，導(dǎo)致RFID系統(tǒng)可能會(huì)產(chǎn)生大量冗余數(shù)據(jù)，即重復(fù)出現(xiàn)但不會(huì)給系統(tǒng)帶來有價(jià)值信息的數(shù)據(jù)。如果不對(duì)這些冗余數(shù)據(jù)進(jìn)行濾重處理，則會(huì)浪費(fèi)系統(tǒng)資源和降低系統(tǒng)處理效率。因此，開展RFID冗余數(shù)據(jù)濾重策略研究對(duì)提高RFID系統(tǒng)的可用性具有重要意義。

RFID冗余數(shù)據(jù)過濾是最早是采用硬件方法，如冗余閱讀器消除方法(Redundant Reader Elimination，RRE)，分層消除優(yōu)化方法(Layered Elimination Optimization, LEO)等。但是由于硬件方法的成本較高，基于Bloom過濾器的RFID數(shù)據(jù)過濾策略近年來得到重視。Bloom過濾器是Burton Bloom于70年代提出的一種近似濾重策略，它具有無需存儲(chǔ)實(shí)際數(shù)據(jù)，占用存儲(chǔ)空間少，元素更新及查詢時(shí)間不隨數(shù)據(jù)量大小變化而變化等優(yōu)點(diǎn)。雖然Bloom過濾器可能導(dǎo)致假陽性（False Positive）錯(cuò)誤，但在誤差容忍范圍內(nèi)仍然具有重要實(shí)用價(jià)值。

2 Bloom過濾器原理

標(biāo)準(zhǔn)Bloom過濾器（bloom filter, BF）是采用具有m位的位數(shù)組表示數(shù)據(jù)集合。當(dāng)需存儲(chǔ)具有n個(gè)元素的集合S={x1, x2,…,xn}時(shí)，元素本身不會(huì)存儲(chǔ)到過濾器中，而是通過使用k個(gè)互相獨(dú)立的哈希函數(shù)，將集合中的每個(gè)元素映射到位數(shù)組中。

初始時(shí)，全部位數(shù)組的初始狀態(tài)都置為0。對(duì)任意一個(gè)元素x?S，若被第i(1≤i≤k)個(gè)哈希函數(shù)映射的位置hi(x)，則將其值置為1。如圖1所示，設(shè)m=10，k=2，元素x1和x2分別映射到單元1和4、5和 9，則相應(yīng)位都置為1。

布隆過濾器濾重原理為：若一個(gè)元素經(jīng)過k個(gè)哈希函數(shù)映射，全部對(duì)應(yīng)單元的值都為1，則x為冗余數(shù)據(jù)，進(jìn)行濾重處理；否則，x為非冗余數(shù)據(jù)。

由于標(biāo)準(zhǔn)布隆過濾器是用有限的位數(shù)表示無限的對(duì)象，故可能出現(xiàn)假陽性錯(cuò)誤，即將非冗余數(shù)據(jù)判斷為冗余數(shù)據(jù)。在圖1中，元素y被映射到第1和第5號(hào)單元，分別與元素x1、x2的一個(gè)單元重疊。由于這兩個(gè)單元的值都為1，故y判斷為冗余數(shù)據(jù)，出現(xiàn)了誤判。

圖1 BF原理及假陽性錯(cuò)誤示例

由于Bloom Filter具有哈希查找時(shí)間固定且能較大程度節(jié)省存儲(chǔ)空間等優(yōu)點(diǎn)，因此在數(shù)據(jù)濾重方面得到了廣泛應(yīng)用。

3 基于Bloom過濾器的RFID數(shù)據(jù)流濾重策略分析

與其它來源數(shù)據(jù)不同，RFID數(shù)據(jù)流具有以下特征：

①流特性。來自閱讀器的數(shù)據(jù)通常是按一定閱讀周期以數(shù)據(jù)流方式持續(xù)不斷到達(dá)系統(tǒng)。顯然，傳統(tǒng)“先存儲(chǔ)后判斷”濾重策略已不能有效應(yīng)用于RFID數(shù)據(jù)的濾重處理；

②海量性。RFID系統(tǒng)產(chǎn)生的數(shù)據(jù)量非常龐大，在一些應(yīng)用系統(tǒng)中，每天產(chǎn)生的數(shù)據(jù)量通常達(dá)到GB以上級(jí)別，很容易導(dǎo)致過濾器單元空間變“滿”；

③位置移動(dòng)性。標(biāo)簽對(duì)象的位置可能隨時(shí)發(fā)生變化。如果一個(gè)標(biāo)簽對(duì)象在較近時(shí)間內(nèi)被不同閱讀器探測到，則不能判斷為冗余數(shù)據(jù)。

因此，對(duì)RFID數(shù)據(jù)進(jìn)行濾重處理不能簡單根據(jù)標(biāo)簽對(duì)象是否重復(fù)出現(xiàn)，而應(yīng)綜合考慮上述特征。

3.1 面向一般數(shù)據(jù)流的Bloom過濾器

在數(shù)據(jù)流應(yīng)用中，Bloom過濾器所分配的空間遠(yuǎn)小于流的大小。當(dāng)越來越多的元素到達(dá)后，Bloom過濾器中零的位數(shù)不斷下降，假陽性率會(huì)不斷增加。當(dāng)每一位都被置為1時(shí)（變“滿”），每一個(gè)元素都將被報(bào)告為重復(fù)元素，導(dǎo)致BF失效。因此,需要在錯(cuò)誤率達(dá)到自定義的閾值之前，刪除bloom filter 中的過期元素。主要有以下方法：

文獻(xiàn)[4]提出了一種衰減布隆過濾器(Decaying Bloom Filter，DBF)。每當(dāng)插入一個(gè)新數(shù)據(jù)時(shí)，需掃描過濾器的所有非零單元，并將其值減1。由于每插入一個(gè)新數(shù)據(jù)都需遍歷所有單元，故算法效率不高。文獻(xiàn)[5]提出一種穩(wěn)定布隆過濾器(Stable Bloom Filter, SBF)，隨機(jī)選擇一定數(shù)量的單元進(jìn)行過期元素刪除。該過濾器的優(yōu)點(diǎn)是使用固定空間，假陽性率可以控制在常數(shù)范圍內(nèi)，但其除了存在假陽性錯(cuò)誤之外，還存在假陰性錯(cuò)誤，而參數(shù)設(shè)置復(fù)雜。為較好解決過期元素刪除問題，考慮到新到達(dá)的元素比舊元素重要，文獻(xiàn)[6]提出了一種時(shí)間衰減布隆過濾器（Time-Decaying Bloom Filter，TDBF），利用時(shí)間衰減函數(shù)動(dòng)態(tài)維護(hù)元素權(quán)值，保證元素重要性隨時(shí)間流逝逐漸降低?？紤]對(duì)象的價(jià)值不同，文獻(xiàn)[7]提出了一種按需時(shí)間衰減布隆過濾器（On-demand Time-decaying Bloom Filter,On-demand TDBF）。每當(dāng)新元素到達(dá)滑動(dòng)窗口，通過時(shí)間衰減函數(shù)計(jì)算其在窗口內(nèi)的價(jià)值。該方法在TDBF的基礎(chǔ)上增加了對(duì)元素權(quán)重的考慮。考慮數(shù)據(jù)的不確定性，文獻(xiàn)[8]提出了一種浮點(diǎn)計(jì)數(shù)Bloom過濾器（Floating Counter Bloom Filter，F(xiàn)CBF），用概率值代替計(jì)數(shù)Bloom過濾器中的整數(shù)，并給出了概率更新策略。但是，為保證正確消除過期元素的影響，該方法需要空間保存窗口中全部未過期的元素，這違背了Bloom過濾器無需保存元素值的初衷。

上述面向一般數(shù)據(jù)流的BF過濾器均未考慮RFID數(shù)據(jù)流的位置特性及移動(dòng)特性，故不能直接應(yīng)用于RFID數(shù)據(jù)流濾重。

3.2 面向RFID數(shù)據(jù)流的Bloom過濾器

近年來，基于Bloom過濾器的RFID濾重策略得到越來越多關(guān)注，主要有以下策略：

3.2.1 時(shí)間布隆過濾器

文獻(xiàn)[9]提出了一種時(shí)間布隆過濾器（Time Bloom Filters，TBF）。與傳統(tǒng)布隆過濾器不同，TBF將位數(shù)組改為整形數(shù)組，直接在過濾器單元中存儲(chǔ)探測時(shí)間(time)。當(dāng)需判斷探測數(shù)據(jù)是否為冗余數(shù)據(jù)時(shí)，算法將該數(shù)據(jù)的標(biāo)簽ID(TID)哈希到對(duì)應(yīng)的k個(gè)單元。如果存在至少一個(gè)單元中的時(shí)間與數(shù)據(jù)的探測時(shí)間之差超過閾值t，則認(rèn)為該數(shù)據(jù)為非冗余數(shù)據(jù)；否則判斷為冗余數(shù)據(jù)。為了解決時(shí)間變長導(dǎo)致過濾器存儲(chǔ)空間變大的問題，文獻(xiàn)[9]進(jìn)一步提出了一種時(shí)間間隔布隆過濾器（Time Interval Bloom Filter，TIBF），在每個(gè)單元存儲(chǔ)標(biāo)簽對(duì)象的開始時(shí)間與結(jié)束時(shí)間之差，即時(shí)間間隔。在判斷冗余時(shí)，需檢查到達(dá)數(shù)據(jù)的探測時(shí)間與所對(duì)應(yīng)的全部k個(gè)單元中時(shí)間間隔的交叉域是否為空。若為空，則新到達(dá)數(shù)據(jù)判斷為非冗余數(shù)據(jù)。

TBF和TIBF都是由標(biāo)準(zhǔn)布隆過濾器改進(jìn)而來的，它們通過時(shí)間更新保證過濾器中的元組不會(huì)存滿，可以過濾時(shí)間冗余。但是它們只適用于多個(gè)閱讀器檢測同一區(qū)域內(nèi)靜態(tài)標(biāo)簽的情形(如倉庫管理)，而不能應(yīng)用于對(duì)象位置發(fā)生變化的動(dòng)態(tài)情形(如智能超市)。而且，它們沒有考慮數(shù)據(jù)流的窗口概念，在數(shù)據(jù)量比較小時(shí)尚可應(yīng)對(duì)，當(dāng)數(shù)據(jù)量變得很大時(shí)就難以處理，不能有效應(yīng)用于具有大量RFID對(duì)象的真實(shí)應(yīng)用環(huán)境。

3.2.2 時(shí)空布隆過濾器（Time-Space Bloom Filter，TSBF）

在一些應(yīng)用中，如智能超市，標(biāo)簽對(duì)象的位置隨時(shí)可能發(fā)生變化。因此在進(jìn)行數(shù)據(jù)過濾時(shí)，除了考慮數(shù)據(jù)的時(shí)間特征之外，還應(yīng)考慮數(shù)據(jù)的位置特征，即閱讀器信息。文獻(xiàn)[10]提出了一種時(shí)空布隆過濾器（TSBF）。TSBF每個(gè)單元表示為一個(gè)二維整型數(shù)組，第一列存儲(chǔ)觀測值的閱讀器ID(RID, 記錄標(biāo)簽的位置信息)，第二列存儲(chǔ)觀測時(shí)間信息(time)。過濾器的第i個(gè)單元的值可表示為Mi[RID][time]。當(dāng)有新數(shù)據(jù)x到達(dá)時(shí)，對(duì)標(biāo)簽ID進(jìn)行k次哈希，同時(shí)使用存儲(chǔ)在k個(gè)單元中的RID和時(shí)間信息進(jìn)行判斷是否冗余。設(shè)w為滑動(dòng)窗口大小，冗余判斷原理為：若存在一個(gè)存儲(chǔ)單元i，滿足Mi[time]=0，或者x.RID!=Mi[RID]，或者x.time-Mi[time]>w，則x不是冗余數(shù)據(jù)，否則，x為冗余數(shù)據(jù)。

TSBF可很好地解決多個(gè)閱讀器探測范圍不重疊情形下的時(shí)間冗余及位置發(fā)生變化時(shí)的濾重問題，但其不能應(yīng)用于閱讀器探測范圍重疊的情形。

3.2.3 兩階段過濾（Two-phase Filtering,TPF）框架

為了解決閱讀器探測區(qū)域重疊的問題。文獻(xiàn)[11]中提出了一種兩階段過濾（Two-phase Filtering,TPF）框架，即當(dāng)閱讀器讀取到標(biāo)簽數(shù)據(jù)后，首先在閱讀器上進(jìn)行本地過濾，將關(guān)于相同標(biāo)簽的數(shù)據(jù)進(jìn)行時(shí)間冗余過濾，然后將本地過濾后的數(shù)據(jù)發(fā)給服務(wù)器，由中間件進(jìn)行全局過濾，將來自不同閱讀器關(guān)于相同標(biāo)簽的數(shù)據(jù)進(jìn)行空間冗余過濾。在本地過濾時(shí)，對(duì)新到達(dá)數(shù)據(jù)的TID進(jìn)行哈希，如果映射到的單元中有一個(gè)的count為0，則不為冗余數(shù)據(jù)，并將該位置的count值加1，如果全部單元的count都不為0，則判斷為冗余數(shù)據(jù)。在全局過濾時(shí)，對(duì)新到達(dá)數(shù)據(jù)的TID進(jìn)行哈希，如果映射到的單元中有一個(gè)的time為0，則不為冗余信息。如果time不為0，則判斷數(shù)據(jù)的探測時(shí)間是否小于過濾器中保存的時(shí)間。若是，則為冗余數(shù)據(jù)，反之不為冗余數(shù)據(jù)。

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

為支持閱讀器探測區(qū)域重疊及節(jié)省過濾器存儲(chǔ)空間，文獻(xiàn)[12]提出了一種副本濾重哈希模型（Duplicate Filter Hash，DFH）。

DFH由兩個(gè)數(shù)組構(gòu)成，在一個(gè)閱讀周期內(nèi)，對(duì)于每個(gè)新到的元素x用一個(gè)哈希函數(shù)進(jìn)行哈希處理，哈希到的位置h(x)存儲(chǔ)元素標(biāo)簽TID，如果第一個(gè)數(shù)組Arry1[h(x)]=0，則將Arry1[h(x)]置為x的TID，否則，如果第二個(gè)數(shù)組Arry2[h(x)]=0， 則 將Arry2[h(x)值 置 為x的TID。 若Arry1h(x)]和Arry2[h(x)]均不為0，則發(fā)生假陽性錯(cuò)誤。

DFH過濾器使用兩個(gè)數(shù)組進(jìn)行冗余數(shù)據(jù)判斷，處理效率較高。但每個(gè)數(shù)據(jù)只對(duì)應(yīng)過濾器數(shù)組中的一位，假陽性率較高。

4 全文總結(jié)

由于RFID數(shù)據(jù)具有流特性、海量性和位置移動(dòng)性等特征，傳統(tǒng)“先存儲(chǔ)后判斷”濾重策略和一般數(shù)據(jù)流濾重策略已不能直接應(yīng)用于RFID數(shù)據(jù)流濾重。本文對(duì)Bloom過濾器的RFID數(shù)據(jù)流濾重原理進(jìn)行了介紹、分析和比較。可以看出，已有RFID數(shù)據(jù)流濾重策略能夠在一定程度解決時(shí)間冗余和空間冗余，并且考慮了位置移動(dòng)及多個(gè)探測器區(qū)域重疊等情形，有效地提高了RFID系統(tǒng)效率。但是，由于RFID技術(shù)易受外界環(huán)境的干擾，存在漏讀、多讀和錯(cuò)讀現(xiàn)象，導(dǎo)致RFID數(shù)據(jù)具有不確定性。因此，針對(duì)RFID不確定RFID數(shù)據(jù)流的濾重策略將是將來研究方向之一。另外，由于RFID應(yīng)用場景較為復(fù)雜，差異較大，因此，針對(duì)不同應(yīng)用場景研究特殊的RFID數(shù)據(jù)濾重策略也將得到關(guān)注。

[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]吳銳. 基于滑動(dòng)窗口的 RFID 冗余數(shù)據(jù)濾重研究[D]. 江西財(cái)經(jīng)大學(xué), 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

本文受國家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目、江西省自然科學(xué)基金項(xiàng)目(20151122040083)資助 。