0 引言

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

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

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

1 研究現狀

1.1 DFSA算法介紹

    DFSA算法是一種可以動態調整幀長，使幀長接近待識別標簽數目，讓系統吞吐率盡可能保持在最大值的一種算法。當幀長等于待識別標簽數目時，系統吞吐率達到最大值，并且當標簽數遠大于1時，吞吐率的峰值保持在36.8%。證明過程參見文獻[6]。

1.2 EPC Gen2算法介紹

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

1.2.1 EPC Gen2防碰撞算法的實現步驟

    該算法流程如圖1所示，具體實現步驟如下：

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

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

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

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

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

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

    (1)Q值反復跳變。

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

    (2)幀長并不能做到和標簽數相等，導致吞吐率較低。

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

2 優化算法的提出

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

2.1 穩定Q值算法

    由上文分析可知，當標簽數量比較多時，Q值會從初始值增加到某一個值，然后在這一個值左右反復跳變。可以設計穩定Q值算法，記錄Q值的變化過程，一旦檢測到Q值不是依次遞增或遞減，而是反復跳變，則固定下Q值，讓讀寫器不再反復發送QuerryAdjust，導致所有待識別標簽都反復生成隨機數。將Q值固定后的狀態定義為Q值穩定狀態。具體算法流程如圖3所示。

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

    由式(2)可以仿真得到總的標簽數量n與達到穩定狀態后的Q值，以及達到穩定狀態后，碰撞時隙中平均包含的標簽數量N_c的對應關系，結果如表1所示。

    由表1可以得出結論，當Q值穩定后，標簽的分布比較分散，每一個碰撞時隙的標簽數量是少量的，在2~6的范圍內。

2.2 碰撞時隙再處理算法

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

    證明過程如下：

    設幀長為L，標簽數為n。某個時隙僅被一個標簽選擇的概率為P_s，則：

    該函數圖像如圖4所示。可以觀察到，當標簽數量小于40時，吞吐率明顯高于36.8%，并且隨著標簽的減少，吞吐率有大幅度的提高。而這個特點被很多研究EPC Gen2防碰撞算法優化的學者忽視，并沒有充分利用，導致提出的優化方案總是想辦法讓吞吐率接近36.8%，而始終無法超過這個理論瓶頸。

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

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

3 仿真結果與分析

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

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

    圖8的結果表明，InnerQ算法的碰撞時隙個數明顯小于優化之前的算法。因為優化算法使得碰撞時隙內的標簽數目比較少，這樣再次處理時，發生碰撞的機率就比較小，碰撞時隙數自然就會減少。

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

4 結論

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

參考文獻

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

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

[3] 吳淼，劉德盟，張釗鋒.基于EPC Gen2防碰撞機制的研究與優化[J].微電子學與計算機，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.中國科學院上海高等研究院，上海201210；2.中國科學院大學，北京100190）