面向離散制造的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.