射頻識別系統(tǒng)中，當(dāng)讀寫器的讀寫范圍內(nèi)有多個標(biāo)簽同時存在時,，這些標(biāo)簽幾乎同時響應(yīng)讀寫器的指令,，從而產(chǎn)生碰撞，使得讀寫器不能正確接收標(biāo)簽返回的信號,。為解決產(chǎn)生的碰撞問題,，必需采取相應(yīng)的防碰撞技術(shù)。然而,，由于RFID系統(tǒng)的特殊性,，標(biāo)簽無源、存儲能力有限并且不具有載波監(jiān)聽能力,，防碰撞算法主要考慮系統(tǒng)的效率,、能耗等問題。目前已有一些方法來解決標(biāo)簽碰撞[1],。其中比較關(guān)鍵的是如何用防碰撞算法快速和有效地將標(biāo)簽全部識別出來,。縱觀已有的標(biāo)簽防碰撞方法,，主要分為基于樹形的搜索防碰撞算法和基于ALOHA的算法[2],。樹形算法主要通過遍歷所有碰撞的節(jié)點(diǎn),，檢測出碰撞后讓它分成兩個分支,，直到檢測到所有標(biāo)簽的ID都不存在碰撞便識別完成[3]?；贏LOHA的一類算法在RFID系統(tǒng)中也得到了廣泛的應(yīng)用,。ALOHA算法類主要分為純ALOHA算法、時隙ALOHA算法和動態(tài)幀時隙ALOHA[4],。動態(tài)幀時隙最大的特點(diǎn)是幀的長度可根據(jù)標(biāo)簽的具體情況而改變,，從而保證效率的最大化,。

1 動態(tài)幀時隙ALOHA的防碰撞算法分析
    ALOHA類算法最初是從純ALOHA算法，標(biāo)簽發(fā)送數(shù)據(jù)遇到碰撞則延時發(fā)送,，系統(tǒng)效率最大能到18.4%,。后來將發(fā)送時間離散化,分成若干時隙，在各時隙內(nèi)發(fā)送數(shù)據(jù)也即時隙ALOHA算法,，如此,，因去掉了不完全碰撞，系統(tǒng)效率最高達(dá)到36.8%,，而遇到大量標(biāo)簽時效率會急劇下降,。之后改進(jìn)得到幀時隙算法，在時隙算法的基礎(chǔ)上將若干個時隙組成一幀,，標(biāo)簽在與讀寫器通信時隨機(jī)選擇一個時隙發(fā)送數(shù)據(jù),，幀長度由讀寫器設(shè)定，該算法的理論最大效率也是36.8%,，不過可以分成若干幀來識別所有標(biāo)簽,。
1.1 動態(tài)幀時隙ALOHA算法
    為使系統(tǒng)吞吐量達(dá)到最大，假設(shè)每一幀的時隙數(shù)目為M,，還未讀取的標(biāo)簽數(shù)為n,。當(dāng)一個時隙只有一個標(biāo)簽的應(yīng)答時，讀取標(biāo)簽成功,。以概率論分布統(tǒng)計的構(gòu)造成功率的數(shù)學(xué)模型,，成功時隙的統(tǒng)計概率為:            
1.2 標(biāo)簽估計
　 目前已經(jīng)出現(xiàn)了多種標(biāo)簽數(shù)目估計的方法，此類估計方法大都基于將各個時隙分為沒有標(biāo)簽的空時隙,，只有一個標(biāo)簽的獨(dú)占時隙以及被兩個或多個標(biāo)簽占用的碰撞時隙的模型設(shè)計,。因?yàn)槊總€碰撞時隙至少有兩個或兩個以上的標(biāo)簽響應(yīng)，假設(shè)前一幀檢測下來有C個碰撞時隙,，Lower bound method[5]則以每個碰撞時隙有最少的兩個標(biāo)簽來估計,，也即用N=2·C來估計閱讀范圍內(nèi)未識別的標(biāo)簽數(shù)量。該算法的誤差源于它只考慮了兩個標(biāo)簽碰撞的有偏估計,，在標(biāo)簽數(shù)量比較多的情況下效率很低,。FRITS C. Schoute[6] 在lowerbound基礎(chǔ)上做了改進(jìn)，考慮到每個時隙標(biāo)簽大于3個的情形,。通過構(gòu)造泊松過程分布函數(shù),，當(dāng)標(biāo)簽數(shù)等于幀長的情況下得到N=2.39·C。即,，用N=2.39·C來估計未識別的標(biāo)簽數(shù)量,，該值比lowerbound 算法更為準(zhǔn)確，但只是靜態(tài)估計不能動態(tài)反應(yīng)當(dāng)前幀碰撞情況。
    Vogt[7]后來又提出一種不同的估計方法,，根據(jù)切比雪夫不等式：一個涉及隨機(jī)變量的隨機(jī)試驗(yàn)過程其輸出很可能在該變量的期望值附近,。因此，可以用讀取結(jié)果與期望值之間的取得最短距離時的數(shù)值來估計標(biāo)簽數(shù)目,。估計模型如式(3)所示：
 

    基于FBC-DFSA算法模型,，再結(jié)合蒙特卡洛法的思路建立了模擬標(biāo)簽識別的數(shù)學(xué)模型，并在MATLAB的環(huán)境下進(jìn)行了仿真實(shí)驗(yàn),，圖4給出了采用Lowerbound,、Schoute以及FBC_DFSA算法時系統(tǒng)效率的仿真結(jié)果。

    從結(jié)果可以看到,，在絕大多數(shù)標(biāo)簽情況下,，F(xiàn)BC方法的系統(tǒng)吞吐率都要好于其他算法。
    FBC_DFSA在標(biāo)簽數(shù)接近幀長大小處還是能取得吞吐率的最大值,，在標(biāo)簽數(shù)不等于幀長的情況下,，能夠?qū)φ`差做出調(diào)整，從而也可以進(jìn)一步提高系統(tǒng)效率,。但是反觀FBC_DFSA算法模型,，可以看到一個比較關(guān)鍵的調(diào)整參數(shù)u，u參數(shù)決定了檢測估計結(jié)果與當(dāng)前檢測結(jié)果之間的誤差調(diào)整幅度,。因此,，u的大小會影響整個系統(tǒng)的識別效率。設(shè)定初始幀長之后,，在MATLAB軟件環(huán)境下進(jìn)行仿真實(shí)驗(yàn),，實(shí)驗(yàn)部分結(jié)果如圖5所示?？梢园l(fā)現(xiàn),，在初始幀長固定的情況下，當(dāng)標(biāo)簽數(shù)改變時,，改變參數(shù)u能夠相應(yīng)地影響系統(tǒng)效率,。
   但是，隨著幀長的不斷調(diào)整,，相應(yīng)的估計誤差值也會隨之改變,，雖然已經(jīng)對系統(tǒng)效率做出了改進(jìn)，但是僅僅用固定參數(shù)u對誤差進(jìn)行調(diào)整還是不能更好地動態(tài)顯示當(dāng)前幀情況,。
    因此,，本文嘗試用一個隨誤差改變而自動調(diào)整的動態(tài)變量來代替u，提出了動態(tài)反饋調(diào)整動態(tài)幀時隙算法DFBC_DFSA,。以下實(shí)驗(yàn)選擇了用動態(tài)調(diào)整參數(shù)α|F1-F0|來代替u進(jìn)行算法的仿真,，其中,，F(xiàn)1為后來計算的測量幀長,， F0為之前估計的幀長,，α則是調(diào)整因子。當(dāng)α=1時,，得到結(jié)果如圖6所示,。

   可以看到，此時盡管在某些標(biāo)簽數(shù)量情況下,，DFBC方法的效率不及固定參數(shù)u的FBC效率,，但是從整體效果上看，特別是當(dāng)標(biāo)簽數(shù)目大于1 000后,，DFBC方法的效率都有所提高,，幾乎都能圍繞在0.35 左右，系統(tǒng)的吐率表現(xiàn)更加穩(wěn)定,。
    理論上講,，在識別幀長與未識別的標(biāo)簽數(shù)相近時，系統(tǒng)的效率能達(dá)到最高,，但是如何得到當(dāng)前閱讀范圍內(nèi)的標(biāo)簽數(shù)目便成了一個極為重要的問題,。本文分析了一系列的標(biāo)簽估計算法后，考慮到標(biāo)簽估計算法的估計誤差問題,為有效地減小估計誤差并對識別幀長做出調(diào)整,，提出了一種基于上述改進(jìn)思路的新方法,，也即FBC和DFBC動態(tài)幀時隙防碰撞算法。通過檢測后的反饋數(shù)據(jù)與之前的估計幀長作對比,，可以動態(tài)地描述和調(diào)整相應(yīng)的幀長,。從系統(tǒng)效率的仿真實(shí)驗(yàn)中看出，改進(jìn)算法在不增加過多的計算復(fù)雜度的情況下使系統(tǒng)效率得到了相應(yīng)的提高,。而且本算法的機(jī)理可以拓展到基于其他標(biāo)簽估計的動態(tài)幀時隙算法上去(像Vogt,、Bayesian等)?；贔BC/DFBC的算法也能夠較為方便地應(yīng)用到具體的RFID系統(tǒng)通信協(xié)議中去,，從而在工程上真正改善RFID系統(tǒng)的效率。
參考文獻(xiàn)
[1] FINKENZELLER K. RFID Handbook[C]. Radio-Frequency  Identifications Fundamentals and Applications, 2nd ed. New  York: wiley, 2003.
[2] MYUNG J, LEE W, SRIVASTAVA J, Adaptive binary splitting for efficient RFID tag anti-collision[J]. IEEE Commun. Left, 2006,10(3):144-146.
[3] Bai Chengsen, Zhu Jiang. Research on an RFID anti-collision improved algorithm based on binary search[J]. International Conference on Computer Application and System  Modelling (ICCASM), 2010(6):430-432.
[4] 程良倫,，林偉勇.一種穩(wěn)定高效的動態(tài)幀時隙ALOHA算法[J].計算機(jī)應(yīng)用研究,，2009，26(1)：85-91.
[5] FLOERKEMEIER C. Transmission control scheme for fast RFID object identification[C]. IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOMW), 2006.
[6] SCHOUTE F C. Dynamic frame length ALOHA[J].IEEE Transactions on Communications, 1983,31(4):565-568.
[7] VOGT H. Efficient object identification with passive RFID tags[C]. in Proc. Int. Conf. Pervasive Computing, 2002:98-113.
[8] 韓振偉,宋克非.射頻識別防碰撞Q算法的分析與改進(jìn)[J].計算機(jī)工程與設(shè)計,，2011,32(7),2313-2318.
[9] Wu Haifeng, Zeng Yu. Tag estimate and frame length for dynamic frame slotted ALOHA anti-collision RFID system[J]. Acta Automatic SINCA, 2010,36(4):620-624.