RFID位屏蔽二進制搜索防碰撞算法研究

莫 磊

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

RFID位屏蔽二進制搜索防碰撞算法研究

莫 磊

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

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

防碰撞;位屏蔽;射頻識別

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

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

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

1 RFID二進制搜索樹算法

在搜索樹算法中,必須采用合適的編碼,以便閱讀器能夠準確識別沖突位的準確比特位置。同時要保證所有標簽能夠同時傳送數據,即能準確同步。曼徹斯特編碼(Manchester)可在多個標簽同時傳送數據時按位識別出沖突位,現有的搜索樹算法大多采用曼徹斯特編碼。

1.1 二進制搜索樹算法[3]

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

設閱讀器作用范圍內標簽數目為K,則基本二進制搜索樹算法搜索到第1個標簽的命令次數為完成所有標簽識別的搜索命令次數為

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

1.2 返回式二進制搜索樹算法[4]

在基本二進制算法中,當通過搜索識別出一個標簽后,又從頭開始新的搜索和識別。

返回式二進制搜索樹算法中,當識別出一個標簽后,并沒有從頭開始識別,這種算法利用了上次搜索獲得的信息,利用“后退原則”,縮小了標簽的搜索范圍,減小了搜索次數。

返回式二進制搜索樹算法完成所有標簽識別的搜索命令次數為

和基本二進制搜索樹算法相比,搜索次數大大減小。

閱讀器發(fā)送命令的參數長度和標簽返回數據的長度同基本二進制搜索樹算法。

1.3 返回式動態(tài)二進制搜索樹算法[4]

返回式二進制搜索樹算法減小了搜索次數,但并沒有減小閱讀器發(fā)送命令和標簽返回數據的參數長度。

前兩種算法有一個缺點:閱讀器發(fā)送命令和標簽返回數據都有大量的重復信息。閱讀器發(fā)出的請求命令中,最高沖突位后的所有比特位都被置1,對標簽的識別不能提供任何的信息,對于標簽來說,屬于多余的重復信息;標簽返回的數據中,最高沖突位以及最高沖突位以前的比特位對于閱讀器來說,也是知道的,屬于多余的重復信息。

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

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

返回式動態(tài)二進制搜索樹算法完成所有標簽識別的搜索命令次數和返回式二進制搜索樹算法一樣:

2 位屏蔽二進制搜索樹算法

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

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

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

2.1 算法實現

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

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

位屏蔽:指標簽ID中和R的‘0’對應的比特位,反之,標簽ID中和R的‘1’對應的比特位為非屏蔽位(或沖突位)。

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

假設標簽ID號的長度為N,按位表示為1,2,…,N。

為了清楚地描述位屏蔽二進制搜索樹算法,先對閱讀器請求控制命令進行說明。

1)REQ0(SNR)

①SNR=0 請求所有標簽返回標簽ID數據。

②SNR≠0

a)R中‘1’的個數和SNR長度相等的標簽更新屏蔽寄存器R,更新方法為SNR各位取代R的對應‘1’位。

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

2)REQ1(SER)

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

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

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

2)標簽收到命令后,所有標簽同時返回ID數據給閱讀器。

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

4)標簽收到命令后,更新R,并發(fā)返回數據給閱讀器。

5)閱讀器檢測接收數據,若有沖突位,跳至3);若沒有沖突位,則識別出1個標簽,閱讀器讀取該標簽數據,對該標簽進行去活化處理,該標簽不再響應任何命令(要激活標簽,必須暫時離開閱讀器的作用范圍)。

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

7)標簽收到命令后,更新R,并發(fā)返回數據給閱讀器。

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

閱讀器處理能力強,處理速度快,存儲數據量大,可以處理比較復雜的算法。下面討論步驟5)中閱讀器識別標簽的算法和步驟6)中閱讀器計算出SER的算法。

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

1)若閱讀器請求命令為REQ0(0),則直接存儲收到的ID數據。

2)若閱讀器請求命令為REQ0(SNR)(SNR≠0),則作如下處理:返回數據首位補0,組成一個新數據,該數據逐位取代前一個存儲值的對應沖突位(前一個存儲值還繼續(xù)保留),得到一個新的存儲值。

3)若閱讀器請求命令為REQ1(SER),則返回數據首位補1,組成一個新數據;在ID存儲區(qū)中,搜索最新存儲的第SER位為首位沖突位的ID存儲值,用該新數據逐位取代該ID存儲值的對應沖突位(原存儲值還繼續(xù)保留),得到一個新的存儲值。

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

5)若閱讀器收到的ID數據無沖突位,則可識別出一個標簽ID。

假設標簽的編碼為8位,閱讀器作用范圍內有4個標簽,分別為

標簽A:01101010;

標簽B:01001011;

標簽C:00101010;

標簽D:10101001。

位屏蔽二進制搜索樹算法過程如表1所示。

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

2.2 算法仿真

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

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

為評價位屏蔽二進制搜索樹算法的性能,對位屏蔽二進制搜索樹算法和動態(tài)二進制搜索樹算法進行了仿真,由于識別每個標簽所需的平均比特數反映了防碰撞算法的平均最小時延,是衡量防碰撞算法的一個重要指標,所以,以識別每個標簽所需的平均比特數作為指標進行仿真,假定略去控制命令本身及前、后綴等所需的比特數,則

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

通過仿真結果可以看出,位屏蔽二進制搜索樹算法明顯優(yōu)于動態(tài)二進制搜索樹算法,這是由于位屏蔽二進制搜索樹算法減少了多余的重復傳送的比特數,效率更高,速度更快。

3 結 語

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

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

圖1 不同標簽數量情況下識別每個標簽平均比特數Fig.1 Average bit number of each tags identification in the case of different quantity of tags

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

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

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

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

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

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

[7] 廉國斌.射頻識別系統(tǒng)中的防碰撞算法研究[J].計算機技術與發(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] 劉東輝,張新嶺,邱金蕙,等.基于無線傳輸的智能小區(qū)門禁系統(tǒng)設計[J].河北科技大學學報(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;責任編輯:陳書欣

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