基于A(yíng)LOHA 算法的 RFID 防碰撞技術(shù)研究

　　1射頻識別系統介紹

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

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

　　2系統防碰撞

　　RFID系統工作時(shí)，當有2個(gè)或2個(gè)以上的電子標簽同時(shí)在同一個(gè)讀寫(xiě)器的作用范圍內向讀寫(xiě)器發(fā)送數據的時(shí)候，就會(huì )出現信號的干擾，這個(gè)干擾就稱(chēng)為碰撞，其結果將會(huì )導致該次傳輸的失敗，因為必須采用適當的技術(shù)防止碰撞的產(chǎn)生。

　　3ALOHA算法及仿真結果

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

　　3．1幀時(shí)隙ALOHA算法

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

　　讀寫(xiě)器當前使用幀的長(cháng)度為N，標簽數為n，在一個(gè)時(shí)隙中存在r個(gè)標簽的概率為：

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

　　其中，a₁ ^N.n表示只有一個(gè)標簽占據一個(gè)時(shí)隙的時(shí)隙總數。其中幀長(cháng)度為N，標簽總數為n。
系統效率為PN:

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

　　根據上式可推出當幀的長(cháng)度為N時(shí)，效率最高的標簽響應數為：

　　當標簽數為n時(shí)，幀長(cháng)度的最佳值為：

　　當n很大時(shí)，將上式泰勒爾展開(kāi)：

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

　　3．2動(dòng)態(tài)幀時(shí)隙ALOHA算法

　　為使系統效率最優(yōu)，提出動(dòng)態(tài)幀時(shí)隙ALOHA(DynamicFramedSlottedAloha，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è)標簽的概率，根據二項分布原理，得：

　　利用切比雪夫不等式估計標簽數目。

　　3．3分組幀時(shí)隙ALOHA算法

　　在RFID系統中，我們經(jīng)常使用動(dòng)態(tài)幀時(shí)隙ALOHA算
法。但是由于最大幀時(shí)隙數有限制。當標簽數量過(guò)大時(shí)，我們不能無(wú)限制地增加幀的時(shí)隙數。因此提出了分組幀時(shí)隙ALOHA(GroupFramedSlottedAloha，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ǔ)

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