《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 業(yè)界動態(tài) > 基于時隙的RFID防碰撞算法分析

基于時隙的RFID防碰撞算法分析

2008-03-17
作者:劉 佳, 張有光

  摘? 要:介紹了幾種常見的基于時隙" title="時隙">時隙的防碰撞算法" title="防碰撞算法">防碰撞算法:幀時隙ALOHA算法和時隙隨機算法,并通過仿真,比較分析這些算法識別所用總時隙和對系統(tǒng)吞吐性能的影響。
  關(guān)鍵詞:RFID? 防碰撞? 時隙

?

  無線射頻識別技術(shù)(RFID)是一種非接觸的自動識別技術(shù),因其具有識別距離遠、穿透能力強、多物體識別、抗污染等優(yōu)點,現(xiàn)已廣泛應(yīng)用于工業(yè)自動化、商業(yè)自動化、交通運輸控制管理、產(chǎn)品證件防偽、防盜等眾多領(lǐng)域,成為當前IT業(yè)研究的熱點技術(shù)之一。
  RFID系統(tǒng)一般由標簽(Tag)和讀寫器" title="讀寫器">讀寫器(Reader)兩個部分組成。在系統(tǒng)工作時,當有多個標簽同時發(fā)送數(shù)據(jù)時就會出現(xiàn)碰撞,其結(jié)果會導(dǎo)致傳輸失敗。因此需制定適當?shù)姆琅鲎菜惴?,避免或減少碰撞,從而有效地提高系統(tǒng)性能。一般防碰撞算法可以分為隨機型和決定型。本文主要研究隨機防碰撞算法中常見的兩類算法:幀時隙ALOHA算法及其改進型的、時隙隨機算法。
1 幀時隙ALOHA算法
  在RFID系統(tǒng)中,幀時隙ALOHA算法的“幀”是由讀寫器定義的一段時間長度,其中包含若干時隙。時隙指標簽收到讀寫器命令后,發(fā)送標識的時間長度。標簽被隨機分配到一個時隙應(yīng)答,當一個時隙中分配到多個標簽時就產(chǎn)生碰撞。根據(jù)幀內(nèi)時隙數(shù)是否變化分為固定幀時隙ALOHA算法和動態(tài)幀時隙ALOHA算法。
1.1 固定幀時隙ALOHA算法
  固定幀時隙ALOHA(FFSA)算法是最基本的一種算法,每幀時隙數(shù)的大小都一樣。識別過程開始時,由讀寫器向識別場內(nèi)所有標簽發(fā)送一個包含時隙數(shù)L的命令。這些標簽收到命令后,將其時隙計數(shù)器復(fù)位為1,開始記錄時隙數(shù),同時從1~L中選擇一個數(shù)做為其時隙數(shù)值。當時隙計數(shù)器值與標簽隨機選擇的時隙數(shù)值相同時,標簽向讀寫器發(fā)出應(yīng)答信息。若標簽被讀寫器成功識別,則退出識別系統(tǒng)。一個幀完成后,讀寫器開始時隙數(shù)同樣為L的新幀。
  FFSA算法設(shè)計簡單,但缺點是如果標簽數(shù)遠遠多于固定的時隙數(shù),會產(chǎn)生過多碰撞;反之,會產(chǎn)生較多空閑時隙,造成資源浪費。只有在標簽數(shù)與時隙數(shù)差不多的一段時間內(nèi),系統(tǒng)吞吐率" title="吞吐率">吞吐率最大" title="最大">最大。可見,由于FFSA算法的時隙數(shù)不能隨著標簽數(shù)而變化,系統(tǒng)無法獲得穩(wěn)定的吞吐率。為改善這一缺點,提出一種改進算法——動態(tài)幀時隙ALOHA算法。
1.2 動態(tài)幀時隙ALOHA算法
  動態(tài)幀時隙ALOHA(DFSA)算法是每幀時隙數(shù)都會根據(jù)標簽數(shù)的不同而變化。為獲得系統(tǒng)最大吞吐率,DFSA算法需要在識別過程中估算標簽數(shù),用以確定匹配時隙數(shù)。在標簽總數(shù)未知的情況下,當初始時隙數(shù)L<16時,第一次讀取過程通常不能識別出標簽。因此為節(jié)約初始時間,設(shè)置初始時隙數(shù)Linit=16[1]。
  標簽估算的方法有很多種[2-4],例如:
  (1)估算出參與識別的標簽總數(shù)。設(shè)時隙數(shù)為L,標簽數(shù)為n,則一個幀中碰撞時隙率Cratio=1-(1-)n(1+)[2]。在讀寫器識別過程中,已知當前幀時隙數(shù)為L,并且可以統(tǒng)計出該幀時隙碰撞率Cratio,采用逼近算法,可以估算出n。
 ?。?)直接估算出未識別的標簽數(shù)。當系統(tǒng)達到最大吞吐率時,一個時隙的碰撞率Ctags=0.418 0[2],因此一個時隙碰撞的標簽數(shù)Ctags==2.392 2[2]。讀寫器在識別過程中,統(tǒng)計前一個幀的時隙碰撞數(shù)Ncoll,則未識別標簽數(shù)nest=2.392 2×Ncoll。
  得到未識別標簽估計數(shù)nest后,從理論上講最優(yōu)的時隙數(shù)L應(yīng)該等于nest[2],但在實際應(yīng)用中,讀寫器能夠設(shè)定的時隙數(shù)是定值,通常為1,8,16,32,64,128,256。因此,讀寫器需要根據(jù)nest從以上幾個數(shù)中選擇一個數(shù)作為下一幀的時隙數(shù)。對250個以內(nèi)不同數(shù)目的標簽,選擇不同時隙數(shù),計算一個幀的吞吐率。對不同標簽數(shù)選擇吞吐率最大所對應(yīng)的時隙數(shù)如圖1所示,得到標簽數(shù)與匹配時隙數(shù)的對應(yīng)關(guān)系如表1所示。這樣就可以在估算出未識別標簽數(shù)之后,在下一幀中選擇匹配的時隙數(shù),從而提高系統(tǒng)吞吐率。

?

表1時隙數(shù)與標簽數(shù)的對應(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 帶延遲的幀時隙ALOHA算法
  幀時隙ALOHA算法中,若幀時隙數(shù)遠遠小于標簽數(shù),在匹配前系統(tǒng)吞吐率很低。為了在時隙數(shù)與標簽數(shù)匹配前,提高當前幀的吞吐率,引入了延遲機制,即當標簽隨機選擇的時隙數(shù)與時隙計數(shù)器數(shù)值相同時,標簽并不立即應(yīng)答讀寫器,而是延遲若干時隙(從0~7的范圍內(nèi)選擇)后再發(fā)出應(yīng)答信息[5]。
  圖2是設(shè)定初始時隙為16,對比不同標簽數(shù)(標簽數(shù)大于16)下第一個幀的吞吐率。由圖2看出,帶延遲的算法的確可以提高一幀的吞吐率,然而延遲算法只有在標簽數(shù)多而時隙數(shù)少的情況下才有利于提高系統(tǒng)吞吐率。在相反的情況下,延遲算法在減少碰撞時隙的同時,產(chǎn)生過多的空閑時隙,不能提高系統(tǒng)的吞吐率。


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


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


3 仿真分析
  圖5、圖6分別描述了識別一定數(shù)目的標簽所需要的總時隙數(shù)和系統(tǒng)吞吐率。圖中,F(xiàn)FSA 128和FFSA 256分別代表采用128和256時隙數(shù)的固定幀時隙ALOHA算法;DFSA I和DFSA II分別代表采用1.2節(jié)第一種標簽估計算法和第二種標簽估計算法的動態(tài)幀時隙ALOHA算法;SR算法代表時隙隨機算法,其Q值算法采用第2節(jié)所述方法。
從圖5、圖6中可以看出,若采用時隙數(shù)為128的FFSA算法,當標簽數(shù)超過300時,識別標簽所需的時隙總數(shù)迅速增長。同樣采用時隙數(shù)為256的FFSA算法,時隙總數(shù)也呈現(xiàn)迅速增長的趨勢。FFSA算法的系統(tǒng)吞吐率較低而且吞吐性能不穩(wěn)定。


  若采用DFSA算法,識別標簽所需的時隙總數(shù)略有下降。當標簽數(shù)少于600時,系統(tǒng)吞吐率較高而且相對穩(wěn)定;當標簽數(shù)大于600時,由于受到最大時隙數(shù)256的限制,系統(tǒng)吞吐率開始下降。此時可以通過GFSA算法提高系統(tǒng)吞吐率。仿真中采用兩種不同估算標簽算法的DFSA算法,其性能差不多。但從實現(xiàn)角度講,DFSA II算法更好一些,因為它容易實現(xiàn)。
  SR算法作為另外一類基于時隙的防碰撞算法,其性能遠遠優(yōu)于前面幾種算法。SR算法采用時隙數(shù)自適應(yīng)機制,不僅減少碰撞時隙和空閑時隙產(chǎn)生,而且使碰撞標簽可以及時重新參與識別。SR算法的最大時隙數(shù)可達215,在實際應(yīng)用中,即便識別很大數(shù)量的標簽時,也不會受到時隙數(shù)的限制。采用SR算法系統(tǒng)吞吐率最高且保持在一個定值左右。特別在識別很大數(shù)量的標簽時,SR算法識別標簽所用的總時隙數(shù)比DFSA算法減少很多。
  總之,在RFID系統(tǒng)中,基于時隙的防碰撞算法關(guān)心的首要問題都是使時隙數(shù)與標簽數(shù)相匹配,這樣才能提高系統(tǒng)吞吐率。對于文中分析的兩類算法,幀時隙ALOHA算法設(shè)計簡單,適合于識別數(shù)量在600個以內(nèi)的標簽;時隙隨機算法相對復(fù)雜一些,但系統(tǒng)吞吐率高而且性能穩(wěn)定,特別適合識別很大數(shù)量的標簽。
參考文獻
[1] 吳晶,熊璋,王曄. 利用動態(tài)時間槽分配的多目標防沖突射頻識別.北京航空航天大學學報,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.

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,避免給雙方造成不必要的經(jīng)濟損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。