《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 業界動態 > 基于時隙的RFID防碰撞算法分析

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

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

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

?

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

?

表1時隙數與標簽數的對應關系

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


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


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


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


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

本站內容除特別聲明的原創文章之外,轉載內容只為傳遞更多信息,并不代表本網站贊同其觀點。轉載的所有的文章、圖片、音/視頻文件等資料的版權歸版權所有權人所有。本站采用的非本站原創文章及圖片等內容無法一一聯系確認版權者。如涉及作品內容、版權和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,避免給雙方造成不必要的經濟損失。聯系電話:010-82306118;郵箱:aet@chinaaet.com。
热re99久久精品国产66热_欧美小视频在线观看_日韩成人激情影院_庆余年2免费日韩剧观看大牛_91久久久久久国产精品_国产原创欧美精品_美女999久久久精品视频_欧美大成色www永久网站婷_国产色婷婷国产综合在线理论片a_国产精品电影在线观看_日韩精品视频在线观看网址_97在线观看免费_性欧美亚洲xxxx乳在线观看_久久精品美女视频网站_777国产偷窥盗摄精品视频_在线日韩第一页
  • <strike id="ygamy"></strike>
  • 
    
      • <del id="ygamy"></del>
        <tfoot id="ygamy"></tfoot>
          <strike id="ygamy"></strike>
          国产精品自在线| 欧美二区在线播放| 欧美激情乱人伦| 欧美另类在线播放| 午夜亚洲性色福利视频| 亚洲精品国产无天堂网2021| 国产一区二区电影在线观看| 国产日产高清欧美一区二区三区| 国产专区欧美精品| 日韩午夜高潮| 欧美自拍偷拍| 红桃av永久久久| 最新高清无码专区| 国产精品久久久久一区二区三区| 国产精品www色诱视频| 欧美一区二区三区视频| 亚洲国产成人在线视频| 亚洲精品永久免费精品| 在线观看亚洲精品视频| 黑人操亚洲美女惩罚| 欧美亚洲视频一区二区| 欧美体内she精视频在线观看| 欧美不卡视频一区发布| 免费日韩av片| 一本色道久久99精品综合| 国内揄拍国内精品少妇国语| 欧美精品入口| 欧美在线观看一二区| 亚洲一区二区三区影院| 亚洲精品专区| 欧美午夜www高清视频| 欧美成人一区二免费视频软件| 日韩午夜中文字幕| 99在线精品免费视频九九视| 日韩午夜激情| 亚洲精品视频在线观看网站| 欧美久久久久久久久久| 欧美视频日韩视频| 亚洲制服欧美中文字幕中文字幕| 久久人人爽人人爽爽久久| 亚洲一区二区不卡免费| 欧美午夜精品理论片a级大开眼界| 欧美日本高清| 亚洲欧美影院| 亚洲一区二区精品| 久久人人精品| 欧美亚洲免费电影| 久久久久久亚洲精品杨幂换脸| 国产日产亚洲精品| 亚洲欧美国产另类| 欧美日韩在线观看视频| 免费在线欧美视频| 99视频国产精品免费观看| 久久er精品视频| 中文日韩在线视频| 亚洲日本中文字幕免费在线不卡| 国内精品写真在线观看| 亚洲综合社区| 嫩草伊人久久精品少妇av杨幂| 欧美xx69| 午夜电影亚洲| 亚洲国产精品一区制服丝袜| 欧美视频在线一区二区三区| 欧美性事免费在线观看| 久久在线免费观看视频| 99国产欧美久久久精品| 欧美一级淫片播放口| 国产精品乱码一区二三区小蝌蚪| 亚洲老板91色精品久久| 欧美日韩国产综合一区二区| 国产一二精品视频| 久久综合中文色婷婷| 一本色道久久综合亚洲精品婷婷| 久久久精品日韩欧美| 亚洲国产欧洲综合997久久| 欧美视频免费在线| 激情成人中文字幕| 一区在线影院| 99国产精品自拍| 欧美日韩国产一级| 亚洲毛片在线观看| 一本色道久久综合亚洲精品高清| 欧美视频第二页| 亚洲精品视频在线观看网站| 9人人澡人人爽人人精品| 久久亚洲一区二区| 亚洲成人资源网| 欧美午夜精品一区| 国产精品网站视频| av成人免费在线观看| 久久久视频精品| 久久精品国产99精品国产亚洲性色| 国产婷婷色一区二区三区| 国产主播一区二区三区四区| 久久久精品网| 国产日本欧美在线观看| 韩国一区二区三区美女美女秀| 日韩视频免费大全中文字幕| 欧美大片在线看免费观看| 伊人久久大香线蕉综合热线| 国产欧美亚洲一区| 欧美在线视频导航| 日韩视频一区二区三区| 欧美国产精品人人做人人爱| 久久久免费精品| 欧美精品自拍偷拍动漫精品| 中文一区字幕| 亚洲资源在线观看| 美女精品一区| 欧美视频一区在线观看| 国产精品人人做人人爽| 久久天堂精品| 亚洲免费在线看| 一区二区动漫| 欧美一区在线看| 亚洲免费一级电影| 欧美在线视频a| 免费视频久久| 欧美精品v日韩精品v国产精品| 久久国产精品一区二区三区四区| 国产精品免费视频观看| 国产自产v一区二区三区c| 久久精品国产69国产精品亚洲| 国产精品久久激情| 亚洲午夜在线| 夜夜夜精品看看| 国产亚洲一区二区三区在线观看| 国产精品青草综合久久久久99| 久久婷婷久久一区二区三区| 亚洲国产精品va在看黑人| 欧美日韩一区二区在线播放| 国产欧美在线| 亚洲一区二区在线免费观看视频| 国产综合久久久久久| 欧美日韩中文字幕精品| 欧美专区一区二区三区| 欧美日韩福利视频| 久久一区二区三区四区五区| 国产日韩欧美自拍| 在线播放国产一区中文字幕剧情欧美| 久久一二三国产| 国产精品一二一区| 欧美一区二区三区啪啪| 亚洲欧美在线磁力| 欧美成人三级在线| 欧美色偷偷大香| 午夜久久久久| 欧美午夜精彩| 国内精品久久久久久久影视蜜臀| 欧美日韩精品高清| 欧美精品一二三| 国产色爱av资源综合区| 欧美日韩成人| 久久久亚洲精品一区二区三区| 99视频热这里只有精品免费| 一区二区三区精品视频在线观看| 久久久亚洲高清| 欧美精品免费在线| 一区二区免费看| 国产一区二区三区免费观看| 亚洲深夜福利网站| 欧美日韩国产影院| 亚洲欧美激情在线视频| 国产精品久久久久一区二区| 欧美午夜免费电影| 欧美午夜无遮挡| 亚洲国产日本| 欧美福利视频在线观看| 在线播放豆国产99亚洲| 黑人中文字幕一区二区三区| av不卡在线看| 欧美怡红院视频| 国产精品久久久久久久久久ktv| 欧美人交a欧美精品| 亚洲欧美影音先锋| 国产精品一区二区久久| 久久只有精品| 久久国产精品99国产精| 亚洲欧美日本国产有色| 久久亚洲影音av资源网| 亚洲一卡二卡三卡四卡五卡| 久久久www免费人成黑人精品| 亚洲精品免费看| 欧美在线免费观看视频| 欧美四级在线观看| 伊人久久亚洲热| 欧美日韩高清一区| 欧美日韩精品一二三区| 欧美视频一区二区在线观看| 欧美成人在线影院| 亚洲三级影院| 欧美精品一区二区三区蜜臀| 亚洲嫩草精品久久| 亚洲一区二区精品视频| 香蕉视频成人在线观看| av不卡在线观看| 久久久久久久久久久久久9999| 久久精品国产999大香线蕉| 久久久亚洲国产天美传媒修理工| 欧美日韩国产一中文字不卡| 尤妮丝一区二区裸体视频| 一区二区三区在线高清| 伊人久久综合| 国模叶桐国产精品一区| 亚洲电影在线看| 国产精品久久中文| 国产精品第13页| 国产精品丝袜91| 亚洲精品久久久久久久久久久久| 久久五月激情| 久久精精品视频| 在线中文字幕一区| 中国成人黄色视屏| 一区二区三区av| 欧美电影免费网站| 欧美在线短视频| 午夜国产一区| 欧美婷婷在线| 欧美日韩一区二区在线| 香蕉视频成人在线观看| 美女网站在线免费欧美精品| 欧美亚洲一区二区在线观看| 在线成人免费视频| 国产一区二区欧美日韩| 日韩视频精品在线观看| 久久夜色撩人精品| 久久精品视频在线免费观看| 久久久久久九九九九| 欧美在线亚洲一区| 亚洲你懂的在线视频| 久久夜精品va视频免费观看| 欧美少妇一区| 欧美破处大片在线视频| 午夜精品久久久久久久男人的天堂| 91久久综合亚洲鲁鲁五月天| 在线观看欧美日韩国产| 韩国成人精品a∨在线观看| 国产精品大片wwwwww| 国产欧美一区二区三区国产幕精品| 在线观看欧美日韩| 艳女tv在线观看国产一区| 国产真实乱偷精品视频免| 国产精品红桃| 欧美福利一区二区三区| 亚洲免费小视频| 亚洲国产电影| 国产欧美日韩中文字幕在线| 久久亚洲精品网站| 亚洲日本理论电影| 亚洲日韩欧美视频一区| 欧美黑人国产人伦爽爽爽| 欧美综合77777色婷婷| 亚洲激情网址| 麻豆freexxxx性91精品| 欧美永久精品| 亚洲高清视频中文字幕| 国产精品视频免费在线观看| 精品成人国产在线观看男人呻吟| 亚洲精品乱码久久久久久久久| 久久国产精品久久久久久电车| 欧美激情免费观看| 亚洲日本在线视频观看| 亚洲国产高清在线观看视频| 欧美伦理a级免费电影| 在线日韩中文| 欧美亚洲视频在线观看| 欧美日韩国产成人高清视频| 国产精品成人观看视频免费| 欧美午夜精品理论片a级按摩| 久久综合一区| 国产精品一区二区久久精品| 正在播放欧美一区| 欧美.www| 欧美午夜在线| 亚洲精品之草原avav久久| 亚洲丶国产丶欧美一区二区三区| 亚洲一区二区免费看| 久久综合九九| 欧美一区二区三区日韩视频| 国产精品青草综合久久久久99| 国产精品vip| 国产精品夜夜嗨| 麻豆精品一区二区综合av| 国产精品麻豆欧美日韩ww| 欧美精品在线免费播放| 国产乱码精品一区二区三区av| 国产欧美在线看| 国产日韩欧美一区二区三区四区| 在线午夜精品自拍| 欧美日韩一区二区免费在线观看| 在线观看亚洲一区| 亚洲午夜日本在线观看| 欧美三级在线播放| 欧美岛国激情| 国产日本欧美视频| 亚洲精品国产精品乱码不99| 国产日韩欧美不卡| 国产精品爱久久久久久久| 亚洲夜晚福利在线观看| 欧美高清视频在线观看| 亚洲精品专区| 亚洲一区二区在线免费观看| 久久精品在线视频| 亚洲国产综合在线看不卡| 国产一区二区精品在线观看| 欧美视频精品一区| 欧美日一区二区在线观看| 久久综合中文色婷婷| 99re视频这里只有精品| 欲香欲色天天天综合和网| 欧美精品亚洲二区| 中文欧美字幕免费| 亚洲综合色在线| 亚洲欧洲一区二区在线播放| 在线综合视频| 老司机免费视频久久| 久久激情综合| 欧美精品九九99久久| 亚洲国产精品精华液网站| 国产精品久久久久一区二区三区共| 国产精品mv在线观看| 亚洲国产精品久久久久秋霞蜜臀| 国产精品美女一区二区在线观看| 亚洲毛片网站| 制服诱惑一区二区| 久久久久国产免费免费| 亚洲一区二区免费在线| 亚洲欧美中文另类|