一種穩定高效的動態幀時隙ＡＬＯＨＡ算法
2009-01-01 00:00:00程良倫林偉勇
計算機應用研究 2009年1期
（廣東工業大學 自動化學院， 廣州 510006）
摘 要：基于ALOHA的隨機性算法是解決標簽碰撞的常用方法，在分析這類方法的基礎上，提出了一種基于倍乘因子和分組思想的優化方法。改進算法實現簡單，且大量的統計及仿真數據表明，該算法取得了穩定的高系統效率，縮短了標簽的識別時間。
關鍵詞：射頻識別； 標簽反碰撞； 動態幀時隙ALOHA； 倍乘因子； 分組
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)01008503
Steady dynamic framed slot ALOHA algorithm with high system efficiency
CHENG Lianglun， LIN Weiyong
(Institute of Automation， Guangdong University of Technology， Guangzhou 510006， China)
Abstract:ALOHAbased stochastic algorithm is one of the most frequentlyused approaches in solving tags collision. Based on the introduction of these kinds of anticollision algorithm， this paper proposed an optimal algorithm which based on multiple factor and grouping. The advanced algorithm is easy to achieve. Simulation and statistic indicates that this new algorithm can get high and steady system efficiency and shorten the tags identification time.
Key words：RFID; tag anticollision; dynamic framed slot ALOHA algorithm; multiple factor; grouping
射頻識別（RFID）技術是自動識別技術的一種，通過無線射頻方式進行非接觸雙向數據通信，對目標加以識別并獲取信息[1]。隨著RFID技術的不斷成熟，對供應鏈管理、物流、工商業自動化、交通運輸控制管理和零售等領域產生越來越重要的影響，并將成為未來自動識別技術的主流[2]。
RFID系統主要由電子標簽、讀寫器和信息處理系統三部分組成。標簽反碰撞技術是RFID領域的研究熱點和重點之一。標簽碰撞是指讀寫器作用范圍內的兩個或兩個以上標簽同時向讀寫器返回信息時產生的信號干擾，導致標簽無法正確識別；解決碰撞的方法就稱為反碰撞算法，目前有確定性和概率性兩種算法。概率性算法是在ALOHA算法[3，4]基礎上的研究與改進，主要包括時隙ALOHA（SA）[4~6]、時隙隨機算法（SR）[6]、幀時隙ALOHA（FSA）[7，8]、動態幀時隙ALOHA（DFSA）[7，9~11]和增強型動態幀時隙ALOHA（EDFSA）[12~14]。DFSA和EDFSA算法中，共同關注的一個問題是如何根據讀寫器作用范圍內的標簽數量，動態地調整一幀內時隙的數量，以期達到最大的系統效率。本文在分析DFSA和EDFSA算法的基礎上，提出基于倍乘因子的改進算法（ADFSA）。算法實現簡單，仿真結果表明ADFSA有更好的性能。
1 DFSA算法和EDFSA算法
1.1 準備知識
DFSA和EDFSA算法是在FSA算法基礎上的改進。在FSA算法中，閱讀器向其作用范圍內的標簽發出詢問信號，標簽收到信息后，在一個幀周期內隨機選擇一個時隙向閱讀器返回信息；閱讀器將對成功識別的標簽作進一步的讀寫操作，這個過程稱為一個閱讀周期。經過一個閱讀周期后，標簽占有時隙的情況有以下三種：
a)空閑時隙，沒有標簽選擇在這個時隙里發送信息，用S0表示一幀中此時隙的數量；
b)成功識別時隙，有且只有一個標簽在該時隙中發送信息，用S1表示一幀中此時隙的數量；
c)碰撞時隙，有兩個或以上的標簽在此時隙中發送信息，用Sk表示一幀中此時隙的數量。
假設一幀內的時隙總數為S，閱讀器作用范圍內的標簽數量為T，那么同時有r個標簽落在同一個時隙的概率，符合參數T和的1/S二項式分布[8]，即
BT，1/S(r)=Tr(1/S)r(1-1/S)T-r（1）
那么，一幀中一個時隙內同時有r個標簽的時隙數量為[8]
Sr=S×BT，1/S(r)=STr(1/S)r(1-1/S)T-r（2）
在此，定義系統效率為成功識別標簽所用的時隙數量與系統使用的時隙總數的比值，即S1/S；系統的碰撞概率為碰撞時隙數量與時隙總數的比值，即Sk/S。
文獻[15]指出，當閱讀器作用范圍的標簽數量約等于使用的時隙數量時，能取得最大的系統效率。為便于計算機的實現，取時隙數為2的指數冪（如8、16、32、64…）。標簽與時隙的對應關系如表1所示。
1.2 DFSA和EDFSA算法
文獻[8]提出，RFID系統中標簽的碰撞至少發生在兩個標簽之間，因此可以采用一種非常簡單的方法估算閱讀器作用范圍內待識別的標簽數量T，如式（3）所示。估算得到待識別的標簽數量后，就可以根據表1 選擇適當的時隙數量，稱此算法為DFSAI算法。
T=2×Sr（3）
表1 標簽數量與時隙數量的對應關系
時隙數量標簽數量時隙數量標簽數量
41~512889~177
86~11256178~354
1612~22512355~709
3223~441 024710~1 419
6445~882 0481 420~2 839
文獻[9]提出，若RFID系統達到最大的系統效率，一個時隙中標簽的碰撞概率為0.418 0，所以一個時隙中發生碰撞的標簽數量為2.392 2，因此待識別的標簽數量T可通過式（4）來估算，然后根據表1選擇對應的時隙數量，稱此算法為DFSAII算法。
T=2.392 2×Sr（4）
文獻[7]提出，閱讀器作用范圍內的標簽數量可以通過式（5）來估算。
εvd(N，c0，c1，ck)=minnaN，n0aN，n1aN，n≥2-c0c1ck
（5）
其中：N代表時隙數量；n代表標簽數量；aN，n0、aN，n1、aN，n≥2分別代表由式（2）計算出的S0、S1、Sk的理論值；c0、c1、ck分別表示經過一個閱讀周期后S0、S1、Sk的實際值。公式首先計算aN，n0和c0，aN，n1和c1，aN，n≥2和ck的差，并取其絕對值最小者對應的值，結合式（2）計算對應的n。
文獻 [12，14]提出利用式（5）估算標簽的數量，再根據表1確定時隙數量。當標簽數量大于時隙數量，導致系統效率下降時，文獻[12]中通過判斷系統碰撞概率是否大于等于0.8，決定采用限制響應標簽數量的方法來提高系統效率；文獻[14]則采用取模分組的方法來限制響應標簽的數量，從而提高系統效率，分別稱為EDFSAI算法和EDFSAII算法。
DFSAI和DFSAII雖然估算方法簡單，但當標簽數量遠大于時隙數量時，一個時隙內碰撞的標簽不再符合式（3）或（4），出現標簽數量估算偏差大的問題，根據這個錯誤估算得到的標簽數量選擇的時隙也將不準確，導致系統效率的降低。EDFSAI算法通過向標簽傳送“比較比特值”“比較比特值長度”和“比較比特值起始位”信息的方法，實現對應答標簽數量的限制，從而解決DFSAI和DFSAII中標簽數量過大的問題，其實質是將標簽分成兩組，分別應答。例如，當閱讀器傳送的“比較比特值”為“10 000 000”時，標簽將被按127∶129的比例分成兩組，然而文獻[12]并沒有進一步分析當標簽數量太大，第一次分組后無法解決標簽數量過大問題時的處理方法。同時，EDFSAI和EDFSAII算法采用式（5）來估算標簽，雖然能取得較準確的估算值，卻涉及到求解非線性方程的問題，增加了系統的實現難度。
2 改進算法的描述
2.1 算法約定
改進的算法是以DFSAII的剩余標簽估算方法和EDFSA算法的分組思想為基礎，結合倍乘因子的一種改進算法，在此稱為ADFSA算法。為更好地描述算法，有以下幾點約定：
a)閱讀器向其作用范圍內的標簽發送請求指令，所有標簽隨機選擇一個時隙響應，在這個閱讀周期中，每個標簽必須且只能響應一次。
b)閱讀器范圍內的標簽有活動和靜默兩種狀態。處于活動狀態的標簽可以響應閱讀器的任何指令；處于靜默狀態的標簽不響應閱讀器的任何指令，直到其離開閱讀器的作用范圍，重新復位?；顒拥臉撕炘诒婚喿x器識別后將進入靜默狀態。
c)標簽數量在一個閱讀周期內保持不變。
2.2 算法原理
FSA算法屬于概率性防碰撞算法，符合概率統計規律。根據分析，RFID系統在經過一個閱讀周期后，可以統計系統效率、實際剩余的標簽數量和估算剩余的標簽數量三個量。在此，選用式（4）這種簡單的估算方法，分別使用4、8、16、32、64、128、256和512為初始時隙，對1～1 000個標簽進行數據統計。統計的部分數據如表2所示。
表2 部分統計數據
標簽數量
時隙數量（32）時隙數量（64）時隙數量（128）時隙數量（256）
注：“實際”指實際剩余的標簽數量；“估算”指估算所得剩余的標簽數量。
分析統計數據，根據閱讀器作用范圍內剩余的實際標簽數量，對照表1 可以得到匹配的時隙數量，在系統效率滿足一定范圍時，這與目前使用的時隙數量存在一定的比例關系，稱此比例為倍乘因子，如表3所示。
表3 系統效率與倍乘因子的關系
系統效率(≤)倍乘因子系統效率(≤)倍乘因子
實際應用中，若約定系統提供的最大時隙數為512，則最小的系統效率（除“0”外）為1/512≈1.953E-03，所以可以不必考慮系統效率小于5.20E-41的情況。
統計數據還表明，當標簽數量小于或相當于系統提供的時隙數量時，實際剩余的標簽數量與估算剩余的標簽數量基本相等，此時按式（4）的估算方法適用。因此，在這種情況下可以繼續采用式（4）的簡單估算方法；當標簽數量大于時隙數量時，可以根據表3采用倍乘因子，迅速合理地增加時隙數量，使其與標簽數量匹配，快速提高系統效率。
根據表3和式（2）可知，當系統效率小于等于31.12%時，針對不同的時隙數量，可得到滿足要求的標簽數量T（T＞0）的范圍，如表4所示。
下面將證明在系統效率小于等于31.12%的情況下，T＞S和Sk＞S0的等價性。
由式（2）可以得到，一幀內碰撞時隙總數Sk與空閑時隙總數S0之差為
Sk-S0=S-2S(1-1/S)T-T(1-1/S)T-1（6）
1)T＞SSk＞S0
因為T＞S，由表4可知S/T符合S/T＜0.59，把S=0.59T代入式（6），兩邊同除S(S＞0)，并對T求導可得
明顯當T≥2時式（7）大于零，因此函數(Sk-S0)/S在T≥2時單調遞增；而且，當S=0.59T時，(Sk-S0)｜T=1，2＞0，所以(Sk-S0)/S＞0，即Sk＞S0。
2)Sk＞S0T＞S
根據表4知道，當S1/S≤0.311 2時，S/T＜0.59或S/T＞1.91，由1)的分析可知當S/T＜0.59時，Sk＞S0成立；同理把S=1.91T代入式（6），整理可得
-1/(1.91T2)(1-1/(1.91T))T (2+1/
(1.91-1/T))ln (1-1/(1.91T))（8）
明顯當T≥1時式（8）小于零，函數(Sk-S0)/S在T≥1時單調遞減；而且，當S=1.91T時，(Sk-S0)｜T=1＜0，(Sk-S0)/S＜0，即Sk＜S0，這與題設矛盾，因此S/T＜0.59，即T＞S。
由上述分析可知，當S1/S≤0.311 2時，T＞SSk＞S0，進一步得出改進算法的具體操作步驟。
2.3 算法步驟
標簽進入閱讀器的作用范圍后，閱讀器設定一個初始時隙，開啟一個閱讀周期。當系統效率小于等于31.12%，且標簽數量大于時隙數量時，由以上的分析可知Sk＞S0，實際閱讀過程中則體現為ck＞c0。此時根據表3采用倍乘因子，快速增大時隙數量，并設定系統中使用的最大時隙數為512，當根據表3得到的時隙數大于512時，采用取模的方法對標簽分組，然后每組分別完成余下的識別過程；否則，采用式（4）估算剩余的標簽，并根據表1選擇適當的時隙數，開始新一輪閱讀過程。具體步驟如下：
a）閱讀器設定初始時隙數后，向其作用范圍內的標簽發送請求指令，開始一個閱讀周期，活動的標簽隨機選擇一個時隙響應。
b）閱讀器根據標簽響應的情況，對識別的標簽進行讀寫操作后發送靜默指令，使標簽進入靜默狀態。
c）一個閱讀周期后，閱讀器統計系統效率和c0、c1、ck的值；如果ck≤c0或系統效率大于31.12%，轉d）；否則轉e）。
d）采用式（4）估算剩余標簽數量，如果為零，轉g）；否則，根據表1選擇匹配的時隙數，轉a），開始新一輪閱讀過程。
e）不進行剩余標簽數量的估算，而是根據表3選擇對應的倍乘因子，直接計算出新的時隙數，如果時隙數小于等于512，轉a）；否則，轉f）。
f）如果時隙數為1 024，此時證明閱讀器作用范圍內的剩余標簽數量比較大，512的時隙數量無法滿足標簽識別的要求。根據表1，通過取模的方法把標簽分為兩組，并設定時隙數量512，讓兩組標簽分別應答，轉a）；同理，當時隙數大于或等于2 048，可以根據表1 ，將標簽分為四組，時隙數設為512，轉a）。
g）估算剩余的標簽數量為零，再經一個閱讀周期，確保完成所有標簽都已識別后，結束標簽的識別過程。
3 算法仿真
在Windows XP系統下，用C語言編寫仿真程序，并調用MATLAB引擎，實現C程序調用MATLAB函數fsolve()，解決EDFSAI和EDFSAII算法中的非線性方程求解問題；在MATLAB環境下，使用mex命令編譯仿真源程序，生成.exe可執行文件。運行仿真程序，輸入初始時隙數，完成仿真統計過程。文中選擇64的初始時隙，對1~4 000個標簽進行仿真，分別統計DFSAI、DFSAII、EDFSAI、EDFSAII和ADFSA算法的系統效率、使用的時隙總數量和總共的閱讀周期數量，統計結果如圖1~3所示。
4 結束語
仿真結果表明，DFSAI和DFSAII在系統效率、使用的時隙總數和閱讀周期總數都表現出非常相似的特性，因為這兩種算法沒有本質的差別；EDFSAI算法雖然使用的閱讀周期總數最少，但其使用的時隙總數大于EDFSAII和ADFSA算法，系統效率也隨著標簽數量的增加而急劇下降。由于EDFSAII算法采用式（5）的估算方法，能較準確地估算剩余的標簽數量，從而選擇合適的時隙數，其系統效率略優于ADFSA；然而這種方法實現復雜，EDFSAII使用的時隙總數與ADFSA相當，但其閱讀周期總數隨著標簽數量的增加，卻大于ADFSA算法，閱讀周期數量的增加意味著閱讀器與標簽間的交互命令也隨之增加，從而增加了標簽的識別時間。
上述分析表明，基于倍乘因子的ADFSA算法實現簡單，且隨標簽的增加，其系統效率能穩定地保持在35%；同時時隙總數和閱讀周期數量的降低，意味著識別標簽時間的減少，相對于DFSA和EDFSA能取得更優的性能。
參考文獻：
［1］程良倫，劉學鋼. 一種UHF及微波段RFID標簽芯片的研究與應用[J].微計算機信息，2006，22（26）：182184， 74.
[2]謝振華，賴聲禮，陳鵬.RFID技術和防碰撞算法[J].計算機工程與應用，2007，43（6）：223239.
[3]程良倫.網絡工程概論[M].北京：機械工業出版社，2007.
[4]FINKENIELLER K. RFID handbook fundamentals and applications in contactless smart card and identification[M]. 2nd ed.[S.l.]:Wiley， 2002:132150.
[5]胡建赟，李強，閔昊.時隙ALOHA法在RFID系統防碰撞問題中的應用[J].應用科學學報，2005，23（5）：489492.
[6]劉佳，張有光.基于時隙的RFID防碰撞算法分析[J].電子技術應用，2007，33（5）：9496，100.
[7]VOGT H. Efficient object identification with passive RFID tags[C]//Proc ofInternational Conference on Pervasive Computing.[S.l.]: SpringerVerlag， 2002.
[8]VOGT H. Multiple object identification with passive RFID tags[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics. 2002:651656.
[9]CHA J R， KIM J H. Novel anticollision algorithms for fast object identification in RFID system[C]//Proc of the 11th International Conference on Parallel and Distributed Systems (ICPADS). 2005:6367.
[10]高樂.RFID技術中的防碰撞算法研究[D].成都：電子科技大學，2006.
[11]吳晶，熊璋，王曄.利用動態時間槽分配的多目標防沖突射頻識別[J].北京航空航天大學學報，2005，31（6）：618622.
[12]HWANG T W， LEE B G， KIM Y S，et al. Improved anticollision scheme for high speed identification in RFID system[C]//Proc of the 1st International Conference on Innovative Computing， Information and Control (ICICIC’06).[S.l.]: IEEE Press， 2007.
[13]PENG Qingsong， ZHANG Ming， WU Weimin. Variant enhanced dynamic frame slotted ALOHA algorithm for fast object identification in RFID system[C]//Proc ofIEEE International Workshop on Anticounterfeiting， Security， Identification. 2007:8891.
[14]LEE S R， JOO S D， LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]//Proc of MobiQuitous. 2005:166174.
[15]JOE I， LEE J. A novel anticollision algorithm with optimal frame size for RFID system[C]//Proc of the 5th IEEE International Conference on Software Engineering Research， Management and Applications. 2007:424428.
