射頻識別RFID（Radio Frequency Identification）是一種非接觸式自動識別技術，它通過無線射頻方式進行非接觸雙向數據通信，能夠自動識別目標對象并獲取相關數據，無需人工接觸，能夠實現自動化且不易損壞。可識別高速運動物體,并可同時識別多個射頻標簽，操作快捷方便。射頻識別技術被廣泛應用于工業自動化、商業自動化、交通運輸控制管理等眾多領域。RFID系統一般包含電子標簽，讀寫器（RFID天線和RFID控制器）和計算機數據管理系統三部分。RFID系統工作時，在讀寫器的作用范圍內可能存在多個標簽，這些標簽在同時響應讀寫器的查詢時會出現數據碰撞，導致讀寫器無法正確讀出標簽數據，這就是RFID系統中的碰撞問題。因此，用于解決讀寫器作用范圍內多標簽識別問題的防碰撞算法已成為該領域研究的熱點之一。
    目前比較經典的防碰撞算法主要有基于Aloha的防碰撞算法和二進制搜索BS（Binary Search）算法[1-2]。基于Aloha的防碰撞算法包括幀時隙Aloha FSA(Frame Slotted Aloha)算法和動態幀時隙DFSA(Dynamic Frame Slotted Aloha)算法[3-4]及其改進算法。該算法操作簡便，便于實際應用。但是由于該算法的時隙是隨機分配的，當大量標簽并存時，幀沖突嚴重，存在“標簽饑餓”問題。而基于二進制搜索算法，包括動態二進制搜索DBS（Dynamic Binary search）算法[1]、自適應二叉樹搜索(Adaptive Binary Splitting)算法[5]和查詢樹搜索算法[6]QT（Query Tree）等。這類算法的電路實現比Aloha算法復雜，增加了不必要的識別時延。鑒于此，本文提出了新型的RFID混合防碰撞算法。該算法結合幀時隙Aloha算法（FSA）和動態二進制搜索算法(DBS)，大大提高了系統的識別效率。
1 新型的RFID混合防碰撞算法
    本文提出的RFID混合防碰撞算法是基于兩方面的目的：(1)通過FSA算法在第一個階段來減少碰撞發生的次數； (2)通過DBS算法在第二個階段處理發生的碰撞。本算法步驟如下：
    (1)讀寫器發送查詢指令和幀長N，通過FSA算法對時隙進行查詢。如果一幀中某個時隙為成功時隙，可直接讀取標簽，然后標簽進入“休眠”狀態；如果為空閑時隙，則不進行任何操作；如果為碰撞時隙，讀寫器估算出當前的碰撞時隙數Ck。
    (2)計算Ck/N,如果Ck/N≤?酌(0.5≤?酌≤1)，則發生碰撞的時隙小于幀長的一半。這時處于讀寫器作用范圍內的待識別標簽較少，此時這些待識別標簽直接采用DBS算法。當Ck/N≤?酌時，則發生的碰撞時隙較多，待識別的標簽也較多，此時需要通過比較標簽ID的一部分比特位，以限制響應請求命令的標簽數。讀寫器向標簽發送比較的開始位，比較位的長度和基準值；標簽接收到這些數據后，將自己的部分序列號與規定的比較基準值相比較，如若小于比較基準值，該標簽響應讀寫器，開始采用DBS算法對符合條件的標簽進行查詢,直到這部分標簽全部正確識別并進入休眠狀態。進而判斷是否仍有標簽存在，如有標簽可繼續重復步驟(1)和步驟(2)直到所有標簽全被正確識別；如沒有標簽，則該算法結束。例如，假設標簽的ID號為64 bit的二進制數，比較開始位為第35位,比較位的長度為6，比較基準值為100 000。如果標簽的第35位到30位的比特數小于或等于比較基準值，則該標簽響應讀寫器，采用DBS算法；大于比較基準值則標簽不響應讀寫器，處于等待狀態等待下一次的查詢。如果此時直接采用動態DBS算法，會造成很多碰撞，浪費大量資源。因為DBS在標簽相對較少的情況下,可以對標簽進行快速高效地識別；而當標簽數量較多時,由于初期對標簽的選擇識別會發生較多碰撞,造成浪費過多的時隙和信道資源，降低了算法的識別效率。圖1為該算法的搜索流程圖。

2 算法性能的分析比較
2.1理論性能分析
   根據混合防碰撞算法描述，可知該算法的步驟(1)通過采用FSA算法識別標簽并估算當前碰撞時隙數Ck，然后計算Ck/N，并判斷是否直接采用DBS算法。因此混合防碰撞算法時隙數是FSA算法時隙數和DBS算法時隙數之和。

     通過式(9)可以看出β>0.5，即混合防碰撞算法的識別效率要高于其他兩種算法。
2.2仿真結果分析

     假定標簽均勻地分布在讀寫器作用的范圍內，已經被識別的標簽性能較穩定。圖2所示為三種算法在系統的識別效率和查詢時隙數這兩方面的Matlab仿真比較。從圖2可以看出當標簽數量超過一定值時，混合防碰撞算法的識別效率要比其他兩種算法高，可達61%。而FSA算法的系統識別效率最高達到36.8%，DBS算法的系統識別效率保持在50%左右。圖3則表明混合算法優于其他兩種算法，該算法能夠減少總的查詢時隙數，加快標簽識別過程。總之，通過各方面的比較，混合防碰撞算法的性能要比其他兩種算法更具有優勢，系統性能更好。

    在RFID識別系統中，標簽防碰撞是RFID系統中一個關鍵問題。本文在FSA算法和DBS算法的基礎上提出了一種混合防碰撞算法。經一系列理論分析和仿真實驗證明該算法明顯比FSA算法和DBS算法更具有優勢，能夠提高系統的識別效率并減少查詢的時隙數，使系統達到最好的性能，從而更有效地解決射頻識別系統中多目標識別的防碰撞問題。
參考文獻
[1] FINKENZELLER K. RFID Handbook: Fundamentals and applications in contact　less smart cards and identification [M].New York: John Wiley and Sons, 2003.
[2] 莫磊.計數型位屏蔽射頻識別防碰撞算法設計[J].電訊技術，2010,50(9):60-64.
[3] 宋鵬，王剛．RFID系統中改進的動態幀時隙ALOHA算法[J]．煤炭技術，2010，29(7)：136-138．
[4] CHA J R, KIM J H. Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system[D].Proceedings of the 3rd IEEE Consumer Communications and networking conference[C]. Piscataway, NJ, USA: IEEE,  2006.
[5] MYUNG J, LEE W, SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.
[6] LAW C. LEE K, KAI Y S. Efficient memory less protocol for tag identification[C]. Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. Boston,USA:ACM, 2000.