基于幀內(nèi)調(diào)整的RFID防碰撞Q值算法的研究

胡智宏，李 凱

（鄭州輕工業(yè)學(xué)院 電氣信息工程學(xué)院，鄭州 450002）

0 引言

RFID（Radio Frequency Identif i cation）技術(shù)是20世紀(jì)80年代興起的一種非接觸式的自動識別技術(shù)[1]。閱讀器通過無線射頻方式與電子標(biāo)簽進(jìn)行雙向數(shù)據(jù)通信，識別電子標(biāo)簽并對其進(jìn)行讀/寫操作[2]。RFID技術(shù)具有很多突出的優(yōu)點(diǎn)，如識別距離遠(yuǎn)、多目標(biāo)自動識別、能夠工作在惡劣的環(huán)境下、電子標(biāo)簽存儲的信息量大以及具有很高的保密性等[3]。因此在工業(yè)自動化、交通運(yùn)輸管理、物流倉儲自動化和圖書檔案管理等領(lǐng)域得到了廣泛的應(yīng)用[4]。但其在使用中存在很多技術(shù)難點(diǎn)，比如當(dāng)多個標(biāo)簽進(jìn)入同一個讀寫器的射頻覆蓋區(qū)時，它們之間會產(chǎn)生碰撞的問題，該問題也是影響RFID技術(shù)應(yīng)用的一個問題。ISO 18000-6C標(biāo)準(zhǔn)提出了一種解決多標(biāo)簽碰撞問題的建議算法，即Q值防碰撞算法[3]。但該算法中沒有明確給出參數(shù)C調(diào)整時的取值，且其僅在一幀結(jié)束時調(diào)整Q值的大小，使其在識別多個標(biāo)簽時時隙利用率不高，系統(tǒng)吞吐率低。

基于以上原因，首先給出了不同標(biāo)簽數(shù)量下使系統(tǒng)吞吐率達(dá)到最大的Q值，其次提出了在幀內(nèi)動態(tài)調(diào)整Q值的方法，在一幀的中間時隙和結(jié)尾處分別對Q值進(jìn)行調(diào)整。算法的改進(jìn)對提高系統(tǒng)的吞吐率和標(biāo)簽的識別速度具有重要意義。

1 經(jīng)典Q值防碰撞算法

1.1 算法總體描述

對于超高頻頻段的標(biāo)簽識別來說，6C是一種常見的應(yīng)用標(biāo)準(zhǔn)。其識別過程簡述如下：讀寫器首先向標(biāo)簽發(fā)送包含參數(shù)Q的Query命令，并開啟一個盤存周期，即讀寫器對標(biāo)簽盤存2Q次[5～8]。

1）標(biāo)簽根據(jù)參數(shù)Q產(chǎn)生一個16位的RN16作為代表其身份的臨時ID，并從中抽取Q位的子集將其置入時隙計數(shù)器（slot counter）中[5～8]；

2）時隙計數(shù)器數(shù)值為0的標(biāo)簽立即響應(yīng)，反射其RN16。若讀寫器接收到有效的RN16，則發(fā)送包含該RN16參數(shù)的ACK指令，若標(biāo)簽收到有效的ACK指令則將其EPC反射給閱讀器并轉(zhuǎn)換到確認(rèn)狀態(tài)[5～8]。時隙計數(shù)器數(shù)值不為0的標(biāo)簽進(jìn)入仲裁狀態(tài)[5～8]；

3）讀寫器發(fā)送QueryRep指令，處于仲裁狀態(tài)標(biāo)簽的slot counter的數(shù)值減1，執(zhí)行步驟2的操作；

4）在一幀識別結(jié)束后判斷Q值，若Q的值改變，讀寫器發(fā)送QueryAdjust指令，改變Q值并開啟一個新的盤存周期，若Q的值不變則發(fā)送Query指令開啟一個新的盤存周期，轉(zhuǎn)到步驟1執(zhí)行。

在一個時隙中，若沒有標(biāo)簽應(yīng)答則為空閑時隙；若有單個標(biāo)簽應(yīng)答為成功時隙；若有多個標(biāo)簽應(yīng)答則為碰撞時隙。Q值防碰撞算法就是讀寫器通過檢測到的空閑時隙、成功時隙和碰撞時隙的個數(shù)來動態(tài)調(diào)整Q值的大小[9～11]，其算法流程如圖1所示。其中Qfp為參數(shù)Q的浮點(diǎn)表示，C為Q值的調(diào)整步長。在一個盤存周期中，若讀寫器檢測到空閑時隙，則Qfp=max(0,Qfp-C)；若檢測到成功時隙，則Qfp保持不變；若檢測到碰撞時隙，則Qfp=min(15,Qfp+C)[9～11]。當(dāng)Q值較大時，C取較小值，而當(dāng)Q值較小時，C取較大值。在一幀結(jié)束時對Qfp取整并調(diào)整Q的值[9～11]。

圖1 Q值防碰撞算法流程圖

1.2 最佳幀長

在一個盤存周期中，當(dāng)標(biāo)簽的數(shù)量遠(yuǎn)大于時隙數(shù)時，會出現(xiàn)大量的碰撞時隙，導(dǎo)致時隙的浪費(fèi)；而當(dāng)標(biāo)簽的數(shù)量遠(yuǎn)小于時隙數(shù)時，會出現(xiàn)很多空時隙，也會造成時隙的浪費(fèi)。可以證明，當(dāng)時隙數(shù)約等于標(biāo)簽數(shù)時，讀寫器在一幀中識別出的成功時隙的數(shù)目達(dá)到最大值，能識別出最多的標(biāo)簽數(shù)。證明過程如下：

假設(shè)待識別的標(biāo)簽數(shù)為N，如果標(biāo)簽隨機(jī)選擇（0,L）中的隨機(jī)數(shù)ξ載入槽計數(shù)器，并且各個Tag選擇的數(shù)值是相互獨(dú)立的，則ξ服從二項分布，ξ～ B（N,1/L）。因此，一個時隙為空，成功和碰撞時隙的概率為[12]：

系統(tǒng)的吞吐率為：

由式(2)可得成功時隙的數(shù)學(xué)期望為：

通過對式(4)中的L求導(dǎo)，并令其等于0，可得：

即每幀時隙的個數(shù)與待識別的Tag數(shù)近似相等時，系統(tǒng)的吞吐率能取得最大值。該時隙數(shù)即為Q值算法的最佳幀長。

由于Q值算法沒有具體給出C值的大小，只是建議C的值在0.1～0.5之間，當(dāng)Q取較大值時C取較小值，Q取較小值時C取較大值[13]。因此，我們首先需要確定不同標(biāo)簽數(shù)下的最佳幀長，以此來得到不同標(biāo)簽數(shù)下的最佳Q值。

圖2 不同幀長的系統(tǒng)吞吐率與標(biāo)簽數(shù)關(guān)系圖

圖2描述了不同的標(biāo)簽數(shù)量在不同的幀長下系統(tǒng)的吞吐率。從圖中可以看出，當(dāng)幀長與標(biāo)簽的數(shù)量近似相等時，系統(tǒng)的吞吐率達(dá)到理論上的最大值，近似為0.368。通過式(4)和圖2，我們可以得到不同標(biāo)簽數(shù)下的最佳Q值，如表1所示。

表1 不同標(biāo)簽數(shù)下的最佳Q值

2 改進(jìn)的Q值防碰撞算法

以往對防碰撞算法的改進(jìn)，主要包括兩個方面：一是提高未識別標(biāo)簽數(shù)目預(yù)測的準(zhǔn)確度。但復(fù)雜的標(biāo)簽預(yù)測算法會加重計算能力有限的讀寫器的負(fù)擔(dān)；二是與其他防碰撞算法相結(jié)合，例如與二叉樹防碰撞算法的結(jié)合。但二叉樹防碰撞算法的實現(xiàn)要求讀寫器的編碼方式為曼徹斯特編碼，而6C標(biāo)準(zhǔn)規(guī)定的讀寫器的編碼方式為PIE編碼[14]。這些改進(jìn)在一定程度上都可以提高系統(tǒng)的吞吐率，但不利于在實際中的應(yīng)用。

本文在先前研究和經(jīng)典Q值算法的基礎(chǔ)上，提出了在6C標(biāo)準(zhǔn)下易于實現(xiàn)的改進(jìn)算法。該算法采用Lowbou-nd算法[15]來預(yù)測標(biāo)簽的數(shù)量，以減輕計算能力有限的讀寫器的負(fù)擔(dān)。經(jīng)典Q值算法是在一幀識別結(jié)束時調(diào)整Q的值，而當(dāng)幀長較大時，不合適的Q值會造成大量碰撞時隙或空閑時隙的出現(xiàn)，導(dǎo)致系統(tǒng)的吞吐率下降。改進(jìn)算法采用了在幀內(nèi)動態(tài)調(diào)整Q值的策略，在一幀的中間時隙和結(jié)束時分別對標(biāo)簽的數(shù)量進(jìn)行預(yù)測，并與表1中得到的最佳幀長進(jìn)行比較，若與其不同則發(fā)送QueryAdjust或Query指令調(diào)整Q的值，使幀長調(diào)整到最佳值；具體的算法流程如圖3所示。

圖3 改進(jìn)的Q值防碰撞算法流圖

3 系統(tǒng)仿真與性能分析

在MATLAB平臺下分別對固定幀時隙算法、基于Schoute預(yù)測的DFSA（Dynamic Framed Slotted Aloha）算法[15]和改進(jìn)算法的系統(tǒng)吞吐率和識別時間進(jìn)行了仿真。標(biāo)簽范圍選擇在0～500之間，結(jié)果是通過測試1000次求其平均值得到的。

由圖4可以看出，256固定幀時隙算法在標(biāo)簽數(shù)和時隙數(shù)相等時，系統(tǒng)吞吐率達(dá)到最大值0.368，基于Schoute預(yù)測的DFSA算法系統(tǒng)吞吐率維持在0.37左右；改進(jìn)算法的吞吐率維持在0.42左右。在標(biāo)簽數(shù)量大于50個時，改進(jìn)算法的性能優(yōu)勢明顯。

圖4 不同算法下的系統(tǒng)吞吐率

圖5 不同算法下的識別時間

由圖5可知，基于Schoute預(yù)測的DFSA算法和本文所提出的改進(jìn)算法識別標(biāo)簽所需的時間要少于時隙數(shù)為256的固定幀時隙算法。改進(jìn)算法在標(biāo)簽數(shù)較小時所用的識別時間多于DFSA算法。但當(dāng)標(biāo)簽數(shù)大于50時，改進(jìn)算法所用的識別時間增長緩慢并少于DFSA算法，說明該改進(jìn)算法在標(biāo)簽數(shù)較多時性能較好。如圖5所示, 該改進(jìn)算法識別500個標(biāo)簽大概需要1450ms，識別速度約為345個/秒。物流管理的應(yīng)用中要求讀寫器的識別速度要大于300個/秒，故該改進(jìn)算法能滿足物流管理的應(yīng)用要求。

4 結(jié)束語

本文通過理論推導(dǎo)和仿真，給出了不同標(biāo)簽數(shù)量下的最佳Q值，并在Q值算法的基礎(chǔ)上提出了一種改進(jìn)算法。該改進(jìn)算法采取了在一幀的中間時隙和結(jié)束時分別動態(tài)調(diào)整Q值的策略。通過與其他算法的比較，證明了該改進(jìn)算法在性能上的優(yōu)越性。同時該算法也考慮了

ISO 18000-6C標(biāo)準(zhǔn)和實際的硬件條件，能在計算能力有限的讀寫器上實現(xiàn)，具有實用價值。

[1] 管小衛(wèi),傅偉,蔣道霞.一種改進(jìn)的分組幀時隙ALOHA算法[J].制造業(yè)自動化,2014,36(7):1-4.

[2] 陸冰清,牛國柱,趙英臣.一種新型RFID動態(tài)多叉樹查詢防碰撞算法[J].制造業(yè)自動化,2012,34(15):12-15.

[3] 王維,宣兆龍,程澤,等.基于RFID技術(shù)的彈藥儲運(yùn)方艙自動識別系統(tǒng)研究[J].包裝工程,2014,35(11):91-95.

[4] 張學(xué)軍,蔡文琦,王鎖萍.改進(jìn)型自適應(yīng)多叉樹防碰撞算法研究[J].電子學(xué)報,2012,40(1):193-198.

[5] 李萌,錢志鴻,張旭,等.基于時隙預(yù)測的RFID防碰撞ALOHA算法[J].通信學(xué)報,2011,32(12):43-50.

[6] Muhammad F,Muddassar A, Syed N, etal. Optimal Adjustment Parameters for EPC Global RFID Anti-Colli -sion Q Algorithm in Different Traffic Scenarios[A].Proc of 10th International Conference on Frontiers of In -formation Technology, Islamabad,Pakistan[C],CA,2012:302-305.

[7] Andreas S,Christoph R. Retransmission Strategies for RFID systems Using the EPC Protocol[A].Proc of the 2013 IEEE International Conference on RFID Technologies and Applications,Johor Bahru, Malaysia,CA[C].2013:1-6.

[8] Eom J, Lee T.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Com-munications Letters,2010,14(1):60-62.

[9] 陳穎,張福洪,廖彬彬.一種新的RFID傳感系統(tǒng)的防碰撞算法的研究[J].傳感技術(shù)學(xué)報,2009,22(6):865-868.

[10] 王進(jìn),易靈芝,王根平.新型Q值防碰撞算法在RFID系統(tǒng)中的研究[J].計算機(jī)工程與科學(xué),2011,33(6):182-185.

[11] 任守綱,楊帆,徐煥良.一種雙權(quán)重參數(shù)的RFID防碰撞Q值算法研究[J].計算機(jī)科學(xué),2014,41(4):256-259.

[12] 吳海鋒,曾玉.RFID動態(tài)幀時隙ALOHA防沖突中的標(biāo)簽估計和幀長確定[J].自動化學(xué)報,2010,36(4):620-624.

[13] Chen Y H, Horng S J,and Tun R S. A novel anti-collision algorithm in RFID systems for identifying pa-ssive tags[J].IEEE Transactions on Industrial Informatics, 2010,6(1):105-121.

[14] Eom J, Lee T.Rietman R. An efficient framed-slotted ALOHA algorithm with pilot frame and binary sele-ction for anti-collision of RFID tags[J].IEEE Communications Letters,2008,12(10):861-863.

[15] 李青青,劉洪武,張小林.一種基于不等長時隙的射頻識別防碰撞算法[J].電子與信息學(xué)報,2011,33(11):2628-2633.