利用RFID數(shù)據(jù)時(shí)空冗余性提升數(shù)據(jù)清洗性能

李晶　張磊　王斌

摘要：無線射頻識(shí)別（RFID）技術(shù)已經(jīng)大規(guī)模應(yīng)用于許多數(shù)據(jù)采集方面的應(yīng)用。然而由于電磁干擾、元器件質(zhì)量等因素，原始采集的RFID數(shù)據(jù)通常是低質(zhì)量的，并且包含許多異常信息。目前已有的RFID數(shù)據(jù)清洗技術(shù)沒有完全利用RFID數(shù)據(jù)的時(shí)空冗余性、環(huán)境先驗(yàn)知識(shí)及應(yīng)用限制等特征。本文提出了一種基于貝葉斯推理的RFID數(shù)據(jù)清洗方法，充分利用了數(shù)據(jù)的冗余性。

關(guān)鍵詞：時(shí)空冗余性；概率算法；貝葉斯推理；數(shù)據(jù)清洗

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）29-0232-03

1 引言

RFID是一種允許物體在一定范圍內(nèi)，被自動(dòng)識(shí)別而無需直接觀測(cè)到的電子標(biāo)簽技術(shù)，采用電磁和響應(yīng)交換[1，2]。目前大量的零售商如沃爾瑪、中國(guó)EMS、思科在倉庫和分發(fā)中心的存貨系統(tǒng)中安裝RFID技術(shù)。然而RFID閱讀器收集到的數(shù)據(jù)是不可靠的，中間件系統(tǒng)需要糾正閱讀數(shù)據(jù)并提供清洗過的數(shù)據(jù)。目前大部分解決方案是清洗一組閱讀器采集的數(shù)據(jù)[3]。然而，已有的方法主要存在三個(gè)方面的限制：

1）未利用RFID數(shù)據(jù)的時(shí)空冗余性提高數(shù)據(jù)的準(zhǔn)確性。由大量擁有重復(fù)檢測(cè)區(qū)域并且靜止的閱讀器可產(chǎn)生數(shù)據(jù)的空間冗余，移動(dòng)的閱讀器在一段時(shí)間內(nèi)持續(xù)的數(shù)據(jù)采集可形成數(shù)據(jù)的時(shí)間冗余。

2）沒有有效地利用標(biāo)簽物體和RFID閱讀器的先驗(yàn)知識(shí)提高數(shù)據(jù)的準(zhǔn)確性。

3）未有效的利用特定應(yīng)用中的限制（比如一個(gè)房間或書架的容量）清洗數(shù)據(jù)。

本文提出一種考慮到這三種限制的新方法，充分利用數(shù)據(jù)的冗余性、先驗(yàn)知識(shí)和應(yīng)用限制來提高準(zhǔn)確性和數(shù)據(jù)清洗的有效性。

2 貝葉斯推理框架及n元檢測(cè)模型

2.1貝葉斯推理框架

首先描述如何基于貝葉斯推理的方法來處理冗余數(shù)據(jù)和先驗(yàn)知識(shí)。貝葉斯推理是根據(jù)觀察（y）得出假設(shè)（x）可能性的統(tǒng)計(jì)學(xué)方法。貝葉斯推理表明后驗(yàn)知識(shí)跟先驗(yàn)知識(shí)息息相關(guān)，可表示為[pxy∝pyxpx]。

假設(shè)在檢測(cè)環(huán)境中有m個(gè)區(qū)域和n個(gè)物體，每個(gè)區(qū)域中間位置部署一個(gè)閱讀器。oi表示擁有ID為i的物體。對(duì)于每個(gè)oi，它的位置表示為一個(gè)隨機(jī)變量hi。因此，n個(gè)物體在m個(gè)區(qū)域可能的分布表示為一個(gè)向量[H=h1，h2，…，hn]。hi表示物體oi所在的位置。例如h1=2表示物體o1當(dāng)前在區(qū)域2內(nèi)。對(duì)于區(qū)域j中的閱讀器，從物體oi標(biāo)簽接受到的未處理的數(shù)據(jù)（0或1）定義為zij。從m個(gè)閱讀器每次完全的掃描得到的未處理數(shù)據(jù)矩陣可以表示為[n×m]階矩陣[?]=|zij|。那么貝葉斯定理可以如公式（1）所示，其中[postH?]表示根據(jù)給定未處理數(shù)據(jù)[?]得到后驗(yàn)位置矢量[H]，假設(shè)滿足以下約束：如果[H]無效，[postH?]=0；如果[H]有效，[postH?]>0；如果[H1]比[H2]可能性大，則[postH1?]>[postH2?]。如果在未處理數(shù)據(jù)矩陣中zij=1而實(shí)際中物體oi沒在區(qū)域j中，那么zij就是誤報(bào)。

為了計(jì)算[postH?]，假定每個(gè)閱讀器檢測(cè)不同的標(biāo)簽是獨(dú)立的（閱讀器成功檢測(cè)到一個(gè)標(biāo)簽不影響它成功檢測(cè)到另一個(gè)標(biāo)簽），可以得到公式（2）。假定不同的hi（物體位置）之間是獨(dú)立的，并且假定對(duì)同一物體每個(gè)閱讀器的檢測(cè)是獨(dú)立的，每個(gè)物體的先驗(yàn)分布不依賴于其他物體。由此可得到公式（3）。采用格式化常量[α]重寫公式（3）可獲得公式（4），對(duì)已給定的臟數(shù)據(jù)[?]和假設(shè)[H]（每個(gè)物體的位置），可以基于公式（4）得到假設(shè)的可能性。

我們的目標(biāo)是創(chuàng)造一個(gè)大的有效假設(shè)樣本集，而有效假設(shè)采樣的一個(gè)先決條件是可以精確計(jì)算每個(gè)假設(shè)的后驗(yàn)概率。

2.2 RFID閱讀器檢測(cè)模型

計(jì)算公式（4）中每個(gè)樣本的先驗(yàn)概率的關(guān)鍵是準(zhǔn)確計(jì)算p（zij|hi）的可能性。為此引入n-狀態(tài)檢測(cè)模型來精確的計(jì)算其可能性。

RFID的物理特性決定其數(shù)據(jù)采集和傳輸是不可靠的。閱讀器的檢測(cè)范圍可以分為主要檢測(cè)區(qū)域和次要檢測(cè)區(qū)域，其中主要檢測(cè)區(qū)域在距離閱讀器較近的范圍內(nèi)，其閱讀率可以維持在95%，而次要檢測(cè)區(qū)域的閱讀率呈直線下降趨勢(shì)，超出閱讀器的檢測(cè)范圍時(shí)，閱讀器的閱讀率惡化為0。

為了解決這個(gè)問題并利用重復(fù)的數(shù)據(jù)，本文提出了一個(gè)n-狀態(tài)檢測(cè)模型，將閱讀器的所有檢測(cè)區(qū)域分成成許多子區(qū)域，每一個(gè)區(qū)域都對(duì)應(yīng)唯一的讀取率。不同狀態(tài)的讀取率構(gòu)成一個(gè)等差數(shù)列。

為了捕獲這種相關(guān)性，選擇n=3（生成3-狀態(tài)檢測(cè)模型）具有更好的可行性。當(dāng)系統(tǒng)有更多可靠的閱讀器就有更少的不確定性，3-狀態(tài)模型比2-狀態(tài)在目標(biāo)定位上提供更多的信息。根據(jù)讀取率和信息熵之間的關(guān)系可以證明，信息熵隨著讀取率的增大而減小，但是n的取值也不是越大越好，實(shí)踐應(yīng)用中3-狀態(tài)檢測(cè)是比較理想的模型。

3 具有約束的采樣算法

由于公式（4）容易計(jì)算但難于采樣，本文提出一種對(duì)采樣進(jìn)行約束管理的Metropolis- Hastings采樣算法（簡(jiǎn)記為MH-C），算法產(chǎn)生的每個(gè)樣本可以自動(dòng)的滿足所有的約束，可有效地從先驗(yàn)分布中抽采樣本。

馬爾可夫鏈蒙特卡爾理論（MCMC）是通過模擬一個(gè)馬爾可夫鏈來從狀態(tài)空間采樣。當(dāng)樣本的數(shù)目足夠大時(shí)，所有的樣本都能隨機(jī)獲得后驗(yàn)知識(shí)。因此，可直接構(gòu)建馬爾可夫鏈來近似逼近后驗(yàn)概率。選擇MCMC而不是其他采樣技術(shù)是因?yàn)镸CMC維持了樣本之間的相關(guān)性。在MCMC中，下一個(gè)樣本的選擇取決于當(dāng)前的樣本[8，9]。下面首先闡述如何利用采樣樣本的相關(guān)性來提高效率，定義如下術(shù)語：

定義1 候選樣本. 稱從采集器獲得的任何樣本為候選樣本，一個(gè)合格的樣本是滿足所有約束的候選樣本。

通常采用的完全隨機(jī)采樣方法中，由于相鄰樣本相關(guān)性的丟失，產(chǎn)生獨(dú)立樣本的效率將受到影響?？梢岳脴颖局g的相關(guān)性來改善采樣效率，合格的采樣空間是完全采樣空間的一個(gè)子集。

盡管MCMC提高了采樣效率，MCMC所產(chǎn)生的樣本不一定是一個(gè)合格的樣本。雖然原始的Metropolis- Hastings算法可以通過構(gòu)造馬爾可夫鏈來評(píng)估后驗(yàn)分布，但它沒有把約束條件考慮進(jìn)來。如果利用約束采樣，將會(huì)拒絕許多樣本，這是由于它們是不合格的樣本。

為了在采樣中利用約束條件，提出了MH-C方法。MH-C的每個(gè)區(qū)域都與資源描述符的變量相關(guān)，當(dāng)前的資源描述符表示有多少相關(guān)資源仍然是可用的。假設(shè)使用一個(gè)變量DescriptorZonei跟蹤區(qū)域i能可用的空白資源，初始的DescriptorZonei值是區(qū)域i內(nèi)能容納的最大容量。那么，占用空間值為Volumeobjectj的j物體能否存儲(chǔ)在i區(qū)域可以表示為：

DescriptorZonei= DescriptorZonei -Volumeobjectj （5）

只有在DescriptorZonei不為0時(shí)資源分配才是可行的，否則必須重新采樣直到找到一個(gè)滿足所有約束新的分配。因此，資源分配是否可行的問題可以簡(jiǎn)化為檢測(cè)描述符的值。

MH-C算法基于Dobject的空間矢量通過空間迭代獲得每個(gè)樣本，如果任何分配的資源符小于0，那么目前的樣本不可能成為合格樣本，應(yīng)該丟棄當(dāng)前的值并重新選擇維度進(jìn)行采樣。構(gòu)造一個(gè)隨機(jī)游走鏈，選擇關(guān)于步長(zhǎng)的一致方案分布。MH-C算法的描述如下，表1給出了相關(guān)符號(hào)的含義。

Algorithm 1 支持約束的Metropolis-Hastings 采樣算法

1） 初始化[S] = ?，獲得原始數(shù)據(jù)矩陣[?]

2） 載入n-狀態(tài)檢測(cè)模型

3） 將資源描述符初始化為最大容量.

4） 初始化[C]，在Post（[H]|[?]）中隨機(jī)選擇合格的樣本作為開始點(diǎn).

5） for Cycle = 2 to E+B do

6） for j = 1 to Dobject do

7） repeat

8） Pj = Cj+ Random（-S，S） {根據(jù)當(dāng)前值和建議步長(zhǎng)生成新整數(shù)}

9） if Pj < 1 then

10） Pj = 1+ （1-Pj ）{溢出并重設(shè)}

11） end if

12） if Pj > Dzone then

13） Pj = Dzone -（Pj -Dzone）

14） end if

15） until所有與引用區(qū)域相關(guān)的資源描述符值不小于0，在接受當(dāng)前對(duì)象的建議分配之后

16） j ← j + 1

17） end for

18） Jitter←生成0，1之間的一個(gè)隨機(jī)數(shù)

19） if Jitter ≤ min（1， [Post（P|?）Post（C|?）]） then

20）[C] = [P] //Metropolis-Hastings采樣

21） end if

22） 將[C]添加到[S]作為下一個(gè)樣本

23） 重置所有資源描述符

24） Cycle ← Cycle + 1

25） end for

算法1中用到的符號(hào)含義如下：[S]：樣本集， [C]：馬爾可夫鏈上當(dāng)前的樣本，[P]：馬爾可夫鏈上建議的樣本，Cj：[C]的第j維，Pj：[P]的第j維，E：有效樣本個(gè)數(shù)，B：老化階段的樣本個(gè)數(shù)，S：統(tǒng)一建議分布步長(zhǎng)，Dobject：監(jiān)測(cè)對(duì)象的總數(shù)，Dzone：區(qū)域總數(shù)。

4 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證算法性能，本文模擬大型倉庫生成檢測(cè)物品的RFID數(shù)據(jù)集，讓物體對(duì)應(yīng)盒子，區(qū)域?qū)?yīng)貨架。采用3-狀態(tài)檢測(cè)模型實(shí)現(xiàn)MH-C算法，并且作為對(duì)比，擴(kuò)充基于SIS的方法[4]，增加利用重復(fù)讀數(shù)功能，達(dá)到可對(duì)比程度。

4.1實(shí)驗(yàn)數(shù)據(jù)及測(cè)度

本文設(shè)計(jì)了模擬器生成大型倉庫的隨機(jī)產(chǎn)生分布矩陣（行表示物體，列表示貨架（區(qū)域））和具有噪聲的RFID原始數(shù)據(jù)，通過100次試驗(yàn)來驗(yàn)證MH-C方法在重建的效率和準(zhǔn)確性方面相對(duì)于SIS的性能。

定義2 前k成功率. 真實(shí)位置匹配了重建分布中前k個(gè)預(yù)測(cè)位置的箱子個(gè)數(shù)在總共箱子個(gè)數(shù)中所占的百分比，k=1時(shí)表示最佳成功率。

4.2 實(shí)驗(yàn)描述及性能分析

本節(jié)模擬5000個(gè)箱子和200個(gè)貨架的大型倉庫環(huán)境，比較MH-C和SIS在重建效率和準(zhǔn)確性方面的性能。在重建精度實(shí)驗(yàn)中，隨機(jī)生成的真實(shí)分布矩陣和100個(gè)相應(yīng)的RFID蘊(yùn)含噪聲的矩陣。在每個(gè)重建分布中，記錄采樣時(shí)間，計(jì)算平均K-L散度，5000例的最佳成功率（每個(gè)結(jié)果進(jìn)行平均5000次位置查詢）。

實(shí)驗(yàn)1：重建準(zhǔn)確性

在本實(shí)驗(yàn)中，改變合格樣本的數(shù)據(jù)、數(shù)據(jù)冗余度和每個(gè)閱讀器管理貨架的數(shù)目，研究這些因素對(duì)重建準(zhǔn)確性的影響。

實(shí)驗(yàn)2：冗余度對(duì)算法性能的影響

接下來，通過改變數(shù)據(jù)的冗余度研究MH-C和SIS的重建準(zhǔn)確度的性能。因?yàn)檎`報(bào)實(shí)際上是閱讀器成功檢測(cè)到了在次要檢測(cè)區(qū)域的物體，使用在次要區(qū)域的讀取率來定義數(shù)據(jù)冗余程度。越大的冗余程度表明一個(gè)閱讀器越可能檢測(cè)到鄰近區(qū)域（貨架）內(nèi)的物體。

實(shí)驗(yàn)3：閱讀器管理貨架數(shù)目對(duì)算法性能的影響

為了使部署在倉庫中的閱讀器更加有效率，用戶可能要為每個(gè)閱讀器分配多個(gè)貨架。目前實(shí)際應(yīng)用場(chǎng)景中，一個(gè)普通的RFID閱讀器的整體檢測(cè)區(qū)域幾乎沒有超過5米的，因此設(shè)置每個(gè)閱讀器管理貨架數(shù)目從1到6變化。

5結(jié)論

實(shí)際應(yīng)用中，RFID設(shè)備所接收的數(shù)據(jù)被是不可靠的。本研究提出采用貝葉斯推理方法清洗RFID原始數(shù)據(jù)，從而可以充分利用具有時(shí)空冗余的讀數(shù)。為了估計(jì)位置信息和聚合查詢結(jié)果，本方法采用先驗(yàn)知識(shí)來量化每個(gè)物體的不確定位置和每個(gè)區(qū)域的剩余容量，并且提出了n-狀態(tài)檢測(cè)模型捕獲可能性，設(shè)計(jì)并實(shí)現(xiàn)了MH-C算法。實(shí)驗(yàn)證明本文提出的方法可有效的環(huán)境中從后驗(yàn)分布環(huán)境中符合約束采樣，可以廣泛地應(yīng)用于物聯(lián)網(wǎng)實(shí)際應(yīng)用。

參考文獻(xiàn)：

[1]L. Sullivan. RFID Implementation Challenges Persist， All This Time Later. InformationWeek， October 2005.

[2] M. J. Franklin， S. R. Jeffery， S. Krishnamurthy， F. Reiss， S. Rizvi， E. Wu， O. Cooper， A. Edakkunni， and W. Hong. Design Considerations for High Fan-In Systems： The HiFi Approach. In CIDR， pages 290-304， 2005.