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

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

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

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

    在RFID識別系統(tǒng)中，標(biāo)簽防碰撞是RFID系統(tǒng)中一個關(guān)鍵問題。本文在FSA算法和DBS算法的基礎(chǔ)上提出了一種混合防碰撞算法。經(jīng)一系列理論分析和仿真實(shí)驗(yàn)證明該算法明顯比FSA算法和DBS算法更具有優(yōu)勢，能夠提高系統(tǒng)的識別效率并減少查詢的時隙數(shù)，使系統(tǒng)達(dá)到最好的性能，從而更有效地解決射頻識別系統(tǒng)中多目標(biāo)識別的防碰撞問題。
參考文獻(xiàn)
[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)中改進(jìn)的動態(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.