《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 一種基于ALOHA的改進RFID防碰撞算法
一種基于ALOHA的改進RFID防碰撞算法
來源:微型機與應(yīng)用2011年第9期
孫文勝, 陳榮慶
(杭州電子科技大學(xué) 通信工程學(xué)院, 浙江 杭州 310018)
摘要: 標簽碰撞是無線射頻識別(RFID)技術(shù)中的常見問題,,它使得系統(tǒng)效率降低,。ALOHA算法是解決此類問題的重要方法,提出了一種基于ALOHA的改進防碰撞算法,,并分別給出了應(yīng)用該方法處理碰撞時,閱讀器和標簽各自需要執(zhí)行的程序步驟。仿真結(jié)果表明,,該算法具有較高的效率,尤其在標簽數(shù)量較大時相比動態(tài)幀時隙算法(DFSA)消耗時隙更少,。
關(guān)鍵詞: RFID 防碰撞算法 ALOHA
中圖分類號: TN911
文獻標識碼: A
文章編號: 0258-7998(2011)09-107-04

An improved anti-collision algorithm based on ALOHA in RFID system
Sun Wensheng, Chen Rongqing
Department of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
Abstract: Tag collision is a common problem in radio frequency identification(RFID), it will reduce the efficiency of a RFID system. ALOHA algorithm is an important method to solve this problem. This article proposes a modified anti-collision algorithm based on ALOHA, also gives the pseudo codes of the reader and tag when a collision is detected. Simulation results show that the proposed algorithm is very efficiency and costs fewer slots than DFSA when the number of tags is large.
Key words : RFID; anti-collision; ALOHA


    無線射頻識別技術(shù)(RFID)是一種利用射頻信號進行非接觸自動識別的技術(shù),,廣泛應(yīng)用于物流、供應(yīng)鏈管理,、商業(yè)零售和交通運輸?shù)阮I(lǐng)域,。RFID系統(tǒng)一般由具有電子編碼(ID)的標簽和閱讀器組成,它們利用無線信道實現(xiàn)相互通信來交換信息,。當(dāng)系統(tǒng)中有多個標簽同時向閱讀器發(fā)送數(shù)據(jù)時,,將會產(chǎn)生相互干擾,使閱讀器不能正確接收信息,,這就是標簽碰撞,。防碰撞算法能夠有效解決標簽的碰撞問題,實現(xiàn)閱讀器高效,、快速地讀取標簽信息,。
 目前主要存在兩種類型的標簽:有源標簽和無源標簽。前者通過電源提供能量來計算和發(fā)送信息,,計算能力強,,但使用成本高;后者通過接收閱讀器發(fā)送的電磁波獲得能量,,計算能力有限,,所以傳統(tǒng)網(wǎng)絡(luò)中的許多防碰撞技術(shù)難以直接應(yīng)用,但較低的成本更利于其在RFID系統(tǒng)中推廣使用,。本文研究的是無源標簽在RFID系統(tǒng)中的防碰撞問題,,并基于ALOHA提出了一種改進算法,它能夠迅速處理當(dāng)前識別循環(huán)中發(fā)生的碰撞,,從而有效降低此后在循環(huán)中發(fā)生標簽碰撞的概率,。仿真結(jié)果表明該方法效率較高,尤其在標簽數(shù)量較大時相比動態(tài)幀時隙算法(DFSA)消耗時隙更少,。
1 幾種主要的防碰撞算法
 目前,,RFID系統(tǒng)中的標簽防碰撞算法主要分為基于ALOHA的算法和基于樹的算法兩大類。基于ALOHA的算法是隨機算法,,該算法中標簽利用隨機時間響應(yīng)閱讀器的命令,。此類算法主要有時隙ALOHA算法、固定幀時隙算法,、動態(tài)幀時隙算法等,,其中系統(tǒng)效率最高的是動態(tài)幀時隙算法(DFSA)。算法中的“幀”是由閱讀器定義的一段時間長度,,其中包含若干時隙,,每個時隙長度等于標簽的數(shù)據(jù)幀長度。在ALOHA算法中標簽需要具備產(chǎn)生隨機數(shù)的功能,。
  固定幀時隙算法是一種基本算法,,每幀的時隙數(shù)相同。在開始識別時,,由閱讀器向作用范圍內(nèi)所有標簽發(fā)送包含時隙數(shù)N的命令,。標簽收到命令后,將其時隙計數(shù)器置為1,,開始記錄時隙數(shù),,同時產(chǎn)生一個介于1和N的數(shù)作為其隨機選擇的時隙數(shù)值。當(dāng)時隙計數(shù)器值與標簽隨機選擇的時隙數(shù)值相同時,,向閱讀器發(fā)送應(yīng)答消息,。若標簽被閱讀器成功識別,則以后不再響應(yīng)閱讀器,。一個幀結(jié)束后,,閱讀器開始識別時隙數(shù)同樣為N的新幀。該算法雖然簡單但識別效率不高,,由于幀長固定,,當(dāng)標簽數(shù)遠小于時隙數(shù)時,會產(chǎn)生較多的空閑時隙,,浪費系統(tǒng)資源,;反之,則會產(chǎn)生過多的碰撞,,大大降低系統(tǒng)效率,。只有在標簽數(shù)目與時隙數(shù)相差不大時,才會有較好的系統(tǒng)效率,。由于該算法的時隙數(shù)不能隨著標簽數(shù)目的變化而改變,,因此,無法獲得穩(wěn)定的系統(tǒng)效率,。
 動態(tài)幀時隙算法(DFSA)是一種改進的幀時隙算法,,具有較高的效率,。其每幀的時隙數(shù)會根據(jù)標簽數(shù)目的不同而變化,主要執(zhí)行過程如下:(1)閱讀器估計在其作用范圍內(nèi)未識別的標簽數(shù)目,,從而決定下一幀需要的時隙數(shù)值N;(2)閱讀器發(fā)送包含N個時隙的幀,,標簽隨機選擇一個時隙向閱讀器發(fā)送應(yīng)答消息,,在此過程中已被成功識別的標簽將不再響應(yīng)閱讀器。重復(fù)執(zhí)行(1),、(2)的操作直至成功識別所有標簽,。該算法的效率在34.6%和36.8%之間[1]。
 二進制樹算法系統(tǒng)效率高,,但系統(tǒng)的設(shè)計復(fù)雜,。其算法的基本思想是:將處于碰撞的標簽分為左右兩個子集0和1,先查詢子集0,,如果沒有碰撞,,則正確識別標簽,若仍然存在碰撞則再次分裂,,把子集0分成00和01兩個子集,,以此類推直到成功識別子集0中的所有標簽,再按上述步驟查詢子集1,。該算法雖然不存在錯誤判決,,但是整個識別過程需要逐一檢查標簽ID前綴是否匹配,如果一個標簽集中各個標簽的ID非常相近,,則完成整個識別過程需要花費過長的時間,。
2 改進的方法
 本文提出一種基于ALOHA協(xié)議的簡單高效防碰撞算法,該算法能夠迅速處理標簽發(fā)生的碰撞,。當(dāng)發(fā)生碰撞時,,系統(tǒng)會立刻開始一個新的識別過程,此時閱讀器需要先估計發(fā)生碰撞的標簽數(shù)目,,然后向碰撞標簽發(fā)送重新設(shè)置的時隙數(shù)值,,而標簽也會產(chǎn)生一個隨機選擇的時隙數(shù)值,當(dāng)該隨機數(shù)等于其時隙計數(shù)器時,,向閱讀器發(fā)送應(yīng)答消息,。如果在這個新的識別過程中再次發(fā)生碰撞,則重復(fù)執(zhí)行上述步驟,,這樣可以減少如下情況的發(fā)生:當(dāng)前發(fā)生碰撞的標簽在下一次循環(huán)中可能再次發(fā)生碰撞從而在系統(tǒng)中產(chǎn)生更多的碰撞,。
 實驗中假定有n個不同電子編碼(ID)的無源標簽,閱讀器可以估計標簽數(shù)目但是不知道其確切的值,。設(shè)初始時隙數(shù)為Ni,,當(dāng)開始識別時,閱讀器向所有標簽發(fā)送包含Ni的消息,標簽收到后將產(chǎn)生一個介于1和Ni之間的隨機數(shù),,當(dāng)標簽的時隙計數(shù)器值與其隨機產(chǎn)生的時隙數(shù)值相同時,,將向閱讀器發(fā)送應(yīng)答消息。若此過程中沒有發(fā)生碰撞,,則閱讀器就能成功識別標簽,。上述過程與ALOHA算法類似。但如果標簽發(fā)生碰撞,,閱讀器則放棄之前已經(jīng)成功識別的時隙,,開始一個新的識別過程(此處假定閱讀器和標簽?zāi)軌虺晒ν瓿梢?guī)定的動作)。在此過程中,,閱讀器估計發(fā)生碰撞的標簽數(shù)目nc[2],,通過nc來確定新設(shè)置的時隙數(shù)Nc,標簽收到包含該數(shù)的消息后產(chǎn)生一個介于1和Nc之間的隨機數(shù),,重復(fù)執(zhí)行此過程直到不再發(fā)生碰撞,。圖1是本文方法的流程圖,圖中閱讀器初始時發(fā)送包含Ni的消息,,當(dāng)發(fā)生碰撞時,,能夠迅速進行處理。剩余的標簽將在第一組碰撞標簽處理完成后再進行識別,。

    前面在描述DFSA算法時提到,,閱讀器會在第一輪識別完成后發(fā)送一個新設(shè)置的時隙數(shù)值給所有發(fā)生碰撞的標簽,這些標簽分別產(chǎn)生隨機選擇的時隙數(shù),。但是可以發(fā)現(xiàn),,第一輪識別中發(fā)生碰撞的標簽同樣可能在之后的識別輪次中再次發(fā)生碰撞,而本文的方法能夠迅速處理標簽的碰撞,,降低碰撞標簽以后再次發(fā)生碰撞的概率,。閱讀器本身無法知道發(fā)生碰撞標簽數(shù)目,但是可以通過估計得到nc,,由nc確定重新設(shè)置的時隙數(shù)值Nc并開始新的循環(huán),。為了獲得較優(yōu)的系統(tǒng)吞吐率,本文根據(jù)不同范圍的標簽數(shù)由表1來確定Nc[3],。
 當(dāng)未被識別的標簽數(shù)目很少時就不需要采用過大的時隙數(shù)值,,反之如果標簽數(shù)目很多而時隙數(shù)過小時,則發(fā)生碰撞的概率將會增加,。當(dāng)設(shè)置的時隙數(shù)與需要識別的標簽數(shù)目相等時,,可以獲得最大系統(tǒng)效率[4]。因此,,選擇合適的時隙數(shù)非常重要,。在本文的方法中,,將根據(jù)表1的數(shù)據(jù)來確定識別過程中不斷改變的時隙數(shù)值。
 為了執(zhí)行本文的方法,,需先定義一個特殊的命令“throw_away”,,它表示開始執(zhí)行該方法的各個步驟,程序1所示是閱讀器需執(zhí)行程序的偽碼,,描述了當(dāng)閱讀器檢測到標簽碰撞時將會發(fā)生的動作,。當(dāng)c>0時,表示發(fā)生碰撞,,閱讀器將發(fā)送throw_away命令給碰撞標簽;ad是針對碰撞標簽的計數(shù)值,,當(dāng)發(fā)生碰撞時,,ad的值加1;在此之后閱讀器將通過估計碰撞標簽數(shù)目來確定Nc,。
    程序1 檢測到碰撞時閱讀器執(zhí)行的程序
  /*Reader:*/
      /*發(fā)送”throw_away”命令*/
      if (c>0)  /* 發(fā)生碰撞*/
    /* 閱讀器發(fā)送throw_away命令給發(fā)生碰撞的標簽 */
      tag_respond = tag (throw_away);   
    if ( tag_respond > 0 )  /* 命令發(fā)送成功 */
          ad = ad + 1;  /*當(dāng)發(fā)生碰撞時ad的值增加1 */
      tag (ad);  /* 將ad的值發(fā)送給標簽 */
      start a new round;
      broadcast Nc;
    程序2所示是標簽需執(zhí)行程序的偽碼,,描述了碰撞標簽收到閱讀器發(fā)送的throw_away命令后將會發(fā)生的動作。通過設(shè)置ct的值來限制碰撞標簽應(yīng)答閱讀器,,當(dāng)標簽接收到throw_away命令時其值加1,;當(dāng)標簽隨機選擇的時隙數(shù)等于其時隙計數(shù)器值,并且ad與ct相等時,,發(fā)送應(yīng)答消息給閱讀器,,同時ct值置0,標簽再次收到throw_away命令之前不再響應(yīng)閱讀器,。
    程序2 接收到throw_away命令時標簽執(zhí)行的程序
  /*  Tag:  */
  /* 從閱讀器處獲取初始參數(shù) */
  ct = 1;
  transmission;
  receive the number of slots;
  generate random numbers;
  if ( slot = = ti && ct = = ad )
    transmit message;  /* 標簽發(fā)送應(yīng)答消息 */
    ct = 0;   /* 發(fā)送完成后ct置0 */
  if (receive “throw_away”)
    ct = ct + 1;
      goto transmission;
    如果在最后一個時隙中發(fā)生標簽碰撞,,系統(tǒng)將會放棄之前已經(jīng)成功識別的時隙。若此情況經(jīng)常出現(xiàn),,則系統(tǒng)效率會降低很多,,這是應(yīng)用本文方法理論上可能會發(fā)生的最壞情況。圖2的仿真結(jié)果是這種情況發(fā)生的概率,,從中可以看出當(dāng)標簽數(shù)量較大時,,這種最壞的情況發(fā)生概率其實很小。因此,,當(dāng)標簽數(shù)目較多時,,這種最壞的情況幾乎不會發(fā)生,而應(yīng)用本文的方法就可以減少識別過程中的時隙消耗,。

3 仿真結(jié)果
    大量標簽向閱讀器發(fā)送消息時產(chǎn)生碰撞,,假定標簽數(shù)從10增加到300,圖3是應(yīng)用本文方法進行仿真得到的結(jié)果,。從中可以看出本文方法比DFSA算法耗費的時隙少,,并且標簽數(shù)目越多差別越明顯,。這表明對比DFSA算法,本文方法節(jié)約了時隙資源,。

 為獲得較高的系統(tǒng)效率,,仿真時設(shè)初始時隙數(shù)Ni為16,約為開始時的標簽數(shù)目,??梢酝ㄟ^改變初始時隙數(shù)Ni來觀察所產(chǎn)生的影響,圖4表明,,當(dāng)初始時隙數(shù)變?yōu)?4時,,即使標簽數(shù)目增加,系統(tǒng)效率也不會有明顯的變化,;但標簽數(shù)目較少時,,較大的初始時隙數(shù)Ni對應(yīng)較小的碰撞發(fā)生概率,此時,Ni=128時的系統(tǒng)效率比Ni=16和Ni=64時低,。上述結(jié)果表明初始時隙數(shù)Ni設(shè)為16,,可以應(yīng)用于標簽數(shù)較多的情況。
 設(shè)初始幀長Ni為16,,持續(xù)增加標簽數(shù)目,,仿真結(jié)果如圖5所示??梢钥闯?,當(dāng)標簽數(shù)持續(xù)增加時,本文方法耗費的時隙數(shù)明顯小于DFSA算法,;而當(dāng)標簽數(shù)較少時,,這種差異并不明顯。綜上,,本文提出的方法系統(tǒng)效率優(yōu)于DFSA算法,,并且耗費更少的時隙。

 本文提出了一種基于ALOHA協(xié)議的簡單高效RFID系統(tǒng)防碰撞算法,。閱讀器先給標簽發(fā)送一個包含初始時隙數(shù)的消息,,標簽收到后隨機選擇一個時隙同時將自己的時隙計數(shù)器置為1。當(dāng)標簽隨機選擇的時隙數(shù)等于時隙計數(shù)器時,,回復(fù)其電子編碼(ID)給閱讀器,,如果發(fā)生碰撞,閱讀器將放棄已經(jīng)成功識別的時隙而開始新的識別循環(huán),,這樣使碰撞標簽?zāi)艿玫窖杆偬幚?。該方法中閱讀器能夠在新的識別循環(huán)中首先鑒別出碰撞標簽,然后再識別其余的標簽,。當(dāng)標簽數(shù)增加到1 000時,,本文方法比DFSA算法少耗費約54%的時隙,,并且系統(tǒng)效率可以穩(wěn)定在35%左右,相比DFSA算法此時約20%[5]的效率也有較大提高,。
參考文獻
[1] 許武忠,,胡斌杰. 一種新穎快速的二進制搜索防碰撞算法[J].中國電子商情(RFID技術(shù)與應(yīng)用),2008(3):26-28.
[2] VOGT H. Efficient object identification with passive RFID tags[C]. International Conference on Pervasive Computing. LNCS, Springer-Verlag,2002.
[3] 程良倫,,林偉勇. 一種穩(wěn)定高效的動態(tài)幀時隙ALOHA算法[J]. 計算機應(yīng)用研究,2009,26(1):85-91.
[4] VOGT H. Multiple object identification with passive RFID tags[C]. Systems, Man and Cybernetics, 2002 IEEE International Conference, 2002,10(3):6-9.
[5] 張頗,,崔喆. RFID系統(tǒng)中的一種改進的防碰撞算法[J].計算機應(yīng)用, 2008,28(8):2141-2143.
 

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。