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