食品質量追溯中RFID多標簽識別防碰撞算法

姚金玲 劉 婕 閆雪鋒

(1.天津職業大學，天津 300410；2.天津理工大學天津市先進機電系統設計與智能控制重點實驗室，天津 300384；3.天津職業技術師范大學，天津 300110)

隨著信息技術的快速發展，射頻識別(Radio Frequency Identification，RFID)技術由于其非接觸式信息交互、安全可靠信息傳輸、靈活快捷標識追溯等優點而被廣泛用于工業、農業和商業等領域[1]。在食品質量追溯過程中，尤其是在運輸和倉儲中，需要對整車貨品標簽進行批量識別。多標簽識別是RFID最為明顯的優勢，但當多個標簽同時發送標識信息時，其發送信號會在數據傳輸到讀取器時發生干擾形成碰撞[2]。碰撞不僅會降低系統的識別效率，還會導致識別時間變長，一定程度上限制了RFID技術的應用。

國內外學者對基于RFID標簽沖突檢測的防碰撞算法進行了大量研究，并取得了一定的成果，大部分防碰撞算法研究集中在ALOHA算法和二叉樹算法。王祖良等[3]提出了一種用于農產品可追溯性的標簽防碰撞自適應動態幀時隙ALOHA算法，該方法適用于設計的農產品追溯系統，大大提高了識別效率。與廣泛采用的國際標準相比，吞吐量提升了30%。潘雪峰等[4]提出了一種結合動態幀時隙ALOHA算法和生日悖論概率理論的RFID系統防碰撞算法，該方法可以有效提高標簽識別的準確性，減少識別過程的時間，提高射頻系統信道的利用率及系統性能。尚弘[5]提出了一種基于搜索樹的輕量級防碰撞方法，并設計了一種新的查詢響應模式(單查詢—雙響應)，可以提高標簽識別的效率。結果表明，采用雙響應模式和計數器觸發的單查詢模式可將整體通信開銷減少42%。賀曉霞等[6]提出了一種基于鎖定位的并行二進制分區(LPBS)防碰撞算法，該算法減少了讀取器和標簽之間發送的位數，同時降低了競爭時隙。仿真結果表明，大多數情況下，該算法在吞吐量和延遲方面均優于傳統的防碰撞算法。但是，上述研究并沒有全完消除空閑時隙，造成一部分時間和資源浪費，具有一定的局限性。

在食品質量追溯過程中，多標簽識別是追溯的關鍵，而多標簽識別不可避免地會產生碰撞。針對目前防碰撞算法查詢時間過程會產生大量的沉余，增加通信開銷，文章擬結合幀時隙ALOHA(Frame Slotted ALOHA, FSA)算法和最小均方誤差(Minimum Mean Square Error, MMSE)預編碼技術，提出一種RFID多標簽識別防碰撞算法，即預編碼幀時隙ALOHA算法，旨在為RFID多標簽技術的發展提供依據。

1 RFID多標簽識別技術基礎

1.1 RFID系統構成及工作原理

RFID系統由標簽、天線、讀取器和后臺數據庫系統4部分組成(圖1)。每個標簽都有一個唯一的ID號，該ID號使用電磁波和天線進行數據交換和能量傳輸[7]。天線是位于RFID系統標簽和讀取器之間的數據收發器。讀取器是RFID系統的信息傳輸站，負責讀取和寫入標簽信息。后端數據庫系統由中間件和信息處理等內部組件組成，對信息進行采集、分類、分析等[8]，還可以控制閱讀器和電子標簽之間的雙向標識。

1.后臺數據庫 2.讀取器 3.天線 4.RFID標簽 5.待識別食品

RFID的基本工作原理：在后臺數據庫系統的控制下，讀取器通過天線將特定頻率的電磁信號發送到標簽，標簽接收到該信號后，便會通過改變自身的阻抗來存儲ID，信息被調制并反射回來。閱讀器通過天線接收反射信號，對標簽信息進行解調和解碼，然后將其發送到數據庫系統。后臺數據庫系統將根據接收到的信息執行相應的動作。

由于電子標簽和讀取器通過非接觸進行信號傳輸，因此在進行多數據傳輸時有干擾的可能，嚴重時會導致傳輸失敗[9]。RFID系統碰撞可分為標簽—標簽碰撞、標簽—讀取器碰撞、讀取器—讀取器碰撞3類。文章主要針對標簽—標簽碰撞問題進行相關算法和RFID多標簽識別防碰撞算法改進。

1.2 幀時隙ALOHA算法

RFID多標簽識別防碰撞算法包括基于樹搜索的算法系列和基于ALOHA的算法系列。幀時隙ALOHA(FSA)算法與時隙ALOHA算法的最大區別為時隙ALOHA算法將識別周期劃分為不同的時隙間隔[10]。FSA是一個由多個時隙組成的幀，并且該時隙由多個時間段組成。在數據傳輸過程中，每個幀的大小由系統確定。如果標簽需要發送數據，讀取器將隨機生成一些時隙發送給標簽[11]。整個過程的時隙數據就是唯一的標識號。標簽還具有一個時隙計數器，一段時間后，時隙計數器增加1。如果時隙計數器的值等于幀中時隙的隨機數，則標簽可以發送數據，并且在數據發送過程中不會產生沖突。圖2為幀時隙ALOHA算法。

圖2 幀時隙 ALOHA算法通信原理

為系統設置特定的幀長L，待識別標簽個數n，當讀取器與標簽進行通信時，標簽隨機選擇時隙返回序列碼信息的概率p=1/L。由于該算法基于二項式分布，m個標簽在同一時隙中響應讀取器的查詢命令的概率如式(1)所示[12]。

(1)

如果該時隙沒有標簽響應讀取器的查詢命令時，則該時隙為空閑時隙I，即m=0，概率如式(2)所示。

(2)

如果時隙中對查詢命令的響應僅一個標簽，則該時隙為成功的時隙S，即m=1，概率如式(3)所示[13]。

(3)

如果時隙中對多個同時標記響應閱讀器的查詢命令，則該時隙為碰撞時隙C，即m>1，該概率如式(4)所示。

Pc=1-Pi-Ps。

(4)

一個幀長時間內，成功識別標簽的時隙數目如式(5)所示[14]。

(5)

算法系統的吞吐量如式(6)所示[15]。

(6)

對式(6)進行求導，則

(7)

整理可得：

(8)

當n為無窮大時，將式(8)按泰勒級數展開，得到最優幀長[16]：

(9)

當幀長L=n時，系統的最大吞吐率S如式(10)所示[17]。

(10)

因此，在處理大量標簽識別問題時，幀長等于標簽數時，識別效率最高，識別時間最短。但是，幀時隙也有其缺點。如果標簽數量較多，則不能將幀長度增加到任意長度值，即幀時隙是有限的。當幀長達到最大時，隨著標簽的增加，效率逐漸下降。如果標簽數遠小于幀長度，則空閑時隙較多，造成大量的時隙浪費。

2 改進幀時隙ALOHA算法

2.1 預編碼技術

考慮到噪聲在信息傳輸過程中的影響，采用最小均方誤差預編碼技術對幀時隙ALOHA算法進行改進，以最小化實際傳輸符號與接收器估計輸出值之間的差異，從而找到最優的預編碼矩陣[18]。

argminE‖s-β-1s‖2，

(11)

(12)

式中：

β——功率影響系數；

Pt——系統的總發射功率，W。

當式(12)成立時，實際傳輸信號與接收機估計輸出信號的差異最小。

根據式(12)建立拉格朗日函數，得到該函數的解：

FMMSE=HH(HHH+δI)-1，

(13)

式中：

H——信道矩陣；

δ、I——功率控制因子和單位矩陣。

(14)

式中：

(·)H——共軛轉置運算；

(·)-1——求逆運算；

功率歸一化因子β為[19]：

(15)

式中：

Tr(·)——跡運算。

此時預編碼矩陣為：

(16)

預編碼模型方框圖如圖3所示。

圖3 預編碼模型

信道矩陣H由Nt根發射天線和Nr根接收天線組成Nt×Nr，通過天線優化算法對信道矩陣進行選取。

2.2 預編碼幀時隙ALOHA算法

基于預編碼技術提出了預編碼幀時隙ALOHA(MMSE-FSA算法)，該算法將一些預設時隙組合為一幀fs，并將讀取器工作輻射區的標簽數設置為N。當識別認證標簽時，標簽隨機且獨立選擇1-fs個時隙發送響應信號。

時隙中標簽數量k的概率為：

(17)

時隙中標簽數為1的概率為：

(18)

如果標簽數量為1，此時隙中沒有碰撞，可以成功完成標簽標識。因此，根據式(19)可以正確識別幀中的標簽時隙數。

(19)

則碰撞時隙數為：

fcollosion=fs-fsuccess。

(20)

2.3 MMSE-FSA算法工作流程

假設讀取器在工作輻射區有天線，則工作輻射區可以識別很多標簽，標簽數量為N，MMSE-FSA算法步驟如下：

① 當讀取器的工作輻射區中有標簽進入，就會廣播一個請求命令，RFID系統開始識別認證。

② 識別前對所有未識別的標簽進行分組，并通過預編碼技術進行預處理。通過式(14)建立預編碼矩陣，發射機發送信號為：

x=smPek，

(21)

式中：

sm——發射信號映射；

ek——信號映射的調制符號；

接收信號為：

(22)

③ 使用FSA算法對接收信號進行識別。

④ 檢查是否識別了堆棧中的所有標簽。如果未識別完，執行③，否則繼續執行下一步。

⑤ 確定所有標簽后，算法完成。

改進算法的流程圖如圖4所示。

圖4 改進算法流程

3 仿真試驗及結果分析

3.1 仿真試驗設置

仿真設備為聯想PC機，操作系統為Windows 7 64位旗艦版，Intel i5 2450m CPU，2.5 GHz頻率，8 GB內存和Matlab r2018a作為仿真平臺。將MMSE-FSA算法(幀時隙ALOHA算法和最小均方誤差預編碼技術相結合)與幀時隙ALOHA算法、后退二進制搜索樹算法(Regressive-style Binary Search Tree，RBST)[20]進行時隙總數、吞吐量、沖突時隙和識別時間分析。RBST算法引入標簽狀態計數器進行分組，利用前、后向搜索方法來減少標簽的搜索范圍。標簽數量N在[0,1 000]變化，50為一個間隔。

3.2 仿真結果分析

MMSE-FSA算法、幀時隙ALOHA算法和RBST算法所需總時隙數比較結果見圖5。由圖5可知，MMSE-FSA算法的總時隙數隨標簽數量的增加呈線性增加，但是與幀時隙ALOHA算法和RBST算法相比，具有明顯的優勢。當標簽總數從0～1 000變化時，幀時隙ALOHA算法生成的時隙曲線總數呈指數增長。RBST算法生成的時隙曲線總數呈線性增長。當標簽數為1 000時，改進算法所需的時隙總數約為800，比幀時隙ALOHA算法少4 000，比RBST算法少1 000。因此，MMSE-FSA算法總時隙數變化最為緩慢，符合預期效果。

圖5 不同算法總時隙數變化曲線

MMSE-FSA算法、幀時隙ALOHA算法和RBST算法的吞吐率比較結果見圖6。由圖6可知，當讀取器輻射區域內標簽數相同時，MMSE-FSA算法的吞吐量高于幀時隙ALOHA算法和RBST算法的。當標簽數為1 000時，MMSE-FSA算法的吞吐率為0.8，比幀時隙ALOHA算法和RBST算法的分別提高了340%，58%。在輻射范圍內，MMSE-FSA算法的吞吐量可以保持在0.8左右，識別效率有了較大提升。

圖6 不同算法吞吐率變化曲線

圖7為MMSE-FSA算法、幀時隙ALOHA算法和RBST算法碰撞時隙數的比較結果。由圖7可知，如果標簽總數相同，MMSE-FSA算法產生的碰撞時隙數最少，當標簽總數從0～1 000變化時，MMSE-FSA算法碰撞時隙數變化最為緩慢。當標簽數為1 000時，MMSE-FSA算法相比于RBST算法碰撞時隙數減少了830個，比幀時隙ALOHA算法少3 200個。

圖7 不同算法碰撞時隙數變化曲線

圖8為MMSE-FSA算法與幀時隙ALOHA算法和RBST算法的識別時間比較結果。由圖8可知，當標簽總數從0～1 000變化時，MMSE-FSA算法識別時間變化最為緩慢，比幀時隙ALOHA算法和RBST算法花費的時間短。當標簽數為1 000時，MMSE-FSA算法的識別時間相比于RBST算法的降低了3.7 s，比幀時隙ALOHA算法的降低了8.2 s。MMSE-FSA算法有效降低了識別時間，相對于幀時隙ALOHA算法和RBST算法，其識別速度有了較大提升。

圖8 不同算法識別時間變化曲線

綜上，MMSE-FSA算法完成了對大量標簽識別認證過程，采用最小均方誤差預編碼技術對幀時隙ALOHA算法進行了改進，不僅降低了時隙總數、碰撞數，而且識別時間也得到了一定的改善，穩定性較好，具有一定的實際意義。

4 結論

文中提出了一種結合幀時隙ALOHA算法和最小均方誤差預編碼技術的RFID系統防碰撞算法。當標簽總數為1 000時，改進幀時隙ALOHA算法顯著提升了系統吞吐量，降低了標簽識別時間，減少了碰撞時隙數量。考慮到當前的試驗設備和數據規模，文中提出的食品RFID標簽沖突檢測的防碰撞算法仍處于起步階段，僅對[0，1 000]內標簽進行了仿真分析，后續應對大規模識別數據進行研究，以適應未來不斷變化的應用環境。