鄧中婷

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

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

1 引言

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

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

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

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

2 問題的提出

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

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

3 FKSS算法

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

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

（1）

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

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

（2）

由式（2）的Markov計算公式，我們可以得到信息幀的前k個時隙的狀態(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ù)時隙的門限值，Cc表示一個幀中頭個時隙均為空時隙的數(shù)目，當(dāng)Ci=k時，幀長為為原幀長的一半；Ci表示一個幀中頭幾個時隙均為沖突時隙的數(shù)目，當(dāng)Cs=k時，幀長為為原幀長的一倍。該算法表示為

（6）

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

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

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

3.令Ci，Cs分別表示一個幀中頭幾個均為空時隙和沖突時隙的數(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 實驗仿真

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

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

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

5 結(jié)論

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

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

參考文獻

[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動態(tài)幀時隙ALOHA防沖突中的標(biāo)簽估計和幀長確定，自動化學(xué)報，36卷，4期，2010，620-624

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