面向離散制造的RFID數(shù)據(jù)清洗方法研究

余 杰，王 睿

（中國航天系統(tǒng)科學(xué)與工程研究院，北京 100048）

0 概述

RFID（Radio Frequency Identification）技術(shù)（射頻識別）是一種無需建立機(jī)械或光學(xué)聯(lián)系的非接觸式自動識別技術(shù)，通過無線電訊信號自動識別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù)信息。在離散制造，RFID感知涉及“人”、“機(jī)”、“料”、“環(huán)”等繁雜對象，RFID標(biāo)簽的智能對象將被制造過程各環(huán)節(jié)的讀寫器反復(fù)讀取，快速自動產(chǎn)生海量的數(shù)據(jù)流，產(chǎn)生數(shù)據(jù)量非常龐大，形成大量冗余數(shù)據(jù)。制約RFID技術(shù)在制造業(yè)中進(jìn)一步發(fā)展的一個關(guān)鍵因素就是獲取到的RFID數(shù)據(jù)呈現(xiàn)出很強(qiáng)的不可靠性，為了提供高質(zhì)量的RFID數(shù)據(jù)使其能夠真正被企業(yè)所應(yīng)用，亟需對RFID原始數(shù)據(jù)進(jìn)行恰當(dāng)?shù)那逑础２煌膽?yīng)用領(lǐng)域選擇的清洗策略也應(yīng)該不同，國內(nèi)外各領(lǐng)域?qū)FID的數(shù)據(jù)清洗已經(jīng)做了一定的深入研究，也取得了一定的進(jìn)展。在實(shí)際工程應(yīng)用中，通常在讀寫器和應(yīng)用程序之間部署中間件系統(tǒng)進(jìn)行RFID數(shù)據(jù)清洗。在這些中間件系統(tǒng)中，一種典型的數(shù)據(jù)清洗機(jī)制就是平滑過濾，在RFID數(shù)據(jù)流中利用滑動窗口，對時間窗口的每個標(biāo)簽按照一定規(guī)則進(jìn)行插補(bǔ)。Massawe[1]等研究一個更加有效的轉(zhuǎn)換檢測機(jī)制，在基于統(tǒng)計平滑窗口技術(shù)（SMURF）的基礎(chǔ)上，提出了一種自適應(yīng)清洗方案（WSTD），利用二項(xiàng)抽樣概念來計算窗口大小，用π估計來統(tǒng)計標(biāo)簽的數(shù)量，最后通過比較兩個窗口的觀察值或者估計的標(biāo)簽數(shù)量來自適應(yīng)的調(diào)整窗口大小。Shin[2]等在分析不同窗口下閱讀器的功能，利用采用加權(quán)平均法來自適應(yīng)動態(tài)調(diào)整平滑窗口，開發(fā)了一個智能RFID中間件系統(tǒng)。Liu[3]等針對大規(guī)模冗余RFID數(shù)據(jù)，提出了結(jié)合歐氏距離和自適應(yīng)滑動窗口的RFID數(shù)據(jù)清洗方法，大規(guī)模減少RFID多讀現(xiàn)象。Zhang[4]等給出了誤讀和漏讀的兩個應(yīng)用場景的數(shù)學(xué)模型，并針對這兩種應(yīng)用模型分別提出了改進(jìn)的自適應(yīng)平滑和貝葉斯方法。Gonzalez[5]等考慮不同RFID數(shù)據(jù)清洗方法的成本，提出一種RFID數(shù)據(jù)清洗策略，針對不同的應(yīng)用場景，綜合考慮所有清洗方法的效率采用相應(yīng)的清洗方法組合。秦鵬飛[6]等認(rèn)為要實(shí)現(xiàn)對動態(tài)標(biāo)簽的有效清洗，需要擺脫滑動窗口清洗模式，并提出了一種基于虛擬空間粒度的清洗方法，根據(jù)不同閱讀讀取的實(shí)時觀測數(shù)據(jù)，利用虛擬空間粒度矩陣的表示求解方法，實(shí)現(xiàn)虛擬空間粒度動態(tài)自適應(yīng)調(diào)整。

現(xiàn)有國內(nèi)外研究成果主要適合RFID標(biāo)簽固定運(yùn)動的場景，難以適用于離散制造過程中標(biāo)簽頻繁移動的應(yīng)用場景，本文針對離散制造過程中RFID數(shù)據(jù)的特點(diǎn)，研究了基于時間和基于時間間隔的布魯姆濾波方法，在低內(nèi)存空間下實(shí)現(xiàn)了時間效率的大幅度提高，保障RFID數(shù)據(jù)上層應(yīng)用的實(shí)時性。因此，本文探索和研究航天產(chǎn)品智能制造數(shù)據(jù)處理及應(yīng)用方面具有較高的工程價值和一定的學(xué)術(shù)價值。

1 應(yīng)用場景分析

離散制造企業(yè)生產(chǎn)過程，制造資源（比如托盤、小車、原材料、工人等）都將被貼上RFID標(biāo)簽（或者條碼），從而使得它們在制造過程中成為能夠?qū)崟r感知外界動態(tài)變化的智能對象。但是，RFID技術(shù)在帶來好處的同時也產(chǎn)生一個新的問題。一方面，由于RFID標(biāo)簽被讀取時候不存在交流，只要在讀寫器的可讀區(qū)域內(nèi)既可以被讀取，因此RFID標(biāo)簽在某個區(qū)域緩慢移動或者保持靜止時，將產(chǎn)生大量冗余數(shù)據(jù)；另一方面，對于快速移動的標(biāo)簽，常常在同一檢測區(qū)域布置多個讀寫器來保證RFID標(biāo)簽的讀取的準(zhǔn)確率，多個讀寫器讀取一個標(biāo)簽也將產(chǎn)生一定的冗余數(shù)據(jù)。

圖1 應(yīng)用場景

RFID讀寫器產(chǎn)生的原始數(shù)據(jù)流經(jīng)過服務(wù)器中的過濾模塊進(jìn)行冗余清洗后發(fā)送給應(yīng)用程序，RFID數(shù)據(jù)格式包括EPC編碼、RFID讀寫器的位置和讀取時間，本文定義RFID數(shù)據(jù)如下：

定義1：RFID數(shù)據(jù)流S是一個集合{s1,s2,…,sn}，Si是一個三元組（TagID,Loc,Time），其中“TagID”是電子產(chǎn)品（EPC）編碼表示每一個實(shí)體對象的唯一代碼；“Loc”監(jiān)測到標(biāo)簽的讀寫器位置；“Time”監(jiān)測到標(biāo)簽的時間。

如果RFID數(shù)據(jù)流中存在數(shù)據(jù)x（≠y）滿足x.TagID且x.Time-y.Time＜τ，其中τ為根據(jù)系統(tǒng)應(yīng)用程序所設(shè)置的時間間隔值，則認(rèn)為RFID數(shù)據(jù)x重復(fù)冗余數(shù)據(jù)。但是制造過程中經(jīng)常一種情況，在小于或者等于τ的時間內(nèi)具有相同TagID的數(shù)據(jù)將被重復(fù)讀取（比如某個加工區(qū)域的加工件上的標(biāo)簽數(shù)據(jù)在一段時間內(nèi)會被讀寫器重復(fù)讀取），此時發(fā)現(xiàn)沒有重復(fù)冗余的RFID數(shù)據(jù)流就比較困難了。例如，存在RFID數(shù)據(jù)流S=(s1,s2,s3)，其中s1=(tag1,locl,5)，s2=(tag1,locl,10)，s3=(tag1,locl,5)，τ=8。有以上判斷方法可知，相對s1，s2是重復(fù)數(shù)據(jù)；相對s2，s3是重復(fù)數(shù)據(jù)。但是實(shí)際情況，數(shù)據(jù)流S按時間序列到達(dá)服務(wù)器，s2到達(dá)服務(wù)器時判斷是重復(fù)數(shù)據(jù)將被刪除，s3到達(dá)服務(wù)器時，由于s2已經(jīng)被刪除且τ=8，此時會判斷s3為非重復(fù)數(shù)據(jù)。冗余數(shù)據(jù)判斷還需要依據(jù)不同的應(yīng)用程序需求。在上述情況下，本文認(rèn)為非重復(fù)數(shù)據(jù)流S={s1}而不是S={s1，s3}，因?yàn)樵谛∮诘扔讦拥臅r間采集同一ID的標(biāo)簽得到多個重復(fù)數(shù)據(jù)往往是沒用的。

RFID重復(fù)冗余數(shù)據(jù)額定義如下：

定義2：對于RFID數(shù)據(jù)流S中的數(shù)據(jù)x和y，如果存在z∈S，同時滿足x.TagID=y.TagID，z.TagID=x.TagID，|x.Time-z.Time|≤τ且|z.Time-y.Time|≤τ，稱數(shù)據(jù)x和y在數(shù)據(jù)流S中是相關(guān)的。如果x和z在數(shù)據(jù)流S相關(guān)，z和y在數(shù)據(jù)流S相關(guān)，也稱x和y是相關(guān)的。

這里定義數(shù)據(jù)的“相關(guān)”性是為了能夠有效去除一個標(biāo)簽在小于等于τ的時間內(nèi)被多次讀取所產(chǎn)生的重復(fù)冗余數(shù)據(jù)，如果RFID的元素具有相同的ID和時間，將后者視為重復(fù)冗余數(shù)據(jù)，在定義2的基礎(chǔ)上，對RFID重復(fù)冗余數(shù)據(jù)進(jìn)行定義如下：

定義3：對于RFID數(shù)據(jù)流S中的元素x，如果存在任意一個y（≠x）∈S，滿足x.TagID=y.TagID且x.Time-y.Time≤τ或者x和y是相關(guān)且y.Time≤x.Time。

移除RFID重復(fù)數(shù)據(jù)的數(shù)據(jù)流S稱之為非重復(fù)RFID數(shù)據(jù)流，同時將非重復(fù)RFID數(shù)據(jù)流視為無重復(fù)最大集合，關(guān)于無重復(fù)集合和無反復(fù)最大集合的定義如下：

定義4：在集合S′(?S)中，x是集合S中的一個重復(fù)元素，如果不存在x∈S′，稱S′是S中為無重復(fù)集合。

定義5：在集合S′(?S)中，x是集合S中的一個重復(fù)元素，如果S'是S中的無重復(fù)集合，且對于任意x∈S'-S，不存在x∈S'，稱S'是S中為最大無重復(fù)集合。

為了保證數(shù)據(jù)處理的實(shí)時性，想要在一個較小的內(nèi)存里獲取最大無重復(fù)數(shù)據(jù)集是比較困難的。由于在很多應(yīng)用場合中允許數(shù)據(jù)清洗出現(xiàn)一定錯誤，所以本文設(shè)計一個既可以滿足實(shí)時性又能達(dá)到錯誤率要求的基于時間Bloom Filter的RFID重復(fù)數(shù)據(jù)清洗方法。因此，將問題模型描述為：在給定的內(nèi)存空間m情況下，從RFID海量數(shù)據(jù)流S中發(fā)現(xiàn)無重復(fù)數(shù)據(jù)集，滿足為最小（其中S′為集合S中的最大無重復(fù)數(shù)據(jù)集）。

2 基于時間的布魯姆濾波

布魯姆濾波算法是一種時間和空間效率極高的海量數(shù)據(jù)處理工具，被廣泛的應(yīng)用于大數(shù)據(jù)的查詢和過濾，如BigTable、Hbase和Hadoop等[8]。其主要思想是通過使用位數(shù)組的方式來表示一個集合，并利用構(gòu)建的函數(shù)映射來對元素進(jìn)行識別和查詢或過濾。初始狀態(tài)時，布魯姆濾波是一個具有m個位數(shù)均為0的位數(shù)組。如圖2所示，假設(shè)存在一個包含n個元素的集合S={x1，x2，…，xn}，布魯姆濾波將集合中的每一個元素經(jīng)過k個哈希函數(shù)（相互獨(dú)立）映射到用0和1表示的m個二進(jìn)制位數(shù)組。例如集合中元素x1，經(jīng)過3個哈希函數(shù)hi(x)映射，12位位組中第2、5、9個的位置將被置為1(1≤i≤k)；集合中元素x2，經(jīng)過3個哈希函數(shù)hi(x)映射，12位位組中第5、7、11個的位置將被置為1。

圖2 元素x的映射

當(dāng)有新的元素y進(jìn)入時，需要對y是否屬于這個集合進(jìn)行判斷。首先對元素y進(jìn)行k次哈希函數(shù)映射，如果元素y映射后所對應(yīng)的元組中所有的位置都是1(1≤i≤k)，則可以判定元素y屬于該集合，否則認(rèn)為集合中不存在元素y。如圖3所示，元素y1不屬于這個集，元素y2屬于這個集合，因?yàn)樵貀1映射后指向的位置不全為1，而元素y2映射后指向的位置全為1。

圖3 元素y的映射

從定義3中可知，盡管RFID數(shù)據(jù)的TagID相同，單純依靠時間x.Time來判斷的RFID數(shù)據(jù)x有可能不是重復(fù)數(shù)據(jù)。因此，采用時間的信息來鑒別RFID重復(fù)數(shù)據(jù)。在一般的布魯姆濾波中，每個數(shù)組單元將被置為0或者1，但是在基于時間信息的布魯姆濾波中，每個數(shù)據(jù)單元將被置為檢測到RFID數(shù)據(jù)的具體時間。換句話說，基于時間的Bloom Filters采用的整數(shù)數(shù)組而不是位數(shù)組。

基于時間的布魯姆濾波的如圖4所示。與傳統(tǒng)的布魯姆濾波類似，基于時間的布魯姆使用k個獨(dú)立的哈希函數(shù)(h1,h2,…,hk)映射到{1,2,…,m}的范圍中，第i個單元格將被置為M[i]的值。為了能夠是數(shù)組能夠存儲RFID數(shù)據(jù)，將h1(x.tagID)，…，hk(x.tagID)所得到的k個單元用來存放檢測的RFID數(shù)據(jù)x的時間，如果這些單元已經(jīng)被存放了之前的RFID數(shù)據(jù)的檢測時間，那就需要用現(xiàn)在的時間值進(jìn)行重寫。

圖4 基于時間的布魯姆濾波

為了判斷RFID數(shù)據(jù)x是否為重復(fù)數(shù)據(jù)，對h1(x.tagID)，…，hk(x.tagID)所映射的k單元序號存放的數(shù)組進(jìn)行判斷，如果x.Time-M[hi(x.TagID)]＞τ，可以判斷RFID數(shù)據(jù)x不是重復(fù)數(shù)據(jù)。基于時間的布魯姆濾波可以在很少的內(nèi)存空間內(nèi)求得非重復(fù)數(shù)據(jù)集，具體算法如圖5所示。首先初始化，將基于時間的Bloom Filters的單元數(shù)值置為0；其次，對于第一組數(shù)據(jù)進(jìn)入基于時間的Bloom Filters，將時間值存放到(h1,h2,…,hk)映k個哈希函數(shù)所映射的k單元序號對應(yīng)的數(shù)組中；最后，如果判斷x為重復(fù)數(shù)據(jù)，刪除數(shù)據(jù)x；否則，將數(shù)據(jù)x傳至應(yīng)用程序，將x.Time存入

3 基于時間間隔的布魯姆濾波

上節(jié)介紹了基于時間的布魯姆濾波適合簡單的應(yīng)用場景，當(dāng)檢測區(qū)域具有多個不同的TagID的時候，極易出現(xiàn)誤判。例如，某個檢測區(qū)域某段時間內(nèi)產(chǎn)生RFID數(shù)據(jù)流{(ID1,Loc1,10)，(ID1,Loc1,11)，(ID2,Loc2,14)，(ID3,Loc3,15)，(ID2,Loc4,17)，(ID2,Loc2,18)}。設(shè)置數(shù)組大小為8，哈希函數(shù)個數(shù)k=3，時間閾值為=100。其中h1(ID1)=h2(ID4)，h1(ID2)=h1(ID4)，and h3(ID3)=h3(ID4)。如圖5所示，當(dāng)(ID4,Loc4,20)通過基于時間間隔的布魯姆濾波時，根據(jù)的判別方法可知20-M[h1(ID4)]≤此時可判定讀取到的ID4數(shù)據(jù)為重復(fù)數(shù)據(jù)，但是實(shí)際上是第一次讀取到ID4數(shù)據(jù)。

圖5 基于時間的布魯姆濾波的實(shí)例

在制造物聯(lián)中，不管是倉儲還是制造過程，在檢測區(qū)域內(nèi)的某段時間內(nèi)RFID數(shù)據(jù)將被大量重復(fù)讀取，RFID重復(fù)數(shù)據(jù)往往具有地域和時間集中特點(diǎn)；同時，在可檢測區(qū)域產(chǎn)生的可被檢測的TagID種類較多。因此，可以將相同TagID的標(biāo)簽被讀取的時間范圍看成為短時間間隔，基于時間間隔布魯姆濾波的進(jìn)行RFID數(shù)據(jù)的清洗。

如圖6所示，基于時間間隔的布魯姆濾波中第i個數(shù)據(jù)單元中分別存放著起止時間M[i].StartTime和終止時間M[i].EndTime，初值為0。當(dāng)RFID數(shù)據(jù)x（TagID=1）經(jīng)過基于時間間隔的布魯姆濾波的時候，將x.Time值存放在TagID=1所映射的數(shù)組單元值，最初的時間間隔只是一個時間點(diǎn)。當(dāng)RFID數(shù)據(jù)y（TagID=1）到達(dá)基于時間間隔的布魯姆濾波時，只是用y.Time覆蓋TagID=1所映射的數(shù)組單元中的EndTime值。因此，基于時間間隔的Bloom Filters保持的是相同的標(biāo)簽的時間間隔。對于RFID數(shù)據(jù)x，當(dāng)X.Time-EndTime≥且X.Time-時，時間間隔是無用的，應(yīng)該將StartTime和EndTime重置為x.Time。

圖6 基于時間間隔的布魯姆濾波的原理

由于一個數(shù)組可能被不同TagID的RFID數(shù)據(jù)所重置，所以每個TagID的時間間隔可能是混淆的。然而，時間間隔[StartTime，EndTime]包括了所有RFID數(shù)據(jù)的檢測時間，所以為了能夠判斷RFID是否為重復(fù)數(shù)據(jù)，可以檢查hk(x.TagID)，…，hk(x.TagID)所映射的k單元中存放的時間間隔的交集是否為空集。當(dāng)TagID=x.TagID的RFID數(shù)據(jù)進(jìn)入服務(wù)器的時候，所有跟x.TagID有關(guān)的時間間隔都應(yīng)該包括數(shù)據(jù)的檢測時間，時間間隔的交集不應(yīng)該為空集。因此，當(dāng)時間間隔的交集為空集的時，就可以確定TagID=x.TagID的RFID數(shù)據(jù)在時間內(nèi)沒有經(jīng)過布魯姆濾波。圖5說明了如何判斷RFID數(shù)據(jù)x是一個重復(fù)數(shù)據(jù)，如圖7(a)所示，四個時間間隔的交集為[10,15]，可以判定x為重復(fù)數(shù)據(jù)；如圖7(b)所示，時間間隔為空集，可以判定數(shù)據(jù)x不是重復(fù)數(shù)據(jù)。

圖7 基于時間間隔的布魯姆濾波的實(shí)例

圖7中的例子采用基于時間的布魯姆濾波，極易造成誤判。采用基于時間間隔的布魯姆濾波進(jìn)行實(shí)例說明。如圖7所示，當(dāng)(ID4, Loc4, 20)通過基于時間間隔的布魯姆濾波時，ID4所對應(yīng)的三個時間間隔的交集為空集，因此可以判定ID4不是重復(fù)數(shù)據(jù)。

4 應(yīng)用實(shí)例

本文應(yīng)用.NET平臺的C#語言，在Visual Studio2010環(huán)境下將SQL Server 2000作為系統(tǒng)數(shù)據(jù)庫，初步開發(fā)了RFID數(shù)據(jù)清洗系統(tǒng)。該系統(tǒng)在中國航天某總裝廠車間得到初步應(yīng)用實(shí)施，并實(shí)現(xiàn)了與該廠數(shù)據(jù)管理系統(tǒng)的初步集成。在應(yīng)用實(shí)施過程中，首先依照EPC Global標(biāo)準(zhǔn)對專用生產(chǎn)設(shè)備、原材料、零部件等物品的標(biāo)識數(shù)據(jù)格式和存儲方式進(jìn)行分類定義，并根據(jù)各種類型物品狀態(tài)記錄持續(xù)性的要求，確定標(biāo)識的存儲容量和讀寫方式，為了可以更加具體的評價數(shù)據(jù)清洗的效果，在噪聲環(huán)境下對1000個詢問周期進(jìn)行清洗算法數(shù)據(jù)錯誤率（其值等于錯誤值/真實(shí)值）的驗(yàn)證，獲取1×107、2×107、3×107、4×107、5×107、6×107六組數(shù)據(jù)進(jìn)行分析，經(jīng)過清洗后，對原始數(shù)據(jù)以及經(jīng)過不同種清洗方法處理后數(shù)據(jù)的錯誤率比較如圖8、圖9所示。

實(shí)驗(yàn)分析結(jié)果可知：在單標(biāo)簽情況下，如圖8所示，基于時間的布魯姆濾波和基于時間間隔的布魯姆濾波清洗效果差不多，后者效果稍微理想一點(diǎn)；在多標(biāo)簽的情況下，如圖9所示，基于時間間隔的布魯姆濾波的

【】【】清洗效果明顯要理想與基于時間的布魯姆濾波。在這兩種情況下的一般的布魯姆濾波清洗效果均不理想。

圖8 單標(biāo)簽情況下多種清洗方法效果比較

圖9 多標(biāo)簽情況下多種清洗方法效果比較

5 結(jié)束語

本文針對離散制造生產(chǎn)過程中RFID數(shù)據(jù)的特點(diǎn)，面向單標(biāo)簽和多標(biāo)簽的應(yīng)用場景，分別研究了基于時間和基于時間間隔的布魯姆濾波方法，在低內(nèi)存空間下大幅度提高時間效率，很好的保障了RFID數(shù)據(jù)上層應(yīng)用的實(shí)時性。本文提出的RFID數(shù)據(jù)方法為目前智能制造數(shù)據(jù)處理提供了一種新的思路。數(shù)據(jù)處理是智能制造智能化應(yīng)用的基礎(chǔ)，如何從智能制造產(chǎn)生的海量RFID數(shù)據(jù)中進(jìn)一步挖掘出有用的數(shù)據(jù)，將是未來研究的一種重點(diǎn)。

[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數(shù)據(jù)清洗方法[D].遼寧:遼寧大學(xué),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.