【文章內(nèi)容簡(jiǎn)介】 RFID 系統(tǒng)發(fā)生了碰撞【 7】 ，從而導(dǎo)致數(shù)據(jù)不能正確的傳輸，信息無法得到正確的讀取，一方面影響了產(chǎn)品的識(shí)別，另一方面還可 能導(dǎo)致信息的泄露。在全球信息安全意識(shí)廣泛普及的背景下，可靠的安全機(jī)制成為了 RFID技術(shù)發(fā)展的關(guān)鍵性制約因素，如何有效的解決 RFID 系統(tǒng)的碰撞問題，成為了技術(shù)的關(guān)鍵，對(duì)此就需要采用一定的防碰撞算法來對(duì)其進(jìn)行處理。目前關(guān)于防碰撞算法的研究還在進(jìn)行當(dāng)中，理論成果已經(jīng)得出了很多，許多國(guó)際標(biāo)準(zhǔn)也對(duì)一些成熟的算法進(jìn)行了規(guī)定，但是無論在理論效率還是實(shí)際應(yīng)用上，都還存在很大的改進(jìn)空間。 1． 4 課題提出的背景及其意義 早期的 RFID 技術(shù)很少涉及到防碰撞問題，而在近年來，隨著 RFID 技術(shù)的發(fā)展，應(yīng)用范圍的擴(kuò)大，使得防碰撞問題日 益成為制約 RFID 發(fā)展的關(guān)鍵技術(shù)，原因有兩個(gè)，首先，早期的 RFID 一般是近距離感應(yīng)耦合式系統(tǒng)，其操作頻率 功率普遍較低，讀取的速度慢，范圍小，所以也較少有發(fā)生碰撞的可能，而目前 RFID應(yīng)用中多目標(biāo)識(shí)別成為了主流方向，這就要求實(shí)現(xiàn)在多個(gè)物品中正確的識(shí)別出單個(gè)目標(biāo)；其次，早期的 RFID 應(yīng)用沒有統(tǒng)一的規(guī)范，各個(gè)廠家的 RFID 產(chǎn)品也僅是 10 應(yīng)用在單個(gè)的系統(tǒng)當(dāng)中，不存在碰撞的可能，而近年來 RFID 應(yīng)用迅速發(fā)展，各個(gè)不同 RFID 制造商的產(chǎn)品之間的不兼容，也帶來了碰撞問題?？傊?，由于多目標(biāo)識(shí)別應(yīng)用的需要， RFID 系統(tǒng)防碰撞問題 成為了關(guān)鍵技術(shù)，為了解決碰撞，可以從硬件和軟件兩方面著手，由于 RFID 系統(tǒng)的大規(guī)模應(yīng)用限制了成本，所以，硬件實(shí)現(xiàn)是不實(shí)際的，因此就需要采用一定的防碰撞算法來予以解決。依前所述，RFID 系統(tǒng)碰撞主要有兩種情況，讀寫器碰撞和應(yīng)答器碰撞，讀寫器碰撞是一個(gè)應(yīng)答器同時(shí)收到不同讀寫器發(fā)出的命令，應(yīng)答器碰撞是一個(gè)讀寫器同時(shí)給不同應(yīng)答器發(fā)送命令。在實(shí)際的應(yīng)用當(dāng)中，應(yīng)答器由于其低成本的優(yōu)越 ,從而得到大量的生產(chǎn)，而讀寫器往往是固定在系統(tǒng)的某處，來識(shí)別多個(gè)應(yīng)答器，所以碰撞的主要情況是應(yīng)答器碰撞，即一個(gè)讀寫器的工作范圍內(nèi)同時(shí)出現(xiàn)了 多個(gè)應(yīng)答器，并且對(duì)該讀寫器發(fā)出的命令同時(shí)予以響應(yīng)，從而導(dǎo)致讀寫器無法正確的識(shí)別出一個(gè)應(yīng)答器，稱該現(xiàn)象為發(fā)生了應(yīng)答器碰撞。解決碰撞的過程相應(yīng)的被稱為防碰撞，如前所述，該防碰撞過程主要從軟件的角度來予以解決，稱為防碰撞算法 【 8】 。 在上述前提下，基于應(yīng)答器的確定型二進(jìn)制樹防碰撞算法是目前最好的一種選擇，對(duì)其進(jìn)行研究，是最有實(shí)際應(yīng)用價(jià)值的，所以，本文將對(duì)其進(jìn)行理論分析與具體實(shí)現(xiàn)，在研究過程中，注重與新一代智能 RFID 系統(tǒng)的結(jié)合，應(yīng)用擁有強(qiáng)大功能的 FPGA(FieldProgrammable GateArray)做 為算法運(yùn)行的微處理器，這種思路將是未來 RFID 技術(shù)發(fā)展的重要方向， RFID 技術(shù)中的關(guān)鍵算法與先進(jìn)的電子技術(shù) FPGA 的結(jié)合，將為 RFID 技術(shù)的應(yīng)用拓開廣闊的前景。 1． 5 本文的主要工作 本文將在 RFID 技術(shù)的前提下，結(jié)合當(dāng)前數(shù)字電路設(shè)計(jì)的主流思路，重點(diǎn)研究 RFID 的關(guān)鍵技術(shù)防碰撞算法，并主要著眼于其中基于應(yīng)答器的確定性算法，即二進(jìn)制樹防碰撞算法，在理論分析的基礎(chǔ)上，對(duì)其進(jìn)行具體實(shí)現(xiàn)?；谏鲜隹紤]，論文將分四章來予以講述，文章結(jié)構(gòu)與內(nèi)容安排如下： 第 1 章：緒論。系統(tǒng)的介紹了 RFID 技術(shù)，描述了典型 RFID 系統(tǒng)的 結(jié)構(gòu)組成，提出了 RFID 系統(tǒng)的分類思想，講述了 RFID 系統(tǒng)的工作原理，以及其應(yīng)用范圍，重點(diǎn)強(qiáng)調(diào)了 RFID 技術(shù)的現(xiàn)狀和所面臨的主要問題，由此體現(xiàn)了研究 RFID 關(guān)鍵技術(shù)防碰撞算法的意義，明確了本文的主要研究?jī)?nèi)容。 第 2 章：現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法。概要性的描述了 RFID 防碰撞算法，對(duì)其進(jìn)行了分類，重點(diǎn)介紹其中的二進(jìn)制樹防碰撞算法，研究了三種最基本的二進(jìn)制樹算法，對(duì)其進(jìn)行了原理闡述，性能分析，以及實(shí)例演示。 第 3 章：改進(jìn)型二進(jìn)制樹防碰撞算法。二進(jìn)制樹防碰撞算法在多個(gè)國(guó)際標(biāo)準(zhǔn)中均有規(guī)定，基于 IS014443 標(biāo) 準(zhǔn)的 TYPEA 是其中的一個(gè)典型例子，本章首先介紹了涉及到二進(jìn)制樹防碰撞算法的幾個(gè)標(biāo)準(zhǔn)，其次詳細(xì)研究了 ISOl4443 標(biāo)準(zhǔn)對(duì)二進(jìn)制樹防碰撞算法的規(guī)定，最后提出了在此基礎(chǔ)上的改進(jìn)算法，這也是本章的重點(diǎn)。 第 4 章： FPGA 實(shí)現(xiàn)改進(jìn)型二進(jìn)制樹防碰撞算法。 FPGA 技術(shù)是目前數(shù)字電路設(shè)計(jì)的主流思路，利用 FPGA 做主處理器，是 RFID 技術(shù)發(fā)展的方向，本章探討了這一想法，介紹了 FPGA 技術(shù)的相關(guān)要點(diǎn)，并應(yīng)用 FPGA，實(shí)現(xiàn)了改進(jìn)型二進(jìn)制樹防碰撞算法。 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)答器共存的情況，毫無疑問，此時(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è)備，來識(shí)別多個(gè)應(yīng)答器，所以發(fā)生讀寫器碰撞的應(yīng)用場(chǎng)合是不多的，因此下文將 著重研究應(yīng)答器碰撞。 在上述前提下，有兩種類型的通信方式，一種是讀寫器發(fā)送的數(shù)據(jù)同時(shí)被多個(gè)應(yīng)答器接收，稱為“無線廣播”，另一種是多個(gè)應(yīng)答器的數(shù)據(jù)同時(shí)傳送給讀寫器，稱為“多路存取”，兩者都是無線電技術(shù)中長(zhǎng)期面臨的難題，同時(shí)也發(fā)展出一系列相應(yīng)的解決思路，一般來說分為四種，即空分多路 (SDMA)，碼分多路 (CDMA),頻分多路 (FDMA)，時(shí)分多路 (TDMA)，從 RFID 系統(tǒng)的通信形式、功耗、 系統(tǒng)復(fù)雜性以及成本多方面綜合考慮，時(shí)分多路法是最有實(shí)際應(yīng)用價(jià)值的，它也是目前RFID 防碰撞算法應(yīng)用中最廣泛的一類，時(shí)分多路 法的基本思想是把整個(gè)可供使用的通路容量按時(shí)間分配給多個(gè)用戶，從而達(dá)到在不同時(shí)隙將各個(gè)應(yīng)答器一 一識(shí)別出來的目的【 11】 。時(shí)分多路法按照能量的供給者可以分為兩大類，一類是應(yīng)答器驅(qū)動(dòng)型，另一類是讀寫器驅(qū)動(dòng)型，這也正是對(duì)應(yīng)了第一章中 RFID系統(tǒng)分類思路中的有源系統(tǒng)和無源系統(tǒng)，根據(jù)實(shí)際應(yīng)用情況，無源系統(tǒng)是應(yīng)用最廣泛的一類，所以下文重點(diǎn)研究讀寫器驅(qū)動(dòng)型的時(shí)分多路法。在該類讀寫器驅(qū)動(dòng)型時(shí)分多路法中，目前最常用的防碰撞算法有兩種，一類是基于時(shí)隙 ALOHA 的統(tǒng)計(jì)型算法，另一類是基于二進(jìn)制樹的確定型算法，統(tǒng)計(jì) 型算法的意義是在 一定的時(shí)隙范圍內(nèi)，系統(tǒng)有可能識(shí)別出所有應(yīng)答器 ，確定型算法的最大優(yōu)點(diǎn)是，在一定的時(shí)隙范圍內(nèi)，系統(tǒng)一定可以將所有的應(yīng)答器一一識(shí)別出來【 13】 。從應(yīng)用的角度來說，正確有效的識(shí)別是實(shí)際所需要的，因此下文將著重于二進(jìn)制樹防碰撞算法的研究。 2． 2 RFID 二進(jìn)制樹防碰撞算法概述 2． 2． 1 基本概念 在 RFID 防碰撞算法中，二進(jìn)制樹算法是目前應(yīng)用最廣泛的一種 ，之所以稱為“二進(jìn)制樹”，是因?yàn)樵谒惴▓?zhí)行過程中，讀寫器要多次發(fā)送命令給應(yīng)答器，每次命令都把應(yīng)答器分成兩組，多次分組后最終得到唯一的一個(gè)應(yīng)答器，在這個(gè)分組過程中，將 對(duì)應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲(chǔ)起來，就可以得到一個(gè)數(shù)據(jù)的分叉樹，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹”。 12 為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統(tǒng)當(dāng)中，每個(gè)應(yīng)答器都是獨(dú)一無二的，它們的獨(dú)立性通過唯一的自身序列號(hào)來體現(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】 。事實(shí)上，這些都 是對(duì)應(yīng)答器序列號(hào)的名稱描述，因?yàn)橄挛纳婕暗降姆琅鲎菜惴ㄊ瞧毡橐饬x上的，既包括了 EPC標(biāo)準(zhǔn)中的規(guī)定，也包括了 ISO 標(biāo)準(zhǔn)中的規(guī)定，因此在本文對(duì)普遍意義上的防碰撞算法的描述過程中，統(tǒng)一用序列號(hào) SN(SerialNumber)來描述上述概念，同時(shí)，序列號(hào)的長(zhǎng)度，格式，以及編碼方式也是各個(gè)標(biāo)準(zhǔn)各自差異的，為了說明的便利，統(tǒng)一定義為 8 位長(zhǎng)度的 二進(jìn)制碼。如圖 2． 1所示。 圖 2． 1 應(yīng)答器序列號(hào)數(shù)據(jù)格式 讀寫器與應(yīng)答器之間進(jìn)行數(shù)據(jù)交換時(shí)，往往要傳輸序列號(hào)的部分或者全部位，此時(shí)的傳輸順序定義為：先發(fā)送低位，再發(fā)送高位。 在讀寫器或者應(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． 2． 2 性能指標(biāo) 定義碰撞解決時(shí)期 CRI，即 Collision Resolution Interval【 16】 ，即解決一個(gè)讀寫器工作范圍內(nèi)碰撞所需要的時(shí)隙數(shù)，對(duì)二進(jìn)制樹算法的評(píng)價(jià)，一些常用的性能指 標(biāo)如下所示【 17】 ： 首先是算法執(zhí)行效率 ， 定義如下：在算法執(zhí)行過程，一 共 個(gè)時(shí)隙，識(shí)別了 n 個(gè)應(yīng)答器，則 =n/ 表示算法的執(zhí)行效率。 分析如下： n=l，顯而易見，在第一個(gè)時(shí)隙內(nèi)不發(fā)生碰撞，可以成功識(shí)別該應(yīng)答器， =1。 n≥ 2，由于應(yīng)答器序列號(hào)的唯一性，將有碰撞發(fā)生，在一個(gè)時(shí)隙內(nèi)發(fā)生碰撞的概率 p 是一個(gè)隨機(jī)事件，在 n 個(gè)應(yīng)答器信息包中 i個(gè)發(fā)生碰撞的概率為： 給出 i個(gè)碰撞，則 CRI的長(zhǎng)度為： 其中 1是 n個(gè)信息包最初的一個(gè)時(shí)隙， 是 i個(gè)碰撞的順利傳輸?shù)臅r(shí)隙， 13 是 ni個(gè)無碰撞傳輸?shù)臅r(shí)隙。 由上式可知， 是逐漸遞歸的，通過遞歸可得： 根據(jù)式 ()，上式可化為： 由此可見， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p的函數(shù)，一般情況下，可以參考二項(xiàng)分布，將 p取為 1／ 2。 算法的第二個(gè)重要的性能指標(biāo)是穩(wěn)定性，顯然，基于 TDMA 的二進(jìn)制樹防碰撞算法是沿著時(shí)間軸線來執(zhí)行協(xié)議的，有一系列的碰撞解決時(shí)期 CRI，定義一個(gè)隨機(jī)變量 ，表示第 k個(gè) CRI的長(zhǎng)度，這些 ???? 形成一個(gè)馬爾可夫鏈 (Markovchain)，因?yàn)榈?個(gè) CRI 的長(zhǎng)度由它開始的第一個(gè)時(shí)隙傳輸?shù)男畔?，也就是?k 個(gè) CRI 區(qū)間內(nèi)到達(dá)的信息包決定的，所以，如果馬爾可夫鏈滿足遍歷性分布，那么這個(gè)系統(tǒng) 就可以說是穩(wěn)定的。 馬爾可夫鏈遍歷性分布要滿足下列兩個(gè)條件 【 18】 ： 這里有： 也就是 n個(gè)信息包從發(fā)生碰撞開始傳輸?shù)?CRI區(qū)間長(zhǎng)度的數(shù)學(xué)期望， 是 在一個(gè)時(shí)隙內(nèi)到達(dá)這個(gè)系統(tǒng)信息包的期望值，該過程屬于泊松過程【 l9】 。一般來說， 在二進(jìn)制樹防碰撞算法中，系統(tǒng)都能夠滿足馬爾可夫鏈的兩個(gè)遍歷性分布條件，即作為一種確定型的算法，二進(jìn)制樹防碰撞算法是穩(wěn)定的。算法的第三個(gè)重要性能是系統(tǒng)通信復(fù)雜度，顯而易見，系統(tǒng)的通信雙方是讀寫器與應(yīng)答器，則通信復(fù)雜度也應(yīng)該從這兩方面著手考慮，即讀寫器與應(yīng)答器各自發(fā)送的數(shù)據(jù)位的位 數(shù)。該指標(biāo)的評(píng)價(jià)標(biāo)準(zhǔn)是基于能量消耗的角度的，即發(fā)送的數(shù)據(jù)信息量越少，則整個(gè)系統(tǒng)消耗的能量也越少，這顯然是一個(gè)理想的效果。 2． 2． 3 算法分類 在基本的二進(jìn)制樹搜索算法的基礎(chǔ)上，有多種形式的二進(jìn)制樹搜索算法，它 14 們之間主要的區(qū)別在于命令的數(shù)據(jù)形式，主要有兩點(diǎn)。 (1)命令參數(shù)是 1bit 數(shù)據(jù)，還是多 bit 數(shù)據(jù)。 (2)命令參數(shù)長(zhǎng)度是固定的，還是變化的。 圖 2． 2 是一個(gè)二進(jìn)制樹搜索算法的分類圖，在基本二進(jìn)制樹的基礎(chǔ)上，按照命令參數(shù)分為 1bit 和多 bit，根據(jù)傳輸?shù)拿顓?shù)的長(zhǎng)度分為定長(zhǎng)二進(jìn)制樹和動(dòng)態(tài)二進(jìn)制樹兩種，根 據(jù)二進(jìn)制樹遍歷時(shí)是一輪前進(jìn)到底的還是退避返回的分為前進(jìn)二進(jìn)制樹和退避二進(jìn)制樹兩種。需要說明的是，這只是一個(gè)大略的分類法，主要目的在于說明二進(jìn)制樹分類的基本原則。事實(shí)上，分類所得的這些算法中也有互相重合的，如動(dòng)態(tài)二進(jìn)制樹算法既可以采用前進(jìn)思路，也可以采用退避思路。另外，在具體應(yīng)用時(shí)，可能還存在多種不同的說法，如 lbit 長(zhǎng)二進(jìn)制樹中還有修正二進(jìn)制樹 MBBT，加強(qiáng)二進(jìn)制樹 EBBT 等區(qū)別【 20】 。 圖 2． 2二進(jìn)制樹算法分類 2． 3 基本二進(jìn)制樹防碰撞算法 2． 3． 1 算法思路 定義兩個(gè)具有普遍意義的命令來描述算法 ： (1)請(qǐng)求命令 Request(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若小于或者等于，則該應(yīng)答器回送其 SN 給讀寫器。注： Request(SN)初始值設(shè)為 Request(11111111)。 (2)休眠命令 Sleep(SN)：該命令攜帶一個(gè)參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN與接收到的 SN 比較，若等于，則該應(yīng)答器被選中，進(jìn)入休眠狀態(tài)，也即是不再響應(yīng) Request 命令，除非該應(yīng)答器通過先離開讀寫器工作范圍再進(jìn)入的方式重新上電，才可以再次響應(yīng) Request 命令 。 基本二進(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í)