一種基于碰撞位指示的射頻識別標簽防碰撞算法

李志堅賴順橋

?

一種基于碰撞位指示的射頻識別標簽防碰撞算法

李志堅*①②賴順橋②

①(華南理工大學電子與信息學院 廣州 510640)②(廣州市光機電技術研究院 廣州 510663)

多標簽碰撞是射頻識別(RFID)技術在推廣應用中必須克服的一個問題。針對目前RFID標簽防碰撞算法存在識別效率低的不足，該文提出一種基于碰撞位指示的RFID標簽防碰撞的碰撞位指示算法(CBIA)。通過跟蹤待識別標簽的碰撞位，采用碰撞位編解碼技術，對待識別標簽進行重復分組，直到所有標簽都被正確識別。算法通過確定性分組，避免了空閑時隙的產生。仿真結果表明，采用CBIA算法的多標簽識別系統，吞吐率可以達到每時隙0.7個標簽，CBIA算法識別效率優于優化查詢跟蹤樹算法(OQTT)和碰撞跟蹤樹算法(CTTA)算法。

射頻識別；防碰撞算法；位跟蹤技術；吞吐率

1 引言

射頻識別(Radio Frequency IDentification, RFID)是上世紀90年代興起的一種非接觸式自動識別技術。近年來，隨著物聯網技術的發展，RFID被廣泛應用于軍事、供應鏈、衛生保健和公共管理等領域[1,2]。由于RFID系統標簽和讀寫器共用一個無線頻道，當多讀寫器和多標簽同時占用頻道通信時，信號相互干擾，發生了碰撞。

ALOHA算法易于實現，成本低廉，但是由于算法的時隙是隨機分配，因此可能造成某些標簽長時間無法識別，亦即存在標簽饑餓(tag starvation)問題。

基于樹的分組算法是確定型算法，算法依據確定的分組規則，對活動標簽反復分組，直到每個組內只含一個標簽或者不含標簽，從而識別所有標簽。根據分組規則的不同，基于樹的分組算法又進一步分為二進制樹搜索算法(Binary Tree protocol, BT)和查詢樹算法(Query Tree protocol, QT)?；镜腂T算法和QT算法都存在空閑時隙，降低了系統效率。

采用碰撞位跟蹤技術可以提高基于樹的分組算法的系統效率。增強防碰撞算法(Enhanced Anti-collision Algorithm, EAA)和碰撞跟蹤樹算法(Collision Tracking Tree Algorithm, CTTA)[11,12]分別是對基本的BT算法和QT算法，都采用了碰撞位跟蹤技術。這兩種算法都檢測最高碰撞位，之后按照最高碰撞位分別為‘0’和‘1’把碰撞標簽分成兩組，從而避免了空閑時隙的產生，提高了系統效率。

但是，當活動標簽數量很大時，EAA算法和CTTA算法都存在大量的碰撞時隙。減少碰撞時隙可以進一步提高系統效率。文獻[8]提出的優化查詢跟蹤樹算法(Optimal Query Tracking Tree, OQTT)算法。該算法在識別開始時，先通過碰撞位置估計標簽數量，之后依據最優分組規則把待識別標簽分成若干組，每一組都采用CTTA算法進行識別。OQTT減少了識別最初的碰撞時隙數量，提高了識別效率。

OQTT算法只在查詢樹首層增加了分支，而在每個子查詢樹里面仍采用CTTA算法。因此，在標簽數量很大的時候，識別初期的碰撞時隙還是比較多。進一步減少碰撞時隙，可以進一步提高系統效率。

本文正是基于進一步減少碰撞時隙的思想，提出一種基于碰撞位指示的RFID多標簽防碰撞算法(Collided Bits Indicator Algorithm, CBIA)。CBIA通過跟蹤待識別標簽的碰撞位，采用碰撞位編解碼技術，對待識別標簽進行重復分組，直到所有標簽都被正確識別。算法的創新點在于增加了查詢樹每一層的分枝數量，同時避免空閑時隙的產生，進一步壓縮了查詢樹的層數，減少了碰撞時隙的數量，提高了系統效率。本文通過數學分析，給出了CBIA算法的占用時隙的估計模型，并在此技術上得出了系統吞吐率估計。仿真結果表明，相對于現有查詢樹算法CTTA和OQTT算法，CBIA具有更快的識別速率和更高的吞吐率。

2 基于碰撞位指示(CBI)的RFID防碰撞算法

2.1 算法的預設條件

(1)標簽ID采用曼徹斯特編碼[13]，長度為，讀寫器能夠正確識別非碰撞位和碰撞位。讀寫器中設置一個查詢前綴堆棧S和兩個寄存器碰撞位模板(Collided Bits Mask, CBM)和識別位模板(Recognized Bits Mask, RBM)，分別用于記錄碰撞位和已識別位數據。

(2)標簽中設置一個2位的碰撞位指示(CBI) 寄存器。當接收讀寫器廣播的CBM時，標簽順序取出ID中的高位碰撞位，形成一個二進制數，這個二進制數成為碰撞位編碼CBC(Collided Bits Code)，然后根據CBC把CBI的第CBC位置‘1’，其他位置‘0’。

(3)標簽中設置一個狀態寄存器SF，標簽根據SF的值在不同的時候響應讀寫器命令。

2.2 算法的命令格式

(1)Act (0)命令：讀寫器廣播這個命令，有效通信范圍內所有標簽回送各自ID給讀寫器同時把狀態標志位SF置‘1’。

(2)Req (opt)：查詢命令。其中參數‘’是一個長度為()的二進制數，可以是查詢前綴序列或者CBM，由參數opt區分。參數opt為‘0’時，‘’是一個查詢前綴序列。若標簽ID的高()位與‘’一致，則標簽回送剩下的-()位給讀寫器并把狀態標志位SF置‘1’。參數opt為‘1’時，‘’是一個CBM。狀態標志位SF為‘1’的標簽回送CBI給讀寫器并把SF清零。

2.3 算法流程圖

CBIA算法的流程圖如圖1所示，其主要步驟如下：

步驟1 讀寫器初始化，清空堆棧S，清零CBM和RBM。廣播Act (0)命令。識別范圍內所有標簽回送ID并置位SF；

步驟2 讀寫器檢測碰撞位，設置CBM和RBM。如果沒有檢測到碰撞，讀寫器識別一個標簽；若只存在一個碰撞位，則讀寫器識別兩個標簽。如果存在多個碰撞位，讀寫器跟蹤所有碰撞發生的位置，并把CBM對應位置‘1’。讀寫器識別所有未碰撞位，把RBM對應位置上置位已識別數碼；

步驟3 讀寫器發送命令Req(CBM,1)。有效識別范圍內，SF為‘1’的標簽回送CBI并把SF置‘0’；

步驟..4 讀寫器接收CBI，并跟蹤所有碰撞位位置，然后根據碰撞位位置譯碼得到CBC。例如，若讀寫器接收到8位CBI為“000x0xx0”，x表示該位發生碰撞。則表示碰撞發生在第1，第2和第4位，那么讀寫器可以譯碼出3個CBC，分別是“001”，“010”，“100”；

圖1 CBIA流程圖

步驟6 若S不空，則讀寫器從S中取出一個查詢前綴序列，并廣播Req(prefix,0)命令。有效識別范圍內，ID高位與前綴一致的標簽回送剩余ID，并把SF置‘1’。算法跳轉到步驟2；

步驟7 若S讀空，則所有標簽都被識別，識別過程結束。

2.4 算法應用舉例

圖2給出了一個利用CBIA算法識別7個標簽TagA~TagG的示例。圖中x表示該位發生碰撞。CBC長度為4。在第1個時隙，讀寫器廣播啟動命令，所有標簽都響應讀寫器命令。在第2個時隙，讀寫器廣播CBM“111111111111011”。SF為‘1’的標簽回送CBI，并置 SF 為‘0’。在本示例中，標簽A, B, F和G 的CBI相同，均為“000001000000000”，對應CBC為“1010”；標簽C的CBC是“0101”回送CBI “0000000000100000”；標簽D 的CBC是“0001”回送CBI“00 00000000000010”；標簽E 的CBC是“0111”回送CBI“0000000010000000”。讀寫器接收端接收到的CBI為“00000x00x0x000x0”。這樣讀寫器可以根據碰撞位發生位置計算所有的CBC，分別是“1010”，“0111”，“0101”，“0001”。然后讀寫器就可以生產4個查詢前綴序列“1010”，“0111”，“0101”，“0001”，并壓棧。在第3個時隙，讀寫器取出一個查詢前綴序列“0001”，并廣播查詢命令。標簽D高4位與這個前綴一致，所以它回送剩余ID位，這樣標簽D成功識別。同樣標簽 C和 E 分別在第4個和第5個時隙被識別。第6個時隙，讀寫器廣播查詢前綴“1010”，標簽A, B, F 和G 同時回送剩余ID位并置各自SF為‘1’。讀寫器接收CBI“0x0xx0x0”。此時碰撞位位數為4，那么這4個標簽可以在下個時隙一次識別。在第7時隙，讀寫器廣播CBM “000001011010”，標簽A, B, F和G回送CBI。讀寫器接收CBI“00x00x0000x 0x000”經譯碼得CBCs:“1101”，“0101”，“1010”，“0011”，然后把CBC嵌入到RBM中可識別這4個標簽。此時，S為空，識別過程結束，所有標簽都被識別。

3 算法性能分析

算法性能可以通過估計識別個標簽所需要的時隙樹和估算系統吞吐量進行衡量。

在數學分析之前，有必要區分CBIA算法的兩種碰撞：

可識別碰撞：讀寫器在接收標簽回送ID數據時，如果檢測出碰撞位數不大于CBC位數，則碰撞的多個標簽可通過譯碼CBC全部識別。

不可識別碰撞：讀寫器在接收標簽回送ID數據時，如果檢測出碰撞位數大于CBC位數，則碰撞的多個標簽不可在一次譯碼中識別，這種碰撞為不可識別碰撞。

圖2 CBIA示例

由于每個數位等概率取得‘0’和‘1’。所以=1/2。當個標簽ID的同一位上均為‘0’或者‘1’時，該位不會發生碰撞。這樣個標簽某位不發生碰撞的概率為

(2)

相應地，該位發生碰撞的概率為

在一棵完整的CBIA查詢樹中，每個父節點可以產生2個子節點，第層有2子節點。每個子節點對應一個查詢前綴序列。個標簽ID中具有相同前綴的標簽ID數量服從二項分布

同樣，由于標簽ID是均勻分布，因此標簽前綴等概率出現，從而有

當只有一個標簽具有某一前綴時，該標簽可以直接識別。由式(4)，單標簽被識別的概率為

當多個標簽具有相同前綴，但回送數據僅有一個碰撞位時，說明當前只有兩個標簽響應讀寫器查詢命令，這樣兩個標簽可以一次識別。識別概率為

當多個標簽具有相同前綴，但回送數據碰撞位數n不大于時，通過下一個時隙CBC譯碼，這些標簽都可以識別出來，這種情況發生的概率為

如果用P表示CBIA查詢樹上第層的第個節點被訪問的概率。顯然當0,00/N1，也就是CBIA的根節點總是被訪問到。

進而有

這樣，CBIA算法訪問節點的數學期望為

綜上，有CBIA識別個標簽的時隙樹為

進而可得系統的吞吐率為

需要說明的是，在實際識別過程中，CBIA查詢樹的層數不可能無窮大，它與系統設置的標簽CBC位數有關。

4 實驗仿真分析

仿真結果表明：相比于CTTA, OQTT算法，CBIA算法平均識別時隙數優勢明顯，且隨著待識別標簽數據的增大，算法性能優勢越明顯。在系統吞吐率方面，CBIA算法性能優于其他兩種算法，平均每個時隙可識別0.7個標簽，優于OQTT算法的吞吐率僅為0.6和CTTA的0.5。

圖4反應了CBC位數和標簽ID位數對CBIA算法性能的影響。圖4(a)中，標簽ID位數固定為64位，標簽CBC位數分別為2,4,6,8,10位。圖4(b)中，標簽數量固定為1000個，標簽ID位數分別為32,48,64,96和128位。仿真結果表明，當CBC位數為6時，識別相同數量的標簽所用時隙最少。

5 算法的性能對比優勢和標簽硬件開銷分析

本節主要分析CBIA算法與CTTA, OQTT的對比優勢，并分析CBIA獲取這些優勢所付出的硬件成本。

5.1 算法的性能對比優勢

CTTA, OQTT和CBIA都是查詢樹算法QT的改進，其核心思想是不斷地對待識別標簽進行分組，直到組內標簽可以一次識別。這幾種算法性能差異，是由各自采取的分組協議引起的。

CTTA每次只處理一個碰撞位。每次檢測到碰撞位，CTTA自動把待識別標簽分成碰撞位為‘0’和‘1’的兩組，直到組內僅含一個標簽或者僅含有兩個只有一個沖突位的標簽，識別這些標簽。CTTA采用確定性分組，避免了空閑時隙的產生。然而，CTTA每次只把組內待識別標簽劃分成兩個小組。這樣，在標簽數量較大時，CTTA搜索深度會很深。而且，在識別初期，每一組內待識別標簽數量很大，碰撞概率很高，在標簽數量較大時，碰撞時隙數量非?？捎^，識別效率不高。

OQTT對QT算法的改進僅在于識別最初的最優化分組，而在之后的各組內識別過程仍舊采用CTTA算法。盡管采用了碰撞位跟蹤技術，但每次也僅處理一個碰撞位。這一方面，CTTA算法的不足，在OQTT算法中仍然存在。另一方面，OQTT的最優化分組是隨機分組。當標簽ID不服從均勻分布時，OQTT的最初分組會不平衡[8]，從而使得某些組內待識別標簽非常多，而某些組內待識別標簽很少，甚至沒有。其結果是OQTT算法性能下降。

圖3 算法性能比較

圖4 CBC位數和ID位數對CBIA性能影響仿真

CBIA算法與OQQT算法比較，其最大特點是確定性分組。與OQTT的隨機分組不同，CBIA算法在最初分組時采用確定性分組，每個小組內都有待識別標簽，不會出現無標簽的小組。因此，CBIA可以避免OQTT算法在最初分組時的空閑時隙的產生。而之后的識別過程，OQTT組內采用CTTA算法，這樣，CBIA算法對CTTA算法的優勢也同樣體現在對OQTT算法的比較中。

5.2 標簽硬件開銷分析

CTTA是采用了位跟蹤技術的QT算法。QT算法是一種無記憶防碰撞協議，標簽在識別過程中不需要存儲任何數據，每次回送剩余標簽ID。因此，CTTA算法標簽中無存儲資源，硬件成本低廉。

OQTT是對CTTA算法的改進，繼承了CTTA算法的無記憶的特點。但是，OQTT算法在最初的進行標簽數量估計時，需要標簽根據協議產生一個log2位的隨機數，并根據這個隨機數對一個位的二進制數(其中是標簽ID的位數)進行位調制[8]。因此，OQTT算法在硬件開銷方面，將增加隨機數生成模塊和位調制模塊。

CBIA算法也是CTTA算法的改進。根據協議需要，標簽接收讀寫器廣播的CBM，并根據CBM的非零位位置和標簽ID的對應位產生一個二進制數，并用這個二進制數對2位CBI進行位調制。因此，CBIA算法與OQTT類似，都增加了二進制數生成和位調制的硬件開銷。但是，由于CBC位數小于log2, CBI位數小于，因此，與OQTT比較，CBIA算法所消耗的硬件資源更少?？紤]到標簽需把調制后的二進制數回送讀卡器，OQTT算法回送一個位的二進制數，而CBIA算法僅回送一個2位的CBI，因此，CBIA比OQTT的通信數據量更少。

6 結束語

本文提出了一種新穎的RFID多標簽防碰撞算法，CBIA。該算法利用碰撞位跟蹤技術，對待識別標簽進行重復分組，直到所有標簽都被正確識別。算法增加了查詢樹的每一層分叉數目，同時避免了空閑時隙的產生，壓縮了查詢樹的層數，減少了碰撞時隙的數量。仿真結果表明，采用CBIA算法的多標簽識別系統，吞吐率可以達到每時隙0.7個標簽，CBIA算法識別效率優于OQTT和CTTA算法。最后，CBIA和OQTT都增加了一些硬件開銷，但是CBIA硬件開銷低于OQTT。

[1] Zuo Y J . Survivable RFID systems: issues, challenges and techniques[J].,,-:, 2010, 40(4): 406-418.

[2] Mohamed B, Adel M, and Belkacem F. Dual antenna for physical layer UHF RFID collision cancelling[C]. 2012 International Conference on Multimedia Computing and Systems, Melbourne, Australia, 2012: 623-628.

[3] Lee C C and Lin S Y. A double blocking dynamic framed slotted ALOHA anti-collision method for mobile RFID systems[C]. 2012 Sixth International Conference on Genetic and Evolutionary Computing, Kyushu, Japan2012: 581-584.

[4] Jiang Y J, Xu Y F, and Wang Q. Cancellation strategy in dynamic framed slotted ALOHA for RFID system[C]. 2013 IEEE Wireless Communications and Networking Conference (WCNC), Shanghai, China,2013: 854-859.

[5] Wang S, Hong W J, and Li S F. A slot-wise LMMSE estimate algorithm for frame slotted aloha protocol of RFID system[C]. 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai, China, 2012: 1-5.

[6] Xue J B, Wang W H, Li S B,.. Anti-collision algorithm based on counting mechanism and multi-state binary[C]. 2013 Fifth Conference on Measuring Technology and Mechatronics Automation, Hong Kong, China, 2013: 276-282.

[7] Landaluce H, Perallos A, and Zuazola I J G. A fast RFID identi?cation protocol with low tag complexity[J]., 2013, 17(9): 1704-1706.

[8] Lai Y C, Hsiao Y L, Chen H J,.. A novel query tree protocol with bit tracking in RFID tag identification[J]., 2012, 12(10): 2063-2075.

[9] Yang Y K, Cui C S, Zhou T F,.. Improvement on RFID-based binary anti-collision algorithm[C]. 2012 International Conference on Computer Science and Service System, Nanjing, China, 2012: 515-518.

[10] Jin D, Ma Y M, Fan Z P,.. A RFID anti-collision algorithm based on multithread regressive-style binary system[C]. 2012 International Conference on Measurement, Information and Control, Harbin, China, 2012: 365-369.

[11] Liang C K and Lin H M. Using dynamic slots collision tracking tree technique towards an efficient tag anti-collision algorithm in RFID systems[C]. 2012 9th International Conference on Ubiquitous Intelligence & Computing and 9th International Conference on Autonomic & Trusted Computing, Fukuoka, Japan, 2012: 272-277.

[12] Bai Y, Xuan X W, Teng J F,.. An anti-collision algorithm based on collision bit position and splitting[C]. 2010 6th International Conference on Wireless Communications Networking and Mobile Computing, Chengdu, China, 2010: 1-4.

[13] Piao C H, Fan Z J, Yang C Y,.. Research on group-based polling anti-collision algorithm for RFID tag identification[C]. 2010 International Forum on Information Technology and Applications. Kunming, China, 2010: 185-188.

李志堅： 男，1981年生，講師，研究方向為物聯網RFID關鍵技術與應用、雷達信號處理.

賴順橋： 男，1981年生，工程師，研究方向為物聯網RFID關鍵技術與應用.

An Anti-collision Algorithm Based on Collided Bits Indicatorin Radio Frequency Identification Systems

Li Zhi-jian①②Lai Shun-qiao②

①(,,510640,)②(,510663,)

Multiple tags collision becomes an important factor blocking the popularization of Radio Frequency IDentification (RFID). To improve the identification efficiency and reduce the communication overhead, an novel algorithm, anti-Collided Bits Indicator Algorithm (CBIA) is proposed base don Bits Indicator Algorthm (BIA). Using the collision bit tracking technology and collided bits coding technology, the reader splits the tags into smaller subsets according to the identified collided bits. This process is repeated until all collided bits are solved. CBIA groups the tags into determinate subsets to avoid generating idle slots. The analysis and simulation results show that the average throughput of CBIA is 0.7 tags per slot, which is better than that of other algorithms, such as Optimal Query Tracking Tree protocol (OQTT) and Collision Tracking Tree Algorithm (CTTA).

Radio Frequency IDentification (RFID); Anti-collision algorithm; Bit-tracking technology; Throughput

TN92

A

1009-5896(2014)12-2842-06

10.3724/SP.J.1146.2013.01759

李志堅 leemu1001@126.com

2013-11-08收到，2014-06-30改回

廣東省科技計劃 (2010A011300016)，廣州市科技計劃(2011J4100034)和中央高?；究蒲袠I務費自主項目(2009ZM0097)資助課題