基于擴頻ALOHA的RFID防碰撞算法

王云峰，張 斌

?

基于擴頻ALOHA的RFID防碰撞算法

王云峰，張 斌

(解放軍信息工程大學密碼工程學院，鄭州 450004)

在射頻識別系統中，讀寫器作用范圍內的多標簽識別存在數據碰撞的問題。為此，在分析ALOHA算法的基礎上，應用碼分多址技術，提出一種基于Gold碼擴頻的ALOHA防碰撞算法，并進行算法的推導和仿真。該算法的吞吐量會隨著標簽數據幀發送延時的增大而減小，隨著擴頻碼數量的增加而增大。當擴頻碼數量和負載相等時，系統吞吐量最小；當擴頻碼數量大于負載時，吞吐效率會隨擴頻碼數量的增加而增大，系統吞吐效率高于時隙ALOHA。應用Simulink構建基于碼分多址的多標簽與閱讀器通信系統，分別研究信噪比、上行速率和幀長對通信誤碼率的影響，實驗結果表明，該算法可提高閱讀器與標簽之間的通信質量，在現實情況下誤碼率趨近于0。

射頻識別；碼分多址；ALOHA算法；防碰撞；擴頻

1 概述

射頻識別技術是通過無線射頻方式對目標進行自動識別的非接觸式雙向數據通信技術。其特有的性能優勢，使其被廣泛應用到零售行業、物流供應鏈管理和交通等領域。射頻識別(Radio Frequency Identification, RFID)系統由標簽、閱讀器、后臺數據庫三部分數據組成。其中，解決讀寫器作用范圍內多標簽識別問題已成為RFID領域研究的熱點[1]。

多標簽識別勢必帶來數據碰撞問題，設計高效的防碰撞算法是多標簽識別問題的研究重點。目前常用的防碰撞算法一般可分為2類：(1)基于時隙隨機分配的ALOHA算法，包括幀時隙ALOHA算法[2]、分群時隙ALOHA算法[3]、分組幀時隙ALOHA算法[4]和高效幀時隙算法[5]等。其特點是算法簡單，便于實現，適用于低成本RFID系統，但其吞吐量最大只能達到0.368，且存在標簽無法被識別的情況。(2)基于二進制樹搜索的算法，主要包括自適應二叉樹搜索算法[6]、四叉樹搜索算法[7]、自適應多叉樹算法[8]和改進型多叉樹算法[9]等。該類算法能夠識別讀寫器有效通信范圍內所有標簽，但計算復雜，延時較長。因此，研究人員致力于設計能夠高效率識別閱讀器作用范圍內所有標簽的防碰撞算法。文獻[10]提出了一種基于碼分多址思想的時隙ALOHA算法，當此算法選用的擴頻碼數量為時，其最大吞吐量可達幀時隙ALOHA算法的倍，但文中沒有考慮擴頻之后有效傳輸效率的降低，吞吐量不會一味地增長。

本文結合文獻[10]的設計思路，引入數據幀重傳機制，提出一種基于擴頻ALOHA的RFID防碰撞算法(ABSS)。該算法基于碼分多址技術，利用偽隨機Gold序列的正交性來區分同信道同時隙條件下的不同標簽。

2 ABSS防碰撞算法原理

傳統的幀時隙ALOHA算法規定，所有標簽只有在每個時隙的開始時刻才能發送數據，這樣標簽的數據分組或成功發送或完全碰撞，避免了部分碰撞，使數據分組在同一時隙內碰撞周期減半。其吞吐量=e–，當=1時得到最大吞吐量0.368[2]。

本文防碰撞算法實現多標簽識別的原理如圖1所示。某時刻有個標簽同時向閱讀器發送數據，此時數據發生碰撞，系統隨機分配個擴頻碼(1~M)供碰撞數據使用，閱讀器端采用同樣的擴頻碼對信息解擴，以恢復標簽數據。當有2個或以上標簽選擇的擴頻碼相同時，標簽數據發生碰撞，此時啟動重傳機制，通過排隊重傳解決這個碰撞事件，并在一個時隙內經歷重傳延時對數據幀進行重傳。標簽封裝的數據幀格式如圖2所示。

圖1 ABSS算法數據分組碰撞圖

圖2 標簽數據幀格式

因此，數據幀重傳成功的概率為：

單個標簽成功被閱讀器識別的概率為：

個標簽被成功識別的概率為：

若定義系統的吞吐量為一個時隙內標簽數據幀成功發送并被閱讀器解擴的標簽數據均值，則其可以表示為:

3 算法仿真分析

3.1 算法吞吐量分析

在中高頻系統中，標簽向閱讀器發送數據的速率通常為=40 Kb/s[11]，若取標簽數據幀長=320 bit，則數據幀的發送延時=0.008 s。圖3為發送延時=0.008 s時，系統吞吐量與負載和擴頻碼數量的關系。

圖3 吞吐量與負載和擴頻碼數量的關系

吞吐效率為：

吞吐效率與負載和擴頻碼數量的關系如圖4所示。可以看出，當擴頻碼數量N一定時，系統吞吐量S會隨著負載G的增加而先增大達到峰值再逐漸減小。同時負載G一定時，吞吐量S會隨著擴頻碼數量N的增加而逐漸增大；吞吐性能S/G在G=1時最大為1，其后當N一定時，會隨著G的增加而逐漸減小。且當N=G時，；當N>G時，吞吐效率還會隨著N的增加而增大，因此，只要保證擴頻碼數量N足夠大，系統吞吐效率將遠遠高于時隙ALOHA的吞吐效率。

3.2 吞吐量影響因子分析

由吞吐量表達式可知，系統負載一定時，發送延時和擴頻碼數量是影響系統吞吐量的主要因子。

由于數據在標簽與閱讀器之間采用無線傳輸方式，發送延時與數據幀長和無線傳輸速率有關，通常為毫秒級[9]，因此分別取=0.005,0.01,0.02對算法進行仿真，吞吐量與發送延時關系如圖5所示，可以看出，隨著的增加，系統最大吞吐量逐漸減小，同時獲得最大吞吐量的對應負載也在減小。因此，減小發送延時對增大系統吞吐量起著至關重要的作用，在實際應用中則體現在標簽與閱讀器硬件的優化。

本文考慮閱讀器范圍內流動標簽數量較大時對系統吞吐量的影響，相應增加擴頻碼數量，取=100,200,500對算法進行仿真，吞吐量與擴頻碼數量關系如圖6所示。可以看出，隨著的增加，系統最大吞吐量逐漸增大，同時獲得其對應負載也在增大。所以，當碰撞數據較多時，增加擴頻碼數量可以提升系統的吞吐量，在實際應用中只需增加Gold序列產生器的級數即可。

圖5 吞吐量與發送延時的關系

圖6 吞吐量與擴頻碼數量的關系

4 多標簽識別系統誤碼率分析

ABSS防碰撞算法基于擴頻實現系統吞吐量的成倍增大，但究竟多標簽與閱讀器通信質量如何，還需通過系統仿真實驗驗證通信的誤碼率。

4.1 多標簽識別系統仿真

應用Simulink模擬基于碼分多址技術的多標簽與閱讀器的通信系統，仿真結構框圖如圖7所示。隨機生成±1序列的S函數構成通信系統內的10個標簽，通過改變增益參數控制各個標簽的功率，標簽信息與Gold序列發生器作為乘法器的輸入端實現擴頻。使用高斯白噪聲模塊作為噪聲源，并經增益模塊放大其功率，應用加模塊實現擴頻信息的合路。閱讀器端使用相應的Gold碼解擴，并對解擴后的離散值進行積分平均運算，將結果引入符號判決器還原±1序列，并與對應的標簽信息對比進行誤碼率的計算。

圖7 多標簽系統Matlab仿真結構

4.2 誤碼率與影響因子分析

通信誤碼率與信噪比、上行速率、幀長等因素有關[12]。仿真中，通過改變標簽功率控制信噪比；通過控制采樣速率調節上行速率；通過改變仿真時長調節碼元數量，以實現幀長的改變。具體操作如下，設高斯白噪聲功率=100 W，分別設置10個標簽的功率(1~10)，因此，信噪比= 20lg(/)的范圍是–40 dB~–20 dB，碼元數量分別設置為120 bit、240 bit、480 bit。分別考慮采樣速率為1/10 000、1/20 0 00、1/40 000，即在上行速率為10 Kb/s、20 Kb/s、 40 Kb/s的情況下，10個標簽的誤碼率。實驗數據如表1~表3所示，其關系對比如圖8所示。可以看出，多標簽識別系統中誤碼率隨著信噪比的增大而減小，隨著幀長的增大而增大，隨著上行速率的增大而增大。在相同信噪比相同幀長條件下，上行速率越大，誤碼率越高；在相同信噪比相同上行速率條件下，幀長越大，誤碼率越高；在相同幀長相同上行速率條件下，信噪比越大，誤碼率越低。同時，當仿真系統信噪比高于–20 dB時，誤碼率趨近于0。

實驗證明采用基于碼分多址防碰撞算法的系統，閱讀器與標簽之間的通信質量可靠，在現實情況下誤碼率趨近于0。

表1 Pn=100 W，上行速率為10 Kb/s時的誤碼率

表2 Pn=100 W，上行速率為20 Kb/s時的誤碼率

表3 Pn=100 W，上行速率為40 Kb/s時的誤碼率

圖8 誤碼率與影響因子的關系

5 結束語

針對RFID領域中多標簽識別過程存在的數據碰撞問題，本文結合碼分多址技術，引入碰撞數據幀隨機退避重傳機制，提出了一種高吞吐量防碰撞算法。依據碼分多址和排隊論原理推導出其吞吐量表達式并進行仿真，仿真結果表明其吞吐量高于傳統防碰撞算法。此外，多標簽環境下通信仿真表明通信質量可靠，當仿真系統信噪比高于–20 dB時，誤碼率趨近于0。下一步工作將針對如何簡化閱讀器的解擴過程及降低系統成本進行深入研究，同時合理減小數據幀長和實際條件下閱讀器對標簽數據的發送延時，進一步提高系統的效率。

[1] 石封茶, 崔 琛, 余 劍. 基于標簽運動的一種新型RFID防碰撞算法[J]. 計算機科學, 2013, 40(6): 76-79.

[2] Finkenzeller K. RFID Handbook: Fundamentals and Applica- tions in Contactless Smart Cards and Identification[M]. [S. l.]: John Wiley & Sons, 2003.

[3] Hwang Tae-Wook, Lee Byong-Gyo, Kim Young-Soo. Improved Anticollision Scheme for High Speed Identification in RFID System[C]//Proc. of the 1st International Conference on Innovative Computing, Information and Control. Beijing, China: [s. n.], 2006: 449-452.

[4] 魏 靜, 馮秀芳. 基于自適應分組的幀時隙 ALOHA 算法在RFID 中的研究[J]. 計算機技術與發展, 2012, 22(11): 57-60.

[5] Wu Haifeng, Zeng Yu. Efficient Framed Slotted Aloha Protocol for RFID Tag Anticollision[J]. IEEE Transactions on Automation Science and Engineering, 2011, 8(3): 581-588.

[6] Lai Y C, Lin C C. A Pair-resolution Blocking Algorithm on Adaptive Binary Splitting for RFID Tag Identification[J]. IEEE Communications Letters, 2008, 12(6): 432-434.

[7] Shih B Y, Lo T W, Chen C Y. The Research of Quadtree Search Algorithms for Anti-collision in Radio Frequency Identification Systems[J]. Scientific Research and Essays, 2011, 6(25): 5342-5350.

[8] 丁治國, 朱學永, 郭 立, 等. 自適應多叉樹防碰撞算法研究[J]. 自動化學報, 2010, 36(2): 237-241.

[9] 張學軍, 蔡文琦, 王鎖萍. 改進型自適應多叉樹防碰撞算法研究[J]. 電子學報, 2012, 40(1): 193-198.

[10] 梁 彪, 胡愛群, 秦中元. 一種新的RFID防碰撞算法設計[J]. 電子與信息學報, 2007, 29(9): 2158-2160.

[11] 周曉光, 王曉華. 射頻識別(RFID)技術原理與應用實例[M].北京: 人民郵電出版社, 2006.

[12] 樊昌信, 曹麗娜. 通信原理[M]. 北京: 國防工業出版社, 2006.

編輯 金胡考

Anti-collision Algorithm for RFID Based on Spread Spectrum ALOHA

WANG Yun-feng, ZHANG Bin

(Institute of Cipher Engineering, PLA Information Engineering University, Zhengzhou 450004, China)

In the Radio Frequency Identification(RFID) system, in order to solve data collision problems between multiply tags existing within the scope of the reader during identification process, based on the analysis of ALOHA algorithm and the application of Code Division Multiple Access(CDMA) technology, an anti-collision ALOHA algorithm Based on Spread Spectrum(ABSS) is proposed. The throughput of this algorithm decreases along with the increase of frame’s transmission delay and increases as the number of spread codes increase. When the number of spreading codes is equal to the load, the minimum throughput of this system is gotten. When the number of spreading codes is larger than the load, the throughput will increase with the number of spreading codes, so the throughput of system will be higher than that of slot ALOHA. CDMA-based communication system model of multi-tag and reader is established on Simulink to respectively study influence of the signal-to-noise ratio, the uplink rate and frame size on the communication error rate. Experimental data show that communication quality between the reader and tags is reliable, and in reality, the error rate is close to zero.

Radio Frequency Identification(RFID); Code Division Multiple Access(CDMA); ALOHA algorithm; anti-collision; spread spectrum

1000-3428(2014)03-0001-05

A

TP309.2

10.3969/j.issn.1000-3428.2014.03.001

國家“973”計劃基金資助項目(2011CB311901)。

王云峰(1990－)，男，碩士研究生，主研方向：RFID 安全認證協議；張斌，教授。

2013-07-17

2013-09-16 E-mail：aaa900509@163.com