基于ALOHA算法的RFID防碰撞技術研究
加入技術交流群
3．2 動態幀時隙ALOHA算法
為使系統效率最優，提出動態幀時隙ALOHA(DynamicFramed Slotted Aloha，DFSA)算法，使得幀時隙數等于參與循環的標簽數。DFSA每幀時隙數可以根據標簽數的變化及時調整，使得標簽數量與幀時隙數匹配。在開始新一個幀循環時，讀寫器要對參與幀循環的標簽數進行估計，這個過程在整個算法中發揮著重要的作用。如果所估計的標簽數與實際情況相差甚遠，那么算法的效率就會發生大幅的下降，這樣就影響了系統的穩定性。
目前，主要有兩種估計標簽數的方法。第一種方法是在發生沖突時，一個時隙中至少有兩個標簽發生碰撞。標簽的估計函數為：
N代表當前幀的長度，C0表示空閑時隙，C1表示成功時隙，Ck表示碰撞時隙數。當沖突較頻繁時，這種估計方法的相對估計誤差較大，但具有方法簡單等優點。
另一種方法是基于時隙二項分布來估計標簽數。假設N代表當前幀的長度，n表示標簽數。標簽選擇各個時隙數是等概率的，同一個時隙內出現r個標簽的概率，根據二項分布原理，得：
利用切比雪夫不等式估計標簽數目。本文引用地址：http://www.j9360.com/article/157800.htm
3．3 分組幀時隙ALOHA算法
在RFID系統中，我們經常使用動態幀時隙ALOHA算
法。但是由于最大幀時隙數有限制。當標簽數量過大時，我們不能無限制地增加幀的時隙數。因此提出了分組幀時隙ALOHA(Group Framed Slotted Aloha，GFSA)算法。分組的目的是要限制標簽的應答數量，使得參與識別循環的標簽與幀的時隙數匹配。在GFSA算法中，如果估計出待識別的標簽數超過了最大幀時隙數所能匹配的范圍時，保證每一組的待識別標簽與最大幀時隙數相匹配。
在圖3中，無論是采用一組還是兩組，都會達到同樣的期望系統效率的標簽數：
由上式我們可以得到n=354。如果未識別標簽數大于354時，為達到最佳系統效率，我們將標簽分成兩組。我們提出的分組算法是基于最大幀時隙數為256的動態幀時隙ALOHA算法。在算法中，首先定義：
(1)為達到最大系統效率，通過獲取最后一個閱讀幀的結果(0或是1)來決定對分組標簽進行響應，以確定新循環幀的大小。
(2)為減小RFID系統的復雜性，通過使用n=c1+2ck估計函數來確定標簽數量。
(3)利用上面推導出的n=354，作為分組的條件。當系統內標簽數量比較小時，則使用最大幀時隙數為256的動態幀時隙ALOHA算法。一旦標簽數量超過了354時，則使用分組幀時隙ALOHA算法，來限制系統內的響應的標簽數量。過程如圖4所示。
我們利用二進制樹形分解法對標簽進行分組，如圖5所示。二進制樹形結構可以有效地對未識別標簽進行搜索。對分組后，獲取最后一個閱讀幀的結果(0或是1)來判斷是否繼續分組。如果結果是1，表示達到時隙分離條件，需要對標簽繼續進行分組，直到結構是0為止。如果結果是0，表示未達到時隙分離條件，并采用動態幀時隙ALOHA算法對標簽進行識別。
對提出的算法進行了仿真。結果表明：當標簽數小于354時，分組幀時隙ALOHA算法采用動態幀時隙ALOHA算法；當標簽數大于354時，分組幀時隙ALOHA算法對標簽數進行分組識別。所以標簽數越多，分組幀時隙ALOHA算法所使用的時隙數越少，效率越高。如圖6所示。
4 結束語
本文基于ALOHA算法，分別對幀時隙算法和動態幀時隙算法進行研究和分析，并提出一種利用二進制樹形分組的時隙ALHOA算法。對提出的分組算法和傳統的動態幀時隙算法進行比較。當標簽數過大時，采用此方法有利于提高系統效率，并減少了計算和操作的復雜度。
評論