(四川托普信息技術(shù)職業(yè)學(xué)院 通信系，成都 611743)

1 引 言

射頻識(shí)別(RFID)系統(tǒng)主要由閱讀器和電子標(biāo)簽兩部分組成。閱讀器和標(biāo)簽之間通過無線方式相互通信和交換數(shù)據(jù)，所有電子標(biāo)簽都工作在同一頻率，共享同一通信信道，如果多個(gè)標(biāo)簽進(jìn)入閱讀器作用范圍內(nèi)，當(dāng)標(biāo)簽收到閱讀器發(fā)出的命令后，所有標(biāo)簽同時(shí)向閱讀器發(fā)出返回?cái)?shù)據(jù)，信號(hào)就會(huì)相互干擾，發(fā)生沖突，這就是RFID系統(tǒng)中的碰撞問題。防止這些沖突發(fā)生的方法就叫防碰撞算法。

解決沖突的方法主要有4種：時(shí)分多址(TDMA)、頻分多址(FDMA)、碼分多址(CDMA)和空分多址(SDMA)。由于RFID系統(tǒng)的一些特點(diǎn)和限制要求，傳統(tǒng)的一些防碰撞技術(shù)很難在RFID系統(tǒng)中應(yīng)用。目前，大多采用時(shí)分多址的方法。

RFID技術(shù)要得到普及和廣泛應(yīng)用，標(biāo)簽的成本必須足夠低，應(yīng)當(dāng)盡可能使用無源標(biāo)簽，標(biāo)簽內(nèi)部沒有電源，標(biāo)簽的工作能量由閱讀器產(chǎn)生的電磁場(chǎng)提供。閱讀器可有自己的電源，但閱讀器的成本也不能太高。由于這些特點(diǎn)，對(duì)標(biāo)簽有以下限制要求：

(1)由于標(biāo)簽內(nèi)部沒有電源，所以不允許標(biāo)簽消耗過大的功率和能量;

(2)標(biāo)簽之間不能相互通信，沒有載波檢測(cè)能力，也不能檢測(cè)位沖突;

(3)標(biāo)簽不能處理過于復(fù)雜的計(jì)算，存儲(chǔ)空間也比較小。

在標(biāo)簽的防碰撞算法中，可以分為概率性算法和確定性算法兩大類，概率性算法主要有ALOHA時(shí)隙防碰撞算法[1-2]，確定性算法主要有二進(jìn)制搜索防碰撞算法[3]。ALOHA算法在標(biāo)簽數(shù)量較大時(shí)，整個(gè)系統(tǒng)的可靠性難以保證，信道利用率也不高。二進(jìn)制搜索防碰撞算法有較高的信道利用率，系統(tǒng)的可靠性高，但識(shí)別延時(shí)較長(zhǎng)。本文主要研究確定性算法中的二進(jìn)制搜索防碰撞算法及其改進(jìn)算法。

現(xiàn)有的二進(jìn)制搜索算法及其改進(jìn)算法主要有二進(jìn)制搜索基本算法、返回式二進(jìn)制樹搜索算法[3]、返回式動(dòng)態(tài)二進(jìn)制樹搜索算法[4]、修剪枝二進(jìn)制搜索樹算法[5]、引入預(yù)處理的改進(jìn)多狀態(tài)二進(jìn)制搜索算法[6-7]等，這些算法可參考相應(yīng)文獻(xiàn)，在此不再贅述。這些算法經(jīng)過不斷的改進(jìn)，減小了標(biāo)簽搜索次數(shù)，閱讀器和標(biāo)簽之間相互通信的數(shù)據(jù)量也在不斷減小，但是，這些算法或多或少都存在一個(gè)問題：閱讀器和標(biāo)簽之間重復(fù)發(fā)送已知信息，影響了標(biāo)簽識(shí)別的速率。為此，本文提出了一種計(jì)數(shù)型位屏蔽射頻識(shí)別防碰撞算法，該算法充分利用已知信息，不發(fā)送和反饋重復(fù)信息，同時(shí)，盡量減小閱讀器和標(biāo)簽之間信息交換的比特?cái)?shù)，提高了標(biāo)簽識(shí)別的速率。

2 防碰撞算法原理

2.1 沖突位的檢測(cè)

要通過搜索樹的方法實(shí)現(xiàn)防碰撞操作，閱讀器必須要對(duì)標(biāo)簽返回的數(shù)據(jù)進(jìn)行準(zhǔn)確的沖突位檢測(cè)，這就需要對(duì)返回?cái)?shù)據(jù)進(jìn)行適當(dāng)?shù)木幋a。曼徹斯特編碼(Manchester)可以方便地實(shí)現(xiàn)沖突位檢測(cè)，該編碼用“01”表示二進(jìn)制的‘0’碼，用“10”表示二進(jìn)制的‘1’碼，如：二進(jìn)制編碼“0101”用Manchester編碼表示為“01100110”。若兩個(gè)或多個(gè)標(biāo)簽同時(shí)發(fā)送Manchester編碼，當(dāng)某位發(fā)生了沖突，即該位有不同的值，既有“01”，又有“10”，則閱讀器檢測(cè)到的數(shù)據(jù)為“11”，由于Manchester編碼沒有“11”碼元，閱讀器就判斷該位發(fā)生了沖突[8]。

在RFID系統(tǒng)中，每個(gè)標(biāo)簽都有唯一的編碼(ID)。設(shè)有兩個(gè)標(biāo)簽，ID分別為01100101和01010111，利用Manchester編碼，閱讀器可以正確檢測(cè)出沖突位，如圖1所示。

圖1 Manchester編碼沖突位檢測(cè)

由圖1可以看出，閱讀器檢測(cè)出D1、D4、D5位為“11”，共有3位沖突位，用X表示，閱讀器檢測(cè)出的數(shù)據(jù)可表示為01XX01X1。

2.2 算法設(shè)計(jì)

計(jì)數(shù)型位屏蔽防碰撞算法的設(shè)計(jì)思想是：盡量利用已知信息，減少重復(fù)發(fā)送的信息，以提高標(biāo)簽識(shí)別速率。

首先，由閱讀器發(fā)送請(qǐng)求命令，所有標(biāo)簽都返回ID數(shù)據(jù)，閱讀器檢測(cè)出所有沖突位，沖突位記為‘1’，非沖突位記為‘0’，并把沖突位信息發(fā)送給標(biāo)簽，由于非沖突位是已識(shí)別位，是閱讀器已知的數(shù)據(jù)信息，不需要標(biāo)簽再發(fā)送。所以，標(biāo)簽把這些非沖突位進(jìn)行屏蔽，這些屏蔽位不再返回給閱讀器，避免重復(fù)發(fā)送，標(biāo)簽僅返回必要的沖突位數(shù)據(jù)信息給閱讀器，閱讀器檢測(cè)出沖突位，并發(fā)送沖突位信息給標(biāo)簽，標(biāo)簽再對(duì)非沖突位進(jìn)行屏蔽。這樣，在不發(fā)送非沖突位信息的前提下，可識(shí)別出所有標(biāo)簽。

在以下的論述中，假設(shè)標(biāo)簽的長(zhǎng)度為N，按位表示為(1，2，3，…，N)。

2.2.1屏蔽位和計(jì)數(shù)器

(1)屏蔽位

在標(biāo)簽中設(shè)置一個(gè)屏蔽寄存器R，R的長(zhǎng)度同標(biāo)簽ID的長(zhǎng)度N，R的初值為全‘1’。

屏蔽位的概念由本文作者首先提出，在此，先給出屏蔽位的定義。

屏蔽位指的是標(biāo)簽中和屏蔽寄存器R的‘0’位對(duì)應(yīng)的ID數(shù)據(jù)位，反之，和R的‘1’位對(duì)應(yīng)的ID數(shù)據(jù)位為非屏蔽位。

(2)休眠計(jì)數(shù)器

標(biāo)簽有激活態(tài)和去活態(tài)2種工作狀態(tài)，未識(shí)別的標(biāo)簽處于激活態(tài)；已識(shí)別的標(biāo)簽由閱讀器發(fā)出去活命令后處于去活態(tài)，不再響應(yīng)任何命令。激活態(tài)又分待命態(tài)和休眠態(tài)，標(biāo)簽中設(shè)置一個(gè)休眠計(jì)數(shù)器，處于激活態(tài)的標(biāo)簽，計(jì)數(shù)值為0則為待命態(tài)，計(jì)數(shù)值等于或大于1則為休眠態(tài)。當(dāng)標(biāo)簽收到命令后，首先更新休眠計(jì)數(shù)器，完成更新后，處于待命態(tài)的標(biāo)簽發(fā)送返回?cái)?shù)據(jù)給閱讀器。

2.2.2請(qǐng)求控制命令

為了方便描述，先對(duì)閱讀器的請(qǐng)求控制命令REQ(SNR)進(jìn)行說明：

(1)SNR=0：標(biāo)簽收到命令后，休眠計(jì)數(shù)值為0，處于待命態(tài)的標(biāo)簽返回ID數(shù)據(jù)；

(2)SNR=1：標(biāo)簽收到命令后，休眠計(jì)數(shù)值減1，處于待命態(tài)的標(biāo)簽更新R，R中最高位‘1’改為‘0’，R完成更新后，該標(biāo)簽非屏蔽位組成返回?cái)?shù)據(jù)，發(fā)送給閱讀器；

(3)SNR>1：標(biāo)簽收到命令后，處于待命態(tài)的標(biāo)簽先更新屏蔽寄存器R：SNR各位取代R的對(duì)應(yīng)‘1’位，再更新休眠計(jì)數(shù)值：非屏蔽位首位為0的標(biāo)簽仍處于待命態(tài)，否則轉(zhuǎn)入休眠態(tài)，休眠值為1。處于休眠態(tài)的標(biāo)簽計(jì)數(shù)值加1。完成休眠計(jì)數(shù)值更新后，處于待命態(tài)的標(biāo)簽，R的最高‘1’位改為‘0’，該標(biāo)簽發(fā)送返回?cái)?shù)據(jù)給閱讀器，返回?cái)?shù)據(jù)由標(biāo)簽ID非屏蔽位組成。

2.2.3算法流程

計(jì)數(shù)型位屏蔽二進(jìn)制搜索算法的具體算法處理流程如下：

(1)閱讀器發(fā)送REQ(0)；

(2)標(biāo)簽收到命令后，休眠計(jì)數(shù)值為0，所有標(biāo)簽同時(shí)返回ID數(shù)據(jù)給閱讀器；

(3)閱讀器檢測(cè)接收數(shù)據(jù)是否有沖突位，若沒有沖突位，跳至步驟5；若有沖突位，則可得到下次請(qǐng)求命令的SNR(SNR>1)，SNR構(gòu)成如下：接收數(shù)據(jù)的所有沖突位為‘1’，其余位為‘0’，閱讀器發(fā)送REQ(SNR)；

(4)標(biāo)簽收到命令后，更新R，更新休眠計(jì)數(shù)器，處于待命態(tài)的標(biāo)簽發(fā)返回?cái)?shù)據(jù)給閱讀器；

(5)閱讀器若檢測(cè)出沖突位，則轉(zhuǎn)至步驟3；閱讀器若沒有檢測(cè)出沖突位，則識(shí)別出一個(gè)標(biāo)簽，閱讀器讀取該標(biāo)簽數(shù)據(jù)，對(duì)該標(biāo)簽進(jìn)行去活化，該標(biāo)簽處于去活態(tài)；

(6)閱讀器發(fā)送REQ(1)；

(7)標(biāo)簽收到命令后，更新休眠計(jì)數(shù)器，更新R，處于待命態(tài)的標(biāo)簽發(fā)返回?cái)?shù)據(jù)給閱讀器；

(8)跳至步驟3，依此循環(huán)，直到識(shí)別出所有標(biāo)簽。

步驟3還可以進(jìn)一步改進(jìn)：若閱讀器檢測(cè)到僅有一個(gè)沖突位，則可識(shí)別出兩個(gè)標(biāo)簽：一個(gè)標(biāo)簽該沖突位為‘0’，另一個(gè)標(biāo)簽該沖突位為‘1’。

閱讀器識(shí)別標(biāo)簽的算法如下：閱讀器中設(shè)置一個(gè)ID存儲(chǔ)區(qū)域來存放收到的數(shù)據(jù)，設(shè)閱讀器作用范圍內(nèi)共有K個(gè)標(biāo)簽，由于計(jì)數(shù)型位屏蔽搜索算法總的搜索次數(shù)最多為2K-1次，所以存儲(chǔ)區(qū)大小設(shè)置為2K-1就足夠了。通過對(duì)收到的數(shù)據(jù)進(jìn)行存儲(chǔ)和處理，可以識(shí)別出所有的標(biāo)簽：

(1)若閱讀器請(qǐng)求命令的SNR=0，則直接存儲(chǔ)標(biāo)簽返回的ID數(shù)據(jù)；

(2)若閱讀器請(qǐng)求命令的SNR≠0，則作如下處理；若SNR>1，則返回?cái)?shù)據(jù)首位補(bǔ)0；若SNR=1，則返回?cái)?shù)據(jù)首位補(bǔ)1，得到一個(gè)新數(shù)據(jù)。在ID存儲(chǔ)區(qū)，搜索最新存儲(chǔ)的沖突位個(gè)數(shù)和該新數(shù)據(jù)長(zhǎng)度相等的ID存儲(chǔ)值，用該新數(shù)據(jù)逐位取代該存儲(chǔ)值的對(duì)應(yīng)沖突位(前一個(gè)存儲(chǔ)值還繼續(xù)保留)，得到一個(gè)新的存儲(chǔ)值；

(3)若閱讀器收到的ID數(shù)據(jù)無沖突位，則可識(shí)別出一個(gè)標(biāo)簽；若閱讀器檢測(cè)到僅有一個(gè)沖突位，則可識(shí)別出兩個(gè)標(biāo)簽。

3 算法比較和仿真

為評(píng)介計(jì)數(shù)型位屏蔽二進(jìn)制搜索算法的性能，對(duì)位屏蔽二進(jìn)制搜索算法和返回式動(dòng)態(tài)二進(jìn)制搜索算法進(jìn)行了比較和仿真。

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

返回式動(dòng)態(tài)二進(jìn)制搜索算法是在基本二進(jìn)制搜索算法基礎(chǔ)上改進(jìn)的一種算法。

當(dāng)閱讀器檢測(cè)到最高沖突位(假設(shè)為第Q位)，則可得到下次請(qǐng)求命令序列號(hào)(長(zhǎng)度為Q)：前Q-1位與接收到的ID號(hào)的前Q-1位相同，第Q位為0。各標(biāo)簽把自身ID號(hào)的前Q位與之比較，相同的標(biāo)簽返回后面的N-Q位給閱讀器。當(dāng)識(shí)別出一個(gè)標(biāo)簽后，閱讀器的請(qǐng)求命令序列號(hào)為：上一次請(qǐng)求命令序列號(hào)的第Q位改為1，其余不變。通過這種返回動(dòng)態(tài)式的搜索，可以識(shí)別出所有的標(biāo)簽。

假設(shè)閱讀器作用范圍內(nèi)有K個(gè)標(biāo)簽，閱讀器檢測(cè)數(shù)據(jù)共有H次僅1個(gè)沖突位。返回式動(dòng)態(tài)二進(jìn)制搜索算法完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)為L(zhǎng)(K)=2K-1。計(jì)數(shù)型位屏蔽搜索算法完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)為L(zhǎng)(K)=2K-2H-1。

由于計(jì)數(shù)型位屏蔽搜索算法僅發(fā)送非屏蔽位信息，所以閱讀器和標(biāo)簽之間的數(shù)據(jù)通信量更少，特別是在有大量相同ID比特位的情況下，更加明顯。

3.2 算法仿真

對(duì)計(jì)數(shù)型位屏蔽二進(jìn)制搜索算法和動(dòng)態(tài)二進(jìn)制搜索算法進(jìn)行了仿真，仿真環(huán)境為：標(biāo)簽ID長(zhǎng)度為96 bit,其中30 bit是相同的，其余66 bit隨機(jī)分配；比特率為128 kbit/s，標(biāo)簽數(shù)量為10～300。仿真結(jié)果如圖2所示。

圖2 不同標(biāo)簽數(shù)量的識(shí)別時(shí)間

根據(jù)計(jì)數(shù)型位屏蔽二進(jìn)制搜索算法的原理不難看出，標(biāo)簽中的相同比特位越多，其識(shí)別速度越快，在上述仿真環(huán)境中，假設(shè)66 bit是相同的，其余30 bit隨機(jī)分配，其余條件不變，仿真結(jié)果如圖3所示。

圖3 相同比特位較多情況下標(biāo)簽的識(shí)別時(shí)間

由仿真結(jié)果可以看出，計(jì)數(shù)型位屏蔽搜索算法識(shí)別時(shí)間遠(yuǎn)小于返回式動(dòng)態(tài)二進(jìn)制搜索算法。

在標(biāo)簽相同比特位個(gè)數(shù)增加的情況下，返回式動(dòng)態(tài)二進(jìn)制搜索算法識(shí)別時(shí)間并沒有減少，但計(jì)數(shù)型位屏蔽搜索算法識(shí)別時(shí)間卻大大減小了。

4 結(jié)束語

本文提出了計(jì)數(shù)型位屏蔽搜索算法，其核心思想是：充分利用已知信息，不發(fā)送和反饋重復(fù)信息，最大程度減少閱讀器和標(biāo)簽之間的通信量。

現(xiàn)有的二進(jìn)制搜索算法及其改進(jìn)算法，或多或少都存在重復(fù)發(fā)送和反饋已知信息的問題。與已有的二進(jìn)制搜索算法相比，計(jì)數(shù)型位屏蔽搜索算法徹底解決了閱讀器和標(biāo)簽之間重復(fù)發(fā)送信息的問題，利用位屏蔽寄存器屏蔽所有的已知信息，標(biāo)簽僅發(fā)送閱讀器未知的沖突位信息；休眠計(jì)數(shù)器把不需要返回?cái)?shù)據(jù)的標(biāo)簽轉(zhuǎn)入休眠態(tài)。

計(jì)數(shù)型位屏蔽搜索算法特別適合于有大量比特位相同的標(biāo)簽的識(shí)別，待識(shí)別標(biāo)簽相同比特位越多，越能體現(xiàn)其優(yōu)勢(shì)。需要提到的是，文獻(xiàn)[6]中提到的預(yù)處理方法，對(duì)于全部待識(shí)別標(biāo)簽都有部分比特位相同的情況，也能在一定程度上提高標(biāo)簽的識(shí)別速率。但是，由于該方法只是進(jìn)行簡(jiǎn)單的預(yù)處理，對(duì)于待識(shí)別標(biāo)簽中的部分標(biāo)簽有相同比特位的情況卻無能為力，但在實(shí)際應(yīng)用中，這卻是經(jīng)常出現(xiàn)的情況，而計(jì)數(shù)型位屏蔽搜索算法能很好地解決這一問題。計(jì)數(shù)型位屏蔽搜索算法不但有一定的理論價(jià)值，而且也有一定的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1] 萬紅,楊延昭.RFID防碰撞算法研究與改進(jìn)[J].微計(jì)算機(jī)信息,2009,25(3-2):230-232.

WAN Hong,YANG Yan-zhao.Research and Improvement on Anti-collision Algorithm for RFID System[J].Microcomputer Information,2009,25(3-2):230-232.(in Chinese)

[2] 劉丹,魏鵬,譚杰,等.一種RFID多標(biāo)簽防碰撞檢測(cè)方法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(9):1890-1894.

LIU Dan, WEI Peng, TAN Jie，et al.Method for Detecting the Collision of Multiple RFID Tags[J].Mini Microcomputer System, 2009, 30(9): 1890-1894. (in Chinese)

[3] 林挺釗,劉建成.RFID二進(jìn)制搜索算法的研究與改進(jìn)[J].福建工程學(xué)院學(xué)報(bào),2008,6(6):732-736.

LIN Ting-zhao, LIU Jian-cheng. Improvements on radio frequency identification(RFID) binary search algorithm[J]. Journal of Fujian University of Technology, 2008, 6(6): 732-736. (in Chinese)

[4] 王忠勇,高向川.基于回溯的RFID防沖撞算法[J].微計(jì)算機(jī)信,2009,25(2):187-188,217.

WANG Zhong-yong,GAO Xiang-chuan.RFID Anti-collision Algorithm Based on the Recollection[J]. Microcomputer Information,2009,25(2):187-188,217.(in Chinese)

[5] 余松森,詹宜巨.基于修剪枝的二進(jìn)制樹形搜索反碰撞算法與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2005,31(16):217-218.

YU Song-shen, ZHAN Yi-ju. A Binary-tree Searching Anti-collision Algorithm Based on Pruning Away Branches and Its Practice[J]. Computer Engineering,2005,31(16):217-218.(in Chinese)

[6] 吳躍前,辜大光,范振粵.RFID系統(tǒng)防碰撞算法比較分析及其改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(3):210-213.

WU Yue-qian, GU Da-guang, FAN Zhen-yue. Comparison and analysis of anti-collision in RFID system and improved algorithm[J].Computer Engineering and Applications,2009,45(3):210-213.(in Chinese)

[7] 李興鶴, 胡詠梅, 王華蓮.基于動(dòng)態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu)RFID 反碰撞算法[J].山東科學(xué), 2006,19(2):51-55.

LI Xing-he, HU Yong-mei, WANG Hua-lian. An anti-collision RFID algorithm based on binary-tree search of the dynamic binary[J].Shandong Science, 2006, 19(2): 51-55. (in Chinese)

[8] 廉國斌.射頻識(shí)別系統(tǒng)中的防碰撞算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(1):36-38.

LIAN Guo-bin. Research on Anti-Collision Algorithm for RFID Systems[J].Computer Technology and Development, 2009, 19(1): 36-38. (in Chinese)