RFID系統中二叉樹防碰撞算法性能的提升*

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

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

RFID系統中二叉樹防碰撞算法性能的提升*

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

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

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

防碰撞;RFID;子集劃分;動態調整

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

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

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

1 算法的幾點約定

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

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

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

為了動態傳輸標簽ID數據,標簽中計數器flag是表示標簽是否被屏蔽的標志位,為0表示沒有被屏蔽,可以響應閱讀器的命令,傳送從計數器count指向的對應位開始的ID數據,該標志非零表示標簽被屏蔽,不響應閱讀器的命令.

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

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

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

c)Read-Data讀出數據:選中的標簽將存儲的數據發送給閱讀器.

d)Unselect去選擇:取消一個事先選中的標簽,標簽進入“無聲狀態”.

2 算法要點和實現

2.1 算法要點

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

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

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

ID1:01001001 ID2:11000001

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

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

2.2 算法實現:

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

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

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

表2 標簽識讀過程例Tab.2 An examp le of identifying tags

3 算法的分析與比較

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

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

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

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

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

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

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

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

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

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

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

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

表4 各算法讀寫器發送信息量比較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 結 語

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

[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] 余松森,詹宜巨,王志平,等.跳躍式動態樹形反碰撞算法及其分析[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].計算機工程與應用,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計劃先進制造技術領域重大資助項目(2006AA 04A 104)

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

?通訊聯系人,E-mail:sheryl_huang@163.com