0 引言

    射頻識別(Radio Frequency Identification,，RFID)是一種可以通過無線電信號識別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù)的無線通信技術(shù)^[1],。RFID系統(tǒng)的射頻通信部分包括閱讀器和標(biāo)簽，當(dāng)閱讀器的電磁能量覆蓋范圍內(nèi)同時有多個標(biāo)簽向該閱讀器返回信息時,，閱讀器便無法正確識別任何一個標(biāo)簽的信息,，這種現(xiàn)象稱之為標(biāo)簽碰撞。

    目前,，國際通用標(biāo)準(zhǔn)EPC Gen2中采用的防碰撞算法可用于解決標(biāo)簽碰撞問題,。EPC Gen2算法基于ALOHA類算法，有很好的自適應(yīng)性,，實現(xiàn)簡單,，有較低的識別時延,，但是缺點是吞吐率較低。前人的一些文章中對EPC Gen2防碰撞算法進行了優(yōu)化,，吞吐率有所提高,，但都難于實現(xiàn)，并且很多文章也沒能突破在標(biāo)簽數(shù)比較多的情況下,，吞吐率僅為36.8%的瓶頸^[2-4],。

    本文提出的優(yōu)化方案在分析了EPC Gen2算法和動態(tài)幀時隙ALOHA算法(Dynamic Frame Slotted ALOHA，DFSA)^[5]的特點和性能的基礎(chǔ)上,，提出了InnerQ算法,，仍然保持了ALOHA類算法的易于實現(xiàn)的優(yōu)點，減少了標(biāo)簽碰撞時隙數(shù),，同時提高了系統(tǒng)吞吐率,，突破了36.8%的瓶頸。

1 研究現(xiàn)狀

1.1 DFSA算法介紹

    DFSA算法是一種可以動態(tài)調(diào)整幀長,，使幀長接近待識別標(biāo)簽數(shù)目，讓系統(tǒng)吞吐率盡可能保持在最大值的一種算法,。當(dāng)幀長等于待識別標(biāo)簽數(shù)目時,，系統(tǒng)吞吐率達到最大值，并且當(dāng)標(biāo)簽數(shù)遠(yuǎn)大于1時,，吞吐率的峰值保持在36.8%,。證明過程參見文獻[6]。

1.2 EPC Gen2算法介紹

    EPC Gen2標(biāo)準(zhǔn)中的防碰撞算法也是一種特殊的DFSA算法,。該算法由讀寫器定義一段時間長度（包含若干個時隙）,，當(dāng)標(biāo)簽接收到對應(yīng)命令后，隨機選擇一個時隙進行接入,。讀寫器通過Query,、QueryRep、QueryAdjust等指令的組合對標(biāo)簽中時隙計數(shù)器數(shù)值進行調(diào)整,，當(dāng)標(biāo)簽的計數(shù)器值為0時進行響應(yīng),。在一個盤存（Inventory）周期中包含多個幀。EPC Gen2防碰撞算法可以在盤存過程中的任意時刻動態(tài)調(diào)整幀長,，使未識別標(biāo)簽進入下一幀的響應(yīng)周期中^[7],。

1.2.1 EPC Gen2防碰撞算法的實現(xiàn)步驟

    該算法流程如圖1所示，具體實現(xiàn)步驟如下：

    (1)Q初始值設(shè)為4,。讀寫器發(fā)出Query(Q)指令,，開始一個盤存周期。

    (2)標(biāo)簽會在[0,，2^Q-1]范圍內(nèi)生成一個隨機數(shù)載入到標(biāo)簽時隙計數(shù)器,。同時在閱讀器端將2^Q載入到閱讀器時隙計數(shù)器，以此記錄當(dāng)前幀長剩余時隙數(shù)。

    (3)標(biāo)簽時隙計數(shù)器的值為0時進行響應(yīng),，若當(dāng)前時隙只有一個標(biāo)簽進行響應(yīng),，則為成功時隙。若有兩個或兩個以上標(biāo)簽進行響應(yīng),，則為碰撞時隙,，Q_fp的值加上C值；若沒有標(biāo)簽響應(yīng),，則為空閑時隙,，Q_fp的值減去C值。

    (4)當(dāng)前時隙處理完成,，閱讀器的時隙計數(shù)器減去1,。若閱讀器的時隙計數(shù)器減為0，則再次發(fā)送Querry命令,，開啟新的一幀,，回到步驟(2)；若閱讀器的時隙計數(shù)不為零,，并且Q值發(fā)生了變化,，則發(fā)送QueryAdjust命令，調(diào)整Q值,，開啟新的一幀,，回到步驟(2)；若閱讀器的時隙計數(shù)器不為零,，并且Q值未發(fā)生改變,，則發(fā)送QuerryRep命令，標(biāo)簽時隙計數(shù)器的值減1,，回到步驟(3),。如此循環(huán)往復(fù)。

1.2.2 EPC Gen2防碰撞算法的性能分析

    在識別過程中,，參數(shù)Q決定了標(biāo)簽產(chǎn)生的隨機數(shù)的范圍,，參數(shù)C決定了是否改變幀長以適應(yīng)標(biāo)簽數(shù)目的變化，從而直接影響系統(tǒng)的性能,。該算法并不消耗大量的運算去估算待識別標(biāo)簽的數(shù)量,，只是去統(tǒng)計碰撞時隙、空閑時隙的次數(shù),。當(dāng)接入信道連續(xù)的發(fā)生1/C次碰撞或空閑時,，Q值進行加1或減1操作。該算法實現(xiàn)簡單,，但也有如下兩個缺點：

    (1)Q值反復(fù)跳變,。

    標(biāo)準(zhǔn)規(guī)定Q的初始值等于4,，當(dāng)標(biāo)簽數(shù)量比較多時，Q值會依次增加到某一個值,，并在該值左右反復(fù)跳變,。Q值每改變一次，標(biāo)簽就得重新生成一次隨機數(shù),，即使當(dāng)Q值改變到合理范圍（2^Q接近標(biāo)簽個數(shù)）,，仍會反復(fù)跳變，導(dǎo)致標(biāo)簽做大量的無用動作,，增加識別時延,。舉例說明：在標(biāo)簽數(shù)量為200、600和1 000的情況下,，待識別標(biāo)簽數(shù)目的變化和Q值的關(guān)系如圖2所示,。

    (2)幀長并不能做到和標(biāo)簽數(shù)相等，導(dǎo)致吞吐率較低,。

    由于Q值控制的幀長始終是2的冪,，而標(biāo)簽數(shù)量不可能總是2的冪，因此該算法的吞吐率一定無法達到36.8%的理論值,。由于C值對吞吐率有直接的影響,，而標(biāo)準(zhǔn)中又沒有給出具體的取值，因此不同的文章選取不同的C值,，分析得到的吞吐率也不同。為了便于研究,，本文借鑒文獻[8],，采用基于經(jīng)驗值的C=0.8/Q調(diào)整Q_fp的值，使得系統(tǒng)吞吐率能夠保持在32%左右,。

2 優(yōu)化算法的提出

    本文提出的優(yōu)化算法InnerQ,，針對上文提到的兩個問題進行優(yōu)化。InnerQ算法由兩部分組成,，一是穩(wěn)定Q值算法,，二是碰撞時隙再處理算法。

2.1 穩(wěn)定Q值算法

    由上文分析可知,，當(dāng)標(biāo)簽數(shù)量比較多時,，Q值會從初始值增加到某一個值，然后在這一個值左右反復(fù)跳變,?？梢栽O(shè)計穩(wěn)定Q值算法，記錄Q值的變化過程,，一旦檢測到Q值不是依次遞增或遞減,，而是反復(fù)跳變,，則固定下Q值，讓讀寫器不再反復(fù)發(fā)送QuerryAdjust,，導(dǎo)致所有待識別標(biāo)簽都反復(fù)生成隨機數(shù),。將Q值固定后的狀態(tài)定義為Q值穩(wěn)定狀態(tài)。具體算法流程如圖3所示,。

    達到Q值穩(wěn)定狀態(tài)后,，標(biāo)簽時隙的分布相對比較分散，不會出現(xiàn)大量標(biāo)簽都選擇同一個時隙,，也不會出現(xiàn)大量的空閑時隙,，造成時隙浪費的情況。在某一個時隙內(nèi)標(biāo)簽接入成功,、發(fā)生碰撞及空閑的概率^[9]如式(1)所示：

    由式(2)可以仿真得到總的標(biāo)簽數(shù)量n與達到穩(wěn)定狀態(tài)后的Q值,，以及達到穩(wěn)定狀態(tài)后，碰撞時隙中平均包含的標(biāo)簽數(shù)量N_c的對應(yīng)關(guān)系,，結(jié)果如表1所示,。

    由表1可以得出結(jié)論，當(dāng)Q值穩(wěn)定后,，標(biāo)簽的分布比較分散,，每一個碰撞時隙的標(biāo)簽數(shù)量是少量的，在2~6的范圍內(nèi),。

2.2 碰撞時隙再處理算法

    達到Q值穩(wěn)定狀態(tài)后,，只是標(biāo)簽選擇接入的時隙比較分散，但是仍有碰撞標(biāo)簽的存在,。這些標(biāo)簽需要再次處理,，才能全部識別。本文提出的方案出于兼容性的考慮,，借鑒了原先的EPC Gen2防碰撞算法的處理邏輯,，并且它是一種特殊的DFSA算法，而DFSA算法在標(biāo)簽個數(shù)比較少時,，吞吐率是比較高的,。

    證明過程如下：

    設(shè)幀長為L，標(biāo)簽數(shù)為n,。某個時隙僅被一個標(biāo)簽選擇的概率為P_s,，則：

    該函數(shù)圖像如圖4所示?？梢杂^察到,，當(dāng)標(biāo)簽數(shù)量小于40時，吞吐率明顯高于36.8%,，并且隨著標(biāo)簽的減少,，吞吐率有大幅度的提高,。而這個特點被很多研究EPC Gen2防碰撞算法優(yōu)化的學(xué)者忽視，并沒有充分利用,，導(dǎo)致提出的優(yōu)化方案總是想辦法讓吞吐率接近36.8%,，而始終無法超過這個理論瓶頸。

    本文首先利用上文提到的Q值穩(wěn)定算法,，使得每一碰撞時隙標(biāo)簽的個數(shù)平均在2~6之間,，對這些碰撞標(biāo)簽再處理并不影響到其他時隙的標(biāo)簽，同時又利用了DFSA算法在標(biāo)簽個數(shù)少時吞吐率高的特性,，大幅度提高了系統(tǒng)的吞吐率,。算法流程圖如圖5所示。

    需要注意的是,，本文在碰撞時隙再處理時借鑒了原有標(biāo)準(zhǔn)中Q值的處理流程,，但是也有一些變動，其中有個明顯的變動是Q值的初始值要從4改成2,。因為由表1的數(shù)據(jù)可知：碰撞時隙內(nèi)的標(biāo)簽數(shù)量在2~6個之間,。Q值等于2時是更接近實際標(biāo)簽的數(shù)量，雖然做不到理論上的嚴(yán)格相等,，但是在數(shù)學(xué)規(guī)律上符合DFSA算法在標(biāo)簽數(shù)量比較少時吞吐率較高的規(guī)律,。圖6展示了不同的Q的初始值對應(yīng)吞吐率的變化情況。

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

    為了從實驗角度證實InnerQ算法的有效性,，利用仿真軟件MATLAB分別對EPC Gen2算法,、DFSA算法、InnerQ算法進行仿真,。標(biāo)簽數(shù)量1 000個,。由于這3種算法都是基于ALOHA算法改進的隨機性算法，仿真的結(jié)果是取500次實驗的平均值,。以系統(tǒng)吞吐率,、碰撞時隙個數(shù),、總時隙個數(shù)這3個指標(biāo)作為評價標(biāo)準(zhǔn),，仿真得到的結(jié)果如圖7～圖9所示。

    圖7截取了標(biāo)簽數(shù)量從100～1 000個的數(shù)據(jù)來展示,，結(jié)果表明DFSA算法的吞吐率始終保持在36.8%,，與本文的的理論分析和前人的研究結(jié)果相吻合。本文提出的InnerQ算法結(jié)合了DFSA算法在少量標(biāo)簽的情況下吞吐率比較高的特點,，利用碰撞時隙再處理的思想,，使系統(tǒng)吞吐率穩(wěn)定在42%左右。

    圖8的結(jié)果表明,，InnerQ算法的碰撞時隙個數(shù)明顯小于優(yōu)化之前的算法,。因為優(yōu)化算法使得碰撞時隙內(nèi)的標(biāo)簽數(shù)目比較少,，這樣再次處理時，發(fā)生碰撞的機率就比較小,，碰撞時隙數(shù)自然就會減少,。

    圖9的結(jié)果顯示，DFSA算法,、EPC Gen2算法和InnerQ算法在識別標(biāo)簽總時隙的差別上不算太大,，雖然利用碰撞時隙再處理的方法其實是相當(dāng)于引進了更多的時隙，但是碰撞時隙內(nèi)的標(biāo)簽較少,，并且穩(wěn)定Q值算法,，使得Q值不再反復(fù)跳變，相當(dāng)于減少了不必要的時隙浪費,。所以優(yōu)化算法在整體上并沒有增加過多額外的時隙,。

4 結(jié)論

    本文研究了DFSA算法和EPC Gen2算法的特性，指出了其中被很多人忽略的地方,，從理論和仿真數(shù)據(jù)上證明,，本文提出的優(yōu)化算法可以突破原來的ALOHA類算法在多標(biāo)簽識別的情況下，吞吐率最高只能達到36.8%的瓶頸,。優(yōu)化算法的吞吐率提高到了42%左右,，碰撞時隙數(shù)也有了大幅減少，同時確保了與當(dāng)前標(biāo)準(zhǔn)的兼容性,，可以快速投入到實際的生產(chǎn)中,，具有很好的應(yīng)用前景。

參考文獻

[1] 杜云明,，周楊.無線射頻識別技術(shù)與應(yīng)用研究[J].自動化技術(shù)與應(yīng)用,，2010，29(5)：52-55.

[2] 任守綱,，楊帆,，王浩云，等.基于判決門限的RFID防碰撞Q值算法[J].計算機科學(xué),，2014,，41(8)：154-157.

[3] 吳淼，劉德盟,，張釗鋒.基于EPC Gen2防碰撞機制的研究與優(yōu)化[J].微電子學(xué)與計算機,，2013，30(5)：100-103.

[4] LEE D,，BANG O,，IM S，et al.Efficient dual bias Q-Algo-rithm and optimum weights for EPC Class 1 Generation 2 protocol[C].Wireless Conference,，2008. Ew 2008. European.IEEE,，2008：1-5.

[5] CHA J R,，KIM J H.Dynamic frame slotted ALOHA algo-rithms using fast tag estimation method for RFID system[C].Proceeding of the IEEE International Conference on Consumer Communications，2006：768-772.

[6] LEE S R,，JOO S D,，LEE C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C].IEEE Computer Society，2005：166-174.

[7] EPC Global.Radio-frequency identity protocols Class-1 Generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S/OL].(2008-05-11)[2017-08-08].URL：http：//www.gs1.org/sites/default/files/docs/epc/uhfc1g2_1_2_0-standard-20080511.pdf.

[8] FLOERKEMEIER C,，WILLE M.Comparison of transmission schemes for framed ALOHA based RFID protocols[C].International Symposium Applications and the Internet Workshops.Phoenix,，2006：94-97.

[9] CHA J R，KIM J H.Novel anti-collision algorithms for fastobject identification in RFID system[C].International Conference on Parallel and Distributed Systems. Fukuoka,，2005：63-67.

作者信息:

孫  磊1,，2，莊健敏1,，張釗鋒1

(1.中國科學(xué)院上海高等研究院,，上海201210；2.中國科學(xué)院大學(xué),，北京100190）