射頻識別(RFID)技術防碰撞算法研究與應用探討

摘 要：隨著射頻識別（RFID）技術的不斷發展，RFID技術已在諸多領域得以應用。本文首先針對RFID技術中多標簽與閱讀器通信時的防碰撞問題進行了介紹，然后以幾種常用的防碰撞算法為例，對其研究與應用進行了探討。

關鍵詞：RFID技術 標簽 閱讀器 防碰撞算法

中圖分類號：TN99文獻標識碼：文章編號：1674-098X(2011)12(c)-0000-00

隨著RFID射頻識別技術的不斷發展，該項技術得到了人們越來越多的關注。人們通過對該項技術的不斷深入研究，將其廣泛地應用于各個領域的多個環節，如物流與供應管理、城市一卡通、動物身份識別、生產制造與裝配、航空行李處理等。

RFID技術的基本工作原理為：當標簽進入閱讀器的閱讀范圍后，會接收到閱讀器發出的一定頻率的射頻信號，而標簽憑借感應電流所獲得的能量被激活后，將儲存在芯片內部的產品信息通過內置天線發送出去。閱讀器通過接收天線將標簽發送的信息接收后對其進行解調和解碼，然后將其送至中央信息系統進行相關數據的處理。然而在實際的RFID應用系統中經常會存在一種情況，就是多個電子標簽同時處于一個閱讀器的閱讀范圍內，如圖1所示。在這種情況下，當多個標簽在獲取能量被激活后，就會在同一時間內向閱讀器發送數據信號，而閱讀器在讀取多個標簽發送的數據時就會出現沖突即數據碰撞，這將導致閱讀器無法正常讀出數據，從而降低了RFID應用系統的可靠性。

針對以上數據碰撞的問題，人們提出了解決數據碰撞問題的四類方法：空分多路法（SDMA）、頻分多路法（FDMA）、時分多路法（TDMA）和碼分多路法（CDMA）。在這四種方法中，時分多路法（TDMA）應用較為廣泛，源于該方法更加符合實際RFID應用系統的要求：較高的數據傳輸速度、較低的運行成本及較高的可靠性。在實際應用中基于TDMA的防碰撞算法主要分為基于ALOHA機制的算法和基于二進制搜索的算法。

1 防碰撞算法

1.1 ALOHA算法

ALOHA算法應用較為簡便，被廣泛地應用在只讀電子標簽系統中來解決數據碰撞問題。該算法是基于概率統計的一種方法，隨機性比較大，并且只在只讀電子標簽中適用。在實際的RFID系統中，只讀電子標簽在通常情況下需要向閱讀器傳送的只是一些序列號，而且傳送序列號的過程是在一個周期性的循環中完成的。相對于一個循環周期，只讀電子標簽傳送數據的時間只占了一小部分，從而使得數據傳輸之間的間隔相當長。此外，由于不同電子標簽重復傳輸數據的時間稍有不同，所以兩個電子標簽在不同的時間段上傳輸各自的數據包并且發生相互碰撞，這種情況存在一定的可能性。ALOHA算法利用概率的方法，在數據傳輸過程中解決數據碰撞問題，其數據交換過程如圖2所示。

通過了解ALOHA算法的基本原理，不難看出基于該防碰撞算法的RFID系統相對簡單，并且易于實現，但其由于其隨機性較大，從而數據產生碰撞的概率也就比較高，在一定程度上降低了RFID系統的利用率，而且閱讀器有可能產生錯誤判斷。鑒于此，結合RFID系統應用的不同范圍及要求，人們在ALHOA算法基礎上提出了許多改進的方法，如時隙ALHOA法（SA算法）、幀時隙ALHOA算法（FSA算法）、動態幀時隙ALHOA算法（DFSA算法）等，這些改進的算法在應用過程中大大提高了數據的處理速度及數據量，并且有效降低了數據傳輸過程中的碰撞率。

1.2 二進制搜索算法

二進制搜索算法的實現需要一個前提，即數據碰撞的精確位位置必須能夠在閱讀器中得以確認。此外，該算法的實現還需要有合適的位編碼，通過數據碰撞狀況的比較，Manchester編碼相比于NRZ編碼更適合二進制搜索算法，因此，二進制搜索算法的位編碼是選用Manchester編碼來實現的。就二進制搜索算法自身而言，它是由一個閱讀器與多個電子標簽之間相互作用（命令和回應）的預定義序列（規范）構成的，其目的是能夠從較大一組電子標簽中選擇任意需要的一組標簽。如果將該算法在實際應用中實現，需要具備兩個條件，一是每個電子標簽有各自唯一的序列號，二是一組標簽能夠處理的命令。在實際的應用中，標簽的序列號可以通過編碼實現唯一性，而標簽可以處理的命令是使用以下一組命令：

（1）REQUEST (SNR）：此命令發送給電子標簽一個序列號作為參數。如果該標簽自身的序列號小于或等于接收到的序列號，那么該標簽將其自身的序列號發送回閱讀器，這樣可以起到縮小預選標簽范圍的作用。

（2）SEL ECT＿(SNR)：發送給電子標簽一個（預定義的）序列號（SNR）作為參數。如果標簽自身的序列號與發送的序列號相同，則該標簽具有執行其他命令（例如讀出和寫入數據）的權限，即該標簽即被選中。而那些自身的序列號與發送的序列號不相同的標簽此后只能對REQUEST命令應答。

（3）READ＿DA TA：被選中的標簽將存儲的數據發送給閱讀器。（在實際的系統中，還有鑒別或寫入、借記、貸記等命令）。

（4）UNSEL ECT：事先選中的標簽被取消，并且該標簽處于“無聲”狀態，在這種狀態下該標簽是完全無回應的，對接收到的REQUEST 命令不作任何回應。要想重新激活該標簽，必須將其暫時移出閱讀器的作用范圍（等于沒有供應電壓）以進行復位。

通過實際應用，二進制搜索算法具有較高的識別率，并且出現錯誤判斷的幾率較小，比較適用于應用標簽數量較多的場合，但該算法處理的數據量較大，從而導致系統所耗時間較長、所耗功率較大，而且通信過程較為復雜。為此，人們通過深入研究在此基礎上提出了改進的二進制搜索算法，如后退式二進制搜索算法、動態二進制搜索算法、修剪枝二進制搜索算法等，這些算法在一定程度上提高了數據處理速度，有效縮短了系統所耗時間及功率，并提高了系統判斷的準確率及系統的吞吐率。

2 防碰撞算法研究與應用探討

目前，應用較為廣泛的防碰撞算法主要有ALOHA算法和二進制搜索算法以及在這兩類算法基礎上的改進算法。這兩大類算法根據各自不同的特點，它們在系統中的應用也有所不同：

（1）純的ALOHA 算法較為簡單，其隨機性大，碰撞率較高，一般應用在較為簡單的只讀電子標簽系統中，整個系統的利用率相對較低，而且可能存在錯誤判決的問題；時隙ALOHA算法因為有閱讀器的控制，電子標簽只在規定的同步時隙內才傳輸數據，這樣使得可能發生碰撞的時間較純的ALOHA算法就縮短了一半，而吞吐率較純的ALOHA算法增加了一倍，但該算法的應用仍局限在只讀電子標簽系統中；幀時隙ALOHA算法適用于數據信息量傳輸較大的系統，但數據信息量不是無止境的大，當系統標簽數量遠遠大于時隙個數時，系統讀取標簽的時間將會大大增加，而在標簽數遠遠小于時隙個數時，就會造成時隙的浪費；動態時隙幀算法通過讀寫器查詢發生碰撞的次數解決了幀時隙算法中的時隙浪費問題，如果讀寫器查詢到標簽碰撞次數較多，那么就提供更多的時隙，直到有唯一標簽的時隙為止，從而大大提高了系統的吞吐率。

（2）二進制搜索算法屬于確定性算法，該算法的穩定性較高，而且具有較高的識別率，然而該算法處理的數據量較大，識別時間較長，當序列號過長時不適用，而且該算法對于標簽信息的安全性存在一定的隱患；后退式二進制搜索算法系統的識別時間與所需識別的標簽數量成線性關系，此算法能在大批量物品的識別、追蹤、管理中得以有效應用，但標簽序列號過長時仍然不適用；動態二進制搜索算法隨機性小，準確率較高，而且系統的吞吐率較大，具有較好的穩定性，而且所用同步時隙小；修剪枝二進制搜索算法雖然程序較為復雜，但其所需時間較短，因而比較適用于標簽數量較多且標簽序列號長的系統。

3結語

本文對基于ALOHA的算法和基于二進制搜索的算法這兩大類基本的算法進行了介紹，并通過結合兩大類算法的諸多改進算法的特點對防碰撞問題的研究和應用進行了初步探討，希望能為各類算法的選用提供一定的參考。同時，防碰撞問題逐步成為一個探討的熱點同時也是一個研究的難點，隨著RFID技術在諸多領域的廣泛應用，防碰撞算法將會有更為深入的研究和更高層次的發展。

參考文獻

[1] 聶賽如，劉有源.RFID防碰撞算法研究現狀與發展趨勢綜述[J.物流技術.2008，27(3).

[2] KLAUS FINKENZELLER.RFID HANDBOOK Second Edition [M].Translated by Rachel Waddington.

[3](美)菲特(Fette)等，著.射頻和無線技術[M].李根生，匡泓，文志成譯.北京:電子工業出版社，2009.11

[4].陳博.一種類二進制搜索的RFID系統反碰撞算法及其實現[J].電子器件.2006，3，(1)29.

[5].崔沂峰，陳平，張景元.RFID電子標簽防碰撞算法的研究[J].《微計算機信息》（嵌入式與SOC），2007，23(8-2).