RFID多標簽防碰撞算法研究

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

關鍵詞：防碰撞 時隙 動態ALOHA算法

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

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

1 ALOHA算法

1.1 純ALOHA算法

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

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

1.2 時隙ALOHA算法

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

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

1.3 幀時隙ALOHA算法

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

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

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

1.4 動態幀時隙ALOHA算法

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

1.5 動態幀時隙ALOHA算法的改進算法分析

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

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

基于分組的動態幀時隙ALOHA算法描述：（1）在動態幀時隙ALOHA算法的基礎上估算出閱讀器范圍內標簽個數N，如果N>256，閱讀器向標簽發送分組命令，把標簽分為待命組和休眠組，每組標簽數為256。（2）待命組標簽數參與識別過程，其余標簽分到休眠組暫時不參與識別過程。（3）當前幀結束后，待命組的標簽自動休眠，休眠組的標簽按順序自動把狀態變為待命狀態。（4）重復（2）、（3）直至所有組的標簽都被識別，返回（1）。

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

2 結語

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

參考文獻

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

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

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

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