確定型標簽防碰撞算法研究綜述

張德慧+李政

摘 要：確定型標簽防碰撞算法是無線射頻識別（Radio Frequency Identification，RFID）技術中一種關鍵性的標簽防碰撞算法，可100%識別完畢所有待測標簽。本文對確定型標簽防碰撞算法的核心思想進行深入探討，總結歸納不同確定型標簽防碰撞算法的優缺點，結合現狀，提出下一步研究方向。

關鍵詞：RFID；標簽防碰撞技術；確定型標簽防碰撞算法

中圖分類號：TP312 文獻標志碼：A

0 引言

RFID技術是一種非接觸式的自動識別技術，在“萬物皆可通過網絡互聯”的物聯網時代，RFID技術以其自身獨特的優勢，如：閱讀器可同時識別大量標簽、標簽信息可重復利用、標簽體積形狀多樣化等，成為物聯網中物體身份識別的關鍵技術。一個完整RFID系統由閱讀器、標簽和計算機系統組成。計算機系統向閱讀器傳達讀取標簽指令后，閱讀器便發送該指令給處于其自身范圍內的所有標簽，激活的標簽立即與閱讀器建立通信。通信過程中，由于標簽數量過多，容易產生信號沖突。因此，本文就標簽碰撞問題研究標簽防碰撞算法。

目前，標簽防碰撞算法主要從4個方面入手空分多址（Space Division Multiple Access，SDMA），碼分多址（Code Division Multiple Access，CDMA），頻分多址（Frequency Division Multiple Access，FDMA），時分多址（Time Division Multiple Access，TDMA）。其中，TDMA是把整個通路容量按時間劃分給多個用戶，也是現在RFID標簽防碰撞算法領域應用最為廣泛的劃分方式。基于TDMA技術的特點，又將標簽防碰撞算法分為兩類：一類是概率型的標簽防碰撞算法，該算法中，標簽通過隨機選擇時間點來響應閱讀器，算法雖然簡單易執行，但是容易造成“標簽饑餓”現象。另一類是確定型的標簽防碰撞算法，主要分為4種：二進制搜索樹算法、動態二進制搜索樹算法、回退式二進制搜索樹算法、查詢樹算法，該類算法通過二進制編碼逐一選擇標簽進行通信，可100%識別完所有待測標簽，避免“標簽饑餓”現象。

1 確定型標簽防碰撞算法

1.1 二進制搜索樹算法

閱讀器向在它范圍內的所有標簽發送二進制位全為1的搜索指令，該指令長度與標簽ID號長度相同。被激活的標簽會將自身ID號位數與指令中的每一位進行比較。若ID號小于或等于該二進制指令，則對閱讀器進行響應，下一次的讀取指令與初始指令相同；否則，檢測最高碰撞位，并將該位從“1”置為“0”，碰撞位之前的位數保持不變，作為下一次的搜索指令。直至標簽全部搜索完畢，查詢結束。假設有4個標簽，分別為標簽A：11010111、標簽B：11100101、標簽C：11101111、標簽D：11010101，其二進制搜索樹算法搜索過程可見表1。

總的搜索次數為式（1）所示，其中，N為待測標簽總數量。

（1）

標簽識別完畢傳輸的總信息量為式（2）所示：

（2）

1.2 動態二進制搜索樹算法

動態二進制搜索樹算法在二進制搜索樹算法的基礎上，保留算法思想，但減少了通信傳輸的信息量，檢測到碰撞位時，碰撞位后面的所有二進制位全都成為冗余數據，步驟與二進制搜索樹算法類似。依舊以上述4個標簽為例，其動態二進制搜索樹算法搜索過程可見表2。

標簽識別完畢傳輸的總信息量為式（3）所示：

（3）

1.3 回退式二進制搜索樹算法

回退式二進制搜索樹算法算法以二進制搜索樹算法為基礎，修改了二進制搜索樹算法的搜索規則，該算法中，每當閱讀器成功識別一個標簽之后，都要重新發一個二進制位數全為“1”的搜索指令，增加了總的查詢次數。回退式二進制搜索樹算法為了改進該弊端，在一個標簽被成功讀取之后，不會再重新發送一個二進制位數全為“1”的搜索指令，而是依據上一輪的搜索指令，將上一輪中的碰撞位從“0”修改為“1”，進行下一輪的標簽讀取。每一輪標簽讀取的命令碼長度與標簽ID號長度相同，依舊以上述4個標簽為例，其回退式二進制搜索樹算法搜索過程見表3。

總的搜索次數為式（4）所示：

Sum=2N-1 （4）

標簽識別完畢傳輸的總信息量為式（5）所示：

Ctraffic=2L（2N-1） （5）

1.4 查詢樹算法

查詢樹算法與之前的二進制搜索樹算法、動態二進制搜索樹算法和回退式二進制搜索樹算法有所不同，閱讀器在發送查詢標簽的初始化命令碼時，會根據標簽的ID特征，發送長度為K的前綴碼，不再是發送和標簽ID號相同的序列長度，被激活的標簽將自己ID號的前K位與該前綴碼相比較，若相同，則標簽與閱讀器建立通信，并把第“K+1”位至最后一位發送給閱讀器，此時標簽識別成功。若多個標簽ID號的前K位與前綴碼相同，則發生碰撞。假設標簽為標簽A：0010、標簽B：1110、標簽C：0001、標簽D：1101其查詢樹算法搜索過程見表4。

結語

通過以上分析，在幾種確定型標簽防碰撞算法中，二進制搜索樹算法在實現上相對簡單，但是在執行過程中，重復性工作較多，搜索次數大，且識別標簽所需信息通信量高，增加了系統的負擔。動態二進制搜索樹算法在通信量方面明顯要低于BST算法，但搜索次數沒有減少，與二進制搜索算法的搜索次數相同。回退式二進制搜索樹算法不僅降低了搜索次數，還減少了信息通信量，但標簽數量過多時，會增加系統搜索時間。查詢樹算法通信量少，但是隨著標簽數量增多，二叉分支也會增多，直到檢測出沒有響應的標簽時，才終止查詢，增加系統的搜索時間。

目前，針對確定型算法的研究主要集中在查詢樹算法上，眾多研究學者通過對查詢樹中二叉樹或者多叉樹動態結合，來達到減少查詢次數、降低信息通信量的目的。因此，為了后續的研究能夠高效快速的開展，建議針對確定型標簽防碰撞算法中的查詢樹算法重點研究，以取得更優良的算法。

參考文獻

[1]Ying-Meng H U， Zhang X H. Research of an Adaptive Searching Anti-collision Algorithm for RFID Based on Information-Bit Encoding[J]. Acta Electronica Sinica， 2016.

[2]楊曉嬌，吳必造.射頻識別中確定性防碰撞算法研究[J].微型機與應用，2017，36（8）：67-69.

[3]丁治國，雷迎科.基于優先級避讓的防碰撞算法研究[J].計算機應用研究，2016，33（3）：836-839.endprint