幀時隙ALOHA防碰撞算法仿真與研究

馮 媛，蔡增玉，譚前進，李娜娜

（1.鄭州輕工業(yè)學院，鄭州450002；2.大連海洋大學 經(jīng)濟管理學院，遼寧 大連116023）

射頻識別（RFID）是一種非接觸式自動識別技術，它利用無線射頻信號進行非接觸雙向通信，實現(xiàn)對特定物體的自動識別，具有識別距離遠、抗干擾性強、可同時識別多個目標等優(yōu)點，近年來得到了廣泛應用［1］.當閱讀器識別區(qū)域內(nèi)存在多個標簽時，如果它們同時向閱讀器發(fā)送標識信息，閱讀器無法同時識別這些標識信息，就產(chǎn)生了標簽沖突，解決此沖突的方法稱為防碰撞算法.標簽防碰撞算法對于RFID系統(tǒng)的識別能力至關重要，是RFID系統(tǒng)的關鍵［2］.目前，高頻段的防碰撞算法一般采用ALOHA協(xié)議以及改進的ALOHA算法.本文在對幀時隙ALOHA研究的基礎上，實現(xiàn)了基于MATLAB的幀時隙ALOHA仿真算法，并研究了幀時隙ALOHA中標簽數(shù)量、幀長度、識別時間、系統(tǒng)效率、系統(tǒng)負載等參數(shù)之間的關系，為相關應用系統(tǒng)的設計提供了參考.

1 幀時隙ALOHA算法分析

1.1 ALOHA算法

所有多路存取方法中，最簡單的方法是純ALOHA算法.純ALOHA算法的基本原理是：當標簽進入閱讀器工作區(qū)域并被激活后，標簽隨機選擇某個時間發(fā)送信息，閱讀器根據(jù)接收到的信號判斷其有無碰撞發(fā)生，若發(fā)生碰撞，則發(fā)送命令讓標簽停止發(fā)送，標簽等待隨機時間，再重新發(fā)送標簽自身序列號，以減少碰撞［3］.當標簽數(shù)目很少時，純ALOHA算法能表現(xiàn)出良好的性能；但是，隨著標簽數(shù)目的增加，信道占有率增加到一定閾值后，其執(zhí)行性能就變得相當差.純ALOHA算法的優(yōu)點是算法簡單，易于理解和實現(xiàn)；缺點是沖突發(fā)生的概率很大［4］，存在錯誤判決問題.本文針對這些問題，提出了一些擴展的方法來改善識別算法在RFID系統(tǒng)中的可行性和有效性，其中比較典型的有時隙ALOHA算法、幀時隙ALOHA算法等.

1.2 幀時隙ALOHA算法

時隙ALOHA算法基于純ALOHA算法，把識別時間分成多個時隙，被識別標簽只能在時隙的開始傳輸數(shù)據(jù).如果在一個時隙內(nèi)有多個標簽響應，閱讀器就會檢測多個標簽的響應而產(chǎn)生沖突，這時閱讀器通知標簽在下一輪循環(huán)中重新選擇時隙發(fā)送數(shù)據(jù)，直至所有的標簽都被識別出來.這樣，在一個時隙內(nèi)，只能單個標簽成功發(fā)送或多個標簽發(fā)生沖突，避免了純ALOHA算法的部分沖突的情況.因為標簽只在確定的時隙中傳輸數(shù)據(jù)，所以該算法的沖突發(fā)生概率僅為純ALOHA算法的一半，而系統(tǒng)的數(shù)據(jù)吞吐性能卻增加一倍［5］.時隙ALOHA算法避免了純ALOHA算法的部分沖突，提高了信道利用率.

幀時隙ALOHA算法是時隙ALOHA算法的擴展.幀時隙算法是將若干個時隙組合成一幀，標簽選擇某一幀中的某個時隙向讀寫器傳輸數(shù)據(jù)［5］.幀時隙ALOHA算法對系統(tǒng)要求較簡單，識別速度較快，在很多國際和國內(nèi)RFID標準中被采用.幀時隙ALOHA算法在閱讀器發(fā)出讀取命令后，等待標簽應答：當一個時隙中僅有一個標簽應答時，該標簽被正確識別；當一個時隙中沒有標簽應答時，該時隙為空時隙；當一個時隙中有2個或2個以上的標簽應答時，則發(fā)生沖突，該時隙中標簽不能被識別，所有未被識別的標簽需要重新選擇時隙來應答，直到所有標簽被識別.

1.3 幀時隙ALOHA算法理論分析

假設一幀含有N個時隙（為便于討論，用N表示幀長），共有n個待檢測的標簽，每個標簽以均等的概率1／N來隨機選擇一幀中的某個時隙發(fā)送數(shù)據(jù)，可以得到在一個時隙里有k個標簽同時發(fā)送數(shù)據(jù)的概率服從二項分布，即：

在幀時隙ALOHA算法中，當在一個時隙內(nèi)只發(fā)送一個標簽數(shù)據(jù)時，標簽才能被閱讀器正確識別，所以在一個時隙內(nèi)正確識別一個標簽的概率為P（1）.每幀包含N個時隙，所以系統(tǒng)的吞吐率T（n，N）為：

T（n，N）＝一幀中識別出的標簽數(shù)／當前幀的幀長＝N＊P（1）／N＝P（1）

通過數(shù)學運算可以推出，當N≥1，且n≈N時，系統(tǒng)吞吐率達到最大，為36.8%.

2 幀時隙ALOHA算法仿真分析

筆者進行了基于MATLAB的幀時隙ALOHA算法仿真，通過仿真模擬了幀時隙ALOHA算法的防碰撞過程.為了便于分析，設定讀取一個RFID標簽信息的時間等于一個時隙的時長.

2.1 標簽數(shù)量對識別時間的影響

參數(shù)設定：時隙數(shù)固定為256，標簽的數(shù)量從1個增加到1 000個，仿真次數(shù)為10次.統(tǒng)計得到系統(tǒng)中標簽數(shù)量增加時識別所有標簽所用的總時隙數(shù)量的變化情況，如圖1所示.當系統(tǒng)中標簽的數(shù)量較少時，識別所有標簽的總用時較短，說明讀寫器識別率較高；識別時間增長比較緩慢，說明標簽的成功識別率基本穩(wěn)定；隨著標簽數(shù)量的增加，當標簽數(shù)量超過300個后，識別所有標簽的總時隙數(shù)以較大幅度增加，標簽的成功識別率以較大幅度降低.

圖1 標簽數(shù)量與識別時間的關系圖

仿真結(jié)論1：當標簽數(shù)大于每幀的時隙數(shù)后，識別讀寫器范圍內(nèi)所有標簽的總用時會隨著標簽數(shù)量的增加而顯著增大.

2.2 幀長度對識別時間的影響

參數(shù)設定：標簽的數(shù)量固定為30個，一幀中最大時隙數(shù)設為120，仿真次數(shù)為100次.統(tǒng)計在不同的最大時隙數(shù)量下識別30個標簽的總用時的變化情況，得到標簽數(shù)量和幀長度的對應關系，如圖2所示.從圖2可得出，當一幀中的時隙數(shù)小于10時，識別30個標簽的總用時非常多；隨著一幀中的時隙數(shù)的增加，識別所有標簽的總用時急劇減少；當幀長度為12～20個時隙時，幀時隙ALOHA算法的性能最好，識別所有標簽的總用時最短；當一幀中的時隙數(shù)從20增加到120時，識別所有標簽的總用時增加.

圖2 幀長度與識別時間的關系圖

仿真結(jié)論2：當時隙數(shù)由遠小于標簽數(shù)逐漸變大時，系統(tǒng)識別所有標簽所用的時間將會急劇減少；而在標簽數(shù)遠小于時隙數(shù)時，雖然多個標簽發(fā)生沖突的次數(shù)將會減少，但是一幀中的時隙數(shù)相對較多，導致識別所有標簽的總用時依然較多，從而造成時隙的浪費.因此，每幀的時隙數(shù)與標簽數(shù)不宜相差太大.

2.3 系統(tǒng)效率和標簽數(shù)的關系

一幀中時隙數(shù)固定為256，標簽的數(shù)量固定為100～800個，仿真次數(shù)為10次.統(tǒng)計隨著標簽數(shù)量的增加系統(tǒng)效率的變化，得到標簽數(shù)量和幀長度的對應關系，如圖3所示.當系統(tǒng)中標簽的數(shù)量較少（小于256個）時，系統(tǒng)效率較低；隨著標簽數(shù)量的增加，系統(tǒng)效率快速增長；當標簽數(shù)量到達256個時，系統(tǒng)效率到達最大，為36%；當標簽數(shù)量超過256個后，系統(tǒng)的效率緩慢下降.

圖3 系統(tǒng)效率與標簽數(shù)的關系圖

仿真結(jié)論3：當標簽數(shù)大于或小于每幀的時隙數(shù)時，系統(tǒng)的效率較低；當標簽數(shù)等于每幀的時隙數(shù)時，系統(tǒng)的效率達到最大值，與前面理論分析相同.

2.4 系統(tǒng)負載與吞吐量

一幀中時隙數(shù)固定為64，系統(tǒng)負載從0增加到4，仿真次數(shù)為50次.統(tǒng)計隨著系統(tǒng)負載的增加系統(tǒng)負載與吞吐量的對應關系，如圖4所示.當系統(tǒng)負載小于0.5時，系統(tǒng)吞吐量較低；隨著負載的增加，系統(tǒng)吞吐量快速增長；當系統(tǒng)負載在1附近時，系統(tǒng)吞吐量到達最大；當系統(tǒng)負載大于1時，隨著系統(tǒng)負載的增加，吞吐量逐漸下降.

圖4 系統(tǒng)負載與吞吐量的關系圖

仿真結(jié)論4：當系統(tǒng)負載大于或小于1時，系統(tǒng)的吞吐量較低；當系統(tǒng)負載等于1時，系統(tǒng)的吞吐量最大.

3 結(jié) 語

本文對幀時隙ALOHA算法進行了性能分析和仿真分析，對碰撞過程中的相關參數(shù)進行了統(tǒng)計分析，獲得了RFID標簽識別中標簽數(shù)量、幀長度與識別時間的關系，以及標簽數(shù)量、系統(tǒng)負載和系統(tǒng)效率的關系.如何利用所得結(jié)論設計自適應的動態(tài)幀時隙ALOHA算法，是下一步研究工作.

［1］李寶山，羅春青.RFID防碰撞算法計算機仿真模型的研究［J］.自動化與儀器儀表，2010（5）：13－14.

［2］鄧曉，何怡剛，陳洪云，等.幀時隙ALOHA反碰撞算法仿真及數(shù)據(jù)分析［J］.汕頭大學學報（自然科學版），2008，23（3）：58－62.

［3］徐海峰，姜暉.RFID系統(tǒng)實時高效ALOHA防沖突算法研究與仿真［J］.計算機與數(shù)字工程，2011，39（5）：19－22.

［4］李晶，欒爽，金美善.RFID防碰撞算法中ALOHA算法的研究［J］.電腦編程技巧與維護，2009（s1）：14－16.

［5］喻成，魏亮，李磊.標簽防沖撞 ALOHA算法研究［J］.計算機與數(shù)字工程，2007，35（9）：13－15.