無源RFID自適應(yīng)幀時隙防碰撞算法研究

張小紅,張留洋2,

(1.江西理工大學(xué)信息工程學(xué)院,江西贛州341000;2.北京航空航天大學(xué)電子信息工程學(xué)院,北京100191)

?

無源RFID自適應(yīng)幀時隙防碰撞算法研究

張小紅1,張留洋2,1

(1.江西理工大學(xué)信息工程學(xué)院,江西贛州341000;2.北京航空航天大學(xué)電子信息工程學(xué)院,北京100191)

射頻識別RFID作為一種重要的物聯(lián)網(wǎng)終端數(shù)據(jù)采集技術(shù),系統(tǒng)的吞吐率直接影響著數(shù)據(jù)采集終端的性能,但目前廣泛應(yīng)用于無源RFID系統(tǒng)的幀時隙類防碰撞算法吞吐率普遍較低.本文著重分析了影響無源RFID幀時隙類ALOHA防碰撞算法性能兩類因素:幀長和碰撞時隙的處理方式,通過構(gòu)建和求解幀長調(diào)整和標(biāo)簽碰撞的數(shù)學(xué)模型,給出了無源RFID幀時隙類ALOHA防碰撞算法的具體優(yōu)化途徑和方案:幀長自適應(yīng)調(diào)整和碰撞實時散列.在此基礎(chǔ)上提出了自適應(yīng)二進制散列幀時隙ALOHA防碰撞算法—ABSFSA.實驗結(jié)果表明ABSFSA算法在同等條件下可以有效減少無效時隙,明顯將RFID系統(tǒng)的吞吐率穩(wěn)定提高到45%.本文的研究工作為無源RFID幀時隙類防碰撞算法的優(yōu)化提供了可供參考的數(shù)學(xué)模型,同時對提升物聯(lián)網(wǎng)數(shù)據(jù)采集終端的性能具有一定的應(yīng)用價值.

射頻識別;ALOHA防碰撞算法;幀長自適應(yīng)調(diào)整;二進制散列機制;標(biāo)簽估計函數(shù)

1 引言

射頻識別(Radio Frequency Identification,RFID)技術(shù)是一種利用射頻信號和空間耦合的傳輸特性,在讀寫器和標(biāo)簽之間進行雙向通信的非接觸式自動識別技術(shù).與條碼和二維碼技術(shù)相比,具有多標(biāo)簽識別能力、非視距讀取、讀取速度快、存儲容量大、安全性高等優(yōu)點[1].物聯(lián)網(wǎng)被世界公認為是繼計算機、互聯(lián)網(wǎng)與移動通信網(wǎng)之后的世界信息產(chǎn)業(yè)第三次浪潮[2],RFID技術(shù)作為物聯(lián)網(wǎng)的一種終端數(shù)據(jù)采集技術(shù),現(xiàn)已在第二代居民身份證、校園卡公交卡系統(tǒng)、小區(qū)門禁系統(tǒng)、田徑賽事計時系統(tǒng)、物流供應(yīng)鏈管理、畜牧管理、高速公路不停車收費系統(tǒng)等方面得到了應(yīng)用[2],隨著RFID系統(tǒng)中讀寫器和標(biāo)簽技術(shù)的進步和發(fā)展,RFID技術(shù)的應(yīng)用將會越來越廣泛.

RFID系統(tǒng)一般由附著在物品上的標(biāo)簽、讀寫器和數(shù)據(jù)庫組成.當(dāng)無源(內(nèi)部沒有電源供應(yīng))標(biāo)簽進入到讀寫器的讀寫區(qū)域時,標(biāo)簽從電磁場中獲取能量,按照一定的數(shù)據(jù)交換協(xié)議獲取標(biāo)簽的ID,完成對標(biāo)簽的識別.RFID系統(tǒng)中一般存在多個讀寫器和大量的標(biāo)簽,讀寫器與讀寫器、讀寫器與標(biāo)簽之間的通信通常是在單一信道上進行,讀寫器和標(biāo)簽隨機占用信道造成信號混疊,致使彼此都不能正確獲取信息,即在復(fù)雜的RFID系統(tǒng)中一般存在著兩種形式的碰撞:讀寫器碰撞和標(biāo)簽碰撞.由于讀寫器屬于有電源供應(yīng)的系統(tǒng),能夠監(jiān)測信道的占用情況,因此可以很好地解決讀寫器碰撞.本文討論的重點是標(biāo)簽碰撞問題.

2 制約RFID標(biāo)簽防碰撞算法性能的因素

標(biāo)簽防碰撞算法主要解決如何快速從大量標(biāo)簽中選取一個標(biāo)簽與之通信,并在盡量短的時間內(nèi)完成對所有標(biāo)簽的識別.在RFID系統(tǒng)中,由于無源標(biāo)簽低成本性的限制,標(biāo)簽本身不能主動探測信道占用情況,因此無法避免碰撞;而且標(biāo)簽結(jié)構(gòu)較為簡單,計算能力和存儲能力有限,成熟的防碰撞算法無法直接應(yīng)用.現(xiàn)有的RFID防碰撞算法一般采用時分多路(TDMA)技術(shù)解決標(biāo)簽碰撞問題[3,4],一般分為樹形算法和概率性算法.樹形算法通過讓發(fā)生碰撞的標(biāo)簽不斷地分為左右兩個子集,直到每個子集下只有一個標(biāo)簽來解決標(biāo)簽碰撞,二進制搜索算法[5]、動態(tài)二進制搜索算法[6]、查詢樹算法等都屬此類;概率性算法,通過讓標(biāo)簽在規(guī)定的一段時間內(nèi)隨機選擇一個時刻接入信道來解決標(biāo)簽碰撞,常用的概率性算法有時隙ALOHA(SA)算法、幀時隙ALOHA(FSA)算法[7]、動態(tài)幀時隙(DFSA)算法[8]、增強型動態(tài)幀時隙(EDFSA)算法[9～11]和Q值時隙ALOHA(QSA)算法等.RFID系統(tǒng)防碰撞算法性能一般用系統(tǒng)吞吐率來衡量,定義為成功識別標(biāo)簽數(shù)與識別完這些標(biāo)簽所用時隙數(shù)的比值.

RFID系統(tǒng)防碰撞算法的性能除了受標(biāo)簽硬件限制外,還受算法本身效率的約束.純ALOHA算法的理論吞吐率在18.4%左右;通過改進算法,讓標(biāo)簽在讀寫器規(guī)定的時刻響應(yīng),SA算法和FSA算法的理論吞吐率提高到約36.8%;DFSA算法根據(jù)上一幀標(biāo)簽的響應(yīng)情況,通過動態(tài)調(diào)整FSA算法幀長的方法,使得DFSA算法的系統(tǒng)吞吐率比FSA算法略有提升;除純ALOHA算法和SA算法外,FSA算法、DFSA算法和QSA算法都可以歸為幀時隙類ALOHA防碰撞算法,它們的共同點是:將一段時間劃分為若干個時隙,讓所有等待被識別的標(biāo)簽隨機選擇一個時隙響應(yīng),因此它們的算法性能受到的限制因素和對算法進行優(yōu)化的手段也大致類似.

本文在分析RFID系統(tǒng)幀時隙類ALOHA防碰撞算法的基礎(chǔ)上,以FSA算法為例,著重分析了幀長和碰撞時隙的處理方式對幀時隙類ALOHA防碰撞算法系統(tǒng)吞吐率的影響.為了提高幀時隙類ALOHA算法系統(tǒng)吞吐率,本文構(gòu)建并求解了幀長調(diào)整和標(biāo)簽碰撞的數(shù)學(xué)模型,從理論上證明了自適應(yīng)調(diào)整幀長和碰撞標(biāo)簽實時二進制散列機制可以較大地提高幀時隙FSA算法的性能,提升RFID系統(tǒng)吞吐率.本文提出了自適應(yīng)二進制散列幀時隙ALOHA防碰撞算法—ABSFSA (Adaptive Binary Splitting Frame Slotted ALOHA algorithm,ABSFSA).ABSFSA算法綜合運用了自適應(yīng)調(diào)整幀長和實時二進制散列碰撞標(biāo)簽這兩類優(yōu)化手段,實驗結(jié)果表明ABSFSA算法在同等條件下可以明顯提高RFID系統(tǒng)吞吐率.

3 幀長自適應(yīng)調(diào)整模型

FSA防碰撞算法:讀寫器將一段時間劃分為N個時隙,將由N個時隙組成的時間長度稱為長度為N的幀.讀寫器與標(biāo)簽之間通過詢問-應(yīng)答的方式進行數(shù)據(jù)交換,讀寫器向標(biāo)簽發(fā)送查詢指令,所有收到指令的標(biāo)簽在N個時隙內(nèi)隨機選擇一個時隙響應(yīng)讀寫器的查詢指令.

當(dāng)標(biāo)簽數(shù)遠大于幀長時,多個標(biāo)簽在同一個時隙上響應(yīng)的概率增大,會出現(xiàn)較多碰撞時隙;當(dāng)幀長過大時又會出現(xiàn)較多空閑時隙,勢必影響RFID系統(tǒng)的吞吐率,因此幀時隙FSA算法的系統(tǒng)吞吐率一定與標(biāo)簽讀取過程中設(shè)置的幀長相關(guān).

3.1 標(biāo)簽數(shù)量與最佳幀長之間的關(guān)系

定理1 當(dāng)標(biāo)簽數(shù)量n一定時,存在幀長N使得FSA算法的系統(tǒng)吞吐率達到最大,標(biāo)簽數(shù)量n與最佳幀長Nopt之間的關(guān)系為:

Nopt=2∧[floor(log2n)+1],n∈N+

floor為向下取整函數(shù).

證明 假設(shè)當(dāng)前標(biāo)簽數(shù)量為n,幀長為N.每一個標(biāo)簽隨機在N個時隙中選擇一個時隙響應(yīng)讀寫器的查詢指令,則每個標(biāo)簽選擇某一個時隙的概率為1/N,于是某一個時隙被r個標(biāo)簽選擇的概率為:

所以在當(dāng)前幀上,成功時隙的期望值為:

根據(jù)RFID系統(tǒng)吞吐率的定義,當(dāng)前幀內(nèi)系統(tǒng)吞吐率η的期望值為:

(1)

由式(1)可知,影響系統(tǒng)吞吐率的主要因素為標(biāo)簽數(shù)量n和幀長N.求得當(dāng)標(biāo)簽數(shù)量為n,當(dāng)前幀內(nèi)最佳幀長為:

Nopt=n,n∈N+

(2)

即當(dāng)幀長N等于當(dāng)前幀上的標(biāo)簽數(shù)n時,FSA算法的系統(tǒng)吞吐率取得最大值:

(3)

由式(3),當(dāng)n>50,理想情況下FSA算法的系統(tǒng)吞吐率穩(wěn)定在36.8%左右.理想情況下幀長N的取值為正整數(shù),且只能取2的次冪.于是實際情況下最佳幀長N應(yīng)為:

Nopt=2∧[floor(log2n)+1],n∈N+

(4)

證畢.

實際情況下讀寫器無法預(yù)知讀寫區(qū)域內(nèi)標(biāo)簽的數(shù)量n.此時如何選擇合適的幀長使FSA算法保持一個較高的系統(tǒng)吞吐率是一個具有挑戰(zhàn)性的問題[12～14].

3.2 標(biāo)簽估計函數(shù)的構(gòu)造與自適應(yīng)調(diào)整實現(xiàn)

利用由樣本估計總體的方法,構(gòu)造標(biāo)簽估計函數(shù),在兼顧估計準(zhǔn)確度和幀長調(diào)整靈敏度的同時,優(yōu)化估計讀寫器范圍內(nèi)存在的標(biāo)簽數(shù).

每個時隙上存在的標(biāo)簽數(shù)量X是一個隨機變量,X～B(n,1/N),n為標(biāo)簽數(shù)量,N為幀長.每個時隙上存在標(biāo)簽數(shù)的期望為:

(5)

(6)

(7)

(8)

為保證估計靈敏度,樣本容量K不應(yīng)太大;但樣本容量K越大,估計準(zhǔn)確度越高.估計誤差率定義為估計值減去真實值的絕對值與真實值的比值.隨著時隙樣本容量的增加,估計誤差率急劇下降;當(dāng)時隙樣本容量K=5時,估計誤差率已經(jīng)下降到30%左右.由式(4)及對數(shù)函數(shù)的性質(zhì),30%誤差率的估計值對最佳幀長求解影響不大,通過后續(xù)估計可以很快收斂到最佳幀長.因此時隙樣本容量的最小值取K=5較為合適.綜上所述,在未知讀寫器范圍內(nèi)標(biāo)簽數(shù)的情況下,通過一定容量的時隙樣本Xk,可求得FSA算法的最佳的幀長.重復(fù)進行估計和調(diào)整,使FSA算法執(zhí)行過程中的幀長自適應(yīng)趨于最合適的幀長.

4 碰撞標(biāo)簽的二進制散列模型

在FSA算法中,當(dāng)前幀上發(fā)生碰撞的標(biāo)簽會與其他標(biāo)簽在下一幀再次碰撞,嚴(yán)重影響FSA算法的性能.

4.1 碰撞時隙處理方式——二進制散列BS機制

二進制散列BS[12,13]機制是一種專門處理碰撞的時隙散列機制,可以利用碰撞時隙的信息解決發(fā)生的碰撞.本文根據(jù)碰撞時隙的二進制散列模型求解決n個發(fā)生碰撞的標(biāo)簽所需要時隙數(shù)的期望值,從理論上證明二進制散列BS機制確實可以提高系統(tǒng)吞吐率.

4.2 二進制散列模型

定理2 二進制散列BS機制可以有效地解決碰撞,解決n個發(fā)生碰撞的標(biāo)簽所需要時隙數(shù)的期望為:

證明 首先對推導(dǎo)中使用的變量進行說明:

n:表示當(dāng)前時隙上發(fā)生碰撞的標(biāo)簽數(shù);

P1或P2:表示碰撞標(biāo)簽經(jīng)過一次散列,散列模型的出現(xiàn)概率;

Pn,m:表示當(dāng)前時隙上發(fā)生碰撞的n個標(biāo)簽,經(jīng)過m次散列,參與碰撞的標(biāo)簽數(shù)首次降低時某一種散列模型出現(xiàn)的概率;

Nn,m:表示當(dāng)前時隙上發(fā)生碰撞的n個標(biāo)簽,經(jīng)過m次散列,參與碰撞的標(biāo)簽數(shù)首次降低時某一種散列模型所使用的時隙數(shù);

En,m:表示當(dāng)前時隙上發(fā)生碰撞的n個標(biāo)簽,經(jīng)過m次散列,參與碰撞的標(biāo)簽數(shù)首次降低時所需要時隙數(shù)的期望;

E″n:表示在解決n個發(fā)生碰撞的標(biāo)簽過程中,參與碰撞的標(biāo)簽數(shù)首次降低后,解決t(1≤t≤n-1)個發(fā)生碰撞的標(biāo)簽所需要時隙數(shù)的期望;

En:表示解決n個碰撞標(biāo)簽所需時隙數(shù)的期望.

假設(shè)有n個標(biāo)簽在當(dāng)前時隙上發(fā)生了碰撞,參與碰撞的標(biāo)簽經(jīng)過第一次二進制散列后可能出現(xiàn)的散列模型有n+1種,根據(jù)散列后時隙上碰撞的標(biāo)簽數(shù)是否降低,將這n+1種散列模型分為兩類,第Ⅰ類為散列后時隙上碰撞的標(biāo)簽數(shù)沒有降低時的散列模型,第Ⅱ類為散列后時隙上參與碰撞的標(biāo)簽數(shù)降低時的散列模型.圖1中,□代表碰撞時隙,△代表成功時隙,○代表空閑時隙.

二進制散列時每個發(fā)生碰撞的標(biāo)簽在兩個時隙中選擇其一,選擇其中一個時隙的概率為1/2,根據(jù)二項式分布定理:

第Ⅰ類模型出現(xiàn)的概率為:

第Ⅱ類模型出現(xiàn)的概率為:

對于第Ⅰ類模型來說,原來發(fā)生碰撞的n個標(biāo)簽經(jīng)過一次二進制散列,全部又一次在一個時隙上發(fā)生了碰撞,對于這類發(fā)生碰撞的標(biāo)簽繼續(xù)進行二進制散列,直到散列后時隙上發(fā)生碰撞的標(biāo)簽數(shù)第一次降低,則此時滿足這種要求的散列模型及分類如圖2所示.

由圖2可知,發(fā)生碰撞的標(biāo)簽進行二進制散列,發(fā)生碰撞的標(biāo)簽數(shù)第一次降低時經(jīng)過的散列次數(shù)可能趨于無窮多次,而且經(jīng)過散列的次數(shù)越大,對應(yīng)的散列模型出現(xiàn)的概率可能就越小.根據(jù)二項式分布定理,經(jīng)過不同散列次數(shù)的散列模型其出現(xiàn)概率如下:

這些散列模型的概率之和滿足:

對于每一類散列模型中的某一個散列模型,發(fā)生碰撞的n個標(biāo)簽,經(jīng)過m次散列,參與碰撞的標(biāo)簽數(shù)首次降低時所使用的時隙數(shù)Nn,m=2m,m=1,2,3……,根據(jù)期望的定義,則圖2中每一類散列模型經(jīng)過m次散列,解決n個發(fā)生碰撞的標(biāo)簽,參與碰撞的標(biāo)簽數(shù)首次降低時所使用時隙數(shù)的期望如下,第1類散列模型是指經(jīng)過1次散列,參與碰撞的標(biāo)簽數(shù)便發(fā)生降低時的散列模型.

第1類散列模型所使用時隙數(shù)的期望為:

第2類散列模型所使用時隙數(shù)的期望為:

第m類散列模型所使用時隙數(shù)的期望為:

于是,解決n個發(fā)生碰撞的標(biāo)簽,參與碰撞的標(biāo)簽數(shù)首次降低時所使用時隙數(shù)的期望為:

(9)

定義圖1中第Ⅱ類散列模型中某一種散列模型為事件At,n-t,t與n-t分別表示n個發(fā)生碰撞的標(biāo)簽經(jīng)過一次散列,散列后兩個時隙上的標(biāo)簽數(shù).當(dāng)經(jīng)過散列發(fā)生碰撞的標(biāo)簽數(shù)降低時,t∈[1,n-1].則對于圖1中的第Ⅱ類散列模型中的某一種散列模型,其出現(xiàn)的概率為:

定義圖1中第Ⅱ類模型為事件A2,則在第Ⅱ類模型一定出現(xiàn)的情況下,第Ⅱ類散列模型中的某一種散列模型,其出現(xiàn)的條件概率為:

圖1中第Ⅱ類散列模型的某一種散列模型繼續(xù)進行二進制散列,直到發(fā)生碰撞的標(biāo)簽完全得到解決,則此時所使用的時隙數(shù)的期望為Et,t∈[1,n-1],若圖2中的散列模型在參與碰撞的標(biāo)簽數(shù)首次降低后繼續(xù)進行散列,則此時后續(xù)完全解決發(fā)生碰撞的標(biāo)簽所使用時隙總數(shù)的期望為:

(10)

(11)

易知當(dāng)n=1,當(dāng)前時隙上只有一個標(biāo)簽,沒有發(fā)生碰撞,故E1=0.所以解決發(fā)生碰撞的標(biāo)簽所需時隙數(shù)的期望為:

(12)

證畢.

4.3 實時解決碰撞對FSA算法性能的提高

根據(jù)式(12)可知,發(fā)生碰撞的標(biāo)簽數(shù)與解決發(fā)生碰撞的標(biāo)簽所需時隙數(shù)之間近似呈線性關(guān)系.解決碰撞標(biāo)簽的效率定義為:發(fā)生碰撞的標(biāo)簽數(shù)與解決發(fā)生碰撞的標(biāo)簽所需時隙數(shù)的比值.發(fā)生碰撞的標(biāo)簽數(shù)在[2,30]范圍內(nèi)時,隨著碰撞標(biāo)簽數(shù)的增多,解決碰撞的效率下降也較快.隨著發(fā)生碰撞的標(biāo)簽數(shù)繼續(xù)增多,解決碰撞的效率曲線趨于平緩.當(dāng)發(fā)生碰撞的標(biāo)簽數(shù)為13時,此時解決碰撞的效率約為36.6%.

綜上所述,當(dāng)發(fā)生碰撞的標(biāo)簽數(shù)n∈[2,13]時,解決碰撞的效率在37%左右,接近或大于理想情況下FSA算法的系統(tǒng)吞吐率36.8%,所以二進制散列BS機制在一定范圍內(nèi)實時解決發(fā)生碰撞的標(biāo)簽可以提高FSA算法的系統(tǒng)吞吐率.

5 ABSFSA算法

FSA算法是幀時隙類ALOHA防碰撞算法中的一種基本的算法,但吞吐率并不高.將第3節(jié)和第4節(jié)提出的優(yōu)化思想分別用于FSA算法優(yōu)化,則可以產(chǎn)生自適應(yīng)幀時隙ALOHA算法AFSA (Adaptive Frame Slotted ALOHA Algorithm)和二進制散列幀時隙算法BSFSA (Binary Splitting Frame Slotted ALOHA Algorithm).ABSFSA算法同時運用了第3節(jié)和第4節(jié)的優(yōu)化方案.AFSA算法針對FSA算法不能自動調(diào)整幀長以適應(yīng)標(biāo)簽數(shù)量變化的缺點,運用了幀長隨標(biāo)簽數(shù)自適應(yīng)調(diào)整的方法,大大減少了因幀長不能及時調(diào)整導(dǎo)致的無效時隙.實時對碰撞標(biāo)簽進行二進制散列可以進一步提高系統(tǒng)吞吐率,這是BSFSA算法提高系統(tǒng)吞吐率的原因所在.ABSFSA算法的基本思想是:讓所有待識別的標(biāo)簽在幀上隨機選擇一個時隙響應(yīng)讀寫器的查詢指令,當(dāng)某個時隙發(fā)生碰撞時,將這些發(fā)生碰撞的標(biāo)簽進行二進制散列,每一幀的幀長在識別過程中中自適應(yīng)調(diào)整,以減少無效時隙的出現(xiàn).以下是ABSFSA算法的執(zhí)行流程:

①讀寫器初始化.

②讀寫調(diào)整幀長參數(shù),向讀寫范圍內(nèi)所有未被識別的標(biāo)簽發(fā)送查詢指令.

③所有收到查詢指令的標(biāo)簽隨機在當(dāng)前的幀上選擇一個時隙,并在讀寫器輪詢到該時隙時響應(yīng)讀寫器的查詢指令.

④讀寫器對當(dāng)前幀的每一個時隙,按照順序逐一查詢每個時隙上響應(yīng)的標(biāo)簽.在查詢過程中,讀寫器統(tǒng)計每個時隙上響應(yīng)的標(biāo)簽數(shù).若在某個時隙上發(fā)生了標(biāo)簽碰撞,轉(zhuǎn)到⑥.當(dāng)時隙上標(biāo)簽數(shù)樣本容量大于5時,根據(jù)時隙上標(biāo)簽的分布情況,估計合適的幀長,若發(fā)現(xiàn)當(dāng)前幀長與估計的幀長不一致,轉(zhuǎn)到⑤;若估計幀長為1,轉(zhuǎn)到⑦.

⑤讀寫器停止輪詢,當(dāng)前幀結(jié)束,將估計的幀長設(shè)置為下一幀的幀長,轉(zhuǎn)到②.

⑥將在當(dāng)前時隙上發(fā)生碰撞的標(biāo)簽進行二進制散列,進行碰撞標(biāo)簽的識別,其他尚未被識別的標(biāo)簽依次滯后處理.

⑦若在當(dāng)前幀上,無任何標(biāo)簽響應(yīng),則可判定該讀寫器讀寫范圍的所有標(biāo)簽都已識別完成.

6 ABSFSA算法仿真實驗

為驗證ABSFSA算法的有效性和吞吐率提升效果,同時為了說明第3節(jié)、第4節(jié)中提出的兩種優(yōu)化方案的可行性,本文進行了以下4組實驗.實驗中每組數(shù)據(jù)均取100次數(shù)據(jù)的算術(shù)平均值,所有幀長參數(shù)或初始幀長參數(shù)均設(shè)置為128,標(biāo)簽數(shù)量都以100為步長,在[100,1000]間變化.

仿真實驗1β值選取.在AFSA算法中,幀長自適應(yīng)調(diào)整涉及到公式(8)中的調(diào)節(jié)因子β,當(dāng)β在以步長0.2在區(qū)間[0.1,2.0]間取值時,AFSA算法隨標(biāo)簽數(shù)量變化的曲線如圖3所示.

綜合考慮系統(tǒng)吞吐率的大小和波動幅度,β值取0.5較為合適,此時系統(tǒng)吞吐率最大,且波動幅度在可以接受的范圍內(nèi).

仿真實驗2 AFSA算法系統(tǒng)吞吐率.為了驗證幀長自適應(yīng)調(diào)整機制提升幀時隙類ALOHA算法的可行性,對比算法為幀時隙類算法中的兩種基本算法,FSA算法和DFSA算法.如圖4(a)和4(b)所示為AFSA、FSA和DFSA算法在不同標(biāo)簽規(guī)模下的無效時隙和吞吐率.

從圖4(a)可以看到,AFSA算法抑制無效時隙的效果最為明顯.其根本原因是AFSA算法可以根據(jù)標(biāo)簽在幀上的分布,自適應(yīng)調(diào)整幀長以快速適應(yīng)標(biāo)簽數(shù)量的變化,進而大幅減少無效時隙的出現(xiàn).綜上,AFSA算法的系統(tǒng)吞吐率也是最高的,如圖4(b)所示由圖4(b),FSA和DFSA算法隨著標(biāo)簽的增多,其吞吐率呈現(xiàn)不斷下降的趨勢.AFSA算法在標(biāo)簽規(guī)模較小時,其吞吐率略小于DFSA,但AFSA的平均系統(tǒng)吞吐率大于DFSA,且其波動小較小,但是這不影響AFSA算法自適應(yīng)調(diào)整機制的有效性,同時也優(yōu)于DFSA算法的幀長調(diào)整機制.

仿真實驗3 BSFSA算法系統(tǒng)吞吐率.同樣也以FSA算法和DFSA算法為對照算法,驗證二進制散列機制的有效性.如圖5(a)和5(b)所示為BSFSA、FSA和DFSA算法在不同標(biāo)簽規(guī)模下的無效時隙和吞吐率.從圖5(a)可看出,FSA算法和DFSA算法隨著標(biāo)簽數(shù)量的增加,出現(xiàn)了較多的碰撞時隙;BSFSA算法的碰撞時隙數(shù)雖有增加,但較為緩慢.因此BSFSA算法有效地減少了無效時隙的出現(xiàn).BSFSA算法減少無效時隙的機理是:當(dāng)標(biāo)簽在某個時隙上發(fā)生碰撞時,與FSA算法和DFSA算法將碰撞標(biāo)簽延遲至下一幀響應(yīng)不同,BSFSA算法有效利用了碰撞時隙的碰撞信息,將碰撞標(biāo)簽實時進行二進制散列,防止在當(dāng)前幀上發(fā)生碰撞的標(biāo)簽延遲至下一幀時增加下一幀上響應(yīng)的標(biāo)簽數(shù)量,增大與其他標(biāo)簽再次發(fā)生碰撞的概率.因此二進制散列機制可以在一定程度上抑制無效時隙,特別是碰撞時隙的出現(xiàn).

由圖5(b),BSFSA算法的系統(tǒng)吞吐率最大,可達40%以上.其原因前已有述,BSFSA算法有效利用了碰撞時隙信息,碰撞標(biāo)簽實時進行散列,防止在下一幀上與其他標(biāo)簽再次發(fā)生碰撞.

仿真實驗4 ABSFSA算法系統(tǒng)吞吐率.ABSFSA算法綜合運用了幀長自適應(yīng)調(diào)整機制和碰撞標(biāo)簽實時二進制散列機制,實驗2和3分別驗證了這兩種機制的可行性和有效性,為驗證這兩種機制綜合使用的效果,特進行本實驗.對照算法為BSFSA、AFSA、DFSA和FSA算法.圖6(a)和6(b)所示為ABSFSA、BSFSA、AFSA、DFSA和FSA算法在不同標(biāo)簽規(guī)模下的無效時隙和吞吐率.

由圖6(a),ABSFSA算法中出現(xiàn)無效時隙最少,顯示較強的抑制無效時隙的能力.由圖12(b),ABSFSA算法的吞吐率最高,且較穩(wěn)定,吞吐率曲線沒有發(fā)生大的跌落.BSFSA、AFSA、DFSA和FSA算法依次次之.ABSFSA算法的吞吐率比FSA算法有大幅提高,達到45%左右.

綜上所述,ABSFSA算法顯示了較強的抑制無效時隙的能力,且性能穩(wěn)定,同時也充分說明了幀長自適應(yīng)調(diào)整機制和碰撞標(biāo)簽實時二進制散列機制的可行性和有效性.

7 結(jié)束語

本文對影響無源RFID幀時隙類ALOHA防碰撞算法性能的幀長和碰撞時隙兩因素進行分析,并在此基礎(chǔ)上提出了自適應(yīng)二進制散列ABSFSA防碰撞算法.針對幀長和碰撞時隙因素建立了相應(yīng)的數(shù)學(xué)模型,從理論上證明了幀長自適應(yīng)調(diào)整機制和碰撞標(biāo)簽實時二進制散列機制可以有效提高幀時隙類ALOHA算法的系統(tǒng)的吞吐率.仿真實驗結(jié)果表明幀長自適應(yīng)調(diào)整機制和碰撞標(biāo)簽實時二進制散列機制具有較強的抑制無效時隙的能力;ABSFSA算法系統(tǒng)吞吐率相比其他經(jīng)典算法有大幅提升,可較穩(wěn)定達45%左右,減少了信道占用時間,且算法復(fù)雜度較低,對讀寫器運算能力無特別要求.本文提出的ABSFSA算法可為物聯(lián)網(wǎng)數(shù)據(jù)采集終端RFID系統(tǒng)性能的提升提供一個較為有效的解決方案.

[1]Grover A,Berghel H.A survey of RFID deployment and security issues[J].Journal of Information Processing Systems,2011,7(4):561-580.

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

Qian Z H,Wang Y J.IoT technology and application[J].Acta Electronica Sinica,2012,40(5):1023-1029.(in Chinese)

[3]Weilian S,Nikolaos V A.Multiple RFID tags access algorithm[J].IEEE Transactions on Mobile Computing,2010,9(2):174-187.

[4]Sree K R,Ajay O,Archana M,et al.Anti-collision policy for RFID systems:fast predict tags in field algorithm[J].International Journal of Radio Frequency Identification Technology and Applications,2011,3(3):215-228.

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

Wang X,Qian Z H,Hu Z C,et al.Research on RFID anti-collision algorithms based on binary tree[J].Journal on Communications,2010,31(6):49-57.(in Chinese)

[6]Bih-yaw S,Ta-wei L,Chen-yuan C.The research of quadtree search algorithms for anti-collision in radio frequency identification systems[J].Scientific Research and Essays,2011,6(25):5342-5350.

[7]Donghwan L,Jihoon C,Wonjun L,et al.A time-optimal anti-collision algorithm for FSA-based RFID systems[J].ETRI Journal,2011,33(3):458-461.

[8]Shi-an L,Xiao-juan P.Improved dynamic frame slotted ALOHA algorithm for anti-collision in RFID systems[J].Knowledge Discovery and Data Mining,2012,135:423-430.

[9]Chun-yi W,Chi-chung L,Ming-cheng L.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.

[10]Lei Z,Yum T S P.Optimal framed aloha based anti-collision algorithms for RFID systems[J].IEEE Transactions on Communications,2010,58(12):3583-3592.

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

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

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

[14]Thomas F L P,Gaia M,Chiara P.Anticollision protocols for single-reader RFID systems:temporal analysis and optimization[J].IEEE Transactions on Mobile Computing,2011,10(2):267-279.

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

E-mail:xiaohongzh@263.net

張留洋(通信作者) 男,1988年1月出生,河南禹州人.現(xiàn)為北京航空航天大學(xué)電子信息工程學(xué)院博士研究生.研究方向:射頻傳感理論、RFID防碰撞算法.

E-mail:zhangliuyang2011@126.com

Research on Passive RFID System Adaptive Frame Slot Anti-collision Algorithm

ZHANG Xiao-hong1,ZHANG Liu-yang2,1

(1.SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China;2.SchoolofElectronicsandInformationEngineering,BeihangUniversity,Beijing100191,China)

As an important data acquisition technology,throughput of RFID system affects performance of the data acquisition terminal of Internet of Things directly,but the throughputs of passive RFID system anti-collision algorithms of framed slot are generally low.Two factors influencing throughput of RFID systems are analyzed,which were frame length and the way of solving collided slots.Mathematical models of frame adjusting and tag collision are set up and solved,and then a solution is proposed for optimizing the anti-collision ALOHA algorithms of framed slot,that is,frame length adjusting adaptively and collision binary splitting timely.On these bases,the adaptive binary splitting frame slotted ALOHA anti-collision is constructed.The simulation results show that ABSFSA algorithm is able to decrease the invalid slots effectively in the same condition,and the throughput of RFID system is steadily improved to 45% obviously.The research work provides a referable mathematical model for optimizing the anti-collision ALOHA algorithms of framed slot,and a valuable solution for improving performance of data acquisition terminal of Internet of Things.

RFID;ALOHA anti-collision algorithm;frame length adjusting adaptively;binary splitting mechanism;tag estimation function

2014-09-13;

2015-11-26;責(zé)任編輯:梅志強

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

TN911.23

A

0372-2112 (2016)09-2211-08

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

10.3969/j.issn.0372-2112.2016.09.028