陸霞

摘要：標(biāo)簽碰撞一直是影響RFID系統(tǒng)工作性能的重要因素之一，解決標(biāo)簽碰撞問題，可以提高閱讀器的識別效率，信道的利用率。該文對基于ALOHA算法的隨機(jī)競爭類防碰撞技術(shù)進(jìn)行分析和研究，并對各類技術(shù)的特點(diǎn)作出總結(jié)。

關(guān)鍵詞：RFID；ALOHA；防碰撞

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）21-5102-03

射頻識別（Radio Frequency Identification，RFID）技術(shù)是利用射頻信號通過無線電波或空間耦合實(shí)現(xiàn)能量和數(shù)據(jù)信息傳遞的一種非接觸式自動識別技術(shù)。RFID因其無需人工干預(yù)、識別速度快、距離遠(yuǎn)、批量識別等優(yōu)點(diǎn)，被譽(yù)為21世紀(jì)最具發(fā)展前景的技術(shù)之一。目前，被廣泛應(yīng)用于供應(yīng)鏈管理、自動化生產(chǎn)、智能交通等多個領(lǐng)域，是物聯(lián)網(wǎng)實(shí)現(xiàn)的關(guān)鍵。

RFID系統(tǒng)實(shí)際在工作時，在閱讀器可讀取范圍內(nèi)，可能有多個標(biāo)簽同時向其發(fā)送數(shù)據(jù)，閱讀器就無法正確獲取相關(guān)數(shù)據(jù)，即為標(biāo)簽碰撞。選擇好的防碰撞算法可以降低閱讀器的識別時間，提高系統(tǒng)的工作效率。

為了解決標(biāo)簽防碰撞問題，目前主要采取兩種設(shè)計(jì)類型：隨機(jī)競爭類防碰撞算法和確定性防碰撞算法[1]。確定性防碰撞算法主要是基于二叉樹進(jìn)行設(shè)計(jì)的，包括二進(jìn)制搜索算法、動態(tài)二進(jìn)制搜索算法、動態(tài)查詢樹算法等。由于這類算法在標(biāo)簽發(fā)生碰撞時，沒有隨機(jī)的延時等待過程，識別時間可以確定，整個過程不存在隨機(jī)性，所以稱為確定性防碰撞算法。確定性防碰撞算法由于對每種可能性都會進(jìn)行遍歷，會導(dǎo)致閱讀器的識別時間延長，尤其是標(biāo)簽數(shù)量過多時，算法的效率會明顯降低。

本文主要對隨機(jī)競爭類防碰撞算法進(jìn)行分析和介紹，并對每種算法進(jìn)行性能總結(jié)。

1 RFID系統(tǒng)簡介

典型的RFID系統(tǒng)的工作前端由電子標(biāo)簽和讀寫器兩個部分構(gòu)成。其中，電子標(biāo)簽由標(biāo)簽芯片和天線封裝而成，電子標(biāo)簽保存被識別物體的信息，附著在物體表面，物體信息通過天線，使用射頻原理傳遞給讀寫器。

在復(fù)雜的物聯(lián)網(wǎng)環(huán)境下，應(yīng)用環(huán)境中的多標(biāo)簽、多讀寫器、外部噪聲等很多因素，都會影響到RFID技術(shù)的大規(guī)模使用。在標(biāo)簽防碰撞方面，必須考慮標(biāo)簽本身內(nèi)部的結(jié)構(gòu)和成本問題。目前，防碰撞方案主要建立在空分多址（SDMA）、頻分多址（FDMA）和時分多址（TDMA）三種多路復(fù)用技術(shù)之上。

2 隨機(jī)競爭類防碰撞算法

2.1 ALOHA算法

ALOHA算法是標(biāo)簽防碰撞算法中最簡單的一種，是基于TDMA的思想進(jìn)行通信的。在ALOHA算法中，標(biāo)簽中只存儲簡單的數(shù)據(jù)序列號，當(dāng)標(biāo)簽位于閱讀器范圍內(nèi)的時，標(biāo)簽主動將數(shù)據(jù)幀發(fā)送給閱讀器，若有其他標(biāo)簽也在發(fā)送數(shù)據(jù)幀，則發(fā)生碰撞。

這里的碰撞有兩種形式：部分沖突和完全沖突。部分沖突是指多個標(biāo)簽發(fā)送的數(shù)據(jù)幀中只有部分出現(xiàn)重疊；完全沖突是指碰撞標(biāo)簽發(fā)送的數(shù)據(jù)幀每位都發(fā)生重疊。

ALOHA算法的識別過程是：

① 閱讀器隨時處于偵聽狀態(tài)。

② 標(biāo)簽隨機(jī)向閱讀器發(fā)送數(shù)據(jù)幀。

③ 閱讀器判斷是否發(fā)生碰撞。

④ 如果沒有發(fā)生碰撞，閱讀器正確識別；如果發(fā)生碰撞，閱讀器命令所有標(biāo)簽停止數(shù)據(jù)幀發(fā)送，延長隨機(jī)的一段時間后，重新發(fā)送。

假設(shè)時隙ALOHA算法的碰撞周期為[T]，[λ]代表平均每秒發(fā)送的標(biāo)簽信息幀數(shù)

ALOHA算法是一種隨機(jī)接入算法，標(biāo)簽不需要同步工作，可以在任意時間段隨意發(fā)送數(shù)據(jù)，隨機(jī)性大，吞吐率低，只是用于實(shí)時性要求不高的場合。所以，它也是一種純ALOHA算法。

2.2 時隙ALOHA算法

時隙ALOHA算法把時間分為多個固定的時間段，每個時間段又分為若干個相等的時隙，時隙長度由系統(tǒng)時鐘決定。系統(tǒng)規(guī)定，只有在每個時隙的臨界處，標(biāo)簽才可以向閱讀器發(fā)送數(shù)據(jù)幀，并且標(biāo)簽數(shù)據(jù)幀的傳送過程必須在固定的一個時隙內(nèi)完成。如果發(fā)生碰撞，則必須等待下一個時隙再發(fā)送。

在時隙ALOHA算法的每個時隙內(nèi)，只有空閑、正確接收、碰撞三種情況發(fā)生。由于嚴(yán)格控制標(biāo)簽發(fā)送的時間，所以，如果在一個時隙內(nèi)沒有其他標(biāo)簽發(fā)送數(shù)據(jù)，就一定不會產(chǎn)生碰撞。

假設(shè)時隙ALOHA算法的碰撞周期為[T]，[λ]代表平均每秒發(fā)送的標(biāo)簽信息幀數(shù)，則[t]秒內(nèi)標(biāo)簽發(fā)送的數(shù)據(jù)幀數(shù)為：

2.3 動態(tài)幀時隙ALOHA算法

動態(tài)幀時隙ALOHA算法主要通過識別標(biāo)簽的數(shù)量來改變幀的長度，當(dāng)標(biāo)簽數(shù)量大于數(shù)據(jù)幀的時隙時，閱讀器根據(jù)發(fā)生碰撞的標(biāo)簽數(shù)量適當(dāng)增加時隙數(shù)；當(dāng)標(biāo)簽數(shù)量小于數(shù)據(jù)幀時隙時，閱讀器適量減少時隙數(shù)。

目前比較流行的估計(jì)標(biāo)簽數(shù)量的方法主要有兩種：

①使用估算函數(shù)

這種方法估算的依據(jù)主要是，當(dāng)發(fā)生碰撞時，一個時隙中至少同時存在兩個標(biāo)簽，則標(biāo)簽數(shù)量估算函數(shù)為：

3 總結(jié)

隨機(jī)競爭類防碰撞算法是建立在ALOHA算法之上的，可以根據(jù)RFID系統(tǒng)的特點(diǎn)進(jìn)行改變。它的本質(zhì)是分離標(biāo)簽的應(yīng)答時間，使標(biāo)簽在不同的時隙內(nèi)發(fā)送數(shù)據(jù)，一旦發(fā)生碰撞，采用退避原則，等待下一個周期[3]。所以這一類算法的缺點(diǎn)是隨機(jī)性比較大，當(dāng)標(biāo)簽數(shù)量過多，識別的復(fù)雜度會提高，系統(tǒng)吞吐率也比較低。

參考文獻(xiàn)：

[1] 單劍鋒，陳明，謝建兵.基于ALOHA算法的RFID防碰撞技術(shù)研究[J].南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（1）.

[2] 謝振華，賴聲禮，陳鵬. RFID技術(shù)和防沖撞算法[J].計(jì)算機(jī)工程與應(yīng)用，2007 ，43（6） ：223-225.

[3] 于佳，肖麗萍.基于ALOHA算法的RFID防碰撞技術(shù)研究[J].電子技術(shù)，2009，36（8） ：43-45.

[4] 俞曉磊，于銀山，汪東華.物聯(lián)網(wǎng)環(huán)境下RFID防碰撞及動態(tài)測試關(guān)鍵技術(shù)研究[J].物聯(lián)網(wǎng)技術(shù)，2012（7）：25-29.