莫 磊

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

RFID位屏蔽二進(jìn)制搜索防碰撞算法研究

莫 磊

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

在對(duì)基本二進(jìn)制搜索樹算法及其改進(jìn)算法進(jìn)行比較、分析的基礎(chǔ)上,首次提出了位屏蔽搜索防碰撞算法,該算法利用“后退策略”以減少搜索的總次數(shù);同時(shí),利用已知信息,不發(fā)送和反饋重復(fù)信息,以減少閱讀器和標(biāo)簽之間數(shù)據(jù)交換的比特?cái)?shù)。該算法有效減少了命令發(fā)送的總次數(shù)和每次命令的參數(shù)長度,提高了搜索標(biāo)簽的效率和速度。

防碰撞;位屏蔽;射頻識(shí)別

RFID(radio frequency identification)是一種非接觸數(shù)據(jù)采集無線射頻自動(dòng)識(shí)別技術(shù)。RFID系統(tǒng)主要由2部分組成:閱讀器和電子標(biāo)簽。每個(gè)標(biāo)簽都具有唯一的標(biāo)識(shí)代碼(ID)。當(dāng)標(biāo)簽進(jìn)入閱讀器無線電磁場(chǎng)作用范圍內(nèi),閱讀器和標(biāo)簽之間通過無線射頻進(jìn)行雙向通信,完成閱讀器對(duì)標(biāo)簽的數(shù)據(jù)采集。閱讀器和所有標(biāo)簽共用一個(gè)信道,當(dāng)有多個(gè)標(biāo)簽同時(shí)向讀寫器發(fā)送數(shù)據(jù),讀寫器就不能正確識(shí)別標(biāo)簽發(fā)送的數(shù)據(jù),即發(fā)生了碰撞。為了保證閱讀器對(duì)標(biāo)簽的準(zhǔn)確識(shí)別,并讀取標(biāo)簽的數(shù)據(jù),需要一定的防碰撞算法來解決這些問題。

在現(xiàn)有的RFID防碰撞算法中,主要有ALOHA時(shí)隙防碰撞算法[1]和搜索樹防碰撞算法[2]2種,ALOHA算法是概率性算法,比較簡單,但隨機(jī)性大,存在錯(cuò)判、漏判問題,其性能隨著標(biāo)簽數(shù)量的增大而急劇惡化。搜索樹算法是確定行算法,識(shí)別率較高,不存在錯(cuò)判、漏判問題,適合于標(biāo)簽數(shù)量較大的情況,但搜索樹算法有較長的識(shí)別延時(shí)和較大的通信復(fù)雜度。筆者主要討論搜索樹防碰撞算法。

防碰撞算法的主要指標(biāo)有:閱讀標(biāo)簽的速度、讀寫信號(hào)的輸出帶寬、標(biāo)簽返回信號(hào)的帶寬、準(zhǔn)確率、穩(wěn)定性、安全性和成本等。對(duì)于搜索樹防碰撞算法,最重要的是要提高閱讀標(biāo)簽的速度,減少讀寫信號(hào)的輸出帶寬以及標(biāo)簽返回信號(hào)的帶寬。在不提高標(biāo)簽成本的情況下,如何快速高效地完成標(biāo)簽的識(shí)別,是當(dāng)前RFID防碰撞技術(shù)的一個(gè)亟待解決的難題。筆者在現(xiàn)有的搜索樹算法的基礎(chǔ)上,首次提出了解決該難題的一個(gè)全新的方法:位屏蔽搜索樹算法,該算法大大減少了閱讀器和標(biāo)簽之間的數(shù)據(jù)通信量,提高了閱讀標(biāo)簽的速度。

1 RFID二進(jìn)制搜索樹算法

在搜索樹算法中,必須采用合適的編碼,以便閱讀器能夠準(zhǔn)確識(shí)別沖突位的準(zhǔn)確比特位置。同時(shí)要保證所有標(biāo)簽?zāi)軌蛲瑫r(shí)傳送數(shù)據(jù),即能準(zhǔn)確同步。曼徹斯特編碼(Manchester)可在多個(gè)標(biāo)簽同時(shí)傳送數(shù)據(jù)時(shí)按位識(shí)別出沖突位,現(xiàn)有的搜索樹算法大多采用曼徹斯特編碼。

1.1 二進(jìn)制搜索樹算法[3]

其基本思想是閱讀器首先查詢所有標(biāo)簽,看標(biāo)簽ID是否有沖突,若沒有沖突,則正確識(shí)別標(biāo)簽,若有沖突,則標(biāo)簽分裂成2個(gè)子集:0和1。先查詢子集0,若無沖突,則正確識(shí)別,若有沖突,再把子集0分裂成2個(gè)子集00和01。依次類推,直到識(shí)別出子集0的所有標(biāo)簽,接著再依此方法查詢子集1。

設(shè)閱讀器作用范圍內(nèi)標(biāo)簽數(shù)目為K,則基本二進(jìn)制搜索樹算法搜索到第1個(gè)標(biāo)簽的命令次數(shù)為完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)為

閱讀器發(fā)送單次命令的參數(shù)長度為N,標(biāo)簽返回單次命令的長度也為N。

1.2 返回式二進(jìn)制搜索樹算法[4]

在基本二進(jìn)制算法中,當(dāng)通過搜索識(shí)別出一個(gè)標(biāo)簽后,又從頭開始新的搜索和識(shí)別。

返回式二進(jìn)制搜索樹算法中,當(dāng)識(shí)別出一個(gè)標(biāo)簽后,并沒有從頭開始識(shí)別,這種算法利用了上次搜索獲得的信息,利用“后退原則”,縮小了標(biāo)簽的搜索范圍,減小了搜索次數(shù)。

返回式二進(jìn)制搜索樹算法完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)為

和基本二進(jìn)制搜索樹算法相比,搜索次數(shù)大大減小。

閱讀器發(fā)送命令的參數(shù)長度和標(biāo)簽返回?cái)?shù)據(jù)的長度同基本二進(jìn)制搜索樹算法。

1.3 返回式動(dòng)態(tài)二進(jìn)制搜索樹算法[4]

返回式二進(jìn)制搜索樹算法減小了搜索次數(shù),但并沒有減小閱讀器發(fā)送命令和標(biāo)簽返回?cái)?shù)據(jù)的參數(shù)長度。

前兩種算法有一個(gè)缺點(diǎn):閱讀器發(fā)送命令和標(biāo)簽返回?cái)?shù)據(jù)都有大量的重復(fù)信息。閱讀器發(fā)出的請(qǐng)求命令中,最高沖突位后的所有比特位都被置1,對(duì)標(biāo)簽的識(shí)別不能提供任何的信息,對(duì)于標(biāo)簽來說,屬于多余的重復(fù)信息;標(biāo)簽返回的數(shù)據(jù)中,最高沖突位以及最高沖突位以前的比特位對(duì)于閱讀器來說,也是知道的,屬于多余的重復(fù)信息。

返回式動(dòng)態(tài)二進(jìn)制搜索樹算法對(duì)此作了改進(jìn),減小了這些重復(fù)信息的發(fā)送。

閱讀器只發(fā)送最高沖突位以前的數(shù)據(jù)位,標(biāo)簽只返回最高沖突位以后的數(shù)據(jù)位。這樣,閱讀器發(fā)送命令的參數(shù)長度和標(biāo)簽返回?cái)?shù)據(jù)的長度減少了一半。

返回式動(dòng)態(tài)二進(jìn)制搜索樹算法完成所有標(biāo)簽識(shí)別的搜索命令次數(shù)和返回式二進(jìn)制搜索樹算法一樣:

2 位屏蔽二進(jìn)制搜索樹算法

可以看出,以上所有算法中,動(dòng)態(tài)二進(jìn)制搜索樹算法減少了重復(fù)發(fā)送的多余數(shù)據(jù),識(shí)別速度最快,效率最高。但是,該算法仍有很多重復(fù)發(fā)送的數(shù)據(jù),比如:閱讀器每次只發(fā)送前Q個(gè)比特?cái)?shù)據(jù),減少了后面的(NQ)個(gè)比特?cái)?shù)據(jù)的發(fā)送,但是,前Q個(gè)比特?cái)?shù)據(jù)仍存在部分比特重復(fù)發(fā)送的問題。

有人對(duì)動(dòng)態(tài)二進(jìn)制搜索樹算法提出了改進(jìn),提出了多狀態(tài)二進(jìn)制搜索樹算法[5-11],主要思想:只發(fā)送首位碰撞位的位置信息,在該算法中,閱讀器發(fā)送命令基本做到了無多余發(fā)送的重復(fù)信息,但標(biāo)簽返回?cái)?shù)據(jù)中,仍有部分重復(fù)發(fā)送的無用信息,這必定會(huì)降低通信效率,減少識(shí)別標(biāo)簽的速度。

位屏蔽二進(jìn)制搜索樹算法的指導(dǎo)思想是:利用已知信息,不發(fā)送和反饋無用的重復(fù)信息,以提高標(biāo)簽識(shí)別速率。該算法借鑒了返回式二進(jìn)制搜索樹算法和動(dòng)態(tài)二進(jìn)制搜索樹算法的基本思想,同時(shí),充分利用了閱讀器檢測(cè)到的沖突位信息和已識(shí)別比特位信息,最大限度地減少了閱讀器發(fā)送數(shù)據(jù)量和標(biāo)簽返回?cái)?shù)據(jù)量。

2.1 算法實(shí)現(xiàn)

在位屏蔽二進(jìn)制搜索樹算法中,標(biāo)簽增加了一個(gè)位屏蔽寄存器R,以屏蔽多余的重復(fù)發(fā)送的信息,僅發(fā)送有用的碰撞位信息。屏蔽寄存器R的長度等于標(biāo)簽ID的長度N。

由于筆者首先提出了位屏蔽的概念,所以,先對(duì)位屏蔽作一個(gè)定義。

位屏蔽:指標(biāo)簽ID中和R的‘0’對(duì)應(yīng)的比特位,反之,標(biāo)簽ID中和R的‘1’對(duì)應(yīng)的比特位為非屏蔽位(或沖突位)。

屏蔽寄存器R的初始值全為‘1’。

假設(shè)標(biāo)簽ID號(hào)的長度為N,按位表示為1,2,…,N。

為了清楚地描述位屏蔽二進(jìn)制搜索樹算法,先對(duì)閱讀器請(qǐng)求控制命令進(jìn)行說明。

1)REQ0(SNR)

①SNR=0 請(qǐng)求所有標(biāo)簽返回標(biāo)簽ID數(shù)據(jù)。

②SNR≠0

a)R中‘1’的個(gè)數(shù)和SNR長度相等的標(biāo)簽更新屏蔽寄存器R,更新方法為SNR各位取代R的對(duì)應(yīng)‘1’位。

b)按上述要求完成R更新的標(biāo)簽中,ID非屏蔽位首位為‘0’的標(biāo)簽,再次進(jìn)行R更新,更新方法為R的最高‘1’位改為‘0’。該標(biāo)簽發(fā)送返回?cái)?shù)據(jù)給閱讀器,返回?cái)?shù)據(jù)由標(biāo)簽ID非屏蔽位組成。

2)REQ1(SER)

標(biāo)簽收到命令后,則R中最高位‘1’為第SNR位的標(biāo)簽更新屏蔽寄存器R,更新方法為R中最高位‘1’改為‘0’。R完成更新后,該標(biāo)簽非屏蔽位組成返回?cái)?shù)據(jù),發(fā)送給閱讀器。未更新R的標(biāo)簽不返回?cái)?shù)據(jù)。

位屏蔽二進(jìn)制搜索樹算法的具體算法處理流程如下。

1)閱讀器發(fā)送REQ0(0)。

2)標(biāo)簽收到命令后,所有標(biāo)簽同時(shí)返回ID數(shù)據(jù)給閱讀器。

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

4)標(biāo)簽收到命令后,更新R,并發(fā)返回?cái)?shù)據(jù)給閱讀器。

5)閱讀器檢測(cè)接收數(shù)據(jù),若有沖突位,跳至3);若沒有沖突位,則識(shí)別出1個(gè)標(biāo)簽,閱讀器讀取該標(biāo)簽數(shù)據(jù),對(duì)該標(biāo)簽進(jìn)行去活化處理,該標(biāo)簽不再響應(yīng)任何命令(要激活標(biāo)簽,必須暫時(shí)離開閱讀器的作用范圍)。

6)閱讀器堆棧區(qū)彈出SER值,閱讀器發(fā)送REQ1(SER)。

7)標(biāo)簽收到命令后,更新R,并發(fā)返回?cái)?shù)據(jù)給閱讀器。

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

閱讀器處理能力強(qiáng),處理速度快,存儲(chǔ)數(shù)據(jù)量大,可以處理比較復(fù)雜的算法。下面討論步驟5)中閱讀器識(shí)別標(biāo)簽的算法和步驟6)中閱讀器計(jì)算出SER的算法。

閱讀器中設(shè)置一個(gè)ID存儲(chǔ)區(qū)域來存放收到的數(shù)據(jù),由于位屏蔽二進(jìn)制搜索樹算法總的搜索次數(shù)為(2N-1)次,所以存儲(chǔ)區(qū)大小可設(shè)置為(2N-1)。另外,閱讀器還要設(shè)置一個(gè)堆棧區(qū)來存放SER值,SER值按后進(jìn)先出的原則存取數(shù)據(jù)。算法如下。

1)若閱讀器請(qǐng)求命令為REQ0(0),則直接存儲(chǔ)收到的ID數(shù)據(jù)。

2)若閱讀器請(qǐng)求命令為REQ0(SNR)(SNR≠0),則作如下處理:返回?cái)?shù)據(jù)首位補(bǔ)0,組成一個(gè)新數(shù)據(jù),該數(shù)據(jù)逐位取代前一個(gè)存儲(chǔ)值的對(duì)應(yīng)沖突位(前一個(gè)存儲(chǔ)值還繼續(xù)保留),得到一個(gè)新的存儲(chǔ)值。

3)若閱讀器請(qǐng)求命令為REQ1(SER),則返回?cái)?shù)據(jù)首位補(bǔ)1,組成一個(gè)新數(shù)據(jù);在ID存儲(chǔ)區(qū)中,搜索最新存儲(chǔ)的第SER位為首位沖突位的ID存儲(chǔ)值,用該新數(shù)據(jù)逐位取代該ID存儲(chǔ)值的對(duì)應(yīng)沖突位(原存儲(chǔ)值還繼續(xù)保留),得到一個(gè)新的存儲(chǔ)值。

4)若閱讀器收到的ID數(shù)據(jù)有沖突位,最高沖突位為第Y位,則Y存于堆棧區(qū)。

5)若閱讀器收到的ID數(shù)據(jù)無沖突位,則可識(shí)別出一個(gè)標(biāo)簽ID。

假設(shè)標(biāo)簽的編碼為8位,閱讀器作用范圍內(nèi)有4個(gè)標(biāo)簽,分別為

標(biāo)簽A:01101010;

標(biāo)簽B:01001011;

標(biāo)簽C:00101010;

標(biāo)簽D:10101001。

位屏蔽二進(jìn)制搜索樹算法過程如表1所示。

表1 位屏蔽二進(jìn)制搜索樹算法過程Tab.1 Process of binary searching algo rithm based on bit-shield

2.2 算法仿真

位屏蔽二進(jìn)制搜索樹算法和返回式動(dòng)態(tài)二進(jìn)制搜索樹算法相比,其搜索方法都是基于后退策略的二進(jìn)制搜索樹算法,搜索次數(shù)是一樣的,都是(2N-1)次。但是,位屏蔽二進(jìn)制搜索樹算法由于只傳送標(biāo)簽ID位的沖突位信息,所以傳送的比特?cái)?shù)更少,標(biāo)簽識(shí)別速率得到了提高。

另外,由于采用了堆棧技術(shù),使用后退策略搜索時(shí),閱讀器只發(fā)送ID的首位沖突位的位置信息,發(fā)送命令參數(shù)長度進(jìn)一步減小。

為評(píng)價(jià)位屏蔽二進(jìn)制搜索樹算法的性能,對(duì)位屏蔽二進(jìn)制搜索樹算法和動(dòng)態(tài)二進(jìn)制搜索樹算法進(jìn)行了仿真,由于識(shí)別每個(gè)標(biāo)簽所需的平均比特?cái)?shù)反映了防碰撞算法的平均最小時(shí)延,是衡量防碰撞算法的一個(gè)重要指標(biāo),所以,以識(shí)別每個(gè)標(biāo)簽所需的平均比特?cái)?shù)作為指標(biāo)進(jìn)行仿真,假定略去控制命令本身及前、后綴等所需的比特?cái)?shù),則

其中,L(AVE)是識(shí)別每個(gè)標(biāo)簽平均比特?cái)?shù),L(TX)是閱讀器發(fā)送命令參數(shù)總長度,L(RX)是標(biāo)簽響應(yīng)命令參數(shù)總長度。仿真環(huán)境標(biāo)簽ID長度為96 bit,考慮到大多數(shù)在同一區(qū)域的ID有部分ID位相同的實(shí)際情況,假定其中16 bit是相同的,其余80 bit隨機(jī)生成;標(biāo)簽數(shù)量為10～300。仿真結(jié)果如圖1所示。

通過仿真結(jié)果可以看出,位屏蔽二進(jìn)制搜索樹算法明顯優(yōu)于動(dòng)態(tài)二進(jìn)制搜索樹算法,這是由于位屏蔽二進(jìn)制搜索樹算法減少了多余的重復(fù)傳送的比特?cái)?shù),效率更高,速度更快。

3 結(jié) 語

對(duì)二進(jìn)制搜索樹算法及其改進(jìn)算法進(jìn)行了分析,這些算法都存在重復(fù)發(fā)送已知信息的問題。為了減少閱讀器和標(biāo)簽之間數(shù)據(jù)交換的信息量,提高標(biāo)簽識(shí)別速率,提出了一種新的搜索樹防碰撞算法,全面利用已知信息,不發(fā)送和反饋無用的重復(fù)信息,標(biāo)簽識(shí)別速率得到較大提高。

筆者創(chuàng)新點(diǎn):首次提出了位屏蔽的概念以及基于位屏蔽的二進(jìn)制搜索樹防碰撞算法,在標(biāo)簽內(nèi)設(shè)置一個(gè)位屏蔽寄存器,凡是閱讀器已知的數(shù)據(jù)位予以屏蔽,標(biāo)簽只發(fā)送閱讀器不知道的沖突位信息。另外,還采用了堆棧技術(shù),在使用后退策略搜索時(shí),閱讀器只發(fā)送最高非屏蔽的位置信息,發(fā)送命令參數(shù)長度進(jìn)一步減小,最大限度地避免了重復(fù)發(fā)送信息,減少了數(shù)據(jù)發(fā)送比特?cái)?shù),能夠快速、有效地識(shí)別多個(gè)標(biāo)簽。該算法對(duì)研究RFID防碰撞問題提出了一個(gè)全新的思路和方法,對(duì)RFID技術(shù)的推廣和應(yīng)用具有重要的意義。

圖1 不同標(biāo)簽數(shù)量情況下識(shí)別每個(gè)標(biāo)簽平均比特?cái)?shù)Fig.1 Average bit number of each tags identification in the case of different quantity of tags

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

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

[3] 姜麗芬,盧桂章,辛運(yùn)帷.射頻識(shí)別系統(tǒng)中的防碰撞算法研究[J].計(jì)算機(jī)工程與應(yīng)用(Computer Engineering and Applications),2007,43 (15):29-32.

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

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

[6] 劉 丹,魏 鵬,譚 杰,等.一種RFID多標(biāo)簽碰撞檢測(cè)方法[J].小型微型計(jì)算機(jī)系統(tǒng)(Journal of Chinese Computer Systems),2009,30 (9):1 890-1 894.

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

[8] CHEN W T,L IN G H.An efficient anti-collisionmethod for tag identification in a RFID system[J].IEICE Transactionson Communications,2006(12):3 386-3 392.

[9] CHOIJ,LEED,YOUN Y.Scanning-based p re-p rocessing for enhanced RFID tag anti-collision p rotocols[A].International Symposium on Communications and Information Technologies(ISCIT’06)[C].[S.l.]:[s.n.],2006.

[10] 袁萬錦,張 革.基于RC500的智能門禁控制系統(tǒng)研究[J].河北工業(yè)科技(Hebei Journal of Industrial Science and Technology),2006, 23(5):284-286.

[11] 劉東輝,張新嶺,邱金蕙,等.基于無線傳輸?shù)闹悄苄^(qū)門禁系統(tǒng)設(shè)計(jì)[J].河北科技大學(xué)學(xué)報(bào)(Journal of Hebei University of Science and Technology),2007,28(1):37-40.

Research in binary tree anti-collision algo rithm based on bit-shield in RFID system

MO Lei
(Department of Communication,Sichuan TOP Vocational Institute of Info rmation Technology,Chengdu Sichuan 611743,China)

The elementary binary searching algorithm and some imp roved algorithm s are compared and analyzed,and an anticollision searching algorithm based on bit-shield isp roposed for the first time.The algorithm adop ts themethod of"back mechanism"to decrease the total timesof search,and by using know n information and not sending and responding redup licated information decreases the bits between the reader and the tags.The total timesof command and the length of parameter of every command are decreased effectively,and the efficiency and speed of tags identification is imp roved.

anti-collision;bit-shield;radio frequency identification

TP301

A

1008-1542(2010)05-0458-05

2010-04-01;責(zé)任編輯:陳書欣

莫 磊(1969-),男,四川遂寧人,講師,碩士,主要從事RFID技術(shù)、自動(dòng)控制技術(shù)方面的研究。