楊曉嬌1，吳必造2

　　（1． 重慶交通大學(xué) 信息技術(shù)中心，重慶 400074；2. 中移物聯(lián)網(wǎng)有限公司 解決方案中心,重慶 401336)

        摘要：針對RFID系統(tǒng)中的不確定防碰撞算法即ALOHA算法進(jìn)行分析，首先介紹了ALOHA算法的工作原理，并對該類算法的吞吐率進(jìn)行理論分析;然后推算得出當(dāng)時隙數(shù)等于標(biāo)簽個數(shù)時吞吐率最高為36.8%;最后分析了幾類改進(jìn)的ALOHA算法的工作原理，對比了幾類改進(jìn)算法的優(yōu)缺點以及在實際工程實踐中的實用性。本文對ALOHA算法的后續(xù)研究工作以及工程實踐中ALOHA算法的選取以及應(yīng)用具有參考價值。

　　關(guān)鍵詞：時分多路算法；不確定算法；動態(tài)幀時隙ALOHA；時隙

　　中圖分類號：TP312文獻(xiàn)標(biāo)識碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.004

　　引用格式：楊曉嬌，吳必造. RFID中的不確定性標(biāo)簽防碰撞算法簡介［J］.微型機(jī)與應(yīng)用，2017,36（6）：10-12.

0引言

　　由于RFID具有同時快速識別多目標(biāo)且存儲信息量大等特點，從而被作為感知層的關(guān)鍵技術(shù)廣泛應(yīng)用于物流、工業(yè)、農(nóng)業(yè)等物聯(lián)網(wǎng)領(lǐng)域。要實現(xiàn)多目標(biāo)快速識別就需要在RFID系統(tǒng)中實現(xiàn)防碰撞算法，這也是本文研究的重點。防碰撞算法主要有基于時分多路的防碰撞算法和基于頻分多路的防碰撞算法。而目前應(yīng)用最廣泛防碰撞算法大多是時分多路的，主要有如下兩類：確定性防碰撞算法和概率性防碰撞算法［1］。

　　確定性標(biāo)簽防碰撞算法主要有二進(jìn)樹算法及其改進(jìn)算法，優(yōu)點是能識別所有標(biāo)簽，沒有標(biāo)簽“餓死”現(xiàn)象；缺點是該算法對閱讀器硬件要求較高且算法的空間和時間復(fù)雜度較高。概率性標(biāo)簽防碰撞算法主要是指ALOHA及其改進(jìn)算法，這類算法優(yōu)點是復(fù)雜度小且容易實現(xiàn)，硬件成本相對較低；缺點是存在標(biāo)簽“餓死”的情況。由于ALOHA算法對硬件要求較低，且實現(xiàn)復(fù)雜度較低，因此在RFID標(biāo)簽防碰撞領(lǐng)域內(nèi)ALOHA算法是應(yīng)用最廣泛的［2］。這也是本文探討的重點。本文首先介紹了時隙ALOHA算法及動態(tài)幀時隙ALOHA算法；然后介紹了目前比較好的改進(jìn)型ALOHA算法；最后對各種算法的使用情況以及性能做綜合對比分析并給出總結(jié)。

1時隙ALOHA算法

　　1.1時隙ALOHA算法工作原理

　　圖1時隙ALOHA算法的示意圖時隙ALOHA（Slotted ALOHA）算法將標(biāo)簽與閱讀器的通信時間分為如圖1所示的若干個等長的時槽（每個時槽的長度大于標(biāo)簽與閱讀器完成一次通信的時長）。根據(jù)時隙ALOHA算法的規(guī)定，標(biāo)簽在每個時隙開始時向閱讀器傳輸數(shù)據(jù)，且在當(dāng)前時隙結(jié)束時將本輪數(shù)據(jù)傳輸完畢。

　　1.2時隙ALOHA算法吞吐率分析

　　根據(jù)泊松分布可以推導(dǎo)出，時隙ALOHA算法的吞吐率為［3］：

　　S=Ge-G（1）

　　其中：S為吞吐率，表示實際傳輸?shù)挠行У臄?shù)據(jù)率；G為輸入負(fù)載，表示標(biāo)簽向閱讀器發(fā)送的總數(shù)據(jù)率。

　　下面探討時隙ALOHA算法的吞吐率極值，對公式（1）中的G求導(dǎo)可得：

　　然后把G=1帶入式（1）可得S的最大值為：

　　Smax=e-1≈36.8%（3）

　　由公式（3）可知，時隙ALOHA算法的吞吐率極值為36.8%。

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

　　幀時隙以及動態(tài)幀時隙ALOHA算法都是在時隙ALOHA算法的基礎(chǔ)上將N個時隙組成一幀，如圖2所示，所有標(biāo)簽都在一幀內(nèi)的N個時隙中選擇一個時隙與閱讀器進(jìn)行通信，若由于碰撞導(dǎo)致無法識別標(biāo)簽，則對下一幀繼續(xù)識別。

　　動態(tài)幀時隙ALOHA算法即根據(jù)標(biāo)簽個數(shù)n來動態(tài)調(diào)整幀長N的大小，使ALOHA算法的吞吐率最優(yōu)。

　　已有很多文章對幀長N與標(biāo)簽個數(shù)n與吞吐率的關(guān)系做過論證。當(dāng)N=n時幀時隙ALOHA算法的吞吐率最高。

3改進(jìn)的動態(tài)幀時隙ALOHA算法

　　改進(jìn)的ALOHA算法主要有三種，下面分別對其進(jìn)行分析。

　　3.1基于數(shù)學(xué)分析的改進(jìn)ALOHA算法

　　這類改進(jìn)的動態(tài)幀時隙ALOHA算法本質(zhì)上還是隨機(jī)算法，算法的思想是通過對閱讀器接收到的一幀中的碰撞、空閑以及成功時隙的個數(shù)進(jìn)行數(shù)學(xué)建模和分析，推導(dǎo)出相應(yīng)數(shù)學(xué)公式來估計閱讀器作用域內(nèi)處于活動狀態(tài)的標(biāo)簽個數(shù)，這類算法推導(dǎo)公式的目的是盡量使估計到的標(biāo)簽個數(shù)接近實際的標(biāo)簽個數(shù)［45］。

　　估算結(jié)束后閱讀器向標(biāo)簽廣播的幀長N=估計出的標(biāo)簽個數(shù)n，從而使算法理論上的吞吐率盡量接近36.8%。注意，算法在實際實現(xiàn)過程中幀長N=2Q（Q=1，2，3，…）即N=2，4，8，16，32，64，128，…。

　　總之這類算法的吞吐率在理論上能夠無限接近于36.8%，但是算法的時間復(fù)雜度較高，而RFID閱讀器計算能力以及存儲空間都有限，因此在實際工程中，若閱讀器計算能力以及存儲空間較優(yōu)，則可以采用這類算法。

　　3.2基于工程實現(xiàn)改進(jìn)ALOHA 算法

　　由于實際應(yīng)用中閱讀器提供的時隙數(shù)N=2Q即N取值只能為2，4，8，16，32，64，128，…，且閱讀器的存儲能力以及運算能力都有限，因此有了基于EPC G1,G2協(xié)議中動態(tài)幀時隙ALOHA 算法的改進(jìn)算法。

　　這類算法通過閱讀器接收到空閑、成功以及碰撞時隙的個數(shù)，對幀長參數(shù)Q進(jìn)行動態(tài)調(diào)整，調(diào)整的方法為檢測到碰撞（空閑）時隙則Q+C（Q-C）。改進(jìn)算法通過仿真數(shù)學(xué)運算選取一個合適的C值，使幀長調(diào)整更合理。這種算法較3.1節(jié)的算法時間復(fù)雜度更低，也更易實現(xiàn)。

　　另一種是基于閾值跳變的時隙數(shù)調(diào)整算法，這類算法時隙數(shù)變化不與C值相關(guān)，閱讀器維護(hù)一個時隙數(shù)跳變的列表，收到標(biāo)簽回復(fù)后根據(jù)標(biāo)簽總數(shù)和空閑碰撞時隙數(shù)所占的比例選取表中相應(yīng)的時隙數(shù)。這種算法相比于C值調(diào)整時隙的算法避免了浮點運算，但對閱讀器的存儲能力要求較高［68］。

　　3.3基于二分法的改進(jìn)ALOHA 算法

　　將ALOHA算法與二進(jìn)制搜索算法相結(jié)合，來提高算法的效率。具體實現(xiàn)是先用ALOHA算法對標(biāo)簽進(jìn)行分流，如碰上碰撞時隙則對該碰撞時隙采用二分法進(jìn)行分流，直至完全識別當(dāng)前時隙的所有標(biāo)簽，再返回繼續(xù)識別下一時隙［910］。這類算法由于需要應(yīng)用到二進(jìn)制搜索算法，因此算法需要閱讀器在硬件上支持曼側(cè)斯特編碼，故該算法對系統(tǒng)硬件的要求相對較高，且算法的時間復(fù)雜度也相對較高，但是該算法的優(yōu)勢是吞吐率較高，且由于具有二分法的特點因此可以避隨機(jī)算法中標(biāo)簽餓死的情況出現(xiàn)。

4算法仿真

　　本文的所有仿真實驗都是在MATLAB 7.0平臺上進(jìn)行的。分別編程實現(xiàn)不同算法識別標(biāo)簽的過程，再統(tǒng)計運行的結(jié)果，為了減小偶然因素對算法評估造成影響，圖3中所有的結(jié)果都是對相同的標(biāo)簽識別10次后取平均值的結(jié)果。

　　從圖3可以看出，基于二分的ALOHA算法吞吐率最高穩(wěn)定在55%左右，但是需要結(jié)合二分法，硬件要支持曼側(cè)斯特編碼，且算法的復(fù)雜度相對較高。其次是基于EPC的改進(jìn)算法吞吐率穩(wěn)定在0.41%左右，在工程實現(xiàn)中推薦這種方法，吞吐率較高且算法復(fù)雜度較低，對硬件要求也不高。如圖3數(shù)學(xué)估計算法中標(biāo)簽估計最準(zhǔn)確吞吐率能接近35%，一般工程實現(xiàn)中不適用這種方法。

5結(jié)論

　　本文首先介紹了ALOHA算法的基本原理和優(yōu)缺點，然后介紹了ALOHA算法以及動態(tài)幀時隙的工作原理并對算法的理論吞吐率做了推導(dǎo)，得出當(dāng)標(biāo)簽個數(shù)等于時隙數(shù)時ALOHA算法的理論最高吞吐率為36.8%，簡介了當(dāng)前主流的基于ALOHA算法的改進(jìn)算法原理，并總結(jié)了算法的優(yōu)缺點，最后對不同吞吐率仿真得出基于二分法的ALOHA算法吞吐率最高接近55%，但是實現(xiàn)難度較高，EPC改進(jìn)算法吞吐率其次，接近41%，實現(xiàn)難度較低。本文可為RFID系統(tǒng)中防碰撞算法的研究工作提供參考。

參考文獻(xiàn)

　　［1］ 孫其博，劉杰，黎羴，等．物聯(lián)網(wǎng):概念、架構(gòu)與關(guān)鍵技術(shù)研究綜述［J］．北京郵電大學(xué)學(xué)報，2010,33(3):2-3.

　　［2］ 黃玉蘭，夏璞，夏巖，等．物聯(lián)網(wǎng)射頻識別(RFID)核心技術(shù)詳解［M］. 北京:人民郵電出版社，2012．

　　［3］ CHA J R, KIM J H. Dynamic framed slotted ALOHA algorithm using fast tag estimation method for RFID system［C］. Consumer Communications and Networking Conference, 2006 CCNC.3 IEEE, 2006:768-772.

　　［4］ 陳平華，王康順，李超，等.基于線性回歸的動態(tài)幀時隙ALOHA算法［J］.計算機(jī)仿真，2014,31(7):259-263.

　　［5］ 石封查，崔琛，余劍.基于標(biāo)簽運動的一種新型RFID防碰撞算法［J］.計算機(jī)科學(xué)，2013,40（6）: 76-79.

　　［6］ EPC Global. EPC RadioFrequency Identity Protocols Gengernation2 UHF RFID Protocol for Communication at 860 MHz~960 MHz Version［S］. California: EPC Global ,2008.

　　［7］ EPC Global. EPC RadioFrequency Identity Protocols Gengernation1［S］. American:UCC, 2013.

　　［8］ 吳淼，劉德盟，張釗鋒.基于EPC Gen2防碰撞機(jī)制的研究與優(yōu)化［J］．微電子學(xué)與計算機(jī)，2013,30（5）:101-104.

　　［9］ 徐圓圓，曾雋芳，劉禹.基于Aloha算法的幀長及分組數(shù)改進(jìn)研究［J］. 計算機(jī)應(yīng)用，2008,28(3):588-590.

　　［10］ 鞠偉成，俞承芳.一種基于動態(tài)二進(jìn)制的RFID抗沖突算法［J］. 復(fù)旦大學(xué)學(xué)報（自然科學(xué)版），2005，44(1):46-50.