基于RFID的二進制防碰撞算法的改進

王道強，李志鵬

(東北林業大學交通學院，哈爾濱150040)

1 RFID系統中的二進制防碰撞算法

二進制防碰撞算法是基于二進制樹理論，是把產生碰撞的標簽分裂成兩個結點0和1，若結點1中的標簽繼續發生碰撞，則再次分裂分成10和11兩個結點［1］。依此類推，直到識別出結點1中的所有標簽。如圖1所示。

圖1 二進制防碰撞算法模型Fig.1 Binary anti－collision algorithm model

2 二進制搜索 (Binary Search)算法

在二進制防碰撞算法的基礎上提出了二進制搜索算法，這是一種無記憶的算法，為了在一組電子標簽中選擇任意一個，閱讀器發出一個請求命令，有意識地將電子標簽傳輸時的數據碰撞引導到閱讀器上。閱讀器的命令查詢的是一個比特前綴，只有序列號與閱讀器查詢命令前綴相符的標簽才能響應閱讀器，并回送其序列號，當有多個標簽同時響應的時候，閱讀器把下一次發送的查詢命令的前綴增加一個比特0，通過不斷的增加命令前綴，使閱讀器能夠識別所有的標簽［2］。

2.1 算法的命令

(1)REQUEST:請求命令，該命令發送一組序列號作為參數給電子標簽。若電子標簽的序列號小于或等于閱讀器發送的序列號，則將自身的序列號回送給閱讀器。

(2)SELECT:選擇命令，用某個事先確定好的序列號作為參數發送給電子標簽。具有相同的序列號的標簽將此作為執行其他的命令 (例如讀出和寫入)的切入開關，即選擇了標簽。

(3)READDATE:讀出數據命令，選中的電子標簽將其存儲的數據發送給閱讀器。

(4)UNSELECT:去選擇命令，取消一個選中的標簽，標簽進入無聲狀態，這種狀態中的電子標簽完全是非激活的，對收到的REQUEST命令不作應答［3］。

2.2 算法的原理和執行過程

假設閱讀器周圍存在著四個電子標簽T1、T2、T3、T4，并 且 它 們 的 ID分 別 為 10111101、10101111、10110101、10100111。

第1步，閱讀器在其工作區域內發送命令REQUEST(11111111)，標簽序列號小于或等于閱讀器命令的與閱讀器進行通信。閱讀器對應答的標簽進行譯碼，得到解碼數據101XX1X1，判斷出發生碰撞的比特位D4、D3、D1［4］，進行如下處理:將D4位置“0”，高于D4位的不變化，低于D4位的置“1”，得到下一次命令所需要的序列號10101111。

第2步，閱讀器發送命令 REQUEST(10101111)，標簽T2和T4應答，對標簽進行解碼，得到解碼數據為1010X111，將最高碰撞位D3置“0”，得到下一次命令所需要的序列號10100111。

第3步，閱讀器發送命令 REQUEST(10100111)，只有標簽T4應答。無碰撞產生，閱讀器處理完標簽T4后，使其進入無聲狀態，接著重復上述過程直到識別所有的標簽為止。識別過程見表1。

表1 二進制搜索算法的實現過程Tab.1 Realization of binary search algorithm

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

二進制搜索算法有著明顯的缺陷，閱讀器發給每個標簽的比較序列，其中有用的信息只包含在高于上次碰撞碰撞位X比特的高位之中，而且每一次識別標簽之后都要從頭開始查詢，算法執行時間較長，為了解決這些缺陷，本文提出了改進的算法。

3.1 算法編碼原理

為了能夠在算法中準確的辨認出數據碰撞的比特位，改進的算法采用Manchester編碼［5］。該編碼也叫做相位編碼 (PE)，是一個同步時鐘編碼技術，是用電平的跳變 (上升沿/下降沿)來表示數值位。這里，虛線所在位置由高電平跳變到低電平，編碼為邏輯“1”;由低電平跳變到高電平，編碼為邏輯“0”，若不產生跳變，則視為非法數據，當作錯誤數據識別。當兩個或兩個以上標簽同時返回的數位出現不同值時，則上升沿與下降沿相互抵消，導致無狀態跳變，可知閱讀器的數據出現碰撞，出現了錯誤，應當進一步搜索，如圖2所示。

3.2 算法的原理和執行過程

在二進制搜索算法命令的基礎上，新增兩個命令。

(1)新增命令REQUEST(ID，1):這里的ID的取值表示的是閱讀器第一次與標簽進行通訊之后，對標簽的序列號進行譯碼，判斷出產生碰撞的比特位，我們規定把產生碰撞的比特位置“1”，沒有產生碰撞的比特位置“0”，從而得到的下一次尋呼的序列號。

1表示的是先處理鎖定的標簽碰撞位中最高位為1的標簽組。

圖2 Manchester編碼得到的沖突位Fig.2 The conflict bit in Manchester coding

(2)新增命令REQUEST(ID):

這里的ID的取值表示的是閱讀器在進行REQUEST(ID，1)命令之后，如果標簽繼續產生碰撞，同樣我們規定把產生碰撞的比特位置1，沒有產生碰撞的比特位置0，則標簽鎖定閱讀器第一次發出的ID中值為1的比特位，在接下來的防碰撞處理過程中，參與數據發送的僅僅是鎖定的幾個產生標簽碰撞的比特位，然后通過對標簽的譯碼所得到的下一次尋呼的鎖定序列號［6］。這里產生碰撞的標簽中，首先將鎖定的所有比特位中的最高位的值為1的標簽回送自己的序列號給閱讀器，并且返回鎖定位除最高位以外的其他鎖定位。

改進的二進制算法的工作流程圖如圖3所示。

圖3 改進的二進制防碰撞算法的工作流程圖Fig.3 Work flowchart of the improved binary anti－collision algorithm

改進的二進制算法的主要工作步驟為:

第1步，閱讀器在其工作區域內發送 REQUEST(全“1”序列)，標簽ID小于或等于閱讀器命令的與閱讀器進行通信。

第2步，閱讀器對應答的標簽進行譯碼，若無碰撞產生則識別標簽，使其進入無聲狀態。

第3步，若有碰撞產生，則對標簽進行譯碼，將產生碰撞的比特位置“1”，未產生碰撞的比特位置“0”，得到新增命令REQUEST(ID，1)。

第4步，閱讀器發送REQUEST(ID，1)，標簽再接收到該命令后，將閱讀器的命令ID與自己的序列號進行比較，鎖定產生碰撞的比特位，鎖定位中比特位最高位為1的標簽優先進行作答，并將除鎖定位以外的剩下幾位回送給閱讀器［7］。

第5步，閱讀器判斷回送的標簽序列號是否產生碰撞，若無碰撞產生則識別標簽，使其進入無聲狀態，若有碰撞產生，閱讀器對回送的標簽序列號繼續進行譯碼，判斷產生碰撞的比特位，將發生碰撞的最高比特位置1，高于該碰撞位的不變。低于該碰撞位的舍去，得到新增命令REQUEST(ID)。

第6步，閱讀器發送REQUEST(ID)，繼續判斷有無碰撞，每當順利的識別標簽之后，都將采用后退策略，返回上一次產生碰撞的結點，識別結點的另一個分支，直到把鎖定碰撞位的最高位為1的標簽組全部識別完。

第7步，閱讀器在識別完鎖定碰撞位最高位為1的標簽組之后，發送命令REQUEST(0)，識別鎖定碰撞位最高位為0的標簽組，過程原理同第5步和第6步。直到識別所有標簽結束。

下面舉例介紹改進算法工作的具體實現過程:

假設閱讀器周圍存在著四個電子標簽T1、T2、T3、T4，并 且 它 們 的 ID分 別 為 11100010、11110011、11100011、10100011。識別標簽 T2的具體操作流程如圖4所示。

圖4 改進的二進制搜索算法的實例操作流程Fig.4 Procedures of the example based on improved binary search algorithm

4 MATLAB 仿真分析

通過matlab仿真比較分析了在不同的情況下，改進的算法相比于二進制搜索算法的優勢。

(1)通信次數。二進制搜索算法識別n個標簽所需要的尋呼次數為QBS=n· ［integ(log2n)+1］，integ()表示向上取整函數［8］。而改進的算法的通訊次數Q改=2n－1，如圖5所示。

從圖可以看出，改進的二進制算法在閱讀器的尋呼次數上明顯低于二進制搜索算法，而且隨著n值的增大，改進的二進制算法優勢越明顯。

(2)傳輸時延。傳輸時延就是閱讀器從開始發送數據到數據全部發送完畢所需要的時間［9］，二進制搜索算法和改進的二進制算法的傳輸時延分別為:

圖5 改進的算法與二進制搜索算法的通信次數比較Fig.5 Comparison on the communication frequency of improved algorithm and binary search algorithm

其中x的取值范圍為 ［integ(log2n)，k］。

假設標簽ID的長度k的取值為64 bit，傳輸速率為100K bit/s，，產生碰撞的比特位數x取k時，得到算發法的傳輸時延隨標簽個數n的變化關系如圖6所示。

圖6 改進的算法與二進制搜索算法的傳輸時延比較Fig.6 Comparison on the transmission delay of improved algorithm and binary search algorithm

從圖6中可以看到即使x取最大值k，改進的二進制算法的傳輸時延都要小于二進制搜索算法。

(3)吞吐量。吞吐量代表有效傳輸的實際總效率［10］，二進制搜索算法和改進的算法的吞吐量分別為:

改進的算法和二進制搜索算法在吞吐量上的比較，從圖中可以看出在吞吐量上改進的算法的明顯優于二進制搜索算法，隨著n的增大，改進的二進制算法吞吐量趨近于50%如圖7所示。

5 結論

圖7 改進的算法與二進制搜索算法的吞吐量的比較Fig.7 Comparison on the transaction capacity of improved algorithm and binary search algorithm

在實際的情況下，RFID系統一般都使用較長的ID碼進行數據的傳輸，二進制搜索算法在每一次識別標簽之后都要從頭開始查詢，耗費大量的算法執行時間。通過matlab仿真對比分析，改進的二進制算法不僅節省了數據傳輸的時間，減少了通訊次數，而且在傳輸的效率上也明顯高于二進制搜索算法。

［1］康 東，石喜勤，李勇鵬.射頻識別核心技術與典型應用開發案例［M］.北京:人民郵政出版社，2008.

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

［3］ Wang T P.Enhanced binary search with cut－through operation for anti－ Collision in RFID systems［J］.IEEE Communications Letters，2006，10(4):236 －238.

［4］吳偉陵，牛 凱.移動通信原理［M］.北京:電子工業出版社，2005.

［5］傅祖蕓.信息論—基礎理論與應用［M］.北京:電子工業出版社，2001.

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

［7］ Shih D H，Sun P L，Yen D.Taxonomy and survey of RFID anticollision protocols［J］.Computer Communications，2006，29(11):2150－2166.

［8］單承贛，余春梅，王聰聰.改進的二進制查詢樹的RFID標簽防碰撞算法［J］.合肥工業大學學報，2008，31(11)，1801 －1804.

［9］ Choi J H.Query tree－based reservation for efficient RFID tag anticollision［J］.IEEE Communications Letters，2007，11(1):85 －87.

［10］李 瑾.無線射頻識別(RFID)防碰撞算法的研究和仿真［D］.北京:北京交通大學，2007.