文獻(xiàn)標(biāo)識碼: A
文章編號: 0258-7998(2013)02-0130-04
射頻識別技術(shù)(RFID" title="RFID" target="_blank">RFID)是一種非接觸,、低功耗、無線通信技術(shù),,可通過無線電信號識別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù),。典型的RFID系統(tǒng)由電子標(biāo)簽(Tags)和讀寫器(Reader)組成,電子標(biāo)簽與讀寫器之間是通過耦合(天線)實現(xiàn)射頻信號的空間(無接觸)耦合,。在耦合通道內(nèi),,根據(jù)時序關(guān)系,實現(xiàn)能量的傳遞,、數(shù)據(jù)的交換,。其工作原理如圖1所示。
隨著RFID技術(shù)的廣泛應(yīng)用,,存在的問題也越來越凸顯出來,。目前RFID技術(shù)存在的主要問題有:安全問題,、傳輸距離問題、碰撞問題等,其中碰撞問題嚴(yán)重制約著RFID的發(fā)展,。目前,雖然已經(jīng)有很多種防碰撞的算法,,但是在算法執(zhí)行效率和精確度方面各有缺陷。本文在研究大量防碰撞算法的基礎(chǔ)上,經(jīng)過比較分析提出了一種新的基于樹搜索的防碰撞算法,,該算法根據(jù)碰撞位的情況動態(tài)地選擇合適的搜索樹算法,大幅度提高了RFID的性能,。
1 防碰撞算法簡介
如果在RFID讀寫器可讀取范圍內(nèi)有多個標(biāo)簽,或是一個標(biāo)簽同時接收到幾個讀寫器發(fā)出的信號就會發(fā)生沖突,即所謂的碰撞,。一旦發(fā)生碰撞就會導(dǎo)致讀寫器不能讀取電子標(biāo)簽信息或是無法讀到正確的標(biāo)簽信息,,所以防碰撞算法就顯得尤為重要。根據(jù)碰撞的產(chǎn)生原理可以將RFID的碰撞分為[1]:標(biāo)簽碰撞,、頻率干擾,、標(biāo)簽干擾。其中頻率干擾和標(biāo)簽干擾統(tǒng)稱為讀寫器碰撞,。
由于讀寫器碰撞的發(fā)生概率較小且容易避免,,所以本文主要研究對象是標(biāo)簽碰撞。解決碰撞的算法就稱為防碰撞算法,。防碰撞算法最常使用的方法[2]有空分多址(SDMA),、頻分多址(FDMA)、碼分多址(CDMA)和時分多址(TDMA),。目前較為流行的RFID的兩種防碰撞算法,,基于ALOHA和基于樹的算法都是基于時分多址的。
2 基于多叉樹的RFID防碰撞算法
二進(jìn)制樹算法(BS)[3]的基本思想是將處于碰撞狀態(tài)的標(biāo)簽分為0和1兩個子集,先查詢子集0,若沒有沖突,,則正確識別,;若仍有沖突,則再分裂,把子集0分為00和01兩個子集,,依次類推,,直到子集0中的所有標(biāo)簽全部識別,再按照此步驟查詢子集1,。使用BS算法的標(biāo)簽要經(jīng)過多次比較,并通過循環(huán)操作以達(dá)到識別所有標(biāo)簽,搜索過程中會出現(xiàn)路徑的重復(fù),搜索效率比較低[4]。為滿足RFID系統(tǒng)能耗低,、速度快等要求,,其防碰撞算法有如下特點[5]:(1)識別過程中查詢時間要短,查詢次數(shù)也要盡量少,。(2)對于無源標(biāo)簽來說必須是低能耗,,要達(dá)到低能耗就要求算法中標(biāo)簽與讀寫器之間傳輸?shù)谋忍財?shù)要少。(3)標(biāo)簽?zāi)軌虮煌耆?、正確地識別,,要求讀寫器對其可讀取范圍內(nèi)的所有標(biāo)簽都要正確,、完整地識別,不能出現(xiàn)錯誤識別和遺漏識別,。本文提出的基于多叉樹搜索的防碰撞算法在滿足RFID防碰撞算法的基礎(chǔ)上,盡量解決上述防碰撞算法中的問題,。
2.1 算法的基本思想
讀寫器在發(fā)出Request命令后,讀寫器可讀取范圍內(nèi)的所有標(biāo)簽都要做出應(yīng)答,,如果讀寫器譯碼后得到n個位發(fā)生碰撞,,即只有標(biāo)簽這n個比特是讀寫器無法識別的。讀寫器根據(jù)這n個碰撞位所在的位置,分成三種情況進(jìn)行處理:(1)若碰撞位連續(xù)兩位,則采用動態(tài)四叉樹分裂查詢,; (2)若碰撞位非連續(xù),則采用動態(tài)二叉樹分裂查詢,;(3)若碰撞位只有一位,則采用二叉樹查詢。
在發(fā)送查詢指令時,,不需發(fā)送碰撞標(biāo)簽完整的ID號,,只要用二進(jìn)制代碼表示碰撞位即可,這樣可以在很大程度上減少發(fā)送的數(shù)據(jù)量,,繼而降低功耗,、提高識別效率。
2.2 算法的工作流程
算法的步驟如下:
(1) 算法先發(fā)送一個Request(11111111)命令,,所有電子標(biāo)簽對此做出應(yīng)答,,然后將自己的ID碼發(fā)送出去。
(2) 讀寫器檢測接收到的信號,,若未能檢測到信號,,則說明在讀寫器可讀取的范圍內(nèi)沒有電子標(biāo)簽,返回步驟(1),;若檢測到信號,,則轉(zhuǎn)到步驟(3)。
(3) 判斷是否有碰撞發(fā)生,,若無則對標(biāo)簽進(jìn)行讀寫操作,;若有,則轉(zhuǎn)到步驟(4)。
(4) 將查詢碼壓入堆棧,并發(fā)送棧頂?shù)牟樵兇a,滿足該查詢碼的標(biāo)簽應(yīng)答,。判斷碰撞情況:若沒有標(biāo)簽應(yīng)答,則讀寫器本次識別過程結(jié)束,,并檢堆棧是否為空;若只有一個標(biāo)簽應(yīng)答,,讀寫器發(fā)出RW-DATA指令,對該標(biāo)簽進(jìn)行讀寫操作之后,,讀寫器發(fā)出Sleep指令,標(biāo)簽進(jìn)入休眠狀態(tài),不參與后續(xù)的識別過程;若有多個標(biāo)簽做出應(yīng)答,,即發(fā)生碰撞,,則轉(zhuǎn)到步驟(5)。
(5) 根據(jù)碰撞位的不同情況,選擇不同的搜索方法,重復(fù)步驟(4),直到堆棧為空,。
(6) 堆棧為空說明所有標(biāo)簽都被成功識別,,整個標(biāo)簽識別過程結(jié)束。
2.3 算法舉例
假如電子標(biāo)簽的ID碼均是8位,在讀寫器可讀取范圍內(nèi)有4個處于準(zhǔn)備狀態(tài)的電子標(biāo)簽A,、B,、C、D,它們的ID號為:TagA:10000110,、TagB:11010010,、TagC:01000010、TagD:01001010,。本例的搜索過程中堆棧變化情況如圖2所示,,算法實現(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),該分支的識別過程結(jié)束,;發(fā)送指令Request(01,111),,有標(biāo)簽C、D響應(yīng),,即發(fā)生了碰撞,,將C、D重新譯碼后得到新的譯碼數(shù)據(jù)為0100X010,,此時讀寫器檢測到只有一個碰撞位,。參考文獻(xiàn)[6]中設(shè)定只有一個碰撞位時,讀寫器能直接識別出兩個標(biāo)簽,但是由于標(biāo)簽本身無法識別,,所以只有一個碰撞位時,,讀寫器也還是要經(jīng)過一次比較,才能識別出兩個標(biāo)簽最高碰撞位為第3位,將Request(0,11),、Request(1,11)壓入堆棧,。
(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ā)送,,堆棧為空,,說明待識別的標(biāo)簽全部識別完,標(biāo)簽識別過程結(jié)束,。
3 新算法的性能分析
3.1發(fā)送數(shù)據(jù)量分析
當(dāng)標(biāo)簽的ID較長時,讀寫器每次發(fā)送的查詢指令的位數(shù)就會很多,,這樣會嚴(yán)重影響傳輸速率和系統(tǒng)識別效率[6]。如果直接用二進(jìn)制表示碰撞位的信息,,則可以大大減少發(fā)送的數(shù)據(jù)量,。假設(shè)標(biāo)簽的ID號有N位,則只要n位序列就能表示出所有的碰撞位,,其中:
假設(shè)在整個識別過程中查詢M次只有1個碰撞位,,則整個識別過程中有M個葉子節(jié)點,那么動態(tài)二叉樹查詢次數(shù)為:
4 實驗仿真與分析
利用軟件Matlab對上述算法的傳輸數(shù)據(jù)量,、查詢次數(shù)和吞吐率進(jìn)行試驗仿真,,結(jié)果如圖3所示。
由圖3(a)可以看出,隨著標(biāo)簽ID的增長,,新算法的傳輸數(shù)據(jù)量增加很少,,與未經(jīng)過改進(jìn)的算法的指令長度相比,新算法能很大程度地減少傳輸指令長度,,從而能減少系統(tǒng)的能耗,,增加系統(tǒng)的識別效率。
由圖3(b)可以看出,,在同樣數(shù)目的待識別標(biāo)簽的情況下,,動態(tài)二叉樹和動態(tài)四叉樹所需的查詢總數(shù),與本文的算法所需查詢總數(shù)的比較中,,本文新算法所需的總查詢數(shù)較少,,即識別時間較短。
由圖3(c)可得新算法的吞吐率高于動態(tài)二叉樹和動態(tài)四叉樹搜索算法的吞吐率,,即新算法的識別率更高,。
本文在研究大量防碰撞算法的基礎(chǔ)上經(jīng)過比較分析,提出了一種新的基于樹搜索的防碰撞算法,該算法根據(jù)碰撞位的情況,,動態(tài)地選擇合適的搜索樹算法,,而且本文還引用了堆棧來存儲查詢命令,這樣可以避免重復(fù),、多余的搜索,,減少了搜索樹的分支數(shù)。由數(shù)學(xué)分析和算法的仿真結(jié)果可得,,該算法查詢時間短,、系統(tǒng)效率高、性能優(yōu)良,,特別是在待識別標(biāo)簽數(shù)量龐大時,,該算法表現(xiàn)出更加明顯的優(yōu)勢。
參考文獻(xiàn)
[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] 胡兆吉.基于嵌入式的射頻識別系統(tǒng)[D].西安:西安電子科技大學(xué),,2011.
[3] 丁治國.RFID關(guān)鍵技術(shù)研究與實現(xiàn)[D].合肥:中國科學(xué)技術(shù)大學(xué),2009.
[4] 李興鶴,,胡詠梅,王華蓮,,等.基于動態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu)RFID反碰撞算法[J].山東科學(xué),,2006,19(2):51-55.
[5] 江岸,伍繼雄,,黃生葉,,等.改進(jìn)的RFID二進(jìn)制搜索防碰撞算法[J].計算機(jī)工程與應(yīng)用,2009,45(5):229-235.
[6] 江城,,黃立波.基于二進(jìn)制搜索的RFID標(biāo)簽防碰撞算法研究[J].計算機(jī)與數(shù)字工程,,2011(4):29-33.
[7] 孫文勝,胡玲敏.基于后退式搜索的自適應(yīng)多叉樹防碰撞算法[J].計算機(jī)應(yīng)用, 2011,31(08):2052-2055.
[8] 丁俊.射頻識別RFID標(biāo)簽防碰撞算法[D].合肥:中國科技大學(xué)2010.