【正文】 ...........58致謝 ...............................................................621 引言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)中，當(dāng)工作范圍內(nèi)同時出現(xiàn)了多個讀寫器和多個應(yīng)答器時，讀寫器與讀寫器之間，應(yīng)答器與應(yīng)答器之間的相互干擾，稱 RFID 系統(tǒng)發(fā)生了碰撞【7】 ，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產(chǎn)品的識別，另一方面還可能導(dǎo)致信息的泄露?？傊?，由于多目標識別應(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(FieldProgrammableGateArray)做為算法運行的微處理器，這種思路將是未來 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ū)動型的時分多路法。為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統(tǒng)當(dā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ù)的大小，只有當(dāng)兩個數(shù)的全部位均相等時，兩數(shù)才相等。由上式可知， 是逐漸遞歸的，通過遞歸可得：根據(jù)式()，上式可化為：由此可見， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p 的函數(shù)，一般情況下，可以參考二項分布，將 p 取為 1／2。算法的第三個重要性能是系統(tǒng)通信復(fù)雜度，顯而易見，系統(tǒng)的通信雙方是讀寫器與應(yīng)答器，則通信復(fù)雜度也應(yīng)該從這兩方面著手考慮，即讀寫器與應(yīng)答器各自發(fā)送的數(shù)據(jù)位的位數(shù)。(2)命令參數(shù)長度是固定的，還是變化的。另外，在具體應(yīng)用時，可能還存在多種不同的說法，如 lbit 長二進制樹中還有修正二進制樹 MBBT，加強二進制樹 EBBT 等區(qū)別【20】 ?；径M制樹算法的流程圖如圖 2．3 所示：圖 2．3 基本二進制樹算法流程基本二進制樹算法的步驟如下：(1) 應(yīng)答器進入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，所有應(yīng)答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號返回給讀寫器。也就是說，下一次讀寫器再發(fā)最大序列號時，該應(yīng)答器不再響應(yīng)。假設(shè) RFID 系統(tǒng)中有一個讀寫器 R，四個應(yīng)答器 Tl(10100101)，T2(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)，得到識別，時間也是一樣的，則總時間為：當(dāng)有 n 個應(yīng)答器時，假設(shè)識別總時間為：則當(dāng) 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，總時間為：得證。本文中，定義根據(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)，即除非重新上電，否則不再對 Request 命令做出響應(yīng)。3 改進型二進制樹防碰撞算法3．1 涉及二進制樹算法的國際標準3．1．1 IS0 15693ISO l5693【23】 ，短距離智能卡(Vicinity coupling smart cards)標準，讀取距離可高達一分米，使用的頻率為 l3．56MHz，它設(shè)計簡單，生產(chǎn)成本比IS014443 低，大都用來做出入控制、出勤考核等，現(xiàn)在很多企業(yè)使用的門禁卡大都使用這一類的標準。100％幅值調(diào)制10％的幅值調(diào)制數(shù)據(jù)編碼數(shù)據(jù)編碼采用脈沖位置調(diào)制。ISO／IECl4443 標準開始于 1995年，單個系統(tǒng)于 1999 年進入市場，而其完成在 2022 年以后，迄今為止，ISO／IECl4443 標準中的非接觸式智能卡的類型可以分為 TypeA 和TypeB。TypeA 技術(shù)設(shè)計簡單扼要，應(yīng)用項目的開發(fā)周期可以很短，同時又能起到足夠的保密作用，可以適用于非常多的應(yīng)用場合。TypeD 由 Cubic 公司研制，該系統(tǒng)的非接觸方式讀卡／認證速度非?？焖?，約為 70ms 左右，并且實現(xiàn)了數(shù)據(jù)加密技術(shù)，開創(chuàng)了交通系統(tǒng)中“刷卡”的先例。TypeF 由歐洲 LEGIC 公司研制，其保密系統(tǒng)的產(chǎn)品在歐洲市場占有率達到60％以上。TYPEA 和 TYPEB 的不同主要在于載波的調(diào)制深度和位編碼方式，TYPEA 采用l00％ASK 調(diào)制、同步時序以及改進的米勒(Miller)編碼方式，使用的是間斷式調(diào)制方式，即當(dāng)表示信息“l(fā)”時，表示有信號到卡，當(dāng)表示信息“0“時，沒有信號到卡。在價格上由于 A 類的廣泛性和芯片本身的低端設(shè)計性，A 類有更大的優(yōu)勢。3．2．2 算法思路PCD 的初始化，防碰撞，以及數(shù)據(jù)交換的流程如圖 3．1 所示：圖 3．1ISOl4443 標準 TYPE A 類型 PCD 通信全過程如圖所示，分為這么幾個部分：1．PCD 與 PICC 進行符合 lSO／IECl4443．2 的初始化通信。(4)PCD 對該 Atq 進行檢測，決定下一步動作。(2)PIC。2．PCD 與 PICC 進行符合 I