基于多叉樹搜索算法改進(jìn)的RFID防碰撞算法*

林 偉，李景霞，葉林鋒

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006）

射頻識(shí)別技術(shù)（RFID）是一種非接觸、低功耗、無線通信技術(shù)，可通過無線電信號(hào)識(shí)別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù)。典型的RFID系統(tǒng)由電子標(biāo)簽 (Tags)和讀寫器(Reader)組成，電子標(biāo)簽與讀寫器之間是通過耦合(天線)實(shí)現(xiàn)射頻信號(hào)的空間(無接觸）耦合。在耦合通道內(nèi)，根據(jù)時(shí)序關(guān)系，實(shí)現(xiàn)能量的傳遞、數(shù)據(jù)的交換。其工作原理如圖1所示。

圖1 RFID工作原理

隨著RFID技術(shù)的廣泛應(yīng)用，存在的問題也越來越凸顯出來。目前RFID技術(shù)存在的主要問題有：安全問題、傳輸距離問題、碰撞問題等,其中碰撞問題嚴(yán)重制約著RFID的發(fā)展。目前,雖然已經(jīng)有很多種防碰撞的算法，但是在算法執(zhí)行效率和精確度方面各有缺陷。本文在研究大量防碰撞算法的基礎(chǔ)上,經(jīng)過比較分析提出了一種新的基于樹搜索的防碰撞算法，該算法根據(jù)碰撞位的情況動(dòng)態(tài)地選擇合適的搜索樹算法,大幅度提高了RFID的性能。

1 防碰撞算法簡(jiǎn)介

如果在RFID讀寫器可讀取范圍內(nèi)有多個(gè)標(biāo)簽,或是一個(gè)標(biāo)簽同時(shí)接收到幾個(gè)讀寫器發(fā)出的信號(hào)就會(huì)發(fā)生沖突，即所謂的碰撞。一旦發(fā)生碰撞就會(huì)導(dǎo)致讀寫器不能讀取電子標(biāo)簽信息或是無法讀到正確的標(biāo)簽信息，所以防碰撞算法就顯得尤為重要。根據(jù)碰撞的產(chǎn)生原理可以將RFID的碰撞分為[1]：標(biāo)簽碰撞、頻率干擾、標(biāo)簽干擾。其中頻率干擾和標(biāo)簽干擾統(tǒng)稱為讀寫器碰撞。

由于讀寫器碰撞的發(fā)生概率較小且容易避免，所以本文主要研究對(duì)象是標(biāo)簽碰撞。解決碰撞的算法就稱為防碰撞算法。防碰撞算法最常使用的方法[2]有空分多址(SDMA)、頻分多址(FDMA)、碼分多址(CDMA)和時(shí)分多址(TDMA)。目前較為流行的RFID的兩種防碰撞算法，基于ALOHA和基于樹的算法都是基于時(shí)分多址的。

2 基于多叉樹的RFID防碰撞算法

二進(jìn)制樹算法(BS)[3]的基本思想是將處于碰撞狀態(tài)的標(biāo)簽分為0和1兩個(gè)子集,先查詢子集0,若沒有沖突，則正確識(shí)別；若仍有沖突,則再分裂，把子集 0分為00和01兩個(gè)子集，依次類推，直到子集0中的所有標(biāo)簽全部識(shí)別，再按照此步驟查詢子集1。使用BS算法的標(biāo)簽要經(jīng)過多次比較,并通過循環(huán)操作以達(dá)到識(shí)別所有標(biāo)簽,搜索過程中會(huì)出現(xiàn)路徑的重復(fù),搜索效率比較低[4]。為滿足RFID系統(tǒng)能耗低、速度快等要求，其防碰撞算法有如下特點(diǎn)[5]：(1)識(shí)別過程中查詢時(shí)間要短，查詢次數(shù)也要盡量少。(2)對(duì)于無源標(biāo)簽來說必須是低能耗，要達(dá)到低能耗就要求算法中標(biāo)簽與讀寫器之間傳輸?shù)谋忍財(cái)?shù)要少。(3)標(biāo)簽?zāi)軌虮煌耆⒄_地識(shí)別，要求讀寫器對(duì)其可讀取范圍內(nèi)的所有標(biāo)簽都要正確、完整地識(shí)別，不能出現(xiàn)錯(cuò)誤識(shí)別和遺漏識(shí)別。本文提出的基于多叉樹搜索的防碰撞算法在滿足RFID防碰撞算法的基礎(chǔ)上,盡量解決上述防碰撞算法中的問題。

2.1 算法的基本思想

讀寫器在發(fā)出Request命令后，讀寫器可讀取范圍內(nèi)的所有標(biāo)簽都要做出應(yīng)答，如果讀寫器譯碼后得到n個(gè)位發(fā)生碰撞，即只有標(biāo)簽這n個(gè)比特是讀寫器無法識(shí)別的。讀寫器根據(jù)這n個(gè)碰撞位所在的位置,分成三種情況進(jìn)行處理：(1)若碰撞位連續(xù)兩位,則采用動(dòng)態(tài)四叉樹分裂查詢；(2)若碰撞位非連續(xù),則采用動(dòng)態(tài)二叉樹分裂查詢；(3)若碰撞位只有一位,則采用二叉樹查詢。

在發(fā)送查詢指令時(shí)，不需發(fā)送碰撞標(biāo)簽完整的ID號(hào)，只要用二進(jìn)制代碼表示碰撞位即可，這樣可以在很大程度上減少發(fā)送的數(shù)據(jù)量，繼而降低功耗、提高識(shí)別效率。

2.2 算法的工作流程

算法的步驟如下：

(1)算法先發(fā)送一個(gè)Request(11111111)命令，所有電子標(biāo)簽對(duì)此做出應(yīng)答，然后將自己的ID碼發(fā)送出去。

(2)讀寫器檢測(cè)接收到的信號(hào)，若未能檢測(cè)到信號(hào)，則說明在讀寫器可讀取的范圍內(nèi)沒有電子標(biāo)簽，返回步驟(1)；若檢測(cè)到信號(hào)，則轉(zhuǎn)到步驟(3)。

(3)判斷是否有碰撞發(fā)生，若無則對(duì)標(biāo)簽進(jìn)行讀寫操作；若有,則轉(zhuǎn)到步驟(4)。

(4)將查詢碼壓入堆棧,并發(fā)送棧頂?shù)牟樵兇a,滿足該查詢碼的標(biāo)簽應(yīng)答。判斷碰撞情況：若沒有標(biāo)簽應(yīng)答,則讀寫器本次識(shí)別過程結(jié)束，并檢堆棧是否為空；若只有一個(gè)標(biāo)簽應(yīng)答，讀寫器發(fā)出RW-DATA指令,對(duì)該標(biāo)簽進(jìn)行讀寫操作之后，讀寫器發(fā)出Sleep指令,標(biāo)簽進(jìn)入休眠狀態(tài)，不參與后續(xù)的識(shí)別過程;若有多個(gè)標(biāo)簽做出應(yīng)答，即發(fā)生碰撞，則轉(zhuǎn)到步驟(5)。

(5)根據(jù)碰撞位的不同情況,選擇不同的搜索方法，重復(fù)步驟(4),直到堆棧為空。

(6)堆棧為空說明所有標(biāo)簽都被成功識(shí)別，整個(gè)標(biāo)簽識(shí)別過程結(jié)束。

2.3 算法舉例

假如電子標(biāo)簽的ID碼均是8位,在讀寫器可讀取范圍內(nèi)有4個(gè)處于準(zhǔn)備狀態(tài)的電子標(biāo)簽 A、B、C、D,它們的ID 號(hào)為：TagA：10000110、TagB：11010010、TagC:01000010、TagD:01001010。本例的搜索過程中堆棧變化情況如圖2所示，算法實(shí)現(xiàn)步驟如下：

(1)當(dāng)讀寫器發(fā)出Request(11111111)指令后，得到譯碼后的碰撞位為：XX0XXX10。

(2)讀寫器將連續(xù)碰撞位XX用四叉樹進(jìn)行查詢,發(fā)生碰撞的最高位為第7位，用二進(jìn)制表示為111。將Request(00,111)、Request(01,111)、 Request(10,111)、Request(11,111)依次入棧，然后發(fā)送棧頂指令Request(00，111)，沒有符合查詢碼的標(biāo)簽響應(yīng),該分支的識(shí)別過程結(jié)束；發(fā)送指令 Request(01,111)，有標(biāo)簽 C、D響應(yīng)，即發(fā)生了碰撞，將C、D重新譯碼后得到新的譯碼數(shù)據(jù)為0100X010，此時(shí)讀寫器檢測(cè)到只有一個(gè)碰撞位。參考文獻(xiàn)[6]中設(shè)定只有一個(gè)碰撞位時(shí),讀寫器能直接識(shí)別出兩個(gè)標(biāo)簽，但是由于標(biāo)簽本身無法識(shí)別，所以只有一個(gè)碰撞位時(shí)，讀寫器也還是要經(jīng)過一次比較，才能識(shí)別出兩個(gè)標(biāo)簽最高碰撞位為第 3位,將 Request(0,11)、Request(1,11)壓入堆棧。

圖2 搜索過程中堆棧變化情況

(3)讀寫器發(fā)送 Request(0，11)命令，只有標(biāo)簽 D應(yīng)答，經(jīng)讀寫器讀寫操作后進(jìn)入休眠態(tài)。

(4)讀寫器發(fā)送 Request(1,11)命令，只有標(biāo)簽 C應(yīng)答，執(zhí)行讀寫操作后轉(zhuǎn)入休眠態(tài)。

(5)讀寫器發(fā)送 Request(10,111)命令，只有標(biāo)簽 A應(yīng)答，執(zhí)行讀寫操作后轉(zhuǎn)入休眠態(tài)。

(6)讀寫器發(fā)送 Request(11,111)命令，只有標(biāo)簽 B應(yīng)答，執(zhí)行讀寫操作后轉(zhuǎn)入休眠態(tài)。

(7)堆棧內(nèi)的命令全部讀取并發(fā)送，堆棧為空，說明待識(shí)別的標(biāo)簽全部識(shí)別完，標(biāo)簽識(shí)別過程結(jié)束。

3 新算法的性能分析

3.1 發(fā)送數(shù)據(jù)量分析

當(dāng)標(biāo)簽的ID較長(zhǎng)時(shí),讀寫器每次發(fā)送的查詢指令的位數(shù)就會(huì)很多，這樣會(huì)嚴(yán)重影響傳輸速率和系統(tǒng)識(shí)別效率[6]。如果直接用二進(jìn)制表示碰撞位的信息，則可以大大減少發(fā)送的數(shù)據(jù)量。假設(shè)標(biāo)簽的ID號(hào)有N位，則只要n位序列就能表示出所有的碰撞位，其中：

用q表示采用新算法前后發(fā)送數(shù)據(jù)量的比值，表示形式為：

由式(2)可知，隨著N的增大，q值在減小，這表明在ID長(zhǎng)度較大時(shí)，采用新算法在發(fā)送數(shù)據(jù)量上有更加明顯的優(yōu)勢(shì)。

3.2 系統(tǒng)效率分析

系統(tǒng)效率是衡量一個(gè)算法優(yōu)劣的很重要的標(biāo)準(zhǔn)。假設(shè)所研究的RFID系統(tǒng)內(nèi)有N個(gè)待識(shí)別的標(biāo)簽，全部識(shí)別所需總的查詢次數(shù)為T，則系統(tǒng)效率e通常定義為如下形式[7]：

本文根據(jù)碰撞位的情況選擇動(dòng)態(tài)二叉樹或是用動(dòng)態(tài)四叉樹進(jìn)行分裂搜索，所以本文算法總的查詢次數(shù)是動(dòng)態(tài)二叉樹查詢數(shù)和動(dòng)態(tài)四叉樹查詢數(shù)之和：

假設(shè)在整個(gè)識(shí)別過程中查詢M次只有1個(gè)碰撞位，則整個(gè)識(shí)別過程中有M個(gè)葉子節(jié)點(diǎn)，那么動(dòng)態(tài)二叉樹查詢次數(shù)為：

所以本文中提出的二叉樹查詢次數(shù)為：

其中

由算法的特性可得，一定存在一個(gè)搜索深度l，使得搜索深度大于或等于l時(shí)，采用動(dòng)態(tài)二叉樹搜索；當(dāng)深度小于l時(shí)，采用動(dòng)態(tài)四叉樹搜索，即l=log4，其中」為向下取整。

由式(2)、式(4)、式(5)得到新算法所需查詢總次數(shù)為：

根據(jù)式(1)、式(6)，得到系統(tǒng)的效率，即吞吐率為：

4 實(shí)驗(yàn)仿真與分析

利用軟件Matlab對(duì)上述算法的傳輸數(shù)據(jù)量、查詢次數(shù)和吞吐率進(jìn)行試驗(yàn)仿真，結(jié)果如圖3所示。

圖3 性能分析比較

由圖3(a)可以看出,隨著標(biāo)簽ID的增長(zhǎng)，新算法的傳輸數(shù)據(jù)量增加很少，與未經(jīng)過改進(jìn)的算法的指令長(zhǎng)度相比，新算法能很大程度地減少傳輸指令長(zhǎng)度，從而能減少系統(tǒng)的能耗，增加系統(tǒng)的識(shí)別效率。

由圖3(b)可以看出，在同樣數(shù)目的待識(shí)別標(biāo)簽的情況下，動(dòng)態(tài)二叉樹和動(dòng)態(tài)四叉樹所需的查詢總數(shù)，與本文的算法所需查詢總數(shù)的比較中，本文新算法所需的總查詢數(shù)較少，即識(shí)別時(shí)間較短。

由圖3(c)可得新算法的吞吐率高于動(dòng)態(tài)二叉樹和動(dòng)態(tài)四叉樹搜索算法的吞吐率，即新算法的識(shí)別率更高。

本文在研究大量防碰撞算法的基礎(chǔ)上經(jīng)過比較分析，提出了一種新的基于樹搜索的防碰撞算法，該算法根據(jù)碰撞位的情況，動(dòng)態(tài)地選擇合適的搜索樹算法，而且本文還引用了堆棧來存儲(chǔ)查詢命令，這樣可以避免重復(fù)、多余的搜索，減少了搜索樹的分支數(shù)。由數(shù)學(xué)分析和算法的仿真結(jié)果可得，該算法查詢時(shí)間短、系統(tǒng)效率高、性能優(yōu)良，特別是在待識(shí)別標(biāo)簽數(shù)量龐大時(shí)，該算法表現(xiàn)出更加明顯的優(yōu)勢(shì)。

[1]Jia Xiaolin,Feng Quanyuan,Fan Taihua,et al.Analysis of anti-collision protocols for RFID tag identification[C].IEEE 2012 2nd International Conference on Digital Object Identifier,2012.

[2]胡兆吉.基于嵌入式的射頻識(shí)別系統(tǒng)[D].西安：西安電子科技大學(xué)，2011.

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

[4]李興鶴，胡詠梅，王華蓮，等.基于動(dòng)態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu) RFID反碰撞算法[J].山東科學(xué)，2006,19(2)：51-55.

[5]江岸，伍繼雄，黃生葉，等.改進(jìn)的 RFID二進(jìn)制搜索防碰撞算法[J].計(jì)算機(jī)工程與應(yīng)用，2009,45(5)：229-235.

[6]江城，黃立波.基于二進(jìn)制搜索的RFID標(biāo)簽防碰撞算法研究[J].計(jì)算機(jī)與數(shù)字工程，2011(4):29-33.

[7]孫文勝，胡玲敏.基于后退式搜索的自適應(yīng)多叉樹防碰撞算法[J].計(jì)算機(jī)應(yīng)用,2011,31(08)：2052-2055.

[8]丁俊.射頻識(shí)別 RFID標(biāo)簽防碰撞算法[D].合肥：中國(guó)科技大學(xué) 2010.