通信工程畢業設計-rfid二進制樹防碰撞算法的研究與實現-資料下載頁

【導讀】號進行非接觸式的雙向數據通信，從而達到自動識別的目的。理的算法來有效的解決該問題，稱為RFID系統的防碰撞算法。在傳統思路中，一般是通過單片機來進行算法處理，隨著RFID技。程的專用集成電路，FPGA擁有高速度，可編程等多個適應于算法處理的優點，系統二進制樹防碰撞算法，進行了理論與實踐方面的探討，主要分為三個方面，樹算法，該算法識別速度快，執行效率高，極大的改進了識別效果。KeyWords：RFID；Anticollision；Read／WriteDeVices；Transponders；FPGA

　　

【正文】 于該位者不變。 (3) 讀寫器將處理后的碰撞起始位與低位發送給應答器，應答器序列號與該值比較，等于該值者，將自身序列號中剩余位發回． (4) 循環這個過程，就可以選出一個最小序列號的應答器，與該應答器進行正常通信后，發出命令使該應答器進入休眠狀態，即除非重新上電，否則不對讀寫器請求命令起響應。 (5) 重復上述過程，即可按序列號從小到大依次識別出各個應答器． 2． 4． 2 實例演示 動態二進制樹算法的實例演示如圖 2． 6 所示 ，基本設置同基本二進制樹算法： 圖 2． 6動態二進制樹算法實例 (1)啟動第一輪循環，讀寫器發送 Request(11111111)命令，所有應答器響應該命令，按照約定，命令參數為全 1時，所有應答器均返回自身序列號給讀寫器，因為序列號的唯一性，應答器返回的序列號在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 1XXXXl01，其中 X 表示該位發生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，得到 0101，則下一次 Request命令攜帶的參數值，即 Request(0101)。 (2)讀寫器發送 Request(0l01)命令，所有應答器響應，將自身序列號與該SN(0101)比較，其中 Tl(10l00101)， T3(110l0l01)的序列號低四位等于該值，則 T1， T3 返回剩余位給讀寫器，在讀寫器接收端發生碰撞，讀寫器檢測到返回數據為 lXXX，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，得到 0010l，作為下一次 Request 命令參數值，即 Request(00l01)。 (3)讀寫器發送 Request(00l01)命令，所有應答器響應，將自身序列號與該SN(00101)比較，其中 Tl(10100101)的序列號對應位等于該值，則 Tl 返回剩余序列號給讀寫器，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 l0l，讀寫器做如下處理：將上一次 Request(00l01)命令參數 00101 與返回數據 101組合起來，作為下一次 Sleep 命令攜帶的參數值，即 Sleep(10100101)。 (4)讀寫器發送 Sleep(10100101)命令，所有應答器響應該命令，將自身序列 22 號與該 SN(10100101)比較，其中 T1(10100101)的序列號等于該值，則 Tl執行該命令，進入休眠狀態，即除非重新上電 ，否則不再響應 Request 命令。 (5)啟動新一輪循環，重復上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數變化過程見圖 2． 6中標示，具體內容不再詳述。 2． 4． 3 性能評價 與 3． 3． 2基本二進制樹實例圖比較可知，動態二進制樹算法的識別過程中，節點數目，循環輪次都是一樣的，但是每次循環過程中，讀寫器命令與應答器指令所攜帶的參數都是在動態改變長度的，所以動態算法的優勢主要體現在兩個方面，一是算法執行過程中數據傳輸時間；二是算法執行過程中數據信息量。根據分析，算法執行過程中，讀寫器與應答器傳送的 數據主體是應答器的序列號，為了便于分析，假定數據交換過程中，雙方只傳送序列號 SN，則在基本算法中，讀寫器與應答器均傳送了序列號全部長度，而在動態算法中，讀寫器傳送序列號的部分位，應答器再傳送剩余位，兩者組合起來才得到全部的序列號，顯然，雖然每次傳送時動態算法的數據長度不同，但是在整個算法執行過程中，基本算法傳送了兩倍序列號，動態算法則只傳送了一倍數據量，從而可知，動態算法傳送的信息量是基本算法的 50％，從而數據傳輸時間也是原基本算法的 50在本例中，由于假定了應答器的序列號為 8 位長度二進制數，所以這個動態變化 的優勢并不明顯，然而，事實上在實際應用中，應答器序列號長度往往是極大的，比如說常見的是 96 位，在這樣的情況下，動態算法的優勢就體現出來了。 2． 5 退避式二進制樹防碰撞算法 2． 5． 1 算法思路 退避式二進制樹搜索算法是對基本二進制樹搜索算法的一種改進，根據 2． 3基本二進制樹算法的分析可知，每識別一個應答器后，讀寫器恢復 Request 命令參數的初始值，重新從二進制樹的根部開始執行，對此可以采取退避的思想，即每次識別出一個應答器后，算法返回其上一個父節點，而不返回整棵樹的根節點。 定義兩個具有普遍意義的命令來描述 算法： (1)請求命令 Request(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應答器回送其 SN 給讀寫器。注： Request(SN)初始值設為 Request(11ll1111)。 (2)休眠命令 Sleep(SN)：該命令攜帶一個參數 SN，應答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應答器被選中，進入休眠狀態，即除非重新上電，否則不再響應 Request 命令。退避式二進制樹算法的流程見圖2． 7，基本設置可參考基本二進制樹算法： 23 圖 2． 7退避式二進制樹算法流程 如圖所示，退避式二進制樹算法的流程與基本算法的區別在于：基本算法中，一個應答器被識別后，重新啟動新循環時，讀寫器返回整棵樹的根節點，獲取原始 Request 命令參數，而退避式算法中，讀寫器返回上一次發生碰撞節點，獲取Request 命令參數。事實上，退避式算法的改進是基于如下考慮的，在基本二進制樹的分析過程中可見，算法之所以稱為二進制樹，是因為每次碰撞后，均以碰撞起始位為界，將應答器分為兩個部分，形象的看，如同一棵樹在進行從根部到主干到樹枝的一個不斷的分叉過程，所以，分叉也即是 分組的理念是二進制樹算法的本質所在，根據這一點，算法每次分叉到達末端之后，不再返回根部重新開 始分叉，而是返回上一次分叉的節點即可重新開始新的樹干，該節點也即是上一次發生碰撞的節點。采用該返回思路的二進制樹算法，稱為退避式二進制樹算法。 退避式二進制樹算法的步驟如下： (1) 應答器進入讀寫器工作范圍，讀寫器發出一個最大序列號，所有應答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號發回給讀寫器。 (2)由于應答器序列號的唯一性，若應答器數目不小于兩個，必發生碰撞。此時將最大序列號中對應碰撞起始位置 為 O。低于該位者不變，高于該位者置 1。 (3)讀寫器將處理后的最大序列號發送給應答器，應答器序列號與該值比較，小于或等于該值者，將自身序列號發回． (4)循環這個過程，選出一個最小序列號的應答器，與之正常通信后，命令該應答器進入休眠狀態，即除非重新上電，否則不再響應讀寫器請求命令。 (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)。 (2)讀 寫器發送 Request(1l110101)命令，所有應答器響應，將自身序列號與該 SN(111l0l01)比較，其中 T1(10100101)， T3(110l0101)的序列號小于該值，則 Tl， T3 返回自身序列號給讀寫器，在讀寫器接收端發生碰撞，讀 RFID 二進制樹防碰掩算法的研究與實現寫器檢測到返回數據為 1XXX0101，讀寫器做如下處理：將碰撞起始位 D5位置 0，低于該位者不變，高于該位者置 1，得到 11l 00101，作為下一次 Request 命令攜帶的參數值，即 Request(1l100101)。 (3)讀寫器 發送 Request(11100101)命令，所有應答器響應，將自身序列號與 SN(1ll 00101)比較，其中 T1(10100101)序列號小于該值，則 Tl返回序列號，在讀寫器接收端不發生碰撞，讀寫器檢測到返回數據為 10100l01，做如下處理：將該值作為下一次 Sleep 命令參數值，即 Sleep(10100101)。 (4)讀寫器發送 Sleep(10l00l01)命令，所有應答器響應，將自身序列號與該SN(10100ll1)比較，其中 T1(10100l01)的序列號等于該值，則 Tl 執行該命令，進入休眠狀態， 即除非重新上電，否則不再對 Request 命令做出響應。 (5)啟動新一輪循環，重復上述步驟，總計 12步后，依次識別出 T1， T3， T2，T4，參數變化過程見圖 2． 8中標示，具體內容不再詳述。 25 2． 5． 3 性能評價 與基本二進制樹比較可知，退避式算法每次傳送的數據信息量與基本算法是一樣的，區別在于，退避式算法的傳送次數，也即是所遍歷的節點數目比之基本算法大大減少，假設讀寫器工作范圍內有 n個應答器，則所需節點數目為而，則可用式子 2． 19來表示： 數學歸納法證明如下： 當讀寫器工作范圍內只有一個應答器時，顯然有： 假設 n個應答器時，有： 則當系統中有 n+1 個應答器時，由于新增加的這個應答器與原來 n個應答 器的序列號均不相同，為了將其與某個匹配度最高的應答器區分開來，需要在原 來二進制樹中增加一個節點，由于節點之間僅存在父子關系，且僅通過兩條邊相 連，所以有： 得證。 2． 6 本章小結 本章歸納了現有的二進制樹防碰撞算法，將其分為三個基本類別，分別講述了其實現思路，進行了實例演示，并且對其做了性能分析，結果表明，動態算法和退避式算法是對基本算法的兩個改進思路，具有各自的優勢。 3 改進型二進制樹防碰撞算法 3． 1 涉及二進制樹算法的國際標準 3． 1． 1 IS0 15693 ISO l5693【 23】，短距離智能卡 (Vicinity coupling smart cards)標準，讀取距離可高達一分米，使用的頻率為 l3． 56MHz，它設計簡單，生產成本比IS014443 低，大都用來做出入控制、出勤考核等，現在很多企業使用的門禁卡大都使用這一類的標準。符合 IS015693 標準的信號接口部分的性能如下： 工作場強：工作場的最小值為 O． 15A／ m，最大場為 5A／ m。 工作頻率：工作頻率為 13． 56MKz 士 7KHz 26 調制 ：用 2種幅值調制方式，即 l0％和 l00％調制方式。讀寫器應能確定用哪種方式。 100％幅值調制 10％的幅值調制 數據編碼 數據編碼采用脈沖位置調制。兩種數據編碼模式： 256選 1模式和 4選 1模式。 數率：有高和低兩種數率。 表 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】 。 ISO／ IECl4443 標準開始于 1995 年， 單個系統于 1999年進入市場，而其完成在 2021 年以后，迄今為止， ISO／ IECl4443 標準中的非接觸式智能卡的類型可以分為 TypeA 和 TypeB。 TypeC— G 目前已經暫時被列入IS014443 標準，等待復議。 下面簡要介紹一下 ISO／ IECl 4443標準中各個不同類型的非接觸式智能卡。 TypeA 由 Philips 半導體公司首次開發和使用，在亞洲等地區， TypeA 技術和產品占據了很大的市場份額。 TypeA 技術設計簡單扼要，應用項目的開發周期可以很短，同時又能起到足夠的保密作用，可以適用于非常多的應用場 合。 TypeB 是一個開放式的非接觸式智能卡標準，所有的讀寫操作可以由應用系統開發者定義，因此被世界上眾多的智能卡廠家所廣泛接受。 TypeC 由日本索尼公司研制。有兩個主要特點，一是獨特的天線結構和技術，使其讀寫距離可以穩定地達到 10cm 以上，同時其天線結構中鑲嵌的特殊材料 (鐵氧體等材料 )使其天線電磁場的讀寫距離非常均勻，沒有“死區”現象出現，二是 SONY 非接觸智能卡數據寫操作失敗時的數據恢復功能。 TypeD 由 C