計數(shù)型位屏蔽射頻識別防碰撞算法設(shè)計*

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

1 引 言

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

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

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

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

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

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

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

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

2 防碰撞算法原理

2.1 沖突位的檢測

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

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

圖1 Manchester編碼沖突位檢測

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

2.2 算法設(shè)計

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

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

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

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

(1)屏蔽位

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

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

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

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

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

2.2.2請求控制命令

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

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

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

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

2.2.3算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法比較和仿真

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

3.1 返回式動態(tài)二進制搜索算法

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

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

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

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

3.2 算法仿真

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

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

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

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

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

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

4 結(jié)束語

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

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

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

參考文獻：

[1] 萬紅,楊延昭.RFID防碰撞算法研究與改進[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)簽防碰撞檢測方法[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].福建工程學(xué)院學(xué)報,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].微計算機信,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] 余松森,詹宜巨.基于修剪枝的二進制樹形搜索反碰撞算法與實現(xiàn)[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].計算機工程與應(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] 李興鶴, 胡詠梅, 王華蓮.基于動態(tài)二進制的二叉樹搜索結(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] 廉國斌.射頻識別系統(tǒng)中的防碰撞算法研究[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)