登錄
注冊
標簽防沖撞ALOHA算法研究
作者：中南民族大學計算機科學學院 喻成 魏亮 李磊
來源：RFID世界網
日期：2007-12-03 10:34:00
摘要：RFID系統中，多標簽引起的沖突是影響系統效率的難題。Aloha算法是運用比較普遍的一種防沖突算法，對目前常用的Aloha算法及其衍生算發進行研究，提出優化的標簽防沖突算法。
1 引言
射頻識別技術(Radio Frequency Identification，RFID)是自動識別技術的一種，近幾年發展非常迅速。射頻識別技術的工作方式是利用射頻方式進行非接觸雙向通信，以達到識別目標對象并交換數據。同其它自動識別技術相比，射頻識別技術有許多特點，如：無需光學可視、非接觸、數據存儲容量大、并能同時識別大量數據等，因此它可廣泛應用到門禁控制、物流跟蹤、倉儲管理等領域。
2 RFID系統的數據碰撞問題
RFID系統一般由電子標簽、讀寫器以及天線組成。射頻識別系統交換的數據存儲在電子標簽中。電子標簽工作的能量供應及與讀寫器之間的數據交換，都是通過電磁波的無線傳輸實現的。
RFID系統的基本工作流程是：讀寫器通過發射天線發送一定頻率的射頻信號，當電子標簽進入發射天線工作區域時產生感應電流，標簽獲得能量被激活；標簽將自身攜帶的數據編碼等信息通過標簽內置天線發送出去；讀寫器接收天線接收到從標簽發送來的載波信號，讀寫器對接收到的信號進行解調和解碼，然后送到后臺主系統進行相關處理。
RFID系統工作時，經常有一個以上電子標簽同時處于閱讀器的作用范圍內。當這些電子標簽同時將自身攜帶數據傳送給讀寫器時，讀寫器讀取數據就會出現沖突即數據碰撞，這將導致讀寫器的接收器不能讀出數據，降低RFID系統工作效率。在RFID無源標簽系統中，目前廣泛使用的防沖突算法大都是TDMA(Time Division Multiple Ac—cess)，主要分為2大類：基于Aloha的算法和基于樹的算法，本文在分析目前基于Aloha的各種算法特點和Aloha算法所采用的數學模型的基礎上，提出自己的改進算法。
3 AL0HA算法
Aloha算法最初用來解決網絡通信中數據包擁塞問題。Aloha算法是一種非常簡單的TDMA算法，該算法被廣泛應用在RFID系統中。這種算法多采取“標簽先發言”的方式，即標簽一進入讀寫器的閱讀區域就自動向讀寫器發送其自身的ID，隨即標簽和讀寫器間開始通信。
3．1 時隙ALOHA算法
在Aloha算法中，標簽通過循環序列傳輸數據。標簽數據的傳輸時間僅僅為循環時間的一個小片段。在第一次傳輸數據完成后，標簽將等待一個相對較長的時間后再次傳輸數據。每個標簽的等待時間很小。
鑒于以上缺點，研究人員提出時隙Aloha算法¨ 。在該算法中，標簽僅能在時隙的開始傳輸數據。用于傳輸數據的時隙數由讀寫器控制，只有當讀寫器分配所有的時隙后，標簽才能利用這些時隙傳輸數據。因此與純Aloha算法不同，時隙Aloha算法是隨機的詢問驅動的TDMA防沖撞算法。
因為標簽僅僅在確定的時隙中傳輸數據，所以該算法的沖撞發生的頻率僅僅是純Aloha算法的一半而且系統的數據吞吐性能卻增加一倍。
雖然時隙Aloha算法提高系統的吞吐量，但是當大量標簽進入系統時，該算法的效率并不高，因此幀時隙算法被提出。幀時隙算法是將多個時隙打包成為一幀，標簽必須選擇一幀中的某個時隙向讀寫器傳輸數據。這也是幀時隙Aloha算法與純的時隙Aloha算法的不同點[2]。
在幀時隙Aloha算法中，所有的幀具有相同的長度，即每一幀中的時隙數是相同的且是固定的。由于讀寫器并不知道標簽數量，當標簽數量遠大于幀時隙數時，一幀中的所有時隙都會發生碰撞，讀寫器不能讀取標簽信息；當標簽數遠小于一幀中時隙數時，識別過程中將有許多時隙被浪費掉。動態幀時隙算法通過根據識別標簽的數量來改變幀長度來客服動態幀時隙的不足。
4 改進的動態幀時隙ALONA算法的實現
4．1 算法分析
通常，在幀時隙Aloha防沖撞算法中，當系統標簽數量變得很大時，系統效率就開始降低。當讀寫器設置幀的長度(包含的時隙數)為N，響應的標簽數為n，則r個標簽在一個時隙中發生碰撞的二項分布的概率是：
4．2 幀長度的改變方法
根據以上的分析，動態幀時隙算法通過動態的調整幀的長度，使幀的長度和未識別的標簽的數量接近，使系統的標簽識別率達到最大。因此正確的獲取當前未識別標簽的數據是該算法成功的關鍵。
目前流行的幀長度調整方法有兩種：一種方法是根據前一幀通信獲取到的空的時隙數、發生碰撞的時隙數和只有一個標簽傳輸數據的時隙數來估計標簽的數量，由估計的標簽的數量來調整下一幀的長度；另一種方法是系統每次啟動讀循環時設定的初始幀長為{2、4、8、16、32、64、128、256}。
為估計RFID標簽數量，在第一種方法中引人多址接人通信系統中著名的三重反饋模型。s表示只有一個標簽傳輸其攜帶數據的時隙數，即數據傳輸成功的時隙數。E表示沒有標簽傳輸數據的空的時隙數。c表示同時有多個標簽在傳輸數據的時隙數，即發生數據包碰撞的時隙數。以上所有的情況都不考慮數據捕獲的效率和噪聲的影響。
在實際的RFID系統中，被正確識別的標簽將不再響應讀寫器發送的數據傳輸請求。同樣，再下面的算法中，成功傳輸數據的標簽也不在響應讀寫器的請求。
文獻4中，Schout提出了再一幀中選擇時隙i傳輸數據的標簽數滿足柏松分布_4]，因此一幀中不能被識別的標簽數為：I1 =2．93C。此處的c表示發生碰撞的時隙數。
根據4．1節的推導，通過一次讀寫器的幀周期，容易得到當前幀中s、E、c沒有被讀取的標簽數I1 =I1一S
4．3 改進的動態幀識別流程
根據以上分析，在估計標簽數量的過程中根據情況使用上述兩種方案綜合。
(1)根據具體的應用模式設定初始化的幀大小F，初始化讀寫器的時隙數slotCount=F；
(2)讀寫器發送以F為參數的清點指令，等待標簽回復，根據收到的回復統計c、E和S；在任何情況下，讀寫器的時隙數減一：slotCount一一；
(3)判斷slotCount是否為零：slotCount為零，進一步判斷c是否為零，c為零，結束清點，c不為零，調用幀長度調整子程序重新設定F，返回步驟(1)；slotCount不為零，發送指令，進入下一時隙，返回步驟(3)。
幀長度子程序：
如果是第一次調整幀長度，令F=I1一S；否則比較上次的系統與前次的系統效率，如果上次的系統效率比前次的大，調整幀長度令F=I1一S，反之，調整幀長度F=2．93C。
5 結束語
標簽沖突是影響RFID應用系統效率的關鍵問題之一，動態ALOHA是根據沖突問題本身的數學特性采取的一種RFID的反沖突方法，通過動態的調整幀的大小實現系統讀取效率的改善是有效的解決該問題的方法之一。本文綜合幾種標簽估計方法，改進多標簽識別流程圖，在標簽數目較多的時候效率將大幅提高。
參考文獻
[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]．通信與信息技術，2006(5)：13—15
原文PDF下載
射頻識別技術(Radio Frequency Identification，RFID)是自動識別技術的一種，近幾年發展非常迅速。射頻識別技術的工作方式是利用射頻方式進行非接觸雙向通信，以達到識別目標對象并交換數據。同其它自動識別技術相比，射頻識別技術有許多特點，如：無需光學可視、非接觸、數據存儲容量大、并能同時識別大量數據等，因此它可廣泛應用到門禁控制、物流跟蹤、倉儲管理等領域。
2 RFID系統的數據碰撞問題
RFID系統一般由電子標簽、讀寫器以及天線組成。射頻識別系統交換的數據存儲在電子標簽中。電子標簽工作的能量供應及與讀寫器之間的數據交換，都是通過電磁波的無線傳輸實現的。
RFID系統的基本工作流程是：讀寫器通過發射天線發送一定頻率的射頻信號，當電子標簽進入發射天線工作區域時產生感應電流，標簽獲得能量被激活；標簽將自身攜帶的數據編碼等信息通過標簽內置天線發送出去；讀寫器接收天線接收到從標簽發送來的載波信號，讀寫器對接收到的信號進行解調和解碼，然后送到后臺主系統進行相關處理。
RFID系統工作時，經常有一個以上電子標簽同時處于閱讀器的作用范圍內。當這些電子標簽同時將自身攜帶數據傳送給讀寫器時，讀寫器讀取數據就會出現沖突即數據碰撞，這將導致讀寫器的接收器不能讀出數據，降低RFID系統工作效率。在RFID無源標簽系統中，目前廣泛使用的防沖突算法大都是TDMA(Time Division Multiple Ac—cess)，主要分為2大類：基于Aloha的算法和基于樹的算法，本文在分析目前基于Aloha的各種算法特點和Aloha算法所采用的數學模型的基礎上，提出自己的改進算法。
3 AL0HA算法
Aloha算法最初用來解決網絡通信中數據包擁塞問題。Aloha算法是一種非常簡單的TDMA算法，該算法被廣泛應用在RFID系統中。這種算法多采取“標簽先發言”的方式，即標簽一進入讀寫器的閱讀區域就自動向讀寫器發送其自身的ID，隨即標簽和讀寫器間開始通信。
3．1 時隙ALOHA算法
在Aloha算法中，標簽通過循環序列傳輸數據。標簽數據的傳輸時間僅僅為循環時間的一個小片段。在第一次傳輸數據完成后，標簽將等待一個相對較長的時間后再次傳輸數據。每個標簽的等待時間很小。
鑒于以上缺點，研究人員提出時隙Aloha算法¨ 。在該算法中，標簽僅能在時隙的開始傳輸數據。用于傳輸數據的時隙數由讀寫器控制，只有當讀寫器分配所有的時隙后，標簽才能利用這些時隙傳輸數據。因此與純Aloha算法不同，時隙Aloha算法是隨機的詢問驅動的TDMA防沖撞算法。
因為標簽僅僅在確定的時隙中傳輸數據，所以該算法的沖撞發生的頻率僅僅是純Aloha算法的一半而且系統的數據吞吐性能卻增加一倍。
雖然時隙Aloha算法提高系統的吞吐量，但是當大量標簽進入系統時，該算法的效率并不高，因此幀時隙算法被提出。幀時隙算法是將多個時隙打包成為一幀，標簽必須選擇一幀中的某個時隙向讀寫器傳輸數據。這也是幀時隙Aloha算法與純的時隙Aloha算法的不同點[2]。
在幀時隙Aloha算法中，所有的幀具有相同的長度，即每一幀中的時隙數是相同的且是固定的。由于讀寫器并不知道標簽數量，當標簽數量遠大于幀時隙數時，一幀中的所有時隙都會發生碰撞，讀寫器不能讀取標簽信息；當標簽數遠小于一幀中時隙數時，識別過程中將有許多時隙被浪費掉。動態幀時隙算法通過根據識別標簽的數量來改變幀長度來客服動態幀時隙的不足。
4 改進的動態幀時隙ALONA算法的實現
4．1 算法分析
通常，在幀時隙Aloha防沖撞算法中，當系統標簽數量變得很大時，系統效率就開始降低。當讀寫器設置幀的長度(包含的時隙數)為N，響應的標簽數為n，則r個標簽在一個時隙中發生碰撞的二項分布的概率是：
4．2 幀長度的改變方法
根據以上的分析，動態幀時隙算法通過動態的調整幀的長度，使幀的長度和未識別的標簽的數量接近，使系統的標簽識別率達到最大。因此正確的獲取當前未識別標簽的數據是該算法成功的關鍵。
目前流行的幀長度調整方法有兩種：一種方法是根據前一幀通信獲取到的空的時隙數、發生碰撞的時隙數和只有一個標簽傳輸數據的時隙數來估計標簽的數量，由估計的標簽的數量來調整下一幀的長度；另一種方法是系統每次啟動讀循環時設定的初始幀長為{2、4、8、16、32、64、128、256}。
為估計RFID標簽數量，在第一種方法中引人多址接人通信系統中著名的三重反饋模型。s表示只有一個標簽傳輸其攜帶數據的時隙數，即數據傳輸成功的時隙數。E表示沒有標簽傳輸數據的空的時隙數。c表示同時有多個標簽在傳輸數據的時隙數，即發生數據包碰撞的時隙數。以上所有的情況都不考慮數據捕獲的效率和噪聲的影響。
在實際的RFID系統中，被正確識別的標簽將不再響應讀寫器發送的數據傳輸請求。同樣，再下面的算法中，成功傳輸數據的標簽也不在響應讀寫器的請求。
文獻4中，Schout提出了再一幀中選擇時隙i傳輸數據的標簽數滿足柏松分布_4]，因此一幀中不能被識別的標簽數為：I1 =2．93C。此處的c表示發生碰撞的時隙數。
根據4．1節的推導，通過一次讀寫器的幀周期，容易得到當前幀中s、E、c沒有被讀取的標簽數I1 =I1一S
4．3 改進的動態幀識別流程
根據以上分析，在估計標簽數量的過程中根據情況使用上述兩種方案綜合。
(1)根據具體的應用模式設定初始化的幀大小F，初始化讀寫器的時隙數slotCount=F；
(2)讀寫器發送以F為參數的清點指令，等待標簽回復，根據收到的回復統計c、E和S；在任何情況下，讀寫器的時隙數減一：slotCount一一；
(3)判斷slotCount是否為零：slotCount為零，進一步判斷c是否為零，c為零，結束清點，c不為零，調用幀長度調整子程序重新設定F，返回步驟(1)；slotCount不為零，發送指令，進入下一時隙，返回步驟(3)。
幀長度子程序：
如果是第一次調整幀長度，令F=I1一S；否則比較上次的系統與前次的系統效率，如果上次的系統效率比前次的大，調整幀長度令F=I1一S，反之，調整幀長度F=2．93C。
5 結束語
標簽沖突是影響RFID應用系統效率的關鍵問題之一，動態ALOHA是根據沖突問題本身的數學特性采取的一種RFID的反沖突方法，通過動態的調整幀的大小實現系統讀取效率的改善是有效的解決該問題的方法之一。本文綜合幾種標簽估計方法，改進多標簽識別流程圖，在標簽數目較多的時候效率將大幅提高。
參考文獻
[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]．通信與信息技術，2006(5)：13—15
原文PDF下載
