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

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

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

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

    在RFID識別系統(tǒng)中，標簽防碰撞是RFID系統(tǒng)中一個關(guān)鍵問題,。本文在FSA算法和DBS算法的基礎(chǔ)上提出了一種混合防碰撞算法,。經(jīng)一系列理論分析和仿真實驗證明該算法明顯比FSA算法和DBS算法更具有優(yōu)勢，能夠提高系統(tǒng)的識別效率并減少查詢的時隙數(shù),，使系統(tǒng)達到最好的性能,，從而更有效地解決射頻識別系統(tǒng)中多目標識別的防碰撞問題。
參考文獻
[1] FINKENZELLER K. RFID Handbook: Fundamentals and applications in contact　less smart cards and identification [M].New York: John Wiley and Sons, 2003.
[2] 莫磊.計數(shù)型位屏蔽射頻識別防碰撞算法設(shè)計[J].電訊技術(shù),，2010,50(9):60-64.
[3] 宋鵬,，王剛．RFID系統(tǒng)中改進的動態(tài)幀時隙ALOHA算法[J]．煤炭技術(shù)，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.