陸冰清，牛國柱，趙英臣

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

0 引言

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

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

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

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

1 改進的動態(tài)多叉樹查詢算法

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

1.1 算法設計思路

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

圖1 曼徹斯特編碼

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

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

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

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

圖2 動態(tài)二叉樹查詢算法

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

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

圖3 動態(tài)四叉樹查詢算法

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

圖4 動態(tài)多叉樹查詢算法

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

1.2 算法原理及流程

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

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

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

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

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

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

1.3 算法分析

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

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

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

圖5 動態(tài)多叉樹查詢算法搜索流程圖

采用四叉樹的概率為：

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

2 算法仿真與分析

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

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

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

3 結束語

圖7 三種算法吞吐率對比

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

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

[1] Finkenzeller K著, 陳大才譯.射頻識別(RFID)技術[M].北京: 電子工業(yè)出版社, 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聯(lián)合防碰撞算法[J].微計算機信息, 2010, 26(10): 145-146.

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