基于統(tǒng)計(jì)平滑處理的單標(biāo)簽RFID數(shù)據(jù)清洗改進(jìn)算法

饒晶晶

摘要：在RFID應(yīng)用過程中，基于統(tǒng)計(jì)平滑處理（SMURF）的窗口自適應(yīng)算法相比靜態(tài)窗口算法可以大大改善清洗數(shù)據(jù)的效果，但是當(dāng)閱讀器在其與標(biāo)簽的動(dòng)態(tài)移動(dòng)環(huán)境下發(fā)生漏讀現(xiàn)象時(shí)，該算法中的躍遷檢測(cè)機(jī)制不能合理使清洗窗口大小自適應(yīng)調(diào)整，從而導(dǎo)致消極讀錯(cuò)誤的大量產(chǎn)生；針對(duì)以上問題，本文在原算法的基礎(chǔ)上提出改進(jìn)，把清洗窗口平均分成子窗口1和子窗口2，將個(gè)閱讀周期內(nèi)在窗口中觀測(cè)到標(biāo)簽的概率差值以及在子窗口2中標(biāo)簽被觀測(cè)到的值作為判斷標(biāo)簽是否發(fā)生躍遷的條件，使得原算法中的躍遷檢測(cè)準(zhǔn)確度提高，實(shí)現(xiàn)對(duì)移動(dòng)單標(biāo)簽數(shù)據(jù)更有效的清洗。經(jīng)實(shí)驗(yàn)驗(yàn)證：在移動(dòng)環(huán)境中，該算法相比SMURF原算法能獲得更好清洗效果。

關(guān)鍵詞：RFID數(shù)據(jù)清洗；SMURF；自適應(yīng)窗口；躍遷檢測(cè)；

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）15-0237-04

Abstract：In the process of RFID application， the adaptive window algorithm based on SMURF can greatly improve the effect of data cleaning compared to static window algorithm， but the algorithm does not consider the dynamic mobile environment between tags and reader， if the reader missing the tags， the transition detection mechanism of this method will cause the cleaning window size can not reasonably and adaptively regulate， also will produce lots of false negative； In view of the above problems， this paper put forward the improvement based on the original algorithm， the average divideinto sub-windows of number one and sub-window of number two， use the observed valuein the number two of tagand the observed probabilitiesin the windowas the tag transition conditions， improved the tags transition detection accuracy of the original algorithm， and more effective to realize mobile single tag data cleaning. By experimental verification： In the mobile environment， the improved algorithm have better cleaning effect than SMURF.

Key words：RFID data cleaning； SMURF； adaptive window； transition detection

1 引言

射頻識(shí)別 （Radio Frequency Identification，RFID）技術(shù)是利用射頻通信原理實(shí)現(xiàn)非接觸式的自動(dòng)識(shí)別技術(shù)。在實(shí)際應(yīng)用過程中，閱讀器在其閱讀范圍內(nèi)一旦識(shí)別到帶有標(biāo)簽的物品經(jīng)過時(shí)，就會(huì)自動(dòng)且無(wú)接觸的從標(biāo)簽中獲取相應(yīng)信息，識(shí)別物品或者實(shí)現(xiàn)自動(dòng)收集物品信息的功能。目前阻礙RFID技術(shù)廣泛應(yīng)用的主要原因之一，就是原始數(shù)據(jù)獲取的不準(zhǔn)確，有時(shí)準(zhǔn)確率僅為60%～70%，即閱讀器漏讀了30%～40%的數(shù)據(jù)[1]。 為了有效地支持RFID上層業(yè)務(wù)的邏輯處理，目前普遍采用的方法就是清洗原始數(shù)據(jù)。

在RFID應(yīng)用過程的數(shù)據(jù)清洗技術(shù)中，有三種有效的方法可以提高RFID數(shù)據(jù)可靠性：硬件解決方案、中間件解決方案以及存儲(chǔ)器解決方案。硬件解決方案著重提升包括閱讀器和標(biāo)簽設(shè)備在內(nèi)的硬件性能，如使用多個(gè)標(biāo)簽和閱讀器來準(zhǔn)確獲取同一個(gè)物品的物理信息[2-4]。中間件解決方案主要在RFID原始數(shù)據(jù)未進(jìn)入到數(shù)據(jù)庫(kù)[5-7]之前，使用各種清洗算法對(duì)RFID原始數(shù)據(jù)進(jìn)行清洗，從而到達(dá)數(shù)據(jù)可靠。而存儲(chǔ)器解決方案是在數(shù)據(jù)存儲(chǔ)過程中采用智能化控制技術(shù)對(duì)RFID不可靠數(shù)據(jù)進(jìn)行修正[8-9]。基于中間件解決方案的簡(jiǎn)單與實(shí)用性，這一種解決方案已經(jīng)成為保證RFID數(shù)據(jù)可靠性的主要研究熱點(diǎn)，比較典型的方法有基于靜態(tài)滑動(dòng)窗口清洗方法和基于管道RFID數(shù)據(jù)清洗模型ESP。

對(duì)于靜態(tài)窗口清洗方法[10]，這種清洗方式簡(jiǎn)單易行，但是錯(cuò)誤率較高，在標(biāo)簽移動(dòng)過程中固定的滑動(dòng)窗口不會(huì)在系統(tǒng)的整個(gè)生命周期保持有效；管道RFID數(shù)據(jù)清洗模型[11]其在絕大多數(shù)的RFID應(yīng)用系統(tǒng)中，都能有效處理冗余數(shù)據(jù)和大部分的錯(cuò)誤數(shù)據(jù)，但不能理想的動(dòng)態(tài)性追蹤標(biāo)簽；而Jeffery等人為了解決管道RFID數(shù)據(jù)清洗模型中所選時(shí)間粒度（即清洗窗口大?。┑牟磺‘?dāng)，造成更多的積極讀錯(cuò)誤（閱讀器認(rèn)為已經(jīng)離開閱讀范圍的標(biāo)簽仍然在其閱讀范圍之內(nèi)）或消極讀錯(cuò)誤（標(biāo)簽沒有離開閱讀范圍，但是被誤解為已經(jīng)出了閱讀器的閱讀范圍）的問題，提出統(tǒng)計(jì)平滑處理方法SMURF[12]，該方法的窗口大小隨著系統(tǒng)生命周期中RFID觀測(cè)數(shù)據(jù)的改變，從而自適應(yīng)調(diào)整；但是該方法忽略了單標(biāo)簽的空間粒度多變環(huán)境，當(dāng)閱讀器在動(dòng)態(tài)移動(dòng)中發(fā)生漏讀，方法中的躍遷檢測(cè)機(jī)制不能合理調(diào)整清洗窗口的自適應(yīng)大小，并且使消極讀錯(cuò)誤大量產(chǎn)生。

本文對(duì)RFID數(shù)據(jù)清洗技術(shù)進(jìn)行了深入研究，針對(duì)基于統(tǒng)計(jì)平滑處理（SMURF）的RFID數(shù)據(jù)清洗算法沒有充分考慮到閱讀器在其與標(biāo)簽的動(dòng)態(tài)移動(dòng)環(huán)境下發(fā)生漏讀現(xiàn)象時(shí)，該算法中的躍遷檢測(cè)機(jī)制不能合理使清洗窗口大小自適應(yīng)調(diào)整，從而導(dǎo)致消極讀錯(cuò)誤大量產(chǎn)生的問題，提出把清洗窗口平均分成子窗口1和子窗口2，將個(gè)閱讀周期內(nèi)在窗口中觀測(cè)到標(biāo)簽的概率差值以及在子窗口2中標(biāo)簽被觀測(cè)到的值作為判斷標(biāo)簽是否發(fā)生躍遷的條件，使原算法中的躍遷檢測(cè)準(zhǔn)確度提高。

2 基于統(tǒng)計(jì)樣本的RFID數(shù)據(jù)流建模

本文提到的標(biāo)簽躍遷是指標(biāo)簽從閱讀器閱讀范圍之內(nèi)移動(dòng)到閱讀器范圍之外后，RFID實(shí)際理想數(shù)據(jù)中的空白部分（見圖1）。

在典型的RFID中間件解決方案中通常采用平滑窗口來清洗RFID數(shù)據(jù)流，但是窗口大小的調(diào)整需滿足以下兩種對(duì)立的應(yīng)用要求：標(biāo)簽閱讀的完整性和獲取標(biāo)簽的動(dòng)態(tài)變化。如圖1所示。

（1）完整性（Completeness）：由于小窗口的清洗容易產(chǎn)生消極讀，丟失某些標(biāo)簽信息。因此必須保證有足夠大的清洗窗口，能夠在閱讀器閱讀范圍內(nèi)有效的讀取到所有標(biāo)簽的信息，避免數(shù)據(jù)丟失。當(dāng)然，周圍環(huán)境、標(biāo)簽的種類以及閱讀器的種類和閱讀率都會(huì)影響窗口的大小，從而影響閱讀器讀取數(shù)據(jù)的完整性。

（2）標(biāo)簽動(dòng)態(tài)性（Tag Dynamics）：大窗口清洗雖然可以避免產(chǎn)生消極讀錯(cuò)誤，但同樣不可避免的會(huì)出現(xiàn)閱讀器錯(cuò)誤的認(rèn)為已經(jīng)遠(yuǎn)離其閱讀范圍的標(biāo)簽仍存在于讀取范圍內(nèi)，導(dǎo)致積極讀錯(cuò)誤產(chǎn)生。最糟糕的是，某些標(biāo)簽在離開閱讀范圍后又被放回閱讀區(qū)間，但是由于窗口過大，閱讀器無(wú)法正確判斷標(biāo)簽的真實(shí)移動(dòng)，從而在標(biāo)簽移動(dòng)狀態(tài)檢測(cè)上出現(xiàn)問題。為了保證標(biāo)簽的動(dòng)態(tài)性，我們需要了解標(biāo)簽的移動(dòng)特點(diǎn)和應(yīng)用領(lǐng)域。

在RFID應(yīng)用過程中，當(dāng)被附著標(biāo)簽的對(duì)象進(jìn)入閱讀器的閱讀范圍內(nèi)時(shí)，就會(huì)產(chǎn)生一個(gè)RFID信息，但是標(biāo)簽與閱讀器之間的動(dòng)態(tài)移動(dòng)環(huán)境下，閱讀器讀取的標(biāo)簽信息并不能保證連續(xù)；同時(shí)，標(biāo)簽與閱讀器之間的距離也影響到標(biāo)簽被讀取的概率，由于距離限制了閱讀器發(fā)射的射頻信號(hào)，所以標(biāo)簽想要被讀取就要離閱讀器近，反之離閱讀器的閱讀范圍越遠(yuǎn)的標(biāo)簽就難以被成功讀取到。因此基于統(tǒng)計(jì)平滑處理（SMURF）的RFID數(shù)據(jù)清洗算法對(duì)抽象的統(tǒng)計(jì)樣本（閱讀器讀取的RFID數(shù)據(jù)信息）進(jìn)行建模，利用樣本理論，根據(jù)RFID數(shù)據(jù)的觀測(cè)值驅(qū)動(dòng)滑動(dòng)窗口在系統(tǒng)的整個(gè)生命周期內(nèi)，都能夠連續(xù)地自適應(yīng)調(diào)整自己的大小。

查詢周期是單標(biāo)簽情況下，RFID閱讀器與標(biāo)簽通信的基本時(shí)間單位，它包括兩部分： 閱讀器將射頻信號(hào)發(fā)送給標(biāo)簽、標(biāo)簽接受到信號(hào)后發(fā)送應(yīng)答給閱讀器。為了增加RFID數(shù)據(jù)的可靠性，通常一個(gè)閱讀周期由多個(gè)查詢周期組成。用表示單位閱讀周期，。

一個(gè)閱讀周期內(nèi)閱讀器能讀到的標(biāo)簽總數(shù)用表示，而一個(gè)閱讀周期內(nèi)被成功讀取的標(biāo)簽數(shù)用表示，則一個(gè)閱讀周期內(nèi)標(biāo)簽的讀取概率即為：

但是當(dāng)標(biāo)簽信息漏讀現(xiàn)象，發(fā)生在閱讀器閱讀范圍之內(nèi)的標(biāo)簽相對(duì)閱讀器動(dòng)態(tài)移動(dòng)時(shí)（圖3藍(lán)線區(qū)間），也會(huì)使窗口條件滿足情況1條件。這樣就會(huì)使原算法錯(cuò)誤地認(rèn)為標(biāo)簽信號(hào)在當(dāng)前窗口內(nèi)發(fā)生了躍遷，而過大的窗口調(diào)整會(huì)產(chǎn)生更多的消極讀。

針對(duì)情況1，本文提出規(guī)則1對(duì)當(dāng)前清洗窗口大小進(jìn)行適度調(diào)整，以滿足清洗要求。

規(guī)則1：當(dāng)且滿足式（4）時(shí)，調(diào)整當(dāng)前清洗窗口為；

情況2：改進(jìn)算法為了更加準(zhǔn)確的實(shí)現(xiàn)標(biāo)簽信號(hào)躍遷檢測(cè)，提出規(guī)則2，引入窗口內(nèi)個(gè)閱讀周期觀測(cè)到標(biāo)簽的概率差值和作為標(biāo)簽是否處于閱讀器閱讀范圍之內(nèi)的判斷條件。

規(guī)則2：當(dāng)在窗口內(nèi)且，調(diào)整當(dāng)前清洗窗口調(diào)整為原窗口的，也就是。

3.2 算法實(shí)現(xiàn)

為了減少RFID數(shù)據(jù)出現(xiàn)的積極讀錯(cuò)誤，同時(shí)平衡清洗窗口的平滑性，設(shè)置一個(gè)閱讀周期為滑動(dòng)窗口每次向前滑動(dòng)的距離，為最小的清洗窗口值。將清洗窗口的中間時(shí)間節(jié)點(diǎn)作為標(biāo)準(zhǔn)，若滑動(dòng)窗口內(nèi)的數(shù)據(jù)在一個(gè)閱讀周期內(nèi)滿足輸出條件，即可輸出數(shù)據(jù)。單個(gè)標(biāo)簽的改進(jìn)算法如表1所示。

4 實(shí)驗(yàn)驗(yàn)證

測(cè)試環(huán)境如圖4所示：

測(cè)試環(huán)境平臺(tái)和軟件：

測(cè)試平臺(tái)：Microsoft Visual Studio 2010

數(shù)據(jù)庫(kù)工具：Microsoft SQL Server 2008

數(shù)據(jù)生成的語(yǔ)言：C#

串口參數(shù)：

波特率：9600

數(shù)據(jù)位：8位

停止位：1位

校驗(yàn)位：無(wú)

現(xiàn)有的RFID數(shù)據(jù)清洗技術(shù)廣泛采用模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，為了驗(yàn)證本文所提出的改進(jìn)算法，現(xiàn)數(shù)據(jù)模擬場(chǎng)景如下：固定一個(gè)閱讀半徑4.6m，最大閱讀率為95%的閱讀器，讓單標(biāo)簽在閱讀器閱讀范圍內(nèi)外的任意位置以隨機(jī)速度（）變化移動(dòng)。根據(jù)模擬場(chǎng)景，當(dāng)有符合條件的數(shù)據(jù)（圖6中RFID原數(shù)據(jù)）PC1就會(huì)自動(dòng)生成并且儲(chǔ)存在自己的數(shù)據(jù)庫(kù)表格中。

由于一個(gè)閱讀周期中還包含標(biāo)簽給閱讀器的應(yīng)答，因此每隔一個(gè)周期PC2會(huì)得到一條由PC1從數(shù)據(jù)庫(kù)中通過串口發(fā)送的標(biāo)簽數(shù)據(jù)，PC2會(huì)執(zhí)行完整性置信度的清洗算法，處理得到的標(biāo)簽數(shù)據(jù)，保存記錄最終數(shù)據(jù)以作分析。簡(jiǎn)單構(gòu)建標(biāo)簽信息數(shù)據(jù)格式如圖5所示，以模擬閱讀器有無(wú)讀取到隨機(jī)速度的標(biāo)簽：

B1位：標(biāo)簽未被讀取即為0，標(biāo)簽被讀取即為1；A1～A7：標(biāo)簽的移動(dòng)速度，0～90隨機(jī)數(shù)。

由圖6可知，當(dāng)標(biāo)簽在閱讀器閱讀范圍內(nèi)動(dòng)態(tài)移動(dòng)而發(fā)生閱讀器漏讀標(biāo)簽信息時(shí)，改進(jìn)算法能夠更加合理的使清洗窗口大小自適應(yīng)調(diào)整，從而使得清洗的數(shù)據(jù)更加接近實(shí)際理想數(shù)據(jù)，并且能夠更準(zhǔn)確地動(dòng)態(tài)判斷標(biāo)簽信號(hào)躍遷檢測(cè)。這種與實(shí)際數(shù)據(jù)相比，清洗效果明顯優(yōu)于SMURF原算法的改進(jìn)算法在性能上整體實(shí)現(xiàn)了提升。

由圖7可知，相較于SMURF原算法，改進(jìn)算法在標(biāo)簽以隨機(jī)速度變化移動(dòng)過程中，減少了積極讀錯(cuò)誤的產(chǎn)生；但是卻增加了消極讀錯(cuò)誤，因?yàn)楦倪M(jìn)算法中進(jìn)行數(shù)據(jù)處理的清洗窗口會(huì)比原算法的小，因而標(biāo)簽躍遷檢測(cè)機(jī)制檢測(cè)不到清洗窗口。

5 結(jié)論

本文分析比較了幾種經(jīng)典的數(shù)據(jù)清洗技術(shù)，并且對(duì)基于統(tǒng)計(jì)平滑處理的RFID數(shù)據(jù)清洗技術(shù)進(jìn)行了深入研究，針對(duì)閱讀器在動(dòng)態(tài)移動(dòng)環(huán)境下發(fā)生標(biāo)簽信息漏讀現(xiàn)象，該算法中的躍遷檢測(cè)機(jī)制不能合理使清洗窗口大小自適應(yīng)調(diào)整，導(dǎo)致消極讀錯(cuò)誤大量產(chǎn)生；為此，本文提出改進(jìn)算法，利用個(gè)閱讀周期內(nèi)在窗口觀測(cè)到標(biāo)簽的概率差值和子窗口2中標(biāo)簽被觀測(cè)到的值作為判斷標(biāo)簽發(fā)生躍遷的條件。經(jīng)實(shí)驗(yàn)驗(yàn)證，改進(jìn)算法使得動(dòng)態(tài)標(biāo)簽躍遷檢測(cè)的準(zhǔn)確度提高，但是改進(jìn)算法過小的清洗窗口，也將引入一定程度的消極讀錯(cuò)誤，這個(gè)問題有待進(jìn)一步研究解決。

參考文獻(xiàn)：

[1]谷峪，于戈，張?zhí)斐?RFID復(fù)雜事件處理技術(shù)[J].計(jì)算機(jī)科學(xué)與探索，2007，I（2）：255-267.

[2] M. S. Trotter and G. D. Durgin.Survey of Range Improvement of Commercial RFID Tags with Power Optimized Waveforms[C].IEEE International Conference on RFID， April 2010：195-202.

[3] A. Rahmati， L. Zhong， M. Hiltunen， and R. Jana.Reliability Techniques for RFID-Based Object Tracking Applications[C]/.Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks （DSN 07）. IEEE Computer Society， 2007：113–118.

[4] H. Chen， W. Ku， H. Wang and M. Sun.Leveraging spatio-temporal redundancy for RFID data cleansing[C]/.Proceedings of the 2010 international conference on Management of data， SIGMOD '10， 2010.

[5] S.R. Jeffery， M. Garofalakis， and M.J.Franklin.Adaptive cleaning for RFID data streams[C]// Proceedings of the 32nd international conference on Very large data bases ， VLDB Endowment， 2006：163-174.

[6] H. Gonzalez， J. Han， and X. Shen.Cost-conscious cleaning of massive RFID data sets[C]/.Proc. 2007 Int. Conf. on Data Engineering （ICDE'06）， Istanbul， Turkey， April 2007.

[7] B. Song， P. Qin， H. Wang， W. Xuan， G. Yu，.bSpace： A data cleaning approach for RFID data streams based on virtual spatial granularity[J].Proceedings of HIS， 2009 （3）：252-256.

[8] P. Darcy， B.Stantic and A.Sattar.A Fusion of Data Analysis and Non-Monotonic Reasoning to Restore Missed RFID Readings[J].Proceedings of Intelligent Sensors， Sensor Networks and Information Processing （ISSNIP 2009）， 2009：313-318.

[9] J. Rao， S. Doraiswamy， H. Thakkar and L. S. Colby. A Deferred Cleansing Method for RFID Data Analytics[C].VLDB， 2006.

[10] E.Rahm and H.Do.Data cleaning：Problems and current approaches[J] .IEEE Data Eng.Bull， 200023（4）：3-13.

[11] S.R.Jeffery，G.Alonso，et al.A Pipelined Framework for Online Cleaning of Sensor Data Streams[C]. ICDE，2006.

[12] Jeffcry S R，Garofalakis M，F(xiàn)rakklin M J.Adaptive cleaning for RFID data stream.Proc of the 32nd Int Conf on Very large Databases[C]. NewYork：ACM，2006：163-17.