基于扩频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