基于黃金分割的動態(tài)幀時隙ALOHA防碰撞算法

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

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

基于黃金分割的動態(tài)幀時隙ALOHA防碰撞算法

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

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

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

射頻識別；防碰撞算法；動態(tài)幀時隙；黃金分割法

0 引言

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

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

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

1 Aloha類算法簡介

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

1.1 純ALOHA算法（PA）

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

1.2 時隙ALOHA算法（SA）

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

1.3 幀時隙ALOHA算法（FSA）

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

1.4 動態(tài)幀時隙ALOHA算法（DFSA）

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

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

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

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

某時隙內(nèi)含有n個標簽的期望值為

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

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

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

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

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

2.1 標簽數(shù)目的估計方法

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

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

每一幀識別完成后，沖突時隙內(nèi)的標簽會在下一幀識別時響應，所以剩余的標簽數(shù)由沖突時隙數(shù)決定，這里假定剩余標簽數(shù)與沖突標簽數(shù)存在某一線性關系，系數(shù)k不是固定不變的，可以根據(jù)時隙的碰撞情況做適當?shù)恼{(diào)整．

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

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

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

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

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

2.2 時隙調(diào)整方法

2.2.1 黃金分割法

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

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

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

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

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

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

2.2.2 黃金分割法時隙調(diào)整

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

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

2.2.3 算法流程

算法基本過程如下：

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

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

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

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

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

6）判斷標簽數(shù)N是否為0，不為0則轉(zhuǎn)到第2）步繼續(xù)識別，直到所有標簽都被識別完結(jié)束．

主要流程圖如圖5所示．

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

3 算法的仿真及結(jié)果分析

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

[1]寧煥生．RFID重大工程與國家物聯(lián)網(wǎng)[M]．北京：機械工業(yè)出版社，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]郭志濤，程林林，周艷聰，等．動態(tài)幀時隙ALOHA算法的改進[J]．計算機應用研究，2012，29（3）：907-909．

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

[5]周朝陽．射頻識別系統(tǒng)沖突防范算法[J]．計算機系統(tǒng)應用，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動態(tài)幀時隙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動態(tài)幀時隙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]楊永發(fā)．概率論與數(shù)理統(tǒng)計教程[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）；河北省高等學?？茖W技術研究項目（ZD20131097）

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

數(shù)字出版日期：2015-06-17數(shù)字出版網(wǎng)址：http://www.cnki.net/kcms/detail/13.1208.T.20150617.1538.004.html