智能制造中RFID多標簽快速識別問題的研究

(山東建筑大學 信息與電氣工程學院，濟南 250101)

0 引言

所謂RFID，指的是無線射頻識別技術(Radio Frequency IDentification)，它通過無線電訊號識別特定的目標對象，無需識別系統與目標對象之間有接觸，即可實現兩者的雙向數據通信。與以往應用在工業現場的條形碼識別技術相比，RFID技術不受應答對象尺寸大小和形狀限制，不易被污染，適應惡劣環境的能力更強，已逐步成為工程機械智能制造領域的核心推動力[1]。

工程機械生產線依托RFID 系統，能夠自動且準確地獲取生產過程中有關“工序、工件、工人”的信息，實現全過程溯源，提高生產安全和質量。目前，影響工業現場RFID技術應用效果的主要問題就是多標簽快速識別問題，該問題直接影響著RFID系統的工作效率，進而影響整個智能制造生產線的工程進度。

現有的RFID防碰撞算法主要分為ALOHA 算法和樹形算法兩類。其中ALOHA算法原理簡單，容易實現，特別是其中一種動態幀時隙ALOHA算法已經具備比較高的吞吐率，但這種算法具有不可避免的隨機性，存在標簽饑餓現象，即總會有少量標簽不能被識別[2]。這在準確性和安全性要求高的工業現場是不被允許的，因此ALOHA算法僅適用于待識別標簽數目較少的情景。二進制樹算法不存在隨機性，解決了標簽饑餓問題，但這卻以系統的復雜度為代價，對系統識別總時長有顯著影響，這就不符合工業現場高實時性的特點。因此二進制樹類算法僅適用于待識別標簽數目較多，且對識別時間要求不高的情景。查詢樹算法解決了標簽饑餓問題的同時，系統復雜度也不高，但系統識別效率受標簽ID的長度影響較為嚴重，可見該類算法靈活性較低，僅適用于待識別標簽ID長度較短的情景[3]。

ALOHA 算法和樹形算法都不可避免空時隙或空搜索的存在，造成資源浪費的同時，算法的性能和識別效率都受到很大的影響。這兩類算法都無法在短時間內完成大量標簽的識別，不能滿足工業現場的生產要求。針對上述問題，本文提出一種更具靈活性的改進型算法，該算法建立在查詢樹算法的基礎上，保留了查詢樹算法的優點的同時，對查詢樹算法的缺點進行了針對性改進，能夠實現多標簽快速識別，可運用于工程機械智能制造生產線中。

本文提出的新算法對RFID系統的軟硬件沒有特殊要求，尤其是不需要電子標簽具有歷史記錄功能，只需要與閱讀器傳來的查詢前綴進行對比，然后判斷是否響應該命令即可。

1 曼徹斯特編碼方式簡述

本文提出的新算法中標簽ID采用曼徹斯特編碼(ManchesterEncoding)方式編碼，也叫做相位編碼方式，它是一種同步時針編碼方式。該編碼方式能在兩個或多個標簽同時響應閱讀器的命令時，精確地識別出發生碰撞的數據的比特位，從而采取相應措施使發生碰撞的標簽能被識別。

曼徹斯特編碼方式采用半個周期的電平正負跳變來表示1和0，約定由高電平到低電平的跳變為1，由低電平到高電平跳變為0[4]。若同時響應的兩個或多個標簽的編號中有某一位數據是不同值，則閱讀器接收到的上升沿和下降沿之間會相互抵消，呈現沒有電平跳變的狀態，這是不被允許的，此時閱讀器就可以判定這些數據位之間發生了碰撞，如圖1所示。

圖1 曼徹斯特編碼示意圖

2 改進型算法過程描述

本文提出的新算法延續了查詢樹算法的優點，此外，針對查詢樹算法存在的識別效率受標簽編號長度影響的問題進行了改進。即當多個標簽發生碰撞時，根據首位碰撞位生成兩個新的搜索前綴，而不是機械的在之前的搜索前綴后添加1或0。

該算法中，閱讀器自身帶有查詢前綴棧prefix、數據儲存棧string和分組編號棧group；標簽帶有寄存器count。

2.1 待識別標簽分組

本算法主要是實現短時間內大量標簽的識別，故為減少標簽碰撞發生的可能性，提高系統的識別效率，閱讀器將標簽ID中數值1的總位數作為分組編號，對場內所有待識別標簽進行分組識別。

首先，閱讀器發送數值1的總位數請求命令Quest，場內所有標簽接收到該命令后，統計自身ID中數值1的個數，將該統計值保存在標簽的寄存器count中，并將該統計值編碼后發送給閱讀器。

為提高數據傳輸的穩定性，在信道中傳輸分組編號時不采用傳統的二進制編碼，而是由標簽生成一個比特串，該比特串中位序號與該統計值相同的二進制數位設置為1，其余二進制數位設置為0(若標簽編碼不包含1，則返回全0比特串)。閱讀器接收到該比特串后，還原為1的總位數，將其作為分組編號，壓入分組編號棧group中。具體示例如表1所示。

表1 統計值編碼示例圖

2.2 搜索前綴的生成

傳統的查詢樹算法中，當標簽發生數據碰撞時，閱讀器直接在之前的搜索前綴后增加一位1或者0，生成新的搜索前綴[5]。這種做法不可避免空搜索的存在，降低了系統的識別效率，同時又使算法的效率很大程度上受標簽ID長度的影響。

針對上述問題，本文提出算法中采取了一種更具靈活性的搜索前綴生成方式，即根據首位碰撞位P來生成兩個搜索前綴，這就很好地解決了空搜索的問題，一定程度上減少了標簽ID長度對系統效率的影響。此外，當前組的待識別標簽與搜索前綴匹配成功后，只將自身ID中與搜索前綴相匹配之后的數據發送給閱讀器，這就減少了標簽與閱讀器間的數據通信量，進一步優化了算法的性能[6]。

本算法中生成搜索前綴時應考慮當前組標簽進行首輪識別和非首輪識別兩種情況[7]。

當前組進行首輪識別時，閱讀器的搜索前綴棧中只有空字符串。閱讀器接收標簽的返回信號，若檢測到未發生碰撞，則進入下一組標簽的識別；若檢測到發生碰撞，則根據首位碰撞位P生成兩個新搜索前綴，兩個新搜索前綴由標簽ID中首位碰撞位P之前的部分與首位碰撞位P組成，且P分別賦值為0或1，閱讀器將兩個新搜索前綴壓入查詢前綴棧prefix中，開啟下一輪搜索[8]。

當前組進行非首輪識別時，此時搜索前綴棧中定有非空字符串，設棧頂字符串為M。閱讀器發送搜索前綴M給當前組標簽，標簽將自身編號中與搜索前綴M匹配成功之后的字符串發送給閱讀器。閱讀器接收到字符串后，若檢測到沒有發生碰撞，則成功識別一個標簽，且該標簽的ID編號由搜索前綴M與收到的字符串連接組成；若檢測到發生碰撞，則根據首位碰撞位P生成兩個全新的搜索前綴M1和M2，這兩個新搜索前綴由之前的搜索前綴M與接收到的字符串中首位碰撞位P之前的部分以及首位碰撞位 P連接而成，且首位碰撞位P分別賦值0和1。閱讀器將兩個全新的搜索前綴壓入查詢前綴棧prefix中，開啟新一輪搜索。

2.3 改進型算法步驟介紹

分組完成后，RFID系統正式進入標簽識別環節。閱讀器從分組編號棧group中取出棧頂元素N1，從查詢前綴棧prefix中取出棧頂元素M，向場內待識別標簽發送命令(N1,M)。場內所有待識別標簽接收到該命令后，寄存器count中分組編號值與N1相同的標簽被選中為當前組標簽。該組標簽中與參數M相匹配的標簽響應該命令，發送自身ID編號給閱讀器。若此時搜索前綴M為空字符串，當前組所有標簽都會響應該命令。

閱讀器收到返回的ID編號后，檢測是否發生數據碰撞，如果沒有發生碰撞，則成功識別一個標簽，閱讀器從查詢前綴棧中取出棧頂元素，進行下一輪識別；如果發生碰撞，則根據首位碰撞位P生成兩個新的搜索前綴M1和M2，閱讀器將兩個新的搜索前綴依次壓入查詢前綴棧prefix中。重復上述過程直到查詢前綴棧為空，就可以結束當前組的識別，之后閱讀器從分組編號棧group中取出棧頂元素N2，開啟下一組的識別，直到group為空，則沒有待識別標簽，結束識別過程。以表2中6個標簽為例，本文提出的改進型算法的查詢樹如圖2所示。

圖2 改進型算法查詢樹示例圖

由圖2可以看出，本文提出的新算法可以根據首位碰撞位生成兩個新的搜索前綴，相比傳統查詢樹算法在之前的搜索前綴后直接添加1或0的做法，有效解決了空搜索的問題，提高了RFID系統的識別效率，且系統效率受標簽ID長度的影響程度有所降低。

2.4 RFID防碰撞系統結構綜述

本設計中，RFID防碰撞系統硬件部分主要分為電子標簽和閱讀器[9]。根據前文的算法介紹，本設計中閱讀器硬件系統可以分為分組模塊和識別模塊兩大部分。閱讀器硬件系統結構圖如圖3所示。

圖3 閱讀器硬件系統結構圖

由圖3可知，分組模塊主要包含請求模塊、接收模塊和確定模塊。其中，請求模塊負責向場內待識別標簽發送數值1 的總位數的請求命令；接收模塊負責接收標簽返回的數值1的統計值的比特串，將其還原回數值1的總位數，并將其儲存到閱讀器的分組編號棧group中；確定模塊負責將分組編號相同的標簽編為一組。

識別模塊主要包括起始模塊、命令模塊、識別模塊、前綴生成模塊、判斷模塊和結束模塊。其中，起始模塊負責從分組編號棧group中取出棧頂元素N1;命令模塊負責從查詢前綴棧prefix中取出棧頂元素M，并向場內待識別標簽發送命令(N1,M)；識別模塊負責接收響應(N1,M)命令的標簽的ID，并檢測是否發生碰撞；前綴生成模塊負責根據首位碰撞位生成兩個全新的搜索前綴；判斷模塊負責查看查詢前綴棧prefix中是否有非空元素，若是，則進入命令模塊，若否，則進入結束模塊；結束模塊負責查看分組編號棧group是否有非空元素，若是，則進入起始模塊，若否，則標簽識別全部結束[10]。

3 改進型算法仿真分析

本章利用Matlab軟件對動態幀時隙ALOHA算法、二進制樹算法、查詢樹算法以及本文提出的新算法的通信量和吞吐率進行試驗仿真。

仿真實驗中，標簽的數目的范圍取0～1000。為保證仿真試驗結果的可靠性，仿真進行了100次取其平均值，結果如圖4和圖5所示。

圖4 標簽個數為不同值時系統通信量對比

從圖4可以看出，隨著待識別標簽數目的增加，動態幀時隙ALOHA算法、二進制樹算法和查詢樹算法這三種算法的系統通信量呈線性增長，而本文提出的新算法的系統通信量則呈對數增長。其主要原因有兩個，一是本算法中新的搜索前綴由碰撞位產生，直接減少了閱讀器與標簽的通信次數；二是標簽ID編號與搜索前綴匹配成功后，只回傳匹配成功之后的數據位，直接減少了系統通信量。

由此可見，本文提出的新算法的兩點改進，有效減少了通信時間的同時，減少了系統通信量，這也是該算法能夠減少標簽識別總時長，實現多標簽快速識別的關鍵因素。

圖5 標簽個數為不同值時系統的吞吐率對比

由圖5可以看出，本文提出的新算法的系統吞吐率明顯高于其他三種算法，且當待識別標簽數目增多時，其他幾種算法吞吐率波動較大，而本文提出的算法性能穩定，保持在65%左右。這主要是因為本文提出的新算法有效減少了系統識別總時長，從而顯著提高了系統識別吞吐率。

由仿真試驗的結果圖可見，本文提出的算法能有效提高系統的識別效率，節約系統的通信量，相比與現存的其他幾種算法，更適合用于短時間內大量標簽的識別。

4 總結

本文提出了一種新算法來實現工業現場短時間內大量標簽的快速識別。該算法延續了查詢樹算法的優點的同時，改進了查詢樹算法中易出現空搜索的缺點，使新的查詢前綴根據碰撞位直接生成，生成的碰撞樹為滿二叉樹，有效避免了電子標簽與閱讀器之間的無效通信。此外，匹配成功的標簽響應命令時，只回傳自身ID中與搜索前綴相匹配之后的數據，這就減少了標簽與閱讀器間的數據通信量，進一步優化了算法的性能。

該算法通過以上兩點改進，有效減少了RFID系統識別總時長。此外，通過對待識別標簽的分組從識別初始便減少了發生標簽碰撞的可能性。仿真結果表明，本文提出的新算法吞吐率高達65%，且當場內存有大量待識別標簽時，通信量僅呈對數增長?？梢娫撍惴捎行н\用于工程機械智能制造生產線中，實現短時間大量標簽的識別。