RFID多標(biāo)簽防碰撞算法研究

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2012）12（c）-0020-02

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

1 ALOHA算法

1.1 純ALOHA算法

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

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

1.2 時(shí)隙ALOHA算法

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

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

1.3 幀時(shí)隙ALOHA算法

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

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

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

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

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

1.5 動(dòng)態(tài)幀時(shí)隙ALOHA算法的改進(jìn)算法分析

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

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

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

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

2 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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