無(wú)線(xiàn)射頻識(shí)別技術(shù)( RFID) 是一種非接觸的自動(dòng)識(shí)別技術(shù), 因其具有識(shí)別距離遠(yuǎn)、穿透能力強(qiáng)、多物體識(shí)別、抗污染等優(yōu)點(diǎn), 現(xiàn)已廣泛應(yīng)用于工業(yè)自動(dòng)化、商業(yè)自動(dòng)化、交通運(yùn)輸控制管理、產(chǎn)品證件防偽、防盜等眾多領(lǐng)域, 成為當(dāng)前IT 業(yè)研究的熱點(diǎn)技術(shù)之一。

　　RFID 系統(tǒng)一般由標(biāo)簽(Tag)和讀寫(xiě)器(Reader)兩個(gè)部分組成。在系統(tǒng)工作時(shí), 當(dāng)有多個(gè)標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)時(shí)就會(huì)出現(xiàn)碰撞, 其結(jié)果會(huì)導(dǎo)致傳輸失敗。因此需制定適當(dāng)?shù)姆琅鲎菜惴? 避免或減少碰撞, 從而有效地提高系統(tǒng)性能。一般防碰撞算法可以分為隨機(jī)型和決定型。本文主要研究隨機(jī)防碰撞算法中常見(jiàn)的兩類(lèi)算法: 幀時(shí)隙ALOHA 算法及其改進(jìn)型的、時(shí)隙隨機(jī)算法。

1 幀時(shí)隙ALOHA 算法

　　在RFID 系統(tǒng)中, 幀時(shí)隙ALOHA 算法的“幀”是由讀寫(xiě)器定義的一段時(shí)間長(zhǎng)度, 其中包含若干時(shí)隙。時(shí)隙指標(biāo)簽收到讀寫(xiě)器命令后, 發(fā)送標(biāo)識(shí)的時(shí)間長(zhǎng)度。標(biāo)簽被隨機(jī)分配到一個(gè)時(shí)隙應(yīng)答, 當(dāng)一個(gè)時(shí)隙中分配到多個(gè)標(biāo)簽時(shí)就產(chǎn)生碰撞。根據(jù)幀內(nèi)時(shí)隙數(shù)是否變化分為固定幀時(shí)隙ALOHA 算法和動(dòng)態(tài)幀時(shí)隙ALOHA 算法。

1 .1 固定幀時(shí)隙ALOHA 算法

　　固定幀時(shí)隙ALOHA( FFSA) 算法是最基本的一種算法, 每幀時(shí)隙數(shù)的大小都一樣。識(shí)別過(guò)程開(kāi)始時(shí), 由讀寫(xiě)器向識(shí)別場(chǎng)內(nèi)所有標(biāo)簽發(fā)送一個(gè)包含時(shí)隙數(shù)L 的命令。這些標(biāo)簽收到命令后, 將其時(shí)隙計(jì)數(shù)器復(fù)位為1, 開(kāi)始記錄時(shí)隙數(shù), 同時(shí)從1~L 中選擇一個(gè)數(shù)做為其時(shí)隙數(shù)值。當(dāng)時(shí)隙計(jì)數(shù)器值與標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)值相同時(shí), 標(biāo)簽向讀寫(xiě)器發(fā)出應(yīng)答信息。若標(biāo)簽被讀寫(xiě)器成功識(shí)別, 則退出識(shí)別系統(tǒng)。一個(gè)幀完成后, 讀寫(xiě)器開(kāi)始時(shí)隙數(shù)同樣為L(zhǎng) 的新幀。

　　FFSA 算法設(shè)計(jì)簡(jiǎn)單, 但缺點(diǎn)是如果標(biāo)簽數(shù)遠(yuǎn)遠(yuǎn)多于固定的時(shí)隙數(shù), 會(huì)產(chǎn)生過(guò)多碰撞; 反之, 會(huì)產(chǎn)生較多空閑時(shí)隙, 造成資源浪費(fèi)。只有在標(biāo)簽數(shù)與時(shí)隙數(shù)差不多的一段時(shí)間內(nèi), 系統(tǒng)吞吐率最大。可見(jiàn), 由于FFSA 算法的時(shí)隙數(shù)不能隨著標(biāo)簽數(shù)而變化, 系統(tǒng)無(wú)法獲得穩(wěn)定的吞吐率。為改善這一缺點(diǎn), 提出一種改進(jìn)算法——— 動(dòng)態(tài)幀時(shí)隙ALOHA 算法。

1 .2 動(dòng)態(tài)幀時(shí)隙ALOHA 算法
　　動(dòng)態(tài)幀時(shí)隙ALOHA( DFSA) 算法是每幀時(shí)隙數(shù)都會(huì)根據(jù)標(biāo)簽數(shù)的不同而變化。為獲得系統(tǒng)最大吞吐率,DFSA 算法需要在識(shí)別過(guò)程中估算標(biāo)簽數(shù), 用以確定匹配時(shí)隙數(shù)。在標(biāo)簽總數(shù)未知的情況下, 當(dāng)初始時(shí)隙數(shù)L<16 時(shí), 第一次讀取過(guò)程通常不能識(shí)別出標(biāo)簽。因此為節(jié)約初始時(shí)間, 設(shè)置初始時(shí)隙數(shù)Linit=16[1]。標(biāo)簽估算的方法有很多種[2- 4] , 例如:

　　(1)估算出參與識(shí)別的標(biāo)簽總數(shù)。設(shè)時(shí)隙數(shù)為L(zhǎng), 標(biāo)簽數(shù)為n, 則一個(gè)幀中碰撞時(shí)隙率Cratio=1- (1- 1L)n (1+nL- 1)[2]。在讀寫(xiě)器識(shí)別過(guò)程中, 已知當(dāng)前幀時(shí)隙數(shù)為L(zhǎng), 并且可以統(tǒng)計(jì)出該幀時(shí)隙碰撞率Cratio, 采用逼近算法, 可以估算出n。

　　( 2) 直接估算出未識(shí)別的標(biāo)簽數(shù)。當(dāng)系統(tǒng)達(dá)到最大吞吐率時(shí), 一個(gè)時(shí)隙的碰撞率Ctags=0.418 0[2], 因此一個(gè)時(shí)
隙碰撞的標(biāo)簽數(shù)Ctags= 1　Crate=2.392 2[2]。讀寫(xiě)器在識(shí)別過(guò)程中, 統(tǒng)計(jì)前一個(gè)幀的時(shí)隙碰撞數(shù)Ncoll , 則未識(shí)別標(biāo)簽數(shù)nest=2.392 2×Ncoll。得到未識(shí)別標(biāo)簽估計(jì)數(shù)nest 后, 從理論上講最優(yōu)的時(shí)隙數(shù)L 應(yīng)該等于nest[2] , 但在實(shí)際應(yīng)用中, 讀寫(xiě)器能夠設(shè)定的時(shí)隙數(shù)是定值, 通常為1, 8, 16, 32, 64, 128, 256。

　　因此, 讀寫(xiě)器需要根據(jù)nest 從以上幾個(gè)數(shù)中選擇一個(gè)數(shù)作為下一幀的時(shí)隙數(shù)。對(duì)250 個(gè)以?xún)?nèi)不同數(shù)目的標(biāo)簽,選擇不同時(shí)隙數(shù), 計(jì)算一個(gè)幀的吞吐率。對(duì)不同標(biāo)簽數(shù)選擇吞吐率最大所對(duì)應(yīng)的時(shí)隙數(shù)如圖1 所示, 得到標(biāo)簽數(shù)與匹配時(shí)隙數(shù)的對(duì)應(yīng)關(guān)系如表1 所示。樣就可以在估算出未識(shí)別標(biāo)簽數(shù)之后, 在下一幀中選擇匹配的時(shí)隙數(shù), 從而提高系統(tǒng)吞吐率。

1 .3 帶延遲的幀時(shí)隙ALOHA 算法

　　幀時(shí)隙ALOHA 算法中, 若幀時(shí)隙數(shù)遠(yuǎn)遠(yuǎn)小于標(biāo)簽數(shù), 在匹配前系統(tǒng)吞吐率很低。為了在時(shí)隙數(shù)與標(biāo)簽數(shù)匹配前, 提高當(dāng)前幀的吞吐率, 引入了延遲機(jī)制, 即當(dāng)標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)與時(shí)隙計(jì)數(shù)器數(shù)值相同時(shí), 標(biāo)簽并不立即應(yīng)答讀寫(xiě)器, 而是延遲若干時(shí)隙( 從0~7 的范圍內(nèi)選擇) 后再發(fā)出應(yīng)答信息[5]。

表1 時(shí)隙數(shù)與標(biāo)簽數(shù)的對(duì)應(yīng)關(guān)系

L	nest
1	0~1
8	2~11
16	12~22
32	23~45
64	46~89
128	90~176
256	>176

　　圖2 是設(shè)定初始時(shí)隙為16, 對(duì)比不同標(biāo)簽數(shù)( 標(biāo)簽數(shù)大于16) 下第一個(gè)幀的吞吐率。由圖2 看出, 帶延遲的算法的確可以提高一幀的吞吐率, 然而延遲算法只有在標(biāo)簽數(shù)多而時(shí)隙數(shù)少的情況下才有利于提高系統(tǒng)吞吐率。在相反的情況下, 延遲算法在減少碰撞時(shí)隙的同時(shí), 產(chǎn)生過(guò)多的空閑時(shí)隙, 不能提高系統(tǒng)的吞吐率。


1 .4 分組幀時(shí)隙ALOHA 算法

　　幀時(shí)隙ALOHA 算法局限于每幀最大時(shí)隙數(shù)為256。當(dāng)標(biāo)簽數(shù)遠(yuǎn)遠(yuǎn)大于256 時(shí), 系統(tǒng)無(wú)法通過(guò)增大時(shí)隙數(shù)來(lái)提高吞吐率。為解決這個(gè)問(wèn)題, 在DFSA 算法的基礎(chǔ)上提出分組幀時(shí)隙ALOHA 算法( GFSA) 。參考文獻(xiàn)[3]中說(shuō)明, 當(dāng)標(biāo)簽數(shù)多于354 時(shí)將全部標(biāo)簽分成兩組或者更多組, 讀寫(xiě)器分別對(duì)每組標(biāo)簽進(jìn)行識(shí)別, 從而可以很好地提高系統(tǒng)的吞吐率。圖3 為普通DFSA 算法與分組GFSA 算法在標(biāo)簽數(shù)多于400 時(shí)識(shí)別所用的總時(shí)隙數(shù)的比較, 初始時(shí)隙設(shè)為256。圖3 的結(jié)果表明, 標(biāo)簽數(shù)越多, 分組算法GFSA 的優(yōu)越性越明顯。但是這種算法需要在原有的DFSA 算法上做很多修改, 例如讀寫(xiě)器命令需要加入分組參數(shù), 標(biāo)簽需要確定并保存自己的分組序號(hào), 這使得實(shí)現(xiàn)變得有些困難。

2 時(shí)隙隨機(jī)算法( SR)
　　時(shí)隙隨機(jī)算法沒(méi)有幀的概念, 取而代之的是識(shí)別周期。識(shí)別周期是指讀寫(xiě)器兩次發(fā)送開(kāi)始識(shí)別命令( Query) 的時(shí)間間隔。SR 算法同樣是令標(biāo)簽選擇時(shí)隙應(yīng)答, 但區(qū)別在于, 幀時(shí)隙ALOHA 算法在一個(gè)幀所有時(shí)隙完成之后才能更改時(shí)隙數(shù), 使未識(shí)別標(biāo)簽重新選擇時(shí)隙; 而SR 算法在一個(gè)識(shí)別周期內(nèi)可以隨時(shí)更改時(shí)隙數(shù),讓未識(shí)別標(biāo)簽重新選擇, 實(shí)現(xiàn)了時(shí)隙數(shù)的自適應(yīng)過(guò)程。以ISO/IEC 18000 - 6 Type C[5] 為例, 識(shí)別過(guò)程由讀寫(xiě)器發(fā)送Query 命令開(kāi)始, 命令包含時(shí)隙參數(shù)Q。標(biāo)簽從0~2Q- 1 范圍內(nèi)隨機(jī)選擇一個(gè)數(shù)作為自己的槽計(jì)數(shù)器值。當(dāng)槽計(jì)數(shù)器值等于0 時(shí), 標(biāo)簽應(yīng)答。若標(biāo)簽被讀寫(xiě)器成功識(shí)別, 則退出識(shí)別系統(tǒng)。
讀寫(xiě)器通過(guò)發(fā)送開(kāi)始下一個(gè)時(shí)隙的命令( QueryRep) , 令標(biāo)簽的槽計(jì)數(shù)器值減1, 若槽計(jì)數(shù)器值為0(前一個(gè)時(shí)隙碰撞的標(biāo)簽), 則將其記為最大值(7FFFh)。當(dāng)讀寫(xiě)器認(rèn)為需要更改時(shí)隙數(shù)時(shí), 發(fā)送更改時(shí)隙參數(shù)的命令(QueryAdjust), 令原有Q 值加1 或減1, 這時(shí)標(biāo)簽會(huì)重新產(chǎn)生槽計(jì)數(shù)器值。時(shí)隙數(shù)的自適應(yīng)過(guò)程是通過(guò)發(fā)送QueryAdjust 命令實(shí)現(xiàn)的。讀寫(xiě)器根據(jù)幾個(gè)時(shí)隙的識(shí)別情況( 而非一個(gè)周期) , 增加或減少時(shí)隙參數(shù)Q, 使之能夠及時(shí)有效地反映標(biāo)簽數(shù)的動(dòng)態(tài)變化。一種簡(jiǎn)單的Q 值算法是在讀寫(xiě)器中設(shè)計(jì)一個(gè)參數(shù)Qfp 作為Q 的浮點(diǎn)數(shù)。每次讀寫(xiě)器都根據(jù)標(biāo)簽的應(yīng)答情況更改Qfp 值, 然后將Qfp 四舍五入為一個(gè)整數(shù)值。若這個(gè)整數(shù)不同于之前的Q 值, 則讀寫(xiě)器發(fā)送QueryAdjust 命令, 令Q 等于這個(gè)整數(shù); 否則讀寫(xiě)器不
改變Q 值, 發(fā)送QueryRep 命令。其過(guò)程如圖4 所示。其中C 為Qfp 的變化步長(zhǎng)。一般來(lái)說(shuō), Q 與C 成反比, 因此
可以取C=0.8/Q [6]。初始時(shí)隙數(shù)與DFSA 算法相同, 取16, 即Q=4。

3 仿真分析

　　圖5、圖6 分別描述了識(shí)別一定數(shù)目的標(biāo)簽所需要的總時(shí)隙數(shù)和系統(tǒng)吞吐率。圖中, FFSA 128 和FFSA 256分別代表采用128 和256 時(shí)隙數(shù)的固定幀時(shí)隙ALOHA算法; DFSA I 和DFSA II 分別代表采用1.2 節(jié)第一種標(biāo)簽估計(jì)算法和第二種標(biāo)簽估計(jì)算法的動(dòng)態(tài)幀時(shí)隙ALOHA 算法; SR 算法代表時(shí)隙隨機(jī)算法, 其Q 值算法采用第2 節(jié)所述方法。

　　從圖5、圖6 中可以看出, 若采用時(shí)隙數(shù)為128 的FFSA 算法, 當(dāng)標(biāo)簽數(shù)超過(guò)300 時(shí), 識(shí)別標(biāo)簽所需的時(shí)隙總數(shù)迅速增長(zhǎng)。同樣采用時(shí)隙數(shù)為256 的FFSA 算法, 時(shí)隙總數(shù)也呈現(xiàn)迅速增長(zhǎng)的趨勢(shì)。FFSA 算法的系統(tǒng)吞吐率較低而且吞吐性能不穩(wěn)定。若采用DFSA 算法, 識(shí)別標(biāo)簽所需的時(shí)隙總數(shù)略有下降。當(dāng)標(biāo)簽數(shù)少于600 時(shí), 系統(tǒng)吞吐率較高而且相對(duì)穩(wěn)定; 當(dāng)標(biāo)簽數(shù)大于600 時(shí), 由于受到最大時(shí)隙數(shù)256的限制, 系統(tǒng)吞吐率開(kāi)始下降。此時(shí)可以通過(guò)GFSA 算法提高系統(tǒng)吞吐率。仿真中采用兩種不同估算標(biāo)簽算法的DFSA 算法, 其性能差不多。但從實(shí)現(xiàn)角度講, DFSA II算法更好一些, 因?yàn)樗菀讓?shí)現(xiàn)。
SR 算法作為另外一類(lèi)基于時(shí)隙的防碰撞算法, 其性能遠(yuǎn)遠(yuǎn)優(yōu)于前面幾種算法。SR 算法采用時(shí)隙數(shù)自適應(yīng)機(jī)制, 不僅減少碰撞時(shí)隙和空閑時(shí)隙產(chǎn)生, 而且使碰撞標(biāo)簽可以及時(shí)重新參與識(shí)別。SR 算法的最大時(shí)隙數(shù)可達(dá)215 , 在實(shí)際應(yīng)用中, 即便識(shí)別很大數(shù)量的標(biāo)簽時(shí),也不會(huì)受到時(shí)隙數(shù)的限制。采用SR 算法系統(tǒng)吞吐率最高且保持在一個(gè)定值左右。特別在識(shí)別很大數(shù)量的標(biāo)簽時(shí), SR 算法識(shí)別標(biāo)簽所用的總時(shí)隙數(shù)比DFSA 算法減少很多。

　　總之, 在RFID 系統(tǒng)中, 基于時(shí)隙的防碰撞算法關(guān)心的首要問(wèn)題都是使時(shí)隙數(shù)與標(biāo)簽數(shù)相匹配, 這樣才能提高系統(tǒng)吞吐率。對(duì)于文中分析的兩類(lèi)算法, 幀時(shí)隙ALOHA 算法設(shè)計(jì)簡(jiǎn)單, 適合于識(shí)別數(shù)量在600 個(gè)以?xún)?nèi)的標(biāo)簽; 時(shí)隙隨機(jī)算法相對(duì)復(fù)雜一些, 但系統(tǒng)吞吐率高而且性能穩(wěn)定, 特別適合識(shí)別很大數(shù)量的標(biāo)簽。

參考文獻(xiàn)
[1] 吳晶, 熊璋, 王曄. 利用動(dòng)態(tài)時(shí)間槽分配的多目標(biāo)防沖突射頻識(shí)別. 北京航空航天大學(xué)學(xué)報(bào), 2005 , 31(6).
[2] CHA J R, KIM J H. Novel anti- collision algorithms forfast object identification in RFID System. The 11th InternationalConference on Parallel and Distributed Systems,2005.
[3] LEE S R, JOO S D, LEE C W. An enhanced dynamicframed slotted ALOHA algorithm for RFID tag identification.The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2005.
[4] VOGT H. Multiple object identification with passive RFID tags. Department of Computer Science Swiss Federal Institute of Technology.2002.
[5] ISO/IEC 18000- 6.
[6] CHRISTIAN F, MATTHIAS W. Comparison of transmission schemes for framed ALOHA based RFID protocols.
The International Symposium on Applications and the Internet Workshops, 2005.