摘  要： 在分析了目前現有的時隙ALOHA算法和查詢樹QT算法后，結合這兩類算法的優點，提出了一種混合型算法GFA-QT來解決RFID中的碰撞問題。理論與仿真表明，這種混合型的算法在系統效率上優于現有的算法。
關鍵詞： 射頻識別；防碰撞；GFA-QT；吞吐量

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

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

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

    在該仿真中看出當標簽數量較小時，GFA-QT算法的系統效率低于DFSA、QT算法的系統效率，這是因為標簽數量小，分組優勢不明顯。當標簽數增加時，GFA-QT算法的系統效率優于其他兩種算法并且趨于穩定，說明該算法受標簽數量影響不大。
    在圖3中，探討了不同時隙數對GFA-QT算法系統效率的影響，從仿真結果來看，當時隙數為4時算法的系統效率高于時隙數分別為2、8、16時的系統效率。這主要是因為當時隙數為8或者16時，造成時隙數過大，識別時延增加，當時隙數為2時，容易造成標簽分布于各個時隙不均勻，使得閱讀器無法達到最大識別效率。

    本文提出了一種基于時隙ALOHA算法和二進制查詢樹QT算法的混合型算法GFA-QT，用于RFID系統的防碰撞功能的實現，該算法的系統效率高于現有的算法。仿真結果表明，新的混合型算法將RFID系統識別效率提高至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）.