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

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

?

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

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

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

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

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

1　引言

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

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

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

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

2　GAAS算法描述

2.1基本定義

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

(1)

當(dāng)r=0,即一個(gè)時(shí)隙里沒有請(qǐng)求識(shí)別標(biāo)簽,該時(shí)隙稱為空閑(idle)時(shí)隙,其概率為:

(2)

當(dāng)r=1,即一個(gè)時(shí)隙里只有一個(gè)標(biāo)簽請(qǐng)求識(shí)別標(biāo)簽,該時(shí)隙稱為成功(success)時(shí)隙,其概率為:

(3)

當(dāng)r≥2,即一個(gè)時(shí)隙里有兩個(gè)及以上的標(biāo)簽請(qǐng)求識(shí)別標(biāo)簽,該時(shí)隙稱為碰撞(collision)時(shí)隙,其概率為:

Pc=1-Ps-Pi

(4)

(5)

(6)

(7)

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

(8)

2.2標(biāo)簽數(shù)目估計(jì)

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

(9)

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

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

(10)

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

(11)

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

(12)

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

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

(13)

(14)

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

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

2.4標(biāo)簽分組原理

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

(15)

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

(16)

(17)

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

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

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

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

2.5.1GAAS算法約定

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

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

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

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

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

2.5.2GAAS防碰撞協(xié)議

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

(1)標(biāo)簽數(shù)目估計(jì)及分組階段

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

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

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

④初始化當(dāng)前識(shí)別的組編號(hào)t=1,開始對(duì)第t組進(jìn)行識(shí)別.

(2)時(shí)隙處理階段

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

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

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

(3)標(biāo)簽識(shí)別階段

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

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

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

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

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

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

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

3　算法對(duì)比分析

3.1DFSA算法分析

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

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

3.2GAAS算法分析

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

表3　時(shí)隙掃描過程中時(shí)隙的選擇情況

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

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

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

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

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

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

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

4　算法性能分析

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

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

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

4.2傳輸開銷分析

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

4.2.1閱讀器的開銷

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

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

4.2.2標(biāo)簽的開銷

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

4.3總時(shí)隙數(shù)分析

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

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

4.4吞吐率分析

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

5　結(jié)論

本文提出了一種分組自適應(yīng)分配時(shí)隙RFID防碰撞(GAAS)算法,通過對(duì)標(biāo)簽數(shù)量的估計(jì)和分組、時(shí)隙預(yù)約以及自適應(yīng)分配時(shí)隙等策略對(duì)標(biāo)簽進(jìn)行快速識(shí)別.仿真結(jié)果表明,隨著標(biāo)簽數(shù)量的不斷增加,特別是當(dāng)標(biāo)簽的數(shù)目超過1000時(shí),GAAS算法的吞吐率維持在0.71以上,比基于ALOHA的傳統(tǒng)算法的吞吐率都較大幅度的提高,整個(gè)識(shí)別過程所需要的時(shí)隙總數(shù)和傳輸開銷幾乎保持了線性增加.能有效地提高RFID系統(tǒng)的工作效率,增加了系統(tǒng)吞吐率的穩(wěn)定性,降低了標(biāo)簽的成本.針對(duì)于大量的標(biāo)簽的識(shí)別,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é)報(bào),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]李萌,錢志鴻,張旭,等.基于時(shí)隙預(yù)測的RFID防碰撞ALOHA算法[J].通信學(xué)報(bào),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]王亞奇,蔣國平.基于分組機(jī)制的跳躍式動(dòng)態(tài)二進(jìn)制防碰撞算法[J].自動(dòng)化學(xué)報(bào),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防碰撞時(shí)隙應(yīng)變協(xié)處理算法研究[J].電子學(xué)報(bào),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標(biāo)簽的設(shè)計(jì)與實(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]龐宇,彭琦,林金朝,等.基于分組動(dòng)態(tài)幀時(shí)隙的射頻識(shí)別防碰撞算法[J].物理學(xué)報(bào),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 動(dòng)態(tài)幀時(shí)隙 ALOHA 防沖突中的標(biāo)簽估計(jì)和幀長確定[J].自動(dòng)化學(xué)報(bào),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ò)、非線性動(dòng)力學(xué)理論、混沌保密通信.

E-mail:xiaohongzh@263.net

胡應(yīng)夢(mèng)男,1989年11月出生,湖南婁底人,現(xiàn)為江西理工大學(xué)信息工程學(xué)院碩士研究生,研究方向:RFID防碰撞算法、可信認(rèn)證協(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é)任編輯:梅志強(qiáng)

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

TN911.23

A

0372-2112 (2016)06-1328-08