一種新型RFID動態(tài)多叉樹查詢防碰撞算法

陸冰清，牛國柱，趙英臣

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

0 引言

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

RFID系統(tǒng)在工作時，可能會有多個標簽同時處在閱讀器的作用范圍內(nèi)。這樣如果有兩個或兩個以上的應(yīng)答器同時發(fā)送數(shù)據(jù)，就會出現(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是一種把整個可供使用的通路容量按時間分配給多個用戶的技術(shù)。

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

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

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

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

1.1 算法設(shè)計思路

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

圖1 曼徹斯特編碼

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

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

2）碰撞時隙：多個標簽應(yīng)答導(dǎo)致碰撞；

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

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

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

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

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

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

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

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

1.2 算法原理及流程

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

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

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

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

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

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

1.3 算法分析

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

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

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

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

采用四叉樹的概率為：

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

2 算法仿真與分析

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

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

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

3 結(jié)束語

圖7 三種算法吞吐率對比

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

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

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

[2] 王雪, 錢志鴻, 胡正超等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報, 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關(guān)鍵技術(shù)研究與實現(xiàn)[D].合肥: 中國科學(xué)技術(shù)大學(xué), 2009.