基于成功時(shí)隙的自適應(yīng)Q值防碰撞算法

徐春艷，陳科明，孫智勇，嚴(yán)迪科，洪 慧

（杭州電子科技大學(xué)電子信息學(xué)院，杭州310018）

基于成功時(shí)隙的自適應(yīng)Q值防碰撞算法

徐春艷，陳科明，孫智勇，嚴(yán)迪科，洪 慧

（杭州電子科技大學(xué)電子信息學(xué)院，杭州310018）

為提高射頻識(shí)別系統(tǒng)中動(dòng)態(tài)幀時(shí)隙ALOHA算法的識(shí)別效率，提出一種快速收斂的自適應(yīng)Q值防碰撞算法。基于上一幀成功識(shí)別標(biāo)簽的時(shí)隙數(shù)對(duì)Q值進(jìn)行不同步長的調(diào)整，使其以自適應(yīng)方式快速收斂到最優(yōu)Q值的情況下進(jìn)行工作，加快系統(tǒng)的標(biāo)簽識(shí)別速度，并使實(shí)際系統(tǒng)吞吐率快速逼近于理想值，保證系統(tǒng)的高吞吐率。仿真結(jié)果表明，在待識(shí)別標(biāo)簽數(shù)為5 000的情況下，該算法的系統(tǒng)吞吐率比泊松估計(jì)算法提高了8.19%，且隨著標(biāo)簽數(shù)的增加，其系統(tǒng)吞吐率可穩(wěn)定在33%以上。

射頻識(shí)別；防碰撞；ALOHA算法；快速收斂；成功時(shí)隙

1 概述

射頻識(shí)別［1］（Radio Frequency Identification，RFID）技術(shù)是一項(xiàng)非接觸式的自動(dòng)識(shí)別技術(shù)［2］，通過無線射頻方式獲取物體存儲(chǔ)在標(biāo)簽內(nèi)的相關(guān)數(shù)據(jù)，并對(duì)物體加以識(shí)別，也可修改相關(guān)數(shù)據(jù)，具有可讀寫、識(shí)別距離遠(yuǎn)、安全性好、實(shí)時(shí)性強(qiáng)等特點(diǎn)，廣泛應(yīng)用于工業(yè)自動(dòng)化、商業(yè)自動(dòng)化、物流、防偽等領(lǐng)域，成為當(dāng)前物流網(wǎng)技術(shù)研究的熱點(diǎn)之一。

超高頻RFID系統(tǒng)由閱讀器和標(biāo)簽組成［1］。當(dāng)閱讀器向標(biāo)簽發(fā)出一個(gè)請(qǐng)求信號(hào)時(shí)，它會(huì)提供能量給無源標(biāo)簽。但是由于標(biāo)簽響應(yīng)區(qū)比閱讀器的識(shí)別區(qū)要小很多，在處于多張標(biāo)簽響應(yīng)的情況下，多張標(biāo)簽反射回的信號(hào)會(huì)產(chǎn)生碰撞導(dǎo)致閱讀器不能正確接收到標(biāo)簽的響應(yīng)信息，從而降低系統(tǒng)識(shí)別效率。標(biāo)簽防碰撞算法可以降低系統(tǒng)標(biāo)簽之間產(chǎn)生碰撞的概率，提高系統(tǒng)識(shí)別效率，為此RFID系統(tǒng)中防碰撞算法的優(yōu)劣很大程度上決定了系統(tǒng)性能。

目前學(xué)術(shù)界中標(biāo)簽防碰撞算法的研究主要包括基于ALOHA協(xié)議的算法、基于樹協(xié)議的算法和基于計(jì)數(shù)器協(xié)議的算法［3］。而基于ALOHA協(xié)議的算法因?qū)崿F(xiàn)簡(jiǎn)單被大多RFID系統(tǒng)采用，例如目前全球廣泛認(rèn)可的EPC Gen2標(biāo)準(zhǔn)［4-5］就是采用該算法。然而學(xué)術(shù)界大多針對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法［6-7］的防碰撞問題的研究（包括最小值估計(jì)算法、泊松估計(jì)算法、空間點(diǎn)逼近估計(jì)算法等標(biāo)簽估計(jì)算法［8］）都是根據(jù)上一幀中產(chǎn)生的碰撞時(shí)隙數(shù)來估計(jì)未被識(shí)別的電子標(biāo)簽數(shù)［9-10］，然后據(jù)此選擇最優(yōu)的下一幀長度2Q（也即時(shí)隙的個(gè)數(shù)），提高系統(tǒng)吞吐率。但是在實(shí)際系統(tǒng)中，無法分辨出未成功識(shí)別的時(shí)隙是空閑時(shí)隙還是碰撞時(shí)隙，碰撞時(shí)隙數(shù)無法準(zhǔn)確統(tǒng)計(jì)。為此，本文提出一種新的自適應(yīng)Q值防碰撞算法，該算法只考慮上一幀中的成功時(shí)隙數(shù)，得到當(dāng)前系統(tǒng)吞吐率。對(duì)實(shí)際系統(tǒng)吞吐率與理論系統(tǒng)吞吐率進(jìn)行比較，將Q值分為是否達(dá)到理想值的2種情況，并對(duì)2種情況下Q值的調(diào)整方式進(jìn)行分析。采用不同的步長ΔQ方式來調(diào)整Q值，使系統(tǒng)Q值以最快速度收斂到最優(yōu)值，保證系統(tǒng)始終處于最優(yōu)Q值的狀態(tài)下工作，提高系統(tǒng)工作效率。

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

超高頻閱讀器的EPC Gen2協(xié)議中采用動(dòng)態(tài)幀時(shí)隙算法，其中，幀長L=2Q（Q∈［0，15］，且Q為整數(shù)）。算法通過調(diào)整Q值確定下一幀的幀長度，該算法實(shí)現(xiàn)流程如圖1所示。

圖1 動(dòng)態(tài)幀時(shí)隙ALOHA算法流程

動(dòng)態(tài)幀時(shí)隙ALOHA算法實(shí)現(xiàn)步驟如下［8］：

步驟1 在開始盤點(diǎn)存儲(chǔ)標(biāo)簽時(shí)，確定Q初值，也即確定初始幀長度L（L=2Q），閱讀器發(fā)送Query指令（包含Q參數(shù)）給標(biāo)簽群。標(biāo)簽接收到Query指令，所有未識(shí)別標(biāo)簽在（0，2Q-1）范圍內(nèi)隨機(jī)選擇一個(gè)時(shí)隙，并將其存入時(shí)隙計(jì)數(shù)器，進(jìn)入步驟2。

步驟2 閱讀器發(fā)送QueryRep指令，所有響應(yīng)標(biāo)簽的時(shí)隙計(jì)數(shù)器減1。當(dāng)標(biāo)簽時(shí)隙計(jì)數(shù)器為0時(shí)，產(chǎn)生一個(gè)16位的隨機(jī)數(shù)RN16，并將RN16發(fā)送給閱讀器。若在同一個(gè)時(shí)隙中只有一個(gè)標(biāo)簽響應(yīng)，閱讀器成功接收RN16，進(jìn)入步驟3。若在同一個(gè)時(shí)隙中多種標(biāo)簽同時(shí)響應(yīng)，則標(biāo)簽信息產(chǎn)生碰撞，閱讀器無法識(shí)別到正確的RN16，識(shí)別不成功，進(jìn)入步驟4。

步驟3 閱讀器會(huì)發(fā)送ACK指令，標(biāo)簽將EPC傳遞給閱讀器，標(biāo)簽識(shí)別成功。

步驟4 一幀結(jié)束，系統(tǒng)有標(biāo)簽產(chǎn)生碰撞。閱讀器發(fā)送QueryAdjust指令給標(biāo)簽調(diào)整Q值，重新查詢標(biāo)簽，重復(fù)上述工作，直到所有標(biāo)簽識(shí)別為止。

3 快速收斂的自適應(yīng)Q值防碰撞算法

3.1 定義與推論

由于動(dòng)態(tài)幀時(shí)隙算法是以包含多個(gè)時(shí)隙的幀為基礎(chǔ)，而且本文算法思想是依據(jù)系統(tǒng)吞吐率函數(shù)進(jìn)行Q值調(diào)整，需要分析一幀中成功發(fā)送數(shù)據(jù)的時(shí)隙數(shù)，以計(jì)算最大吞吐率值，因此給出如下定義和推論［9］。

定義1 令同一個(gè)時(shí)隙內(nèi)識(shí)別的標(biāo)簽數(shù)R服從標(biāo)簽總數(shù)為n、概率為1/L（L為幀長度，L=2Q（Q∈［0，15］，且Q為整數(shù)））的二項(xiàng)分布，即R～（n，1/L），從而同一時(shí)隙中出現(xiàn)標(biāo)簽數(shù)的概率表達(dá)式為［11-13］：

推論 根據(jù)定義1，同一時(shí)隙成功識(shí)別標(biāo)簽（識(shí)別到一張標(biāo)簽）和未成功識(shí)別標(biāo)簽（包括未識(shí)別到標(biāo)簽和多張標(biāo)簽產(chǎn)生碰撞）的概率為：

定義2 超高頻閱讀器的系統(tǒng)吞吐率為一幀時(shí)長內(nèi)成功識(shí)別到標(biāo)簽的時(shí)隙數(shù)與該幀的時(shí)隙數(shù)的比值，系統(tǒng)吞吐率可以用S表示，一幀中的成功時(shí)隙數(shù)可以用K表示，幀長用L表示。

根據(jù)定義1和推論可知，系統(tǒng)吞吐率表達(dá)式為：

根據(jù)式（5）可知，最大系統(tǒng)吞吐率Smax關(guān)于幀長度L的對(duì)應(yīng)關(guān)系如圖2所示。即同一時(shí)隙成功識(shí)別的效率S∈［1，0.367 9］，且Q≥3后系統(tǒng)吞吐率穩(wěn)定在0.367 9左右。本文定義0.367 9為系統(tǒng)吞吐率的理想值。

圖2 Q值與系統(tǒng)吞吐率的對(duì)應(yīng)關(guān)系

根據(jù)上述定義和推論，系統(tǒng)可依據(jù)S值判斷Q值是否設(shè)置合理。若S值大于0.367 9，說明系統(tǒng)設(shè)置的Q值合理，Q值不需要調(diào)整。但若是S值遠(yuǎn)離0.367 9，則說明幀長L偏離標(biāo)簽數(shù)n，需要調(diào)整Q值，使幀長L接近于待檢標(biāo)簽數(shù)。在傳統(tǒng)幀時(shí)隙算法中，每個(gè)QueryAd just命令只能對(duì)Q值進(jìn)行加1或是減1，調(diào)整Q值則收斂速度過慢。但若將S進(jìn)行分組處理，采用不同的步長ΔQ來調(diào)整Q值，就可加快Q值的收斂速度，使幀長L快速接近于待檢標(biāo)簽數(shù)n，從而提高系統(tǒng)吞吐率S。

3.2 自適應(yīng)Q值調(diào)整方法

由于提高系統(tǒng)吞吐率可以提升系統(tǒng)標(biāo)簽識(shí)別效率，因此本文算法基于成功時(shí)隙，根據(jù)當(dāng)前實(shí)際系統(tǒng)吞吐率與理想系統(tǒng)吞吐率的比較，對(duì)Q值進(jìn)行不同步長的調(diào)整，使實(shí)際系統(tǒng)吞吐率快速接近理想值，之后繼續(xù)通過Q值的調(diào)整，保證系統(tǒng)的高吞吐率，加快系統(tǒng)的標(biāo)簽識(shí)別速度。本文算法主要分為2個(gè)部分：逼近理想系統(tǒng)吞吐率的快速Q(mào)值調(diào)整方法和維持高系統(tǒng)吞吐率的自適應(yīng)Q調(diào)整方法。

3.2.1 逼近理想系統(tǒng)吞吐率的快速Q(mào)值調(diào)整方法

當(dāng)Q值取不同固定值時(shí)，根據(jù)式（4）得到待識(shí)別標(biāo)簽數(shù)與系統(tǒng)吞吐率的關(guān)系曲線如圖3所示。可以看出，標(biāo)簽數(shù)分別為8，16，32時(shí)，對(duì)應(yīng)的Q值為3，4，5的曲線都達(dá)到最高系統(tǒng)吞吐率0.368。當(dāng)標(biāo)簽數(shù)大于幀長（2Q）時(shí)，系統(tǒng)吞吐率函數(shù)為單調(diào)遞減函數(shù)，因此當(dāng)待識(shí)別標(biāo)簽數(shù)大于幀長（2Q）時(shí)，增大Q值可提高系統(tǒng)吞吐率。

圖3 不同幀長（2Q）下待識(shí)別標(biāo)簽數(shù)對(duì)應(yīng)的系統(tǒng)吞吐率

假設(shè)當(dāng)前系統(tǒng)中的幀長L=2Q小于標(biāo)簽數(shù)n，根據(jù)定義2、式（4）和圖3可得，在L＜n時(shí)系統(tǒng)吞吐率函數(shù)關(guān)于標(biāo)簽數(shù)是單調(diào)遞減的函數(shù)，因此當(dāng)標(biāo)簽數(shù)n∈［2Q，2Q+ΔQ］時(shí)，系統(tǒng)吞吐率S∈［S2，S1］（S1為標(biāo)簽數(shù)n=2Q時(shí)的系統(tǒng)吞吐率，S2為標(biāo)簽數(shù)n=2Q+ΔQ時(shí)的系統(tǒng)吞吐率），為此：

（1）當(dāng)ΔQ=1、n∈［2Q，2Q+1］時(shí)，系統(tǒng)吞吐率S∈［S2，S1］，S1，S2為：

根據(jù)式（6），當(dāng)幀長不同時(shí)，系統(tǒng)吞吐率S1，S2如圖2、圖4所示。從圖2、圖4中分別可得S∈［0.367 9，1］，S2∈［0，0.270 9］，且當(dāng)Q≥3后系統(tǒng)吞率S1，S2分別穩(wěn)定在極限值0.367 9和0.270 9左右，則當(dāng)標(biāo)簽數(shù)n∈［2Q，2Q+1］時(shí)，系統(tǒng)吞吐率S∈［S2min，S1max］，即S∈［0，1］。為此，結(jié)合式（5）系統(tǒng)達(dá)到理想狀況的條件下和ΔQ=1的情況，當(dāng)標(biāo)簽n∈（2Q，2Q+1］時(shí)，系統(tǒng)吞吐率S∈［0，0.367 9］。

圖4 ΔQ=1時(shí)的系統(tǒng)吞吐率S2

（2）當(dāng)ΔQ=2、n∈［2Q，2Q+2］時(shí)，系統(tǒng)吞吐率S∈［S2，S1］，S1，S2為：

根據(jù)式（7），當(dāng)幀長不同時(shí)，系統(tǒng)吞吐率S1，S2如圖2、圖5所示。從圖2、圖5中可得S∈［0.367 9，1］，S2∈［0，0.073 3］，且當(dāng)Q≥3后系統(tǒng)吞率S1，S2分別穩(wěn)定在極限值0.367 9和0.073 3左右，則當(dāng)標(biāo)簽數(shù)n∈［2Q，2Q+2］時(shí)，系統(tǒng)吞吐率S∈［S2min，S1max］，即S∈［0，1］。為此，結(jié)合ΔQ=1、ΔQ=2的情況，當(dāng)標(biāo)簽n∈（2Q+1，2Q+2］時(shí)，系統(tǒng)吞吐率S∈［0，0.270 9）。

圖5 ΔQ=2時(shí)的系統(tǒng)吞吐率S2

（3）當(dāng)ΔQ=3時(shí)，n∈［2Q，2Q+3］時(shí)，系統(tǒng)吞吐率S∈［S1，S2］，S1，S2為：

根據(jù)式（8），當(dāng)幀長不同時(shí)，系統(tǒng)吞吐率S1，S2如圖2、圖6所示。

圖6 ΔQ=3時(shí)的系統(tǒng)吞吐率S2

從圖2、圖6中分別可得S∈［0.367 9，1］，S2∈［0，0.002 7］。則當(dāng)標(biāo)簽數(shù)n=［2Q，2Q+3］時(shí)，系統(tǒng)吞吐率S∈［S2min，S1max］，即S∈［0，1］。為此，結(jié)合ΔQ=2和ΔQ=3的情況，當(dāng)標(biāo)簽n∈（2Q+2，2Q+3］時(shí)，系統(tǒng)吞吐率S∈［0，0.073 3）。

綜上所述，同理當(dāng)ΔQ≥4時(shí)，標(biāo)簽數(shù)n∈（2Q+3，2Q+ΔQ］時(shí)，系統(tǒng)吞吐率S∈［0，0.002 7），此時(shí)系統(tǒng)吞吐率很低近似為0，為此不做吞吐率分組考慮。因此，結(jié)合系統(tǒng)Q達(dá)到理想值情況下的系統(tǒng)吞吐率S∈［0.367 9，1］，將系統(tǒng)吞吐率分為S∈［0.367 9，1］、S∈［0.270 9，0.367 9）、S∈［0.073 3，0.270 9）、S∈［0，0.073 3）4組。為此，系統(tǒng)吞吐率臨界參考值為0.367 9，0.270 9，0.073 3，以S0，S1，S2表示，系統(tǒng)吞吐率未達(dá)到理想值時(shí)，ΔQ可取值為1，2，3，系統(tǒng)吞吐率達(dá)到理想值時(shí)，結(jié)合3.2.2節(jié)ΔQ的調(diào)整值ΔQ0，Q值調(diào)整方式與系統(tǒng)吞吐率對(duì)應(yīng)關(guān)系如表1所示。

表1 Q值調(diào)整方式與系統(tǒng)吞吐率的關(guān)系1

此時(shí)未考慮標(biāo)簽數(shù)在步長ΔQ為1范圍內(nèi)的標(biāo)簽其理想Q值也將處于Q～Q+1之間波動(dòng)。為此考慮系統(tǒng)上述情況，結(jié)合標(biāo)簽數(shù)大于時(shí)隙數(shù)時(shí)系統(tǒng)吞吐率的單調(diào)遞減特性，對(duì)系統(tǒng)效率的臨界參考值S0，S1，S2重新處理，表達(dá)式為：

其中，i=0，1，2。由式（9）和表3可得，吞吐率分組臨界值S0，S1，S2調(diào)整為0.319 4，0.172 1，0.036 7。為此，重新調(diào)整后快速收斂自適應(yīng)Q算法的Q值調(diào)整方式與系統(tǒng)吞吐率的對(duì)應(yīng)關(guān)系如表2所示。

表2 Q值調(diào)整方式與系統(tǒng)效率的關(guān)系2

3.2.2 保證高系統(tǒng)吞吐率的自適應(yīng)Q值調(diào)整方法

當(dāng)系統(tǒng)吞吐率達(dá)到理想臨界值后，此時(shí)系統(tǒng)具有最優(yōu)Q值，系統(tǒng)可以根據(jù)成功時(shí)隙數(shù)與系統(tǒng)吞吐率估算出未成功識(shí)別標(biāo)簽數(shù)，其未成功識(shí)別標(biāo)簽數(shù)n的表達(dá)式為：

為此，在吞吐率達(dá)到理想臨界值后自適應(yīng)Q值采用ΔQ0的方式調(diào)整步長ΔQ。

3.3 算法流程

結(jié)合上述系統(tǒng)吞吐率、ΔQ的調(diào)整原則，本文提出的自適應(yīng)Q算法流程（見圖7），具體步驟如下：

步驟1 設(shè)定Q的初值為0，發(fā)送Query命令，獲取一幀中的成功時(shí)隙數(shù)，得到系統(tǒng)吞吐率S。

步驟2 將系統(tǒng)吞吐率S與S0進(jìn)行比較。若系統(tǒng)吞吐率小于S0，則將S與S1，S2作比較，調(diào)整相應(yīng)的Q值，重復(fù)步驟2。若系統(tǒng)吞吐率大于等于S0值，則跳到步驟3。

步驟3 若系統(tǒng)吞吐率大于等于S0值，說明系統(tǒng)處于最優(yōu)Q值狀態(tài)下工作，估算未識(shí)別的標(biāo)簽數(shù)n，由round（lb n）獲取下一幀Q值。將當(dāng)前的Q值與上一幀的Q值作比較得到步長ΔQ，調(diào)整Q值。若剩余標(biāo)簽數(shù)為0，則標(biāo)簽識(shí)別結(jié)束，否則重復(fù)步驟2、步驟3。為此，直到所有標(biāo)簽識(shí)別完，系統(tǒng)都處于最優(yōu)Q值狀態(tài)下識(shí)別標(biāo)簽。

由式（10）可確定系統(tǒng)下一步的調(diào)整步長，其步長獲得的表達(dá)式為：

圖7 本文自適應(yīng)Q值防碰撞算法流程

4 仿真結(jié)果與分析

本文采用Matlab7.8.0對(duì)以下3種不同情況下的最小值估計(jì)算法、泊松估計(jì)算法和快速收斂Q算法性能進(jìn)行對(duì)比分析。

（1）在5 000張待識(shí)別標(biāo)簽和Q初值為0的條件下，3種算法使Q值達(dá)到理想情況所需調(diào)整次數(shù)如圖8所示。

圖8 不同調(diào)整次數(shù)時(shí)3種算法的吞吐率比較

從圖8可看出，最小值估計(jì)算法經(jīng)過11次Q值調(diào)整使系統(tǒng)吞吐率達(dá)到21.25%后無法再次提高，系統(tǒng)性能明顯比泊松估計(jì)算法和本文算法差。當(dāng)系統(tǒng)到達(dá)理想Q值（Q=12）時(shí)，系統(tǒng)達(dá)到最大吞吐率36.02%，該過程本文算法只調(diào)整了6次Q值，而泊松估計(jì)算法調(diào)整了12次Q值，收斂速度遠(yuǎn)快于另外2種算法。

（2）在5 000張待識(shí)別標(biāo)簽和不同Q初值情況下，3種算法的系統(tǒng)吞吐率如表3（吞吐率提高百分比為本文算法吞吐率與泊松算法吞吐率之比）、圖9所示。

表3 5 000張待識(shí)別標(biāo)簽情況下不同Q初值的吞吐率

圖9 不同Q初值時(shí)3種算法的系統(tǒng)吞吐率比較

從表3、圖9可以看出，當(dāng)Q初值小于10時(shí)，快速收斂自適應(yīng)Q算法系統(tǒng)吞吐率相比泊松估計(jì)算法提高了5.67%～15.62%。當(dāng)時(shí)隙數(shù)小于待識(shí)別標(biāo)簽數(shù)時(shí)，快速收斂自適應(yīng)Q算法系統(tǒng)吞吐率穩(wěn)定在32.25%～36.51%之間，相比于泊松估計(jì)算法和最小值估計(jì)算法的30.28%～36.85%和27.90%～35.67%，系統(tǒng)穩(wěn)定性具有明顯的提高。

（3）在Q初值為0、最大標(biāo)簽數(shù)為5 000張的情況下，3種算法的系統(tǒng)吞吐率如表4、圖10所示。

表4 Q初值為0情況下不同標(biāo)簽數(shù)的吞吐率提高比

圖10 不同標(biāo)簽數(shù)時(shí)3種算法的系統(tǒng)吞吐率比較

從表4、圖10可以看出，最小值估計(jì)算法系統(tǒng)吞吐率最低、性能最差。本文算法相比泊松估計(jì)算法的提高了8.19%以上，而且系統(tǒng)吞吐率穩(wěn)定在33%左右，接近理論值36.79%，性能穩(wěn)定，時(shí)隙利用率高。

5 結(jié)束語

本文為提高超高頻閱讀器系統(tǒng)的識(shí)別效率和實(shí)用性，提出基于成功時(shí)隙的快速收斂自適應(yīng)Q值防碰撞算法。該算法通過采用合理的Q調(diào)整值使系統(tǒng)吞吐率快速逼近理想值，以提高系統(tǒng)吞吐率。該算法與傳統(tǒng)Q算法相比，不僅提高了系統(tǒng)吞吐量，而且隨著標(biāo)簽數(shù)的增加，系統(tǒng)吞吐率能夠穩(wěn)定在33%以上。但是現(xiàn)有算法的Q值更新是基于前一次成功的標(biāo)簽識(shí)別，因此可進(jìn)一步優(yōu)化算法，使得算法能夠參考前多幀成功識(shí)別標(biāo)簽的經(jīng)驗(yàn)值獲得更加合理的Q值。

［1］ 黃玉蘭.物聯(lián)網(wǎng)射頻識(shí)別（RFID）核心技術(shù)詳解［M］.北京：人民郵電出版社，2010.

［2］ 張學(xué)軍，王 娟，王鎖萍.基于標(biāo)簽識(shí)別碼分組的連續(xù)識(shí)別防碰撞算法研究［J］.電子與信息學(xué)報(bào)，2011，33（5）：1159-1165.

［3］ 張 彥，陳積明.RFID與傳感器網(wǎng)絡(luò)：架構(gòu)、協(xié)議、安全與集成［M］.北京：機(jī)械工業(yè)出版社，2012.

［4］ EPC Global.ISO 18000-6C-2004 EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz，Version：1.0.9［S］.2004.

［5］ Zhu Lei.The Optim al Reading Strategy for EPC Gen-2 RFID Anti-Collision System s［J］.IEEE Transactions on Communications，2010，58（9）：2725-2733.

［6］ 李青青，劉洪武，張小林.一種基于不等長時(shí)隙的射頻識(shí)別防碰撞算法［J］.電子與信息學(xué)報(bào)，2011，33（11）：2628-2633.

［7］ Maguire Y，Pappu R.An Optimal Q-Algorithm for the ISO 18000-6C RFID Protocol［J］.IEEE Transactions on Automation Science and Engineering，2009，6（1）：16-24.

［8］ 江 建.RFID中多標(biāo)簽防碰撞技術(shù)的研究［D］.成都：電子科技大學(xué)，2009.

［9］ 龐 宇，彭 琦，林金朝，等.基于分組動(dòng)態(tài)幀時(shí)隙的射頻識(shí)別防碰撞算法［J］.物理學(xué)報(bào)，2013，62（14）：496-503.

［10］ 軒秀巍.超高頻射頻識(shí)別系統(tǒng)的關(guān)鍵技術(shù)研究［D］.天津：天津大學(xué)，2012.

［11］ Peng Qi，Zhang Chun，Wang Zhihua.A Multi-tag Emulator for the UHF RFID System［J］.IEEE Transactions on Instrumentation and Measurement，2014，63（6）：1461-1495.

［12］ Xie Lei，Yin Yafen，Vasilakos A，et al.Managing RFID Data：Challenges，Opportunities and Solutions［J］.IEEE Communications Surveys&Tutorials，2014，16（3）：1294-1311.

［13］ Zhu Lei，Yum T S P.Optimal Framed Aloha Based Anticollision Algorithms for RFID Systems［J］.IEEE Transactions on Communications，2010，58（12）：3583-3592.

編輯 陸燕菲

AdaPtive Q Value Anti-collision Algorithm Based on Successful Tim e Slot

XU Chunyan，CHEN Kem ing，SUN Zhiyong，YAN Dike，HONG Hui
（Institute of Electronic Information，Hangzhou Dianzi University，Hangzhou 310018，China）

In order to im prove the recognition efficiency of dynamic framed slot ALOHA algorithm in Radio Frequency Identification（RFID）system，this paper proposes a fast convergence amd adaptive Q value anti-collision algorithm.To make the system throughput quickly close to theoretical value，the actual system throughput based on the singleton slots is com pared with the theoretical system throughput to adjust Q value by the empirical value.Then，Q value is adaptively adjusted to ensure high system throughput and speed up tags identification.Simulation results show that the throughput of proposed algorithm is increased by more than 8.19%com pared with Poisson estimation algorithm when the number of identification tag is 5 000，and it can stabilize the throughput above 33%With the increase of tag number.

Radio Frequency Identification（RFID）；anti-collision；ALOHA algorithm；fast convergence；successful time slot

徐春艷，陳科明，孫智勇，等.基于成功時(shí)隙的自適應(yīng)Q值防碰撞算法［J］.計(jì)算機(jī)工程，2015，41（9）：7-12.

英文引用格式：Xu Chunyan，Chen Kem ing，Sun Zhiyong，et al.Adaptive Q Value Anti-collision Algorithm Based on Successful Time Slot［J］.Computer Engineering，2015，41（9）：7-12.

1000-3428（2015）09-0007-06

A

TN911

10.3969/j.issn.1000-3428.2015.09.002

國家自然科學(xué)基金資助項(xiàng)目（61107025）；浙江省自然科學(xué)基金資助項(xiàng)目（LY 13F040004）。

徐春艷（1989-），女，碩士研究生，主研方向：物聯(lián)網(wǎng)技術(shù)，射頻識(shí)別；陳科明，副教授；孫智勇、嚴(yán)迪科，碩士研究生；洪 慧，副教授。

2014-09-02

2014-10-15 E-m ail：xcy198903@163.com