《電子技術(shù)應用》
您所在的位置:首頁 > 通信與網(wǎng)絡 > 設計應用 > 多標簽快速識別算法研究與改進
多標簽快速識別算法研究與改進
來源:電子技術(shù)應用2012年第1期
顏 元1,2, 武岳山1,2
1. 西北大學 信息科學與技術(shù)學院, 陜西 西安 710127; 2. 深圳市遠望谷信息技術(shù)股份有限公司,廣東 深圳 518057
摘要: 為了提高Aloha算法中標簽的識別效率,根據(jù)ISO/IEC18000-6C國際標準中的防碰撞要求,對時隙計數(shù)(Q)的選擇進行動態(tài)調(diào)整,以滿足標簽快速識別的要求,實現(xiàn)了一種動態(tài)的時隙Aloha算法。除此以外,在此基礎上提出了對標簽數(shù)量進行分組,分析了滿足最大時隙利用率的客觀條件,對動態(tài)時隙Aloha算法進行改進。仿真結(jié)果顯示,改進后的算法提高了標簽的識別效率,表現(xiàn)出良好的性能,具有一定的研究價值。
中圖分類號: TP301
文獻標識碼: B
文章編號: 0258-7998(2012)01-0081-04
Research and improvement of multi-tag rapid recognition algorithm
Yan Yuan1,2, Wu Yueshan1,2
1. School of Information Science & Technology, Northwest University, Xi’an, 710127, China 2. Invengo Information Technology Co., Ltd, Shenzhen 518057, China
Abstract: In this paper, according to the prevent collision requirements in ISO/IEC18000-6C international standard, in order to achieve the requirements of tag′s rapid identification, we dynamically adjust the number(Q) of time slot, which is a dynamic time solt Aloha algorithm. In addition, we divide tags into groups base on this algorithm, analyze the objective conditions, which is content with the utilization ratio of the maximum time solt, and improve the dynamic time solt Aloha algorithm. The simulation result indicates that the improved algorithm enhances the recognition efficiency of the tags, it has a good performance and certain value for studying.
Key words : RFID; slot utilization; anti-collision; poisson distribution

    射頻識別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)境等眾多因素有關,但理論識別時間可以通過時隙總數(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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。