确定型标签防碰撞算法研究综述

张德慧+李政

摘 要：确定型标签防碰撞算法是无线射频识别（Radio Frequency Identification，RFID）技术中一种关键性的标签防碰撞算法，可100%识别完毕所有待测标签。本文对确定型标签防碰撞算法的核心思想进行深入探讨，总结归纳不同确定型标签防碰撞算法的优缺点，结合现状，提出下一步研究方向。

关键词：RFID；标签防碰撞技术；确定型标签防碰撞算法

中图分类号：TP312 文献标志码：A

0 引言

RFID技术是一种非接触式的自动识别技术，在“万物皆可通过网络互联”的物联网时代，RFID技术以其自身独特的优势，如：阅读器可同时识别大量标签、标签信息可重复利用、标签体积形状多样化等，成为物联网中物体身份识别的关键技术。一个完整RFID系统由阅读器、标签和计算机系统组成。计算机系统向阅读器传达读取标签指令后，阅读器便发送该指令给处于其自身范围内的所有标签，激活的标签立即与阅读器建立通信。通信过程中，由于标签数量过多，容易产生信号冲突。因此，本文就标签碰撞问题研究标签防碰撞算法。

目前，标签防碰撞算法主要从4个方面入手空分多址（Space Division Multiple Access，SDMA），码分多址（Code Division Multiple Access，CDMA），频分多址（Frequency Division Multiple Access，FDMA），时分多址（Time Division Multiple Access，TDMA）。其中，TDMA是把整个通路容量按时间划分给多个用户，也是现在RFID标签防碰撞算法领域应用最为广泛的划分方式。基于TDMA技术的特点，又将标签防碰撞算法分为两类：一类是概率型的标签防碰撞算法，该算法中，标签通过随机选择时间点来响应阅读器，算法虽然简单易执行，但是容易造成“标签饥饿”现象。另一类是确定型的标签防碰撞算法，主要分为4种：二进制搜索树算法、动态二进制搜索树算法、回退式二进制搜索树算法、查询树算法，该类算法通过二进制编码逐一选择标签进行通信，可100%识别完所有待测标签，避免“标签饥饿”现象。

1 确定型标签防碰撞算法

1.1 二进制搜索树算法

阅读器向在它范围内的所有标签发送二进制位全为1的搜索指令，该指令长度与标签ID号长度相同。被激活的标签会将自身ID号位数与指令中的每一位进行比较。若ID号小于或等于该二进制指令，则对阅读器进行响应，下一次的读取指令与初始指令相同；否则，检测最高碰撞位，并将该位从“1”置为“0”，碰撞位之前的位数保持不变，作为下一次的搜索指令。直至标签全部搜索完毕，查询结束。假设有4个标签，分别为标签A：11010111、标签B：11100101、标签C：11101111、标签D：11010101，其二进制搜索树算法搜索过程可见表1。

总的搜索次数为式（1）所示，其中，N为待测标签总数量。

（1）

标签识别完毕传输的总信息量为式（2）所示：

（2）

1.2 动态二进制搜索树算法

动态二进制搜索树算法在二进制搜索树算法的基础上，保留算法思想，但减少了通信传输的信息量，检测到碰撞位时，碰撞位后面的所有二进制位全都成为冗余数据，步骤与二进制搜索树算法类似。依旧以上述4个标签为例，其动态二进制搜索树算法搜索过程可见表2。

标签识别完毕传输的总信息量为式（3）所示：

（3）

1.3 回退式二进制搜索树算法

回退式二进制搜索树算法算法以二进制搜索树算法为基础，修改了二进制搜索树算法的搜索规则，该算法中，每当阅读器成功识别一个标签之后，都要重新发一个二进制位数全为“1”的搜索指令，增加了总的查询次数。回退式二进制搜索树算法为了改进该弊端，在一个标签被成功读取之后，不会再重新发送一个二进制位数全为“1”的搜索指令，而是依据上一轮的搜索指令，将上一轮中的碰撞位从“0”修改为“1”，进行下一轮的标签读取。每一轮标签读取的命令码长度与标签ID号长度相同，依旧以上述4个标签为例，其回退式二进制搜索树算法搜索过程见表3。

总的搜索次数为式（4）所示：

Sum=2N-1 （4）

标签识别完毕传输的总信息量为式（5）所示：

Ctraffic=2L（2N-1） （5）

1.4 查询树算法

查詢树算法与之前的二进制搜索树算法、动态二进制搜索树算法和回退式二进制搜索树算法有所不同，阅读器在发送查询标签的初始化命令码时，会根据标签的ID特征，发送长度为K的前缀码，不再是发送和标签ID号相同的序列长度，被激活的标签将自己ID号的前K位与该前缀码相比较，若相同，则标签与阅读器建立通信，并把第“K+1”位至最后一位发送给阅读器，此时标签识别成功。若多个标签ID号的前K位与前缀码相同，则发生碰撞。假设标签为标签A：0010、标签B：1110、标签C：0001、标签D：1101其查询树算法搜索过程见表4。

结语

通过以上分析，在几种确定型标签防碰撞算法中，二进制搜索树算法在实现上相对简单，但是在执行过程中，重复性工作较多，搜索次数大，且识别标签所需信息通信量高，增加了系统的负担。动态二进制搜索树算法在通信量方面明显要低于BST算法，但搜索次数没有减少，与二进制搜索算法的搜索次数相同。回退式二进制搜索树算法不仅降低了搜索次数，还减少了信息通信量，但标签数量过多时，会增加系统搜索时间。查询树算法通信量少，但是随着标签数量增多，二叉分支也会增多，直到检测出没有响应的标签时，才终止查询，增加系统的搜索时间。

目前，针对确定型算法的研究主要集中在查询树算法上，众多研究学者通过对查询树中二叉树或者多叉树动态结合，来达到减少查询次数、降低信息通信量的目的。因此，为了后续的研究能够高效快速的开展，建议针对确定型标签防碰撞算法中的查询树算法重点研究，以取得更优良的算法。

参考文献

[1]Ying-Meng H U， Zhang X H. Research of an Adaptive Searching Anti-collision Algorithm for RFID Based on Information-Bit Encoding[J]. Acta Electronica Sinica， 2016.

[2]杨晓娇，吴必造.射频识别中确定性防碰撞算法研究[J].微型机与应用，2017，36（8）：67-69.

[3]丁治国，雷迎科.基于优先级避让的防碰撞算法研究[J].计算机应用研究，2016，33（3）：836-839.endprint