唐志軍，陽　懿，吳笑峰，席在芳，胡仕剛

?

超高頻RFID新型后退式二叉樹防碰撞算法*

唐志軍+，陽懿，吳笑峰，席在芳，胡仕剛

湖南科技大學(xué)信息與電氣工程學(xué)院，湖南湘潭411201

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(05)-0646-11

E-mail: fcst@vip.163.com http:

//www.ceaj.org Tel:

+86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61377024, 61274026, 61376076 (國家自然科學(xué)基金); the Scientific Research Fund of Hunan Provincial Education Department under Grant No. 14B060 (湖南省教育廳青年項目); the Science and Technology Project of Hunan Province under Grant Nos. 2014FJ2017, 2013FJ2011 (湖南省科技計劃項目).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-09-01, http://www.cnki.net/kcms/detail/11.5602.TP.20150901.1538.006.htm l

TANG Zhijun, YANG Yi, WU Xiaofeng, et al. Novel back-off binary tree anti-collision algorithm for ultra high frequency RFID. Journal of Frontiersof Com puter Scienceand Technology, 2016, 10(5): 612-622.

摘要：針對目前超高頻射頻識別（radio frequency identification，RFID）二叉樹防碰撞算法通信量大和傳輸時

延長等問題，結(jié)合跳躍式動態(tài)搜索（jumping dynam ic search，JDS）和新穎跳躍式動態(tài)搜索（novel JDS，NJDS）防碰撞算法，引入后退尋呼策略，提出了一種新的后退式二叉樹（novel back-off binary tree，NBBT）防碰撞算法。該算法通過在閱讀器尋呼指令中加入引導(dǎo)位使標(biāo)簽以更快的速度響應(yīng)閱讀器，從而減少總通信量和傳輸時延。仿真結(jié)果表明，與現(xiàn)有JDS或NJDS防碰撞算法相比，該算法在傳輸時延和通信量方面更高效。此外，該算法能夠顯著提高閱讀器和標(biāo)簽之間的通信速率。

關(guān)鍵詞：射頻識別（RFID）；二叉樹防碰撞算法；后退尋呼；引導(dǎo)位

1 引言

物聯(lián)網(wǎng)是構(gòu)成物與物之間相互通信的一種網(wǎng)絡(luò)，被稱為繼計算機、互聯(lián)網(wǎng)之后世界信息產(chǎn)業(yè)的第三次浪潮[1]。作為實現(xiàn)物聯(lián)網(wǎng)的關(guān)鍵技術(shù)[2]，射頻識別（radio frequency identification，RFID）是一種以電磁波為傳輸介質(zhì)來實現(xiàn)數(shù)據(jù)雙向通信的非接觸式自動識別技術(shù)。超高頻RFID系統(tǒng)識別距離遠，目前廣泛應(yīng)用于物流、交通、軍事等各個領(lǐng)域，但在對多目標(biāo)的識別上還存在識別時間長，準(zhǔn)確率低和通信量大等問題，這已成為超高頻RFID技術(shù)發(fā)展的瓶頸。為了順應(yīng)物聯(lián)網(wǎng)的發(fā)展，RFID技術(shù)正在不斷革新，而解決超高頻RFID系統(tǒng)在識別標(biāo)簽過程中存在的碰撞問題，就顯得至關(guān)重要。因此，選擇一種好的防碰撞算法對物聯(lián)網(wǎng)中的RFID系統(tǒng)性能影響很大。

目前RFID系統(tǒng)的標(biāo)簽防碰撞算法大多采用時分多址方法，該方法可分為非確定性算法和確定性算法兩大類[3]。ALOHA算法是一種傳統(tǒng)的非確定性算法，但其標(biāo)簽存在“饑餓”問題（tag starvation）。二進制樹型搜索算法是一種典型的確定性算法，這種算法實現(xiàn)起來比較復(fù)雜，識別時間也相對較長，但不存在標(biāo)簽饑餓問題[4]。對于需要保證準(zhǔn)確率的識別系統(tǒng)選擇二叉樹防碰撞算法是一個不錯的選擇[5-6]?；诙鏄涞拇_定性算法雖然解決了標(biāo)簽饑餓的問題，但與ALOHA算法相比其存在識別周期長，詢問次數(shù)多，吞吐率低和標(biāo)簽耗能大等問題[7]。最近幾年，國內(nèi)外學(xué)者對二叉樹防碰撞算法進行了廣泛研究。如文獻[8]提出了一種增強型智能分組時隙二叉樹算法，通過將標(biāo)簽進行智能分組的方式有效地解決了標(biāo)簽響應(yīng)的碰撞問題。文獻[9]將二叉樹防碰撞算法和時隙ALOHA防撞算法相結(jié)合，提出了二叉樹時隙ALOHA防撞算法，這種算法不需要估計標(biāo)簽數(shù)量，從而提高了防碰撞算法的效率。文獻[10]提出了一種廣義的二叉樹協(xié)議，將識別進程分配到多個二叉樹中來解決識別效應(yīng)問題。堆棧二叉樹算法[11]構(gòu)建一個“ID二叉樹”，并用堆棧存儲標(biāo)簽的碰撞信息，同時標(biāo)簽利用計數(shù)器來跟蹤自身在堆棧中的位置，從而減少與閱讀器的通信量，使系統(tǒng)識別效率得到提升。Yang等人[12]對基于查詢樹16位隨機數(shù)算法進行了性能分析，并提出了高效查詢樹的16位隨機數(shù)算法。文獻[13]通過分析后退式索引二進制樹形搜索算法的基本原理，提出了一種基于后退式索引二進制樹形搜索的RFID防碰撞算法。該算法利用碰撞節(jié)點的信息，有效地減少了數(shù)據(jù)的傳輸量，提高了閱讀器識別標(biāo)簽的速率。王鑫等人[14]通過制訂一組特殊的編碼，在二叉樹碰撞跟蹤樹算法基礎(chǔ)上，提出了三叉碰撞跟蹤樹算法，此算法通過降低搜索樹的整體深度，有效地提高了算法識別速率。文獻[15]提出了一種改進的四叉樹算法，該算法的標(biāo)簽根據(jù)不同的閱讀器尋呼命令來修改自身應(yīng)答概率并進行分組，以減少閱讀器尋呼次數(shù)和通信量，從而有效提高了閱讀器的識別效率。目前，雖然二叉樹算法較多，對RFID系統(tǒng)性能改進各異，并偏向不同的改進點，但是根據(jù)對這些算法進行分析可以得出，其主要改進方式有分組、后退、自適應(yīng)、多叉樹、索引、標(biāo)記和堆棧等。其中引用分組的算法減少了閱讀器尋呼次數(shù)，但是根據(jù)分組方式的不同會要求增強閱讀器或者標(biāo)簽的功能。后退算法是在閱讀器的閱讀方式上進行改進，在算法性能上的改進主要是減少了閱讀器的尋呼數(shù)據(jù)量。運用自適應(yīng)功能的算法主要改進點在標(biāo)簽的響應(yīng)方式上，標(biāo)簽需具有記憶功能。多叉樹算法主要是通過改變編碼方式使標(biāo)簽自動分組，達到減少閱讀器尋呼次數(shù)的目的，但是這種方式使標(biāo)簽的通用性變差。索引是在閱讀器尋呼指令前端加入引導(dǎo)標(biāo)簽響應(yīng)的字段，減少標(biāo)簽響應(yīng)的通信量。標(biāo)記是在標(biāo)簽中添加一個與自身響應(yīng)次數(shù)有關(guān)的計數(shù)器，減少標(biāo)簽響應(yīng)次數(shù)。索引和標(biāo)記都使標(biāo)簽的功能復(fù)雜化，不利于當(dāng)前降低標(biāo)簽價格的發(fā)展趨勢。堆棧是閱讀器一種存儲通信數(shù)據(jù)的結(jié)構(gòu)，可以記錄閱讀器的尋呼指令和記錄標(biāo)簽的響應(yīng)信息，它一般不單獨出現(xiàn)，是后退等功能實現(xiàn)的依靠。

基于此，本文結(jié)合跳躍式動態(tài)搜索（jumping dynam ic search，JDS）防碰撞算法和新穎跳躍式動態(tài)搜索（novel jumping dynam ic search，NJDS）防碰撞算法，引入一種改進的閱讀器后退尋呼方式，提出了一種新的后退式二叉樹（novel back-off binary tree，NBBT）防碰撞算法，期望能夠為物聯(lián)網(wǎng)RFID技術(shù)的發(fā)展提供幫助。

2 NBBT算法機理

如圖1所示，設(shè)有4個標(biāo)簽A、B、C、D，標(biāo)簽ID分別為1000、0001、0100、0110。圖中有兩種后退方式，其中后退方式1是目前一般采用的方法，NJDS算法就是用的這種后退方式，后退方式2是JDS算法中采用的方法。在步驟2中閱讀器發(fā)送00后只有標(biāo)簽B響應(yīng)，識別標(biāo)簽B后，后退方式1中閱讀器將發(fā)送命令改為01，而后退方式2中閱讀器則還是發(fā)送0信號，其閱讀器通信量就比后退方式1減少了1位。在圖例中只出現(xiàn)了一次有差異的后退方式，而在實際應(yīng)用中這個減少的數(shù)據(jù)量就可能擴大很多倍。從圖1中可看出，兩種后退方式的閱讀器通信量相差較大，這一點在后續(xù)仿真部分中會得到進一步驗證。

通過對JDS和NJDS算法所采用的后退策略比較可以發(fā)現(xiàn)：JDS算法使用的后退策略比NJDS算法使用的后退策略要先進；在同等條件下不考慮閱讀器尋呼指令中的標(biāo)志位時，JDS算法的閱讀器通信量要比NJDS算法的通信量少。對JDS算法中的后退策略進行分析發(fā)現(xiàn)，其識別一個標(biāo)簽后，從堆棧中取得上一次尋呼命令的唯一標(biāo)識碼（unique identifier，UID）再一次尋呼。而NJDS算法識別一個標(biāo)簽后，是改變當(dāng)前尋呼命令中的UID來尋呼，而上一次尋呼命令總是要比當(dāng)前尋呼命令的數(shù)據(jù)量要少，因此JDS算法的閱讀器通信量要少。NBBT算法就是在NJDS算法的基礎(chǔ)上采取JDS算法中的后退策略，來達到減少防碰撞算法中總通信量的目的。鑒于篇幅限制，關(guān)于JDS和NJDS算法的具體分析過程在此不再贅述，下面主要闡述NBBT算法的改進思路及機理。

Fig.1 Comparison of back-off reading mode圖1 后退閱讀模式比較

在NBBT算法中，將標(biāo)簽響應(yīng)的信息分為4部分：第一部分為最高碰撞位與最高碰撞位之前的信息，參與形成下一次尋呼的UID，保存每一次的UID在堆棧0中；第二部分為最高碰撞位與次高碰撞位之間的信息，為閱讀器已知信息存入堆棧1中，設(shè)這部分信息為String1；第三部分為次高碰撞位與最低碰撞之間的信息，為閱讀器未知部分，是需要標(biāo)簽響應(yīng)的部分，標(biāo)簽只要知道其ID中未知部分的范圍即可，保存次高碰撞位和最低碰撞位加入到下一次尋呼命令中；第四部分為最低碰撞位到末尾的信息，這部分信息也是已知信息存入堆棧2中，設(shè)這部分信息為String2。設(shè)標(biāo)簽響應(yīng)的信息為1X0X0X1，這4個部分的劃分如表1所示。

Table 1 Example of tag response information division表1 標(biāo)簽響應(yīng)信息劃分舉例

閱讀器尋呼的信息包含提供給標(biāo)簽匹配的UID和需要標(biāo)簽返回其ID信息中有用信息的兩個標(biāo)志位。閱讀器收到標(biāo)簽響應(yīng)的信息后先形成一個與標(biāo)簽ID長度相同的信息設(shè)為TC，TC就是所有響應(yīng)的標(biāo)簽ID的完整疊加信息。將當(dāng)前的TC存入堆棧3中，其表達式為：

TC=UID+String1+ID+String2（1）

NBBT算法中的閱讀器尋呼分為向前搜索和后退搜索兩部分，如果標(biāo)簽響應(yīng)的信息中有兩個或兩個以上的碰撞位則閱讀器采取向前搜索，反之向后搜索。當(dāng)閱讀器向前搜索時存儲TC，當(dāng)閱讀器識別一個標(biāo)簽后開始后退搜索，移除堆棧3中的頂部信息后，讀取當(dāng)前頂部信息得到上一次的TC，從而形成String1、String2和標(biāo)簽所要響應(yīng)的ID范圍，移除堆棧0中的頂部信息后，讀取當(dāng)前頂部信息作為下一次尋呼的UID。例如，得到的上一次TC為00X0X0X0，上一次的UID為0，則下一次尋呼指令中的UID為0，取得TC中次高位之前的位除去首部UID的信息0得到P(0X0），按照向前搜索規(guī)則，上一次尋呼的UID為000，最后一位就是TC中最高碰撞位置0得出的，而這次就將最高碰撞位置1，將P中的X改為1得到010存入String1中。最高碰撞位與次高碰撞位之間的0保存在String2中，標(biāo)簽需要返回的ID信息就是次高位與最低碰撞位之間的信息。假設(shè)TC從左至右的位數(shù)第一位為0，則標(biāo)簽需要返回的ID信息的范圍為[4, 6]，閱讀器尋呼這段指令后假設(shè)收到標(biāo)簽的信息為100，閱讀器根據(jù)式（1）形成標(biāo)簽的ID信息為00101000。這里UID和String1中的信息組成形式就是改進后退策略的特點。利用這種方法就減少了閱讀器的通信量，當(dāng)閱讀器后退搜索的次數(shù)越多，在后退中的UID與上一次識別了一個標(biāo)簽的UID信息長度相差越多，在標(biāo)簽識別過程中閱讀器的尋呼量就減少得越多。在此假設(shè)中后退中的UID為0，上一次識別了一個標(biāo)簽的UID為000，按照原來的后退策略，后退中的UID應(yīng)該為001，則經(jīng)過改進后標(biāo)簽通信量減少了2，而這兩位信息存入了String1中。

3 NBBT算法相關(guān)指令

因為在NBBT算法中閱讀器尋呼加入了兩個位置序號，所以其尋呼指令與傳統(tǒng)二叉樹算法有所不同，但其主要的指令數(shù)量不變，只改變了閱讀器尋呼指令，其他指令與傳統(tǒng)的二叉樹算法相同，這里只介紹其不同部分。

REQUEST(UID，P0，P1)：閱讀器尋呼指令。因為在后退算法中有向前尋呼和向后尋呼模式，所以在不同的尋呼模式下，尋呼指令中的參數(shù)來源不同。當(dāng)閱讀器處于向前尋呼時，與大多數(shù)算法相同，UID來自于標(biāo)簽響應(yīng)信息中的最高碰撞位之前的位加上一個0，這時就代表搜尋二叉樹的0分支，直至識別一個標(biāo)簽。P0和P1代表閱讀器對標(biāo)簽ID未知序列的范圍，也就是標(biāo)簽響應(yīng)信息中第三部分在TC中的范圍。假設(shè)標(biāo)簽的ID從左至右由低到高，則P0代表標(biāo)簽ID序列中需要響應(yīng)的最高位，P1代表最低位，則標(biāo)簽ID序列響應(yīng)的區(qū)間是[P0,P1]。當(dāng)閱讀器處于向后搜索時，因為每一次閱讀器尋呼的UID都存入了堆棧0，所以先使堆棧0出棧一次，再推出堆棧0的頂部信息形成UID。P0、P1來自于堆棧3，也是先使堆棧3出棧一次，然后再通過堆棧3的頂部信息來判斷標(biāo)簽響應(yīng)信息中的第三部分的形成。標(biāo)簽接收到尋呼指令后先判斷尋呼指令中的UID是否匹配，相匹配則將其ID中P0至P1位中的信息響應(yīng)給閱讀器。

REQUEST(NULL,0,P1)，閱讀器廣播指令。這是一條特殊的尋呼指令，其UID等于空，代表所有標(biāo)簽都要響應(yīng)；P0等于0代表標(biāo)簽響應(yīng)的信息從ID的起始位開始；P1是一個常數(shù)，其值等于標(biāo)簽ID的長度，代表標(biāo)簽響應(yīng)的信息到ID的最高位結(jié)束。這條指令的整體意義在于所有處于激活狀態(tài)的標(biāo)簽都將其自身的ID響應(yīng)給閱讀器。

4 NBBT算法流程

采用NBBT算法的閱讀器在其工作時用到了4個堆棧，堆棧存放的信息如下：

Stack0：在閱讀器發(fā)送尋呼指令前，將UID存入其中。

Stack1：保存標(biāo)簽信息的第二部分String1。

Stack2：保存標(biāo)簽信息的第四部分String2。

Stack3：在收到標(biāo)簽響應(yīng)信息后，保存形成的TC。

下面闡述閱讀器的工作流程：

（1）閱讀器發(fā)送廣播命令REQUEST(NULL，0，P1)，將一個空的信息存入Stack0、Stack1和Stack2中。標(biāo)簽收到這個信息后都發(fā)送自己的ID給閱讀器，進入步驟（2）。

（2）分析接收到的標(biāo)簽信息，如果響應(yīng)信息為空，代表在閱讀器尋呼范圍內(nèi)沒有標(biāo)簽，則結(jié)束識別過程。如果有響應(yīng)且沒有碰撞，則識別這個標(biāo)簽進入步驟（3），后退閱讀模式；如果有響應(yīng)且只有一個碰撞，則識別兩個標(biāo)簽進入步驟（3），后退閱讀模式；如果有響應(yīng)且有一個以上的碰撞位，則進入步驟（4），向前閱讀模式。

（3）后退閱讀模式。推出Stack0頂部信息，如果頂部信息為空，則代表閱讀器處于根節(jié)點，不可后退，結(jié)束識別過程。如果不為空，則保存這部分信息，設(shè)其為UID1；Stack0的頂部信息繼續(xù)推出，設(shè)為UID0，UID1信息長度必定大于UID0，設(shè)UID1相比UID0多出的部分D，Stack1出棧兩次，保存后一次的信息為Str1；將D與Str1結(jié)合形成新的String1存入Stack1中，Stack2出棧一次，Stack3出棧兩次，保存后一次信息TC；去掉TC中與UID0信息相同的部分得到信息ID，將信息ID當(dāng)作標(biāo)簽響應(yīng)信息分為4部分，將第二和第四部分存入對應(yīng)堆棧中；根據(jù)標(biāo)簽響應(yīng)信息中的第三部分得出閱讀器尋呼指令中的P0和P1，將UID0作為這次尋呼指令中的UID，閱讀器發(fā)送尋呼指令REQUEST(UID，P0，P1)，進入步驟（2）。

（4）向前閱讀模式。將標(biāo)簽響應(yīng)信息Stack1、Stack2的頂部信息代入式（1）形成TC，并將其存入Stack3中，將Stack1和Stack2出棧，根據(jù)標(biāo)簽的響應(yīng)信息的4部分，將第二和第四部分存入對應(yīng)堆棧中。從Stack0中得到上一次的尋呼UID與第一部分信息相結(jié)合形成UID，將UID最后一個碰撞位X改為0，形成新的UID；利用標(biāo)簽信息的第三部分信息得出P0和P1，閱讀器發(fā)送尋呼指令REQUEST（UID，P0，P1），進入步驟（2）。

從NBBT算法的工作流程中可以看出其工作步驟只有兩步：向前閱讀和向后閱讀。如果閱讀器尋呼范圍內(nèi)有標(biāo)簽時則結(jié)束識別過程，其一定是處于向后閱讀模式中。NBBT算法識別流程圖如圖2所示。

5 NBBT算法識別演示

設(shè)在閱讀器尋呼范圍內(nèi)有5個標(biāo)簽，標(biāo)簽的ID和識別過程如表2所示。

下面對NBBT算法識別這5個標(biāo)簽的過程進行詳細說明。

（1）閱讀器發(fā)送廣播指令REQUEST(NULL，0，7)，將NULL存入堆棧0、1、2中。標(biāo)簽接收到廣播指令都將自己的ID發(fā)送給閱讀器，發(fā)送的混合信號為X1XXXXXX。

（2）閱讀器對接收到的信息進行譯碼，得到的ID 為X1XXXXXX，ID的碰撞位大于一個，根據(jù)ID得出Part1為X，Part2為1，Part3為XXXXXX，Part4為NULL。讀取Stack0、Stack1、Stack2的頂部信息分別賦給UID (NULL)、String1(NULL)、String2(NULL)，根據(jù)式（1）生成TC等于X1XXXXXX，將TC存入Stack3，分析TC得出下一次尋呼的UID、P0、P1分別為0、2、7。將UID(0)存入Stack0，Part2(1)的數(shù)據(jù)存入Stack1，Part4(NULL)的數(shù)據(jù)存入Stack2。閱讀器發(fā)出尋呼指令REQUEST(0，2，7)。標(biāo)簽接收到尋呼指令，根據(jù)尋呼指令的UID信息進行匹配，匹配的標(biāo)簽發(fā)送其ID的2 到7位的序列號給閱讀器。Tag1、2、4、5匹配成功。

（3）閱讀器接收的ID為XX0XXX，ID的碰撞位大于一個，根據(jù)ID得出Part1為X，Part2為NULL， Part3為X0XXX，Part4為NULL。讀取Stack0、Stack1、Stack2的頂部信息分別賦給UID(0)、String1(1)、String2(NULL)，根據(jù)式（1）生成TC等于01XX0XXX，將TC存入Stack3，分析TC得出下一次尋呼的UID、P0、P1分別為010、3、7。將UID(010)存入Stack0，Part2(NULL)的數(shù)據(jù)存入Stack1，Part4(NULL)的數(shù)據(jù)存入Stack2。閱讀器發(fā)出尋呼指令REQUEST(010，3，7)。Tag1、2、4響應(yīng)，發(fā)送其ID的3到7位的數(shù)據(jù)給閱讀器。

Table 2 Demonstration of NBBT algorithm identification process表2 NBBT算法識別過程演示

Fig.2 Flow chart of NBBT algorithm identification圖2 NBBT算法識別流程圖

（4）閱讀器接收的ID為X01XX，ID的碰撞位大于一個，根據(jù)ID得出Part1為X，Part2為01，Part3為XX，Part4為NULL。讀取Stack0、Stack1、Stack2的頂部信息分別賦給UID(010)、String1(NULL)、String2 (NULL），根據(jù)式（1）生成TC等于010X01XX，將TC存入Stack3，分析TC得出下一次尋呼的UID、P0、P1分別為0100、3、7。將UID(0100)存入Stack0，Part2 (01)的數(shù)據(jù)存入Stack1，Part4(NULL)的數(shù)據(jù)存入Stack2。閱讀器發(fā)出尋呼指令REQUEST(0100，3，7)。Tag4響應(yīng)，發(fā)送其ID的3到7位的數(shù)據(jù)給閱讀器。

（5）閱讀器接收到的ID為0101，ID沒碰撞位，讀取并推出Stack0、Stack1、Stack2的頂部信息分別賦給UID(0100)、String1(NULL)、String2(NULL)，根據(jù)式（1）得出TC等于01000101，識別Tag4。將Stack3出棧形成新的TC為010X01XX，將Stack0出棧得到UID(010)，將Stack1出棧得到String1(01)，更改String1的信息為101存入堆棧Stack1中。目前閱讀器未知的信息是TC的最后兩位，則P1、P2分別為6、7。閱讀器發(fā)出尋呼指令REQUEST(010，6，7)。Tag1、2響應(yīng)，發(fā)送其ID的6到7位的數(shù)據(jù)給閱讀器。

（6）閱讀器接收到的ID為X0，ID只有一個碰撞位，讀取并推出Stack0、Stack1、Stack2的頂部信息分別賦給UID(010)、String1(101)、String2(NULL)，根據(jù)式（1）得出TC等于010101X0，識別Tag1、2。將Stack3出棧形成新的TC為01XX0XXX，將Stack0出棧得到UID(0)，將Stack1出棧得到String1(1)，更改String1的信息為11存入堆棧Stack1中。目前閱讀器未知的信息是TC的最后5位，則P1、P2分別為3、7。閱讀器發(fā)出尋呼指令REQUEST(0，3，7)。Tag5響應(yīng)，發(fā)送其ID的3到7位的數(shù)據(jù)給閱讀器。

（7）閱讀器接收到的ID為10001，ID沒碰撞位，讀取并推出Stack0、Stack1、Stack2的頂部信息分別賦給UID(0)、String1(11)、String2(NULL)，根據(jù)式（1）得出TC等于01110001，識別Tag4。將Stack3出棧形成新的TC為NULL，將Stack0出棧得到UID(NULL)，將Stack1出棧得到String1(1)，TC的最高位為碰撞位，將其改為1后加上出棧的1，String1的信息更改為11存入堆棧Stack1中。目前閱讀器未知的信息是TC的最后6位，則P1、P2分別為2、7。閱讀器發(fā)出尋呼指令REQUEST(NULL，3，7)。Tag3響應(yīng)，發(fā)送其ID 的3到7位的數(shù)據(jù)給閱讀器，閱讀器收到信息后讀取其沒碰撞識別Tag3。將Stack0推出時發(fā)現(xiàn)其中沒有元素，從而結(jié)束識別過程。

6 NBBT算法仿真及性能分析

NJDS算法相對于JDS算法主要改進的地方是標(biāo)簽通信量，而NBBT算法相對于NJDS算法的改進是在閱讀器的通信量上。這3種算法其閱讀器尋呼指令中加入了引導(dǎo)位，指定標(biāo)簽返回特定的信息。

本文利用Java開發(fā)的RFID防碰撞算法仿真平臺對算法進行仿真，統(tǒng)計JDS、NJDS、NBBT算法的閱讀器尋呼次數(shù)、閱讀器通信量、標(biāo)簽通信量。下面對其統(tǒng)計的數(shù)據(jù)進行分析。

圖3～圖6中數(shù)據(jù)為算法不含引導(dǎo)位的仿真結(jié)果，其中標(biāo)簽長度（ID_len）為16，運行次數(shù)（Ave_run）為20。閱讀器尋呼次數(shù)如圖3所示，NBBT算法所需尋呼次數(shù)較少，其原因是NBBT算法中使用單個碰撞位的直接識別方法，所以尋呼次數(shù)少于NJDS算法。圖4～圖6分別代表閱讀器通信量、標(biāo)簽通信量、總通信量。從圖4中可發(fā)現(xiàn)，NJDS需要的閱讀器通信量最多，NBBT算法最少，JDS所需要的閱讀器通信量與NJDS算法的差值大于其與NBBT算法的差值。通信量的不同主要是由后退策略不同造成的，這表明NBBT算法的改進型后退策略性能最佳。

從圖4可知，NBBT算法與NJDS算法的標(biāo)簽通信量數(shù)目近似相等，這說明NBBT算法繼承了NJDS算法的優(yōu)點。通過圖4和圖5可知，總通信量最少的一定是NBBT算法。圖6是在不計閱讀器引導(dǎo)位的前提下得出的總通信量，從中可以看出，JDS算法的總通信量是最多的，而NBBT算法總通信量最少，再次驗證了NBBT算法中后退策略的先進性。

對于JDS、NJDS、NBBT這種閱讀器尋呼指令帶引導(dǎo)位的算法，其引導(dǎo)位加入的目的在于減少閱讀器和標(biāo)簽的通信量，其減少的幅度取決于引導(dǎo)位在信號中的標(biāo)簽形式。下面對引導(dǎo)位處理方法進行詳細分析。

將JDS閱讀器尋呼指令REQUEST(UID，P)記為RQ1，NJDS算法和NBBT算法的尋呼指令REQUEST (UID，P0，P1)記為RQ2。如果單獨用一個字節(jié)來存放引導(dǎo)位，那么相對于前面的性能數(shù)據(jù)分析，在JDS算法中閱讀器一次尋呼所需要的數(shù)據(jù)量要增加一個字節(jié)，而NJDS和NBBT算法則要增加兩個字節(jié)。通過增加引導(dǎo)位，當(dāng)標(biāo)簽數(shù)目為1 000時進行統(tǒng)計數(shù)據(jù)分析，其結(jié)果如表3所示。由表3可知，如果引導(dǎo)位占一個字節(jié)，則NJDS算法和NBBT算法在通信量方面的改進就沒有多大意義，因為引導(dǎo)位的數(shù)據(jù)量在總通信量中的比重過大，特別是在NJDS算法和NBBT算法中，而且JDS算法的總通信量要比NJDS、NBBT算法少。因此采取一種好的引導(dǎo)位處理方式對含有引導(dǎo)位的算法來說意義重大。

從表3中也可以可看出，NJDS和NBBT算法比JDS算法多一個引導(dǎo)位，而尋呼次數(shù)也相差不多，一般來說其閱讀器通信量會比JDS的閱讀器通信量多。然而可以通過對引導(dǎo)位做特殊處理減小這種差距，使算法具有更高的應(yīng)用價值。

在數(shù)字通信中信息都是以二進制信息存在，閱讀器尋呼指令中的引導(dǎo)位也一樣，將引導(dǎo)位的十進制以二進制形式表示，其表示長度不做限制，那么可得出十進制越大二進制表現(xiàn)形式越長，但是對于有界的十進制可以將數(shù)據(jù)進行如下處理：

如P1∈[0,ID_len-1]且P1≥ID_len，那么--P1= ID_len-1-P1。例如P1∈[0,15]，且P1=14，那么--

P1=1。對于REQUEST(UID,P0,P1)?REQUEST (UID, P0,--

P1)；設(shè)P0=0，則REQUEST(UID,0,14)?REQUEST (UID,0,1ˉ)；1410=11102，-110=～12（～代表信號1做了處理）。

Fig.3 Comparison of paging number圖3 尋呼次數(shù)比較

Fig.4 Comparison of reader traffic圖4 閱讀器通信量比較

Fig.5 Comparison of tag traffic圖5 標(biāo)簽通信量比較

Fig.6 Comparison of total traffic圖6 總通信量比較

由以上推導(dǎo)可知，對P1做處理后其閱讀器傳輸信息將減少很多，在防碰撞算法仿真軟件中運行采用這種處理方式的JDS、NJDS、NBBT算法，統(tǒng)計出通信量的結(jié)果如圖7～圖9所示（Y-代表有引導(dǎo)位的算法）。

從圖8中可以看出，引導(dǎo)位的添加對標(biāo)簽通信量沒有影響。因為標(biāo)簽的返回指令沒有變化，與沒加入引導(dǎo)位時的通信數(shù)量相同。從圖7中可知，引導(dǎo)位對算法閱讀器通信量的影響隨著標(biāo)簽數(shù)目的增加逐漸增大，但對加入引導(dǎo)位時3種算法的閱讀器通信量大小排序影響不大，NBBT算法的通信量與JDS算法相當(dāng)，與NJDS算法的通信量差距隨著標(biāo)簽增加而加大。這說明引導(dǎo)位對NBBT算法通信量的影響小于對NJDS算法的影響。

對比表3中標(biāo)簽數(shù)目為1 000時的實驗結(jié)果可知，將引導(dǎo)位進行數(shù)據(jù)處理后可急劇減少引導(dǎo)位對算法通信量的影響。綜合圖7～圖9可得出，在NBBT算法中加入引導(dǎo)量統(tǒng)計后，其閱讀器通信量與JDS算法近似，標(biāo)簽通信量與NJDS算法近似，總通信量最少。

一個算法效率高低的直接指標(biāo)為算法復(fù)雜度，算法復(fù)雜度又分為時間復(fù)雜度和空間復(fù)雜度[16]。在二叉樹防碰撞算法中，時間復(fù)雜度主要由閱讀器尋呼次數(shù)所控制，如式（2）所示。其中n為算法的執(zhí)行次數(shù)，f(n)為某個算法，T(n)為時間復(fù)雜度。空間復(fù)雜度由二叉樹防碰撞算法閱讀器與標(biāo)簽之間的總通信量決定，如式（3）所示。其中c為總通信量，f (c)為某個算法所需的存儲空間，S(c)為算法的空間復(fù)雜度。結(jié)合圖2和式（2）可知，NBBT算法的時間復(fù)雜度是最小的。結(jié)合圖5、圖8和式（3）可知，NBBT算法的空間復(fù)雜度也最小。

Fig.7 Comparison of reader traffic w ith guiding bit圖7 具有引導(dǎo)位的閱讀器通信量比較

Fig.8 Comparison of tag traffic w ith guiding bit圖8 具有引導(dǎo)位的標(biāo)簽通信量比較

Fig.9 Comparison of total traffic w ith guiding bit圖9 具有引導(dǎo)位的總通信量比較

Table 3 Analysis of guiding bit表3引導(dǎo)位分析

7 結(jié)束語

本文提出了一種改進的后退式二叉樹防碰撞算法，并闡述了算法的后退策略和基本思想，給出了算法的流程圖，對算法的識別過程進行了詳細的說明，最后利用開發(fā)的防碰撞算法仿真軟件比較分析了3種算法在閱讀器通信量、標(biāo)簽通信量以及總通信量上的特點，同時分析了引導(dǎo)位對3種通信量的影響。總之，本文算法可以明顯減少RFID系統(tǒng)的通信量，從而達到減少傳輸時延的目的。

References:

[1] Ning Huansheng. RFID national major projects and national Internet of things[M]. Beijing: China Machine Press, 2012: 7-20.

[2] Wang Gang. M inistry of industry and information issued the“Internet of things development planning”[J]. Internet of Things Technology, 2012, 2(3): 13-18.

[3] E-Batouty A S, Farag H H, E-Badaw y E-S. A new proposed anti-collision algorithm for RFID[C]//Proceedings of the 30th National Radio Science Conference, Cairo, Egypt, Apr 16-18, 2013. Piscataway, USA: IEEE, 2013: 15-17.

[4] Kim S C, Cho J S, Kim S K. Performance improvement of hybrid tag anti-collision protocol for radio frequency identification systems[J]. International Journal of Communication Systems, 2013, 26(6): 705-719.

[5] Kim S H, Park P G. An efficient tree-based tag anti-collision protocol for RFID systems[J]. IEEE Communications Letters, 2007, 11(5): 449-451.

[6] Lai Y C, Hsiao L Y. General binary tree protocol for coping w ith the capture effect in RFID tag identification[J]. IEEE Communications Letters, 2010, 14(3): 208-210.

[7] Cui Yinghua, Zhao Yuping. Performance evaluation of a multibranch tree algorithm in RFID[J]. IEEE Transactions on Communications, 2010, 58(5): 1356-1364.

[8] Kim S, Kim Y,Ahn K.An enhanced slotted binary tree algorithm w ith intelligent separation in RFID systems[C]//Proceedings of the 2009 IEEE Symposium on Computer and Communications, Sousse, Tunisia, Jul 5-8, 2009. Piscataway, USA: IEEE, 2009: 237-242.

[9] Wu Haifeng, Zeng Yu, Feng Jihua, et al. Binary tree slotted ALOHA for passive RFID tag anti-collision[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(1): 19-31.

[10] Lai Y C, Hsiao L Y. General binary tree protocol for coping w ith the capture effect in RFID tag identification[J]. IEEE Communications Letters, 2010, 14(3): 208-210.

[11] Choi J H, Lee D, Lee H. Query tree-based reservation for efficient RFID tag anti-collision[J]. IEEE Communications Letters, 2007, 11(1): 85-87.

[12] Yang C N, He J Y. An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision[J]. IEEE Communications Letters, 2011, 15(5): 539-541.

[13] Jia Xiaolin, Feng Quanyuan, Yu Lishan. Stability analysis of efficient anti-collision protocol for RFID tag identification[J]. IEEE Transactions on Communications, 2012, 60 (8): 2285-2294.

[14] Wang Xin, Jia Qingxuan, Gao Xin. Effective RFID anti-collision algorithm based on 3-ary collision-track tree[J]. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2014, 42(6): 73-78.

[15] Sun Yaolei, Wu Xiaobo, Chen Yuanwen. Improved quadtree RFID anti-collision algorithm[J]. Computer Engineering and Applications, 2014, 50(4): 63-68.

[16] Yan Weim in, Wu Weim in. Data structure[M]. Beijing: Tsinghua University Press, 2007: 13-17.

附中文參考文獻：

[1]寧煥生. RFID國家重大工程與國家物聯(lián)網(wǎng)[M].北京:機械工業(yè)出版社, 2012: 7-20.

[2]王剛.工信部發(fā)布《物聯(lián)網(wǎng)“十二五”發(fā)展規(guī)劃》[J].物聯(lián)網(wǎng)技術(shù), 2012, 2(3): 13-18.

[14]王鑫,賈慶軒,高欣.基于三叉碰撞跟蹤樹的高效RFID防碰撞算法[J].華中科技大學(xué)學(xué)報:自然科學(xué)版, 2014, 42 (6): 73-78.

[15]孫耀磊,吳曉波,陳元文.一種改進的四叉樹RFID防碰撞算法[J].計算機工程與應(yīng)用, 2014, 50(4): 63-68.

[16]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社, 2007: 13-17.

TANG Zhijun was born in 1974. He is an associate professor and M.S. supervisor at Hunan University of Science and Technology, and the member of CCF. His research interests include RFID technology, Internet of Things technology and UWB antenna, etc.

唐志軍（1974—），男，湖南邵陽人，湖南科技大學(xué)副教授、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為RFID技術(shù)，物聯(lián)網(wǎng)技術(shù)，超寬帶天線等。

YANG Yi was born in 1990. He is an M.S. candidate at Hunan University of Science and Technology. His research interests include RFID anti-collision technology and communication system modeling, etc.

陽懿（1990—），男，湖南長沙人，湖南科技大學(xué)碩士研究生，主要研究領(lǐng)域為RFID防碰撞技術(shù)，通信系統(tǒng)建模等。

WU Xiaofeng was born in 1974. He is an associate professor and M.S. supervisor at Hunan University of Science and Technology, and the member of CCF. His research interest is the design and optim ization of high power m icrowave power amplifiers.

吳笑峰（1974—），男，湖南漣源人，湖南科技大學(xué)副教授、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域為高功率微波功率放大器設(shè)計及優(yōu)化等。

XI Zaifang was born in 1974. He received the M.S. degree from Hunan University in 2003. Now he is an associate professor and M.S. supervisor at Hunan University of Science and Technology. His research interests include signal processing and communication system, etc.

席在芳（1974—），男，湖南常德人，2003年于湖南大學(xué)獲得碩士學(xué)位，現(xiàn)為湖南科技大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為信號處理，現(xiàn)代通信系統(tǒng)等。

HU Shigang was born in 1980. He received the Ph.D. degree in microelectronics from Xidian University in 2009. Now he is an associate professor and M.S. supervisor at Hunan University of Science and Technology. His research interests include analog integrated circuit design and sem iconductor devices, etc.

胡仕剛（1980—），男，湖北咸寧人，2009年于西安電子科技大學(xué)獲得博士學(xué)位，現(xiàn)為湖南科技大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為模擬集成電路設(shè)計，半導(dǎo)體器件等。

Novel Back-off Binary TreeAnti-collision Algorithm for Ultra High Frequency RFID?

TANG Zhijun+, YANG Yi, WU Xiaofeng, XI Zaifang, HU Shigang
College of Information & Electrical Engineering, Hunan University of Science and Technology, Xiangtan, Hunan 411201, China
+ Corresponding author: E-mail: zjtang@hnust.edu.cn

Key words:radio frequency identification (RFID); binary tree anti-collision algorithm; back-off paging; guiding bit

Abstract:Aiming at some problems of existing binary tree anti-collision algorithms in ultra high frequency radio frequency identification (RFID) systems, such as larger communication traffic and higher transmission delay, this paper proposes a novel back-off binary tree (NBBT) anti-collision algorithm by combining the jumping dynam ic search (JDS) and the novel JDS (NJDS) anti-collision algorithms, and introducing a back-off paging strategy. The proposed algorithm adds a guiding bit to the reader?s paging instruction in order that the tag can respond to the reader quickly. As a result, the proposed algorithm can reduce total communication traffic and the transm ission delay. Compared w ith the existing JDS or NJDS algorithms, the simulated results show that the proposed algorithm is more efficient in transmission delay and communication traffic. Furthermore, the algorithm can significantly improve the communication rate between the reader and the tag.

doi:10.3778/j.issn.1673-9418.1507073

文獻標(biāo)志碼：A

中圖分類號：TN926；TN915