摘  要： 在分析了目前現(xiàn)有的時(shí)隙ALOHA算法和查詢樹(shù)QT算法后,，結(jié)合這兩類算法的優(yōu)點(diǎn)，提出了一種混合型算法GFA-QT來(lái)解決RFID中的碰撞問(wèn)題,。理論與仿真表明,，這種混合型的算法在系統(tǒng)效率上優(yōu)于現(xiàn)有的算法。
關(guān)鍵詞： 射頻識(shí)別,；防碰撞,；GFA-QT；吞吐量

    射頻識(shí)別系統(tǒng)（RFID）是一種利用無(wú)線傳輸實(shí)現(xiàn)物體的非接觸式識(shí)別的技術(shù),。自20世紀(jì)90年代興起以來(lái),，該技術(shù)憑借數(shù)據(jù)存儲(chǔ)量大、識(shí)別時(shí)間短,、保密性好等優(yōu)點(diǎn)在貨物銷售,、物流倉(cāng)儲(chǔ)、安保及交通管理等眾多領(lǐng)域得到廣泛的應(yīng)用[1],。RFID系統(tǒng)主要由閱讀器Reader和標(biāo)簽Tag組成,，閱讀器通過(guò)發(fā)射天線發(fā)送一定頻率的射頻信號(hào)，當(dāng)標(biāo)簽進(jìn)入發(fā)射天線工作區(qū)域時(shí)將產(chǎn)生感應(yīng)電流,，獲得能量從而被激活,，并將自身的信息通過(guò)內(nèi)置的天線發(fā)送出去，閱讀器接收到從標(biāo)簽發(fā)來(lái)的載波信號(hào)后,，對(duì)接收的信號(hào)進(jìn)行解調(diào)和解碼，并將標(biāo)簽編碼等信息通過(guò)接口與上位控制計(jì)算機(jī)進(jìn)行數(shù)據(jù)交換同時(shí)執(zhí)行應(yīng)用軟件發(fā)來(lái)的命令,，實(shí)現(xiàn)不同的應(yīng)用功能[2],。
    作為一種無(wú)線通信技術(shù)，RFID同樣不可避免地面臨著多址接入的問(wèn)題,。在RFID系統(tǒng)中,，閱讀器與其工作域內(nèi)的標(biāo)簽之間通過(guò)共享的無(wú)線信道進(jìn)行通信，當(dāng)多個(gè)標(biāo)簽同時(shí)與閱讀器通信時(shí),，信號(hào)就會(huì)在共享的信道中產(chǎn)生碰撞,，進(jìn)而導(dǎo)致閱讀器無(wú)法識(shí)別任何標(biāo)簽信息，這就是標(biāo)簽碰撞問(wèn)題,。
    目前解決RFID防碰撞問(wèn)題的算法主要分為基于時(shí)隙ALOHA的隨機(jī)型防碰撞算法和基于二進(jìn)制樹(shù)的確定型防碰撞算法,，本文在分析這兩種主流算法之后提出了一種混合型算法GFA-QT，該算法結(jié)合了時(shí)隙ALOHA和二進(jìn)制樹(shù)算法的優(yōu)點(diǎn),。
1 RFID標(biāo)簽防碰撞技術(shù)
    多標(biāo)簽防碰撞問(wèn)題的實(shí)質(zhì)是多址接入問(wèn)題,，其解決方案主要可分為四類：空分多址(SDMA)、頻分多址（FDMA）,、時(shí)分多址（TDMA）和碼分多址（CDMA）,?；赟DMA、FDMA,、CDMA的標(biāo)簽防碰撞算法理論上可以解決部分有源的標(biāo)簽防碰撞問(wèn)題,，但是目前大多數(shù)使用的是無(wú)源標(biāo)簽，受其功率的限制,，采用上述方案會(huì)使得標(biāo)簽和閱讀器的設(shè)計(jì)復(fù)雜,、系統(tǒng)成本高，所以RFID防碰撞算法中更多采用的是基于TDMA思想的防碰撞算法,。目前基于TDMA思想的防碰撞算法主要分為兩大類：基于時(shí)隙ALOHA的隨機(jī)接入型算法和基于二進(jìn)制樹(shù)的確定性算法,。
1.1 時(shí)隙ALOHA算法
    時(shí)隙ALOHA算法中閱讀器將一幀劃分為多個(gè)時(shí)隙，在所有標(biāo)簽和閱讀器取得同步基礎(chǔ)上,，規(guī)定標(biāo)簽僅能在每個(gè)時(shí)隙開(kāi)始時(shí)才能發(fā)送數(shù)據(jù),。其算法的基本流程如下：（1）當(dāng)閱讀器向標(biāo)簽發(fā)送請(qǐng)求命令時(shí)會(huì)同步向所有標(biāo)簽廣播時(shí)隙個(gè)數(shù)L（即幀長(zhǎng)）。（2）標(biāo)簽會(huì)在幀長(zhǎng)范圍內(nèi)隨機(jī)地選擇一個(gè)時(shí)隙響應(yīng)閱讀器的命令并發(fā)送自身的信息,，若一個(gè)時(shí)隙中只有一個(gè)標(biāo)簽返回信息則稱為成功時(shí)隙,，沒(méi)有標(biāo)簽返回信息稱為空時(shí)隙，有2個(gè)或者更多的標(biāo)簽返回信息稱為碰撞時(shí)隙,，記一幀中空時(shí)隙數(shù)為C0,，成功時(shí)隙數(shù)為C1，碰撞時(shí)隙數(shù)為Ck,。發(fā)生碰撞的相關(guān)標(biāo)簽會(huì)在下一幀繼續(xù)向閱讀器發(fā)送數(shù)據(jù),。（3）算法根據(jù)前一幀的反饋值C0、C1,、Ck采用標(biāo)簽估算方法來(lái)估算閱讀器范圍內(nèi)未讀標(biāo)簽數(shù)量,，并根據(jù)此調(diào)整下一幀時(shí)隙數(shù)，得到一個(gè)使系統(tǒng)識(shí)別效率最高的時(shí)隙數(shù)L′,。（4）讀寫(xiě)器向標(biāo)簽廣播新的時(shí)隙數(shù),，直至所有標(biāo)簽被識(shí)別完。

    通過(guò)仿真得到第4種標(biāo)簽估算模型準(zhǔn)確度最高,，系統(tǒng)的識(shí)別效率達(dá)到最大,。
1.2 二進(jìn)制樹(shù)算法
    基于樹(shù)結(jié)構(gòu)的確定性算法是實(shí)現(xiàn)標(biāo)簽防碰撞算法的另一種解決思路，它是將閱讀器工作區(qū)域內(nèi)的標(biāo)簽不斷地劃分為p個(gè)子集（p>1）,再對(duì)某個(gè)子集進(jìn)行同樣的劃分,，這樣所劃分子集內(nèi)的標(biāo)簽數(shù)量越來(lái)越少,，直至某子集內(nèi)的標(biāo)簽數(shù)目為1，實(shí)現(xiàn)閱讀器成功識(shí)別標(biāo)簽,。當(dāng)某個(gè)子集內(nèi)的標(biāo)簽讀取完畢,，閱讀器采用回溯的方式處理其他等待讀取的標(biāo)簽。這樣就可以將標(biāo)簽的分組過(guò)程看做是全部標(biāo)簽根據(jù)分組方案從根節(jié)點(diǎn)向葉節(jié)點(diǎn)逐層分流的過(guò)程，只有葉節(jié)點(diǎn)的標(biāo)簽?zāi)鼙怀晒ψx取,。
    查詢樹(shù)QT[7](Query Tree)是一種典型的樹(shù)結(jié)構(gòu)算法,，其算法原理：讀寫(xiě)器發(fā)送長(zhǎng)度為k的prefix；標(biāo)簽ID中前k bit與prefix匹配的tag反饋第(k+1)bit至最后1 bit,。如果閱讀器收到的標(biāo)簽ID碰撞,，再分別將prefix加“1”和“0”，作為新的prefix發(fā)送出去,。如果沒(méi)有碰撞,，就表明一個(gè)標(biāo)簽被識(shí)別了。
    圖1給出了QT算法的實(shí)例,，設(shè)標(biāo)簽的三個(gè)ID分別為“010”“011”“100”,，閱讀器的查詢序列首先置為“0”、“1”,，閱讀器先發(fā)送序列“0”進(jìn)行查詢,，發(fā)生碰撞，此時(shí)將序列置為“00”,、“01”,，再次分別發(fā)送，序列“00”沒(méi)有響應(yīng),，序列“01”發(fā)生碰撞,，將序列置為“010”、“011”,，成功識(shí)別,。回溯到序列“1”,，只有標(biāo)簽“100”響應(yīng),，成功識(shí)別。

2 GFA-QT算法
    在上節(jié)介紹的時(shí)隙ALOHA算法中,，系統(tǒng)實(shí)現(xiàn)起來(lái)較為容易，但是由于是隨機(jī)接入的,，所以在一定時(shí)間范圍內(nèi)可能會(huì)發(fā)生某個(gè)標(biāo)簽沒(méi)有被讀取(即標(biāo)簽“餓死”)的情形,。而二進(jìn)制樹(shù)算法中每個(gè)標(biāo)簽會(huì)被成功識(shí)別，但是識(shí)別時(shí)延較長(zhǎng),。本節(jié)將介紹一種混合的防碰撞算法GFA-QT,，它將ALOHA算法和QT算法的優(yōu)點(diǎn)結(jié)合起來(lái)，首先利用時(shí)隙ALOHA算法對(duì)標(biāo)簽數(shù)量進(jìn)行估計(jì),，然后對(duì)標(biāo)簽進(jìn)行分組,，最后利用QT算法分別讀取每一組標(biāo)簽。這種解決標(biāo)簽防碰撞算法稱為GFA-QT(Grouping Framed Aloha with Query Tree)基于分組時(shí)隙ALOHA的查詢樹(shù)算法,。
2.1 分組的概念
    在時(shí)隙ALOHA算法中,，每個(gè)標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙向閱讀器發(fā)送自身信息,，當(dāng)標(biāo)簽數(shù)量等于時(shí)隙數(shù)時(shí)，系統(tǒng)效率達(dá)到最高36.8%,。但是事實(shí)上時(shí)隙數(shù)有限,，而標(biāo)簽數(shù)可能遠(yuǎn)大于時(shí)隙數(shù)，所以對(duì)標(biāo)簽如何分組就顯得尤為重要,。由于閱讀器在識(shí)別過(guò)程開(kāi)始之前并不知曉其閱讀范圍內(nèi)的剩余標(biāo)簽數(shù)量,，在1.1節(jié)中對(duì)幾種標(biāo)簽估算方法進(jìn)行了比較，得到第4種數(shù)學(xué)模型計(jì)算的剩余標(biāo)簽數(shù)量最為準(zhǔn)確,。
    在QT算法中,，當(dāng)樹(shù)的深度為2時(shí)該算法的性能最佳，因?yàn)殚喿x器發(fā)出查詢序列“0”,、“1”時(shí)恰好分別有一個(gè)標(biāo)簽響應(yīng),。設(shè)標(biāo)簽數(shù)量為N，時(shí)隙數(shù)為L(zhǎng),，則最佳時(shí)隙數(shù)滿足N=2×L,，即每個(gè)時(shí)隙內(nèi)僅有兩個(gè)標(biāo)簽。但是這樣時(shí)隙數(shù)會(huì)過(guò)大,，系統(tǒng)無(wú)法實(shí)現(xiàn),。通過(guò)仿真得到當(dāng)時(shí)隙數(shù)為4，且每個(gè)時(shí)隙內(nèi)標(biāo)簽數(shù)量也為4時(shí),，系統(tǒng)效率達(dá)到最大,。
2.2 算法描述
    GFA-QT算法過(guò)程包括兩個(gè)階段：標(biāo)簽分組階段和標(biāo)簽識(shí)別[8-9]階段。算法的步驟如下：
    （1）預(yù)處理：首先將所有待識(shí)別的標(biāo)簽視為一組,，閱讀器設(shè)置時(shí)隙數(shù)為L(zhǎng)=4,，標(biāo)簽成功分組所需循環(huán)次數(shù)為I（I初始值為1），標(biāo)簽分裂系數(shù)M=4,，標(biāo)簽分裂門(mén)限值pth=8,，標(biāo)簽分組數(shù)為S；
    （2）閱讀器向所有標(biāo)簽發(fā)送包含幀長(zhǎng)的Probe命令,，將時(shí)隙數(shù)L告知標(biāo)簽,；
    （3）標(biāo)簽從1～L中隨機(jī)選擇一個(gè)時(shí)隙對(duì)閱讀器做出反應(yīng)，閱讀器檢測(cè)出一幀中沒(méi)有標(biāo)簽響應(yīng)的時(shí)隙數(shù)C0,，只有一個(gè)標(biāo)簽響應(yīng)的時(shí)隙數(shù)C1和有兩個(gè)或者兩個(gè)以上標(biāo)簽響應(yīng)的時(shí)隙數(shù)Ck,；
    （4）根據(jù)剩余標(biāo)簽估算模型4計(jì)算得出所有等待識(shí)別的標(biāo)簽數(shù)量Nleft，將Nleft與標(biāo)簽分裂門(mén)限值pth比較,。若Nleft<pth,，則分組結(jié)束；若Nleft>pth，則I=I+1,，S=MI-1,，利用分組函數(shù)將所有標(biāo)簽分為S組；
    （5）由于標(biāo)簽分組的隨機(jī)性,，在S組標(biāo)簽中任選一組標(biāo)簽重復(fù)步驟（2）～（4),，直至該組標(biāo)簽數(shù)滿足Nleft<pth。最終得到標(biāo)簽數(shù)組數(shù)S=MI-1,，標(biāo)簽組數(shù)為[group1,，…，groups],；
    （6）利用QT算法分別讀取[group1,，…，groups],，返回所有成功識(shí)別的標(biāo)簽,。
3 計(jì)算機(jī)仿真及結(jié)果分析
    系統(tǒng)效率是衡量RFID防碰撞算法性能的重要指標(biāo)，本文使用MATLAB對(duì)提出的GFA-QT防碰撞算法進(jìn)行仿真,，仿真了在不同的標(biāo)簽數(shù)量,、不同的時(shí)隙數(shù)下GFA-QT的系統(tǒng)效率，并與時(shí)隙ALOHA算法中的DFSA(Dynamic Framed Slotted ALOHA)算法和二進(jìn)制查詢樹(shù)QT算法的系統(tǒng)效率進(jìn)行了比較,。
3.1 仿真條件
    電子標(biāo)簽的ID碼為64 bit,，隨機(jī)生成。在仿真時(shí)不考慮標(biāo)簽的運(yùn)動(dòng),、傳輸誤碼等因素,。所有算法的指令頭、尾以及鏈路時(shí)序符合ISO/IEC 18000-6C協(xié)議規(guī)范,。在GFA-QT算法中,，設(shè)置初始時(shí)隙數(shù)為4，分組數(shù)為1,。
3.2 仿真結(jié)果
    本節(jié)首先研究了在不同的標(biāo)簽數(shù)量下,，GFA-QT、DFSA,、QT算法系統(tǒng)效率之間的差異,。設(shè)標(biāo)簽數(shù)量從100逐步增加到2 000。仿真結(jié)果如圖2所示,。

    在該仿真中看出當(dāng)標(biāo)簽數(shù)量較小時(shí),，GFA-QT算法的系統(tǒng)效率低于DFSA,、QT算法的系統(tǒng)效率,，這是因?yàn)闃?biāo)簽數(shù)量小，分組優(yōu)勢(shì)不明顯。當(dāng)標(biāo)簽數(shù)增加時(shí),，GFA-QT算法的系統(tǒng)效率優(yōu)于其他兩種算法并且趨于穩(wěn)定,，說(shuō)明該算法受標(biāo)簽數(shù)量影響不大。
    在圖3中,，探討了不同時(shí)隙數(shù)對(duì)GFA-QT算法系統(tǒng)效率的影響,，從仿真結(jié)果來(lái)看，當(dāng)時(shí)隙數(shù)為4時(shí)算法的系統(tǒng)效率高于時(shí)隙數(shù)分別為2,、8,、16時(shí)的系統(tǒng)效率。這主要是因?yàn)楫?dāng)時(shí)隙數(shù)為8或者16時(shí),，造成時(shí)隙數(shù)過(guò)大,，識(shí)別時(shí)延增加，當(dāng)時(shí)隙數(shù)為2時(shí),，容易造成標(biāo)簽分布于各個(gè)時(shí)隙不均勻,，使得閱讀器無(wú)法達(dá)到最大識(shí)別效率。

    本文提出了一種基于時(shí)隙ALOHA算法和二進(jìn)制查詢樹(shù)QT算法的混合型算法GFA-QT,，用于RFID系統(tǒng)的防碰撞功能的實(shí)現(xiàn),，該算法的系統(tǒng)效率高于現(xiàn)有的算法。仿真結(jié)果表明,，新的混合型算法將RFID系統(tǒng)識(shí)別效率提高至37.2%左右,，高于DFSA算法和QT算法。
參考文獻(xiàn)
[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）.