標簽防沖撞ALOHA算法研究

1 引言 

射頻識別技術(shù)(Radio Frequency Identification，RFID)是自動識別技術(shù)的一種，近幾年發(fā)展非常迅速。射頻識別技術(shù)的工作方式是利用射頻方式進行非接觸雙向通信，以達到識別目標對象并交換數(shù)據(jù)。同其它自動識別技術(shù)相比，射頻識別技術(shù)有許多特點，如：無需光學(xué)可視、非接觸、數(shù)據(jù)存儲容量大、并能同時識別大量數(shù)據(jù)等，因此它可廣泛應(yīng)用到門禁控制、物流跟蹤、倉儲管理等領(lǐng)域。 

2 RFID系統(tǒng)的數(shù)據(jù)碰撞問題 

RFID系統(tǒng)一般由電子標簽、讀寫器以及天線組成。射頻識別系統(tǒng)交換的數(shù)據(jù)存儲在電子標簽中。電子標簽工作的能量供應(yīng)及與讀寫器之間的數(shù)據(jù)交換，都是通過電磁波的無線傳輸實現(xiàn)的。 

RFID系統(tǒng)的基本工作流程是：讀寫器通過發(fā)射天線發(fā)送一定頻率的射頻信號，當電子標簽進入發(fā)射天線工作區(qū)域時產(chǎn)生感應(yīng)電流，標簽獲得能量被激活；標簽將自身攜帶的數(shù)據(jù)編碼等信息通過標簽內(nèi)置天線發(fā)送出去；讀寫器接收天線接收到從標簽發(fā)送來的載波信號，讀寫器對接收到的信號進行解調(diào)和解碼，然后送到后臺主系統(tǒng)進行相關(guān)處理。 

RFID系統(tǒng)工作時，經(jīng)常有一個以上電子標簽同時處于閱讀器的作用范圍內(nèi)。當這些電子標簽同時將自身攜帶數(shù)據(jù)傳送給讀寫器時，讀寫器讀取數(shù)據(jù)就會出現(xiàn)沖突即數(shù)據(jù)碰撞，這將導(dǎo)致讀寫器的接收器不能讀出數(shù)據(jù)，降低RFID系統(tǒng)工作效率。在RFID無源標簽系統(tǒng)中，目前廣泛使用的防沖突算法大都是TDMA(Time Division Multiple Ac—cess)，主要分為2大類：基于Aloha的算法和基于樹的算法，本文在分析目前基于Aloha的各種算法特點和Aloha算法所采用的數(shù)學(xué)模型的基礎(chǔ)上，提出自己的改進算法。 

3 AL0HA算法 

Aloha算法最初用來解決網(wǎng)絡(luò)通信中數(shù)據(jù)包擁塞問題。Aloha算法是一種非常簡單的TDMA算法，該算法被廣泛應(yīng)用在RFID系統(tǒng)中。這種算法多采取“標簽先發(fā)言”的方式，即標簽一進入讀寫器的閱讀區(qū)域就自動向讀寫器發(fā)送其自身的ID，隨即標簽和讀寫器間開始通信。 

3．1 時隙ALOHA算法 
在Aloha算法中，標簽通過循環(huán)序列傳輸數(shù)據(jù)。標簽數(shù)據(jù)的傳輸時間僅僅為循環(huán)時間的一個小片段。在第一次傳輸數(shù)據(jù)完成后，標簽將等待一個相對較長的時間后再次傳輸數(shù)據(jù)。每個標簽的等待時間很小。 

按照這種方式，所有的標簽完成全部的數(shù)據(jù)傳輸給讀寫器后，重復(fù)的過程才會結(jié)束。分析Aloha算法的運行機制，不難發(fā)現(xiàn)當一個標簽發(fā)送數(shù)據(jù)給讀寫器時，另外一個標簽也開始發(fā)送數(shù)據(jù)給讀寫器，這時標簽數(shù)據(jù)碰撞不可避免發(fā)生。 

鑒于以上缺點，研究人員提出時隙Aloha算法¨ 。在該算法中，標簽僅能在時隙的開始傳輸數(shù)據(jù)。用于傳輸數(shù)據(jù)的時隙數(shù)由讀寫器控制，只有當讀寫器分配所有的時隙后，標簽才能利用這些時隙傳輸數(shù)據(jù)。因此與純Aloha算法不同，時隙Aloha算法是隨機的詢問驅(qū)動的TDMA防沖撞算法。 

因為標簽僅僅在確定的時隙中傳輸數(shù)據(jù)，所以該算法的沖撞發(fā)生的頻率僅僅是純Aloha算法的一半而且系統(tǒng)的數(shù)據(jù)吞吐性能卻增加一倍。 

3．2 幀時隙ALOHA算法的基本原理 
雖然時隙Aloha算法提高系統(tǒng)的吞吐量，但是當大量標簽進入系統(tǒng)時，該算法的效率并不高，因此幀時隙算法被提出。幀時隙算法是將多個時隙打包成為一幀，標簽必須選擇一幀中的某個時隙向讀寫器傳輸數(shù)據(jù)。這也是幀時隙Aloha算法與純的時隙Aloha算法的不同點[2]。 

3．3 動態(tài)幀時隙ALOHA算法 
在幀時隙Aloha算法中，所有的幀具有相同的長度，即每一幀中的時隙數(shù)是相同的且是固定的。由于讀寫器并不知道標簽數(shù)量，當標簽數(shù)量遠大于幀時隙數(shù)時，一幀中的所有時隙都會發(fā)生碰撞，讀寫器不能讀取標簽信息；當標簽數(shù)遠小于一幀中時隙數(shù)時，識別過程中將有許多時隙被浪費掉。動態(tài)幀時隙算法通過根據(jù)識別標簽的數(shù)量來改變幀長度來客服動態(tài)幀時隙的不足。 

4 改進的動態(tài)幀時隙ALONA算法的實現(xiàn) 

4．1 算法分析 
通常，在幀時隙Aloha防沖撞算法中，當系統(tǒng)標簽數(shù)量變得很大時，系統(tǒng)效率就開始降低。當讀寫器設(shè)置幀的長度(包含的時隙數(shù))為N，響應(yīng)的標簽數(shù)為n，則r個標簽在一個時隙中發(fā)生碰撞的二項分布的概率是： 

4．2 幀長度的改變方法 
根據(jù)以上的分析，動態(tài)幀時隙算法通過動態(tài)的調(diào)整幀的長度，使幀的長度和未識別的標簽的數(shù)量接近，使系統(tǒng)的標簽識別率達到最大。因此正確的獲取當前未識別標簽的數(shù)據(jù)是該算法成功的關(guān)鍵。 

目前流行的幀長度調(diào)整方法有兩種：一種方法是根據(jù)前一幀通信獲取到的空的時隙數(shù)、發(fā)生碰撞的時隙數(shù)和只有一個標簽傳輸數(shù)據(jù)的時隙數(shù)來估計標簽的數(shù)量，由估計的標簽的數(shù)量來調(diào)整下一幀的長度；另一種方法是系統(tǒng)每次啟動讀循環(huán)時設(shè)定的初始幀長為{2、4、8、16、32、64、128、256}。 

為估計RFID標簽數(shù)量，在第一種方法中引人多址接人通信系統(tǒng)中著名的三重反饋模型。s表示只有一個標簽傳輸其攜帶數(shù)據(jù)的時隙數(shù)，即數(shù)據(jù)傳輸成功的時隙數(shù)。E表示沒有標簽傳輸數(shù)據(jù)的空的時隙數(shù)。c表示同時有多個標簽在傳輸數(shù)據(jù)的時隙數(shù)，即發(fā)生數(shù)據(jù)包碰撞的時隙數(shù)。以上所有的情況都不考慮數(shù)據(jù)捕獲的效率和噪聲的影響。 

在實際的RFID系統(tǒng)中，被正確識別的標簽將不再響應(yīng)讀寫器發(fā)送的數(shù)據(jù)傳輸請求。同樣，再下面的算法中，成功傳輸數(shù)據(jù)的標簽也不在響應(yīng)讀寫器的請求。 

文獻4中，Schout提出了再一幀中選擇時隙i傳輸數(shù)據(jù)的標簽數(shù)滿足柏松分布_4]，因此一幀中不能被識別的標簽數(shù)為：I1 =2．93C。此處的c表示發(fā)生碰撞的時隙數(shù)。 

根據(jù)4．1節(jié)的推導(dǎo)，通過一次讀寫器的幀周期，容易得到當前幀中s、E、c沒有被讀取的標簽數(shù)I1 =I1一S 

4．3 改進的動態(tài)幀識別流程 
根據(jù)以上分析，在估計標簽數(shù)量的過程中根據(jù)情況使用上述兩種方案綜合。 
(1)根據(jù)具體的應(yīng)用模式設(shè)定初始化的幀大小F，初始化讀寫器的時隙數(shù)slotCount=F； 
(2)讀寫器發(fā)送以F為參數(shù)的清點指令，等待標簽回復(fù)，根據(jù)收到的回復(fù)統(tǒng)計c、E和S；在任何情況下，讀寫器的時隙數(shù)減一：slotCount一一； 
(3)判斷slotCount是否為零：slotCount為零，進一步判斷c是否為零，c為零，結(jié)束清點，c不為零，調(diào)用幀長度調(diào)整子程序重新設(shè)定F，返回步驟(1)；slotCount不為零，發(fā)送指令，進入下一時隙，返回步驟(3)。 
幀長度子程序： 
如果是第一次調(diào)整幀長度，令F=I1一S；否則比較上次的系統(tǒng)與前次的系統(tǒng)效率，如果上次的系統(tǒng)效率比前次的大，調(diào)整幀長度令F=I1一S，反之，調(diào)整幀長度F=2．93C。 

5 結(jié)束語 

標簽沖突是影響RFID應(yīng)用系統(tǒng)效率的關(guān)鍵問題之一，動態(tài)ALOHA是根據(jù)沖突問題本身的數(shù)學(xué)特性采取的一種RFID的反沖突方法，通過動態(tài)的調(diào)整幀的大小實現(xiàn)系統(tǒng)讀取效率的改善是有效的解決該問題的方法之一。本文綜合幾種標簽估計方法，改進多標簽識別流程圖，在標簽數(shù)目較多的時候效率將大幅提高。 

參考文獻 

[1]L．G．Robeas．Extensions of Packet Communication Tech—nology to a Hand Held Personal Terminal，AFIPS Conf．Proc．，Spring Joint Computer Conf．，1 972，vo1．40，295— 298 
[2]J．E．Wieselthier，A．Ephremides，and L．A．Michaels．An Exact Analysis and Perform ance Evaluation of Framed ALOHA with Capture[J]．IEEE Transactions on Communi—,cations，1989，vo1．37，125—137· 
[3]R．Rom and M．Sidi．Multiple Access Proto —cols／Perform ance and Analysis．Springer—Verlag，47—77，1990． 
[4]F．C．Schoute．Dynam ic Frame Length ALOHA[J]．IEEE Transactions on Communications，Apr．，1983，vo1． 31，565—568 
[5]R．Du，H．Okada，H．Nakanishi，H．Sanada，and Y．Tezuka． “Perform ance Evaluation and Optimization of ALOHA Scheme with Capture Effect”．Conf．Rec．GLO—BECOM ’87，Nov．，1987，555—56o 
[6]陳香，薛小平，張恩東．標簽防沖突算法的研究[J]．通信與信息技術(shù)，2006(5)：13—15

原文PDF下載