《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > RFID系統(tǒng)中多電子標(biāo)簽防碰撞改進(jìn)算法
RFID系統(tǒng)中多電子標(biāo)簽防碰撞改進(jìn)算法
來(lái)源:電子技術(shù)應(yīng)用2012年第1期
張 瑜, 李潤(rùn)哲
河南師范大學(xué) 物理與信息工程學(xué)院,,河南 新鄉(xiāng)453007
摘要: 在現(xiàn)有防碰撞算法的基礎(chǔ)上提出了一種改進(jìn)的二進(jìn)制搜索算法,。當(dāng)讀寫(xiě)器檢測(cè)到碰撞位之后,僅需要記錄最高碰撞位和次高碰撞位的位置,,并設(shè)定這兩個(gè)位置上的比特?cái)?shù)作為下次查詢命令,從而使系統(tǒng)的傳輸數(shù)據(jù)量,、查詢次數(shù)及傳輸時(shí)間大大減少,提高了系統(tǒng)的吞吐率,。仿真結(jié)果表明,改進(jìn)后的算法比二進(jìn)制搜索算法和動(dòng)態(tài)二進(jìn)制搜索算法更具優(yōu)勢(shì),。
中圖分類號(hào): TP301
文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 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

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

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

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

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

 


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

    通過(guò)理論和仿真比較可見(jiàn),,采用改進(jìn)后的二進(jìn)制搜索算法較其他兩個(gè)算法有三個(gè)方面的優(yōu)勢(shì):其一減少了查詢標(biāo)簽次數(shù),使計(jì)算時(shí)間減??;其二減少了系統(tǒng)數(shù)據(jù)傳輸量,提高了標(biāo)簽的識(shí)別速率,;其三較大地提高了系統(tǒng)的吞吐率,。
    本文對(duì)BS算法及DBS算法過(guò)程進(jìn)行了分析,,找出了其中的不足之處,在此基礎(chǔ)上提出了一種改進(jìn)的二進(jìn)制搜索算法,,并通過(guò)Matlab仿真得到該算法的查詢次數(shù)和吞吐率方面的數(shù)據(jù),。通過(guò)實(shí)驗(yàn)數(shù)據(jù)表明,該改進(jìn)算法可以減少系統(tǒng)的查詢次數(shù),,提高系統(tǒng)的吞吐率,。從而驗(yàn)證了該改進(jìn)算法的優(yōu)越性。
參考文獻(xiàn)
[1] 李曉東.射頻識(shí)別技術(shù)中的隱私安全問(wèn)題及策略[J].微電子學(xué)與計(jì)算機(jī),,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] 廖傳書(shū),,付泰.射頻識(shí)別系統(tǒng)的防碰撞算法研究[J].國(guó)外電子元器件,,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ìn)制搜索防碰撞算法研究[J].河北科技大學(xué)學(xué)報(bào),,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)東,,等.基于返回式索引的二進(jìn)制樹(shù)形搜索反碰撞算法及其實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2004,40(16):26-28.
[8] 姜麗芬,盧桂章,,辛運(yùn)帷,,等.射頻識(shí)別系統(tǒng)中防碰撞算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2007,,43(5):29-32.
[9] 王忠勇,,高向川.基于回溯的RFID防碰撞算法[J].微計(jì)算機(jī)信息,2009,,25(2):187-188.
[10] FINKENZELLER K.射頻識(shí)別技術(shù)—無(wú)線電感應(yīng)的標(biāo)簽和非接觸式IC卡的原理與應(yīng)用[M].陳大才,譯.北京:電子工業(yè)出版社,,2001.

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