基于标签分组的RFID系统防碰撞算法

郭振军 孙应飞



基于标签分组的RFID系统防碰撞算法

郭振军*①②孙应飞①

①(中国科学院大学 北京 100049);②(桂林航天工业学院 桂林 541004)

防碰撞算法是射频识别(RFID)系统中提高标签识别效率的关键技术。针对确定性的RFID标签防碰撞算法存在的识别效率不高、系统数据交换量大等问题，该文提出一种标签分组机制防碰撞算法，将其与融合后的二进制树搜索算法相结合，读写器系统分批次识别标签组中的标签，能有效地减少数据通信量。实验仿真结果表明，该算法相比其他几种算法，具有识别效率高、数据交换量小等优势。

射频识别；防碰撞；二进制搜索法；融合算法

1 引言

射频识别技术是一种非接触式的自动识别技术，它通过系统发射的射频信号来对目标标签进行识别并获取标签的相关数据信息。该系统因其可以高效准确地进行大量物品的识别读取，已广泛被应用在交通、物品流通的供应链管理等领域[1, 2]。典型的射频识别系统主要由3部分组成：标签、读写器和天线。作为物品信息载体的标签贴于待识别的物品上，在进行物品信息的识别过程中，若存在两个及以上标签同时出现时，即会出现信号间的相互干扰，影响系统对标签群的识别效率。因此，在待识别标签密集度高的射频系统中，需采用一种有效的多标签识别的防碰撞算法。

标签与读写器信号交互中主要有3种形式的碰撞，分别为标签碰撞、读写器间的干扰、标签干扰。其中，读写器间干扰和标签干扰类似于移动蜂窝网频率分配问题，可通过读写器间建立的工作协调机制以解决冲突问题。标签碰撞问题，则应根据RFID识别系统自身特点，选择不同的方法来解决。

RFID系统多标签防碰撞算法的主要任务是确保读写器正确识别在有效通信覆盖范围内的多个目标标签。根据所采用的无线通信多址接入方式，算法可分为时分多路类、码分多路类、空分多路类和频分多路[7]4种。因系统受到成本和资源等方面的要求，时分多路法技术在识别系统的多标签防碰撞算法中应用最为广泛。

时分多路防碰撞算法中的ALOHA算法易于实现，成本低廉，但是由于算法的时隙是随机分配，因此可能造成某些标签长时间无法识别，亦即存在标签饥饿问题。在帧时隙ALOHA防碰撞算法(FSA)应用中，当标签识别量变得很大时，系统的算法执行时间就会很长，标签的读取效率下降。帧时隙ALOHA算法由于帧时长是固定的，所以，不能实现长度的实时调节，以自适应标签数量的变化。而动态帧时隙ALOHA算法(DFSA)需要在系统的识别过程中不断估算标签数量，以便于与时隙数相匹配。但由于硬件条件限制，帧长度并非是可以无限制的增加，限制标签群中标签数量的变化。所以，帧时隙ALOHA算法仅限于每帧中时隙数最大为256的系统中使用。当标签群中的标签数远大于256时，该算法将无法通过时隙数的增大来提高数据的吞吐率。

基于树的分组算法是确定型算法，根据分组规则的不同，基于树的分组算法又进一步分为二进制树搜索算法(Binary Tree protocol, BT) 和查询树算法(Query Tree protocol, QT)。二进制树搜索算法按照递归工作方式，标签若发生碰撞时即可将具有碰撞位的标签分成两个子集，并将此位置“0”，以此方式进行，重复上述过程，继续子集分配，直至标签读取无碰撞发生为止。子集生成算法包括基本的二进制树搜索算法和时隙二进制树算法( slotted binary search)，前者根据碰撞位具体值确定，若该位为“0”则标签在下次询问中响应，否则标签静默；后者则采用随机分组方式，此类标签内部有随机数生成器，当多标签冲突时，碰撞标签自身产生一个随机数“0”或“1”，根据产生随机数值的不同，标签被分为两组；下次询问命令发出后，数值为“0”的标签发送信号，若有冲突，继续分组，以此方式重复进行，直至标签信息读取时无碰撞发生为止，随机数为“0”的标签信息被读取之后进行数值为“1”的标签响应。查询树(QT)算法是确定性的标签防碰撞算法。应用此类算法的标签无需特殊存储器，系统只需记录标签自身UID编号即可。标签读取时，系统先发送一个标签信息查询前缀，若查询前缀与标签信息的前缀相同，标签即响应此次查询。对于单标签来说，二者信息相同后标签将自身的UID编号反馈给读写器，读写器成功接收到标签UID后即表示该标签被成功识别；对于多标签来说，若多个标签响应并发生冲突时，再下一个循环的标签查询时，读写器将会把查询信息的前缀后面增加一个“0”或“1”，以此方法重复进行，标签群的识别过程中，系统通过不断的修改查询指令前缀编码信息，使其能识别在读写区域内出现的所有标签。基本的BT算法和QT算法都存在空闲时隙，降低了系统效率[16]。另外，此类算法系统可实现的必要前提是能辨认出在系统识别时发生数据碰撞的比特的准确位置，并有合适的位编码法。

读写器在多标签读取时所应用的防碰撞算法，由于存在最大吞吐率等问题及不足，因此，为了提高系统识别吞吐率，就必须考虑帧长度，这势必影响到标签读取的剩余率判断问题，及标签识别效率问题。另外，为提高判断的准确度和识别效率，这些方法也会增大算法负荷等，从而可能会增加系统成本[17]。因此从实际角度考虑，针对目前所采用算法存在的缺陷，本文提出了一种融合防碰撞算法。

2 算法描述

标签识别中，如果没有标签碰撞问题，则正常识别标签并读取标签信息；如果出现标签碰撞，则根据碰撞标签的数量进行分组处理，根据产生的随机数将标签群分成适当的组后，再对每个标签组中的标签进行碰撞算法来进行一一识别。重复上述步骤，直至标签内部数据被完全读取。

(1)标签群分组：读写器发送分组指令，标签群中的标签均产生一个自身的随机数，随机数保存在与标签相对应的存储器中，产生随机数相等的标签被分为同一个组，并对该组标签根据随机数进行组命名。通过该分组方法将碰撞标签分裂成多个组，使得每组内碰撞标签数量显著减少，以降低标签间的碰撞率。假设共有个标签，将之分为组，即标签产生的随机数范围为(1,)。在标签识别中，任意一组标签被识别时，由于不同时刻每个标签所产生在该数据范围内的随机数概率是相同的，在同一时刻内，分组中的每个标签都随机产生一个(1,)范围之间的随机数，搜索到个标签的二项分布的概率为

经推导可知，读写器在一个读标签周期内预期读到的标签数量为

(2)

随机数，在个未被读取标签群中，读取到个标签的效率为

通过式(3)计算系统最大效率时标签的数量为

(4)

(2)组内防碰撞识别：根据系统协议标准要求，识别系统通常采用二进制搜索树方法来解决标签读取的碰撞问题，且满足该协议标准的标签内部均自带防碰撞机制。在已分组的标签内部，如果没有标签碰撞，则直接识别读取标签信息；如果仍存在标签碰撞问题，则进行组内部的防碰撞识别工作，读写器发出指令并接收到标签返回的信息，读写器模块将根据接收到的该组中碰撞标签的编码形式，在该碰撞编码位上的编码均为“1”，标签被激活后都返回数据给读写器，如读写器读取各个标签的数据后对比判断若有标签碰撞位数，则把该位置“0”。标签在接收到该组数据信息后立即响应，并将(-1)~1位数据回传给读写器。读写器和标签以碰撞发生的编码位为界分别将前后数据进行传送，以此方式进行一一筛选读取工作。读取完该组后，则进行其他组的标签读取工作。重复上述步骤，直至标签内部数据被完全读取。

碰撞算法执行后，首先返回失败命令，读写器接收响应并判断，有如下几种情况：设读写器模块能正确接收标签数据信息，如果仍产生UID编码碰撞冲突，则继续发送失败命令；标签UID编码信息被正确接收到，则利用读取命令读取标签存储信息准确后，发送成功读取命令，继续识别余下的标签UID；如果没有标签响应，则发送成功命令，被识别成功读取信息后的标签，不在参加冲突仲裁。依据算法原理，首先将标签随机产生(1,)之间的随机数，任何一个随机数都满足二项式分布要求。所有标签分组均搜索次数：

(6)

根据式(7)可知，若标签数量多，则查询时间比较长，为了提高搜索效率和减小碰撞率，采用UID编码分区搜索和碰撞冲突识别相结合的方法以提高读写器有效区域内标签防碰撞的识别效率，来实现读写器模块对多个目标标签的读取操作。因此该搜索算法，具有识别率准确度高、吞吐率大、稳定性好、读取所用时隙更少的特点。融合算法流程如图1所示。

图1 防碰撞算法流程图

3 算法仿真分析

利用Matlab 仿真平台，对本文提出的RFID系统标签融合防碰撞算法，在理想信道下进行仿真实验，设定标签仿真数量最大为1000，标签长度为64 bit，程序仿真50次取仿真结果的平均值，将融合后的防碰撞算法仿真结果与其他算法进行比较，不同算法的标签识别效率比较如图2所示。从图可看出，本文的融合防碰撞算法，相对于其他3种方法具有较高标签的识别效率，几种算法的标签识别效率基本保持稳定，不随标签量的增加而有所变动。

不同算法的标签查询次数仿真结果比较如图3所示，几种不同的算法在标签量逐步增加时，查询次数基本与标签量成正比，从结果可看出本文融合后的算法标签查询次数最少。进一步提高标签查询效率为该算法的进一步优化的关键点。

4 结束语

本文提出了一种基于分组式和融合后的二进制算法相融合来实现标签读取的防碰撞算法，实验结果可看出，标签识别效率高，识别过程中数据通讯量显著减小。但在实验过程中也发现如果标签量更大的时候，标签查询时间仍不够理想，因此在进一步的工作中，将主要针对标签量大的时候的标签识别读取时进一步融合改进。

图2 不同算法的标签识别效率比较 图3 不同算法的查询次数比较

[1] ZUO Y. Survivable RFID systems: issues, challenges and techniques[J].,-:, 2010, 40(4): 406-418. doi: 10.1109/TSMCC.2010.2043949.

[2] 宋建华, 郭亚军, 韩兰胜, 等. 自调整混合树RFID多标签防碰撞算法[J]. 电子学报, 2014, 42(4): 685-695. doi: 10.3969/ j.issn. 0372-2112.2014.04.010.

SONG Jianhua, GUO Yajun, HAN Lansheng,An adjustive hybrid tree-conllision algorithm for RFID multi-tag identification[J]., 2014, 42(4): 685-695. doi: 10.3969/j.issn.0372-2112.2014.04.010.

[3] 王云峰, 张斌, 刘洋, 等. 基于码分多址防碰撞的射频识别认证协议[J]. 电子与信息学报, 2014, 36(6): 1472-1477. doi: 10.3724/ SP.J. 1146.2013.01337.

WANG Yunfeng, ZHANG Bin, LIU Yang,Radio frequency identification authentication protocol based on CDMA anti-collision algorithm[J].&, 2014, 36(6): 1472-1477. doi: 10.3724 /SP.J.1146.201301337.

[4] 李志坚, 赖顺桥. 一种基于碰撞位指示的射频识别标签防碰撞算法[J]. 电子与信息学报, 2014, 36(12): 2842-2847. doi: 10.3724/P.J.1146. 2013.01759.

LI Zhijian and LAI Shunqiao. An anti-collision algorithm based on collided bits indicator in radio frequency identification systems[J].&, 2014, 36(12): 2842-2847. doi: 10.3724/SP.J.1146.2013.01759.

[5] 李青青, 刘洪武, 张小林. 一种基于不等长时隙的射频识别防碰撞算法[J]. 电子与信息学报, 2011, 33(11): 2628-2633. doi: 10.3724/SP.J.1146.2011.00303.

LI Qingqing, LIU Hongwu, and ZHANG Xiaolin. An anti- collision algorithm based on unequal timeslots in radio frequency identification system[J].&, 2011, 33(11): 2628-2633. doi: 10.3724/SP.J.1146.2011.00303.

[6] SHAO Min, JIN Xiaofang, and JIN Libiao. An improved dynamic adaptive multi-tree search anti-collision algorithm based on RFID[C]. International Conference on Data Science and Advanced Analytics (DSAA), Shanghai, China, 2014: 72-75.

[7] LEE C C and LIN S Y. A double blocking dynamic framed slotted ALOHA anti-collision method for mobile RFID systems[C]. 2012 Sixth International Conference on Genetic and Evolutionary Computing, Kyushu, Japan, 2012: 581-584.

[8] JIANG Chenyi, XU Yinfei, and WANG Q. Cancellation strategy in dynamic framed slotted ALOHA for RFID system [C]. 2013 IEEE Wireless Communications and Networking Conference (WCNC), Shanghai, China, 2013: 854-859.

[9] WANG Shuai, HONG Weijun, and LI Shufang. A slot-wise LMMSE estimate algorithm for frame slotted aloha protocol of RFID system[C]. 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai, China, 2012: 1-5. doi: 10.1109/ WiCOM.2012.6478372.

[10] 李萌, 钱志鸿, 张旭, 等. 基于时隙预测的RFID防碰撞ALOHA算法[J]. 通信学报, 2011, 32(12): 43-50.

LI Meng, QIAN Zhihong, ZHANG Xu.Slot-predicting based ALOHA algorithm for RFID anti-collision[J]., 2011, 32(12): 43-50.

[11] Landaluce H, Perallos A, and Zuazola I J G. A fast RFID identification protocol with low tag complexity[J]., 2013, 17(9): 1704-1706. doi: 10.1109/LCOMM.2013.070913.131111.

[12] WU Haifeng, ZENG Yu, FENG Jihua,Binary tree slotted ALOHA for passive RFID tag anti-collision[J]., 2013, 24(1): 19-31. doi: 10.1109/TPDS.2012.120.

[13] 张学军, 王娟, 王锁萍. 基于标签识别码分组的连续识别防碰撞算法研究[J]. 电子与信息学报, 2011, 33(5): 1159-1165. doi: 10.3724/SP.J.1146.2010.00940.

ZHANG Xuejun, WANG Juan, and WANG Suoping. A uninterrupted anti-collision algorithm with ID-based grouping for RFID system[J].&, 2011, 33(5): 1159-1165. doi: 10.3724 /SP.J.1146.2010.00940.

[14] XUE Jianbin, WANG Wenhua, LI Songbai,Anti- collision algorithm based on counting mechanism and multi- state binary[C]. 2013 Fifth Conference on Measuring Technology and Mechatronics Automation, Hong Kong, China, 2013: 276-282.

[15] YANG Yongkang, CUI Chunsheng, ZHOU Tuanfeng,Improvement on RFID-based binary anti-collision algorithm [C]. 2012 International Conference on Computer Science and Service System, Nanjing, China, 2012: 515-518.

[16] Vogt H. Efficint object identification with passive RFID tags[C]. Proceeding of International Conference on pervasive Ccmputing. Berlin: Springer-Verlag, 2002: 98-113. doi: 10.1007/3-540-45866-2_9.

[17] 苏健, 韩雨, 骆忠强, 等. 超高频RFID系统中一种可行的时间最优防碰撞算法[J]. 电子学报, 2015, 43(8): 1651-1655. doi: 10.3969/j.issn.0372-2112.2015.08.027.

SU Jian, HAN Yu, LUO Zhongqiang,A fessible time-optimal anti-collision algorithm for UHF RFID systems[J]., 2015, 43(8): 1651-1655. doi: 10.3969/j.issn.0372-2112.2015.08.027.

郭振军： 男，1977年生，讲师，博士生，研究方向为无线射频识别及相关技术.

孙应飞： 男，1964年生，教授，博士生导师，主要研究方向为机器学习与模式识别的理论、方法与应用，生物信息处理、基因调控网络，信息融合，信息安全.

Anti-collision Algorithm of RFID System Based on Grouped Tag

GUO Zhenjun①②SUN Yingfei①

①(,100049,)②(,541004,)

Anti-collision algorithm is a key technique to improveidentification efficiency in Radio Frequency IDentification (RFID) system. For this problem of the efficient identification and the large amount of data transmission, a group-based anti-collision algorithm is proposed. With the improved binary tree search algorithm combining, the tags in each group are identified by reader in turn, which can reduce the amount of data communication effectively. The simulation results show that, compared with several other algorithms, the proposed algorithm has the advantage of efficient identification and a small amount of data exchange.

Radio Frequency IDentification (RFID); Anti-collision; Binary search; Fusion algorithm

TP391.45

A

1009-5896(2017)01-0250-05

10.11999/JEIT160186

2016-03-01；改回日期：2016-07-25；

2016-10-09

郭振军 zjguo666@126.com