許 航，鄧紅衛(wèi)，孫艷平, 廖瑾蕓，楊 桂，彭麗蓉

(衡陽師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南 衡陽 421002)

一種基于奇偶分組的RFID防碰撞算法

許 航，鄧紅衛(wèi)*，孫艷平, 廖瑾蕓，楊 桂，彭麗蓉

(衡陽師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖南 衡陽 421002)

本算法在混合查詢樹算法的基礎(chǔ)上，利用標(biāo)簽ID中“1”的個(gè)數(shù)分為奇區(qū)域和偶區(qū)域兩組。在奇區(qū)域或偶區(qū)域中根據(jù)標(biāo)簽ID序列的前三位中“1”的個(gè)數(shù)，將標(biāo)簽放入四個(gè)時(shí)隙中分別進(jìn)行響應(yīng)，減少標(biāo)簽碰撞。性能分析結(jié)果表明，該算法優(yōu)于QT、HQT算法，提高了 標(biāo)簽識別的效率。

奇偶分組；奇區(qū)域；偶區(qū)域；防碰撞算法

1 RFID防碰撞算法

射頻識別(RFID)作為一種非接觸式自動識別技術(shù)被廣泛應(yīng)用于銷售、物流和定位等領(lǐng)域[1]。在RFID標(biāo)簽識別過程中，防碰撞算法已成為該領(lǐng)域廣泛研究的熱點(diǎn)問題之一[2]。

目前，國內(nèi)學(xué)者對RFID基本防碰撞算法及其改進(jìn)算法作了深入的研究。文獻(xiàn)[3]提出了一種多周期奇偶分組的防碰撞算法，該算法通過奇偶分組，創(chuàng)造了一種二元確定理論。采用該算法后，可以一次性識別兩個(gè)碰撞位，減少了查詢次數(shù)，縮短了識別時(shí)間，提高了識別效率。在上述研究的基礎(chǔ)上，提出一種改進(jìn)的基于奇偶分組的RFID防碰撞算法。

2 改進(jìn)的奇偶搜索防碰撞算法

2.1 算法指令約定

為了充分利用已得到的碰撞位信息，減少查詢次數(shù)和通信量，本算法對原有的算法指令進(jìn)行了如下改進(jìn)：

(1)查詢指令REQUEST。REQUEST分別有REQUEST(bit) ,REQUEST(xyz),REQUEST(H,Y)三個(gè)指令。REQUEST(bit)為最初查詢指令，要求閱讀器范圍內(nèi)的所有標(biāo)簽都得響應(yīng)。REQUEST (abc)中的x、y、z是響應(yīng)REQUEST(bit)的標(biāo)簽ID序列的前三位，REQUEST(xyz)要求閱讀器讀取所有標(biāo)簽的x、y、z這三位的值，還要求標(biāo)簽計(jì)算它們各自x、y、z這三位值相加的結(jié)果，并存入自己的累加器acc中，acc的值為0、1、2、3。REQUEST(H,Y)中的H為中間碰撞位(或中間兩位)的ID，Y位中間碰撞位的賦值(或賦值組合)。棧stack中存放REQUEST指令，當(dāng)stack為空時(shí)，算法結(jié)束。

(2) 選擇指令SELECT。SELECT(ID)選擇編號為ID的RFID標(biāo)簽，準(zhǔn)備讀出或?qū)懭隦FID標(biāo)簽中的數(shù)據(jù)。

(3) 讀指令READ。READ(ID) 讀出編號為ID標(biāo)簽中的數(shù)據(jù)。

(4) 屏蔽指令UNSELECT。UNSELECT(ID) 屏蔽編號為ID標(biāo)簽。

2.2 算法描述

先根據(jù)標(biāo)簽ID序列的1的個(gè)數(shù)分為奇區(qū)域和偶區(qū)域，然后在奇區(qū)域或偶區(qū)域中再根據(jù)標(biāo)簽ID序列的前三位中“1”的個(gè)數(shù)分為0、1、2、3四個(gè)時(shí)隙，再判斷時(shí)隙中碰撞位的個(gè)數(shù)。如果碰撞位小于等于2位，則直接識別標(biāo)簽；如果碰撞位大于2位，再判斷碰撞位的個(gè)數(shù)是奇數(shù)還是偶數(shù)。如果是奇數(shù)，則發(fā)送對最中間碰撞位賦值0或1的命令；否則，發(fā)送對中間兩個(gè)碰撞位賦值的組合的命令。再判斷響應(yīng)標(biāo)簽的碰撞位的個(gè)數(shù)進(jìn)行識別。算法流程圖如圖1所示。

(1)假設(shè)閱讀器識別范圍內(nèi)有N個(gè)等待識別的標(biāo)簽，閱讀器首先發(fā)送REQUEST (bit)，所有標(biāo)簽都響應(yīng)，根據(jù)標(biāo)簽ID序列中“1”的個(gè)數(shù)是奇數(shù)還是偶數(shù)，分到相應(yīng)的奇區(qū)域或偶區(qū)域中。

(2)在奇區(qū)域或偶區(qū)域中根據(jù)標(biāo)簽ID序列的前三位“1”的個(gè)數(shù)分為0(000)、1(001、010、100)、2(011、101、110)、3(111)四個(gè)時(shí)隙。判斷時(shí)隙中標(biāo)簽的響應(yīng)情況。

(3)如果時(shí)隙中沒有標(biāo)簽響應(yīng)，則為空時(shí)隙；進(jìn)入第(8)步。

(4)如果時(shí)隙中只有一個(gè)標(biāo)簽響應(yīng)，則直接識別該標(biāo)簽；使用UNSELECT指令屏蔽該標(biāo)簽。否則，進(jìn)入第⑻步。

(5)如果時(shí)隙中有兩個(gè)及以上的標(biāo)簽響應(yīng)，則此時(shí)隙中發(fā)生了碰撞，從中得到碰撞位的位數(shù)，如果碰撞位的位數(shù)小于等于2位，則直接識別標(biāo)簽；如果碰撞位的位數(shù)大于2位，再判斷碰撞位的位數(shù)是奇數(shù)個(gè)還是偶數(shù)個(gè)。如果是奇數(shù)個(gè)，進(jìn)入第⑹步，如果是偶數(shù)個(gè)，進(jìn)入第⑺步。

(6)對最中間的那一位碰撞位賦值0或1，判斷響應(yīng)的標(biāo)簽是否還有碰撞位？是，則進(jìn)入第(5)步；否，則識別標(biāo)簽。此時(shí)隙中標(biāo)簽是否識別完？是，則進(jìn)入第⑻步；否，則繼續(xù)識別。

(7)對中間的兩位碰撞位賦值00或01或10或11組合，判斷響應(yīng)的標(biāo)簽是否還有碰撞位？是，則進(jìn)入第(5)步；否，則識別標(biāo)簽。此時(shí)隙中標(biāo)簽是否識別完？是，則進(jìn)入第⑻步；否，則繼續(xù)識別。

(8)識別下一個(gè)時(shí)隙。

(9)兩個(gè)區(qū)域中每個(gè)時(shí)隙是否都為空。為空則表明N個(gè)標(biāo)簽全部識別，算法結(jié)束；否則返回到第(2)步。

2.3 算法流程

圖1 算法流程圖

2.4 算法舉例

下面通過一個(gè)實(shí)例來分析新算法的工作原理。閱讀器作用范圍內(nèi)有8個(gè)待識別的標(biāo)簽，如表1所示。

表1 曼徹斯特編碼

算法的工作原理如下：

(1)閱讀器發(fā)送REQUEST(11111111)，閱讀器識別范圍內(nèi)的所有標(biāo)簽都響應(yīng)，根據(jù)標(biāo)簽ID中“1”的個(gè)數(shù)是奇數(shù)還是偶數(shù)分為奇區(qū)域和偶區(qū)域，可知偶區(qū)域中只有Tag5；奇區(qū)域中有Tag1、Tag2、Tag3、Tag4、Tag6、Tag7、Tag8。

(2)在奇區(qū)域中，根據(jù)標(biāo)簽ID前三位分的四個(gè)時(shí)隙可知Tag4在0時(shí)隙里。Tag2、Tag6、Tag7在1時(shí)隙里，Tag1、Tag3、Tag8在2時(shí)隙里。3時(shí)隙里沒有標(biāo)簽響應(yīng)，為空時(shí)隙。0時(shí)隙里只有Tag4 1個(gè)標(biāo)簽則直接識別。1時(shí)隙里的三個(gè)標(biāo)簽的碰撞信息如表2所示，碰撞位的位數(shù)為5位，最中間的碰撞位為D4，則閱讀器發(fā)送REQUEST(D4，0)，Tag2和Tag6響應(yīng)，得到的解碼為1000XX01，即Tag2和Tag6只有兩個(gè)碰撞位，能直接識別。(因?yàn)槭窃谄鎱^(qū)域里，所以可以肯定產(chǎn)生碰撞的兩個(gè)標(biāo)簽為10000101、10001001)。閱讀器發(fā)送REQUEST(D4，1)，只有Tag7響應(yīng)，標(biāo)簽被識別。1時(shí)隙里的標(biāo)簽識別完。接著識別2時(shí)隙里的標(biāo)簽，2時(shí)隙里的三個(gè)標(biāo)簽的碰位信息如表3所示。碰撞位的位數(shù)為4位，中間兩位碰撞位為D3和D1，則閱讀器發(fā)送REQUEST(D3D1，00)，沒有標(biāo)簽響應(yīng)，閱讀器發(fā)送REQUEST(D3D1，01)，只有Tag3響應(yīng)，標(biāo)簽被識別，閱讀器發(fā)送REQUEST(D3D1，10)，只有Tag1響應(yīng)，標(biāo)簽被識別，閱讀器發(fā)送REQUEST (D3D1,11)，只有Tag8響應(yīng)，標(biāo)簽被識別。奇區(qū)域里的標(biāo)簽識別完。

(3)在偶區(qū)域里，只有Tag5一個(gè)標(biāo)簽自動識別。所有標(biāo)簽識別完畢，算法結(jié)束。

表2 碰撞位信息

表3 碰撞位信息

3 算法仿真

本文利用MATLAB 仿真工具，在相同實(shí)驗(yàn)條件下，將BSPP算法與QT算法、HQT算法進(jìn)行算法對比仿真驗(yàn)證。仿真結(jié)果如圖2所示，該改進(jìn)算法的各項(xiàng)性能有明顯改善。

圖2 算法仿真延時(shí)對比

4 結(jié)束語

本文在多周期奇偶分組的基礎(chǔ)上，利用標(biāo)簽ID中“1”的個(gè)數(shù)分為奇區(qū)域和偶區(qū)域兩組。對標(biāo)簽的分支進(jìn)行縮減，即減少了閱讀器的搜索次數(shù)，提高了閱讀器的識別效率。同時(shí)該算法縮短了系統(tǒng)的傳輸數(shù)據(jù)量以及傳輸時(shí)間，提高標(biāo)簽識別效率。該改進(jìn)算法的優(yōu)勢將會隨著標(biāo)簽數(shù)目和比特位的增加而越來越明顯。

[1] 馮旺,張磊,張琨.多時(shí)隙樹的RFID 防碰撞算法[J].計(jì)算機(jī)仿真,2015,32(8):298-305.

[2] 王偉.射頻識別(RFID)技術(shù)及其應(yīng)用的研究[J].安徽師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,31(2):139-149.

[3] 嚴(yán)利輝,史長瓊,陳蓉,等.基于奇偶分組的多周期RFID標(biāo)簽防碰撞算法[J].計(jì)算機(jī)工程,2016,42(2):312-315.

(編校 左葛生)

A RFID Anti-Collision Algorithm Based on Parity Group

XUHang,DENGHong-wei，SUNYan-ping，LIAOJin-yun，YANGGui，PENGLi-rong

(College of Computer Science and Technology,Hengyang Normal University,Hengyang Hunan 421002,China)

Basis on the algorithm in the hybrid query tree algorithm and using the tag,ID is divided into odd and even number 1 in the area in the two groups.In the odd or even area according to the label ID sequence of number 1 in the top three,label is included in the four slots respectively to respond amd reduce tag collision.Performance analysis results showed that the algorithm is better than that of QT,HQT algorithm,reduces the amount of communication traffic and the label recognition efficiency is improved significantly.

parity group; area; accidentally area; collision algorithm

2015-06-08

國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510546003) ；湖南省大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性實(shí)驗(yàn)計(jì)劃項(xiàng)目(2015372)

許航(1995-)，男，江蘇南京人，衡陽師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)13級本科生。

*通訊作者：鄧紅衛(wèi)(1970-)，男，湖南祁陽人，副教授，碩士,CCF會員，主要研究方向?yàn)橛?jì)算機(jī)通信網(wǎng)絡(luò)、嵌入式系統(tǒng)。

TP312.8

A

1673-0313(2016)06-0171-03