楊曉嬌1，吳必造2

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

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

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

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

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

0引言

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

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

1時(shí)隙ALOHA算法

　　1.1時(shí)隙ALOHA算法工作原理

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

　　1.2時(shí)隙ALOHA算法吞吐率分析

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

　　S=Ge-G（1）

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

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

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

　　Smax=e-1≈36.8%（3）

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

2幀時(shí)隙及動(dòng)態(tài)幀時(shí)隙ALOHA算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4算法仿真

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

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

5結(jié)論

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

參考文獻(xiàn)

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

　?。?］ 黃玉蘭，夏璞，夏巖，等．物聯(lián)網(wǎng)射頻識(shí)別(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.

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

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

　?。?］ 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.

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

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

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