史長(zhǎng)瓊，夏廣偉，嚴(yán)利輝

SHI Changqiong1，2,XIAGuangwei1，2,YAN Lihui1，2

1.長(zhǎng)沙理工大學(xué) 智能交通大數(shù)據(jù)處理湖南省重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410114

2.長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

1.Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation,Changsha University of Science and Technology,Changsha 410114,China

2.SchoolofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha410114,China

1 引言

RFID射頻識(shí)別技術(shù)（Radio Frequency Identification，RFID），是利用射頻信號(hào)通過(guò)空間耦合實(shí)現(xiàn)無(wú)接觸信息傳遞并通過(guò)所傳遞的信息達(dá)到識(shí)別目的，具有快速、實(shí)時(shí)準(zhǔn)確的采集與處理信息的特點(diǎn)。RFID系統(tǒng)主要包括標(biāo)簽（Tag）和讀寫(xiě)器（Reader）兩部分，標(biāo)簽用于對(duì)象的身份識(shí)別，每個(gè)標(biāo)簽具有唯一的ID。閱讀器用于接收標(biāo)簽信息，通過(guò)無(wú)線信號(hào)在可讀范圍內(nèi)識(shí)別所有標(biāo)簽，廣泛應(yīng)用于自動(dòng)識(shí)別系統(tǒng)，比傳統(tǒng)的條形碼更加方便、快速并且無(wú)需直接接觸被識(shí)別物體[1-3]。在射頻識(shí)別系統(tǒng)中，若有多個(gè)標(biāo)簽在同一時(shí)間響應(yīng)閱讀器將會(huì)發(fā)生標(biāo)簽碰撞，此時(shí)，閱讀器無(wú)法快速識(shí)別出標(biāo)簽，標(biāo)簽必須在閱讀器的查詢指令下重新發(fā)送ID直到標(biāo)簽被識(shí)別，導(dǎo)致識(shí)別時(shí)間過(guò)長(zhǎng)，嚴(yán)重影響識(shí)別效率[4]。

結(jié)合比特轉(zhuǎn)換和分時(shí)隙的思想，本文提出一種基于比特轉(zhuǎn)換的時(shí)隙二叉樹(shù)RFID標(biāo)簽防碰撞算法（Bit-Conversion anti-collision algorithm based on Slotted Binary Tree，BC-SBT），通過(guò)將標(biāo)簽的原始比特進(jìn)行轉(zhuǎn)換，根據(jù)轉(zhuǎn)換后比特碰撞位的不同，結(jié)合轉(zhuǎn)換后比特的特點(diǎn)，分時(shí)隙響應(yīng)閱讀器的查詢請(qǐng)求，閱讀器收到標(biāo)簽發(fā)送的數(shù)據(jù)，直接還原出ID信息，從而減少查詢次數(shù)并降低通信量。

2 相關(guān)工作

按照標(biāo)簽響應(yīng)方式，防碰撞算法通常分為不確定算法和確定性算法兩種[5]。不確定性算法大都基于Aloha機(jī)制，標(biāo)簽利用隨機(jī)時(shí)間響應(yīng)閱讀器，如時(shí)隙Aloha、Frame-slotted Aloha算法等；確定性算法根據(jù)標(biāo)簽的惟一性選擇標(biāo)簽進(jìn)行通信，最常見(jiàn)的算法是樹(shù)型搜索算法，包括二叉樹(shù)算法、動(dòng)態(tài)二叉樹(shù)算法、查詢樹(shù)算法等。

2.1 Aloha算法

Aloha算法的基本原理是在識(shí)別過(guò)程中，閱讀器檢測(cè)標(biāo)簽的響應(yīng)是否存在碰撞，如果存在，則閱讀器發(fā)送終止命令，并且每個(gè)標(biāo)簽等待隨機(jī)延遲時(shí)間來(lái)響應(yīng)閱讀器。根據(jù)不同的情況，基于Aloha的算法可以分為Slot-Aloha（SA）算法、幀時(shí)隙Aloha（FSA）算法和動(dòng)態(tài)幀時(shí)隙Aloha（DFSA）算法[6]。由于Aloha算法識(shí)別標(biāo)簽的時(shí)隙比較簡(jiǎn)單，在少量標(biāo)簽的情況下性能良好。然而，時(shí)隙是隨機(jī)生成的，所以存在一定的時(shí)間延遲，導(dǎo)致標(biāo)簽不可識(shí)別或不正確識(shí)別，即標(biāo)簽餓死情況[7]。而且，隨著標(biāo)簽數(shù)量的增加，算法的性能也會(huì)下降。

2.2 二叉樹(shù)搜索算法（BS算法）

樹(shù)型搜索算法是一種確定性標(biāo)簽防碰撞算法[8-9]。該算法將閱讀器查詢范圍內(nèi)的多個(gè)標(biāo)簽ID進(jìn)行逐位比較，直到成功讀取該標(biāo)簽信息。文獻(xiàn)[10]中，Wang Xue等提出二叉樹(shù)搜索算法（BS算法），根據(jù)標(biāo)簽ID的信息所建的N叉查找樹(shù)，并令N=2。標(biāo)簽根據(jù)碰撞信號(hào)的譯碼結(jié)果發(fā)出尋呼，每識(shí)別出一個(gè)標(biāo)簽就返回到起始點(diǎn)，是樹(shù)型算法中的經(jīng)典算法。其在識(shí)別過(guò)程中，將標(biāo)簽ID按照響應(yīng)建立搜索樹(shù)，以樹(shù)的路徑搜索葉節(jié)點(diǎn)來(lái)完成對(duì)標(biāo)簽的識(shí)別。同時(shí)，規(guī)定標(biāo)簽擁有唯一的ID，且電子標(biāo)簽需要準(zhǔn)確同步，標(biāo)簽的序列號(hào)必須采用曼徹斯特編碼。如圖1所示，閱讀器根據(jù)接收到的標(biāo)簽的應(yīng)答，找到碰撞位，并據(jù)此向它們發(fā)送請(qǐng)求，采用二叉樹(shù)查找的方法，可以根據(jù)每個(gè)標(biāo)簽ID號(hào)的不同將它們逐一區(qū)分開(kāi)來(lái)。與基于Aloha的算法相比，樹(shù)遍歷算法不遭受標(biāo)簽饑餓，但是在面對(duì)長(zhǎng)標(biāo)簽ID時(shí)仍然產(chǎn)生許多沖突時(shí)隙。并且不管是否存在樹(shù)的碰撞節(jié)點(diǎn)，該算法會(huì)遍歷整個(gè)二叉樹(shù)，這將導(dǎo)致RFID系統(tǒng)的效率降低。

圖1 編碼碰撞識(shí)別示例圖

2.3 4-ary詢問(wèn)樹(shù)算法（4-ary QT算法）

文獻(xiàn)[11]提出了4-ary QT算法，是一種基于詢問(wèn)樹(shù)算法（QT算法）的改進(jìn)算法。QT算法在識(shí)別過(guò)程中引入“終止”命令，一旦發(fā)生碰撞，則終止標(biāo)簽繼續(xù)發(fā)送ID，閱讀器以初始“0”或“1”開(kāi)始查詢，若以“0”開(kāi)始，則閱讀器以前綴“01”開(kāi)始向范圍內(nèi)的標(biāo)簽詢問(wèn)，如果響應(yīng)的標(biāo)簽碰撞，閱讀器將串“01”增長(zhǎng)為“010”繼續(xù)詢問(wèn)，直到完全識(shí)別標(biāo)簽。當(dāng)識(shí)別完所有以“010”為前綴的標(biāo)簽后，開(kāi)始識(shí)別以“011”為前綴的標(biāo)簽。因此，查詢樹(shù)的內(nèi)部節(jié)點(diǎn)為碰撞周期，葉子節(jié)點(diǎn)為空閑周期或成功周期。為了減少碰撞和查詢次數(shù)，改進(jìn)的4-ary QT算法結(jié)合了QT算法和時(shí)隙補(bǔ)償機(jī)制，通過(guò)減少標(biāo)簽碰撞周期和空閑周期，來(lái)減少平均標(biāo)簽識(shí)別延時(shí)，并使用四叉查詢樹(shù)代替?zhèn)鹘y(tǒng)的二叉詢問(wèn)樹(shù)。如果響應(yīng)的標(biāo)簽發(fā)生碰撞，下次閱讀器的詢問(wèn)串不像傳統(tǒng)的QT算法那樣增加1個(gè)二進(jìn)制位，而是增加2位再進(jìn)行詢問(wèn)。因此增加了詢問(wèn)樹(shù)的寬度，減少了碰撞周期。在4-ary QT算法中，節(jié)點(diǎn)編碼具有四種組合：“00，01，10和11”，并將記錄分組到標(biāo)簽的原始編碼，該算法改進(jìn)了生成樹(shù)的結(jié)構(gòu)且消除了空槽。

基于樹(shù)型的標(biāo)簽防碰撞算法不存在標(biāo)簽餓死情況，但此類(lèi)算法查詢次數(shù)多，識(shí)別時(shí)間過(guò)長(zhǎng)，通信量大仍是限制系統(tǒng)效率的主要因素。因此，本文提出一種基于比特轉(zhuǎn)換的時(shí)隙二叉樹(shù)RFID標(biāo)簽防碰撞算法，結(jié)合了樹(shù)型算法，并使標(biāo)簽分時(shí)隙響應(yīng)閱讀器的查詢請(qǐng)求，通過(guò)設(shè)計(jì)一種新的反向編碼轉(zhuǎn)換規(guī)則，使得識(shí)別碰撞的過(guò)程更加高效。

3 BC-SBT（Bit-Conversion anti-collision algorithm based on Slotted Binary Tree）算法

改進(jìn)的樹(shù)型算法和Aloha算法雖然在一定程度上提升了識(shí)別效率，但仍然存在查詢次數(shù)多，消耗時(shí)間長(zhǎng)和冗余數(shù)據(jù)量大等局限性，致使系統(tǒng)的吞吐率和識(shí)別效率無(wú)法達(dá)到最優(yōu)。本文融合分時(shí)隙思想和樹(shù)型算法的優(yōu)點(diǎn)，提出一種基于比特轉(zhuǎn)碼的時(shí)隙二叉樹(shù)算法，該算法的原理是：首先設(shè)計(jì)轉(zhuǎn)碼規(guī)則，將標(biāo)簽ID識(shí)別碼進(jìn)行轉(zhuǎn)換，響應(yīng)閱讀器查詢請(qǐng)求，如果產(chǎn)生碰撞，則根據(jù)曼徹斯特編碼規(guī)則，判斷出碰撞位置，然后分時(shí)隙響應(yīng)閱讀器；最后，進(jìn)行編碼還原，最終達(dá)到識(shí)別標(biāo)簽信息的目的。

3.1 算法描述

在BC-SBT算法中，標(biāo)簽內(nèi)部設(shè)有轉(zhuǎn)碼器，可以將標(biāo)簽的ID信息經(jīng)過(guò)編碼后發(fā)送給閱讀器，例如：標(biāo)簽信息中分別含有“00，01，10，11”等編碼，則經(jīng)過(guò)反向編碼轉(zhuǎn)換后，其編碼變?yōu)椤?000，0100，0010，0001”，轉(zhuǎn)碼流程如圖2所示。

圖2 兩位比特一組轉(zhuǎn)換格式示例圖

3.1.1 算法核心

根據(jù)以上轉(zhuǎn)碼規(guī)則，可將標(biāo)簽信息進(jìn)行每2位比特一轉(zhuǎn)，且經(jīng)過(guò)轉(zhuǎn)碼后的每4位比特有且只有1個(gè)“1”，基于此特點(diǎn)，設(shè)置碰撞位第1位為“1”的標(biāo)簽在第1時(shí)隙響應(yīng)，碰撞位第1位為“0”的標(biāo)簽在第2時(shí)隙響應(yīng)。

基于比特轉(zhuǎn)換的時(shí)隙二叉樹(shù)防碰撞算法主要在以下方面進(jìn)行改進(jìn)：

（1）減少了查詢次數(shù)和查詢時(shí)間

閱讀器發(fā)送尋呼指令之后，范圍內(nèi)的所有電子標(biāo)簽對(duì)此尋呼做出應(yīng)答，本算法經(jīng)轉(zhuǎn)碼后采用4位比特為一組的方式來(lái)進(jìn)行識(shí)別，每組識(shí)別后，只需返回上次的碰撞節(jié)點(diǎn)并根據(jù)每4位比特有且只有1個(gè)“1”的規(guī)則判斷下一組碰撞位置，進(jìn)行下一組的識(shí)別過(guò)程，并不需要像BS算法和返回到根節(jié)點(diǎn)去發(fā)送尋呼識(shí)別其他電子標(biāo)簽；而4-ary QT算法雖然在BS算法的基礎(chǔ)上，將二叉樹(shù)改進(jìn)為四叉樹(shù)來(lái)進(jìn)行識(shí)別，但是同樣需要返回根節(jié)點(diǎn)重新進(jìn)行尋呼，這樣與本文的算法相比就大大增加了查詢的次數(shù)和查詢時(shí)間。

（2）減少了數(shù)據(jù)冗余

在標(biāo)簽的識(shí)別過(guò)程中，按本文算法規(guī)則對(duì)標(biāo)簽進(jìn)行分組，閱讀器收到譯碼后比特并得到n個(gè)沖突位，只需發(fā)送代表沖突位的指令即可進(jìn)行識(shí)別，例如：閱讀器收到的信息為101000XX10XX，則只需發(fā)送Request（A2，3）即可，并不需要重新發(fā)送前面的比特序列。而B(niǎo)S算法和4-ary QT算法中，閱讀器和電子標(biāo)簽每次發(fā)出的尋呼是整個(gè)序列號(hào)，含有的冗余信息太大，BC-SBT算法就是在此基礎(chǔ)上繼續(xù)減除尋呼中信息冗余位，以減少傳輸時(shí)延和能耗。

（3）提高了識(shí)別效率和系統(tǒng)吞吐量

由于Aloha算法在RFID的防碰撞過(guò)程中有著很好的效果，使其廣泛地被引入到標(biāo)簽的防碰撞的應(yīng)用中，但是當(dāng)標(biāo)簽數(shù)稍多時(shí)，該算法的效率很低，如果將信道劃分為固定時(shí)隙，使得標(biāo)簽只能在某一時(shí)隙內(nèi)應(yīng)答，可將系統(tǒng)的效率提高1倍。本文根據(jù)該優(yōu)點(diǎn)，在樹(shù)型算法中引入了時(shí)隙的思想，使標(biāo)簽分時(shí)隙對(duì)閱讀器進(jìn)行應(yīng)答，以圖3所示為例：假如閱讀器收到的碰撞信息為XX0XXXXXXXXXXXXX，則根據(jù)轉(zhuǎn)碼特點(diǎn)，可判斷出前4位可能為“1000，0100或0001”，令所有以“1000”開(kāi)始的ID在第1個(gè)時(shí)隙進(jìn)行響應(yīng)，以“0100，0001”開(kāi)始的在第2個(gè)時(shí)隙響應(yīng)。和BS算法和4-ary QT算法相比，這樣即可有效地減少重復(fù)循環(huán)所發(fā)送的比特?cái)?shù)，從而提高識(shí)別效率，大大增加了系統(tǒng)的吞吐率。

圖3 時(shí)隙響應(yīng)示例圖

3.1.2 算法約定

根據(jù)標(biāo)簽碰撞位個(gè)數(shù)分為如下不同的形式：

（1）如果閱讀器收到的編碼中只有1個(gè)碰撞位，則根據(jù)標(biāo)簽ID的唯一性，可以直接識(shí)別出標(biāo)簽ID信息，并且可以判斷出只有2個(gè)標(biāo)簽響應(yīng)。

（2）如果閱讀器收到的編碼中有2位發(fā)生碰撞，按照本文中轉(zhuǎn)碼規(guī)則進(jìn)行轉(zhuǎn)換。例如：當(dāng)閱讀器收到的信息為XXX0時(shí)，則可以判斷出標(biāo)簽發(fā)送信息經(jīng)過(guò)轉(zhuǎn)碼后變?yōu)椤?000，0100，0010”，由于轉(zhuǎn)換之后的4位比特中只有一個(gè)1，可直接識(shí)別出標(biāo)簽中轉(zhuǎn)碼為“1000，0100，0010”的標(biāo)簽，將其按照比特轉(zhuǎn)碼規(guī)則還原后為“00，01，10”，并且可以直接判斷出標(biāo)簽數(shù)為3個(gè)。

（3）如果是其他的碰撞的情況，首先將所有碰撞位按照本文的轉(zhuǎn)換規(guī)則進(jìn)行編碼轉(zhuǎn)換（如果標(biāo)簽長(zhǎng)度為n，則轉(zhuǎn)換之后的長(zhǎng)度為2n），在閱讀器發(fā)送查詢命令后，將經(jīng)過(guò)轉(zhuǎn)碼后的ID信息發(fā)送給閱讀器，從第1位碰撞位開(kāi)始，轉(zhuǎn)碼后首位為“1”的標(biāo)簽在第1時(shí)隙響應(yīng)，為“0”的標(biāo)簽在第2時(shí)隙響應(yīng)，由于轉(zhuǎn)碼后每4位比特中有且只有1個(gè)“1”存在，所以可以按照這個(gè)特點(diǎn)將每4位設(shè)定為1組，分別另碰撞位為“1”，其他3位為“0”進(jìn)行識(shí)別。按照以上算法規(guī)則分組后，每組的碰撞情況可以重新轉(zhuǎn)化為上述的只有1位碰撞和只有2位碰撞的方式進(jìn)行識(shí)別。

3.2 算法流程

本文結(jié)合了樹(shù)型搜索算法和標(biāo)簽分時(shí)隙響應(yīng)的閱讀器思想，設(shè)計(jì)基于比特轉(zhuǎn)碼的時(shí)隙二叉樹(shù)算法，使閱讀器能夠準(zhǔn)確識(shí)別出碰撞位置[12]，然后對(duì)轉(zhuǎn)碼后的比特信息進(jìn)行分組并分配時(shí)隙。采用曼徹斯特編碼[13]規(guī)則，該編碼約定邏輯“1”對(duì)應(yīng)信號(hào)含下降沿跳變，而邏輯“0”對(duì)應(yīng)信號(hào)含上升沿跳變，若無(wú)狀態(tài)跳變，則視為錯(cuò)誤被識(shí)別。標(biāo)簽ID序列碼根據(jù)比特轉(zhuǎn)換規(guī)則進(jìn)行出廠設(shè)置，轉(zhuǎn)換規(guī)則按照?qǐng)D4所示，并以n位比特為例。閱讀器內(nèi)置比特轉(zhuǎn)換還原模塊，標(biāo)簽內(nèi)置響應(yīng)時(shí)隙計(jì)數(shù)器，時(shí)隙數(shù)根據(jù)標(biāo)簽轉(zhuǎn)換后的位數(shù)確定。

圖4 n位比特一組比特轉(zhuǎn)換格式示例圖

（1）查詢命令Request（），本文中轉(zhuǎn)換規(guī)則是將每2位比特轉(zhuǎn)碼為4位比特，使得轉(zhuǎn)換后每4位編碼中有且只有1個(gè)“1”存在，基于此設(shè)置參數(shù) Ax、Bx、Cx…（其中A，B，C…為分組序號(hào)，且 x=2，3，4）作為編碼定位。例如編碼轉(zhuǎn)換后閱讀器收到的信息為：0XXXXXX0，則可以分為A組和B組，同時(shí)另0100XXX0在第1時(shí)隙響應(yīng)，0010XXX0，0001XXX0在第2時(shí)隙響應(yīng)，然后閱讀器發(fā)送Request（A3，1）查詢命令，即可識(shí)別出符合條件的標(biāo)簽的ID信息。

（2）退出選擇命令unselect，當(dāng)標(biāo)簽完全被識(shí)別后，則閱讀器取消對(duì)此標(biāo)簽的選中，使標(biāo)簽進(jìn)入到“無(wú)聲”狀態(tài)。在此狀態(tài)下，標(biāo)簽處于“非激活”狀態(tài)，對(duì)于以后收到的Request命令不做回應(yīng)。

BC-SBT算法流程如圖5所示，步驟如下：

步驟1閱讀器發(fā)送查詢命令Request（）。

步驟2進(jìn)行編碼反向轉(zhuǎn)碼，經(jīng)轉(zhuǎn)碼后所有與查詢命令匹配的標(biāo)簽進(jìn)行響應(yīng)，閱讀器根據(jù)曼徹斯特編碼規(guī)則識(shí)別標(biāo)簽信息，如果沒(méi)有發(fā)生碰撞，則進(jìn)入到步驟4；如果發(fā)生碰撞，則進(jìn)入到步驟3。

圖5 BC-SBT算法流程圖

步驟3判斷碰撞個(gè)數(shù)和碰撞位信息，如果只有1位碰撞，根據(jù)標(biāo)簽ID的唯一性，可以直接識(shí)別出標(biāo)簽；如果有2位及以上碰撞，則根據(jù)轉(zhuǎn)碼規(guī)則，每4位比特中有且只有1個(gè)“1”，閱讀器發(fā)送對(duì)應(yīng)Request命令，使得符合條件的標(biāo)簽響應(yīng)，最終識(shí)別后進(jìn)入到步驟4。

步驟4閱讀器成功識(shí)別標(biāo)簽后，執(zhí)行unselect命令，使標(biāo)簽進(jìn)入到“無(wú)聲”狀態(tài)。

3.3 算法舉例

下面舉例說(shuō)明BC-SBT算法識(shí)別標(biāo)簽的步驟，假設(shè)有6個(gè)待識(shí)別標(biāo)簽的ID分別為a：00110010，b：10101101，c：01001010，d：11011011，e：10000110，f：01110100。經(jīng)過(guò)標(biāo)簽內(nèi)轉(zhuǎn)碼后變?yōu)閍：1000000110000010，b：0010001 000010100，c：0100100000100010，d：0001010000100001，e：0010000101000010，f：0100000101001000。當(dāng)閱讀器發(fā)送查詢命令后，所有標(biāo)簽響應(yīng)閱讀器，此時(shí)閱讀器收到的信息為XXXXXXXXXXXXXXXX，此時(shí)共有16位發(fā)生碰撞。閱讀器根據(jù)收到的信息發(fā)送查詢命令，按每4位一組進(jìn)行識(shí)別，首先使第1位碰撞位為“1”（同時(shí)令其他3位為“0”）的標(biāo)簽在第1時(shí)隙響應(yīng)，閱讀器發(fā)送Request（A1，1）命令，即令第一組首個(gè)碰撞位為“1”的標(biāo)簽進(jìn)行響應(yīng)，此時(shí)響應(yīng)的標(biāo)簽只有a：1000000110000010，通過(guò)編碼還原后可以直接識(shí)別出a標(biāo)簽。在第2個(gè)時(shí)隙中，閱讀器發(fā)送request（A2，1）命令，即令第二組首個(gè)碰撞位為“1”的標(biāo)簽進(jìn)行響應(yīng)，此時(shí)，分別有c：0100100000100010，f：0100000101001000兩個(gè)標(biāo)簽對(duì)其響應(yīng)，閱讀器接收的信息為0100X00X0XX0X0X0，然后將c、f標(biāo)簽信息壓棧，繼續(xù)判斷碰撞位信息，同時(shí)分配下個(gè)響應(yīng)時(shí)隙。在此次查詢中的第1個(gè)時(shí)隙中，可以根據(jù)上述過(guò)程直接識(shí)別出標(biāo)簽c，進(jìn)而根據(jù)算法約定規(guī)則判斷出標(biāo)簽f，對(duì)其進(jìn)行編碼還原后可以識(shí)別出標(biāo)簽ID信息。然后，閱讀器發(fā)送Request（A3，1）命令，即令第三組首個(gè)碰撞位為“1”的標(biāo)簽進(jìn)行響應(yīng)，響應(yīng)的標(biāo)簽有兩個(gè)，分別是b：0010001000010100，e：0010000101000010，此時(shí)閱讀器收到的信息為001000XX0X0X0XX0，將b，e標(biāo)簽信息壓棧，同時(shí)判斷碰撞位信息，并分配響應(yīng)時(shí)隙，此次查詢中的第1個(gè)時(shí)隙，可以直接識(shí)別出標(biāo)簽b，進(jìn)而識(shí)別出標(biāo)簽e，對(duì)其進(jìn)行編碼還原識(shí)別出標(biāo)簽ID信息。最后閱讀器發(fā)送request（A4，1）命令，標(biāo)簽d響應(yīng)，此時(shí)識(shí)別出全部標(biāo)簽。全部識(shí)別過(guò)程如表1所示，表中φ表示空集。

4 算法性能分析

采用叉樹(shù)算法（BS）來(lái)識(shí)別n個(gè)標(biāo)簽時(shí)，標(biāo)簽之間碰撞位的位置和ID的編碼值均會(huì)影響閱讀器的查詢次數(shù)，最好的狀況下查詢次數(shù)為2n-1，最壞情況下的查詢次數(shù)為，通過(guò)計(jì)算，可得出BS算法完成所有標(biāo)簽識(shí)別的查詢次數(shù)為：

表1 算法舉例識(shí)別過(guò)程

閱讀器和標(biāo)簽的篩選過(guò)程都發(fā)送完整的序列號(hào)，若發(fā)送一次查詢的時(shí)間為t，則識(shí)別n個(gè)標(biāo)簽的搜索時(shí)間為：

4-ary QT算法中，所有中間節(jié)點(diǎn)都是碰撞節(jié)點(diǎn)，所有的葉節(jié)點(diǎn)都是識(shí)別節(jié)點(diǎn)或空閑節(jié)點(diǎn)[16]，識(shí)別n個(gè)標(biāo)簽時(shí)，如果查詢深度為L(zhǎng)，則查詢次數(shù)和查詢時(shí)間分別為：

本文中BC-SBT算法中利用時(shí)隙的特點(diǎn)將碰撞位為“0”或“1”的標(biāo)簽分別在兩個(gè)時(shí)隙中響應(yīng)，并利用轉(zhuǎn)碼4位有且僅有1個(gè)“1”的規(guī)則，可以同時(shí)識(shí)別2個(gè)碰撞位，相比與BS算法在查詢次數(shù)上減少了約1/2，同時(shí)對(duì)比以上兩種算法，查詢時(shí)間提高了至少20%，并且系統(tǒng)的吞吐量也明顯高于BS算法和4-ary QT算法，BC-SBT算法查詢次數(shù)和查詢時(shí)間為：

5 實(shí)驗(yàn)分析

為了驗(yàn)證改進(jìn)算法的性能，本文使用Matlab進(jìn)行仿真對(duì)比。實(shí)驗(yàn)環(huán)境為在理想信道條件下，設(shè)定標(biāo)簽數(shù)量n為0～1 000，標(biāo)簽ID識(shí)別碼長(zhǎng)度為64 bit，從閱讀器的查詢次數(shù)、標(biāo)簽的查詢時(shí)間以及系統(tǒng)吞吐率三方面分別與文獻(xiàn)[10]中的BS算法和文獻(xiàn)[9]中的4-ary QT算法進(jìn)行仿真比較。

圖6 4-ary QT算法、BS算法、BC-SBT算法查詢次數(shù)比較

大量標(biāo)簽的情況如圖6所示，可以看出隨著標(biāo)簽數(shù)的增加，文獻(xiàn)[9]中的4-ary QT算法、文獻(xiàn)[10]中的BS算法和本文中的BC-SBT算法的查詢次數(shù)都在不斷上升。由于BS算法是基于二叉樹(shù)進(jìn)行搜索，而4-ary QT算法是基于四叉樹(shù)的搜索，導(dǎo)致查詢次數(shù)上BS幾乎達(dá)到4-ary QT算法的2倍；而B(niǎo)C-SBT算法中，由于引入轉(zhuǎn)碼規(guī)則，使得幾乎每一次都可以直接識(shí)別出標(biāo)簽，與文獻(xiàn)[9-10]進(jìn)行比較，大大減少了查詢次數(shù)。本文中的BC-SBT算法的查詢次數(shù)上升較為緩慢，明顯少于其他兩種算法?；诓樵兇螖?shù)與系統(tǒng)吞吐量的關(guān)系，可以反映出BC-SBT在對(duì)于系統(tǒng)吞吐量的優(yōu)化上，要高于其他兩種算法。

圖7中，通過(guò)本文算法與文獻(xiàn)[9]和文獻(xiàn)[10]中的算法同時(shí)識(shí)別1 000個(gè)隨機(jī)生成的64位標(biāo)簽，可以發(fā)現(xiàn)隨著標(biāo)簽數(shù)量的增加，查詢時(shí)間是一個(gè)呈指數(shù)上升的過(guò)程，從結(jié)果上看：當(dāng)標(biāo)簽數(shù)小于500時(shí)，三種算法識(shí)別所用的時(shí)間差距不大；當(dāng)標(biāo)簽數(shù)大于500時(shí)，其他兩種算法所需要的時(shí)間要漸漸多余本文的BC-SBT算法；而完全識(shí)別1 000個(gè)標(biāo)簽時(shí)，BS算法需要大概5.4 s的時(shí)間，4-ary QT算法需要4.8 s的時(shí)間，而B(niǎo)C-SBT算法只用了4 s的時(shí)間，在識(shí)別效率上較其他兩種算法提高了20%以上。

圖7 4-ary QT算法、BS算法、BC-SBT算法查詢時(shí)間比較

系統(tǒng)的吞吐率是衡量算法性能的重要指標(biāo)，從圖8中可以看出三種算法的吞吐率在標(biāo)簽超過(guò)一定數(shù)量時(shí)都呈現(xiàn)下降趨勢(shì)，這種趨勢(shì)由最初的急劇下降，到趨于平緩，這主要是因?yàn)殡S著標(biāo)簽數(shù)的增加，查詢的次數(shù)也會(huì)越來(lái)越多[18-19]，但是由于文中BC-SBT算法采用時(shí)隙與轉(zhuǎn)碼相結(jié)合的方式，大大減少了查詢次數(shù)，基于系統(tǒng)吞吐量的計(jì)算公式（7），可以計(jì)算出系統(tǒng)的吞吐量要明顯優(yōu)于4-ary QT算法和BS算法。

圖8 4-ary QT算法、BS算法、BC-SBT算法吞吐率比較

6 結(jié)論

本文對(duì)目前研究的確定性標(biāo)簽防碰撞算法進(jìn)行分析和比較，提出了基于比特轉(zhuǎn)換的時(shí)隙二叉樹(shù)RFID標(biāo)簽防碰撞算法，通過(guò)將標(biāo)簽的ID信息進(jìn)行轉(zhuǎn)碼變換，再根據(jù)碰撞位首位的不同分時(shí)隙響應(yīng)閱讀器請(qǐng)求。經(jīng)過(guò)理論分析和實(shí)驗(yàn)證明，本文提出的BC-SBT算法可以大大減少識(shí)別過(guò)程中所需的查詢次數(shù)、查詢時(shí)間和數(shù)據(jù)冗余量，同時(shí)在識(shí)別效率和系統(tǒng)吞吐率等方面明顯優(yōu)于其他防碰撞算法。隨著大數(shù)據(jù)時(shí)代的來(lái)臨，標(biāo)簽無(wú)論是數(shù)量上，還是ID識(shí)別碼的長(zhǎng)度上都會(huì)呈不斷的增長(zhǎng)趨勢(shì)，本文中的BC-SBT算法在大量標(biāo)簽的防碰撞過(guò)程中有著更大的優(yōu)勢(shì)。

參考文獻(xiàn)：

[1]宋建華，郭亞軍，韓蘭勝.自調(diào)整混合樹(shù)RFID多標(biāo)簽防碰撞算法[J].電子學(xué)報(bào)，2014，42（4）：685-689.

[2]葉寧，王忠勤，王汝傳.基于EPC網(wǎng)絡(luò)的智能物資管理系統(tǒng)應(yīng)用研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22（10）：209-212.

相對(duì)于客觀性、可靠性、真實(shí)性的歷史成本計(jì)量模式，公允價(jià)值在現(xiàn)行會(huì)計(jì)制度中存在著很大的不確定性、主觀性和變動(dòng)性。這些因素導(dǎo)致的計(jì)量成果不準(zhǔn)確，是公允價(jià)值面臨的最大挑戰(zhàn)。

[3]李平，孫利民，吳佳英.基于可離散處理的RFID防碰撞混雜算法研究[J].通信學(xué)報(bào)，2013，34（8）：10-17.

[4]李萌，錢(qián)志鴻.基于時(shí)隙預(yù)測(cè)的RFID防碰撞ALOHA算法[J].通信學(xué)報(bào)，2011，32（12）：43-50.

[5]單建鋒，陳明，謝建兵.基于ALOHA算法的RFID防碰撞技術(shù)研究[J].南京郵電大學(xué)學(xué)報(bào)，2013，33（1）：56-61.

[6]吳海峰，曾玉.自適應(yīng)幀Aloha的RFID標(biāo)簽防沖突協(xié)議[J].計(jì)算機(jī)研究與發(fā)展，2011，48（5）：802-810.

[7]丁治國(guó)，郭立，朱學(xué)永.基于二叉樹(shù)分解的自適應(yīng)防碰撞算法[J].電子與信息學(xué)報(bào)，2009，31（6）：1395-1398.

[8]張學(xué)軍，王娟，王鎖萍.基于標(biāo)簽識(shí)別碼分組的連續(xù)識(shí)別防碰撞算法研究[J].電子與信息學(xué)報(bào)，2011，33（5）：1159-1165.

[9]Kim Y，Kim S，Ahn S L K.Improved 4-ary query tree algorithm for anti-collision in RFID system[C]//International Conference on Advanced Information Networking and Applications，2009：699-704.

[10]王雪，錢(qián)志鴻，胡正超.基于二叉樹(shù)的RFID防碰撞算法的研究[J].通信學(xué)報(bào)，2010，31（6）：49-57.

[11]張學(xué)軍，馬軍飛，魯友.基于位編碼單元的雙時(shí)隙防碰撞算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（9）：93-102.

[12]王必勝，張其善.可并行識(shí)別的超高頻RFID系統(tǒng)防碰撞性能研究[J].通信學(xué)報(bào)，2009，30（6）：108-113.

[13]梁彪，胡愛(ài)群，秦中元.一種新的RFID防碰撞算法設(shè)計(jì)[J].電子與信息學(xué)報(bào)，2007，29（9）：2158-2160.

[14]Cheng T，Jin L.Analysis and simulation of RFID anticollison algorithm[C]//IEEE Advanced Communication Technology，2007：697-701.

[15]Eom J B，Lee T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Comumunication Letters，2010，14（1）：60-62.

[16]Zhang Xuejun，Ye Chuanling，Ma Junfei.An improved anti-collision algorithm with intelligent seperation for RFID system[J].International Journal of Advancements in Computing Technology，2012，4（22）：823-831.

[17]Tian Yun，Chen Gongliang，Li Jianhua.Bi-slotted binary tree algorithm with stack for radio frequency identification tag anti-collision[J].Shanghai Jiao Tong University，2013，18（2）：173-179.

[18]Lai Y C，Hsiao L Y.Optimal slot assignment for binary tracking tree Protocol in RFID tag identification[J].IEEE/ACM Transactions on Networking，2015，23（1）.

[19] ?lic P，Radi? J，Ro?? N.Energy efficient tag estimation method for ALOHA-based RFID systems[J].IEEE Sensors Journal，2014，14（10）：3637-3647.