基于TDMA的RFID多標簽識別防碰撞算法研究

賀曉霞 秦松 賈小林

摘 要：射頻識別技術是一種非接觸式自動識別技術，是物聯網（IoT）的核心技術之一。RFID技術可通過射頻信號快速、準確地自動識別目標對象并獲取相關數據，識別工作無需人工干預。然而影響RFID系統識別效率的重要因素之一就是標簽碰撞問題，所以高效的防碰撞算法對于RFID系統而言非常重要。現有的RFID防碰撞算法大都基于時分多址（TDMA）算法，可劃分為Aloha類算法、樹搜索類算法和混合算法。文中主要對Aloha類算法、樹搜索算法、混合算法以及主要的改進算法進行分析研究，并對未來研究方向提出一些見解。

關鍵詞：RFID；防碰撞算法；Aloha算法；樹搜索算法；混合算法

中圖分類號：TP39；TN911 文獻標識碼：A 文章編號：2095-1302（2018）07-00-04

0 引 言

射頻識別技術（Radio Frequency Identification，RFID）是一種非接觸式自動識別技術，隨著物聯網的快速發展，RFID技術也受到越來越多的關注。一般RFID系統由閱讀器設備、電子標簽以及計算機數據管理系統組成，通過DSRC短程通信技術進行數據傳輸和交換。標簽具有唯一的ID號，目前該項技術已經廣泛應用于金融支付、身份識別、交通管理及物流跟蹤等方面，但是RFID系統中多標簽碰撞問題一直是制約其發展的主要因素。

在RFID系統中，如果在閱讀器讀寫范圍內存在多張電子標簽，當閱讀器發出查詢命令后，多張標簽同時做出應答就會產生多標簽碰撞問題，使得標簽的數據混疊，如圖1所示。在RFID閱讀器的讀寫范圍內存在4張電子標簽，當這些標簽同時應答發送自身的數據信息時就會相互干擾產生沖突，如果沒有合適的防碰撞算法加以解決，會大大影響系統的識別效率，甚至影響運轉。

現有的RFID防碰撞算法大都基于時分多址（TDMA）算法，可將其劃分為基于Aloha算法和基于二進制搜索BS（Binary Search）算法兩大類，以及正在發展的結合前兩種算法的混合協議，其中還包括大量改進算法。

1 基于Aloha協議

Aloha算法是一種隨機的、不確定性算法[1]，該算法的核心思想就是當多個標簽發生碰撞時，閱讀器將發送命令讓標簽停止發送，隨機等待一段時間后再重新發起查詢。該算法的特點是簡單、便于實現，但是因為該算法的隨機性較大，識別效率不太理想，故適用于低成本RFID系統。Aloha算法可以細分為以下幾種。

1.1 純Aloha（PA）算法

在基于PA的RFID系統中，當標簽進入閱讀器讀取范圍被通電激活之后隨機地用其ID進行響應。然后等待閱讀器回復，當閱讀器發出肯定確認（ACK）時，表示該標簽的ID已被正確接收，反之發送否定確認（NACK），這意味著標簽之間發生了碰撞。如果兩個或兩個以上的標簽發送時產生沖突，則隨機后退等待一段時間后再傳遞其ID。但是早期的純Aloha算法識別效率較低，最大吞吐率僅為18.4%[2]。

1.2 時隙Aloha（SA）算法

在基于Slotted Aloha（SA）的RFID系統中，將時間劃分為多個離散的時隙，標簽以同步時隙發送其ID。如果存在標簽沖突，即在同一個時隙內有多個標簽響應，則在隨機延遲后重新發送標簽，直到所有的標簽被成功識別。SA克服了PA部分碰撞的缺點，減少了時間開銷，SA算法的最大吞吐率可以達到36.8%[2]。

1.3 FSA與DFSA

改進的DFSA算法[3]在多輪中運行，并且還可以結合提前結束功能。然而，關鍵的區別是在每個讀取循環中，閱讀器可以使用標簽估計功能來改變其幀長。

標簽估計函數根據來自閱讀器幀的反饋來計算標簽的數量，其中包括用0填充的時隙數（c0）、用1填充的時隙數（c1）和多個簽響應（ck）。

標簽估計函數主要包括Vogt，Cha-I，Q協議，這里主要講解前兩種。

1.3.1 Vogt

Vogt具有兩種標簽估計功能[4]，分別表示為Vogt-I和Vogt-II。Vogt-I在碰撞期間至少涉及兩個標簽，因此標簽估計是c1+2ck。Vogt還提出了一組幀的大小，見表1所列。例如，當存在1～9個標簽時，幀的大小等于16，被認為最佳。基于他們的實驗，還提出1.4×（c1+2.39ck）作為標簽估計。另一方面，對于靜音環境，則0.65×（c1+2.39ck）為最佳。

1.3.2 Cha-I

Cha-I通過計算具有沖突的時隙數和幀長的比率來估計標簽[5]，并由下式給出，其中n是標簽個數，Cratio碰撞率為沖突時隙數和幀長的比值，Cratio=ck/N。在Cha-II中，標簽估計只是2.39ck。

1.4 增強型DFSA（EDFSA）

DFSA算法的限制是幀長的最大值被限制為256或512。如果標簽的數量超過此值，則持續的沖突成為關鍵問題。為此，Lee等人提出了DFSA的增強版本[6]，稱為增強型DFSA或EDFSA。其中，如果標簽群體大于可用的最大幀長，則將標簽分為M組。表2顯示給定標簽范圍的M值。

2 基于樹的協議

基于樹的算法可以分為樹分裂（TS）、查詢樹（Qt）、二進制搜索（BS）以及按位仲裁（BTA）等。

2.1 樹分裂（TS）

Tree Splitting（樹分裂）算法：TS算法通過使用隨機數發生器將響應標簽分成多個子集來操作。Hush[7]等人提出BTS，一種通過將碰撞標簽分解為幾個不相交的子集來解決沖突的算法。這些子集變得越來越小，直到它們包含一個標簽為止。在一系列時隙中，每個標簽都有一個隨機的計數器，將結果記錄在樹中的位置。計數器為0時，標簽處于發送狀態，否則處于等待或睡眠狀態。在每個時隙中閱讀器會通知標簽是否發生碰撞、單響應、無響應，如果沖突，則計數器隨機生成一個二進制數，加到當前計數器中。另外一方面，等待狀態的標簽計數器值加1。在空閑或單響應時，等待狀態標簽計數器值減1。

采用BTS算法識別{A = 010，B = 011，C = 100，D = 110}的基本過程見表3所列。

2.2 查詢樹Qt

查詢樹算法[8]（Qt）是一種典型的樹形結構算法。閱讀器選取搜索前綴（Prefix），發送Query命令，詢問其識別區域中的待識別標簽。標簽收到命令后，前綴與自身編號匹配。如果閱讀器收到標簽ID發生碰撞，再分別將Prefix加“1”和“0”作為新的Prefix發送出去。如果沒有碰撞則表明一個標簽被成功識別，直到所有的標簽都被成功識別。

圖2給出了采用Qt算法識別{1010，1011，1100，1101}的基本過程。經過13個周期完成了對這4個標簽的識別。

Qt算法只與當前查詢有關，不需要存儲先前查詢和響應狀態信息。Qt算法被稱為無記憶算法，是查詢樹算法的基礎和代表。

2.3 BS算法

BS算法[8]涉及閱讀器將序列號傳輸到標簽，然后將其與ID比較等內容。序列號長度與標簽編號長度一致，初始值由可能的最大標簽編號構成。當ID等于或低于序列號時標簽響應，然后，閱讀器通過使用曼徹斯特編碼對標簽的回復進行監視，一旦發生碰撞，閱讀器就會根據碰撞位減小序號，然后繼續搜索。如果沒有發生碰撞，則閱讀器成功識別一個標簽，并以初始序列號為參數重新開始搜索，直到識別出所有標簽。圖3給出了采用BS算法識別標簽{1010，1011，1100，1101}的基本過程。初始序列號ID值為“1111”，4個標簽的編號小于初始序號，標簽全部響應。由于標簽編號在空中媒介中的相互干擾，閱讀器收到“1XXX”，這表明標簽后三個比特都經歷過碰撞。然后閱讀器根據碰撞位，減小序列號為“1011”，繼續搜索，閱讀器收到“101X”。在第三個周期中，只有一個標簽“1010”響應，閱讀器在收到響應時沒有碰撞，完成了標簽的識別。接著又以初始序列號“1111”重新開始搜索，直到全部標簽識別完成。此次標簽識別采用BS算法經過8個周期，完成了對這4個標簽的識別。

BS算法具有很高的穩定性，易于軟件實現，吞吐率最高可達36.4%。但ID越長所需時間也就越長，時間超過一定限度后，BS算法將不再適用。

3 混合協議

混合協議是一項新的標簽閱讀協議的分支，該算法結合了Aloha算法與基于二進制搜索樹算法的優點，是碰撞算法的重要研究方向。

3.1 樹時隙 Aloha（TSA）

TSA算法是增強的FSA算法，在識別過程中使用樹狀結構[8]。在第一次讀取過程中傳遞的時隙用樹的根節點表示。每個標簽記住它們用于傳輸的時隙編號，如果在讀取周期內產生碰撞，閱讀器就會為每個發生碰撞的時隙開始一個新的閱讀周期，與樹的更新有關。每個標簽都有一個計數器來記住它在樹中的位置。每當發生碰撞時，就會將一個新節點插入到樹中，并啟動另一個閱讀周期。此過程重復進行，直到沒有碰撞發生。

3.2 混合查詢樹（HQT）[9]

該算法是將Qt算法與時隙的隨機回退機制相結合。基于該算法的識別過程：首先閱讀器向標簽發送兩位查詢，然后在回退延遲后發送前綴匹配的標簽。假設有0001，0011和0010，三個標簽如果閱讀器發送查詢00，那么每個標簽查詢之后的兩位是01，11和10。然后這些標簽分別將一個和兩個時隙的回退定時器設置為0。

3.3 HQT改進算法[10]

將Qt和Frame Aloha算法結合的兩種算法，即幀查詢樹算法和查詢樹Aloha算法[11]。幀查詢樹算法：閱讀器發送一幀給標簽，標簽隨機選擇一個時隙。在每個時隙中，Qt用于識別標簽。查詢樹Aloha算法：閱讀器發送一個前綴和幀長，然后前綴匹配的標簽在幀中隨機選擇一個時隙。換句話說，匹配的前綴標簽使用幀的Aloha協議進行識別。

4 結 語

本文對基于時分多址的RFID多標簽防碰撞算法做了全面的調查和分析。劃分為Aloha算法、樹搜索算法以及混合算法。

Aloha算法的最大優點是動態適應性，可以對不同的負載和低讀取器進行標簽命令，該算法簡單易于實現，適用于低成本RFID系統。研究出一種高效率的基于標簽估計函數的DFSA算法是當前任務，因為該算法對于給定的標簽范圍的準確性更高。

對于樹協議，Qt算法只需要一個前綴匹配和一個同步電路。然而，Qt算法的一個關鍵缺點是查詢的長度與構建樹的深度成比例，另一個問題是識別延遲隨ID大小而增加。因此，一個有趣的研究方向是使用偽ID來提升性能。

目前混合算法的數量還較少，鑒于Aloha和樹算法的數量，一個具有挑戰性的研究方向是確定具有最高讀取速率的組合。

隨著RFID技術的發展，每年電子標簽的使用量也呈指數增長。因此，一個高效準確且安全性高的防碰撞算法是未來的研究方向，以此適用于標簽范圍較大且識別系統較復雜的場景。

參考文獻

[1]周少珂，鄧淼磊.ALOHA標簽防碰撞算法綜述[J].計算機工程與應用，2017，53（14）：9-17.

[2]王勇，李婷.改進的基于ALOHA的RFID防碰撞算法[J].電信科學，2016，32（8）：77-81.

[3] FINKENZELLER K. RFID handbook：fundamentals and applications in contactless smart cards，radio frequency identification and near-field communication[Z]. New York：Wiley，2010：189-212.

[4] VOGT H. Multiple object identification with passive RFID tags[C]// International Conference on Pervasive Computing. Springer，Berlin，Heidelberg，2002：98-113.

[5] WANG J，ZHAO Y，WANG D. A Novel Fast Anti-Collision Algorithm for RFID Systems[C]// International Conference on Wireless Communications，Networking and Mobile Computing. IEEE，2007：2044-2047.

[6] LEE S R，LEE C W. An enhanced dynamic framed slotted aloha anti-collision algorithm [J]. Lecture notes in computer science，2006，4097：403-412.

[7] HUSH D R，WOOD C. Analysis of tree algorithms for RFID arbitration[C]// IEEE International Symposium on Information Theory，1998. Proceedings. IEEE，2002：15-23.

[8] BONUCCELLI M A，LONETTI F，MARTELLI F. Tree slotted aloha：a new protocol for tag identification in RFID networks[C]. 2006 International Symposium on a World of Wireless，Mobile and Multimedia Networks（WoWMoM'06），Buffalo-Niagara Falls，NY，2006：600-608.

[9] SHIN J D，YEO S S，KIM T H，et al. Hybrid tag anti-collision algorithms in RFID systems[C]// International Conference on Computational Science. Springer-Verlag，2007：693-700.

[10]錢東昊.基于標簽識別碼分組的混合防碰撞算法研究[D].天津：河北工業大學，2014.

[11]孫文勝，陳安輝.高效的RFID混合詢問樹防碰撞算法[J].計算機應用研究，2011，28（10）：3717-3719.

[12]蘇健，謝良波，楊穎，等.基于空閑時隙消除的超高頻RFID防碰撞算法[J].電子學報，2017，45（2）：307-314.