賀曉霞 秦松 賈小林

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

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

中圖分類號(hào)：TP39；TN911 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2018）07-00-04

0 引 言

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

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

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

1 基于Aloha協(xié)議

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

1.1 純Aloha（PA）算法

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

1.2 時(shí)隙Aloha（SA）算法

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

1.3 FSA與DFSA

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

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

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

1.3.1 Vogt

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

1.3.2 Cha-I

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

1.4 增強(qiáng)型DFSA（EDFSA）

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

2 基于樹的協(xié)議

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

2.1 樹分裂（TS）

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

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

2.2 查詢樹Qt

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

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

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

2.3 BS算法

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

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

3 混合協(xié)議

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

3.1 樹時(shí)隙 Aloha（TSA）

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

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

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

3.3 HQT改進(jìn)算法[10]

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

4 結(jié) 語

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

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

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

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

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

參考文獻(xiàn)

[1]周少珂，鄧淼磊.ALOHA標(biāo)簽防碰撞算法綜述[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（14）：9-17.

[2]王勇，李婷.改進(jìn)的基于ALOHA的RFID防碰撞算法[J].電信科學(xué)，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]錢東昊.基于標(biāo)簽識(shí)別碼分組的混合防碰撞算法研究[D].天津：河北工業(yè)大學(xué)，2014.

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

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