基于黃金分割的動態幀時隙ALOHA防碰撞算法

董永峰，周艷聰，張晶，張素琪

（1.河北工業大學計算機科學與軟件學院，天津 300401；2.天津商業大學信息工程學院，天津 300134）

基于黃金分割的動態幀時隙ALOHA防碰撞算法

董永峰1，周艷聰2，張晶1，張素琪2

（1.河北工業大學計算機科學與軟件學院，天津 300401；2.天津商業大學信息工程學院，天津 300134）

為了提高射頻識別（RFID）系統中標簽的識別效率，本文對基于ALOHA的概率性防碰撞算法進行了詳細的分析，提出了一種基于黃金分割的動態幀時隙ALOHA防碰撞算法．標簽估計中，選取動態調整機制來自動調整標簽估計式中的系數，使得標簽估計個數隨著標簽數動態變化；下一查詢周期幀時隙長度調整中，根據標簽到達的概率分布特點并結合黃金分割法思想，通過設置閾值條件來動態優化幀長度．MATLAB仿真結果表明，該算法能夠減少空時隙的數量，有效的提高了系統的識別效率和時隙利用率．

射頻識別；防碰撞算法；動態幀時隙；黃金分割法

0 引言

隨著科學技術的不斷提高，物聯網技術得到了全面快速的發展與應用，射頻識別（radio frequency identification，RFID）技術作為其關鍵技術之一，已廣泛應用于交通、運輸、工業、服務業等各種信息化系統．目前影響RFID識別技術的關鍵因素是標簽的碰撞、沖突問題，這在很大程度上降低了系統對標簽成功識別的效率，也成為眾多科研人員致力研究的問題．

所謂標簽碰撞問題，即在閱讀器識別范圍內，當有兩個或多個標簽同時響應閱讀器并發送數據時，在通信信道內產生的數據信息間的沖突[1]．目前解決RFID中標簽防碰撞問題主要是基于ALOHA的防碰撞算法和基于二進制樹的防碰撞算法．基于二進制樹的搜索確定性算法是以標簽的ID號為基礎來防止碰撞發生的[2]，根據標簽的ID號劃分成0組和1組，以此逐步縮小每組內標簽的個數直到最終完成對所有標簽的識別．此類算法可以識別完全部標簽而不會產生漏讀現象，系統的效率可以達到最大值0.43，但相對復雜度較高，識別時間較長，應用較少．基于ALOHA的隨機性防碰撞算法基本思想是當閱讀器檢測到有碰撞時，令標簽隨機的延遲一段時間再響應閱讀器，其中動態幀時隙ALOHA算法是最常見的算法．它將時間劃分成多個幀，每幀內又分成多個時隙，幀長度可以根據標簽數量動態變化，大大提高了標簽識別效率，減少了時隙內標簽的碰撞，縮短了識別時間．為了提高識別效率，文獻[3]采用構造哈希函數的方法對標簽進行時隙分配，使其在時隙內分布最優；文獻[4]采用二分查找的方法，根據時隙內標簽識別情況來動態的增加或減少時隙數，以減少時隙的浪費和碰撞時隙數的增加．文獻[5]中采用FibonacciNumber數列實現幀長度的動態調整，實現了標簽的高效識別．

本文在研究了動態幀時隙ALOHA算法幀長調整不靈活的缺點后，提出了一種新的幀長度調整方法．算法中，采用動態調整機制，根據每次估計的標簽數,動態調整標簽估計式中的系數，使其與實際標簽數更接近；當有碰撞發生時，根據閾值條件和當前碰撞情況，采用黃金分割法動態調整下一幀需要的幀長度．仿真結果表明，所提出的算法在系統識別效率和時隙利用率方面都有明顯的改善．

1 Aloha類算法簡介

Aloha算法是一種基于時分機制（TDMA）的概率性防碰撞算法，最初用來解決通信系統中數據信息的堵塞問題，現已廣泛應用于解決RFID系統中標簽碰撞問題，主要包括以下幾種：純ALOHA算法、時隙ALOHA算法、幀時隙ALOHA算法、動態幀時隙ALOHA算法等[6-10]．

1.1 純ALOHA算法（PA）

PA算法是最基本的ALOHA算法，當閱讀器檢測到有信息沖突時會令標簽延遲一段時間再次發送，由于延遲的時間是隨機的，所以信息傳輸過程中可能會出現部分沖突的情況，并且系統效率最大只能達到18.4%．

1.2 時隙ALOHA算法（SA）

SA算法是將PA算法的時間分成多個時間段（時隙），標簽選擇某一時隙的起始處發送信息．由于減少了部分沖突的情況，沖突周期由原來的2T減少為T，即系統吞吐率由S=G*e-2G變成S=G*e-G，所以信道的吞吐率提高了一倍，最大約達到36.8%，如圖1所示，但在標簽量比較大時，系統的信道利用率仍不是很理想，而且系統中還需要有同步時鐘來確保所有標簽達到時隙同步．

1.3 幀時隙ALOHA算法（FSA）

FSA算法是將SA算法中的時隙組成幀，標簽在某幀內選擇時隙發送信息，當時隙內有碰撞時標簽會等待該幀識別結束后再在下一幀響應閱讀器．對于FSA算法來說，每幀中包含的時隙數是固定不變的，它不隨閱讀器范圍內標簽數量的變化而變化．但當標簽數變化時，不同的幀長度取得的系統效率是不同的，如圖2所示．當標簽數目遠小于幀時隙數時，需要的時隙數比較少而空閑的時隙會比較多，造成時隙嚴重浪費，系統的效率也較低；當標簽數目遠大于幀時隙數時，當前的幀長度不滿足當前標簽數目的需要，造成時隙內標簽碰撞的幾率增大．

1.4 動態幀時隙ALOHA算法（DFSA）

圖1 PA和SA吞吐率對比關系圖Fig.1The throughput comparison of PA and SA

圖2 FSA算法不同幀長對應的系統吞吐率Fig.2The system throughput of FSA algorithm corresponding to different frame length

DFSA算法改進了FSA算法中幀時隙數固定不變的缺點，當一幀識別結束后，閱讀器根據上一幀時隙中的碰撞情況來估計下一幀中未識別的標簽數量，然后調整合理的幀長度作為一下幀的開始，從而解決了時隙浪費的問題，大大提高了信道的吞吐率．

假設閱讀器定義的幀長度為L，識別范圍內的標簽數目為N，n個標簽選擇某一時隙i的概率服從二項分布，即

某時隙內含有n個標簽的期望值為

那么，一幀內成功識別的時隙數S1、空閑時隙數S0、碰撞時隙數Sc的期望值分別為：

系統吞吐率定義為：一次查詢周期內，成功識別的時隙數占總時隙數的比值，由式(3)可得系統吞吐率為

由此可以看出，想要提高DFSA算法的識別效率，如何估算初始標簽數量以及合理的調整最適幀長度成為動態幀時隙ALOHA算法的關鍵．

2 基于黃金分割的DFSA防碰撞算法

目前對動態幀時隙ALOHA算法的研究主要在標簽數目估計和幀時隙數的調整方面，常用的標簽估計算法主要有Schoute，Vogt，e-pc，Lower Bound，C-ratio，偽貝葉斯估計[11-12]等．在這些算法中，每幀識別完成后都會統計時隙內標簽的碰撞情況，如成功識別時隙數S1、碰撞時隙數Sc和空閑時隙數S0，下一幀根據上一幀的統計情況估計此時剩余的未被識別的標簽數量，然后確定一個適當的幀長度來識別這些標簽，以此類推，直到所有標簽都被識別完．但他們都忽略了一個問題是，以上算法只是單純的根據此幀的碰撞情況估計下一幀未識別標簽數，而沒有對這個估計結果進行驗證．此外，在實際應用當中，當幀長度等于標簽數目時并沒有像期望的那樣得到最大的吞吐率，此時時隙內標簽的沖突比較頻繁[13]．因此，應對DFSA算法進行更深入的研究分析，優化幀長度以達到更好的效果．

2.1 標簽數目的估計方法

本文提出的估計方法中，通過當前幀的碰撞情況估計下一幀待識別的標簽數，下一幀識別結束后，根據已有的估計方法，對此幀內的所有標簽數進行估計，然后與上一幀估計出的結果進行比較，最后根據比較的誤差調整上一幀估計式中的系數，從而使2次估計值相接近，估計更準確．

第i次查詢結束后，閱讀器統計成功識別時隙數S1(i)、碰撞時隙數Sc(i)和空時隙數S0(i),假設下一次查詢閱讀器應讀取的標簽數與碰撞時隙數存在某一線性關系，如式(7)所示．

每一幀識別完成后，沖突時隙內的標簽會在下一幀識別時響應，所以剩余的標簽數由沖突時隙數決定，這里假定剩余標簽數與沖突標簽數存在某一線性關系，系數k不是固定不變的，可以根據時隙的碰撞情況做適當的調整．

第i+1次查詢結束后，采用Bin ZHEN在文獻[14]中提出的標簽估計方法（DFSAZ）對本次查詢內的總標簽數進行估計，如式(8)所示．

要使兩次查詢結果的誤差最小，即n1i+1=n2i+1，將(8)式帶入(7)式，求得k的值為

由于第1次查詢時需要第2次查詢結果出來才能計算出k值，這是不現實的，所以對上式進行改進為

將(10)式帶入(7)式得到下一次查詢待識別的標簽數目的估計值，為

這就是下一次識別的動態標簽個數估計方程，其中k為一可變系數，取決于本次的碰撞情況和上次的碰撞的情況，F為開始識別時設置的初始時隙數．

2.2 時隙調整方法

2.2.1 黃金分割法

黃金分割法的數學定義是采用黃金值求解函數最大（小）值的一種數值搜索方法．對于區間[0，1]，將其分成長度分別為r和1 r的兩部分（其中r＞1 r），當1/r=r/1 r時，求得位于區間[0,1]的根為5 1/2，其近似值就是黃金比值0.618．如圖3所示．

黃金分割是1種數學上的比例關系，在很多科學實驗中，選取方案常用1種0.618法，即優選法，它可以使我們合理地安排較少的試驗次數找到合適的條件，在建筑、文學、工農業生產和科學實驗中有著廣泛而重要的應用．

對于泊松分布，其數學定義為：如果稀有事件A在每個單元（設想為n次實驗）內平均出現次，那么在一個單元（n次）的試驗中，稀有事件A出現次數x的概率分布服從Poisson分布[15]．由此可知，標簽隨機進入閱讀器讀寫范圍內的概率分布符合泊松分布的特點．泊松分布曲線圖如圖4所示．根據泊松分布圖中上升階段和下降階段幅度均為單調的增加或減少的特點，對于標簽而言即單位時間內，標簽數量增加或減少比較快．所以根據這一特點對其斜率進行模擬，可以更好的預測下一次標簽識別需要的時隙數，減少標簽傳輸過程中的碰撞概率．

圖3 線段上的黃金比值Fig.3The golden ratio on a segment

圖4 泊松分布曲線圖Fig.4The curve of Poisson distribution

通過對泊松分布特點的分析可知，精確計算泊松分布的斜率是比較復雜的，為了減少標簽沖突，提高識別率，我們采用黃金分割法即黃金比值（0.618）來求得斜率的近似值．有的采用了二分查找的方法即兩邊取中的策略，近似模擬其斜率，也有的通過分析沖突因子和沖突時隙的關系來擬合其曲線來減少沖突．

2.2.2 黃金分割法時隙調整

本文通過黃金分割法動態的調整幀內時隙數以達到最佳，避免因時隙的過多或過少而引起的系統效率的降低．通過對標簽到達閱讀器的概率分布可得，調整最佳時隙數是本文的核心部分，其中，通過判斷每幀標簽的沖突情況來動態的調整時隙數．基于二分法的DFSA算法中，時隙長度的調整是在幀內，每識別完一個時隙即根據當前時隙的狀態進行相應的增加或減少時隙數，這樣可以很好的實現幀長度的調整，但是工作量很大，耗時也較長．本文提出一種簡單的幀長度調整方案．

當一幀識別結束后，首先通過此幀的碰撞情況計算下一幀的最大時隙數，根據上述標簽估計算法估計出的下一幀待識別的標簽數，則下一幀最大幀長即為此時的待識別標簽數．

2.2.3 算法流程

算法基本過程如下：

1）初始化預處理，設置初始標簽數N，初始時隙數F，同時將幀長計數器SlotCounter初始化為F，清零碰撞計數器Sc、成功識別計數器S1和空時隙計數器S0．閱讀器發送查詢命令等待標簽回復．

2）標簽收到閱讀器的查詢命令后，隨機的選取[0-F]中的一個數，并存入時隙計數器內．

3）閱讀器依次查詢每個時隙，根據標簽的響應信息記錄碰撞情況：如果時隙內有一個標簽響應，則S1+ +，如果時隙內沒有標簽響應則S0++，如果時隙內有多個標簽（2）響應，則Sc++．

4）根據碰撞情況，采用標簽估計法，估計下一幀剩余標簽數，并初始化下一幀最大幀長Fmax．

5）計算Sc/F，若Sc/f＜0.51，令幀長F等于估計的標簽數；若Sc/Fslot，表示發生碰撞的情況較多，則進行黃金比例調整下一幀時隙數．

6）判斷標簽數N是否為0，不為0則轉到第2）步繼續識別，直到所有標簽都被識別完結束．

主要流程圖如圖5所示．

圖5 基于黃金分割的動態幀時隙ALOHA算法流程圖Fig.5The flow chart of dynamic framed slotted tag anti-collision algorithm based on golden section

3 算法的仿真及結果分析

為了驗證改進算法的性能優勢，本實驗采用MATLAB軟件進行程序編寫，在Windows7平臺和2G內存環境下運行，標簽最大數目設置為100，初始幀長度設為16，在相同條件下運行100次，對仿真實驗結果取平均．本實驗中，DFSA算法的標簽估計采用DFSAZ估計法，FPDFSA算法為文獻[13]提出的1種改進的DFSA方法．圖6～圖9為基于MATLAB軟件對本文算法、DFSA算法和FPDFSA算法進行的仿真，分別在系統效率、時隙利用率、總時隙數、空時隙數方面進行比較分析．

首先定義兩個性能參數：系統效率和時隙利用率．系統效率是指在一個識別周期內，成功識別的標簽數與所需的總的時隙數的比值；時隙利用率是指在一個識別周期內，成功識別的時隙與碰撞時隙的和與總的時隙數的比值，主要反應時隙內空時隙出現的情況．

隨著標簽數的增加，3種算法在系統效率方面的比較情況如圖6所示．從圖中可以看出，本算法的系統效率明顯優于DFSA算法，最大系統效率可以達到0.4，隨著標簽數的增加，系統效率維持在0.35左右，高于DFSA算法的0.3左右．與FPDFSA算法相比較，在標簽數量較少時本文算法可以取得很好的系統效率，隨著標簽數增加這種優勢逐漸減弱．

隨著標簽數的增加，3種算法在時隙利用率方面的比較情況如圖7所示．從圖中可以看出，本算法與DFSA算法相比有較高的時隙利用率，與FPDFSA算法相比，當標簽數較多時，本算法體現出了很好的時隙利用率，標簽數少時優勢減少．

圖63 種算法系統效率比較Fig.6The comparison on system efficiency about these three algorithms

圖73 種算法時隙利用率比較Fig.7The comparison on the slot utilization about these three algorithms

隨著標簽數的增加，3種算法在所需空時隙數方面的比較情況如圖8所示．從圖中可以看出，本算法所需空時隙數明顯少于DFSA算法，與FPDFSA算法相比，在標簽數少時沒有多大變化，當標簽數多時所需的空時隙數量快速減少．

隨著標簽數的增加，3種算法在所需總時隙數方面的比較情況如圖9所示．從圖中可以看出，本算法所需總的時隙數少于DFSA算法，但與FPDFSA算法相比，雖然在標簽數目較多時減少了空時隙的數量，但所需的總時隙數目相差不大，當標簽數少時幾乎與FPDFSA一樣，當標簽數多時略低于FPDFSA算法．這主要是因為標簽數的增多加大了時隙的碰撞概率，此方面仍需要做進一步的改進．綜上所述，本文算法在系統效率和時隙利用率上都有明顯的改善，并且算法簡單，可操作性強．

4 結論

防碰撞算法是提高RFID系統識別效率的關鍵．標簽估計和幀長度調整方法是動態幀時隙ALOHA算法中改進的主要方面，本文通過對黃金分割法和泊松分布的研究與分析，將其應用到DFSA算法中，采用動態方法估計未識別標簽數量，根據設置閾值條件來判斷如何進行幀長度的黃金分割調整．通過MATLAB軟件的仿真比較，在標簽數量較少時，算法的系統效率明顯高于常用的動態幀時隙ALOHA算法；同時，該算法在時隙利用率以及減少空時隙數方面都有明顯的改善，并且算法簡單、可操作性強．

圖83 種算法空時隙數比較Fig.8The comparison on empty slot number about these three algorithms

圖93 種算法所需總時隙數比較Fig.9The comparison on the required total time slot number about these three algorithms

[1]寧煥生．RFID重大工程與國家物聯網[M]．北京：機械工業出版社，2011．

[2]Chennai，Tamil Nadu．Analysis of bit grouping algorithm for collision resolution in passive RFID tags[J]．International Journal of Engineering Science and Technology，2010，2（9）：4192-4240．

[3]郭志濤，程林林，周艷聰，等．動態幀時隙ALOHA算法的改進[J]．計算機應用研究，2012，29（3）：907-909．

[4]郭志濤，李瑋瑋，等．基于二分查找的動態幀時隙標簽防沖突算法[J]．計算機應用研究，2012，29（11）：4287-4289．

[5]周朝陽．射頻識別系統沖突防范算法[J]．計算機系統應用，2013，22（10）：132-135．

[6]Eom Jun-Bong，Lee Tae-Jin．Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J]．IEEE Communication Letters，2010，14（1）：60-62．

[7]吳海峰，曾玉．RFID動態幀時隙ALOHA防沖突中的標簽估計和幀長確定[J]．自動化學報，2010，36（4）：621-624．

[8]EomJ B，Lee T J，RietmanR，et al．Anefficient framed-slot-tedALOHA algorithm withpilot frame andbinary selection for anti-collisionof RFID tags[J]．IEEE Communication Letters，2008，12（11）：861-863．

[9]Eom J B，Lee T J．Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J]．IEEE Communication Letters，2010，14（1）：60-62．

[10]Okkyeong Bang，Sunghyun Kim，Hyuckjae Lee．Identification of RFID tags in dynamic framed slotted Aloha[C]//Advanced Communication Technology of ICACT 11th International Conference．2009，1：354-357．

[11]孫文勝，金成敏．新型的RFID動態幀時隙ALOHA防碰撞算法[J]．信息與控制，2012，41（2）：233-237．

[12]Lin Chun-Fu，Lin Frank Yeong-Sung．Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted ALOHA in RFID networks[J]．IEEE Transactions on Automation Science and Engineering，2010，7（4）：840-848．

[13]栗華．UHFRFID多標簽防碰撞算法的研究與性能分析[D]．濟南：山東大學，2011．

[14]BinZhen，Mamoru KOBAYASHI，Masashi SHIMIZU．Framed Aloha for multiple RFID objects identification[J]．IEICE Transactions on Communications，2005，E88-B：991-999．

[15]楊永發．概率論與數理統計教程[M]．天津：南開大學出版社，2009．

[責任編輯 田豐夏紅梅]

Dynamic framed slotted tag anti-collision algorithm based on golden section

DONG Yongfeng1，ZHOU Yancong2，ZHANG Jing1，ZHANG Suqi2

(1.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;2.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China)

In order to improve the efficiency of tag identification in RFID（Radio Frequency Identification）system，the probabilistic collision algorithm based on the ALOHA has been analyzed in detail.A dynamic frame slot ALOHA anticollision algorithm based on the golden section was proposed.In tag estimation,the coefficients in tag estimation are adjusted automatically so that the estimated number of tags changes dynamically with the tags number.In next polling cycle,frame slot length is adjusted based on the probability distribution of the tag.And combined with golden section method of thought,the threshold conditions are set to dynamically optimize the frame length.Matlab simulation results show that the algorithm can reduce the number of empty slots and improve the recognition and slot utilization efficiency of system.

radio frequency identification;anti-collision algorithm;dynamic framed;slotted;golden section method

TP391.44

A

1007-2373(2015)03-0053-07

10.14081/j.cnki.hgdxb.2015.03.011

2015-02-17

天津市應用基礎與前沿技術研究計劃（14JCYBJC15900）；河北省高等學校科學技術研究項目（ZD20131097）

董永峰（1977-），男（漢族），副教授，博士．

數字出版日期：2015-06-17數字出版網址：http://www.cnki.net/kcms/detail/13.1208.T.20150617.1538.004.html