賀曉霞 秦松 賈小林

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

關(guān)鍵詞：RFID；防碰撞算法；Aloha算法；樹搜索算法；混合算法

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

0 引 言

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

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

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

1 基于Aloha協(xié)議

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

1.1 純Aloha（PA）算法

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

1.2 時隙Aloha（SA）算法

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

1.3 FSA與DFSA

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

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

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

1.3.1 Vogt

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

1.3.2 Cha-I

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

1.4 增強型DFSA（EDFSA）

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

2 基于樹的協(xié)議

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

2.1 樹分裂（TS）

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

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

2.2 查詢樹Qt

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

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

Qt算法只與當前查詢有關(guān)，不需要存儲先前查詢和響應(yīng)狀態(tài)信息。Qt算法被稱為無記憶算法，是查詢樹算法的基礎(chǔ)和代表。

2.3 BS算法

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

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

3 混合協(xié)議

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

3.1 樹時隙 Aloha（TSA）

TSA算法是增強的FSA算法，在識別過程中使用樹狀結(jié)構(gòu)[8]。在第一次讀取過程中傳遞的時隙用樹的根節(jié)點表示。每個標簽記住它們用于傳輸?shù)臅r隙編號，如果在讀取周期內(nèi)產(chǎn)生碰撞，閱讀器就會為每個發(fā)生碰撞的時隙開始一個新的閱讀周期，與樹的更新有關(guān)。每個標簽都有一個計數(shù)器來記住它在樹中的位置。每當發(fā)生碰撞時，就會將一個新節(jié)點插入到樹中，并啟動另一個閱讀周期。此過程重復進行，直到?jīng)]有碰撞發(fā)生。

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

該算法是將Qt算法與時隙的隨機回退機制相結(jié)合?；谠撍惴ǖ淖R別過程：首先閱讀器向標簽發(fā)送兩位查詢，然后在回退延遲后發(fā)送前綴匹配的標簽。假設(shè)有0001，0011和0010，三個標簽如果閱讀器發(fā)送查詢00，那么每個標簽查詢之后的兩位是01，11和10。然后這些標簽分別將一個和兩個時隙的回退定時器設(shè)置為0。

3.3 HQT改進算法[10]

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

4 結(jié) 語

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

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

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

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

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

參考文獻

[1]周少珂，鄧淼磊.ALOHA標簽防碰撞算法綜述[J].計算機工程與應(yīng)用，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].天津：河北工業(yè)大學，2014.

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

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