【總結(jié)】RFID二進(jìn)制樹防碰撞算法總結(jié)

1、南 陽 理 工 學(xué) 院本科生畢業(yè)設(shè)計（論文）學(xué)院（系）：運算機與信息工程學(xué)院專業(yè)：通信工程學(xué)生：喬軍惠指導(dǎo)老師：路新華完成日期2021年 4月南 陽 理 工 學(xué) 院 本 科 畢 業(yè) 設(shè) 計（論文）rfid 二進(jìn)制樹防碰撞算法設(shè)計38 / 27學(xué) 院（系）：運算機與信息工程學(xué)院專業(yè)：通信工程學(xué) 生 姓 名：喬軍惠學(xué)號：1指 導(dǎo) 教 師（職稱）：路新華（講師）評 閱 教 師：完 成 日 期：2021 年 4 月南陽理工學(xué)院nanyang institute of technologyrfid 二進(jìn)制樹防碰撞算法設(shè)計【摘要】射頻識別技術(shù) rfid 是目前正快速進(jìn)展的一項新技術(shù)， 它通過射頻信號進(jìn)行非

2、接觸式的雙向數(shù)據(jù)通信，從而達(dá)到自動識別的目的；隨著rfid技術(shù)的進(jìn)展，如何實現(xiàn)同時與多個目標(biāo) 之間的正確的數(shù)據(jù)交換，即解決 rfid 系統(tǒng)中多個讀寫器和應(yīng)答器之間的數(shù)據(jù)碰撞，成為了限制rfid技術(shù)進(jìn)展的難題， 采納合理的算法來有效的解決該問題， 稱為 rfid系統(tǒng)的防碰撞算法； 在各種算法當(dāng)中，二進(jìn)制樹算法由于它識別應(yīng)答器的確定性，成為了應(yīng)用最廣泛的一種，多個國際標(biāo)準(zhǔn)均對其進(jìn)行了規(guī)定，這推動了防碰撞算法的進(jìn)展，但是也帶來明白決思路不統(tǒng)一的沖突；在傳統(tǒng)思路中，一般是通過單片機來進(jìn)行算法處理，隨著rfid技術(shù)的進(jìn)展，將來的一個重要方向是現(xiàn)場可編程門陣列 fpga，做為一種現(xiàn)場可編程的專用集成電路，

3、 fpga擁有高速度，可編程等多個適應(yīng)于算法處理的優(yōu)點， 從而為 rfid防碰撞算法問題開創(chuàng)了新的有效途徑依據(jù)上述分析， 全文針對 rfid 系統(tǒng)二進(jìn)制樹防碰撞算法，進(jìn)行了理論與實踐方面的探討，主要分為三個方面， 第一是二進(jìn)制樹算法的理論爭論，將現(xiàn)有的二進(jìn)制樹算法進(jìn)行了歸納，匯總為基本算法，動態(tài)算法，退避式算法三類，闡述了各個算法的思路，對其進(jìn)行了性能評判；其次，在現(xiàn)有的三類 防碰撞算法的基礎(chǔ)上，提出了一種新的改進(jìn)型二進(jìn)制樹算法，該算法識別速度快，執(zhí)行效率高， 極大的改進(jìn)了識別成效；【關(guān)鍵詞】： 射頻識別；防碰撞算法；讀寫器；應(yīng)答器；現(xiàn)場可編程門陣列abstractrfid is anewly

4、 developedtechnologywhich communicates through the contact rf signal ， so asto achieve objective automatic identification along with the development of rfid technology， how to realize data exchange accurately amongmultipletargets atthe same timebecomes the keyproblemofrfidtechnology rfid anti-collis

5、ion algorithm is the solution to the above mentioned problemsin all the algorithms ，binary algorithm is most widely used as an international standard fbr its exactness ofidentincation international standards have put forward manyregulations on binary algorithmit not onlypromotes the development of a

6、nticouision algorithm ，butalso b“ ngsthe conflictto a unilfiedsolution traditionalideasin general are handled bymcu alongwith the developmentofrfidtechnology ， an imponantdirectioninthe f utureis thefieldprogrammablegates arrayfpga as kindof integrated circuitsthatcanbe programmed in the field， fpga

7、 is fast and programmable all these advantagesopenup anewef active way ofrfidanti collisionarithmetic in viewof the above problems， this paperprobes into the rfid systembinary prevent collisionf rom the perspectives ofboth theory and practice it canbedivided into three aspects：6rstly ，theoretical re

8、searchon binary algorithm it sums up all thebinary algorithms inbeingandgathertothreecategoryssuchasbasicalgorithm ，dynamicalgorithmandbackoff algorithm moreover ，it expounds the idea of the various algorithms and evalues their perf6rmance； secondary， it introduces an improved version of algorithm o

9、nthe basis of specinc standardthis algorithm has f ast recognition ， high efnciency and greatly improvedthe identification results key words： rfid ； anticollision ； read write devices ； transponders； fpga目錄1 引言 .511 rfid技術(shù)簡介 .512 rfid系統(tǒng) .5121 rfid 系統(tǒng)組成 .5122 rfid 系統(tǒng)分類 .6123 rfid 系統(tǒng)工作原理 .613 rfid技術(shù)現(xiàn)狀

10、及其進(jìn)展 .7131 rfid技術(shù)應(yīng)用 .7132 rfid 標(biāo)準(zhǔn)統(tǒng)一化 .7133 rfid 防碰撞算法 .714 課題提出的背景及其意義 . .815 本文的主要工作 . .82 現(xiàn)有 rfid 二進(jìn)制樹防碰撞算法.921 rfid防碰撞算法概述 .922 rfid二進(jìn)制樹防碰撞算法概述 .9221 基本概念 .9222 性能指標(biāo) .10223 算法分類 .1123 基本二進(jìn)制樹防碰撞算法 . .12231 算法思路 .12232 實例演示 .13233 性能評判 .1524 動態(tài)二進(jìn)制樹防碰撞算法 . .16241 算法思路 .16242 實例演示 .17243 性能評判 .1825 退

11、避式二進(jìn)制樹防碰撞算法. .18251 算法思路 .18252 實例演示 .19253 性能評判 .2026 本章小結(jié) . .213 改進(jìn)型二進(jìn)制樹防碰撞算法.2131 涉及二進(jìn)制樹算法的國際標(biāo)準(zhǔn) . .21311 is0 15693 . .21312 is014443 . .2132 is014443 標(biāo)準(zhǔn)二進(jìn)制樹防碰撞算法.22321 基本概念 .22322 算法思路 .2333 改進(jìn)型二進(jìn)制樹防碰撞算法. .26331 改進(jìn)方向 .26332 基本概念 .錯誤. 未定義書簽；334 實例演示 .錯誤. 未定義書簽；34 本章小結(jié) . .錯誤. 未定義書簽；4 fpga實現(xiàn)改進(jìn)型二進(jìn)制樹防

12、碰撞算法 .錯誤. 未定義書簽；41 fpga技術(shù) .錯誤. 未定義書簽；411 fpga簡介 .錯誤. 未定義書簽；412 fpga設(shè)計流程 .錯誤. 未定義書簽；413 fpga設(shè)計工具 .錯誤. 未定義書簽；414 fpga設(shè)計語言 .錯誤. 未定義書簽；415 testbench 驗證平臺 .錯誤. 未定義書簽；42 rfid系統(tǒng)中的防碰撞模塊 .錯誤. 未定義書簽；43 fpga實現(xiàn)算法流程 .錯誤. 未定義書簽；44 曼徹斯特解碼模塊 . .錯誤. 未定義書簽；45 命令處理模塊 . .錯誤. 未定義書簽；451 懇求命令處理 .錯誤. 未定義書簽；452 防碰撞命令處理 .錯誤.

13、 未定義書簽；453 挑選命令處理 .錯誤. 未定義書簽；454 去挑選命令處理 .錯誤. 未定義書簽；46 命令挑選模塊 . .錯誤. 未定義書簽；47 數(shù)據(jù)儲備模塊 . .錯誤. 未定義書簽；48 密勒編碼模塊 . .錯誤. 未定義書簽；49 模塊連接 . .錯誤. 未定義書簽；410 本章小結(jié) .錯誤. 未定義書簽；結(jié)論 .錯誤. 未定義書簽；致謝 .錯誤. 未定義書簽；1 引言1.1 rfid 技術(shù)簡介自動設(shè)備識別技術(shù)是目前國際上進(jìn)展很快的一項新技術(shù)，英文名稱為 automatic equipment identif ication，簡稱 aei，它通過一些先進(jìn)的技術(shù)手段，實現(xiàn)人們對各

14、種設(shè)備在不同狀態(tài)下的自動識別和治理【 ll 】；目前，應(yīng)用最廣泛的自動識別技術(shù)大致可以分為光學(xué)技術(shù)和無線電技術(shù)兩種，其中光學(xué)技術(shù)普遍應(yīng)用于條形碼和攝像兩大類，而無線電技術(shù)在自動識別領(lǐng)域的應(yīng)用更具體的名稱為射頻識別，英文名為 radio frequency identification，簡寫為 rfidi21；rfid 技術(shù)通過射頻方式進(jìn)行非接觸的雙向通信，達(dá)到自動識別的目的，它源起于上世紀(jì)四五十歲月，最初是基于雷達(dá)與微波理論的進(jìn)展，自從上世紀(jì)九十歲月以來，rfid 技術(shù)快速進(jìn)展，得到了廣泛的應(yīng)用，進(jìn)入新世紀(jì)后，各個國家，組織仍有企業(yè)都加大了對rfid 技術(shù)的投入，生產(chǎn)了大批相應(yīng)的產(chǎn)品，在多個領(lǐng)

15、域有了勝利的應(yīng)用案例；rfid 被譽為二十一世紀(jì)的十大戰(zhàn)略性產(chǎn)業(yè)之一，可以預(yù)想，將來 rfid 技術(shù)的進(jìn)展空間是無限寬闊的；1.2 rfid 系統(tǒng)1.2.1 rfid 系統(tǒng)組成依據(jù)實際應(yīng)用環(huán)境， rfid系統(tǒng)結(jié)構(gòu)有多種不同分法， 一般來說， 一個典型 rfid系統(tǒng)包括三個部分：前端信息載體，數(shù)據(jù)交換環(huán)節(jié)，后端應(yīng)用環(huán)境【3】；在具體應(yīng)用中，前端信息載體有多個名稱，如標(biāo)簽 tag ，智能標(biāo)簽 smart labels，射頻卡 rf card 等，本文建議采納應(yīng)答器transponder 這種更具普遍意義的說法；在rfid 系統(tǒng)中，應(yīng)答器放置在待識別的物體上， 它內(nèi)部儲備的信息表征著該物品的獨一性；

16、通常來說，應(yīng)答器由耦合元件和微電子芯片組成，主要電氣性能為工作頻率，讀寫才能，數(shù)據(jù)傳輸率，信息數(shù)據(jù)儲備量，防碰撞才能，信息安全性能等，應(yīng)答器的分類也是以這些性能為依據(jù)的，例如依據(jù)儲備器可將應(yīng)答器分為eepro，mfrom鐵電儲備器 ，sram靜態(tài)隨機儲備器 ，依據(jù)信息注入方式可分為集成電路固化，現(xiàn)場線改寫，現(xiàn)場無線改寫，依據(jù)電源供應(yīng)方式分為無源，半無源，有源；一般來說，應(yīng)用最廣泛的是無源+集成電路固化 +靜態(tài)隨機儲備的應(yīng)答器；由于在rfid 系統(tǒng)中，應(yīng)答器是大規(guī)模生產(chǎn)的； 應(yīng)答器的典型產(chǎn)品有 ti 公司的 6000 系列， philips公司的 i code等；數(shù)據(jù)交換環(huán)節(jié)即rfid系統(tǒng)中的讀

17、出寫入設(shè)備，它是系統(tǒng)的核心部件，是后端應(yīng)用環(huán)境和前端信息載體的數(shù)據(jù)通道，在實際應(yīng)用中，往往被稱為查詢器，掃描器，閱讀器，編程器等，本文建議采納讀寫器readwrite device 這種更具普遍意義的說法，這樣既包括了從應(yīng)答器中讀出信息，同時也包括了向應(yīng)答器中寫入信息；依據(jù)天線與讀寫器模塊的分別與否，讀寫器可以分為分別式和集成式，但無論哪種讀寫器，其基本結(jié)構(gòu)都是類似的，從硬件部分來說，典型的讀寫器由三塊組成：射頻通道模塊，掌握處理模塊，天線；后端應(yīng)用環(huán)境主要完成數(shù)據(jù)信息的儲備及處理，它實質(zhì)上就是一個數(shù)據(jù)治理系統(tǒng)，也是一個全局掌握系統(tǒng)，一般由pc機或者工作站組成，同時也包括了應(yīng)用軟件在內(nèi)，整個后

18、端應(yīng)用環(huán)境負(fù)責(zé)接收來自讀寫器的數(shù)據(jù)，并進(jìn)行儲備以及相應(yīng)的處理，協(xié)同調(diào)劑多個讀寫器的工作，該部分在應(yīng)用中常稱為中間件 savant ，它擴展了 rfid系統(tǒng)的應(yīng)用范疇和應(yīng)用才能，是將來 rfid 系統(tǒng)智能化，大型化進(jìn)展的有力技術(shù)支撐，是 rfid 技術(shù)進(jìn)展的重要方式；微軟公司近年來也介入了rfid技術(shù)領(lǐng)域，所瞄準(zhǔn)的就是 rfid系統(tǒng)后端應(yīng)用的相關(guān)軟件和服務(wù)；綜上所述，一個典型的 rfid 系統(tǒng)的組成如下列圖：圖 1.1 rfid系統(tǒng)組成1.2.2 rfid 系統(tǒng)分類rfid系統(tǒng)依據(jù)不同的標(biāo)準(zhǔn)， 可以分為很多類別， 各個不同的 rfid系統(tǒng)， 在工作方式和應(yīng)用范疇上，有著各自不同的特點，在應(yīng)用時要

19、依據(jù)實際需要來挑選；幾種典型的分類方式如下所示：依據(jù)作用距離的遠(yuǎn)近， rfid系統(tǒng)可以分為如下三個方面：(1) 密耦合：典型的作用范疇為 0lcm；(2) 遙耦合：典型的作用范疇為 lcm1m；(3) 遠(yuǎn)距離系統(tǒng)：典型的作用范疇為l 10m；依據(jù)工作頻率的大小， rfid系統(tǒng)可以分為如下四個方面：(1) 低頻： 30300khz，典型應(yīng)用為 134khz；(2) 高頻： 330mhz，典型應(yīng)用為 1356mhz(3) 超高頻： 300mhz5 8ghz，典型應(yīng)用為 24g；(4) 混頻：多個頻率的混合使用，典型應(yīng)用為134khz+430mh；z依據(jù)應(yīng)答器供電方式， rfid系統(tǒng)可以分為三個方面

20、：(1) 無源系統(tǒng)：由讀寫器負(fù)責(zé)給應(yīng)答器供電；(2) 半無源系統(tǒng)：應(yīng)答器內(nèi)的電池僅做幫助作用；(3) 有源系統(tǒng)：應(yīng)答器內(nèi)置電池負(fù)責(zé)供應(yīng)工作電壓；1.2.3 rfid 系統(tǒng)工作原理rfid 是一門多學(xué)科綜合技術(shù)，涉及到電磁場理論，數(shù)字電路，模擬電路，無線電廣播，通信原理等多方面學(xué)問 rfld 系統(tǒng)中，讀寫器將要發(fā)送的信號調(diào)制到載波上，經(jīng)由射頻通道，通過天線發(fā)送出去，應(yīng)答器上的電壓依據(jù)載波的變化而變化，將該電壓信號進(jìn)行整流和濾波后，得 到解調(diào)后的數(shù)據(jù)，這是下行鏈路的過程，應(yīng)答器傳輸?shù)臄?shù)據(jù)的變化掌握應(yīng)答器天線上負(fù)載電阻 的通斷，從而促使讀寫器天線上電壓的變化，從而實現(xiàn)了數(shù)據(jù)的上行鏈路傳輸；在數(shù)據(jù)的雙

21、向 傳輸過程中，是通過電磁場的相互感應(yīng)來實現(xiàn)的，該過程也可以用變壓器的模型來予以參考； 同時，依據(jù) rfid系統(tǒng)的不同，在供電方式上有無源或者有源，調(diào)制方式上有幅度調(diào)制或者相位調(diào)制，數(shù)據(jù)讀取上有電感耦合或者反向散射等區(qū)分【5】；1.3 rfid 技術(shù)現(xiàn)狀及其進(jìn)展1.3.1 rfid 技術(shù)應(yīng)用做為一種新興的自動識別技術(shù)，rfid近年來進(jìn)展很快，在國內(nèi)國外都取得了廣泛的應(yīng)用，主要表達(dá)在以下幾個領(lǐng)域【6】；(1) 物流治理 物流治理是 rfid 技術(shù)最具應(yīng)用前景的領(lǐng)域，近年來提出了一個物聯(lián)網(wǎng)的概念，意在將全球全部的物品信息都用唯獨的電子代碼來表示，從而將這些物品都聯(lián)系在一起，可以隨時隨地的 識別，追

22、蹤，治理這些物品，最終在產(chǎn)品，用戶，企業(yè)和政府之間建立但是該應(yīng)用涉及到的方 面太廣，技術(shù)難度很大，目前仍在爭論當(dāng)中；(2) 身份識別利用 rfid 技術(shù)，將應(yīng)答器嵌入到身份證，護照等各種證件當(dāng)中，甚至植入動物皮毛，用來跟蹤和識別目標(biāo)； 這方面應(yīng)用的典型例子是我國目前實行的二代身份證，它基于 iso iec14443 標(biāo)準(zhǔn)定義的 type b 類型卡； rfid 在身份識別方面的主要問題是頻段的局限性，一般使用的是l35khz 和 1356mhz的工作頻率，這是由于過高的頻段簡潔帶來對人體有害的電磁輻射；(3) 防偽應(yīng)用應(yīng)答器在防偽應(yīng)用中有識別快速，偽造難，成本低等優(yōu)點，再加上安全認(rèn)證和加密功能

23、， 就可以大大提高偽造的難度和成本，同時，在識別的時刻，可以通過讀寫器的快速閱讀功能， 在瞬時得出全部物品的信息，并加以記錄和處理；目前在日本和歐洲已經(jīng)有了類似的應(yīng)用；(4) 交通治理交通治理是 rfid 最先應(yīng)用的領(lǐng)域，目前已經(jīng)擁有了成熟的技術(shù)，它利用了應(yīng)答器便利快速識別，牢靠性高，安全性強的特點，目前主要應(yīng)用范疇是電子車票，高速大路收費等方面，在我國深圳，基于 rfid技術(shù)的高速大路收費系統(tǒng)已經(jīng)得到了勝利的應(yīng)用；rfid 技術(shù)的應(yīng)用遠(yuǎn)不止以上提及的四個方面，它在諸如生產(chǎn)線自動化治理，門禁系統(tǒng)，新生嬰兒防錯治理，地理信息標(biāo)識等多個方面都有著廣泛應(yīng)用，可以毫不夸張的說，rfid 技術(shù)有著良好的

24、進(jìn)展前景，它孕育的經(jīng)濟效益將是超乎想像的；1.3.2 rfid 標(biāo)準(zhǔn)統(tǒng)一化rfid 最初是各個廠家在各自的獨立標(biāo)準(zhǔn)下開發(fā)出來的，缺乏統(tǒng)一的規(guī)范，因此制約了該項技術(shù)在大規(guī)模系統(tǒng)中的應(yīng)用，隨著rfid 技術(shù)的進(jìn)展，參加到其中的國家，組織，企業(yè)也越來越多，目前形成了國際標(biāo)準(zhǔn)化組織iso，泛在 id 中心 uid，全球電子產(chǎn)品代碼治理中心 epc三大標(biāo)準(zhǔn)體系，這些標(biāo)準(zhǔn)涉及到 rfid 系統(tǒng)的物理結(jié)構(gòu)，通信協(xié)議，防碰撞算法，應(yīng)用系統(tǒng)接口協(xié)議等等多個方面的內(nèi)容，它們針對不同的頻率，基于不同的工作原理，甚至在同樣的應(yīng)用背景下也有著龐大的協(xié)議上的區(qū)分；而要建立一個全球互聯(lián)的rfid 產(chǎn)品網(wǎng)絡(luò)，實現(xiàn) rfid

25、技術(shù)的飛躍進(jìn)展，就必需解決標(biāo)準(zhǔn)不統(tǒng)一的難題，近年來，隨著rfid 技術(shù)的應(yīng)用更加廣泛，有識之士都意識到并著手解決這個問題，目前主要有兩種思路，一是生產(chǎn)出適應(yīng)于不同標(biāo)準(zhǔn)，多制式兼容的 rfid 產(chǎn)品，二是制定一個統(tǒng)一的 rfid 碩十學(xué)位論技術(shù)標(biāo)準(zhǔn)；但是rfid 本身的技術(shù)難度，以及標(biāo)準(zhǔn)帶來的經(jīng)濟利益的沖突，使得該目標(biāo)實施起來特別困難；由此可見，標(biāo)準(zhǔn)統(tǒng)一化問題的重要性與困難性是并存的，這將是一個任重而道遠(yuǎn)的過程；1.3.3 rfid 防碰撞算法隨著 rfid 技術(shù)的進(jìn)展，多目標(biāo)識別成為了一個很重要的應(yīng)用方向，特殊在目標(biāo)跟蹤，物品識別，拜訪掌握等操作中， 利用 rfid 技術(shù)，對附著在不同目標(biāo)上的

26、應(yīng)答器快速牢靠的進(jìn)行識別， 從而大大提高了定位的精確度，治理的自動化促進(jìn)了整個產(chǎn)業(yè)鏈的進(jìn)展；因此，如何保證快速快捷，又安全牢靠的同時識別多個目標(biāo)，就成為了rfid 技術(shù)進(jìn)展的關(guān)鍵性技術(shù)；在 rfid 系統(tǒng)中，當(dāng)工作范疇內(nèi)同時顯現(xiàn)了多個讀寫器和多個應(yīng)答器時，讀寫器與讀寫器之間，應(yīng)答器與應(yīng)答器之間的相互干擾，稱rfid 系統(tǒng)發(fā)生了碰撞【 7】，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產(chǎn)品的識別，另一方面仍可能導(dǎo)致信息的泄露；在全球信息安全意識廣泛普及的背景下，牢靠的安全機制成為了rfid 技術(shù)進(jìn)展的關(guān)鍵性制約因素，如何有效的解決 rfid 系統(tǒng)的碰撞問題，成為了技術(shù)的關(guān)鍵，

27、對此就需要采納肯定的防碰撞算法來對其進(jìn)行處理；目前關(guān)于防碰撞算法的爭論仍在進(jìn)行當(dāng)中，理論成果已經(jīng)得出了很多，很多國際標(biāo)準(zhǔn)也對一些成熟的算法進(jìn)行了規(guī)定，但是無論在理論效率仍是實際應(yīng)用上，都仍存在很大的改進(jìn)空間；1.4 課題提出的背景及其意義早期的 rfid 技術(shù)很少涉及到防碰撞問題，而在近年來，隨著rfid 技術(shù)的進(jìn)展，應(yīng)用范疇的擴大， 使得防碰撞問題日益成為制約 rfid進(jìn)展的關(guān)鍵技術(shù)，緣由有兩個，第一，早期的rfid 一般是近距離感應(yīng)耦合式系統(tǒng)，其操作頻率功率普遍較低，讀取的速度慢，范疇小，所以也較少有發(fā)生碰撞的可能，而目前 rfid 應(yīng)用中多目標(biāo)識別成為了主流方向，這就要求實現(xiàn)在多個物品中

28、正確的識別出單個目標(biāo)；其次，早期的rfid 應(yīng)用沒有統(tǒng)一的規(guī)范，各個廠家的rfid 產(chǎn)品也僅是應(yīng)用在單個的系統(tǒng)當(dāng)中， 不存在碰撞的可能， 而近年來 rfid應(yīng)用快速進(jìn)展，各個不同 rfid 制造商的產(chǎn)品之間的不兼容，也帶來了碰撞問題；總之，由于多目標(biāo)識別應(yīng)用的需要，rfid 系統(tǒng)防碰撞問題成為了關(guān)鍵技術(shù)，為明白決碰撞，可以從硬件和軟件兩方面著手，由于rfid 系統(tǒng)的大規(guī)模應(yīng)用限制了成本，所以，硬件實現(xiàn)是不實際的，因此就需要采納肯定的防碰撞算法來予以解決；依前所述， rfid 系統(tǒng)碰撞主要有兩種情形，讀寫器碰撞和應(yīng)答器碰撞，讀寫器碰撞是一個應(yīng)答器同時收到不同讀寫器發(fā)出的命令，應(yīng)答器碰撞是一個讀寫

29、器同時給不同應(yīng)答器發(fā)送命令；在實際的應(yīng)用當(dāng)中，應(yīng)答器由于其低成本的優(yōu)越, 從而得到大量的生產(chǎn)，而讀寫器往往是固定在系統(tǒng)的某處，來識別多個應(yīng)答器，所以碰撞的主要情形是應(yīng)答器碰撞，即一個讀寫器的工作范疇內(nèi)同時顯現(xiàn)了多個應(yīng)答器，并且對該讀寫器發(fā)出的命令同時予以響應(yīng)，從而導(dǎo)致讀寫器無法正確的識別出一個應(yīng)答器，稱該現(xiàn)象為發(fā)生了應(yīng)答器碰撞；解決碰撞的過程相應(yīng)的被稱為防碰撞，如前所述，該防碰撞過程主要從軟件的角度來予以解決，稱為防碰撞算法【8】；在上述前提下，基于應(yīng)答器的確定型二進(jìn)制樹防碰撞算法是目前最好的一種挑選，對其進(jìn)行爭論，是最有實際應(yīng)用價值的，所以，本文將對其進(jìn)行理論分析與具體實現(xiàn)，在爭論過程中，留

30、意與新一代智能 rfid 系統(tǒng)的結(jié)合，應(yīng)用擁有強大功能的fpgafieldprogrammable gatearray 做為算法運行的微處理器， 這種思路將是將來 rfid技術(shù)進(jìn)展的重要方向， rfid 技術(shù)中的關(guān)鍵算法與先進(jìn)的電子技術(shù)fpga的結(jié)合，將為 rfid 技術(shù)的應(yīng)用拓開寬闊的前景；1.5 本文的主要工作本文將在 rfid 技術(shù)的前提下，結(jié)合當(dāng)前數(shù)字電路設(shè)計的主流思路，重點爭論rfid 的關(guān)鍵技術(shù)防碰撞算法，并主要著眼于其中基于應(yīng)答器的確定性算法，即二進(jìn)制樹防碰撞算法，在理論分析的基礎(chǔ)上，對其進(jìn)行具體實現(xiàn)；基于上述考慮，論文將分四章來予以敘述，文章結(jié)構(gòu)與內(nèi)容支配如下：第 1 章：緒論

31、；系統(tǒng)的介紹了 rfid 技術(shù)，描述了典型 rfid系統(tǒng)的結(jié)構(gòu)組成，提出了 rfid 系統(tǒng)的分類思想，敘述了 rfid 系統(tǒng)的工作原理，以及其應(yīng)用范疇，重點強調(diào)了rfid 技術(shù)的現(xiàn)狀和所面臨的主要問題，由此表達(dá)了爭論rfid 關(guān)鍵技術(shù)防碰撞算法的意義，明確了本文的主要爭論內(nèi)容；第 2 章：現(xiàn)有 rfid 二進(jìn)制樹防碰撞算法；概要性的描述了rfid 防碰撞算法，對其進(jìn)行了分類，重點介紹其中的二進(jìn)制樹防碰撞算法，爭論了三種最基本的二進(jìn)制樹算法，對其進(jìn)行了原理闡述，性能分析，以及實例演示；第 3 章：改進(jìn)型二進(jìn)制樹防碰撞算法；二進(jìn)制樹防碰撞算法在多個國際標(biāo)準(zhǔn)中均有規(guī)定，基于 is014443 標(biāo)準(zhǔn)的

32、 typea是其中的一個典型例子， 本章第一介紹了涉及到二進(jìn)制樹防碰撞算法的幾個標(biāo)準(zhǔn)，其次具體爭論了 isol4443 標(biāo)準(zhǔn)對二進(jìn)制樹防碰撞算法的規(guī)定，最終提出了在此基礎(chǔ)上的改進(jìn)算法，這也是本章的重點；第 4 章：fpga實現(xiàn)改進(jìn)型二進(jìn)制樹防碰撞算法； fpga技術(shù)是目前數(shù)字電路設(shè)計的主流思路， 利用 fpga做主處理器，是 rfid技術(shù)進(jìn)展的方向，本章探討了這一想法，介紹了fpga技術(shù)的相關(guān)要點，并應(yīng)用 fpga，實現(xiàn)了改進(jìn)型二進(jìn)制樹防碰撞算法；2 現(xiàn)有 rfid 二進(jìn)制樹防碰撞算法2.1 rfid 防碰撞算法概述rfid系統(tǒng)的數(shù)據(jù)通信雙方是讀寫器和應(yīng)答器， 在實際的 rfid 系統(tǒng)工作時，

33、 可能會顯現(xiàn)同時多個讀寫器和多個應(yīng)答器共存的情形，毫無疑問，此時系統(tǒng)的數(shù)據(jù)交換就會顯現(xiàn)信道與時序上的重疊，也就是發(fā)生了碰撞，在多個讀寫器與多個應(yīng)答器的射頻識別系統(tǒng)中，存在著兩種形式的沖突方式，一種是同一應(yīng)答器同時收到不同讀寫器發(fā)出的命令，另一種是同一個讀寫器同時收到多個不同應(yīng)答器返回的數(shù)據(jù)，前者我們稱為讀寫器碰撞，后者稱為應(yīng)答器碰撞【9】，在實際應(yīng)用當(dāng)中，一般是讀寫器做為主設(shè)備，來識別多個應(yīng)答器，所以發(fā)生讀寫器碰撞的應(yīng)用場合是不多的，因此下文將著重爭論應(yīng)答器碰撞；在上述前提下，有兩種類型的通信方式，一種是讀寫器發(fā)送的數(shù)據(jù)同時被多個應(yīng)答器接收，稱為“無線廣播”，另一種是多個應(yīng)答器的數(shù)據(jù)同時傳送給

34、讀寫器，稱為“多路存取”，兩者都是無線電技術(shù)中長期面臨的難題，同時也進(jìn)展出一系列相應(yīng)的解決思路，一般來說分為四種，即空分多路 sdma， 碼分多路 cdma,頻分多路 fdma，時分多路 tdma，從 rfid 系統(tǒng)的通信形式、功耗、系統(tǒng)復(fù)雜性以及成本多方面綜合考慮，時分多路法是最有實際應(yīng)用價值的，它也 是目前 rfid 防碰撞算法應(yīng)用中最廣泛的一類， 時分多路法的基本思想是把整個可供使用的通路容量按時間安排給多個用戶，從而達(dá)到在不同時隙將各個應(yīng)答器一一識別出來的目的【 11】；時分多路法依據(jù)能量的供應(yīng)者可以分為兩大類，一類是應(yīng)答器驅(qū)動型，另一類是讀寫器驅(qū)動型，這也正是對應(yīng)了第一章中rfid

35、系統(tǒng)分類思路中的有源系統(tǒng)和無源系統(tǒng)，依據(jù)實際應(yīng)用情形，無源系統(tǒng)是應(yīng)用最廣泛的一類，所以下文重點爭論讀寫器驅(qū)動型的時分多路法；在該類讀寫器驅(qū)動型時分多路法中，目前最常用的防碰撞算法有兩種，一類是基于時隙 aloha的統(tǒng)計型算法，另一類是基于二進(jìn)制樹的確定型算法，統(tǒng)計型算法的意義是在肯定的時隙范疇內(nèi)，系統(tǒng)有可能識別出全部應(yīng)答器，確定型算法的最大優(yōu)點是，在肯定的時隙范疇內(nèi)，系統(tǒng)肯定可以將全部的應(yīng)答器一一識別出來【13】；從應(yīng)用的角度來說，正確有效的識別是實際所需要的，因此下文將著重于二進(jìn)制樹防碰撞算法的爭論；2.2 rfid 二進(jìn)制樹防碰撞算法概述2.2.1 基本概念在 rfid 防碰撞算法中，二進(jìn)

36、制樹算法是目前應(yīng)用最廣泛的一種，之所以稱為“二進(jìn)制樹”， 是由于在算法執(zhí)行過程中，讀寫器要多次發(fā)送命令給應(yīng)答器，每次命令都把應(yīng)答器分成兩組，多次分組后最終得到唯獨的一個應(yīng)答器，在這個分組過程中，將對應(yīng)的命令參數(shù)以節(jié)點的形式 儲備起來，就可以得到一個數(shù)據(jù)的分叉樹，而全部的這些數(shù)據(jù)節(jié)點又是以二進(jìn)制的形式顯現(xiàn)的， 所以稱為“二進(jìn)制樹” ；為了便于描述算法，聲明一些基本概念如下：第一，在rfid系統(tǒng)當(dāng)中，每個應(yīng)答器都是獨一無二的，它們的獨立性通過唯獨的自身序列號來表達(dá)，該序列號在不同的標(biāo)準(zhǔn)中有不同的名稱，如 epc標(biāo)準(zhǔn)中稱其為電子產(chǎn)品代碼 epc，即英文 electronicproductcode的縮

37、寫， is014443 標(biāo)準(zhǔn)中稱其為唯獨標(biāo)識碼 uid，即英文 unique identmer的縮寫【 15】；事實上，這些都是對應(yīng)答器序列號的名稱描述，由于下文涉及到的防碰撞算法是普遍意義上的，既包括了epc標(biāo)準(zhǔn)中的規(guī)定，也包括了 iso 標(biāo)準(zhǔn)中的規(guī)定，因此在本文對普遍意義上的防碰撞算法的描述過程中，統(tǒng)一用序列號 snserialnumber 來描述上述概念，同時，序列號的長度，格式，以及編碼方式也是各個標(biāo)準(zhǔn)各自差異的，為了說明的便利，統(tǒng)肯定義為8 位長度的二進(jìn)制碼；如圖 21 所示；圖 2 1 應(yīng)答器序列號數(shù)據(jù)格式讀寫器與應(yīng)答器之間進(jìn)行數(shù)據(jù)交換時，往往要傳輸序列號的部分或者全部位，此時的傳

38、輸次序定義為：先發(fā)送低位，再發(fā)送高位；在讀寫器或者應(yīng)答器內(nèi)部，對數(shù)據(jù)進(jìn)行比較時，遵循這樣的原就，即按位依次比較，先比較低位，再比較高位，商定01，依據(jù)這個比較次序，在判定大小時，低位數(shù)據(jù)優(yōu)先，即兩數(shù) a，b 相比較，從低位開頭的第一個不相等位的大小打算了兩數(shù)的大小，只有當(dāng)兩個數(shù)的全部位均相等時，兩數(shù)才相等；2.2.2 性能指標(biāo)定義碰撞解決時期cri，即 collision resolution interval【16】，即解決一個讀寫器工作范疇內(nèi)碰撞所需要的時隙數(shù)，對二進(jìn)制樹算法的評判，一些常用的性能指標(biāo)如下所示【17】：第一是算法執(zhí)行效率，定義如下：在算法執(zhí)行過程，一共個時隙，識別了 n 個

39、應(yīng)答器， 就 =n/表示算法的執(zhí)行效率；分析如下： n=l ，顯而易見，在第一個時隙內(nèi)不發(fā)生碰撞，可以勝利識別該應(yīng)答器，=1；n 2，由于應(yīng)答器序列號的唯獨性，將有碰撞發(fā)生，在一個時隙內(nèi)發(fā)生碰撞的概率p 是一個隨機大事，在 n 個應(yīng)答器信息包中 i 個發(fā)生碰撞的概率為：給出 i 個碰撞，就 cri 的長度為：其中 1 是 n 個信息包最初的一個時隙，是 i 個碰撞的順當(dāng)傳輸?shù)臅r隙，是 n-i個無碰撞傳輸?shù)臅r隙；由上式可知，是逐步遞歸的，通過遞歸可得：依據(jù)式 2.3 ，上式可化為：由此可見，是關(guān)于 p 的函數(shù)，就 =n/也是關(guān)于 p 的函數(shù)，一般情形下，可以參考二項分布，將 p 取為 12；算法

40、的其次個重要的性能指標(biāo)是穩(wěn)固性，明顯，基于tdma的二進(jìn)制樹防碰撞算法是沿著時間軸線來執(zhí)行協(xié)議的，有一系列的碰撞解決時期cri，定義一個隨機變量，表示第 k 個 cri 的長度，這些形成一個馬爾可夫鏈 markovchain ，由于第個 cri 的長度由它開頭的第一個時隙傳輸?shù)男畔?，也就是在k 個 cri 區(qū)間內(nèi)到達(dá)的信息包打算的，所以， 假如馬爾可夫鏈滿意遍歷性分布，那么這個系統(tǒng)就可以說是穩(wěn)固的；馬爾可夫鏈遍歷性分布要滿意以下兩個條件【18】：這里有：. 也就是 n 個信息包從發(fā)生碰撞開頭傳輸?shù)?cri 區(qū)間長度的數(shù)學(xué)期望， 是在一個時隙內(nèi)到達(dá)這個系統(tǒng)信息包的期望值，該過程屬于泊松過程【 l

41、9 】；一般來說，在二進(jìn)制樹防碰撞算法中，系統(tǒng)都能夠滿意馬爾可夫鏈的兩個遍歷性分布條件，即作為一種確定型的算法，二進(jìn)制樹防碰撞算法是穩(wěn)固的；算法的第三個重要性能是系統(tǒng)通信復(fù)雜度，顯而易見，系統(tǒng)的通信雙方是讀寫器與應(yīng)答器，就通信復(fù)雜度也應(yīng)當(dāng)從這兩方面著手考慮，即讀寫器與應(yīng)答器各自發(fā)送的數(shù)據(jù)位的位數(shù)；該指標(biāo)的評判標(biāo)準(zhǔn)是基于能量消耗的角度的，即發(fā)送的數(shù)據(jù)信息量越少，就整個系統(tǒng)消耗的能量也越少，這明顯是一個抱負(fù)的成效；2.2.3 算法分類在基本的二進(jìn)制樹搜尋算法的基礎(chǔ)上，有多種形式的二進(jìn)制樹搜尋算法，它們之間主要的區(qū)分在于命令的數(shù)據(jù)形式，主要有兩點；(1) 命令參數(shù)是 1bit數(shù)據(jù)，仍是多 bit數(shù)據(jù)

42、；(2) 命令參數(shù)長度是固定的，仍是變化的；圖 22 是一個二進(jìn)制樹搜尋算法的分類圖，在基本二進(jìn)制樹的基礎(chǔ)上，依據(jù)命令參數(shù)分為1bit和多 bit ，依據(jù)傳輸?shù)拿顓?shù)的長度分為定長二進(jìn)制樹和動態(tài)二進(jìn)制樹兩種，依據(jù)二進(jìn)制樹遍歷時是一輪前進(jìn)究竟的仍是退避返回的分為前進(jìn)二進(jìn)制樹和退避二進(jìn)制樹兩種；需要說明的是，這只是一個大略的分類法，主要目的在于說明二進(jìn)制樹分類的基本原就；事實上，分類所得的這些算法中也有相互重合的，如動態(tài)二進(jìn)制樹算法既可以采納前進(jìn)思路，也可以采納退避思路；另外，在具體應(yīng)用時，可能仍存在多種不同的說法，如lbit長二進(jìn)制樹中仍有修正二進(jìn)制樹 mbbt，加強二進(jìn)制樹 ebbt等區(qū)分【

43、 20】；圖 2 2 二進(jìn)制樹算法分類2.3 基本二進(jìn)制樹防碰撞算法2.3.1 算法思路定義兩個具有普遍意義的命令來描述算法：(1) 懇求命令 requestsn ：該命令攜帶一個參數(shù) sn，應(yīng)答器接收到該命令，將自身的sn 與接收到的 sn比較，如小于或者等于，就該應(yīng)答器回送其sn給讀寫器；注： requestsn 初始值設(shè)為 request11111111 ；(2) 休眠命令 sleepsn ：該命令攜帶一個參數(shù) sn，應(yīng)答器接收到該命令，將自身的sn與接收到的 sn比較，如等于， 就該應(yīng)答器被選中， 進(jìn)入休眠狀態(tài)， 也即是不再響應(yīng) request 命令， 除非該應(yīng)答器通過先離開讀寫器工作

44、范疇再進(jìn)入的方式重新上電，才可以再次響應(yīng)request 命令；基本二進(jìn)制樹算法的流程圖如圖 23 所示：圖 2 3 基本二進(jìn)制樹算法流程基本二進(jìn)制樹算法的步驟如下：(1) 應(yīng)答器進(jìn)入讀寫器工作范疇，讀寫器發(fā)出一個最大序列號，全部應(yīng)答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號返回給讀寫器；(2) 由于應(yīng)答器序列號的唯獨性，當(dāng)應(yīng)答器數(shù)目不小于兩個時，必定發(fā)生碰撞發(fā)生碰撞時，將最大序列號中對應(yīng)的碰撞起始位設(shè)置為o，低于該位者不變，高于該位者設(shè)置為l ；(3) 讀寫器將處理后的序列號發(fā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，小于或等于該值者，將自身序列號返回給讀寫器；(4) 循環(huán)這個過程，就

45、可以選出一個最小序列號的應(yīng)答器，與該應(yīng)答器進(jìn)行正常通信后，發(fā)出命令使該應(yīng)答器進(jìn)入休眠狀態(tài)，即除非重新上電，否就不再響應(yīng)讀寫器懇求命令；也就是說，下一次讀寫器再發(fā)最大序列號時，該應(yīng)答器不再響應(yīng)；(5) 重復(fù)上述過程，即可按序列號從小到大依次識別出各個應(yīng)答器；注：第五步時，從步驟 1 開頭重復(fù)，也就是說，讀寫器識別完一個應(yīng)答器后，將重新發(fā)送原始的最大序列號；2.3.2 實例演示依據(jù)上述分析，下面給出一個基本二進(jìn)制樹搜尋算法的實例演示，如圖24所示；假設(shè) rfid 系統(tǒng)中有一個讀寫器 r，四個應(yīng)答器 tl10100101 ， t2 10l01101 ，t311010101 ，t411101101 ，

46、在某一時刻，四個應(yīng)答器同時進(jìn)入讀寫器的工作范疇之內(nèi)，讀寫器發(fā)出命令，四個應(yīng)答器同時響應(yīng)，由于其序列號 sn的唯獨性，將發(fā)生應(yīng)答器碰撞，從而啟動防碰撞循環(huán)，分析如下：圖 2.4基本二進(jìn)制樹算法實例注：圖中共有四輪循環(huán)，依次識別出四個應(yīng)答器，分別以不同格式的線條表示，并加有循環(huán)輪次的數(shù)字標(biāo)識；(1) 啟動第一輪循環(huán)，讀寫器發(fā)送 request1lll1111命令，全部應(yīng)答器響應(yīng)當(dāng)命令，將自身序列號與該 sn1l1l1111 比較，均小于該值，于是全部應(yīng)答器均返回自身序列號給讀寫器， 由于序列號的唯獨性，應(yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為 lxxxxl0l ，其中 x表

47、示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位d4 位置 0，低于該位者不變，高于該位者置l ，得到 11ll0l01，作為下一次 request 命令攜帶的參數(shù)值，即request11110l01 ；(2) 讀寫器發(fā)送 request11110101 命令，全部應(yīng)答器響應(yīng)當(dāng)命令，將自身序列號與該sn11110l01 比較，其中 t110l00101 ，t31l010101 的序列號小于該值，就 tl ，t3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為1xxx0l01，讀寫器做如下處理：將碰撞起始位 d5 位置 0，低于該位者不變，高于該位者置l ，得到 11l0

48、0l01 ，作為下一次 request 命令攜帶的參數(shù)值，即 request11100101 ；(3) 讀寫器發(fā)送 request11100101 命令，全部應(yīng)答器響應(yīng)當(dāng)命令， 將自身序列號與該 sn11100l01 比較，其中 tl10100l01的序列號小于該值， 就 tl 返回自身序列號給讀寫器， 在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回數(shù)據(jù)為10100101，讀寫器做如下處理：將該數(shù)值作為下一次 sleep 命令攜帶的參數(shù)值，即 sleep10100101 ；(4) 讀寫器發(fā)送sleep10100101 命令，全部應(yīng)答器響應(yīng)當(dāng)命令，將自身序列號與該sn10l00111 比較，其中 t110l00101 的序列號等于該值，就t1 執(zhí)行該命令，進(jìn)入休眠狀態(tài)， 即除非重新上電，否就不再響應(yīng)request 命令；(5) 啟動其次輪循環(huán)，讀寫