王云峰，張 斌

?

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

王云峰，張 斌

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

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

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

1 概述

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

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

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

2 ABSS防碰撞算法原理

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

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

圖1 ABSS算法數(shù)據(jù)分組碰撞圖

圖2 標簽數(shù)據(jù)幀格式

因此，數(shù)據(jù)幀重傳成功的概率為：

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

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

若定義系統(tǒng)的吞吐量為一個時隙內(nèi)標簽數(shù)據(jù)幀成功發(fā)送并被閱讀器解擴的標簽數(shù)據(jù)均值，則其可以表示為:

3 算法仿真分析

3.1 算法吞吐量分析

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

圖3 吞吐量與負載和擴頻碼數(shù)量的關(guān)系

吞吐效率為：

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

3.2 吞吐量影響因子分析

由吞吐量表達式可知，系統(tǒng)負載一定時，發(fā)送延時和擴頻碼數(shù)量是影響系統(tǒng)吞吐量的主要因子。

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

本文考慮閱讀器范圍內(nèi)流動標簽數(shù)量較大時對系統(tǒng)吞吐量的影響，相應(yīng)增加擴頻碼數(shù)量，取=100,200,500對算法進行仿真，吞吐量與擴頻碼數(shù)量關(guān)系如圖6所示?？梢钥闯觯S著的增加，系統(tǒng)最大吞吐量逐漸增大，同時獲得其對應(yīng)負載也在增大。所以，當碰撞數(shù)據(jù)較多時，增加擴頻碼數(shù)量可以提升系統(tǒng)的吞吐量，在實際應(yīng)用中只需增加Gold序列產(chǎn)生器的級數(shù)即可。

圖5 吞吐量與發(fā)送延時的關(guān)系

圖6 吞吐量與擴頻碼數(shù)量的關(guān)系

4 多標簽識別系統(tǒng)誤碼率分析

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

4.1 多標簽識別系統(tǒng)仿真

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

圖7 多標簽系統(tǒng)Matlab仿真結(jié)構(gòu)

4.2 誤碼率與影響因子分析

通信誤碼率與信噪比、上行速率、幀長等因素有關(guān)[12]。仿真中，通過改變標簽功率控制信噪比；通過控制采樣速率調(diào)節(jié)上行速率；通過改變仿真時長調(diào)節(jié)碼元數(shù)量，以實現(xiàn)幀長的改變。具體操作如下，設(shè)高斯白噪聲功率=100 W，分別設(shè)置10個標簽的功率(1~10)，因此，信噪比= 20lg(/)的范圍是–40 dB~–20 dB，碼元數(shù)量分別設(shè)置為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個標簽的誤碼率。實驗數(shù)據(jù)如表1~表3所示，其關(guān)系對比如圖8所示?？梢钥闯?，多標簽識別系統(tǒng)中誤碼率隨著信噪比的增大而減小，隨著幀長的增大而增大，隨著上行速率的增大而增大。在相同信噪比相同幀長條件下，上行速率越大，誤碼率越高；在相同信噪比相同上行速率條件下，幀長越大，誤碼率越高；在相同幀長相同上行速率條件下，信噪比越大，誤碼率越低。同時，當仿真系統(tǒng)信噪比高于–20 dB時，誤碼率趨近于0。

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

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

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

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

圖8 誤碼率與影響因子的關(guān)系

5 結(jié)束語

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

[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] 魏 靜, 馮秀芳. 基于自適應(yīng)分組的幀時隙 ALOHA 算法在RFID 中的研究[J]. 計算機技術(shù)與發(fā)展, 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] 丁治國, 朱學永, 郭 立, 等. 自適應(yīng)多叉樹防碰撞算法研究[J]. 自動化學報, 2010, 36(2): 237-241.

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

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

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

[12] 樊昌信, 曹麗娜. 通信原理[M]. 北京: 國防工業(yè)出版社, 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 安全認證協(xié)議；張斌，教授。

2013-07-17

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