陸冰清，牛國(guó)柱，趙英臣

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

0 引言

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

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

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

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

1 改進(jìn)的動(dòng)態(tài)多叉樹查詢算法

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

1.1 算法設(shè)計(jì)思路

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

圖1 曼徹斯特編碼

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

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

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

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

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

由圖2可以看出，完成整個(gè)標(biāo)簽的搜索共需14個(gè)時(shí)隙，其中6個(gè)是碰撞時(shí)隙，搜索深度有3層。

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

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

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

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

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

1.2 算法原理及流程

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

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

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

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

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

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

1.3 算法分析

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

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

則當(dāng)前分支采用二叉樹的概率為：

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

采用四叉樹的概率為：

由式（1）、式（2）可以看出分支內(nèi)標(biāo)簽個(gè)數(shù)越少，采用二叉樹的概率較大，即碰撞的位數(shù)越少，相鄰位碰撞的概率也越?。环粗捎盟牟鏄涞母怕瘦^大。

2 算法仿真與分析

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

圖6 三種算法碰撞時(shí)隙和空閑時(shí)隙對(duì)比

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

3 結(jié)束語

圖7 三種算法吞吐率對(duì)比

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

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

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

[2] 王雪, 錢志鴻, 胡正超等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報(bào), 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].微計(jì)算機(jī)信息, 2010, 26(10): 145-146.

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