射頻識別RFID（Radio Frequency Identification）是一種非接觸自動識別技術。RFID系統主要由閱讀器和標簽構成，閱讀器通過天線信道按照一定的協議讀寫標簽。由于在一個閱讀器的識別范圍內可能存在多個標簽，為了正確識別這些標簽，RFID系統的防碰撞算法主要包括兩類，一類是基于時隙的Aloha算法；另一類是基于二進制樹形搜索的確定性算法。

    本文中所研究的多標簽快速識別算法，是以RFID空中接口協議ISO/IEC18000-6C的防碰撞要求為基礎，利用隨機時隙算法解決多標簽識別的碰撞問題。本文在研究多標簽快速識別算法的同時，結合理論研究，提出了一種改進的基于分組的多標簽快速識別算法。仿真結果顯示，改進后的算法提高了標簽的識別效率，并縮短了識別過程中程序的運行時間。
1 多標簽快速識別算法研究
1.1 ISO/IEC18000-6C識別標簽過程
　    ISO/IEC18000-6C規定，閱讀器通過Query命令將其產生的隨機數Q發給每個標簽，標簽選擇一個0~2Q-1范圍內的隨機數裝入其時隙計數器。選到零值的標簽應轉移到應答(reply)狀態，并立即應答。選到非零數的標簽應轉移到仲裁(arbitrate)狀態，并等待閱讀器命令來對它們的時隙計數器中的值進行減1操作，當標簽的時隙計數值減為0時應答。ISO/IEC18000-6C的附錄D描述了選擇Q值的算法，如圖1所示。

    由圖1看出，閱讀器根據相應的標簽數為0、1還是大于1去調整Q值，大于1時為發生碰撞的情況。在碰撞的情況下，根據Qfp=min(15，Qfp+C)和Q=round(Qfp)調整下一輪的Q值。Q值的調整參數C往往根據經驗選擇，其中x為標簽數。
1.2 多標簽快速識別算法數學模型
    在一個輪詢周期中，每個時隙內的標簽響應有三種情況：沒有標簽響應（空時隙）；有一個標簽響應（沒有碰撞的時隙）；有一個以上的標簽響應（碰撞時隙）。設標簽數量為x，閱讀器通過Query命令來產生隨機數Q所給出的時隙數為A=2Q。對于每個時隙而言，某個標簽在其中響應的概率為A-1，該標簽不在其中響應的概率為(1-A-1)。共有x個標簽，可以看成對每個時隙進行x次試驗，上述情況符合二項分布B(x,A-1)。在多標簽識別過程中，標簽數比較多。因此，x很大而A-1很小，此時，二項分布近似為泊松分布。泊松分布參數：
 
    根據最大時隙利用率，總結出多標簽識別算法的流程圖如圖2所示。

    從圖2可以看到，當時隙利用率P1近似于0.367 9時，在后續的循環中只需要調整時隙數A即可，否則比較空時隙率P0與0.367 9大小，并對Q值作出調整，Q的調整參數C的取值應根據實際情況而定，往往靠經驗選取，本文取值為0.8。
2 基于分組的多標簽快速識別改進算法設計與分析
    首先介紹一下此算法涉及到的標簽的幾個工作狀態。準備態(READY)：處于閱讀器的詢問區域中的標簽，而且標簽接收到足夠支持標簽工作的能量。
    待命態(STANDBY)：閱讀器對所有處于其詢問區域中的準備態的標簽進行初始化后，選出一組標簽來進行組內識別算法。
    靜默態(QUIET)：標簽被閱讀器正確讀取后，不參與隨后的識別過程的狀態。
2.1 基于分組的多標簽快速識別算法分析
2.1.1 標簽的分組
    在這個改進算法中，為了對標簽執行分組操作，閱讀器在發送命令中設定分組參數Q，作用域內的標簽一旦接收到詢問命令，就會隨機產生一個介于0~2Q-1的隨機數(包括0與2Q-1)，這樣將所有處于“準備”狀態的標簽分成2Q組。例如，假設Q=2，第一組標簽的組號為00，第二組標簽組號為01，依次類推。閱讀器選定所有屬于第一組的標簽，使它們處于“待命”態，閱讀器再根據組內識別算法對處于“待命”狀態的標簽進行識別。
    在實際應用中，設定Q的值最大值為15（即可以分為32 768組，完全滿足實際需求），閱讀器根據特殊序列發生碰撞的情況來適當調整分組Q值，當空閑時隙數過多時Q-1，當碰撞時隙數過多時Q-1。
2.1.2 組內識別算法改進
    根據1.1節的數學原理分析，當標簽數目與時隙數目大約相等時，時隙利用率最大，那么在分組比特時隙算法中,在每次分組之后對分組標簽數目進行統計，并分配與之相等的比特時隙,算法就可以達到最好的性能。
2.2 基于分組多標簽快速識別算法流程
    根據以上分析本文提出的算法步驟如下：
    (1)閱讀器發送詢問命令，開始一個讀取周期。
    (2)閱讀器作用域內的標簽隨機選擇一個介于[0, 2Q-1]隨機數，只有產生隨機數為0的標簽應答。統計產生隨機數為0的標簽的個數，并分配與之相等的時隙數目，標簽隨機選擇不同的時隙數，生成特殊比特序列并發送給閱讀器。
    (3)閱讀器檢測接收到特殊序列，計算時隙利用率P1，空時隙率P0。
    (4)根據表1調節Q值，進而調整標簽的分組數。
    (5)重復以上過程，直到所有標簽都被讀取完畢。
    基于分組的多標簽快速識別算法流程圖如圖3所示。

3 算法仿真與結果分析
    衡量算法，要看同樣數量標簽的識別時間，它與所需的時隙總數、時隙利用率、閱讀器的軟硬件設備、標簽與閱讀器的實際距離、實際工作的電磁環境等眾多因素有關，但理論識別時間可以通過時隙總數、時隙利用率加以衡量。除此以外，算法程序本身運行時間在一定程度上也能反映理論識別時間。在給出改進算法的仿真結果之前，先介紹3個衡量算法性能的參數。
    (1)時隙數：閱讀器識別其詢問區域內所有標簽所花費的總時隙數。時隙數的值越小，反應的識別速度越快。
    (2)吞吐率（Througput）：定義為識別時隙數目與總時隙數目之比，即時隙利用率。


    從圖6中可以清楚地看到，從程序的運行時間來看改進后的算法具有絕對的優勢，當標簽數目相同時，改進算法所需的運行時間更短，而且標簽數量越大優勢越明顯，也就是說在相同的時間里改進的算法識別的標簽數量更多。

    由此看來，改進后的算法在時隙數量、吞吐率、運行時間三個方面都比原算法具有更好的防碰撞性能的表現。這為實際生活中標簽識別的防碰撞問題的研究提供了更加優越的方法。
    本文對基于ISO/IEC18000-6C協議的多標簽快速識別防碰撞算法進行了分析和仿真，并提出了一種改進的基于分組的多標簽快速識別算法。在改進的算法中，將待識別的標簽首先分成若干組，再根據組內的時隙數依次識別。用Matlab軟件對這兩種算法進行了仿真對比分析。實驗結果表明，在相同的標簽總數的情況下，改進之后的算法所需的總時隙數比原算法的少，并且提高了標簽的識別效率。除此之外改進的算法還縮短了標簽識別的時間。這對于RFID系統中標簽的防碰撞問題研究具有一定的參考價值。
參考文獻
[1] ISO/IEC.18000-6C-2004-FDAM 1:2006(E)[S].
[2] 胡乃英.UHF頻段RFID空中接口協議的研究[D].西安：西北大學，2008.
[3] 徐凌云. EPC C1G2防碰撞算法仿真研究[J].通信技術，2010，43(05):53-55.
[4] [德]FINKENZELLER K.射頻識別(RFID)技術[M].北京：電子工業出版社，2006.
[5] 劉會燈，朱飛. MATLAB編程基礎與典型應用[M].北京：人民郵電出版社，2008.