基于標(biāo)簽分組的RFID系統(tǒng)防碰撞算法

郭振軍 孫應(yīng)飛

?

基于標(biāo)簽分組的RFID系統(tǒng)防碰撞算法

郭振軍*①②孫應(yīng)飛①

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

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

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

1 引言

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

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

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

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

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

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

2 算法描述

標(biāo)簽識別中，如果沒有標(biāo)簽碰撞問題，則正常識別標(biāo)簽并讀取標(biāo)簽信息；如果出現(xiàn)標(biāo)簽碰撞，則根據(jù)碰撞標(biāo)簽的數(shù)量進行分組處理，根據(jù)產(chǎn)生的隨機數(shù)將標(biāo)簽群分成適當(dāng)?shù)慕M后，再對每個標(biāo)簽組中的標(biāo)簽進行碰撞算法來進行一一識別。重復(fù)上述步驟，直至標(biāo)簽內(nèi)部數(shù)據(jù)被完全讀取。

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

經(jīng)推導(dǎo)可知，讀寫器在一個讀標(biāo)簽周期內(nèi)預(yù)期讀到的標(biāo)簽數(shù)量為

(2)

隨機數(shù)，在個未被讀取標(biāo)簽群中，讀取到個標(biāo)簽的效率為

通過式(3)計算系統(tǒng)最大效率時標(biāo)簽的數(shù)量為

(4)

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

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

(6)

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

圖1 防碰撞算法流程圖

3 算法仿真分析

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

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

4 結(jié)束語

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

圖2 不同算法的標(biāo)簽識別效率比較 圖3 不同算法的查詢次數(shù)比較

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

[2] 宋建華, 郭亞軍, 韓蘭勝, 等. 自調(diào)整混合樹RFID多標(biāo)簽防碰撞算法[J]. 電子學(xué)報, 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] 王云峰, 張斌, 劉洋, 等. 基于碼分多址防碰撞的射頻識別認證協(xié)議[J]. 電子與信息學(xué)報, 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] 李志堅, 賴順橋. 一種基于碰撞位指示的射頻識別標(biāo)簽防碰撞算法[J]. 電子與信息學(xué)報, 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]. 電子與信息學(xué)報, 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] 李萌, 錢志鴻, 張旭, 等. 基于時隙預(yù)測的RFID防碰撞ALOHA算法[J]. 通信學(xué)報, 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] 張學(xué)軍, 王娟, 王鎖萍. 基于標(biāo)簽識別碼分組的連續(xù)識別防碰撞算法研究[J]. 電子與信息學(xué)報, 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系統(tǒng)中一種可行的時間最優(yōu)防碰撞算法[J]. 電子學(xué)報, 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年生，講師，博士生，研究方向為無線射頻識別及相關(guān)技術(shù).

孫應(yīng)飛： 男，1964年生，教授，博士生導(dǎo)師，主要研究方向為機器學(xué)習(xí)與模式識別的理論、方法與應(yīng)用，生物信息處理、基因調(diào)控網(wǎng)絡(luò)，信息融合，信息安全.

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