一種改進的動態(tài)二進制防碰撞算法

岳青青

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

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

DOIDOI：10.11907/rjdk.172434

中圖分類號：TP312

文獻標識碼：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)點，是一種便捷、快速的信息識別技術(shù)。因此，該技術(shù)廣泛應(yīng)用于生產(chǎn)制造、交通物流、醫(yī)療管理、自動化、校園管理等各個領(lǐng)域。當(dāng)閱讀器的閱讀范圍出現(xiàn)兩個以上標簽發(fā)送標簽信息時，由于信息間的相互干擾，導(dǎo)致閱讀器無法正確識別每一個標簽發(fā)送的數(shù)據(jù)信息，即出現(xiàn)了標簽信息碰撞問題。

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

1算法約定

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

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

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

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

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

2改進的防碰撞算法

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

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

3算法原理實例

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

tag1：00010011tag2：11111100tag3：10010101

tag4：01100100tag5：01110101

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

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

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

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

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

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

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

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

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

4算法比較與分析

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

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

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

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

5結(jié)語

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

參考文獻參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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