一種改進的RFID防碰撞時隙ALOHA算法

孫 笠

（北京郵電大學國際學院物聯網工程 北京 100876）

一種改進的RFID防碰撞時隙ALOHA算法

孫 笠

（北京郵電大學國際學院物聯網工程 北京 100876）

引言

目前有多種防碰撞算法，主要分為ALOHA算法和樹形分解算法。由于樹形分解法有時會使某些標簽的識別延遲可能比較長，所以ALOHA算法因具有簡單易實現等優點而成為應用最廣的算法之一。文中將對ALOHA算法進行詳細研究，并針對如何降低識別沖突標簽時延和減少標簽碰撞次數方面進行改進，從而提高識別效率。

1.防沖撞算法介紹

1.1 ALOHA算法

在ALOHA算法中當標簽進入讀寫器范圍時，電子標簽自動地向讀寫器廣播自己的ID(即唯一標識自身的數據，一般情況下為定長)，在發送數據時如果有其他的標簽也在發送數據，那么將會發生信號沖突，讀寫器將不能正確地識別標簽的ID號。讀寫器在檢查到信號沖突時，將發送一個停止發送信號的命令讓所有標簽停止當前發送并隨機等待一個時間后再發送自己信息。純ALOHA算法較簡單、易實現，但標簽之間發生信號沖突的概率很大，系統的識別率較低。

1.2 幀時隙ALOHA

幀時隙ALOHA(Framed Slotted ALOHA,FSA)算法是一種隨機時分多址方式的用戶信息通信收發算法。

1.3 動態幀時隙ALOHA算法

目前，主要有以下三種估計標簽數的方法。第一種是利用切比雪夫不等式估計標簽數目。

第二種方法是基于時隙二項分布來估計標簽數。假設N代表當前幀的長度，n表示標簽數。標簽選擇各個時隙數是等概率的，同一個時隙內出現r個標簽的概率，根據二項分布原理得：

第三種方法是在發生沖突時，一個時隙中至少有兩個標簽發生碰撞。標簽的估計函數為：

N代表當前幀的長度，c0表示空閑時隙，c1表示成功時隙，ck表示碰撞時隙數。當沖突較頻繁時，這種估計方法的相對估計誤差較大，但具有方法簡單等優點[3-4]。

2.改進的算法

在幀時隙ALOHA算法中，隨著標簽個數的增加，系統的吞吐率呈下降趨勢。假設時隙數N，標簽總數為n，根據統計學的原理，有r個標簽選擇1個時隙的概率為：

當r=1時，表示一個時隙只有一個標簽，即成功讀取的時隙。因此，在一個閱讀周期中讀取標簽數的期望值為：

其中，aN,n 1表示只有一個標簽占據一個時隙的時隙總數。其中幀長度為N，標簽總數為n。系統效率為PN：

當我們要想獲得最大效率時，使得：

根據上式可推出當幀的長度為N時，效率最高的標簽響應數為：

當標簽數為n時，幀長度的最佳值為：

當n很大時，將上式泰勒爾展開：

以上推導證明：當待識別標簽數與幀長度基本相當時，系統吞吐率最大，即一個幀長度識別周期中能夠成功識別的標簽數最多。

另一方面，讀寫器能設定的時隙數通常是定值，如1，8，16，32，64，128，256。因此，讀寫器根據上一輪識別過程結束后，剩余未識別標簽個數中選擇1個數作為下一幀的長度，具體選擇標準：當碰撞的時隙數高于70%的總時隙數時，下一幀長度加倍；當空時隙數高于30%的總時隙數時，下一幀長度減半；當到來的標簽數n急劇增加，而一幀的時隙數不可能無限增加時，用下式將標簽分成M組，只允許一組標簽相應請求命令，以使系統仍能工作在最大吞吐量下。

式中，Nmax為讀寫器能分配的最大時隙，這里取256。

表1顯示了未識別標簽個數與最佳幀長下分組的個數的關系。

表1 未識別標簽個數對應的幀長度和分組情況

文中介紹了三種標簽的估算方法，為減小RFID系統的復雜性，使用n=c1+2ck估計函數來確定標簽數量。得到n值后，由式(11)計算出M值，若M=0，則對標簽進行分組；若M≠0，則不分組。

3 仿真結果分析

仿真實驗采用Matlab 7平臺，記錄標簽數從0到1000遞增變化時的系統效率和讀取標簽所花時間(用讀取標簽所用的總時隙數來衡量)，對改進算法、動態幀時隙ALOHA算法、固定幀時隙的ALOHA算法三者進行比較。初始時，動態幀時隙ALOHA和改進算法幀長度都是8，而固定幀時隙ALOHA的幀長度即為允許的最大幀長256。改進的動態幀時隙ALOHA算法在標簽數量大于500時，仍能以35%上下的吞吐量工作，而固定時隙的ALOHA算法性能則急劇惡化。固定幀時隙的ALOHA算法需要最多時間；改進算法需要最少的時間，在大量標簽的情況下，具有明顯的優勢，當標簽數量增加到1000左右時，所用時間與前者相比幾乎減少了一半；動態幀時隙的ALOHA算法在標簽數量較少時(小于500)，性能與改進算法接近，但是在標簽總數超過500以后，所需的時隙數大量增加，幾乎沒有時間上的優勢。

仿真結果顯示改進算法在標簽數量很大時，吞吐量可提高100%，標簽讀取時間下降近50%。因此，這種算法對于短時間需要讀取大量標簽的實時RFID系統具有良好的適用性。