岳青青

摘要：針對RIFD標(biāo)簽識別過程中的碰撞問題，在動態(tài)二進(jìn)制防碰撞算法基礎(chǔ)上提出一種改進(jìn)的防碰撞算法。該算法在動態(tài)二進(jìn)制算法基礎(chǔ)上結(jié)合了后退式二進(jìn)制算法，使閱讀器不用每次從頭開始發(fā)送請求命令，而且改進(jìn)算法中引入了計數(shù)器，以控制標(biāo)簽狀態(tài)信息。分析表明，該算法可以降低閱讀器發(fā)送請求的次數(shù)，同時可以減少標(biāo)簽識別所需的時間。

關(guān)鍵詞：射頻識別（RFID）；碰撞算法；動態(tài)二進(jìn)制；后退式二進(jìn)制

DOIDOI：10.11907/rjdk.172434

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）003008103

英文摘要Abstract：In this paper，in view of the occurrence of collision when identifying labels simultaneously in the RFID system，we introduced an improved dynamic binary anticollision algorithm.This algorithm combines the idea of dynamic binary algorithm and regressive binary algorithm，which avoid the reader starting sending request commands every time.In addition，the algorithm proposes a tag counter that control the status of tag.The analysis shows that the algorithm can reduce the number of times that the reader can send the request，and also reduce the time required to identify the label.

英文關(guān)鍵詞Key Words：Radio Frequency Identification （RFID）； collision algorithm； dynamic binary searching algorithm； regressive binary algorithm

0引言

RFID（Radio Frequency Identification）是一種通過射頻信號通信實現(xiàn)非接觸的自動識別技術(shù)。RFID具有存儲容量大、信息讀取速度快、范圍廣等優(yōu)點(diǎn)，是一種便捷、快速的信息識別技術(shù)。因此，該技術(shù)廣泛應(yīng)用于生產(chǎn)制造、交通物流、醫(yī)療管理、自動化、校園管理等各個領(lǐng)域。當(dāng)閱讀器的閱讀范圍出現(xiàn)兩個以上標(biāo)簽發(fā)送標(biāo)簽信息時，由于信息間的相互干擾，導(dǎo)致閱讀器無法正確識別每一個標(biāo)簽發(fā)送的數(shù)據(jù)信息，即出現(xiàn)了標(biāo)簽信息碰撞問題。

隨著RFID技術(shù)的普及，很多應(yīng)用場合都出現(xiàn)了碰撞問題，也成為了RFID系統(tǒng)應(yīng)用急需解決的關(guān)鍵問題[1]。防碰撞技術(shù)是解決碰撞問題、提高標(biāo)簽識別效率的關(guān)鍵技術(shù)，主要解決的是如何快速、準(zhǔn)確地從多個標(biāo)簽中選出一個與閱讀器進(jìn)行數(shù)據(jù)交流，而其它標(biāo)簽也以同樣方法與閱讀器進(jìn)行數(shù)據(jù)交流[23]。

1算法約定

RFID系統(tǒng)二進(jìn)制搜索算法采用曼徹斯特編碼方法，通過電平的改變表示數(shù)值位，用邏輯“0”表示上升沿跳變，邏輯“1”表示下降沿跳變。當(dāng)某一位不發(fā)生狀態(tài)跳變時，讀寫器即知道該位發(fā)生了碰撞，產(chǎn)生錯誤，從而進(jìn)行下一次循環(huán)。為了方便描述，使用如下不同的命令機(jī)制[4]：

（1）Request（請求）：閱讀器向識別區(qū)域內(nèi)的所有標(biāo)簽發(fā)送請求命令序列號ID，標(biāo)簽對該請求作出響應(yīng)。

（2）Select（選擇）：閱讀器發(fā)送特定的請求命令I(lǐng)D，經(jīng)過多次循環(huán)比較，只有與序列號ID相同的標(biāo)簽才能被選中。

（3）ReadDate（讀數(shù)據(jù)）：被選中的標(biāo)簽發(fā)送自身攜帶的信息，閱讀器接收來自該標(biāo)簽的編碼信息。

（4）Unselect（取消選擇）：對已經(jīng)讀寫完信息的標(biāo)簽取消選中狀態(tài)，使該標(biāo)簽進(jìn)入“休眠”狀態(tài)，對閱讀器之后發(fā)送的任何請求命令序列號，該標(biāo)簽不再作出響應(yīng)。

2改進(jìn)的防碰撞算法

防碰撞算法主要分為確定性的基于樹的防碰撞算法和概率性的基于ALOHA的防碰撞算法。在傳統(tǒng)二進(jìn)制搜索算法[5]中，當(dāng)標(biāo)簽的EPC小于閱讀器發(fā)送的命令I(lǐng)D時，標(biāo)簽才會響應(yīng)閱讀器命令，閱讀器每完成一個標(biāo)簽的識別，都會從頭開始搜索，每次傳輸?shù)臄?shù)據(jù)是全部長度的序列號。因此，學(xué)者們提出了許多改進(jìn)的二進(jìn)制防碰撞算法[68]。為了減少閱讀器每次發(fā)送的請求序列長度，N為標(biāo)簽EPC編碼的長度，X為標(biāo)簽碰撞的最高位。將最高碰撞位X置0，閱讀器只傳輸NX位作為下一次的請求序列號，即動態(tài)二進(jìn)制防碰撞算法[9]。為了減少閱讀器查詢次數(shù)，閱讀器每識別出一個標(biāo)簽，不是從根節(jié)點(diǎn)重新查詢，而是返回它的上一層，即后退式二進(jìn)制防碰撞算法[1011]。其特點(diǎn)是標(biāo)簽發(fā)生碰撞時，根據(jù)碰撞位中的最高位向前搜索，無碰撞時采用后退策略。

為了減少傳輸?shù)臄?shù)據(jù)長度，提高標(biāo)簽識別速度，將動態(tài)二進(jìn)制防碰撞算法與后退式二進(jìn)制防碰撞算法相結(jié)合，并加入計數(shù)器，用于控制標(biāo)簽狀態(tài)。當(dāng)標(biāo)簽不再發(fā)生碰撞或者被識別后，選擇鄰近節(jié)點(diǎn)，結(jié)合動態(tài)二進(jìn)制算法，使用最高碰撞位判斷，滿足最高碰撞位X為0的標(biāo)簽參與對閱讀器命令的響應(yīng)，否則被屏蔽。同時引入計數(shù)器，用于對被屏蔽標(biāo)簽狀態(tài)的管理。當(dāng)標(biāo)簽計數(shù)器中的狀態(tài)S<0時，說明該標(biāo)簽信息已經(jīng)被獲取，S=0時的標(biāo)簽才對閱讀器命令響應(yīng)，S>0時同樣對閱讀器發(fā)送的請求命令不響應(yīng)，改進(jìn)算法流程如圖1所示。

3算法原理實例

在改進(jìn)的動態(tài)二進(jìn)制防碰撞算法基礎(chǔ)上，通過實例分析算法的可行性。假設(shè)閱讀器的閱讀范圍內(nèi)有5個標(biāo)簽，標(biāo)簽EPC長度為8位。用X表示一個碰撞比特位。

tag1：00010011tag2：11111100tag3：10010101

tag4：01100100tag5：01110101

（1）閱讀器發(fā)送R（11111111），所有標(biāo)簽的計數(shù)器初始化值為S1=S2=S3=S4=S5=0，即所有標(biāo)簽對閱讀器發(fā)送的指令進(jìn)行響應(yīng)。標(biāo)簽在發(fā)送EPC編碼時發(fā)生碰撞，此時閱讀器的譯碼結(jié)果為XXXXXXXX。最高碰撞位為D7。

（2）閱讀器發(fā)送R（7，0），即判斷所有標(biāo)簽的D7位是否為0，標(biāo)簽D7位為0的標(biāo)簽響應(yīng)閱讀器發(fā)送的請求，其余標(biāo)簽被屏蔽并且計數(shù)器值加1。標(biāo)簽2與3被屏蔽，計數(shù)器值加1，即S2=S3=1。標(biāo)簽1、4、5發(fā)送信息時發(fā)生碰撞，譯碼結(jié)果為0XXX0XXX。最高碰撞位為D6。

（3）閱讀器發(fā)送R（6，0），標(biāo)簽D6位為0，且計數(shù)器值為0的標(biāo)簽響應(yīng)。只有標(biāo)簽1響應(yīng)，標(biāo)簽4與5被屏蔽，S2=S3=2，S4=S5=1。因此標(biāo)簽1被識別，與閱讀器進(jìn)行數(shù)據(jù)讀寫操作，完成后進(jìn)行Unselect操作，使標(biāo)簽1處于“休眠”狀態(tài)，不再參與信息響應(yīng)。同時所有標(biāo)簽計數(shù)器值減1，S2=S3=1，S4=S5=0。此時標(biāo)簽4、5處于等待狀態(tài)。

（4）閱讀器返回上一層發(fā)送R（6，1）命令。此時只有標(biāo)簽4、5對該請求命令進(jìn)行響應(yīng)，標(biāo)簽2、3被屏蔽，計數(shù)值加1，S2=S3=2。標(biāo)簽4、5發(fā)送信息給閱讀器，閱讀器譯碼結(jié)果為：011x010x，最高碰撞位為D4。

（5）閱讀器發(fā)送R（4，0），只有標(biāo)簽4對此命令響應(yīng)，5被屏蔽C5=1。標(biāo)簽與閱讀器進(jìn)行信息讀寫，標(biāo)簽4進(jìn)入“休眠”狀態(tài)。其余標(biāo)簽計數(shù)器減1，S2=S3=1，S5=0。

（6）閱讀器發(fā)送R（4，1），只有標(biāo)簽5響應(yīng)，標(biāo)簽5與閱讀器進(jìn)行信息讀寫，處于“休眠”狀態(tài)。標(biāo)簽計數(shù)器減1，S2=S3=0。

（7）通過后項搜索，發(fā)現(xiàn)只有碰撞位D7沒有進(jìn)行1檢測。閱讀器發(fā)送R（D7，1），只有標(biāo)簽2、3對閱讀器的命令響應(yīng)。標(biāo)簽2、3發(fā)生碰撞，閱讀器得到的譯碼結(jié)果為1XX1X10X，最高碰撞位為D6。

（8）閱讀器發(fā)送R（6，0），只有標(biāo)簽3響應(yīng)，標(biāo)簽2被屏蔽，S2=1。標(biāo)簽3與閱讀器進(jìn)行讀寫操作，并進(jìn)入“休眠”狀態(tài)。同時計數(shù)器S2為0。

（9）閱讀器發(fā)送R（6，1），只有唯一的標(biāo)簽2響應(yīng)，并進(jìn)行數(shù)據(jù)的讀寫等操作，此時所有標(biāo)簽都已經(jīng)識別完畢。

4算法比較與分析

只使用5個標(biāo)簽的EPC編碼，將改進(jìn)算法與動態(tài)二進(jìn)制算法進(jìn)行對比。使用的標(biāo)簽為tag1：00010001，tag2：11111100，tag3：10010101，tag4：01110100，tag5：01110101。

動態(tài)二進(jìn)制搜索算法整個搜索過程如表1所示。改進(jìn)的動態(tài)二進(jìn)制算法實施過程如表2所示。

通過表1、表2的分析，兩種算法無論是閱讀器搜索次數(shù)、標(biāo)簽碰撞次數(shù)還是閱讀器發(fā)送指令的長度，改進(jìn)的二進(jìn)制動態(tài)算法都較原有的動態(tài)二進(jìn)制算法有一定提升。

閱讀器發(fā)送的指令更加簡潔，碰撞次數(shù)也隨之減少，其中改進(jìn)算法中采用的計數(shù)器控制標(biāo)簽狀態(tài)，使每次參與閱讀器指令響應(yīng)的標(biāo)簽數(shù)量減少，縮短了標(biāo)簽響應(yīng)時間。

5結(jié)語

本文在動態(tài)二進(jìn)制防碰撞算法基礎(chǔ)上提出改進(jìn)的動態(tài)二進(jìn)制防碰撞算法，該算法結(jié)合了原始動態(tài)二進(jìn)制和后退式二進(jìn)制兩種算法，并且加入了標(biāo)簽計數(shù)器。利用計數(shù)器的3種狀態(tài)排除在請求外的標(biāo)簽則不再響應(yīng)，減少了內(nèi)部干擾，從而減少了算法搜索次數(shù)。同時將標(biāo)簽發(fā)送的請求命令形式簡化，縮短了閱讀器發(fā)送指令的長度與時間。因此，改進(jìn)的算法具有一定優(yōu)勢。

參考文獻(xiàn)參考文獻(xiàn)：

[1]趙斌，張紅雨.RFID技術(shù)的應(yīng)用與發(fā)展[J].電子設(shè)計工程，2012，18（10）：123126.

[2]謝振華，賴聲禮，陳鵬.RFID技術(shù)和防沖撞算法[J].計算機(jī)工程與應(yīng)用，2007，43（6）：223225.

[3]張友能.射頻識別系統(tǒng)中的防沖突算法研究[J].國外電子元器件，2008（12）：7174.

[4]高金輝，鄭曉彥.RFID系統(tǒng)中二進(jìn)制搜索防碰撞改進(jìn)算法[J].計算機(jī)測量與控制，2012，20（10）：27542756.

[5]魯玉軍，吳遠(yuǎn).RFID系統(tǒng)二進(jìn)制防碰撞算法的研究[J].工業(yè)控制計算機(jī)，2015，28（5）：6264.

[6]楊曉嬌，閆斌，謝光斌.一種改進(jìn)的二進(jìn)制防碰撞算法[J].計算機(jī)應(yīng)用與軟件，2013，30（10）：312316.

[7]潘磊，諶貴輝，李柯.二進(jìn)制防碰撞算法在RFID系統(tǒng)中的改進(jìn)研究[J].自動化與儀器儀表，2015，35（7）：161163.

[8]張鳴.RFID系統(tǒng)中改進(jìn)的二進(jìn)制防碰撞算法[J].工業(yè)控制計算機(jī)，2016，29（5）：2932.

[9]蘇俊，王忠，陳和恒.基于動態(tài)二進(jìn)制改進(jìn)算法的RFID防碰撞算法[J].測控技術(shù)，2015，34（2）：111114.

[10]樊文靜，張珊珊，田智慧.基于后退式二進(jìn)制搜索的RFID防碰撞算法的研究[J].計算機(jī)應(yīng)用與軟件，2012，29（5）：191194.

[11]豐碩，高飛，薛艷明，等.一種改進(jìn)的RFID標(biāo)簽防碰撞算法[J].微計算機(jī)信息，2011，27（1）：4952.

責(zé)任編輯（責(zé)任編輯：黃健）