李志堅,肖熠琳

(1.華南理工大學(xué)電子與信息學(xué)院,廣州510640;2.廣州市光機電技術(shù)研究院,廣州510663; 3.廣東省現(xiàn)代控制與光機電技術(shù)公共實驗室,廣州510663)

一種基于二進制碼調(diào)制的射頻識別防碰撞算法

李志堅1,3,肖熠琳2

(1.華南理工大學(xué)電子與信息學(xué)院,廣州510640;2.廣州市光機電技術(shù)研究院,廣州510663; 3.廣東省現(xiàn)代控制與光機電技術(shù)公共實驗室,廣州510663)

針對射頻識別(RFID)標(biāo)簽防碰撞算法識別效率低的問題,提出一種基于二進制碼調(diào)制的RFID標(biāo)簽防碰撞算法BCMA。對傳統(tǒng)多叉樹防碰撞算法進行改進,活動標(biāo)簽采用位編碼技術(shù)把標(biāo)簽ID在多叉數(shù)中的位置信息調(diào)制到一個2m位的二進制數(shù)主控繼電器(MCR)上,并把MCR回送給閱讀器;閱讀器采用位跟蹤技術(shù),定位MCR碰撞發(fā)生的數(shù)位,從而解調(diào)出活動標(biāo)簽的分組信息。閱讀器對待識別標(biāo)簽的分組是確定性的,進而避免空閑時隙的產(chǎn)生,提高系統(tǒng)識別效率。仿真結(jié)果表明,與常見的八叉樹算法相比,BCMA算法使系統(tǒng)吞吐率提高168%。

射頻識別;防碰撞算法;吞吐率;二進制碼調(diào)制算法;多叉樹;位跟蹤技術(shù)

1 概述

射頻識別(RadioFrequencyIdentification, 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)簽和天線3個部分組成。在多數(shù)應(yīng)用系統(tǒng)中都會存在多個標(biāo)簽或者多個讀寫器。系統(tǒng)中所有的標(biāo)簽和讀寫器共用一個無線頻道,當(dāng)多讀寫器和多標(biāo)簽同時占用頻道通信時,由于信號相互干擾,讀寫器和標(biāo)簽之間的通信不能正常進行,這樣就發(fā)生了碰撞。

RFID多標(biāo)簽防碰撞算法主要使讀寫器正確識別有效通信范圍內(nèi)的多個標(biāo)簽。根據(jù)所采用的無線通信多址接入方式,這些算法可以分為時分多址(Time Division Multiple Access,TDMA)類[3-4],碼分多址(Code Division Multiple Access,CDMA)類,空分多址(Space Division Multiple Access,SDMA)類和頻分多址(Frequency Division Multiple Access, FDMA)類。然而,受RFID系統(tǒng)成本和資源約束,時分多址技術(shù)在RFID多標(biāo)簽防碰撞算法中應(yīng)用最為廣泛?；赥DMA技術(shù)的防碰撞算法又可分為隨機ALOHA算法[5-6]和二進制樹[7-8]2類。目前多標(biāo)簽防碰撞算法研究工作主要圍繞這2類算法的改進展開[9]。從已發(fā)表文獻(xiàn)情況來看,隨機ALOHA算法易于實現(xiàn),成本低廉,但是由于算法的時隙是隨機分配,因此可能造成某些標(biāo)簽長時間無法識別,亦即存在標(biāo)簽饑餓問題[10-11]。二進制樹算法是對待識別標(biāo)簽的反復(fù)分組,直到每個組內(nèi)只含一個標(biāo)簽或者不含標(biāo)簽。這類不存在標(biāo)簽饑餓現(xiàn)象,但是識別時間較長[12]。

本文通過研究二進制編碼特征,對基于二進制數(shù)的搜索算法進行改進,提出一種基于二進制碼調(diào)制的RFID多標(biāo)簽防碰撞算法BCMA。

2 二進制樹搜索算法

二進制樹搜索算法的前提是閱讀器能夠正確判斷碰撞的發(fā)生,這就要求系統(tǒng)設(shè)計滿足2個預(yù)設(shè)條件:(1)活動標(biāo)簽?zāi)軌蛲瑫r響應(yīng)讀寫器命令且信道延遲相同,也就是活動標(biāo)簽的反饋信息能夠同時到達(dá)閱讀器的接收端;(2)標(biāo)簽ID采用曼徹斯特編碼,讀寫器能夠正確識別碰撞位在標(biāo)簽ID中的位置[13-14]。

在二進制樹搜索算法中,閱讀器維持一個查詢前綴序列堆棧,該堆棧的初始成員為“0”和“1”2個查詢前綴序列。二進制樹搜索算法流程如下:

Setp 1閱讀器從堆棧中取出并廣播棧頂查詢前綴序列,識別范圍內(nèi)僅ID序列與查詢前綴序列匹配的標(biāo)簽回送自己的ID給讀寫器,其他標(biāo)簽不響應(yīng)。

Setp 2閱讀器檢測是否有碰撞發(fā)生:若無標(biāo)簽應(yīng)答,則產(chǎn)生一個空閑時隙,閱讀器不做任何操作;若有標(biāo)簽應(yīng)答,但沒有發(fā)生碰撞,則產(chǎn)生一個識別時隙,閱讀器直接識別一個標(biāo)簽;若有多個標(biāo)簽應(yīng)答,則產(chǎn)生一個碰撞時隙,閱讀器檢測到碰撞,則分別在本次查詢的前綴序列后加“0”和“1”形成2個新的查詢前綴序列,并把新產(chǎn)生的前綴序列壓入棧底。

Setp 3重復(fù)Step1和Step2,直到查詢序列前綴為空。

基本的二進制樹查詢算法識別在標(biāo)簽數(shù)量較大的情況下,由于存在大量碰撞時隙,識別效率低下。四叉樹、八叉樹等改進型算法可以減小基本二進制樹查詢算法中的碰撞時隙。但是,當(dāng)叉樹增多,會增加空閑時隙的數(shù)量。

因此,如何在增加叉樹減小碰撞時隙的同時減小空閑時隙,是多叉樹算法的關(guān)鍵問題。文獻(xiàn)[15]提出了基于碰撞因子的自適應(yīng)多叉樹算法和基于分組碼的八叉樹算法,取得了很好的仿真對比結(jié)果。本文提出另一種基于位編碼方式的多叉樹算法,能夠避免空閑時隙的產(chǎn)生。

3 基于位編碼的多叉樹防碰撞算法

3.1 算法預(yù)設(shè)條件

標(biāo)簽ID采用曼徹斯特編碼,長度為L,閱讀器能夠正確識別非碰撞位和碰撞位。閱讀器中設(shè)置一個查詢前綴堆棧S和一個寄存器RBM(Recognized Bits Mask),用于記錄已識別位數(shù)據(jù)。

標(biāo)簽中設(shè)置一個2m位的編碼寄存器MCR。在查詢過程中,ID號與查詢前綴匹配的標(biāo)簽可根據(jù)查詢前綴后的高m位ID數(shù)據(jù),對MCR進行調(diào)制。若某次查詢,查詢前綴Q為“q(0):q(x)”,某標(biāo)簽查詢前綴后的高m位數(shù)據(jù)為“ID(L-1-x):ID(L-1-x-m)”,則把MCR的第“ID(L-1-x):ID(L-1-x-m)”位置“1”,其他位置“0”。

3.2 算法基本操作

算法基本操作如下:

(1)閱讀器查詢命令Request(Q):參數(shù)Q是x位查詢前綴序列“q0q1…qx”。一次查詢過程由閱讀器廣播該命令發(fā)起。有效識別范圍內(nèi),ID號與Q匹配的標(biāo)簽響應(yīng)查詢命令,其他標(biāo)簽不響應(yīng)。Q值缺省情況下,有效識別范圍內(nèi)所有標(biāo)簽響應(yīng)查詢命令。

(2)標(biāo)簽響應(yīng)閱讀器查詢回送數(shù)據(jù)Data:設(shè)某次查詢,標(biāo)簽接收到的查詢前綴序列“q0q1…qx”,若標(biāo)簽高x位與查詢前綴序列匹配,則響應(yīng)查詢,回送數(shù)據(jù)Data格式如圖1所示。回送數(shù)據(jù)的高2m位是標(biāo)簽當(dāng)前編碼寄存器MCR內(nèi)容,回送數(shù)據(jù)的后L-x-m位為標(biāo)簽ID的低位數(shù)據(jù)。

圖1 標(biāo)簽回送的數(shù)據(jù)格式

(3)閱讀器接收標(biāo)簽回送數(shù)據(jù),分別跟蹤接收數(shù)據(jù)的MCR區(qū)碰撞位和ID區(qū)碰撞位,閱讀器通過對接收數(shù)據(jù)的MCR區(qū)碰撞位解調(diào),確定本次查詢前綴序列對應(yīng)結(jié)點的子結(jié)點。設(shè)MCR區(qū)碰撞位數(shù)量為J,ID區(qū)碰撞位數(shù)量為K,若:

1)J=0,K=0,則無碰撞發(fā)生,閱讀器直接識別一個標(biāo)簽。

2)J=0,K=1,在剩余ID中僅有一個碰撞位(One Bit Collision Time-slot,OIBCT),由于標(biāo)簽ID的唯一性,閱讀器可直接識別2個標(biāo)簽。

3)J=0,K＞1,閱讀器通過接收數(shù)據(jù)MCR區(qū)“1”的位置解調(diào)出本結(jié)點的唯一子結(jié)點序號;并把子結(jié)點序號接在本次查詢前綴序列后,形成一個新的查詢前綴序列,壓入堆棧S。

4)J≠0,K=0,剩余標(biāo)簽ID無碰撞,但MCR存在碰撞(Multiple MCR Bits Collision Time-slot, MMBCT),則說明子結(jié)點均為樹葉,可直接識別J個標(biāo)簽。

5)J≠0,K≠0,閱讀器檢測到不可識別碰撞。此時,閱讀器通過解調(diào)接收數(shù)據(jù)的MCR區(qū)碰撞位,獲得本次結(jié)點的J個子結(jié)點序號,并分別把每個子結(jié)點序號增補在原查詢前綴序列后,形成J個新的查詢前綴序列,壓入堆棧S。

3.3 BCMA算法流程

如圖2所示,BCMA的基本步驟如下:

(1)系統(tǒng)初始化,閱讀器清空查詢前綴堆棧S。

(2)閱讀器廣播命令Request(),有效通信范圍內(nèi)所有標(biāo)簽響應(yīng)讀寫器查詢命令。

(3)閱讀器接收標(biāo)簽回送數(shù)據(jù),跟蹤碰撞位,記錄MCR區(qū)碰撞位位數(shù)J和ID區(qū)碰撞位位數(shù)K,并對MCR區(qū)碰撞信息進行解調(diào),計算子結(jié)點序號。

(4)閱讀器根據(jù)J,K的數(shù)量關(guān)系,直接識別標(biāo)簽或產(chǎn)生新的查詢前綴序列入棧。

(5)閱讀器查詢前綴堆棧S是否為空,若為空,則說明所有標(biāo)簽都已經(jīng)正確識別,程序退出,否則轉(zhuǎn)步驟(6)。

(6)閱讀器從查詢前綴堆棧中取棧頂序列Q,并發(fā)送查詢命令Request(Q),有效通信范圍內(nèi)ID與Q匹配的標(biāo)簽響應(yīng)閱讀器命令,其他標(biāo)簽不響應(yīng)。程序返回步驟(3)。

3.4 示例分析

設(shè)m=3,識別范圍內(nèi)存在8個待識別標(biāo)簽TagA～TagH,各自ID號如表1所示。

表1 待識別標(biāo)簽及其ID號

系閱讀器廣播Request()命令后,對接收數(shù)據(jù)MCR進行解調(diào),發(fā)現(xiàn)根結(jié)點上有4個非空子結(jié)點,節(jié)點序號分別為“000”,“010”,“011”和“101”。閱讀器依次訪問這4個結(jié)點。具體識別過程如表2所示。若采用常見八叉樹算法識別上述8個標(biāo)簽,閱讀器需要向標(biāo)簽發(fā)送32次查詢命令。而在基于位編碼的八叉樹識別算法里不存在空閑時隙,閱讀器識別這8個標(biāo)簽僅需發(fā)送9次查詢命令,顯著提高了系統(tǒng)識別效率。

表2 CBMA識別信息

4 算法性能分析

文獻(xiàn)[16]對傳統(tǒng)基于二進制樹算法性能進行了詳盡反洗,若標(biāo)簽ID位長為L,待識別標(biāo)簽數(shù)為N,搜索樹深度K,則傳統(tǒng)B叉樹所需的時隙數(shù)為:

其中,碰撞時隙和識別時隙數(shù)分別為:

空閑時隙數(shù)量為:

與傳統(tǒng)的B叉樹防碰撞算法不同,本文算法利用標(biāo)簽ID的唯一性和不同二進制編碼同數(shù)位數(shù)碼的互斥性,通過二進制編碼調(diào)制的方式去除了空閑時隙,提高識別效率。新算法的空閑時隙樹為零。由于存在MMBCT時隙,在傳統(tǒng)B叉樹中為碰撞時隙,在新算法中為一個可識別多個標(biāo)簽的識別時隙,因此新算法的碰撞時隙將小于傳統(tǒng)B叉樹算法。同時,由于存在一個時隙識別多個標(biāo)簽,因此新算法的識別時隙將小于傳統(tǒng)算法的識別時隙數(shù)。但是在標(biāo)簽數(shù)目很大時,MMBCT和OIBCT數(shù)目將減少,對識別時隙和碰撞時隙數(shù)的影響可以忽略。在大標(biāo)簽數(shù)量情況下,新算法的總時隙數(shù)為:

式(1)減去式(5),可得新算法節(jié)省總時隙數(shù)為:

新算法的吞吐率為:

5 仿真分析

要驗證所提算法的有效性,可在Matlab環(huán)境下對算法進行仿真。設(shè)標(biāo)簽ID位數(shù)為64位;標(biāo)簽ID服從均勻分布;標(biāo)簽數(shù)目分別為10,100,200,…, 1000。每設(shè)置一次標(biāo)簽數(shù)目,實驗重復(fù)100次,平均時隙為100次取平均。

圖3所示為標(biāo)簽MCR長度是8位時,八叉樹算法和BCMA的平均時隙數(shù)和吞吐率對比仿真結(jié)果。仿真結(jié)果表明,BCMA的空閑時隙為零,碰撞時隙與八叉樹算法相同,總時隙數(shù)明顯小于八叉樹算法。仿真結(jié)果還表明,BCMA顯著提高了系統(tǒng)的吞吐率。BCMA的平均吞吐率為0.67 slot/標(biāo)簽,八叉樹的平均吞吐率為0.25 slot/標(biāo)簽,BCMA使系統(tǒng)吞吐率提高了168%。

圖3 BCMA與八叉樹算法性能對比

圖4所示為標(biāo)簽MCR位數(shù)在1～8之間動態(tài)變化時,BCMA系統(tǒng)吞吐率的仿真結(jié)果。仿真結(jié)果表明,BCMA系統(tǒng)吞吐率隨著MCR位數(shù)的增大呈現(xiàn)先增大后減小的變化趨勢。當(dāng)MCR位數(shù)為lbL(L為標(biāo)簽ID位數(shù))時,系統(tǒng)吞吐率達(dá)到最大。仿真結(jié)果還表明,當(dāng)標(biāo)簽數(shù)量較小時,系統(tǒng)吞吐率起伏比較大,當(dāng)標(biāo)簽數(shù)量較大時,系統(tǒng)吞吐率趨于穩(wěn)定。這是因為,在標(biāo)簽數(shù)量較少時,多位同時發(fā)生碰撞的概率較低, MMBCT和OIBCT會對系統(tǒng)吞吐率產(chǎn)生影響。

圖4 MCR位數(shù)對BCMA系統(tǒng)吞吐率的影響

MCR位數(shù)的增大,增加了標(biāo)簽的復(fù)雜度,同時也增大了系統(tǒng)的通信載荷。BCMA在提高系統(tǒng)吞吐率的同時需要兼顧成本和通信載荷,因此,標(biāo)簽MCR位數(shù)不宜過高,通常取4位或8位。

6 結(jié)束語

本文提出一種基于二進制碼調(diào)制的RFID多標(biāo)簽防碰撞算法BCMA。通過確定性分組,避免空閑時隙的產(chǎn)生,顯著提高識別效率。理論分析和仿真實驗表明,BCMA性能優(yōu)于常見的多叉樹算法,顯著提高了系統(tǒng)吞吐率。BCMA對常見的多叉數(shù)算法進行了改進,具有一定的創(chuàng)新性。同時提高了RFID系統(tǒng)識別效率,具有一定的實用性。下一步工作是設(shè)計并實現(xiàn)能夠支持本文算法的標(biāo)簽和讀寫器并開展應(yīng)用。

[1] Zuo Yanjun.Survivable RFID Systems:Issues,Challenges and Techniques[J].IEEE Transactions on Systems,Man, and Cybernetics-Part C:Applications and Reviews,2010, 40(4):406-418.

[2] Mohamed B,Adel M,Belkacem F.Dual Antenna for Physical Layer UHF RFID Collision Cancelling[C]// Proceedings of International Conference on Multimedia Computing and Systems.[S.l.]:IEEE Press,2012:623-628.

[3] Lee Chi-Chung,Lin Shengyue.A Double Blocking Dynamic Framed Slotted ALOHA Anti-collision Method for Mobile RFID Systems[C]//Proceedings of the 6th International Conference on Genetic and Evolutionary Computing.[S.l.]:Springer,2012:581-584.

[4] Jiang Chenyi,XuYinfei,WangQiao.Cancellation Strategy in Dynamic Framed Slotted ALOHA for RFID System[C]//Proceedings of IEEE Wireless Communications and Networking Conference.[S.l.]:IEEE Press,2013:854-859.

[5] Yang Qing,Li Jiancheng,Wang Hongyi,et al.A Dynamic Framed Slotted ALOHA Anti-collision Algorithm BasedonTag-groupingforRFIDSystems[C]// Proceedings of the11th International Conference on Digital Object Identifier.[S.l.]:IEEE Press,2012:1-3.

[6] Wang Shuai,Hong Weijun,Li Shufang.A Slot-wise LMMSE Estimate Algorithm for Frame Slotted Aloha Protocol of RFID System[C]//Proceedings of the 8th International Conference on Wireless Communications, Networking and Mobile Computing.[S.l.]:IEEE Press,2012:1-5.

[7] Xue Jianbin,Wang Wenhua,Li Songbai,et al.Anticollision Algorithm Based on Counting Mechanism and Multi-stateBinary[C]//Proceedingsofthe5th Conference on Measuring Technology and Mechatronics Automation.[S.l.]:IEEE Press,2013:276-282.

[8] Landaluce H,Perallos A,Zuazola I J G.A Fast RFID Identification Protocol with Low Tag Complexity[J]. IEEE Communications Letters,2013,17(9):1704-1706.

[9] Lai Yuancheng,Hsiao Ling-Yen,Chen Hongjie,et al.A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification[J].IEEE Transactions on Mobile Computing,2013,12(10):2063-2075.

[10] Yang Yongkang,Cui Chunsheng,Zhou Tuanfeng,et al. ImprovementonRFID-basedBinaryAnti-collision Algorithm[C]//Proceedings of International Conference on Computer Science and Service System.[S.l.]:IEEE Press,2012:515-518.

[11] Di Jin,Ma Yanmin,Fan ZhiPeng,et al.A RFID Anticollision Algorithm Based on Multithread Regressivestyle Binary System[C]//Proceedings of International Conference on Measurement,Information and Control. [S.l.]:IEEE Press,2012:365-369.

[12] Liang Chiu-Kuo,Lin Hsin-Mo.Using Dynamic Slots Collision Tracking Tree Technique Towards an Efficient Tag Anti-collision Algorithm in RFID Systems[C]// Proceedings of the 9th International Conference on Autonomic&Trusted Computing.[S.l.]:IEEE Press, 2012:272-277.

[13] Piao Chunhui.Fan Zhenjiang.Yang Chunyan,et al. ResearchonGroup-basedPollingAnti-collision AlgorithmforRFIDTagIdentification[C]// Proceedings ofInternationalForumonInformation Technology and Applications.[S.l.]:IEEE Press, 2010:185-188.

[14] Bai Yu,Xuan Xiuwei,Teng Jianfu,et al.An Anticollision Algorithm Based on Collision Bit Position and Splitting[C]//Proceedings of the 6th International Conference on Wireless Communications Networking and Mobile Computing.[S.l.]:IEEE Press,2010:1-4.

[15] 張學(xué)軍,王緒海,蔡文琦.基于分組碼的改進型防碰撞算法研究[J].計算機應(yīng)用研究,2012,29(11): 4265-4268.

[16] Hush D R,Wood C.Analysis of Tree Algorithms for RFID Arbitration[C]//Proceedings of International Symposium on Information Theory.[S.l.]:IEEE Press,1998:1-10.

編輯 顧逸斐

A Radio Frequency Identification Anti-collision Algorithm Based on Binary Code Modulation

LI Zhijian1,3,XIAO Yilin2
(1.School of Electronic and Information Engineering,South China University of China,Guangzhou 510640,China;
2.Guangzhou Research Institute of Optical Mechanical Electrics Technology,Guangzhou 510663,China;
3.Guangdong Public Laboratory of Modern Control and Optical Mechanical Electrics Technology,Guangzhou 510663,China)

To improve the identification efficiency and reduce the communication overhead,a novel algorithm,Binary Code Modulation Algorithm(BCMA)is proposed.BCMA works as follows:the activated tag generates and sends back a 2mbit binary code,Master Control Relay(MCR),on which the location information of the tag’s ID in the multi-branch tree is modulated.After receiving the MCR,the reader finds out the collided bits,demodulates the branch information,and groups the tags into determinate subsets.It is obvious that BCMA avoids generating idle slots.Analysis results and simulations show that compared with other existing multi-branch algorithms,as the common octree algorithm,BCMA improves the system throughput by168%.

Radio Frequency Identification(RFID);anti-collision algorithm;throughput;Binary Code Modulation Algorithm(BCMA);multi-branch tree;bit tracking technique

李志堅,肖熠琳.一種基于二進制碼調(diào)制的射頻識別防碰撞算法[J].計算機工程,2015,41(2): 308-312.

英文引用格式:Li Zhijian,Xiao Yilin.A Radio Frequency Identification Anti-collision Algorithm Based on Binary Code Modulation[J].Computer Engineering,2015,41(2):308-312.

1000-3428(2015)02-0308-05

:A

:TN92

10.3969/j.issn.1000-3428.2015.02.059

廣東省科技計劃基金資助項目(2010A011300016,2011J4100034,2011J4300078)。

李志堅(1981-),男,講師、博士研究生,主研方向:RFID技術(shù),信號處理,物聯(lián)網(wǎng)應(yīng)用;肖熠琳,工程師。

2014-01-03

:2014-03-31E-mail:lizhjian@scut.edu.cn