【正文】 內(nèi)，讀寫器發(fā)出命令，四個(gè)應(yīng)答器同時(shí)響應(yīng)，由于 其序列號(hào) SN的唯一性，將發(fā)生應(yīng)答器碰撞，從而啟動(dòng)防碰撞循環(huán)，分析如下： 圖 基本二進(jìn)制樹算法實(shí)例 注：圖中共有四輪循環(huán)，依次識(shí)別出四個(gè)應(yīng)答器，分別以不同格式的線條表 示，并加有循環(huán)輪次的數(shù)字標(biāo)識(shí)。 注：第五步時(shí)，從步驟 1開始重復(fù)，也就是說(shuō)，讀寫器識(shí)別完一個(gè)應(yīng)答器后，將重新發(fā)送原始的最大序列號(hào)。也就是說(shuō)，下一次讀寫器再發(fā)最大序列號(hào)時(shí)，該應(yīng)答器不再響應(yīng)。 (3) 讀寫器將處理后的序列號(hào)發(fā)送給應(yīng)答器，應(yīng)答器序列號(hào)與該值比較，小于或等于該值者，將自 身序列號(hào)返回給讀寫器。 基本二進(jìn)制樹算法的流程圖如圖 2． 3所示： 15 圖 2． 3基本二進(jìn)制樹算法流程 基本二進(jìn)制樹算法的步驟如下： (1) 應(yīng)答器進(jìn)入讀寫器工作范圍，讀寫器發(fā)出一個(gè)最大序列號(hào)，所有應(yīng)答器的序列號(hào)均小于該最大序列號(hào)，所以在同一時(shí)刻將自身序列號(hào)返回給讀寫器。注： Request(SN)初始值設(shè)為 Request(11111111)。另外，在具體應(yīng)用時(shí)，可能還存在多種不同的說(shuō)法，如 lbit 長(zhǎng)二進(jìn)制樹中還有修正二進(jìn)制樹 MBBT，加強(qiáng)二進(jìn)制樹 EBBT 等區(qū)別【 20】 。需要說(shuō)明的是，這只是一個(gè)大略的分類法，主要目的在于說(shuō)明二進(jìn)制樹分類的基本原則。 (2)命令參數(shù)長(zhǎng)度是固定的，還是變化的。 2． 2． 3 算法分類 在基本的二進(jìn)制樹搜索算法的基礎(chǔ)上，有多種形式的二進(jìn)制樹搜索算法，它 14 們之間主要的區(qū)別在于命令的數(shù)據(jù)形式，主要有兩點(diǎn)。算法的第三個(gè)重要性能是系統(tǒng)通信復(fù)雜度，顯而易見(jiàn)，系統(tǒng)的通信雙方是讀寫器與應(yīng)答器，則通信復(fù)雜度也應(yīng)該從這兩方面著手考慮，即讀寫器與應(yīng)答器各自發(fā)送的數(shù)據(jù)位的位 數(shù)。 馬爾可夫鏈遍歷性分布要滿足下列兩個(gè)條件 【 18】 ： 這里有： 也就是 n個(gè)信息包從發(fā)生碰撞開始傳輸?shù)?CRI區(qū)間長(zhǎng)度的數(shù)學(xué)期望， 是 在一個(gè)時(shí)隙內(nèi)到達(dá)這個(gè)系統(tǒng)信息包的期望值，該過(guò)程屬于泊松過(guò)程【 l9】 。 由上式可知， 是逐漸遞歸的，通過(guò)遞歸可得： 根據(jù)式 ()，上式可化為： 由此可見(jiàn)， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p的函數(shù)，一般情況下，可以參考二項(xiàng)分布，將 p取為 1／ 2。 分析如下： n=l，顯而易見(jiàn)，在第一個(gè)時(shí)隙內(nèi)不發(fā)生碰撞，可以成功識(shí)別該應(yīng)答器， =1。 在讀寫器或者應(yīng)答器內(nèi)部，對(duì)數(shù)據(jù)進(jìn)行比較時(shí)，遵循這樣的原則，即按位依次比較，先比較低位，再比較高位，約定 01，根據(jù)這個(gè)比較順序，在判斷大小時(shí)，低位數(shù)據(jù)優(yōu)先，即兩數(shù)A， B 相比較，從低位開始的第一個(gè)不相等位的大小決定了兩數(shù)的大小，只有當(dāng)兩個(gè)數(shù)的全部位均相等時(shí)，兩數(shù)才相等。如圖 2． 1所示。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統(tǒng)當(dāng)中，每個(gè)應(yīng)答器都是獨(dú)一無(wú)二的，它們的獨(dú)立性通過(guò)唯一的自身序列號(hào)來(lái)體現(xiàn)，該序列號(hào)在不同的標(biāo)準(zhǔn)中有不同的名稱，如 EPC 標(biāo)準(zhǔn)中稱其為電子產(chǎn)品代碼 EPC，即英文ElectronicProduct Code 的縮寫， IS014443 標(biāo)準(zhǔn)中稱其為唯一標(biāo)識(shí)碼 UID，即英文 Unique Identmer 的縮寫【 15】 。從應(yīng)用的角度來(lái)說(shuō)，正確有效的識(shí)別是實(shí)際所需要的，因此下文將著重于二進(jìn)制樹防碰撞算法的研究。時(shí)分多路法按照能量的供給者可以分為兩大類，一類是應(yīng)答器驅(qū)動(dòng)型，另一類是讀寫器驅(qū)動(dòng)型，這也正是對(duì)應(yīng)了第一章中 RFID系統(tǒng)分類思路中的有源系統(tǒng)和無(wú)源系統(tǒng)，根據(jù)實(shí)際應(yīng)用情況，無(wú)源系統(tǒng)是應(yīng)用最廣泛的一類，所以下文重點(diǎn)研究讀寫器驅(qū)動(dòng)型的時(shí)分多路法。 11 2 現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法 2． 1 RFID 防碰撞算法概述 RFID 系統(tǒng)的數(shù)據(jù)通信雙方是讀寫器和應(yīng)答器，在實(shí)際的 RFID 系統(tǒng)工作時(shí)，可能會(huì)出現(xiàn)同時(shí)多個(gè)讀寫器和多個(gè)應(yīng)答器共存的情況，毫無(wú)疑問(wèn)，此時(shí)系統(tǒng)的數(shù)據(jù)交換就會(huì)出現(xiàn)信道與時(shí)序上的重疊，也就是發(fā)生了碰撞，在多個(gè)讀寫器與多個(gè)應(yīng)答器的射頻識(shí)別系統(tǒng)中，存在著兩種形式的沖突方式，一種是同一應(yīng)答器同時(shí)收到不同讀寫器發(fā)出的命令，另一種是同一個(gè)讀寫器同時(shí)收到多個(gè)不同應(yīng)答器返回的數(shù)據(jù)，前者我們稱為讀寫器碰撞，后者稱為應(yīng)答器碰撞【 9】，在實(shí)際應(yīng)用當(dāng)中，一般是讀寫器做為主設(shè)備，來(lái)識(shí)別多個(gè)應(yīng)答器，所以發(fā)生讀寫器碰撞的應(yīng)用場(chǎng)合是不多的，因此下文將 著重研究應(yīng)答器碰撞。 第 4 章： FPGA 實(shí)現(xiàn)改進(jìn)型二進(jìn)制樹防碰撞算法。 第 3 章：改進(jìn)型二進(jìn)制樹防碰撞算法。 第 2 章：現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法?；谏鲜隹紤]，論文將分四章來(lái)予以講述，文章結(jié)構(gòu)與內(nèi)容安排如下： 第 1 章：緒論。 在上述前提下，基于應(yīng)答器的確定型二進(jìn)制樹防碰撞算法是目前最好的一種選擇，對(duì)其進(jìn)行研究，是最有實(shí)際應(yīng)用價(jià)值的，所以，本文將對(duì)其進(jìn)行理論分析與具體實(shí)現(xiàn)，在研究過(guò)程中，注重與新一代智能 RFID 系統(tǒng)的結(jié)合，應(yīng)用擁有強(qiáng)大功能的 FPGA(FieldProgrammable GateArray)做 為算法運(yùn)行的微處理器，這種思路將是未來(lái) RFID 技術(shù)發(fā)展的重要方向， RFID 技術(shù)中的關(guān)鍵算法與先進(jìn)的電子技術(shù) FPGA 的結(jié)合，將為 RFID 技術(shù)的應(yīng)用拓開廣闊的前景。在實(shí)際的應(yīng)用當(dāng)中，應(yīng)答器由于其低成本的優(yōu)越 ,從而得到大量的生產(chǎn)，而讀寫器往往是固定在系統(tǒng)的某處，來(lái)識(shí)別多個(gè)應(yīng)答器，所以碰撞的主要情況是應(yīng)答器碰撞，即一個(gè)讀寫器的工作范圍內(nèi)同時(shí)出現(xiàn)了 多個(gè)應(yīng)答器，并且對(duì)該讀寫器發(fā)出的命令同時(shí)予以響應(yīng)，從而導(dǎo)致讀寫器無(wú)法正確的識(shí)別出一個(gè)應(yīng)答器，稱該現(xiàn)象為發(fā)生了應(yīng)答器碰撞。總之，由于多目標(biāo)識(shí)別應(yīng)用的需要， RFID 系統(tǒng)防碰撞問(wèn)題 成為了關(guān)鍵技術(shù)，為了解決碰撞，可以從硬件和軟件兩方面著手，由于 RFID 系統(tǒng)的大規(guī)模應(yīng)用限制了成本，所以，硬件實(shí)現(xiàn)是不實(shí)際的，因此就需要采用一定的防碰撞算法來(lái)予以解決。目前關(guān)于防碰撞算法的研究還在進(jìn)行當(dāng)中，理論成果已經(jīng)得出了很多，許多國(guó)際標(biāo)準(zhǔn)也對(duì)一些成熟的算法進(jìn)行了規(guī)定，但是無(wú)論在理論效率還是實(shí)際應(yīng)用上，都還存在很大的改進(jìn)空間。在 RFID 系統(tǒng)中，當(dāng)工作范圍內(nèi)同時(shí)出現(xiàn)了多個(gè)讀寫器和多個(gè)應(yīng)答器時(shí)，讀寫器與讀寫器之間，應(yīng)答器與應(yīng)答器之間的相互干擾，稱 RFID 系統(tǒng)發(fā)生了碰撞【 7】 ，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無(wú)法得到正確的讀取，一方面影響了產(chǎn)品的識(shí)別，另一方面還可 能導(dǎo)致信息的泄露。 1． 3． 3 RFID 防碰撞算法 隨著 RFID 技術(shù)的發(fā)展，多目標(biāo)識(shí)別成為了一個(gè)很重要 的應(yīng)用方向，特別在目標(biāo)跟蹤，物品識(shí)別，訪問(wèn)控制等操作中，利用 RFID 技術(shù)，對(duì)附著在不同目標(biāo)上的應(yīng)答器快速可靠的進(jìn)行識(shí)別，從而大大提高了定位的精確度，管理的自動(dòng)化促進(jìn)了整個(gè)產(chǎn)業(yè)鏈的發(fā)展。但是 RFID 本身的技術(shù)難度，以及標(biāo)準(zhǔn)帶來(lái)的經(jīng)濟(jì)利益的沖突，使得該目標(biāo)實(shí)施起來(lái)非常困難。 1． 3． 2 RFID 標(biāo)準(zhǔn)統(tǒng)一化 RFID 最初是各個(gè)廠家在各自的獨(dú)立標(biāo)準(zhǔn)下開發(fā)出來(lái)的，缺乏統(tǒng)一的規(guī)范，因此制約了該項(xiàng)技術(shù)在大規(guī)模系統(tǒng)中的應(yīng)用，隨著 RFID 技術(shù)的發(fā)展，參與到其中的國(guó)家，組織，企業(yè)也越來(lái)越多，目前形成了國(guó)際標(biāo)準(zhǔn)化組織 ISO，泛在 ID中心 UID，全球電子產(chǎn)品代碼管理中心 EPC 三大標(biāo)準(zhǔn)體系，這些標(biāo)準(zhǔn)涉及到 RFID系統(tǒng)的物理結(jié)構(gòu)，通信協(xié)議，防碰撞算法，應(yīng)用系統(tǒng)接口協(xié)議等等多個(gè)方面的內(nèi)容，它們針對(duì)不同的頻率，基于不同的工作原理，甚至在同樣的應(yīng)用背景下也有著巨大的協(xié)議上的區(qū)別。 (4)交通管理 交通管理是 RFID 最先應(yīng)用的領(lǐng)域，目前已經(jīng)擁有了成熟的技術(shù)，它利用了應(yīng)答器便捷快速識(shí)別，可靠性高，安全性強(qiáng)的特點(diǎn)，目前主要應(yīng)用范圍是電子車票，高速公路收費(fèi)等方面，在我國(guó)深圳，基于 RFID 技術(shù)的高速公路收費(fèi)系統(tǒng)已經(jīng)得到了成功的應(yīng)用。 (3)防偽應(yīng)用 應(yīng)答器在防偽應(yīng)用中有識(shí)別快速，偽造難，成本低等優(yōu)點(diǎn)，再加上安全認(rèn)證和加密功能，就可以大大提高偽造的難度和成本，同時(shí)，在識(shí)別的時(shí)刻，可以通過(guò)讀寫器的快速閱讀功能，在瞬間得出所有物品的信息，并加以記錄 和處理。這方面應(yīng)用的典型例子是我國(guó)目前實(shí)行的二代身份證，它基于 ISO／ IEC14443 標(biāo)準(zhǔn)定義的 TYPE B 類型卡。 (1)物流管理 ． 物流管理是 RFID 技術(shù)最具應(yīng)用前景的領(lǐng)域，近年來(lái)提出了一個(gè)物聯(lián)網(wǎng)的概念，意在將全球所有的物品信息都用唯一的電子代碼來(lái)表示，從而將這些物品都聯(lián)系在一起，可以隨時(shí)隨地的識(shí)別，追蹤，管理這些物品，最終在產(chǎn)品，用戶，企業(yè)和政府之間建立但是該應(yīng)用涉及到的方面太廣，技術(shù)難度很大，目前還在研究當(dāng)中。同時(shí)，根據(jù) RFID 系統(tǒng)的不同，在供電方式上有無(wú)源或者有源，調(diào)制方式上有幅度調(diào)制或者相位調(diào)制，數(shù)據(jù)讀取上有電感耦合或者反向散射等區(qū)別【 5】 。 8 1． 2． 3 RFID 系統(tǒng)工作原理 RFID 是一門多學(xué)科綜合技術(shù)，涉及到電磁場(chǎng)理論，數(shù)字電路，模擬電路，無(wú)線電廣播，通信原理等多方面知識(shí) RFlD 系統(tǒng)中，讀寫器將要發(fā)送的信號(hào)調(diào)制到載波上，經(jīng)由射頻通道，通過(guò)天線發(fā) 送出去，應(yīng)答器上的電壓根據(jù)載波的變化而變化，將該電壓信號(hào)進(jìn)行整流和濾波后，得到解調(diào)后的數(shù)據(jù)，這是下行鏈路的過(guò)程，應(yīng)答器傳輸?shù)臄?shù)據(jù)的變化控制應(yīng)答器天線上負(fù)載電阻的通斷，從而促使讀寫器天線上電壓的變化，從而實(shí)現(xiàn)了數(shù)據(jù)的上行鏈路傳輸。 (2)半無(wú)源系統(tǒng)：應(yīng)答器內(nèi)的電池僅做輔助作用。 (4)混頻：多個(gè)頻率的混合使用，典型應(yīng)用為 134KHz+430MHz。 根據(jù)工作頻率的大小， RFID 系統(tǒng)可以分為如下四個(gè)方面： (1)低頻： 30～ 300KHz，典型應(yīng)用為 134KHz。 (2)遙耦合：典型的作用范圍為 lcm～ 1m。 綜上所述，一個(gè)典型的 RFID 系統(tǒng)的組成如圖所示： 圖 RFID 系統(tǒng)組成 1． 2． 2 RFID 系統(tǒng)分類 RFID 系統(tǒng)依據(jù)不同的標(biāo)準(zhǔn)，可以分為很多類別，各個(gè)不同 的 RFID 系統(tǒng)，在工作方式和應(yīng)用范圍上，有著各自不同的特點(diǎn)，在應(yīng)用時(shí)要根據(jù)實(shí)際需要來(lái)選擇。后端應(yīng)用環(huán)境主要完成數(shù)據(jù)信息的存儲(chǔ)及處理， 7 它實(shí)質(zhì)上就是一個(gè)數(shù)據(jù)管理系統(tǒng)，也是一個(gè)全局控制系統(tǒng)，一般由 PC 機(jī)或者工作站組成，同時(shí)也包括了應(yīng)用軟件在內(nèi)，整個(gè)后端應(yīng)用 環(huán)境負(fù)責(zé)接收來(lái)自讀寫器的數(shù)據(jù)，并進(jìn)行存儲(chǔ)以及相應(yīng)的處理，協(xié)同調(diào)節(jié)多個(gè)讀寫器的工作，該部分在應(yīng)用中常稱為中間件 (Savant)，它擴(kuò)展了 RFID 系統(tǒng)的應(yīng)用范圍和應(yīng)用能力，是未來(lái) RFID 系統(tǒng)智能化，大型化發(fā)展的有力技術(shù)支撐，是 RFID 技術(shù)發(fā)展的重要方式。數(shù)據(jù)交換環(huán)節(jié)即 RFID 系統(tǒng)中的讀出寫入設(shè)備，它是系統(tǒng)的核心部件，是后端應(yīng)用環(huán)境和前端信息載體的數(shù)據(jù)通道，在實(shí)際應(yīng)用中，往往被稱為查 詢器，掃描器，閱讀器，編程器等，本文建議采用讀寫器 (Read／ Write Device)這種更具普遍意義的說(shuō)法，這樣既包括了從應(yīng)答器中讀出信息，同時(shí)也包括了向應(yīng)答器中寫入信息。 應(yīng)答器的典型產(chǎn)品有 TI公司的 6000 系列， Philips 公司的 I一般來(lái)說(shuō)，應(yīng)用最廣泛的是無(wú)源 +集成電路固化 +靜態(tài)隨機(jī)存儲(chǔ)的應(yīng)答器。在 RFID 系統(tǒng)中，應(yīng)答器放置在待識(shí)別的物體上，它內(nèi)部存儲(chǔ)的信息表征著該物品的獨(dú)一性。 1． 2 RFID 系統(tǒng) 1． 2． 1 RFID 系統(tǒng)組成 根據(jù)實(shí)際應(yīng)用環(huán)境， RFID 系統(tǒng)結(jié)構(gòu)有多種不同分法，一般來(lái)說(shuō)，一個(gè)典型RFID 系統(tǒng)包括三個(gè)部分：前端信息載體，數(shù)據(jù)交換環(huán)節(jié)，后端應(yīng)用環(huán)境【 3】。 RFID 技術(shù)通過(guò)射頻 方式進(jìn)行非接觸的雙向通信，達(dá)到自動(dòng)識(shí)別的目的，它源起于上世紀(jì)四五十年代，最初是基于雷達(dá)與微波理論的發(fā)展，自從上世紀(jì)九十年代以來(lái)， RFID 技術(shù)快速發(fā)展，得到了廣泛的應(yīng)用，進(jìn)入新世紀(jì)后，各個(gè)國(guó)家，組織還有企業(yè)都加大了對(duì) RFID 技術(shù)的投入，生產(chǎn)了大批相應(yīng)的產(chǎn)品，在多個(gè)領(lǐng)域有了成功的應(yīng)用案例。 【 關(guān)鍵詞 】 ： 射頻識(shí)別；防碰撞算法；讀寫器；應(yīng)答器；現(xiàn)場(chǎng)可編程門陣列 Abstract RFID is anewly developedtechnologywhich municates through the—contact RF signal，so asto achieve objective automatic identification． Along with the development of RFID technology， how to realize Data Exchange accurately amongMultiple Targets at the same time bees the key problem of RFID technology． RFID anticollision algorithm is the solution to the above mentioned problems． In all the algorithms， binary algorithm is most widely used as an international standard fbr its exactness ofidentincation． International standards have put forward manyregulations on binary algorithm． It not onlypromotes the development of anti． coUision algorithm， but also b“ngs t