分组部分时隙帧预测的RFID防碰撞算法

吴 垚,霍亮生,刘玉德,顾祖宝

(北京工商大学材料与机械工程学院,北京100048)

分组部分时隙帧预测的RFID防碰撞算法

吴 垚,霍亮生,刘玉德,顾祖宝

(北京工商大学材料与机械工程学院,北京100048)

针对最大帧长度受限情况下射频识别中的标签碰撞问题,提出分组部分时隙帧预测ALOHA算法。通过分组操作,限定每次待识别标签数在最大帧长的有效识别范围内。采用部分时隙帧预测,若部分时隙的碰撞或空闲比例超过门限值,则立即调整帧长,从而减少使用的时隙数。实验结果表明,该算法能有效降低使用的时隙数,提高系统识别效率,在标签大量动态变化的情况下,平均识别率可达35.58%,具有良好的适用性。

射频识别;防碰撞;动态帧时隙ALOHA;部分时隙;随机数

1 概述

近几年来,随着物联网(Internet of Things,IOT)的兴起,作为其重要支撑的射频识别(Radio Frequency Identification,RFID)技术得到了重视,在物流、零售、工业自动化等领域发展迅速。RFID系统实际工作时大量标签可能处于一个读写器的作用范围内,这将导致多个标签同时响应读写器而造成标签识别失败,称为标签碰撞(Collision),因此需采用防碰撞算法最大限度地正确识别尽可能多的标签。

标签防碰撞算法可分为ALOHA算法和基于树的防碰撞算法[1]。ALOHA算法实现结构简单、成本较低,目前被广泛使用,如全球超高频RFID主流标准之一的ISO/IEC18000-6的TypeA和TypeC均基于ALOHA算法[2]。实际使用的帧时隙ALOHA算法将若干离散时隙组合成一帧,标签在每一帧中随机选择一个时隙发送数据以减少标签冲突的概率[3]。当帧长L和标签数量n近似相等时,系统识别效率可达到最大值36.79%[4];当L和n相差很大时,系统识别效率较低。动态帧时隙 ALOHA(Dynamic Framed Slotted ALOHA,DFSA)算法使帧长动态近似等于待识别标签数,常见算法有Q算法(n=2Q)、Lower Bound[5](n=2C)、Schoute[6](n=2.39C)、Vogt[5]、Bayesian[7]等,其中,C为碰撞时隙数。DFSA算法在标签相对较少的情况下识别效率较高[8],但在标签数量很多、发送时隙受限时,DFSA算法几乎显示不出优越性[9],且上述算法都是对实际情况的统计近似,具有一定的预测误差。为解决最大帧长度受限情况下射频识别中的标签碰撞问题,本文提出一种分组部分时隙帧预测ALOHA算法。

2 分组部分时隙帧预测算法

2.1 分组

在实际RFID系统中受到体积等限制,标签内的随机数发生器一般为8位[10],这使得最大帧长为28=256。若限制最大帧长,DFSA算法整体性能较差,并最终退化为固定帧长ALOHA算法,如图1所示。

图1 DFSA算法效率

通过分组操作,将每组待识别标签数量限定在最大帧长度能较好识别的有效范围内。分组部分时隙帧预测(Grouping Part Slots Prediction ALOHA, GPSPA)算法将标签分成3类:(1)待识别标签组,马上进行识别;(2)休眠标签组,进入休眠状态,等待下一周期进行识别;(3)成功标签组,已经成功进行数据交换的标签为成功标签,不再响应读写器命令。

以ISO/IEC 18000-6C中推荐的Q算法为基础设计GPSPA算法。Q算法的基本思想为:Q为一非负整数,帧长度L=2Q。若碰撞时隙数C＞空闲时隙数E,则Q值加1;若碰撞时隙数C＜空闲时隙数E,则Q值减1。其实质是帧长度按照2倍长度变化。

假定有n个待识别的电子标签,帧长度为L个时隙,忽略环境噪声对信号传输及接收的影响。由于电子标签随机选择时隙,r个电子标签的响应服从二项分布[11],当且仅当一个时隙中有一个电子标签响应(即r=1)时,电子标签才能被读写器成功识别,因此一帧中成功识别的标签数目为:

定义系统识别效率=成功识别标签数量/使用的时隙数量[12],由式(1)可得系统识别效率为:

在L和2L长度下,系统效率应该相同[7]。令ρL=ρ2L,可解得临界标签数为:

将帧长L=256带入式(3),可得临界标签数为354。这说明考虑到统计效应,帧长为256时隙的一帧最多可识别354个标签,故可将354作为分组数目。

分组操作的具体实现为:首先将估计标签数除以354,向无穷方向取整后得到组数,然后读写器广播分组命令,每个待识别标签产生从1～组数的随机数,以此作为组号。从1号组开始,各组依次作为待识别组进行识别,成功识别的标签记组号为0,不再响应读写器分组指令。

2.2 部分时隙帧预测

在传统的DFSA算法中,不管采用何种标签估计算法,都必须完全遍历一帧中所有时隙。不妨考虑2种极端情况:时隙数远小于标签数量时会出现大量时隙碰撞;若时隙数远大于标签数,则有众多时隙空闲。由数理统计学的知识可知,部分时隙的统计特性完全可以代表整体帧的统计特性。设采样率为SA,则通过检验前SA×L部分时隙的碰撞和空闲状态,可以推断整帧的碰撞与空闲情况。若在前SA×L个时隙内,碰撞时隙所占百分比大于判断门限,则可推知帧长过小,应将帧长度立即扩大;若空闲时隙百分比大于判断门限,则可认为帧长过大,应将帧长立即缩小。GPSPA算法采用部分时隙帧预测,若调整帧长能节省(1-SA)×L个时隙。

算法具体实现为:每次识别时,先检验前SA×L个时隙情况,若碰撞、空闲时隙比例超过门限值,则按照2倍或1/2的关系立即调整帧长;若未达到判决门限,可认为帧长无需立即调整,继续检测剩余时隙;如此循环往复对所有组进行识别,直到所有标签均被成功识别。

2.3 算法分析

GPSPA根据标签冲突情况高效地调节数据帧长度,试图使帧长动态接近未识别标签数。将数据帧根据冲突情况进行变长,会给物理层和网络层带来一定的处理开销。具体表现在:RFID物理层频繁发收无线电波,会增加读写器和电子标签的处理功耗;网络层对数据帧进行封装时,由于帧长不定长,会增加网络层设备复杂性。但是综合分析后可认为,GPSPA算法非常适用于实际工业情况下,即标签数量在大范围内动态变化时[13]。GPSAP算法以牺牲一定功耗和处理算法复杂性的代价下,大大提高了系统效率,极大地节省了使用的时隙数目,并使系统识别效率较为稳定地工作在接近极限效率36.79%,具有良好的应用前景。

2.4 GPSPA算法流程

GPSPA算法流程如图2所示。

图2 GPSPA算法流程

3 仿真实验与分析

为了验证GPSPA算法的优势,利用Matlab进行4组仿真,每组实验均进行100次取均值。

3.1 仿真实验

将GPSPA与DFSA中性能较好的Schoute算法进行比较,其中GPSPA算法参数如表1所示。

表1 GPSPA仿真参数

仿真结果如图 3、图 4所示。由图 3可见, GPSPA较Schoute算法具有更高更稳定的系统识别效率。在标签数大量动态变化的情况下,系统识别效率的平均值可达35.58%。当标签数量为1 000时,GPSPA算法效率是Schoute的1.75倍;标签数量为 1 200时,GPSPA算法效率是 Schoute的2.5倍。图4说明GPSPA使用时隙明显少于Schoute算法,尤其是当标签数较大时,GPSPA节省的时隙数更为可观。

图3 GPSPA(SA=0.5)和Schoute的系统识别率比较

图4 GPSPA(SA=0.5)和Schoute使用时隙数比较

3.2 采样率对系统识别效率的影响

下面分析采样率对系统识别效率的影响。GPSPA参数分别如表2所示变化,得到仿真结果如图5所示。由图5可知当采样率SA较小时,算法效果更好。因为可根据小部分时隙的统计情况及时调整帧长度,若采样率为100%,GPSPA算法系统识别效率最低。

表2 采样率仿真参数

图5 采样率对GPSPA算法的影响

3.3 判决门限对系统识别效率的影响

令GPSPA参数变化如表3所示,得到仿真结果如图6所示。由图6可见判决条件越宽松,系统效率振动程度越大,但总的说来,不同判决门限下系统效率接近,可以不将判决门限作为重点考虑因素。

表3 判决门限仿真参数

图6 不同判决门限系统下识别率对GPSPA算法的影响

3.4 初始帧长度对系统识别效率的影响

令参数变化如表4所示,对系统仿真后得系统识别效率如图7所示。由图7可见,当标签数较小时,较小的初始帧长度具有较高的识别效率,但当标签数目远大于256时,初始帧长度为256具有更高的效率。对于标签数量较大的情形,可将初始帧长度定义为256。

图7 初始帧长度对GPSPA算法的影响

4 结束语

本文在研究ISO/IEC18000-6C标准中ALOHA防碰撞算法的基础上,提出一种基于分组部分时隙帧预测ALOHA算法。该算法能适应电子标签大量动态变化的环境。通过分组,将远超过最大帧长256时隙的标签分成待识别组、休眠组、成功组3类,通过分别对各组进行识别,可在最大帧长度限制下有效地进行系统识别。根据部分时隙的统计性质能代表整帧的情况,对部分时隙的碰撞、空闲情况进行统计,若发现部分时隙的碰撞或空闲百分比超过门限值,则立即调整帧长,能节省较多时隙。仿真结果表明,本文提出的算法能有效降低使用时隙数,提高系统识别效率,表现出较优越的性能,尤其对标签数量剧烈变化、实时性要求较高的物联网终端RFID系统具有良好的适用性。

[1] 赵瑞思,李 涛,张 帅,等.RFID动态标签估计防碰撞算法[J].计算机工程,2012,38(8):249-251.

[2] International Organization for Standardization.ISO/IEC 18000-6-2003 Information Technology Automatic Identification and Data Capture Techniques-Radio Frequency Identification forItem ManagementAir Interface[S].2003.

[3] Wong C P,Feng Quanyuan.Grouping Based Bit-slot ALOHA ProtocolforTag Anti-collision in RFID Systems[J].IEEE Communications Letters,2007,11 (12):946-948.

[4] Klaus Finkenzeller.射频识别技术[M].3版.吴晓峰,陈大才,译.北京:电子工业出版社,2006.

[5] Vogt H.EfficientObjectIdentification with Passive RFID Tags[C]//Proc.of International Conference on Pervasive Computing.[S.1.]:IEEE Press,2002: 98-113.

[6] Schoute F.Dynamic Frame Length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[7] Floerkemeier C.Transmission Control Scheme for fast RFID Object Identification[C]//Proc.of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops.[S.1.]:IEEE Press, 2006:222-229.

[8] Cui Yinghua,Wang Huiyang.A New Anti-collision Method for RFID Systems[C]//Proc.of the 12th IEEE International Symposium on Computational Intelligence and Informatics.Budapest,Hungary:[s.n.],2011:549-556.

[9] Hwang T W,Lee B G,Kim Y S,et al.Improved Anticollision Scheme for High Speed Identification in RFID System[C]//Proc.ofInternationalConferenceon Innovative Computing,Information and Control.Beijing, China:[s.n.],2006:123-129.

[10] 李 慧,张治国.不定长RFID标签反碰撞识别算法[J].计算机工程,2010,36(20):241-243.

[11] 郭来功,黄友锐,蔡 俊.优化的动态帧时隙ALOHA防碰撞算法[J].计算机应用研究,2012,29(11): 4141-4143.

[12] 程文青,赵梦欣,徐 晶.改进的 RFID动态帧时隙ALOHA算法[J].华中科技大学学报:自然科学版, 2007,35(6):14-16.

[13] Gao Jianliang,Wang Jianxin,He Jianbiao,et al.Query Splitting-based Anticollision forMobileRFID-based Internet-of-things [J]. International Journal of Distributed Sensor Networks,2013,(2013):674-698.

编辑 索书志

RFID Anti-collision Algorithm of Grouping Part Time Slot Frame Prediction

WU Yao,HUO Liang-sheng,LIU Yu-de,GU Zu-bao
(School of Material and Mechanical Engineering,Beijing Technology and Business University,Beijing 100048,China)

To solve the tags collision problem in Radio Frequency Identification(RFID)system where the maximum size of frame is limited,this paper proposes a new Grouping Part time Slot frame Prediction ALOHA(GPSPA) algorithm.Tags are divided into smaller groups considering the limited frame size's capability.Part slots prediction scheme is used in identification to decide whether to change the frame size immediately.If the empty or collision slots percentage exceeds the threshold value,the frame size is changed promptly.Simulation results show that the proposed algorithm can increase the system efficiency and consume fewer slots than previous work.Besides,the influence of the parameters of the algorithm is discussed by simulation tests.The system identification efficiency can maintain 35.58%, approximating to the limit value,where dynamic tags are changing greatly.The proposed algorithm provides a good solution for RFID systems where the tags are changing within a wide range and the frame size is limited.

Radio Frequency Identification(RFID);anti-collision;Dynamic Framed Slotted ALOHA(DFSA);part time slot;random number

1000-3428(2014)09-0280-04

A

TP391

10.3969/j.issn.1000-3428.2014.09.056

北京市教委重大基金资助重点项目(PXM2013_014213_000037);北京工商大学研究生科研学术创新基金资助项目。

吴 垚(1990-),男,硕士研究生,主研方向:无线射频识别,嵌入式系统;霍亮生、刘玉德,教授;顾祖宝,硕士研究生。

2013-06-14

2013-09-28E-mail:wuyao391@163.com