確定型標(biāo)簽防碰撞算法研究綜述

張德慧+李政

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

關(guān)鍵詞：RFID；標(biāo)簽防碰撞技術(shù)；確定型標(biāo)簽防碰撞算法

中圖分類號：TP312 文獻標(biāo)志碼：A

0 引言

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

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

1 確定型標(biāo)簽防碰撞算法

1.1 二進制搜索樹算法

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

總的搜索次數(shù)為式（1）所示，其中，N為待測標(biāo)簽總數(shù)量。

（1）

標(biāo)簽識別完畢傳輸?shù)目傂畔⒘繛槭剑?）所示：

（2）

1.2 動態(tài)二進制搜索樹算法

動態(tài)二進制搜索樹算法在二進制搜索樹算法的基礎(chǔ)上，保留算法思想，但減少了通信傳輸?shù)男畔⒘浚瑱z測到碰撞位時，碰撞位后面的所有二進制位全都成為冗余數(shù)據(jù)，步驟與二進制搜索樹算法類似。依舊以上述4個標(biāo)簽為例，其動態(tài)二進制搜索樹算法搜索過程可見表2。

標(biāo)簽識別完畢傳輸?shù)目傂畔⒘繛槭剑?）所示：

（3）

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

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

總的搜索次數(shù)為式（4）所示：

Sum=2N-1 （4）

標(biāo)簽識別完畢傳輸?shù)目傂畔⒘繛槭剑?）所示：

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

1.4 查詢樹算法

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

結(jié)語

通過以上分析，在幾種確定型標(biāo)簽防碰撞算法中，二進制搜索樹算法在實現(xiàn)上相對簡單，但是在執(zhí)行過程中，重復(fù)性工作較多，搜索次數(shù)大，且識別標(biāo)簽所需信息通信量高，增加了系統(tǒng)的負擔(dān)。動態(tài)二進制搜索樹算法在通信量方面明顯要低于BST算法，但搜索次數(shù)沒有減少，與二進制搜索算法的搜索次數(shù)相同?；赝耸蕉M制搜索樹算法不僅降低了搜索次數(shù)，還減少了信息通信量，但標(biāo)簽數(shù)量過多時，會增加系統(tǒng)搜索時間。查詢樹算法通信量少，但是隨著標(biāo)簽數(shù)量增多，二叉分支也會增多，直到檢測出沒有響應(yīng)的標(biāo)簽時，才終止查詢，增加系統(tǒng)的搜索時間。

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

參考文獻

[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].微型機與應(yīng)用，2017，36（8）：67-69.

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