一種基于二叉樹的RFID防碰撞改進算法

江　岸，姚幼敏

（廣東農工商職業(yè)技術學院計算機系，廣東廣州510507）

?

［應用研究］

一種基于二叉樹的RFID防碰撞改進算法

江岸，姚幼敏

（廣東農工商職業(yè)技術學院計算機系，廣東廣州510507）

電子標簽防碰撞是RFID系統(tǒng)中的一個關鍵問題，該文提出一種基于標簽識別碼分組的防碰撞算法。該算法根據(jù)標簽識別碼按位異或的結果，將待識別標簽分為兩個集合，通過分散閱讀器識別的標簽數(shù)目、簡化識別碼數(shù)據(jù)的傳輸、動態(tài)調整沖突檢測過程，有效的降低了標簽沖突概率和系統(tǒng)通信量。再利用并行處理策略，使閱讀器同時識別兩個標簽子集。理論分析和仿真結果顯示，該算法較其他二叉樹算法性能有明顯提升，具有良好的應用前景。

RFID；防碰撞算法；并行處理；二進制搜索

一、引言

射 頻 識 別（Radio frequency identification，RFID）是一種利用無線電訊號識別目標的通信技術，［1］它無需識別系統(tǒng)與被識別目標建立物理接觸，整個識別過程快捷方便，且無需人工干預。射頻識別技術及其應用正處于迅速發(fā)展上升階段，目前其在自動收費、防偽防盜、交通管理等諸多領域得到了越來越廣泛的應用。

一個基本的RFID系統(tǒng)由標簽、閱讀器和天線三部分組成。［1］標簽之間共享同一無線通信信道，當同一時刻有多個標簽發(fā)送數(shù)據(jù)時，閱讀器端必然因為信號干擾而無法正確接收數(shù)據(jù)，即會產生標簽碰撞問題。防碰撞算法是RFID系統(tǒng)中的一個核心問題，它對提升RFID系統(tǒng)性能至關重要。而一個優(yōu)秀的防碰撞算法必須具備識別精度高、識別延時低、功率消耗小等三個重要特點。目前按照標簽的響應方式，將防碰撞算法分為隨機算法和樹分叉算法兩種。

隨機算法基本思路是將通信信道劃分為若干個時隙，標簽只要有數(shù)據(jù)就會隨機選擇時隙發(fā)送，因此標簽之間會出現(xiàn)通信信道的競爭，若競爭成功，那么標簽被成功識別，若競爭失敗，標簽則會等待一段時間后再次隨機選擇時隙發(fā)送數(shù)據(jù)。該類算法比較簡單，易于實現(xiàn)，且標簽數(shù)較少時具有良好性能。但是由于隨機性大，當待識別標簽規(guī)模較大時，幀沖突現(xiàn)象嚴重，系統(tǒng)的性能將急劇下降，可能存在一個標簽在很長時間內都不能被識別的狀況，即“標簽饑餓問題（Tag Starvation）”現(xiàn)象。典型的隨機算法有純時隙ALOHA算法、幀時隙ALOHA算法等。［2-3］樹結構算法的識別精度較高，可以識別完所有待識別標簽，主要包括有查詢樹算法（Query Tree QT）［4］、ABS算法［5］、跳躍式動態(tài)樹形反碰撞算法（Jumping Dynamic Search JDS）［6］等。但現(xiàn)有樹分叉算法的主要問題是識別延時較大、通信復雜度較高，功率消耗也隨之增大，因此仍然有進一步提高的空間。

為此，筆者提出一種基于標簽識別碼分組的防碰撞算法，該算法根據(jù)標簽識別碼按位異或的結果，將待識別標簽分為兩個集合，降低了同一時間響應閱讀器的標簽數(shù)，從而減少了碰撞概率。并通過簡化識別碼數(shù)據(jù)的傳輸、動態(tài)調整沖突檢測過程，降低了系統(tǒng)的整體通信量。此外，該算法引入了并行處理策略，使得閱讀器同時識別兩個標簽子集，極大地提高了識別效率。

二、改進的算法

筆者提出的改進算法與文獻中的二叉樹搜索算法相比較，采取了較明顯的優(yōu)化措施，主要從以下一些方面進行改進：

降低標簽碰撞概率：改進算法將標簽ID比特位數(shù)據(jù)按位異或的結果存入計數(shù)器R當中，R值有0和1兩種情況，分別表示標簽識別碼中比特位“1”的個數(shù)是偶數(shù)和奇數(shù)的情況。根據(jù)R值，算法將標簽劃分為兩個子集，閱讀器分別識別每個子集，這樣縮小了閱讀器的識別范圍，降低了多個標簽同時發(fā)送數(shù)據(jù)而產生碰撞的概率。［7］

提高閱讀器識別效率：改進算法采取并行處理技術，閱讀器使用相同算法同時處理兩個標簽子集的沖突檢測過程。

降低系統(tǒng)傳輸?shù)耐ㄐ帕浚簶撕炛械膄lag和count是兩個預設的計數(shù)器，其中flag是表示標簽是否被激活的標識位，當flag=0時表示沒有被識別，收到閱讀器指令后，根據(jù)count標識的比特位為起始點傳輸自己的數(shù)據(jù)信息，這種動態(tài)傳輸標簽數(shù)據(jù)的措施有效減少了冗余數(shù)據(jù)的傳輸，當flag大于零時則表示標簽處于靜默狀態(tài)，此時不會響應閱讀器的命令。閱讀器為了減少指令傳輸?shù)拈L度，會利用上一次輪詢周期的信息，即把上次標簽比特碰撞的最高位作為Request指令。［8］

優(yōu)化碰撞處理技巧：每一輪閱讀器輪詢周期中，響應閱讀器的標簽都具有相同的R值，意味著所有響應的標簽，它們的ID中比特位“1”的個數(shù)具有相同的奇偶性。根據(jù)此特性，如果一次標簽碰撞只有兩次比特位產生沖突，那么可以直接識別出發(fā)生沖突的兩個標簽。例如標簽C：10101001、D：11001001都屬于按位異或結果為0的子集成員。閱讀器識別這兩個標簽時接收到的解碼為1××01001，根據(jù)曼徹斯特編碼規(guī)則能夠判斷只有兩個沖突位發(fā)生，閱讀器對成功接收到的標簽比特位1××01001進行按位異或的運算，此時結果為1，因此可知沖突位部分的按位異或結果也必須為1，即說明當中只有一個比特位值等于1，也就是說××部分應該是01和10，那么對應的標簽ID為10101001和11001001。

降低識別延時：當閱讀器在一次識別過程中檢測到有三次比特位沖突時，即終止本次搜索，進入下一次搜索周期，因為后續(xù)標簽比特位數(shù)據(jù)即使正確被接收也無法被利用，即無效數(shù)據(jù)，這樣有效地減少了識別過程中的識別延時。

（一）算法的相關指令

為了更好地描述算法，下面詳細介紹算法中使用的指令，算法中每個電子標簽擁有唯一的識別碼。［9］具體指令如下：

1.Request（m，n）-----請求命令：m表示上一次輪詢周期中比特位沖突的最高位置，n表示子集劃分的標志位。根據(jù)算法規(guī)定，只有標簽計數(shù)器R=n時，該標簽才能響應閱讀器。如果m+1> count，則令count=m+1。然后根據(jù)標簽的第m個比特位作出下一步判斷，當該位等于0時，標簽選擇從計數(shù)器count指向的比特位為起始數(shù)據(jù)傳輸點發(fā)送ID數(shù)據(jù)，若該位等于1時，那么對應的flag++，該標簽被屏蔽。此外，算法規(guī)定閱讀器進行第一次輪詢時發(fā)送Request（m-1，n）指令，m等于標簽的長度，搜索范圍內對應子集標識位n的所有標簽都會響應。［9］

2.Select（ID）-----選擇命令：當閱讀器確定讀取或者寫入某個標簽數(shù)據(jù)，則發(fā)送ID數(shù)據(jù)給標簽，只有與該ID數(shù)據(jù)匹配的標簽響應，并令flag--。

3.Read-Data-----讀出數(shù)據(jù)：被Select（ID）命令確定后的標簽，發(fā)送自己的數(shù)據(jù)信息給閱讀器。

4.Unselect-----去選擇：當標簽被成功識別后，閱讀器發(fā)送該命令，讓標簽變成“無聲狀態(tài)”，不再響應閱讀器命令。［10］

（二）算法的工作流程

由圖1可以看出，閱讀器同時對兩個標簽子集進行搜索，每個子集的具體搜索流程按照同一識別規(guī)則進行。假設閱讀器作用區(qū)域內有5個標簽，各個標簽的編碼及其識別過程如圖2所示。

圖1　算法整體框架

步驟1：閱讀器同時對兩個子集進行搜索識別，發(fā)出Request（7，0）和Request（7，1）。分別要求R=0和R=1的標簽響應閱讀器的指令，標簽在傳送子集識別碼時會附上子集的模塊標記，即R值，閱讀器會根據(jù)模塊標記值分類處理。

圖2　算法的搜索識別過程

步驟2：閱讀器處理R=0子集時，檢測出標簽碼沖突位是X0X102X3，有標簽1、2、3響應，在檢測到3個沖突位后即停止接收標簽數(shù)據(jù)。同時在處理R=1子集中，檢測出標簽沖突位是00X1X21304050617，有標簽4、5響應，則直接識別出標簽4：00110001和標簽5：01010001。因此R=1的子集即全部識別完。

步驟3：閱讀器處理R=0子集，發(fā)出Request（0，0），即要求第0位上比特位為“0”的所有標簽響應，標簽1、2響應，閱讀器解碼得到X102X304050617，只有2位沖突位，因此標簽1、2得到識別。

步驟4：閱讀器繼續(xù)處理R=0子集，發(fā)出Re?quest（7，0），要求所有未被識別的標簽響應，此時只有標簽3響應，直接識別。

由圖2可知識別按位異或為0的子集使用了3次搜索過程，識別按位異或為1的子集用了1次搜索過程。由于閱讀器是同時對兩個子集進行識別搜索，那么整個系統(tǒng)的搜索開銷等于兩個子集中較大一個子集的搜索開銷。因在此使用本算法識別5個標簽等同于只用了3次搜索過程，標簽與閱讀器之間的通信量為47。相比于傳統(tǒng)的二叉樹搜索算法，搜索次數(shù)和通信量都有了較大的優(yōu)化。

三、算法的性能分析

（一）閱讀器的搜索次數(shù)

命題：本算法中，為了成功識別閱讀器輪詢范圍內的N個標簽，假設需要S(N)次搜索，那么，

S(N)=MAX(2×(N1-K1)-1,2×(N2-K2)-1)（1）

其中R值等于1的標簽數(shù)量為N1，R值等于0的標簽數(shù)量為N2，標簽根據(jù)自己的R值被劃分為奇偶兩個子集，閱讀器分別對奇偶兩個子集進行識別，設在識別過程中只發(fā)生2次碰撞位的次數(shù)分別為K1、和K2。

證明：在跳躍式動態(tài)樹形反碰撞算法［6］中，當發(fā)生比特位沖突時，對應的沖突位分裂成0和1兩個子節(jié)點，將沖突范圍不斷縮小，節(jié)點分裂的過程也是二叉樹構建的過程，最后的葉子節(jié)點即待識別標簽ID。在跳躍式動態(tài)樹形反碰撞算法中，識別P個標簽的搜索次數(shù)是S(P)=2×P-1［6］，本算法繼承了該算法的識別優(yōu)點，在本算法中當只檢測出二次比特位發(fā)生沖突時可以直接識別兩個標簽，那么說明當只發(fā)生二次碰撞位時不需要分裂節(jié)點，這樣二叉樹的葉子節(jié)數(shù)得到修剪。假設閱讀器輪詢過程中出現(xiàn)了T次只有2次碰撞位的情況，那么本算法在跳躍式動態(tài)樹形反碰撞算法的基礎上減少了T個葉子節(jié)點，即二叉樹只有P-T個葉子節(jié)點。由此可知閱讀器的搜索次數(shù)變?yōu)椋?/p>

S(P)=2×(P-T)-1（2）

根據(jù)公式（2），可得識別子集N1個、N2個標簽的搜索次數(shù)為

S(N1)=2×(N1-K1)-1（3）

S(N2)=2×(N2-K2)-1（4）

由于本算法采用了并行策略，能同時對兩個子集進行標簽識別，所以整個系統(tǒng)的搜索次數(shù)等于兩個子集中較大的一個搜索次數(shù)。則識別完N個標簽的搜索次數(shù)：

S(N)=MAX(S(N1),S(N2))

=MAX(2×(N1-K1)-1,2×(N2-K2)-1)（5）

（二）算法的傳輸延時

假設待識別標簽數(shù)為n，標簽的ID長度為kbit，標簽數(shù)據(jù)傳輸速率為vbit/s，閱讀器在識別完所有標簽的過程中，標簽的k位ID中有m位發(fā)生了碰撞，由于碰撞位置是隨機的，則k位比特位中某一位發(fā)生碰撞的概率為

因此在本算法中，標簽每次發(fā)送數(shù)據(jù)的平均長度是

再加上標識標簽所屬模塊的1個比特位和閱讀器指令的長度2位，那么本算法中一次搜索的有效通信量是

因為數(shù)據(jù)傳輸?shù)臅r延是由閱讀器的搜索次數(shù)和有效通信量決定的，因此本文算法中的識別延時為

從（9）式可知本算法的識別延時主要是由識別完標簽的搜索次數(shù)決定。

（三）與其它算法的性能比較

通過MATLAB對改進算法和其它二進制搜索算法進行了性能的仿真對比。設標簽ID長度為64，標簽數(shù)據(jù)隨機分配，閱讀器和標簽的數(shù)據(jù)傳輸速率均為128 Kbps，搜索過程中的響應延遲為40 μs，空閑時隙為80 μs。

根據(jù)圖3的數(shù)據(jù)，我們可以看出，當待識別標簽數(shù)量增加時，改進算法的搜索次數(shù)要明顯優(yōu)于其他算法，這是因為當標簽樣本數(shù)較多時，按位異或結果分離的兩個子集標簽數(shù)趨于一致。即公式（5）中N1的值約等于N2，那么識別完N個標簽所需的搜索次數(shù)為：

圖3　算法搜索次數(shù)比較

S（N）≈2×（N/2-K1）-1=N-2XK1-1

由于識別標簽的搜索次數(shù)減少，再加上改進算法采取了簡化閱讀器指令，動態(tài)傳輸標簽識別碼的策略，因此較大程度降低了閱讀器與標簽之間的通信量，如圖4所示。通過公式（9）得知標簽的識別延時取決于搜索次數(shù)，而改進算法中閱讀器的搜索次數(shù)得到了有效地降低，所以標簽的識別延時也會隨之減少，如圖5所示。這說明算法的仿真結果與理論分析一致。

四、結束語

圖4　算法通信量比較

圖5　算法識別延時比較結論

筆者提出了一個改進的二進制搜索算法，根據(jù)標簽按位異或結果分為兩個子集，再通過并行策略的引入，有效地減少了標簽的碰撞概率和識別延時。理論分析和仿真比較均顯示本算法優(yōu)于文獻中的二進制搜索算法，且當標簽數(shù)量較多時，本算法優(yōu)勢越明顯。雖然算法增加了一定的硬件復雜度，但是由于在標簽中設置計數(shù)器的成本較低，且硬件增加的代價是遠小于整個識別系統(tǒng)的性能提升產生的價值，因此該算法具有良好的應用前景。

［1］ Ali K，Hassanein H，and Taha A E M.RFID anti-colli?sion protocol for dense passive tag environments［C］. IEEE Conference on Local Computer Networks，Dublin，Ireland，2007：819-824.

［2］ 吳海鋒，曾玉，豐繼華.無標簽數(shù)估計的被動RFID標簽防沖突二進制樹時隙協(xié)議［J］.計算機研究與發(fā)展，2012，49（9）：1959-1971.

［3］ Eom D F and Lee T J.Accurate tag estimation for dynam?ic framed-slotted ALOHA in RFID systems［J］.IEEE Communications Letters，2010，14（1）：60-62.

［4］ 王雪，錢志鴻，胡正超，等.基于二叉樹的RFID防碰撞算法的研究［J］.通信學報，2010，31（6）：49-57.

［5］ Jihoon Myung，Wonjun Lee，Jaideep Srivastava，Timo?thy K.Shih.“Tag-Splitting：Adaptive Collision Arbitra?tion Protocols for RFID Tag Identification”［J］.IEEE transactions on parallel and distributed systems，2007，18（6）：763-775.

［6］ 謝振華，賴聲禮，陳鵬.RFID技術和防沖撞算法［J］.計算機工程與應用，2007，43（6）：223-225.

［7］ FINKENZELLER K.RFID Handbook：Fundamentals and Applications in Contactless Smart Cards and Identifi?cation［M］.John Wiley&Sons Ltd，2003：187-193.

［8］ 伍繼雄，江岸，黃生葉，等.RFID系統(tǒng)中二叉樹防碰撞算法性能的提升［J］.湖南大學學報，2010，37（12）：82-96.

［9］ 江岸.無線射頻識別系統(tǒng)中防碰撞問題的研究［D］.長沙：湖南大學，2009：31-36.

［10］Auto-ID Center.Draft Protocol Specification for a 900MHz Class 0 Radio Frequency Identification tag［Z］. Auto-ID Center，2003.

（責任編輯：肖勝中）

An Improved RFID Anti-collision Algorithm Based on Binary Tree

JIANG An，YAO You-min
（Department of Computer Science，Guangdong Agriculture Industry Business Polytechnic，Guangzhou 510507，China）

Tag anti-collision is a key technology in RFID.This paper presents an anti-collision algorithm based on grouping mechanism of tag identification data.According to the result of bitwise XOR of tag identification data，we divide the unidentified tags into two groups，it greatly reduced the transmit data of system and tags collision probability by disperse the unidentified tags，simplify the transmit data of tag and adjust the process of conflict detection dynamically.In addition，the reader can identify two subsets according to parallel processing strategy. Theoretical analysis and simulation results show that the proposed algorithm has made a distinct progress in perfor?mance and has a well application prospect compared with other binary search Anti-collision algorithms.

RFID；anti-collision algorithm；parallel processing；binary search

TP273

A

1009-931X（2016）02—00063-05

2015-11-13

廣東農工商職業(yè)技術學院2014年度科研課題（xyzd1403）

江岸（1982-），男，湖南常德人，講師，碩士。研究方向：RFID防沖突算法。