基于標簽分組的RFID系統防碰撞算法

郭振軍 孫應飛

?

基于標簽分組的RFID系統防碰撞算法

郭振軍*①②孫應飛①

①(中國科學院大學 北京 100049);②(桂林航天工業學院 桂林 541004)

防碰撞算法是射頻識別(RFID)系統中提高標簽識別效率的關鍵技術。針對確定性的RFID標簽防碰撞算法存在的識別效率不高、系統數據交換量大等問題，該文提出一種標簽分組機制防碰撞算法，將其與融合后的二進制樹搜索算法相結合，讀寫器系統分批次識別標簽組中的標簽，能有效地減少數據通信量。實驗仿真結果表明，該算法相比其他幾種算法，具有識別效率高、數據交換量小等優勢。

射頻識別；防碰撞；二進制搜索法；融合算法

1 引言

射頻識別技術是一種非接觸式的自動識別技術，它通過系統發射的射頻信號來對目標標簽進行識別并獲取標簽的相關數據信息。該系統因其可以高效準確地進行大量物品的識別讀取，已廣泛被應用在交通、物品流通的供應鏈管理等領域[1, 2]。典型的射頻識別系統主要由3部分組成：標簽、讀寫器和天線。作為物品信息載體的標簽貼于待識別的物品上，在進行物品信息的識別過程中，若存在兩個及以上標簽同時出現時，即會出現信號間的相互干擾，影響系統對標簽群的識別效率。因此，在待識別標簽密集度高的射頻系統中，需采用一種有效的多標簽識別的防碰撞算法。

標簽與讀寫器信號交互中主要有3種形式的碰撞，分別為標簽碰撞、讀寫器間的干擾、標簽干擾。其中，讀寫器間干擾和標簽干擾類似于移動蜂窩網頻率分配問題，可通過讀寫器間建立的工作協調機制以解決沖突問題。標簽碰撞問題，則應根據RFID識別系統自身特點，選擇不同的方法來解決。

RFID系統多標簽防碰撞算法的主要任務是確保讀寫器正確識別在有效通信覆蓋范圍內的多個目標標簽。根據所采用的無線通信多址接入方式，算法可分為時分多路類、碼分多路類、空分多路類和頻分多路[7]4種。因系統受到成本和資源等方面的要求，時分多路法技術在識別系統的多標簽防碰撞算法中應用最為廣泛。

時分多路防碰撞算法中的ALOHA算法易于實現，成本低廉，但是由于算法的時隙是隨機分配，因此可能造成某些標簽長時間無法識別，亦即存在標簽饑餓問題。在幀時隙ALOHA防碰撞算法(FSA)應用中，當標簽識別量變得很大時，系統的算法執行時間就會很長，標簽的讀取效率下降。幀時隙ALOHA算法由于幀時長是固定的，所以，不能實現長度的實時調節，以自適應標簽數量的變化。而動態幀時隙ALOHA算法(DFSA)需要在系統的識別過程中不斷估算標簽數量，以便于與時隙數相匹配。但由于硬件條件限制，幀長度并非是可以無限制的增加，限制標簽群中標簽數量的變化。所以，幀時隙ALOHA算法僅限于每幀中時隙數最大為256的系統中使用。當標簽群中的標簽數遠大于256時，該算法將無法通過時隙數的增大來提高數據的吞吐率。

基于樹的分組算法是確定型算法，根據分組規則的不同，基于樹的分組算法又進一步分為二進制樹搜索算法(Binary Tree protocol, BT) 和查詢樹算法(Query Tree protocol, QT)。二進制樹搜索算法按照遞歸工作方式，標簽若發生碰撞時即可將具有碰撞位的標簽分成兩個子集，并將此位置“0”，以此方式進行，重復上述過程，繼續子集分配，直至標簽讀取無碰撞發生為止。子集生成算法包括基本的二進制樹搜索算法和時隙二進制樹算法( slotted binary search)，前者根據碰撞位具體值確定，若該位為“0”則標簽在下次詢問中響應，否則標簽靜默；后者則采用隨機分組方式，此類標簽內部有隨機數生成器，當多標簽沖突時，碰撞標簽自身產生一個隨機數“0”或“1”，根據產生隨機數值的不同，標簽被分為兩組；下次詢問命令發出后，數值為“0”的標簽發送信號，若有沖突，繼續分組，以此方式重復進行，直至標簽信息讀取時無碰撞發生為止，隨機數為“0”的標簽信息被讀取之后進行數值為“1”的標簽響應。查詢樹(QT)算法是確定性的標簽防碰撞算法。應用此類算法的標簽無需特殊存儲器，系統只需記錄標簽自身UID編號即可。標簽讀取時，系統先發送一個標簽信息查詢前綴，若查詢前綴與標簽信息的前綴相同，標簽即響應此次查詢。對于單標簽來說，二者信息相同后標簽將自身的UID編號反饋給讀寫器，讀寫器成功接收到標簽UID后即表示該標簽被成功識別；對于多標簽來說，若多個標簽響應并發生沖突時，再下一個循環的標簽查詢時，讀寫器將會把查詢信息的前綴后面增加一個“0”或“1”，以此方法重復進行，標簽群的識別過程中，系統通過不斷的修改查詢指令前綴編碼信息，使其能識別在讀寫區域內出現的所有標簽。基本的BT算法和QT算法都存在空閑時隙，降低了系統效率[16]。另外，此類算法系統可實現的必要前提是能辨認出在系統識別時發生數據碰撞的比特的準確位置，并有合適的位編碼法。

讀寫器在多標簽讀取時所應用的防碰撞算法，由于存在最大吞吐率等問題及不足，因此，為了提高系統識別吞吐率，就必須考慮幀長度，這勢必影響到標簽讀取的剩余率判斷問題，及標簽識別效率問題。另外，為提高判斷的準確度和識別效率，這些方法也會增大算法負荷等，從而可能會增加系統成本[17]。因此從實際角度考慮，針對目前所采用算法存在的缺陷，本文提出了一種融合防碰撞算法。

2 算法描述

標簽識別中，如果沒有標簽碰撞問題，則正常識別標簽并讀取標簽信息；如果出現標簽碰撞，則根據碰撞標簽的數量進行分組處理，根據產生的隨機數將標簽群分成適當的組后，再對每個標簽組中的標簽進行碰撞算法來進行一一識別。重復上述步驟，直至標簽內部數據被完全讀取。

(1)標簽群分組：讀寫器發送分組指令，標簽群中的標簽均產生一個自身的隨機數，隨機數保存在與標簽相對應的存儲器中，產生隨機數相等的標簽被分為同一個組，并對該組標簽根據隨機數進行組命名。通過該分組方法將碰撞標簽分裂成多個組，使得每組內碰撞標簽數量顯著減少，以降低標簽間的碰撞率。假設共有個標簽，將之分為組，即標簽產生的隨機數范圍為(1,)。在標簽識別中，任意一組標簽被識別時，由于不同時刻每個標簽所產生在該數據范圍內的隨機數概率是相同的，在同一時刻內，分組中的每個標簽都隨機產生一個(1,)范圍之間的隨機數，搜索到個標簽的二項分布的概率為

經推導可知，讀寫器在一個讀標簽周期內預期讀到的標簽數量為

(2)

隨機數，在個未被讀取標簽群中，讀取到個標簽的效率為

通過式(3)計算系統最大效率時標簽的數量為

(4)

(2)組內防碰撞識別：根據系統協議標準要求，識別系統通常采用二進制搜索樹方法來解決標簽讀取的碰撞問題，且滿足該協議標準的標簽內部均自帶防碰撞機制。在已分組的標簽內部，如果沒有標簽碰撞，則直接識別讀取標簽信息；如果仍存在標簽碰撞問題，則進行組內部的防碰撞識別工作，讀寫器發出指令并接收到標簽返回的信息，讀寫器模塊將根據接收到的該組中碰撞標簽的編碼形式，在該碰撞編碼位上的編碼均為“1”，標簽被激活后都返回數據給讀寫器，如讀寫器讀取各個標簽的數據后對比判斷若有標簽碰撞位數，則把該位置“0”。標簽在接收到該組數據信息后立即響應，并將(-1)~1位數據回傳給讀寫器。讀寫器和標簽以碰撞發生的編碼位為界分別將前后數據進行傳送，以此方式進行一一篩選讀取工作。讀取完該組后，則進行其他組的標簽讀取工作。重復上述步驟，直至標簽內部數據被完全讀取。

碰撞算法執行后，首先返回失敗命令，讀寫器接收響應并判斷，有如下幾種情況：設讀寫器模塊能正確接收標簽數據信息，如果仍產生UID編碼碰撞沖突，則繼續發送失敗命令；標簽UID編碼信息被正確接收到，則利用讀取命令讀取標簽存儲信息準確后，發送成功讀取命令，繼續識別余下的標簽UID；如果沒有標簽響應，則發送成功命令，被識別成功讀取信息后的標簽，不在參加沖突仲裁。依據算法原理，首先將標簽隨機產生(1,)之間的隨機數，任何一個隨機數都滿足二項式分布要求。所有標簽分組均搜索次數：

(6)

根據式(7)可知，若標簽數量多，則查詢時間比較長，為了提高搜索效率和減小碰撞率，采用UID編碼分區搜索和碰撞沖突識別相結合的方法以提高讀寫器有效區域內標簽防碰撞的識別效率，來實現讀寫器模塊對多個目標標簽的讀取操作。因此該搜索算法，具有識別率準確度高、吞吐率大、穩定性好、讀取所用時隙更少的特點。融合算法流程如圖1所示。

圖1 防碰撞算法流程圖

3 算法仿真分析

利用Matlab 仿真平臺，對本文提出的RFID系統標簽融合防碰撞算法，在理想信道下進行仿真實驗，設定標簽仿真數量最大為1000，標簽長度為64 bit，程序仿真50次取仿真結果的平均值，將融合后的防碰撞算法仿真結果與其他算法進行比較，不同算法的標簽識別效率比較如圖2所示。從圖可看出，本文的融合防碰撞算法，相對于其他3種方法具有較高標簽的識別效率，幾種算法的標簽識別效率基本保持穩定，不隨標簽量的增加而有所變動。

不同算法的標簽查詢次數仿真結果比較如圖3所示，幾種不同的算法在標簽量逐步增加時，查詢次數基本與標簽量成正比，從結果可看出本文融合后的算法標簽查詢次數最少。進一步提高標簽查詢效率為該算法的進一步優化的關鍵點。

4 結束語

本文提出了一種基于分組式和融合后的二進制算法相融合來實現標簽讀取的防碰撞算法，實驗結果可看出，標簽識別效率高，識別過程中數據通訊量顯著減小。但在實驗過程中也發現如果標簽量更大的時候，標簽查詢時間仍不夠理想，因此在進一步的工作中，將主要針對標簽量大的時候的標簽識別讀取時進一步融合改進。

圖2 不同算法的標簽識別效率比較 圖3 不同算法的查詢次數比較

[1] ZUO Y. Survivable RFID systems: issues, challenges and techniques[J].,-:, 2010, 40(4): 406-418. doi: 10.1109/TSMCC.2010.2043949.

[2] 宋建華, 郭亞軍, 韓蘭勝, 等. 自調整混合樹RFID多標簽防碰撞算法[J]. 電子學報, 2014, 42(4): 685-695. doi: 10.3969/ j.issn. 0372-2112.2014.04.010.

SONG Jianhua, GUO Yajun, HAN Lansheng,An adjustive hybrid tree-conllision algorithm for RFID multi-tag identification[J]., 2014, 42(4): 685-695. doi: 10.3969/j.issn.0372-2112.2014.04.010.

[3] 王云峰, 張斌, 劉洋, 等. 基于碼分多址防碰撞的射頻識別認證協議[J]. 電子與信息學報, 2014, 36(6): 1472-1477. doi: 10.3724/ SP.J. 1146.2013.01337.

WANG Yunfeng, ZHANG Bin, LIU Yang,Radio frequency identification authentication protocol based on CDMA anti-collision algorithm[J].&, 2014, 36(6): 1472-1477. doi: 10.3724 /SP.J.1146.201301337.

[4] 李志堅, 賴順橋. 一種基于碰撞位指示的射頻識別標簽防碰撞算法[J]. 電子與信息學報, 2014, 36(12): 2842-2847. doi: 10.3724/P.J.1146. 2013.01759.

LI Zhijian and LAI Shunqiao. An anti-collision algorithm based on collided bits indicator in radio frequency identification systems[J].&, 2014, 36(12): 2842-2847. doi: 10.3724/SP.J.1146.2013.01759.

[5] 李青青, 劉洪武, 張小林. 一種基于不等長時隙的射頻識別防碰撞算法[J]. 電子與信息學報, 2011, 33(11): 2628-2633. doi: 10.3724/SP.J.1146.2011.00303.

LI Qingqing, LIU Hongwu, and ZHANG Xiaolin. An anti- collision algorithm based on unequal timeslots in radio frequency identification system[J].&, 2011, 33(11): 2628-2633. doi: 10.3724/SP.J.1146.2011.00303.

[6] SHAO Min, JIN Xiaofang, and JIN Libiao. An improved dynamic adaptive multi-tree search anti-collision algorithm based on RFID[C]. International Conference on Data Science and Advanced Analytics (DSAA), Shanghai, China, 2014: 72-75.

[7] 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, Japan, 2012: 581-584.

[8] JIANG Chenyi, XU Yinfei, 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.

[9] WANG Shuai, HONG Weijun, and LI Shufang. 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. doi: 10.1109/ WiCOM.2012.6478372.

[10] 李萌, 錢志鴻, 張旭, 等. 基于時隙預測的RFID防碰撞ALOHA算法[J]. 通信學報, 2011, 32(12): 43-50.

LI Meng, QIAN Zhihong, ZHANG Xu.Slot-predicting based ALOHA algorithm for RFID anti-collision[J]., 2011, 32(12): 43-50.

[11] Landaluce H, Perallos A, and Zuazola I J G. A fast RFID identification protocol with low tag complexity[J]., 2013, 17(9): 1704-1706. doi: 10.1109/LCOMM.2013.070913.131111.

[12] WU Haifeng, ZENG Yu, FENG Jihua,Binary tree slotted ALOHA for passive RFID tag anti-collision[J]., 2013, 24(1): 19-31. doi: 10.1109/TPDS.2012.120.

[13] 張學軍, 王娟, 王鎖萍. 基于標簽識別碼分組的連續識別防碰撞算法研究[J]. 電子與信息學報, 2011, 33(5): 1159-1165. doi: 10.3724/SP.J.1146.2010.00940.

ZHANG Xuejun, WANG Juan, and WANG Suoping. A uninterrupted anti-collision algorithm with ID-based grouping for RFID system[J].&, 2011, 33(5): 1159-1165. doi: 10.3724 /SP.J.1146.2010.00940.

[14] XUE Jianbin, WANG Wenhua, LI Songbai,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.

[15] YANG Yongkang, CUI Chunsheng, ZHOU Tuanfeng,Improvement on RFID-based binary anti-collision algorithm [C]. 2012 International Conference on Computer Science and Service System, Nanjing, China, 2012: 515-518.

[16] Vogt H. Efficint object identification with passive RFID tags[C]. Proceeding of International Conference on pervasive Ccmputing. Berlin: Springer-Verlag, 2002: 98-113. doi: 10.1007/3-540-45866-2_9.

[17] 蘇健, 韓雨, 駱忠強, 等. 超高頻RFID系統中一種可行的時間最優防碰撞算法[J]. 電子學報, 2015, 43(8): 1651-1655. doi: 10.3969/j.issn.0372-2112.2015.08.027.

SU Jian, HAN Yu, LUO Zhongqiang,A fessible time-optimal anti-collision algorithm for UHF RFID systems[J]., 2015, 43(8): 1651-1655. doi: 10.3969/j.issn.0372-2112.2015.08.027.

郭振軍： 男，1977年生，講師，博士生，研究方向為無線射頻識別及相關技術.

孫應飛： 男，1964年生，教授，博士生導師，主要研究方向為機器學習與模式識別的理論、方法與應用，生物信息處理、基因調控網絡，信息融合，信息安全.

Anti-collision Algorithm of RFID System Based on Grouped Tag

GUO Zhenjun①②SUN Yingfei①

①(,100049,)②(,541004,)

Anti-collision algorithm is a key technique to improveidentification efficiency in Radio Frequency IDentification (RFID) system. For this problem of the efficient identification and the large amount of data transmission, a group-based anti-collision algorithm is proposed. With the improved binary tree search algorithm combining, the tags in each group are identified by reader in turn, which can reduce the amount of data communication effectively. The simulation results show that, compared with several other algorithms, the proposed algorithm has the advantage of efficient identification and a small amount of data exchange.

Radio Frequency IDentification (RFID); Anti-collision; Binary search; Fusion algorithm

TP391.45

A

1009-5896(2017)01-0250-05

10.11999/JEIT160186

2016-03-01；改回日期：2016-07-25；

2016-10-09

郭振軍 zjguo666@126.com