通信工程畢業設計-rfid二進制樹防碰撞算法的研究與實現(編輯修改稿)

　

【文章內容簡介】 RFID 系統發生了碰撞【 7】 ，從而導致數據不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產品的識別，另一方面還可 能導致信息的泄露。在全球信息安全意識廣泛普及的背景下，可靠的安全機制成為了 RFID技術發展的關鍵性制約因素，如何有效的解決 RFID 系統的碰撞問題，成為了技術的關鍵，對此就需要采用一定的防碰撞算法來對其進行處理。目前關于防碰撞算法的研究還在進行當中，理論成果已經得出了很多，許多國際標準也對一些成熟的算法進行了規定，但是無論在理論效率還是實際應用上，都還存在很大的改進空間。 1． 4 課題提出的背景及其意義 早期的 RFID 技術很少涉及到防碰撞問題，而在近年來，隨著 RFID 技術的發展，應用范圍的擴大，使得防碰撞問題日 益成為制約 RFID 發展的關鍵技術，原因有兩個，首先，早期的 RFID 一般是近距離感應耦合式系統，其操作頻率 功率普遍較低，讀取的速度慢，范圍小，所以也較少有發生碰撞的可能，而目前 RFID應用中多目標識別成為了主流方向，這就要求實現在多個物品中正確的識別出單個目標；其次，早期的 RFID 應用沒有統一的規范，各個廠家的 RFID 產品也僅是 10 應用在單個的系統當中，不存在碰撞的可能，而近年來 RFID 應用迅速發展，各個不同 RFID 制造商的產品之間的不兼容，也帶來了碰撞問題。總之，由于多目標識別應用的需要， RFID 系統防碰撞問題 成為了關鍵技術，為了解決碰撞，可以從硬件和軟件兩方面著手，由于 RFID 系統的大規模應用限制了成本，所以，硬件實現是不實際的，因此就需要采用一定的防碰撞算法來予以解決。依前所述，RFID 系統碰撞主要有兩種情況，讀寫器碰撞和應答器碰撞，讀寫器碰撞是一個應答器同時收到不同讀寫器發出的命令，應答器碰撞是一個讀寫器同時給不同應答器發送命令。在實際的應用當中，應答器由于其低成本的優越 ,從而得到大量的生產，而讀寫器往往是固定在系統的某處，來識別多個應答器，所以碰撞的主要情況是應答器碰撞，即一個讀寫器的工作范圍內同時出現了 多個應答器，并且對該讀寫器發出的命令同時予以響應，從而導致讀寫器無法正確的識別出一個應答器，稱該現象為發生了應答器碰撞。解決碰撞的過程相應的被稱為防碰撞，如前所述，該防碰撞過程主要從軟件的角度來予以解決，稱為防碰撞算法 【 8】 。 在上述前提下，基于應答器的確定型二進制樹防碰撞算法是目前最好的一種選擇，對其進行研究，是最有實際應用價值的，所以，本文將對其進行理論分析與具體實現，在研究過程中，注重與新一代智能 RFID 系統的結合，應用擁有強大功能的 FPGA(FieldProgrammable GateArray)做 為算法運行的微處理器，這種思路將是未來 RFID 技術發展的重要方向， RFID 技術中的關鍵算法與先進的電子技術 FPGA 的結合，將為 RFID 技術的應用拓開廣闊的前景。 1． 5 本文的主要工作 本文將在 RFID 技術的前提下，結合當前數字電路設計的主流思路，重點研究 RFID 的關鍵技術防碰撞算法，并主要著眼于其中基于應答器的確定性算法，即二進制樹防碰撞算法，在理論分析的基礎上，對其進行具體實現。基于上述考慮，論文將分四章來予以講述，文章結構與內容安排如下： 第 1 章：緒論。系統的介紹了 RFID 技術，描述了典型 RFID 系統的 結構組成，提出了 RFID 系統的分類思想，講述了 RFID 系統的工作原理，以及其應用范圍，重點強調了 RFID 技術的現狀和所面臨的主要問題，由此體現了研究 RFID 關鍵技術防碰撞算法的意義，明確了本文的主要研究內容。 第 2 章：現有 RFID 二進制樹防碰撞算法。概要性的描述了 RFID 防碰撞算法，對其進行了分類，重點介紹其中的二進制樹防碰撞算法，研究了三種最基本的二進制樹算法，對其進行了原理闡述，性能分析，以及實例演示。 第 3 章：改進型二進制樹防碰撞算法。二進制樹防碰撞算法在多個國際標準中均有規定，基于 IS014443 標 準的 TYPEA 是其中的一個典型例子，本章首先介紹了涉及到二進制樹防碰撞算法的幾個標準，其次詳細研究了 ISOl4443 標準對二進制樹防碰撞算法的規定，最后提出了在此基礎上的改進算法，這也是本章的重點。 第 4 章： FPGA 實現改進型二進制樹防碰撞算法。 FPGA 技術是目前數字電路設計的主流思路，利用 FPGA 做主處理器，是 RFID 技術發展的方向，本章探討了這一想法，介紹了 FPGA 技術的相關要點，并應用 FPGA，實現了改進型二進制樹防碰撞算法。 11 2 現有 RFID 二進制樹防碰撞算法 2． 1 RFID 防碰撞算法概述 RFID 系統的數據通信雙方是讀寫器和應答器，在實際的 RFID 系統工作時，可能會出現同時多個讀寫器和多個應答器共存的情況，毫無疑問，此時系統的數據交換就會出現信道與時序上的重疊，也就是發生了碰撞，在多個讀寫器與多個應答器的射頻識別系統中，存在著兩種形式的沖突方式，一種是同一應答器同時收到不同讀寫器發出的命令，另一種是同一個讀寫器同時收到多個不同應答器返回的數據，前者我們稱為讀寫器碰撞，后者稱為應答器碰撞【 9】，在實際應用當中，一般是讀寫器做為主設備，來識別多個應答器，所以發生讀寫器碰撞的應用場合是不多的，因此下文將 著重研究應答器碰撞。 在上述前提下，有兩種類型的通信方式，一種是讀寫器發送的數據同時被多個應答器接收，稱為“無線廣播”，另一種是多個應答器的數據同時傳送給讀寫器，稱為“多路存取”，兩者都是無線電技術中長期面臨的難題，同時也發展出一系列相應的解決思路，一般來說分為四種，即空分多路 (SDMA)，碼分多路 (CDMA),頻分多路 (FDMA)，時分多路 (TDMA)，從 RFID 系統的通信形式、功耗、 系統復雜性以及成本多方面綜合考慮，時分多路法是最有實際應用價值的，它也是目前RFID 防碰撞算法應用中最廣泛的一類，時分多路 法的基本思想是把整個可供使用的通路容量按時間分配給多個用戶，從而達到在不同時隙將各個應答器一 一識別出來的目的【 11】 。時分多路法按照能量的供給者可以分為兩大類，一類是應答器驅動型，另一類是讀寫器驅動型，這也正是對應了第一章中 RFID系統分類思路中的有源系統和無源系統，根據實際應用情況，無源系統是應用最廣泛的一類，所以下文重點研究讀寫器驅動型的時分多路法。在該類讀寫器驅動型時分多路法中，目前最常用的防碰撞算法有兩種，一類是基于時隙 ALOHA 的統計型算法，另一類是基于二進制樹的確定型算法，統計 型算法的意義是在 一定的時隙范圍內，系統有可能識別出所有應答器 ，確定型算法的最大優點是，在一定的時隙范圍內，系統一定可以將所有的應答器一一識別出來【 13】 。從應用的角度來說，正確有效的識別是實際所需要的，因此下文將著重于二進制樹防碰撞算法的研究。 2． 2 RFID 二進制樹防碰撞算法概述 2． 2． 1 基本概念 在 RFID 防碰撞算法中，二進制樹算法是目前應用最廣泛的一種 ，之所以稱為“二進制樹”，是因為在算法執行過程中，讀寫器要多次發送命令給應答器，每次命令都把應答器分成兩組，多次分組后最終得到唯一的一個應答器，在這個分組過程中，將 對應的命令參數以節點的形式存儲起來，就可以得到一個數據的分叉樹，而所有的這些數據節點又是以二進制的形式出現的，所以稱為“二進制樹”。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統當中，每個應答器都是獨一無二的，它們的獨立性通過唯一的自身序列號來體現，該序列號在不同的標準中有不同的名稱，如 EPC 標準中稱其為電子產品代碼 EPC，即英文ElectronicProduct Code 的縮寫， IS014443 標準中稱其為唯一標識碼 UID，即英文 Unique Identmer 的縮寫【 15】 。事實上，這些都 是對應答器序列號的名稱描述，因為下文涉及到的防碰撞算法是普遍意義上的，既包括了 EPC標準中的規定，也包括了 ISO 標準中的規定，因此在本文對普遍意義上的防碰撞算法的描述過程中，統一用序列號 SN(SerialNumber)來描述上述概念，同時，序列號的長度，格式，以及編碼方式也是各個標準各自差異的，為了說明的便利，統一定義為 8 位長度的 二進制碼。如圖 2． 1所示。 圖 2． 1 應答器序列號數據格式 讀寫器與應答器之間進行數據交換時，往往要傳輸序列號的部分或者全部位，此時的傳輸順序定義為：先發送低位，再發送高位。 在讀寫器或者應答器內部，對數據進行比較時，遵循這樣的原則，即按位依次比較，先比較低位，再比較高位，約定 01，根據這個比較順序，在判斷大小時，低位數據優先，即兩數A， B 相比較，從低位開始的第一個不相等位的大小決定了兩數的大小，只有當兩個數的全部位均相等時，兩數才相等。 2． 2． 2 性能指標 定義碰撞解決時期 CRI，即 Collision Resolution Interval【 16】 ，即解決一個讀寫器工作范圍內碰撞所需要的時隙數，對二進制樹算法的評價，一些常用的性能指 標如下所示【 17】 ： 首先是算法執行效率 ， 定義如下：在算法執行過程，一 共 個時隙，識別了 n 個應答器，則 =n/ 表示算法的執行效率。 分析如下： n=l，顯而易見，在第一個時隙內不發生碰撞，可以成功識別該應答器， =1。 n≥ 2，由于應答器序列號的唯一性，將有碰撞發生，在一個時隙內發生碰撞的概率 p 是一個隨機事件，在 n 個應答器信息包中 i個發生碰撞的概率為： 給出 i個碰撞，則 CRI的長度為： 其中 1是 n個信息包最初的一個時隙， 是 i個碰撞的順利傳輸的時隙， 13 是 ni個無碰撞傳輸的時隙。 由上式可知， 是逐漸遞歸的，通過遞歸可得： 根據式 ()，上式可化為： 由此可見， 是關于 p 的函數，則 =n/ 也是關于 p的函數，一般情況下，可以參考二項分布，將 p取為 1／ 2。 算法的第二個重要的性能指標是穩定性，顯然，基于 TDMA 的二進制樹防碰撞算法是沿著時間軸線來執行協議的，有一系列的碰撞解決時期 CRI，定義一個隨機變量 ，表示第 k個 CRI的長度，這些 ???? 形成一個馬爾可夫鏈 (Markovchain)，因為第 個 CRI 的長度由它開始的第一個時隙傳輸的信息，也就是在 k 個 CRI 區間內到達的信息包決定的，所以，如果馬爾可夫鏈滿足遍歷性分布，那么這個系統 就可以說是穩定的。 馬爾可夫鏈遍歷性分布要滿足下列兩個條件 【 18】 ： 這里有： 也就是 n個信息包從發生碰撞開始傳輸的 CRI區間長度的數學期望， 是 在一個時隙內到達這個系統信息包的期望值，該過程屬于泊松過程【 l9】 。一般來說， 在二進制樹防碰撞算法中，系統都能夠滿足馬爾可夫鏈的兩個遍歷性分布條件，即作為一種確定型的算法，二進制樹防碰撞算法是穩定的。算法的第三個重要性能是系統通信復雜度，顯而易見，系統的通信雙方是讀寫器與應答器，則通信復雜度也應該從這兩方面著手考慮，即讀寫器與應答器各自發送的數據位的位 數。該指標的評價標準是基于能量消耗的角度的，即發送的數據信息量越少，則整個系統消耗的能量也越少，這顯然是一個理想的效果。 2． 2． 3 算法分類 在基本的二進制樹搜索算法的基礎上，有多種形式的二進制樹搜索算法，它 14 們之間主要的區別在于命令的數據形式，主要有兩點。 (1)命令參數是 1bit 數據，還是多 bit 數據。 (2)命令參數長度是固定的，還是變化的。 圖 2． 2 是一個二進制樹搜索算法的分類圖，在基本二進制樹的基礎上，按照命令參數分為 1bit 和多 bit，根據傳輸的命令參數的長度分為定長二進制樹和動態二進制樹兩種，根 據二進制樹遍歷時是一輪前進到底的還是退避返回的分為前進二進制樹和退避二進制樹兩種。需要說明的是，這只是一個大略的分類法，主要目的在于說明二進制樹分類的基本原則。事實上，分類所得的這些算法中也有互相重合的，如動態二進制樹算法既可以采用前進思路，也可以采用退避思路。另外，在具體應用時，可能還存在多種不同的說法，如 lbit 長二進制樹中還有修正二進制樹 MBBT，加強二進制樹 EBBT 等區別【 20】 。 圖 2． 2二進制樹算法分類 2． 3 基本二進制樹防碰撞算法 2． 3． 1 算法思路 定義兩個具有普遍意義的命令來描述算法 ： (1)請求命令 Request(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。注： Request(SN)初始值設為 Request(11111111)。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，也即是不再響應 Request 命令，除非該應答器通過先離開讀寫器工作范圍再進入的方式重新上電，才可以再次響應 Request 命令 。 基本二進制樹算法的流程圖如圖 2． 3所示： 15 圖 2． 3基本二進制樹算法流程 基本二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時