王 健，樂(lè)嘉錦

1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，鄭州 450046

2.東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620

無(wú)線射頻識(shí)別（radio frequency identification，RFID）技術(shù)具有非接觸識(shí)別、穿透力強(qiáng)、識(shí)別速度快、自動(dòng)檢測(cè)、節(jié)省人力等眾多優(yōu)點(diǎn)，已經(jīng)廣泛應(yīng)用于一些需要采集[1]、監(jiān)控[2]或追蹤[3]信息的領(lǐng)域中，例如倉(cāng)儲(chǔ)物流運(yùn)輸、門(mén)禁考勤、固定資產(chǎn)管理、車(chē)輛識(shí)別、行李安檢、醫(yī)療信息追蹤、軍事國(guó)防安全等[4]。伴隨著廣泛應(yīng)用而來(lái)的是對(duì)高數(shù)據(jù)質(zhì)量的迫切需求。

盡管RFID 具有很多優(yōu)點(diǎn)，但是在面對(duì)水和金屬時(shí)穿透能力相對(duì)較弱，易受無(wú)線電信號(hào)干擾，這種情況下RFID標(biāo)簽的識(shí)別準(zhǔn)確率就大大降低，造成數(shù)據(jù)的不可靠性[5]。另外，RFID 標(biāo)簽的長(zhǎng)期停留、多讀寫(xiě)器的部署、為提高識(shí)別率而采取的多個(gè)同一標(biāo)簽的粘貼，在系統(tǒng)采集數(shù)據(jù)[6]時(shí)也會(huì)造成數(shù)據(jù)的冗余。在數(shù)據(jù)傳輸過(guò)程中，由于網(wǎng)絡(luò)延遲等因素，收集到的數(shù)據(jù)還會(huì)產(chǎn)生亂序的問(wèn)題。因此，RFID 數(shù)據(jù)的不可靠性主要包含數(shù)據(jù)的漏讀、多讀/交叉讀、冗余、亂序等[7]。如果應(yīng)用端直接使用RFID原始數(shù)據(jù)，會(huì)造成很多問(wèn)題。因此，預(yù)處理系統(tǒng)一般會(huì)對(duì)RFID原始數(shù)據(jù)進(jìn)行清洗，以提高RFID數(shù)據(jù)的質(zhì)量。

在對(duì)RFID 原始數(shù)據(jù)清洗的過(guò)程中，存在著很多的挑戰(zhàn)。這些挑戰(zhàn)一般是由RFID 數(shù)據(jù)流的特點(diǎn)和應(yīng)用端的需求帶來(lái)的[8]。RFID數(shù)據(jù)是突發(fā)產(chǎn)生的，因此造成的挑戰(zhàn)之一是其產(chǎn)生和到達(dá)速度快。只要RFID 數(shù)據(jù)在采集設(shè)備（讀寫(xiě)器）的讀寫(xiě)范圍內(nèi)，就會(huì)產(chǎn)生數(shù)據(jù)，造成的挑戰(zhàn)之二是數(shù)據(jù)流的總量是無(wú)限的。由于RFID 數(shù)據(jù)在傳輸過(guò)程中遇到不同的網(wǎng)絡(luò)狀況，造成的挑戰(zhàn)之三是數(shù)據(jù)到達(dá)次序不受應(yīng)用約束。查詢等應(yīng)用一般在內(nèi)存中完成，且內(nèi)存容量有限，造成的挑戰(zhàn)之四是除非刻意保存，一般每個(gè)數(shù)據(jù)只處理一次。RFID標(biāo)簽一般貼于位置經(jīng)常變動(dòng)的物品上，造成的挑戰(zhàn)之五是數(shù)據(jù)時(shí)效性強(qiáng)，必須在很短時(shí)間內(nèi)處理。

RFID 數(shù)據(jù)清洗一度成為最流行的研究熱點(diǎn)之一，研究者們從各個(gè)方面出發(fā)，提出了許多高質(zhì)量的方法。為了方便廣大研究者借鑒和使用相關(guān)方法，很有必要對(duì)RFID 數(shù)據(jù)清洗技術(shù)進(jìn)行綜述。文中介紹了RFID 數(shù)據(jù)清洗問(wèn)題的描述，給出了RFID 數(shù)據(jù)清洗研究的挑戰(zhàn)，整理了典型的數(shù)據(jù)集和評(píng)價(jià)標(biāo)準(zhǔn)，梳理了現(xiàn)有的RFID數(shù)據(jù)清洗技術(shù)，并從漏讀數(shù)據(jù)處理[9-10]、多讀數(shù)據(jù)處理[9]、冗余數(shù)據(jù)處理[9]、亂序數(shù)據(jù)處理[11]、RFID 系統(tǒng)應(yīng)用[9-10]等方面對(duì)RFID 數(shù)據(jù)清洗技術(shù)的現(xiàn)有工作進(jìn)行了詳細(xì)的歸納和總結(jié)，最后對(duì)RFID數(shù)據(jù)清洗上可能的研究方向進(jìn)行了展望。

1 RFID系統(tǒng)與數(shù)據(jù)清洗問(wèn)題描述

1.1 RFID系統(tǒng)

RFID 系統(tǒng)通常包含以下幾部分：RFID 標(biāo)簽、RFID 讀寫(xiě)器、RFID 中間件和后端應(yīng)用系統(tǒng)[12]。其中，RFID標(biāo)簽由芯片和標(biāo)簽天線或線圈組成，通過(guò)電感耦合或電磁反射原理與讀寫(xiě)器進(jìn)行通信。RFID讀寫(xiě)器是讀取/寫(xiě)入標(biāo)簽信息的設(shè)備。天線可以內(nèi)置在RFID讀寫(xiě)器中，也可以通過(guò)同軸電纜與RFID讀寫(xiě)器天線接口相連。RFID 中間件負(fù)責(zé)數(shù)據(jù)清洗[13-14]和復(fù)雜事件處理等工作。圖1為RFID系統(tǒng)的示意圖。

圖1 RFID系統(tǒng)Fig.1 RFID system

RFID 標(biāo)簽分為三種類(lèi)型：無(wú)源標(biāo)簽、半無(wú)/有源標(biāo)簽和有源標(biāo)簽[15]。其中源的含義是供電電源，這種電源一般具有體積小、使用時(shí)間長(zhǎng)等特點(diǎn)。

RFID技術(shù)的基本原理是：無(wú)源標(biāo)簽進(jìn)入RFID讀寫(xiě)器的讀寫(xiě)范圍內(nèi)時(shí)，接收讀寫(xiě)器發(fā)出的電磁信號(hào)，接著自身產(chǎn)生感應(yīng)電流，然后憑借感應(yīng)電流產(chǎn)生的能量將存儲(chǔ)于芯片上的信息傳遞給讀寫(xiě)器；若為有源標(biāo)簽，其不需要借助讀寫(xiě)器的信號(hào)來(lái)產(chǎn)生能量，因?yàn)槠渥陨韼в须娫?，所以它?huì)主動(dòng)發(fā)出某一頻率的電磁波，這樣讀寫(xiě)器讀取電磁波并解碼，然后送到中央系統(tǒng)進(jìn)行后續(xù)的數(shù)據(jù)處理，最后將信息傳遞給用戶或者應(yīng)用系統(tǒng)[7]。

1.2 RFID數(shù)據(jù)清洗問(wèn)題描述

RFID 數(shù)據(jù)清洗問(wèn)題主要包括數(shù)據(jù)的漏讀、數(shù)據(jù)的多讀、數(shù)據(jù)的冗余、數(shù)據(jù)的亂序等。下面給出相關(guān)定義與描述。

定義1（數(shù)據(jù)的漏讀） 也稱(chēng)假陰性讀數(shù)（false negative readings）[16-18]，是指某個(gè)或者某些標(biāo)簽實(shí)際上已經(jīng)處于RFID讀寫(xiě)器的讀取范圍內(nèi)，但是讀寫(xiě)器卻沒(méi)有產(chǎn)生相應(yīng)時(shí)間點(diǎn)或者時(shí)間段的有關(guān)此標(biāo)簽的數(shù)據(jù)。在RFID數(shù)據(jù)采集過(guò)程中，漏讀是一個(gè)常見(jiàn)的現(xiàn)象。產(chǎn)生漏讀的原因有：（1）當(dāng)許多標(biāo)簽同時(shí)被讀寫(xiě)器探測(cè)到的時(shí)候，無(wú)線電波的沖突和信號(hào)的干擾經(jīng)常出現(xiàn)，因此干擾了讀寫(xiě)器識(shí)別任何一個(gè)標(biāo)簽；（2）水、金屬或者無(wú)線電波的干擾?，F(xiàn)有的研究與實(shí)驗(yàn)表明，在部署有RFID 設(shè)備的應(yīng)用中，電子標(biāo)簽的識(shí)別率通常在60%到70%之間，即超過(guò)30%的數(shù)據(jù)被常規(guī)地丟棄掉。圖2 給出了一個(gè)數(shù)據(jù)漏讀的示意圖。在一個(gè)貨架上放滿了帶有標(biāo)簽的物品，RFID 讀寫(xiě)器讀取到了大部分標(biāo)簽的數(shù)據(jù)，只有個(gè)別數(shù)據(jù)沒(méi)讀到，這就是RFID數(shù)據(jù)漏讀現(xiàn)象。

圖2 RFID數(shù)據(jù)的漏讀示意圖Fig.2 Example of RFID false negative readings

定義2（數(shù)據(jù)的多讀） 也稱(chēng)假陽(yáng)性讀數(shù)（false positive readings）、交叉讀（cross readings）或噪聲（noise）[16-17]，是指RFID 讀寫(xiě)器不僅讀取到了期望的標(biāo)簽，而且也讀取到了不期望的標(biāo)簽。這種現(xiàn)象可以歸結(jié)于以下幾種形式：（1）位于RFID 正常讀取范圍之外的標(biāo)簽被讀取到。比如，當(dāng)在采集一個(gè)箱子內(nèi)的標(biāo)簽數(shù)據(jù)過(guò)程中，讀寫(xiě)器可能從鄰近的箱子內(nèi)讀到了標(biāo)簽。（2）讀寫(xiě)器所處環(huán)境中的不確定因素，比如，某讀寫(xiě)器產(chǎn)生并傳送非其探測(cè)范圍內(nèi)的標(biāo)簽中的數(shù)據(jù)。圖3 給出了一個(gè)數(shù)據(jù)多讀的示意圖。交叉區(qū)域內(nèi)被兩個(gè)讀寫(xiě)器都捕捉到的數(shù)據(jù)稱(chēng)為多讀數(shù)據(jù)（交叉讀數(shù)據(jù)）。

圖3 RFID數(shù)據(jù)的多讀示意圖Fig.3 Example of RFID false positive readings

定義3（數(shù)據(jù)的冗余） 英文為duplicated readings[16-17]，是由以下幾種原因引起的：（1）標(biāo)簽在一個(gè)讀寫(xiě)器探測(cè)范圍內(nèi)停留很長(zhǎng)時(shí)間，被讀寫(xiě)器讀取了許多次；（2）在一個(gè)大的區(qū)域或者長(zhǎng)距離的范圍內(nèi)部署了多個(gè)RFID讀寫(xiě)器，位于讀寫(xiě)器重疊區(qū)域的標(biāo)簽被讀取了多次；（3）為了提高讀取精度，許多帶有同一標(biāo)識(shí)的標(biāo)簽粘貼于同一物品上，因此產(chǎn)生冗余現(xiàn)象。圖4給出一個(gè)數(shù)據(jù)冗余的示意圖。該圖含義是某個(gè)帶有RFID標(biāo)簽的數(shù)據(jù)在不同的n個(gè)狀態(tài)（比如不同位置、不同讀寫(xiě)器讀寫(xiě)）下產(chǎn)生了多個(gè)讀數(shù)，但是每個(gè)狀態(tài)下有許多冗余，只有每個(gè)狀態(tài)的第一個(gè)數(shù)據(jù)是有效的數(shù)據(jù)，其他的讀數(shù)可以丟棄。

圖4 RFID數(shù)據(jù)的冗余示意圖Fig.4 Example of RFID duplicated readings

定義4（數(shù)據(jù)的亂序） 英文為out-of-order readings[11]。由于不同網(wǎng)絡(luò)傳輸中的延遲、擁塞等情況，讀寫(xiě)器在工作過(guò)程中生成的原本產(chǎn)生時(shí)間戳較早但到達(dá)時(shí)間戳較晚或者原本產(chǎn)生時(shí)間戳較晚但到達(dá)時(shí)間戳較早等非順序到達(dá)。圖5 給出了一個(gè)數(shù)據(jù)亂序的示意圖。該圖含義是在t+1 到t+8 時(shí)刻數(shù)據(jù)1到8 依次產(chǎn)生，然而由于網(wǎng)絡(luò)延遲等原因經(jīng)過(guò)一定的傳輸時(shí)間，其到達(dá)次序就變得與產(chǎn)生次序完全不一樣。

圖5 RFID數(shù)據(jù)的亂序示意圖Fig.5 Example of RFID out-of-order readings

定義5（RFID 數(shù)據(jù)清洗） 是對(duì)讀寫(xiě)器在工作過(guò)程中產(chǎn)生的漏讀、多讀、冗余讀、亂序到達(dá)數(shù)據(jù)進(jìn)行填補(bǔ)、去偽存真、約減、排序等工作的過(guò)程。

2 研究挑戰(zhàn)

RFID 數(shù)據(jù)屬于流數(shù)據(jù)中的一種，其具有流數(shù)據(jù)的特點(diǎn)[8]，這些特點(diǎn)也就形成了若干研究挑戰(zhàn)。下面介紹一下比較重要的挑戰(zhàn)。

研究挑戰(zhàn)1：數(shù)據(jù)源源不斷產(chǎn)生，規(guī)模之大難以數(shù)計(jì)。由于RFID 技術(shù)為感知識(shí)別，在RFID 讀寫(xiě)器開(kāi)啟的情況下，瞬間可以采集多次，比如1 s可以采集1 000次。同時(shí)RFID讀寫(xiě)器是分布式部署的，這樣同時(shí)采集多個(gè)帶有RFID標(biāo)簽的物品，會(huì)形成猶如洪水般的數(shù)據(jù)流，并源源不斷地流向應(yīng)用端。

研究挑戰(zhàn)2：數(shù)據(jù)到達(dá)速率極快。RFID 技術(shù)感知式采集，采集到的數(shù)據(jù)通過(guò)無(wú)線網(wǎng)、有線網(wǎng)、局域網(wǎng)、廣電網(wǎng)等不同網(wǎng)絡(luò)傳遞到應(yīng)用端，同時(shí)多個(gè)網(wǎng)絡(luò)傳輸，因此RFID數(shù)據(jù)流的到達(dá)極快。

研究挑戰(zhàn)3：數(shù)據(jù)到達(dá)次序不受應(yīng)用約束。RFID數(shù)據(jù)來(lái)自周?chē)h(huán)境，隨機(jī)發(fā)生，你追我趕，多路并發(fā)傳播，同時(shí)也受網(wǎng)絡(luò)狀況的影響，到達(dá)的次序與產(chǎn)生時(shí)的順序完全不同。由于不以任何事物的意志為轉(zhuǎn)移，其到達(dá)次序也難以預(yù)測(cè)。

研究挑戰(zhàn)4：除非刻意保存，每個(gè)數(shù)據(jù)都只能“看”一次。由于RFID數(shù)據(jù)規(guī)模巨大，受處理機(jī)內(nèi)存大小的限制，該數(shù)據(jù)無(wú)法全部容納于內(nèi)存之中。為了快速處理這些數(shù)據(jù)，只能掃描一遍。在掃描一遍數(shù)據(jù)情況下，如何完成相關(guān)工作時(shí)間緊迫。

研究挑戰(zhàn)5：數(shù)據(jù)時(shí)效性高，價(jià)值轉(zhuǎn)瞬即逝。由于RFID 數(shù)據(jù)具有獨(dú)特的時(shí)空語(yǔ)義性，帶有RFID 標(biāo)簽的物品位置也是在不斷變換的，比如帶有RFID標(biāo)簽的書(shū)籍，可能剛才還在書(shū)架上，短時(shí)間內(nèi)就有可能被學(xué)生借走，出現(xiàn)在借閱處。如果為了實(shí)時(shí)監(jiān)控每一本書(shū)籍的情況，就需要不停地處理帶有時(shí)空信息的RFID數(shù)據(jù)，距離當(dāng)前時(shí)刻越近的數(shù)據(jù)越具有應(yīng)用價(jià)值。

3 數(shù)據(jù)集與評(píng)價(jià)標(biāo)準(zhǔn)

本章將會(huì)介紹典型的RFID 數(shù)據(jù)集以及RFID 數(shù)據(jù)清洗的評(píng)價(jià)標(biāo)準(zhǔn)。

3.1 數(shù)據(jù)集

高質(zhì)量與合適場(chǎng)景的數(shù)據(jù)集對(duì)RFID 數(shù)據(jù)清洗方法的驗(yàn)證與評(píng)估非常重要。本節(jié)總結(jié)了兩個(gè)廣泛使用的RFID數(shù)據(jù)集。表1給出了相關(guān)數(shù)據(jù)集的基本信息，比如數(shù)據(jù)集名稱(chēng)、年份、來(lái)源、描述、文件數(shù)量、網(wǎng)址等。

表1 常見(jiàn)RFID數(shù)據(jù)集Table 1 Typical RFID datasets

hope/amd 數(shù)據(jù)集是從2008 年7 月18 日至20 日舉行的第七屆HOPE（地球上的黑客）會(huì)議上收集的RFID跟蹤數(shù)據(jù)。與會(huì)者佩戴了RFID徽章，通過(guò)該徽章可以在整個(gè)會(huì)議空間內(nèi)唯一地識(shí)別和跟蹤他們。貢獻(xiàn)者是Aestetix和Christopher Petro。2008年8月7日上傳于CRAWDAD（community resource for archiving wireless data at Dartmouth）網(wǎng)站，該網(wǎng)站是達(dá)特茅斯的無(wú)線數(shù)據(jù)存檔社區(qū)資源。網(wǎng)址為https://crawdad.org/hope/amd/20080807。數(shù)據(jù)集中有13個(gè)文件，總數(shù)據(jù)量約為25 MB，包含了與會(huì)者參會(huì)期間的位置信息。

hope/nh_amd 數(shù)據(jù)集是從2010 年7 月18 日至20日舉行的HOPE（地球上的黑客）會(huì)議上收集的RFID跟蹤數(shù)據(jù)。目的與hope/amd數(shù)據(jù)集一致。貢獻(xiàn)者是Travis Goodspeed 和Nathaniel Filardo。2010 年7 月18 日上傳于CRAWDAD 網(wǎng)站。具體下載地址為https://crawdad.org/hope/nh_amd/20100718。數(shù)據(jù)集中有33個(gè)文件，且每個(gè)文件的數(shù)據(jù)量都接近100 MB，總的數(shù)據(jù)量約為3.1 GB，同樣包含了與會(huì)者參會(huì)期間的位置信息。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

由于本研究方向的評(píng)價(jià)標(biāo)準(zhǔn)表達(dá)形式多樣，不能一一列舉，這里只給出具有代表性的評(píng)價(jià)標(biāo)準(zhǔn)。

精確度指的是清洗后的數(shù)據(jù)Dc與真正數(shù)據(jù)Dr的交集占真正數(shù)據(jù)Dr的比重。定義如式（1）所示：

數(shù)據(jù)壓縮率指的是原始數(shù)據(jù)Draw與數(shù)據(jù)清洗過(guò)后的數(shù)據(jù)Dc的數(shù)據(jù)量的差值占真正數(shù)據(jù)Dr的比重。定義如式（2）所示：

吞吐量指的是處理過(guò)的數(shù)據(jù)量|Draw|與所用處理時(shí)間T的比值。定義如式（3）所示：

運(yùn)行時(shí)間是指算法運(yùn)行穩(wěn)定時(shí)處理數(shù)據(jù)流所需要的時(shí)間。

4 RFID數(shù)據(jù)清洗

本章主要從漏讀數(shù)據(jù)清洗、多讀數(shù)據(jù)清洗、冗余數(shù)據(jù)清洗、亂序數(shù)據(jù)處理、RFID系統(tǒng)應(yīng)用等方面來(lái)總結(jié)現(xiàn)有方法的基本思想、優(yōu)勢(shì)、局限和適用場(chǎng)景。

4.1 漏讀數(shù)據(jù)清洗

Jeffery等人[19]提出一種稱(chēng)為ESP（extensible receptor stream processing）的數(shù)據(jù)清洗方法。其在時(shí)間滑動(dòng)窗口中平滑RFID數(shù)據(jù)，并將多個(gè)讀寫(xiě)器分組在一個(gè)空間粒度中，以糾正漏讀數(shù)據(jù)（亦稱(chēng)假陰性數(shù)據(jù)或誤報(bào)）并去除異常值。然而，很難確定不同RFID 數(shù)據(jù)的最佳窗口大小，尤其是在移動(dòng)環(huán)境[20]中。在這樣的環(huán)境中，重要的是確保兩個(gè)應(yīng)用需求（完整性、標(biāo)簽動(dòng)態(tài)）之間的平衡。完整性：確保所有在讀寫(xiě)器范圍內(nèi)的RFID標(biāo)簽都被檢測(cè)到。標(biāo)簽動(dòng)態(tài)：捕獲標(biāo)簽在讀寫(xiě)器檢測(cè)范圍內(nèi)進(jìn)出的動(dòng)態(tài)。通過(guò)設(shè)置較大的窗口大小來(lái)消除數(shù)據(jù)的漏讀，可以確保數(shù)據(jù)的完整性，但它們?cè)跈z測(cè)標(biāo)簽躍遷時(shí)效率不高，還引入了多讀數(shù)據(jù)（假陽(yáng)性）。然而，窗口大小設(shè)置較小時(shí)能夠檢測(cè)到RFID標(biāo)簽的移動(dòng)，但不能補(bǔ)償漏讀數(shù)據(jù)。

Jeffery 等人[17]提出一種自適應(yīng)滑動(dòng)窗口清洗方法，稱(chēng)為不可靠RFID 數(shù)據(jù)的統(tǒng)計(jì)平滑（statistical smoothing for unreliable RFID data，SMURF）。SMURF把RFID流數(shù)據(jù)看成統(tǒng)計(jì)學(xué)中的隨機(jī)事件，并在系統(tǒng)的整個(gè)生命周期內(nèi)不斷地根據(jù)流數(shù)據(jù)的統(tǒng)計(jì)學(xué)特點(diǎn)自適應(yīng)調(diào)整窗口大小（不會(huì)向應(yīng)用程序公開(kāi)平滑窗口參數(shù)），從一定程度上提高了漏讀數(shù)據(jù)填補(bǔ)的精確度。然而當(dāng)監(jiān)控對(duì)象在某邏輯區(qū)域內(nèi)的讀數(shù)完全丟失時(shí)，該方法的清洗效果較差。

Massawe 等人[21]采用SMURF[17]中提出的統(tǒng)計(jì)方法，給出了一種稱(chēng)為窗口子范圍躍遷檢測(cè)（window subrange transition detection，WSTD）的RFID 數(shù)據(jù)流自適應(yīng)清洗方案。其具有更高效的標(biāo)簽遷移檢測(cè)機(jī)制。WSTD能夠調(diào)整窗口大小，以應(yīng)對(duì)環(huán)境變化導(dǎo)致的標(biāo)簽和讀寫(xiě)器整體性能波動(dòng)，同時(shí)相對(duì)準(zhǔn)確地檢測(cè)遷移時(shí)間點(diǎn)。然而，由于使用的窗口較小，它會(huì)產(chǎn)生更多的漏讀數(shù)據(jù)。

現(xiàn)有的清洗技術(shù)專(zhuān)注于設(shè)計(jì)在各種條件下都能很好工作的精確方法，但忽視了在可能有數(shù)千個(gè)讀寫(xiě)器和數(shù)百萬(wàn)個(gè)標(biāo)簽的應(yīng)用場(chǎng)景的高昂開(kāi)銷(xiāo)。Gonzalez 等人[22]提出了一個(gè)清洗框架，該框架采用RFID 數(shù)據(jù)集和一系列清洗方法以及相關(guān)開(kāi)銷(xiāo)，并通過(guò)確定廉價(jià)方法適用的條件，得出一個(gè)清洗計(jì)劃，進(jìn)而優(yōu)化整體清洗開(kāi)銷(xiāo)。該框架所考慮的開(kāi)銷(xiāo)主要包括三方面：一是機(jī)器學(xué)習(xí)中的訓(xùn)練開(kāi)銷(xiāo)；二是存儲(chǔ)與運(yùn)行開(kāi)銷(xiāo)；三是分類(lèi)錯(cuò)誤時(shí)所需要的開(kāi)銷(xiāo)。具體的清洗方法主要是基于滑動(dòng)窗口的平滑過(guò)濾填補(bǔ)方法，還可以是用戶自定義方法，其中窗口包括靜態(tài)和動(dòng)態(tài)窗口。文中還介紹了基于決策樹(shù)和貝葉斯的數(shù)據(jù)清洗方法，根據(jù)不同數(shù)據(jù)特征進(jìn)行最優(yōu)清洗策略，以達(dá)到總體開(kāi)銷(xiāo)最小。該方法只解決了漏讀現(xiàn)象，如何解決多讀、冗余、亂序到達(dá)等問(wèn)題，還有待進(jìn)一步研究。該方法的優(yōu)點(diǎn)在于考慮了觀測(cè)值和估計(jì)值，然而這些估計(jì)值與觀測(cè)值的關(guān)系是由歷史數(shù)據(jù)集得到的，不能動(dòng)態(tài)更新，因而對(duì)動(dòng)態(tài)標(biāo)簽的清洗結(jié)果也不十分理想。

Baba等人[23]重點(diǎn)研究了原始室內(nèi)RFID跟蹤[24]數(shù)據(jù)中的漏讀現(xiàn)象。其研究有限制，即室內(nèi)空間數(shù)據(jù)，有限制的同時(shí)還可以利用時(shí)空約束進(jìn)行數(shù)據(jù)清洗。其次，利用概率距離感知圖模型[25]來(lái)識(shí)別和填補(bǔ)漏讀數(shù)據(jù)。另外，該方案還可以應(yīng)用于其他類(lèi)型的符號(hào)化室內(nèi)跟蹤數(shù)據(jù)的清洗，例如藍(lán)牙跟蹤數(shù)據(jù)。該方法的優(yōu)點(diǎn)是利用了時(shí)空約束信息，應(yīng)用領(lǐng)域較廣，但局限于室內(nèi)物品產(chǎn)生的數(shù)據(jù)。

Gu等人[26]通過(guò)有效維護(hù)和分析監(jiān)控對(duì)象的相關(guān)性，提出了RFID漏讀數(shù)據(jù)的填補(bǔ)模型。監(jiān)測(cè)對(duì)象之間的時(shí)空相關(guān)性用于填補(bǔ)漏讀數(shù)據(jù)。突破了大多數(shù)RFID數(shù)據(jù)清洗算法只是根據(jù)獨(dú)立監(jiān)測(cè)對(duì)象的歷史讀數(shù)來(lái)填補(bǔ)缺失的讀數(shù)的情況。

在深入分析RFID對(duì)象[27]的關(guān)鍵特征之后，Xie等人[28]提出一種用于高效處理不確定RFID 數(shù)據(jù)的框架，并支持各種查詢和跟蹤RFID 對(duì)象。特別地，提出了一種自適應(yīng)清洗方法，根據(jù)不確定數(shù)據(jù)的不同速率調(diào)整平滑窗口的大小，采用不同的策略處理不確定數(shù)據(jù)，并根據(jù)不確定數(shù)據(jù)出現(xiàn)位置區(qū)分不同類(lèi)型的數(shù)據(jù)。還提出一種路徑編碼方案，通過(guò)聚合路徑序列、位置和時(shí)間間隔來(lái)顯著壓縮海量數(shù)據(jù)。該方法的優(yōu)點(diǎn)在于自適應(yīng)調(diào)整窗口大小，融入了時(shí)空信息，考慮了群體和單個(gè)物體的運(yùn)動(dòng)。局限在于規(guī)則設(shè)置不合理、不完整等都會(huì)影響清洗效果。

Baba 等人[29-30]提出一種稱(chēng)為IR-MHMM（indoor RFID multi-variate hidden Markov model）的數(shù)據(jù)清洗方法。該方法是一種基于學(xué)習(xí)的數(shù)據(jù)清洗方法，可以應(yīng)對(duì)RFID源數(shù)據(jù)中存在噪聲（多讀、交叉讀數(shù)）和不完整性（漏讀）的問(wèn)題。與現(xiàn)有方法不同，該方法不需要關(guān)于室內(nèi)空間和RFID 閱讀器部署的時(shí)空特性的詳細(xì)先驗(yàn)知識(shí)。該方法只需要有關(guān)RFID 部署的最少信息（室內(nèi)拓?fù)?、設(shè)備部署），就可以從原始RFID 數(shù)據(jù)中學(xué)習(xí)相關(guān)知識(shí)，并使用它來(lái)清洗數(shù)據(jù)。該方法的優(yōu)勢(shì)是不需要關(guān)于室內(nèi)空間和RFID 閱讀器部署的時(shí)空特性的先驗(yàn)知識(shí)，只需要少量RFID部署信息。然而，局限于室內(nèi)物品產(chǎn)生的數(shù)據(jù)，局限于馬爾可夫模型。

現(xiàn)有RFID 漏讀數(shù)據(jù)填補(bǔ)方法以原始讀數(shù)為粒度，在此基礎(chǔ)上進(jìn)行窗口平滑操作，其會(huì)填補(bǔ)許多冗余數(shù)據(jù)。在多邏輯區(qū)域參與的場(chǎng)景中，填補(bǔ)準(zhǔn)確度較差。為了改變上述狀況，谷峪等人[31]首次將RFID數(shù)據(jù)從數(shù)據(jù)層抽象到邏輯區(qū)域?qū)幼鳛樘幚淼牧６?，提? 種基于動(dòng)態(tài)概率路徑事件模型的數(shù)據(jù)填補(bǔ)算法，通過(guò)挖掘已知的區(qū)域事件的順序相關(guān)性來(lái)對(duì)后續(xù)發(fā)生的事件進(jìn)行判斷和填補(bǔ)。該方法的優(yōu)勢(shì)在于對(duì)漏讀數(shù)據(jù)進(jìn)行了填補(bǔ)，并考慮了實(shí)時(shí)性、準(zhǔn)確性和維護(hù)代價(jià)等因素。局限在于未考慮包含相同的區(qū)域事件問(wèn)題；未考慮依次經(jīng)過(guò)多個(gè)邏輯區(qū)域時(shí)，每個(gè)邏輯停留時(shí)間的相關(guān)性。

為了同時(shí)解決RFID 數(shù)據(jù)采集過(guò)程中存在的漏讀、多讀和冗余問(wèn)題，Jiang等人[32]探索了利用通信信息進(jìn)行RFID 數(shù)據(jù)清洗，并使RFID 讀寫(xiě)器在早期階段產(chǎn)生更少的臟數(shù)據(jù)。首先，設(shè)計(jì)了一個(gè)讀者通信協(xié)議，以有效地利用讀者之間的通信信息。然后，提出了帶參數(shù)的單元事件序列樹(shù)。最后，提出了三種新的RFID 數(shù)據(jù)清洗方法，分別用于減少重復(fù)、消除誤報(bào)和填補(bǔ)缺失數(shù)據(jù)。該方法有一個(gè)假設(shè)，即讀寫(xiě)器之間可以相互通信，但是實(shí)際情況還有所差別，也許在未來(lái)是可行的。

在很多RFID 監(jiān)控應(yīng)用中，監(jiān)控物體都是以動(dòng)態(tài)變化的小組為單位進(jìn)行活動(dòng)的。谷峪等人[33]通過(guò)定義關(guān)聯(lián)度和動(dòng)態(tài)聚簇對(duì)各個(gè)RFID 監(jiān)控物體所在的小組進(jìn)行動(dòng)態(tài)的分析[34]，并在此基礎(chǔ)上定義了一套關(guān)聯(lián)度維護(hù)和數(shù)據(jù)清洗的模型和算法，通過(guò)壓縮圖模型，提出了基于分裂重組思想的鏈模型關(guān)聯(lián)度維護(hù)策略，提高了維護(hù)的時(shí)空效率。該方法的不足是：當(dāng)邏輯上的小組頻繁分裂重組時(shí)，性能會(huì)大大降低。

Xie等人[35]考慮如何有效地識(shí)別移動(dòng)輸送機(jī)上的標(biāo)簽?？紤]到現(xiàn)實(shí)環(huán)境中的路徑丟失和多徑效應(yīng)等情況，研究者首先提出了一個(gè)RFID標(biāo)簽識(shí)別的概率模型?；谠撃Ｐ?，根據(jù)輸送機(jī)上的固定路徑移動(dòng)，提出了識(shí)別移動(dòng)RFID 標(biāo)簽的有效解決方案。該方法的優(yōu)勢(shì)在于考慮概率傳播。局限在于事先設(shè)定好路徑，超出該路徑范圍，處理效果不確定。

現(xiàn)有的工作主要集中在靜態(tài)環(huán)境中的RFID 數(shù)據(jù)清洗（例如庫(kù)存檢查）。為了補(bǔ)充現(xiàn)有方法的不足，Zhao 等人[36]提出一種移動(dòng)環(huán)境中目標(biāo)跟蹤RFID數(shù)據(jù)的清洗方法。首先提出了一個(gè)移動(dòng)環(huán)境中目標(biāo)跟蹤的概率模型。同時(shí)，設(shè)計(jì)了一種基于貝葉斯推理的方法，用于使用該模型清洗RFID數(shù)據(jù)。為了從運(yùn)動(dòng)分布中采集數(shù)據(jù)，設(shè)計(jì)了一種順序采樣器，該采樣器能夠以高精度和高效率的方式清洗RFID 數(shù)據(jù)。該方法的優(yōu)勢(shì)是適用于漏讀率比較高的移動(dòng)環(huán)境，利用了物品之間的時(shí)空關(guān)聯(lián)。局限在于概率計(jì)算來(lái)自于歷史數(shù)據(jù)。

Fazzinga等人[37]提出了一種離線清洗技術(shù)，用于將RFID 跟蹤的移動(dòng)物體產(chǎn)生的讀數(shù)轉(zhuǎn)換為地圖上的位置。它包含一個(gè)基于網(wǎng)格的雙向過(guò)濾方案，其中嵌入了一個(gè)用于解決缺失檢測(cè)（漏讀）的采樣策略。首先按時(shí)間順序處理讀數(shù)：在每個(gè)時(shí)間點(diǎn)t，根據(jù)該時(shí)刻產(chǎn)生的位置信息與前一時(shí)間點(diǎn)t-1 過(guò)濾后的位置的可達(dá)性進(jìn)行過(guò)濾。然后，對(duì)經(jīng)過(guò)第一次濾波后的位置進(jìn)行重新過(guò)濾，并按相反順序應(yīng)用相同的方案。隨著兩個(gè)階段的進(jìn)行，在每個(gè)時(shí)間點(diǎn)t逐步評(píng)估每個(gè)候選位置的概率。該概率集合了過(guò)去、未來(lái)、實(shí)際位置的概率。在第一個(gè)過(guò)濾階段的某些步驟中進(jìn)行采樣，智能地減少在下一步被視為候選位置的單元數(shù)量，因?yàn)樗鼈兊臄?shù)量在連續(xù)缺失檢測(cè)（漏讀）的情況下會(huì)急劇增加。該方法能做到很高的精確度，但是不能滿足實(shí)時(shí)的應(yīng)用需求，只能做后續(xù)離線分析[38]之用。

現(xiàn)有RFID 數(shù)據(jù)清洗方法主要針對(duì)靜態(tài)標(biāo)簽，沒(méi)有考慮動(dòng)態(tài)標(biāo)簽的特性。對(duì)于動(dòng)態(tài)標(biāo)簽進(jìn)出讀寫(xiě)器探測(cè)范圍的時(shí)間檢測(cè)存在延遲，清洗效果并不理想。針對(duì)RFID 數(shù)據(jù)流不準(zhǔn)確性和不能及時(shí)響應(yīng)標(biāo)簽躍遷的問(wèn)題，王妍等人[39]首次在RFID 數(shù)據(jù)流清洗中引入卡爾曼濾波，提出了一種稱(chēng)為KAL-RFID（Kalman radio frequency identification）的數(shù)據(jù)清洗方法。該方法通過(guò)時(shí)間更新和測(cè)量更新形成自回歸逼近真實(shí)值，從而改善了由滑動(dòng)窗口引發(fā)的漏讀和多讀問(wèn)題。該方法還可以及時(shí)檢測(cè)標(biāo)簽發(fā)生躍遷的時(shí)間，避免現(xiàn)有清洗方法在動(dòng)態(tài)標(biāo)簽離開(kāi)閱讀器時(shí)易產(chǎn)生的多讀現(xiàn)象和對(duì)標(biāo)簽發(fā)生躍遷的時(shí)間響應(yīng)延遲問(wèn)題，從而提高了清洗效率。該方法解決了單個(gè)讀寫(xiě)器的漏讀、多讀數(shù)據(jù)的問(wèn)題，以及動(dòng)態(tài)標(biāo)簽躍遷產(chǎn)生的延遲問(wèn)題。

表2給出了幾種典型的RFID漏讀數(shù)據(jù)清洗方法的對(duì)比，包括分類(lèi)、子類(lèi)、代表性工作、優(yōu)勢(shì)、局限、適用場(chǎng)景等內(nèi)容。

表2 典型RFID漏讀數(shù)據(jù)清洗方法對(duì)比Table 2 Comparison of methods of RFID false negative reading cleaning

4.2 多讀數(shù)據(jù)清洗

RFID 數(shù)據(jù)的多讀又稱(chēng)為交叉讀，其產(chǎn)生的因素很多，比如環(huán)境的干擾、射頻技術(shù)的限制等。RFID數(shù)據(jù)的交叉讀問(wèn)題會(huì)導(dǎo)致位置信息沖突，進(jìn)而無(wú)法滿足RFID 上層應(yīng)用的需求。為此，Liao 等人[41]提出了一種基于內(nèi)核密度的概率清洗方法（kernel densitybased probability cleaning method，KLEAP）來(lái)消除滑動(dòng)窗口中的交叉讀數(shù)。該方法使用基于核的函數(shù)估計(jì)每個(gè)標(biāo)簽的密度。與具有最大密度的微集群相對(duì)應(yīng)的讀寫(xiě)器將被視為標(biāo)記對(duì)象在當(dāng)前窗口中應(yīng)定位的位置，從其他讀寫(xiě)器獲得的讀數(shù)將被視為交叉讀數(shù)。該方法的優(yōu)勢(shì)是能檢測(cè)到標(biāo)簽的確切位置，局限是滑動(dòng)窗口大小是固定的。

SMURF方法[19]可以調(diào)整窗口大小以減少交叉讀數(shù)據(jù)，但不能消除物理因素產(chǎn)生的交叉讀取。

Bai等人[16]使用一種簡(jiǎn)單的計(jì)數(shù)方法去除交叉讀數(shù)，該方法基于交叉讀數(shù)通常比正常真實(shí)讀數(shù)的發(fā)生率低的假設(shè)。然而，該方法的有效性與計(jì)數(shù)閾值直接相關(guān)，如果用戶沒(méi)有太多的領(lǐng)域知識(shí)，計(jì)數(shù)閾值很難設(shè)置。此外如果交叉讀數(shù)的數(shù)量大于正常的真實(shí)讀數(shù)，該方法可能會(huì)產(chǎn)生錯(cuò)誤的過(guò)濾結(jié)果。

潘巍等人[42]提出了利用參考標(biāo)簽思想結(jié)合信號(hào)強(qiáng)度[43]特征的相對(duì)定位技術(shù)來(lái)解決交叉讀仲裁的問(wèn)題，設(shè)計(jì)并實(shí)現(xiàn)了基于滑動(dòng)窗口的交叉數(shù)據(jù)讀入檢測(cè)和仲裁的核心算法。該方法的優(yōu)勢(shì)是巧妙地利用了讀寫(xiě)器的信號(hào)強(qiáng)弱，同時(shí)輔以參考標(biāo)簽，利用相對(duì)位置推測(cè)標(biāo)簽位置。不足之處是其中用到的窗口大小不能自適應(yīng)調(diào)整，還不適用于非規(guī)則布局的應(yīng)用場(chǎng)景。

表3給出了幾種典型的RFID多讀數(shù)據(jù)清洗方法的對(duì)比，包括分類(lèi)、子類(lèi)、代表性工作、優(yōu)勢(shì)、局限、適用場(chǎng)景等內(nèi)容。

表3 典型RFID多讀數(shù)據(jù)清洗方法對(duì)比Table 3 Comparison of methods of RFID false positive reading cleaning

4.3 冗余數(shù)據(jù)清洗

在RFID 系統(tǒng)中，一個(gè)RFID 讀寫(xiě)器或部署到同一區(qū)域的一些RFID 讀寫(xiě)器多次讀取RFID 標(biāo)簽，因此RFID 數(shù)據(jù)流中存在大量重復(fù)項(xiàng)。Wang 等人[44]發(fā)現(xiàn)現(xiàn)有的基于時(shí)間布魯姆濾波器（time Bloom filter，TBF）的重復(fù)消除方法需要多個(gè)計(jì)數(shù)器來(lái)存儲(chǔ)RFID數(shù)據(jù)流中元素的檢測(cè)時(shí)間，從而浪費(fèi)了寶貴的內(nèi)存資源。為了改變上述情況，其設(shè)計(jì)了d-左時(shí)間布魯姆濾波器（d-left time Bloom filter，DLTBF），作為d-左計(jì)數(shù)布魯姆濾波器的擴(kuò)展。通過(guò)d-left 散列（一種平衡分配機(jī)制），DLTBF可以將檢測(cè)到的元素時(shí)間存儲(chǔ)到一個(gè)計(jì)數(shù)器中。在此基礎(chǔ)上，提出了一種基于DLTBF 的一次性近似消除RFID 數(shù)據(jù)流中重復(fù)項(xiàng)的方法。不過(guò)，其在插入數(shù)據(jù)之前需要計(jì)算最小裝載桶。此外，它還使用了許多散列函數(shù)。

通常，RFID 數(shù)據(jù)流包含大量重復(fù)數(shù)據(jù)。由于RFID數(shù)據(jù)是流數(shù)據(jù)，其產(chǎn)生源源不斷，很難用少量?jī)?nèi)存一次性消除重復(fù)的RFID數(shù)據(jù)。因此，Lee等人[45]提出了基于Bloom濾波器的近似重復(fù)消除方法，即時(shí)間Bloom 濾波器（TBF）和時(shí)間間隔Bloom 濾波器（time interval Bloom filter，TIBF）。在時(shí)間Bloom 過(guò)濾器中，將Bloom 過(guò)濾器中的位數(shù)組替換為時(shí)間信息數(shù)組，因?yàn)镽FID數(shù)據(jù)中重復(fù)項(xiàng)的定義與檢測(cè)到的時(shí)間有關(guān)。此外，為了減少冗余數(shù)據(jù)，時(shí)間間隔Bloom 過(guò)濾器使用時(shí)間間隔來(lái)處理。實(shí)驗(yàn)結(jié)果表明，所提出的方法可以在一次過(guò)程中以較小的誤差去除重復(fù)的RFID 數(shù)據(jù)。該方法內(nèi)存效率不高，因?yàn)樾枰鄠€(gè)時(shí)間計(jì)數(shù)器來(lái)存儲(chǔ)讀取時(shí)間。

針對(duì)現(xiàn)有方法不能滿足處理海量RFID 數(shù)據(jù)流的實(shí)時(shí)性要求的問(wèn)題，Mahdin 等人[40]提出了一種稱(chēng)為CBF（comparison Bloom filter）的數(shù)據(jù)過(guò)濾方法，可以有效地檢測(cè)和刪除RFID 數(shù)據(jù)流中的重復(fù)讀數(shù)。其優(yōu)勢(shì)是將布隆過(guò)濾器的數(shù)量減少至1個(gè)，同時(shí)在時(shí)間和空間上都有很好的性能。不過(guò)其只能過(guò)濾一個(gè)讀寫(xiě)器的冗余數(shù)據(jù)，且使用了許多哈希函數(shù)，滑動(dòng)窗口在標(biāo)簽運(yùn)動(dòng)不規(guī)則的情況下效果不好。

Baba 等人[46]研究了室內(nèi)RFID 跟蹤數(shù)據(jù)的數(shù)據(jù)清洗。其關(guān)注兩個(gè)相關(guān)的任務(wù)：消除時(shí)間冗余和減少空間歧義。對(duì)于前者，設(shè)計(jì)了一個(gè)臨時(shí)清洗算法來(lái)臨時(shí)聚集原始RFID讀數(shù)，從而在不丟失信息的情況下壓縮數(shù)據(jù)大小。對(duì)于后者，設(shè)計(jì)了一種空間清洗技術(shù)。同時(shí)，提出了一個(gè)距離感知部署圖來(lái)捕獲RFID讀寫(xiě)器部署以及室內(nèi)拓?fù)浣Y(jié)構(gòu)所隱含的時(shí)空約束。通過(guò)利用圖中捕捉到的時(shí)空約束，設(shè)計(jì)了一種空間清洗算法來(lái)減少RFID 數(shù)據(jù)中的空間模糊性。本文提出的技術(shù)也適用于其他符號(hào)定位技術(shù)（如藍(lán)牙）獲得的室內(nèi)跟蹤數(shù)據(jù)。其局限在于不容易設(shè)定時(shí)間和空間粒度的大小。

表4給出了幾種典型的RFID冗余數(shù)據(jù)清洗方法的對(duì)比，包括分類(lèi)、子類(lèi)、代表性工作、優(yōu)勢(shì)、局限、適用場(chǎng)景等內(nèi)容。

表4 典型RFID冗余數(shù)據(jù)清洗方法對(duì)比Table 4 Comparison of methods of RFID duplicated reading cleaning

4.4 亂序數(shù)據(jù)處理

現(xiàn)有的方法無(wú)法處理存在基于事件的系統(tǒng)（event based system，EBS）時(shí)由網(wǎng)絡(luò)延遲引入的亂序事件到達(dá)的情況，而且亂序事件處理可能導(dǎo)致系統(tǒng)故障。為此，Mutschler等人[47]提出了一種基于K時(shí)間寬松（K-slack）的低延遲方法。該方法在沒(méi)有先驗(yàn)知識(shí)的情況下實(shí)現(xiàn)了對(duì)高數(shù)據(jù)率傳感器和事件流的有序事件處理。在不使用本地或全局時(shí)鐘的情況下，動(dòng)態(tài)調(diào)整空閑緩沖區(qū)以適應(yīng)數(shù)據(jù)流中的亂序。中間件系統(tǒng)透明地重新排列事件輸入流，以便事件仍然可以聚合和處理到滿足應(yīng)用程序需求的粒度。在實(shí)時(shí)定位系統(tǒng)（realtime locating systems,RTLS）上，該系統(tǒng)在亂序事件到達(dá)的情況下能夠執(zhí)行準(zhǔn)確的低延遲事件檢測(cè)，并且當(dāng)系統(tǒng)分布在多個(gè)線程和機(jī)器上時(shí)，具有接近線性的性能。該方法局限在于滑動(dòng)窗口的大小是固定不變的，不能適應(yīng)網(wǎng)絡(luò)延遲的實(shí)時(shí)變化。

網(wǎng)絡(luò)延遲、機(jī)器故障等因素可能會(huì)導(dǎo)致事件在事件流處理引擎中亂序到達(dá)。Li 等人[48]解決了在可能包含亂序數(shù)據(jù)的事件流上查詢指定的事件模式的問(wèn)題。首先，研究者分析了典型的事件流處理技術(shù)在面對(duì)亂序數(shù)據(jù)到達(dá)時(shí)會(huì)遇到的問(wèn)題。然后，研究者為核心流代數(shù)操作符（如序列掃描和模式構(gòu)建）提出了一種新的物理實(shí)現(xiàn)策略，包括基于堆棧的數(shù)據(jù)結(jié)構(gòu)和相關(guān)的清除算法。還介紹了序列掃描和構(gòu)造以及狀態(tài)清除的優(yōu)化，以最小化CPU 成本和內(nèi)存消耗。不過(guò)，該方法還存在一定量的誤配或者錯(cuò)位事件，同時(shí)結(jié)果也存在一定的延遲。

亂序處理涉及延遲和生成的連接結(jié)果質(zhì)量之間不可避免的權(quán)衡。為了滿足流應(yīng)用程序的不同需求，需要提供用戶可配置的結(jié)果延遲與結(jié)果質(zhì)量的權(quán)衡?，F(xiàn)有的亂序處理方法要么不提供這種可配置性，要么只支持用戶指定的延遲約束。為此，Ji等人[49]提倡質(zhì)量驅(qū)動(dòng)的亂序處理思想，并提出了一種基于緩沖區(qū)的m路滑動(dòng)窗口連接（m-way sliding window joins，MSWJ）亂序處理方法。該方法在滿足用戶指定的結(jié)果質(zhì)量要求的同時(shí)，最小化輸入排序緩沖區(qū)的大小，從而減少結(jié)果延遲。該方法的核心是一個(gè)分析模型，它建模了輸入緩沖區(qū)大小與生成結(jié)果質(zhì)量之間的關(guān)系。該方法也是通用的，它支持具有任意連接條件的m路滑動(dòng)窗口連接。優(yōu)點(diǎn)是允許用戶指定結(jié)果質(zhì)量要求，在保證處理結(jié)果質(zhì)量的前提下，盡可能減少延遲時(shí)間；缺點(diǎn)是緩存容量的減少和質(zhì)量的保證，促使實(shí)時(shí)性要求較高的應(yīng)用無(wú)法使用該方法的處理結(jié)果。

現(xiàn)有的事件流處理技術(shù)在遇到亂序數(shù)據(jù)到達(dá)時(shí)遇到了重大挑戰(zhàn)，比如輸出阻塞、較長(zhǎng)的系統(tǒng)延遲、內(nèi)存資源溢出和不正確的結(jié)果生成。為了解決這些問(wèn)題，Liu等人[50-51]提出了兩種備選解決方案：分別采用激進(jìn)策略和保守策略來(lái)處理亂序事件流上的序列模式查詢。在亂序事件很少出現(xiàn)的樂(lè)觀假設(shè)下，激進(jìn)策略產(chǎn)生最大輸出。相反，為了解決亂序事件的意外發(fā)生以及由此產(chǎn)生的任何過(guò)早錯(cuò)誤結(jié)果，為激進(jìn)策略設(shè)計(jì)了適當(dāng)?shù)腻e(cuò)誤補(bǔ)償方法。保守方法是在亂序數(shù)據(jù)可能很常見(jiàn)的假設(shè)下工作的，因此只有當(dāng)其正確性得到保證時(shí)才會(huì)產(chǎn)生輸出。提出了一個(gè)偏序保證（partial order guarantee，POG）模型，該模型下可以保證這種正確性。對(duì)于尖峰工作負(fù)載下的健壯性，這兩種策略在持久存儲(chǔ)支持和用戶訪問(wèn)方法上相互補(bǔ)充。不過(guò)，該研究還未能實(shí)現(xiàn)在兩個(gè)策略間自動(dòng)切換。

在亂序數(shù)據(jù)流上執(zhí)行連續(xù)查詢是一項(xiàng)挑戰(zhàn)，其中元組不是根據(jù)時(shí)間戳排序的；因?yàn)楦邷?zhǔn)確性和低延遲是兩個(gè)相互沖突的性能指標(biāo)。盡管許多應(yīng)用程序允許以精確的查詢結(jié)果換取較低的延遲，但它們?nèi)匀幌Ｍ傻慕Y(jié)果滿足一定的質(zhì)量要求。然而，現(xiàn)有的亂序處理方法沒(méi)有考慮在滿足用戶指定的查詢結(jié)果質(zhì)量要求的同時(shí)最小化結(jié)果延遲。Ji 等人[52]提出一種基于緩沖區(qū)的自適應(yīng)亂序處理方法AQ-Kslack（approximate query-K-slack），它支持以質(zhì)量驅(qū)動(dòng)的方式對(duì)亂序數(shù)據(jù)流執(zhí)行滑動(dòng)窗口聚合查詢。通過(guò)采用基于采樣的近似查詢處理和控制理論領(lǐng)域的技術(shù)，該方法在查詢運(yùn)行時(shí)動(dòng)態(tài)調(diào)整輸入緩沖區(qū)大小以最小化結(jié)果延遲，同時(shí)遵守用戶指定的查詢結(jié)果錯(cuò)誤閾值。該方法的優(yōu)點(diǎn)是同時(shí)考慮準(zhǔn)確性和低延遲，動(dòng)態(tài)調(diào)整緩沖區(qū)的大小，允許用戶指定結(jié)果的閾值；缺點(diǎn)是結(jié)果既不是最準(zhǔn)確的，也不是延遲最短的。

網(wǎng)絡(luò)延遲和機(jī)器故障可能會(huì)導(dǎo)致事件亂序到達(dá)。此外，現(xiàn)有文獻(xiàn)假設(shè)事件沒(méi)有持續(xù)時(shí)間，但許多實(shí)際應(yīng)用程序中的事件都有持續(xù)時(shí)間，并且這些事件之間的關(guān)系往往很復(fù)雜。Zhou等人[53]首先分析了時(shí)間語(yǔ)義學(xué)的基礎(chǔ)知識(shí)，接著提出了一個(gè)時(shí)間語(yǔ)義學(xué)模型。還介紹了一種包含時(shí)間間隔的混合解決方案，用于處理亂序事件。在未來(lái)，該方案還可以考慮其他影響因素，比如緩沖區(qū)的大小、亂序比例、亂序事件的平均步長(zhǎng)，以便找到平衡點(diǎn)。

現(xiàn)有的事件流處理技術(shù)主要提供盡最大努力（best-effort）式的服務(wù)來(lái)減少平均響應(yīng)時(shí)間，這種方式并不能在確定的時(shí)間延遲需求下輸出更多的結(jié)果。針對(duì)監(jiān)控應(yīng)用中的確定性服務(wù)質(zhì)量需求，谷峪等人[54]討論了常見(jiàn)的泊松監(jiān)控流上的截止期敏感[55]的復(fù)雜事件處理最優(yōu)化資源分配問(wèn)題。從系統(tǒng)服務(wù)角度對(duì)事件的到達(dá)和復(fù)雜事件處理進(jìn)行了理論分析和建模，提出了復(fù)合事件的截止期滿足率模型和多事件流處理亂序反饋修正模型，進(jìn)而給出最優(yōu)化資源分配模型。通過(guò)合理地分配處理資源，保證了在實(shí)時(shí)限制下產(chǎn)生更多的正確結(jié)果，兼顧了復(fù)雜事件處理的實(shí)時(shí)性和正確性。

表5 給出了典型RFID 亂序數(shù)據(jù)清洗方法的對(duì)比，包括分類(lèi)、優(yōu)勢(shì)、局限、適用場(chǎng)景等內(nèi)容。

表5 典型RFID亂序數(shù)據(jù)處理方法對(duì)比Table 5 Comparison of methods of RFID out-of-order reading cleaning

4.5 應(yīng)用系統(tǒng)

由于RFID 數(shù)據(jù)清洗屬于數(shù)據(jù)預(yù)處理環(huán)節(jié)，沒(méi)有專(zhuān)門(mén)的RFID 數(shù)據(jù)清洗系統(tǒng)，大部分RFID 應(yīng)用系統(tǒng)是RFID復(fù)雜事件處理系統(tǒng)、RFID不確定事件處理系統(tǒng)。下面介紹相關(guān)系統(tǒng)并重點(diǎn)介紹與數(shù)據(jù)預(yù)處理相關(guān)的應(yīng)用。

美國(guó)加州大學(xué)伯克利分校的Gyllstrom 等人[56]開(kāi)發(fā)和設(shè)計(jì)了原型系統(tǒng)SASE（stream-based and shared event processing），其提供擴(kuò)展的事件語(yǔ)言、事件查詢處理器和操作優(yōu)化策略等，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的收集和清洗、基本事件生成、復(fù)合事件處理、事件歸檔以及對(duì)事件的查詢。然而，SASE忽略了時(shí)間這一關(guān)鍵因素，而在許多RFID應(yīng)用中，有些事件只有在指定的時(shí)間限制內(nèi)或限制之后才被認(rèn)為是“有效事件”。同時(shí)，SASE還假設(shè)所有事件是按照其時(shí)間戳排序的，但該假設(shè)并不適用于所有的RFID場(chǎng)景，比如亂序的情形。

美國(guó)馬薩諸塞大學(xué)Tran等人[57]以帶有RFID標(biāo)簽的對(duì)象固定、讀寫(xiě)器移動(dòng)為應(yīng)用場(chǎng)景設(shè)計(jì)和實(shí)現(xiàn)了RFID概率推演系統(tǒng)，旨在將缺失的、帶有噪音的原始數(shù)據(jù)流清洗成帶有較精確位置的事件流。該推演系統(tǒng)適合于倉(cāng)儲(chǔ)管理等這類(lèi)貨物相對(duì)固定、讀寫(xiě)器隨著使用人員移動(dòng)的應(yīng)用。

移動(dòng)和應(yīng)用程序通常依賴(lài)RFID 天線或傳感器等設(shè)備向其提供有關(guān)物理世界的信息。然而，這些設(shè)備是不可靠的。它們產(chǎn)生的部分?jǐn)?shù)據(jù)可能丟失、重復(fù)或錯(cuò)誤。目前的技術(shù)水平是局部校正誤差（例如，溫度讀數(shù)的范圍限制）或使用空間/時(shí)間相關(guān)性（例如，平滑溫度讀數(shù)）。然而錯(cuò)誤通常僅在全局設(shè)置中才明顯，例如，已知存在的對(duì)象的讀數(shù)缺失，或停車(chē)場(chǎng)的讀數(shù)與進(jìn)入讀數(shù)不匹配。美國(guó)華盛頓大學(xué)的Khoussainova 等人[58]設(shè)計(jì)了名為StreamClean 的系統(tǒng)，該系統(tǒng)使用應(yīng)用程序定義的全局完整性約束自動(dòng)糾正輸入數(shù)據(jù)錯(cuò)誤。由于通常不可能確定地進(jìn)行糾正，研究者提出了一種概率方法，其中系統(tǒng)為每個(gè)輸入元組分配正確的概率。

美國(guó)華盛頓大學(xué)的Khoussainova等人[59-60]介紹了概率事件抽取器（probabilistic event extractor，PEEX），一個(gè)使應(yīng)用程序能夠從RFID 數(shù)據(jù)中定義和提取有意義的概率高層事件的系統(tǒng)。PEEX 能有效地處理數(shù)據(jù)中的錯(cuò)誤和事件提取的固有模糊性。同時(shí)，PEEX提取了所有可能的活動(dòng)。此外，由于PEEX基于關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)（relational database management system，RDBMS），用戶可以方便地查詢和管理生成的事件。由于該系統(tǒng)的目標(biāo)是從錯(cuò)誤和不準(zhǔn)確的RFID數(shù)據(jù)中檢測(cè)事件，傳感器和RFID數(shù)據(jù)清洗領(lǐng)域是該工作的補(bǔ)充。該系統(tǒng)直接對(duì)不準(zhǔn)確和骯臟的數(shù)據(jù)進(jìn)行操作，而不需要用戶指定如何清洗數(shù)據(jù)。

美國(guó)華盛頓大學(xué)的Ré等人[61]設(shè)計(jì)和實(shí)現(xiàn)了原型系統(tǒng)Lahar。該大學(xué)的研究人員給出了一個(gè)真實(shí)的應(yīng)用場(chǎng)景，他們?cè)谵k公樓里的公共場(chǎng)合部署設(shè)計(jì)和實(shí)現(xiàn)了原型系統(tǒng)Lahar。該大學(xué)的研究人員給出了一個(gè)真實(shí)的應(yīng)用場(chǎng)景，他們?cè)谵k公樓里的公共場(chǎng)合部署了一些RFID讀寫(xiě)器，并且給相關(guān)的物品也貼上了電子標(biāo)簽，通過(guò)該系統(tǒng)實(shí)時(shí)監(jiān)測(cè)和跟蹤[62]樓內(nèi)人員的工作和日常生活，必要時(shí)給予友善提醒。在數(shù)據(jù)預(yù)處理方面，Lahar 通過(guò)粒子濾波技術(shù)填補(bǔ)漏讀數(shù)據(jù)并推演標(biāo)簽對(duì)象位置的概率分布。在事件處理方面，Lahar系統(tǒng)可以對(duì)歸檔數(shù)據(jù)和近實(shí)時(shí)數(shù)據(jù)執(zhí)行復(fù)雜事件查詢?？傊?，該系統(tǒng)提出了不確定概率事件流之上的復(fù)雜事件處理系統(tǒng)，兼顧考慮了數(shù)據(jù)流上事件的關(guān)聯(lián)性。該系統(tǒng)局限在于只能簡(jiǎn)單地回答查詢，且要求處理的數(shù)據(jù)是有序的。

Cascadia 系統(tǒng)[63]提供了面向普適RFID 應(yīng)用的基礎(chǔ)結(jié)構(gòu)，管理漏讀數(shù)據(jù)的不確定性、位置信息的不確定性、事件語(yǔ)義的不確定性和事件發(fā)生時(shí)間的不確定性。在復(fù)雜事件建模方面，其構(gòu)建了概率事件模型。在數(shù)據(jù)預(yù)處理方面，其接收讀寫(xiě)器讀取的原始數(shù)據(jù)，并用粒子濾波技術(shù)將原始讀數(shù)清洗成帶有位置信息和概率的時(shí)間。與文獻(xiàn)[57]系統(tǒng)不同，Cascadia系統(tǒng)中讀寫(xiě)器的位置是固定的，只能過(guò)濾出粗粒度的位置信息。Cascadia系統(tǒng)貢獻(xiàn)主要是針對(duì)RFID數(shù)據(jù)的不確定性構(gòu)建了RFID 概率數(shù)據(jù)模型并實(shí)現(xiàn)了概率事件抽取算法，支持面向RFID移動(dòng)對(duì)象跟蹤等復(fù)雜應(yīng)用。

表6給出了幾種典型的RFID數(shù)據(jù)清洗應(yīng)用系統(tǒng)的對(duì)比，包括系統(tǒng)名稱(chēng)、功能描述、貢獻(xiàn)、局限、適用場(chǎng)景等內(nèi)容。

表6 RFID應(yīng)用系統(tǒng)對(duì)比Table 6 Comparison of RFID application systems

5 未來(lái)研究方向

RFID 是一種很有前景的技術(shù)，其在新興領(lǐng)域的應(yīng)用必將給RFID 數(shù)據(jù)清洗技術(shù)帶來(lái)新的機(jī)遇和挑戰(zhàn)。為了豐富和完善RFID數(shù)據(jù)清洗技術(shù)，有待從以下五方面做進(jìn)一步的研究：

（1）構(gòu)建高質(zhì)量的RFID 源數(shù)據(jù)集和RFID 基準(zhǔn)測(cè)試數(shù)據(jù)集?，F(xiàn)有的用來(lái)做實(shí)驗(yàn)的RFID 源數(shù)據(jù)集基本沒(méi)有公共的數(shù)據(jù)集，一般都是研究者根據(jù)實(shí)驗(yàn)情況人工生成的[64]，這樣的數(shù)據(jù)缺少權(quán)威性和通用性，因此一般沒(méi)有二次利用價(jià)值。如果能夠在實(shí)際場(chǎng)景中生成一個(gè)或者若干高質(zhì)量的源數(shù)據(jù)集，對(duì)于相關(guān)研究方向的廣大的科研工作者無(wú)疑是一個(gè)福音。建議從以下方面保證RFID源數(shù)據(jù)集的質(zhì)量：一是RFID數(shù)據(jù)產(chǎn)生環(huán)境盡可能擁有不同等級(jí)的噪聲、干擾等情況；二是RFID數(shù)據(jù)在傳輸過(guò)程盡可能包含延遲、擁塞、丟包等情況。同時(shí)，廣大科研工作者提出的相關(guān)RFID數(shù)據(jù)清洗技術(shù)對(duì)于源數(shù)據(jù)的處理也沒(méi)有統(tǒng)一可用的結(jié)果，這樣大量相關(guān)新技術(shù)到底孰優(yōu)孰劣無(wú)從評(píng)價(jià)，因此構(gòu)建一個(gè)高質(zhì)量的RFID 基準(zhǔn)數(shù)據(jù)集也是很有必要的。同樣，建議從以下方面保證RFID基準(zhǔn)測(cè)試數(shù)據(jù)集的質(zhì)量：一是測(cè)試數(shù)據(jù)應(yīng)該盡可能少；二是測(cè)試基準(zhǔn)數(shù)據(jù)應(yīng)該覆蓋更廣泛的業(yè)務(wù)類(lèi)型。

（2）如何對(duì)加密RFID 數(shù)據(jù)和具有隱私保護(hù)[65]的數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗。安全性[66]是一個(gè)倍受使用者關(guān)注的問(wèn)題。例如，一些公司不希望其他競(jìng)爭(zhēng)對(duì)手能通過(guò)貨物上的RFID 標(biāo)簽追蹤到貨物的行蹤及貨物種類(lèi)。同樣，用戶在使用貼有RFID標(biāo)簽的與金融信息相關(guān)的設(shè)備時(shí)，不希望與用戶帳戶相關(guān)的信息遭到泄露[67]。為此，科研工作者設(shè)計(jì)了一些用于RFID標(biāo)簽對(duì)可信讀寫(xiě)器認(rèn)證的加密算法，用于標(biāo)簽對(duì)讀寫(xiě)器實(shí)現(xiàn)身份認(rèn)證，通過(guò)認(rèn)證的讀寫(xiě)器才能獲取RFID標(biāo)簽中的信息。然而，認(rèn)證過(guò)程耗時(shí)，如何設(shè)計(jì)滿足安全性與隱私要求的高性能算法就顯得尤為重要。

（3）讀取準(zhǔn)確率需要提高。數(shù)據(jù)完整并且正確性是決定RFID 系統(tǒng)性能的重要因素[68]，在讀寫(xiě)器作用域內(nèi)，多個(gè)標(biāo)簽同時(shí)向讀寫(xiě)器發(fā)送數(shù)據(jù)或者一個(gè)讀寫(xiě)器在另一個(gè)讀寫(xiě)器的作用域內(nèi)時(shí)，信號(hào)間發(fā)生相互干擾，導(dǎo)致讀寫(xiě)器接收到的數(shù)據(jù)錯(cuò)誤，即無(wú)法完整識(shí)別出標(biāo)簽，或者識(shí)別出錯(cuò)誤的標(biāo)簽[69]。因此，多目標(biāo)識(shí)別既是RFID的最大優(yōu)勢(shì)，也是亟待解決的技術(shù)難點(diǎn)。雖然早在2009 年，美國(guó)某個(gè)知名企業(yè)就宣稱(chēng)其單品RFID庫(kù)存管理系統(tǒng)能提供99%的店面庫(kù)存可見(jiàn)度，然而在現(xiàn)實(shí)操作中，由于算法原因、人員問(wèn)題和流程問(wèn)題而引起的誤讀仍是RFID 技術(shù)普及道路上的絆腳石。另外，有媒體報(bào)道，在“無(wú)人零售店”的體驗(yàn)過(guò)程中，也有購(gòu)買(mǎi)兩件同樣的商品只能識(shí)別出一件，以及因?yàn)檎迟N太緊密而無(wú)法識(shí)別金屬易拉罐商品的情況出現(xiàn)。

（4）大數(shù)據(jù)時(shí)代，要充分考慮清洗結(jié)果的時(shí)效性。在大數(shù)據(jù)時(shí)代，數(shù)據(jù)量大已經(jīng)不是研究者關(guān)注的主要問(wèn)題，最主要關(guān)注的問(wèn)題應(yīng)該是數(shù)據(jù)處理的時(shí)效性。如何在非常短的時(shí)間內(nèi)把海量的RFID 數(shù)據(jù)進(jìn)行處理，這就是大數(shù)據(jù)處理面臨的最大的挑戰(zhàn)。RFID數(shù)據(jù)的大量應(yīng)用都是實(shí)時(shí)或者近實(shí)時(shí)的應(yīng)用，如果不能對(duì)這些數(shù)據(jù)進(jìn)行及時(shí)處理，這些RFID數(shù)據(jù)的價(jià)值就消失殆盡，這就是RFID大數(shù)據(jù)處理最大的挑戰(zhàn)。

（5）設(shè)計(jì)一個(gè)沒(méi)有固定限制的適用范圍更廣的方法。通常，現(xiàn)有的RFID數(shù)據(jù)清洗算法大多基于某種情況的假設(shè)，比如有的假設(shè)標(biāo)簽移動(dòng)讀寫(xiě)器固定[70]，有的假設(shè)標(biāo)簽固定讀寫(xiě)器移動(dòng)，有的物品間有時(shí)空關(guān)聯(lián)，有的假設(shè)物品布局規(guī)則，有的假設(shè)多讀寫(xiě)器場(chǎng)景，有的假設(shè)數(shù)據(jù)符合某種分布等，一旦轉(zhuǎn)換場(chǎng)景該方法的性能就大打折扣甚至不可用。因此，在今后的研究中，很有必要設(shè)計(jì)出一種自學(xué)習(xí)的算法，系統(tǒng)算法能分析現(xiàn)有情況屬于何種場(chǎng)景，從而從庫(kù)中選擇出合適的數(shù)據(jù)清洗算法，使得性能達(dá)到最佳。如果一種數(shù)據(jù)清洗算法效果不好，可以有選擇多種算法的能力，這樣的算法也正迎合了人工智能時(shí)代的要求。

6 總結(jié)

本文旨在回顧RFID 數(shù)據(jù)清洗技術(shù)的研究進(jìn)展情況，以幫助相關(guān)科研人員對(duì)該領(lǐng)域的全面了解。本文對(duì)RFID數(shù)據(jù)清洗相關(guān)研究進(jìn)行了全面回顧，給出了RFID系統(tǒng)與RFID數(shù)據(jù)清洗問(wèn)題的有關(guān)定義與描述，列出了典型的數(shù)據(jù)集與評(píng)價(jià)標(biāo)準(zhǔn)，從相關(guān)技術(shù)的分類(lèi)、子類(lèi)、基本思想、優(yōu)勢(shì)、局限、適用場(chǎng)景等方面詳細(xì)比較和總結(jié)了現(xiàn)有的RFID數(shù)據(jù)清洗工作，同時(shí)給出了相關(guān)應(yīng)用系統(tǒng)。最后，從RFID原始數(shù)據(jù)與基準(zhǔn)數(shù)據(jù)集構(gòu)建、加密與隱私保護(hù)數(shù)據(jù)的清洗策略、數(shù)據(jù)采集準(zhǔn)確率、清洗結(jié)果的時(shí)效性、場(chǎng)景自學(xué)習(xí)的全面方法等方面提出了RFID 數(shù)據(jù)清洗領(lǐng)域五個(gè)未來(lái)有前景的研究方向。