文獻(xiàn)標(biāo)識(shí)碼: B
文章編號(hào): 0258-7998(2012)01-0081-04
射頻識(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à)值。
參考文獻(xiàn)
[1] ISO/IEC.18000-6C-2004-FDAM 1:2006(E)[S].
[2] 胡乃英.UHF頻段RFID空中接口協(xié)議的研究[D].西安:西北大學(xué),,2008.
[3] 徐凌云. EPC C1G2防碰撞算法仿真研究[J].通信技術(shù),2010,,43(05):53-55.
[4] [德]FINKENZELLER K.射頻識(shí)別(RFID)技術(shù)[M].北京:電子工業(yè)出版社,,2006.
[5] 劉會(huì)燈,朱飛. MATLAB編程基礎(chǔ)與典型應(yīng)用[M].北京:人民郵電出版社,,2008.