自適應時間閾值的RFID數據清洗算法

潘偉杰，李少波,2，許吉斌

（1.貴州大學 教育部現代制造技術重點實驗室，貴陽 550003；2.中國科學院 成都計算機應用研究所，成都 6100413；3.貴州大學 計算機科學與信息學院，貴陽 550025）

0 引言

射頻識別(Radio Frequency Identification, RFID)系統中，由于RFID閱讀器本身數據的不可靠性以及無線傳輸信號受外界干擾等諸多因素，出現漏讀、多讀和臟數據的情況；同時，RFID系統中存在海量中間數據。為了減少以上情況的出現，提供高質量的RFID數據，對RFID原始數據進行處理顯的尤為重要。

目前，RFID的數據清洗技術研究已經取得一定的進展。文獻[1～3]通過將數據過濾算法嵌入到標簽閱讀器當中，解決漏讀和臟數據。但由于閱讀器本身的處理能力和存儲單元的限制，這種處理方法能產生的效果還比較有限。文獻[4～6]采用定長時間窗口清洗方法應用在中間件中，設定一個時間窗口，在窗口內若標簽被讀到則認為其存在于閱讀區域內，雖然方法簡單易行，但缺乏靈活性，不能很好地實現數據過濾。文獻[7,8]采用一種基于事件驅動的滑動時間窗處理RFID數據，設定一個固定的時間閾值，當新的閱讀到達時，根據時間戳和時間閾值，判斷其過期時間，然而該方法缺乏靈活性，沒有解決冗余讀問題。文獻[9～11]采用一種基于偽事件的數據清洗方法，將標簽的冗余讀當作偽事件，通過設定時間閾值的方式，來判斷標簽是否為偽事件，對偽事件數據進行丟棄。在一定程度上解決了冗余讀的問題。文獻[12]用閱讀區域的大小和標簽的運動速度估計出時間窗口長度，但是在實際應用中閱讀器的閱讀區域是一個范圍估計值，存在著較大誤差，而且該方法只能用于固定流速的標簽信息處理，對于非勻速標簽運動則無法實現數據過濾。文獻[13]提出一種自適應調整滑動窗口大小的數據清洗方法(Statistical sMoothing for Unreliable RFid data，SMURF)，把閱讀器讀取到的RFID數據流看做統計學中的隨機事件抽象成樣本統計和建模，并且靈活的根據當前得到的樣本對窗口大小進行連續的動態調整。但是這種方法會對時間窗內的數據重復存儲，消耗大量的系統內存，同時也可能造成多讀和漏讀數據，同樣不能解決非勻速標簽運動問題。

針對目前研究的不足，本文提出一種新的自適應時間窗的RFID數據清洗算法(Adaptive Time-thresholds for RFID Data Cleaning Algorithm,ATDCA)。將時間窗模型和偽事件過濾模型結合在一起，基于分層機制過濾數據，解決冗余讀問題，減少系統緩存。

1 相關算法研究

1.1 自適應滑動窗口RFID數據清洗算法

SMURF算法中規定窗口大小為w，閱讀器在大小為wi個時段中檢測單標簽i，在窗口的每個時段中，只有部分時段能讀到標簽i，窗口中每個閱讀周期的平均閱讀率定為piavg。

針對單標簽清洗，利用伯努利二項分布模型來處理數據。為了保證閱讀器讀到數據的完整性，要求窗口的大小能保證存在于標簽閱讀區域內的所有標簽都被讀到的概率δ滿足理，SMURF算法規定標簽發生動態變化的條件為：簽閱讀出現的次數。

而對于多標簽聚集清洗的情況，SMURF算法采用一種基于π-estimator分布模型的多標簽閱讀清洗問題解決方案，用以確定窗口的標簽數量。通過窗口中標簽至少出現一次的概率為：估計出窗口中間總的標簽數量為：中sw表示窗口檢測出的標簽集合。假設不同標簽之間相互具有獨立性，則Nw'的方差可以表示為而標簽發生動態變化的條件為：表示在當前窗口和當前1/2窗口內存在標簽個數之和。針對這兩個條件的響應具體操作與解決單個標簽的情況類似。SMURF算法可以根據窗口數據自動調整窗口大小，當新閱讀產生時，標簽進入時間窗口，將每次讀到的標簽信息依次放入緩存隊列當中，每個標簽的信息，在一個時間窗口中只輸出一次。從而改善窗口大小設置不合理而造成的漏讀、冗余讀等問題[13]。

1.2 基于偽事件的RFID數據清洗方法

偽事件是一種人為定義的事件，以特定時間觸發特定動作。將冗余讀設為偽事件，分別對各個偽事件設定閾值，判斷標簽信息的讀入是否為偽事件。

針對冗余讀偽事件，設定閾值δ1，當標簽首次被發現，記該時刻為t，在時間區間[δ1,δ1+t]內，若標簽被重復讀取，則認為是重復讀偽事件，不輸出該標簽信息。該方法解決了傳統數據清洗方式會給系統帶來大量中間數據的問題，減少了緩存的開銷[10]。

由于每個標簽在其存在周期內都可能被讀到多次，SMURF算法在存儲時間窗內每次閱讀產生的標簽信息需要消耗大量的緩存，同時在一個時間窗內的標簽被讀取次數隨機性較大，如果僅僅通過設置閾值來達到清除多讀數據和臟數據，可能會導致真實標簽被誤判為多讀數據或者臟數據。而偽事件的RFID數據清洗方法設定的閾值是固定的，取值缺少靈活性。

2 自適應時間閾值的標簽數據過濾

2.1 改進算法的思想

ATDCA結合時間窗模型和偽事件過濾模型，以偽事件過濾算法為基礎，通過設定事件過期時間閾值，過濾閱讀范圍內的標簽信息，觸發事件過期閾值根據閱讀范圍內標簽的存在狀態自適應改變。

算法首先通過查詢緩存隊列中的標簽信息，來判斷新閱讀產生的數據是否為冗余讀數據，從而實現閱讀范圍內新標簽的發現和信息輸出。在實際應用中，大量已過期的標簽信息占用大量的緩存空間，增加了查詢消耗。因此要求緩存隊列中的數據要實時更新。SMURF算法可以得到當前時刻時間窗的長度，其長度根據讀卡器閱讀區域內的標簽數目變化而自適應的變化，可以動態的反應當前時刻閱讀區域內的標簽存在狀態，所以選擇自適應時間窗的大小作為緩存隊列中標簽信息過期的閾值。利用標簽時間戳和閾值實現標簽過期的判斷。

閱讀器在實際讀取標簽信息時，會出現多讀數據和臟數據，這些信息在以時間窗作為閾值的數據過濾算法中很難有效地與真實存在的標簽信息進行區分。但是在單緩存隊列的方法中，由于標簽信息的過期時間是整個存在周期，而同一個信息多次發生多讀或誤讀的概率極低。因此對多讀數據和臟數據設置一個時間閾值來判斷標簽信息的真實性。

圖1 單緩存隊列中數據過濾

當新的閱讀產生，查詢此時緩存隊列中的標簽數目，若標簽數目在閾值有效范圍內，則不更新時間閾值。若標簽的數目不在范圍內，則觸發時間閾值更新，更新完成后，通過算并更新閾值。

2.2 改進方法軟件實現

定義標簽緩存隊列的單元格式：∪t={[UIDt][][Nt]}，其中UID為標簽ID，Tend為標簽預計過期時間， N為標簽被讀到的次數，i表示標簽的序號。

標簽在整個存在周期內，被閱讀器多次重復發現。當一個新的閱讀發生時，系統查詢緩存隊列，判斷它是否已存在緩存隊列當中，若已經存在，則根據此時的時間t和時間閾值長度T，求出標簽的預計過期時間Tend= t+T，更新該標簽的相關信息，并且將標簽信息放入隊列末尾；若不存在，則將標簽的相關信息直接插入緩存隊列末尾，同時順序查詢緩存隊列，若當前時間大于或者等于某個標簽的預計過期時間則認為該標簽已經過期，從緩存隊列中刪除該標簽。具體實現流程如圖2所示。

步驟1：讀寫器進行新的閱讀，得到標簽UID。

步驟2：系統緩存隊列中的標簽數目是否在閾值有效范圍內。若在有效范圍內，轉至步驟4執行，若不在有效范圍內轉至步驟3執行。

圖2 算法流程圖

步驟4：根據標簽被讀取時刻的時間t和此時的時間閾值T計算出標簽信息的預計過期時間Tend= t+T。

步驟5：將標簽中記錄的UID與緩存隊列中的標簽信息進行對比，判斷標簽信息是否已經存在于緩存隊列當中。若已存在則轉至步驟6執行，若不存在則轉至步驟7執行。

步驟6：將標簽被讀到的次數Nt加1，更新標簽的預計過期時間等相關信息，并且將該標簽信息移至緩存隊列末尾，轉至步驟8執行。

步驟7：將標簽被讀到次數記為Nt 加1，并將該標簽的相關信息插入到緩存隊列末尾，轉至步驟9。

步驟8：判斷標簽被讀到的次數，若次數大于μ，認為該標簽信息為真實信息，將其輸出給上層模塊并且對其進行標記，轉至步驟9。

步驟9：更新緩存隊列，統計緩存隊列長度L并初始化計數值k=1，用以表示緩存隊列的第一個標簽信息，轉至步驟10。

步驟10：將緩存隊列中第一個標簽的預計過期時間與當前時間相比對，若當前時間已經超出或者等于標簽的預計過期時間，則認為標簽信息已經過期，將其從緩存隊列中刪除，轉至步驟9。若沒有，則轉至步驟11。

步驟11：判斷讀操作是否停止，若停止，則結束數據清洗，若沒有停止，轉至步驟1繼續執行清洗操作。

2.3 改進方法的硬件實現

改進方法的清洗過濾器主要由計算器、時鐘、比較器和緩存隊列組成，清洗機制如圖3所示。

圖3 清洗過濾器結構圖

其中時鐘用于獲取當前時間t，計算器用于計算此刻時間窗長度T，并且得出標簽預計過期時間。比較器1用于判斷標簽是否已經在緩存隊列當中，從而實現對緩存隊列的添加。比較器2用于判斷標簽是否是真實數據，過濾多讀數據和臟數據。比較器3用于判斷標簽是否過期，從而刪除隊列中的冗余信息。

3 仿真結果及分析

標簽信息由Matlab隨機產生，取標簽的置信區間δ≤0.01，保證標簽被讀到的概率大于1-δ≥0.99，每個閱讀周期中，標簽任意標簽被讀大小w為滿足條件的最小整數值，μ=2。在試驗中，考慮到標簽的兩種通過場景，分別是快通過場景和慢通過場景，這兩個場景的區別是每個時間窗長度之內，標簽的變化率的大小，在快通過場景，標簽的變化率可能達到 60%～70%，取θ =70%，在慢通過場景標簽的變化率可能只有5%～10%，取θ =10%。

由圖4可以看出，相比較SMURF算法，隨著讀寫器閱讀區域中標簽的數量的增大，傳統數據清洗方法所占用的緩存空間與改進方法相比差距成倍增長，從而可以看出改進方法能有效地減少緩存空間的占用率。到的平均概率

圖4 與SMURF算法比較

而對于偽事件標簽清洗方法，其發出的標簽信息量由時間窗值T與時間閾值T '之比還有標簽的變化率θ有關，

由圖5可得，在時間閾值T '選取的不是很恰當時，當標簽慢速通過，偽事件標簽清洗方法會帶來大量的冗余數據輸出，會嚴重的影響系統的性能；當標簽快速通過時，它依然還會有一定的冗余數據輸出。而兩種改進方法都基本不會帶來冗余數據的輸出。

圖5 與偽事件標簽清洗比較

4 結束語

本文針對RFID系統中的冗余讀事件和緩存清理進行了探討，深入研究了現有RFID數據清洗技術。提出了以自適應時間窗長度作為閾值來觸發標簽輸出和過期的改進數據清洗方法。實驗結果表明，改進后的算法在保證數據的準確性、實時性和精簡性。相對SMURF算法，該算法大大降低了緩存隊列的長度；相對偽事件過濾算法，其時間閾值自適應調整，靈活性增強，進一步解決了時間閾值選取不當造成的冗余數據輸出問題。而且相比起以往的數據清洗方法，其對于多讀數據和臟數據有更好的過濾效果，算法的硬件實現簡單，顯著提高了RFID原始數據的清洗效率。

[1] 姜兆寧, 丁香乾, 李謙.生產線嵌入式RFID終端讀寫器設計[J].微計算機信息, 2007, 23(8): 221, 225, 226.

[2] 丁帥, 楊善林.基于.NET精簡框架的嵌入式RFID服務組件[J].計算機工程, 2008, 34(17): 50-52, 55.

[3] Rasmus Jacobsen, Karsten Fyhn Nielsen, Petar Popovski,Torben Larsen.Reliable Identification of RFID Tags Using Multiple Independent Reader Sessions[C].Orlando, FL, USA:Presented at IEEE RFID 2009 Conference, 2009: 64-71.

[4] Graham Cormode, Vladislav Shkapenyuk, Divesh Srivastava, Bojian Xu.Forward decay: A practical time decay model for streaming systems[C].Washington DC,USA: ICDE '09 Proceedings of the 2009 IEEE International Conference on Data Engineering, 2009: 138-149.

[5] Shawn R.Jeffery, Gustavo Alonso, Michael J.Franklin, Wei Hong, Jennifer Widom.Declarative Support for Sensor Data Cleaning[C].Dublin, Ireland: PERVASIVE'06, 2006: 83-100.

[6] Shawn R.Jeffery, Gustavo Alonso, Michael J.Franklin1,Wei Hong, Jennifer Widom.A Pipelined Framework for Online Cleaning of Sensor Data Streams[C].Atlanta, USA:the 22nd International Conference on Data Engineering,2006: 140-142.

[7] Harald Vogt.Efficient Object Identification with Passive RFID Tags[J].Lecture Notes in Computer Science, 2002,2414: 98-113.

[8] 陳金花, 劉國輝, 吳軍, 周鑫.數據過濾在RFID系統中的應用[J].光通信研究.2009, (4): 41-43.

[9] Yijian Bai, Fusheng Wang, Peiya Liu.Efficiently Filtering RFID Data Streams[C].Seoul, Korea:the First Int'l VLDB Workshop on Clean Databases, 2006: 50-57.

[10] 王妍, 石鑫, 宋寶燕.基于偽事件的RFID數據清洗方法[J].計算機研究與發展, 2009, 46 (z2): 270-274.

[11] 谷峪, 李曉靜, 呂雁飛, 于戈.基于RFID應用的綜合性數據清洗策略[J].東北大學學報(自然科學版), 2009, 30(1):34-37.

[12] 王文闖, 鳳宇.基于動態時間窗的射頻識別中間件數據過濾算法[J].信息與電子工程, 2009, 7(3): 177-179, 183.

[13] Shawn R.Jeffery, Minos Garofalakis, Michael J.Franklin.Adaptive Cleaning for RFID Data Streams[C].Seoul,Korea: VLDB, 2006: 163-174.