馬爾科夫鏈的RFID數(shù)據(jù)清洗算法研究

何濤+劉暢+徐鶴+姜彥男

摘要：在獲取RFID（Radio Frequency Identification）數(shù)據(jù)過程中，大量的漏讀導致用戶無法直接使用原始數(shù)據(jù)，需通過一定方法對其清洗。在現(xiàn)有的清洗算法的基礎上，分析已有算法的優(yōu)缺點，并結合馬爾科夫鏈提出改進算法。通過馬爾科夫鏈對于狀態(tài)轉移概率的計算，改進SMURF算法檢測標簽狀態(tài)改變機制，并將概率引入窗口大小調整策略中。實驗中將勻速運動的標簽和隨機運動的標簽產(chǎn)生的數(shù)據(jù)進行清洗。結果表明，所提出的算法對于數(shù)據(jù)漏讀的填補效果更好。

關鍵詞：RFID；數(shù)據(jù)清洗；填補；馬爾科夫鏈

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）17-0168-05

1概述

射頻識別（Radio Frequency Identification，RFID）技術是一種無需和目標對象進行接觸的自動識別技術，它通過讀寫器識別出電子標簽的信息來獲取用戶所需數(shù)據(jù)。

由于半導體技術的快速發(fā)展，目前已經(jīng)能夠生產(chǎn)較低成品的電子標簽，這使得RFID技術迅速代替?zhèn)鹘y(tǒng)的條碼技術而廣泛應用到日常生活中，比如物流的定位跟蹤、貨架上物品的管理、機場行李輸送等。RFID技術的使用大大提升了現(xiàn)代服務業(yè)、生產(chǎn)制造、商業(yè)流通、交通運輸、醫(yī)藥衛(wèi)生、軍事、郵政、煙草等行業(yè)的管理效率和商業(yè)價值。可以說，RFID的應用前景十分廣闊。但就目前來看，還有著制約其更大范圍推廣使用的因素亟待解決，那就是在獲取RFID數(shù)據(jù)時用戶面臨的諸多問題，如數(shù)據(jù)數(shù)據(jù)的漏讀和數(shù)據(jù)的多讀等。

用戶在采集RFID數(shù)據(jù)時，閱讀器上報的原始數(shù)據(jù)，其準確性只有60%-70%，是無法直接上傳給上層應用使用的。其中數(shù)據(jù)的多讀情況較少而漏讀情況較為嚴重，我們需要采取一定措施使數(shù)據(jù)盡可能還原其真實性。目前較為常用的三種措施為：硬件解決措施、中間件解決措施和存儲器解決措施。硬件解決措施指的是提升采集設備和電子標簽的屬性；中間件解決措施是通過中間件對采集來的數(shù)據(jù)做相關處理；存儲器解決措施是將數(shù)據(jù)在存儲過程中通過智能化控制技術對其進行還原。中間件解決措施以其實用、高效、成本低的特性被廣泛用。

2相關研究

目前的RFID中間件數(shù)據(jù)清洗技術，比較常用的有基于定長滑動窗口的處理方法、在線可擴展清洗框架、自適應滑動窗口的數(shù)據(jù)清洗、基于完整性約束的清洗方法和基于布隆濾波的清洗方法等。其中基于窗口的清洗方法適用場景廣泛，機制簡單，實際應用中被采用較多。但是，基于窗口的清洗方案仍有缺陷。

固定長度的滑動窗口在清洗時的優(yōu)勢是較為快速，當硬件設備和周圍環(huán)境變化較小時清洗效果有明顯優(yōu)勢。但是，窗口大小的取值完全取決于行業(yè)經(jīng)驗，如果窗口大小設定不當，清洗的效果將十分低下。通過觀察圖1中的“真實數(shù)據(jù)”可以推斷出，標簽一開始處于閱讀器的讀取范圍內，在隨后的一段時間里離開了閱讀器的讀取區(qū)域，之后再次回到讀取區(qū)域內。而在實際采集時，由于漏讀情況的存在，呈現(xiàn)的數(shù)據(jù)流是不連續(xù)的，如圖中“接收到數(shù)據(jù)”除了真實離開時閱讀器讀取不到的一段空白，還有很多大大小小的空白區(qū)域。“小窗口平滑結果”顯示了利用長度較短的窗口進行處理之后的結果，“大窗口平滑結果”所使用的窗口較長?？梢钥闯?，不論窗口大小如何，一定程度上都對數(shù)據(jù)的漏讀現(xiàn)象做了填補，但過小的窗口無法對所有的漏讀現(xiàn)象進行修復，而過大的窗口填補了所有遺漏，致使最后的結果對標簽離開閱讀器射頻區(qū)域這一事實無法體現(xiàn)。

Jeffery等人基于以上問題，在固定窗口清洗方法的基礎上提出可動態(tài)調整窗口大小的數(shù)據(jù)清洗方法——SMURF。該方法創(chuàng)造性地將概率引人清洗模型，將閱讀器對標簽的讀取看作隨機事件，從而根據(jù)觀測值動態(tài)的改變窗口的大小。其具體實現(xiàn)過程如下：

如果標簽狀態(tài)發(fā)生改變，算法會依據(jù)式（8）動態(tài)的調整窗口大小。

SMURF算法首先將初始的窗口大小設置為1，然后根據(jù)讀取的實際情況動態(tài)調整窗口長度。如果當前窗口內沒有任何閱讀，SMURF算法將窗口保持為1。然后窗口以時間片為單位進行滑動，如果當前窗口滿足完整性需求，SMURF算法會根據(jù)式（8）對標簽的狀態(tài)進行檢測。當檢測結果表明標簽狀態(tài)改變時，SMURF會將當前窗口長度調整為原窗口的1/2，從而對標簽的遷躍做出反應；若檢測出標簽并未發(fā)生遷躍，則算法以當前窗口中點為輸出點進行輸出，再繼續(xù)滑動一個epoch來進行下一次處理。若計算得出的滿足完整性約束的窗口大小大于當前窗口大小，則算法以2為步長線性增大當前窗口大小，并對當前窗口中點數(shù)據(jù)進行輸出。

3改進算法MC-SMURF

3.1新算法的提出

SMURF算法通過將標簽的讀取看作是隨機事件，通過概率知識判斷標簽的狀態(tài)改變，從而減少了固定窗口清洗由于窗口長度設置不當導致的較多積極讀或消極讀現(xiàn)象。但是，當標簽進行頻繁的遷躍，或者標簽運動速度較快時，SMURF算法不能及時對窗口大小做出合適的調整。算法性能缺陷分析如下：

1）在標簽的動態(tài)性檢測方面，只通過對窗口內標簽平均讀取率的改變來判定標簽是否發(fā)生了遷躍，這在某些情況下是不準確的。我們知道，標簽的狀態(tài)改變除非肉眼所見，否則是無法尋找一個百分之百準確及時的判定標簽狀態(tài)改變的策略。

2）對于窗口大小的調整。無論是以2為步長增大窗口，還是將窗口大小設置為原來的一半，窗口的大小調整幅度和標簽的狀態(tài)變化并無關系，這使得在某些場景下積極讀和消極讀的現(xiàn)象較多。并且，當檢測到標簽狀態(tài)變化時，將窗口大小減半是武斷的，這可能造成消極讀的概率很高；而當窗口以2為步長增大時，可能會因為不能夠及時滿足完整性需求導致平滑結果和實際數(shù)據(jù)差異較大。

基于以上兩點考慮，在SMURF算法的基礎上，設計新的標簽狀態(tài)檢測方法和窗口大小調整機制，對標簽的狀態(tài)變化可能通過概率來表現(xiàn)，并將改變概率和窗口大小調整結合，使清洗過程更加高效。

3.2 MC-SMURF算法描述

由于馬爾科夫鏈是該算法的理論基礎，并且新算法是基于SMURF算法的改進，我們將此算法命名為MC-SMURF。在此首先要了解什么是馬爾科夫鏈。

定義1（馬爾科夫過程）過程（或系統(tǒng)）在時刻t₀所處的狀態(tài)為已知的條件下，過程在時刻t>t₀所處狀態(tài)的條件分布與過程在時刻b之前所處的狀態(tài)無關，即是在已知過程“現(xiàn)在”的條件下，其“將來”不依賴于“過去”，則稱此過程為馬爾科夫過程。

得出狀態(tài)轉移概率矩陣，我們就可以通過標簽從閱讀器讀取范圍離開或是留在讀取范圍的概率和標簽在閱讀器讀取范圍外進入讀取范圍的概率或是仍在讀取范圍外的概率做進一步討論。

在完整性檢測方面，繼續(xù)沿用SUMRF算法的方法，即式（8）。原算法中，當計算出的窗口較原窗口大時，通過增大窗口來保證完整性。但是在窗口增大的過程中，窗口內的平均讀取率會降低，此時，原算法默認是由于窗口增大造成而不進行標簽狀態(tài)的檢測，這樣是不符合實際情況的，因為在窗口增大的過程中，隨著標簽的狀態(tài)改變，窗口內的平均讀取率也在下降。改進算法通過概率轉移矩陣判斷標簽是否發(fā)生狀態(tài)改變，巧妙的彌補了平均讀取率下降時不進行狀態(tài)改變檢測的不足。

在計算過程中，如果得出的結果是標簽的狀態(tài)發(fā)生了改變，原算法通過將窗口減半來減少消極讀，這是缺乏合理性的。改進算法通過引人狀態(tài)改變和未改變的概率差值τ來對窗口大小進行調整。當標簽處于狀態(tài)1（狀態(tài)2情況相同）時，具體情況如下：

在用概率來檢測標簽狀態(tài)改變的改進算法中，在某些情況下是存在很大不確定性的，即：當通過狀態(tài)轉移概率矩陣計算出的狀態(tài)改變和未改變數(shù)值相近時，此時在判定標簽是否發(fā)生遷躍時不確定性較大。對于標簽的狀態(tài)改變檢測，任何系統(tǒng)都沒有辦法做到百分百確定的檢測正確，因此，改進算法通過在對窗口大小的幅度調整中加入τ來將誤差減少至最低。

如果檢測結果表明標簽發(fā)生狀態(tài)改變，但差值很小，那么是有一定可能標簽并未發(fā)生狀態(tài)轉變的。此時，將差值τ引人新窗口的計算公式，差值小時窗口的改變幅度也隨之很小，這就避免了由于誤判導致的消極讀。

同時，當未滿足完整性需求時，原算法通過每次增加2來增大窗口，但這有可能導致窗口大小不足而使清洗后的數(shù)據(jù)與真實數(shù)據(jù)產(chǎn)生較大偏差。改進算法通過將計算出的新窗口大小加入窗口的線性增大過程，新窗口較原窗口很大時，窗口增大的速度會更快，更好的彌補讀取時完整性的不足。具體方法是設置窗口大小為新窗口和原窗口和的二分之一。

3.3 MC-SMURF算法流程

MC-SMURF算法步驟如下：

1）將窗口初始大小設置為1，且在窗口內沒有任何閱讀時，均將大小調整為1。

2）改進算法以時間片為單位滑動窗口。如果當前窗口大小滿足完整性需求，則轉至步驟3）執(zhí)行，否則轉至步驟5）執(zhí)行。

3）根據(jù)式91計算狀態(tài)轉移概率矩陣，然后計算狀態(tài)轉移概率，通過狀態(tài)轉移概率判斷標簽狀態(tài)是否發(fā)生改變，改變則轉至步驟4）執(zhí)行，否則轉至步驟6）執(zhí)行。

4）通過式10）計算新窗口的大小并將滑動窗口調整為此大小，轉至步驟6）執(zhí)行。

5）計算滿足完整性需求的窗口大小，并將新窗口大小和原窗口大小相加除以2作為當前窗口大小，調整窗口，轉至步驟6）執(zhí)行。

6）以當前滑動窗口中心為滑動點輸出，滑動時間片做下一次處理。

新算法的流程圖如圖2所示。

3.4 MC-SMURF優(yōu)化策略

如果每獲取一次讀取數(shù)據(jù)都需要進行標簽狀態(tài)改變概率計算的話，即使標簽的運動狀態(tài)變化不頻繁，其代價也比較大。在實際運用中，諸如超市貨架或是圖書館書架等RFID運用場景，標簽物品的位置變化并不頻繁，因此，我們在使用MC-SMURF算法時可加入以下策略：

如果計算出的標簽位置在連續(xù)的N個窗口內都未發(fā)生變化，則認為標簽在下一個窗口時位置仍不發(fā)生變化。

該策略的使用大大減少了對于概率的計算量，且是有理可循的。如果標簽連續(xù)N個窗口檢測結果位置都沒有發(fā)生改變，則可以跳過下一個窗口直接計算再下一個窗口的概率值。

如圖3所示，假設上述改進策略中的N取3，則在窗口滑動的過程中，如果計算出的W₁、W₂、W₃窗口中標簽的狀態(tài)均未發(fā)生改變，則跳過W₄直接計算眠中的標簽狀態(tài)變化概率，如果計算結果仍是標簽狀態(tài)沒有發(fā)生改變，則繼續(xù)跳過計算W₇窗口中的概率值。該策略大大提高了該算法的運行效率。

4實驗與分析

4.1數(shù)據(jù)生成器設計

為了驗證改進算法在數(shù)據(jù)清洗方面的性能，本節(jié)運用文獻[8]里的方法，通過數(shù)據(jù)生成器生成RFID系統(tǒng)的模擬數(shù)據(jù)，再通過仿真實驗模擬其他幾種清洗算法，然后進行交叉對比，凸顯本文提出的改進算法的清洗效果。

首先設計兩個標簽運動的模型：“托盤運動模型”和“隨機運動模型”。

“托盤”運動模型：此模型模擬了托盤上被標記的物品，所有標簽的運動速度均相同。

“隨機”運動模型：此模型中，每個標簽有一個1 feet/epoch至3 feet/epoch的初始速度。每隔一百個

epoch改變一次標簽的狀態(tài)或運動速度。（這里的lepoch代表閱讀器的一個讀取周期）。

閱讀器的讀取模型根據(jù)實際應用進行設計，如圖4所示。

在主讀取區(qū)里，讀取率較高，一般約為80%至95%，意味著標簽在主讀取區(qū)基本都能讀到。隨著標簽與閱讀器的距離增加，標簽進入閱讀器次讀取區(qū)，讀取率呈線性衰減趨勢。直至降為0，代表標簽離開了閱讀器的讀取范圍。

4.2實驗結果與分析

該節(jié)將本課題的改進算法與SMURF算法和其他固定窗口清洗算法比較來驗證改進算法性能，每個固定窗口清洗算法用Static-X表示。

實驗通過數(shù)據(jù)生成器模擬一個6*6m的區(qū)域，閱讀器的最大讀取范圍為4.6m，標簽個數(shù)為30個，每個實驗使用數(shù)據(jù)生成器生成的500個時間片的數(shù)據(jù)進行處理。

實驗過程中，每個算法通過處理數(shù)據(jù)生成器產(chǎn)生的數(shù)據(jù)，將結果與真實數(shù)據(jù)對比，用每個epoch里的錯誤閱讀數(shù)來表示各個算法的清洗效果，其中的錯誤閱讀數(shù)是指標簽在閱讀器讀取范圍但是結果中沒有顯示的（a false negative），或是標簽不在閱讀器讀取范圍但在結果中顯示有讀數(shù)的（a false positive），公式如下：

首先選取“托盤”模型的運動方式來進行仿真實驗。設置閱讀器的主讀取區(qū)百分比為70%，通過改變標簽勻速運動速度比較各種清洗算法的性能。實驗所得數(shù)據(jù)如圖5所示。圖中可以看出，隨著標簽速度增大，小窗口的清洗效果逐步提高，那是因為較小的窗口有更好的填補作用。對于SMURF算法和MC-SMURF算法，它們的清洗效果穩(wěn)定且高效。而MC-SMURF由于改進了標簽狀態(tài)轉變檢測條件和窗口大小調整策略，對標簽狀態(tài)變化更為敏感，清洗效果更佳。

第二個實驗中，使用“隨機運動模型”進行驗證，通過改變閱讀器的主讀取區(qū)百分比驗證隨機運動狀態(tài)下各種清洗算法的性能，并讓標簽在每100個epoch時改變其狀態(tài)。實驗結果對比如圖6所示：

由圖6可以看出，小窗口在主讀取區(qū)百分比較小的時候清洗效果不佳，因為主讀取區(qū)很小的時候，次讀取區(qū)的讀取率很低，即對標簽的漏讀率很高，而過小的窗口無法有效地對漏讀數(shù)據(jù)進行清洗，導致錯誤讀數(shù)較高。而對于大窗口，其過濾效果隨著主讀取區(qū)百分比的增加幾乎沒有變化，原因是過長的窗口在清洗的過程中雖然可以將漏讀數(shù)據(jù)清洗完整，但無法對標簽的狀態(tài)變化導致的真實空白數(shù)據(jù)做出判斷，從而將標簽離開閱讀器讀取范圍而形成的0數(shù)據(jù)錯誤清洗為1。本文的改進算法較SMURF算法和另外兩種定長窗口算法有著更好的清洗效果，是因為改進算法對于標簽的狀態(tài)改變判定更為及時準確，同時在窗口大小的調整方面更為合理，使清洗后的數(shù)據(jù)錯誤數(shù)最低。

5結束語

為了讓提供給用戶的RFID數(shù)據(jù)更加真實可靠，提出一種基于SMURF的改進算法。算法結合馬爾科夫鏈對檢測標簽狀態(tài)轉變條件做出改變，并結合計算出的轉變概率動態(tài)設置窗口大小。實驗結果表明，與定長滑動窗口算法和SMURF算法相比，改進算法對于數(shù)據(jù)漏讀的填補效果更優(yōu)。