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