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