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