基于RFID的多叉树防冲撞算法研究

王硕 孙知信

摘  要：射频识别技术目前在生活中被广泛使用，其具有识别质量高、适应度强且成本较低的优点。但是，目前在多目标环境下，会出现识别冲突的现象，降低识别效率。为此，该文提出一种基于多叉树动态分裂机制的防碰撞算法，在二叉树确定性防碰撞算法的基础上，引入多叉树分裂机制，并对插槽结点碰撞机制进行优化，对重复结点进行跨越式读取，减少插槽使用个数，提高标签命中几率。通过仿真测试可以看出，该文所提出的算法在多标签读取速度上有所提高，在实际的使用中有着重大的意义。

关键词：RFID 防碰撞算法  多叉树  分裂  动态

中图分类号：TP3                             文献标识码：A文章编号：1672-3791（2021）04（b）-0048-04

Research on Multi Tree Anti-Collision Algorithm Based on RFID

WANG Shuo  SUN Zhixin

（School of Modern Posts， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu Province， 210003  China）

Abstract： Radio frequency identification technology is widely used in our daily life， which has the advantages of high identification quality， strong adaptability and low cost. However， in the current multi-target environment， there will be recognition conflicts， which will reduce the recognition efficiency. Therefore， this paper proposes an anti-collision algorithm based on multi tree dynamic splitting mechanism. On the basis of binary tree deterministic anti-collision algorithm， the multi tree splitting mechanism is introduced， and the slot node collision mechanism is optimized. The repeated nodes are read by leaps and bounds to reduce the number of slots and improve the tag hit probability. Through the simulation test， we can see that the algorithm proposed in this paper has improved the speed of multi tag reading， which has great significance in practical use.

Key Words： RFID; Anti-collision algorithm; More tree; Division; dynamic

随着物联网时代的到来，射频识别技术（Radio Frequency Identification，RFID）[1-2]的普及使得在我们的生活中相应的技术应用的场景越来越多，如：商品售卖、货物运输、食品溯源等多方面进行应用。RFID系统的使用不单单是一个电子标签，而是多种物联网技术的结合。一个RFID系统主要包括电子标签、读取器和数据处理系统。当使用阅读器对电子标签进行读取时，其会通过数据传输通道读取数据到达数据处理系统。但是，当在阅读器的扫描区域内出现多个标签时，由于其阅读器只存在一个数据传输通道，这时，多标签之间产生了相互干扰，如果产生碰撞则会导致识别时间的增加且影响系统的效率，导致阅读器无法识别标签。这就是RFID系统中标签碰撞问题。

1  相关技术研究

RFID防冲突算法可以分为确定性算法和不确定性算法。不确定性算法主要是ALOHA算法[3]。其基本思想是：当多个标签同时进入到扫描器中，则扫描器命令其作用范围内的所有标签延迟一段时间再进行响应，其延迟时间是随机选择的。但是由于ALOHA算法容易发生碰撞问题，尤其是部分冲突易于发生。不确定性算法的优点在于简单、快速，但是识别性能不够稳定，处理大量标签时会出現处理时间较长的问题。确定性算法主要基于二叉树进行实现的算法。确定性防碰撞算法虽然对RFID系统的要求更高，但是其算法不存在不稳定的情况，在处理大量标签时其性能较不确定防碰撞算法更有优势。

金迪[4]对RFID冲突的问题提出了一种并发执行的后退式二进制RFID防冲突算法，通过并发执行多线程技术同步运行多个独立的程序片段，解决冲入问题，提高系统效率。江岸、罗小平[5]则提出一种基于时隙冲突判断的RFID防碰撞的算法，该算法在时隙前就对碰撞探测码进行判断，判断是否会产生碰撞，以此为根据消除空闲的时隙。当发生探测码碰撞时，结合冲突位置和时隙规避机制可以有效地降低碰撞时隙的概率。陈清等人[6]对于木制品多目标扫描时出现的冲突问题，在动态帧时隙ALOHA防冲突算法的基础上，采用概率学方法进行研究，提出一种智慧防冲突算法。张荣华等人[7]针对树的防碰撞算法效率较低的问题，利用在树型结构中的冲突位分布信息，提出一种基于冲突分段的动态树型防冲突算法。苏健、温广军等人[8]提出了一种基于二进制搜索算法的IACA算法。在RFID标签发生碰撞时，阅读器会根据曼彻斯特代码的特点确定碰撞的位置，并分别查询最高的两位碰撞位，查询命令位设置为1。当电子标签ID小于或等于查询命令时，电子标签向读取器返回响应命令以发送自己的ID信息，从而减少碰撞概率，减少阅读标签时间。LAIYC等[9]提出了一种最佳的二进制跟踪树协议，在这种算法中，标签被一次次地拆分成更小的分组进行识别。

在该文中，针对确定性算法所存在的缺点提出一种基于分裂树的防冲突算法。称为多叉树动态防碰撞算法（Multi-tree Dynamic Anti-Collision Algorithm，MDACA）。

2  相关算法研究

2.1 二叉树算法

确定性防碰撞算法主要是基于树形结构思想发展而来，之所以被称为确定性算法，是因为根据树的节点不断衍生子节点的原因，无论怎么样都可以最终都会被查询到，也就是说，在确定性防碰撞算法的阅读器扫描区域中，每一个RFID标签最终都可以被扫描到。图1二叉树防碰撞算法树形结构图。

从图1中可以看出，在第一层的一个节点会分成两个节点，可以看出第二层的两个节点依然冲突，所以还会再次分裂，直到节点不再有冲突发生。

我们可以根据不同的遍历树的方法得到多种，但在解决冲突所需的插槽个数方面，它们本质上是相同的。在这个例子中，它们需要相同数量的插槽来解决初始结点5个标签的冲突，即10个插槽。

2.2 改进二叉树防碰撞算法

在二叉树中，每一个节点都可以在下一级分成两个新的节点。通过这个机制，可以对冲突的节点进行分割。可以将冲突的插槽分成两个子插槽，如果第一个子组是空闲的，则可以确定第二个子组是冲突。因此，通过假装已经发生碰撞，仅通过将第二子组分成两个子组就可以减少时隙浪费，具体见图2。

从图2可以看到在对碰撞标签进行处理时，相对于原始二叉树防碰撞算法的效率更高。

3  多叉树动态防碰撞算法

3.1 算法改进

改进二叉树算法虽然解决了二叉树算法的一些插槽浪费的问题，但是在实际的使用中，其分裂节点的效率仍然较低。为此，在此基础上再次改进，引入多叉树分裂机制进行碰撞标签分裂。提出了一种多叉树动态防碰撞算法（MDACA）。该算法具有以下改进方向。

（1）该算法在基于树的防碰撞算法的基础上进行改进，提出使用多叉树分裂机制对防碰撞标签进行分裂，提高标签读取效率。

（2）为了减少时隙的浪费，针对碰撞标签，如果此标签左插槽为空闲插槽，则通过改进二叉树防碰撞算法思想，对重复父插槽的子插槽进行不读取机制。

（3）多叉树中冲突插槽分裂处理问题，针对其插槽中标签个数按照（n/2）+1的机制对插槽进行分裂。其中n为该次标签冲突时标签的个数。

（4）在多叉树动态防碰撞算法中，对插槽分裂后的子插槽分裂顺序进行左分支优先处理原则，在进行分裂处理时先对左分子插槽处理，直至只包含一个节点或者0个节点。这样保证标签碰撞处理的顺序和有效性。

（5）在多叉树动态防碰撞算法中，对碰撞插槽进行遍历时，对各插槽标签数进行计数。为了增加标签命中率，在确保某个插槽（只包含2个插槽）为冲突插槽时，直接采取读取这两个插槽，提高RFID系统标签读取效率。

如图3所示，对碰撞节点（A，B，C，D，E）进行处理，按照该章提出的MDACA算法思想，采用（n/2）+1公式计算，可得知在对初始插槽使用三分裂机制进行插槽分裂处理。按照所提出的左子集优先处理原则，先对级别2中的（A，B）插槽进行处理，在对级别2中的（A，B）冲突插槽进行处理时，因其左子集插槽为空闲插槽，所以右子集必定为冲突插槽，为了减少时隙的浪费，不对级别3中的（A，B）进行扫描。最后对最右子集（D，E）进行处理时，因知道其子集个数，其必定为冲突插槽，所以直接扫描其D、E两个插槽子集。这样，在5个碰撞标签的情况下，只需要7个插槽就可以解决。

则其Lk的公式为：

（1）

通過对所提出算法所需要的平均时隙进行分析，其效率公式为：

（2）

其中，T（N）是识别N个冲突标签所需的平均时隙数。

对MDACA算法中使用的平均时隙公式进行推导，可得出：

（3）

（4）

（5）

其中p是随机概率，且认为TMDACA（0）=TMDACA（1）=0，表示插槽中只包含0个或1个结点不再冲突，无需再次分割。q为多叉树算法进行分裂的概率，该文提出的算法中使用随机概率round。其中B（N，1/Li，0）表示初始第i层的标签个数，B（N，1/Li，1）表示阅读器扫描第i层时扫描成功的几率。

3.2 算法实现

通过matlab对提出的MDACA算法进行仿真，与MTA算法、PNBA算法进行对比，由图4可看出，在一定范围内多标签存在的情况下，阅读器一次性正确读取的标签个数，BTDCAA算法读取的个数更多，其效率更高。

从实验结果中可以看出，该文所提出的改进算法在进行碰撞标签处理时读取效率比原始的二叉树防碰撞确定算法和改进二叉树算法都有提高。

4  结语

该文所提出的多叉树动态防碰撞算法在改进二叉树算法的基础上引入多叉树动态分裂机制，并对分支分裂进行改进，使其按照左子树优先分裂原则，遇到非碰撞结点结束，并在读取时实现跨越式读取，省去读取重复插槽，减少插槽使用个数，从而提高读取正确率和时间效率。其在实际的使用中有着深刻的意义。

参考文献

[1] 王大伟.基于RFID的物流管理系统设计及应用[J].电子设计工程，2016，24（20）：66-68，71.

[2] 马宗正，马海舒，马涛.基于射频识别技术的工件定位系统设计与实现[J].现代制造工程，2017，50（7）：109-113.

[3] Hu haiyan，yan hui.Study on ALOHA Anti-Collision Algorithm Based on LoRa for Internet of Things[C]//2018 3rd International Conference on Smart City and Systems Engineering （ICSCSE）. IEEE，2018：652-654.

[4] 金迪.RFID包装系统中防冲突算法研究[J].包装工程，2018，39（1）：1-5.

[5] 江岸，罗小平.基于时隙冲突预判的RFID防碰撞算法[J].计算机工程与设计，2017，38（7）：7-13.

[6] 陈清耀，林宇洪，邱荣祖.基于RFID木制品物流多目标识别算法的优化[J].福建农林大学学报：自然科学版，2016，45（4）：476-480.

[7] 张荣华，张海周，杨大志，等.基于冲突分段的动态树型RFID防碰撞算法[J].计算机工程与应用，2017，53（17）：117-121.

[8] 苏健，温广军，韩佳丽.一种基于ISO18000-6B标准的RFID防碰撞算法[J].电子学报，2014，42（12）： 2515-2519.

[9] LAI Y C，HSIAO L Y，LIN B S.Option slot assignment for binary tracking tree protocol in RFID tag identification[J].IEEE/ACM Transactions on Networking（TON），2015，23（1）：255-268.