分組自適應(yīng)分配時隙的RFID防碰撞算法研究

張小紅,胡應(yīng)夢

(江西理工大學(xué)信息工程學(xué)院,江西贛州 341000)

?

分組自適應(yīng)分配時隙的RFID防碰撞算法研究

張小紅,胡應(yīng)夢

(江西理工大學(xué)信息工程學(xué)院,江西贛州 341000)

為了解決射頻識別(Radio Frequency IDentification,RFID)系統(tǒng)中的多標簽防碰撞問題,在分析幀時隙ALOHA算法的基礎(chǔ)上,提出一種基于分組自適應(yīng)分配時隙的RFID防碰撞算法(GAAS).首先讓閱讀器對標簽隨機所選的時隙進行掃描統(tǒng)計,并將其發(fā)送給每一個標簽,標簽再進行相應(yīng)地時隙調(diào)整,使閱讀器跳過空閑時隙和碰撞時隙,自適應(yīng)地分配有效時隙,進而對標簽進行快速識別.當未識別標簽數(shù)比較大時,算法采用分組以及動態(tài)調(diào)整幀長等策略,以減少時隙處理的時間.仿真結(jié)果表明:GAAS算法提高了系統(tǒng)的識別效率和穩(wěn)定性,降低了傳輸開銷.特別是當標簽數(shù)超過1000時,該算法的吞吐率仍保持在71%以上,比傳統(tǒng)的幀時隙ALOHA-256算法和分組動態(tài)幀時隙ALOHA算法的系統(tǒng)效率分別提高了300%和97.2%.

射頻識別;ALOHA算法;標簽分組;吞吐率;自適應(yīng)分配時隙

1　引言

射頻識別(Radio Frequency IDentification,RFID)是一種利用電磁波傳播方式在閱讀器和標簽之間進行非接觸雙向數(shù)據(jù)傳輸,進而獲取被標識物體信息的識別技術(shù)[1],被公認為21世紀的最具發(fā)展前景和變革力的高新技術(shù).該技術(shù)具有數(shù)據(jù)交換快、追蹤物體及時、無空間限制、穿透能力強、多目標識別和抗污染等優(yōu)點,在物流管理、交通運輸、自動化生產(chǎn)、公共信息服務(wù)等行業(yè)有著廣泛的應(yīng)用,可大幅提高管理與運作效率,降低成本[2,3].

RFID系統(tǒng)由電子標簽(tag)、讀寫器(reader)和后端數(shù)據(jù)庫(database)三大部分組成.在多個閱讀器與多個標簽的射頻識別系統(tǒng)中,存在著兩種形式的碰撞,即閱讀器碰撞和標簽碰撞[4].由于閱讀器碰撞發(fā)生的概率較小且閱讀器本身的處理能力較強,因此閱讀器碰撞問題較容易解決.國內(nèi)外的學(xué)者在多標簽同時與讀寫器進行通信的碰撞問題方面已經(jīng)做了大量的研究[5～7],這些方法一般被分為四類:空分多路法、頻分多路法、碼分多路法和時分多路法[8].由于標簽的低功耗、低存儲能力和有限的計算能力等特點,標簽防碰撞方法主要采用時分多路法.

在時分多路法中,目前最常用的多標簽防碰撞算法分為兩種,一種是基于二進制樹的確定型算法,其主要代表算法有二進制搜索算法[9]、動態(tài)二進制搜索算法[10]、跳躍式動態(tài)樹算法[11]、查詢樹算法[12]等.該類法是由閱讀器根據(jù)標簽ID的唯一性來選擇標簽進行通信,所以搜索算法的性能會隨ID位數(shù)的增加而急劇惡化.另一種是基于ALOHA的統(tǒng)計型算法.其主要算法包括時隙ALOHA(Slotted ALOHA,SA)算法[13]、幀時隙ALOHA(Frame-slotted ALOHA,FSA)算法[14]、動態(tài)幀時隙ALOHA(Dynamic Frame-slotted ALOHA,DFSA)算法[15],另外還有EPCglobal提出的EPC Class-1 Generation-2(EPC C1G2)標準[16]采用一種基于Q值的隨機幀時隙算法[17,18]以及近期有文獻提出基于碰撞預(yù)測的ALOHA防碰撞(Collision Prediction-ALOHA,CP-ALOAH)算法[19]等.這些防碰撞算法實現(xiàn)過程相對比較簡單,標簽內(nèi)部也不需要設(shè)計復(fù)雜的電路,因此標簽的成本也較低.然而,隨著標簽的數(shù)目增大,甚至上千時,發(fā)生碰撞的概率也隨之增大,系統(tǒng)識別的性能急劇下降.針對于大量標簽的識別問題,研究者們又提出分組的概念,有增強的動態(tài)幀時隙算法[20]、分組動態(tài)幀時隙ALOHA(Grouped Dynamic Frame-slotted ALOHA,GDFSA)算法[21]等.與之前的算法相比,分組類的防碰撞法其吞性能比較穩(wěn)定,但是與其他算法一樣,其吞吐率均比較低,只有40%～50%左右.

本文提出了自適應(yīng)分配時隙(Adaptive Allocating Slots,AAS)算法,隨著待識別標簽數(shù)目的增加,又加入分組的概念,即分組自適應(yīng)分配時隙(Grouped Adaptive Allocating Slots,GAAS)算法.該算法結(jié)合了傳統(tǒng)GDFSA和CP-ALOHA算法的特點,在它們的基礎(chǔ)上進行了優(yōu)化和改進.首先估計標簽數(shù)量,然后采用分組、動態(tài)調(diào)整幀長、時隙預(yù)約以及自適應(yīng)分配時隙等策略對標簽進行識別.仿真結(jié)果表明,新的算法降低了傳輸開銷,簡化了標簽電路的設(shè)計,提高了系統(tǒng)的識別效率和穩(wěn)定性.當標簽數(shù)目大于1000時,其系統(tǒng)識別效率仍可達71%以上,與EPC標準協(xié)議相比,傳輸開銷大約下降了48.1%,且隨著標簽數(shù)目的增加,新算法的優(yōu)越性更加明顯.

2　GAAS算法描述

2.1基本定義

定義1[22]設(shè)定一幀內(nèi)的時隙數(shù),即幀長為L,在對n個標簽進行識別時,每一個標簽都會隨機選擇一個時隙來發(fā)送自己的識別碼信息,根據(jù)二項分布定理,某個標簽占用幀內(nèi)任意時隙的概率為p=1/L,則同一個時隙里有r個標簽的概率可以表示為:

(1)

當r=0,即一個時隙里沒有請求識別標簽,該時隙稱為空閑(idle)時隙,其概率為:

(2)

當r=1,即一個時隙里只有一個標簽請求識別標簽,該時隙稱為成功(success)時隙,其概率為:

(3)

當r≥2,即一個時隙里有兩個及以上的標簽請求識別標簽,該時隙稱為碰撞(collision)時隙,其概率為:

Pc=1-Ps-Pi

(4)

(5)

(6)

(7)

定義2[23]RFID系統(tǒng)的吞吐率S是指閱讀器在一個識別幀長的時間內(nèi)成功傳輸信息的標簽數(shù)目所占的比例,即:

(8)

2.2標簽數(shù)目估計

GAAS算法要求閱讀器在開始識別前,需估計剩下標簽的數(shù)量.幀長的大小和未識別標簽的數(shù)目越接近,系統(tǒng)效率越高,因此該過程對于整個識別過程起著至關(guān)重要的作用.目前已經(jīng)提出了多種標簽數(shù)目估計方法,有Vogt算法[24],Cratio算法[25],Schoute算法[26]和Low Bound算法[27].Vogt算法可以做出誤差相對較為小且穩(wěn)定的估計,因此本文采用Vogt算法來估計標簽的數(shù)目.

(9)

2.3RFID系統(tǒng)最優(yōu)幀長分析

閱讀器在其可讀范圍內(nèi)的標簽數(shù)目進行估計之后,需要根據(jù)標簽數(shù)目動態(tài)的調(diào)整幀長,如果幀長取值太大就會產(chǎn)生大量的空閑時隙,反之會導(dǎo)致碰撞時隙急劇上升,最終都將影響系統(tǒng)識別效率.因此要想取得較高的吞吐率效率,必須找出幀長與標簽數(shù)目之間對應(yīng)關(guān)系,即確定最優(yōu)幀長[28].對式(8)求導(dǎo):

(10)

令式(10)等于0,達到幀長L與標簽的個數(shù)n應(yīng)滿足:

(11)

再由泰勒級數(shù)展開得到

(12)

由式(12)可知,當標簽數(shù)n遠大于1,并且n接近于幀長L時,系統(tǒng)的吞吐率達到最大.圖1給出了L為不同固定值時系統(tǒng)吞吐率的仿真結(jié)果:

根據(jù)式(8),相鄰固定幀長L1和L2的吞吐率曲線交點處的標簽的數(shù)目,即為調(diào)整幀長的臨界點.

(13)

(14)

其中?*」表示向下取整運算,從而得到了標簽數(shù)目n和幀長L的對應(yīng)關(guān)系,如表1所示.由標簽數(shù)目的取值范圍決定幀長的大小,當標簽數(shù)目大于354時,仍以最大幀長256分別進行識別.

表1　幀長與標簽數(shù)目對應(yīng)關(guān)系

2.4標簽分組原理

由于受到標簽成本的限制,使得幀時隙數(shù)不能夠隨著標簽數(shù)目的增加而無限地增加,所以針對于大量的標簽的情況,只有通過限制每次響應(yīng)的標簽的數(shù)目,才能使系統(tǒng)保持相對較高的吞吐率.根據(jù)式(8),選取對標簽進行分組的臨界值[29],即兩相鄰幀的性能曲線交點Pa=Pb處的標簽數(shù)值.

(15)

其中,a,b為標簽的相鄰分組數(shù),例如當取a=1,b=2代入式(15)可得:

(16)

(17)

即n=354是將標簽分為一組或兩組的臨界值,為了使系統(tǒng)保持較高的吞吐率效率,未識別標簽數(shù)n不能大于354,當n大于354時,需要對未識別的標簽進行分組.由式(15)可計算得到標簽數(shù)量在2283以內(nèi)的分組數(shù),如表2所示.

表2　標簽總數(shù)與分組數(shù)的對應(yīng)關(guān)系

表2中的分組數(shù)1,2,4,6,8是自主設(shè)計的,各組中的最小標簽數(shù)與最大標簽數(shù)是式(15)中通過a,b數(shù)值計算出來的門限值.隨著標簽數(shù)目的增加,分組數(shù)也不斷增大.

2.5分組自適應(yīng)時隙分配算法

2.5.1GAAS算法約定

(1)Query(M)命令是碰撞時隙掃描的命令,其中的參數(shù)M是幀的時隙數(shù).標簽在這M個時隙中隨機選取一個時隙,并加載到計數(shù)器中,同時向閱讀器返回預(yù)約時隙數(shù)k,然后根據(jù)所選擇的時隙進行相應(yīng)的延時.

(2)Refresh-slot(Slots)命令,該命令是閱讀器根據(jù)在碰撞時隙掃描的過程中,將時隙的選擇情況發(fā)送給每一個標簽,其中,Slots是一個數(shù)組.如果時隙能夠完整讀取就標記為0,反之則記為-1.標簽接收到該命令之后,再進行時隙調(diào)整.

(3)Collection()命令,該命令是讀取標簽信息的命令.標簽接收到這個命令之后,會根據(jù)上一個命令中更新的時隙,延遲響應(yīng)時間,最后再將自身的數(shù)據(jù)發(fā)送至閱讀器.

(4)Count()命令,該命令的作用是讓標簽時隙計數(shù)器減1,計數(shù)器為0的標簽響應(yīng)閱讀器.

(5)S1eep()命令,該命令的作用是讓標簽暫時處于靜默狀態(tài),使其不參與后面的查詢.

2.5.2GAAS防碰撞協(xié)議

GAAS算法的核心就是在進行標簽識別之前,首先進行時隙掃描操作,記錄下標簽所預(yù)約時隙的情況,然后在標簽識別階段,讓閱讀器跳過碰撞時隙和空閑時隙,而直接分配有效時隙,對成功預(yù)約的標簽直接進行識別,從而提高了時隙的利用率.其協(xié)議流程如圖2所示,協(xié)議過程可分為三個階段:

(1)標簽數(shù)目估計及分組階段

①在識別開始階段,用Vogt算法估計待識別標簽的數(shù)目n.

②當標簽數(shù)目小于354個時,采用動態(tài)幀時隙策略,動態(tài)調(diào)整識別幀的長度M,直接進入時隙處理階段.當n大于354時,則需要對標簽進行分組,由表2求得分組數(shù)g.

③標簽在1到g之間隨機選擇一個數(shù)i,作為自己的組編號,同時把s[t]的值增加1,記錄該組的標簽數(shù).

④初始化當前識別的組編號t=1,開始對第t組進行識別.

(2)時隙處理階段

①在進行數(shù)據(jù)讀取之前,首先進行時隙掃描,閱讀器以廣播的形式發(fā)送Query(M)命令給每個標簽.標簽收到該命令之后,再向閱讀器返回各自所預(yù)約的時隙數(shù).

②閱讀器再根據(jù)所接收到的數(shù)據(jù)信息,來判斷哪些時隙可以成功識別,哪些時隙將會產(chǎn)生碰撞或空閑時隙.如果能成功識別標簽,就將相應(yīng)的時隙標志位Flag設(shè)為0,其他情況就將Flag設(shè)為-1.

③閱讀器根據(jù)標簽所預(yù)約時隙的情況,將其通過命令Refresh-slot(Slots)發(fā)送給每個標簽,讓標簽也能夠知道其他標簽選擇時隙的情況,然后調(diào)整相應(yīng)的時隙.Slots里面的元素就是在前面的時隙掃描過程中記錄下的標記值,標簽根據(jù)這個數(shù)組來調(diào)整相應(yīng)所選擇的時隙數(shù).

(3)標簽識別階段

①由于閱讀器在上一個階段已經(jīng)知道了各時隙的選擇情況,在識別階段直接分配有效時隙.接下來閱讀器發(fā)送Collection()命令,標簽接收到這個命令之后,就按照調(diào)整后的時隙依次向閱讀器發(fā)送數(shù)據(jù).

②閱讀器發(fā)送Count()命令,讓該組中各個標簽的時隙計數(shù)器減1.

③最后閱讀器發(fā)送S1eep()命令,在這一輪查詢過程中被正確讀取到的標簽就會進入靜默狀態(tài),即不參與接下來的查詢.

④在每一輪識別結(jié)束以后,再估算剩余未識別標簽的數(shù)目,若標簽數(shù)目不為0,則重復(fù)上面②,③兩個階段,直至將該組剩下的標簽全部識別完.

⑤組編號加1,即t=t+1,然后執(zhí)行下述兩種情況之一.

(a)如果t≤g,則表示存在沒有識別的組,繼續(xù)進行下一組的識別.

(b)如果t>g,即所有的組都識別完成,識別結(jié)束.

3　算法對比分析

3.1DFSA算法分析

動態(tài)幀時隙DFSA算法會根據(jù)前一幀的情況,估算出標簽的數(shù)量,動態(tài)的調(diào)整幀的長度,這相對于FSA算法提高了效率.圖3為DFSA算法的示意圖,假設(shè)有8個標簽,幀長為8,即每幀中含有8個時隙,各標簽在每幀中隨機選取一個時隙發(fā)送信息.DFSA算法的識別過程是:首先由閱讀器向周圍標簽廣播發(fā)送一個命令,通知標簽該幀包含有8個時隙,然后標簽從1～8時隙中隨機選擇一個作為自己的發(fā)送時隙,如果所選時隙上沒有產(chǎn)生碰撞,則標簽就會成功識別,接著退出系統(tǒng).否則,閱讀器將通知剩下未識別標簽,在下一輪識別中重新選擇發(fā)送時隙,直到所有的標簽均被正確識別.

這種算法雖然簡單,但是在其識別過程中會產(chǎn)生過多的碰撞時隙或空閑時隙,進而導(dǎo)致系統(tǒng)吞吐率不高.

3.2GAAS算法分析

仍以上面的例子,我們以GAAS算法進行分析.首先進行時隙掃描,閱讀器以廣播的形式發(fā)送Query(8)命令給每個標簽,每個標簽就從8個時隙中隨機選擇一個作為自己的時隙,并按照所選時隙進行相應(yīng)的延時,然后向閱讀器返回一個時長非常短的預(yù)約幀.由于受到標簽成本的限制,所預(yù)約的時隙數(shù)不會超過256個,即8bit,為了盡量避免預(yù)約幀產(chǎn)生碰撞,后面的協(xié)議都將預(yù)約幀規(guī)定為16bit,即2個字節(jié),按照IS018000-6協(xié)議規(guī)定,數(shù)據(jù)速率為40Kbps,每個普通數(shù)據(jù)幀為16個字節(jié),可知發(fā)送預(yù)約幀只需1/8個時隙,所以發(fā)送預(yù)約幀非?？?假設(shè)有8個標簽,幀長為8,即M=8.如表3所示,其中φ表示沒有標簽.

表3　時隙掃描過程中時隙的選擇情況

然后閱讀器發(fā)送Refresh-slot(Slots)命令,其中數(shù)組Slots為[-1,0,0,-1,-1,0,-1,-1],標簽就會根據(jù)這個數(shù)組來調(diào)整將要發(fā)送數(shù)據(jù)的時隙.例如標簽1,7開始所預(yù)約的時隙為1,但是該時隙上產(chǎn)生了碰撞,故將時隙數(shù)調(diào)整為0,所以標簽1,7就不再參加后面的查詢過程.標簽2開始所選時隙為2,則根據(jù)數(shù)組的前2個數(shù)值來調(diào)整,即2-1=1,所以標簽2將在時隙1中上傳數(shù)據(jù).同理,可以求得其他標簽最終所選擇的時隙,并且將進行相應(yīng)的延時.標簽調(diào)整之后的時隙數(shù)如表4所示.

接下來閱讀器發(fā)送Collection()命令,標簽接收到這個命令之后,就會按照調(diào)整后的時隙依次發(fā)送數(shù)據(jù).只有標簽2,3和6號標簽選擇了有效時隙,分別為新時隙1,2,3.如圖4所示.閱讀器跳過了碰撞時隙以及空閑時隙,自適應(yīng)地分配有效時隙,因此就提高了信道的利用率.假設(shè)每個時隙為5ms,可以看到在這一輪查詢過程中總的時間消耗為8個預(yù)約幀為5ms,然后是15ms的讀取時隙,所以一共消耗了20ms.相對于前面DFSA算法而言,減少了20ms的時間,當標簽的數(shù)目增加,幀長值更大時,該算法將會節(jié)省更多的時隙.

表4　調(diào)整后的時隙選擇情況

以上僅是一個簡單的范例.由2.5.2節(jié)可知整個算法可分為三個階段:標簽數(shù)目估計及分組階段,時隙處理階段和標簽識別階段.由于第一階段所消耗的時隙很少,所以本文主要討論后面兩個階段.

閱讀器首先根據(jù)在其作用范圍內(nèi)標簽的數(shù)目分配一定數(shù)量的時隙(如表5所示,與識別幀的長度有關(guān)),以便獲得標簽預(yù)約時隙的情況,然后再根據(jù)協(xié)議,讓標簽重新調(diào)整時隙,進入標簽識別階段.閱讀器再根據(jù)標簽成功預(yù)約的數(shù)目,自適應(yīng)地分配相應(yīng)數(shù)量的時隙,最后將此次成功預(yù)約的標簽全部識別出來.

表5　標簽數(shù)與時隙預(yù)測階段消耗的時隙數(shù)對應(yīng)關(guān)系

從圖5可知,當標簽數(shù)目不斷增大時,系統(tǒng)的性能急劇下降,因此需要對其進行分組.但是,分組越多,其消耗的時隙會相應(yīng)的增加,調(diào)整時隙的時間也會越長.當標簽的數(shù)目在0～600之間時,分四組反而會降低系統(tǒng)的性能.所以GAAS算法采取自適應(yīng)分組的方法,根據(jù)標簽的數(shù)目自主進行分組.該策略能夠解決標簽數(shù)目較大而致識別效率過低的問題,同時也能使系統(tǒng)性能保持相對穩(wěn)定,減少了標簽的識別時間.

4　算法性能分析

為了從實驗角度證實GAAS算法的有效性,在Windows7操作系統(tǒng),2G內(nèi)存的環(huán)境下,利用仿真軟件MATLAB分別對FSA-256算法、DFSA算法、EPC標準算法、GDFSA算法以及GAAS算法進行仿真.假設(shè)系統(tǒng)的標簽分布是均勻的,標簽個數(shù)取1500以上,為了與分析相對應(yīng),仿真的結(jié)果是取相同條件下100次實驗的平均值.

4.1標簽電路復(fù)雜度分析

假設(shè)標簽隨機選取時隙的隨機數(shù)為R,則需?log2R」位隨機數(shù),由于本算法采取分組的方法,R最大值設(shè)為256,僅需8位即可,所以標簽只需8位隨機數(shù)產(chǎn)生電路.而EPC C1G2防碰撞協(xié)議除了產(chǎn)生選取時隙的隨機數(shù)需4位外,還要求生成16位RN16隨機數(shù),一共需要16+4=20位隨機數(shù)產(chǎn)生電路.因此,本算法對標簽設(shè)計隨機數(shù)電路復(fù)雜性明顯低于EPC C1G2標簽.此外,標簽中還有基于狀態(tài)機的控制器來執(zhí)行命,EPC C1G2標簽需執(zhí)行主要命令有5個(Query,QueryAdjust,QueryRep,Ack,RN16),本文協(xié)議中標簽也需執(zhí)行5個(Query,Refresh-slot,Count,Collection,Sleep),故GAAS協(xié)議標簽的控制器電路復(fù)雜性也與EPC C1G2協(xié)議相當.綜上所述,GAAS協(xié)議標簽電路設(shè)計比EPC C1G2協(xié)議簡單,從而降低了標簽的成本.

4.2傳輸開銷分析

傳輸開銷是評估一個算法的重要指標,其包括閱讀器開銷和標簽開銷兩部分.分別對AAS算法、GAAS算法以及EPC標準中的算法在標簽識別過程中的傳輸開銷進行仿真,仿真中用到的GAAS命令和參數(shù)長度如表6所示.

4.2.1閱讀器的開銷

設(shè)標簽數(shù)量在區(qū)間[0,2000]內(nèi)變化,讀寫器傳輸?shù)谋忍財?shù)如圖6所示,隨著標簽數(shù)目的增加,閱讀器的開銷也不斷增大.當標簽的數(shù)目少于1300時,AAS算法與GAAS算法閱讀器開銷相當,而當標簽的數(shù)目超過1300時,GAAS算法的優(yōu)勢開始凸顯出來.這是因為AAS算法沒有將標簽進行分組處理,隨著標簽數(shù)目的增加,標簽碰撞的概率急劇上升,閱讀器發(fā)送的指令也會隨之增加.當標簽數(shù)目為2000時,AAS算法中讀寫器比特數(shù)為66790,EPC標準算法分別為60527,而GAAS算法為54245,比AAS算法的開銷下降了18.8%,比ECP標準算法下降了10.4%.

表6　GAAS算法中涉及的命令和參數(shù)長度

4.2.2標簽的開銷

圖7顯示了三種算法標簽的開銷,隨著標簽數(shù)目的增加,AAS算法中標簽傳送比特數(shù)接近指數(shù)增長,而GAAS算法和EPC標準算法近似線性增長,其中GAAS增長最為緩慢.當標簽的數(shù)目為2000時,AAS算法中讀寫器比特數(shù)為422135,EPC標準算法分別為121545,而GAAS算法僅為39601,比AAS算法標簽的開銷下降了96.1%,比ECP標準算法下降了67.4%.

4.3總時隙數(shù)分析

總時隙是決定系統(tǒng)效率的一個關(guān)鍵因素,總時隙數(shù)越少,系統(tǒng)的性能越好.從上面分析可知,整個算法分為兩個階段:時隙掃描階段和標簽識別階段,所以查詢總時隙也是這兩個階段消耗時隙之和.

對FSA-256算法、DFSA算法、GDFSA算法以及GAAS算法的總時隙數(shù)進行仿真,仿真結(jié)果如圖8所示.標簽數(shù)量從0變化到1500的過程中,FSA-256算法和DFSA算法所需要的總時隙數(shù)隨標簽數(shù)量的增加呈指數(shù)增長,GDFSA算法和GAAS算法呈線性增長,其中FSA-256算法增長速度最快,而GAAS算法最慢,其次是GDFSA算法.特別是當標簽數(shù)目較大時,GAAS算法的優(yōu)勢更加明顯.當標簽數(shù)目為1000時,GAAS算法只需要約1400個時隙,比FSA-256減少約4165,比DFSA減少約3727,比GDFS減少約1366.

4.4吞吐率分析

系統(tǒng)吞吐率也是衡量系統(tǒng)性能的一個重要指標.從圖9可以看出,當標簽少于354時,GDFSA與DFSA吞吐率相同,FSA-256算法最低,僅有0.2左右,而GAAS算法最高,可達0.7以上.GDFSA、DFSA、GAAS算法都能根據(jù)實際標簽數(shù)目,自適應(yīng)地分配有效時隙進行識別,而FSA-256算法采用固定幀長256.當標簽數(shù)大于354時,FSA-256、DFSA算法的吞吐率均急劇下降,而GDFSA、GAAS算法則將標簽分為多組,通過動態(tài)調(diào)整幀長對各組標簽進行識別,使得吞吐率穩(wěn)定在一定范圍內(nèi).本文算法的系統(tǒng)吞吐率比其他三種算法顯然要大得多,FSA-256算法的吞吐率在0.1～0.25之間,DFSA算法則在0.2～0.36之間,GDFSA算法僅維持在0.36左右,而GAAS算法比它們都要高.當標簽的數(shù)目達到1000時,與FSA-256和GDFSA相比,GAAS算法的系統(tǒng)效率分別提高了300%和97.2%.

5　結(jié)論

本文提出了一種分組自適應(yīng)分配時隙RFID防碰撞(GAAS)算法,通過對標簽數(shù)量的估計和分組、時隙預(yù)約以及自適應(yīng)分配時隙等策略對標簽進行快速識別.仿真結(jié)果表明,隨著標簽數(shù)量的不斷增加,特別是當標簽的數(shù)目超過1000時,GAAS算法的吞吐率維持在0.71以上,比基于ALOHA的傳統(tǒng)算法的吞吐率都較大幅度的提高,整個識別過程所需要的時隙總數(shù)和傳輸開銷幾乎保持了線性增加.能有效地提高RFID系統(tǒng)的工作效率,增加了系統(tǒng)吞吐率的穩(wěn)定性,降低了標簽的成本.針對于大量的標簽的識別,GAAS算法的優(yōu)勢尤為顯著,具有廣闊的應(yīng)用前景.

[1]Want R.An introduction to RFID technology[J].IEEE Pervasive Computing,2006,5(1):25-33.

[2]寧煥生,張瑜,劉芳麗,等.中國物聯(lián)網(wǎng)信息服務(wù)系統(tǒng)研究[J].電子學(xué)報,2006,34(12A):2514-2517.NING H S,ZHANG Y,LIU F L,et al.Research onchina internet of things’ services and management[J].Acta Electronica Sinica,2006,34(12A):2514-2517.(in Chinese)

[3]Hunt V D,Puglia A,Puglia M.RFID:A Guide to Radio Frequency Identification[M].New Jersey:John Wiley & Sons,2007.

[4]Yoon W,Vaidya N H.RFID reader collision problem:performance analysis and medium access[J].Wireless Communications andMobile Computing,2012,12(5):420-430.

[5]李萌,錢志鴻,張旭,等.基于時隙預(yù)測的RFID防碰撞ALOHA算法[J].通信學(xué)報,2012,32(12):43-50.

Li Meng,Qian Zhi-hong,Zhang Xu,et al.Slot-predicting based ALOHA algorithm for RFID anti-collision[J].Journal on Communications,2012,32(12):43-50.(in Chinese)

[6]Wu H,Zeng Y.Bayesian tag estimate and optimal frame length for anti-collision ALOHA RFID system[J].IEEE Transactions on Automation Science and Engineering,2010,7(4):963-969.

[7]Deng D J,Tsao H W.Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J].Wireless Personal Communications,2011,59(1):109-122.

[8]Küpper A.Front Matter[M].New Jersey:John Wiley & Sons,Ltd,2005.

[9]Finkenzeller K.Example Applications[M].New Jersey:John Wiley & Sons,Ltd,2003.

[10]Crain T,Gramoli V,Raynal M.A speculation-friendly binary search tree[J].Acm Sigplan Notices,2012,47(8):161-170.

[11]王亞奇,蔣國平.基于分組機制的跳躍式動態(tài)二進制防碰撞算法[J].自動化學(xué)報,2010,36(10):1390-1400.

Wang Ya-qi,Jiang Guo-ping.Anti-collisionalgorithm based on grouping mechanism and jumping dynamic binary[J].Acta Automatica Sinica,2010,36(10):1390-1400.(in Chinese)

[12]Yang C N,He J Y.An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision[J].IEEE Communications Letters,2011,15(5):539-541.

[13]Liva G.Graph-based analysis and optimization of contention resolution diversity slotted ALOHA[J].IEEE Transactions on Communications,2011,59(2):477-487.

[14]Wu H,Zeng Y.Efficient framed slotted ALOHA protocol for RFID tag anti-collision[J].IEEE Transactions on Automation Science and Engineering,2011,8(3):581-588.

[15]Deng D J,Tsao H W.Optimaldynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J].Wireless Personal Communications,2011,59(1):109-122.

[16]Chien H Y,Chen C H.Mutual authentication protocol for RFID conforming to EPC Class-1 Generation-2 standards[J].Computer Standards & Interfaces,2007,29(2):254-259.

[17]Chen W T.Afeasible and easy-to-implement anti-collision algorithm for the EPC global UHF Class-1 Generation-2 RFID protocol[J].IEEE Transactions on Automation Science and Engineering,2014,11(2):485-491.

[18]張小紅,張留洋.RFID防碰撞時隙應(yīng)變協(xié)處理算法研究[J].電子學(xué)報,2013,42(6):1139-1146.

ZHANG Xiao-hong,ZHANG Liu-yang.Research on RFID anti-collision algorithm of slot responding in real-time and co-processing[J].Acta Electronica Sinica,2013,42(6):1139-1146.(in Chinese)

[19]龔冰青.一種433MHz有源RFID標簽的設(shè)計與實現(xiàn)[D].成都:電子科技大學(xué),2013.Gong Bing-qing.Desing and implementation of active RFID tag with 433MHZ[D].Chengdu:University of Electronic Science and Technology of China,2013.(in Chinese)

[20]Wang C Y,Lee C C,Lee M C.An enhanced dynamic framed slotted ALOHA anti-collision method for mobile RFID tag identification[J].Journal of Convergence Information Technology,2011,6(4):340-351.

[21]Lin C F,Lin F Y S.Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted ALOHA in RFID networks[J].IEEE Transactions on Automation Science and Engineering,2010,7(4):840-848.

[22]Park J,Chung M Y,Lee T J.Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection[J].IEEE Communications Letters,2007,11(5):452-454.

[23]龐宇,彭琦,林金朝,等.基于分組動態(tài)幀時隙的射頻識別防碰撞算法[J].物理學(xué)報,2013,62(14):148401-148401.Pang Yu,Peng Qi,Lin Jin-zhao,et al.Reducing tag collision in radio frequency identification systems by using a grouped dynamic frame slotted ALOHA algorithm[J].Acta Phys Sin,2013,62(14):148401-148401.(in Chinese)

[24]吳海鋒,曾玉.RFID 動態(tài)幀時隙 ALOHA 防沖突中的標簽估計和幀長確定[J].自動化學(xué)報,2010,36(4):620-624.Wu Hai-feng,Zeng Yu.Tagestimate and fame length for dynamic frame slotted ALOHA anti-collision RFID system[J].Acta Automatica Sinica,2010,36(4):620-624.(in Chinese)

[25]Eom J B,Lee T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Communications Letters,2010,14(1):60-62.

[26]Schoute F C.Dynamic frame length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[27]Chen W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J].IEEE Transactions on Automation Science and Engineering,2009,6(1):9-15.

[28]Cha J R,Kim J H.Novel anti-collision algorithms for fast object identification in RFID system[A].Proceedings ofthe 2005 Eleventh International Conference on Parallel and Distributed Systems[C].Fukuoka:IEEE,2005.63-67.

[29]Lee S R,Joo S D,Lee C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[A].Proceedings ofthe Second Annual International Conference on Mobile and Ubiquitous Systems:Networking and Services[C].California:IEEE,2005.166-172.

張小紅女,1966年8月出生,河北昌黎人,現(xiàn)為江西理工大學(xué)信息工程學(xué)院教授、博士、碩士生導(dǎo)師,研究方向:無線傳感器網(wǎng)絡(luò)、非線性動力學(xué)理論、混沌保密通信.

E-mail:xiaohongzh@263.net

胡應(yīng)夢男,1989年11月出生,湖南婁底人,現(xiàn)為江西理工大學(xué)信息工程學(xué)院碩士研究生,研究方向:RFID防碰撞算法、可信認證協(xié)議.

E-mail:huyingmeng89@163.com

Research on a Grouped Adaptive Allocating Slot Anti-collision Algorithm in RFID System

ZHANG Xiao-hong,HU Ying-meng

(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China)

Based on frame slotted ALOHA algorithm, a grouped adaptive allocating slots (GAAS) anti-collision algorithm is presented to solve the problem of collision between the reader and multi-tag in radio frequency identification(RFID) system. First, the reader needs to obtain the time slots chosen randomly by tags and send the results to each tag; then the tags rectify the time according to the instruction; moreover, the reader skips free and collision time slots, and adaptively distributes valid ones; finally, the tags are quickly recognized in GAAS. When the number of unidentified tags is very large, the tags are grouped and the frame sizes are adjusted dynamically to reduce the processing time. The simulation results show that GAAS has higher identification efficiency and stability, and lower cost of communication. Particularly, when the number of tags is over 1000，the throughput rate still maintains above 71%. Compared with the framed slotted ALOHA-256 algorithm and the grouped dynamic framed slotted ALOHA algorithm, the proposed algorithm enhances the system efficiency by 300% and 97.2% respectively.

RFID;ALOHA algorithm;tags grouping;throughput rate;adaptively allocating slots

2014-09-08;修回日期:2014-12-01;責(zé)任編輯:梅志強

國家自然科學(xué)基金(No.61363076,11062002);江西省自然科學(xué)基金(No.20142BAB207020);江西省教育廳科技項目(No.GJJ14465);江西省研究生創(chuàng)新專項資金(No.YC2014-S370)

TN911.23

A

0372-2112 (2016)06-1328-08