RFID數據清洗算法概述?

張　燕，湯一彬，李旭斐

（河海大學物聯網工程學院，常州213022）

RFID數據清洗算法概述?

張燕，湯一彬，李旭斐

（河海大學物聯網工程學院，常州213022）

RFID技術作為當前與物聯網領域相關的一個熱門技術，具有廣闊的應用前景，但因其獲取數據過程中產生的不可靠數據極大地限制了RFID技術的發展，因此對于RFID數據進行清洗是非常必要的。對RFID數據清洗方法進行綜合敘述，主要介紹了國內外針對RFID中單個閱讀器數據獲取中產生不可靠的數據清洗解決算法，分析了各種方法的基本原理，討論了目前企業對于數據不可靠提出的數據清洗應用解決方案。分析表明當前的數據清洗算法主要針對單一問題設計，計算效率不高，尚不適合各種RFID應用場景，未來RFID技術的發展趨勢應該向普適性、高效性發展。

RFID技術；物聯網；不可靠；數據清洗；解決方案；普適性

1　引　言

無線射頻識別（RFID）系統使用無線射頻技術在開放系統環境中進行對象識別，并且能夠快速、準確、實時地采集和處理數據信息。這種識別的優點之一是無需物理接觸或其它任何可見的接觸。RFID技術在生活中應用非常廣泛，例如，它可以用于生產和銷售管理場合以簡化供應鏈管理并實現對存貨成本的有效控制；可以代替傳統的二維條形碼用于數字圖書館管理；可用于動物研究和飼養中的動物識別；可用于防偽造的電子護照系統；甚至可以用于構建智能無線傳感器網絡環境等等。

然而，由于受到各種環境和射頻技術本身一些特點的影響，RFID閱讀器識別標簽時會出現各種錯誤識別現象包括：積極讀、消極讀、數據冗余等，這些因素都會制約RFID技術的進一步發展。為有效支持RFID高層業務邏輯處理，提供高質量的RFID數據，對RFID數據進行清洗是非常必要的。

國外大學和研究機構對RFID閱讀器識別標簽出現錯誤數據的現象已經進行了多年的探索并取得了一些成果。加州大學洛杉磯分校（UCLA）提出了通過使用時間滑動窗口技術清洗RFID原始標簽數據流的方法［1］。加州大學伯克力（UC Berkeley）針對時間平滑處理窗口大小設置困難的問題，提出了一種基于概率論知識動態改變窗口大小的方法——自適應改變滑動窗口大小的數據清洗算法（SMURF）［2］。日本九州大學（Kyushu University）提出了一種基于現實世界的約束關系來提高RFID數據的可靠性［3］。伊利諾伊大學厄巴納－尚佩恩分校提出了使用動態貝葉斯網絡（DBN）清洗原始標簽流的方法［4］。格里菲斯大學采用集合理論提出一種清洗策略［5］等等。

盡管用于數據清洗的技術已相對比較成熟，但是由于RFID閱讀器受多方面因素的影響，閱讀器對標簽數據識別的正確率仍只有60%－70%左右。如何使RFID數據傳輸更加高效可靠也是一個挑戰。下面將詳細介紹這些數據清洗算法，并分析這些算法的優缺點。

2　RFID數據清洗需要解決的問題

在RFID系統中，RFID數據管理是RFID應用的重要部分。由于各類物理的和信號傳輸方面的原因，比如電源失效、電磁干擾、網絡傳輸中斷以及RFID電子標簽低功耗和低成本的限制等，收集到的RFID數據往往不可靠［6－7］，這嚴重影響了RFID技術在各領域的應用（比如精確的庫存跟蹤，嚴格的病人監護等）。數據作為分析和應用的基礎，在實際應用中起到了至關重要的作用，一旦RFID獲取數據出現問題，會對相關企業和公司造成嚴重影響。例如：在基于RFID的物流系統中，RFID獲取的不可靠數據使得數據定位不準確；基于RFID的監控系統也部分失去了其價值；而在基于RFID的停車場收費系統中，對象的漏讀直接損失了停車場的經濟收益。同時，不可靠數據的存在也限制了基于RFID數據的分析、決策支持、知識發現等復雜應用。

在RFID閱讀器獲取數據的過程中，主要存在以下三種典型的數據讀取錯誤：

（1）消極讀

研究表明，在RFID項目系統中部署的閱讀器的讀取率（即閱讀器射頻范圍內電子標簽被實際讀取到的百分比）經常處于60%～70%的范圍，即超過30%的標簽被漏讀了［8－9］。造成這種情況的原因包括：當多個標簽被同時檢測到時，射頻碰撞發生以及信號互相干擾，阻止了閱讀器對標簽的識別；由于水或者金屬屏蔽和干擾射頻信號影響了標簽被檢測到。

（2）積極讀

這種錯誤又被稱為噪聲，在該情況下，除了讀取到原有的電子標簽，也可能讀取到一些額外的、并不期望的標簽數據。這歸因于以下幾個方面：在閱讀器正常射頻范圍之外的標簽被該閱讀器讀取到了，例如閱讀器被設置為從某一場景中讀取對象，它同時也可能從鄰近場景中讀取對象；閱讀器和環境的未知原因，例如某一個閱讀器周期性的發送錯誤ID。

（3）數據冗余

這種情況主要由以下幾個原因造成：標簽長期處于閱讀器射頻范圍之內在重復讀取模式下被閱讀器多次讀到；安裝了多個閱讀器覆蓋了大范圍的區域，處于重疊區域內的標簽被多個閱讀器讀取到；為了增強讀取的精確性，多個擁有相同EPC編碼的標簽被貼在同一物體上，產生了多個相同的讀取結果。

RFID數據與傳統關系數據庫和數據倉庫數據庫的數據相比，作為一種流數據，使得數據清洗［10］變得更加困難。①因為內存的限制，很多在靜態數據上有效的清洗算法對RFID數據不適用；②流的特質使得記錄表的范圍只限于局部，無法觀其全貌，這使得清洗結果的準確性更低；③因為應用的特點，必須在短時間內完成RFID數據的清洗工作，因此算法的時間要求更高。特別是當某個RFID應用布置規模極大時，如涉及到數千個閱讀器、數萬個標簽時，數據清洗的難度更大。

因此，系統中必須增加對RFID數據的預處理環節，使閱讀器讀取來的數據，無論從時間序列還是從數值上都盡可能的接近真實數據。數據清洗的目的是檢測數據中存在的錯誤和不一致，剔除或者改正它們，提高數據質量［8］。數據清洗的過程必須滿足如下幾個條件：不論是單數據源還是多數據源，都要檢測并且除去數據中所有明顯的錯誤和不一致；盡可能地減小人工干預和用戶的編程工作量，而且要容易擴展到其他數據源；應該和數據轉化相結合；要有相應的描述語言來指定數據轉化和數據清洗操作；所有這些操作應該在一個統一的框架下完成［11］。

3　RFID數據清洗算法

目前，針對RFID數據的不可靠性提出了許多數據清洗算法，算法主要在兩個方面展開：第一個方面是尋找高效的清洗模型和算法來解決單個閱讀器識別標簽的不可靠問題，該方面的研究對大多數RFID應用系統都具有一定的適用性；另一個方面是通過系統自身的獨特規則和閱讀器架構，從系統邏輯的角度來對數據進行清洗。采用第二種方法往往清洗效率很高，但清洗策略和具體應用相關，不具有普遍適用性。通過上述分析得出，進行數據清洗主要有三類數據清洗算法：一種是基于滑動窗口的數據清洗算法，一種是根據現實約束進行數據清洗，還有一種是優化方法獲得最小代價的值。

3.1基于定義滑動窗口的RFID數據清洗算法

滑動窗口是一種比較典型、常用的數據流清洗技術。加州大學洛杉磯分校（UCLA）的Bai等人提出一種基于滑動窗口的方法清洗RFID數據流。使用滑動窗口解決清洗輸出結果的順序問題，RFID的定長滑動窗口數據清洗技術示意圖如圖1所示。

圖1　定長滑動窗口數據清洗示意圖

定長滑動窗口清洗技術是指在對RFID數據流進行清洗時，窗口的長度始終都保持不動。定長滑動窗口方法的清洗原理：在原始數據流上使用大小固定的滑動窗口，在某一時刻，如果窗口捕獲到了某個數據，則這個數據會被認為一直存在于這個窗口中，并將這個數據輸出。隨著新數據的到來，窗口向前滑動，在窗口內存在的漏讀錯誤會被填補。

通過圖2可以看出，真實數據反映了這樣一種情況，標簽離開閱讀器的覆蓋區域之后經過一段時間又重新回到了閱讀器射頻范圍之內。由于環境變化和RFID本身非接觸式識別的技術特點，我們通過閱讀器收集上來的數據用原始數據來表示，數據流出現了很多中斷的地方，這就造成了數據漏讀的現象。

圖2　定長窗口引發的問題

根據圖2中第三部分和第四部分可以看出小窗口能夠彌補一些漏讀錯誤。但是由于窗口選擇過小，有些真正的漏讀情況并沒有被彌補掉，依然存在消極讀取的錯誤。而大窗口確實對漏讀進行了完全彌補，通過大窗口平滑之后所有的漏讀錯誤都解決了，但是，卻不能檢測到標簽離開閱讀器這個事件所引發的積極讀取錯誤。這樣由于窗口大小固定，導致窗口過大產生積極讀取錯誤，窗口過小產生消極讀取錯誤。由于窗口大小固定造成RFID不能根據數據特點進行精確填補漏讀的數據，最好的改進方法是通過自適應的改變窗口大小，這樣可以適應多變的環境。

3.2自適應窗口大小的RFID數據清洗算法

為避免定長滑動窗口帶來的問題，加州大學伯克力分校的Jeffery R等人針對RFID數據流所固有的不可靠性，針對定長滑動窗口的窗口大小不容易確定問題，提出了一種自適應改變滑動窗口大小的RFID數據清洗方法——SMURF。

SMURF方法的主要思想是采用統計采樣理論來自適應進行過濾。將RFID閱讀器捕獲的標簽數據當成是對探測器范圍內存在的標簽的一次抽樣，然后對RFID閱讀器捕獲的數據進行數學建模，根據建立起的數學模型，并結合探測到標簽的情況對窗口大小進行實時更新。SMURF策略采用兩個不同的概率模型來對探測范圍內不同的情況進行清洗：

（1）單個標簽數據清洗

利用標簽閱讀率決定滑動窗口的大小，若標簽的閱讀率較低則會賦予其大窗口以減少消極讀；反之，如果標簽的閱讀率較高，則賦予一個小窗口以減少積極讀。該方法通過定義窗口大小為wi，每個標簽被閱讀發生的概率為pi。將若干查詢周期組合成一個紀元，每個紀元內標簽的閱讀率pi與窗口大小wi符合二項式分布B（wi，pi），根據伯努利概率模型得到窗口的大小如下：

通過（1）式能夠以很高的概率保證其完整性，但同時可能導致丟失標簽的動態變化過程，方法用下式來保證探測標簽的動態變化。

（2）式表示在平滑窗口內檢測到標簽的次數，即數學期望與實際檢測數值之差的絕對值大于二倍標準差，此時適當減小其窗口。由此根據標簽的當前檢測信息，適應性的調整窗口大小，可以保證較完整的填充數據。

（2）多標簽集合清洗

多標簽數據清洗技術：與單標簽方法不同的是，其利用的概率模型是π－estimator，判斷標簽移動的條件是，其他的操作和單標簽數據清洗技術操作一樣。

SMURF方法與定長的滑動窗口方法相比，可以自適應改變窗口的長度，既能保證數據完整性又能保證及時捕獲標簽的狀態改變，可以很好的彌補由于窗口長度一定而不能夠同時滿足這兩要求不足。但是利用數學模型進行調整時，采用了平均概率，若數據速率波動大就不能反映某一時刻的數據特征，造成窗口調整錯誤，致使閱讀率陡然下降。SMURF方法反而增大窗口進行平滑，此時將產生更多積極讀取錯誤。

3.3基于約束的清洗算法

Kyushu University提出了一種基于現實世界的約束關系來提高RFID數據的可靠性［5］。它指出現實世界的約束主要有兩種，一種是Accompany Constraint（伴隨約束）另外一種是Route Constraint（路徑約束）。所謂伴隨約束是指系統明確知道一組物體同時運動，閱讀器只要檢測到部分物體就可以推知整個物體被檢測到。另外一種路徑約束是指系統已知物體會沿著特定的路徑運動。通過這兩種約束可以解決標簽漏讀問題。

本文提出的綜合清洗系統主要由兩個部分組成：冗余去除引擎和約束引擎，如圖3所示。冗余去除引擎主要是刪除原始RFID數據中的大量冗余數據，減少待清洗的RFID數據量。約束引擎主要是對去冗余之后還存在錯誤的RFID數據再次進行清洗，以保證最后輸出干凈的RFID數據流以供用戶后續的查詢工作。

圖3　綜合清洗系統框架圖

將原始的帶有冗余的RFID數據輸入冗余刪除引擎；經冗余刪除引擎處理后，得到去冗余后的RFID數據以進行下一步處理；將用戶指定約束及自學約束輸入約束引擎，維護約束引擎；用約束引擎清洗去冗余后的RFID數據；得到經約束清洗后干凈的RFID數據，并輸出給用戶以供上層應用。

冗余去除算法可將原來采集到的RFID數據量減少40%－50%，這將極大降低系統開銷，為后續的數據清洗工作提供便利。約束算法是在自學約束及用戶指定約束的指導下進行清洗的，考慮進了對象之間的聯系以及約束對數據對象的影響，其性能要優于在線清洗的五層管道框架系統算法。

3.4基于動態貝葉斯網絡（DBN）的清洗算法

由于SMURF方法只是根據觀測值改變滑動窗口的大小，同一窗口中數據具有相同權重的問題。伊利諾伊大學厄巴納－尚佩恩分校（University of Illinois at Urbana-Champaign）的Gonzalez H等人提出一種考慮代價的大量RFID數據集的清洗方法。該方法引入一個全新的清洗規則即最小化代價，提出一個清洗框架，來產生一個全局的最優清洗方案。提出了一種動態調節信任狀態的清洗新方法——基于動態貝葉斯網絡（DBN）的方法。

動態貝葉斯網絡主要思想是通過利用網絡結構以及條件概率表，獲得所要求事件的概率，并利用先驗知識和樣本數據獲得對未知樣本的估計。在RFID數據清洗方法中利用動態貝葉斯網絡是通過假設一個隱模式標簽來決定實際標簽位置，實際讀取可以觀察該隱模式加噪聲的情況，算法是通過歷史觀測數據對標簽進行預測并獲得一個概率值，以此概率值判斷標簽是否存在。

動態貝葉斯網絡中的模型具體實現是定義一個隱變量Xt，若標簽在時間t出現在閱讀器范圍內改制為真；另定義一個觀測變量et作為關于Xt的噪聲觀測量。通過e1：t＋1得出Xt＋1的可能狀態：

式（3）中P（et＋1｜Xt＋1）已知為真時，通過觀測可得概率P（Xt＋1｜xt）為一個真狀態轉換為另一個真狀態的概率，而P（Xt｜et＋1）為之前的信任狀態，觀測模型和轉換模型可從歷史數據得到，具體方法框圖如圖4所示。

圖4　DBN清洗方法框圖

與滑動窗口、SMURF等方法比較，貝葉斯網絡的優點在于結合觀察值和預測值的關系賦予新數據更高的權重，且不需要記載最新的標簽數據。然而從歷史數據集中得到預測值與觀察值的關系，不能動態更新，所以不能理想地清洗動態標簽，對于動態標簽的清洗效果不是十分理想。

4　RFID數據清洗應用解決方案

隨著對RFID項目的實施研究，發現通過RFID中間件可以將RFID數據正確導入相應的信息管理系統。國際上，比較知名的RFID中間件廠商提供了對于RFID數據清洗的應用方案，主要有IBM、SUN、Oracle等大型企業。

IBM基于Java語言并依照J2EE企業構架開發的RFID中間件產品可以簡化企業實施RFID項目的步驟，同時實現企業能夠處理海量貨物數據的目的。IBM的RFID中間件產品是開放式的，其RFID中間件架構［12］中的Edge Domain模塊的功能是管理RFID底層設備以及過濾、聚合和分發原始標簽數據。在整個RFID中間件系統中Filter Agent與數據處理相關，但只能實現冗余過濾和位過濾，不能針對漏讀、臟讀、冗余讀以及復雜時間清洗。

SUN的RFID中間件架構包括兩個部分，分別是Execution Agent和Control Station，但只有Execution Agent中的Filter組件和數據處理有關。最早提出用smooth、delta和bandpass等簡單過濾規則組件來過濾冗余讀、消極讀的是SUN公司，但增加過濾功能仍然需要特定組件，而且不存在完整的數據清理解決方案和靈活的復雜事件讀取引擎。

基于BEA的Web Logic Enterprise Server 9.2架構是Oracle／BEA聯合研發的RFID中間件架構［13］，其中的事件引擎位于事件服務架構中，是目前功能最完善的事件引擎。它使用Esper流事件處理引擎和EPL語言來監控實時標簽數據并生成具有邏輯業務含義的復雜事件。但建于關系代數模式之上的引擎不能順序讀取時序，同時RFID事件讀取中的時序讀取又非常關鍵，在這一點上它是不適用的，并且BEA的事件處理模塊對RFID數據中存在的問題也沒有提供合適的清洗方案。

5　結束語

RFID技術已被大多數人所熟知，其廣泛的應用場景，低廉的成本，部署實施的簡單性，已經越來越多地吸引著更多的用戶、研究人員和IT廠商。RFID技術作為無線射頻技術，技術特點決定了其數據流具有不可靠性的缺點，該缺點是限制RFID技術被廣泛應用的關鍵因素，該缺點造成了RFID技術在高水平的精確應用中應用價值不高的問題。為解決該問題，需要對原始數據進行清洗，以得到干凈的、可實際應用的數據流。通過詳細討論已有的RFID數據清洗算法，分析了這些算法中存在的缺陷。根據算法比較結果表明：目前尚不存在一個高效、實用、干凈的低成本RFID清洗算法。設計高效、實用、低成本的實用RFID清洗算法以及清洗策略依舊是一個值得挑戰的領域，尤其是對中間件研發使其具有高效的數據處理模式是一個值得開發的領域。

［1］Yijian Bai，Fusheng Wang，Peiya Liu.Efficiently filtering RFID data streams［C］.The first international VLDB Workshop on Clean Database（CleanDB）Workshop，Seoul，Kerea，2006：50－57.

［2］Shawn R.Jeffery，Minos Garofalakis，Michael J.Franklin，et al.Adaptive cleaning for RFID data streams［J］.Proceedings of the 32nd international conference on Very Large Data Bases（VLDB），Seoul，Korea，2006：163－174.

［3］Sozo Inoue，Daisuke Hagiwara，Hiroto Yasuura.Systematic Error detection for RFID reliability［C］.proceedings of the Frist International Conferece on Availability，Reliability and Secuity.2006.

［4］Hector Gonzalez，Jiawei Han，Xuehua Shen.Cost－conscious cleaning of massive RFID data sets［C］.Conferenece on DataEngineering（ICDE 07），Istanbul，Turkey.April 2007：1268－1272.

［5］Jeffery S R，Alonso G，Franklin M J，et al.A pipelined framework for online cleaning of sensor data streams［C］.Proceedings of the 22nd International Conference on Data Engineering，2006：140－153.

［6］許嘉，于戈，谷峪，等.RFID不確定數據管理技術［J］.計算機科學與探索，2009，3（6）：561－576.Xu Jia，Yu Yi，Gu Yu，et al.RFID data management Technology［J］.Computer Science and exploration 2009，3（6）：561－576.

［7］陳旭輝，王馨，柯銘.一種改進的基于RFID中間件的冗余數據清洗算法［J］.微電子學與計算機，2013，30（7）：154－158.Chen Xu_hui，Wang Xin，Ke Xin.An improved Redundancy Data Cleaning Alogorithm based on RFID Midsoftware［J］.Microelectronics and Computer，2013，30（7）：154－158.

［8］Popovski P，Fyhn K，Jacobsen R M，et al.Robust statistical methods for detection of missing RFID tags［J］.IEEE Wireless Communicationns，2011，18（4）：74－80.

［9］Wang F，Liu P.Temporal Management of RFID Data［C］.In：Proceedings of the 31st International Conference on Very Large Data Dases.Trondheim，Norway，2005：1128－1139.

［10］Daniel J.Abadi，Don Carney，Ugur C.etintemel.Aurora：A new model and architecture for data stream management［J］.In：VLDB.Journal，2003.

［11］R Jeffery，M Graofalakis，M J Flanklin.Adaptive Cleaning for RFID Data Streams［C］.Proceedings of the 32nd International Conference on Very Llarge Data Bases.Seoul，Korea，2006：163－174.

［12］Rahm E，Do H H.Data cleaning problems and current approaches［J］.IEEE Data Engineering Bulletin，2000，23（4）；3－13.

［13］郭志懋，周傲英.數據質量和數據清洗研究綜述［J］.軟件學報，2002，13（11）：2076－2082.Guo zhimao，Zhou aoying.Survey of data quality and data cleaning［J］.Iournal of Sofrware，2002，13（11）：2076－2082.

Overview on RFID Data Cleaning

Zhang Yan，Tang Yibin，Li Xufei
（College of Internet of Things Engineering，HoHai University，Changzhou 213022，China）

RFID，as a popular technology related to Internet of Things field，has good application in the future.It is necessary for RFID data cleaning，because the unreliability of the data is produced，in the process of the data acquired，and the development of RFID technology is limited.RFID data cleaning methods are surveyed through introducing the RFID data cleaning technology research in domestic and overseas.The advantages and disadvantages of the various algorithms are compared and analyzed，and the application based on the middleware of data cleaning solutions is discussed.The result shows that the algorithm of data cleaning is mainly designed for a single issue with low calculation efficiency，and the new one，with good applicability and high efficiency，should be developed in the future.

RFID technology；Internet of Things；Unreliability；Data cleaning；Solutions；universal

10.3969／j.issn.1002－2279.2016.01.009

TN911.73

A

1002－2279（2016）01－0032－05

?江蘇省自然科技基金（BK20130238）

張燕（1992－），女，山東省濰坊市人，本科生，主研方向：數字圖像處理。湯一彬（1982－），男，東南大學博士，河海大學講師。

2015－05－20