RFID動(dòng)態(tài)幀時(shí)隙防沖撞改進(jìn)算法研究

陳春明,馮玉田，付良成

（上海大學(xué) 通信與信息工程學(xué)院，上海 200072）

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

1 動(dòng)態(tài)幀時(shí)隙ALOHA的防碰撞算法分析

ALOHA類算法最初是從純ALOHA算法，標(biāo)簽發(fā)送數(shù)據(jù)遇到碰撞則延時(shí)發(fā)送，系統(tǒng)效率最大能到18.4%。后來將發(fā)送時(shí)間離散化,分成若干時(shí)隙，在各時(shí)隙內(nèi)發(fā)送數(shù)據(jù)也即時(shí)隙ALOHA算法，如此，因去掉了不完全碰撞，系統(tǒng)效率最高達(dá)到36.8%，而遇到大量標(biāo)簽時(shí)效率會(huì)急劇下降。之后改進(jìn)得到幀時(shí)隙算法，在時(shí)隙算法的基礎(chǔ)上將若干個(gè)時(shí)隙組成一幀，標(biāo)簽在與讀寫器通信時(shí)隨機(jī)選擇一個(gè)時(shí)隙發(fā)送數(shù)據(jù)，幀長度由讀寫器設(shè)定，該算法的理論最大效率也是36.8%，不過可以分成若干幀來識(shí)別所有標(biāo)簽。

1.1 動(dòng)態(tài)幀時(shí)隙ALOHA算法

為使系統(tǒng)吞吐量達(dá)到最大，假設(shè)每一幀的時(shí)隙數(shù)目為M，還未讀取的標(biāo)簽數(shù)為n。當(dāng)一個(gè)時(shí)隙只有一個(gè)標(biāo)簽的應(yīng)答時(shí)，讀取標(biāo)簽成功。以概率論分布統(tǒng)計(jì)的構(gòu)造成功率的數(shù)學(xué)模型，成功時(shí)隙的統(tǒng)計(jì)概率為: ,

其中ps為傳輸同路的吞吐率，M為一幀的時(shí)隙數(shù) (幀長)，n為閱讀器范圍內(nèi)未識(shí)別的標(biāo)簽數(shù)。固定n對(duì)M求導(dǎo)：

1.2 標(biāo)簽估計(jì)

目前已經(jīng)出現(xiàn)了多種標(biāo)簽數(shù)目估計(jì)的方法，此類估計(jì)方法大都基于將各個(gè)時(shí)隙分為沒有標(biāo)簽的空時(shí)隙，只有一個(gè)標(biāo)簽的獨(dú)占時(shí)隙以及被兩個(gè)或多個(gè)標(biāo)簽占用的碰撞時(shí)隙的模型設(shè)計(jì)。因?yàn)槊總€(gè)碰撞時(shí)隙至少有兩個(gè)或兩個(gè)以上的標(biāo)簽響應(yīng)，假設(shè)前一幀檢測(cè)下來有C個(gè)碰撞時(shí)隙，Lower bound method[5]則以每個(gè)碰撞時(shí)隙有最少的兩個(gè)標(biāo)簽來估計(jì)，也即用N=2·C來估計(jì)閱讀范圍內(nèi)未識(shí)別的標(biāo)簽數(shù)量。該算法的誤差源于它只考慮了兩個(gè)標(biāo)簽碰撞的有偏估計(jì)，在標(biāo)簽數(shù)量比較多的情況下效率很低。FRITS C.Schoute[6]在lowerbound基礎(chǔ)上做了改進(jìn)，考慮到每個(gè)時(shí)隙標(biāo)簽大于3個(gè)的情形。通過構(gòu)造泊松過程分布函數(shù)，當(dāng)標(biāo)簽數(shù)等于幀長的情況下得到N=2.39·C。即，用N=2.39·C來估計(jì)未識(shí)別的標(biāo)簽數(shù)量，該值比lowerbound算法更為準(zhǔn)確，但只是靜態(tài)估計(jì)不能動(dòng)態(tài)反應(yīng)當(dāng)前幀碰撞情況。

Vogt[7]后來又提出一種不同的估計(jì)方法，根據(jù)切比雪夫不等式：一個(gè)涉及隨機(jī)變量的隨機(jī)試驗(yàn)過程其輸出很可能在該變量的期望值附近。因此，可以用讀取結(jié)果與期望值之間的取得最短距離時(shí)的數(shù)值來估計(jì)標(biāo)簽數(shù)目。估計(jì)模型如式(3)所示：

其中，c0、c1、ck為實(shí)際測(cè)得的成功、空閑、碰撞時(shí)隙數(shù)值。

在標(biāo)簽數(shù)量 N取值范圍[c0+2ck,…,2(c1+2ck)]內(nèi)找到最小的ε值，所對(duì)應(yīng)的N就是估計(jì)的標(biāo)簽數(shù)量。

除此之外，還有基于Bayesian理論的后驗(yàn)概率估計(jì)方法[5],其系統(tǒng)效率有所提高但計(jì)算復(fù)雜度也變得很高。ISO-18000-6C標(biāo)準(zhǔn)中使用的Q算法[8]對(duì)系統(tǒng)的吞吐率作了一定的改進(jìn)。但是，既然是估計(jì)算法就必然會(huì)存在估計(jì)誤差，估計(jì)算法的效果影響著系統(tǒng)效率。為改善估計(jì)誤差對(duì)系統(tǒng)效率的影響，本文提出了改進(jìn)方法。

2 FBC_DFSA算法及其仿真

時(shí)隙幀識(shí)別法都涉及到標(biāo)簽估計(jì)，但這些估計(jì)算法顯然都存在誤差。因此，本文提出FBC_DFSA算法，用估計(jì)算法得到的標(biāo)簽數(shù)來設(shè)置幀長，在進(jìn)行一輪識(shí)別后得到的測(cè)量結(jié)果反饋到前面估計(jì)得到的標(biāo)簽數(shù)目，與其進(jìn)行對(duì)比，檢驗(yàn)估計(jì)算法的準(zhǔn)確性并做出調(diào)整。本算法的原理模型如圖2所示。

首先看一下基于空閑時(shí)隙、成功時(shí)隙、碰撞時(shí)隙的一系列標(biāo)簽估計(jì)，假設(shè)n個(gè)標(biāo)簽在某個(gè)幀選擇了其中第i個(gè)時(shí)隙的標(biāo)簽數(shù)目，概率分布為：

M為一幀內(nèi)時(shí)隙數(shù)。如果該時(shí)隙為碰撞時(shí)隙,x≥2。得到x標(biāo)簽選擇識(shí)別時(shí)隙的概率分布為:

可得到選擇時(shí)隙i標(biāo)簽數(shù)目的平均值：

其實(shí)可以看到，當(dāng) e=2和e=2.39時(shí)，分別為 lowerbound和Schoute估計(jì)結(jié)果。Vogt方法是通過比較一個(gè)向量組中與期望值的距離來得到最佳標(biāo)簽數(shù)，Bayesian算法用后驗(yàn)概率分布來估計(jì)識(shí)別的標(biāo)簽數(shù)目。但是，基于向量空間的搜索法 (Vogt)和基于后驗(yàn)概率分布法(Bayesian)盡管在系統(tǒng)效率上有些改進(jìn)，但是計(jì)算復(fù)雜度也比較大[9]。如圖3算法模型，基于lowerbound和Schoute的標(biāo)簽估計(jì)DFSA方法來驗(yàn)證FBC_DFSA算法。值也會(huì)隨之改變，雖然已經(jīng)對(duì)系統(tǒng)效率做出了改進(jìn)，但是僅僅用固定參數(shù)u對(duì)誤差進(jìn)行調(diào)整還是不能更好地動(dòng)態(tài)顯示當(dāng)前幀情況。

因此，本文嘗試用一個(gè)隨誤差改變而自動(dòng)調(diào)整的動(dòng)態(tài)變量來代替u，提出了動(dòng)態(tài)反饋調(diào)整動(dòng)態(tài)幀時(shí)隙算法DFBC_DFSA。以下實(shí)驗(yàn)選擇了用動(dòng)態(tài)調(diào)整參數(shù)α|F1-F0|來代替u進(jìn)行算法的仿真，其中，F(xiàn)1為后來計(jì)算的測(cè)量幀長，F(xiàn)0為之前估計(jì)的幀長，α則是調(diào)整因子。當(dāng)α=1

圖3 FBC_DFSA算法模型

基于FBC-DFSA算法模型，再結(jié)合蒙特卡洛法的思路建立了模擬標(biāo)簽識(shí)別的數(shù)學(xué)模型，并在MATLAB的環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)，圖4給出了采用Lowerbound、Schoute以及FBC_DFSA算法時(shí)系統(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算法模型，可以看到一個(gè)比較關(guān)鍵的調(diào)整參數(shù)u，u參數(shù)決定了檢測(cè)估計(jì)結(jié)果與當(dāng)前檢測(cè)結(jié)果之間的誤差調(diào)整幅度。因此，u的大小會(huì)影響整個(gè)系統(tǒng)的識(shí)別效率。設(shè)定初始幀長之后，在MATLAB軟件環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)部分結(jié)果如圖5所示?？梢园l(fā)現(xiàn)，在初始幀長固定的情況下，當(dāng)標(biāo)簽數(shù)改變時(shí)，改變參數(shù)u能夠相應(yīng)地影響系統(tǒng)效率。

但是，隨著幀長的不斷調(diào)整，相應(yīng)的估計(jì)誤差時(shí)，得到結(jié)果如圖6所示。

可以看到，此時(shí)盡管在某些標(biāo)簽數(shù)量情況下，DFBC方法的效率不及固定參數(shù)u的FBC效率，但是從整體效果上看，特別是當(dāng)標(biāo)簽數(shù)目大于1 000后，DFBC方法的效率都有所提高，幾乎都能圍繞在0.35左右，系統(tǒng)的吐率表現(xiàn)更加穩(wěn)定。

理論上講，在識(shí)別幀長與未識(shí)別的標(biāo)簽數(shù)相近時(shí)，系統(tǒng)的效率能達(dá)到最高，但是如何得到當(dāng)前閱讀范圍內(nèi)的標(biāo)簽數(shù)目便成了一個(gè)極為重要的問題。本文分析了一系列的標(biāo)簽估計(jì)算法后，考慮到標(biāo)簽估計(jì)算法的估計(jì)誤差問題,為有效地減小估計(jì)誤差并對(duì)識(shí)別幀長做出調(diào)整，提出了一種基于上述改進(jìn)思路的新方法，也即FBC和DFBC動(dòng)態(tài)幀時(shí)隙防碰撞算法。通過檢測(cè)后的反饋數(shù)據(jù)與之前的估計(jì)幀長作對(duì)比，可以動(dòng)態(tài)地描述和調(diào)整相應(yīng)的幀長。從系統(tǒng)效率的仿真實(shí)驗(yàn)中看出，改進(jìn)算法在不增加過多的計(jì)算復(fù)雜度的情況下使系統(tǒng)效率得到了相應(yīng)的提高。而且本算法的機(jī)理可以拓展到基于其他標(biāo)簽估計(jì)的動(dòng)態(tài)幀時(shí)隙算法上去(像Vogt、Bayesian等)?；贔BC/DFBC的算法也能夠較為方便地應(yīng)用到具體的RFID系統(tǒng)通信協(xié)議中去，從而在工程上真正改善RFID系統(tǒng)的效率。

[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)定高效的動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].計(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]韓振偉,宋克非.射頻識(shí)別防碰撞Q算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，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.