【文章內(nèi)容簡介】 術(shù)的前提下，結(jié)合當(dāng)前數(shù)字電路設(shè)計(jì)的主流思路，重點(diǎn)研究 RFID 的關(guān)鍵技術(shù)防碰撞算法，并主要著眼于其中基于應(yīng)答器的確定性算法，即二進(jìn)制樹防碰撞算法，在理論分析的基礎(chǔ)上，對其進(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ù)防碰撞算法的意義，明確了本文的主要研究內(nèi)容。第 2 章：現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法。概要性的描述了 RFID 防碰撞算法，對其進(jìn)行了分類，重點(diǎn)介紹其中的二進(jìn)制樹防碰撞算法，研究了三種最基本的二進(jìn)制樹算法，對其進(jìn)行了原理闡述，性能分析，以及實(shí)例演示。第 3 章：改進(jìn)型二進(jìn)制樹防碰撞算法。二進(jìn)制樹防碰撞算法在多個國際標(biāo)準(zhǔn)中均有規(guī)定，基于 IS014443 標(biāo)準(zhǔn)的 TYPEA 是其中的一個典型例子，本章首先介紹了涉及到二進(jìn)制樹防碰撞算法的幾個標(biāo)準(zhǔn)，其次詳細(xì)研究了 ISOl4443 標(biāo)準(zhǔn)對二進(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)制樹防碰撞算法。2 現(xiàn)有 RFID 二進(jìn)制樹防碰撞算法2．1 RFID 防碰撞算法概述RFID 系統(tǒng)的數(shù)據(jù)通信雙方是讀寫器和應(yīng)答器，在實(shí)際的 RFID 系統(tǒng)工作時，可能會出現(xiàn)同時多個讀寫器和多個應(yīng)答器共存的情況，毫無疑問，此時系統(tǒng)的數(shù)據(jù)交換就會出現(xiàn)信道與時序上的重疊，也就是發(fā)生了碰撞，在多個讀寫器與多個應(yīng)答器的射頻識別系統(tǒng)中，存在著兩種形式的沖突方式，一種是同一應(yīng)答器同時收到不同讀寫器發(fā)出的命令，另一種是同一個讀寫器同時收到多個不同應(yīng)答器返回的數(shù)據(jù)，前者我們稱為讀寫器碰撞，后者稱為應(yīng)答器碰撞【9】 ，在實(shí)際應(yīng)用當(dāng)中，一般是讀寫器做為主設(shè)備，來識別多個應(yīng)答器，所以發(fā)生讀寫器碰撞的應(yīng)用場合是不多的，因此下文將著重研究應(yīng)答器碰撞。在上述前提下，有兩種類型的通信方式，一種是讀寫器發(fā)送的數(shù)據(jù)同時被多個應(yīng)答器接收，稱為“無線廣播” ，另一種是多個應(yīng)答器的數(shù)據(jù)同時傳送給讀寫器，稱為“多路存取” ，兩者都是無線電技術(shù)中長期面臨的難題，同時也發(fā)展出一系列相應(yīng)的解決思路，一般來說分為四種，即空分多路(SDMA)，碼分多路(CDMA),頻分多路(FDMA)，時分多路(TDMA)，從 RFID 系統(tǒng)的通信形式、功耗、系統(tǒng)復(fù)雜性以及成本多方面綜合考慮，時分多路法是最有實(shí)際應(yīng)用價值的，它也是目前 RFID 防碰撞算法應(yīng)用中最廣泛的一類，時分多路法的基本思想是把整個可供使用的通路容量按時間分配給多個用戶，從而達(dá)到在不同時隙將各個應(yīng)答器一一識別出來的目的【11】 。時分多路法按照能量的供給者可以分為兩大類，一類是應(yīng)答器驅(qū)動型，另一類是讀寫器驅(qū)動型，這也正是對應(yīng)了第一章中 RFID系統(tǒng)分類思路中的有源系統(tǒng)和無源系統(tǒng)，根據(jù)實(shí)際應(yīng)用情況，無源系統(tǒng)是應(yīng)用最廣泛的一類，所以下文重點(diǎn)研究讀寫器驅(qū)動型的時分多路法。在該類讀寫器驅(qū)動型時分多路法中，目前最常用的防碰撞算法有兩種，一類是基于時隙ALOHA 的統(tǒng)計(jì)型算法，另一類是基于二進(jìn)制樹的確定型算法，統(tǒng)計(jì)型算法的意義是在一定的時隙范圍內(nèi)，系統(tǒng)有可能識別出所有應(yīng)答器，確定型算法的最大優(yōu)點(diǎn)是，在一定的時隙范圍內(nèi)，系統(tǒng)一定可以將所有的應(yīng)答器一一識別出來【13】 。從應(yīng)用的角度來說，正確有效的識別是實(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)答器分成兩組，多次分組后最終得到唯一的一個應(yīng)答器，在這個分組過程中，將對應(yīng)的命令參數(shù)以節(jié)點(diǎn)的形式存儲起來，就可以得到一個數(shù)據(jù)的分叉樹，而所有的這些數(shù)據(jù)節(jié)點(diǎn)又是以二進(jìn)制的形式出現(xiàn)的，所以稱為“二進(jìn)制樹” 。為了便于描述算法，聲明一些基本概念如下：首先，在 RFID 系統(tǒng)當(dāng)中，每個應(yīng)答器都是獨(dú)一無二的，它們的獨(dú)立性通過唯一的自身序列號來體現(xiàn)，該序列號在不同的標(biāo)準(zhǔn)中有不同的名稱，如 EPC 標(biāo)準(zhǔn)中稱其為電子產(chǎn)品代碼 EPC，即英文 ElectronicProduct Code 的縮寫，IS014443 標(biāo)準(zhǔn)中稱其為唯一標(biāo)識碼 UID，即英文 Unique Identmer 的縮寫【15】 。事實(shí)上，這些都是對應(yīng)答器序列號的名稱描述，因?yàn)橄挛纳婕暗降姆琅鲎菜惴ㄊ瞧毡橐饬x上的，既包括了 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)制碼。如圖 2．1 所示。圖 2．1 應(yīng)答器序列號數(shù)據(jù)格式讀寫器與應(yīng)答器之間進(jìn)行數(shù)據(jù)交換時，往往要傳輸序列號的部分或者全部位，此時的傳輸順序定義為：先發(fā)送低位，再發(fā)送高位。在讀寫器或者應(yīng)答器內(nèi)部，對數(shù)據(jù)進(jìn)行比較時，遵循這樣的原則，即按位依次比較，先比較低位，再比較高位，約定 01，根據(jù)這個比較順序，在判斷大小時，低位數(shù)據(jù)優(yōu)先，即兩數(shù) A，B 相比較，從低位開始的第一個不相等位的大小決定了兩數(shù)的大小，只有當(dāng)兩個數(shù)的全部位均相等時，兩數(shù)才相等。2．2．2 性能指標(biāo)定義碰撞解決時期 CRI，即 Collision Resolution Interval【16】 ，即解決一個讀寫器工作范圍內(nèi)碰撞所需要的時隙數(shù)，對二進(jìn)制樹算法的評價，一些常用的性能指標(biāo)如下所示【17】：首先是算法執(zhí)行效率 ，定義如下：在算法執(zhí)行過程，一共 個時隙，識別了 n 個應(yīng)答器，則 =n/ 表示算法的執(zhí)行效率。分析如下：n=l，顯而易見，在第一個時隙內(nèi)不發(fā)生碰撞，可以成功識別該應(yīng)答器， =1。n≥2，由于應(yīng)答器序列號的唯一性，將有碰撞發(fā)生，在一個時隙內(nèi)發(fā)生碰撞的概率 p 是一個隨機(jī)事件，在 n 個應(yīng)答器信息包中 i 個發(fā)生碰撞的概率為：給出 i 個碰撞，則 CRI 的長度為：其中 1 是 n 個信息包最初的一個時隙， 是 i 個碰撞的順利傳輸?shù)臅r隙，是 ni 個無碰撞傳輸?shù)臅r隙。由上式可知， 是逐漸遞歸的，通過遞歸可得：根據(jù)式()，上式可化為：由此可見， 是關(guān)于 p 的函數(shù)，則 =n/ 也是關(guān)于 p 的函數(shù)，一般情況下，可以參考二項(xiàng)分布，將 p 取為 1／2。算法的第二個重要的性能指標(biāo)是穩(wěn)定性，顯然，基于 TDMA 的二進(jìn)制樹防碰撞算法是沿著時間軸線來執(zhí)行協(xié)議的，有一系列的碰撞解決時期 CRI，定義一個隨機(jī)變量 ，表示第 k 個 CRI 的長度，這些 …………形成一個馬爾可夫鏈(Markovchain)，因?yàn)榈?個 CRI 的長度由它開始的第一個時隙傳輸?shù)男畔?，也就是?k 個 CRI 區(qū)間內(nèi)到達(dá)的信息包決定的，所以，如果馬爾可夫鏈滿足遍歷性分布，那么這個系統(tǒng)就可以說是穩(wěn)定的。馬爾可夫鏈遍歷性分布要滿足下列兩個條件【18】：這里有：也就是 n 個信息包從發(fā)生碰撞開始傳輸?shù)?CRI 區(qū)間長度的數(shù)學(xué)期望，是在一個時隙內(nèi)到達(dá)這個系統(tǒng)信息包的期望值，該過程屬于泊松過程【l9】 。一般來說，在二進(jìn)制樹防碰撞算法中，系統(tǒng)都能夠滿足馬爾可夫鏈的兩個遍歷性分布條件，即作為一種確定型的算法，二進(jìn)制樹防碰撞算法是穩(wěn)定的。算法的第三個重要性能是系統(tǒng)通信復(fù)雜度，顯而易見，系統(tǒng)的通信雙方是讀寫器與應(yīng)答器，則通信復(fù)雜度也應(yīng)該從這兩方面著手考慮，即讀寫器與應(yīng)答器各自發(fā)送的數(shù)據(jù)位的位數(shù)。該指標(biāo)的評價標(biāo)準(zhǔn)是基于能量消耗的角度的，即發(fā)送的數(shù)據(jù)信息量越少，則整個系統(tǒng)消耗的能量也越少，這顯然是一個理想的效果。2．2．3 算法分類在基本的二進(jìn)制樹搜索算法的基礎(chǔ)上，有多種形式的二進(jìn)制樹搜索算法，它們之間主要的區(qū)別在于命令的數(shù)據(jù)形式，主要有兩點(diǎn)。(1)命令參數(shù)是 1bit 數(shù)據(jù)，還是多 bit 數(shù)據(jù)。(2)命令參數(shù)長度是固定的，還是變化的。圖 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)制樹兩種。需要說明的是，這只是一個大略的分類法，主要目的在于說明二進(jìn)制樹分類的基本原則。事實(shí)上，分類所得的這些算法中也有互相重合的，如動態(tài)二進(jìn)制樹算法既可以采用前進(jìn)思路，也可以采用退避思路。另外，在具體應(yīng)用時，可能還存在多種不同的說法，如 lbit 長二進(jìn)制樹中還有修正二進(jìn)制樹 MBBT，加強(qiáng)二進(jìn)制樹 EBBT 等區(qū)別【20】 。圖 2．2 二進(jìn)制樹算法分類2．3 基本二進(jìn)制樹防碰撞算法2．3．1 算法思路定義兩個具有普遍意義的命令來描述算法：(1)請求命令 Request(SN)：該命令攜帶一個參數(shù) SN，應(yīng)答器接收到該命令，將自身的 SN 與接收到的 SN 比較，若小于或者等于，則該應(yīng)答器回送其 SN 給讀寫器。注：Request(SN)初始值設(shè)為 Request(11111111)。(2)休眠命令 Sleep(SN)：該命令攜帶一個參數(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 所示：圖 2．3 基本二進(jìn)制樹算法流程基本二進(jìn)制樹算法的步驟如下：(1) 應(yīng)答器進(jìn)入讀寫器工作范圍，讀寫器發(fā)出一個最大序列號，所有應(yīng)答器的序列號均小于該最大序列號，所以在同一時刻將自身序列號返回給讀寫器。 (2) 由于應(yīng)答器序列號的唯一性，當(dāng)應(yīng)答器數(shù)目不小于兩個時，必然發(fā)生碰撞．發(fā)生碰撞時，將最大序列號中對應(yīng)的碰撞起始位設(shè)置為 O，低于該位者不變，高于該位者設(shè)置為 l。(3) 讀寫器將處理后的序列號發(fā)送給應(yīng)答器，應(yīng)答器序列號與該值比較，小于或等于該值者，將自身序列號返回給讀寫器。(4) 循環(huán)這個過程，就可以選出一個最小序列號的應(yīng)答器，與該應(yīng)答器進(jìn)行正常通信后，發(fā)出命令使該應(yīng)答器進(jìn)入休眠狀態(tài)，即除非重新上電，否則不再響應(yīng)讀寫器請求命令。也就是說，下一次讀寫器再發(fā)最大序列號時，該應(yīng)答器不再響應(yīng)。(5)重復(fù)上述過程，即可按序列號從小到大依次識別出各個應(yīng)答器。注：第五步時，從步驟 1 開始重復(fù)，也就是說，讀寫器識別完一個應(yīng)答器后，將重新發(fā)送原始的最大序列號。2．3．2 實(shí)例演示根據(jù)上述分析，下面給出一個基本二進(jìn)制樹搜索算法的實(shí)例演示，如圖2．4所示。假設(shè) RFID 系統(tǒng)中有一個讀寫器 R，四個應(yīng)答器 Tl(10100101)，T2(10l01101)，T3(11010101)，T4(11101101)，在某一時刻，四個應(yīng)答器同時進(jìn)入讀寫器的工作范圍之內(nèi)，讀寫器發(fā)出命令，四個應(yīng)答器同時響應(yīng)，由于其序列號 SN 的唯一性，將發(fā)生應(yīng)答器碰撞，從而啟動防碰撞循環(huán)，分析如下：圖 基本二進(jìn)制樹算法實(shí)例注：圖中共有四輪循環(huán)，依次識別出四個應(yīng)答器，分別以不同格式的線條表示，并加有循環(huán)輪次的數(shù)字標(biāo)識。(1)啟動第一輪循環(huán)，讀寫器發(fā)送 Request(1lll1111)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(1l1l1111)比較，均小于該值，于是所有應(yīng)答器均返回自身序列號給讀寫器，因?yàn)樾蛄刑柕奈ㄒ恍?，?yīng)答器返回的序列號在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回?cái)?shù)據(jù)為 lXXXXl0l，其中 X 表示該位發(fā)生了碰撞，讀寫器做如下處理：將碰撞起始位 D4 位置 0，低于該位者不變，高于該位者置 l，得到 11ll0l01，作為下一次 Request 命令攜帶的參數(shù)值，即Request(11110l01)。(2)讀寫器發(fā)送 Request(11110101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(11110l01)比較，其中 T1(10l00101)，T3(1l010101)的序列號小于該值，則 Tl，T3 返回自身序列號給讀寫器，在讀寫器接收端發(fā)生碰撞，讀寫器檢測到返回?cái)?shù)據(jù)為 1XXX0l01，讀寫器做如下處理：將碰撞起始位 D5 位置 0，低于該位者不變，高于該位者置 l，得到 11l00l01，作為下一次 Request 命令攜帶的參數(shù)值，即 Request(11100101)。(3)讀寫器發(fā)送 Request(11100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(111 00l01)比較，其中 Tl(10100l01)的序列號小于該值，則 Tl返回自身序列號給讀寫器，在讀寫器接收端不發(fā)生碰撞，讀寫器檢測到返回?cái)?shù)據(jù)為 10100101，讀寫器做如下處理：將該數(shù)值作為下一次 Sleep 命令攜帶的參數(shù)值，即 Sleep(10100101)。(4)讀寫器發(fā)送 Sleep(10100101)命令，所有應(yīng)答器響應(yīng)該命令，將自身序列號與該 SN(10l00111)比較，其中 T1(10l00101)的序列號等于該值，則 T1 執(zhí)行該命令，進(jìn)入休眠狀態(tài)