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