基于二進(jìn)制搜索的RFID 標(biāo)簽防碰撞算法研究

蔣 霞 白鐵成 鄭洪江

(塔里木大學(xué)信息工程學(xué)院，新疆 阿拉爾 843300)

射頻識(shí)別RFID(Radio Frequency Identification)是一種自動(dòng)識(shí)別技術(shù)［1］。它以射頻方式進(jìn)行非接觸式雙向通信，以達(dá)到自動(dòng)識(shí)別目標(biāo)并獲取其相關(guān)數(shù)據(jù)的目的。但目前RFID 技術(shù)也存在著很多亟待解決問(wèn)題，例如安全和隱私，數(shù)據(jù)存儲(chǔ)和碰撞等。標(biāo)簽防碰撞算法是RFID 系統(tǒng)需要研究和解決的一個(gè)重要課題。目前存在的RFID 防碰撞算法主要有2種:一種是基于ALOHA的不確定性算法［2］，另一種是基于二進(jìn)制問(wèn)詢的確定性算法。本文就基于二進(jìn)制的RFID 標(biāo)簽防碰撞算法進(jìn)行了研究和改進(jìn)。

1 二進(jìn)制搜索的防碰撞算法介紹

二進(jìn)制搜索算法的基本思想是將處于碰撞的標(biāo)簽根據(jù)碰撞位分成左右兩個(gè)子集，先查詢一個(gè)子集，若沒(méi)有碰撞，則正確識(shí)別，若仍有碰撞則再分裂，依次類推，直到識(shí)別出子集中的所有標(biāo)簽，再查詢另一個(gè)子集［3］。為了最簡(jiǎn)捷地找到碰撞位，數(shù)據(jù)編碼選用曼徹斯特編碼［4］。依據(jù)曼徹斯特編碼的特點(diǎn)可以檢測(cè)出碰撞位。

為了實(shí)現(xiàn)算法，需要引入一組閱讀器命令［5］，這組指令能被標(biāo)簽處理。以下為了舉例，假定標(biāo)簽唯一的序列號(hào)ID 長(zhǎng)度為8 bit，也就是說(shuō)最多可以有256 個(gè)標(biāo)簽處于運(yùn)行狀態(tài)，實(shí)際中ID 較長(zhǎng)。

REQUEST:請(qǐng)求命令，其參數(shù)根據(jù)算法而不同，該命令給向閱讀器識(shí)別范圍域內(nèi)的所有標(biāo)簽發(fā)送參數(shù)，標(biāo)簽收到該命令后把自己的ID 與接收的相比較，若小于或者等于，則此標(biāo)簽用其序列號(hào)回應(yīng)閱讀器。若大于則不作任何回應(yīng)。

SELECT:選擇命令，閱讀器用序列號(hào)作為參數(shù)發(fā)送給標(biāo)簽，具有相同的序列號(hào)的標(biāo)簽將以此作為執(zhí)行其命令(讀出和寫入)切入開(kāi)關(guān)，即選擇了這個(gè)標(biāo)簽［6］。

RD－DATA:讀出選中的標(biāo)簽，使其將存儲(chǔ)的數(shù)據(jù)發(fā)送給閱讀器。

UNSELECT:去選擇，取消一個(gè)被選中操作完的標(biāo)簽，讓其進(jìn)入“無(wú)聲”狀態(tài)，這樣標(biāo)簽對(duì)收到的REQUEST 命令不再作回復(fù)。為了重新激活此類標(biāo)簽，必須進(jìn)行復(fù)位操作。

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

1.1.1 算法描述

在BS 算法中，REQUEST 命令的參數(shù)為標(biāo)簽的序列號(hào)ID。以4 個(gè)在閱讀器范圍內(nèi)的標(biāo)簽為例，說(shuō)明這種算法的原理和標(biāo)簽識(shí)別過(guò)程。標(biāo)簽ID 分別為:10110010、10100011、10110011、11100011。

第一步，閱讀器向識(shí)別分為內(nèi)所有合法標(biāo)簽發(fā)送REQUEST(11111111)命令，所有標(biāo)簽都用其序列號(hào)ID 響應(yīng)，用曼徹斯特編碼得到解碼數(shù)據(jù)為1X1X001X，X 位碰撞位，得到下一次請(qǐng)求命令所需的參數(shù)。

第二步，閱讀器發(fā)送REQUEST(10111111)，標(biāo)簽1、標(biāo)簽2 和標(biāo)簽3 響應(yīng)。閱讀器得到解碼數(shù)據(jù)為101X001X。

第三步，閱讀器發(fā)送REQUEST(10101111)，只有標(biāo)簽10100011 響應(yīng)，無(wú)碰撞發(fā)生，閱讀器對(duì)該標(biāo)簽進(jìn)行處理后對(duì)它進(jìn)行屏蔽操作，使其進(jìn)入“無(wú)聲”狀態(tài)。重復(fù)上述過(guò)程直到識(shí)別完所有的標(biāo)簽。

標(biāo)簽2 通過(guò)3 次請(qǐng)求被閱讀器識(shí)別，應(yīng)答RDDATA 命令。在讀出活寫入操作完成之后，閱讀器用UNSELECT 命令讓其進(jìn)入“無(wú)聲”狀態(tài)，這樣標(biāo)簽2 對(duì)后面的請(qǐng)求命令不再作應(yīng)答。閱讀器用標(biāo)簽1經(jīng)過(guò)3 次請(qǐng)求被閱讀器識(shí)別到，標(biāo)簽3 經(jīng)過(guò)1 次請(qǐng)求命令被識(shí)別，最后標(biāo)簽4 被識(shí)別。

1.1.2 性能分析

從大量的標(biāo)簽中識(shí)別出一個(gè)標(biāo)簽，需要多次問(wèn)詢操作。其平均問(wèn)詢次數(shù)由閱讀器識(shí)別范圍內(nèi)的標(biāo)簽總數(shù)n 決定，如公式(1)所示［7］。

BS 算法可以快速簡(jiǎn)單地解決標(biāo)簽碰撞問(wèn)題。如果在閱讀器識(shí)別范圍內(nèi)只有一個(gè)標(biāo)簽，那么只需要一次問(wèn)詢操作即可識(shí)別標(biāo)簽，沒(méi)有碰撞發(fā)生。如果在閱讀器的識(shí)別范圍內(nèi)有多于一個(gè)的標(biāo)簽，那么問(wèn)詢次數(shù)的平均值很快增加。

在8 位ID的標(biāo)簽識(shí)別過(guò)程中，通過(guò)3 次問(wèn)詢過(guò)程，另外加上最開(kāi)始的1 次共操作［7］，完成一個(gè)標(biāo)簽的識(shí)別平均需要4 次操作。在n 個(gè)待識(shí)別標(biāo)簽中，完成n 個(gè)標(biāo)簽的識(shí)別需要的總問(wèn)詢次數(shù)如公式(2)所示。

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

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

1.2.1 算法思想

上述BS 算法，不僅搜索的范圍較大，而且標(biāo)簽的序列號(hào)ID 每次完整地傳輸。而在實(shí)際中標(biāo)簽的序列號(hào)長(zhǎng)度按系統(tǒng)的規(guī)模可能長(zhǎng)達(dá)96bit 或更長(zhǎng)，為了選擇一個(gè)標(biāo)簽，數(shù)據(jù)傳輸量較大。因而DBS 算法被提出。

DBS 算法是國(guó)際標(biāo)準(zhǔn)ISO14443A 所推薦的防碰撞算法［8］。在BS 算法中，閱讀器傳輸?shù)恼?qǐng)求命令序列號(hào)與標(biāo)簽應(yīng)答的序列號(hào)部分信息是重復(fù)的，可以不必傳輸，這樣就得到了DBS 算法，如圖1 所示。DBS 算法中，假定K 為標(biāo)簽序列號(hào)的最高位，請(qǐng)求命令為REQUEST(ID(K～X)，X)，X 為碰撞的最高位，序列號(hào)的K～X 位與參數(shù)相符的標(biāo)簽，傳輸其(X－1)～0 位作為對(duì)閱讀器的響應(yīng)。

圖1 DBS 算法原理

下 面 以 4 個(gè) 標(biāo) 簽(10110010、10100011、10110011、11100011)為例說(shuō)明標(biāo)簽算法的執(zhí)行過(guò)程。

第一步，閱讀器發(fā)送REQUEST(NUL)，處于閱讀器識(shí)別范圍的所有標(biāo)簽都用其序列號(hào)響應(yīng)，通過(guò)曼徹斯特編碼得到解碼數(shù)據(jù)為1X1X001X，碰撞最高位是第6 位，將該位置“0”，高于該位的不變，可得到下一次請(qǐng)求命令所需的參數(shù)(10)。

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

第三步，閱讀器發(fā)送REQUEST(1010)，只有序列號(hào)前綴為1010的標(biāo)簽2 響應(yīng)，閱讀器處理完標(biāo)簽2 后用UNSELECT 命令使其進(jìn)入“無(wú)聲”狀態(tài)。然后不斷重復(fù)上述操作直到所有標(biāo)簽識(shí)別完。

1.2.2 算法性能分析由于DBS 算法與前面的基本二進(jìn)制算法使用相似的搜索過(guò)程，因此在限制查詢范圍時(shí)動(dòng)態(tài)二進(jìn)制搜索算法也可以釆用與基本二進(jìn)制算法相同的重復(fù)操作。故而可以得出動(dòng)態(tài)二進(jìn)制搜索算法總搜索次數(shù)如公式(4)。

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ù)。對(duì)某個(gè)標(biāo)簽進(jìn)行識(shí)別時(shí)，可以設(shè)標(biāo)簽動(dòng)態(tài)傳輸序列號(hào)部分位的平均值等于BS算法一半［7］。標(biāo)簽需要傳輸?shù)谋忍財(cái)?shù)為公式(5)所示。

將公式(3)和公式(5)比較，可以看出，采用DBS 算法時(shí)，標(biāo)簽傳輸?shù)臄?shù)據(jù)量和傳輸時(shí)間比BS算法減少了近50%。閱讀器識(shí)別一次傳輸平均數(shù)據(jù)量為［9］公式(6)所示。

當(dāng)閱讀器使用動(dòng)態(tài)二進(jìn)制搜索算法時(shí)，識(shí)別n個(gè)標(biāo)簽所需要傳輸?shù)男蛄刑?hào)總長(zhǎng)度為公式(7)所示。

下圖為BS 與DBS 算法中閱讀器用于問(wèn)詢標(biāo)簽傳輸序列號(hào)總長(zhǎng)度比較。可以看出隨著標(biāo)簽數(shù)的增多，DBS 算法所需的數(shù)據(jù)量是BS 算法的一半，提高了效率。

1.3 返回式二進(jìn)制搜索(BBS)算法

1.3.1 算法的基本思想

BS 算法與DBS 算法之所以效率較低.最根本原因在于其無(wú)記憶性［10］。其識(shí)別完一個(gè)標(biāo)簽，都要從頭再來(lái)，把剩下的標(biāo)簽全部問(wèn)詢一遍，而沒(méi)有利用上次搜索已經(jīng)獲得的信息來(lái)縮小搜索范圍。

返回式策略是閱讀器每完成一個(gè)標(biāo)簽的讀取，不是返回到根節(jié)點(diǎn)而是返回上一個(gè)碰撞發(fā)生的節(jié)點(diǎn)，識(shí)別此節(jié)點(diǎn)的另外一個(gè)分枝，這樣不斷重復(fù)操作，直到把所有標(biāo)簽識(shí)別完［11］。

1.3.2 性能分析

BBS 算法在識(shí)別n 個(gè)標(biāo)簽時(shí)，閱讀器共需搜索2n－1 次，當(dāng)標(biāo)簽數(shù)增多時(shí)，平均搜索次數(shù)為2 次。假設(shè)標(biāo)簽序列號(hào)長(zhǎng)度為k bit，則閱讀器發(fā)送的數(shù)據(jù)量為k(2n－1)bit。通過(guò)畫圖比較BS、DBS 和BBS之間的優(yōu)劣。假設(shè)k=96。

從圖2 可以看出，基于BBS的算法相比DBS 算法有了改進(jìn)，問(wèn)詢數(shù)據(jù)量減少了25%，較BS 算法減少了57%。DBS的優(yōu)點(diǎn)是減少了REQUEST 命令的參數(shù)長(zhǎng)度，而B(niǎo)BS的優(yōu)點(diǎn)是減少了問(wèn)詢次數(shù)，如果能將兩者的優(yōu)勢(shì)結(jié)合，必能提高性能?；诖吮疚奶岢隽艘韵赂倪M(jìn)算法。

2 改進(jìn)的二進(jìn)制防碰撞算法

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

根據(jù)以上三種基于二進(jìn)制防碰撞算法的分析，本文研究了結(jié)合DBS 和BBS的優(yōu)點(diǎn)的返回式動(dòng)態(tài)二進(jìn)制算法。由于該算法基于返回式算法和動(dòng)態(tài)算法，因此簡(jiǎn)稱為BDBS。其請(qǐng)求命令為REQUEST(ID(K～X)，X)，序列號(hào)K～X 位與之一致的標(biāo)簽傳輸剩余的(X－1)～0 位信息作為應(yīng)答，閱讀器完成一個(gè)標(biāo)簽的識(shí)別后，返回上一個(gè)碰撞發(fā)生節(jié)點(diǎn)，識(shí)別該節(jié)點(diǎn)的另外一個(gè)分枝，而不是返回根節(jié)點(diǎn)，不斷重復(fù)操作，直到把每一個(gè)節(jié)點(diǎn)碰撞的所有標(biāo)簽識(shí)別完。

在BDBS 算法中，閱讀器的問(wèn)詢次數(shù)為2n－1，閱讀器每次問(wèn)詢平均傳輸?shù)臄?shù)據(jù)量為(k +1)/2，所以閱讀器識(shí)別所有標(biāo)簽所需要發(fā)送的數(shù)據(jù)量為公式(8)所示。

根據(jù)以上的對(duì)比分析，可以得出如圖2 所示仿真圖。

圖2 幾種算法搜索數(shù)據(jù)量比較

從仿真圖2 可以較為明顯地得出結(jié)論，對(duì)于返回式動(dòng)態(tài)二進(jìn)制搜索算法，閱讀器用于識(shí)別標(biāo)簽的數(shù)據(jù)通信量最少，比返回式二進(jìn)制搜索算法通信量減少近50%，比動(dòng)態(tài)二進(jìn)制搜索算法減少約67%，比BS 算法減少了約83%。

2.2 改進(jìn)的BDBS 算法IBDBS(Improved BDBS)

在識(shí)別中，若遍歷到碰撞位只有一位時(shí)，說(shuō)明只有兩個(gè)標(biāo)簽發(fā)生碰撞，則認(rèn)為沒(méi)有發(fā)生碰撞。對(duì)一個(gè)標(biāo)簽的碰撞位認(rèn)為是“0”。另一個(gè)標(biāo)簽的碰撞位認(rèn)為是“1”，直接使用SELECT(ID)命令選擇標(biāo)簽。則閱讀器的問(wèn)詢次數(shù)減少為公式(9)(［］為向上取整)。

則完成n 個(gè)標(biāo)簽識(shí)別，閱讀器的數(shù)據(jù)通信量為公式(10)所示。

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

說(shuō)明:此處如果考慮標(biāo)簽搜索樹(shù)為滿樹(shù)，問(wèn)詢次數(shù)應(yīng)減掉n，如果搜索樹(shù)為非滿樹(shù)，減去n 顯然太多，最差的情況是減去2，取中間值n/2，這種取值使得仿真與實(shí)際性能之間有一定差距，但總體是有了改進(jìn)。

下面從系統(tǒng)吞吐率性能來(lái)分析幾種算法，假設(shè)系統(tǒng)標(biāo)簽數(shù)量為n，問(wèn)詢標(biāo)簽的平均操作數(shù)為L(zhǎng)(n)，則定義系統(tǒng)吞吐率為公式(11)。

則BS、BDBS 及IBDBS 算法下系統(tǒng)的吞吐率分別為公式(12)、(13)、(14)。

對(duì)幾種算法吞吐率進(jìn)行仿真比較如圖4 所示。隨著標(biāo)簽數(shù)量的增多，BS 算法的吞吐率隨標(biāo)簽數(shù)量的增多不斷減小，BDBS 算法的吞吐率穩(wěn)定在50%，IBDBS 算法的吞吐率趨近于67%，相比較有了較大的提升。但是在IBDBS 中，請(qǐng)求命令REQUEST的參數(shù)長(zhǎng)度當(dāng)碰撞最高位較低時(shí)依然較長(zhǎng)。而在REQUEST 命令中實(shí)際需要的只是最高碰撞位的位置，因此只要得到碰撞最高位的位置就可以了。

圖3 BDBS 與IBDBS的問(wèn)詢數(shù)據(jù)量比較

圖4 三種算法吞吐率比較

李學(xué)橋等人在文獻(xiàn)［12］中提出了一種新的標(biāo)簽搜索算法，在REQUEST(x)命令中，x 為碰撞最高位，即請(qǐng)求命令只傳輸碰撞最高位的二進(jìn)制表示，請(qǐng)求第x 位為0的標(biāo)簽響應(yīng)。這種算法中搜索的數(shù)據(jù)長(zhǎng)度為log2(k)，比如ID 為96 位的標(biāo)簽，x的長(zhǎng)度為log296，即x 可用7 位二進(jìn)制表示，比DBS 算法請(qǐng)求命令(k +1)/2 減少了42 位，極大地減少了問(wèn)詢標(biāo)簽的數(shù)據(jù)通信量，節(jié)省了信道資源，提高標(biāo)簽識(shí)別的速度。將這種算法與IBDBS 算法問(wèn)詢次數(shù)少的優(yōu)勢(shì)相結(jié)合，其吞吐率沒(méi)有改善，但是標(biāo)簽問(wèn)詢數(shù)據(jù)量大大減少，如公式(15)，當(dāng)標(biāo)簽數(shù)量接近100 時(shí)，比IBDBS 問(wèn)詢數(shù)據(jù)量減少了約86.5%。如圖5所示。

圖5 IBDBS 與新改進(jìn)算法的問(wèn)詢數(shù)據(jù)量比較

圖6 新改進(jìn)算法與李學(xué)橋算法比較

在李學(xué)橋的改進(jìn)算法中，標(biāo)簽問(wèn)詢次數(shù)為2n－1 次，比本文的改進(jìn)算法多，比較兩種算法的問(wèn)詢數(shù)據(jù)量如圖6 所示，仿真圖中新算法比李學(xué)橋改進(jìn)算法有所提高，當(dāng)標(biāo)簽數(shù)量增多時(shí)，問(wèn)詢數(shù)據(jù)量減少25%。

3 結(jié)論

本文分析了結(jié)合DBS 及BBS 優(yōu)點(diǎn)的返回式動(dòng)態(tài)二進(jìn)制算法BDBS，對(duì)三者的在標(biāo)簽問(wèn)詢通信數(shù)據(jù)量及吞吐率等性能方面進(jìn)行了仿真比較，提出了改進(jìn)的BDBS 算法IBDBS，將只有一位碰撞的情況認(rèn)為無(wú)碰撞進(jìn)行識(shí)別，系統(tǒng)性能得到較大的提高?；诶顚W(xué)橋等人提出的對(duì)REQUSET 命令參數(shù)的改進(jìn)，本文對(duì)IBDBS 算法進(jìn)行了新的改進(jìn)，傳輸數(shù)據(jù)量進(jìn)一步減少，系統(tǒng)吞吐率得到了提高，算法性能有了改進(jìn)。仿真結(jié)果表明，通過(guò)對(duì)算法的改進(jìn)，能有效地提高標(biāo)簽識(shí)別的速度。

［1］史軍暉.基于捕獲效應(yīng)的RFID 防碰撞算法研究［D］.廣東工業(yè)大學(xué).2012.

［2］王雪，錢志鴻，胡正超.基于二叉樹(shù)的RFID 防碰撞算法的研究［J］.通信學(xué)報(bào).2010，31(6):49－56.

［3］王秀玲，耿淑琴，蒙榮生，等.二進(jìn)制搜索算法在系統(tǒng)中的實(shí)現(xiàn).中國(guó)通信學(xué)會(huì)第五屆學(xué)術(shù)年會(huì)論文集［C］.2008.

［4］周曉光，王曉華.射頻識(shí)別(RFID)技術(shù)原理與應(yīng)用實(shí)例［M］.北京:人民郵電出版社.2006:25－30.

［5］李興鶴，胡詠梅.基于動(dòng)態(tài)二進(jìn)制的二叉樹(shù)RFID 搜索結(jié)構(gòu)反碰撞算法［J］.山東科學(xué).2006(2):51－55 .

［6］江岸.無(wú)線射頻識(shí)別系統(tǒng)中防碰撞問(wèn)題的研究(D).湖南大學(xué).2009.

［7］楊恒.射頻識(shí)別－RFID 防碰撞算法研究(D).西南石油大學(xué).2012.

［8］ISO/IEC 14443－3 identification cards contactless integrated circuit (s)card－proximity cards，part 3.initialization and anti－collision［S］.2003.

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

［10］劉康.基于無(wú)源RFID 標(biāo)簽防碰撞算法的研究(D).山東大學(xué).2012.

［11］余松森，詹宜巨，彭衛(wèi)東，等.基于后退式索引的二進(jìn)制樹(shù)形搜索反碰撞算法及其實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40(16):26－28.

［12］李學(xué)橋，賈小愛(ài)，趙磊.基于后退式索引的動(dòng)態(tài)樹(shù)形防碰撞算法［J］.通信技術(shù).2009，06(42).118－120.