李志堅賴順橋
?
一種基于碰撞位指示的射頻識別標(biāo)簽防碰撞算法
李志堅*①②賴順橋②
①(華南理工大學(xué)電子與信息學(xué)院 廣州 510640)②(廣州市光機電技術(shù)研究院 廣州 510663)
多標(biāo)簽碰撞是射頻識別(RFID)技術(shù)在推廣應(yīng)用中必須克服的一個問題。針對目前RFID標(biāo)簽防碰撞算法存在識別效率低的不足,該文提出一種基于碰撞位指示的RFID標(biāo)簽防碰撞的碰撞位指示算法(CBIA)。通過跟蹤待識別標(biāo)簽的碰撞位,采用碰撞位編解碼技術(shù),對待識別標(biāo)簽進行重復(fù)分組,直到所有標(biāo)簽都被正確識別。算法通過確定性分組,避免了空閑時隙的產(chǎn)生。仿真結(jié)果表明,采用CBIA算法的多標(biāo)簽識別系統(tǒng),吞吐率可以達到每時隙0.7個標(biāo)簽,CBIA算法識別效率優(yōu)于優(yōu)化查詢跟蹤樹算法(OQTT)和碰撞跟蹤樹算法(CTTA)算法。
射頻識別;防碰撞算法;位跟蹤技術(shù);吞吐率
射頻識別(Radio Frequency IDentification, RFID)是上世紀(jì)90年代興起的一種非接觸式自動識別技術(shù)。近年來,隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展,RFID被廣泛應(yīng)用于軍事、供應(yīng)鏈、衛(wèi)生保健和公共管理等領(lǐng)域[1,2]。由于RFID系統(tǒng)標(biāo)簽和讀寫器共用一個無線頻道,當(dāng)多讀寫器和多標(biāo)簽同時占用頻道通信時,信號相互干擾,發(fā)生了碰撞。
ALOHA算法易于實現(xiàn),成本低廉,但是由于算法的時隙是隨機分配,因此可能造成某些標(biāo)簽長時間無法識別,亦即存在標(biāo)簽饑餓(tag starvation)問題。
基于樹的分組算法是確定型算法,算法依據(jù)確定的分組規(guī)則,對活動標(biāo)簽反復(fù)分組,直到每個組內(nèi)只含一個標(biāo)簽或者不含標(biāo)簽,從而識別所有標(biāo)簽。根據(jù)分組規(guī)則的不同,基于樹的分組算法又進一步分為二進制樹搜索算法(Binary Tree protocol, BT)和查詢樹算法(Query Tree protocol, QT)?;镜腂T算法和QT算法都存在空閑時隙,降低了系統(tǒng)效率。
采用碰撞位跟蹤技術(shù)可以提高基于樹的分組算法的系統(tǒng)效率。增強防碰撞算法(Enhanced Anti-collision Algorithm, EAA)和碰撞跟蹤樹算法(Collision Tracking Tree Algorithm, CTTA)[11,12]分別是對基本的BT算法和QT算法,都采用了碰撞位跟蹤技術(shù)。這兩種算法都檢測最高碰撞位,之后按照最高碰撞位分別為‘0’和‘1’把碰撞標(biāo)簽分成兩組,從而避免了空閑時隙的產(chǎn)生,提高了系統(tǒng)效率。
但是,當(dāng)活動標(biāo)簽數(shù)量很大時,EAA算法和CTTA算法都存在大量的碰撞時隙。減少碰撞時隙可以進一步提高系統(tǒng)效率。文獻[8]提出的優(yōu)化查詢跟蹤樹算法(Optimal Query Tracking Tree, OQTT)算法。該算法在識別開始時,先通過碰撞位置估計標(biāo)簽數(shù)量,之后依據(jù)最優(yōu)分組規(guī)則把待識別標(biāo)簽分成若干組,每一組都采用CTTA算法進行識別。OQTT減少了識別最初的碰撞時隙數(shù)量,提高了識別效率。
OQTT算法只在查詢樹首層增加了分支,而在每個子查詢樹里面仍采用CTTA算法。因此,在標(biāo)簽數(shù)量很大的時候,識別初期的碰撞時隙還是比較多。進一步減少碰撞時隙,可以進一步提高系統(tǒng)效率。
本文正是基于進一步減少碰撞時隙的思想,提出一種基于碰撞位指示的RFID多標(biāo)簽防碰撞算法(Collided Bits Indicator Algorithm, CBIA)。CBIA通過跟蹤待識別標(biāo)簽的碰撞位,采用碰撞位編解碼技術(shù),對待識別標(biāo)簽進行重復(fù)分組,直到所有標(biāo)簽都被正確識別。算法的創(chuàng)新點在于增加了查詢樹每一層的分枝數(shù)量,同時避免空閑時隙的產(chǎn)生,進一步壓縮了查詢樹的層數(shù),減少了碰撞時隙的數(shù)量,提高了系統(tǒng)效率。本文通過數(shù)學(xué)分析,給出了CBIA算法的占用時隙的估計模型,并在此技術(shù)上得出了系統(tǒng)吞吐率估計。仿真結(jié)果表明,相對于現(xiàn)有查詢樹算法CTTA和OQTT算法,CBIA具有更快的識別速率和更高的吞吐率。
(1)標(biāo)簽ID采用曼徹斯特編碼[13],長度為,讀寫器能夠正確識別非碰撞位和碰撞位。讀寫器中設(shè)置一個查詢前綴堆棧S和兩個寄存器碰撞位模板(Collided Bits Mask, CBM)和識別位模板(Recognized Bits Mask, RBM),分別用于記錄碰撞位和已識別位數(shù)據(jù)。
(2)標(biāo)簽中設(shè)置一個2位的碰撞位指示(CBI) 寄存器。當(dāng)接收讀寫器廣播的CBM時,標(biāo)簽順序取出ID中的高位碰撞位,形成一個二進制數(shù),這個二進制數(shù)成為碰撞位編碼CBC(Collided Bits Code),然后根據(jù)CBC把CBI的第CBC位置‘1’,其他位置‘0’。
(3)標(biāo)簽中設(shè)置一個狀態(tài)寄存器SF,標(biāo)簽根據(jù)SF的值在不同的時候響應(yīng)讀寫器命令。
(1)Act (0)命令:讀寫器廣播這個命令,有效通信范圍內(nèi)所有標(biāo)簽回送各自ID給讀寫器同時把狀態(tài)標(biāo)志位SF置‘1’。
(2)Req (opt):查詢命令。其中參數(shù)‘’是一個長度為()的二進制數(shù),可以是查詢前綴序列或者CBM,由參數(shù)opt區(qū)分。參數(shù)opt為‘0’時,‘’是一個查詢前綴序列。若標(biāo)簽ID的高()位與‘’一致,則標(biāo)簽回送剩下的-()位給讀寫器并把狀態(tài)標(biāo)志位SF置‘1’。參數(shù)opt為‘1’時,‘’是一個CBM。狀態(tài)標(biāo)志位SF為‘1’的標(biāo)簽回送CBI給讀寫器并把SF清零。
CBIA算法的流程圖如圖1所示,其主要步驟如下:
步驟1 讀寫器初始化,清空堆棧S,清零CBM和RBM。廣播Act (0)命令。識別范圍內(nèi)所有標(biāo)簽回送ID并置位SF;
步驟2 讀寫器檢測碰撞位,設(shè)置CBM和RBM。如果沒有檢測到碰撞,讀寫器識別一個標(biāo)簽;若只存在一個碰撞位,則讀寫器識別兩個標(biāo)簽。如果存在多個碰撞位,讀寫器跟蹤所有碰撞發(fā)生的位置,并把CBM對應(yīng)位置‘1’。讀寫器識別所有未碰撞位,把RBM對應(yīng)位置上置位已識別數(shù)碼;
步驟3 讀寫器發(fā)送命令Req(CBM,1)。有效識別范圍內(nèi),SF為‘1’的標(biāo)簽回送CBI并把SF置‘0’;
步驟..4 讀寫器接收CBI,并跟蹤所有碰撞位位置,然后根據(jù)碰撞位位置譯碼得到CBC。例如,若讀寫器接收到8位CBI為“000x0xx0”,x表示該位發(fā)生碰撞。則表示碰撞發(fā)生在第1,第2和第4位,那么讀寫器可以譯碼出3個CBC,分別是“001”,“010”,“100”;
圖1 CBIA流程圖
步驟6 若S不空,則讀寫器從S中取出一個查詢前綴序列,并廣播Req(prefix,0)命令。有效識別范圍內(nèi),ID高位與前綴一致的標(biāo)簽回送剩余ID,并把SF置‘1’。算法跳轉(zhuǎn)到步驟2;
步驟7 若S讀空,則所有標(biāo)簽都被識別,識別過程結(jié)束。
圖2給出了一個利用CBIA算法識別7個標(biāo)簽TagA~TagG的示例。圖中x表示該位發(fā)生碰撞。CBC長度為4。在第1個時隙,讀寫器廣播啟動命令,所有標(biāo)簽都響應(yīng)讀寫器命令。在第2個時隙,讀寫器廣播CBM“111111111111011”。SF為‘1’的標(biāo)簽回送CBI,并置 SF 為‘0’。在本示例中,標(biāo)簽A, B, F和G 的CBI相同,均為“000001000000000”,對應(yīng)CBC為“1010”;標(biāo)簽C的CBC是“0101”回送CBI “0000000000100000”;標(biāo)簽D 的CBC是“0001”回送CBI“00 00000000000010”;標(biāo)簽E 的CBC是“0111”回送CBI“0000000010000000”。讀寫器接收端接收到的CBI為“00000x00x0x000x0”。這樣讀寫器可以根據(jù)碰撞位發(fā)生位置計算所有的CBC,分別是“1010”,“0111”,“0101”,“0001”。然后讀寫器就可以生產(chǎn)4個查詢前綴序列“1010”,“0111”,“0101”,“0001”,并壓棧。在第3個時隙,讀寫器取出一個查詢前綴序列“0001”,并廣播查詢命令。標(biāo)簽D高4位與這個前綴一致,所以它回送剩余ID位,這樣標(biāo)簽D成功識別。同樣標(biāo)簽 C和 E 分別在第4個和第5個時隙被識別。第6個時隙,讀寫器廣播查詢前綴“1010”,標(biāo)簽A, B, F 和G 同時回送剩余ID位并置各自SF為‘1’。讀寫器接收CBI“0x0xx0x0”。此時碰撞位位數(shù)為4,那么這4個標(biāo)簽可以在下個時隙一次識別。在第7時隙,讀寫器廣播CBM “000001011010”,標(biāo)簽A, B, F和G回送CBI。讀寫器接收CBI“00x00x0000x 0x000”經(jīng)譯碼得CBCs:“1101”,“0101”,“1010”,“0011”,然后把CBC嵌入到RBM中可識別這4個標(biāo)簽。此時,S為空,識別過程結(jié)束,所有標(biāo)簽都被識別。
算法性能可以通過估計識別個標(biāo)簽所需要的時隙樹和估算系統(tǒng)吞吐量進行衡量。
在數(shù)學(xué)分析之前,有必要區(qū)分CBIA算法的兩種碰撞:
可識別碰撞:讀寫器在接收標(biāo)簽回送ID數(shù)據(jù)時,如果檢測出碰撞位數(shù)不大于CBC位數(shù),則碰撞的多個標(biāo)簽可通過譯碼CBC全部識別。
不可識別碰撞:讀寫器在接收標(biāo)簽回送ID數(shù)據(jù)時,如果檢測出碰撞位數(shù)大于CBC位數(shù),則碰撞的多個標(biāo)簽不可在一次譯碼中識別,這種碰撞為不可識別碰撞。
圖2 CBIA示例
由于每個數(shù)位等概率取得‘0’和‘1’。所以=1/2。當(dāng)個標(biāo)簽ID的同一位上均為‘0’或者‘1’時,該位不會發(fā)生碰撞。這樣個標(biāo)簽?zāi)澄徊话l(fā)生碰撞的概率為
(2)
相應(yīng)地,該位發(fā)生碰撞的概率為
在一棵完整的CBIA查詢樹中,每個父節(jié)點可以產(chǎn)生2個子節(jié)點,第層有2子節(jié)點。每個子節(jié)點對應(yīng)一個查詢前綴序列。個標(biāo)簽ID中具有相同前綴的標(biāo)簽ID數(shù)量服從二項分布
同樣,由于標(biāo)簽ID是均勻分布,因此標(biāo)簽前綴等概率出現(xiàn),從而有
當(dāng)只有一個標(biāo)簽具有某一前綴時,該標(biāo)簽可以直接識別。由式(4),單標(biāo)簽被識別的概率為
當(dāng)多個標(biāo)簽具有相同前綴,但回送數(shù)據(jù)僅有一個碰撞位時,說明當(dāng)前只有兩個標(biāo)簽響應(yīng)讀寫器查詢命令,這樣兩個標(biāo)簽可以一次識別。識別概率為
當(dāng)多個標(biāo)簽具有相同前綴,但回送數(shù)據(jù)碰撞位數(shù)n不大于時,通過下一個時隙CBC譯碼,這些標(biāo)簽都可以識別出來,這種情況發(fā)生的概率為
如果用P表示CBIA查詢樹上第層的第個節(jié)點被訪問的概率。顯然當(dāng)0,00/N1,也就是CBIA的根節(jié)點總是被訪問到。
進而有
這樣,CBIA算法訪問節(jié)點的數(shù)學(xué)期望為
綜上,有CBIA識別個標(biāo)簽的時隙樹為
進而可得系統(tǒng)的吞吐率為
需要說明的是,在實際識別過程中,CBIA查詢樹的層數(shù)不可能無窮大,它與系統(tǒng)設(shè)置的標(biāo)簽CBC位數(shù)有關(guān)。
仿真結(jié)果表明:相比于CTTA, OQTT算法,CBIA算法平均識別時隙數(shù)優(yōu)勢明顯,且隨著待識別標(biāo)簽數(shù)據(jù)的增大,算法性能優(yōu)勢越明顯。在系統(tǒng)吞吐率方面,CBIA算法性能優(yōu)于其他兩種算法,平均每個時隙可識別0.7個標(biāo)簽,優(yōu)于OQTT算法的吞吐率僅為0.6和CTTA的0.5。
圖4反應(yīng)了CBC位數(shù)和標(biāo)簽ID位數(shù)對CBIA算法性能的影響。圖4(a)中,標(biāo)簽ID位數(shù)固定為64位,標(biāo)簽CBC位數(shù)分別為2,4,6,8,10位。圖4(b)中,標(biāo)簽數(shù)量固定為1000個,標(biāo)簽ID位數(shù)分別為32,48,64,96和128位。仿真結(jié)果表明,當(dāng)CBC位數(shù)為6時,識別相同數(shù)量的標(biāo)簽所用時隙最少。
本節(jié)主要分析CBIA算法與CTTA, OQTT的對比優(yōu)勢,并分析CBIA獲取這些優(yōu)勢所付出的硬件成本。
CTTA, OQTT和CBIA都是查詢樹算法QT的改進,其核心思想是不斷地對待識別標(biāo)簽進行分組,直到組內(nèi)標(biāo)簽可以一次識別。這幾種算法性能差異,是由各自采取的分組協(xié)議引起的。
CTTA每次只處理一個碰撞位。每次檢測到碰撞位,CTTA自動把待識別標(biāo)簽分成碰撞位為‘0’和‘1’的兩組,直到組內(nèi)僅含一個標(biāo)簽或者僅含有兩個只有一個沖突位的標(biāo)簽,識別這些標(biāo)簽。CTTA采用確定性分組,避免了空閑時隙的產(chǎn)生。然而,CTTA每次只把組內(nèi)待識別標(biāo)簽劃分成兩個小組。這樣,在標(biāo)簽數(shù)量較大時,CTTA搜索深度會很深。而且,在識別初期,每一組內(nèi)待識別標(biāo)簽數(shù)量很大,碰撞概率很高,在標(biāo)簽數(shù)量較大時,碰撞時隙數(shù)量非常可觀,識別效率不高。
OQTT對QT算法的改進僅在于識別最初的最優(yōu)化分組,而在之后的各組內(nèi)識別過程仍舊采用CTTA算法。盡管采用了碰撞位跟蹤技術(shù),但每次也僅處理一個碰撞位。這一方面,CTTA算法的不足,在OQTT算法中仍然存在。另一方面,OQTT的最優(yōu)化分組是隨機分組。當(dāng)標(biāo)簽ID不服從均勻分布時,OQTT的最初分組會不平衡[8],從而使得某些組內(nèi)待識別標(biāo)簽非常多,而某些組內(nèi)待識別標(biāo)簽很少,甚至沒有。其結(jié)果是OQTT算法性能下降。
圖3 算法性能比較
圖4 CBC位數(shù)和ID位數(shù)對CBIA性能影響仿真
CBIA算法與OQQT算法比較,其最大特點是確定性分組。與OQTT的隨機分組不同,CBIA算法在最初分組時采用確定性分組,每個小組內(nèi)都有待識別標(biāo)簽,不會出現(xiàn)無標(biāo)簽的小組。因此,CBIA可以避免OQTT算法在最初分組時的空閑時隙的產(chǎn)生。而之后的識別過程,OQTT組內(nèi)采用CTTA算法,這樣,CBIA算法對CTTA算法的優(yōu)勢也同樣體現(xiàn)在對OQTT算法的比較中。
CTTA是采用了位跟蹤技術(shù)的QT算法。QT算法是一種無記憶防碰撞協(xié)議,標(biāo)簽在識別過程中不需要存儲任何數(shù)據(jù),每次回送剩余標(biāo)簽ID。因此,CTTA算法標(biāo)簽中無存儲資源,硬件成本低廉。
OQTT是對CTTA算法的改進,繼承了CTTA算法的無記憶的特點。但是,OQTT算法在最初的進行標(biāo)簽數(shù)量估計時,需要標(biāo)簽根據(jù)協(xié)議產(chǎn)生一個log2位的隨機數(shù),并根據(jù)這個隨機數(shù)對一個位的二進制數(shù)(其中是標(biāo)簽ID的位數(shù))進行位調(diào)制[8]。因此,OQTT算法在硬件開銷方面,將增加隨機數(shù)生成模塊和位調(diào)制模塊。
CBIA算法也是CTTA算法的改進。根據(jù)協(xié)議需要,標(biāo)簽接收讀寫器廣播的CBM,并根據(jù)CBM的非零位位置和標(biāo)簽ID的對應(yīng)位產(chǎn)生一個二進制數(shù),并用這個二進制數(shù)對2位CBI進行位調(diào)制。因此,CBIA算法與OQTT類似,都增加了二進制數(shù)生成和位調(diào)制的硬件開銷。但是,由于CBC位數(shù)小于log2, CBI位數(shù)小于,因此,與OQTT比較,CBIA算法所消耗的硬件資源更少??紤]到標(biāo)簽需把調(diào)制后的二進制數(shù)回送讀卡器,OQTT算法回送一個位的二進制數(shù),而CBIA算法僅回送一個2位的CBI,因此,CBIA比OQTT的通信數(shù)據(jù)量更少。
本文提出了一種新穎的RFID多標(biāo)簽防碰撞算法,CBIA。該算法利用碰撞位跟蹤技術(shù),對待識別標(biāo)簽進行重復(fù)分組,直到所有標(biāo)簽都被正確識別。算法增加了查詢樹的每一層分叉數(shù)目,同時避免了空閑時隙的產(chǎn)生,壓縮了查詢樹的層數(shù),減少了碰撞時隙的數(shù)量。仿真結(jié)果表明,采用CBIA算法的多標(biāo)簽識別系統(tǒng),吞吐率可以達到每時隙0.7個標(biāo)簽,CBIA算法識別效率優(yōu)于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年生,講師,研究方向為物聯(lián)網(wǎng)RFID關(guān)鍵技術(shù)與應(yīng)用、雷達信號處理.
賴順橋: 男,1981年生,工程師,研究方向為物聯(lián)網(wǎng)RFID關(guān)鍵技術(shù)與應(yīng)用.
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)和中央高校基本科研業(yè)務(wù)費自主項目(2009ZM0097)資助課題