楊曉嬌1，吳必造2
（1． 重慶交通大學 信息技術中心，重慶 400074；2. 中移物聯網有限公司 解決方案中心,重慶 401336)
摘要：針對RFID系統中的不確定防碰撞算法即ALOHA算法進行分析，首先介紹了ALOHA算法的工作原理，并對該類算法的吞吐率進行理論分析;然后推算得出當時隙數等于標簽個數時吞吐率最高為36.8%;最后分析了幾類改進的ALOHA算法的工作原理，對比了幾類改進算法的優缺點以及在實際工程實踐中的實用性。本文對ALOHA算法的后續研究工作以及工程實踐中ALOHA算法的選取以及應用具有參考價值。
關鍵詞：時分多路算法；不確定算法；動態幀時隙ALOHA；時隙
中圖分類號：TP312文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.004
引用格式：楊曉嬌，吳必造. RFID中的不確定性標簽防碰撞算法簡介［J］.微型機與應用，2017,36（6）：10-12.
0引言
由于RFID具有同時快速識別多目標且存儲信息量大等特點，從而被作為感知層的關鍵技術廣泛應用于物流、工業、農業等物聯網領域。要實現多目標快速識別就需要在RFID系統中實現防碰撞算法，這也是本文研究的重點。防碰撞算法主要有基于時分多路的防碰撞算法和基于頻分多路的防碰撞算法。而目前應用最廣泛防碰撞算法大多是時分多路的，主要有如下兩類：確定性防碰撞算法和概率性防碰撞算法［1］。
確定性標簽防碰撞算法主要有二進樹算法及其改進算法，優點是能識別所有標簽，沒有標簽“餓死”現象；缺點是該算法對閱讀器硬件要求較高且算法的空間和時間復雜度較高。概率性標簽防碰撞算法主要是指ALOHA及其改進算法，這類算法優點是復雜度小且容易實現，硬件成本相對較低；缺點是存在標簽“餓死”的情況。由于ALOHA算法對硬件要求較低，且實現復雜度較低，因此在RFID標簽防碰撞領域內ALOHA算法是應用最廣泛的［2］。這也是本文探討的重點。本文首先介紹了時隙ALOHA算法及動態幀時隙ALOHA算法；然后介紹了目前比較好的改進型ALOHA算法；最后對各種算法的使用情況以及性能做綜合對比分析并給出總結。
1時隙ALOHA算法
1.1時隙ALOHA算法工作原理
圖1時隙ALOHA算法的示意圖時隙ALOHA（Slotted ALOHA）算法將標簽與閱讀器的通信時間分為如圖1所示的若干個等長的時槽（每個時槽的長度大于標簽與閱讀器完成一次通信的時長）。根據時隙ALOHA算法的規定，標簽在每個時隙開始時向閱讀器傳輸數據，且在當前時隙結束時將本輪數據傳輸完畢。
1.2時隙ALOHA算法吞吐率分析
根據泊松分布可以推導出，時隙ALOHA算法的吞吐率為［3］：
S=Ge-G（1）
其中：S為吞吐率，表示實際傳輸的有效的數據率；G為輸入負載，表示標簽向閱讀器發送的總數據率。
下面探討時隙ALOHA算法的吞吐率極值，對公式（1）中的G求導可得：
然后把G=1帶入式（1）可得S的最大值為：
Smax=e-1≈36.8%（3）
由公式（3）可知，時隙ALOHA算法的吞吐率極值為36.8%。
2幀時隙及動態幀時隙ALOHA算法
幀時隙以及動態幀時隙ALOHA算法都是在時隙ALOHA算法的基礎上將N個時隙組成一幀，如圖2所示，所有標簽都在一幀內的N個時隙中選擇一個時隙與閱讀器進行通信，若由于碰撞導致無法識別標簽，則對下一幀繼續識別。
動態幀時隙ALOHA算法即根據標簽個數n來動態調整幀長N的大小，使ALOHA算法的吞吐率最優。
已有很多文章對幀長N與標簽個數n與吞吐率的關系做過論證。當N=n時幀時隙ALOHA算法的吞吐率最高。
3改進的動態幀時隙ALOHA算法
改進的ALOHA算法主要有三種，下面分別對其進行分析。
3.1基于數學分析的改進ALOHA算法
這類改進的動態幀時隙ALOHA算法本質上還是隨機算法，算法的思想是通過對閱讀器接收到的一幀中的碰撞、空閑以及成功時隙的個數進行數學建模和分析，推導出相應數學公式來估計閱讀器作用域內處于活動狀態的標簽個數，這類算法推導公式的目的是盡量使估計到的標簽個數接近實際的標簽個數［45］。
估算結束后閱讀器向標簽廣播的幀長N=估計出的標簽個數n，從而使算法理論上的吞吐率盡量接近36.8%。注意，算法在實際實現過程中幀長N=2Q（Q=1，2，3，…）即N=2，4，8，16，32，64，128，…。
總之這類算法的吞吐率在理論上能夠無限接近于36.8%，但是算法的時間復雜度較高，而RFID閱讀器計算能力以及存儲空間都有限，因此在實際工程中，若閱讀器計算能力以及存儲空間較優，則可以采用這類算法。
3.2基于工程實現改進ALOHA 算法
由于實際應用中閱讀器提供的時隙數N=2Q即N取值只能為2，4，8，16，32，64，128，…，且閱讀器的存儲能力以及運算能力都有限，因此有了基于EPC G1,G2協議中動態幀時隙ALOHA 算法的改進算法。
這類算法通過閱讀器接收到空閑、成功以及碰撞時隙的個數，對幀長參數Q進行動態調整，調整的方法為檢測到碰撞（空閑）時隙則Q+C（Q-C）。改進算法通過仿真數學運算選取一個合適的C值，使幀長調整更合理。這種算法較3.1節的算法時間復雜度更低，也更易實現。
另一種是基于閾值跳變的時隙數調整算法，這類算法時隙數變化不與C值相關，閱讀器維護一個時隙數跳變的列表，收到標簽回復后根據標簽總數和空閑碰撞時隙數所占的比例選取表中相應的時隙數。這種算法相比于C值調整時隙的算法避免了浮點運算，但對閱讀器的存儲能力要求較高［68］。
3.3基于二分法的改進ALOHA 算法
將ALOHA算法與二進制搜索算法相結合，來提高算法的效率。具體實現是先用ALOHA算法對標簽進行分流，如碰上碰撞時隙則對該碰撞時隙采用二分法進行分流，直至完全識別當前時隙的所有標簽，再返回繼續識別下一時隙［910］。這類算法由于需要應用到二進制搜索算法，因此算法需要閱讀器在硬件上支持曼側斯特編碼，故該算法對系統硬件的要求相對較高，且算法的時間復雜度也相對較高，但是該算法的優勢是吞吐率較高，且由于具有二分法的特點因此可以避隨機算法中標簽餓死的情況出現。
4算法仿真
本文的所有仿真實驗都是在MATLAB 7.0平臺上進行的。分別編程實現不同算法識別標簽的過程，再統計運行的結果，為了減小偶然因素對算法評估造成影響，圖3中所有的結果都是對相同的標簽識別10次后取平均值的結果。
從圖3可以看出，基于二分的ALOHA算法吞吐率最高穩定在55%左右，但是需要結合二分法，硬件要支持曼側斯特編碼，且算法的復雜度相對較高。其次是基于EPC的改進算法吞吐率穩定在0.41%左右，在工程實現中推薦這種方法，吞吐率較高且算法復雜度較低，對硬件要求也不高。如圖3數學估計算法中標簽估計最準確吞吐率能接近35%，一般工程實現中不適用這種方法。
5結論
本文首先介紹了ALOHA算法的基本原理和優缺點，然后介紹了ALOHA算法以及動態幀時隙的工作原理并對算法的理論吞吐率做了推導，得出當標簽個數等于時隙數時ALOHA算法的理論最高吞吐率為36.8%，簡介了當前主流的基于ALOHA算法的改進算法原理，并總結了算法的優缺點，最后對不同吞吐率仿真得出基于二分法的ALOHA算法吞吐率最高接近55%，但是實現難度較高，EPC改進算法吞吐率其次，接近41%，實現難度較低。本文可為RFID系統中防碰撞算法的研究工作提供參考。
參考文獻
［1］ 孫其博，劉杰，黎羴，等．物聯網:概念、架構與關鍵技術研究綜述［J］．北京郵電大學學報，2010,33(3):2-3.
［2］ 黃玉蘭，夏璞，夏巖，等．物聯網射頻識別(RFID)核心技術詳解［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］ 陳平華，王康順，李超，等.基于線性回歸的動態幀時隙ALOHA算法［J］.計算機仿真，2014,31(7):259-263.
［5］ 石封查，崔琛，余劍.基于標簽運動的一種新型RFID防碰撞算法［J］.計算機科學，2013,40（6）: 76-79.
［6］ EPC Global. EPC RadioFrequency Identity Protocols Gengernation2 UHF RFID Protocol for Communication at 860 MHz~960 MHz Version［S］. California: EPC Global ,2008.
［7］ EPC Global. EPC RadioFrequency Identity Protocols Gengernation1［S］. American:UCC, 2013.
［8］ 吳淼，劉德盟，張釗鋒.基于EPC Gen2防碰撞機制的研究與優化［J］．微電子學與計算機，2013,30（5）:101-104.
［9］ 徐圓圓，曾雋芳，劉禹.基于Aloha算法的幀長及分組數改進研究［J］. 計算機應用，2008,28(3):588-590.
［10］ 鞠偉成，俞承芳.一種基于動態二進制的RFID抗沖突算法［J］. 復旦大學學報（自然科學版），2005，44(1):46-50.