基于ALOHA 算法的 RFID 防碰撞技術(shù)研究

　　1射頻識別系統(tǒng)介紹

　　射頻識別技術(shù)(RadioFrequencyIdentification，RFID)是一種非接觸式自動識別技術(shù)，與傳統(tǒng)的識別方式相比，它無需直接接觸、無需光學(xué)可視、無需人工干預(yù)即可完成信息輸入和處理，具有操作方便快捷、存儲數(shù)據(jù)量大、保密性好、反應(yīng)時間短、對環(huán)境適應(yīng)性強(qiáng)等優(yōu)點(diǎn)，現(xiàn)在已廣泛應(yīng)用于工業(yè)自動化、商業(yè)自動化和交通運(yùn)輸管理等領(lǐng)域，成為當(dāng)前IT業(yè)研究的熱點(diǎn)技術(shù)之一。

　　典型的RFID系統(tǒng)主要包括三個部分：電子標(biāo)簽(tag)、讀寫器(Read)和應(yīng)用系統(tǒng)(如圖1)。電子標(biāo)簽放置在被識別的對象上，是RFID系統(tǒng)真正的數(shù)據(jù)載體。通常電子標(biāo)簽處于休眠狀態(tài)，一旦進(jìn)入讀寫器作用范圍內(nèi)就會被激活，并與讀寫器進(jìn)行無線射頻方式的非接觸式雙向數(shù)據(jù)通信，以達(dá)到識別并交換數(shù)據(jù)的目的。此外，許多讀寫器還都有附加的通信接口，以便將所獲的數(shù)據(jù)傳給應(yīng)用系統(tǒng)進(jìn)行進(jìn)一步的處理。

　　2系統(tǒng)防碰撞

　　RFID系統(tǒng)工作時，當(dāng)有2個或2個以上的電子標(biāo)簽同時在同一個讀寫器的作用范圍內(nèi)向讀寫器發(fā)送數(shù)據(jù)的時候，就會出現(xiàn)信號的干擾，這個干擾就稱為碰撞，其結(jié)果將會導(dǎo)致該次傳輸?shù)氖?，因?yàn)楸仨毑捎眠m當(dāng)?shù)募夹g(shù)防止碰撞的產(chǎn)生。

　　3ALOHA算法及仿真結(jié)果

　　目前有多種防碰撞算法，主要分為ALOHA算法和樹形分解算法。由于樹形分解法有時會使某些標(biāo)簽的識別延遲可能比較長，所以ALOHA算法因具有簡單易實(shí)現(xiàn)等優(yōu)點(diǎn)而成為應(yīng)用最廣的算法之一。ALOHA算法是在ALOHA思想的基礎(chǔ)上，根據(jù)RFID系統(tǒng)的特點(diǎn)和技術(shù)要求不斷改進(jìn)形成的算法體系。它的本質(zhì)是分離標(biāo)簽的應(yīng)答時間，使標(biāo)簽在不同的時隙內(nèi)發(fā)送應(yīng)答。一旦發(fā)生碰撞，一般采取退避原則，等待下一循環(huán)周期發(fā)送應(yīng)答。ALOHA算法又分為幀時隙ALOHA算法、動態(tài)幀時隙ALOHA算法和分組幀時隙ALOHA算法等。

　　3．1幀時隙ALOHA算法

　　幀時隙ALOHA(FramedslottedAloha，F(xiàn)SA)算法是基于通信領(lǐng)域的ALOHA協(xié)議提出的。在FSA中，"幀"(Frame)是由讀寫器定義的一段時間長度，其中包含若干時隙。標(biāo)簽在每個幀內(nèi)隨機(jī)選擇一個時隙發(fā)送數(shù)據(jù)。所有標(biāo)簽應(yīng)答同步，即只能在時隙(Slot)開始點(diǎn)向讀寫器發(fā)送信息，每個標(biāo)簽發(fā)送的時隙是隨機(jī)選擇的。時隙可以分為三類：空閑時隙、應(yīng)答時隙和碰撞時隙。在空閑時隙中沒有識別任何標(biāo)簽，應(yīng)答時隙中可以正確識別一個標(biāo)簽。當(dāng)一個時隙中有多個標(biāo)簽同時發(fā)送應(yīng)答時就會產(chǎn)生碰撞，形成碰撞時隙。碰撞的標(biāo)簽退出當(dāng)前循環(huán)，等待參與新的幀循環(huán)。

　　讀寫器當(dāng)前使用幀的長度為N，標(biāo)簽數(shù)為n，在一個時隙中存在r個標(biāo)簽的概率為：

　　當(dāng)r=1時，表示一個時隙只有一個標(biāo)簽，即成功讀取的時隙。因此，在一個閱讀周期中讀取標(biāo)簽數(shù)的期望值為：

　　其中，a₁ ^N.n表示只有一個標(biāo)簽占據(jù)一個時隙的時隙總數(shù)。其中幀長度為N，標(biāo)簽總數(shù)為n。
系統(tǒng)效率為PN:

　　圖2示出了當(dāng)幀的長度為256時的系統(tǒng)效率。當(dāng)我們要想獲得最大效率時，使得：

　　根據(jù)上式可推出當(dāng)幀的長度為N時，效率最高的標(biāo)簽響應(yīng)數(shù)為：

　　當(dāng)標(biāo)簽數(shù)為n時，幀長度的最佳值為：

　　當(dāng)n很大時，將上式泰勒爾展開：

　　因此，當(dāng)標(biāo)簽數(shù)量與幀時隙數(shù)相同時，讀寫器的識讀效率最高。標(biāo)簽數(shù)量與幀時隙數(shù)不匹配時，識讀效率會大大下降。如標(biāo)簽數(shù)遠(yuǎn)小于幀時隙數(shù)，會造成大量的空閑時隙數(shù)；而當(dāng)標(biāo)簽數(shù)量遠(yuǎn)高于幀時隙數(shù)時，則會產(chǎn)生過多的碰撞時隙；這兩種情況都會導(dǎo)致識別效率的降低。

　　3．2動態(tài)幀時隙ALOHA算法

　　為使系統(tǒng)效率最優(yōu)，提出動態(tài)幀時隙ALOHA(DynamicFramedSlottedAloha，DFSA)算法，使得幀時隙數(shù)等于參與循環(huán)的標(biāo)簽數(shù)。DFSA每幀時隙數(shù)可以根據(jù)標(biāo)簽數(shù)的變化及時調(diào)整，使得標(biāo)簽數(shù)量與幀時隙數(shù)匹配。在開始新一個幀循環(huán)時，讀寫器要對參與幀循環(huán)的標(biāo)簽數(shù)進(jìn)行估計(jì)，這個過程在整個算法中發(fā)揮著重要的作用。如果所估計(jì)的標(biāo)簽數(shù)與實(shí)際情況相差甚遠(yuǎn)，那么算法的效率就會發(fā)生大幅的下降，這樣就影響了系統(tǒng)的穩(wěn)定性。

　　目前，主要有兩種估計(jì)標(biāo)簽數(shù)的方法。第一種方法是在發(fā)生沖突時，一個時隙中至少有兩個標(biāo)簽發(fā)生碰撞。標(biāo)簽的估計(jì)函數(shù)為：

　　N代表當(dāng)前幀的長度，C0表示空閑時隙，C1表示成功時隙，Ck表示碰撞時隙數(shù)。當(dāng)沖突較頻繁時，這種估計(jì)方法的相對估計(jì)誤差較大，但具有方法簡單等優(yōu)點(diǎn)。

　　另一種方法是基于時隙二項(xiàng)分布來估計(jì)標(biāo)簽數(shù)。假設(shè)N代表當(dāng)前幀的長度，n表示標(biāo)簽數(shù)。標(biāo)簽選擇各個時隙數(shù)是等概率的，同一個時隙內(nèi)出現(xiàn)r個標(biāo)簽的概率，根據(jù)二項(xiàng)分布原理，得：

　　利用切比雪夫不等式估計(jì)標(biāo)簽數(shù)目。

　　3．3分組幀時隙ALOHA算法

　　在RFID系統(tǒng)中，我們經(jīng)常使用動態(tài)幀時隙ALOHA算
法。但是由于最大幀時隙數(shù)有限制。當(dāng)標(biāo)簽數(shù)量過大時，我們不能無限制地增加幀的時隙數(shù)。因此提出了分組幀時隙ALOHA(GroupFramedSlottedAloha，GFSA)算法。分組的目的是要限制標(biāo)簽的應(yīng)答數(shù)量，使得參與識別循環(huán)的標(biāo)簽與幀的時隙數(shù)匹配。在GFSA算法中，如果估計(jì)出待識別的標(biāo)簽數(shù)超過了最大幀時隙數(shù)所能匹配的范圍時，保證每一組的待識別標(biāo)簽與最大幀時隙數(shù)相匹配。

　　在圖3中，無論是采用一組還是兩組，都會達(dá)到同樣的期望系統(tǒng)效率的標(biāo)簽數(shù)：

　　由上式我們可以得到n=354。如果未識別標(biāo)簽數(shù)大于354時，為達(dá)到最佳系統(tǒng)效率，我們將標(biāo)簽分成兩組。我們提出的分組算法是基于最大幀時隙數(shù)為256的動態(tài)幀時隙ALOHA算法。在算法中，首先定義：
　　(1)為達(dá)到最大系統(tǒng)效率，通過獲取最后一個閱讀幀的結(jié)果(0或是1)來決定對分組標(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ù)為256的動態(tài)幀時隙ALOHA算法。一旦標(biāo)簽數(shù)量超過了354時，則使用分組幀時隙ALOHA算法，來限制系統(tǒng)內(nèi)的響應(yīng)的標(biāo)簽數(shù)量。過程如圖4所示。

　　我們利用二進(jìn)制樹形分解法對標(biāo)簽進(jìn)行分組，如圖5所示。二進(jìn)制樹形結(jié)構(gòu)可以有效地對未識別標(biāo)簽進(jìn)行搜索。對分組后，獲取最后一個閱讀幀的結(jié)果(0或是1)來判斷是否繼續(xù)分組。如果結(jié)果是1，表示達(dá)到時隙分離條件，需要對標(biāo)簽繼續(xù)進(jìn)行分組，直到結(jié)構(gòu)是0為止。如果結(jié)果是0，表示未達(dá)到時隙分離條件，并采用動態(tài)幀時隙ALOHA算法對標(biāo)簽進(jìn)行識別。

　　對提出的算法進(jìn)行了仿真。結(jié)果表明：當(dāng)標(biāo)簽數(shù)小于354時，分組幀時隙ALOHA算法采用動態(tài)幀時隙ALOHA算法；當(dāng)標(biāo)簽數(shù)大于354時，分組幀時隙ALOHA算法對標(biāo)簽數(shù)進(jìn)行分組識別。所以標(biāo)簽數(shù)越多，分組幀時隙ALOHA算法所使用的時隙數(shù)越少，效率越高。如圖6所示。

　　4結(jié)束語

　　本文基于ALOHA算法，分別對幀時隙算法和動態(tài)幀時隙算法進(jìn)行研究和分析，并提出一種利用二進(jìn)制樹形分組的時隙ALHOA算法。對提出的分組算法和傳統(tǒng)的動態(tài)幀時隙算法進(jìn)行比較。當(dāng)標(biāo)簽數(shù)過大時，采用此方法有利于提高系統(tǒng)效率，并減少了計(jì)算和操作的復(fù)雜度。