《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > RFID系統(tǒng)中多電子標簽防碰撞改進算法
RFID系統(tǒng)中多電子標簽防碰撞改進算法
來源:電子技術(shù)應(yīng)用2012年第1期
張 瑜, 李潤哲
河南師范大學(xué) 物理與信息工程學(xué)院,河南 新鄉(xiāng)453007
摘要: 在現(xiàn)有防碰撞算法的基礎(chǔ)上提出了一種改進的二進制搜索算法。當讀寫器檢測到碰撞位之后,僅需要記錄最高碰撞位和次高碰撞位的位置,并設(shè)定這兩個位置上的比特數(shù)作為下次查詢命令,從而使系統(tǒng)的傳輸數(shù)據(jù)量、查詢次數(shù)及傳輸時間大大減少,提高了系統(tǒng)的吞吐率。仿真結(jié)果表明,改進后的算法比二進制搜索算法和動態(tài)二進制搜索算法更具優(yōu)勢。
中圖分類號: TP301
文獻標識碼: A
文章編號: 0258-7998(2012)01-0109-03
An improved anti-collision algorithm for multi-tag in RFID system
Zhang Yu, Li Runzhe
College of Physics and Information Engineering, Henan Normal University, Xinxiang 453007, China
Abstract: A novel anti-collision algorithm was proposed in the paper,which is based on analysis of the old binary search and dynamic binary search algorithm.When detecting the collision,the reader records the maximal and the next collision position,then set collision bits′ value in the responded identification code of tags.Theory and computer simulations show that the new anti-collision algorithm is superior to the binary search algorithm and the dynamic binary search algorithm.
Key words : radio frequency identification(RFID);collision;binary search algorithm;dynamic binary search algorithm

    射頻識別(RFID)技術(shù)是一種非接觸式的自動識別技術(shù),通常由讀寫器、電子標簽和計算機數(shù)據(jù)管理系統(tǒng)三部分組成[1],通過DSRC短程通信技術(shù)進行數(shù)據(jù)傳輸和交換。RFID系統(tǒng)工作時,如果遇到兩個以上電子標簽都在讀寫器信號的覆蓋范圍內(nèi),則各個電子標簽會同時對讀寫器發(fā)出信號,從而造成各電子標簽間數(shù)據(jù)的碰撞,使讀寫器不能正常讀取各個電子標簽內(nèi)的有關(guān)數(shù)據(jù),這就是RFID系統(tǒng)中的多路存取問題。因此只有解決好電子標簽的碰撞問題,才能使RFID系統(tǒng)正常工作,而解決電子標簽防碰撞問題的關(guān)鍵是優(yōu)化的防碰撞算法。

    現(xiàn)有的RFID防碰撞算法都是基于TDMA算法,可劃分為Aloha防碰撞算法和基于二進制搜索BS(Binary search)算法兩大類[2-3]。Aloha是一種隨機接入算法,這種算法多采取“標簽先發(fā)言”的方式,即標簽一旦進入閱讀器的閱讀區(qū)域就自動向閱讀器發(fā)送其自身的ID,隨即標簽和閱讀器間開始通信。在標簽發(fā)送數(shù)據(jù)的過程中,若有其他標簽也在發(fā)送數(shù)據(jù),將發(fā)生信號重疊從而導(dǎo)致完全沖突或部分沖突,閱讀器檢測接收到的信號來判斷有無沖突。如果發(fā)生沖突,閱讀器將發(fā)送命令讓標簽停止發(fā)送,隨機等待一段時間后再重新發(fā)起查詢。該算法特點是:算法簡單、便于實現(xiàn),適用于低成本RFID系統(tǒng)。但是由于該算法的時隙是隨機分配的,當大量標簽并存時,幀沖突嚴重[4]。而基于BS算法是通過多次比較,不斷篩選出不同的標簽號,時分復(fù)用地進行讀寫器和射頻卡之間的信號交換,以一個獨特的序列號識別射頻卡為基礎(chǔ)。為了從一組射頻卡中選出其中的一個,讀寫器需要發(fā)出一個請求命令,有意識地將射頻卡序列號傳輸時的數(shù)據(jù)碰撞引導(dǎo)到讀寫器上,即讓讀寫器來判斷是否發(fā)生碰撞。如發(fā)生碰撞,則縮小范圍進行進一步搜索。這類算法雖然識別效率高, 但是算法比較復(fù)雜, 識別時間較長[5-6]。本文在二進制防碰撞算法的基礎(chǔ)上提出一種改進的防碰撞算法。
1 兩種典型的二進制防碰撞算法的分析
1.1 二進制搜索算法

    實現(xiàn)BS算法系統(tǒng)的必要前提是能夠辨認出在讀寫器中數(shù)據(jù)沖突位的準確位置,因此必須選用合適的編碼。曼徹斯特編碼能夠按位識別出碰撞位,這樣可以根據(jù)碰撞的位置,按一定的規(guī)則重新搜索標簽。因此,使用曼徹斯特編碼是實現(xiàn)二進制搜索防碰撞算法的必要前提[7-8]。BS算法的工作流程如下:
    (1)電子標簽進入讀寫器的作用范圍時,讀寫器發(fā)送命令REQUEST(≤11111111),所有滿足此條件的電子標簽響應(yīng)此命令,并將自己的EPC號傳給讀寫器。
   (2)讀寫器對比電子標簽響應(yīng)的EPC碼相同位數(shù)上的數(shù),根據(jù)Manchester編碼規(guī)則,若出現(xiàn)不一致現(xiàn)象,即可判斷出該比特位有碰撞。
   (3)當確定有碰撞后,將此次發(fā)生碰撞的最高位置“0”,最高碰撞位之前的比特位不變,最高碰撞位后的所有比特位都置“1”,并產(chǎn)生新的請求命令REQUEST,依次排除序列號大的標簽,直到讀寫器對比電子標簽響應(yīng)的序列號中相同位數(shù)上的數(shù)完全一致時,則說明無碰撞。此時,使用選擇命令(SELECT)選出一個唯一的標簽。
    (4)選出唯一的標簽后,使用READ-DATA命令完成讀寫器與該電子標簽的數(shù)據(jù)交換。并使用選擇命令(UNSELECT)進入“無聲”狀態(tài),此時在讀寫器范圍內(nèi)不再響應(yīng)(重新進入讀寫器范圍可再次響應(yīng))。為了重新激活電子標簽,必須進行復(fù)位操作。
    (5)重復(fù)前4個步驟,并選擇剩余的電子標簽數(shù)據(jù)交換。多次循環(huán)后即可完成所有電子標簽的讀取。
1.2 動態(tài)二進制搜索算法(DBS)
    在BS搜索算法中,從讀寫器和單個電子標簽的數(shù)據(jù)流可以看出,讀寫器發(fā)出的請求命令中,最高碰撞位后的所有比特位都被置“1”,對標簽的識別不能提供任何的信息。而標簽返回的數(shù)據(jù)中,最高碰撞位以前的比特位及最高碰撞位不包含給讀寫器的補充信息,因為這些位是已知且給定的,屬于多余的重復(fù)信息?;诖巳藗兲岢隽?a class="innerlink" href="http://ihrv.cn/tags/動態(tài)二進制搜索算法" title="動態(tài)二進制搜索算法" target="_blank">動態(tài)二進制搜索算法(DBS)[9],當讀寫器檢測到碰撞后,下一次讀寫器在請求命令中只發(fā)送搜索序列號中的最高位和最高碰撞位之間的部分作為搜索依據(jù),然后中斷傳輸,所有在與最高位和最高碰撞位之間的部分相同的電子標簽響應(yīng)并送回它們序列號的剩余各位,即最高碰撞位之后的比特位作為應(yīng)答。因此,DBS算法避免了序列號中多余部分的傳輸,數(shù)據(jù)傳輸時間明顯縮短。DBS算法較BS算法在傳輸數(shù)據(jù)量和所需時間上可減少50%[10]。
2 改進的二進制搜索算法
2.1算法約定

    鑒于BS算法的缺點,本文提出了一種改進的二進制搜索算法,算法約定如下:
    (1)采用曼徹斯特編碼的電子標簽序列號每個比特位上的取值不是“0”就是“1”。因此,如果當讀寫器探測到僅有一位碰撞位時,讀寫器不需要發(fā)送請求命令,可以直接識別出2個標簽。
     (2)讀寫器如果檢測到有N個碰撞位,則說明這N個碰撞位的比特位對讀寫器來說是未知的,而其他的比特位對讀寫器來說是已知的。因此讀寫器只需要對未知的碰撞位處理,而不需要傳輸那些已知的比特位,從而減少傳輸時延。
    為了便于描述以及實現(xiàn)該算法,給出如下防碰撞命令:
     ①查詢命令request(DX,MX;DX1,MX1)。參數(shù)DX、DX1分別為檢測到碰撞位的最高位和次高位,參數(shù)MX、MX1為0、1的二維排列組合,例如檢測到1?1?00?1,那么讀寫器發(fā)送request(D6,0;D4,0)符合條件的標簽響應(yīng)并返回沖突位及相關(guān)信息。
     ②退出選擇命令unselect。取消事先選中的電子標簽,使標簽進入“無聲”狀態(tài)。在這種狀態(tài)下標簽完全是非激活的,對收到的request命令不做應(yīng)答。為了重新激活標簽,必須暫時離開讀寫器的作用范圍,然后再次進入該讀寫器范圍。
2.2 算法原理
  下面以讀寫器作用范圍內(nèi)的8個編碼為8 bit的標簽為例說明該算法,8個標簽的編碼如下:tag1:01001000,tag2:01010100,tag3:01011010,tag4:01000000,tag5:01000010,
tag6:01010000,tag7:01001010,tag8:01011000。
    (1)request≤11111111命令,讀寫器作用范圍內(nèi)的所有標簽應(yīng)答,讀寫器譯碼的結(jié)果為010????0碰撞位為D4,D3,D2,D1,最高碰撞位為D4,次高碰撞位為D3,因此下次查詢命令為request(D4,0;D3,0)。
    (2)讀寫器發(fā)送查詢命令request(D4,0;D3,0),標簽通過比較各自的D4、D3位,與之相同的標簽則發(fā)送自己的相關(guān)信息給讀寫器。通過比較后標簽4和標簽5響應(yīng),編碼后得到010000?0,讀寫器檢測到僅只有一位碰撞,可以直接識別出標簽4和標簽5。讀寫器正確識別它們之后,執(zhí)行unselect命令,使標簽4和標簽5處于“無聲”狀態(tài)。
    (3)讀寫器發(fā)送查詢命令request(D4,0;D3,1),標簽1和標簽7響應(yīng),編碼后得到010010?0,讀寫器檢測到僅只有一位碰撞,可以直接識別出標簽1和標簽7。讀寫器正確識別它們之后,執(zhí)行unselect命令,使標簽1和標簽7處于“無聲”狀態(tài)。
    (4)讀寫器發(fā)送查詢命令request(D4,1;D3,0),標簽2和標簽6響應(yīng),編碼后得到01010?00,讀寫器檢測到僅只有一位碰撞,可以直接識別出標簽2和標簽6。讀寫器正確識別它們之后,執(zhí)行unselect命令,使標簽1和標簽7處于“無聲”狀態(tài)。
    (5)讀寫器發(fā)送查詢命令request(D4,1;D3,1),標簽3和標簽8響應(yīng),編碼后得到010110?0,讀寫器檢測到僅只有一位碰撞,可以直接識別出標簽3和標簽8。讀寫器正確識別它們之后,執(zhí)行unselect命令,使標簽1和標簽7處于“無聲”狀態(tài)。至此,讀寫器作用范圍內(nèi)的所有標簽都別正確識別完畢。算法流程如圖1所示。
3 算法性能比較
    假設(shè)讀寫器作用范圍內(nèi)有N個電子標簽,則BS算法完成所有標簽識別的搜索命令次數(shù)S(N)為:
    
    系統(tǒng)的吞吐率η1為:
    

 


    對三種算法采用Matlab軟件進行仿真, 其結(jié)果如圖2所示。

    通過理論和仿真比較可見,采用改進后的二進制搜索算法較其他兩個算法有三個方面的優(yōu)勢:其一減少了查詢標簽次數(shù),使計算時間減小;其二減少了系統(tǒng)數(shù)據(jù)傳輸量,提高了標簽的識別速率;其三較大地提高了系統(tǒng)的吞吐率。
    本文對BS算法及DBS算法過程進行了分析,找出了其中的不足之處,在此基礎(chǔ)上提出了一種改進的二進制搜索算法,并通過Matlab仿真得到該算法的查詢次數(shù)和吞吐率方面的數(shù)據(jù)。通過實驗數(shù)據(jù)表明,該改進算法可以減少系統(tǒng)的查詢次數(shù),提高系統(tǒng)的吞吐率。從而驗證了該改進算法的優(yōu)越性。
參考文獻
[1] 李曉東.射頻識別技術(shù)中的隱私安全問題及策略[J].微電子學(xué)與計算機,2005,22(9):137-140.
[2] FINKENZELLER K. RFID Handbook:Fundamentals and  applications in contactless smart cards and identification[M].New York:John Wiley and Sons,2003.
[3] 廖傳書,付泰.射頻識別系統(tǒng)的防碰撞算法研究[J].國外電子元器件,2008,16(9):6-8.
[4] LEE S R,JOO S D,LEE C W.An enhanced dynamic  framed slotted ALOHA algorithm for RFID tag identification[C]. The Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems,2005.
[5] 莫磊.RFID位屏蔽二進制搜索防碰撞算法研究[J].河北科技大學(xué)學(xué)報,2010,31(5):458-462.
[6] TSAN P W.Enhanced binary search with cut through operation for anti-collision in RFID systems[J].Communications Letter IEEE,2005,10(4):236-238.
[7] 余松森,詹宜巨,彭衛(wèi)東,等.基于返回式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)[J]. 計算機工程與應(yīng)用, 2004,40(16):26-28.
[8] 姜麗芬,盧桂章,辛運帷,等.射頻識別系統(tǒng)中防碰撞算法研究[J].計算機工程與應(yīng)用,2007,43(5):29-32.
[9] 王忠勇,高向川.基于回溯的RFID防碰撞算法[J].微計算機信息,2009,25(2):187-188.
[10] FINKENZELLER K.射頻識別技術(shù)—無線電感應(yīng)的標簽和非接觸式IC卡的原理與應(yīng)用[M].陳大才,譯.北京:電子工業(yè)出版社,2001.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。