孫 笠

（北京郵電大學國際學院物聯(lián)網(wǎng)工程 北京 100876）

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

孫 笠

（北京郵電大學國際學院物聯(lián)網(wǎng)工程 北京 100876）

引言

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

1.防沖撞算法介紹

1.1 ALOHA算法

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

1.2 幀時隙ALOHA

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

1.3 動態(tài)幀時隙ALOHA算法

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

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

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

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

2.改進的算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

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