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

馬翠紅，趙 躍，楊友良，孟凡偉

(河北聯(lián)合大學(xué)，河北唐山063009)

0 引言

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

1 防沖撞算法介紹

1.1 Aloha算法

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

圖1 FSA算法的信息幀時(shí)分多址

1.2 幀時(shí)隙ALOHA

幀時(shí)隙ALOHA(Framed Slotted ALOHA，F(xiàn)SA)算法是一種隨機(jī)時(shí)分多址方式的用戶信息通信收發(fā)算法。FSA算法的信息幀時(shí)分多址如圖1所示。

該算法將信道用信息幀表示，其中，幀是指由閱讀器要求的包含若干時(shí)隙的時(shí)間間隔。信息幀可以分成多個(gè)時(shí)隙，其中，時(shí)隙是指標(biāo)簽發(fā)送自身標(biāo)識(shí)的時(shí)間長(zhǎng)度。當(dāng)一個(gè)時(shí)隙只被一個(gè)標(biāo)簽占有時(shí)，閱讀器才會(huì)正確識(shí)別該標(biāo)簽，而當(dāng)一個(gè)時(shí)隙內(nèi)有2個(gè)或2個(gè)以上標(biāo)簽時(shí)，會(huì)發(fā)生碰撞，讀寫器無法正確識(shí)別，若時(shí)隙為空則跳過。如此循環(huán)，至到所有的標(biāo)簽都被識(shí)別。幀的大小是固定的，所以如果在某一時(shí)刻標(biāo)簽的個(gè)數(shù)遠(yuǎn)大于幀中時(shí)隙的個(gè)數(shù)，則在一個(gè)幀中發(fā)生碰撞的幾率將被提高，被浪費(fèi)的時(shí)隙也將增多，從而延長(zhǎng)了識(shí)別所有標(biāo)簽的時(shí)間。［1-2］

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

為使系統(tǒng)效率最優(yōu)，提出動(dòng)態(tài)幀時(shí)隙ALOHA(Dynamic Framed Slotted ALOHA，DFSA)算法，使得幀時(shí)隙數(shù)等于參與循環(huán)的標(biāo)簽數(shù)。DFSA每幀時(shí)隙數(shù)可以根據(jù)標(biāo)簽數(shù)的變化及時(shí)調(diào)整，使得標(biāo)簽數(shù)量與幀時(shí)隙數(shù)匹配。在開始新一個(gè)幀循環(huán)時(shí)，讀寫器要對(duì)參與幀循環(huán)的標(biāo)簽數(shù)進(jìn)行估計(jì)，這個(gè)過程在整個(gè)算法中發(fā)揮著重要的作用。如果所估計(jì)的標(biāo)簽數(shù)與實(shí)際情況相差甚遠(yuǎn)，那么算法的效率就會(huì)發(fā)生大幅的下降，這樣就影響了系統(tǒng)的穩(wěn)定性。

目前，主要有以下三種估計(jì)標(biāo)簽數(shù)的方法。

第一種是利用切比雪夫不等式估計(jì)標(biāo)簽數(shù)目。

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

A：我生孩子的時(shí)候是在國(guó)內(nèi)生的。因?yàn)轫槷a(chǎn)，我在醫(yī)院住了三天就出院了，當(dāng)時(shí)生孩子的時(shí)候是5月份，但是天氣已經(jīng)很熱了，所以家里一直保持著恒溫24攝氏度。我并沒有坐月子，孩子也在出生7天左右就帶他出門曬太陽了。很多國(guó)外媽媽生產(chǎn)后一周就上班了，他們沒有坐月子一說。

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

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

2 改進(jìn)的算法

分組動(dòng)態(tài)幀時(shí)隙的ALOHA算法是在DFSA算法的基礎(chǔ)上提出的，針對(duì)大規(guī)模標(biāo)簽進(jìn)行快速識(shí)別的一種改進(jìn)型算法。此算法很好地改善了標(biāo)簽識(shí)讀效率問題，即使有大量標(biāo)簽同時(shí)存在，該算法也能線性地增加請(qǐng)求時(shí)間來識(shí)讀標(biāo)簽。

2.1 算法分析及數(shù)學(xué)模型

在幀時(shí)隙ALOHA算法中，隨著標(biāo)簽個(gè)數(shù)的增加，系統(tǒng)的吞吐率呈下降趨勢(shì)。假設(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ù)的期望值為:

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

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

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

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

圖2 標(biāo)簽數(shù)目與吞吐率的關(guān)系

以上推導(dǎo)證明:當(dāng)待識(shí)別標(biāo)簽數(shù)與幀長(zhǎng)度基本相當(dāng)時(shí)，系統(tǒng)吞吐率最大，即一個(gè)幀長(zhǎng)度識(shí)別周期中能夠成功識(shí)別的標(biāo)簽數(shù)最多。圖2給出了L取不同值時(shí)系統(tǒng)效率的仿真結(jié)果。

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

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

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

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

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

3 仿真結(jié)果分析

仿真實(shí)驗(yàn)采用Matlab 7平臺(tái)，記錄標(biāo)簽數(shù)從0到1 000遞增變化時(shí)的系統(tǒng)效率和讀取標(biāo)簽所花時(shí)間(用讀取標(biāo)簽所用的總時(shí)隙數(shù)來衡量)，對(duì)改進(jìn)算法、動(dòng)態(tài)幀時(shí)隙ALOHA算法、固定幀時(shí)隙的ALOHA算法三者進(jìn)行比較。初始時(shí)，動(dòng)態(tài)幀時(shí)隙ALOHA和改進(jìn)算法幀長(zhǎng)度都是8，而固定幀時(shí)隙ALOHA的幀長(zhǎng)度即為允許的最大幀長(zhǎng)256.從圖3可見，改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA算法在標(biāo)簽數(shù)量大于500時(shí)，仍能以35%上下的吞吐量工作，而固定時(shí)隙的ALOHA算法性能則急劇惡化.在圖4中，固定幀時(shí)隙的ALOHA算法需要最多時(shí)間;改進(jìn)算法需要最少的時(shí)間，在大量標(biāo)簽的情況下，具有明顯的優(yōu)勢(shì)，當(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)勢(shì)。

圖3 標(biāo)簽數(shù)目與系統(tǒng)效率的關(guān)系

圖4 標(biāo)簽數(shù)目與時(shí)隙數(shù)的關(guān)系

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

［1］ Finkenzeller K.射頻識(shí)別技術(shù)［M］.3版.吳曉峰，陳大才，譯.北京:電子工業(yè)出版社，2006.

［2］ 陸端，等.改進(jìn)ALOHA算法在RFID多目標(biāo)識(shí)別中的應(yīng)用［J］.微計(jì)算機(jī)信息，2006，22(11).

［3］ 徐圓圓，劉禹.基于Aloha算法的幀長(zhǎng)及分組數(shù)改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用，2008，28(3):588－590.

［4］ Vogt H.Multiple object identification with passive RFID tags［M］.IEEE International Conference on Systems，Man and Cybernet－ics.Tunisia: IEEE Press，2002.

［5］ LEE SR，JOO SD，LEE CW.An enhanced dynamicframed slotted ALOHA algorithm for RFID tagidentification.IEEE Computer Society，2005［C］.