摘 要：把RFID電子標簽附著在目標物體上，利用RFID閱讀器讀取電子標簽的信息可以實現(xiàn)物體位置的確定。但是多個標簽同時向閱讀器發(fā)送信號時，就會發(fā)生碰撞，因此，在RFID系統(tǒng)中加入標簽防碰撞算法，使閱讀器正確、高效地讀取標簽信息尤為重要。本文介紹了ALOHA算法及其改進算法，并找出了改進算法中的一些待解決問題。

關(guān)鍵詞：防碰撞 時隙 動態(tài)ALOHA算法

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1672-3791（2012）12（c）-0020-02

RFID技術(shù)是一種非接觸自動識別技術(shù)，它利用無線射頻信號在閱讀器和電子標簽之間進行雙向數(shù)據(jù)傳輸。同一時刻可能有多個標簽向閱讀器發(fā)送數(shù)據(jù)造成信號干擾，這稱為標簽碰撞。因此，需要一種防碰撞技術(shù)來解決信號干擾問題，解決碰撞的算法稱為防碰撞算法。傳統(tǒng)的解決碰撞問題的方法有四種：空分多址（SDMA）法、頻分多址（FDMA）法、碼分多址（CDMA）法和時分多址（TDMA）法[1]。目前，時分多址（TDMA）法是射頻識別系統(tǒng)解決碰撞問題的常用方法[2]。本文主要研究基于TDMA的不確定性碰撞算法ALOHA算法及其改進算法。

1 ALOHA算法

1.1 純ALOHA算法

純ALOHA算法是最簡單的隨機防碰撞算法。純ALOHA算法中標簽隨機的選擇一個時間點發(fā)送數(shù)據(jù)。如果該標簽不被識別，即有碰撞發(fā)生，那么該標簽就會隨機退避一段時間，獨立地再次選擇一時間點重新發(fā)送數(shù)據(jù)，直至成功。如圖1是純ALOHA算法的模型。

純ALOHA算法存在的問題是：如果退避區(qū)間太大，識別標簽所需要的時間會很長；如果退避區(qū)間很小，會導(dǎo)致碰撞的次數(shù)增加，需要退避的次數(shù)就多，這樣不但識別效率很低，而且識別時間也沒有改善。純ALOHA算法簡單易行，但只能獲得18.4%的吞吐率[1]。

1.2 時隙ALOHA算法

在純ALOHA算法的基礎(chǔ)上，人們引入時隙ALOHA算法。時隙ALOHA算法是把時間看成一個個連續(xù)片段，每一個片段稱為一個時隙。一般一個時隙長度等于或稍大于電子標簽和閱讀器的數(shù)據(jù)交換時間。該算法中電子標簽只能在時隙的開始時刻發(fā)送數(shù)據(jù)，這樣或成功發(fā)送或完全碰撞，避免了純ALOHA算法的部分碰撞，使碰撞周期減半，因此系統(tǒng)吞吐率比純ALOHA提高了一倍[1]。如圖2是幀時隙ALOHA算法的模型。

時隙ALOHA算法存在的問題是：每一個電子標簽征用每一個時隙的幾率是相等的，無論其在上一個時隙中是否被識別。即：上一時隙已經(jīng)被成功識別的標簽在下一個時隙被識別的幾率和上一時隙未被識別的標簽是相等的，這樣就可能導(dǎo)致上一時隙已經(jīng)被成功識別過的標簽在下一時隙又被識別，而上一時隙未被識別的標簽仍然不能被識別。這樣，標簽識別效率就比較低。

1.3 幀時隙ALOHA算法

針對時隙ALOHA算法中的問題，人們又引入了幀時隙ALOIHA算法。幀是指包含若干個時隙的時間段。主要思想是對閱讀器引入時隙計數(shù)器和去活命令，對電子標簽引入一個隨機數(shù)產(chǎn)生器。

假設(shè)每幀包含的時隙數(shù)L，閱讀器的時隙計數(shù)器從1～L計數(shù)。電子標簽的隨機數(shù)產(chǎn)生器，用來產(chǎn)生1～L之間的一個隨機數(shù)。閱讀器的時隙計數(shù)器初始值是1，且每經(jīng)過一個時隙長度時隙數(shù)自動加1。識別過程開始時閱讀器向其覆蓋范圍內(nèi)所有電子標簽發(fā)送一個包含時隙數(shù)L的命令，電子標簽的隨機數(shù)生成器生成一個1～L之間的隨機數(shù)，當該隨機數(shù)與閱讀器的時隙計數(shù)器計數(shù)值相同時，電子標簽向閱讀器發(fā)送數(shù)據(jù)。標簽被成功識別后，閱讀器向其發(fā)送去活命令，使之退出識別系統(tǒng)直至當前幀結(jié)束。在一幀完成后，閱讀器開始時隙數(shù)仍為L的新幀。

但是幀時隙ALOHA算法中如果總時隙數(shù)L遠小于標簽數(shù)目N，極有可能導(dǎo)致總有多于一個標簽選同一時隙導(dǎo)致碰撞。如果隙數(shù)L遠大于標簽數(shù)目就造成了時隙的浪費。因此，又引入了動態(tài)幀時隙ALOHA算法。

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

動態(tài)幀時隙ALOHA算法根據(jù)正確識別標簽的時隙數(shù)和產(chǎn)生碰撞的時隙數(shù)來確定下一幀包含的時隙數(shù)，當電子標簽數(shù)大于時隙數(shù)而造成過多碰撞時就增加下一幀的長度，反之則減小下一幀的長度，只有使時隙數(shù)與標簽數(shù)量相當才能達到最佳吞吐率。但是，當標簽數(shù)量遠大于每幀的時隙數(shù)時，受硬件條件限制，幀長度增大有限（Lmax=256）[3]，電子標簽碰撞率就會增大，識別電子標簽的時間會急劇增加，系統(tǒng)的識別效率急劇降低。

1.5 動態(tài)幀時隙ALOHA算法的改進算法分析

針對動態(tài)幀時隙ALOHA算法中幀長度最大值受限的問題，很多學(xué)者都提出了改進的動態(tài)幀時隙ALOHA算法，其中最典型的一種改進思想是分組[3]。

基于分組的動態(tài)幀時隙ALOHA算法實際上是借用了確定性防碰撞算法的思想，即當標簽數(shù)大于時隙允許最大值時，使一部分標簽處于非響應(yīng)狀態(tài)不參與信道競爭，處于響應(yīng)狀態(tài)的標簽被正確識別后閱讀器向其發(fā)送去活命令，即使其處于非響應(yīng)狀態(tài)不參與信道競爭直至所有的標簽都被正確識別。

基于分組的動態(tài)幀時隙ALOHA算法描述：（1）在動態(tài)幀時隙ALOHA算法的基礎(chǔ)上估算出閱讀器范圍內(nèi)標簽個數(shù)N，如果N>256，閱讀器向標簽發(fā)送分組命令，把標簽分為待命組和休眠組，每組標簽數(shù)為256。（2）待命組標簽數(shù)參與識別過程，其余標簽分到休眠組暫時不參與識別過程。（3）當前幀結(jié)束后，待命組的標簽自動休眠，休眠組的標簽按順序自動把狀態(tài)變?yōu)榇鼱顟B(tài)。（4）重復(fù)（2）、（3）直至所有組的標簽都被識別，返回（1）。

基于分組的動態(tài)幀時隙ALOHA算法在每幀內(nèi)都能減少沖突，提高標簽識別率。但是這個算法現(xiàn)在并不完美。存在的問題是：（1）由于標簽在識別過程中有2種可能的狀態(tài)，那么標簽就必須有狀態(tài)標志位，而且分組數(shù)越多標志位就越長，這就得增加標簽攜帶信息量，給硬件設(shè)計增加了難度。（2）由于標簽需要響應(yīng)閱讀器命令在兩種狀態(tài)間轉(zhuǎn)換，這就增加了標簽與閱讀器交換數(shù)據(jù)的時間，在標簽高速運動的狀態(tài)下漏讀率會增加。（3）由于標簽被分為2組或更多組，閱讀器在每幀時間內(nèi)只能識別一組，如果有一組的標簽數(shù)量遠小于256，那么識別該組的幀內(nèi)大部分時隙是空閑的，這就造成了識別時間浪費。（4）由于所有標簽分多組識別，所以一個識別周期（識別完所有標簽的幀數(shù)和）內(nèi)標簽總數(shù)是每個幀內(nèi)標簽數(shù)的和，這給統(tǒng)計標簽總數(shù)增加難度。

2 結(jié)語

基于分組的動態(tài)幀時隙ALOHA算法是當今非確定性算法的主流改進算法，盡管改進方法各有差異，但是主題思想都是本文分析的參照確定性算法的思想，限制響應(yīng)標簽數(shù)量，將響應(yīng)標簽數(shù)限制在識別效率最高的標簽數(shù)目之內(nèi)。但是正如本文分析，這個改進思想還是存在一定缺陷，這就要求我們在以后的研究過程中繼續(xù)優(yōu)化算法解決這些問題，以快速、高效完成閱讀器與電子標簽的數(shù)據(jù)交換。

參考文獻

[1]姜麗芬，盧桂章，辛運帷.射頻識別系統(tǒng)中的防碰撞算法研究[J].計算機工程與應(yīng)用，2007，43（15）：29-32.

[2]崔欣，李鵬.2008年全球RFID九大最具影響力事件[N].中國防偽報道，2009，2.

[3]尹君，何怡剛，李兵，等.基于分組動態(tài)幀時隙的RFID防碰撞算法[J].計算機工程，2009，10，35（20）：268-269.

[4]李寶山，羅春青.基于隨機數(shù)傳送的動態(tài)幀時隙ALOHA算法的研究[N].內(nèi)蒙古科技大學(xué)報，2010，9，29（3）：254-255.