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

　

【正文】 .............................................. 50 4． 5． 1請求命令處理 ............................................ 50 4． 5． 2防碰撞命令處理 .......................................... 51 4． 5． 3選擇命令處理 ............................................ 53 4． 5． 4去選擇命令處理 .......................................... 53 4． 6 命令選擇模塊 .................................................. 53 4． 7 數據存儲模塊 .................................................. 55 4． 8 密勒編碼模塊 .................................................. 56 4． 9 模塊連接 ...................................................... 57 4． 10 本章小結 ..................................................... 58 結論 ........................................................ 58 致謝 ........................................................ 62 6 1 引言 1． 1 RFID 技術 簡介 自動設備識別技術是目前國際上發展很快的一項新技術，英文名稱為Automatic Equipment Identif ication，簡稱 AEI，它通過一些先進的技術手段，實現人們對各種設備在不同狀態下的自動識別和管理【 ll】 。 1． 2 RFID 系統 1． 2． 1 RFID 系統組成 根據實際應用環境， RFID 系統結構有多種不同分法，一般來說，一個典型RFID 系統包括三個部分：前端信息載體，數據交換環節，后端應用環境【 3】。一般來說，應用最廣泛的是無源 +集成電路固化 +靜態隨機存儲的應答器。數據交換環節即 RFID 系統中的讀出寫入設備，它是系統的核心部件，是后端應用環境和前端信息載體的數據通道，在實際應用中，往往被稱為查 詢器，掃描器，閱讀器，編程器等，本文建議采用讀寫器 (Read／ Write Device)這種更具普遍意義的說法，這樣既包括了從應答器中讀出信息，同時也包括了向應答器中寫入信息。 綜上所述，一個典型的 RFID 系統的組成如圖所示： 圖 RFID 系統組成 1． 2． 2 RFID 系統分類 RFID 系統依據不同的標準，可以分為很多類別，各個不同 的 RFID 系統，在工作方式和應用范圍上，有著各自不同的特點，在應用時要根據實際需要來選擇。 根據工作頻率的大小， RFID 系統可以分為如下四個方面： (1)低頻： 30～ 300KHz，典型應用為 134KHz。 (2)半無源系統：應答器內的電池僅做輔助作用。同時，根據 RFID 系統的不同，在供電方式上有無源或者有源，調制方式上有幅度調制或者相位調制，數據讀取上有電感耦合或者反向散射等區別【 5】 。這方面應用的典型例子是我國目前實行的二代身份證，它基于 ISO／ IEC14443 標準定義的 TYPE B 類型卡。 (4)交通管理 交通管理是 RFID 最先應用的領域，目前已經擁有了成熟的技術，它利用了應答器便捷快速識別，可靠性高，安全性強的特點，目前主要應用范圍是電子車票，高速公路收費等方面，在我國深圳，基于 RFID 技術的高速公路收費系統已經得到了成功的應用。但是 RFID 本身的技術難度，以及標準帶來的經濟利益的沖突，使得該目標實施起來非常困難。在 RFID 系統中，當工作范圍內同時出現了多個讀寫器和多個應答器時，讀寫器與讀寫器之間，應答器與應答器之間的相互干擾，稱 RFID 系統發生了碰撞【 7】 ，從而導致數據不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產品的識別，另一方面還可 能導致信息的泄露?？傊?，由于多目標識別應用的需要， RFID 系統防碰撞問題 成為了關鍵技術，為了解決碰撞，可以從硬件和軟件兩方面著手，由于 RFID 系統的大規模應用限制了成本，所以，硬件實現是不實際的，因此就需要采用一定的防碰撞算法來予以解決。 在上述前提下，基于應答器的確定型二進制樹防碰撞算法是目前最好的一種選擇，對其進行研究，是最有實際應用價值的，所以，本文將對其進行理論分析與具體實現，在研究過程中，注重與新一代智能 RFID 系統的結合，應用擁有強大功能的 FPGA(FieldProgrammable GateArray)做 為算法運行的微處理器，這種思路將是未來 RFID 技術發展的重要方向， RFID 技術中的關鍵算法與先進的電子技術 FPGA 的結合，將為 RFID 技術的應用拓開廣闊的前景。 第 2 章：現有 RFID 二進制樹防碰撞算法。 第 4 章： FPGA 實現改進型二進制樹防碰撞算法。時分多路法按照能量的供給者可以分為兩大類，一類是應答器驅動型，另一類是讀寫器驅動型，這也正是對應了第一章中 RFID系統分類思路中的有源系統和無源系統，根據實際應用情況，無源系統是應用最廣泛的一類，所以下文重點研究讀寫器驅動型的時分多路法。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統當中，每個應答器都是獨一無二的，它們的獨立性通過唯一的自身序列號來體現，該序列號在不同的標準中有不同的名稱，如 EPC 標準中稱其為電子產品代碼 EPC，即英文ElectronicProduct Code 的縮寫， IS014443 標準中稱其為唯一標識碼 UID，即英文 Unique Identmer 的縮寫【 15】 。 在讀寫器或者應答器內部，對數據進行比較時，遵循這樣的原則，即按位依次比較，先比較低位，再比較高位，約定 01，根據這個比較順序，在判斷大小時，低位數據優先，即兩數A， B 相比較，從低位開始的第一個不相等位的大小決定了兩數的大小，只有當兩個數的全部位均相等時，兩數才相等。 由上式可知， 是逐漸遞歸的，通過遞歸可得： 根據式 ()，上式可化為： 由此可見， 是關于 p 的函數，則 =n/ 也是關于 p的函數，一般情況下，可以參考二項分布，將 p取為 1／ 2。算法的第三個重要性能是系統通信復雜度，顯而易見，系統的通信雙方是讀寫器與應答器，則通信復雜度也應該從這兩方面著手考慮，即讀寫器與應答器各自發送的數據位的位 數。 (2)命令參數長度是固定的，還是變化的。另外，在具體應用時，可能還存在多種不同的說法，如 lbit 長二進制樹中還有修正二進制樹 MBBT，加強二進制樹 EBBT 等區別【 20】 。 基本二進制樹算法的流程圖如圖 2． 3所示： 15 圖 2． 3基本二進制樹算法流程 基本二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號返回給讀寫器。也就是說，下一次讀寫器再發最大序列號時，該應答器不再響應。 假設 RFID系統中有一個讀寫器 R，四個應答器 Tl(10100101)， T2 16 (10l01101)， T3(11010101)， T4(11101101)，在某一時刻，四個應答器 同時進入讀寫器的工作范圍之內，讀寫器發出命令，四個應答器同時響應，由于 其序列號 SN的唯一性，將發生應答器碰撞，從而啟動防碰撞循環，分析如下： 圖 基本二進制樹算法實例 注：圖中共有四輪循環，依次識別出四個應答器，分別以不同格式的線條表 示，并加有循環輪次的數字標識。 (4)讀寫器發送 Sleep(10100101)命令，所有應答器響應該命令，將自身序列號與該 SN(10l00111)比較，其中 T1(10l00101)的序列號等于該值，則 T1 執行該命令，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。 (8)啟動第三輪循環，讀寫器發送 Request(11111111)命令，除 T1， T3 外所有應答器響應該命令，將自身序列號與該 SN(1111ll11)比較，均小于該值，于是所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1X101101，其中 x表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D7 位置 0，低于該位者不變，高于該位者置 1，得到 10101101，作為下一次 Request 命令攜帶的參數值，即 Request(10101101)。 (12)讀寫器發送 Sleep(1ll 01101)命令，所有應答器響應，將自身序列號與該 SN(11101l01)比較，其中 T4(1l1 01101)的序列號等于該值，則 T4 執行該命令，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。也即是二進制樹的節點數目。 假設有兩個應答器，則讀寫器發送命令，兩個應答器響應，發生碰撞，為第一次過程，該時間為： 讀寫器修改命令參數，發出命令，僅一個應答器響應，則識別出該應答器， 這一次過程時間與前一次一致，讀寫器再發送命令，最后一個應答器響應，得到 識別，時間也是一樣的，則總時間為： 當有 n個應答器時，假設識別總時間為： 則當 n+1 個應答器時，讀寫器首先發送命令，應答器全體響應，發生碰撞，這個過程時間為： 讀寫器修改 命令參數，發出命令， k 個應答器響應，余下 p 個不響應， k+p=n+l，則識別出該 k 個應答器需要時間為： 再識別余下 p 個需要時間為： 則這兩者時間之和為： 加上前一次的． t1+t2，總時間為： 19 得證。 本文中，定義根據第一個思路得來的算法為動態二進制樹，它的一個典型應用為 ISOl4443 TYPEA 二進制樹搜索算法。 (2)休眠命令 Sleep(SN)，該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等 于，則該應答器被選中，進入休眠狀態，也即是不再響應 Request 命令，除非該應答器通過先離開讀寫器工作范圍再進入的方式重新上電，才可以再次響應 Request 命令。 注：如果上一次發出的 Request 為全 l，則表明讀寫器工作范圍內只有一個應答器，此時應答器返回數據為完整序列號，以該序列號作為 Sleep 命令參數。低于該位者不變。 (3)讀寫器發送 Request(00l01)命令，所有應答器響應，將自身序列號與該SN(00101)比較，其中 Tl(10100101)的序列號對應位等于該值，則 Tl 返回剩余序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數 00101 與返回數據 101組合起來，作為下一次 Sleep 命令攜帶的參數值，即 Sleep(10100101)。根據分析，算法執行過程中，讀寫器與應答器傳送的 數據主體是應答器的序列號，為了便于分析，假定數據交換過程中，雙方只傳送序列號 SN，則在基本算法中，讀寫器與應答器均傳送了序列號全部長度，而在動態算法中，讀寫器傳送序列號的部分位，應答器再傳送剩余位，兩者組合起來才得到全部的序列號，顯然，雖然每次傳送時動態算法的數據長度不同，但是在整個算法執行過程中，基本算法傳送了兩倍序列號，動態算法則只傳送了一倍數據量，從而可知，動態算法傳送的信息量是基本算法的 50％，從而數據傳輸時間也是原基本算法的 50在本例中，由于假定了應答器的序列號為 8 位長度二進制數，所以這個動態變化 的優勢并不明顯，然而，事實上在實際應用中，應答器序列號長度往往是極大的，比如說常見的是 96 位，在這樣的情況下，動態算法的優勢就體現出來了。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。 退避式二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號發回給讀寫器。 (3)讀寫器將處理后的最大序列號發送給應答器，應答器序列號與該值比較，小于或等于該值者，將自身序列號發回． (4)循環這個過程，選出一個最小序列號的應答器，與之正常通信后，命令該應答器進入休眠狀態，即除非重新上電，否則不再響應讀寫器請求命令。 (4)讀寫器發送 Sleep(10l00l01)命令，所有應答器響應，將自身序列號與該SN(10100ll1)比較，其中 T1(10100l01)的序列號等于該值，則 Tl 執行該命令，進入休眠狀態， 即除非重新上電，否則不再對 Re