基于FSM的物聯網大數據清洗算法*

郭雷勇，李 宇

（廣東藥科大學 醫藥信息工程學院，廣東 廣州 510006）

0 引 言

目前，物聯網技術在物流管理、供應鏈管理、產品的跟蹤等領域[1]得到了越來越廣泛的應用。與傳統的數據不同，RFID標簽數據不僅包含產品信息和廠商信息，還記錄了該標簽讀取的時間和位置信息。物聯網技術本身固有的對環境的敏感性、標簽沖突現象以及標簽數據存在多讀、漏讀、冗余讀等問題，降低了數據的可靠性。因此，在中間件中需要對數據進行清洗。而這些應用能否取得成功，很大程度取決于RFID數據的可靠性。本文主要對如何清洗標簽中的多讀及重復讀的數據進行深入研究。

RFID數據清洗算法主要是針對標簽數據存在的漏讀、多讀、冗余讀等現象進行過濾清洗，提高數據的可靠性。目前，大多數的RFID清洗算法中，很多工作均只針對標簽的漏讀問題進行研究，往往忽視了數據清洗的效率問題。實際應用中，可能同時面臨多臺閱讀器海量的標簽數據，而物聯網技術應用本身需要對數據進行實時處理，因此希望在保證數據的清洗準確率的前提下，以較低的時間代價處理更多的數據。

1 當前RFID清洗算法存在的主要問題

近些年，RFID標簽的識別率得到了提高，但是無論是標簽的識別率還是抗干擾性都遠遠沒有達到理想水平。面對海量的數據，存在各式各樣的錯誤來源，如何高效地對數據進行清洗是一項極具挑戰性的任務。

文獻[2]提出了一種定長的滑動窗口，在窗口中統計新來標簽數據的讀取次數，如果次數超過閾值，則視為干凈數據，同時解決了標簽輸出順序的問題。文獻[3]則提供了一個數據的清洗框架ESP，針對RFID數據流，使用類似于查詢語言的方式對數據進行清洗，提供了5層管道查詢框架，并提供了一系列過濾方法。文獻[4]提出了一種考慮成本的清洗框架，使用貝葉斯網絡對數據進行清洗，利用決策樹選擇最優的過濾方法，也取得了較好的結果。文獻[5]利用類似查詢的語句對RFID數據進行過濾，并預先通過定義好的標簽動作產生相應的規則，保證了清洗的準確率，但其與實際應用的場景關聯過于緊密，不具有通用性。文獻[7]通過使用AVL樹的數據結構存儲標簽流，解決了滑動窗口清洗算法中存在的重復窗口問題，一定程度上提高了處理效率。

為了解決定長滑動窗口需要預先設定窗口大小的問題，文獻[6]提出了一種基于統計模型動態更新滑動窗口的方法SMURF，把標簽讀寫過程看成一個隨機采樣模型進行建模，針對單個標簽和多個標簽兩種情況，假設了伯努利二項分布和π估計的統計模型。SMURF算法雖然克服了提前設置窗口大小的問題，但其基于概率分布模型，實現較為復雜，處理效率不高，且只適應于一個閱讀器的場景，沒有考慮多閱讀器的情況。在實際的RFID業務應用中，為了提高標簽的識別率，一般會部署多臺閱讀器。另外，SMURF算法主要針對數據的漏讀，現實應用中則希望有更全面的數據清洗功能。

傳統基于定長的滑動窗口清洗算法中，設置窗口的大小是一件極富挑戰性的工作。如果窗口設置太小，將無法保證標簽數據流的完整性，但窗口太大又會丟失標簽的動態性，如圖1所示[6]。

圖1 滑動窗口的問題

效率上，基于定長的滑動窗口數據清洗的時間復雜度為O(KN)，K是滑動窗口的長度，N為數據的規模。當有新的標簽到來的時候，需要遍歷整個滑動窗口以統計該標簽的讀寫次數，查看該讀寫次數是否到達閾值，從而確定是否輸出數據。研究發現，清洗效率不高的原因在于如圖2所示的重復窗口區域會被反復計算，嚴重影響了數據清洗的效率。

圖2 滑動窗口的重復窗口

本文根據實際應用的場景，針對標簽數據存在的多讀和大量冗余現象，提出了一種基于有限狀態機（Finite-State Machine，FSM）的清洗框架，提高了數據的處理效率。

2 基于FSM的數據清洗算法模型實現

本文在定長的滑動窗口算法基礎上進行改進，拋棄了傳統清洗算法設置滑動窗口的方式[7-8]，通過記錄標簽首次進入滑動窗口的時間、最近一次的讀取時間、讀取的次數等作為標簽的狀態記錄，按照標簽的狀態對數據進行清洗。算法使用基于有限狀態機的方式作為清洗策略，解決了重復窗口的問題，通過創建多階哈希表存儲標簽讀寫記錄，提高了數據的處理效率。

2.1 模型的主要思想

一個確定的有限狀態機FSM是由A=(Q,∑,δ,S,F)五元組[9]構成的。本文中五元組的實際意義如下：Q表示非空的狀態集合，由標簽的各個狀態組成；∑表示輸入，即攜帶信息的標簽流；δ表示轉移函數δ:Q×∑→Q，根據輸入和標簽的狀態確定狀態的轉換；S表示標簽的初始狀態，其中S∈Q；F表示最終的標簽狀態集合，其中F ?Q。下面按照有限自動機的五元組闡述本文的清洗算法的思想。

2.1.1 確定標簽的狀態集合Q和初始狀態S

通過對標簽流的研究，提出將標簽的整個讀寫過程定為unknown狀態、captured狀態和observed狀態3種狀態，即標簽的狀態集合Q={unknown，captured，observed}。其中，unknown表示標簽不在讀取區域之內，無法知道標簽的信息，處于未知狀態中；captured表示標簽首次被捕捉后的狀態，意味著標簽已經進入讀取區域，但根據當前的信息無法確定該標簽屬于正常還是異常數據；observed則表示標簽在讀取區域中，已經確認被讀取到，是可靠數據。標簽的初始狀態是指該標簽還未被捕捉的時候，處于未知狀態，即S={unknown}。

2.1.2 確定標簽流的組成∑

從閱讀器傳輸到中間件的RFID原始數據，一般可認為每個標簽記錄都是由一個三元組＜EPC,Location,Time＞組成[10]。其中，EPC代表標簽獨一無二的ID；Location表示閱讀器放置的地方，即標簽被捕獲的位置；Time則表示閱讀器檢測到該標簽的時間。

本文的數據清洗算法中并沒有針對標簽的位置信息Location作任何處理，因此并不需要該特性。本課題在研究標簽的讀取過程的數據后，提出在這個三元組中用標簽的讀取信號強度（Signal Strength）代替標簽的位置信息，作為標簽的讀寫特征，用SS表示，取值范圍0～100。值越大，表明信號越強。由于物聯網技術本身的內在敏感性，信號強度往往與貨物的性質（金屬非金屬、液體等）、標簽所貼的商品位置及與閱讀器所處的位置相關。越貼近閱讀器信號越強，而與閱讀器距離越遠，信號越弱。標簽的讀取信號強度可以更加貼切反映標簽讀取過程的特征，因此本文的標簽數據均可以認為是以＜EPC,Time,SS＞三元組形式存在的。

2.1.3 確定標簽在狀態機轉換機制δ:Q×∑→Q

標簽的狀態轉換機制是清洗算法的核心，標簽的轉換即數據清洗的過程。為了實現快速查詢標簽的讀取記錄，將使用多階哈希表作為存儲標簽讀取記錄的數據結構。

本文算法主要根據在有效的時間內以標簽的讀取次數和讀取信號強度確定標簽的狀態轉換。標簽的讀寫次數是表明標簽讀取過程的一個重要特征，如果讀取次數較多，那么有理由相信該數據不是偶然讀到，屬于正常數據的可能性非常高。

在RFID數據分析中發現，無論應用的場景怎樣變化，無論是快速通道還是庫存盤點，大部分的RFID標簽數據的讀取信號強度都趨近于高斯分布。而標簽多讀現象產生的原因多是標簽剛好經過閱讀器的區域，具有與閱讀器距離較遠、讀取強度較低等特點。因此，本文使用標簽讀取信號強度的目的在于增加一個特征確定數據是否是可靠數據，減少單一特征可能造成的清洗誤差。

同時，為了適應更多的應用場景，避免提前預設信號強度閾值，本文在清洗過程中記錄所有標簽的平均讀取強度SSavg：

其中totalCnt表示標簽的總的讀取數。根據中心極限定理，當某標簽的功率超過當前的平均值，便有理由相信該標簽是正常數據，從而可以確保即使在標簽的讀寫次數達不到閾值煩人情況下，仍然可以判定該數據是正常數據，減少了數據清洗的錯誤率。

下面講述具體的標簽狀態的轉換機制。本文將標簽狀態定義為unknown狀態、captured狀態和observed狀態。在有效的時間內，在不考慮標簽讀取強度的情況下，當標簽未讀到之前處于unknown狀態；當標簽首次讀到后進入captured狀態，處于可疑狀態；當讀取的次數超過設定的閾值后，進入observed狀態，表明該數據是可靠數據，將作為干凈數據輸出；若以后再讀到該標簽，則會被視為冗余數據過濾掉。其中，如果任意一次的標簽讀取過程中，讀取信號強度超過了當前所有標簽的平均讀取強度，則無論其處于unknown或captured狀態下，均會直接躍遷到observed狀態，無需考慮其讀寫次數。若某個標簽連續讀取時間間隔超過了有效的時間間隔，則會被認為讀取記錄已經過時失效，需要清空記錄。

2.2 多階哈希表的創建過程

哈希表[11]也叫散列表，將某個key值映射到哈希表中的存儲位置，實現數據的快速查詢訪問。哈希表結合了鏈表及數組的優點，在軟件設計領域有著極為重要的應用。如果哈希表設計合理，可以在O(1)的時間復雜度內實現數據的快速查找。哈希表設計的關鍵在于找到一個好的散列函數，使散射地址足夠分散，最大程度上避免碰撞的發生。

本文針對標簽數據獨一無二的特點，設計了多階哈希表，利用均勻散射函數使得各個標簽得到了一個隨機地址。該方法獨立于各個平臺，實現簡單，最大程度降低了標簽之間的沖突，可移植性高。下面講述多節哈希表的創建過程。

（1）首先定義在哈希表中的存儲標簽數據的節點。

（2）根據實際業務中貨物中的標簽的數據規模DataSize，確定多階哈希表的最大桶個數M。一般為了避免較多的沖突，可設置M=2*DataSize；再設置哈希表階數N，該值不能太大，否則多階哈希可能退化成多鏈表。

（3）在內存中申請M×N個TagNode節點空間，以二維數組Hash[M][N]表示，作為存儲標簽數據的哈希矩陣，其中N表示哈希表的階數，M表示哈希表的最大桶數。

（4）計算每階哈希表的桶數，哈希表的各階桶數由比最大桶數M小的最大的n個素數組成，存儲在數組primeTable中，primeTable[n]代表第n階的哈希表的桶數，n=1,2,3,…,N。實際上，在哈希表的實現上，直接使用最大桶數作為每階哈希表的桶數也是可行的。但是，使用素數作為每階哈希表的桶數可以降低沖突的概率。它的數學依據在于一個隨機數對質數取余得到的Hash值，比對合數取余的結果散列得多，從而可以最大程度避免哈希沖突，實現如圖3所示。

圖3 多階哈希表的結構

（5）由于RFID標簽的值是唯一的，本文以標簽tagId作為key建立映射函數：f(tagId)=(tagId+M)%primeTable[n]。primeTable[n]表示第n階哈希表的桶數，n=1,2,3,…,N；M為哈希表最大桶數；f(tagId)是在該階哈希表中的存儲地址。如果該位置已經存在其他標簽，則繼續計算嘗試下一階的哈希桶。

（6）以步驟（5）的哈希映射函數為基礎，為多階哈希表提供標簽節點的查詢、修改、增加等方法，而這些方法均是以標簽查找為基礎。當標簽的狀態發生變化時需要更新時間、讀寫次數等狀態。

（7）創建隊列Queue，儲存冗余標簽數據過濾后的對象，此隊列的數據是經清洗后確認讀到的可靠數據。該隊列的數據可以直接被上級應用如業務系統所使用，也可以儲存到數據庫中做下一步處理。

2.3 模型初始值的確定

在確定標簽處于Q={unknown,captured,observed}狀態轉換前，首先需要配置模型的初始值——有效讀取時間閾值Tthreshold和讀取次數閾值TagCntthreshold。

（1）有效讀取時間閾值Tthreshold，表征標簽的有效讀取時段。如果連續兩次讀取到的時間差值超出該時間閾值，則認為是不同的事件，需要清空舊的標簽讀取記錄。本課題中，該值是根據業務的實際應用場景確定，通過對倉儲管理中出入庫流程時間統計，可以確定一批貨從倉庫到通過閱讀器的通道所花費的時間。每批貨物出入庫所花費時間20～600 s不等，時間閾值需要動態更新，以適應實際的場景。該值需要根據實際的業務情況進行調整，如果是獲取靜態的數據如掃描庫存，可以相應增大其閾值；若是獲取動態的數據如傳輸帶的標簽數據，則需要調小該閾值。

（2）讀取次數閾值TagCntthreshold，是標簽狀態變化的臨界值。在有效的時間內，標簽讀到的次數超過該閾值才可認為是可靠數據，若低于該閾值則認為是可疑數據。該值可通過統計歷史經驗值得到。在實際應用中，該值同樣需要根據實際業務進行調整。

2.4 清洗算法流程

本算法針對RFID數據存在的大量冗余及其多讀現象，使用基于確定有限狀態機對數據進行清洗，通過創建多階哈希表作為過濾通道，快速有效地過濾海量RFID數據，減少網絡的傳輸量，降低業務的數據處理規模，提高數據清洗的效率。清洗算法的實現流程如下。

（1）根據業務應用場景確定模型的初始值，依照上述方法創建多階哈希表，并定義好存儲在哈希表的標簽節點數的數據結構。

（2）確定標簽的狀態。當有標簽數據＜EPC,Time,SS＞到來時，首先查詢該標簽在哈希表中是否存在其歷史讀取記錄。若該標簽不在哈希表中，則表示該標簽處于unknown狀態；如若標簽在哈希表中，則在進一步確認標簽的狀態之前，需要先判斷該標簽是否處于有效的讀取間隔內。若最近讀取時間與最后一次的讀取間隔超過有效時間閾值，則表示該標簽之前的讀取記錄已失效，需要清空其讀取記錄，并將其視為首次讀取的標簽進行處理；若讀取間隔仍然在有效的時間閾值之內，則可以根據哈希表該節點的state字段確定標簽的狀態。

（3）如圖4所示，定義標簽狀態轉換的狀態機，確定標簽過濾的準則。

圖4 標簽的狀態轉換

①當標簽處于unknown狀態時，將其加入多階哈希表中，設定其讀取次數、讀取時間。此時，考慮其信號讀取強度是否超過當前的標簽記錄的平均讀取強度SSavg。若超過，則直接設置狀態為observed狀態，作為干凈數據加入隊列Queue中，供上層業務系統調用；若其讀取的信號強度小于平均值，則轉入captured狀態。

②當標簽處于captured狀態時，更新其節點數據，考慮其讀取次數和其信號讀取強度是否超過當前的標簽記錄的平均讀取強度SSavg，若超過平均值或其讀取次數剛好到達有效讀取的閾值，標簽將轉為observed狀態，標簽值則作為過濾后的干凈數據加入隊列Queue中；否則，該標簽仍然處于captured態。

③當標簽處于observed狀態時，新的讀取記錄作為冗余數據過濾掉。在實際應用中，絕大多數標簽均處于該狀態。

（4）更新當前所有標簽記錄的平均讀取信號強度，按照SSavg=(SSlastavg*tagCnt+SS)/(tagCnt+1)

方式進行計算，更新哈希表中該節點的最新讀取時間和讀取次數。

2.5 清洗算法步驟

清洗算法的流程，如圖5所示。

圖5 清洗算法流程

第一步，根據項目的應用場景，將有效讀取時間閾值Tthreshold設置為100 s，有效讀取次數閾值TagCntthreshold設置為5，哈希表的階數設為10。假定標簽的數據規模DataSize為10 000，則可設最大的哈希表桶數M為20 000，以二維數組HashTable[10][20 000]表示多階哈希表。

第二步，計算每階的桶數。本實例中，以20 000作為最大的桶數，從第1階到第10階，哈希表的各階桶數依次設定為19 997、19 993、19 991、19 979、19 973、19 963、19 961、19 949、19 937、19 927，存儲在數組primeTable中。

第三步，假若在10 s同時有一批標簽到來，如表1所示。

表1 標簽讀取記錄表

第四步，對于標簽值0000000100，按照f(tagId)=(tagId+M)%primeTable[n]哈希函數計算其在第一階哈希桶的索引位置index=(100+20000)%19997=103，即是第一階哈希桶位置103。同理，0000000099在位置102，0000000098在位置101，……，0000000001在位置4。因為設定讀取有效次數的閾值為5次，則5次以上讀取記錄000000005～0000000100無論其讀取信號強度最大值與平均值大小如何，其狀態均處于observed態，都可將其作為可靠數據輸出。值得注意的是，對于標簽記錄0000000001，雖然其總的次數沒有達到閾值，但其讀取信號強度最大值超過平均值，所以也認為該標簽是穩定數據，直接轉入observed狀態。通過清洗后，這些標簽記錄只保留（0000000100，000000099……000000005，000000001）共97個標簽值，大大降低了數據規模。這些標簽此時均處observed狀態，而000000002～000000004標簽值則處于captured狀態，這些值均作為可疑數據保留在哈希表中而不輸出。

第五步，假若在100 s有效讀取時間閾值內均沒有值為0000000100的標簽讀取記錄，101 s以后，當值為0000000100標簽再次被讀取到時，由于超過有效的讀取時間閾值，所以該標簽讀取記錄實際已經失效處于unknown狀態，此時再讀到則按照首次讀到的標簽數據進行處理。

第六步，若此時有標簽000020097到來，從第一階哈希表開始計算，其index1=(20097+20000)%19997=103，因為在該桶已有標簽0000000100，產生哈希沖突；接著計算第2階，其index2=(20097+20000)%19993=111，所以該標簽存儲在第二階的索引位置為位置111。多階哈希數據結構如圖6所示。

圖6 哈希表數據實例結構

2.6 算法實現

下面給出基于有限狀態機的清洗算法實現的偽代碼。

3 實驗仿真與分析

本實驗對本文提出的基于有限狀態機的清洗算法，在清洗準確率、清洗的效率以及數據的冗余清洗等方面進行仿真測試。實驗使用的對比算法是文獻[10]中提到的基于定長的滑動窗口的數據清洗方法，記為fix_size，其中size是滑動窗口的大小。需要說明的是，實驗主要使用Visual Studio 2005和Matlab 7.70工具。

3.1 實驗數據集來源

實驗數據采用IBM的RFID數據生成器，可以按照設置的分布模型生成數據集。該生成器可以通過改變標簽的類型、標簽與閱讀器的距離、標簽的移動速率、標簽的密集等方式，模擬標簽的實際移動過程。

實驗中，按＜EPC,Time,SS＞三元組生成數據集。標簽有3個向量特征，數據集每個特征按不同的分布函數生成。其中，RFID數據標簽EPC采用隨機函數生成，標簽的到達時間Time則服從泊松分布，讀取信號強度滿足均值為0.5、方差為0.05的高斯分布。依照上述方法重復生成數據，根據實驗需要調節噪聲的比例。

3.2 閾值對準確率影響實驗

算法在實驗前需要提前設定有效讀取時間閾值Tthreshold和讀取次數閾值TagCntthreshold。有效讀取時間閾值與實際應用場景有著重要聯系，目的在于檢測到標簽的動態性，即判斷標簽在這個過程有無移動。實驗中主要取決于標簽的到達時間和生產數據的間隔。為了簡單起見，算法中的實驗均認為數據是在有效的時間內。

本實驗主要用于測試不同的讀取次數閾值對準確率的影響。首先按照上述方法產生標簽讀取記錄，間隔200 ms，重復該生成過程10次，標簽到達率設置為10 tags/s，設置噪聲比例為5%，效讀取時間閾值Tthreshold設置為100 s。實驗效果如圖7所示。

從圖7的實驗結果可以看出，讀取次數閾值設置為3和4的情況下，識別準確率最高，達到96%；當增大其值后，其識別的準確率呈不斷下降趨勢。這是因為實驗的數據只重復生成了10次，數據重復次數不高。但是，讀取次數閾值設置太高會將一些正常數據當成多讀數據數據，而設置太低則會將一些多讀數據當成正常數據，因此需合理設置。

圖7 不同讀取次數閾值下的數據清洗的準確率

3.3 數據清洗的準確率實驗

為了衡量數據清洗的效果，考慮在不同噪聲的情況下考察算法的數據清洗準確率。本文算法記為FSM，對比算法則按照窗口的大小依次選擇20、50和100，分別記為fix20、fix50和fix100。

數據的準確率是指在清洗后輸出的真實數據占總數據的比例。首先上述方法產生標簽讀取記錄，每隔200 ms，重復該生成過程10次，標簽到達率設置為10 tags/s，有效讀取時間閾值Tthreshold設為100 s，讀取次數閾值TagCntthreshold設為3次。這個過程按照0%、10%、20%、40%、60%、80%的比例在讀取記錄中添加噪聲，運行效果如圖8所示。

圖8 在各種噪聲比例下數據清洗的準確率

從圖8可以看出，提出的FSM方法準確率整體上優于其他3種基于固定滑動窗口的數據清洗算法，但差距小，與預想的情況一致，即4種算法均隨著噪聲的比例的增加，準確率呈下降趨勢。在噪聲比例為0的情況下，可以100%準確識別標簽；當噪聲比例增加到10%，FSM與fix100識別的準確率在96%，優于其他兩種情況；當噪聲比例增加到20%時，此時fix100的準確率最高為94%，FSM算法為93%，此后當噪聲比例持續增多后，FSM算法因為增加了讀取信號強度作為特征，因此比其他3種固定滑動窗口算法表現得更優異。可見，本文提出的基于有限狀態機的方法在數據清洗的識別準確率方面是有效的。

3.4 標簽到達率對數據清洗的性能影響

本實驗考慮到RFID的數據處理有實時性的要求，查看在標簽不同到達率情況下各個算法的性能對比。在本文中以每個標簽的平均時延作為衡量數據清洗的性能。平均時延，是指每個標簽平均清洗的花費時間，其值按照總的數據的清洗時間除以標簽的數據量計算。

以項目的實際運行場景為基礎，本實驗設置噪聲比例為5%，有效讀取時間閾值Tthreshold設為100 s，讀取次數閾值TagCntthreshold設為3次，依次設置標簽到達率為10 tags/sec、100 tags/sec，1 000 tags/sec、10 000 tags/sec。按照上述的方法產生標簽讀取記錄，每隔200 ms重復一次，重復10次。

從圖9的運行結果分析，FSM在性能表現要大大優于基于固定式滑動窗口的算法。當標簽以10 tags/s到達時，各個算法的標簽平均時延幾乎一致，值為8 ms，此時因為數據規模較小，時間的花費主要用于等待標簽的到來。而隨著標簽到達率的提高，增加到5 000 tags/s，此時FSM算法因為采用了多階哈希表，其數據的訪問效率仍然可以維持在O(1)的時間復雜度，因此當數據增加時，其平均時延始終維持在0.8 ms左右，而固定滑動窗口算法則明顯的隨著窗口尺寸的增長，其性能呈線性下降趨勢。

圖9 標簽在不同到達率情況下的平均時延

值得注意是，當數據到達率超過5 000 tags/s，此時FSM的性能下降比較厲害，這是因為當數據的規模超過了哈希桶的預設范圍以后，數據沖突較為嚴重，哈希表便退化成為鏈表，因此根據標簽的規模設置哈希桶的大小就非常重要。

3.5 噪聲對數據清洗的性能影響

本實驗接著查看在不同噪聲對數據清洗算法性能影響，同樣以每個標簽的平均時延作為衡量數據清洗的性能表現。

以項目的實際運行場景為基礎，設置標簽到達率為100 tags/s，有效讀取時間閾值Tthreshold設為100 s，讀取次數閾值TagCntthreshold設為3次。按照上述的方法產生標簽讀取記錄，每隔200 ms，重復該生成過程10次，在這過程中按照0%、10%、20%、40%、60%、80%的比例添加噪聲，其運行結果如圖10所示。

圖10 在各種噪聲比例下數據清洗的平均時延

從結果來分析，本算法在各種噪聲的情況下性能表現優于基于定長滑動窗口的清洗算法，基于定長的滑動窗口的算法性能隨著窗口的增加線性下降。整體上看，各個清洗算法對噪聲不是很敏感，隨著噪聲的增加，平均時延緩慢增加。這是因為噪聲的增加使得各個正確標簽數據在緩沖區停留了較長時間，導致了時延的增加，但總的處理時間變化不大。

3.6 數據的冗余清洗實驗

本實驗主要考察該算法對標簽的冗余數據的清洗結果，并對清洗前和清洗后的數據規模作對比。

按照上述方法產生標簽讀取記錄，將標簽到達率設置為10 tags/s，有效讀取時間閾值Tthreshold設為100 s，讀取次數閾值TagCntthreshold設為3次，依次按照100、1 000、5 000、10 000、50 000、100 000的規模生成原始數據集。考慮到噪聲對數據處理的效率影響相當小，因此本實驗設置噪聲比例為5%，運行結果如圖11和圖12所示。

圖11 清洗后數據集與原始數據集的規模對比

圖12 清洗后數據集與原始數據集的壓縮比

從實驗結果看，提出的數據清洗算法大大減少了原始數據中存在的冗余數據。當標簽數據規模只有100個元組時，清洗后數據仍然有93個元組，壓縮比僅為93%；隨著數據規模的增長，當數據規模達到10 000時，清洗后數據為4 320個，壓縮比為43.2%；當數據規模達到100 000時，清洗后的數據為19 001，壓縮比為19%。因此，可以得出結論：隨著規模的增長，數據的壓縮效果越來越好。實驗仿真結果符合預想效果。值得注意的是，具體數據壓縮比率取決于數據中冗余的比例，因此本實驗的結果只反映了平均情況下的實驗結果。

4 結 語

本文通過分析RFID數據特征，針對在海量標簽數據中存在的多讀、冗余讀現象，通過改進滑動窗口的數據清洗方法在處理效率方面的不足，提出了一種基于有限狀態機的清洗框架，設計了多階哈希表存儲歷史數據，大大提高了數據清洗的效率。