孫 笠

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

一種改進(jìn)的RFID防碰撞時(shí)隙ALOHA算法

孫 笠

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

引言

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

1.防沖撞算法介紹

1.1 ALOHA算法

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

1.2 幀時(shí)隙ALOHA

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

1.3 動(dòng)態(tài)幀時(shí)隙ALOHA算法

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

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

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

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

2.改進(jìn)的算法

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

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

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

當(dāng)我們要想獲得最大效率時(shí)，使得：

根據(jù)上式可推出當(dāng)幀的長度為N時(shí)，效率最高的標(biāo)簽響應(yīng)數(shù)為：

當(dāng)標(biāo)簽數(shù)為n時(shí)，幀長度的最佳值為：

當(dāng)n很大時(shí)，將上式泰勒爾展開：

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

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

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

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

表1 未識別標(biāo)簽個(gè)數(shù)對應(yīng)的幀長度和分組情況

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

3 仿真結(jié)果分析

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

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