基于分組動態幀時隙ALOHA防碰撞算法研究

宋瑞玲，高仲合

（曲阜師范大學 計算機科學學院，山東 日照 276826）

0 引言

射頻識別（RFID，Radio Frequency Identification）是一種使用射頻通信實現的非接觸式自動識別技術[1]。根據射頻耦合方式的不同[2]，RFID可以分為電感耦合方式和反向散射耦合方式，根據供電方式的不同，標簽又可以分為主動式標簽和被動式標簽。典型的RFID系統主要由標簽（Tag）、閱讀器（Reader）和天線（Antenna）3部分組成[3]，閱讀器和電子標簽之間信號傳輸是通過閱讀器和電子標簽上的天線耦合來完成的，信息交互通常是采用詢問-問答的方式。目前，RFID技術由于其自身免接觸、識別距離遠、可以同時識別多個運動物體等優點而廣泛應用于多個領域。

電子標簽碰撞問題是指當閱讀器向工作場區內的一組電子標簽發出查詢指令時，有2個或2個以上的電子標簽同時響應閱讀器的查詢，返回信息產生相互干擾，從而導致閱讀器不能正確識別其中任何一個電子標簽的信息，為了解決這個問題，必須采用防碰撞算法。防碰撞算法一般采用時分多址方式，目前采用ALOHA算法和二進制搜索樹型算法來解決讀寫器碰撞[4]。基于ALOHA的算法簡單易行而被廣泛應用。基于ALOHA算法有純ALOHA算法、幀時隙 ALOHA算法、動態幀時隙 ALOHA算法[5]（DFSA，Dynamic Frame Slotted ALOHA Algorithm）分組的動態幀時隙 ALOHA算法[6]。本文介紹的算法是在分組的動態幀時隙 ALOHA算法的基礎上提出來的。

1 多種防碰撞技術

1.1 純ALOHA算法

純ALOHA算法的思想很簡單，即只要有數據待發，就可以發送，向閱讀器發送數據是隨機的，不需要同步，并且沒有檢測機制，雖然實現起來簡單，但是發生碰撞的幾率很大。所以純ALOHA算法的信道利用率不高，吞吐率最大約18.4%。

1.2 時隙ALOHA算法

時隙算法是在純 ALOAH算法的基礎上改進的，時隙ALOHA算法是將時間分為多個離散時隙，標簽只能在時隙的起始發送數據，這種算法必須有全局的時間同步。該算法相比于純ALOHA算法，信道利用率理論上能提高一倍。但是，該算法只是在電子標簽較少時，才能表現出較好的性能，在標簽數增多時系統性能會急劇惡化。系統的吞吐率 S和幀產生率G的關系如圖1所示。

圖1 純ALOHA和時隙的ALOHA算法吞吐率

由圖1可以看到純ALOHA算法當G=0.5時吞吐率S達到最大約是18.4%，時隙ALOHA算法當G=1時吞吐率最大約36.8%。

1.3 幀時隙ALOHA算法

幀時隙ALOHA算法是在時隙ALOHA算法的基礎上提出的，將N個時隙組成一幀，標簽在N個時隙中隨機選擇一個時隙發送信息。幀時隙要求閱讀器和標簽數之間的同步操作，并且每幀的最大時隙數N需要預先設定。讀寫器附近所有標簽服從相同的統計規律，且在同一幀的標簽機會均等，則 r個標簽出現在某個給定時隙概率服從二項分布。

令一幀的時隙數為N，標簽數為n,則有r個標簽發生在某一時隙的概率是:

某個時隙中只有一個標簽發生的概率為:

則所有標簽中被成功讀取的標簽數為:

系統的吞吐率:

對式（4）求導數，得出到:

所以當閱讀器的幀時隙數跟標簽數目相等時，系統吞吐率最大。N的不同取值對應的系統吞吐率如圖2所示。

圖2 不同幀長對應吞吐率

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

由式（5）知幀長和標簽數相等時系統吞吐率最大，但是幀時隙ALOHA算法由于幀長固定會出現標簽數量和幀長不均衡問題，問了解決這個問題，出現了動態幀時隙ALOHA算法，它的思想是根據前一陣的讀取結果動態減少或增加下一幀的時隙數。

有一點值得注意，就是閱讀器設定的幀時隙數是定值[7]，如 1、8、16、32、64、128、256。所以我們經常根據上一輪估算未識讀的標簽數以如下方法來確定下一幀長，如表1所示。

表1 不同標簽個數對應幀長度

2 改進的分組動態幀時隙ALOHA算法

2.1 分組動態幀時隙算法

在動態幀時隙算法中，由于硬件的限制，幀長并不能無限的增大，目前所允許的最大幀長一般不大于256。如果標簽數量增加到遠遠大于256時，由圖2可以看到系統吞吐率明顯在下降。分組動態幀時隙算法思想是先估算未讀標簽的數量[8]，如果標簽數小于256，直接利用動態幀時隙算法使幀長度盡可能的接近標簽數；如果大于256就把要識讀的標簽先分組,每次只識別其中的一組，從而改善標簽過多系統吞吐率下降的問題。

2.2 算法思想

傳統的分組算法，閱讀器把標簽分成若干組，然后一組一組地將標簽識別出來，在每一組中閱讀器必須不斷的調整幀的長度，直到這一組的標簽被全部識別。

本文改進算法的思路:

1）閱讀器估讀待識別的標簽數目N，閱讀器發送包含此標簽數目信息的Detect指令。

2）如果 N>256的話，這里幀長取最大幀長度256，轉到步驟3；否則依據表1確定幀長度，直接響應，然后轉到步驟4。

3）每個標簽從1-N中隨機的選擇一個數字載入時隙計數器，然后數字小于等于256的數字去響應相應的閱讀器時隙，大于256的暫時不響應（可以看成是分成兩組，小于等于256的一組，大于256是一組）。

4）統計該識別周期中一共正確識別的標簽數Nr，用N減去Nr得出未識別的標簽數目（N=N-Nr），如果未識別的標簽數為零，說明全部識別，否則跳到步驟2。

算法流程圖如圖3所示。

圖3 算法流程

2.3 仿真結果

利用Matlab仿真平臺，最大幀長度取得是256，仿真結果如圖4、圖5 所示。圖4記錄標簽在0～1000變化時，改進后的動態幀時隙ALOHA算法所消耗的時隙數，并和動態幀時隙ALOHA算法，分組的動態幀時隙ALOHA算法作了對比。可以看出當標簽數量大時改進后的算法有明顯優勢。圖5仿真了改進后分組動態幀時隙ALOHA算法系統吞吐率，可見在此算法中，系統吞吐率隨標簽數量的增多幾乎不變，一直穩定在36%附近。

圖4 三種算法的性能比較

圖5 改進算法的系統吞吐率

3 結語

傳統的RFID防碰撞算法識讀標簽時需要的時隙數隨標簽數目的增加急速增加，系統吞吐率變低。本文提出的算法通過一種有效的分組方法限制響應標簽數量解決了該問題,當標簽數很大時消耗時隙數相對較少，系統吞吐率也保持在相對穩定的較高值。

[1]王睿,趙龑.RFID技術及應用系統構架的研究[J].通信技術,2009,42(209):116-118.

[2]單承贛,單玉峰,姚磊.射頻識別（RFID）原理與應用[M].北京:電子工業出版社,2008.

[3]李學嬌,賈小愛,趙磊,等.基于后退式索引的動態樹型防碰撞算法[J].通信技術,2009,42(06):118-120.

[4]魏東梅,黃景武,鄒傳云.調頻CMDA的RFID防碰撞算法研究[J].信息安全與通信保密,2011(08):41-43.

[5]張頗,崔喆.RFID系統中一種改進防碰撞算法[J].計算機應用,2008,28(08):2141-2143.

[6]程文青,趙夢欣,徐晶.改進的RFID動態幀時隙ALOHA算法[J].華中科技大學學報,2007,35(06):14-16.

[7]尹君,何恰剛,李兵,等.基于分組動態幀時隙的RFID防碰撞算法[J].計算機工程,2009,35(20):267-269.

[8]單劍鋒,謝建兵,莊琴清.基于分組的動態幀時隙 ALOHA防碰撞算法研究[J].計算機技術與發展,2011,21(11):40-41.