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

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

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

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

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

2 相關(guān)工作

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

2.1 Aloha算法

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

2.2 二叉樹搜索算法（BS算法）

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

圖1 編碼碰撞識別示例圖

2.3 4-ary詢問樹算法（4-ary QT算法）

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

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

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

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

3.1 算法描述

在BC-SBT算法中，標(biāo)簽內(nèi)部設(shè)有轉(zhuǎn)碼器，可以將標(biāo)簽的ID信息經(jīng)過編碼后發(fā)送給閱讀器，例如：標(biāo)簽信息中分別含有“00，01，10，11”等編碼，則經(jīng)過反向編碼轉(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)過轉(zhuǎn)碼后的每4位比特有且只有1個“1”，基于此特點(diǎn)，設(shè)置碰撞位第1位為“1”的標(biāo)簽在第1時隙響應(yīng)，碰撞位第1位為“0”的標(biāo)簽在第2時隙響應(yīng)。

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

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

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

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

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

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

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

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

3.1.2 算法約定

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

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

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

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

3.2 算法流程

本文結(jié)合了樹型搜索算法和標(biāo)簽分時隙響應(yīng)的閱讀器思想，設(shè)計基于比特轉(zhuǎn)碼的時隙二叉樹算法，使閱讀器能夠準(zhǔn)確識別出碰撞位置[12]，然后對轉(zhuǎn)碼后的比特信息進(jìn)行分組并分配時隙。采用曼徹斯特編碼[13]規(guī)則，該編碼約定邏輯“1”對應(yīng)信號含下降沿跳變，而邏輯“0”對應(yīng)信號含上升沿跳變，若無狀態(tài)跳變，則視為錯誤被識別。標(biāo)簽ID序列碼根據(jù)比特轉(zhuǎn)換規(guī)則進(jìn)行出廠設(shè)置，轉(zhuǎn)換規(guī)則按照圖4所示，并以n位比特為例。閱讀器內(nèi)置比特轉(zhuǎn)換還原模塊，標(biāo)簽內(nèi)置響應(yīng)時隙計數(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個“1”存在，基于此設(shè)置參數(shù) Ax、Bx、Cx…（其中A，B，C…為分組序號，且 x=2，3，4）作為編碼定位。例如編碼轉(zhuǎn)換后閱讀器收到的信息為：0XXXXXX0，則可以分為A組和B組，同時另0100XXX0在第1時隙響應(yīng)，0010XXX0，0001XXX0在第2時隙響應(yīng)，然后閱讀器發(fā)送Request（A3，1）查詢命令，即可識別出符合條件的標(biāo)簽的ID信息。

（2）退出選擇命令unselect，當(dāng)標(biāo)簽完全被識別后，則閱讀器取消對此標(biāo)簽的選中，使標(biāo)簽進(jìn)入到“無聲”狀態(tài)。在此狀態(tài)下，標(biāo)簽處于“非激活”狀態(tài)，對于以后收到的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ī)則識別標(biāo)簽信息，如果沒有發(fā)生碰撞，則進(jìn)入到步驟4；如果發(fā)生碰撞，則進(jìn)入到步驟3。

圖5 BC-SBT算法流程圖

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

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

3.3 算法舉例

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

4 算法性能分析

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

表1 算法舉例識別過程

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

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

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

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

為了驗(yàn)證改進(jìn)算法的性能，本文使用Matlab進(jìn)行仿真對比。實(shí)驗(yàn)環(huán)境為在理想信道條件下，設(shè)定標(biāo)簽數(shù)量n為0～1 000，標(biāo)簽ID識別碼長度為64 bit，從閱讀器的查詢次數(shù)、標(biāo)簽的查詢時間以及系統(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算法是基于二叉樹進(jìn)行搜索，而4-ary QT算法是基于四叉樹的搜索，導(dǎo)致查詢次數(shù)上BS幾乎達(dá)到4-ary QT算法的2倍；而BC-SBT算法中，由于引入轉(zhuǎn)碼規(guī)則，使得幾乎每一次都可以直接識別出標(biāo)簽，與文獻(xiàn)[9-10]進(jìn)行比較，大大減少了查詢次數(shù)。本文中的BC-SBT算法的查詢次數(shù)上升較為緩慢，明顯少于其他兩種算法。基于查詢次數(shù)與系統(tǒng)吞吐量的關(guān)系，可以反映出BC-SBT在對于系統(tǒng)吞吐量的優(yōu)化上，要高于其他兩種算法。

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

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

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

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

6 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[8]張學(xué)軍，王娟，王鎖萍.基于標(biāo)簽識別碼分組的連續(xù)識別防碰撞算法研究[J].電子與信息學(xué)報，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]王雪，錢志鴻，胡正超.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報，2010，31（6）：49-57.

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

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

[13]梁彪，胡愛群，秦中元.一種新的RFID防碰撞算法設(shè)計[J].電子與信息學(xué)報，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.