RFID 數據在供應鏈中的過濾算法研究

劉 峰

（吉林化工學院，信息與控制工程學院，吉林 132011）

RFID 數據在供應鏈中的過濾算法研究

劉 峰

（吉林化工學院，信息與控制工程學院，吉林 132011）

無線射頻識別技術已經被認為是供應鏈管理中必不可少的功能，特別是對于零售商們做出決策的數據收集能力。然而，許多錯誤的讀數卻可能導致完全相反的決定。在本文中，我們提出7種模型及其匹配算法用以過濾那些原始數據，以便管理者能夠在供應鏈管理中更好地使用收集到的RFID數據。

RFID；數據過濾；多數投票法；隱馬爾可夫鏈

0 引言

RFID徹底改革了供應鏈管理，因為它幫助零售商決定在正確的時間、正確的地點提供正確的產品。首先，RFID能夠使整個供應鏈流程對讀寫器可見而標簽卻不必在直接的視線范圍內。其次，識別的特性使 RFID可用于掃描托盤上的集裝箱，這就給企業提供了商品數量的信息——有多少商品、多少次被交付。第三，不久就能夠看到 RFID在其它技術不能適用的環境中使用。此外，它還能夠用于有人身危險的地方來代替人類的工作。

現在，RFID大規模實施的主要障礙是它會產生超過30%的標簽讀取的錯誤[1]。就此而言，基于這些數據做出的決策不可能是有效的。這些挑戰可能是由于傳送的數據只是原始數據而沒有經過過濾這種情況造成的，錯誤讀數的原因可能是信號折射和偏轉、衰減、多點輸入多點輸出、讀寫器的精確度[2]。

許多推薦的解決方案被提出用于過濾這些錯誤的讀數，這樣做的一個重要原因是為了使這些原始數據仍然保持原狀。許多學者在著作中都很重視基于滑動窗口的方法，他們相信增加 RFID的讀取頻率將會降低錯誤讀數的比率。在做這項工作的時候，Y Bai移除噪音、清除副本[3]，而Shawn R. Jeffery則認為環境狀況是決定滑動窗口大小最復雜的因素[4]，所以他們提供了SMURF（自適應平滑過濾）來改善RFID所處環境的動力學狀況[5]。然而，有時讀寫器的讀出數據一直無效，或者信號強度不足以生成足夠的正確數據，在這種意義上，以上方法都是不夠的。如果那樣的話，即使能夠提供自適應的窗口大小，錯誤讀數仍然不能消除。其他一些學者也在RFID的中間件中利用系統結構來解析、過濾和聚合數據[6,7,8]。

在本文中，我們提出7種模型及其匹配算法用以過濾那些原始數據，以便管理者能夠在供應鏈管理中更好地使用收集到的RFID數據。

1 模型 1、2、3[9,10]

在這些模型中，我們假設關注的對象在一個傳送帶上傳送，兩臺讀寫器位于傳送帶兩邊，每個對象安裝三個標簽。

模型1算法：

1、兩臺讀寫器就對象的存在進行多數投票。因為是兩臺讀

寫器讀取對象的3個標簽，所以應該得到6個讀數。如果6個讀數中超過3個相同，我就選取其（‘0’或‘1’）作為它的讀數。

2、如果以上規則不能有效，也就是說出現3對3的矛盾讀數，我們將依賴于更好的讀寫器，意即這臺讀寫器在前10個讀數當中提供一致的讀數。在那種情況下，這臺讀寫器將最有可能給我們提供可靠的讀數。

3、如果很不幸，兩臺讀寫器兩次出現同樣的狀況，那么我們只采用后一次讀數循環的數據。

模型2算法：

1、在本算法中，我們不做多數投票。對于每一個對象，我們在三個嵌入式標簽中使用一個較好的，只對較好的標簽比較兩者讀數。如果來自兩臺讀寫器的讀數相同，可以認為是關注對象的存在形成了相同的讀數。

2、如果兩臺讀寫器對于較好的標簽讀數不同，我們取第二個標簽作為目標讀數并比較標簽二的兩個讀數。如果兩臺讀寫器對于標簽二的讀數相同，可以認為是關注對象的存在形成了相同的讀數。

3、如果兩臺讀寫器對于標簽二讀數不同，我們取第三個標簽作為目標讀數并比較標簽三的兩個讀數。如果兩臺讀寫器對于標簽三的讀數相同，可以認為是關注對象的存在形成了相同的讀數。

模型3算法：

1、兩臺讀寫器就對象的存在進行多數投票。因為是兩臺讀寫器讀取對象的3個標簽，所以應該得到6個讀數。如果6個讀數中超過3個相同，我就選取其（‘0’或‘1’）作為它的讀數。

2、如果以上規則不能有效，也就是說出現3對3的矛盾讀數，我們將依賴于更好的讀寫器，意即這臺讀寫器在前10個讀數當中提供一致的讀數。在那種情況下，這臺讀寫器將最有可能給我們提供可靠的讀數。

3、如果很不幸，兩臺讀寫器兩次出現同樣的狀況，那么我們只采用后一次循環的數據。

4、在我們通過標簽得到足夠的讀數后，我們可以用隱馬爾可夫鏈模擬整個過程，以使讀數的結果能夠得到優化。

我們知道，在隱馬爾可夫模型中，狀態不是直接可見的，但依賴于狀態的輸出是可見的。并且在這個獨特的過程中，我們知道一個存在的標簽趨向于將存在的標簽納入它的鄰域內。因此，我們有下列假設，如圖1所示。

圖1 隱馬爾可夫模型Fig.1 Hidden markov model

使用以上三個模型，我們對1000個讀取對象讀取10次來模擬錯誤讀取率，并且我們也包含了三個標簽一直在或不在讀取對象當中的情況。此外，對于讀數準確率的三種概率為0.4、0.7和0.9，這樣結果就有9種可能的組合。

通過結果圖我們看到，模型3在三種模型里性能最佳，這是由于它能夠糾正不可能的讀數這種特性。圖中所示三種模型都顯示出隨著概率的增長而錯誤讀取率降低的趨勢，這應該是合理的，因為讀寫器的準確率是錯誤讀取率的直接影響因素。隨著讀寫器讀到更少的錯誤數據，結果可以更好。還可以看出，當讀寫器的讀數準確率都達到0.5以上時，模型3幾乎不會提供任何錯誤讀數。絕大多數時間都是非常好的結果，讀寫器讀數正確而不是錯誤。而與模型2比起來，模型1確實更優，因為我們對于錯誤讀數設想的幾乎所有情況它都能明確執行，除了讀寫器的讀數準確率都低于50%這種情況。在這種情況下，兩臺讀寫器給出的結果可能還不如我們只是彈出一枚硬幣，然后隨機選擇存在或不存在的結果。然而，雖然它是一種非常糟糕的情況，在實踐中這種情況卻幾乎不能發生，因為讀寫器讀數準確率都低于50%的環境很少見，并且對于正確性使用多數投票的方法比依賴于更好的讀寫器進行隨機選擇要好。

圖2 錯誤讀取率Fig.2 False reading rate

而且，從圖中還可以看到，對于模型1和模型2來說，P2與P3、P4與P5、P7與P8這幾種情況下錯誤讀取率情況幾乎完全一樣，這主要是因為它們被置于這樣的條件下：兩臺讀寫器都修改它們的讀數準確率，以便無論每一個的選擇是什么，它們對于選擇的概率組合應該是一樣的。僅舉一例：P1假設讀寫器1讀數準確率為0.4，讀寫器2為0.7；而P2是另一種情況，即讀寫器2讀數準確率為0.4，讀寫器1為0.7。從常識上來說我們也應該知道，它們是一樣的。

對于推薦的隱馬爾可夫鏈，我們置于這樣的假設下：如果前一個標簽存在，下一個很可能是存在的。做到這一點有切實可行的辦法——在供應鏈系統的正規環境下，我們總是看到標簽和物品被整齊的排列，以便能夠在傳送帶上更好的傳送，而且大多數時候它們連續出現。在供應鏈系統環境下，這是一個合理的假設。然后，在這種情況下，我們用維特比算法計算隱馬爾可夫鏈提供的讀寫器讀數的統計結果。

2 模型A、B、C、D[9,10]

在這些模型中，我們同樣假設關注的對象在一個傳送帶上傳送，兩臺讀寫器位于傳送帶兩邊，每個對象安裝兩個標簽。但是，這兩個標簽不同，一個是嵌入對象的目標標簽，另一個是帶有我們能夠準確處理的連續編號的標簽，在托盤上。

對于托盤上的帶有連續編號的標簽，我們可以用這種方式處理：我們把一個連續編號的讀數與它相鄰的讀數進行比較，如果可比我們就記為存在的1，如果不可比我們就記為不存在的0。例如，如果我們得到前后標簽的讀數為{77，1000,79}，我們應該意識到中間的讀數是錯的，所以我們把托盤標簽看作不存在。既然我們能夠準確處理托盤標簽，研究它就是有意義的，因為它將必然減少該系統正向錯誤讀數（即讀數顯示存在而標簽其實并不在讀寫器讀取范圍內）。

模型A算法：

1、讀寫器根據兩個標簽的相同讀數判定存在。如果讀寫器從兩個標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

2、如果以上的結果是存在，那么我們檢測托盤標簽的連續編號。如果相鄰比較中連續編號越界，則仍然表示不存在。

3、否則，隨機選擇0或1。

模型B算法：

1、讀寫器根據兩個標簽的相同讀數判定存在。如果讀寫器從兩個標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

2、不再查閱連續編號，只是隨機選擇0或1。

模型C算法：

1、兩臺讀寫器根據兩個目標標簽的相同讀數判定存在。如果兩臺讀寫器從目標標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

2、如果以上條件無效，兩臺讀寫器根據兩個托盤標簽的相同讀數判定存在。如果兩臺讀寫器從托盤標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

3、如果以上的結果是存在，那么我們檢測托盤標簽的連續編號。如果相鄰比較中連續編號越界，則仍然表示不存在。

4、否則，在0.25至1的概率范圍內隨機選擇狀態。

模型D算法：

1、兩臺讀寫器根據兩個目標標簽的相同讀數判定存在。如果兩臺讀寫器從目標標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

2、如果以上條件無效，兩臺讀寫器根據兩個托盤標簽的相同讀數判定存在。如果兩臺讀寫器從托盤標簽獲得的兩個讀數是相同的結果，就可以認為確實是相同的結果。

3、否則，在0.25至 1的概率范圍內隨機選擇狀態。

為了模擬模型a、b、c、d，我們使用四個準確性概率如下所示：

p=[0.8 0.85 0.9 0.95]

意為如果標簽在讀寫器的掃描范圍內確實存在，在第一個例子中讀寫器將其讀為存在的概率是0.8，其他的也一樣。

在模型a和b中，將只考慮一臺讀寫器，而在模型c和d中，則包括兩臺讀寫器和兩個標簽。作為更一般的情況，我們設置存在和不存在為 0.5和0.5，并假設兩個標簽存在或不存在都處于同樣的環境中，也就是說如果關注目標存在，那么兩個標簽在讀寫器讀取范圍內都存在，而如果關注目標不存在，那么兩個標簽在讀寫器讀取范圍內都不存在。并且，我們還會運行系統10次，每次1000個讀數，以便給出一個更穩定的結果。

正向錯誤圖顯示，在那些存在正向錯誤讀數的實例中，帶有連續編號的模型總是比那些不帶的要好。這是因為，當關注對象不存在而讀寫器顯示 1時，將被連續的托盤標簽糾正，也就是說每當兩臺讀寫器就對象的存在取得一致時，它們必定會查閱連續編號來檢驗是否為真。而且，我們已經知道我們能夠準確處理連續編號或者連續標簽，所以顯然我們可以清除正向意義上的錯誤數據。相比于一臺讀寫器，兩臺讀寫器總是更好，正像模型c和模型d在正向讀取率上勝過模型a和模型b。這一點很容易檢驗，因為如果有兩臺讀寫器，隨著讀寫器準確率增加，它們讀數錯誤的可能性更小。這種現象的原因與模型1、2、3中所提到的一樣。

從負向錯誤圖來看，在那些存在負向的錯誤讀數（即讀數顯示不存在而標簽其實在讀寫器讀取范圍內）的實例中，帶有連續編號的模型幾乎與那些不帶的性能相同。這一點應該很清楚，因為連續編號與負向的錯誤讀數無關。也就是說，連續標簽所做的工作就是當不存在時糾正存在標志。然而我們能看到，當兩臺讀寫器都指明不存在時，我們不需要去查閱連續編號。在那種情況下，對于讀數的最終結果不會改變太多。而且，他們也顯示出隨著讀寫器準確率增加而減少的趨勢。

通過所有的性能分析圖可以斷定，帶有連續編號的模型在存在錯誤讀數的情況下總是比那些不帶的要好，并且模型c是四個模型中最好的一個。這是由于模型c不僅使用兩臺讀寫器增加發現不正確的可能性，而且查閱托盤上的連續編號，更易于找到錯誤的正向讀取。而且，隨著讀寫器準確率的提高，它們的性能趨同。

3 結論

可以看到，錯誤讀取率是 RFID大范圍應用最大的難題，它不僅影響管理者的決策，而且極大地影響商品的利潤，因為它給使用者提供的是不可靠的原始數據，無論對于現在的決策還是將來的使用都無法消除。

圖3 正向錯誤讀取率Fig.3 False positive reading rate

圖4 負向錯誤讀取率Fig.4 False negative reading rate

圖5 錯誤讀取率Fig.5 False reading rate

本文所示，我們提供7種模型來給出關于讀數準確率情況的實例。前三個模型，模型 1、模型 2和模型 3，我們比較了三個標簽和兩臺閱讀器的情況。顯然，對最終結果做多數投票比選擇更好的標簽對于決定標簽是否存在要更好。而且，我們提供了一種隱馬爾可夫鏈模型來處理選擇的數據。因為當一個對象存在時，就在它旁邊的下一個對象應該也存在的可能性更大，所以我們所做的就是使用這種轉換概率來對真實情況做最準確的推測，即用維特比算法計算正確的讀數。并且，從仿真結果我們完全能夠確信，使用這種隱馬爾可夫鏈模型我們能夠取得更好的讀數準確率。

在隨后的例子中，我們以比較連續的托盤標簽的方法模擬了四種其他的模型，其中標簽所帶連續編碼我們能夠準確處理。通過模擬一臺讀寫器和兩個標簽的情況，兩臺讀寫器和兩個標簽的情況，我們最終確定，對于正向讀取的情況，連續編號確實能夠提高讀數準確率。然而，對于負向讀取就不是這樣了，因為我們從來沒有對不存在的情況查閱連續編碼。在比較了四種情況之后，我們得出結論：兩臺讀寫器和兩個帶有連續編號的托盤標簽能夠在實際當中給出最全面的結果。

但是，之前的例子都是基于這種假設：兩臺讀寫器相互獨立，所以他們不會影響彼此的結果。如果它們在時間或空間的上相互關聯，或者如果我們考慮信號的多重路徑，那么在這種情況下，它們將得到改善，結果也將更佳。

[1] S.R.Jeffwey, et al. A pipeline framework for online cleaning of sensor data streams[C]//ICDE, 2006.

[2] Y.F.Niederman, et al. Examining RFID applications in supply chain management[J]. Commun: ACM, 2009, 46(2): 586-593.

[3] BAI Yi-jian, et al. Efficiently filtering RFID data streams[C]//Clean DB, 2006.

[4] Shawn R.Jeffery, et al. Adaptive cleaning for RFID data streams[C]//VLDB, 2006.

[5] 尚明, 蔣泰, 李立憲. RFID中間件數據過濾方法研究[J].廣西科學院學報, 2014, 30(1): 47-50.

[6] 孫紅, 厲彥剛, 陳世平. RFID中間件數據處理研究[J]. 上海理工大學學報, 2014, 36(3): 234-238.

[7] 曹國瑞, 解巖. 基于RFID的計量器具物資標簽批量讀取算法. 科技通報, 2015, 31(8): 30-32.

[8] 羅元劍, 姜建國, 王思葉等. 基于有限狀態機的RFID流數據過濾與清理技術. 軟件學報, 2014, 25(8): 1713-1728.

[9] TU Yu-ju, Selwyn Piramuthu. A decision-support model for filtering RFID read data in supply chain[C]//IEEE Transactions on system, man, and cybernetics, 2010.

[10] 賈紅梅, 李文杰. 面向倉儲管理的RFID數據過濾模型研究.計算機應用與軟件, 2014, 31(2): 74-76.

RFID Data Filtering Algorithm in Supply Chain

LIU Feng
(College of information and control engineering, Jilin Institute of Chemical Technology, Jilin 132011, China)

Radio-frequency identification technology has been regarded as an essential role in supply chain management especially for its data collection capability for retailers to make decisions. However, lots of false readings could result in totally opposite resolutions. In this paper, we present seven models and their corresponding algorithms to filter these raw data so that managers can make good use of collected RFID data in supply chain management.

RFID; DataFiltering; Vote for majorities; Hidden markov chain

TP312

A

10.3969/j.issn.1003-6970.2017.12.021

本文著錄格式：劉峰. RFID數據在供應鏈中的過濾算法研究[J]. 軟件，2017，38（12）：110-114

吉林省教育廳重點項目(吉教科合字[2014]第343號)

劉峰(1970-)，男，講師，計算機技術及應用。