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

（1.貴州大學(xué) 教育部現(xiàn)代制造技術(shù)重點(diǎn)實(shí)驗(yàn)室，貴陽 550003；2.中國科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 6100413；3.貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴陽 550025）

0 引言

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

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

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

1 相關(guān)算法研究

1.1 自適應(yīng)滑動(dòng)窗口RFID數(shù)據(jù)清洗算法

SMURF算法中規(guī)定窗口大小為w，閱讀器在大小為wi個(gè)時(shí)段中檢測單標(biāo)簽i，在窗口的每個(gè)時(shí)段中，只有部分時(shí)段能讀到標(biāo)簽i，窗口中每個(gè)閱讀周期的平均閱讀率定為piavg。

針對單標(biāo)簽清洗，利用伯努利二項(xiàng)分布模型來處理數(shù)據(jù)。為了保證閱讀器讀到數(shù)據(jù)的完整性，要求窗口的大小能保證存在于標(biāo)簽閱讀區(qū)域內(nèi)的所有標(biāo)簽都被讀到的概率δ滿足理，SMURF算法規(guī)定標(biāo)簽發(fā)生動(dòng)態(tài)變化的條件為：簽閱讀出現(xiàn)的次數(shù)。

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

1.2 基于偽事件的RFID數(shù)據(jù)清洗方法

偽事件是一種人為定義的事件，以特定時(shí)間觸發(fā)特定動(dòng)作。將冗余讀設(shè)為偽事件，分別對各個(gè)偽事件設(shè)定閾值，判斷標(biāo)簽信息的讀入是否為偽事件。

針對冗余讀偽事件，設(shè)定閾值δ1，當(dāng)標(biāo)簽首次被發(fā)現(xiàn)，記該時(shí)刻為t，在時(shí)間區(qū)間[δ1,δ1+t]內(nèi)，若標(biāo)簽被重復(fù)讀取，則認(rèn)為是重復(fù)讀偽事件，不輸出該標(biāo)簽信息。該方法解決了傳統(tǒng)數(shù)據(jù)清洗方式會給系統(tǒng)帶來大量中間數(shù)據(jù)的問題，減少了緩存的開銷[10]。

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

2 自適應(yīng)時(shí)間閾值的標(biāo)簽數(shù)據(jù)過濾

2.1 改進(jìn)算法的思想

ATDCA結(jié)合時(shí)間窗模型和偽事件過濾模型，以偽事件過濾算法為基礎(chǔ)，通過設(shè)定事件過期時(shí)間閾值，過濾閱讀范圍內(nèi)的標(biāo)簽信息，觸發(fā)事件過期閾值根據(jù)閱讀范圍內(nèi)標(biāo)簽的存在狀態(tài)自適應(yīng)改變。

算法首先通過查詢緩存隊(duì)列中的標(biāo)簽信息，來判斷新閱讀產(chǎn)生的數(shù)據(jù)是否為冗余讀數(shù)據(jù)，從而實(shí)現(xiàn)閱讀范圍內(nèi)新標(biāo)簽的發(fā)現(xiàn)和信息輸出。在實(shí)際應(yīng)用中，大量已過期的標(biāo)簽信息占用大量的緩存空間，增加了查詢消耗。因此要求緩存隊(duì)列中的數(shù)據(jù)要實(shí)時(shí)更新。SMURF算法可以得到當(dāng)前時(shí)刻時(shí)間窗的長度，其長度根據(jù)讀卡器閱讀區(qū)域內(nèi)的標(biāo)簽數(shù)目變化而自適應(yīng)的變化，可以動(dòng)態(tài)的反應(yīng)當(dāng)前時(shí)刻閱讀區(qū)域內(nèi)的標(biāo)簽存在狀態(tài)，所以選擇自適應(yīng)時(shí)間窗的大小作為緩存隊(duì)列中標(biāo)簽信息過期的閾值。利用標(biāo)簽時(shí)間戳和閾值實(shí)現(xiàn)標(biāo)簽過期的判斷。

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

圖1 單緩存隊(duì)列中數(shù)據(jù)過濾

當(dāng)新的閱讀產(chǎn)生，查詢此時(shí)緩存隊(duì)列中的標(biāo)簽數(shù)目，若標(biāo)簽數(shù)目在閾值有效范圍內(nèi)，則不更新時(shí)間閾值。若標(biāo)簽的數(shù)目不在范圍內(nèi)，則觸發(fā)時(shí)間閾值更新，更新完成后，通過算并更新閾值。

2.2 改進(jìn)方法軟件實(shí)現(xiàn)

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

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

步驟1：讀寫器進(jìn)行新的閱讀，得到標(biāo)簽UID。

步驟2：系統(tǒng)緩存隊(duì)列中的標(biāo)簽數(shù)目是否在閾值有效范圍內(nèi)。若在有效范圍內(nèi)，轉(zhuǎn)至步驟4執(zhí)行，若不在有效范圍內(nèi)轉(zhuǎn)至步驟3執(zhí)行。

圖2 算法流程圖

步驟4：根據(jù)標(biāo)簽被讀取時(shí)刻的時(shí)間t和此時(shí)的時(shí)間閾值T計(jì)算出標(biāo)簽信息的預(yù)計(jì)過期時(shí)間Tend= t+T。

步驟5：將標(biāo)簽中記錄的UID與緩存隊(duì)列中的標(biāo)簽信息進(jìn)行對比，判斷標(biāo)簽信息是否已經(jīng)存在于緩存隊(duì)列當(dāng)中。若已存在則轉(zhuǎn)至步驟6執(zhí)行，若不存在則轉(zhuǎn)至步驟7執(zhí)行。

步驟6：將標(biāo)簽被讀到的次數(shù)Nt加1，更新標(biāo)簽的預(yù)計(jì)過期時(shí)間等相關(guān)信息，并且將該標(biāo)簽信息移至緩存隊(duì)列末尾，轉(zhuǎn)至步驟8執(zhí)行。

步驟7：將標(biāo)簽被讀到次數(shù)記為Nt 加1，并將該標(biāo)簽的相關(guān)信息插入到緩存隊(duì)列末尾，轉(zhuǎn)至步驟9。

步驟8：判斷標(biāo)簽被讀到的次數(shù)，若次數(shù)大于μ，認(rèn)為該標(biāo)簽信息為真實(shí)信息，將其輸出給上層模塊并且對其進(jìn)行標(biāo)記，轉(zhuǎn)至步驟9。

步驟9：更新緩存隊(duì)列，統(tǒng)計(jì)緩存隊(duì)列長度L并初始化計(jì)數(shù)值k=1，用以表示緩存隊(duì)列的第一個(gè)標(biāo)簽信息，轉(zhuǎn)至步驟10。

步驟10：將緩存隊(duì)列中第一個(gè)標(biāo)簽的預(yù)計(jì)過期時(shí)間與當(dāng)前時(shí)間相比對，若當(dāng)前時(shí)間已經(jīng)超出或者等于標(biāo)簽的預(yù)計(jì)過期時(shí)間，則認(rèn)為標(biāo)簽信息已經(jīng)過期，將其從緩存隊(duì)列中刪除，轉(zhuǎn)至步驟9。若沒有，則轉(zhuǎn)至步驟11。

步驟11：判斷讀操作是否停止，若停止，則結(jié)束數(shù)據(jù)清洗，若沒有停止，轉(zhuǎn)至步驟1繼續(xù)執(zhí)行清洗操作。

2.3 改進(jìn)方法的硬件實(shí)現(xiàn)

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

圖3 清洗過濾器結(jié)構(gòu)圖

其中時(shí)鐘用于獲取當(dāng)前時(shí)間t，計(jì)算器用于計(jì)算此刻時(shí)間窗長度T，并且得出標(biāo)簽預(yù)計(jì)過期時(shí)間。比較器1用于判斷標(biāo)簽是否已經(jīng)在緩存隊(duì)列當(dāng)中，從而實(shí)現(xiàn)對緩存隊(duì)列的添加。比較器2用于判斷標(biāo)簽是否是真實(shí)數(shù)據(jù)，過濾多讀數(shù)據(jù)和臟數(shù)據(jù)。比較器3用于判斷標(biāo)簽是否過期，從而刪除隊(duì)列中的冗余信息。

3 仿真結(jié)果及分析

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

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

圖4 與SMURF算法比較

而對于偽事件標(biāo)簽清洗方法，其發(fā)出的標(biāo)簽信息量由時(shí)間窗值T與時(shí)間閾值T '之比還有標(biāo)簽的變化率θ有關(guān)，

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

圖5 與偽事件標(biāo)簽清洗比較

4 結(jié)束語

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

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

[2] 丁帥, 楊善林.基于.NET精簡框架的嵌入式RFID服務(wù)組件[J].計(jì)算機(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] 陳金花, 劉國輝, 吳軍, 周鑫.數(shù)據(jù)過濾在RFID系統(tǒng)中的應(yīng)用[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數(shù)據(jù)清洗方法[J].計(jì)算機(jī)研究與發(fā)展, 2009, 46 (z2): 270-274.

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

[12] 王文闖, 鳳宇.基于動(dòng)態(tài)時(shí)間窗的射頻識別中間件數(shù)據(jù)過濾算法[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.