無需先驗RFID標簽數信息的基于樹時隙Aloha的防沖突算法

鄧中婷

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

關鍵詞：RFID；防沖突；Tree Slotted Aloha；FKSS算法

1 引言

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

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

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

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

2 問題的提出

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

圖1 TSA系統效率

3 FKSS算法

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

在Aloha協議中，我們設一個時隙發生沖突的概率為Pc，發生空的概率為Pi，成功時隙數則設為Ps，若已知標簽數N和幀長L，則三個概率可表示為

（1）

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

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

（2）

由式（2）的Markov計算公式，我們可以得到信息幀的前k個時隙的狀態概率。當給定初始幀長L0=128，當標簽數增大，Pci增大，Pii減小；當標簽數減小，Pci減小，Pii增大，其中i=1，2，3。

設k為連續時隙的門限值，Cc表示一個幀中頭個時隙均為空時隙的數目，當Ci=k時，幀長為為原幀長的一半；Ci表示一個幀中頭幾個時隙均為沖突時隙的數目，當Cs=k時，幀長為為原幀長的一倍。該算法表示為

（6）

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

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

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

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

4.TSA算法。

5.結束。

4 實驗仿真

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

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

圖2 不同算法下的系統效率

5 結論

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

由仿真實驗得到它的最大吞吐量高于TSA算法，而且無論標簽增大還是減小，系統吞吐量都不會顯著的降低，且一直高于TSA協議，同時，其吞吐量曲線也高于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動態幀時隙ALOHA防沖突中的標簽估計和幀長確定，自動化學報，36卷，4期，2010，620-624

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