《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 設計應用 > 基于多叉樹搜索算法改進的RFID防碰撞算法
基于多叉樹搜索算法改進的RFID防碰撞算法
來源:電子技術應用2013年第2期
林 偉, 李景霞, 葉林鋒
廣東工業大學 計算機學院, 廣東 廣州510006
摘要: 多標簽碰撞問題嚴重影響了RFID系統的性能。為了更好地解決這一問題,提出了基于多叉樹搜索的防碰撞算法。該算法根據碰撞位的不同來動態選擇二叉樹搜索和四叉樹搜索,并引用堆棧存儲查詢命令以避免重復搜索和冗余搜索,使得在大批量標簽的情況下,系統吞吐率大幅度提高。
中圖分類號: TP309
文獻標識碼: A
文章編號: 0258-7998(2013)02-0130-04
An improved anti-collision algorithm based on multi-tree search in RFID
Lin Wei, Li Jingxia, Ye Linfeng
School of Computer Science,GDUT, Guangzhou 510006, China
Abstract: Multi-tags collision seriously affect the performance of RFID systems,in order to better solve this problem, this paper presents the anti-collision algorithm based on the multi-branch tree search and selects binary tree search and quad tree search algorithm based on the different dynamics of the collision bits,it also references the stack to store query commands to avoid duplication and redundance of search,making the system throughput greatly improve in the case of very large number of tags.
Key words : RFID;anti-collision algorithm;binary tree search; quad tree search; stack

    射頻識別技術(RFID" title="RFID" target="_blank">RFID)是一種非接觸、低功耗、無線通信技術,可通過無線電信號識別特定目標并讀寫相關數據。典型的RFID系統由電子標簽(Tags)和讀寫器(Reader)組成,電子標簽與讀寫器之間是通過耦合(天線)實現射頻信號的空間(無接觸)耦合。在耦合通道內,根據時序關系,實現能量的傳遞、數據的交換。其工作原理如圖1所示。

    隨著RFID技術的廣泛應用,存在的問題也越來越凸顯出來。目前RFID技術存在的主要問題有:安全問題、傳輸距離問題、碰撞問題等,其中碰撞問題嚴重制約著RFID的發展。目前,雖然已經有很多種防碰撞的算法,但是在算法執行效率和精確度方面各有缺陷。本文在研究大量防碰撞算法的基礎上,經過比較分析提出了一種新的基于樹搜索的防碰撞算法,該算法根據碰撞位的情況動態地選擇合適的搜索樹算法,大幅度提高了RFID的性能。
1 防碰撞算法簡介
    如果在RFID讀寫器可讀取范圍內有多個標簽,或是一個標簽同時接收到幾個讀寫器發出的信號就會發生沖突,即所謂的碰撞。一旦發生碰撞就會導致讀寫器不能讀取電子標簽信息或是無法讀到正確的標簽信息,所以防碰撞算法就顯得尤為重要。根據碰撞的產生原理可以將RFID的碰撞分為[1]:標簽碰撞、頻率干擾、標簽干擾。其中頻率干擾和標簽干擾統稱為讀寫器碰撞。
    由于讀寫器碰撞的發生概率較小且容易避免,所以本文主要研究對象是標簽碰撞。解決碰撞的算法就稱為防碰撞算法。防碰撞算法最常使用的方法[2]有空分多址(SDMA)、頻分多址(FDMA)、碼分多址(CDMA)和時分多址(TDMA)。目前較為流行的RFID的兩種防碰撞算法,基于ALOHA和基于樹的算法都是基于時分多址的。
2 基于多叉樹的RFID防碰撞算法
    二進制樹算法(BS)[3]的基本思想是將處于碰撞狀態的標簽分為0和1兩個子集,先查詢子集0,若沒有沖突,則正確識別;若仍有沖突,則再分裂,把子集0分為00和01兩個子集,依次類推,直到子集0中的所有標簽全部識別,再按照此步驟查詢子集1。使用BS算法的標簽要經過多次比較,并通過循環操作以達到識別所有標簽,搜索過程中會出現路徑的重復,搜索效率比較低[4]。為滿足RFID系統能耗低、速度快等要求,其防碰撞算法有如下特點[5]:(1)識別過程中查詢時間要短,查詢次數也要盡量少。(2)對于無源標簽來說必須是低能耗,要達到低能耗就要求算法中標簽與讀寫器之間傳輸的比特數要少。(3)標簽能夠被完全、正確地識別,要求讀寫器對其可讀取范圍內的所有標簽都要正確、完整地識別,不能出現錯誤識別和遺漏識別。本文提出的基于多叉樹搜索的防碰撞算法在滿足RFID防碰撞算法的基礎上,盡量解決上述防碰撞算法中的問題。
2.1 算法的基本思想
    讀寫器在發出Request命令后,讀寫器可讀取范圍內的所有標簽都要做出應答,如果讀寫器譯碼后得到n個位發生碰撞,即只有標簽這n個比特是讀寫器無法識別的。讀寫器根據這n個碰撞位所在的位置,分成三種情況進行處理:(1)若碰撞位連續兩位,則采用動態四叉樹分裂查詢; (2)若碰撞位非連續,則采用動態二叉樹分裂查詢;(3)若碰撞位只有一位,則采用二叉樹查詢。
    在發送查詢指令時,不需發送碰撞標簽完整的ID號,只要用二進制代碼表示碰撞位即可,這樣可以在很大程度上減少發送的數據量,繼而降低功耗、提高識別效率。
2.2 算法的工作流程
    算法的步驟如下:
  (1) 算法先發送一個Request(11111111)命令,所有電子標簽對此做出應答,然后將自己的ID碼發送出去。
  (2) 讀寫器檢測接收到的信號,若未能檢測到信號,則說明在讀寫器可讀取的范圍內沒有電子標簽,返回步驟(1);若檢測到信號,則轉到步驟(3)。
  (3) 判斷是否有碰撞發生,若無則對標簽進行讀寫操作;若有,則轉到步驟(4)。
  (4) 將查詢碼壓入堆棧,并發送棧頂的查詢碼,滿足該查詢碼的標簽應答。判斷碰撞情況:若沒有標簽應答,則讀寫器本次識別過程結束,并檢堆棧是否為空;若只有一個標簽應答,讀寫器發出RW-DATA指令,對該標簽進行讀寫操作之后,讀寫器發出Sleep指令,標簽進入休眠狀態,不參與后續的識別過程;若有多個標簽做出應答,即發生碰撞,則轉到步驟(5)。
  (5) 根據碰撞位的不同情況,選擇不同的搜索方法,重復步驟(4),直到堆棧為空。
  (6) 堆棧為空說明所有標簽都被成功識別,整個標簽識別過程結束。
2.3 算法舉例
    假如電子標簽的ID碼均是8位,在讀寫器可讀取范圍內有4個處于準備狀態的電子標簽A、B、C、D,它們的ID號為:TagA:10000110、TagB:11010010、TagC:01000010、TagD:01001010。本例的搜索過程中堆棧變化情況如圖2所示,算法實現步驟如下:

    (1) 當讀寫器發出Request(11111111)指令后,得到譯碼后的碰撞位為:XX0XXX10。
    (2) 讀寫器將連續碰撞位XX用四叉樹進行查詢,發生碰撞的最高位為第7位,用二進制表示為111。將Request(00,111)、Request(01,111)、 Request(10,111)、Request(11,111)依次入棧,然后發送棧頂指令Request(00,111),沒有符合查詢碼的標簽響應,該分支的識別過程結束;發送指令Request(01,111),有標簽C、D響應,即發生了碰撞,將C、D重新譯碼后得到新的譯碼數據為0100X010,此時讀寫器檢測到只有一個碰撞位。參考文獻[6]中設定只有一個碰撞位時,讀寫器能直接識別出兩個標簽,但是由于標簽本身無法識別,所以只有一個碰撞位時,讀寫器也還是要經過一次比較,才能識別出兩個標簽最高碰撞位為第3位,將Request(0,11)、Request(1,11)壓入堆棧。
    (3) 讀寫器發送Request(0,11)命令,只有標簽D應答,經讀寫器讀寫操作后進入休眠態。
  (4) 讀寫器發送Request(1,11)命令,只有標簽C應答,執行讀寫操作后轉入休眠態。
  (5) 讀寫器發送Request(10,111)命令,只有標簽A應答,執行讀寫操作后轉入休眠態。
  (6) 讀寫器發送Request(11,111)命令,只有標簽B應答,執行讀寫操作后轉入休眠態。
  (7) 堆棧內的命令全部讀取并發送,堆棧為空,說明待識別的標簽全部識別完,標簽識別過程結束。
3 新算法的性能分析
3.1發送數據量分析

 當標簽的ID較長時,讀寫器每次發送的查詢指令的位數就會很多,這樣會嚴重影響傳輸速率和系統識別效率[6]。如果直接用二進制表示碰撞位的信息,則可以大大減少發送的數據量。假設標簽的ID號有N位,則只要n位序列就能表示出所有的碰撞位,其中:

 


    假設在整個識別過程中查詢M次只有1個碰撞位,則整個識別過程中有M個葉子節點,那么動態二叉樹查詢次數為:
     

4 實驗仿真與分析
    利用軟件Matlab對上述算法的傳輸數據量、查詢次數和吞吐率進行試驗仿真,結果如圖3所示。

    由圖3(a)可以看出,隨著標簽ID的增長,新算法的傳輸數據量增加很少,與未經過改進的算法的指令長度相比,新算法能很大程度地減少傳輸指令長度,從而能減少系統的能耗,增加系統的識別效率。
    由圖3(b)可以看出,在同樣數目的待識別標簽的情況下,動態二叉樹和動態四叉樹所需的查詢總數,與本文的算法所需查詢總數的比較中,本文新算法所需的總查詢數較少,即識別時間較短。
    由圖3(c)可得新算法的吞吐率高于動態二叉樹和動態四叉樹搜索算法的吞吐率,即新算法的識別率更高。
    本文在研究大量防碰撞算法的基礎上經過比較分析,提出了一種新的基于樹搜索的防碰撞算法,該算法根據碰撞位的情況,動態地選擇合適的搜索樹算法,而且本文還引用了堆棧來存儲查詢命令,這樣可以避免重復、多余的搜索,減少了搜索樹的分支數。由數學分析和算法的仿真結果可得,該算法查詢時間短、系統效率高、性能優良,特別是在待識別標簽數量龐大時,該算法表現出更加明顯的優勢。
參考文獻
[1] Jia Xiaolin,Feng Quanyuan,Fan Taihua, et al. Analysis of  anti-collision protocols for RFID tag identification[C].IEEE  2012 2nd International Conference on Digital Object Identifier, 2012.
[2] 胡兆吉.基于嵌入式的射頻識別系統[D].西安:西安電子科技大學,2011.
[3] 丁治國.RFID關鍵技術研究與實現[D].合肥:中國科學技術大學,2009.
[4] 李興鶴,胡詠梅,王華蓮,等.基于動態二進制的二叉樹搜索結構RFID反碰撞算法[J].山東科學,2006,19(2):51-55.
[5] 江岸,伍繼雄,黃生葉,等.改進的RFID二進制搜索防碰撞算法[J].計算機工程與應用,2009,45(5):229-235.
[6] 江城,黃立波.基于二進制搜索的RFID標簽防碰撞算法研究[J].計算機與數字工程,2011(4):29-33.
[7] 孫文勝,胡玲敏.基于后退式搜索的自適應多叉樹防碰撞算法[J].計算機應用, 2011,31(08):2052-2055.
[8] 丁俊.射頻識別RFID標簽防碰撞算法[D].合肥:中國科技大學2010.

此內容為AET網站原創,未經授權禁止轉載。
热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>
          国产精品欧美一区喷水| 在线免费观看成人网| 久久久亚洲午夜电影| 久久三级视频| 欧美中文字幕视频| 欧美大片在线影院| 国产精品国产三级国产普通话三级| 国产精品私拍pans大尺度在线| 欧美日韩国产综合在线| 亚洲免费观看高清完整版在线观看熊| 欧美黄色大片网站| 欧美日韩免费精品| 欧美国产在线观看| 国产精品久久久久久久免费软件| 欧美日韩精品国产| 亚洲破处大片| 亚洲最新合集| 一本久道久久综合狠狠爱| 午夜日韩福利| 亚洲精品欧美极品| 亚洲第一精品夜夜躁人人躁| 欧美日韩在线精品一区二区三区| 99精品视频一区二区三区| 国产精品免费久久久久久| 激情文学综合丁香| 欧美高清视频在线| 国产农村妇女精品一二区| 欧美一级欧美一级在线播放| 一区二区欧美激情| 麻豆九一精品爱看视频在线观看免费| 欧美亚男人的天堂| 麻豆精品91| 久久香蕉精品| 亚洲精品一二三| 精品电影在线观看| 国产精品v欧美精品v日本精品动漫| 欧美国产视频在线观看| 国产欧美精品一区二区色综合| 亚洲精品九九| 国产精品你懂的| 亚洲品质自拍| 国产精品欧美久久久久无广告| 美女国产精品| 亚洲国产高潮在线观看| 亚洲在线视频网站| 久久久国产精品一区二区三区| 狠狠色丁香久久婷婷综合_中| 亚洲免费高清| 欧美日韩1区2区3区| 一本久久a久久免费精品不卡| 国产精品久久久免费| 国产自产女人91一区在线观看| 欧美片在线观看| 久久精品国产亚洲高清剧情介绍| 亚洲黄色成人| 欧美一区二区| 国产精品www色诱视频| 亚洲日本va午夜在线影院| 国产视频一区在线观看| 久久久一二三| 久久综合电影一区| 亚洲七七久久综合桃花剧情介绍| 国产欧美日韩精品a在线观看| 亚洲免费视频网站| 国产日韩欧美三级| 欧美激情一区二区三区在线视频| 老牛国产精品一区的观看方式| 亚洲国产一区视频| 一区二区电影免费在线观看| 久久露脸国产精品| 国产精品户外野外| 亚洲精品一区二区三区福利| 久久精品人人做人人爽电影蜜月| 麻豆91精品91久久久的内涵| 国产精品久久久久久久久免费| 国产欧美日韩综合一区在线播放| 在线精品视频免费观看| 欧美大学生性色视频| 亚洲一区二区三区久久| 一本色道久久综合狠狠躁篇的优点| 欧美一区在线看| 亚洲免费高清| 99精品欧美一区二区三区综合在线| 欧美一区二区三区久久精品| 欧美一级二级三级蜜桃| 欧美日韩人人澡狠狠躁视频| 1024成人| 亚洲国产va精品久久久不卡综合| 欧美成va人片在线观看| 黄色成人片子| 国产日韩精品视频一区| 国产精品久久久久国产精品日日| 欧美a级一区| 亚洲精品欧美一区二区三区| 羞羞视频在线观看欧美| 黄色国产精品| 国产精品免费一区二区三区观看| 国产精品永久入口久久久| 免费精品99久久国产综合精品| 一区二区三区久久精品| 久久亚洲免费| 久久精品一二三区| 一本久道久久综合婷婷鲸鱼| 欧美喷水视频| 欧美日韩国产综合视频在线观看中文| 欧美日韩免费区域视频在线观看| 亚洲精品国产精品乱码不99按摩| 国产美女在线精品免费观看| 久久精品一二三区| 午夜精品久久久久久久白皮肤| 欧美激情自拍| 老司机亚洲精品| 欧美一区二区三区四区高清| 亚洲自拍偷拍麻豆| 欧美高清在线一区二区| 国产精品一区三区| 欧美人牲a欧美精品| 欧美激情网友自拍| 亚洲精品久久视频| 国产精品久久久久aaaa樱花| 欧美成人精品不卡视频在线观看| 欧美美女日韩| 国产乱码精品一区二区三区av| 国产亚洲欧美日韩美女| 国产一区二区三区久久| 美女脱光内衣内裤视频久久影院| 在线观看视频一区二区| 久久亚洲一区二区| 欧美三区免费完整视频在线观看| 欧美另类视频| 欧美激情影院| 国产精品成人免费| 蜜臀久久99精品久久久画质超高清| 欧美日韩在线观看一区二区三区| 欧美国产欧美亚州国产日韩mv天天看完整| 欧美高清视频www夜色资源网| 欧美日韩亚洲视频| 亚洲黄色成人| 亚洲最黄网站| 欧美三级视频在线观看| 亚洲高清二区| 国产精品久久久久毛片软件| 亚洲一区二区三区在线观看视频| 亚洲高清精品中出| 欧美精品久久久久久久免费观看| 午夜一区二区三区在线观看| 国产精品国产三级国产aⅴ入口| 免费在线播放第一区高清av| 欧美另类一区二区三区| 欧美高清视频在线播放| 日韩一区二区久久| 美女视频一区免费观看| 91久久精品日日躁夜夜躁国产| 久久高清国产| 欧美日本亚洲视频| 小嫩嫩精品导航| 亚洲欧洲三级电影| 欧美电影打屁股sp| 在线亚洲免费视频| 久久影视精品| 亚洲高清视频的网址| 99视频精品免费观看| 国内精品写真在线观看| 国内视频一区| 亚洲欧美日韩在线观看a三区| 一本一本久久a久久精品综合妖精| 亚洲高清在线观看一区| 欧美日韩在线另类| 欧美成人a∨高清免费观看| 国产伦精品一区二区三区免费| 亚洲第一页中文字幕| 国产精品99久久久久久www| 国产精品扒开腿做爽爽爽软件| 国产女主播视频一区二区| 久久久之久亚州精品露出| 欧美二区在线| 欧美成人国产| 欧美成年人视频| 久久尤物电影视频在线观看| 国产免费成人| 在线观看一区二区视频| 欧美日韩国产不卡在线看| 99re在线精品| 久久久久高清| 激情久久中文字幕| 午夜久久久久久久久久一区二区| 久久久久久噜噜噜久久久精品| 亚洲三级电影全部在线观看高清| 国产欧美日韩麻豆91| 牛牛国产精品| 亚洲黄色在线视频| 国产精品久久7| 一区二区三区在线免费观看| 欧美激情综合网| 久久夜色精品国产噜噜av| 亚洲欧美日韩爽爽影院| 亚洲欧美视频在线观看视频| 欧美午夜在线视频| 亚洲第一伊人| 欧美日韩专区| 亚洲欧美自拍偷拍| 亚洲精品自在久久| 国产精品久久久久久久久久三级| 久久一二三区| 久久精品一区| 亚洲一区二区三区视频播放| 国产乱码精品一区二区三区av| 亚洲一区二区三区高清不卡| 日韩一级网站| 欧美专区中文字幕| 久久亚洲国产精品日日av夜夜| 欧美中文字幕久久| 国产乱码精品一区二区三区五月婷| 999在线观看精品免费不卡网站| 国内外成人免费激情在线视频网站| 一区三区视频| 麻豆国产精品一区二区三区| 国产精品社区| 欧美日韩中文字幕综合视频| 国产精品在线看| 欧美日韩一区二区三区在线看| 国产色视频一区| 亚洲伦理网站| 欧美成人高清| 亚洲精品久久久久久久久久久| av成人免费在线| 久久久综合激的五月天| 亚洲午夜未删减在线观看| 亚洲综合欧美日韩| 国产一区二区精品久久91| 亚洲欧美色一区| 亚洲精品久久在线| 欧美mv日韩mv国产网站| 亚洲国产经典视频| 久久精品av麻豆的观看方式| 午夜视频久久久| 在线亚洲免费| 亚洲一区欧美二区| 国产欧美一区二区精品忘忧草| 欧美久久影院| 国产精品爱啪在线线免费观看| 伊人久久成人| 亚洲国产人成综合网站| 欧美日韩大片| 性伦欧美刺激片在线观看| 99精品视频一区二区三区| 99国产成+人+综合+亚洲欧美| 夜夜嗨av一区二区三区中文字幕| 国产精品亚洲аv天堂网| 99精品国产99久久久久久福利| 欧美一级视频一区二区| 黄色一区二区三区四区| 久久影视精品| 亚洲一区视频在线观看视频| 午夜在线观看欧美| 欧美国产91| 亚洲一区二区三区精品动漫| 99精品欧美一区二区蜜桃免费| 亚洲国产日韩欧美| 久久一区二区精品| 欧美日韩亚洲国产一区| 国产片一区二区| 免费在线亚洲| 亚洲欧美日韩久久精品| 国产日产欧产精品推荐色| 亚洲午夜视频在线观看| 日韩视频免费大全中文字幕| 国产精品网站在线观看| 欧美成年网站| 亚洲高清视频的网址| 久久久水蜜桃av免费网站| 国产精品网站在线观看| 在线亚洲精品| 久久国产天堂福利天堂| 久久久久久综合| 亚洲人成毛片在线播放女女| 国产人妖伪娘一区91| 国产精品99久久久久久www| 欧美日韩1区2区| 亚洲综合第一页| 免费亚洲婷婷| 国产九九视频一区二区三区| 亚洲黄色一区二区三区| 亚洲经典视频在线观看| 欧美 日韩 国产精品免费观看| 国产精品一区二区a| 亚洲午夜精品视频| 国产精品美女www爽爽爽| 欧美高清不卡| 99国产精品国产精品久久| 欧美图区在线视频| 999亚洲国产精| 欧美www视频在线观看| 欧美亚洲视频在线看网址| 国产婷婷一区二区| 国产中文一区| 欧美日韩日本网| 国产精品久久久久久久浪潮网站| 亚洲欧美怡红院| 在线播放日韩专区| 亚洲综合电影| 亚洲国产日韩在线一区模特| 久久夜色精品国产欧美乱极品| 99国产精品久久久久老师| 久久综合999| 亚洲精品国产精品久久清纯直播| 久久久久久久999精品视频| 久久久久久999| 亚洲一品av免费观看| 老司机亚洲精品| 在线中文字幕不卡| 欧美日韩国产系列| 亚洲日本一区二区三区| 欧美亚男人的天堂| 亚洲电影av| 欧美—级高清免费播放| 最新中文字幕一区二区三区| 狠狠色噜噜狠狠色综合久| 欧美专区在线| 国产精品视频大全| 国产喷白浆一区二区三区| 理论片一区二区在线| 亚洲三级免费观看| 免费在线看成人av| 国产亚洲欧美日韩日本| 国产一区99| 亚洲免费视频中文字幕| 尤物九九久久国产精品的分类|