摘? 要：介紹了幾種常見的基于時(shí)隙" title="時(shí)隙">時(shí)隙的防碰撞算法" title="防碰撞算法">防碰撞算法：幀時(shí)隙ALOHA算法和時(shí)隙隨機(jī)算法,，并通過仿真,比較分析這些算法識(shí)別所用總時(shí)隙和對(duì)系統(tǒng)吞吐性能的影響。
關(guān)鍵詞：RFID? 防碰撞? 時(shí)隙
?
無線射頻識(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)和讀寫器" title="讀寫器">讀寫器(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ù)姆琅鲎菜惴ǎ苊饣驕p少碰撞,，從而有效地提高系統(tǒng)性能,。一般防碰撞算法可以分為隨機(jī)型和決定型。本文主要研究隨機(jī)防碰撞算法中常見的兩類算法：幀時(shí)隙ALOHA算法及其改進(jìn)型的,、時(shí)隙隨機(jī)算法,。
1 幀時(shí)隙ALOHA算法
在RFID系統(tǒng)中,，幀時(shí)隙ALOHA算法的“幀”是由讀寫器定義的一段時(shí)間長(zhǎng)度,，其中包含若干時(shí)隙。時(shí)隙指標(biāo)簽收到讀寫器命令后,，發(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í)別過程開始時(shí),，由讀寫器向識(shí)別場(chǎng)內(nèi)所有標(biāo)簽發(fā)送一個(gè)包含時(shí)隙數(shù)L的命令。這些標(biāo)簽收到命令后,，將其時(shí)隙計(jì)數(shù)器復(fù)位為1,，開始記錄時(shí)隙數(shù)，同時(shí)從1~L中選擇一個(gè)數(shù)做為其時(shí)隙數(shù)值,。當(dāng)時(shí)隙計(jì)數(shù)器值與標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)值相同時(shí),，標(biāo)簽向讀寫器發(fā)出應(yīng)答信息。若標(biāo)簽被讀寫器成功識(shí)別,，則退出識(shí)別系統(tǒng),。一個(gè)幀完成后，讀寫器開始時(shí)隙數(shù)同樣為L(zhǎng)的新幀,。
FFSA算法設(shè)計(jì)簡(jiǎn)單,，但缺點(diǎn)是如果標(biāo)簽數(shù)遠(yuǎn)遠(yuǎn)多于固定的時(shí)隙數(shù),，會(huì)產(chǎn)生過多碰撞；反之,，會(huì)產(chǎn)生較多空閑時(shí)隙,，造成資源浪費(fèi)。只有在標(biāo)簽數(shù)與時(shí)隙數(shù)差不多的一段時(shí)間內(nèi),，系統(tǒng)吞吐率" title="吞吐率">吞吐率最大" title="最大">最大,。可見,，由于FFSA算法的時(shí)隙數(shù)不能隨著標(biāo)簽數(shù)而變化,，系統(tǒng)無法獲得穩(wěn)定的吞吐率。為改善這一缺點(diǎn),，提出一種改進(jìn)算法——?jiǎng)討B(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í)別過程中估算標(biāo)簽數(shù),，用以確定匹配時(shí)隙數(shù)。在標(biāo)簽總數(shù)未知的情況下,當(dāng)初始時(shí)隙數(shù)L<16時(shí),，第一次讀取過程通常不能識(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-
)n(1+
)[2]。在讀寫器識(shí)別過程中,，已知當(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=
=2.392 2[2],。讀寫器在識(shí)別過程中,，統(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)用中，讀寫器能夠設(shè)定的時(shí)隙數(shù)是定值,，通常為1,，8，16,，32,，64，128,，256,。因此，讀寫器需要根據(jù)nest從以上幾個(gè)數(shù)中選擇一個(gè)數(shù)作為下一幀的時(shí)隙數(shù),。對(duì)250個(gè)以內(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時(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
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)答讀寫器,，而是延遲若干時(shí)隙（從0~7的范圍內(nèi)選擇）后再發(fā)出應(yīng)答信息[5]。
圖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)生過多的空閑時(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)無法通過增大時(shí)隙數(shù)來提高吞吐率,。為解決這個(gè)問題，在DFSA算法的基礎(chǔ)上提出分組幀時(shí)隙ALOHA算法（GFSA）,。參考文獻(xiàn)[3]中說明,，當(dāng)標(biāo)簽數(shù)多于354時(shí)將全部標(biāo)簽分成兩組或者更多組，讀寫器分別對(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算法上做很多修改,，例如讀寫器命令需要加入分組參數(shù)，標(biāo)簽需要確定并保存自己的分組序號(hào),，這使得實(shí)現(xiàn)變得有些困難,。
2 時(shí)隙隨機(jī)算法（SR）
時(shí)隙隨機(jī)算法沒有幀的概念，取而代之的是識(shí)別周期,。識(shí)別周期是指讀寫器兩次發(fā)送開始識(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)過程。
以ISO/IEC 18000-6 Type C[5]為例,，識(shí)別過程由讀寫器發(fā)送Query命令開始,，命令包含時(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)簽被讀寫器成功識(shí)別,，則退出識(shí)別系統(tǒng),。
讀寫器通過發(fā)送開始下一個(gè)時(shí)隙的命令（QueryRep），令標(biāo)簽的槽計(jì)數(shù)器值減1,，若槽計(jì)數(shù)器值為0(前一個(gè)時(shí)隙碰撞的標(biāo)簽),，則將其記為最大值(7FFFh)。當(dāng)讀寫器認(rèn)為需要更改時(shí)隙數(shù)時(shí),，發(fā)送更改時(shí)隙參數(shù)的命令(QueryAdjust),，令原有Q值加1或減1,，這時(shí)標(biāo)簽會(huì)重新產(chǎn)生槽計(jì)數(shù)器值。
時(shí)隙數(shù)的自適應(yīng)過程是通過發(fā)送QueryAdjust命令實(shí)現(xiàn)的,。讀寫器根據(jù)幾個(gè)時(shí)隙的識(shí)別情況（而非一個(gè)周期）,，增加或減少時(shí)隙參數(shù)Q，使之能夠及時(shí)有效地反映標(biāo)簽數(shù)的動(dòng)態(tài)變化,。一種簡(jiǎn)單的Q值算法是在讀寫器中設(shè)計(jì)一個(gè)參數(shù)Qfp作為Q的浮點(diǎn)數(shù),。每次讀寫器都根據(jù)標(biāo)簽的應(yīng)答情況更改Qfp值，然后將Qfp四舍五入為一個(gè)整數(shù)值,。若這個(gè)整數(shù)不同于之前的Q值,，則讀寫器發(fā)送QueryAdjust命令，令Q等于這個(gè)整數(shù);否則讀寫器不改變Q值,，發(fā)送QueryRep命令,。其過程如圖4所示。其中C為Qfp的變化步長(zhǎng),。一般來說,，Q與C成反比，因此可以取C=0.8/Q[6],。初始時(shí)隙數(shù)與DFSA算法相同,，取16，即Q=4,。
3 仿真分析
圖5,、圖6分別描述了識(shí)別一定數(shù)目的標(biāo)簽所需要的總時(shí)隙數(shù)和系統(tǒng)吞吐率。圖中,，F(xiàn)FSA 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ù)超過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)吞吐率開始下降,。此時(shí)可以通過GFSA算法提高系統(tǒng)吞吐率。仿真中采用兩種不同估算標(biāo)簽算法的DFSA算法,，其性能差不多,。但從實(shí)現(xiàn)角度講，DFSA II算法更好一些,，因?yàn)樗菀讓?shí)現(xiàn),。
SR算法作為另外一類基于時(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)心的首要問題都是使時(shí)隙數(shù)與標(biāo)簽數(shù)相匹配,，這樣才能提高系統(tǒng)吞吐率。對(duì)于文中分析的兩類算法,，幀時(shí)隙ALOHA算法設(shè)計(jì)簡(jiǎn)單,，適合于識(shí)別數(shù)量在600個(gè)以內(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 for fast object identification in RFID System. The 11th Inter-national Conference on Parallel and Distributed Systems, 2005.?????????????????????????????????????????????
[3] LEE S R， JOO S D， LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identifica-tion.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 Inst-itute of Technology.2002.
[5] ISO/IEC 18000-6.
[6] CHRISTIAN F, MATTHIAS W. Comparison of transm-ission schemes for framed ALOHA based RFID protocols. The International Symposium on Applications and the In-ternet Workshops, 2005.