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

許 航，鄧紅衛，孫艷平, 廖瑾蕓，楊 桂，彭麗蓉

(衡陽師范學院 計算機科學與技術學院，湖南 衡陽 421002)

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

許 航，鄧紅衛*，孫艷平, 廖瑾蕓，楊 桂，彭麗蓉

(衡陽師范學院 計算機科學與技術學院，湖南 衡陽 421002)

本算法在混合查詢樹算法的基礎上，利用標簽ID中“1”的個數分為奇區域和偶區域兩組。在奇區域或偶區域中根據標簽ID序列的前三位中“1”的個數，將標簽放入四個時隙中分別進行響應，減少標簽碰撞。性能分析結果表明，該算法優于QT、HQT算法，提高了 標簽識別的效率。

奇偶分組；奇區域；偶區域；防碰撞算法

1 RFID防碰撞算法

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

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

2 改進的奇偶搜索防碰撞算法

2.1 算法指令約定

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

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

(2) 選擇指令SELECT。SELECT(ID)選擇編號為ID的RFID標簽，準備讀出或寫入RFID標簽中的數據。

(3) 讀指令READ。READ(ID) 讀出編號為ID標簽中的數據。

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

2.2 算法描述

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

(1)假設閱讀器識別范圍內有N個等待識別的標簽，閱讀器首先發送REQUEST (bit)，所有標簽都響應，根據標簽ID序列中“1”的個數是奇數還是偶數，分到相應的奇區域或偶區域中。

(2)在奇區域或偶區域中根據標簽ID序列的前三位“1”的個數分為0(000)、1(001、010、100)、2(011、101、110)、3(111)四個時隙。判斷時隙中標簽的響應情況。

(3)如果時隙中沒有標簽響應，則為空時隙；進入第(8)步。

(4)如果時隙中只有一個標簽響應，則直接識別該標簽；使用UNSELECT指令屏蔽該標簽。否則，進入第⑻步。

(5)如果時隙中有兩個及以上的標簽響應，則此時隙中發生了碰撞，從中得到碰撞位的位數，如果碰撞位的位數小于等于2位，則直接識別標簽；如果碰撞位的位數大于2位，再判斷碰撞位的位數是奇數個還是偶數個。如果是奇數個，進入第⑹步，如果是偶數個，進入第⑺步。

(6)對最中間的那一位碰撞位賦值0或1，判斷響應的標簽是否還有碰撞位？是，則進入第(5)步；否，則識別標簽。此時隙中標簽是否識別完？是，則進入第⑻步；否，則繼續識別。

(7)對中間的兩位碰撞位賦值00或01或10或11組合，判斷響應的標簽是否還有碰撞位？是，則進入第(5)步；否，則識別標簽。此時隙中標簽是否識別完？是，則進入第⑻步；否，則繼續識別。

(8)識別下一個時隙。

(9)兩個區域中每個時隙是否都為空。為空則表明N個標簽全部識別，算法結束；否則返回到第(2)步。

2.3 算法流程

圖1 算法流程圖

2.4 算法舉例

下面通過一個實例來分析新算法的工作原理。閱讀器作用范圍內有8個待識別的標簽，如表1所示。

表1 曼徹斯特編碼

算法的工作原理如下：

(1)閱讀器發送REQUEST(11111111)，閱讀器識別范圍內的所有標簽都響應，根據標簽ID中“1”的個數是奇數還是偶數分為奇區域和偶區域，可知偶區域中只有Tag5；奇區域中有Tag1、Tag2、Tag3、Tag4、Tag6、Tag7、Tag8。

(2)在奇區域中，根據標簽ID前三位分的四個時隙可知Tag4在0時隙里。Tag2、Tag6、Tag7在1時隙里，Tag1、Tag3、Tag8在2時隙里。3時隙里沒有標簽響應，為空時隙。0時隙里只有Tag4 1個標簽則直接識別。1時隙里的三個標簽的碰撞信息如表2所示，碰撞位的位數為5位，最中間的碰撞位為D4，則閱讀器發送REQUEST(D4，0)，Tag2和Tag6響應，得到的解碼為1000XX01，即Tag2和Tag6只有兩個碰撞位，能直接識別。(因為是在奇區域里，所以可以肯定產生碰撞的兩個標簽為10000101、10001001)。閱讀器發送REQUEST(D4，1)，只有Tag7響應，標簽被識別。1時隙里的標簽識別完。接著識別2時隙里的標簽，2時隙里的三個標簽的碰位信息如表3所示。碰撞位的位數為4位，中間兩位碰撞位為D3和D1，則閱讀器發送REQUEST(D3D1，00)，沒有標簽響應，閱讀器發送REQUEST(D3D1，01)，只有Tag3響應，標簽被識別，閱讀器發送REQUEST(D3D1，10)，只有Tag1響應，標簽被識別，閱讀器發送REQUEST (D3D1,11)，只有Tag8響應，標簽被識別。奇區域里的標簽識別完。

(3)在偶區域里，只有Tag5一個標簽自動識別。所有標簽識別完畢，算法結束。

表2 碰撞位信息

表3 碰撞位信息

3 算法仿真

本文利用MATLAB 仿真工具，在相同實驗條件下，將BSPP算法與QT算法、HQT算法進行算法對比仿真驗證。仿真結果如圖2所示，該改進算法的各項性能有明顯改善。

圖2 算法仿真延時對比

4 結束語

本文在多周期奇偶分組的基礎上，利用標簽ID中“1”的個數分為奇區域和偶區域兩組。對標簽的分支進行縮減，即減少了閱讀器的搜索次數，提高了閱讀器的識別效率。同時該算法縮短了系統的傳輸數據量以及傳輸時間，提高標簽識別效率。該改進算法的優勢將會隨著標簽數目和比特位的增加而越來越明顯。

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

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

[3] 嚴利輝,史長瓊,陳蓉,等.基于奇偶分組的多周期RFID標簽防碰撞算法[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

國家級大學生創新創業訓練計劃項目(201510546003) ；湖南省大學生研究性學習和創新性實驗計劃項目(2015372)

許航(1995-)，男，江蘇南京人，衡陽師范學院計算機科學與技術專業13級本科生。

*通訊作者：鄧紅衛(1970-)，男，湖南祁陽人，副教授，碩士,CCF會員，主要研究方向為計算機通信網絡、嵌入式系統。

TP312.8

A

1673-0313(2016)06-0171-03