基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法

付 鈺,錢(qián)志鴻,孟 婕,王 雪

(1．吉林大學(xué)通信工程學(xué)院,吉林長(zhǎng)春 130012;2．中國(guó)電信股份有限公司北京分公司,北京100010)

?

基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法

付 鈺1,錢(qián)志鴻1,孟 婕2,王 雪1

(1．吉林大學(xué)通信工程學(xué)院,吉林長(zhǎng)春 130012;2．中國(guó)電信股份有限公司北京分公司,北京100010)

在射頻識(shí)別(Radio Frequency Identification,RFID)系統(tǒng)中,針對(duì)EPC C1G2協(xié)議的Q算法中Q值調(diào)整的不靈活性及對(duì)空閑時(shí)隙和碰撞時(shí)隙處理上的缺點(diǎn),提出了一種基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法.通過(guò)馬爾可夫時(shí)隙狀態(tài)模型,分析不同連續(xù)時(shí)隙狀態(tài)下幀長(zhǎng)與標(biāo)簽數(shù)的關(guān)系,提出連續(xù)時(shí)隙預(yù)測(cè)機(jī)制和自適應(yīng)散列方案.有效地減少了無(wú)效時(shí)隙的出現(xiàn),實(shí)現(xiàn)了讀取階段的時(shí)隙多數(shù)為成功時(shí)隙.仿真結(jié)果表明,本文提出的算法能夠靈活地調(diào)整幀長(zhǎng),有效提高吞吐率,降低傳輸延時(shí)和開(kāi)銷(xiāo),為物聯(lián)網(wǎng)(Internet of Things,IoT)的海量數(shù)據(jù)信息完整性問(wèn)題提供了合理的解決方案.

射頻識(shí)別;防碰撞算法;Aloha;時(shí)隙預(yù)測(cè)

1 引言

物聯(lián)網(wǎng)是一種新興網(wǎng)絡(luò)技術(shù),是信息化時(shí)代的重要發(fā)展階段,RFID(Radio Frequency Identification)作為物聯(lián)網(wǎng)底層網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一,對(duì)物聯(lián)網(wǎng)的發(fā)展起著至關(guān)重要的作用[1].RFID是一種新型的非接觸式自動(dòng)識(shí)別技術(shù),由于其具有低功耗、低成本、數(shù)據(jù)存儲(chǔ)容量大、多目標(biāo)識(shí)別等優(yōu)點(diǎn),已經(jīng)被廣泛地應(yīng)用于供應(yīng)鏈管理、工業(yè)控制、衛(wèi)生保健服務(wù)、智能交通、防偽等領(lǐng)域[2～5].

近些年來(lái),RFID標(biāo)簽防碰撞問(wèn)題引起了大量研究人員的關(guān)注.現(xiàn)有的防碰撞算法通常分為兩類(lèi):基于樹(shù)的確定性算法[6～9]和基于Aloha的概率性算法[10].基于樹(shù)的確定性算法包括查詢(xún)樹(shù)算法[11]、二進(jìn)制樹(shù)算法[12]、搜索樹(shù)算法[13]和碰撞樹(shù)算法[14,15]等.但基于樹(shù)的確定性算法需要識(shí)別查詢(xún)區(qū)域內(nèi)的所有標(biāo)簽,復(fù)雜度高且延時(shí)較長(zhǎng).而Aloha概率性算法不易受到標(biāo)簽ID位數(shù)的影響,更適用于如今的物聯(lián)網(wǎng)大數(shù)據(jù)信息采集應(yīng)用.典型的Aloha算法有純ALOHA(Pure Aloha,PA)算法、時(shí)隙ALOHA(Slotted Aloha,SA)算法、幀時(shí)隙Aloha (Framed-Slotted Aloha,FSA)算法和動(dòng)態(tài)幀時(shí)隙Aloha(Dynamic Framed-Slotted Aloha,DFSA)算法.PA算法[16]中標(biāo)簽將自身ID隨機(jī)發(fā)送給讀寫(xiě)器,然后等待響應(yīng),如果標(biāo)簽在發(fā)送信息的過(guò)程中其他的標(biāo)簽也在發(fā)送,那么可能導(dǎo)致部分碰撞或完全碰撞,系統(tǒng)吞吐率較低;為避免部分碰撞,SA算法將時(shí)間分成多個(gè)離散時(shí)隙,使標(biāo)簽在每個(gè)離散時(shí)隙的起始處同時(shí)傳送ID;FSA算法[17]在SA算法的基礎(chǔ)上,將多個(gè)時(shí)隙劃分為一幀,每個(gè)標(biāo)簽只在每一幀中響應(yīng)一次,若在當(dāng)前幀中發(fā)生碰撞,則在下一幀中重新選擇一個(gè)時(shí)隙,避免了標(biāo)簽頻繁發(fā)生碰撞;DFSA算法[18]是對(duì)FSA算法的改進(jìn),使幀長(zhǎng)盡可能地等于待讀標(biāo)簽數(shù).考慮到大量碰撞時(shí)隙和空閑時(shí)隙對(duì)系統(tǒng)效率的影響,研究人員還提出了不等長(zhǎng)的DFSA算法,通過(guò)時(shí)隙內(nèi)部機(jī)制,減少無(wú)效碰撞時(shí)隙和空閑時(shí)隙數(shù),使系統(tǒng)性能得到顯著改善,如EPC C1G2的Q算法[19].Q算法通過(guò)時(shí)隙內(nèi)的預(yù)測(cè)機(jī)制調(diào)整Q值,進(jìn)而達(dá)到調(diào)整幀長(zhǎng)的目的,但仍存在較多的碰撞時(shí)隙和空閑時(shí)隙.且每個(gè)時(shí)隙結(jié)束后都需要計(jì)算Q值和參數(shù)C,在大量標(biāo)簽的情況下會(huì)嚴(yán)重加劇讀寫(xiě)器運(yùn)算負(fù)擔(dān),并不適用于物聯(lián)網(wǎng)中的大數(shù)據(jù)環(huán)境.

針對(duì)上述不足,在現(xiàn)有的研究成果基礎(chǔ)上,提出了一種基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法,通過(guò)對(duì)連續(xù)空閑時(shí)隙和連續(xù)碰撞時(shí)隙的預(yù)測(cè)可加快跳過(guò)無(wú)效時(shí)隙.算法在大規(guī)模標(biāo)簽的情況下,仍保持較高的吞吐率,可穩(wěn)定在65%左右,與已有算法相比,本文所提算法在系統(tǒng)吞吐率、傳輸開(kāi)銷(xiāo)和傳輸時(shí)延都具有一定的優(yōu)越性.

2 改進(jìn)算法分析

2.1 幀長(zhǎng)調(diào)整方案

2.1.1 馬爾可夫時(shí)隙狀態(tài)模型

假設(shè)標(biāo)簽數(shù)為N,幀長(zhǎng)L=2Q.根據(jù)二項(xiàng)式分布定理,第r個(gè)時(shí)隙中有m個(gè)標(biāo)簽的概率為

(1)

r為空閑時(shí)隙的概率

(2)

r為成功時(shí)隙的概率

(3)

r為碰撞時(shí)隙的概率

PC=1-PI-PS

(4)

通過(guò)幀內(nèi)的成功、碰撞和空閑時(shí)隙數(shù)能動(dòng)態(tài)估計(jì)L與N的關(guān)系.如果出現(xiàn)多個(gè)碰撞時(shí)隙,說(shuō)明L較小.同理,如果有多個(gè)空閑時(shí)隙,則說(shuō)明L遠(yuǎn)大于N,時(shí)隙因?yàn)椤翱臻e”產(chǎn)生了浪費(fèi).在連續(xù)多個(gè)時(shí)隙碰撞或空閑的情況下需要調(diào)整幀長(zhǎng),其系統(tǒng)模型可用馬爾可夫鏈分析,如圖1所示.

設(shè)一幀中的第r個(gè)時(shí)隙,其中r∈[1,L],由于時(shí)隙狀態(tài)僅與狀態(tài)概率有關(guān),因此可用(2i+1)×1的矩陣A(r)表示時(shí)隙r的狀態(tài),

(5)

其中

(6)

AS表示成功時(shí)隙的概率;ACn表示當(dāng)前時(shí)隙為第n個(gè)連續(xù)碰撞時(shí)隙的概率,n∈[1,i];AIn表示當(dāng)前時(shí)隙為第n個(gè)連續(xù)空閑時(shí)隙的概率.根據(jù)當(dāng)前狀態(tài)與前一狀態(tài)概率和轉(zhuǎn)移概率有關(guān),因此得到時(shí)隙r+1的狀態(tài)A(r+1)

A(r+1)=TA(r)

(7)

其中T是一個(gè)(2i+1)×(2i+1)的轉(zhuǎn)移矩陣

(8)

2.1.2 時(shí)隙預(yù)測(cè)機(jī)制

為了動(dòng)態(tài)地分析多個(gè)連續(xù)時(shí)隙狀態(tài),馬爾可夫時(shí)隙狀態(tài)模型中需要預(yù)測(cè)當(dāng)前時(shí)隙之后的時(shí)隙狀態(tài),為此引入時(shí)隙預(yù)測(cè)機(jī)制.設(shè)時(shí)隙r中的標(biāo)簽數(shù)為m,可分為以下兩種情況:

當(dāng)m=1時(shí),標(biāo)簽被成功識(shí)別,讀寫(xiě)器發(fā)送Queryrep命令,標(biāo)簽置SC=SC-1.

當(dāng)m≠1時(shí),預(yù)測(cè)時(shí)隙r+1的狀態(tài),若時(shí)隙r+1與時(shí)隙r的狀態(tài)相同(碰撞或空閑),則繼續(xù)預(yù)測(cè)時(shí)隙r+2的狀態(tài),直到時(shí)隙狀態(tài)不同則預(yù)測(cè)結(jié)束.假設(shè)時(shí)隙r,r+1,…,r+n-1的狀態(tài)相同,即連續(xù)n個(gè)碰撞(或空閑)時(shí)隙,可表示為n-collision-slot(或n-idle-slot).

連續(xù)時(shí)隙預(yù)測(cè)機(jī)制中,n個(gè)時(shí)隙狀態(tài)標(biāo)簽響應(yīng)數(shù)據(jù)格式如下:

[RN16|SC=0]16+[RN16|SC=1]k+…+[RN16|SC=n]k

(9)

SC為0的標(biāo)簽響應(yīng)當(dāng)前時(shí)隙,返回完整的RN16,SC∈[1,n]的標(biāo)簽返回RN16前kbit.當(dāng)n>0時(shí),若預(yù)測(cè)結(jié)束,則讀寫(xiě)器發(fā)送Queryrep指令,標(biāo)簽置SC=SC-n.若識(shí)別幀的預(yù)測(cè)結(jié)束,那么無(wú)效時(shí)隙被跳過(guò),在附加幀識(shí)別碰撞標(biāo)簽.

2.1.3 幀長(zhǎng)調(diào)整方案

通過(guò)預(yù)測(cè)識(shí)別幀連續(xù)時(shí)隙的狀態(tài),即n-collision-slot或n-idle-slot,當(dāng)n值較小時(shí),說(shuō)明幀長(zhǎng)合理;當(dāng)n較大時(shí),則需要調(diào)整幀長(zhǎng).通過(guò)馬爾可夫時(shí)隙狀態(tài)模型分析不同幀長(zhǎng)與連續(xù)碰撞時(shí)隙和連續(xù)空閑時(shí)隙的關(guān)系.

不同幀長(zhǎng)與連續(xù)碰撞時(shí)隙概率關(guān)系如表1,當(dāng)L=0.75N時(shí)3-collision-slot發(fā)生的概率是0.0574,為小概率事件,在此認(rèn)為不可能發(fā)生事件;當(dāng)L=0.5N時(shí),3-collision-slot發(fā)生的概率是0.2125,該情況出現(xiàn)較為合理.因此預(yù)測(cè)到3-collision-slot時(shí),幀長(zhǎng)擴(kuò)大1倍.

不同幀長(zhǎng)與連續(xù)空閑時(shí)隙概率關(guān)系如表2,當(dāng)L=1.5N時(shí)4-idle-slot發(fā)生的概率是0.0650,屬于小概率事件;L分別為1.75N和2N時(shí),4-idle-slot發(fā)生的概率相應(yīng)為0.1017和0.1353,因此預(yù)測(cè)到4-idle-slot時(shí),幀長(zhǎng)減半.

表1 不同幀長(zhǎng)下連續(xù)碰撞時(shí)隙概率分布表

表2 不同幀長(zhǎng)下連續(xù)空閑時(shí)隙概率分布表

2.2 碰撞時(shí)隙處理

算法規(guī)定在每一幀結(jié)束后增加附加幀,幀長(zhǎng)與碰撞標(biāo)簽數(shù)相等.在附加幀中,讀寫(xiě)器通過(guò)自適應(yīng)散列方案對(duì)識(shí)別幀內(nèi)的標(biāo)簽進(jìn)一步識(shí)別,分配時(shí)隙,調(diào)整標(biāo)簽的SC值.

通常,調(diào)整幀長(zhǎng)時(shí)應(yīng)盡量接近待讀標(biāo)簽數(shù)量,由表1可知超過(guò)連續(xù)2個(gè)時(shí)隙發(fā)生碰撞的概率比較低,因此只考慮n-collision-slot (n=1或2)的情況.設(shè)時(shí)隙r為第q個(gè)碰撞時(shí)隙,q=q1+q2,其中qn表示識(shí)別幀內(nèi)直至?xí)r隙r出現(xiàn)時(shí)n-collision-slot的個(gè)數(shù).通過(guò)Schoute算法[20]對(duì)碰撞標(biāo)簽進(jìn)行估計(jì),由碰撞標(biāo)簽數(shù)等于2.39倍的碰撞時(shí)隙數(shù),得到碰撞標(biāo)簽數(shù)CT與qn關(guān)系如下:

(10)

在附加幀中,時(shí)隙r的碰撞標(biāo)簽分配時(shí)隙,加載SC值

(11)

其中remainingslot=2Q-r表示該幀的剩余時(shí)隙數(shù).

如果附加幀中再次發(fā)生碰撞,將采用二進(jìn)制散列機(jī)制.即碰撞標(biāo)簽的SC值隨機(jī)置“0”或“1”,待讀標(biāo)簽SC值加1.調(diào)整方式如下:

(12)

2.3 算法流程

為判斷時(shí)隙狀態(tài),用m表示一個(gè)時(shí)隙內(nèi)響應(yīng)標(biāo)簽數(shù).若m=0,沒(méi)有標(biāo)簽響應(yīng),該時(shí)隙為空閑時(shí)隙;若m=1,只有一個(gè)標(biāo)簽響應(yīng),該時(shí)隙為成功時(shí)隙,標(biāo)簽被識(shí)別后置為靜默狀態(tài),不再參與查詢(xún);若m>1,超過(guò)1個(gè)標(biāo)簽響應(yīng),該時(shí)隙為碰撞時(shí)隙.成功時(shí)隙為有效時(shí)隙,相應(yīng)地,碰撞時(shí)隙和空閑時(shí)隙統(tǒng)稱(chēng)為無(wú)效時(shí)隙.

本文所提算法描述如下:

算法1 基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法

①初始化,令Q=4.

②讀寫(xiě)器發(fā)送Query(Q)指令,向所有標(biāo)簽發(fā)送Q值,各標(biāo)簽加載SC值,SC∈[0,2Q-1].

③判斷該識(shí)別幀是否結(jié)束,若結(jié)束則轉(zhuǎn)向⑦,否則,SC為0的標(biāo)簽響應(yīng),按式(9)向讀寫(xiě)器返回相應(yīng)數(shù)據(jù).讀寫(xiě)器根據(jù)響應(yīng)標(biāo)簽判斷時(shí)隙狀態(tài).若該時(shí)隙發(fā)生碰撞或空閑,則順序執(zhí)行④;若該時(shí)隙為成功時(shí)隙,則標(biāo)簽識(shí)別后置為靜默狀態(tài),其余標(biāo)簽置SC=SC-1,返回③.

④判斷該識(shí)別幀是否結(jié)束,若結(jié)束則轉(zhuǎn)向⑦,否則,SC為1的標(biāo)簽響應(yīng),按式(9)返回相應(yīng)數(shù)據(jù).然后讀寫(xiě)器判斷時(shí)隙狀態(tài).若至該時(shí)隙只出現(xiàn)1-collision-slot,根據(jù)自適應(yīng)散列機(jī)制加載SC值,碰撞標(biāo)簽將在附加幀中進(jìn)一步識(shí)別,其余標(biāo)簽置SC=SC-1,返回③;若至該時(shí)隙只出現(xiàn)1-idle-slot,標(biāo)簽置SC=SC-1,返回③;若至該時(shí)隙出現(xiàn)2-collision-slot或2-idle-slot,則順序執(zhí)行⑤.

⑤判斷該識(shí)別幀是否結(jié)束,若結(jié)束則轉(zhuǎn)向⑦,否則,SC為2的標(biāo)簽響應(yīng),按式(9)返回相應(yīng)數(shù)據(jù).然后讀寫(xiě)器判斷時(shí)隙狀態(tài).若至該時(shí)隙只出現(xiàn)2-collision-slot,根據(jù)自適應(yīng)散列方案加載SC值,碰撞標(biāo)簽將在附加幀中進(jìn)一步識(shí)別,其余標(biāo)簽置SC=SC-2,返回③;若至該時(shí)隙只出現(xiàn)2-idle-slot,標(biāo)簽置SC=SC-2,返回③;若至該時(shí)隙出現(xiàn)3-collision-slot,則Q++,讀寫(xiě)器執(zhí)行QueryAdjust指令,返回②;若至該時(shí)隙出現(xiàn)3-idle-slot,則順序執(zhí)行⑥.

⑥識(shí)別幀是否結(jié)束,若結(jié)束則轉(zhuǎn)向⑦,否則,SC為3的標(biāo)簽響應(yīng),按式(9)返回相應(yīng)數(shù)據(jù).若至該時(shí)隙出現(xiàn)3-idle-slot,其余標(biāo)簽置SC=SC-3;返回③;若至該時(shí)隙出現(xiàn)4-idle-slot,則Q--,讀寫(xiě)器執(zhí)行QueryAdjust指令,返回②.

⑦若附加幀沒(méi)有標(biāo)簽需要識(shí)別,則算法結(jié)束.否則,順序識(shí)別附加幀內(nèi)的標(biāo)簽,SC為0的標(biāo)簽響應(yīng)并發(fā)送[RN16|SC=0]16,當(dāng)m=0或1時(shí),其余標(biāo)簽置SC=SC-1,返回⑦;當(dāng)m>1時(shí),標(biāo)簽采用二進(jìn)制散列機(jī)制重新加載SC,返回⑦.

3 仿真實(shí)驗(yàn)

3.1 幀長(zhǎng)調(diào)整

為提高系統(tǒng)識(shí)別效率,幀長(zhǎng)L應(yīng)盡量接近待讀標(biāo)簽數(shù).當(dāng)標(biāo)簽數(shù)在[100,3000]內(nèi)變化,分別用連續(xù)時(shí)隙預(yù)測(cè)機(jī)制和經(jīng)驗(yàn)C機(jī)制(C=0.8/Q)對(duì)幀長(zhǎng)進(jìn)行調(diào)整.

設(shè)Q的初值為4,圖2為最佳Q值大于Q時(shí),兩種機(jī)制調(diào)整到最優(yōu)幀長(zhǎng)的碰撞時(shí)隙.由于標(biāo)簽數(shù)在一定區(qū)間內(nèi)的最佳Q值相同,隨著標(biāo)簽數(shù)量的增多,出現(xiàn)碰撞時(shí)隙的概率增大,空閑時(shí)隙的概率減小.新出現(xiàn)的空閑時(shí)隙會(huì)使Q值增加的速度減慢,從而需要更多的碰撞時(shí)隙才能調(diào)整到最佳Q值.因此在最佳Q值變化的臨界值處,所需的碰撞時(shí)隙數(shù)會(huì)迅速變化,導(dǎo)致圖7中的曲線(xiàn)呈折線(xiàn)形.顯然,本文所提的機(jī)制比經(jīng)驗(yàn)C機(jī)制所需的碰撞時(shí)隙數(shù)少,且?guī)L(zhǎng)調(diào)整速度快.

設(shè)Q的初值為13,圖3為最佳Q值小于Q時(shí),兩種機(jī)制調(diào)整到最優(yōu)幀長(zhǎng)所需的空閑時(shí)隙.圖3的曲線(xiàn)也呈折線(xiàn)形,原理與圖2相同,但趨勢(shì)截然相反,在對(duì)應(yīng)相同的最佳Q值區(qū)間內(nèi),標(biāo)簽數(shù)量越多,出現(xiàn)空閑時(shí)隙的概率越小,碰撞時(shí)隙的概率越大.因此,隨著標(biāo)簽數(shù)量的增多,最佳Q值減小,空閑時(shí)隙減少.本文所提的機(jī)制比經(jīng)驗(yàn)C機(jī)制調(diào)整幀長(zhǎng)到最優(yōu)時(shí)所需的空閑時(shí)隙更少.對(duì)于相同的最佳Q值,標(biāo)簽數(shù)越多,所需的空閑時(shí)隙數(shù)越少.

在大規(guī)模標(biāo)簽情況下,采取經(jīng)驗(yàn)C機(jī)制調(diào)整幀長(zhǎng)需要多次累加參數(shù)C,導(dǎo)致浪費(fèi)多個(gè)無(wú)效時(shí)隙,系統(tǒng)效率降低.而本文的連續(xù)時(shí)隙預(yù)測(cè)機(jī)制,可以加速跳過(guò)無(wú)效時(shí)隙,本文所提算法在幀長(zhǎng)調(diào)整方式方面性能更優(yōu).

3.2 傳輸開(kāi)銷(xiāo)

設(shè)標(biāo)簽數(shù)量在區(qū)間[100,3000]內(nèi)變化,將本文算法和EPC標(biāo)準(zhǔn)中算法的傳輸開(kāi)銷(xiāo)進(jìn)行比較.如圖4所示,當(dāng)N=3000時(shí)讀寫(xiě)器開(kāi)銷(xiāo)比標(biāo)準(zhǔn)算法下降了11.6%.這是由于預(yù)測(cè)機(jī)制可以對(duì)連續(xù)碰撞時(shí)隙和連續(xù)空閑時(shí)隙加速跳過(guò),減少了讀寫(xiě)器開(kāi)銷(xiāo).同時(shí)附加幀內(nèi)的標(biāo)簽散列比識(shí)別幀的散列更為均勻,讀寫(xiě)器成功識(shí)別標(biāo)簽的概率更大.隨著標(biāo)簽數(shù)量的逐漸增多,本文的算法優(yōu)勢(shì)更加明顯.

如圖5所示,當(dāng)N=3000時(shí),本文提出的算法在k=1時(shí),比標(biāo)準(zhǔn)中算法降低了63.27%.這是因?yàn)槭褂眠B續(xù)時(shí)隙預(yù)測(cè)機(jī)制,讀寫(xiě)器并未增加額外的傳輸開(kāi)銷(xiāo),而是隨著總時(shí)隙數(shù)的遞減使發(fā)送的比特?cái)?shù)減少.進(jìn)行預(yù)測(cè)時(shí)標(biāo)簽返回RN16的前kbit,k每增加1bit,標(biāo)簽的總傳輸開(kāi)銷(xiāo)會(huì)增加,因此標(biāo)簽開(kāi)銷(xiāo)隨k的增加呈上升趨勢(shì).當(dāng)k分別等于2、3和4時(shí),標(biāo)簽的傳輸開(kāi)銷(xiāo)相應(yīng)為76446.4bit、82762.5bit、89750.8bit.

3.3 傳輸時(shí)延與吞吐率

標(biāo)簽數(shù)量從[100,3000]內(nèi)變化,將本文提出的算法的傳輸時(shí)延和吞吐率與幾種經(jīng)典ALOHA算法相比,初始幀長(zhǎng)512.FSA算法幀長(zhǎng)分別取512和1024,本文算法和FSA-DS算法中初值Q=4.

圖6所示為幾種算法識(shí)別標(biāo)簽的傳輸時(shí)延比較.隨著標(biāo)簽數(shù)量的增加,FSA算法性能急劇下降,傳輸時(shí)延最大;FSA-DS算法[21]根據(jù)標(biāo)簽數(shù)能有效的調(diào)整幀長(zhǎng),但仍需要較多的時(shí)隙;而本文所提算法通過(guò)連續(xù)時(shí)隙預(yù)測(cè)機(jī)制,進(jìn)一步減少了無(wú)效時(shí)隙的分配,因此所用時(shí)隙最少.當(dāng)N=3000時(shí)FSA-DS算法所用時(shí)隙達(dá)5275,而本文所提算法只需4614,相比FSA-DS算法降低了12.53%.

圖7所示,FSA算法在標(biāo)簽數(shù)與幀長(zhǎng)相等時(shí),吞吐率最高,達(dá)到36.8%.DFSA算法在標(biāo)簽數(shù)小于512時(shí),多數(shù)標(biāo)簽在預(yù)估計(jì)階段可以被成功識(shí)別,因此與FSA算法吞吐率基本一致;在標(biāo)簽數(shù)大于512時(shí),由于幀長(zhǎng)調(diào)整機(jī)制發(fā)揮作用,使理想情況下的吞吐率約為36.8%左右.FSA-DS算法具有較高的吞吐率,穩(wěn)定地保持在53.1%以上.以FSA-DS算法為基礎(chǔ),本文所提算法進(jìn)一步減少了無(wú)效時(shí)隙數(shù),并加入了自適應(yīng)散列,使得系統(tǒng)吞吐率性能最優(yōu),保持在60%以上.

4 結(jié)論

本文以協(xié)議EPC C1G2為基礎(chǔ),針對(duì)協(xié)議中原始算法Q值調(diào)整不靈活、標(biāo)簽散列隨機(jī)性大等不足,提出了一種基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙ALOHA防碰撞算法.結(jié)合馬爾可夫時(shí)隙狀態(tài)模型,分析不同連續(xù)時(shí)隙狀態(tài)下幀長(zhǎng)與標(biāo)簽數(shù)的關(guān)系,提出連續(xù)時(shí)隙預(yù)測(cè)機(jī)制和自適應(yīng)散列方案,對(duì)空閑和碰撞時(shí)隙加速跳過(guò),有效地減少了無(wú)效時(shí)隙的出現(xiàn).仿真結(jié)果顯示,本文提出的算法降低了傳輸時(shí)延,具有較高的系統(tǒng)吞吐率,為物聯(lián)網(wǎng)中海量數(shù)據(jù)的信息完整性問(wèn)題提供了有效保障.

[1]錢(qián)志鴻,王義君.物聯(lián)網(wǎng)技術(shù)與應(yīng)用研究[J].電子學(xué)報(bào),2012,40(5):1023-1029.

QIAN Zhi-hong,WANG Yi-jun.IoT technology and application[J].Acta Electronica Sinica,2012,40(5):1023-1029.(in Chinese)

[2]Zhu W,Cao J,Chan H,et al.Mobile RFID with a high identification rate[J].IEEE Transactions on Computers,2014,63(7):1778-1792.

[3]Vahedi E,Ward R K,Blake I F.Performance analysis of RFID protocols:CDMA versus the standard EPC Gen-2[J].IEEE Transactions on Automation Science and Engineering,2014,11(4):1250-1261.

[4]宋建華,郭亞軍,韓蘭勝,等.自調(diào)整混合樹(shù)RFID多標(biāo)簽防碰撞算法[J].電子學(xué)報(bào),2013,42(4):685-689.

SONG Jian-hua,GUO Ya-jun,HAN Lan-sheng,et al.An adjustive hybrid tree anti-collision algorithm for RFID multi-tag identification[J].Acta Electronica Sinica,2013,42(4):685-689.(in Chinese)

[5]Zhihong Q,Xue W.An overview of anti-collision protocols for radio frequency identification devices[J].China Communications,2014,11(11):44-59.

[6]王雪,錢(qián)志鴻,胡正超,等.基于二叉樹(shù)的RFID防碰撞算法的研究[J].通信學(xué)報(bào),2010,31(6):49-57.

WANG Xue,QIAN Zhi-hong,HU Zheng-chao.Research on RFID anti-collision algorithms based on binary tree[J].Journal on Communications,2010,31(6):49-57.(in Chinese)

[7]張學(xué)軍,蔡文琦,王鎖萍.改進(jìn)型自適應(yīng)多叉樹(shù)防碰撞算法研究[J].電子學(xué)報(bào),2012,40(1):193-198.

ZHANG Xue-jun,CAI Wen-qi,WANG Suo-ping.One anti-collision algorithm based on improved adaptive multi-tree search[J].Acta Electronica Sinica,2012,40(1):193-198.(in Chinese)

[8]Lai Y C,Hsiao L Y,Chen H J,et al.A novel query tree protocol with bit tracking in RFID tag identification[J].IEEE Transactions on Mobile Computing,2013,12(10):2063-2075.

[9]Liu X,Qian Z,Zhao Y,et al.An adaptive tag anti-collision protocol in RFID wireless systems[J].China Communications,2014,11(7):117-127.

[10]陳毅紅,馮全源.按需時(shí)隙分配RFID防碰撞協(xié)議研究[J].電子學(xué)報(bào),2014,42(2):377-382.

CHEN Yi-hong,FENG Quan-yuan.An on-demand slot assignment anti-collision protocol for RFID system[J].Acta Electronica Sinica,2014,42(2):377-382.(in Chinese)

[11]Hush D R,Wood C.Analysis of tree algorithms for RFID arbitration[A].Proceedings of 1998 IEEE International Symposium on Information Theory[C].Cambridge,USA:IEEE,1998.107-107.

[12]Law C,Lee K,Siu K Y.Efficient memoryless protocol for tag identification[A].Proceedings of 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications[C].New York,USA:ACM,2000.75-84.

[13]Klaus F.RFID Handbook:Fundamentals and Applications in Contactless Smart Cards and Identification[M].New York:John Wiley & Sons Ltd,2003.

[14]Jia X,Feng Q,Ma C.An efficient anti-collision protocol for RFID tag identification[J].IEEE Communications Letters,2010,14(11):1014-1016.

[15]Jia X,Feng Q,Yu L.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications,2012,60(8):2285-2294.

[16]Abramson N.The ALOHA system:another alternative for computer communications[A].Proceedings of Joint Computer Conference[C].New York,USA:ACM,1970.281-285.

[17]Kim S C,Cho J S,Kim S K.Performance improvement of hybrid tag anti-collision protocol for radio frequency identification systems[J].International Journal of Communication Systems,2013,26(6):705-719.

[18]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.

[19]張小紅,張留洋.RFID防碰撞時(shí)隙應(yīng)變協(xié)處理算法研究[J].電子學(xué)報(bào),2014,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,2014,42(6):1139-1146.(in Chinese)

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

[21]李萌,錢(qián)志鴻,張旭,等.基于時(shí)隙預(yù)測(cè)的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)

付 鈺 女,1990年生于吉林省吉林市.現(xiàn)為吉林大學(xué)通信工程學(xué)院博士研究生.主要研究方向?yàn)镽FID和物聯(lián)網(wǎng).

E-mail:fuyu-only@163.com

錢(qián)志鴻(通信作者) 男,1957年生于吉林長(zhǎng)春.現(xiàn)為吉林大學(xué)教授、博士生導(dǎo)師.主要研究方向?yàn)槲锫?lián)網(wǎng)、RFID、WIFI、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)和無(wú)線(xiàn)定位等.

E-mail:dr.qzh@163.com

FSA Anti-collision Algorithm Based on Continuous Slot Prediction

FU Yu1,QIAN Zhi-hong1,MENG Jie2,WANG Xue1

(1.CollegeofCommunicationEngineering,JilinUniversity,Changchun,Jilin130012,China;2.ChinaTelecomCoBeijingBranch,Beijing100010,China)

In the RFID (Radio Frequency Identification,RFID) system,due to inflexibility ofQvalue adjustment and weaknesses of the idle slots and collision slots processing withinQalgorithm of EPC C1G2 protocol,this paper proposes FSA(Framed-Slotted Aloha,FSA) anti-collision algorithm based on continuous slot prediction.The proposed algorithm analyzes the relationship between frame length and the number of tags in different continuous slots status based on Markov slot status model.Continuous slot prediction mechanism and adaptive hashing scheme are proposed to implement that the time slots in read phase are mostly success slots,which effectively reducing invalid slots occur.Simulation results show that the proposed algorithm can flexibly adjust the frame size,improve throughput and reduce transmission delay and overhead,which provides a reasonable solution to integrity problems of massive data in the IoT (Internet of Things,IoT).

radio frequency identification (RFID);anti-collision algorithm;Aloha;slot prediction

2015-01-22;

2015-04-25;責(zé)任編輯:覃懷銀

國(guó)家自然科學(xué)基金(No. 61371092)；吉林省和長(zhǎng)春市科技攻關(guān)項(xiàng)目(No. 20140204019GX, No. 20150101050JC, No. 2014026, No. 16SS02) ; 吉林大學(xué)研究生創(chuàng)新基金資助項(xiàng)目(No. 2016091)

TN92

A

0372-2112 (2016)09-2081-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.009