付 鈺,錢志鴻,孟 婕,王 雪

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

?

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

付 鈺1,錢志鴻1,孟 婕2,王 雪1

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

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

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

1 引言

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

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

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

2 改進算法分析

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

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

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

(1)

r為空閑時隙的概率

(2)

r為成功時隙的概率

(3)

r為碰撞時隙的概率

PC=1-PI-PS

(4)

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

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

(5)

其中

(6)

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

A(r+1)=TA(r)

(7)

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

(8)

2.1.2 時隙預(yù)測機制

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

當m=1時,標簽被成功識別,讀寫器發(fā)送Queryrep命令,標簽置SC=SC-1.

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

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

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

(9)

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

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

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

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

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

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

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

2.2 碰撞時隙處理

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

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

(10)

在附加幀中,時隙r的碰撞標簽分配時隙,加載SC值

(11)

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

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

(12)

2.3 算法流程

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

本文所提算法描述如下:

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

①初始化,令Q=4.

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

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

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

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

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

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

3 仿真實驗

3.1 幀長調(diào)整

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

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

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

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

3.2 傳輸開銷

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

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

3.3 傳輸時延與吞吐率

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

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

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

4 結(jié)論

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

[1]錢志鴻,王義君.物聯(lián)網(wǎng)技術(shù)與應(yīng)用研究[J].電子學(xué)報,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)整混合樹RFID多標簽防碰撞算法[J].電子學(xué)報,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]王雪,錢志鴻,胡正超,等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報,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é)軍,蔡文琦,王鎖萍.改進型自適應(yīng)多叉樹防碰撞算法研究[J].電子學(xué)報,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]陳毅紅,馮全源.按需時隙分配RFID防碰撞協(xié)議研究[J].電子學(xué)報,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防碰撞時隙應(yīng)變協(xié)處理算法研究[J].電子學(xué)報,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]李萌,錢志鴻,張旭,等.基于時隙預(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)

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

E-mail:fuyu-only@163.com

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

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;責任編輯:覃懷銀

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

TN92

A

0372-2112 (2016)09-2081-06

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

10.3969/j.issn.0372-2112.2016.09.009