分時隙的比特轉換RFID標簽防碰撞算法

史長瓊，夏廣偉，嚴利輝

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

1.長沙理工大學 智能交通大數據處理湖南省重點實驗室，長沙 410114

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

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

2 相關工作

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

2.1 Aloha算法

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

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

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

圖1 編碼碰撞識別示例圖

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

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

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

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

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

3.1 算法描述

在BC-SBT算法中，標簽內部設有轉碼器，可以將標簽的ID信息經過編碼后發送給閱讀器，例如：標簽信息中分別含有“00，01，10，11”等編碼，則經過反向編碼轉換后，其編碼變為“1000，0100，0010，0001”，轉碼流程如圖2所示。

圖2 兩位比特一組轉換格式示例圖

3.1.1 算法核心

根據以上轉碼規則，可將標簽信息進行每2位比特一轉，且經過轉碼后的每4位比特有且只有1個“1”，基于此特點，設置碰撞位第1位為“1”的標簽在第1時隙響應，碰撞位第1位為“0”的標簽在第2時隙響應。

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

（1）減少了查詢次數和查詢時間

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

（2）減少了數據冗余

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

（3）提高了識別效率和系統吞吐量

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

圖3 時隙響應示例圖

3.1.2 算法約定

根據標簽碰撞位個數分為如下不同的形式：

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

（2）如果閱讀器收到的編碼中有2位發生碰撞，按照本文中轉碼規則進行轉換。例如：當閱讀器收到的信息為XXX0時，則可以判斷出標簽發送信息經過轉碼后變為“1000，0100，0010”，由于轉換之后的4位比特中只有一個1，可直接識別出標簽中轉碼為“1000，0100，0010”的標簽，將其按照比特轉碼規則還原后為“00，01，10”，并且可以直接判斷出標簽數為3個。

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

3.2 算法流程

本文結合了樹型搜索算法和標簽分時隙響應的閱讀器思想，設計基于比特轉碼的時隙二叉樹算法，使閱讀器能夠準確識別出碰撞位置[12]，然后對轉碼后的比特信息進行分組并分配時隙。采用曼徹斯特編碼[13]規則，該編碼約定邏輯“1”對應信號含下降沿跳變，而邏輯“0”對應信號含上升沿跳變，若無狀態跳變，則視為錯誤被識別。標簽ID序列碼根據比特轉換規則進行出廠設置，轉換規則按照圖4所示，并以n位比特為例。閱讀器內置比特轉換還原模塊，標簽內置響應時隙計數器，時隙數根據標簽轉換后的位數確定。

圖4 n位比特一組比特轉換格式示例圖

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

（2）退出選擇命令unselect，當標簽完全被識別后，則閱讀器取消對此標簽的選中，使標簽進入到“無聲”狀態。在此狀態下，標簽處于“非激活”狀態，對于以后收到的Request命令不做回應。

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

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

步驟2進行編碼反向轉碼，經轉碼后所有與查詢命令匹配的標簽進行響應，閱讀器根據曼徹斯特編碼規則識別標簽信息，如果沒有發生碰撞，則進入到步驟4；如果發生碰撞，則進入到步驟3。

圖5 BC-SBT算法流程圖

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

步驟4閱讀器成功識別標簽后，執行unselect命令，使標簽進入到“無聲”狀態。

3.3 算法舉例

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

4 算法性能分析

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

表1 算法舉例識別過程

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

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

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

5 實驗分析

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

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

大量標簽的情況如圖6所示，可以看出隨著標簽數的增加，文獻[9]中的4-ary QT算法、文獻[10]中的BS算法和本文中的BC-SBT算法的查詢次數都在不斷上升。由于BS算法是基于二叉樹進行搜索，而4-ary QT算法是基于四叉樹的搜索，導致查詢次數上BS幾乎達到4-ary QT算法的2倍；而BC-SBT算法中，由于引入轉碼規則，使得幾乎每一次都可以直接識別出標簽，與文獻[9-10]進行比較，大大減少了查詢次數。本文中的BC-SBT算法的查詢次數上升較為緩慢，明顯少于其他兩種算法。基于查詢次數與系統吞吐量的關系，可以反映出BC-SBT在對于系統吞吐量的優化上，要高于其他兩種算法。

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

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

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

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

6 結論

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

參考文獻：

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

[2]葉寧，王忠勤，王汝傳.基于EPC網絡的智能物資管理系統應用研究[J].計算機技術與發展，2012，22（10）：209-212.

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

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

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

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

[6]吳海峰，曾玉.自適應幀Aloha的RFID標簽防沖突協議[J].計算機研究與發展，2011，48（5）：802-810.

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

[8]張學軍，王娟，王鎖萍.基于標簽識別碼分組的連續識別防碰撞算法研究[J].電子與信息學報，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].通信學報，2010，31（6）：49-57.

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

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

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