RFID系統(tǒng)中二叉樹防碰撞算法性能的提升*

伍繼雄,江 岸,黃生葉?,何怡剛

(1.中國電子科技集團公司第七研究所,廣東廣州 510310,2.湖南大學(xué)計算機與通信學(xué)院,湖南長沙 410082)

RFID系統(tǒng)中二叉樹防碰撞算法性能的提升*

伍繼雄1,江 岸2,黃生葉2?,何怡剛2

(1.中國電子科技集團公司第七研究所,廣東廣州 510310,2.湖南大學(xué)計算機與通信學(xué)院,湖南長沙 410082)

針對RFID系統(tǒng)中的標(biāo)簽碰撞問題,提出了一種改進的二叉搜索樹防碰撞算法.通過劃分標(biāo)簽子集、動態(tài)調(diào)整沖突檢測過程,以減少標(biāo)簽沖突和系統(tǒng)開銷,提高識別效率.仿真結(jié)果表明,相比于目前的二叉樹搜索算法,本文方法在待識別標(biāo)簽數(shù)量較大的情況下提高了識別效率,減少了搜索次數(shù)及閱讀器與標(biāo)簽之間的通信量.

防碰撞;RFID;子集劃分;動態(tài)調(diào)整

在RFID技術(shù)的發(fā)展過程中,防碰撞技術(shù)是信號識別與處理的關(guān)鍵技術(shù)之一.當(dāng)在讀寫器的作用區(qū)域中有多個標(biāo)簽同時發(fā)送信號而產(chǎn)生信道爭用問題時,信號互相干擾,即發(fā)生了碰撞.因此,如何使用防碰撞技術(shù)識別多個目標(biāo)以及如何在保證識別精度的同時提高效率具有重要意義.

當(dāng)前廣泛使用的防碰撞算法有兩類:基于樹分叉的算法和基于A loha的算法[1-2].A loha算法實現(xiàn)相對簡單,效率也較低[3].樹分叉算法采用了確定性搜索的防碰撞策略,其核心思想是讀寫器根據(jù)沖突的信號,按照二叉樹深度優(yōu)先搜索的思想,逐步縮小搜索范圍,直到找到符合指定條件的標(biāo)簽.這類算法主要有跳躍式動態(tài)樹形防碰撞算法(Jumping Dynam ic Search JDS)[4],查詢樹算法(Query T ree QT)[5]、ABS 算法(Adap tive Binary Sp litting)以及文獻[6]中的改進動態(tài)二分搜索算法IDBS(imp roved dynamic binary search)等[1].樹分叉算法有更好的識別精度和信道利用率.但目前的樹分叉算法仍有較長的識別延時和較大的通信復(fù)雜度,需進一步改進.

本文提出的標(biāo)簽防碰撞算法在文獻[6]中算法的基礎(chǔ)上,通過劃分標(biāo)簽子集、動態(tài)調(diào)整沖突檢測過程,旨在大幅度地減少標(biāo)簽沖突和讀寫器與標(biāo)簽之間的通信量.并通過仿真檢驗算法的性能.

1 算法的幾點約定

1)本算法基于樹分叉搜索算法,要求閱讀器能夠準(zhǔn)確地識別出數(shù)據(jù)碰撞位的位置,采用了曼徹斯特編碼[7].該編碼約定邏輯“1”對應(yīng)信號含下降沿跳變,而邏輯“0”對應(yīng)信號含上升沿跳變.若無狀態(tài)跳變,視為錯誤被識別.當(dāng)兩個或多個標(biāo)簽同時返回的某一數(shù)位有不同的值,則接收到的上升沿和下降沿相互抵消,以致出現(xiàn)“沒有變化”或變化被明顯削弱的狀態(tài),閱讀器由此可判斷該位出現(xiàn)了碰撞.假設(shè)標(biāo)簽1和標(biāo)簽2的ID分別是01010011和00110011,利用曼徹斯特編碼能按位識別出碰撞位的示意圖如圖1所示.由于標(biāo)簽1和2是同時傳送其數(shù)據(jù),利用曼徹斯特編碼閱讀器解碼為0XX 1X0X1,于是閱讀器檢測出第1,2,4和6比特出現(xiàn)碰撞.

圖1 用曼徹斯特編碼的碰撞情況Fig.1 Co llision cases with M anchester codes

2)標(biāo)簽內(nèi)部設(shè)置了一個計數(shù)器R用于存儲標(biāo)簽ID中所有比特位的按位異或的結(jié)果,例如標(biāo)簽ID:01001001,則標(biāo)簽中計數(shù)器R的值為1,這個計數(shù)器的值可以在標(biāo)簽制造時由工廠固化寫入.因為該計數(shù)器值可以是0或者1,分別代表標(biāo)簽ID中‘1'的個數(shù)是偶數(shù)和奇數(shù)的情況,所以增加該計數(shù)器R是為了將標(biāo)簽劃分為更小的兩個子集.

為了動態(tài)傳輸標(biāo)簽ID數(shù)據(jù),標(biāo)簽中計數(shù)器flag是表示標(biāo)簽是否被屏蔽的標(biāo)志位,為0表示沒有被屏蔽,可以響應(yīng)閱讀器的命令,傳送從計數(shù)器count指向的對應(yīng)位開始的ID數(shù)據(jù),該標(biāo)志非零表示標(biāo)簽被屏蔽,不響應(yīng)閱讀器的命令.

3)為了便于描述算法,引入以下有關(guān)指令:

a)Request(m,n)請求命令:m為上一次搜索過程中標(biāo)簽第1次碰撞的位置,n為劃分標(biāo)簽子集的標(biāo)識位.標(biāo)簽收到這個請求命令后,只有其計數(shù)器R的值與子集標(biāo)識位n相匹配的標(biāo)簽響應(yīng)請求命令.若匹配,當(dāng)m+1的值大于計數(shù)器count值時,令count=m+1.檢查此m指定的自己ID對應(yīng)的比特位,若為0,則從計數(shù)器count指向的比特位開始傳送自己的ID數(shù)據(jù),若為1,則將計數(shù)器flag值加一,即將標(biāo)簽屏蔽.閱讀器第1次搜索時發(fā)送Request(L-1,n),L為標(biāo)簽ID的長度,要求區(qū)域內(nèi)所有匹配子集標(biāo)識位n的標(biāo)簽應(yīng)答.

b)Select(ID)選擇命令:把某個事先確定的ID作為參數(shù)發(fā)送給標(biāo)簽.具有指定ID的標(biāo)簽將以此作為執(zhí)行后續(xù)命令(例如讀寫和寫入數(shù)據(jù))的切入開關(guān),即選擇這個標(biāo)簽.具有其它ID的標(biāo)簽將自己的計數(shù)器flag值減一.

c)Read-Data讀出數(shù)據(jù):選中的標(biāo)簽將存儲的數(shù)據(jù)發(fā)送給閱讀器.

d)Unselect去選擇:取消一個事先選中的標(biāo)簽,標(biāo)簽進入“無聲狀態(tài)”.

2 算法要點和實現(xiàn)

2.1 算法要點

1)閱讀器每次發(fā)送的Request指令指出了上1次搜索過程中標(biāo)簽第1次碰撞的位置,減少了指令長度.

2)由于一次搜索過程中所有響應(yīng)的標(biāo)簽的計數(shù)器值R都相等,則說明每個標(biāo)簽ID的按位異或結(jié)果相等,等效于每個響應(yīng)標(biāo)簽ID中‘1'的個數(shù)有相同的奇偶性.因此一次搜索過程中不可能出現(xiàn)只有一次沖突的情況.

3)一次搜索過程中只有兩次比特位發(fā)生沖突時,可以直接識別出兩個標(biāo)簽.例如對計數(shù)器值R為1的標(biāo)簽識別過程如下.

ID1:01001001 ID2:11000001

閱讀器端接收到解碼為:×100×001,發(fā)現(xiàn)有兩個沖突位.對閱讀器正確接收部分×100×001進行按位異或結(jié)果為0,表示正確接收部分ID中‘1'的個數(shù)為偶數(shù),而這兩個標(biāo)簽的計數(shù)器值R都為1,說明這兩個標(biāo)簽ID中‘1'的個數(shù)為奇數(shù),可以判斷兩個沖突標(biāo)簽在這兩個沖突位中有且僅有一個比特位值為1,因此可以快速的識別出標(biāo)簽 01001001和11000001.

4)閱讀器檢測到有3次比特位發(fā)生沖突時,即停止接受標(biāo)簽傳送的后續(xù)數(shù)據(jù),進入下一次搜索過程,這樣有效地減少了標(biāo)簽的識別延時和閱讀器與標(biāo)簽之間的通信量.需要強調(diào)的是,目前的信號處理技術(shù)和半導(dǎo)體工藝水平已能為這種處理提供支持.例如,主流的數(shù)字信號處理器(DSP)的指令速度已達(dá)到400 MIPs以上,UHF頻段的 RFID標(biāo)準(zhǔn)中規(guī)定的信息速率為640 kbps,在傳送一bit信息的時間內(nèi),DSP可以執(zhí)行約700條指令,因此一旦比特沖突(碰撞)發(fā)生,讀寫器內(nèi)處理器在標(biāo)簽傳輸一個比特的時間后發(fā)起新一輪標(biāo)簽搜索過程是容易實現(xiàn)的.

2.2 算法實現(xiàn):

本算法的實施依賴于閱讀器與標(biāo)簽,因此下面分兩部分描述算法的詳細(xì)流程.閱讀器中初始狀態(tài)棧stack和string均為空,標(biāo)簽的ID為L位,每個標(biāo)簽的計數(shù)器flag和count均為0.算法中符號ID (i,j)表示標(biāo)簽傳送從第i～第j比特的ID數(shù)據(jù)位.‘+'表示連接操作,例如‘0010'+‘1000'=‘00101000'.表達(dá)式XOR(ID識別)表示對已經(jīng)識別的部分ID進行按位異或.標(biāo)簽的算法描述如下:

假設(shè)ID代碼為8位,閱讀器作用范圍內(nèi)有5個標(biāo)簽,它們在文中的代號及ID碼見表1,閱讀器如何利用該算法來識別它們,如表2所示.由于簡化了閱讀器命令,當(dāng)閱讀器檢測到3次比特位發(fā)生沖突時即停止接受標(biāo)簽傳送的數(shù)據(jù),因為此后標(biāo)簽發(fā)送的比特數(shù)據(jù)是沒有意義的,這樣可節(jié)省數(shù)據(jù)傳輸時間.除此之外,該算法根據(jù)計數(shù)器R將標(biāo)簽分成兩個子集分類進行識別,若一次搜索完畢只檢測出二次比特位發(fā)生沖突可以直接識別兩個標(biāo)簽,提高了標(biāo)簽識別的效率.從表2可知,識別5個標(biāo)簽只用了4次搜索過程,標(biāo)簽與閱讀器的直接通信量為41.

表1 幾個8位ID碼標(biāo)簽舉例Tab.1 An examp le of several tagswith 8-bit identifying codes

表2 標(biāo)簽識讀過程例Tab.2 An examp le of identifying tags

3 算法的分析與比較

采用本算法,識別完閱讀器作用范圍內(nèi)的 N個標(biāo)簽所需的搜索次數(shù)記為S(N),N個標(biāo)簽中有N 1個標(biāo)簽的計數(shù)器R值為1,N2個標(biāo)簽的計數(shù)器R值為0,參照跳躍式動態(tài)樹形防碰撞算法的有關(guān)方法進行對比分析[4],可推出本文算法的時間復(fù)雜度為:

本算法相對于已有的二叉樹搜索算法有如下一些優(yōu)勢:

1)由于將標(biāo)簽劃分為兩個子集分類識別,減小了沖突的概率.當(dāng)標(biāo)簽ID號相對集中時,探測到只有兩次比特位發(fā)生沖突的機率比較大,能減少搜索的次數(shù).

2)簡化了閱讀器發(fā)送的指令,同時當(dāng)檢測到有3次比特位發(fā)生沖突時即停止接受標(biāo)簽傳送的數(shù)據(jù),立刻對標(biāo)簽作出沖突處理,有效地減少了標(biāo)簽的識別延時和閱讀器與標(biāo)簽之間的通信量.

3)閱讀器利用棧stack和字符串string來保存已經(jīng)被閱讀器接收到的標(biāo)簽ID數(shù)據(jù),因此每次搜索中標(biāo)簽只需傳送部分?jǐn)?shù)據(jù),在文獻[6]IDBS算法的基礎(chǔ)上減少了傳輸時間.

閱讀器的搜索次數(shù)和閱讀器與標(biāo)簽之間的通信量直接影響到標(biāo)簽的識別速度.若閱讀器需要M次搜索才能識別N個標(biāo)簽,每次搜索時間t是由閱讀器命令傳輸時間treader,標(biāo)簽ID數(shù)據(jù)傳輸時間ttag,標(biāo)簽對閱讀器命令的響應(yīng)時間DE tag,閱讀器的沖突檢測時間 DE reader組成.閱讀器的數(shù)據(jù)發(fā)送速率為DR reader,標(biāo)簽的數(shù)據(jù)發(fā)送速率為DR tag.RL i為第i次搜索中閱讀器的指令長度,TLi為第i次搜索中標(biāo)簽發(fā)送的數(shù)據(jù)比特長度,ti為第 i次搜索時間, t delay為一次搜索中的響應(yīng)延遲.識別N個標(biāo)簽需要的總時間為:

從式(5)可知閱讀器識別完N個標(biāo)簽的時間T主要由通信量NUM,和搜索次數(shù)M決定.

由于本文算法是基于標(biāo)簽ID碼的奇偶性進行預(yù)分集的動態(tài)二分搜索算法,因此簡記為PDBS(parity -based dynamic binary search).設(shè)標(biāo)簽ID長度是64位,

標(biāo)簽ID隨機分配,DR reader和DR tag均為40 kbps,t delay為20μs,一個空閑時隙為40μs,通過編程并運行本算法與文獻[6]的IDBS算法、跳躍式動態(tài)樹形防碰撞算法JDS、查詢樹算法QT、ABS算法進行仿真.搜索次數(shù)的比較見表3.

表3 各算法搜索次數(shù)比較Tab.3 Comparison of the searching times of different algorithms

可以看出,隨著標(biāo)簽的增多,本文算法中閱讀器搜索次數(shù)相對于其它算法最少,這是因為多標(biāo)簽時,發(fā)生兩次比特位沖突的概率增大,導(dǎo)致本算法優(yōu)勢更明顯.本算法采取了簡化閱讀器指令、動態(tài)傳輸ID數(shù)據(jù)策略,使得閱讀器與標(biāo)簽之間的通信量明顯少于JDS和QT算法.

表4為各算法識別同樣數(shù)量標(biāo)簽條件下不同算法讀寫器所發(fā)出的信息量的比較.由于本算法減少了閱讀器的搜索次數(shù)并通過硬件配合減少了閱讀器與標(biāo)簽之間一些不必要的通信量,根據(jù)式(5)可知標(biāo)簽的識別延時也將隨之減少,這與我們的仿真結(jié)果一致.識別延時的比較如表5所示.在待識別標(biāo)簽數(shù)較大時,本算法識別標(biāo)簽的耗時小于所有其它算法,有更高的識別速率.表3～5所列的每項數(shù)據(jù),都是10次運行結(jié)果的平均,每次所用標(biāo)簽的ID編號是隨機產(chǎn)生的.

表4 各算法讀寫器發(fā)送信息量比較Tab.4 Comparison of the traffic transferred by the reader of different algorithms bit

表5 各算法耗時比較Tab.5 Execution time comparison of different algorithms ms

4 結(jié) 語

標(biāo)簽防碰撞算法對RFID系統(tǒng)識別效率至關(guān)重要,本文提出的防碰撞算法相對于目前的二叉樹搜索算法,能夠在保證識別精度的前提下,明顯提高RFID系統(tǒng)的識別速率.所提出的算法涉及了對讀寫器的指令進行改進,并需要硬件系統(tǒng)的支持.設(shè)計并實現(xiàn)支持本算法的讀寫器以將本文算法付諸實踐是作者下一步要開展的主要工作之一.

[1] M YUNG J,LEEW,SRIVASTA VA J,eta l.Tag-splitting:adaptive collision arbitration p rotocols for RFID tag identification[J].IEEE Transactions on Parallel and Distribu ted System s,2007,18(6):763-775.

[2] VOGT H.E fficient ob ject identification with passive RFID tags[C]//Proceedings of International Conference on Pervasive Com puting.Berlin:Springer,2002.98-113.

[3] A IBERTO LG,INDRA W.Comm unication netw ork s fundamental concep ts and key architectures[M].New York:M c-Graw-H ill,1999:354-365.

[4] 余松森,詹宜巨,王志平,等.跳躍式動態(tài)樹形反碰撞算法及其分析[J].計算機工程,2005,31(9):19-26.

YU Song-sen,ZHAN Yi-ju,WANG Zhi-ping,et a l.A nti-collision algorithm based on jumping and dynamic searching and its analy sis[J].Compu ter Engineering,2005,31(9):19-26.(In Chinese)

[5] LAW C,LEE K,SIU K Y.Efficient mem ory less protocol for tag Identification[C]//Proceedings of the 4th International W orkshop on Discrete A lgorithm s and Methods for Mobile Compu ting and Comm unications.Boston:ACM,2000:75-84.

[6] 江岸,伍繼雄,黃生葉,等.一種改進的RFID二進制搜索防碰撞算法[J].計算機工程與應(yīng)用,2009,35(5):229-235.

JIANG Aan,WU Ji-xiong,HUANG Sheng-yie,et al.Improved RFID binary search anti-collision algorithm[J].Computer Engineering,2009,35(5):229-235.(In Chinese)

[7] FINKENZELLERK.RFID handbook:radio-frequency identification fundamen tals and applications[M].John Wiley and Sons,2003:187-193.

[8] The International Standard Organization.ISO/IEC FDIS 18000-6-2003 Information technology automatic identification and data capture techniques-radio frequency identification for item management air interface-part 6[S].Parameters for Air Interface Communications at 860-960MHz,USA:ISOPress,2003.

Imp rovement of the Binary-searching-based Anti-collision A lgorithm of RFID System s

WU Ji-xiong1,JIANG An2,HUANG Sheng-ye2?,HE Yi-gang2

(1.NO.7th Research Institute,China Electronics Techno logy G roup Corporation,Guangzhou,Guangdong 510310,China; 2.College of Computer and Communication,Hunan Univ,Changsha,H unan 410082,China)

To address the tag collision problem in Radio Frequency Identification(RFID)system,an improved binary-tree anti-collision algorithm was p roposed.By dividing the tags into different subsets and ad justing dynamically the process of collision detection,the collision probabilities and power consum ption were reduced.The simulation resultshave show n that,com pared w ith other binary-tree anti-collision algorithm s,the p roposed algorithm enhances the identifying efficiency,and both the num ber of searching times and the bits transferred between the reader and the tags are relatively low when the number of tags is large.

collision avoidance;radio frequency identification;subset-division;dynamic ad justm ent

TN914.3

A

1674-2974(2010)12-0082-05 *

2009-11-16

國家863計劃先進制造技術(shù)領(lǐng)域重大資助項目(2006AA 04A 104)

伍繼雄(1970-),男,廣東臺山人,湖南大學(xué)博士,中國電子科技集團公司高級工程師

?通訊聯(lián)系人,E-mail:sheryl_huang@163.com