新型鎖位式混合查詢樹射頻識別防碰撞算法*

南敬昌，樊 爽，李 蕾，高明明

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

1 引言

物聯網是一種將用戶應用終端拓展到人與物、物與物交互通信的新型網絡技術和產業模式，是互聯網、電信網和廣播電視網的延伸與拓展[1]。射頻識別（radio frequency identification，RFID）技術作為實現互聯網感知層的數據采集技術[2]，已被廣泛應用于物流管理、制造工業、室內定位等領域。其中無源超高頻（ultra high frequency，UHF）因其通信距離長、識別速度快、存儲容量大、成本低而受到廣泛關注[3]。但要實現多標簽同時對閱讀器做出響應，會不可避免地產生多標簽碰撞問題，此時需要一個高效的防碰撞機制用于實現大量標簽的追蹤與識別[4]。

解決標簽防碰撞問題本質上即為解決無線通信系統中的多路存取問題，基于時分多址（time division multiple access，TDMA）的RFID防碰撞算法因其原理簡單，且無需進行硬件部分的改動而被廣泛應用[5]。常用的標簽防碰撞算法可以分為概率性算法和確定性算法[6]。基于ALOHA的算法[7-8]為傳統的概率性算法，該算法識別吞吐率較低，且在標簽數量未知時，不能保證所有標簽被識別，易造成標簽饑餓現象[9]。確定性算法[10]為基于樹的算法，經典的樹算法包含二進制搜索樹（binary search，BS）算法[11]和查詢樹（query tree，QT）算法[11]，后有人在QT算法的基礎上提出了混合查詢樹(hybrid query tree,HQT)算法[12]。文獻[13]提出一種鎖位式的樹形結構RFID防碰撞算法，該算法可發送鎖位指令對發生碰撞的比特位進行鎖定用來減少查詢過程中的數據傳輸量。文獻[14]在該文獻[13]的基礎上，結合經典的自適應多叉樹（adaptive multi-tree search，AMS）RFID防碰撞算法，提出一種自適應后退鎖位式（regressive lockadaptive multi-tree search，RLAMS）RFID防碰撞算法，通過搜索樹的叉樹后，對標簽中的碰撞位進行提取，從而形成新的序列，可減少大量碰撞時隙的產生，但對于空閑時隙的減少并未作出改善。文獻[15]提出改進的混合查詢樹（improved hybrid query tree，IHQT）RFID防碰撞算法，在閱讀器查詢碰撞標簽前加入分支預測，通過預測判斷出空閑節點并剪除，可達到徹底消除空閑時隙的目的，但該算法未能有效減少空閑時隙，數據傳輸量仍相對較大。

基于以上文獻存在的問題，本文提出一種新型鎖位式混合查詢樹（novel lock-bit hybrid query tree，NLHQT）算法。該算法加入鎖位指令，只將碰撞位進行鎖定并提取，從而形成新的標簽序列，并對新產生的序列加入預測指令，通過預測將空閑節點進行消除。通過分析論證和仿真證明，本文的NLHQT算法不僅能夠徹底消除空閑時隙，還能夠大量減少碰撞時隙，尤其當標簽中出現連續碰撞時，本文算法能夠快速有效地對標簽進行識別，從而有效提高搜索效率和閱讀器與標簽之間的數據傳輸量。

2 NLHQT算法

2.1 NLHQT算法預測描述

2.1.1 NLHQT算法碰撞指令描述

閱讀器初始化時堆棧為空，此時所有標簽都會響應，閱讀器如果只讀取到一個標簽，則成功識別該標簽，查詢結束，若產生碰撞，則對標簽的碰撞位進行鎖定。根據曼切斯特編碼原理，通過解碼使閱讀器檢測的標簽序列中碰撞標簽的碰撞位置為X，相同信息位即非碰撞位置為原信息數。通過提取X所在的碰撞位信息，對碰撞位進行鎖定，從而將鎖定位形成新的標簽序列。鎖位指令的加入可以使標簽在后續的識別過程中不再傳輸非碰撞位信息，進而在很大程度上減小冗余信息的傳輸。例如：產生碰撞的兩個標簽為01011000、11010100，則通過曼切斯特編碼原理使閱讀器檢測到的標簽序列為XX01XX00，碰撞位信息為D7、D6、D3、D2，對碰撞的位置進行提取，在后續的識別過程中，只需對這四位碰撞信息進行傳輸，減少了50%的信息傳輸量。

2.1.2 NLHQT算法預測指令描述

閱讀器在查詢前綴m1,m2,…,mp后添加n位二進制1（n=1時對應二叉樹算法，n=2時對應四叉樹算法，n=2L時對應2L叉樹算法），此時閱讀器產生新的二進制序列m1,m2,…,mp11…（n個1），經鎖位后的新標簽接到閱讀器的預測指令后，將前綴K1,K2,…,Kp與m1,m2,…,mp進行比較，若兩者匹配，標簽將ID前綴K1,K2,…,Kp后的n位二進制數換算成對應的十進制數a，同時向閱讀器回應一個長度為2n的預測響應序列，該序列中的a位為1（從左到右依次為0～2n-1位），其余的2n-1位均為0。閱讀器在接收所有標簽響應后，將序列中記為0的對應位置的子節點判斷為空閑節點，從而產生避開空閑節點的查詢前綴。

雖然通過增大叉樹可以縮短搜索層，從而減少碰撞時隙，但由于本文已通過鎖位指令使算法減少碰撞時隙，且實際操作過程中，只有二叉樹、四叉樹和八叉樹較易實現。其中若采用八叉樹搜索，效率雖略有提升，但會急劇增加前綴優化的復雜度，進而影響算法的普適性。因此文中算法采用n=1和n=2分別對應二叉樹和四叉樹算法進行改進，在這兩種情況進行論述與驗證。

以下分別對n=1和n=2時的情況，對預測指令的設計思路進行分析舉例：

發生碰撞的標簽序列A、B、C、D分別為0010、0100、1001、0110。

n=1時，首次查詢前綴無m1，只包含一位二進制數1，即查詢前綴為1。標簽A、B、C、D將第0位的二進制數換算為對應的十進制數。即A標簽對應位置十進制數為0，標簽B為0，標簽C為1，標簽D為0，其余位為0。即標簽A、標簽B和D回應預測響應10，標簽C回應01，又二叉樹查詢共有兩個子節點0和1，故標簽A、B、D中第0位所對應的子節點為0，C標簽中第0位所對應的子節點為1。進而產生新的查詢指令，完成對標簽首位的預測。則C標簽成功識別，A、B、D標簽以此類推繼續查詢。

n=2時，與n=1時情況類似，首次查詢前綴無m1、m2，只包含兩位二進制數11，即查詢前綴為11。標簽A、B、C、D將第0位和第1位的二進制數換算為對應的十進制數。即A標簽對應位置十進制數為0，標簽B與標簽D為1，標簽C為2。同時各標簽回應一個長度為4的預測響應序列，該序列中標簽換算出的十進制數對應位置為1，其余位為0。即標簽A回應預測響應1000，標簽B與標簽D回應0100，標簽C回應0010，又四叉樹查詢共有四個子節點00、01、10和11，故標簽A中第0位與第1位對應的子節點為00，標簽B與標簽D中第0位與第1位對應的子節點為01，標簽C中第0位與第1位對應的子節點為10。進而產生新的查詢指令，完成對標簽前兩位的預測。則A標簽與C標簽成功識別，標簽B和標簽D以此類推繼續查詢。

2.2 NLHQT算法分析

假設在閱讀器的查詢范圍內有4個標簽，標簽編碼為8位，標簽的ID分別為：標簽A（01000010）、標簽 B（01101110）、標簽 C（01101101）、標簽 D（11001110）。n=1時的NLHQT算法對標簽的識別過程如表1所示，此時由于鎖位指令減少了不必要的空閑時隙，故閱讀器進行預測時，每次發送1即可判斷出識別標簽的空閑子節點。n=1時的NLHQT算法和n=1時的IHQT算法的比較如圖1所示。由圖1可知，采用本文算法對標簽進行識別的過程中不僅沒有空閑時隙的產生，還能夠有效減少碰撞時隙的產生，提高識別效率。

n=2時的NLHQT算法如表2所示，與n=1相似，鎖位指令的存在，使得預測階段，閱讀器每次只需發送“11”即可準確判斷出空閑子節點的存在。n=2時的NLHQT算法和n=2時的IHQT算法的比較如圖2所示。通過對比可以看出，當標簽產生連續碰撞時，NLHQT算法能夠在不產生空閑時隙的同時，大量減少碰撞時隙的產生，較IHQT的識別效率明顯有所提升。

Table 1 NLHQT algorithm recognition process withn=1表1 n=1時的NLHQT算法識別過程

2.3 NLHQT算法流程

2.3.1 NLHQT算法指令

（1）Request(UID,1)鎖位指令：閱讀器通過判斷標簽發生碰撞的準確位置，將發生碰撞的比特位置為“1”，未發生碰撞的比特位置為“0”，標簽在接收到該指令后，將自身的標簽與閱讀器的信息進行比較，將閱讀器對應比特位為“1”的位置進行提取，形成新的標簽序列。

（2）Request(s,m,n)，其中s為更新的查詢前綴，m為待識別標簽與閱讀器查詢前綴進行比較的最高位（即檢測到碰撞的最高位），n為待識別標簽與閱讀器查詢前綴進行比較的次高位（即檢測到碰撞的次高位，n=1時沒有此項），由高位到低位依次為從左至右的0～p（標簽編碼為p位）。

2.3.2 NLHQT算法步驟

NLHQT算法識別步驟如下：

閱讀器初始化堆棧為空，閱讀器發送Request(11111111)搜索指令，閱讀器識別范圍內的所有標簽響應。

閱讀器根據標簽的響應，對時隙狀態做出判斷。若只有一個標簽做出響應，則閱讀器成功識別該標簽，直接跳轉到“結束”，若有多個標簽同時做出響應，則出現碰撞時隙，跳轉到“發送查詢指令”。

根據曼切斯特編碼原理，對發生碰撞的標簽的比特位進行判斷，將碰撞位置為“1”，非碰撞位置為“0”，閱讀器發送鎖位指令Request(UID,1)，將置“1”的碰撞比特位進行鎖定，進而形成新的標簽序列，并將該序列發送給閱讀器。

閱讀器執行預測指令Prognosis(1)（n=1時）或Prognosis(11)（n=2時）。

Table 2 NLHQT algorithm recognition process withn=2表2 n=2時的NLHQT算法識別過程

Fig.2 Algorithm flow withn=2NLHQT andn=2IHQT圖2 n=2的NLHQT和n=2的IHQT算法流程

標簽通過預測指令，將標簽的第0位（n=1時）或標簽的第0位和第1位（n=2時）轉換為對應的十進制數a，并向閱讀器返回一個長度為2位（n=1時）或4位（n=2時）的響應，該響應總的a位為“1”，其余位為“0”。

閱讀器在接收到所有標簽響應后，將序列中記為a的對應位置的子節點判斷為有用節點，其余判斷為空閑子節點，并將有用子節點形成查詢指令所需要的查詢前綴s。通過查詢前綴對標簽進行識別。

判斷標簽是否碰撞，若碰撞，轉到“發送查詢指令”；若不碰撞，則成功識別。

判斷堆棧是否為空，若為空，則全部識別成功；不為空，則堆棧彈出查詢前綴，返回“發送查詢指令”。

算法流程如圖3所示。

Fig.3 Algorithm flowchart圖3 算法流程圖

2.4 NLHQT算法性能分析

2.4.1 總時隙數

本文利用曼切斯特編碼原理鎖定碰撞位信息，在傳輸過程中可以減少數據傳輸信息量。設標簽UID信息為X位長度的二進制數，其中有x位發生碰撞，閱讀器讀取范圍內的標簽數為M。故在最理想時，M個標簽在各位上產生碰撞，（為取小于等于該數的最大整數）。在最不理想的情況下，N個標簽在不同位置上均產生碰撞，即x=M。

n=1時，總時隙數T為：

n=2時，總時隙數T為：

2.4.2 吞吐率

吞吐率指單位時間內通過某節點或者某通信信道成功交付數據的平均速率，可得：

2.4.3 通信復雜度

NLHQT算法的復雜度由標簽通信復雜度和閱讀器通信復雜度構成，它代表標簽被成功識別所需要的總的傳輸位數，表示為：

其中，C(x)表示NLHQT算法成功識別x個標簽時的通信復雜度，L表示首次查詢的通信位數，Li表示每次查詢的通信位數（不包含首次查詢）。鎖位指令降低了新算法的標簽通信復雜度，有效減少了Li，且NLHQT算法與IHQT算法的閱讀器通信復雜度大致相同，故NLHQT算法具有更低的通信復雜度。

2.4.4 閱讀器查詢次數

經典多叉樹算法的閱讀器查詢次數為成功時隙數、碰撞時隙數與空閑時隙數的總和。雖然本文算法增加的分支預測會增加閱讀器的查詢次數，但是由于分支預測消除了所有的空閑時隙，消除了閱讀器對于空閑時隙的查詢，故又一定程度上減小了閱讀器的開銷。

在NLHQT算法中，閱讀器對成功時隙需查詢一次，對碰撞時隙需查詢兩次，第一次查詢獲得碰撞時隙信息，第二次查詢得到碰撞時隙中空閑子節點的位置。設碰撞時隙數、空閑時隙數和成功時隙數分別為T1、T2和T3，則NLHQT算法的閱讀器查詢次數t為：

當n=1時：

當n=2時：

2.5 實驗仿真分析

本文利用Matlab中搭建的RFID防碰撞算法仿真平臺進行仿真，選擇理想無損信道，統計經典的查詢樹QT算法，以及混合查詢樹HQT算法，在自適應多叉樹AMS算法基礎上改進的自適應后退鎖位式RLAMS算法、IHQT算法和NLHQT算法的總時隙數、碰撞時隙數、吞吐率、通信復雜度和閱讀器開銷。且考慮到實際操作和算法的普適性，查詢樹算法叉樹過多，會增加算法復雜度和實現程度，增加算法操作過程的工作量。且由于文中算法的改進已使得碰撞時隙在n=1和n=2時得到很大程度的減少，故本文只需考慮與二叉樹和四叉樹查詢對應的情況，即n=1和n=2時的情況即可，在這兩種情況下，不僅算法復雜度和實現程度低，且滿足查詢速度快和降低碰撞時隙的條件。為保證各算法之間的公平比較，假設系統內的標簽為均勻分布，排除控制字節和校驗冗余的影響，參考ISO18000-6標準，隨機生成ID長度為96 bit的標簽，信息傳輸率為40 kb/s，標簽仿真數量最大為1 000，仿真結果取20次均值。

圖4為QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法分別在n=1時和n=2時的總時隙數的比較。通過統計總時隙數可以分析出，在識別標簽數量相同的情況下，n=1時的NLHQT算法總時隙數已經小于QT算法、HQT算法、RLAMS算法和n=1時的IHQT算法，甚至小于n=2時的IHQT算法，而n=2時的NLHQT算法的總時隙數較n=1時的NLHQT算法的總時隙數進一步減小。結合圖4的分析，考慮到HQT算法與RLAMS算法均為在四叉樹查詢算法的結合上的改進，使得此兩種算法性能較經典查詢樹QT算法已明顯優化，為公平論證文中算法性能，后續主要針對四叉樹條件下，即n=2時的IHQT算法和NLHQT算法進行論述。圖5為QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法分別在n=2時的碰撞時隙數的比較。通過對碰撞位時隙的提取，從圖5可以看出，由于鎖位指令的存在，使得本文算法在n=2時的碰撞時隙較QT算法、RLAMS算法和n=2時IHQT算法的碰撞時隙明顯減小。隨著標簽數量的增加，雖然NLHQT算法總時隙數逐步增多，但是由于預測指令避免了空閑時隙的產生，且同時鎖位指令減小了碰撞時隙的產生，NLHQT算法較其他四種算法性能具有明顯優勢，能夠有效減少總時隙數和碰撞時隙。

Fig.4 Comparison of total number of slots圖4 總時隙數的比較

Fig.5 Comparison of the number of collision slots圖5 碰撞時隙數的比較

表3為QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法分別在n=1時和n=2時的算法性能比較。從表中可以看出，本文算法通過增加預測指令進行額外查詢的方式，不僅能夠有效消除空閑時隙，對于碰撞時隙的有效減小還能很大程度提高閱讀器的查詢效率和查詢速率。通過對識別時間的統計可以看出，本文算法能夠很大程度降低算法識別時間，有效提升防碰撞性能，因此本文算法較其他幾種算法具有更好的整體性能。

Table 3 Algorithm performance comparison表3 算法性能比較

圖6為QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法在n=2時的吞吐率的比較。通過在統計總時隙數的基礎上，對碰撞位x和總時隙數T按式（4）進行運算獲取吞吐率，從圖中可以看出本文算法的吞吐率在0.85左右，明顯高于其他三種算法的吞吐率，進一步驗證了本文算法能夠在有效減少總時隙T的同時通過鎖位指令減少碰撞位x。因此NLHQT算法具有更高的搜索效率和速度。

圖7、圖8和圖9為QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法綜合n=1和n=2情況下統計的標簽通信復雜度、閱讀器通信復雜度和總通信復雜度的比較。從圖7中可以看出，NLHQT的鎖位指令使得標簽被查詢的通信位數大大降低，通過統計平均分析發現本文算法使得標簽通信復雜度得到大量簡化。從圖8中可以看出，NLHQT和IHQT的閱讀器通信復雜度大致相同，由于對于空閑時隙的分支預測使得閱讀器通信復雜度較其他算法明顯降低。故從圖9可以看出，本文算法的總通信復雜度明顯低于其他三種算法，這說明對碰撞位的鎖位和對于空閑時隙的分支預測能夠同時有效地降低閱讀器和標簽的通信復雜度。雖然隨著標簽數目的增加，NLHQT算法通信復雜度有所增長，但對比另外四種算法，增長速度明顯較為緩慢。

Fig.6 Comparison of throughput rates圖6 吞吐率的比較

Fig.7 Comparison of tag communication complexity圖7 標簽通信復雜度的比較

Fig.8 Comparison of reader communication complexity圖8 閱讀器通信復雜度的比較

Fig.9 Comparison of total reader communication complexity圖9 總閱讀器通信復雜度的比較

Fig.10 Reader overhead comparison圖10 閱讀器開銷的比較

圖10展示了QT算法、HQT算法、RLAMS算法、IHQT算法和NLHQT算法綜合n=1與n=2情況下的閱讀器查詢次數隨閱讀器標簽數量增加的變化曲線。由圖10可以看出，NLHQT算法均比其他算法的閱讀器查詢次數少，這是因為雖然IHQT算法增加了額外的查詢和碰撞時隙較多，在面對二叉樹和四叉樹條件時的閱讀器查詢次數較其他算法更多，但NLHQT算法在IHQT算法的基礎上，不僅消除了空閑時隙，還依靠鎖位指令大大降低了碰撞時隙，使得本文算法能夠較其他算法降低閱讀器的查詢次數。

3 結束語

本文提出了一種新型的鎖位式混合查詢樹算法，并闡述了算法的鎖位式策略和消除空閑時隙的基本思想，對于算法的識別過程進行了詳細的說明，且在保證算法性能的同時降低算法復雜程度，本文設置參數在n=1和n=2時的NLHQT算法進行性能分析，即在二叉樹和四叉樹的基礎上進行優化，從而進一步使得算法更易于實現。通過利用Matlab仿真軟件分析對比了幾種算法在總時隙數、碰撞時隙數、吞吐率和通信復雜度等性能上的特點，可以看出本文算法能夠有效減少碰撞時隙的產生，消除空閑時隙，降低通信復雜度，提高吞吐率，從而達到提高識別效率的目的，整體性能均有所提高。且本文算法同時適用于二叉樹和四叉樹情況下的查詢算法，可用范圍較為廣泛，算法復雜度較低，易于實現。