RFID 數(shù)據(jù)在供應(yīng)鏈中的過濾算法研究

劉 峰

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

RFID 數(shù)據(jù)在供應(yīng)鏈中的過濾算法研究

劉 峰

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

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

RFID；數(shù)據(jù)過濾；多數(shù)投票法；隱馬爾可夫鏈

0 引言

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

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

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

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

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

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

模型1算法：

1、兩臺讀寫器就對象的存在進(jìn)行多數(shù)投票。因為是兩臺讀

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

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

3、如果很不幸，兩臺讀寫器兩次出現(xiàn)同樣的狀況，那么我們只采用后一次讀數(shù)循環(huán)的數(shù)據(jù)。

模型2算法：

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

2、如果兩臺讀寫器對于較好的標(biāo)簽讀數(shù)不同，我們?nèi)〉诙€標(biāo)簽作為目標(biāo)讀數(shù)并比較標(biāo)簽二的兩個讀數(shù)。如果兩臺讀寫器對于標(biāo)簽二的讀數(shù)相同，可以認(rèn)為是關(guān)注對象的存在形成了相同的讀數(shù)。

3、如果兩臺讀寫器對于標(biāo)簽二讀數(shù)不同，我們?nèi)〉谌齻€標(biāo)簽作為目標(biāo)讀數(shù)并比較標(biāo)簽三的兩個讀數(shù)。如果兩臺讀寫器對于標(biāo)簽三的讀數(shù)相同，可以認(rèn)為是關(guān)注對象的存在形成了相同的讀數(shù)。

模型3算法：

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

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

3、如果很不幸，兩臺讀寫器兩次出現(xiàn)同樣的狀況，那么我們只采用后一次循環(huán)的數(shù)據(jù)。

4、在我們通過標(biāo)簽得到足夠的讀數(shù)后，我們可以用隱馬爾可夫鏈模擬整個過程，以使讀數(shù)的結(jié)果能夠得到優(yōu)化。

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

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

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

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

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

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

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

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

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

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

模型A算法：

1、讀寫器根據(jù)兩個標(biāo)簽的相同讀數(shù)判定存在。如果讀寫器從兩個標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

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

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

模型B算法：

1、讀寫器根據(jù)兩個標(biāo)簽的相同讀數(shù)判定存在。如果讀寫器從兩個標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

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

模型C算法：

1、兩臺讀寫器根據(jù)兩個目標(biāo)標(biāo)簽的相同讀數(shù)判定存在。如果兩臺讀寫器從目標(biāo)標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

2、如果以上條件無效，兩臺讀寫器根據(jù)兩個托盤標(biāo)簽的相同讀數(shù)判定存在。如果兩臺讀寫器從托盤標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

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

4、否則，在0.25至1的概率范圍內(nèi)隨機選擇狀態(tài)。

模型D算法：

1、兩臺讀寫器根據(jù)兩個目標(biāo)標(biāo)簽的相同讀數(shù)判定存在。如果兩臺讀寫器從目標(biāo)標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

2、如果以上條件無效，兩臺讀寫器根據(jù)兩個托盤標(biāo)簽的相同讀數(shù)判定存在。如果兩臺讀寫器從托盤標(biāo)簽獲得的兩個讀數(shù)是相同的結(jié)果，就可以認(rèn)為確實是相同的結(jié)果。

3、否則，在0.25至 1的概率范圍內(nèi)隨機選擇狀態(tài)。

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

p=[0.8 0.85 0.9 0.95]

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

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

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

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

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

3 結(jié)論

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

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

圖4 負(fù)向錯誤讀取率Fig.4 False negative reading rate

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

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

在隨后的例子中，我們以比較連續(xù)的托盤標(biāo)簽的方法模擬了四種其他的模型，其中標(biāo)簽所帶連續(xù)編碼我們能夠準(zhǔn)確處理。通過模擬一臺讀寫器和兩個標(biāo)簽的情況，兩臺讀寫器和兩個標(biāo)簽的情況，我們最終確定，對于正向讀取的情況，連續(xù)編號確實能夠提高讀數(shù)準(zhǔn)確率。然而，對于負(fù)向讀取就不是這樣了，因為我們從來沒有對不存在的情況查閱連續(xù)編碼。在比較了四種情況之后，我們得出結(jié)論：兩臺讀寫器和兩個帶有連續(xù)編號的托盤標(biāo)簽?zāi)軌蛟趯嶋H當(dāng)中給出最全面的結(jié)果。

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

[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中間件數(shù)據(jù)過濾方法研究[J].廣西科學(xué)院學(xué)報, 2014, 30(1): 47-50.

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

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

[8] 羅元劍, 姜建國, 王思葉等. 基于有限狀態(tài)機的RFID流數(shù)據(jù)過濾與清理技術(shù). 軟件學(xué)報, 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數(shù)據(jù)過濾模型研究.計算機應(yīng)用與軟件, 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數(shù)據(jù)在供應(yīng)鏈中的過濾算法研究[J]. 軟件，2017，38（12）：110-114

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

劉峰(1970-)，男，講師，計算機技術(shù)及應(yīng)用。