多標(biāo)簽快速識(shí)別算法研究與改進(jìn)

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

　　本文中所研究的多標(biāo)簽快速識(shí)別算法，是以RFID空中接口協(xié)議ISO/IEC18000-6C的防碰撞要求為基礎(chǔ)，利用隨機(jī)時(shí)隙算法解決多標(biāo)簽識(shí)別的碰撞問題。本文在研究多標(biāo)簽快速識(shí)別算法的同時(shí)，結(jié)合理論研究，提出了一種改進(jìn)的基于分組的多標(biāo)簽快速識(shí)別算法。仿真結(jié)果顯示，改進(jìn)后的算法提高了標(biāo)簽的識(shí)別效率，并縮短了識(shí)別過程中程序的運(yùn)行時(shí)間。

　　1 多標(biāo)簽快速識(shí)別算法研究

　　1.1 ISO/IEC18000-6C識(shí)別標(biāo)簽過程

　　ISO/IEC18000-6C規(guī)定，閱讀器通過Query命令將其產(chǎn)生的隨機(jī)數(shù)Q發(fā)給每個(gè)標(biāo)簽，標(biāo)簽選擇一個(gè)0~2Q-1范圍內(nèi)的隨機(jī)數(shù)裝入其時(shí)隙計(jì)數(shù)器。選到零值的標(biāo)簽應(yīng)轉(zhuǎn)移到應(yīng)答(reply)狀態(tài)，并立即應(yīng)答。選到非零數(shù)的標(biāo)簽應(yīng)轉(zhuǎn)移到仲裁(arbitrate)狀態(tài)，并等待閱讀器命令來對(duì)它們的時(shí)隙計(jì)數(shù)器中的值進(jìn)行減1操作，當(dāng)標(biāo)簽的時(shí)隙計(jì)數(shù)值減為0時(shí)應(yīng)答。ISO/IEC18000-6C的附錄D描述了選擇Q值的算法，如圖1所示。

　　由圖1看出，閱讀器根據(jù)相應(yīng)的標(biāo)簽數(shù)為0、1還是大于1去調(diào)整Q值，大于1時(shí)為發(fā)生碰撞的情況。在碰撞的情況下，根據(jù)Qfp=min(15，Qfp+C)和Q=round(Qfp)調(diào)整下一輪的Q值。Q值的調(diào)整參數(shù)C往往根據(jù)經(jīng)驗(yàn)選擇，其中x為標(biāo)簽數(shù)。

　　1.2 多標(biāo)簽快速識(shí)別算法數(shù)學(xué)模型

　　在一個(gè)輪詢周期中，每個(gè)時(shí)隙內(nèi)的標(biāo)簽響應(yīng)有三種情況：沒有標(biāo)簽響應(yīng)(空時(shí)隙);有一個(gè)標(biāo)簽響應(yīng)(沒有碰撞的時(shí)隙);有一個(gè)以上的標(biāo)簽響應(yīng)(碰撞時(shí)隙)。設(shè)標(biāo)簽數(shù)量為x，閱讀器通過Query命令來產(chǎn)生隨機(jī)數(shù)Q所給出的時(shí)隙數(shù)為A=2Q。對(duì)于每個(gè)時(shí)隙而言，某個(gè)標(biāo)簽在其中響應(yīng)的概率為A-1，該標(biāo)簽不在其中響應(yīng)的概率為(1-A-1)。共有x個(gè)標(biāo)簽，可以看成對(duì)每個(gè)時(shí)隙進(jìn)行x次試驗(yàn)，上述情況符合二項(xiàng)分布B(x,A-1)。在多標(biāo)簽識(shí)別過程中，標(biāo)簽數(shù)比較多。因此，x很大而A-1很小，此時(shí)，二項(xiàng)分布近似為泊松分布。泊松分布參數(shù)：

　　根據(jù)最大時(shí)隙利用率，總結(jié)出多標(biāo)簽識(shí)別算法的流程圖如圖2所示。

　　從圖2可以看到，當(dāng)時(shí)隙利用率P1近似于0.367 9時(shí)，在后續(xù)的循環(huán)中只需要調(diào)整時(shí)隙數(shù)A即可，否則比較空時(shí)隙率P0與0.367 9大小，并對(duì)Q值作出調(diào)整，Q的調(diào)整參數(shù)C的取值應(yīng)根據(jù)實(shí)際情況而定，往往靠經(jīng)驗(yàn)選取，本文取值為0.8。

　　2 基于分組的多標(biāo)簽快速識(shí)別改進(jìn)算法設(shè)計(jì)與分析

　　首先介紹一下此算法涉及到的標(biāo)簽的幾個(gè)工作狀態(tài)。準(zhǔn)備態(tài)(READY)：處于閱讀器的詢問區(qū)域中的標(biāo)簽，而且標(biāo)簽接收到足夠支持標(biāo)簽工作的能量。

　　待命態(tài)(STANDBY)：閱讀器對(duì)所有處于其詢問區(qū)域中的準(zhǔn)備態(tài)的標(biāo)簽進(jìn)行初始化后，選出一組標(biāo)簽來進(jìn)行組內(nèi)識(shí)別算法。

　　靜默態(tài)(QUIET)：標(biāo)簽被閱讀器正確讀取后，不參與隨后的識(shí)別過程的狀態(tài)。

　　2.1 基于分組的多標(biāo)簽快速識(shí)別算法分析

　　2.1.1 標(biāo)簽的分組

　　在這個(gè)改進(jìn)算法中，為了對(duì)標(biāo)簽執(zhí)行分組操作，閱讀器在發(fā)送命令中設(shè)定分組參數(shù)Q，作用域內(nèi)的標(biāo)簽一旦接收到詢問命令，就會(huì)隨機(jī)產(chǎn)生一個(gè)介于0~2Q-1的隨機(jī)數(shù)(包括0與2Q-1)，這樣將所有處于“準(zhǔn)備”狀態(tài)的標(biāo)簽分成2Q組。例如，假設(shè)Q=2，第一組標(biāo)簽的組號(hào)為00，第二組標(biāo)簽組號(hào)為01，依次類推。閱讀器選定所有屬于第一組的標(biāo)簽，使它們處于“待命”態(tài)，閱讀器再根據(jù)組內(nèi)識(shí)別算法對(duì)處于“待命”狀態(tài)的標(biāo)簽進(jìn)行識(shí)別。

　　在實(shí)際應(yīng)用中，設(shè)定Q的值最大值為15(即可以分為32 768組，完全滿足實(shí)際需求)，閱讀器根據(jù)特殊序列發(fā)生碰撞的情況來適當(dāng)調(diào)整分組Q值，當(dāng)空閑時(shí)隙數(shù)過多時(shí)Q-1，當(dāng)碰撞時(shí)隙數(shù)過多時(shí)Q-1。

　　2.1.2 組內(nèi)識(shí)別算法改進(jìn)

　　根據(jù)1.1節(jié)的數(shù)學(xué)原理分析，當(dāng)標(biāo)簽數(shù)目與時(shí)隙數(shù)目大約相等時(shí)，時(shí)隙利用率最大，那么在分組比特時(shí)隙算法中,在每次分組之后對(duì)分組標(biāo)簽數(shù)目進(jìn)行統(tǒng)計(jì)，并分配與之相等的比特時(shí)隙,算法就可以達(dá)到最好的性能。

　　2.2 基于分組多標(biāo)簽快速識(shí)別算法流程

　　根據(jù)以上分析本文提出的算法步驟如下：

　　(1)閱讀器發(fā)送詢問命令，開始一個(gè)讀取周期。

　　(2)閱讀器作用域內(nèi)的標(biāo)簽隨機(jī)選擇一個(gè)介于[0, 2Q-1]隨機(jī)數(shù)，只有產(chǎn)生隨機(jī)數(shù)為0的標(biāo)簽應(yīng)答。統(tǒng)計(jì)產(chǎn)生隨機(jī)數(shù)為0的標(biāo)簽的個(gè)數(shù)，并分配與之相等的時(shí)隙數(shù)目，標(biāo)簽隨機(jī)選擇不同的時(shí)隙數(shù)，生成特殊比特序列并發(fā)送給閱讀器。

　　(3)閱讀器檢測(cè)接收到特殊序列，計(jì)算時(shí)隙利用率P1，空時(shí)隙率P0。

　　(4)根據(jù)表1調(diào)節(jié)Q值，進(jìn)而調(diào)整標(biāo)簽的分組數(shù)。

　　(5)重復(fù)以上過程，直到所有標(biāo)簽都被讀取完畢。

　　基于分組的多標(biāo)簽快速識(shí)別算法流程圖如圖3所示。

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

　　衡量算法，要看同樣數(shù)量標(biāo)簽的識(shí)別時(shí)間，它與所需的時(shí)隙總數(shù)、時(shí)隙利用率、閱讀器的軟硬件設(shè)備、標(biāo)簽與閱讀器的實(shí)際距離、實(shí)際工作的電磁環(huán)境等眾多因素有關(guān)，但理論識(shí)別時(shí)間可以通過時(shí)隙總數(shù)、時(shí)隙利用率加以衡量。除此以外，算法程序本身運(yùn)行時(shí)間在一定程度上也能反映理論識(shí)別時(shí)間。在給出改進(jìn)算法的仿真結(jié)果之前，先介紹3個(gè)衡量算法性能的參數(shù)。

　　(1)時(shí)隙數(shù)：閱讀器識(shí)別其詢問區(qū)域內(nèi)所有標(biāo)簽所花費(fèi)的總時(shí)隙數(shù)。時(shí)隙數(shù)的值越小，反應(yīng)的識(shí)別速度越快。

　　(2)吞吐率(Througput)：定義為識(shí)別時(shí)隙數(shù)目與總時(shí)隙數(shù)目之比，即時(shí)隙利用率。

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

　　由此看來，改進(jìn)后的算法在時(shí)隙數(shù)量、吞吐率、運(yùn)行時(shí)間三個(gè)方面都比原算法具有更好的防碰撞性能的表現(xiàn)。這為實(shí)際生活中標(biāo)簽識(shí)別的防碰撞問題的研究提供了更加優(yōu)越的方法。

　　本文對(duì)基于ISO/IEC18000-6C協(xié)議的多標(biāo)簽快速識(shí)別防碰撞算法進(jìn)行了分析和仿真，并提出了一種改進(jìn)的基于分組的多標(biāo)簽快速識(shí)別算法。在改進(jìn)的算法中，將待識(shí)別的標(biāo)簽首先分成若干組，再根據(jù)組內(nèi)的時(shí)隙數(shù)依次識(shí)別。用Matlab軟件對(duì)這兩種算法進(jìn)行了仿真對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，在相同的標(biāo)簽總數(shù)的情況下，改進(jìn)之后的算法所需的總時(shí)隙數(shù)比原算法的少，并且提高了標(biāo)簽的識(shí)別效率。除此之外改進(jìn)的算法還縮短了標(biāo)簽識(shí)別的時(shí)間。這對(duì)于RFID系統(tǒng)中標(biāo)簽的防碰撞問題研究具有一定的參考價(jià)值。