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

　　

【正文】 一樣的，區別在于，退避式算法的傳送次數，也即是所遍歷的節點數目比之基本算法大大減少，假設讀寫器工作范圍內有 n個應答器，則所需節點數目為而，則可用式子 2． 19來表示： 數學歸納法證明如下： 當讀寫器工作范圍內只有一個應答器時，顯然有： 假設 n個應答器時，有： 則當系統中有 n+1 個應答器時，由于新增加的這個應答器與原來 n個應答 器的序列號均不相同，為了將其與某個匹配度最高的應答器區分開來，需要在原 來二進制樹中增加一個節點，由于節點之間僅存在父子關系，且僅通過兩條邊相 連，所以有： 得證。此時將最大序列號中對應碰撞起始位置 為 O。 定義兩個具有普遍意義的命令來描述 算法： (1)請求命令 Request(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。 (5) 重復上述過程，即可按序列號從小到大依次識別出各個應答器． 2． 4． 2 實例演示 動態二進制樹算法的實例演示如圖 2． 6 所示 ，基本設置同基本二進制樹算法： 圖 2． 6動態二進制樹算法實例 (1)啟動第一輪循環，讀寫器發送 Request(11111111)命令，所有應答器響應該命令，按照約定，命令參數為全 1時，所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1XXXXl01，其中 X 表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，得到 0101，則下一次 Request命令攜帶的參數值，即 Request(0101)。 動態 二進制樹算法的流程如 圖 2． 5所示： 20 圖 2． 5動態二進制樹算法流程 事實上，動態二進制樹對基本二進制樹的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法的核心部分即新命令參數的生成，是根據是否發生碰撞，以及碰撞位來決定的，特別是新 Request 命令參數的生成是由碰撞的起始位來確定的，而碰撞的起始位的得到只需要應答器序列號中包括碰撞起始位在內的部分位即可，把這些位稱為序列號的有效位，同樣，新 Request 命令參數也為包括碰撞起始位 (設為 0)在內的部分位，綜合如下：若選擇高位加碰撞起始位(設為 0)，則算法為應答器序列號 對應位小于這些位的數值者，返回剩余低位，若選擇碰撞起始位 (設為 0)加低位，則算法為應答器序列號對應位等于這些位的數值者，返回剩余高位，從而讀寫器的新 Request 命令參數與應答器返回的序列號有效部分組合起來，可以得到一個完整的應答器序列號。所以，要改善二進制樹算法的性能，就必須從這兩點著手，現有的二進制樹搜索算法有很多種，它們都是在基本二進制樹搜索算法的基礎上加以改進得來的，根據 前 述分析，主要的改進思路有兩個 ： (1)減少每次通信過程中的數據傳輸位數。循環次數 定義為在整個防碰撞循環過程中的循 18 環 輪次，也即是二進制樹的遍歷次數。 (6)讀寫器發送 Request(11110101)命令，．除 Tl外所有應答器響應該命令，將自身序列號與該 SN(11l10101)比較，其中 T3(1l010l01)的序列號小于該值，則 T3 返回自身序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 110l0101，讀寫器做如下處理：將該數值作為下一次 Sleep 命令攜帶的參數值，即 Sleep(11010101)。 注：第五步時，從步驟 1開始重復，也就是說，讀寫器識別完一個應答器后，將重新發送原始的最大序列號。注： Request(SN)初始值設為 Request(11111111)。 2． 2． 3 算法分類 在基本的二進制樹搜索算法的基礎上，有多種形式的二進制樹搜索算法，它 14 們之間主要的區別在于命令的數據形式，主要有兩點。 分析如下： n=l，顯而易見，在第一個時隙內不發生碰撞，可以成功識別該應答器， =1。從應用的角度來說，正確有效的識別是實際所需要的，因此下文將著重于二進制樹防碰撞算法的研究。 第 3 章：改進型二進制樹防碰撞算法。在實際的應用當中，應答器由于其低成本的優越 ,從而得到大量的生產，而讀寫器往往是固定在系統的某處，來識別多個應答器，所以碰撞的主要情況是應答器碰撞，即一個讀寫器的工作范圍內同時出現了 多個應答器，并且對該讀寫器發出的命令同時予以響應，從而導致讀寫器無法正確的識別出一個應答器，稱該現象為發生了應答器碰撞。 1． 3． 3 RFID 防碰撞算法 隨著 RFID 技術的發展，多目標識別成為了一個很重要 的應用方向，特別在目標跟蹤，物品識別，訪問控制等操作中，利用 RFID 技術，對附著在不同目標上的應答器快速可靠的進行識別，從而大大提高了定位的精確度，管理的自動化促進了整個產業鏈的發展。 (3)防偽應用 應答器在防偽應用中有識別快速，偽造難，成本低等優點，再加上安全認證和加密功能，就可以大大提高偽造的難度和成本，同時，在識別的時刻，可以通過讀寫器的快速閱讀功能，在瞬間得出所有物品的信息，并加以記錄 和處理。 8 1． 2． 3 RFID 系統工作原理 RFID 是一門多學科綜合技術，涉及到電磁場理論，數字電路，模擬電路，無線電廣播，通信原理等多方面知識 RFlD 系統中，讀寫器將要發送的信號調制到載波上，經由射頻通道，通過天線發 送出去，應答器上的電壓根據載波的變化而變化，將該電壓信號進行整流和濾波后，得到解調后的數據，這是下行鏈路的過程，應答器傳輸的數據的變化控制應答器天線上負載電阻的通斷，從而促使讀寫器天線上電壓的變化，從而實現了數據的上行鏈路傳輸。 (2)遙耦合：典型的作用范圍為 lcm～ 1m。 應答器的典型產品有 TI公司的 6000 系列， Philips 公司的 I RFID 技術通過射頻 方式進行非接觸的雙向通信，達到自動識別的目的，它源起于上世紀四五十年代，最初是基于雷達與微波理論的發展，自從上世紀九十年代以來， RFID 技術快速發展，得到了廣泛的應用，進入新世紀后，各個國家，組織還有企業都加大了對 RFID 技術的投入，生產了大批相應的產品，在多個領域有了成功的應用案例。隨著 RFID 技術的發展，如何實現同時與多個目標之間的正確的數據交換，即解決 RFID 系統中多個讀寫器和應答器之間的數據碰撞，成為了限制 RFID 技術發展的難題，采用合理的算法來有效的 解決該問題，稱為 RFID 系統的防碰撞算法。在具體應用中，前端信息載體有多個名稱，如標簽 (Tag)，智能標簽 (Smart Labels)，射頻卡 (RF Card)等，本文建議采用應答器 (Transponder)這種更具普遍意義的說法。根據天線與讀寫器模塊的分離與否，讀寫器可以分為分離式和集成式，但無論哪種讀寫器，其基本結構都是類似的，從硬件部分來說，典型的讀寫器由三塊組成：射頻通道模塊，控制處理模塊，天線。 (2)高頻： 3～ 30MHz，典型應用為 13． 56MHz． (3)超高頻： 300MHz~5． 8GHz，典型應用為 2． 4G。 1． 3 RFID 技術現狀及其發展 1． 3． 1 RFID 技術應用 做為一種新興的自動識別技術， RFID 近年來發展很快，在國內國外都取得 了廣泛的應用，主要體現在以下幾個領域【 6】 。 RFID 技術的應用遠不止以上提及的四個方面，它在諸如生產線自動化管理，門禁系統，新生嬰兒防錯管理，地理信息標識等多個方面都有著廣泛應用，可以毫不夸張的說， RFID 技術有著良好的發展前景，它孕育的 9 經濟效益將是超乎想像的。在全球信息安全意識廣泛普及的背景下，可靠的安全機制成為了 RFID技術發展的關鍵性制約因素，如何有效的解決 RFID 系統的碰撞問題，成為了技術的關鍵，對此就需要采用一定的防碰撞算法來對其進行處理。 1． 5 本文的主要工作 本文將在 RFID 技術的前提下，結合當前數字電路設計的主流思路，重點研究 RFID 的關鍵技術防碰撞算法，并主要著眼于其中基于應答器的確定性算法，即二進制樹防碰撞算法，在理論分析的基礎上，對其進行具體實現。 FPGA 技術是目前數字電路設計的主流思路，利用 FPGA 做主處理器，是 RFID 技術發展的方向，本章探討了這一想法，介紹了 FPGA 技術的相關要點，并應用 FPGA，實現了改進型二進制樹防碰撞算法。事實上，這些都 是對應答器序列號的名稱描述，因為下文涉及到的防碰撞算法是普遍意義上的，既包括了 EPC標準中的規定，也包括了 ISO 標準中的規定，因此在本文對普遍意義上的防碰撞算法的描述過程中，統一用序列號 SN(SerialNumber)來描述上述概念，同時，序列號的長度，格式，以及編碼方式也是各個標準各自差異的，為了說明的便利，統一定義為 8 位長度的 二進制碼。 算法的第二個重要的性能指標是穩定性，顯然，基于 TDMA 的二進制樹防碰撞算法是沿著時間軸線來執行協議的，有一系列的碰撞解決時期 CRI，定義一個隨機變量 ，表示第 k個 CRI的長度，這些 ???? 形成一個馬爾可夫鏈 (Markovchain)，因為第 個 CRI 的長度由它開始的第一個時隙傳輸的信息，也就是在 k 個 CRI 區間內到達的信息包決定的，所以，如果馬爾可夫鏈滿足遍歷性分布，那么這個系統 就可以說是穩定的。 圖 2． 2 是一個二進制樹搜索算法的分類圖，在基本二進制樹的基礎上，按照命令參數分為 1bit 和多 bit，根據傳輸的命令參數的長度分為定長二進制樹和動態二進制樹兩種，根 據二進制樹遍歷時是一輪前進到底的還是退避返回的分為前進二進制樹和退避二進制樹兩種。 (2) 由于應答器序列號的唯一性，當應答器數目不小于兩個時，必然發生碰撞．發生碰撞時，將最大序列號中對應的碰撞起始位設置為 O，低于該位者不變，高于該位者設置為 l。 (1)啟動第一輪循環，讀寫器發送 Request(1lll1111)命令，所有應答器響應該命令，將自身序列號與該 SN(1l1l1111)比較，均小于該值，于是所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 lXXXXl0l，其中 X 表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 l，得到 11ll0l01，作為下一次 Request 命令攜帶的參數值，即Request(11110l01)。 (9)讀寫器發送 Request(10101101)命令，除 Tl， T3 外所有應答器響應該命令，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2 返回自身序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 l0101101，讀寫器做如下處理：將該數值作為下一次 Sleep 命令攜帶的參數值，即 Sleep(10101101)。該值可以用式子 來表示【 21】 ，其中 Integ 表示取整。定義根據第二個思路得來的算法為退避式二進制樹，它的一個典型應用為 EPC 二進制樹搜索 算法。 動態二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，約定此時所有應答器均返回完整序列號，則同一時刻應答器將自身序列號發回給讀寫器。 (4)讀寫器發送 Sleep(10100101)命令，所有應答器響應該命令，將自身序列 22 號與該 SN(10100101)比較，其中 T1(10100101)的序列號等于該值，則 Tl執行該命令，進入休眠狀態，即除非重新上電 ，否則不再響應 Request 命令。退避式二進制樹算法的流程見圖2． 7，基本設置可參考基本二進制樹算法： 23 圖 2． 7退避式二進制樹算法流程 如圖所示，退避式二進制樹算法的流程與基本算法的區別在于：基本算法中，一個應答器被識別后，重新啟動新循環時，讀寫器返回整棵樹的根節點，獲取原始 Request 命令參數，而退避式算法中，讀寫器返回上一次發生碰撞節點，獲取Request 命令參數。 (5)返回上一個發生碰撞的節點，獲取該節點對應的最大序列號，重復上述過程，即可按序列號從小到大依次識別出各個應答器． 24 2． 5． 2 實例演示 退避式二進制樹算法實例演示如圖 2． 8 所示，其設置參考基本二進制樹算法： 圖 2． 8退避式 二進制樹算法實例 (1)啟動第一輪循環，讀寫器發送 Request(11111111)命令，所有應答器響應，將自身序列號與該 SN(11111111)比較，均小于該值，則所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 lXXXXl0l，其中 X表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 1，得到 1l110l01，作為下一次 Request 命令參數，即 Request(1l1 l 0l01)。符合 IS015693 標準的信號接口部分的性能如下： 工作場強：工作場的最小值為 O． 15A／ m，最大場為 5A／ m。 TypeC— G 目前已經暫時被列入IS014443 標準，等待復