摘 要: 在分析了目前現(xiàn)有的時隙ALOHA算法和查詢樹QT算法后,結合這兩類算法的優(yōu)點,,提出了一種混合型算法GFA-QT來解決RFID中的碰撞問題,。理論與仿真表明,這種混合型的算法在系統(tǒng)效率上優(yōu)于現(xiàn)有的算法,。
關鍵詞: 射頻識別,;防碰撞;GFA-QT,;吞吐量
射頻識別系統(tǒng)(RFID)是一種利用無線傳輸實現(xiàn)物體的非接觸式識別的技術,。自20世紀90年代興起以來,該技術憑借數(shù)據(jù)存儲量大,、識別時間短、保密性好等優(yōu)點在貨物銷售,、物流倉儲,、安保及交通管理等眾多領域得到廣泛的應用[1]。RFID系統(tǒng)主要由閱讀器Reader和標簽Tag組成,,閱讀器通過發(fā)射天線發(fā)送一定頻率的射頻信號,,當標簽進入發(fā)射天線工作區(qū)域時將產(chǎn)生感應電流,獲得能量從而被激活,,并將自身的信息通過內(nèi)置的天線發(fā)送出去,,閱讀器接收到從標簽發(fā)來的載波信號后,對接收的信號進行解調和解碼,,并將標簽編碼等信息通過接口與上位控制計算機進行數(shù)據(jù)交換同時執(zhí)行應用軟件發(fā)來的命令,,實現(xiàn)不同的應用功能[2]。
作為一種無線通信技術,,RFID同樣不可避免地面臨著多址接入的問題,。在RFID系統(tǒng)中,閱讀器與其工作域內(nèi)的標簽之間通過共享的無線信道進行通信,,當多個標簽同時與閱讀器通信時,,信號就會在共享的信道中產(chǎn)生碰撞,進而導致閱讀器無法識別任何標簽信息,這就是標簽碰撞問題,。
目前解決RFID防碰撞問題的算法主要分為基于時隙ALOHA的隨機型防碰撞算法和基于二進制樹的確定型防碰撞算法,,本文在分析這兩種主流算法之后提出了一種混合型算法GFA-QT,該算法結合了時隙ALOHA和二進制樹算法的優(yōu)點,。
1 RFID標簽防碰撞技術
多標簽防碰撞問題的實質是多址接入問題,,其解決方案主要可分為四類:空分多址(SDMA)、頻分多址(FDMA),、時分多址(TDMA)和碼分多址(CDMA),。基于SDMA,、FDMA,、CDMA的標簽防碰撞算法理論上可以解決部分有源的標簽防碰撞問題,但是目前大多數(shù)使用的是無源標簽,,受其功率的限制,,采用上述方案會使得標簽和閱讀器的設計復雜、系統(tǒng)成本高,,所以RFID防碰撞算法中更多采用的是基于TDMA思想的防碰撞算法,。目前基于TDMA思想的防碰撞算法主要分為兩大類:基于時隙ALOHA的隨機接入型算法和基于二進制樹的確定性算法。
1.1 時隙ALOHA算法
時隙ALOHA算法中閱讀器將一幀劃分為多個時隙,,在所有標簽和閱讀器取得同步基礎上,,規(guī)定標簽僅能在每個時隙開始時才能發(fā)送數(shù)據(jù)。其算法的基本流程如下:(1)當閱讀器向標簽發(fā)送請求命令時會同步向所有標簽廣播時隙個數(shù)L(即幀長),。(2)標簽會在幀長范圍內(nèi)隨機地選擇一個時隙響應閱讀器的命令并發(fā)送自身的信息,,若一個時隙中只有一個標簽返回信息則稱為成功時隙,沒有標簽返回信息稱為空時隙,,有2個或者更多的標簽返回信息稱為碰撞時隙,,記一幀中空時隙數(shù)為C0,成功時隙數(shù)為C1,,碰撞時隙數(shù)為Ck,。發(fā)生碰撞的相關標簽會在下一幀繼續(xù)向閱讀器發(fā)送數(shù)據(jù)。(3)算法根據(jù)前一幀的反饋值C0,、C1,、Ck采用標簽估算方法來估算閱讀器范圍內(nèi)未讀標簽數(shù)量,并根據(jù)此調整下一幀時隙數(shù),,得到一個使系統(tǒng)識別效率最高的時隙數(shù)L′,。(4)讀寫器向標簽廣播新的時隙數(shù),直至所有標簽被識別完,。
通過仿真得到第4種標簽估算模型準確度最高,,系統(tǒng)的識別效率達到最大,。
1.2 二進制樹算法
基于樹結構的確定性算法是實現(xiàn)標簽防碰撞算法的另一種解決思路,它是將閱讀器工作區(qū)域內(nèi)的標簽不斷地劃分為p個子集(p>1),再對某個子集進行同樣的劃分,,這樣所劃分子集內(nèi)的標簽數(shù)量越來越少,,直至某子集內(nèi)的標簽數(shù)目為1,實現(xiàn)閱讀器成功識別標簽,。當某個子集內(nèi)的標簽讀取完畢,,閱讀器采用回溯的方式處理其他等待讀取的標簽。這樣就可以將標簽的分組過程看做是全部標簽根據(jù)分組方案從根節(jié)點向葉節(jié)點逐層分流的過程,,只有葉節(jié)點的標簽能被成功讀取,。
查詢樹QT[7](Query Tree)是一種典型的樹結構算法,其算法原理:讀寫器發(fā)送長度為k的prefix,;標簽ID中前k bit與prefix匹配的tag反饋第(k+1)bit至最后1 bit,。如果閱讀器收到的標簽ID碰撞,再分別將prefix加“1”和“0”,,作為新的prefix發(fā)送出去,。如果沒有碰撞,就表明一個標簽被識別了,。
圖1給出了QT算法的實例,,設標簽的三個ID分別為“010”“011”“100”,閱讀器的查詢序列首先置為“0”,、“1”,,閱讀器先發(fā)送序列“0”進行查詢,發(fā)生碰撞,,此時將序列置為“00”,、“01”,再次分別發(fā)送,,序列“00”沒有響應,序列“01”發(fā)生碰撞,,將序列置為“010”,、“011”,成功識別,?;厮莸叫蛄?ldquo;1”,只有標簽“100”響應,,成功識別,。
2 GFA-QT算法
在上節(jié)介紹的時隙ALOHA算法中,系統(tǒng)實現(xiàn)起來較為容易,,但是由于是隨機接入的,,所以在一定時間范圍內(nèi)可能會發(fā)生某個標簽沒有被讀取(即標簽“餓死”)的情形,。而二進制樹算法中每個標簽會被成功識別,但是識別時延較長,。本節(jié)將介紹一種混合的防碰撞算法GFA-QT,,它將ALOHA算法和QT算法的優(yōu)點結合起來,首先利用時隙ALOHA算法對標簽數(shù)量進行估計,,然后對標簽進行分組,,最后利用QT算法分別讀取每一組標簽。這種解決標簽防碰撞算法稱為GFA-QT(Grouping Framed Aloha with Query Tree)基于分組時隙ALOHA的查詢樹算法,。
2.1 分組的概念
在時隙ALOHA算法中,,每個標簽隨機選擇一個時隙向閱讀器發(fā)送自身信息,當標簽數(shù)量等于時隙數(shù)時,,系統(tǒng)效率達到最高36.8%,。但是事實上時隙數(shù)有限,而標簽數(shù)可能遠大于時隙數(shù),,所以對標簽如何分組就顯得尤為重要,。由于閱讀器在識別過程開始之前并不知曉其閱讀范圍內(nèi)的剩余標簽數(shù)量,在1.1節(jié)中對幾種標簽估算方法進行了比較,,得到第4種數(shù)學模型計算的剩余標簽數(shù)量最為準確,。
在QT算法中,當樹的深度為2時該算法的性能最佳,,因為閱讀器發(fā)出查詢序列“0”,、“1”時恰好分別有一個標簽響應。設標簽數(shù)量為N,,時隙數(shù)為L,,則最佳時隙數(shù)滿足N=2×L,即每個時隙內(nèi)僅有兩個標簽,。但是這樣時隙數(shù)會過大,,系統(tǒng)無法實現(xiàn)。通過仿真得到當時隙數(shù)為4,,且每個時隙內(nèi)標簽數(shù)量也為4時,,系統(tǒng)效率達到最大。
2.2 算法描述
GFA-QT算法過程包括兩個階段:標簽分組階段和標簽識別[8-9]階段,。算法的步驟如下:
(1)預處理:首先將所有待識別的標簽視為一組,,閱讀器設置時隙數(shù)為L=4,標簽成功分組所需循環(huán)次數(shù)為I(I初始值為1),,標簽分裂系數(shù)M=4,,標簽分裂門限值pth=8,標簽分組數(shù)為S,;
(2)閱讀器向所有標簽發(fā)送包含幀長的Probe命令,,將時隙數(shù)L告知標簽,;
(3)標簽從1~L中隨機選擇一個時隙對閱讀器做出反應,閱讀器檢測出一幀中沒有標簽響應的時隙數(shù)C0,,只有一個標簽響應的時隙數(shù)C1和有兩個或者兩個以上標簽響應的時隙數(shù)Ck,;
(4)根據(jù)剩余標簽估算模型4計算得出所有等待識別的標簽數(shù)量Nleft,將Nleft與標簽分裂門限值pth比較,。若Nleft<pth,,則分組結束;若Nleft>pth,,則I=I+1,,S=MI-1,利用分組函數(shù)將所有標簽分為S組,;
(5)由于標簽分組的隨機性,,在S組標簽中任選一組標簽重復步驟(2)~(4),直至該組標簽數(shù)滿足Nleft<pth,。最終得到標簽數(shù)組數(shù)S=MI-1,,標簽組數(shù)為[group1,…,,groups],;
(6)利用QT算法分別讀取[group1,…,,groups],,返回所有成功識別的標簽。
3 計算機仿真及結果分析
系統(tǒng)效率是衡量RFID防碰撞算法性能的重要指標,,本文使用MATLAB對提出的GFA-QT防碰撞算法進行仿真,,仿真了在不同的標簽數(shù)量、不同的時隙數(shù)下GFA-QT的系統(tǒng)效率,,并與時隙ALOHA算法中的DFSA(Dynamic Framed Slotted ALOHA)算法和二進制查詢樹QT算法的系統(tǒng)效率進行了比較,。
3.1 仿真條件
電子標簽的ID碼為64 bit,隨機生成,。在仿真時不考慮標簽的運動,、傳輸誤碼等因素。所有算法的指令頭,、尾以及鏈路時序符合ISO/IEC 18000-6C協(xié)議規(guī)范,。在GFA-QT算法中,,設置初始時隙數(shù)為4,,分組數(shù)為1。
3.2 仿真結果
本節(jié)首先研究了在不同的標簽數(shù)量下,,GFA-QT,、DFSA,、QT算法系統(tǒng)效率之間的差異。設標簽數(shù)量從100逐步增加到2 000,。仿真結果如圖2所示,。
在該仿真中看出當標簽數(shù)量較小時,GFA-QT算法的系統(tǒng)效率低于DFSA,、QT算法的系統(tǒng)效率,,這是因為標簽數(shù)量小,分組優(yōu)勢不明顯,。當標簽數(shù)增加時,,GFA-QT算法的系統(tǒng)效率優(yōu)于其他兩種算法并且趨于穩(wěn)定,說明該算法受標簽數(shù)量影響不大,。
在圖3中,,探討了不同時隙數(shù)對GFA-QT算法系統(tǒng)效率的影響,從仿真結果來看,,當時隙數(shù)為4時算法的系統(tǒng)效率高于時隙數(shù)分別為2,、8、16時的系統(tǒng)效率,。這主要是因為當時隙數(shù)為8或者16時,,造成時隙數(shù)過大,識別時延增加,,當時隙數(shù)為2時,,容易造成標簽分布于各個時隙不均勻,使得閱讀器無法達到最大識別效率,。
本文提出了一種基于時隙ALOHA算法和二進制查詢樹QT算法的混合型算法GFA-QT,,用于RFID系統(tǒng)的防碰撞功能的實現(xiàn),該算法的系統(tǒng)效率高于現(xiàn)有的算法,。仿真結果表明,,新的混合型算法將RFID系統(tǒng)識別效率提高至37.2%左右,高于DFSA算法和QT算法,。
參考文獻
[1] RAZA N, BRADSHAW V, HAGUE M.Applications of RFID technology[C]. IEEE Colloquium on RFID Technology, London, England, 1999,,10: 1/1-1/5.
[2] FLOR T, NIESS W, VOGLER G.RFID: the integration of contactless identification technology and mobile computing[J]. Proc. of the 7th Int’l Conf. on Telecomm, Zagerb, Croatia, 2003,2(26): 619-623.
[3] CHA J R, KIM J H. Novel anti-collision algorithm for fast objection identification in RFID systems[EB/OL]. http://ieeexplore.ieee.org/ie15/10248/32568/01524254.pdf, 2005.
[4] VOGT H.Efficient object identification with passive RFID tags[C].in IEEE PerCom, (TX,USA), 2002.
[5] CHA J R,KIM J H.Novel anti-collision algorithms for fast object identification in RFID system[C].The 11thIntl. Conference on Parallel and Distributed Systems,,Korea, 2005:63-75.
[6] ZHEN B, KOBAYASHI M,SHIMIZU M.Framed aloha for multiple RFID objects identification[C].IEICE Transactions on Communications, 2005,,E88-B:991-999.
[7] LAW C, LEE K,SIU K.Efficient memorials protocol for tag identification[C].4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000,ACM:75-84.
[8] SHIN J D, YEO S S, KIM T H,et al.Hybrid tag anticollision algorithms in RFID systems[C]. UK: Springer Berlin /Heidelberg,2007.
[9] CHOI S Y, LEE J, KIM S H,et al.Hybrid anti-collision method based on maximum throughput for RFID system[J]. Electronics Letters,2010,,46(19).