無需先驗(yàn)RFID標(biāo)簽數(shù)信息的基于樹時(shí)隙Aloha的防沖突算法

鄧中婷

摘 要：為優(yōu)化射頻識別（Radio frequency identification， RFID）標(biāo)簽的識別效率，本文在樹時(shí)隙Aloha（TSA） [1]基礎(chǔ)上提出了一種新的防沖突協(xié)議。該協(xié)議采用FKSS（Fast k-Slot Selection）算法，對每個(gè)幀中的開始若干個(gè)時(shí)隙，通過判斷是否為空時(shí)隙或沖突時(shí)隙來動(dòng)態(tài)調(diào)整幀中的時(shí)隙數(shù)，即幀長。本文提出的協(xié)議的最大優(yōu)點(diǎn)是，無需先驗(yàn)的RFID標(biāo)簽信息，無論標(biāo)簽突然增大和減小，系統(tǒng)均能使幀長與標(biāo)簽數(shù)保持在合理水平，從而使系統(tǒng)吞吐量的變化不受標(biāo)簽數(shù)的影響。從仿真結(jié)果看，本文提出的協(xié)議的最高吞吐量在0.43左右，高于傳統(tǒng)的動(dòng)態(tài)幀時(shí)隙協(xié)議和Q算法[5]協(xié)議，同時(shí)與TSA相比較，在標(biāo)簽數(shù)沒有接近初始幀長時(shí)其吞吐量曲線要高于TSA的吞吐量曲線。）

關(guān)鍵詞：RFID；防沖突；Tree Slotted Aloha；FKSS算法

1 引言

RFID是物聯(lián)網(wǎng)中的一個(gè)關(guān)鍵技術(shù)， 其中閱讀器識別標(biāo)簽采用共享的無線信道，因此標(biāo)簽的沖突不可避免。通常閱讀器采用防沖突算法[2]來解決該問題，TSA算法是其中一個(gè)重要算法。

本文在TSA算法的基礎(chǔ)上提出了一種FKSS（Fast k-Slot Selection）的防沖突算法，該算法也是把標(biāo)簽的訪問時(shí)間分配到一個(gè)幀中的多個(gè)時(shí)隙之內(nèi)，通過判斷一個(gè)幀時(shí)隙內(nèi)開始的若干個(gè)時(shí)隙是否全為空或沖突時(shí)隙來動(dòng)態(tài)調(diào)整幀長，使幀長與標(biāo)簽數(shù)保持在一個(gè)合理的水平，從而保證較高的系統(tǒng)吞吐量。

本文提出算法的最大優(yōu)點(diǎn)在于，無論標(biāo)簽增大還是減小，系統(tǒng)吞吐量都不會(huì)顯著的降低，因而無需先驗(yàn)的標(biāo)簽數(shù)信息即可保證較高的系統(tǒng)吞吐量。從仿真結(jié)果來看，本文的算法取得的最大吞吐量為0.43，與DyTSA算法[3] [4]相當(dāng)，但是當(dāng)標(biāo)簽數(shù)明顯降低和減少時(shí)卻高于TSA算法。同時(shí)，其吞吐量曲線要高于Q算法和DFSA算法。

本文剩余部分做如下安排：第2部分由系統(tǒng)效率圖指出TSA算法存在的問題；第3部分針對TSA算法的問題，提出了基于TSA的FKSS算法，并給出具體的數(shù)學(xué)推導(dǎo)、算法的基本流程；最后一部分給出系統(tǒng)識別性能的仿真與分析。

2 問題的提出

下圖為TSA算法系統(tǒng)效率圖。從圖中可以看到，只有標(biāo)簽數(shù)接近于初始幀長時(shí)，吞吐量才能取得最大值，當(dāng)標(biāo)簽數(shù)遠(yuǎn)離初始幀長時(shí)，系統(tǒng)吞吐量將大幅下降。因此，當(dāng)標(biāo)簽數(shù)突然增多或者突然下降時(shí)，TSA算法的系統(tǒng)吞吐量將會(huì)迅速惡化。

圖1 TSA系統(tǒng)效率

3 FKSS算法

針對上一節(jié)提出的TSA算法的問題，本節(jié)提出一種FKSS算法。

在Aloha協(xié)議中，我們設(shè)一個(gè)時(shí)隙發(fā)生沖突的概率為Pc，發(fā)生空的概率為Pi，成功時(shí)隙數(shù)則設(shè)為Ps，若已知標(biāo)簽數(shù)N和幀長L，則三個(gè)概率可表示為

（1）

由式（1）可知，如果待閱讀的標(biāo)簽數(shù)n遠(yuǎn)大于初始幀長L，那么Pc就會(huì)很大；相反，如果待閱讀的標(biāo)簽數(shù)n遠(yuǎn)小于初始幀長L，那么Pi就會(huì)很大。若只考慮一個(gè)信息幀的頭幾個(gè)時(shí)隙全為沖突或全為空的概率，我們可以引入Markov算法。

令Pci為一個(gè)信息幀中的前i個(gè)時(shí)隙都是沖突時(shí)隙的概率，Pii為一個(gè)信息幀中的前i個(gè)時(shí)隙都是空時(shí)隙的概率，Pss表示這頭幾個(gè)時(shí)隙中出現(xiàn)成功時(shí)隙的概率，則Markov計(jì)算公式為

（2）

由式（2）的Markov計(jì)算公式，我們可以得到信息幀的前k個(gè)時(shí)隙的狀態(tài)概率。當(dāng)給定初始幀長L0=128，當(dāng)標(biāo)簽數(shù)增大，Pci增大，Pii減?。划?dāng)標(biāo)簽數(shù)減小，Pci減小，Pii增大，其中i=1，2，3。

設(shè)k為連續(xù)時(shí)隙的門限值，Cc表示一個(gè)幀中頭個(gè)時(shí)隙均為空時(shí)隙的數(shù)目，當(dāng)Ci=k時(shí)，幀長為為原幀長的一半；Ci表示一個(gè)幀中頭幾個(gè)時(shí)隙均為沖突時(shí)隙的數(shù)目，當(dāng)Cs=k時(shí)，幀長為為原幀長的一倍。該算法表示為

（6）

由式（6），我們給出FKSS算法的步驟，總結(jié)如下：

1.確定初始幀長，L=L0，其中L0為閱讀器預(yù)先設(shè)定的初始值。

2.閱讀器向標(biāo)簽發(fā)出帶有初始幀長L信息的指令，標(biāo)簽在第0個(gè)到L-1個(gè)時(shí)隙中隨機(jī)應(yīng)答。

3.令Ci，Cs分別表示一個(gè)幀中頭幾個(gè)均為空時(shí)隙和沖突時(shí)隙的數(shù)目。若Ci= k， L=L/2，轉(zhuǎn)向步驟2；若Cs=k， L=2L，轉(zhuǎn)向步驟2；否則，L=L，轉(zhuǎn)向步驟4。

4.TSA算法。

5.結(jié)束。

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

為了證明我們前面提出的FKSS算法，以下給出仿真結(jié)果，計(jì)算過程全部采用蒙特卡洛方法，結(jié)果由獨(dú)立做500次試驗(yàn)平均得到。

圖4 中初始幀長L0=128，N從10到500?？梢钥闯?，Q算法的吞吐量最低，最大也只能達(dá)到約0.34；DFSA算法的吞吐量相對來說也較低，其最大吞吐量無法超過0.40?；旌闲蛥f(xié)議中的樹時(shí)隙Aloha（TSA），動(dòng)態(tài)樹時(shí)隙（DyTSA）相比Q算法和DFSA算法，系統(tǒng)吞吐量得到了大幅提高，最高可達(dá)到約0.43；但是，在TSA算法中，只有當(dāng)初始幀長與標(biāo)簽數(shù)相等時(shí)，吞吐量才能達(dá)到最大值，而當(dāng)初始幀長大于標(biāo)簽數(shù)或小于標(biāo)簽數(shù)，吞吐量會(huì)從峰值0.43左右大幅下降到0.38左右。而我們提出的FKSS算法取得的最大吞吐量為0.43，與DyTSA算法相當(dāng)，但是無論標(biāo)簽增大還是減小，系統(tǒng)吞吐量都不會(huì)顯著的降低，都會(huì)保持在0.40以上，高于TSA協(xié)議，同時(shí)，其吞吐量曲線也高于Q算法和DFSA算法。

圖2 不同算法下的系統(tǒng)效率

5 結(jié)論

本文在樹時(shí)隙Aloha（TSA）基礎(chǔ)上提出了新的FKSS算法，它的最大優(yōu)點(diǎn)是，無需先驗(yàn)的RFID標(biāo)簽信息，無論標(biāo)簽突然增大和減小，系統(tǒng)均能使幀長與標(biāo)簽數(shù)保持在合理水平，從而使系統(tǒng)吞吐量的變化不受標(biāo)簽數(shù)的影響。

由仿真實(shí)驗(yàn)得到它的最大吞吐量高于TSA算法，而且無論標(biāo)簽增大還是減小，系統(tǒng)吞吐量都不會(huì)顯著的降低，且一直高于TSA協(xié)議，同時(shí)，其吞吐量曲線也高于Q算法、DyTSA算法和DFSA算法。

參考文獻(xiàn)

[1]I Hush D R，Wood C.Analysis of tree algorithm for RFID abitration.In： Proceeds of IEEE International Symposium on Information Theory.Cambridge，USA：IEEE，1998.107.

[2]EPC Radio-Frequency Identity Protocols Class-I Generation-2 UHF RFlD Protocol for Communications at 860Mhz-960Mhz version 1.0.9 2004.

[3]Wu， H， Zeng， Y. Bayesian Tag Estimate and Optimal Frame Length for Anti-Collision Aloha RFID System. IEEE Transactions on Automation Science and Engineering， 2010， PP（99）： 1-7.

[4]吳海鋒， 曾玉. RFID動(dòng)態(tài)幀時(shí)隙ALOHA防沖突中的標(biāo)簽估計(jì)和幀長確定，自動(dòng)化學(xué)報(bào)，36卷，4期，2010，620-624

[5]馮波，李錦濤，鄭為民，張平，丁振華.一種新的RFID標(biāo)簽識別防沖突算法，自動(dòng)化學(xué)報(bào)，34卷，6期，2008，631-638