( Radio Frequency Identification) 是利用無線信道實現雙向通信的一種識別技術, 可識別遠距離的貼有標簽的目標,，并讀寫相關數據。RFID系統可識別高速運動的物體并可同時識別多個目標，操作快捷方便。本文基于RFID系統，解決了同一時間識別多個目標的沖突問題。 

1 概述

　　RFID系統主要由射頻通信和計算機信息系統兩部分組成，其中，射頻通信部分主要包括讀寫器和標簽(射頻卡)。其間存在兩種通信形式：從讀寫器到電子標簽的數據傳輸，即讀寫器發送的數據流被其覆蓋范圍內的多個標簽所接收，這種通信形式也被稱為無線電廣播；在讀寫器的作用范圍內有多個標簽同時應答，這種形式被稱為多路存取。在后一種通信形式中，標簽數據的混疊問題被稱為碰撞問題。為了防止由于多個電子標簽的數據在讀寫器的接收機中相互碰撞而不能準確被讀出, 必須采用防碰撞算法[2]來加以克服。

1 .1 防碰撞算法

　　ISO 14443- 3[3]規定了TYPE A和TYPE B兩種防沖撞機制。二者防碰撞機制的原理不同, 前者是基于位碰撞檢測協議, 而TYPE B則通過系列命令序列完成防碰撞。ISO15693采用輪詢機制、分時查詢的方式完成防碰撞機制，這在標準的第三部分有詳細規定。基于此的現存防碰撞算法有ALOHA[4]算法、分隙 ALOHA算法和二進制樹形搜索算法等，前兩者的信道最佳利用率分別為18.4%和36.8%，但隨著標簽數量的增大，性能將急劇惡化。二進制樹形搜索算法在一次性讀取標簽的數目和速度上有了極大的提高。

1 .2 二進制樹形搜索防碰撞算法原理

　　二進制樹形搜索防碰撞算法[5]適用于TYPE A。A型標簽采用Manchester編碼方式，這使得準確地判斷出碰撞位成為可能。圖1所示為利用Manchester編碼識別碰撞位。

　　當讀寫器接收到發送的標簽信號時，首先判斷是否發生碰撞以及發生碰撞的具體位置，然后根據碰撞的具體位置確定下一次發送的請求命令中的參數，再次發送，直到確定其中的一張標簽為止。為了便于說明，假定標簽的數據為 8bit，并定義命令call ( epc ，m)，其含義為：讀寫器向其覆蓋范圍內的標簽發送召喚指令, 如果標簽數據[7]與call命令中epc參數的前m位相等，則滿足這個條件的標簽做出應答。設在某時刻有四個標簽同時進入讀寫器的作用范圍內，它們的EPC碼分別為tag1 =10100011, tag2=10011011, tag3=00010001, tag4=11101100。其算法流程示意圖如圖2所示。

　　從圖2可以看出，call命令的epc參數由碰撞位判斷得出, 而call命令中的m參數又由相應的epc參數求得，這樣就使得算法在執行過程中跳過了空閑的節點,提高了算法的執行效率。又因為算法可以形象地用二進制樹來描述, 故稱為 “二進制樹形防碰撞算法”。

2 碰撞算法的 FPGA 仿真實現

　　目前使用的防碰撞算法大多通過軟件方式實現，容易造成應用軟件非常復雜而且多張卡片應用時速度慢。因此, 對其采用軟硬件結合的方式，用 FPGA[6]實現防碰撞算法，可達到速度快、成本低的要求。

2 .1 總體設計方案

　　EPC標簽模塊可以抽象為一個 Manchester 編碼器模塊，RFID 讀寫器內部包含三個基本的功能模塊:：Manch-ester 解碼器模塊、LIFO 模塊和控制整個算法的狀態機模塊。其基本模塊連接關系如圖 3 所示。

　　具體工作流程如下：

　　(1) RFID 讀寫器內部的狀態機每隔一段時間發送一次 call 命令；　

　　(2) 讀寫器覆蓋范圍內的標簽收到 call 命令后判斷是否滿足 call 命令的條件, 若滿足則發送 epc 碼給讀寫器, 否則不作反應；　　

　　(3) 讀寫器收到標簽發來的數據進行Manchester 解碼。如果無碰撞發生則存儲數據后強制該標簽進入睡眠狀態; 如果產生碰撞, 則根據解出的數據和碰撞位標志進行下一次call命令。如此循環執行直到讀寫器范圍內的所有標簽都被識別出來。

　　本文采用Verilog HDL 語言作為設計輸入，仿真工具采用 Quartus II 5.1 build 216 03/06/2006 SJ Full Version;FPGA 器件為 EP2C5T144C6。

2 .2 RFID 讀寫器各模塊設計及仿真

2 .2 .1 Manches ter 編碼器　　

　　Manchester 編碼器即為 RFID 標簽, 它的主要數據輸入包括該標簽的數據、call或 sleep命令標志以及相應的epc參數和m參數。當接收到RFID讀寫器也就是算法控制狀態機的控制信號后做出相應的判斷，如果滿足call命令的條件則開始對標簽數據進行 Manchester 編碼, 編碼完成后將編碼后的數據發送給Manchester 解碼器, Manchester 解碼器接收到數據后開始進行解碼工作。如果滿足sleep命令的條件，標簽則進入睡眠狀態，對以后的call命令不作應答。

2 .2 .2 Manches ter 解碼器

　　Manchester 解碼及碰撞位判斷是整個跳躍式二進制樹形防碰撞算法的關鍵。解碼和碰 撞位的判斷均由Manchester 解碼器模塊完成。首先, Manchester 解碼器模塊中定義了一個兩位的移位寄存器, 用來檢測標簽發送的Manchester 碼的同步頭,以便斷出編碼的到來。一旦移位寄存器檢測到標簽發送過來的信號的同步頭, Manchester 解碼器便開始解碼工作。采樣信號的產生可以利用循環計數的計數器來實現。該計數器在高頻時鐘的邊沿到來時自動加 1, 其循環周期與 Manchester 編碼時鐘周期相等。為防止延遲干擾, 在計數器循環周期的 1/4、3/4 處令采樣信號為高電平。 當解碼完成后解碼器將向控制狀態機發送一個data_ready 脈沖信號, 表明已經解碼完畢, 可以向狀態機傳送數據。

　　圖 4 為接收到的數據在[7]、 [5]、 [1]位存在碰撞現象時解碼器的時序仿真結果。圖中圓圈圈出部分為解碼后的碰撞位，由圖可以看出標識碰撞位的flag_out的輸出數據為 10100010，可知，接收到的數據的[7]、[5]、[1]位發生了碰撞。

2 .2 .3 存儲節點的 LIFO 棧

　　LIFO（Last In First Out）棧用來存儲算法執行過程中所經過的節點的信息。為了協調 LIFO內部的工作狀態, 在LIFO棧的模塊中定義了一個小型的狀態機。其工作狀態及轉換條件流程圖如圖 5所示。

　　對LIFO棧穿插寫入和讀取數據, 以驗證LIFO模塊功能。第一次寫入兩個數據 10100011、11100010, 進行一次讀取操 作；然后連續寫入兩個數據10101010、01011011，再連續進行四次讀取操作。其仿真結果如圖 6所示。

　　由圖6可看出，第一次寫入兩數據后，LIFO棧的棧內數據為10100011、11100010, 棧頂數據為11100010,，進行一次讀操作，棧頂數據變為10100011；第二次連續寫入兩數據 10101010、01011011后，棧頂數據變為01011011,連續進行三次讀取操作后，根據empty標志信號可以看出此時LIFO已經為空,，所以在第四次讀取時并沒有讀出數據。

2 .3 綜合仿真

　　將Manchester編碼模塊、Manchester解碼模塊、LIF模塊和算法控制狀態機模塊連接起來進行算法的綜合仿真。測試中設定讀寫器作用范圍內共有四個RFID標簽，標簽的 EPC碼為8位二進制碼。四個標簽的數據信息分別為：tag1=10100011，tag2=10011011，tag3=00010001，tag4=11101100。其仿真結果如圖7所示。

3 仿真結果分析

3 .1 一次性最大讀取標簽數　　

　　通過LIFO棧的仿真和分析可得到如下結論: 如果LIFO的大小為N個單元, 則算法一次最多可以處理的標簽數目即為 N+1。這表明系統防碰撞算法一次性最大讀取標簽數由 LIFO 棧的設計大小決定。不同的FPGA器件可用的存儲器空間大小不同，使得基于其上設計的算法的該項性能指標也不同目前的FPGA器件大都內置了較大的存儲器，例如Altera公司的低成本Cyclone II系列產品，最大提供1．1Mbit 的存儲容量。可以估算，存儲器的 1/4 用于存儲節點信息的參數, 1/4 用于存儲節點信息的碰撞位標志, 1/4 用來存儲解出的標簽數據, 1/4作為系統保留。由于標簽數據信息長度為 64bit，用CycloneII系列FPGA器件實現算法，設一次性可讀取標簽的最大數目為Nmax，可以計算出：Nmax≈ 1.1× 1064×64=4296。 

3 .2 算法識別速度 

　　ISO 14443定義了 TYPE A、TYPE B兩種類型協議，其通信速率均為106kbps。以此標準來計算算法的識別速度。算法執行過程中以 all命令和sleep 命令為單元,，每次命令的執行都要發送64bit的參數，8bit的m參數, 接收標簽返回的 64bit 數據，共傳送136bit的數據。另外call 命令中讀寫器與標簽對數據的處理也要占用一定的時間。可以等價為傳送小于 8bit 的數據。這樣每次命令的執行共有 144bit 的數據傳送。所以,每秒鐘可執行call命令次數n為：n≈ 106× 1024144=753。由算法可知, 當區域內存在的標簽數為 L 時, 則全部被識別出所執行的 call 命令的次數約為 2L。

1