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

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

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

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

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