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

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

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

1 引言

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

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

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

2 NLHQT算法

2.1 NLHQT算法預(yù)測(cè)描述

2.1.1 NLHQT算法碰撞指令描述

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

2.1.2 NLHQT算法預(yù)測(cè)指令描述

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

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

以下分別對(duì)n=1和n=2時(shí)的情況，對(duì)預(yù)測(cè)指令的設(shè)計(jì)思路進(jìn)行分析舉例：

發(fā)生碰撞的標(biāo)簽序列A、B、C、D分別為0010、0100、1001、0110。

n=1時(shí)，首次查詢前綴無m1，只包含一位二進(jìn)制數(shù)1，即查詢前綴為1。標(biāo)簽A、B、C、D將第0位的二進(jìn)制數(shù)換算為對(duì)應(yīng)的十進(jìn)制數(shù)。即A標(biāo)簽對(duì)應(yīng)位置十進(jìn)制數(shù)為0，標(biāo)簽B為0，標(biāo)簽C為1，標(biāo)簽D為0，其余位為0。即標(biāo)簽A、標(biāo)簽B和D回應(yīng)預(yù)測(cè)響應(yīng)10，標(biāo)簽C回應(yīng)01，又二叉樹查詢共有兩個(gè)子節(jié)點(diǎn)0和1，故標(biāo)簽A、B、D中第0位所對(duì)應(yīng)的子節(jié)點(diǎn)為0，C標(biāo)簽中第0位所對(duì)應(yīng)的子節(jié)點(diǎn)為1。進(jìn)而產(chǎn)生新的查詢指令，完成對(duì)標(biāo)簽首位的預(yù)測(cè)。則C標(biāo)簽成功識(shí)別，A、B、D標(biāo)簽以此類推繼續(xù)查詢。

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

2.2 NLHQT算法分析

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

n=2時(shí)的NLHQT算法如表2所示，與n=1相似，鎖位指令的存在，使得預(yù)測(cè)階段，閱讀器每次只需發(fā)送“11”即可準(zhǔn)確判斷出空閑子節(jié)點(diǎn)的存在。n=2時(shí)的NLHQT算法和n=2時(shí)的IHQT算法的比較如圖2所示。通過對(duì)比可以看出，當(dāng)標(biāo)簽產(chǎn)生連續(xù)碰撞時(shí)，NLHQT算法能夠在不產(chǎn)生空閑時(shí)隙的同時(shí)，大量減少碰撞時(shí)隙的產(chǎn)生，較IHQT的識(shí)別效率明顯有所提升。

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

2.3 NLHQT算法流程

2.3.1 NLHQT算法指令

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

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

2.3.2 NLHQT算法步驟

NLHQT算法識(shí)別步驟如下：

閱讀器初始化堆棧為空，閱讀器發(fā)送Request(11111111)搜索指令，閱讀器識(shí)別范圍內(nèi)的所有標(biāo)簽響應(yīng)。

閱讀器根據(jù)標(biāo)簽的響應(yīng)，對(duì)時(shí)隙狀態(tài)做出判斷。若只有一個(gè)標(biāo)簽做出響應(yīng)，則閱讀器成功識(shí)別該標(biāo)簽，直接跳轉(zhuǎn)到“結(jié)束”，若有多個(gè)標(biāo)簽同時(shí)做出響應(yīng)，則出現(xiàn)碰撞時(shí)隙，跳轉(zhuǎn)到“發(fā)送查詢指令”。

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

閱讀器執(zhí)行預(yù)測(cè)指令Prognosis(1)（n=1時(shí)）或Prognosis(11)（n=2時(shí)）。

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

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

標(biāo)簽通過預(yù)測(cè)指令，將標(biāo)簽的第0位（n=1時(shí)）或標(biāo)簽的第0位和第1位（n=2時(shí)）轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制數(shù)a，并向閱讀器返回一個(gè)長(zhǎng)度為2位（n=1時(shí)）或4位（n=2時(shí)）的響應(yīng)，該響應(yīng)總的a位為“1”，其余位為“0”。

閱讀器在接收到所有標(biāo)簽響應(yīng)后，將序列中記為a的對(duì)應(yīng)位置的子節(jié)點(diǎn)判斷為有用節(jié)點(diǎn)，其余判斷為空閑子節(jié)點(diǎn)，并將有用子節(jié)點(diǎn)形成查詢指令所需要的查詢前綴s。通過查詢前綴對(duì)標(biāo)簽進(jìn)行識(shí)別。

判斷標(biāo)簽是否碰撞，若碰撞，轉(zhuǎn)到“發(fā)送查詢指令”；若不碰撞，則成功識(shí)別。

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

算法流程如圖3所示。

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

2.4 NLHQT算法性能分析

2.4.1 總時(shí)隙數(shù)

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

n=1時(shí)，總時(shí)隙數(shù)T為：

n=2時(shí)，總時(shí)隙數(shù)T為：

2.4.2 吞吐率

吞吐率指單位時(shí)間內(nèi)通過某節(jié)點(diǎn)或者某通信信道成功交付數(shù)據(jù)的平均速率，可得：

2.4.3 通信復(fù)雜度

NLHQT算法的復(fù)雜度由標(biāo)簽通信復(fù)雜度和閱讀器通信復(fù)雜度構(gòu)成，它代表標(biāo)簽被成功識(shí)別所需要的總的傳輸位數(shù)，表示為：

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

2.4.4 閱讀器查詢次數(shù)

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

在NLHQT算法中，閱讀器對(duì)成功時(shí)隙需查詢一次，對(duì)碰撞時(shí)隙需查詢兩次，第一次查詢獲得碰撞時(shí)隙信息，第二次查詢得到碰撞時(shí)隙中空閑子節(jié)點(diǎn)的位置。設(shè)碰撞時(shí)隙數(shù)、空閑時(shí)隙數(shù)和成功時(shí)隙數(shù)分別為T1、T2和T3，則NLHQT算法的閱讀器查詢次數(shù)t為：

當(dāng)n=1時(shí)：

當(dāng)n=2時(shí)：

2.5 實(shí)驗(yàn)仿真分析

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

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

Fig.4 Comparison of total number of slots圖4 總時(shí)隙數(shù)的比較

Fig.5 Comparison of the number of collision slots圖5 碰撞時(shí)隙數(shù)的比較

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

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

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

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

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

Fig.7 Comparison of tag communication complexity圖7 標(biāo)簽通信復(fù)雜度的比較

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

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

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

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

3 結(jié)束語

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