ALOHA算法的RFID防碰撞技術分析

1、【Word版本下載可任意編輯】 ALOHA算法的RFID防碰撞技術分析 1 射頻識別系統(tǒng)介紹 射頻識別技術(Radio Frequency Identification，RFID)是一種非接觸式自動識別技術，與傳統(tǒng)的識別方式相比，它無需直接接觸、無需光學可視、無需人工干預即可完成信息輸入和處理，具有操作方便快捷、存儲數(shù)據量大、保密性好、反應時間短、對環(huán)境適應性強等優(yōu)點，現(xiàn)在已廣泛應用于工業(yè)自動化、商業(yè)自動化和交通運輸管理等領域，成為當前IT業(yè)研究的熱點技術之一。 典型的RFID系統(tǒng)主要包括三個部分：電子標簽(tag)、讀寫器(Read)和應用系統(tǒng)(如圖1)。電子標簽放置在被識別的對象上，是RF

2、ID系統(tǒng)真正的數(shù)據載體。通常電子標簽處于休眠狀態(tài)，一旦進入讀寫器作用范圍內就會被激活，并與讀寫器開展無線射頻方式的非接觸式雙向數(shù)據通信，以到達識別并交換數(shù)據的目的。此外，許多讀寫器還都有附加的通信接口，以便將所獲的數(shù)據傳給應用系統(tǒng)開展進一步的處理。 2 系統(tǒng)防碰撞 RFID系統(tǒng)工作時，當有2個或2個以上的電子標簽同時在同一個讀寫器的作用范圍內向讀寫器發(fā)送數(shù)據的時候，就會出現(xiàn)信號的干擾，這個干擾就稱為碰撞，其結果將會導致該次傳輸?shù)氖?，因為必須采用適當?shù)募夹g防止碰撞的產生。 3 ALOHA算法及仿真結果 目前有多種防碰撞算法，主要分為ALOHA算法和樹形分解算法。由于樹形分解法有時會使某些標簽的

3、識別延遲可能比較長，所以ALOHA算法因具有簡單易實現(xiàn)等優(yōu)點而成為應用廣的算法之一。ALOHA算法是在ALOHA思想的根底上，根據RFID系統(tǒng)的特點和技術要求不斷改良形成的算法體系。它的本質是分離標簽的應答時間，使標簽在不同的時隙內發(fā)送應答。一旦發(fā)生碰撞，一般采取退避原則，等待下一循環(huán)周期發(fā)送應答。ALOHA算法又分為幀時隙ALOHA算法、動態(tài)幀時隙ALOHA算法和分組幀時隙ALOHA算法等。 3.1 幀時隙ALOHA算法 幀時隙ALOHA(Framed slotted Aloha，F(xiàn)SA)算法是基于通信領域的ALOHA協(xié)議提出的。在FSA中，幀(Frame)是由讀寫器定義的一段時間長度，其中

4、包含若干時隙。標簽在每個幀內隨機選擇一個時隙發(fā)送數(shù)據。所有標簽應答同步，即只能在時隙(Slot)開始點向讀寫器發(fā)送信息，每個標簽發(fā)送的時隙是隨機選擇的。時隙可以分為三類：空閑時隙、應答時隙和碰撞時隙。在空閑時隙中沒有識別任何標簽，應答時隙中可以正確識別一個標簽。當一個時隙中有多個標簽同時發(fā)送應答時就會產生碰撞，形成碰撞時隙。碰撞的標簽退出當前循環(huán)，等待參與新的幀循環(huán)。 讀寫器當前使用幀的長度為N，標簽數(shù)為n，在一個時隙中存在r個標簽的概率為： 當r=1時，表示一個時隙只有一個標簽，即成功讀取的時隙。因此，在一個閱讀周期中讀取標簽數(shù)的期望值為： 其中，表示只有一個標簽占據一個時隙的時隙總數(shù)。其中

5、幀長度為N，標簽總數(shù)為n。 系統(tǒng)效率為PN: 圖2示出了當幀的長度為256時的系統(tǒng)效率。當我們要想獲得效率時，使得： 根據上式可推出當幀的長度為N時，效率的標簽響應數(shù)為： 當標簽數(shù)為n時，幀長度的值為： 當n很大時，將上式泰勒爾展開： 因此，當標簽數(shù)量與幀時隙數(shù)相同時，讀寫器的識讀效率。標簽數(shù)量與幀時隙數(shù)不匹配時，識讀效率會大大下降。如標簽數(shù)遠小于幀時隙數(shù)，會造成大量的空閑時隙數(shù)；而當標簽數(shù)量遠高于幀時隙數(shù)時，則會產生過多的碰撞時隙；這兩種情況都會導致識別效率的降低。 3.2 動態(tài)幀時隙ALOHA算法 為使系統(tǒng)效率，提出動態(tài)幀時隙ALOHA(DynamicFramed Slotted Aloh

6、a，DFSA)算法，使得幀時隙數(shù)等于參與循環(huán)的標簽數(shù)。DFSA每幀時隙數(shù)可以根據標簽數(shù)的變化及時調整，使得標簽數(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)點。 另一種方法是基

7、于時隙二項分布來估計標簽數(shù)。假設N代表當前幀的長度，n表示標簽數(shù)。標簽選擇各個時隙數(shù)是等概率的，同一個時隙內出現(xiàn)r個標簽的概率，根據二項分布原理，得： 利用切比雪夫不等式估計標簽數(shù)目。 3.3 分組幀時隙ALOHA算法 在RFID系統(tǒng)中，我們經常使用動態(tài)幀時隙ALOHA算法。但是由于幀時隙數(shù)有限制。當標簽數(shù)量過大時，我們不能無限制地增加幀的時隙數(shù)。因此提出了分組幀時隙ALOHA(Group Framed Slotted Aloha，GFSA)算法。分組的目的是要限制標簽的應答數(shù)量，使得參與識別循環(huán)的標簽與幀的時隙數(shù)匹配。在GFSA算法中，如果估計出待識別的標簽數(shù)超過了幀時隙數(shù)所能匹配的范圍時，

8、保證每一組的待識別標簽與幀時隙數(shù)相匹配。 在圖3中，無論是采用一組還是兩組，都會到達同樣的期望系統(tǒng)效率的標簽數(shù)： 由上式我們可以得到n=354。如果未識別標簽數(shù)大于354時，為到達系統(tǒng)效率，我們將標簽分成兩組。我們提出的分組算法是基于幀時隙數(shù)為256的動態(tài)幀時隙ALOHA算法。在算法中，首先定義： (1)為到達系統(tǒng)效率，通過獲取一個閱讀幀的結果(0或是1)來決定對分組標簽開展響應，以確定新循環(huán)幀的大小。 (2)為減小RFID系統(tǒng)的復雜性，通過使用n=c1+2ck估計函數(shù)來確定標簽數(shù)量。 (3)利用上面推導出的n=354，作為分組的條件。當系統(tǒng)內標簽數(shù)量比較小時，則使用幀時隙數(shù)為256的動態(tài)幀時

9、隙ALOHA算法。一旦標簽數(shù)量超過了354時，則使用分組幀時隙ALOHA算法，來限制系統(tǒng)內的響應的標簽數(shù)量。過程如圖4所示。 我們利用二進制樹形分解法對標簽開展分組，如圖5所示。二進制樹形構造可以有效地對未識別標簽開展搜索。對分組后，獲取一個閱讀幀的結果(0或是1)來判斷是否繼續(xù)分組。如果結果是1，表示到達時隙分離條件，需要對標簽繼續(xù)開展分組，直到構造是0為止。如果結果是0，表示未到達時隙分離條件，并采用動態(tài)幀時隙ALOHA算法對標簽開展識別。 對提出的算法開展了仿真。結果說明：當標簽數(shù)小于354時，分組幀時隙ALOHA算法采用動態(tài)幀時隙ALOHA算法；當標簽數(shù)大于354時，分組幀時隙ALOHA算法對標簽數(shù)開展分組識別。所以標簽數(shù)越多，分組幀時隙ALOHA算法所使用的時隙數(shù)越