改進的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京郵電大學，江蘇 南京 210023）

改進的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京郵電大學，江蘇 南京 210023）

為了解決RFID系統中電子標簽識別效率不高的問題，對基于ALOHA的隨機性防碰撞算法進行了詳細分析，提出了一種新的ALOHA防碰撞算法。在該算法中，針對標簽估計，采用動態調整的方式自動改變標簽估計式中的系數，使得標簽估計個數隨著已識別的標簽數動態變化，從而估計下一幀待識別標簽數；而對于幀長調整，根據估計的標簽數，通過幀長與標簽數分組的關系確定。通過MATLAB進行仿真，結果表明，該算法能明顯提高系統的吞吐率和穩定性。

RFID；ALOHA算法；吞吐率；分組；標簽估計

1 引言

無線射頻識別（radio frequency identification，RFID）是一種利用射頻信號和空間耦合的傳輸特性進行雙向通信，實現對物體非接觸式自動識別的技術[1]。隨著科學技術的發展，RFID技術現已廣泛應用于倉庫管理[2]、室內定位[3]、圖書館管理[4]等諸多領域。然而當有2個或2個以上的標簽在相同信道同時與閱讀器進行通信時，由于不同的信號會產生混疊和干擾，使讀寫器不能對任意一個標簽進行識別，從而產生碰撞，導致標簽識別和數據傳送失敗[5,6]。因此為了實現電子標簽的有效、可靠識別，如何解決防碰撞問題成為RFID技術研究的關鍵點之一。

目前，解決碰撞問題的算法主要有基于ALOHA的隨機性防碰撞算法[7,8]和基于二進制樹的確定性防碰撞算法[9-11]，并在此基礎上對兩種算法進行改進。其中，隨機性防碰撞算法改進的關鍵點在于幀長的調整，使其動態地與待讀標簽數相吻合，尤其適用于標簽密集、數量較多的情況，確定性防碰撞算法的改進在于減少信息冗余和尋求合理的尋址策略。隨機性防碰撞算法簡單、成本低，但系統吞吐率易受標簽數、幀長等的影響；確定性防碰撞算法雖然能保證每個標簽能及時被識別，但具有整個識別周期過長、系統設計較為復雜、標簽成本較高等缺點[12,13]。

同時近幾年來，針對ALOHA防碰撞算法效率不高的特點，雖然人們提出了各種針對標簽估計和幀長調整的動態幀時隙ALOHA算法來改進算法效率，但是由于大多都是通過采用上一幀的識別情況來估計標簽數和使幀長等于標簽數來改進算法，所以系統的識別效率一般不超過36.8%。

針對這一特點，本文主要研究針對物流貨物管理、健康管理、畜牧業流通等RFID主要應用領域的防碰撞算法，并在分析了各類ALOHA防碰撞算法后，提出了一種新的ALOHA防碰撞算法。在算法中，采用動態自適應調整方式，根據每次估計的標簽數，動態調整估計因子，使下一次待識別的標簽數與實際標簽數更接近。同時，為了使系統效率高于理論上當幀長與待識別標簽數相等時的效率，本文幀長由幀長與標簽數的分組關系確定。仿真表明，改進的算法能使系統的效率有所改善。

2 ALOHA類算法

ALOHA算法是一種最基本、最簡單的標簽防碰撞算法，它是基于TDMA的一種防碰撞算法，是基于概率的算法。該算法是指閱讀器在不同的時間分別與處于閱讀器讀取范圍內的標簽通信，從而減少沖突發生的概率，主要包括改進型的 ALOHA[14]和時隙 ALOHA（slotted-ALOHA）算法[15,16]。

2.1 純ALOHA算法

純ALOHA（P-ALOHA）算法是一種標簽先發言的算法，標簽進入閱讀器作用范圍獲得能量，將自己的編碼信息發給閱讀器，在此過程中，如果有其他標簽同時發送信息，就發生信號重疊，導致信息完全碰撞或部分碰撞，系統最大吞吐率約為18.4%。

2.2 時隙ALOHA算法

時隙ALOHA算法是對純ALOHA 算法一種最簡單的改進算法，能夠節約時間。它是在純ALOHA算法的基礎上，把閱讀器發送信號的時間劃分成多個連續的離散時隙（slot），而由系統時鐘對時隙長度進行控制。與基本ALOHA算法相比，時隙ALOHA算法中任何一個時隙內只存在一個標簽成功識別或無標簽響應或多個標簽完全碰撞，沒有基本ALOHA算法中的部分碰撞，所以返回數據發送碰撞的時間減少了一半，這樣提高了信道利用率，系統吞吐率提高1倍，系統最大吞吐率約為36.8%，如圖1所示。

圖1 不同輸入負載的系統吞吐率

2.3 幀時隙ALOHA算法

幀時隙ALOHA算法是在時隙ALOHA算法基礎上的改進，閱讀器將一幀分成N個時隙，每個時隙的長度大于標簽的響應時間。標簽接到閱讀器的請求信號后，在N個時隙中隨機選擇一個時隙通信。如果一個時隙只被唯一的標簽選中，則此時隙中標簽傳輸的信息被閱讀器成功接收，標簽被正確識別。如果有兩個或兩個以上的標簽選擇了同一時隙發送，則會產生沖突，這些同時發送信息的標簽就不能被讀寫器成功識別。整個算法的識別過程都會如此循環，一直到所有標簽都被識別完成。

假設幀長為N，閱讀器可識別范圍內標簽數為n，并假定所有標簽均勻分布在各個時隙，即標簽選擇每個時隙的概率都是1/N，那么在一個時隙內具有r個標簽的概率將服從二項分布。

具有r個標簽的時隙期望值為：

該時隙為空時隙、成功時隙、碰撞時隙的概率分別為：

該時隙為空時隙、成功時隙、碰撞時隙的期望值分別為：

系統吞吐率為：

對式（9）求導，即可得出最佳幀長為：

當n足夠大時，由泰勒展開式，可得：

所以，當閱讀器幀長N和未識別標簽數量n相等時，標簽成功傳輸概率最大，系統工作在最佳狀態，同時系統效率在標簽數量趨于無窮大時約為36.8%。

圖2為幀時隙ALOHA算法在不同幀長條件下，標簽數量和系統吞吐率的關系曲線。可以看出，當標簽數遠小于閱讀器的幀時隙數時，會造成時隙的浪費，當標簽數和閱讀器的幀時隙數相等時，系統的吞吐率最大。

圖2 不同幀長的系統吞吐率曲線

2.4 動態幀時隙ALOHA算法

動態幀時隙ALOHA （dynamic framed slotted ALOHA,DFSA）算法針對幀時隙ALOHA算法的標簽數目與幀長度相差越多，系統性能越差的這個缺點，提出了一種彌補和改善的方法[17]。具體的做法就是使用動態的幀時隙數，使得每幀內的時隙數接近系統中標簽的數目，是一種改進的FSA算法，在該算法中，閱讀器能動態調整下一次閱讀循環中每幀的時隙數目。

3 改進幀時隙ALOHA算法

通過對上面ALOHA算法的分析可知，影響系統吞吐率的因素主要有標簽個數的估計和幀長的調整。其中，在當前研究中較多使用的標簽估計算法有最小二乘算法、Schoute算法以及Vogt算法。在這些算法中，每識別完一幀時隙后，雖然能根據上一幀的識別情況估算出下一幀待識別的標簽數，并使幀長等于標簽數，從而計算出系統的吞吐率，但是它們僅僅使用了本次查詢的碰撞標簽來進行估計，且系數幾乎都是常數，并沒有進行驗證。同時，使幀長等于標簽估計數，雖然能使系統吞吐率達到最大值，但是碰撞率也隨之變大，并不能使系統工作在穩定吞吐率下，因此提出了一種新的防碰撞算法。

3.1 標簽估計

本標簽估計算法是對參考文獻[18]中算法的改進，核心是根據本次查詢的標簽數情況，估計出下一幀的標簽數，然后根據已有的標簽估計算法，至下一次查詢時，估計出該次查詢的標簽數，然后對其進行比較，得出預測因子，從而使系統能根據兩次連續的讀取狀態自動調整，而當前一幀的碰撞時隙數為零，未識別標簽又不為零時，不停止查詢，而是繼續以初始設置幀長，對系統進行查詢，從而形成一個周期，直到所有的標簽被識別完。

設第i次查詢后，空閑時隙數、成功時隙數、碰撞時隙數分別為 C0(i)、C1(i)、Ck(i)，待識別的下一幀時隙數與碰撞時隙數呈線性關系，即：

那么就可以根據第次查詢的碰撞時隙數預測下一幀的標簽數，這里k不是固定不變的，而是根據實際情況進行調整。

第i+1次查詢后，可以采用JaeRyongCha提出的第一種標簽估計算法進行標簽估計，為：

則可以求出預測標簽與驗證標簽的相對誤差為：

為了使相對誤差的平方最小，使ε2對k求導，可得：

值得注意的是，第i+1的標簽估計仍需第i+1的標簽估計完成后才能得到，這是不現實的，因此調整為：

從而得到下一幀待識別的標簽數為：

其中，Ck(0)等于初始設置的幀長；當Ck(i)為零而系統標簽未識別完時，系統繼續以初始設置幀長識別標簽，直到所有標簽被識別完。

3.2 幀長調整

由式（4）、式（5）可知，雖然當標簽數與幀長相等時，系統能達到最大的吞吐率，但是系統的碰撞率也隨即增大，且如果標簽數量和系統能達到的幀長最大值相差很多，碰撞問題將難以解決。本算法是根據分組的思想來提高系統的吞吐率。算法首先確定出以2的次冪連續為幀長時，如4、8、16、32，系統吞吐率曲線交點處的標簽數，那么該標簽數即可作為調整幀長和標簽分組數的臨界點。一旦標簽數達到該臨界點，就可以調整相應幀長的大小。而通過計算，可得兩相鄰曲線的標簽交點數為：

然后再根據系統最大效率與標簽數進行分組，將各種標簽數量下的幀長調整情況補充完整，見表1。

表1 標簽數分組與幀長選擇

3.3 算法流程

改進算法實現流程如圖3所示。首先系統進行初始化，設置初始幀長、初始標簽數。然后閱讀器發送查詢命令，讀取標簽，記錄標簽響應情況：若空閑，則空閑時隙加1；若識別，則成功時隙加1；若碰撞，則碰撞時隙加1。記錄完后，根據碰撞情況，采用標簽估計算法，估計出下一幀待識別的標簽數，并根據幀長與標簽數分組關系確定下一幀的幀長：若未識別標簽數不為零且上一幀碰撞標簽數不為零，則進入下一幀識別；若未識別標簽數不為零且上一幀碰撞標簽數為零，則進入下一周期，重新開始識別。

圖3 改進算法實現流程

4 算法仿真與分析

圖4 改進算法與固定幀算法的系統吞吐率對比

本文采用MATLAB軟件對改進算法進行仿真，并與固定幀時隙ALOHA算法進行系統吞吐率對比，改進算法中標簽數目設置為100，初始幀長設置為16，固定幀時隙ALOHA算法固定幀長設置為32，標簽數為100。仿真結果如圖4所示。從圖4中可以看出，本改進算法的系統吞吐率明顯優于固定幀時隙ALOHA算法，最大系統吞吐率可以達到42.19%，且隨著標簽數的增多，系統的吞吐率能以一定的穩定狀態維持在35%左右，高于固定幀時隙ALOHA算法。

5 結束語

針對幀時隙ALOHA算法系統吞吐率在標簽數達到一定程度后急劇下降的情況，本文對幀時隙ALOHA算法進行了改進，首先通過驗證機制對標簽進行了估計，然后由標簽數與幀長分組關系調整了幀長。改進后，由仿真結果可以看出，系統具有相對穩定的吞吐率且以一定的周期循環，同時系統吞吐率明顯高于幀時隙ALOHA算法，并且算法簡單，成本低。

[1]LU Y,WU Z,GAO Z M.Advanced technologies,embedded and multimedia for human-centric computing[M].Netherlands:Springer,2014:655-661.

[2]王亞青,凌翔,白小波.基于RFID的倉庫管理系統研究[J].物流工程與管理,2015,37(3):37,92-93.WANG Y Q,LING X,BAI X B.Warehouse management system based on RFID [J].Logistics Engineering and Management,2015,37(3):37,92-93.

[3]吳文炤,王瀟,趙鯤鵬,等.基于RFID技術的智慧園區室內定位算法[J].電信科學，2016,32(3):187-191.WU W Z,WANG X,ZHAO K P,et al.Indoor localization algorithm based on RFID technology forsmartpark[J].Telecommunications Science,2016,32(3):187-191.

[4]胡英俊.基于RFID技術的圖書館管理系統研究[J].信息技術,2013(9):176-178.HU Y J.Research on library management system based on RFID technology[J].Information Technology,2013(9):176-178.

[5]周沫.超高頻射頻識別系統標簽檢測性能研究 [D].南京:南京郵電大學,2013.ZHOU M.The research of tag identification performance in UHF RFID system[D].Nanjing:Nanjing University of Posts and Telecommunications,2013.

[6]JIA X,FENG Q,FAN T,et al.RFID technology and its applications in internet of things (IOT)[C]//The 2nd International Conference on Consumer Electronics,Communications and Networks,April 21-23,2012,Yichang,China.New Jersey:IEEE Press,2012:1282-1285.

[7]孟淑玲.射頻識別系統中防沖突算法的研究[D].天津：天津大學,2008.MENG S L.Research on anti-collision algorithm in RFID system[D].Tianjin:Tianjin University,2008

[8]LEE D,CHOI J,LEE W,et al.A time-optimal anti-collision algorithm for FSA based RFID systems[J].Etri Joural,2011,33(3):458-461.

[9]MYUNG J,LEE W,SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti collision[J].IEEE communications Letters,2006,10(3):144-146.

[10]KIM S H,PARK P G.An efficient tree-based tag anti-collision protocol for RFID systems[J].IEEE Transactions on Letters,2007,11(5):449-451.

[11]LAI Y C,LIN C C.A pair resolution blocking algorithm on adaptive binary splitting for RFID systems [J]. IEEE Communications Letters,2008,12(6):432-234.

[12]尹君,何怡剛,李兵.基于分組動態幀時隙的RFID防碰撞算法[J].計算機工程,2009,35(20):267-269.YIN J,HE Y G,LI B.RFID anti-collision algorithm based on grouping dynamic frame slotted[J].Computer Engineering,2009,35(20):267-269.

[13]胡玲敏.RFID系統的防碰撞算法研究[D].杭州:杭州電子科技大學,2011.HU L M.Research on anti-collision algorithm in RFID system[D].Hangzhou:Hangzhou Dianzi University,2011.

[14]單建鋒,陳明,謝建兵.基于ALOHA算法的RFID防碰撞研究[J].南京郵電大學學報(自然科學報),2013,33(1):56-61.SHAN J F,CHEN M,XIE J B.Research on RFID anti-collision technnology based on Aloha algorithm [J].Journal of Nanjing University of Posts and Telecommunications(Natural Science Edition),2013,33(1):56-61.

[15]WANG H,PEI C,SU B.Collision free arbitration protocol for activeRFID systems [J].JournalofCommunicationsand Networks,2012,14(1):34-39.

[16]舒遠仲,田蕾,張麗.基于排隊理論的時隙ALOHA防碰撞算法[J].計算機工程與設計,2013,34(7):2632-2636.SHU Y Z,TIAN L,ZHANG L.Timeslots ALOHA anti-collision algorithm based on queuing theory[J].Computer Engineering and Design,2013,34(7):2632-2636.

[17]SCHOUTE F C.Dynamic frame length ALOHA [J].IEEE Transactions on Communications,1983,31(4):565-568.

[18]栗華.UHF RFID多標簽防碰撞算法的研究與性能分析[D].濟南:山東大學,2011.LI H.Research and performance analysis of UHF RFID multi-tag anti-collision algorithms[D].Jinan:Shandong University,2011.

Improved RFID anti-collision algorithm based on ALOHA

WANG Yong,LI Ting
Nanjing University of Posts and Telecommunications,Nanjing 210023,China

In order to solve the problem of low efficiency of electronic tag identification in RFID system,a new ALOHA anti-collision algorithm was presented.In this algorithm,the coefficients of the tag estimation were automatically changed by using the dynamic adjustment method,which made the number of tag estimation could be dynamic changed with the number of identified tags,then the number of tags to be identified was estimated.And for the frame length adjustment,it could be determined by the relationship between the length of the frame and the tag number according to the estimated number of tags.With the tool of MATLAB,the results show that the proposed algorithm can significantly improve the throughput and stability of the system.

RFID,ALOHA algorithm,throughput,grouping,tag estimation

TP391

A

10.11959/j.issn.1000-0801.2016174

2016-03-30；

2016-06-15

王勇（1961-），男，博士，南京郵電大學教授，主要研究方向為虛擬儀器（VXI），測量與控制技術，各類通信網的監測、監控與管理。

李婷（1991-），女，南京郵電大學碩士生，主要研究方向為精密測試技術與智能儀器。