張德慧+李政

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

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

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A

0 引言

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

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

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

1.1 二進(jìn)制搜索樹(shù)算法

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

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

（1）

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

（2）

1.2 動(dòng)態(tài)二進(jìn)制搜索樹(shù)算法

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

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

（3）

1.3 回退式二進(jìn)制搜索樹(shù)算法

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

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

Sum=2N-1 （4）

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

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

1.4 查詢樹(shù)算法

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

結(jié)語(yǔ)

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

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

參考文獻(xiàn)

[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]楊曉嬌，吳必造.射頻識(shí)別中確定性防碰撞算法研究[J].微型機(jī)與應(yīng)用，2017，36（8）：67-69.

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