一種新型RFID動態多叉樹查詢防碰撞算法

陸冰清，牛國柱，趙英臣

（1.南京理工大學 機械工程學院，南京 210094；2.山東齊銀水泥有限公司，淄博 255400）

0 引言

隨著信息技術的發展，射頻識別（Radio Frequency Identif i cation）技術被廣泛地應用于生產管理和工業制造自動化等領域。RFID技術利用射頻信號通過空間耦合（交變磁場或電磁場）實現非接觸信息傳遞并達到識別目的。RFID系統一般包含射頻標簽（Tag）、讀寫器（Read/Write Device）和數據管理系統三部分。其中，每個標簽都含有唯一的識別碼；讀寫器與計算機系統進行通信，從而對標簽進行非接觸讀寫操作。

RFID系統在工作時，可能會有多個標簽同時處在閱讀器的作用范圍內。這樣如果有兩個或兩個以上的應答器同時發送數據，就會出現通信沖突，即碰撞。解決信道沖突的方法有四種：空分多址（Space Division Multiple Access，SDMA）、頻分多址（Frequency Division Multiple Access，FDMA）、碼分多址（Code Division Multiple Access，CDMA）和 時 分 多 址（Time Division Multiple Access，TDMA）。在RFID系統中，一般采用時分多址法來解決碰撞。TDMA是一種把整個可供使用的通路容量按時間分配給多個用戶的技術。

常用的基于TDMA思想的防碰撞算法主要分為兩大類：1）基于時隙隨機分配的ALOHA算法，包括時隙ALOHA算法和分群時隙ALOHA算法等。2）基于二進制樹型搜索算法，包括動態二進制搜索算法和查詢樹搜索算法等。

由于ALOHA算法吞吐量低，識別速度緩慢，還可能出現標簽在相當長得一段時間內無法識別，該算法不適宜大規模標簽讀取。而樹型的標簽防碰撞協議可以達到百分之百的讀取率，本文對查詢樹搜索算法在標簽數量較多識別效率較低的問題進行研究，提出一種新的動態多叉樹查詢算法，有效地提高了RFID系統的識別效率。

1 改進的動態多叉樹查詢算法

查詢樹算法的基本思想是將碰撞的標簽分成兩個子集0和1，先查詢子集0，如果沒有碰撞，則正確識別標簽，如果碰撞則再分裂，把子集分成00和01兩個子集，以此類推，直至識別出子集0中的所以標簽，再按步驟查詢子集1。

1.1 算法設計思路

動態二叉樹查詢算法就是基于上述分解原理的防碰撞算法，它在此基礎上采用曼徹斯特編碼，這種編碼采用半個周期的正負跳變來表示0和1，在數據傳輸過程中“沒有變化”的狀態是不允許的。因此，當閱讀器收到標簽的返回信號后，如果發現某些位信號的狀態沒有發生改變，那么閱讀器就能夠判斷這些位一定發生了相互之間的沖突，如圖1所示。

圖1 曼徹斯特編碼

利用碰撞位信息，沒有發生碰撞的比特位直接跳過，檢測下一比特位，這樣可以提高搜索效率，避免出現空閑時隙。但是動態二叉樹算法在每次碰撞時僅分成兩支，當待識別標簽數量較多時，在搜索的初期會頻繁出現碰撞，搜索效率偏低。如圖2所示，RFID系統內有8個4bit的待識別標簽，標簽ID分別為：Tag1:1100 Tag2:0111 Tag3:0101 Tag4:1110 Tag5:1101 Tag6:0100 Tag7:1111 Tag8:0110。查詢過程中定義三種時隙。

1）可讀時隙：只有一個標簽應答，閱讀器正確識別；

2）碰撞時隙：多個標簽應答導致碰撞；

3）空閑時隙：沒有符合查詢條件的標簽，無應答。

圖2 動態二叉樹查詢算法

由圖2可以看出，完成整個標簽的搜索共需14個時隙，其中6個是碰撞時隙，搜索深度有3層。

動態四叉樹查詢算法為了避免頻頻發生碰撞，在檢測到碰撞時將響應的標簽分為四個分支依次查詢，仍以上述8個標簽為例，搜索流程如圖3所示。

圖3 動態四叉樹查詢算法

由圖3可以看出，動態四叉樹算法只有2個碰撞時隙，但多了2個空閑時隙，而且當標簽數量較少時會產生很多空閑時隙，效率未必比二叉樹更好。在上述RFID系統中，標簽的第一比特位碰撞，第二比特位沒有碰撞，根據曼徹斯特碼的編碼特性，可以直接確定第二比特位，采用二叉樹；標簽的第三和第四比特位都發生碰撞，則采用四叉樹。如圖4所示。

圖4 動態多叉樹查詢算法

由圖4可以看出，采用多叉樹查詢算法只有2個碰撞時隙，沒有產生空閑時隙，總時隙也小于前面兩種算法，效率更高。

1.2 算法原理及流程

上述例子說明如果防碰撞算法能根據某種準則自動選擇搜索叉樹時可以提高搜索效率。這種情況下可以充分利用碰撞位信息，規定當檢測到某比特位發生碰撞時，再檢測下一位是否發生碰撞，如果沒有碰撞，則采用動態二叉樹；如果碰撞則采用動態四叉樹。新的算法根據碰撞比特位的分布選擇分叉樹，所以稱為動態多叉樹查詢算法。

該算法的搜索流程圖如圖5所示，分為以下四個步驟。

步驟1：讀寫器初始化查詢數組，使之為空數組，并發出搜索命令。

步驟2：符合查詢條件的標簽響應，讀寫器根據標簽響應確定時隙狀態。

步驟3：根據碰撞比特位的分布（相鄰兩位都碰撞，采用四叉樹，否則采用二叉樹，沒有發生碰撞的比特位跳過），動態地選擇搜索叉數，并將新的查詢碼寫入查詢數組。

步驟4：判斷搜索深度是否達到最大值，如果不是，返回步驟2繼續搜索。否則，算法結束。

1.3 算法分析

一般來說，RFID系統中標簽的數量越多，出現碰撞的位數越多，相鄰兩位都發生的概率越大，可見選擇四叉樹還是二叉樹與分支內標簽個數緊密相關。下面從概率論的角度分析本文提出的算法。

假設RFID系統當前分支內有N個符合查詢條件的待識別標簽，任意比特位不發生碰撞的概

則當前分支采用二叉樹的概率為：

圖5 動態多叉樹查詢算法搜索流程圖

采用四叉樹的概率為：

由式（1）、式（2）可以看出分支內標簽個數越少，采用二叉樹的概率較大，即碰撞的位數越少，相鄰位碰撞的概率也越??；反之采用四叉樹的概率較大。

2 算法仿真與分析

通過Matlab對上述算法進行仿真分析（標簽ID為32bit），仿真結果在同等條件下取20組數據求均值。仿真結果如圖6和圖7所示。其中定義吞吐率為：

圖6 三種算法碰撞時隙和空閑時隙對比

圖6和圖7分別為動態多叉樹，二叉樹和四叉樹三種算法所需碰撞時隙、空閑時隙和吞吐率的比較。從圖中可以觀察出，單純的二叉樹搜索算法碰撞時隙較多；單純的四叉樹搜索算法空閑時隙較多；動態多叉樹搜索算法改進了這兩種算法的缺點，使吞吐率提高15%左右，從而提高了搜索效率，減少搜索時間。

3 結束語

圖7 三種算法吞吐率對比

本文基于傳統的查詢樹防碰撞算法，提出了一種動態多叉樹查詢算法。新算法改進了單純動態二叉樹和四叉樹查詢算法的缺點，通過對三種算法的仿真分析，表明本文提出的算法減少了搜索過程的總時隙，有效的提高了搜索效率和時隙的吞吐率，可以顯著提高工業生產和物流管理的工作效率。

本文創新點：本文提出的算法充分利用曼徹斯特編碼可以識別碰撞位的特性，通過碰撞位的分布情況，檢測相鄰兩位的碰撞情況，動態的調整搜索叉樹，從而更好的解決了射頻識別系統中標簽應答沖突問題。

[1] Finkenzeller K著, 陳大才譯.射頻識別(RFID)技術[M].北京: 電子工業出版社, 2006.

[2] 王雪, 錢志鴻, 胡正超等.基于二叉樹的RFID防碰撞算法的研究[J].通信學報, 2010, 31(6): 50-57.

[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] Jihoon Myung, Wonjun Lee, Srivastava J.Adaptive binary splitting for efficient RFID tag anti-collision[J].IEEE Communications Letters, 2006, 10(3): 144-146.

[5] 劉路, 陳洪云, 何怡剛.一種新型RFID聯合防碰撞算法[J].微計算機信息, 2010, 26(10): 145-146.

[6] 丁治國.RFID關鍵技術研究與實現[D].合肥: 中國科學技術大學, 2009.