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

胡智宏，李 凱

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

0 引言

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

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

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

1.1 算法總體描述

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

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

2）時(shí)隙計(jì)數(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í)隙計(jì)數(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）在一幀識(shí)別結(jié)束后判斷Q值，若Q的值改變，讀寫器發(fā)送QueryAdjust指令，改變Q值并開(kāi)啟一個(gè)新的盤存周期，若Q的值不變則發(fā)送Query指令開(kāi)啟一個(gè)新的盤存周期，轉(zhuǎn)到步驟1執(zhí)行。

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

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

1.2 最佳幀長(zhǎng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 不同算法下的識(shí)別時(shí)間

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

[5] 李萌,錢志鴻,張旭,等.基于時(shí)隙預(yù)測(cè)的RFID防碰撞ALOHA算法[J].通信學(xué)報(bào),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é)報(bào),2009,22(6):865-868.

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

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

[12] 吳海鋒,曾玉.RFID動(dòng)態(tài)幀時(shí)隙ALOHA防沖突中的標(biāo)簽估計(jì)和幀長(zhǎng)確定[J].自動(dòng)化學(xué)報(bào),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] 李青青,劉洪武,張小林.一種基于不等長(zhǎng)時(shí)隙的射頻識(shí)別防碰撞算法[J].電子與信息學(xué)報(bào),2011,33(11):2628-2633.