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

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

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

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

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


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

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