通信工程畢業設計-rfid二進制樹防碰撞算法的研究與實現-免費閱讀

　　

【正文】 TypeB 是一個開放式的非接觸式智能卡標準，所有的讀寫操作可以由應用系統開發者定義，因此被世界上眾多的智能卡廠家所廣泛接受。兩種數據編碼模式： 256選 1模式和 4選 1模式。 (5)啟動新一輪循環，重復上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數變化過程見圖 2． 8中標示，具體內容不再詳述。 (2)由于應答器序列號的唯一性，若應答器數目不小于兩個，必發生碰撞。 2． 5 退避式二進制樹防碰撞算法 2． 5． 1 算法思路 退避式二進制樹搜索算法是對基本二進制樹搜索算法的一種改進，根據 2． 3基本二進制樹算法的分析可知，每識別一個應答器后，讀寫器恢復 Request 命令參數的初始值，重新從二進制樹的根部開始執行，對此可以采取退避的思想，即每次識別出一個應答器后，算法返回其上一個父節點，而不返回整棵樹的根節點。 (3) 讀寫器將處理后的碰撞起始位與低位發送給應答器，應答器序列號與該值比較，等于該值者，將自身序列號中剩余位發回． (4) 循環這個過程，就可以選出一個最小序列號的應答器，與該應答器進行正常通信后，發出命令使該應答器進入休眠狀態，即除非重新上電，否則不對讀寫器請求命令起響應。動態二進制樹算法的流程與基本二進制樹算法是一致的，它們的區別在于：基本二進制樹算法中，應答器返回完整序列號，而動態二進制樹算法中，應答器只返回序列號的有效部分；同樣，基本二進制樹算法中，讀寫器生成新 Request 命令時，其命令參數長度是固定為8位的，而動態二進制樹算法中，該命令參數長度是根據應答器返回的序列號來動態變化的。 因為基本二進制樹算法中每次傳輸的序列號 SN 長度相同， ，所以有： 基本二進制樹搜索算法是所有二進制樹算法的基礎，分析基本二進制樹搜索算法的性能可知，對于固定數目的應答器，二進制樹算法的性能主要取決于二進制樹的節點數目和單次傳輸命令參數的時間，事實上，二進制樹的節點數目與應答器分組的思路是直接相 關的，而單次傳輸命令參數的時間則取決于該命令包含的數據位數。 2． 3． 3 性能評價 假設工作范圍內有 N個應答器存在，通過基本二進制樹搜索算法進行防碰撞操作，依次識別出所有應答器。 17 (5)啟動第二 輪循環，讀寫器發送 Request(111l1111)命令，除 T1 外所有應答器響應該命令，將自身序列號與該 SN(11111l11)比較，均小于該值，于是所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1XXXXl01，其中 X 表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 1，得到 11110101，作為下一次 Request 命令攜帶的參數值，即 Request(11110101)。 (5)重復上述過程，即可按序列號從小到大依次識別出各個應答器。 圖 2． 2二進制樹算法分類 2． 3 基本二進制樹防碰撞算法 2． 3． 1 算法思路 定義兩個具有普遍意義的命令來描述算法 ： (1)請求命令 Request(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。該指標的評價標準是基于能量消耗的角度的，即發送的數據信息量越少，則整個系統消耗的能量也越少，這顯然是一個理想的效果。 2． 2． 2 性能指標 定義碰撞解決時期 CRI，即 Collision Resolution Interval【 16】 ，即解決一個讀寫器工作范圍內碰撞所需要的時隙數，對二進制樹算法的評價，一些常用的性能指 標如下所示【 17】 ： 首先是算法執行效率 ， 定義如下：在算法執行過程，一 共 個時隙，識別了 n 個應答器，則 =n/ 表示算法的執行效率。在該類讀寫器驅動型時分多路法中，目前最常用的防碰撞算法有兩種，一類是基于時隙 ALOHA 的統計型算法，另一類是基于二進制樹的確定型算法，統計 型算法的意義是在 一定的時隙范圍內，系統有可能識別出所有應答器 ，確定型算法的最大優點是，在一定的時隙范圍內，系統一定可以將所有的應答器一一識別出來【 13】 。概要性的描述了 RFID 防碰撞算法，對其進行了分類，重點介紹其中的二進制樹防碰撞算法，研究了三種最基本的二進制樹算法，對其進行了原理闡述，性能分析，以及實例演示。依前所述，RFID 系統碰撞主要有兩種情況，讀寫器碰撞和應答器碰撞，讀寫器碰撞是一個應答器同時收到不同讀寫器發出的命令，應答器碰撞是一個讀寫器同時給不同應答器發送命令。由此可見，標準統一化問題的重要性與困難性是并存的，這將是一個任重而道遠的過程。 RFID 在身份識別方面的主要問題是頻段的局限性，一般使用的是 l35KHz 和 13． 56MHz 的工作頻率，這是因為過高的頻段容易帶來對人體有害的電磁輻射。 (3)有源系統：應答器內置電池負責供給工作電壓。幾種典型的分類方式如下所示： 根據作用距離的遠近， RFID 系統可以分為如下三個方面： (1)密耦合：典型的作用范圍為 0～ lcm。由于在 RFID 系統中，應答器是大規模生產的 。 目前，應用最廣泛的自動識別技術大致可以分為光學技術和無線電技術兩種，其中光學技術普遍應用于條形碼和攝像兩大類，而無線電技術在自動識別領域 的 應 用 更 具 體 的 名 稱 為 射 頻 識 別 ， 英 文 名 為 Radio Frequency Identification，簡寫為 RFIDI21。在各種算法當中，二進制樹算法因為它識別應答器的確定性，成為了應用最廣泛的一種，多個國際標準均對其進行了規定，這推動了防碰撞算法的發展，但是也帶來了解決思路不統一的矛盾。在 RFID 系統中，應答器放置在待識別的物體上，它內部存儲的信息表征著該物品的獨一性。后端應用環境主要完成數據信息的存儲及處理， 7 它實質上就是一個數據管理系統，也是一個全局控制系統，一般由 PC 機或者工作站組成，同時也包括了應用軟件在內，整個后端應用 環境負責接收來自讀寫器的數據，并進行存儲以及相應的處理，協同調節多個讀寫器的工作，該部分在應用中常稱為中間件 (Savant)，它擴展了 RFID 系統的應用范圍和應用能力，是未來 RFID 系統智能化，大型化發展的有力技術支撐，是 RFID 技術發展的重要方式。 (4)混頻：多個頻率的混合使用，典型應用為 134KHz+430MHz。 (1)物流管理 ． 物流管理是 RFID 技術最具應用前景的領域，近年來提出了一個物聯網的概念，意在將全球所有的物品信息都用唯一的電子代碼來表示，從而將這些物品都聯系在一起，可以隨時隨地的識別，追蹤，管理這些物品，最終在產品，用戶，企業和政府之間建立但是該應用涉及到的方面太廣，技術難度很大，目前還在研究當中。 1． 3． 2 RFID 標準統一化 RFID 最初是各個廠家在各自的獨立標準下開發出來的，缺乏統一的規范，因此制約了該項技術在大規模系統中的應用，隨著 RFID 技術的發展，參與到其中的國家，組織，企業也越來越多，目前形成了國際標準化組織 ISO，泛在 ID中心 UID，全球電子產品代碼管理中心 EPC 三大標準體系，這些標準涉及到 RFID系統的物理結構，通信協議，防碰撞算法，應用系統接口協議等等多個方面的內容，它們針對不同的頻率，基于不同的工作原理，甚至在同樣的應用背景下也有著巨大的協議上的區別。目前關于防碰撞算法的研究還在進行當中，理論成果已經得出了很多，許多國際標準也對一些成熟的算法進行了規定，但是無論在理論效率還是實際應用上，都還存在很大的改進空間。基于上述考慮，論文將分四章來予以講述，文章結構與內容安排如下： 第 1 章：緒論。 11 2 現有 RFID 二進制樹防碰撞算法 2． 1 RFID 防碰撞算法概述 RFID 系統的數據通信雙方是讀寫器和應答器，在實際的 RFID 系統工作時，可能會出現同時多個讀寫器和多個應答器共存的情況，毫無疑問，此時系統的數據交換就會出現信道與時序上的重疊，也就是發生了碰撞，在多個讀寫器與多個應答器的射頻識別系統中，存在著兩種形式的沖突方式，一種是同一應答器同時收到不同讀寫器發出的命令，另一種是同一個讀寫器同時收到多個不同應答器返回的數據，前者我們稱為讀寫器碰撞，后者稱為應答器碰撞【 9】，在實際應用當中，一般是讀寫器做為主設備，來識別多個應答器，所以發生讀寫器碰撞的應用場合是不多的，因此下文將 著重研究應答器碰撞。如圖 2． 1所示。 馬爾可夫鏈遍歷性分布要滿足下列兩個條件 【 18】 ： 這里有： 也就是 n個信息包從發生碰撞開始傳輸的 CRI區間長度的數學期望， 是 在一個時隙內到達這個系統信息包的期望值，該過程屬于泊松過程【 l9】 。需要說明的是，這只是一個大略的分類法，主要目的在于說明二進制樹分類的基本原則。 (3) 讀寫器將處理后的序列號發送給應答器，應答器序列號與該值比較，小于或等于該值者，將自 身序列號返回給讀寫器。 (2)讀寫器發送 Request(11110101)命令，所有應答器響應該命令，將 自身序列號與該 SN(11110l01)比較，其中 T1(10l00101)， T3(1l010101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1XXX0l01，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，高于該位者置 l，得到 11l00l01，作為下一次 Request 命令攜帶的參數值，即 Request(11100101)。 (10)讀寫器發送 Sleep(10101101)命令，所有應答器響應，將自身序列號與該 SN(10101101)比較，其中 T2(10101101)的序列號等于該值，則 T2執行該命令，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。 通信時間 t定義為數據交換的時間，也即是命令執行的時間。 2． 4 動態二進制樹防碰撞算法 2． 4． 1 算法思路 定義兩個具有普遍意義的命令來描述算法： (1)請求命令 Request( )，該命令攜帶一個參數 SN，長度為，應答器接收到該命令，將自身的 SN中的前 1～ x位與接收到的比較，若兩者相等，則該 答器返回其 SN 的剩余位給讀寫器。 (2) 由于應答器序列號的唯一性，當 應答器數目不小于兩個時，必然發生碰 21 撞。 (5)啟動新一輪循環，重復上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數變化過程見圖 2． 6中標示，具體內容不再詳述。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是 分組的理念是二進制樹算法的本質所在，根據這一點，算法每次分叉到達末端之后，不再返回根部重新開 始分叉，而是返回上一次分叉的節點即可重新開始新的樹干，該節點也即是上一次發生碰撞的節點。 (2)讀 寫器發送 Request(1l110101)命令，所有應答器響應，將自身序列號與該 SN(111l0l01)比較，其中 T1(10100101)， T3(110l0101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發生碰撞，讀 RFID 二進制樹防碰掩算法的研究與實現寫器檢測到返回數據為 1XXX0101，讀寫器做如下處理：將碰撞起始位 D5位置 0，低于該位者不變，高于該位者置 1，得到 11l 00101，作為下一次 Request 命令攜帶的參數值，即 Request(1l100101)。 工作頻率：工作頻率為 13． 56MKz 士 7KHz 26 調制 ：用 2種幅值調制方式，即 l0％和 l00％調制方式。 下面簡要介紹一下 ISO／ IECl 4443標準中各個不同類型的非接觸式智能卡。 TypeD 由 Cub。 ISO／ IECl4443 標準開始于 1995 年， 單個系統于 1999年進入市場，而其完成在 2021 年以后，迄今為止， ISO／ IECl4443 標準中的非接觸式智能卡的類型可以分為 TypeA 和 TypeB。 3 改進型二進制樹防碰撞算法 3． 1 涉及二進制樹算法的國際標準 3． 1． 1 IS0 15693 ISO l5693【 23】，短距離智能卡 (Vicinity coupling smart cards)標準，讀取距離可高達一分米，使用的頻率為 l3． 56MHz，它設計簡單，生產成本比IS014443 低，大都用來做出入控制、出勤考核等，現在很多企業使用的門禁卡大都使用這一類的標準。 (3)讀寫器將處理后的最大序列號發送給應答器，應答器序列號與該值比較，小于或等于該值者，將自身序列號發回． (4)循環這個過程，選出一個最小序列號的應答器，與之正常通信后，命令該應答器進入休眠狀態，即除非重新上電，否則不再響應讀寫器請求命令。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，