基于二進(jìn)制的RFID防碰撞算法研究與改進(jìn)

蔣霞　白鐵成　鄭洪江

摘要：標(biāo)簽防碰撞技術(shù)是射頻識(shí)別（ RFID） 系統(tǒng)中提高標(biāo)簽識(shí)別效率的關(guān)鍵技術(shù)。在對(duì)基本二進(jìn)制搜索算法（BS）的基礎(chǔ)上，提出一種結(jié)合動(dòng)態(tài)二進(jìn)制搜索算法（DBS）和后退式二進(jìn)制搜索算法（BBS）優(yōu)點(diǎn)的改進(jìn)算法，并對(duì)改進(jìn)算法進(jìn)一步優(yōu)化。仿真結(jié)果表明，該算法能減少閱讀器問(wèn)詢標(biāo)簽的數(shù)據(jù)量，有效地提高了標(biāo)簽識(shí)別的速度。

關(guān)鍵詞：RFID；防碰撞；二進(jìn)制搜索

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）09-2209-02

無(wú)線射頻識(shí)別RFID是一種非接觸式自動(dòng)識(shí)別技術(shù)。因其具有識(shí)別速度快、距離遠(yuǎn)，抗干擾能力強(qiáng)等優(yōu)點(diǎn)，被廣泛應(yīng)用于物品管理、物流等領(lǐng)域。

RFID系統(tǒng)主要由標(biāo)簽、閱讀器及計(jì)算機(jī)系統(tǒng)三部分組成。每個(gè)標(biāo)簽擁有唯一的序列號(hào)ID。RFID 系統(tǒng)中多個(gè)標(biāo)簽可能會(huì)處于同一閱讀器識(shí)別范圍內(nèi)，當(dāng)多個(gè)標(biāo)簽同時(shí)響應(yīng)閱讀器時(shí)會(huì)產(chǎn)生信號(hào)干擾，致使閱讀器無(wú)法正確識(shí)別標(biāo)簽，也即發(fā)生了標(biāo)簽碰撞。碰撞導(dǎo)致了標(biāo)簽被漏讀，因此必須采用防碰撞策略來(lái)避免碰撞發(fā)生，識(shí)別全部標(biāo)簽。

1 基于二進(jìn)制RFID防碰撞算法

二進(jìn)制防碰撞算法是將碰撞的標(biāo)簽分成左右兩個(gè)子集，先查詢左子集0，若沒(méi)有碰撞，則正確識(shí)別標(biāo)簽，如若仍有碰撞就再繼續(xù)進(jìn)行分裂，分成00和01兩個(gè)子集，依次類推，直到識(shí)別出左子集0中的全部標(biāo)簽，再按此步驟查詢右子集1。

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

在BS算法中，閱讀器查詢的不是一個(gè)比特，而是一個(gè)比特前綴，只有標(biāo)簽與這個(gè)查詢前綴相符的標(biāo)簽才能響應(yīng)閱讀器的命令。當(dāng)只有一個(gè)標(biāo)簽響應(yīng)的時(shí)候，閱讀器可以成功識(shí)別標(biāo)簽，但有多個(gè)標(biāo)簽響應(yīng)的時(shí)，發(fā)生碰撞。 為了最簡(jiǎn)捷地實(shí)現(xiàn)二進(jìn)制搜索算法，數(shù)據(jù)編碼選用Machenster編碼，依據(jù)其編碼特點(diǎn)可以檢測(cè)出碰撞位。

要從大量的標(biāo)簽中識(shí)別出唯一的標(biāo)簽，需要重復(fù)搜索操作。其識(shí)別的平均操作次數(shù)由閱讀器范圍內(nèi)的標(biāo)簽總數(shù)n決定[1]：

利用BS算法可以較簡(jiǎn)單地解決碰撞問(wèn)題，但隨著標(biāo)簽數(shù)量的增多，重復(fù)操作的平均值很快增加。完成n個(gè)標(biāo)簽識(shí)別需要的總問(wèn)詢次數(shù)如下公式所示：

所有標(biāo)簽都需要發(fā)送完整的序列號(hào)來(lái)響應(yīng)閱讀器的問(wèn)詢。識(shí)別n個(gè)序列號(hào)為k位的標(biāo)簽，閱讀器需要傳輸?shù)目偙忍財(cái)?shù)為標(biāo)簽序列號(hào)長(zhǎng)度與算法總搜索次數(shù)的乘積

1.2 動(dòng)態(tài)二進(jìn)制搜索（DBS）算法

上述BS算法雖然簡(jiǎn)單，但其不僅搜索范圍較大，而且在閱讀器問(wèn)詢和標(biāo)簽回應(yīng)時(shí)序列號(hào)要全部傳輸。標(biāo)簽序列號(hào)可能長(zhǎng)達(dá)12個(gè)字節(jié)，為了選擇一個(gè)標(biāo)簽，所以數(shù)據(jù)傳輸量較大。因而DBS 算法被提出。

如果研究閱讀器和單個(gè)標(biāo)簽之間傳輸?shù)臄?shù)據(jù)，就可以得出以下結(jié)果。假設(shè)H為最高碰撞位，標(biāo)簽序列號(hào)長(zhǎng)度為K。

⑴ 請(qǐng)求命令（H-1）～0位中不包含任何給標(biāo)簽的補(bǔ)充信息，因?yàn)楦魑豢偸潜恢脼椤?”。

⑵ 標(biāo)簽應(yīng)答的序列號(hào)的K～H位不包含任何給閱讀器的補(bǔ)充信息，因?yàn)檫@些位是閱讀器已經(jīng)給定的。

由于DBS與BS使用相似的搜索過(guò)程，故可以得出的DBS算法總搜索次數(shù)。

DBS算法識(shí)別標(biāo)簽時(shí)，首先要求作用范圍內(nèi)的所有標(biāo)簽都上傳各自的序列號(hào)，n個(gè)標(biāo)簽的序列號(hào)總長(zhǎng)度就是第一次上傳的數(shù)據(jù)長(zhǎng)度，即整個(gè)序列號(hào)長(zhǎng)度作為傳輸比特?cái)?shù)。閱讀器識(shí)別搜索一次傳輸平均數(shù)據(jù)量為[2]

當(dāng)閱讀器使用DBS算法時(shí)，識(shí)別n個(gè)標(biāo)簽所需要傳輸?shù)男蛄刑?hào)總長(zhǎng)度為

1.3 基于后退索引的二進(jìn)制搜索（BBS）算法

BBS算法中，閱讀器完成一個(gè)標(biāo)簽的識(shí)別后，返回上一次發(fā)生碰撞的節(jié)點(diǎn)[3]，識(shí)別該節(jié)點(diǎn)的另外一個(gè)分枝，不斷重復(fù)操作，直到把上一節(jié)點(diǎn)碰撞的標(biāo)簽識(shí)別完。其識(shí)別n個(gè)標(biāo)簽，閱讀器共需問(wèn)詢2*n-1次。假設(shè)標(biāo)簽序列號(hào)長(zhǎng)度為kbit，則在閱讀器的發(fā)送的數(shù)據(jù)量為（2*n-1）*kbit。BBS的優(yōu)點(diǎn)是減少了問(wèn)詢次數(shù)，而DBS的優(yōu)點(diǎn)是減少了問(wèn)詢中參數(shù)長(zhǎng)度，如果能將兩者的優(yōu)勢(shì)結(jié)合，必能提高性能。該文提出了以下改進(jìn)算法。

1.4 返回式動(dòng)態(tài)二進(jìn)制算法BDBS

下面以4個(gè)標(biāo)簽為例（10110011、10100011、10110010、11100011），首先引一條命令REQUEST命令，即REQUEST（ID（K～X），X），X為碰撞的最高位，其作用是讓閱讀器發(fā)送一個(gè)參數(shù)（標(biāo)簽的第K-H位）給區(qū)域內(nèi)標(biāo)簽，序列號(hào)K～H位與之一致標(biāo)簽傳輸剩余的（H-1）～0位信息作為應(yīng)答。閱讀器完成一個(gè)標(biāo)簽的識(shí)別后，返回上一次發(fā)生碰撞的節(jié)點(diǎn)，識(shí)別該節(jié)點(diǎn)的另外一個(gè)分枝，不斷重復(fù)操作，直到把上一節(jié)點(diǎn)碰撞的標(biāo)簽識(shí)別完。算法的執(zhí)行過(guò)程如下：

第①步，閱讀器發(fā)送REQUEST（NUL，8），處于閱讀器作用范圍的所有標(biāo)簽都返回其ID給閱讀器，解碼數(shù)據(jù)為1X1X001X，碰撞最高位是D6，將D6置“0”，高位不變，得到ID（K～H）取10，H取6作為下一次命令所需的兩個(gè)參數(shù)。

第②步，閱讀器發(fā)送REQUEST（10，6），序列號(hào)前綴為10的標(biāo)簽響應(yīng)，即標(biāo)簽10110010、10100011和10110011響應(yīng)。各自返回后6位的信息110010、100011、110011。閱讀器得到解碼數(shù)據(jù)為1X001X，將碰撞最高位D4置為“0”。

第③步，閱讀器發(fā)送REQUEST（1010，4），序列號(hào)前綴為1010的標(biāo)簽響應(yīng)，只有標(biāo)簽10100011響應(yīng)，無(wú)碰撞發(fā)生，讀寫器處理完該標(biāo)簽后對(duì)它進(jìn)行屏蔽。

第④步：從該節(jié)點(diǎn)的父節(jié)點(diǎn)獲得下一次REQUEST指令參數(shù)，閱讀器發(fā)送REQUEST（1011，4）。標(biāo)簽1和標(biāo)簽3應(yīng)答，閱讀器解碼數(shù)據(jù)為001X。

第⑤步：閱讀器發(fā)送REQUEST（10110010，0）指令，標(biāo)簽3應(yīng)答。閱讀器對(duì)標(biāo)簽3進(jìn)行處理后使其進(jìn)入“無(wú)聲”狀態(tài)。

第⑥步：閱讀器發(fā)送REQUEST（10110011，0）指令，只有標(biāo)簽1應(yīng)答。閱讀器對(duì)標(biāo)簽1進(jìn)行處理后使其進(jìn)入“無(wú)聲”狀態(tài)。采用返回策略，返回到最上一個(gè)父節(jié)點(diǎn)11。

第⑦步：閱讀器發(fā)送REQUEST（11，6）指令，標(biāo)簽4應(yīng)答，閱讀器讀取標(biāo)簽4的數(shù)據(jù)，識(shí)別過(guò)程結(jié)束。

在BDBS算法中，閱讀器的搜索次數(shù)為2n-1，閱讀器傳輸每次搜索平均傳輸?shù)臄?shù)據(jù)量為（k+1）/2，所以閱讀器識(shí)別所有標(biāo)簽所需要發(fā)送的數(shù)據(jù)量為

對(duì)于BDBS搜索算法，當(dāng)標(biāo)簽數(shù)量較多時(shí)，比BBS通信量減少近50%，比DBS減少約67%，比BS減少達(dá)到80%。如仿真圖1所示。

1.5 改進(jìn)的BDBS

在標(biāo)簽碰撞位只有一位時(shí)，說(shuō)明只有兩個(gè)標(biāo)簽發(fā)生碰撞，則認(rèn)為沒(méi)有發(fā)生碰撞。一個(gè)標(biāo)簽的碰撞位為“0”。另一個(gè)標(biāo)簽的碰撞位為“1”，直接識(shí)別標(biāo)簽。則閱讀器的搜索次數(shù)減少為（2n-1）-[n/2]（[]為向上取整），則完成n個(gè)標(biāo)簽問(wèn)詢，閱讀器所需發(fā)送的數(shù)據(jù)量為

對(duì)閱讀器的問(wèn)詢通信數(shù)據(jù)量進(jìn)行比較。如圖2所示，數(shù)據(jù)量較BDBS減少了約25%，性能得到了提高。

2 結(jié)論

本文提出了一種改進(jìn)的二進(jìn)制搜索算法，通過(guò)分析仿真和比較，得出該算法優(yōu)于二進(jìn)制搜索算法BS，隨著標(biāo)簽數(shù)量的增加優(yōu)勢(shì)更加明顯。極大地減小了閱讀器問(wèn)詢識(shí)別范圍內(nèi)標(biāo)簽的通信量，提高了標(biāo)簽的識(shí)別速度。

參考文獻(xiàn)：

[1] 鞠偉成，俞承芳.一種基于動(dòng)態(tài)二進(jìn)制的RFID抗沖突算法[J].復(fù)旦學(xué)報(bào)自然科學(xué)版，2005.

[2] 周曉光，王曉華.射頻識(shí)別（RFID）技術(shù)原理與應(yīng)用實(shí)例[M].北京：人民郵電出版社，2006.

[3] 鞠偉成，俞承芳.一種基于動(dòng)態(tài)二進(jìn)制二進(jìn)制的RFID 抗沖突算法[J].復(fù)旦學(xué)報(bào)，2005：46-50.