纺织物资管理中的RFID标签防碰撞算法研究

陈青　陈永当　程云飞　闵渭兴

【摘 要】目的：优化RFID标签防碰撞算法从而提高纺织物资管理效率。方法：针对确定性防碰撞算法存在识别效率不高等问题，设计一种基于位隙分组的动态退避式二进制搜索（BGDRBS）算法。该算法先让标签随机选择各自的位隙，阅读器根据标签返回的位隙值实现标签分组，在组内识别中，每次查询只发送和返回部分序列号，且无须从头开始。结果：仿真实验表明，与DBS算法和RBS算法相比，当标签数达到100时，BGDRBS算法的数据传输量分别降低了70.55%、53.77%，吞吐率分别提高了239.41%、8.14%。结论 BGDRBS算法提高了系统识别效率，且简单易实现，在纺织物资管理中应用前景良好。

【关键词】RFID;位隙分组;防碰撞算法;MATLAB仿真;物资管理

中图分类号： TP391 文献标识码： A 文章编号： 2095-2457（2019）31-0069-002

DOI：10.19694/j.cnki.issn2095-2457.2019.31.031

0 引言

无线射频识别（radio frequency identification，RFID）是一种高效、非接触式的自动识别技术[1]。将RFID技术应用到纺织物资管理中，能消除很多人为差错，提高工作效率，降低人力和物力的开销[2]。由于在阅读器识别多个信息的过程中会发生标签碰撞问题，使阅读器不能对标签进行识别，从而导致标签数据传送失败[3]。目前，主要的标签防碰撞算法有ALOHA类随机性防碰撞算法和二进制树确定性防碰撞算法两大类[4]，ALOHA类算法简单，但存在读取率低、部分标签被“遗忘”等问题，而确定性防碰撞算法可以完全读取[5]。因此，基于RFID纺织物资管理系统，本文提出了一种基于位隙分组的动态退避式二进制搜索（BGDRBS）算法，其思想是在识别前先让全部标签随机选择各自的位隙，阅读器根据标签返回的位隙值实现分组识别，在组内识别中，每次查询只发送和返回部分序列号，且无须从头开始，降低识别过程的查询次数与数据传输量，进一步提高系统的识别效率。

1 基于位隙分组的动态退避式二进制搜索（BGDRBS）算法

1.1 算法原理

本文算法旨在減少阅读器查询次数和数据传输量，提高系统的识别效率。因此，在退避式二进制搜索算法的基础上结合动态查询思想，并且引入标签分组：

假定待识别标签数为n，标签位隙长度为L，p=1L，通过位隙分组后：

一组内有r个标签的概率为：

P（r）=C■■p■（1-p）■（1）

可知，含有r个标签的组的期望值为：

E（r）=L*P（r）（2）

则，分组后的平均标签个数为：

n■■=■（3）

由公式（3）可知，位隙长度L取值越大，平均分到各组的标签数就越少，从而提高了识别效率，但同时也提高了标签成本，所以位隙长度要根据RFID系统的实际应用情景来设置。

1.2 算法实现流程

本算法需要建立新的查询指令：Request（R+B）——初始查询，阅读器发送查询命令，所有序列号小于或等于查询序列号的标签响应，并随机选择自己的位隙;Request（R+BR）——组内查询，只有位隙值等于BR的标签才会响应。其中R参数为查询序列号，B参数为位隙值，BR参数为查询位隙值。

（1）阅读器向周边标签发送初始查询指令Request（R+B），R的初始值为全1，B的初始值为0、长度为位隙长度L，所有标签响应并随机选择自己的位隙。假如某个标签选择的位隙为n，则该标签位隙标志位的第n位为1，其他位为0。随后标签将生成的位隙值B传送回阅读器。

（2）如果B为0，则说明无标签存在，跳转至（8）。否则，找到B中为1的最低位，让BR对应的值为1，其他位为0，形成该组的查询BR，并将B的最低位清零。

（3）阅读器发送组内查询指令Request（R+BR），R的初始值为全1，所有B等于BR的标签响应，将各自的序列号传送回阅读器，若没有收到响应信号，则说明本组内已无未识别的标签，跳转至（2）。否则，继续。

（4）阅读器检查标签返回的序列号，如果能识别，则跳转至（6）。如果出现碰撞位，继续下一步。

（5）阅读器将当前查询序列号压栈，把碰撞的最高比特位置0，高于最高碰撞比特位不变，再输出查询前缀码，跳转至（4）。

（6）根据识别出的标签序列号，执行选取指令Select（R），使该标签进入读取状态，随后阅读器再发送读取指令Read-data，对处于读取状态的标签进行数据读取，数据读取完成后，发送去选择指令Unselect，使该标签转为去激活状态，对此后阅读器的指令不再响应。

（7）压栈的序列号从堆栈中弹出[6]，作为查询序列号，如果序列号为全1，跳转至（3）。否则，跳转至（4）。

（8）回到流程（3）。

（9）结束。

其中步骤（1）、（2）是通过位隙分组实现标签的分组查询，步骤（3）～（8）是通过动态查询与节点退避实现标签的组内识别。

2 算法仿真与分析

应用MATLAB软件分别对DBS算法、RBS算法和本文算法进行实验仿真，实验的标签数目范围为[1，100]，标签ID为16位，位隙长度为16。为了确保实验的准确性，取100次仿真结果的平均值。系统的数据传输量与吞吐率是衡量RFID系统识别效率的重要指标。如图1和2，标签分组使得各组平均识别标签数较总标签数少了很多，从而降低了数据传输量，提高了系统吞吐率。

图1 数据传输量的比较

图2 吞吐率的比较

3 结语

针对纺织物资管理系统中RFID标签碰撞问题，设计了一种基于位隙分组的动态退避式二进制搜索（BGDRBS）算法。在阅读器识别前，先对标签进行分组处理，再运用动态查询和节点退避的查询思想逐组识别所有标签。仿真结果显示，BGDRBS算法的识别效率有了明显的改进，且算法简单易实现，能进一步推动纺织行业企业信息化的发展。

【参考文献】

[1]A.EL ALAMI，Y.GHAZAOUI，S.DAS，S.D.BENNANI，M.EL GHZAOUI.Design and Simulation of RFID Array Antenna 2x1 for Detection System of Objects or Living Things in Motion[J].Procedia Computer Science，2019，151.

[2]杨衡亮.纺织企业仓库管理系统的设计及应用[J].棉纺织技术，2015，43（05）：29-32.

[3]Nasour Bagheri，Parvin Alenaby，Masoumeh Safkhani.A new anti‐collision protocol based on information of collided tags in RFID systems[J].International Journal of Communication Systems，2017，30（3）.

[4]张小红，张佳琦.基于帧时隙的RFID系统迫零预编码防碰撞算法研究[J].信息网络安全，2018（02）：34-39.

[5]王丹，赵凯.基于距离预测分组的ALOHA算法[J].南京理工大学学报，2018，42（01）：102-106.

[6]李锋，南敬昌，李蕾，等.后退锁位式RFID自适应多叉树防碰撞算法[J].计算机工程与应用，2017，53（08）：102-105+164.