基于成功時隙的自適應Q值防碰撞算法

徐春艷，陳科明，孫智勇，嚴迪科，洪 慧

（杭州電子科技大學電子信息學院，杭州310018）

基于成功時隙的自適應Q值防碰撞算法

徐春艷，陳科明，孫智勇，嚴迪科，洪 慧

（杭州電子科技大學電子信息學院，杭州310018）

為提高射頻識別系統中動態幀時隙ALOHA算法的識別效率，提出一種快速收斂的自適應Q值防碰撞算法。基于上一幀成功識別標簽的時隙數對Q值進行不同步長的調整，使其以自適應方式快速收斂到最優Q值的情況下進行工作，加快系統的標簽識別速度，并使實際系統吞吐率快速逼近于理想值，保證系統的高吞吐率。仿真結果表明，在待識別標簽數為5 000的情況下，該算法的系統吞吐率比泊松估計算法提高了8.19%，且隨著標簽數的增加，其系統吞吐率可穩定在33%以上。

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

1 概述

射頻識別［1］（Radio Frequency Identification，RFID）技術是一項非接觸式的自動識別技術［2］，通過無線射頻方式獲取物體存儲在標簽內的相關數據，并對物體加以識別，也可修改相關數據，具有可讀寫、識別距離遠、安全性好、實時性強等特點，廣泛應用于工業自動化、商業自動化、物流、防偽等領域，成為當前物流網技術研究的熱點之一。

超高頻RFID系統由閱讀器和標簽組成［1］。當閱讀器向標簽發出一個請求信號時，它會提供能量給無源標簽。但是由于標簽響應區比閱讀器的識別區要小很多，在處于多張標簽響應的情況下，多張標簽反射回的信號會產生碰撞導致閱讀器不能正確接收到標簽的響應信息，從而降低系統識別效率。標簽防碰撞算法可以降低系統標簽之間產生碰撞的概率，提高系統識別效率，為此RFID系統中防碰撞算法的優劣很大程度上決定了系統性能。

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

2 動態幀時隙ALOHA算法

超高頻閱讀器的EPC Gen2協議中采用動態幀時隙算法，其中，幀長L=2Q（Q∈［0，15］，且Q為整數）。算法通過調整Q值確定下一幀的幀長度，該算法實現流程如圖1所示。

圖1 動態幀時隙ALOHA算法流程

動態幀時隙ALOHA算法實現步驟如下［8］：

步驟1 在開始盤點存儲標簽時，確定Q初值，也即確定初始幀長度L（L=2Q），閱讀器發送Query指令（包含Q參數）給標簽群。標簽接收到Query指令，所有未識別標簽在（0，2Q-1）范圍內隨機選擇一個時隙，并將其存入時隙計數器，進入步驟2。

步驟2 閱讀器發送QueryRep指令，所有響應標簽的時隙計數器減1。當標簽時隙計數器為0時，產生一個16位的隨機數RN16，并將RN16發送給閱讀器。若在同一個時隙中只有一個標簽響應，閱讀器成功接收RN16，進入步驟3。若在同一個時隙中多種標簽同時響應，則標簽信息產生碰撞，閱讀器無法識別到正確的RN16，識別不成功，進入步驟4。

步驟3 閱讀器會發送ACK指令，標簽將EPC傳遞給閱讀器，標簽識別成功。

步驟4 一幀結束，系統有標簽產生碰撞。閱讀器發送QueryAdjust指令給標簽調整Q值，重新查詢標簽，重復上述工作，直到所有標簽識別為止。

3 快速收斂的自適應Q值防碰撞算法

3.1 定義與推論

由于動態幀時隙算法是以包含多個時隙的幀為基礎，而且本文算法思想是依據系統吞吐率函數進行Q值調整，需要分析一幀中成功發送數據的時隙數，以計算最大吞吐率值，因此給出如下定義和推論［9］。

定義1 令同一個時隙內識別的標簽數R服從標簽總數為n、概率為1/L（L為幀長度，L=2Q（Q∈［0，15］，且Q為整數））的二項分布，即R～（n，1/L），從而同一時隙中出現標簽數的概率表達式為［11-13］：

推論 根據定義1，同一時隙成功識別標簽（識別到一張標簽）和未成功識別標簽（包括未識別到標簽和多張標簽產生碰撞）的概率為：

定義2 超高頻閱讀器的系統吞吐率為一幀時長內成功識別到標簽的時隙數與該幀的時隙數的比值，系統吞吐率可以用S表示，一幀中的成功時隙數可以用K表示，幀長用L表示。

根據定義1和推論可知，系統吞吐率表達式為：

根據式（5）可知，最大系統吞吐率Smax關于幀長度L的對應關系如圖2所示。即同一時隙成功識別的效率S∈［1，0.367 9］，且Q≥3后系統吞吐率穩定在0.367 9左右。本文定義0.367 9為系統吞吐率的理想值。

圖2 Q值與系統吞吐率的對應關系

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

3.2 自適應Q值調整方法

由于提高系統吞吐率可以提升系統標簽識別效率，因此本文算法基于成功時隙，根據當前實際系統吞吐率與理想系統吞吐率的比較，對Q值進行不同步長的調整，使實際系統吞吐率快速接近理想值，之后繼續通過Q值的調整，保證系統的高吞吐率，加快系統的標簽識別速度。本文算法主要分為2個部分：逼近理想系統吞吐率的快速Q值調整方法和維持高系統吞吐率的自適應Q調整方法。

3.2.1 逼近理想系統吞吐率的快速Q值調整方法

當Q值取不同固定值時，根據式（4）得到待識別標簽數與系統吞吐率的關系曲線如圖3所示。可以看出，標簽數分別為8，16，32時，對應的Q值為3，4，5的曲線都達到最高系統吞吐率0.368。當標簽數大于幀長（2Q）時，系統吞吐率函數為單調遞減函數，因此當待識別標簽數大于幀長（2Q）時，增大Q值可提高系統吞吐率。

圖3 不同幀長（2Q）下待識別標簽數對應的系統吞吐率

假設當前系統中的幀長L=2Q小于標簽數n，根據定義2、式（4）和圖3可得，在L＜n時系統吞吐率函數關于標簽數是單調遞減的函數，因此當標簽數n∈［2Q，2Q+ΔQ］時，系統吞吐率S∈［S2，S1］（S1為標簽數n=2Q時的系統吞吐率，S2為標簽數n=2Q+ΔQ時的系統吞吐率），為此：

（1）當ΔQ=1、n∈［2Q，2Q+1］時，系統吞吐率S∈［S2，S1］，S1，S2為：

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

圖4 ΔQ=1時的系統吞吐率S2

（2）當ΔQ=2、n∈［2Q，2Q+2］時，系統吞吐率S∈［S2，S1］，S1，S2為：

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

圖5 ΔQ=2時的系統吞吐率S2

（3）當ΔQ=3時，n∈［2Q，2Q+3］時，系統吞吐率S∈［S1，S2］，S1，S2為：

根據式（8），當幀長不同時，系統吞吐率S1，S2如圖2、圖6所示。

圖6 ΔQ=3時的系統吞吐率S2

從圖2、圖6中分別可得S∈［0.367 9，1］，S2∈［0，0.002 7］。則當標簽數n=［2Q，2Q+3］時，系統吞吐率S∈［S2min，S1max］，即S∈［0，1］。為此，結合ΔQ=2和ΔQ=3的情況，當標簽n∈（2Q+2，2Q+3］時，系統吞吐率S∈［0，0.073 3）。

綜上所述，同理當ΔQ≥4時，標簽數n∈（2Q+3，2Q+ΔQ］時，系統吞吐率S∈［0，0.002 7），此時系統吞吐率很低近似為0，為此不做吞吐率分組考慮。因此，結合系統Q達到理想值情況下的系統吞吐率S∈［0.367 9，1］，將系統吞吐率分為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組。為此，系統吞吐率臨界參考值為0.367 9，0.270 9，0.073 3，以S0，S1，S2表示，系統吞吐率未達到理想值時，ΔQ可取值為1，2，3，系統吞吐率達到理想值時，結合3.2.2節ΔQ的調整值ΔQ0，Q值調整方式與系統吞吐率對應關系如表1所示。

表1 Q值調整方式與系統吞吐率的關系1

此時未考慮標簽數在步長ΔQ為1范圍內的標簽其理想Q值也將處于Q～Q+1之間波動。為此考慮系統上述情況，結合標簽數大于時隙數時系統吞吐率的單調遞減特性，對系統效率的臨界參考值S0，S1，S2重新處理，表達式為：

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

表2 Q值調整方式與系統效率的關系2

3.2.2 保證高系統吞吐率的自適應Q值調整方法

當系統吞吐率達到理想臨界值后，此時系統具有最優Q值，系統可以根據成功時隙數與系統吞吐率估算出未成功識別標簽數，其未成功識別標簽數n的表達式為：

為此，在吞吐率達到理想臨界值后自適應Q值采用ΔQ0的方式調整步長ΔQ。

3.3 算法流程

結合上述系統吞吐率、ΔQ的調整原則，本文提出的自適應Q算法流程（見圖7），具體步驟如下：

步驟1 設定Q的初值為0，發送Query命令，獲取一幀中的成功時隙數，得到系統吞吐率S。

步驟2 將系統吞吐率S與S0進行比較。若系統吞吐率小于S0，則將S與S1，S2作比較，調整相應的Q值，重復步驟2。若系統吞吐率大于等于S0值，則跳到步驟3。

步驟3 若系統吞吐率大于等于S0值，說明系統處于最優Q值狀態下工作，估算未識別的標簽數n，由round（lb n）獲取下一幀Q值。將當前的Q值與上一幀的Q值作比較得到步長ΔQ，調整Q值。若剩余標簽數為0，則標簽識別結束，否則重復步驟2、步驟3。為此，直到所有標簽識別完，系統都處于最優Q值狀態下識別標簽。

由式（10）可確定系統下一步的調整步長，其步長獲得的表達式為：

圖7 本文自適應Q值防碰撞算法流程

4 仿真結果與分析

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

（1）在5 000張待識別標簽和Q初值為0的條件下，3種算法使Q值達到理想情況所需調整次數如圖8所示。

圖8 不同調整次數時3種算法的吞吐率比較

從圖8可看出，最小值估計算法經過11次Q值調整使系統吞吐率達到21.25%后無法再次提高，系統性能明顯比泊松估計算法和本文算法差。當系統到達理想Q值（Q=12）時，系統達到最大吞吐率36.02%，該過程本文算法只調整了6次Q值，而泊松估計算法調整了12次Q值，收斂速度遠快于另外2種算法。

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

表3 5 000張待識別標簽情況下不同Q初值的吞吐率

圖9 不同Q初值時3種算法的系統吞吐率比較

從表3、圖9可以看出，當Q初值小于10時，快速收斂自適應Q算法系統吞吐率相比泊松估計算法提高了5.67%～15.62%。當時隙數小于待識別標簽數時，快速收斂自適應Q算法系統吞吐率穩定在32.25%～36.51%之間，相比于泊松估計算法和最小值估計算法的30.28%～36.85%和27.90%～35.67%，系統穩定性具有明顯的提高。

（3）在Q初值為0、最大標簽數為5 000張的情況下，3種算法的系統吞吐率如表4、圖10所示。

表4 Q初值為0情況下不同標簽數的吞吐率提高比

圖10 不同標簽數時3種算法的系統吞吐率比較

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

5 結束語

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

［1］ 黃玉蘭.物聯網射頻識別（RFID）核心技術詳解［M］.北京：人民郵電出版社，2010.

［2］ 張學軍，王 娟，王鎖萍.基于標簽識別碼分組的連續識別防碰撞算法研究［J］.電子與信息學報，2011，33（5）：1159-1165.

［3］ 張 彥，陳積明.RFID與傳感器網絡：架構、協議、安全與集成［M］.北京：機械工業出版社，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］ 李青青，劉洪武，張小林.一種基于不等長時隙的射頻識別防碰撞算法［J］.電子與信息學報，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中多標簽防碰撞技術的研究［D］.成都：電子科技大學，2009.

［9］ 龐 宇，彭 琦，林金朝，等.基于分組動態幀時隙的射頻識別防碰撞算法［J］.物理學報，2013，62（14）：496-503.

［10］ 軒秀巍.超高頻射頻識別系統的關鍵技術研究［D］.天津：天津大學，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

徐春艷，陳科明，孫智勇，等.基于成功時隙的自適應Q值防碰撞算法［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

國家自然科學基金資助項目（61107025）；浙江省自然科學基金資助項目（LY 13F040004）。

徐春艷（1989-），女，碩士研究生，主研方向：物聯網技術，射頻識別；陳科明，副教授；孫智勇、嚴迪科，碩士研究生；洪 慧，副教授。

2014-09-02

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