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