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

褚　天,潘金滿,杜　磊

(1.軍事交通學(xué)院 研究生管理大隊(duì),天津　300161;2.軍事交通學(xué)院 基礎(chǔ)部,天津　300161)

?

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

褚天1,潘金滿1,杜磊2

(1.軍事交通學(xué)院 研究生管理大隊(duì),天津300161;2.軍事交通學(xué)院 基礎(chǔ)部,天津300161)

摘要RFID標(biāo)簽數(shù)據(jù)漏讀問題普遍存在于RFID系統(tǒng)的應(yīng)用中,為確保RFID數(shù)據(jù)的準(zhǔn)確性,必須對(duì)原始數(shù)據(jù)進(jìn)行清洗。針對(duì)當(dāng)前最有效的滑動(dòng)窗口清洗算法SMURF中存在的標(biāo)簽動(dòng)態(tài)性檢測(cè)的缺陷,文中在提出的改進(jìn)算法中引入了標(biāo)簽概率運(yùn)動(dòng)模型進(jìn)行判定,算法能準(zhǔn)確檢測(cè)到標(biāo)簽動(dòng)態(tài)變化,并在窗口大小設(shè)置上更為合理。實(shí)驗(yàn)結(jié)果表明,文中所提出的算法比SMURF算法產(chǎn)生的平均錯(cuò)誤數(shù)減少51%,性能更加優(yōu)越。

關(guān)鍵詞RFID;漏讀;數(shù)據(jù)清洗;滑動(dòng)窗口;標(biāo)簽運(yùn)動(dòng)

RFID(Radio Frequency Identification)是一種非接觸式自動(dòng)識(shí)別和數(shù)據(jù)獲取技術(shù)。其將無線通信、數(shù)據(jù)管理和信號(hào)處理等技術(shù)融為一體,利用無線射頻信號(hào)完成閱讀器與電子標(biāo)簽之間的數(shù)據(jù)通信[1]。由于RFID技術(shù)采用無線射頻信號(hào)進(jìn)行數(shù)據(jù)通信,該信號(hào)易受環(huán)境影響,且相互間干擾較大,尤其當(dāng)標(biāo)簽和閱讀器數(shù)量增多時(shí),信號(hào)之間的干擾加強(qiáng),導(dǎo)致RFID數(shù)據(jù)更不可靠,嚴(yán)重影響了該技術(shù)的推廣。RFID不可靠數(shù)據(jù)包括數(shù)據(jù)冗余(Duplication)、數(shù)據(jù)多讀(False Positive)和數(shù)據(jù)漏讀(False Negative)。在多數(shù)情況下,閱讀器只能讀取到其感應(yīng)范圍內(nèi)60%～70%的標(biāo)簽數(shù)據(jù),即至少有 30%的標(biāo)簽數(shù)據(jù)在讀取時(shí)就被遺漏[2]。因此,為得到高質(zhì)量的RFID數(shù)據(jù),急需解決RFID數(shù)據(jù)漏讀問題。

1RFID漏讀數(shù)據(jù)清洗方法

針對(duì)RFID漏讀數(shù)據(jù)的清洗方法有多種,但基于滑動(dòng)窗口的數(shù)據(jù)填補(bǔ)算法是目前最實(shí)用、可行的方法。文獻(xiàn)[3]中將靜態(tài)時(shí)間窗口用于填補(bǔ)漏讀的 RFID 數(shù)據(jù)。然而,使用靜態(tài)時(shí)間窗口存在一些問題,如圖1所示,若窗口設(shè)置過小,則有可能無法充分對(duì)漏讀數(shù)據(jù)進(jìn)行平滑處理,不能保證標(biāo)簽的完整性;窗口設(shè)置過大,又無法較好地監(jiān)測(cè)標(biāo)簽的動(dòng)態(tài)性。因此,理想窗口大小設(shè)置應(yīng)綜合考慮并合理設(shè)置,使得在保證不漏讀數(shù)據(jù)情況下,準(zhǔn)確地檢測(cè)標(biāo)簽的狀態(tài)轉(zhuǎn)變。

圖1　固定窗口平滑

(1)

(2)

為保證標(biāo)簽的動(dòng)態(tài)性,滑動(dòng)窗口的大小需要滿足

(3)

SMURF算法在實(shí)現(xiàn)過程中將初始滑動(dòng)窗口的大小置為 1,當(dāng)窗口內(nèi)發(fā)生閱讀時(shí),根據(jù)式(2)動(dòng)態(tài)調(diào)整窗口大小以保證數(shù)據(jù)的完整性:如果調(diào)整后的窗口大小滿足式(2)時(shí),SMURF則會(huì)基于式(3)對(duì)標(biāo)簽的動(dòng)態(tài)性進(jìn)行監(jiān)測(cè)。如果窗口大小不滿足式(3),SMURF會(huì)將當(dāng)前窗口縮小為原窗口大小的1/2,從而對(duì)標(biāo)簽狀態(tài)的轉(zhuǎn)變做出反應(yīng);否則,SMURF輸出當(dāng)前窗口,并滑動(dòng)一個(gè)時(shí)間片的長度來進(jìn)行下一次處理。若調(diào)整后的窗口大小不能滿足式(2),則SMURF會(huì)將當(dāng)前窗口以2為步長進(jìn)行增大,以滿足窗口設(shè)置的要求。SMURF算法實(shí)現(xiàn)的具體流程如圖2所示。

圖2　SMURF流程圖

SMURF算法改進(jìn)了定長滑動(dòng)窗口大小難以確定的缺點(diǎn),在靜態(tài)標(biāo)簽下取得了較高的準(zhǔn)確率,但當(dāng)標(biāo)簽數(shù)目增大或者是標(biāo)簽頻繁動(dòng)態(tài)變化時(shí),導(dǎo)致積極平滑或疲憊平滑現(xiàn)象較多,其重要原因是該算法對(duì)標(biāo)簽運(yùn)動(dòng)模式考慮欠缺[5],在標(biāo)簽的動(dòng)態(tài)監(jiān)測(cè)性方面只考慮到了標(biāo)簽在閱讀器區(qū)域與不在區(qū)域兩種情況。而實(shí)際上,這兩種狀態(tài)的轉(zhuǎn)換也是要經(jīng)歷一個(gè)由量變到質(zhì)變的過程,即標(biāo)簽的運(yùn)動(dòng)。本文在SMURF算法的基礎(chǔ)上,提出一種改進(jìn)的基于標(biāo)簽運(yùn)動(dòng)的RFID數(shù)據(jù)清洗算法DCATMS(Data Cleaning Algorithm of Tags in Motion Based on Sliding-window),DCATMS算法通過引入標(biāo)簽的概率運(yùn)動(dòng)模型來判斷標(biāo)簽的動(dòng)態(tài)躍遷性,進(jìn)而動(dòng)態(tài)調(diào)節(jié)滑動(dòng)窗口大小,解決數(shù)據(jù)的完整性和動(dòng)態(tài)性,更好地對(duì)RFID漏讀數(shù)據(jù)進(jìn)行填補(bǔ)。

2DCATMS算法設(shè)計(jì)

DCATMS算法采用的滑動(dòng)窗口模型與SMURF類似,仍將RFID數(shù)據(jù)集當(dāng)作統(tǒng)計(jì)學(xué)中的概率事件,即大量標(biāo)簽的隨機(jī)樣本。針對(duì)SMURF算法在標(biāo)簽動(dòng)態(tài)性檢測(cè)以及窗口大小設(shè)置方面的缺陷,該算法分別引入標(biāo)簽概率運(yùn)動(dòng)模型進(jìn)行標(biāo)簽狀態(tài)發(fā)生變化的判定,同時(shí)對(duì)窗口大小的設(shè)置進(jìn)行改進(jìn)。

2.1標(biāo)簽概率運(yùn)動(dòng)模型引入

RFID技術(shù)在實(shí)際應(yīng)用中,通常會(huì)有標(biāo)簽進(jìn)、出閱讀區(qū),反應(yīng)到物理世界中就是標(biāo)簽位置的變化,即標(biāo)簽的運(yùn)動(dòng)過程。顯然,標(biāo)簽的運(yùn)動(dòng)過程必然符合牛頓運(yùn)動(dòng)學(xué)定律。RFID 閱讀器的識(shí)別半徑通常為幾m,最遠(yuǎn)不超過十幾m。

RFID標(biāo)簽在閱讀器識(shí)別區(qū)域內(nèi)的運(yùn)動(dòng)速度通常較為平穩(wěn),而閱讀器本身處于識(shí)別區(qū)域的中心,如圖3所示。所以在一個(gè)較小的時(shí)間段Δt內(nèi)標(biāo)簽的運(yùn)動(dòng)可被近似看作是過識(shí)別區(qū)域中心(圓心)的勻速直線運(yùn)動(dòng)或者是多個(gè)連續(xù)的勻速直線運(yùn)動(dòng)的組合。如果記d0為標(biāo)簽與閱讀器的初始距離,根據(jù)勻速直線運(yùn)動(dòng)的性質(zhì)顯然可得

d=d0±vΔt

(4)

其中,v表示物體的運(yùn)動(dòng)速率。

為推斷出d的值,將式(4)變?yōu)?/p>

d=a+bΔt

(5)

圖3　閱讀器識(shí)別區(qū)

其中,a=d0,b=±v。

首先估計(jì)未知參數(shù)a和b的值,且a和b值的準(zhǔn)確度直接會(huì)影響到數(shù)據(jù)清洗的準(zhǔn)確度。由式(5)可知,d與Δt成線性關(guān)系,所以可采用最小二乘法對(duì)參數(shù)a和b進(jìn)行線性回歸[6]。詳細(xì)計(jì)算過程此處不再贅述,利用最小二乘法估算出參數(shù)a和b的值為

(6)

(7)

2.2DCATMS算法

DCATMS算法基本思路:在完整性方面,繼續(xù)沿用SMURF算法保證完整性的條件。然而在對(duì)SMURF算法的實(shí)驗(yàn)中發(fā)現(xiàn),將窗口大小每次線性增加2,則有可能導(dǎo)致窗口大小的不足而使得數(shù)據(jù)的平滑結(jié)果與實(shí)際情況相差較遠(yuǎn)。為此,本文采用一種對(duì)計(jì)算出新窗口大小與原窗口大小進(jìn)行折中的方法來對(duì)窗口大小進(jìn)行控制,即當(dāng)計(jì)算出新窗口的大小大于原窗口大小時(shí),將原窗口大小設(shè)置為新窗口大小與原窗口大小之和的一半。在標(biāo)簽動(dòng)態(tài)性檢測(cè)方面,通過上文標(biāo)簽運(yùn)動(dòng)模型進(jìn)行準(zhǔn)確判定。DCATMS算法基本流程如圖4所示。

圖4　DCATMS流程圖

3實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證DCATMS算法的有效性,本文采用JT900R四通道射頻閱讀器,使用符合EPC CLASSI G2標(biāo)準(zhǔn)的標(biāo)簽50個(gè),讓標(biāo)簽以一定的速度通過閱讀器,圖5和圖6所示為實(shí)驗(yàn)室環(huán)境下對(duì)算法進(jìn)行測(cè)試。同時(shí),為了驗(yàn)證算法的可擴(kuò)展性,本文進(jìn)行了大量的仿真實(shí)驗(yàn),采用文獻(xiàn)[7]中的方法生成仿真數(shù)據(jù)。如圖7所示,橫軸代表標(biāo)簽與閱讀器之間的距離,縱軸表示標(biāo)簽被閱讀器讀取到的概率即閱讀率。

圖5　實(shí)驗(yàn)硬件

圖6　實(shí)驗(yàn)硬件與軟件測(cè)試

圖7　仿真數(shù)據(jù)生成模型

實(shí)驗(yàn)中對(duì)標(biāo)簽進(jìn)行了兩種運(yùn)動(dòng)模式的研究:模式1是標(biāo)簽以不同速度勻速運(yùn)動(dòng);模式2是標(biāo)簽隨機(jī)運(yùn)動(dòng)[8-9]。實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

表1　實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)中,通過變化閱讀器主識(shí)別區(qū)在整個(gè)閱讀器閱讀區(qū)中比例大小對(duì)數(shù)據(jù)進(jìn)行實(shí)驗(yàn),算法性能用每個(gè)epoch的錯(cuò)誤閱讀數(shù)來表示。錯(cuò)誤閱讀數(shù)是指當(dāng)標(biāo)簽存在于閱讀器范圍內(nèi)時(shí),經(jīng)算法處理過后并無閱讀數(shù)據(jù)產(chǎn)生,或當(dāng)標(biāo)簽在閱讀器范圍外時(shí),經(jīng)算法處理過后產(chǎn)生了閱讀數(shù)據(jù)。通過大量實(shí)驗(yàn)數(shù)據(jù),本文比較了固定大小的靜態(tài)滑動(dòng)窗口方法Static-x、SMURF算法和DCATMS的算法性能,并重點(diǎn)對(duì)比分析了DCATMS和SMURF算法的清洗效果。

3.1標(biāo)簽勻速運(yùn)動(dòng)算法清洗效果分析

實(shí)驗(yàn)分析了標(biāo)簽在勻速運(yùn)動(dòng)時(shí),算法在不同速度下的平均錯(cuò)誤數(shù),標(biāo)簽勻速進(jìn)出探測(cè)區(qū)域,速度在0～90 cm/epoch之間,實(shí)驗(yàn)記錄了不同速度下每種方案產(chǎn)生的平均錯(cuò)誤數(shù)。圖8顯示了實(shí)驗(yàn)結(jié)果。

圖8　不同算法平滑結(jié)果

如圖8所示,為標(biāo)簽速度不同時(shí)的RAW原始數(shù)據(jù)、固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS的性能比較。結(jié)果顯示隨著標(biāo)簽運(yùn)動(dòng)速度加快,對(duì)固定窗口而言,小窗口更能捕獲標(biāo)簽的運(yùn)動(dòng)狀態(tài)的改變,性能相對(duì)較好。SMURF和DCATMS算法則由于能夠根據(jù)閱讀率和約束條件進(jìn)行動(dòng)態(tài)調(diào)節(jié),能更準(zhǔn)確地應(yīng)對(duì)標(biāo)簽運(yùn)動(dòng)引發(fā)的狀態(tài)變化,從而準(zhǔn)確率相對(duì)較高且較為平穩(wěn),此外DCATMS算法對(duì)標(biāo)簽狀態(tài)改變更加敏感,準(zhǔn)確率更好。由圖7顯示的算法比較可知,DCATMS比SMURF平均錯(cuò)誤數(shù)總體減少量約為50%,對(duì)漏讀數(shù)據(jù)的填補(bǔ)效果更佳。

3.2標(biāo)簽隨機(jī)運(yùn)動(dòng)算法清洗效果分析

實(shí)驗(yàn)分析了標(biāo)簽隨機(jī)運(yùn)動(dòng)時(shí)算法在不同主識(shí)別區(qū)百分比的平均錯(cuò)誤數(shù)和自適應(yīng)清洗結(jié)果。標(biāo)簽在閱讀器閱讀范圍內(nèi)及范圍外以0～90 m/epoch 的速度隨機(jī)運(yùn)動(dòng),主識(shí)別區(qū)的比率從0～1之間以步長為0.1選取11個(gè)值。較低的主識(shí)別區(qū)百分比模擬不可靠的環(huán)境,較高的主識(shí)別區(qū)百分比模擬可靠環(huán)境。圖9顯示了這項(xiàng)實(shí)驗(yàn)的結(jié)果。

圖9　不同算法平滑結(jié)果

圖9顯示了固定窗口Static-5、Static-10、Static-20、SMURF算法和DCATMS算法在不同主識(shí)別區(qū)百分比的錯(cuò)誤數(shù)比較。結(jié)果顯示主識(shí)別區(qū)百分比較低時(shí),標(biāo)簽閱讀率較低,大的固定窗口平滑效果相對(duì)較好且較穩(wěn)定,隨著閱讀率的提高,所有算法的準(zhǔn)確度都隨之上升,針對(duì)固定窗口而言,小窗口的平滑效果較好。SMURF和DCATMS算法相對(duì)固定滑動(dòng)窗口整體效果較好,自適應(yīng)性較高,且DCATMS算法平均錯(cuò)誤數(shù)比SMURF總體減少量約為52%。

4結(jié)束語

本文分析了經(jīng)典的RFID漏讀數(shù)據(jù)清洗算法SMURF,針對(duì)該算法存在標(biāo)簽動(dòng)態(tài)性檢測(cè)以及滑動(dòng)窗口大小設(shè)置方面的缺陷,提出了一種改進(jìn)的RFID漏讀數(shù)據(jù)清洗算法DCATMS。DCATMS算法中引入標(biāo)簽概率運(yùn)動(dòng)模型對(duì)標(biāo)簽的動(dòng)態(tài)性進(jìn)行準(zhǔn)確判斷,防止在填補(bǔ)漏讀數(shù)據(jù)時(shí)造成積極平滑或疲憊平滑現(xiàn)象較多。同時(shí),該算法選擇了一種更為合理的方法來設(shè)置窗口大小。實(shí)驗(yàn)結(jié)果顯示,標(biāo)簽在兩種運(yùn)動(dòng)模式下,DCATMS算法的清洗效果比SMURF算法有顯著提高,前者產(chǎn)生的平均錯(cuò)誤數(shù)量比后者降低了51%,基本可以達(dá)到對(duì)RFID漏讀數(shù)據(jù)的清洗要求。但DCATMS算法依然存在一定的缺陷。該算法中提出的標(biāo)簽運(yùn)動(dòng)模型僅考慮標(biāo)簽與閱讀器之間的位置關(guān)系,由于RFID閱讀過程的復(fù)雜性,其不僅能反映標(biāo)簽的位置信息,同時(shí)也能反映出標(biāo)簽讀取的時(shí)刻。在標(biāo)簽動(dòng)態(tài)檢測(cè)機(jī)制中,若能將標(biāo)簽位置信息與時(shí)間相結(jié)合,可能會(huì)更加準(zhǔn)確地判斷標(biāo)簽的動(dòng)態(tài)變化。此外,該算法有待在大量RFID標(biāo)簽的實(shí)際應(yīng)用環(huán)境下進(jìn)一步檢驗(yàn)。

參考文獻(xiàn)

[1]Want R.An introduction to RFID technology[J].Pervasive Computing,2006,5(1):25-33.

[2]Popovski P,Fyhn K,Jacobsen R M,et al.Robust statistical methods for detection of missing RFID tags[J].IEEE Wireless Communications,2011,18(4):74-80.

[3]Rizvi S,Jeffery S R,Krishnamurthy S,et al.Events on the edge[C].Boston:Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data,2005.

[4]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Korea:VLDB,2006.

[5]樊華.面向物聯(lián)網(wǎng)的RFID不確定數(shù)據(jù)清洗與存儲(chǔ)技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2013.

[6]歐俊豪,王家生,徐漪萍,等.應(yīng)用概率統(tǒng)計(jì)[M].2版.天津:天津大學(xué)出版社,2004.

[7]Jeffery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data streams[C].Porland:Proceedings of the 32nd International Conference on Very Large Data Bases,2006.

[8]陳翅剛.制造物聯(lián)網(wǎng)海量RFID感知數(shù)據(jù)智能清洗處理技術(shù)研究[D].廣州:廣東工業(yè)大學(xué),2014.

[9]封慧英,周良.基于滑動(dòng)窗口的RFID自適應(yīng)數(shù)據(jù)清洗算法[J].計(jì)算機(jī)與現(xiàn)代化,2015(1):31-36.

RFID Missing Data Cleaning Algorithm Based on Adaptive Sliding-window

CHU Tian1,PAN Jinman1,DU Lei2

(1.Postgraduate Training Brigade,Military Transportation University,Tianjin 300161,China;2.General Courses Department,Military Transportation University,Tianjin 300161,China)

AbstractThe original RFID data must be cleaned to ensure the accuracy of data due to the problem of RFID missing data in reading.In view of problems that exist in the SMURF,which is the most effective cleaning algorithm based on sliding-window in the current,this paper proposes an improved algorithm for accurately detecting the tag’s dynamic changing with a more reasonable mechanism to set sliding-window.The experimental results show that the proposed algorithm enjoys fewer errors and better performance than the SMURF algorithm during the cleaning.

KeywordsRFID;missing data in reading;data cleaning;sliding-window;tag motion

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)04-024-05

doi:10.16180/j.cnki.issn1007-7820.2016.04.007

作者簡(jiǎn)介:褚天(1989—),男,碩士研究生。研究方向:交通信息工程及控制。潘金滿(1984—),男,碩士研究生。研究方向:交通信息工程及控制。

收稿日期:2015- 09- 06