通信工程畢業設計-rfid二進制樹防碰撞算法的研究與實現-wenkub.com

　 　

【正文】 有兩個主要特點，一是獨特的天線結構和技術，使其讀寫距離可以穩定地達到 10cm 以上，同時其天線結構中鑲嵌的特殊材料 (鐵氧體等材料 )使其天線電磁場的讀寫距離非常均勻，沒有“死區”現象出現，二是 SONY 非接觸智能卡數據寫操作失敗時的數據恢復功能。 TypeA 由 Philips 半導體公司首次開發和使用，在亞洲等地區， TypeA 技術和產品占據了很大的市場份額。 表 3． 1IS015693 數率 3． 1． 2 IS014443 ISO 是英文 InternationalOrganizationForStandardization 的簡寫，即國際標準化組織， IEC 是 InternationalElectromechanical Commission 的簡寫，即國際電子科技化委員會， JTC(JointTechCommittee)是 ISO 和 IEC 組成的一個聯合技術委員會，負責 ISO／ IEC 國際標準的起草、討論、修正、制定、表決和公布等具體事宜， JTC分為各個子委員會 SC(Submittee)，子委員會又分為各個工作組 WG(WorkGroup)，其中子委員會 SCl7 下的 WG8 負責 ISOl444 ISOl5693以及 ISOl5693 非接觸式智能卡標準具體起草、討論修正、制定、表決和最終 ISO國際標準的公布【 24】 。讀寫器應能確定用哪種方式。 2． 6 本章小結 本章歸納了現有的二進制樹防碰撞算法，將其分為三個基本類別，分別講述了其實現思路，進行了實例演示，并且對其做了性能分析，結果表明，動態算法和退避式算法是對基本算法的兩個改進思路，具有各自的優勢。 (3)讀寫器 發送 Request(11100101)命令，所有應答器響應，將自身序列號與 SN(1ll 00101)比較，其中 T1(10100101)序列號小于該值，則 Tl返回序列號，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 10100l01，做如下處理：將該值作為下一次 Sleep 命令參數值，即 Sleep(10100101)。低于該位者不變，高于該位者置 1。采用該返回思路的二進制樹算法，稱為退避式二進制樹算法。注： Request(SN)初始值設為 Request(11ll1111)。 2． 4． 3 性能評價 與 3． 3． 2基本二進制樹實例圖比較可知，動態二進制樹算法的識別過程中，節點數目，循環輪次都是一樣的，但是每次循環過程中，讀寫器命令與應答器指令所攜帶的參數都是在動態改變長度的，所以動態算法的優勢主要體現在兩個方面，一是算法執行過程中數據傳輸時間；二是算法執行過程中數據信息量。 (2)讀寫器發送 Request(0l01)命令，所有應答器響應，將自身序列號與該SN(0101)比較，其中 Tl(10l00101)， T3(110l0l01)的序列號低四位等于該值，則 T1， T3 返回剩余位給讀寫器，在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 lXXX，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數值，即 Request(00l01)。發生碰撞時，將最大序列號中對應的碰撞起始位置為 0。這兩種選擇方式并沒有本質區別，在本文中，采取其中的一種，即：讀寫器檢測到碰撞后，將碰撞起始位置 0，低位不變，從而將碰撞起始位 (置為 O)加低位作為新 Request 命令參數，應答器響應，從低位開始比較，若對應位等于該參數，則返回剩余位給讀寫器，如果只有 _個應答器響應，讀寫器檢 測到無碰撞發生，則將上一次發出的Request 命令參數與應答器返回的剩余位組合起來，作為新的 Sleep 命令參，該參數也即是剛剛做出響應的這個應答器的序列號。注：Request( )初始值設為 Request(1l111111)，約定當參數值為全 1時，應答器返回完整序列號。 (2)減少應答器分組的詢問次數。假設有 n個應答器，從讀寫器到應答器的傳輸時間為 tl，反之為 t2．總時間為 t，則傳輸的總時間 t 可以用式 來表示【 22】： 數 學歸納法證明如下： 假設只有一個應答器，則讀寫器發送命令，應答器響應，無碰撞，識別出應答器。根據前面的分析可知，做為一種確定性的算法，基本二進制樹一輪循環總能識別出一個應答器，所以在 n個應答器的前提下，經過 n次循環可以識別出 N 個應答器，所以整個過程中的循環次數為 n． 搜索次數 定義為算法執行命令的次數。 (11)啟動第四輪循環，讀寫器發送 Request(1l111111)命令，除 Tl， T3， T2外所有應答器響應該命令，將自身序列號與該 SN(11l1l111)比較，均小于該值，則所有應答器均返回自身序列號給讀寫器，因為只有應答器 T4 返回數據，所以在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 11101101，讀寫器做如下處理：將該數值作為下一次 Sleep 命令攜帶的參數值，即 Sleep(1l1 01101)。 (7)讀寫器發送 Sleep(1l010101)命令，所有應答器響應該命令，將自身序列號與該 SN(110l 0101)比較，其中 T3(11010101)的序列 號等于該值，則 T3 執行該命令，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。 (3)讀寫器發送 Request(11100101)命令，所有應答器響應該命令，將自身序列號與該 SN(111 00l01)比較，其中 Tl(10100l01)的序列號小于該值，則 Tl返回自身序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 10100101，讀寫器做如下處理：將該數值作為下一次 Sleep 命令攜帶的參數值，即 Sleep(10100101)。 2． 3． 2 實例演示 根據上述分析，下面給出一個基本二進制樹搜索算法的實例演示，如圖 2． 4 所示。 (4) 循環這個過程，就可以選出一個最小序列號的應答器，與該應答器進行正常通信后，發出命令使該應答器進入休眠狀態，即除非重新上電，否則不再響應讀寫器請求命令。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，也即是不再響應 Request 命令，除非該應答器通過先離開讀寫器工作范圍再進入的方式重新上電，才可以再次響應 Request 命令 。事實上，分類所得的這些算法中也有互相重合的，如動態二進制樹算法既可以采用前進思路，也可以采用退避思路。 (1)命令參數是 1bit 數據，還是多 bit 數據。一般來說， 在二進制樹防碰撞算法中，系統都能夠滿足馬爾可夫鏈的兩個遍歷性分布條件，即作為一種確定型的算法，二進制樹防碰撞算法是穩定的。 n≥ 2，由于應答器序列號的唯一性，將有碰撞發生，在一個時隙內發生碰撞的概率 p 是一個隨機事件，在 n 個應答器信息包中 i個發生碰撞的概率為： 給出 i個碰撞，則 CRI的長度為： 其中 1是 n個信息包最初的一個時隙， 是 i個碰撞的順利傳輸的時隙， 13 是 ni個無碰撞傳輸的時隙。 圖 2． 1 應答器序列號數據格式 讀寫器與應答器之間進行數據交換時，往往要傳輸序列號的部分或者全部位，此時的傳輸順序定義為：先發送低位，再發送高位。 2． 2 RFID 二進制樹防碰撞算法概述 2． 2． 1 基本概念 在 RFID 防碰撞算法中，二進制樹算法是目前應用最廣泛的一種 ，之所以稱為“二進制樹”，是因為在算法執行過程中，讀寫器要多次發送命令給應答器，每次命令都把應答器分成兩組，多次分組后最終得到唯一的一個應答器，在這個分組過程中，將 對應的命令參數以節點的形式存儲起來，就可以得到一個數據的分叉樹，而所有的這些數據節點又是以二進制的形式出現的，所以稱為“二進制樹”。 在上述前提下，有兩種類型的通信方式，一種是讀寫器發送的數據同時被多個應答器接收，稱為“無線廣播”，另一種是多個應答器的數據同時傳送給讀寫器，稱為“多路存取”，兩者都是無線電技術中長期面臨的難題，同時也發展出一系列相應的解決思路，一般來說分為四種，即空分多路 (SDMA)，碼分多路 (CDMA),頻分多路 (FDMA)，時分多路 (TDMA)，從 RFID 系統的通信形式、功耗、 系統復雜性以及成本多方面綜合考慮，時分多路法是最有實際應用價值的，它也是目前RFID 防碰撞算法應用中最廣泛的一類，時分多路 法的基本思想是把整個可供使用的通路容量按時間分配給多個用戶，從而達到在不同時隙將各個應答器一 一識別出來的目的【 11】 。二進制樹防碰撞算法在多個國際標準中均有規定，基于 IS014443 標 準的 TYPEA 是其中的一個典型例子，本章首先介紹了涉及到二進制樹防碰撞算法的幾個標準，其次詳細研究了 ISOl4443 標準對二進制樹防碰撞算法的規定，最后提出了在此基礎上的改進算法，這也是本章的重點。系統的介紹了 RFID 技術，描述了典型 RFID 系統的 結構組成，提出了 RFID 系統的分類思想，講述了 RFID 系統的工作原理，以及其應用范圍，重點強調了 RFID 技術的現狀和所面臨的主要問題，由此體現了研究 RFID 關鍵技術防碰撞算法的意義，明確了本文的主要研究內容。解決碰撞的過程相應的被稱為防碰撞，如前所述，該防碰撞過程主要從軟件的角度來予以解決，稱為防碰撞算法 【 8】 。 1． 4 課題提出的背景及其意義 早期的 RFID 技術很少涉及到防碰撞問題，而在近年來，隨著 RFID 技術的發展，應用范圍的擴大，使得防碰撞問題日 益成為制約 RFID 發展的關鍵技術，原因有兩個，首先，早期的 RFID 一般是近距離感應耦合式系統，其操作頻率 功率普遍較低，讀取的速度慢，范圍小，所以也較少有發生碰撞的可能，而目前 RFID應用中多目標識別成為了主流方向，這就要求實現在多個物品中正確的識別出單個目標；其次，早期的 RFID 應用沒有統一的規范，各個廠家的 RFID 產品也僅是 10 應用在單個的系統當中，不存在碰撞的可能，而近年來 RFID 應用迅速發展，各個不同 RFID 制造商的產品之間的不兼容，也帶來了碰撞問題。因此，如何保證迅速快捷，又安全可靠的同時識別多個目標，就成為了 RFID 技術發展的關鍵性技術。而要建立一個全球互聯的 RFID 產品網絡，實現 RFID技術的飛躍發展，就必須解決標準不統一的難題，近年來，隨著 RFID 技術的應 用越發廣泛，有識之士都意識到并著手解決這個問題，目前主要有兩種思路，一是生產出適應于不同標準，多制式兼容的 RFID 產品，二是制定一個統一的 RFID碩十學位論 技術標準。目前在日本和歐洲已經有了類似的應用。 (2)身份識別 利用 RFID 技術，將應答器嵌入到身份證，護照等各種證件當中 ，甚至植入動物皮毛，用來跟蹤和識別目標。在數據的雙向傳輸過程中，是通過電磁場的相互感應來實現的，該過程也可以用變壓器的模型來予以參考。 根據應答器供電方式， RFID 系統可以分為三個方面： (1)無源系統：由讀寫器負責給應答器供電。 (3)遠距離系統：典型的作用范圍為 l～ 10m。微軟公司近年來也介入了 RFID 技術領域，所瞄準的就是 RFID 系統后端應用的相關軟件和服務。 CODE 等。通常來說，應答器由耦合元件和微電子芯片組成，主要電氣性能為工作頻率，讀寫能力，數據傳輸率，信息數據存儲量，防碰撞能力，信息安全性能等，應答器的分類也是以這些性能為依據的，例 如根據存儲器可將應答器分為 EEPROM， FROM(鐵電存儲器 )， SRAM(靜態隨機存儲器 )，根據信息注入方式可分為集成電路固化，現場 線改寫，現場無線改寫，根據電源供給方式分為無源，半無源，有源。 RFID 被譽為二十一世紀的十大戰略性產業之一，可以預想，未來 RFID 技術的發展空間是無限廣闊的。在傳統思路中，一般是通過單片機來進行算法處理，隨著 RFID 技術的發展，未來的一個重要方向是現場可編程門陣列 FPGA，做為一種現場可編程的專用集成電路， FPGA 擁有高速度，可編程等多個適應于算法處理的優點，從而為 RFID 防碰撞算法問題開辟了新的有效途徑根據上述分析，全文針對 RFID系統二進制樹防碰撞算法 ，進行了理論與實踐方面的探討，主要分為三個方面，首先是二進制樹算法的理論研究，將現有的二進制樹算法進行了歸納，匯總為基本算法，動態算法，退避式算法三類，闡述了各個算法的思路，對其進行了性能評價；其次，在現有的三類防碰撞算法的基礎上，提出了一種新的改進型二進制樹算法，該算法識別速度快，執行效率高，極大的改進了識別效果。 1 南 陽 理 工 學 院 本科生 畢業設計 （ 論文 ） 學院（系）： 計算機與信息工程學院 專 業： 通信工程 學 生： 指導教師： 完成日期 2021 年 4 月