通信工程畢業設計-rfid二進制樹防碰撞算法的研究與實現(存儲版)

　　

【正文】 即除非重新上電，否則不再響應 Request 命令。 (3)讀寫器發送 Request(00l01)命令，所有應答器響應，將自身序列號與該SN(00101)比較，其中 Tl(10100101)的序列號對應位等于該值，則 Tl 返回剩余序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數 00101 與返回數據 101組合起來，作為下一次 Sleep 命令攜帶的參數值，即 Sleep(10100101)。 注：如果上一次發出的 Request 為全 l，則表明讀寫器工作范圍內只有一個應答器，此時應答器返回數據為完整序列號，以該序列號作為 Sleep 命令參數。 本文中，定義根據第一個思路得來的算法為動態二進制樹，它的一個典型應用為 ISOl4443 TYPEA 二進制樹搜索算法。也即是二進制樹的節點數目。 (8)啟動第三輪循環，讀寫器發送 Request(11111111)命令，除 T1， T3 外所有應答器響應該命令，將自身序列號與該 SN(1111ll11)比較，均小于該值，于是所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1X101101，其中 x表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數值，即 Request(10101101)。 假設 RFID系統中有一個讀寫器 R，四個應答器 Tl(10100101)， T2 16 (10l01101)， T3(11010101)， T4(11101101)，在某一時刻，四個應答器 同時進入讀寫器的工作范圍之內，讀寫器發出命令，四個應答器同時響應，由于 其序列號 SN的唯一性，將發生應答器碰撞，從而啟動防碰撞循環，分析如下： 圖 基本二進制樹算法實例 注：圖中共有四輪循環，依次識別出四個應答器，分別以不同格式的線條表 示，并加有循環輪次的數字標識。 基本二進制樹算法的流程圖如圖 2． 3所示： 15 圖 2． 3基本二進制樹算法流程 基本二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號返回給讀寫器。 (2)命令參數長度是固定的，還是變化的。 由上式可知， 是逐漸遞歸的，通過遞歸可得： 根據式 ()，上式可化為： 由此可見， 是關于 p 的函數，則 =n/ 也是關于 p的函數，一般情況下，可以參考二項分布，將 p取為 1／ 2。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統當中，每個應答器都是獨一無二的，它們的獨立性通過唯一的自身序列號來體現，該序列號在不同的標準中有不同的名稱，如 EPC 標準中稱其為電子產品代碼 EPC，即英文ElectronicProduct Code 的縮寫， IS014443 標準中稱其為唯一標識碼 UID，即英文 Unique Identmer 的縮寫【 15】 。 第 4 章： FPGA 實現改進型二進制樹防碰撞算法。 在上述前提下，基于應答器的確定型二進制樹防碰撞算法是目前最好的一種選擇，對其進行研究，是最有實際應用價值的，所以，本文將對其進行理論分析與具體實現，在研究過程中，注重與新一代智能 RFID 系統的結合，應用擁有強大功能的 FPGA(FieldProgrammable GateArray)做 為算法運行的微處理器，這種思路將是未來 RFID 技術發展的重要方向， RFID 技術中的關鍵算法與先進的電子技術 FPGA 的結合，將為 RFID 技術的應用拓開廣闊的前景。在 RFID 系統中，當工作范圍內同時出現了多個讀寫器和多個應答器時，讀寫器與讀寫器之間，應答器與應答器之間的相互干擾，稱 RFID 系統發生了碰撞【 7】 ，從而導致數據不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產品的識別，另一方面還可 能導致信息的泄露。 (4)交通管理 交通管理是 RFID 最先應用的領域，目前已經擁有了成熟的技術，它利用了應答器便捷快速識別，可靠性高，安全性強的特點，目前主要應用范圍是電子車票，高速公路收費等方面，在我國深圳，基于 RFID 技術的高速公路收費系統已經得到了成功的應用。同時，根據 RFID 系統的不同，在供電方式上有無源或者有源，調制方式上有幅度調制或者相位調制，數據讀取上有電感耦合或者反向散射等區別【 5】 。 根據工作頻率的大小， RFID 系統可以分為如下四個方面： (1)低頻： 30～ 300KHz，典型應用為 134KHz。數據交換環節即 RFID 系統中的讀出寫入設備，它是系統的核心部件，是后端應用環境和前端信息載體的數據通道，在實際應用中，往往被稱為查 詢器，掃描器，閱讀器，編程器等，本文建議采用讀寫器 (Read／ Write Device)這種更具普遍意義的說法，這樣既包括了從應答器中讀出信息，同時也包括了向應答器中寫入信息。 1． 2 RFID 系統 1． 2． 1 RFID 系統組成 根據實際應用環境， RFID 系統結構有多種不同分法，一般來說，一個典型RFID 系統包括三個部分：前端信息載體，數據交換環節，后端應用環境【 3】。 1 南 陽 理 工 學 院 本科生 畢業設計 （ 論文 ） 學院（系）： 計算機與信息工程學院 專 業： 通信工程 學 生： 指導教師： 完成日期 2021 年 4 月 2 南 陽 理 工 學 院 本 科 畢 業 設 計（論文） RFID 二進制樹防碰撞算法設計 學 院（系）： 計算機與信息工程學院 專 業： 通信工程 學 生 姓 名： 學 號： 指 導 教 師（職稱）： 評 閱 教 師： 完 成 日 期： 2021 年 4 月 南陽理工學院 Nanyang Institute of Technology 3 RFID 二進制樹防碰撞算法設計 【 摘要 】 射頻識別技術 RFID 是目前正快速發展的一項新技術，它通過射頻信號進行非接觸式的雙向數據通信，從而達到自動識別的目的。 RFID 被譽為二十一世紀的十大戰略性產業之一，可以預想，未來 RFID 技術的發展空間是無限廣闊的。 CODE 等。 (3)遠距離系統：典型的作用范圍為 l～ 10m。在數據的雙向傳輸過程中，是通過電磁場的相互感應來實現的，該過程也可以用變壓器的模型來予以參考。目前在日本和歐洲已經有了類似的應用。因此，如何保證迅速快捷，又安全可靠的同時識別多個目標，就成為了 RFID 技術發展的關鍵性技術。解決碰撞的過程相應的被稱為防碰撞，如前所述，該防碰撞過程主要從軟件的角度來予以解決，稱為防碰撞算法 【 8】 。二進制樹防碰撞算法在多個國際標準中均有規定，基于 IS014443 標 準的 TYPEA 是其中的一個典型例子，本章首先介紹了涉及到二進制樹防碰撞算法的幾個標準，其次詳細研究了 ISOl4443 標準對二進制樹防碰撞算法的規定，最后提出了在此基礎上的改進算法，這也是本章的重點。 2． 2 RFID 二進制樹防碰撞算法概述 2． 2． 1 基本概念 在 RFID 防碰撞算法中，二進制樹算法是目前應用最廣泛的一種 ，之所以稱為“二進制樹”，是因為在算法執行過程中，讀寫器要多次發送命令給應答器，每次命令都把應答器分成兩組，多次分組后最終得到唯一的一個應答器，在這個分組過程中，將 對應的命令參數以節點的形式存儲起來，就可以得到一個數據的分叉樹，而所有的這些數據節點又是以二進制的形式出現的，所以稱為“二進制樹”。 n≥ 2，由于應答器序列號的唯一性，將有碰撞發生，在一個時隙內發生碰撞的概率 p 是一個隨機事件，在 n 個應答器信息包中 i個發生碰撞的概率為： 給出 i個碰撞，則 CRI的長度為： 其中 1是 n個信息包最初的一個時隙， 是 i個碰撞的順利傳輸的時隙， 13 是 ni個無碰撞傳輸的時隙。 (1)命令參數是 1bit 數據，還是多 bit 數據。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，也即是不再響應 Request 命令，除非該應答器通過先離開讀寫器工作范圍再進入的方式重新上電，才可以再次響應 Request 命令 。 2． 3． 2 實例演示 根據上述分析，下面給出一個基本二進制樹搜索算法的實例演示，如圖 2． 4 所示。 (7)讀寫器發送 Sleep(1l010101)命令，所有應答器響應該命令，將自身序列號與該 SN(110l 0101)比較，其中 T3(11010101)的序列 號等于該值，則 T3 執行該命令，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。根據前面的分析可知，做為一種確定性的算法，基本二進制樹一輪循環總能識別出一個應答器，所以在 n個應答器的前提下，經過 n次循環可以識別出 N 個應答器，所以整個過程中的循環次數為 n． 搜索次數 定義為算法執行命令的次數。 (2)減少應答器分組的詢問次數。這兩種選擇方式并沒有本質區別，在本文中，采取其中的一種，即：讀寫器檢測到碰撞后，將碰撞起始位置 0，低位不變，從而將碰撞起始位 (置為 O)加低位作為新 Request 命令參數，應答器響應，從低位開始比較，若對應位等于該參數，則返回剩余位給讀寫器，如果只有 _個應答器響應，讀寫器檢 測到無碰撞發生，則將上一次發出的Request 命令參數與應答器返回的剩余位組合起來，作為新的 Sleep 命令參，該參數也即是剛剛做出響應的這個應答器的序列號。 (2)讀寫器發送 Request(0l01)命令，所有應答器響應，將自身序列號與該SN(0101)比較，其中 Tl(10l00101)， T3(110l0l01)的序列號低四位等于該值，則 T1， T3 返回剩余位給讀寫器，在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 lXXX，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數值，即 Request(00l01)。注： Request(SN)初始值設為 Request(11ll1111)。低于該位者不變，高于該位者置 1。 2． 6 本章小結 本章歸納了現有的二進制樹防碰撞算法，將其分為三個基本類別，分別講述了其實現思路，進行了實例演示，并且對其做了性能分析，結果表明，動態算法和退避式算法是對基本算法的兩個改進思路，具有各自的優勢。 表 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】 。有兩個主要特點，一是獨特的天線結構和技術，使其讀寫距離可以穩定地達到 10cm 以上，同時其天線結構中鑲嵌的特殊材料 (鐵氧體等材料 )使其天線電磁場的讀寫距離非常均勻，沒有“死區”現象出現，二是 SONY 非接觸智能卡數據寫操作失敗時的數據恢復功能。 TypeA 由 Philips 半導體公司首次開發和使用，在亞洲等地區， TypeA 技術和產品占據了很大的市場份額。讀寫器應能確定用哪種方式。 (3)讀寫器 發送