一種改進的動態二進制防碰撞算法

岳青青

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

關鍵詞：射頻識別（RFID）；碰撞算法；動態二進制；后退式二進制

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.

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

0引言

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

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

1算法約定

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

（1）Request（請求）：閱讀器向識別區域內的所有標簽發送請求命令序列號ID，標簽對該請求作出響應。

（2）Select（選擇）：閱讀器發送特定的請求命令ID，經過多次循環比較，只有與序列號ID相同的標簽才能被選中。

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

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

2改進的防碰撞算法

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

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

3算法原理實例

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

tag1：00010011tag2：11111100tag3：10010101

tag4：01100100tag5：01110101

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

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

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

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

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

（6）閱讀器發送R（4，1），只有標簽5響應，標簽5與閱讀器進行信息讀寫，處于“休眠”狀態。標簽計數器減1，S2=S3=0。

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

（8）閱讀器發送R（6，0），只有標簽3響應，標簽2被屏蔽，S2=1。標簽3與閱讀器進行讀寫操作，并進入“休眠”狀態。同時計數器S2為0。

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

4算法比較與分析

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

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

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

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

5結語

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

參考文獻參考文獻：

[1]趙斌，張紅雨.RFID技術的應用與發展[J].電子設計工程，2012，18（10）：123126.

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

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

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

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

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

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

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

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

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

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

責任編輯（責任編輯：黃健）