基于二進制搜索的RFID 標簽防碰撞算法研究

蔣 霞 白鐵成 鄭洪江

(塔里木大學信息工程學院，新疆 阿拉爾 843300)

射頻識別RFID(Radio Frequency Identification)是一種自動識別技術［1］。它以射頻方式進行非接觸式雙向通信，以達到自動識別目標并獲取其相關數據的目的。但目前RFID 技術也存在著很多亟待解決問題，例如安全和隱私，數據存儲和碰撞等。標簽防碰撞算法是RFID 系統需要研究和解決的一個重要課題。目前存在的RFID 防碰撞算法主要有2種:一種是基于ALOHA的不確定性算法［2］，另一種是基于二進制問詢的確定性算法。本文就基于二進制的RFID 標簽防碰撞算法進行了研究和改進。

1 二進制搜索的防碰撞算法介紹

二進制搜索算法的基本思想是將處于碰撞的標簽根據碰撞位分成左右兩個子集，先查詢一個子集，若沒有碰撞，則正確識別，若仍有碰撞則再分裂，依次類推，直到識別出子集中的所有標簽，再查詢另一個子集［3］。為了最簡捷地找到碰撞位，數據編碼選用曼徹斯特編碼［4］。依據曼徹斯特編碼的特點可以檢測出碰撞位。

為了實現算法，需要引入一組閱讀器命令［5］，這組指令能被標簽處理。以下為了舉例，假定標簽唯一的序列號ID 長度為8 bit，也就是說最多可以有256 個標簽處于運行狀態，實際中ID 較長。

REQUEST:請求命令，其參數根據算法而不同，該命令給向閱讀器識別范圍域內的所有標簽發送參數，標簽收到該命令后把自己的ID 與接收的相比較，若小于或者等于，則此標簽用其序列號回應閱讀器。若大于則不作任何回應。

SELECT:選擇命令，閱讀器用序列號作為參數發送給標簽，具有相同的序列號的標簽將以此作為執行其命令(讀出和寫入)切入開關，即選擇了這個標簽［6］。

RD－DATA:讀出選中的標簽，使其將存儲的數據發送給閱讀器。

UNSELECT:去選擇，取消一個被選中操作完的標簽，讓其進入“無聲”狀態，這樣標簽對收到的REQUEST 命令不再作回復。為了重新激活此類標簽，必須進行復位操作。

1.1 二進制樹搜索(BS)算法

1.1.1 算法描述

在BS 算法中，REQUEST 命令的參數為標簽的序列號ID。以4 個在閱讀器范圍內的標簽為例，說明這種算法的原理和標簽識別過程。標簽ID 分別為:10110010、10100011、10110011、11100011。

第一步，閱讀器向識別分為內所有合法標簽發送REQUEST(11111111)命令，所有標簽都用其序列號ID 響應，用曼徹斯特編碼得到解碼數據為1X1X001X，X 位碰撞位，得到下一次請求命令所需的參數。

第二步，閱讀器發送REQUEST(10111111)，標簽1、標簽2 和標簽3 響應。閱讀器得到解碼數據為101X001X。

第三步，閱讀器發送REQUEST(10101111)，只有標簽10100011 響應，無碰撞發生，閱讀器對該標簽進行處理后對它進行屏蔽操作，使其進入“無聲”狀態。重復上述過程直到識別完所有的標簽。

標簽2 通過3 次請求被閱讀器識別，應答RDDATA 命令。在讀出活寫入操作完成之后，閱讀器用UNSELECT 命令讓其進入“無聲”狀態，這樣標簽2 對后面的請求命令不再作應答。閱讀器用標簽1經過3 次請求被閱讀器識別到，標簽3 經過1 次請求命令被識別，最后標簽4 被識別。

1.1.2 性能分析

從大量的標簽中識別出一個標簽，需要多次問詢操作。其平均問詢次數由閱讀器識別范圍內的標簽總數n 決定，如公式(1)所示［7］。

BS 算法可以快速簡單地解決標簽碰撞問題。如果在閱讀器識別范圍內只有一個標簽，那么只需要一次問詢操作即可識別標簽，沒有碰撞發生。如果在閱讀器的識別范圍內有多于一個的標簽，那么問詢次數的平均值很快增加。

在8 位ID的標簽識別過程中，通過3 次問詢過程，另外加上最開始的1 次共操作［7］，完成一個標簽的識別平均需要4 次操作。在n 個待識別標簽中，完成n 個標簽的識別需要的總問詢次數如公式(2)所示。

所有標簽都需要發送完整的ID 來響應閱讀器的每一次查詢。識別n 個k 位序列號標簽，閱讀器需要傳輸的總比特數為標簽序列號長度與算法總問詢次數的乘積，如公式(3)。

1.2 動態二進制搜索(DBS)算法

1.2.1 算法思想

上述BS 算法，不僅搜索的范圍較大，而且標簽的序列號ID 每次完整地傳輸。而在實際中標簽的序列號長度按系統的規?？赡荛L達96bit 或更長，為了選擇一個標簽，數據傳輸量較大。因而DBS 算法被提出。

DBS 算法是國際標準ISO14443A 所推薦的防碰撞算法［8］。在BS 算法中，閱讀器傳輸的請求命令序列號與標簽應答的序列號部分信息是重復的，可以不必傳輸，這樣就得到了DBS 算法，如圖1 所示。DBS 算法中，假定K 為標簽序列號的最高位，請求命令為REQUEST(ID(K～X)，X)，X 為碰撞的最高位，序列號的K～X 位與參數相符的標簽，傳輸其(X－1)～0 位作為對閱讀器的響應。

圖1 DBS 算法原理

下 面 以 4 個 標 簽(10110010、10100011、10110011、11100011)為例說明標簽算法的執行過程。

第一步，閱讀器發送REQUEST(NUL)，處于閱讀器識別范圍的所有標簽都用其序列號響應，通過曼徹斯特編碼得到解碼數據為1X1X001X，碰撞最高位是第6 位，將該位置“0”，高于該位的不變，可得到下一次請求命令所需的參數(10)。

第二步，閱讀器發送REQUEST(10)，序列號前綴為10的標簽響應，即標簽10110010、10100011 和10110011 響應。返回各自的后6 位信息110010、100011、110011。閱讀器得到解碼數據為1X001X，將碰撞最高位D4 置為“0”，得到下一次命令所需的參數(1010)。

第三步，閱讀器發送REQUEST(1010)，只有序列號前綴為1010的標簽2 響應，閱讀器處理完標簽2 后用UNSELECT 命令使其進入“無聲”狀態。然后不斷重復上述操作直到所有標簽識別完。

1.2.2 算法性能分析由于DBS 算法與前面的基本二進制算法使用相似的搜索過程，因此在限制查詢范圍時動態二進制搜索算法也可以釆用與基本二進制算法相同的重復操作。故而可以得出動態二進制搜索算法總搜索次數如公式(4)。

DBS 算法識別標簽時，首先要求作用范圍內的所有標簽都上傳各自的序列號，n 個標簽的序列號總長度就是第一次上傳的數據長度，即整個序列號長度作為傳輸比特數。對某個標簽進行識別時，可以設標簽動態傳輸序列號部分位的平均值等于BS算法一半［7］。標簽需要傳輸的比特數為公式(5)所示。

將公式(3)和公式(5)比較，可以看出，采用DBS 算法時，標簽傳輸的數據量和傳輸時間比BS算法減少了近50%。閱讀器識別一次傳輸平均數據量為［9］公式(6)所示。

當閱讀器使用動態二進制搜索算法時，識別n個標簽所需要傳輸的序列號總長度為公式(7)所示。

下圖為BS 與DBS 算法中閱讀器用于問詢標簽傳輸序列號總長度比較。可以看出隨著標簽數的增多，DBS 算法所需的數據量是BS 算法的一半，提高了效率。

1.3 返回式二進制搜索(BBS)算法

1.3.1 算法的基本思想

BS 算法與DBS 算法之所以效率較低.最根本原因在于其無記憶性［10］。其識別完一個標簽，都要從頭再來，把剩下的標簽全部問詢一遍，而沒有利用上次搜索已經獲得的信息來縮小搜索范圍。

返回式策略是閱讀器每完成一個標簽的讀取，不是返回到根節點而是返回上一個碰撞發生的節點，識別此節點的另外一個分枝，這樣不斷重復操作，直到把所有標簽識別完［11］。

1.3.2 性能分析

BBS 算法在識別n 個標簽時，閱讀器共需搜索2n－1 次，當標簽數增多時，平均搜索次數為2 次。假設標簽序列號長度為k bit，則閱讀器發送的數據量為k(2n－1)bit。通過畫圖比較BS、DBS 和BBS之間的優劣。假設k=96。

從圖2 可以看出，基于BBS的算法相比DBS 算法有了改進，問詢數據量減少了25%，較BS 算法減少了57%。DBS的優點是減少了REQUEST 命令的參數長度，而BBS的優點是減少了問詢次數，如果能將兩者的優勢結合，必能提高性能?；诖吮疚奶岢隽艘韵赂倪M算法。

2 改進的二進制防碰撞算法

2.1 返回式動態二進制算法BDBS

根據以上三種基于二進制防碰撞算法的分析，本文研究了結合DBS 和BBS的優點的返回式動態二進制算法。由于該算法基于返回式算法和動態算法，因此簡稱為BDBS。其請求命令為REQUEST(ID(K～X)，X)，序列號K～X 位與之一致的標簽傳輸剩余的(X－1)～0 位信息作為應答，閱讀器完成一個標簽的識別后，返回上一個碰撞發生節點，識別該節點的另外一個分枝，而不是返回根節點，不斷重復操作，直到把每一個節點碰撞的所有標簽識別完。

在BDBS 算法中，閱讀器的問詢次數為2n－1，閱讀器每次問詢平均傳輸的數據量為(k +1)/2，所以閱讀器識別所有標簽所需要發送的數據量為公式(8)所示。

根據以上的對比分析，可以得出如圖2 所示仿真圖。

圖2 幾種算法搜索數據量比較

從仿真圖2 可以較為明顯地得出結論，對于返回式動態二進制搜索算法，閱讀器用于識別標簽的數據通信量最少，比返回式二進制搜索算法通信量減少近50%，比動態二進制搜索算法減少約67%，比BS 算法減少了約83%。

2.2 改進的BDBS 算法IBDBS(Improved BDBS)

在識別中，若遍歷到碰撞位只有一位時，說明只有兩個標簽發生碰撞，則認為沒有發生碰撞。對一個標簽的碰撞位認為是“0”。另一個標簽的碰撞位認為是“1”，直接使用SELECT(ID)命令選擇標簽。則閱讀器的問詢次數減少為公式(9)(［］為向上取整)。

則完成n 個標簽識別，閱讀器的數據通信量為公式(10)所示。

對閱讀器的問詢通信數據量進行比較。如圖3所示，IBDBS 標簽問詢數據量較BDBS 減少了約25%，性能得到了提高。

說明:此處如果考慮標簽搜索樹為滿樹，問詢次數應減掉n，如果搜索樹為非滿樹，減去n 顯然太多，最差的情況是減去2，取中間值n/2，這種取值使得仿真與實際性能之間有一定差距，但總體是有了改進。

下面從系統吞吐率性能來分析幾種算法，假設系統標簽數量為n，問詢標簽的平均操作數為L(n)，則定義系統吞吐率為公式(11)。

則BS、BDBS 及IBDBS 算法下系統的吞吐率分別為公式(12)、(13)、(14)。

對幾種算法吞吐率進行仿真比較如圖4 所示。隨著標簽數量的增多，BS 算法的吞吐率隨標簽數量的增多不斷減小，BDBS 算法的吞吐率穩定在50%，IBDBS 算法的吞吐率趨近于67%，相比較有了較大的提升。但是在IBDBS 中，請求命令REQUEST的參數長度當碰撞最高位較低時依然較長。而在REQUEST 命令中實際需要的只是最高碰撞位的位置，因此只要得到碰撞最高位的位置就可以了。

圖3 BDBS 與IBDBS的問詢數據量比較

圖4 三種算法吞吐率比較

李學橋等人在文獻［12］中提出了一種新的標簽搜索算法，在REQUEST(x)命令中，x 為碰撞最高位，即請求命令只傳輸碰撞最高位的二進制表示，請求第x 位為0的標簽響應。這種算法中搜索的數據長度為log2(k)，比如ID 為96 位的標簽，x的長度為log296，即x 可用7 位二進制表示，比DBS 算法請求命令(k +1)/2 減少了42 位，極大地減少了問詢標簽的數據通信量，節省了信道資源，提高標簽識別的速度。將這種算法與IBDBS 算法問詢次數少的優勢相結合，其吞吐率沒有改善，但是標簽問詢數據量大大減少，如公式(15)，當標簽數量接近100 時，比IBDBS 問詢數據量減少了約86.5%。如圖5所示。

圖5 IBDBS 與新改進算法的問詢數據量比較

圖6 新改進算法與李學橋算法比較

在李學橋的改進算法中，標簽問詢次數為2n－1 次，比本文的改進算法多，比較兩種算法的問詢數據量如圖6 所示，仿真圖中新算法比李學橋改進算法有所提高，當標簽數量增多時，問詢數據量減少25%。

3 結論

本文分析了結合DBS 及BBS 優點的返回式動態二進制算法BDBS，對三者的在標簽問詢通信數據量及吞吐率等性能方面進行了仿真比較，提出了改進的BDBS 算法IBDBS，將只有一位碰撞的情況認為無碰撞進行識別，系統性能得到較大的提高。基于李學橋等人提出的對REQUSET 命令參數的改進，本文對IBDBS 算法進行了新的改進，傳輸數據量進一步減少，系統吞吐率得到了提高，算法性能有了改進。仿真結果表明，通過對算法的改進，能有效地提高標簽識別的速度。

［1］史軍暉.基于捕獲效應的RFID 防碰撞算法研究［D］.廣東工業大學.2012.

［2］王雪，錢志鴻，胡正超.基于二叉樹的RFID 防碰撞算法的研究［J］.通信學報.2010，31(6):49－56.

［3］王秀玲，耿淑琴，蒙榮生，等.二進制搜索算法在系統中的實現.中國通信學會第五屆學術年會論文集［C］.2008.

［4］周曉光，王曉華.射頻識別(RFID)技術原理與應用實例［M］.北京:人民郵電出版社.2006:25－30.

［5］李興鶴，胡詠梅.基于動態二進制的二叉樹RFID 搜索結構反碰撞算法［J］.山東科學.2006(2):51－55 .

［6］江岸.無線射頻識別系統中防碰撞問題的研究(D).湖南大學.2009.

［7］楊恒.射頻識別－RFID 防碰撞算法研究(D).西南石油大學.2012.

［8］ISO/IEC 14443－3 identification cards contactless integrated circuit (s)card－proximity cards，part 3.initialization and anti－collision［S］.2003.

［9］鞠偉成，俞承芳.一種基于動態二進制的RFID 抗沖突算法［J］.復旦學報自然科學版.2005(01):46－50.

［10］劉康.基于無源RFID 標簽防碰撞算法的研究(D).山東大學.2012.

［11］余松森，詹宜巨，彭衛東，等.基于后退式索引的二進制樹形搜索反碰撞算法及其實現［J］.計算機工程與應用，2004，40(16):26－28.

［12］李學橋，賈小愛，趙磊.基于后退式索引的動態樹形防碰撞算法［J］.通信技術.2009，06(42).118－120.