基于前缀匹配混合查询树的RFID防碰撞算法

涂蓝

（广东交通职业技术学院，广东广州510800）

射频识别（Radio Frequency Identification，RFID）技术是一种非接触式自动识别技术，利用无线通信信号实现标签与阅读器之间的数据传输及识别[1]。它与条形码、IC卡及生物识别等传统自动识别技术相比，具有存储数据量大、抗污染磨损能力强、识别距离较远、识别速度较快及成本低等优势。所以被广泛应用于物联网、物流管理、门禁、公共交通、智能识别等领域。RFID技术被认为是21世纪的十大重要技术之一，让人类的日常生活最终实现U（Ubiquitous）化，即信息无所不在[2]，也是物联网的三大核心技术之一[3]。一个典型的RFID系统由标签、阅读器、天线和后台管理系统四部分组成[4]，RFID系统主要处理的是标签和阅读器之间的通信，在它们通信过程中往往会发生碰撞问题。解决碰撞问题是研究RFID技术的关键技术之一，特别是多标签碰撞问题，即当阅读器发送射频信号，如果在信号覆盖范围内有多个标签同时响应，导致阅读器无法正确读取标签中的数据信息[5]。

为了解决多标签碰撞问题，国内外研究者提出了很多防碰撞算法，这些防碰撞算法主要是基于时分多址法（TDMA）提出来的，主要有两大类：非确定性的ALOHA算法和确定性的树算法[6]。非确定性的ALOHA算法的基本思想是：签随机选择某个时隙进行响应，进行响应的时间和时隙都具有随机性，所以会可能导致标签不能给在规定时间内100%识别，造成“标签饥饿”现象。该类算法主要有：时隙ALOHA（Slotted ALOHA，SA）[7]算法、帧时隙ALOHA（Frame Slotted ALOHA，SA）[8]算法、动态帧时隙ALOHA（Dynamic Frame slotted ALOHA，DFSA）算法[9]等。确定性的树算法主要思想是：当在识别范围内的标签收到阅读器的查询信号，从标签ID最高位进行匹配，信息一致的标签响应并将信息发送回给阅读器，该类算法主要包括查询树（Query Tree，QT）算法[10]、二进制搜索树（Binary Search Tree，BST）算法[11]、碰撞树 （Collision Tree，CT）算法[12]、连续碰撞比特映射算法（Consecutive Collision bit Mapping Algorithm，CCMA）[13]、自适应多叉树（Adaptive Multi-tree Search，AMS） 算法[14]等。

本文主要在研究查询树算法和自适应多叉树算法的基础上，针对其不足，提了出一种前缀匹配混合查询树（Prefix Matching Hybrid Query Tree，PMHQT）算法。

1 PMHQT算法研究基础

1.1 曼彻斯特编码

曼彻斯特（Manchester）编码通过电平的升降变化来描述逻辑“0”或逻辑“1”。“0”表示信号从正向负跳变，“1”表示信号从负向正跳变。由于Manchester编码不存在无跳变情况，因此阅读器可以识别某个碰撞位，并能够在接收端解码并检测出接收信号的碰撞位信息[15]。图1为通过Manchester编码检测出碰撞位示例图，两个标签A和B的ID号分别为：10010100和10100110，阅读器通过Manchester编码检测，最终会收到“10xx01x0”信息，其中“x”表示碰撞位。

从图1可以看出碰撞位的位置在第2、第5和第6位，阅读器检测到标签碰撞位信息，利用这些碰撞位信息能够将碰撞标签进行分组识别。

图1 Manchester编码示例

1.2 QT算法

QT算法的基本思想是：阅读器发送Query查询命令，作用范围内的标签收到该查询命令后，将ID前缀与查询信息比较，若相同，则响应。如果有多个标签ID前缀匹配，阅读器会在之前的查询前缀加上“0”或“1”，组成心得查询命令，再次发送新的查询命令，直到标签唯一匹配为止。

假设阅读器工作范围内有5个待识别标签（A、B、C、D、E），它们的ID编码分别为：00001011、 00110110、 10011000、 11001101 和01100100，其识别过程如表1所示。

表1 QT算法识别过程

从表1可以得出，识别5个标签总共所需9个时隙数，假设RFID系统中有n个待识别标签，则QT算法所需总时隙数为[15]：

系统吞吐率为：

当n=1 000时，QT算法的吞吐率S=50.03%左右，可以得出，当待识别标签数较多时，吞吐率会下降，这时因为QT算法的本质仍然是基于二进制树的。当标签数较多，则碰撞时隙较多，识别速度就会相对应的下降，及识别时间也会增加。

为了解决QT算法的不足，在查询前缀的基础上引入前缀匹配和混合查询树思想，当碰撞标签较多时，动态使用多叉树进行分组查询。

2 PMHQT算法

2.1 PMHQT算法实现步骤

PMHQT算法思想是基于查询树算法，所以它是属于查询树算法的一种，阅读器通过曼彻斯特编码检测碰撞位信息，并根据碰撞位信息发送匹配查询前缀，前缀相匹配的标签响应，并发送除查询前缀之外的其余ID码给阅读器。

在PMHQT算法中，用堆栈来保存每一轮识别中所需的匹配查询前缀，算法开始，把一个空串压入到堆栈中，此时所有待识别标签都将响应，在接下来的查询过程，阅读器不断重复的进行新的查询前缀入栈和出栈操作，直到堆栈为空，所有标签被识别，算法结束。

PMHQT算法具体实现步骤如下：

①对堆栈进行初始化。将空串压入堆栈；

④阅读器通过曼彻斯特编码检测出碰撞标签的碰撞位信息Coll_inform；⑤根据碰撞位信息确定最佳匹配前缀prefix.；⑥将新的查询前缀压入堆栈中，即执行PUSH（prefix）操作；

⑦判断堆栈是否为空，若为空，则算法识别过程结束；若不为空，则从堆栈的栈顶弹出查询前缀，即执行POP（prefix）操作，根据查询前缀，标签进行响应，然后跳转到步骤③中继续执行。

2.2 PMHQT算法流程

PMHQT算法流程图如图2所示：

2.3 PMHQT算法举例分析

假设系统有5个标签A～E，它们ID编号分别为Tag A：00001011，Tag B：00110110，Tag C：10011000，Tag D：11001101，Tag E：01100100。识别过程如表2所示。

图2 PMHQT算法流程图

表2 PMHQT算法识别过程

从表2中可以得出识别5个标签总共需要7个时隙，在相同条件下，与表1相比较，PMHQT算法比QT算法所需时隙数减少了2个，系统吞吐率可以达到72%左右，明显比传统的QT算法在总时隙数和吞吐率上更有优势，也可以进一步说明PMHQT算法识别速度更快及识别时间更短。

3 仿真实验

仿真实验环境：Intel(R)Core(TM)i7-8550U CPU@1.80GHz 2.00GHz的内存及64位windows 10操作系统下，利用MATLAB仿真软件进行算法编程，与QT算法、AMS算法和AHT算法分别进行了3组仿真对比实验（总时隙数对比、吞吐率对比和通信复杂度对比）。为保证仿真实验的可靠性，实验中待识别标签总数取值范围为[01000]，进行100次实验取平均值。

3.1 总时隙数对比仿真

PMHQT算法由于采用的是前缀匹配思想，根据查询前缀的情况动态选择多叉树进行标签识别，在整个识别过程中没有产生空闲时隙，所以PMHQT算法所需的总时隙数等于碰撞时隙数与成功时隙数之和。图3是本文PMHQT算法与AMS算法、AHT算法和QT算法在总时隙数上的对比，从图中可以得出本文算法在总时隙数上较其他3种算法所需最少。当标签总数增加到1 000时，PMHQT算法所需总时隙数大约为1 370个。

图3 仿真对比：总时隙数

3.2 吞吐率对比仿真

吞吐率S指的是待识别标签数与所需总时隙数之比，是衡量一个算法性能好坏的重要指标之一，吞吐率越高，算法性能越优，反之，吞吐率越低，算法性能越不稳定。图4是本文PMHQT算法与AMS算法、AHT算法和QT算法在吞吐率上的对比，可以看出PMHQT算法的吞吐率最高，基本保持在0.72左右，所以PMHQT算法的性能较其他3种算法是最优的。当标签数增加到1 000时，吞吐率仍然可以维持在0.73左右，间接说明PMHQT算法适合大量标签的场合。

图4 仿真对比：吞吐率

3.3 通信复杂度仿真

PMHQT算法的通信复杂度由2部分构成：阅读器复杂度和标签复杂度，与标签ID号的长度有关。通信复杂度决定成本的高低，阅读器和标签复杂度越低，RFID系统成本就越低，反之则越高。图5是本文PMHQT算法与AMS算法、AHT算法和QT算法在通信复杂度上的对比，标签ID号的长度为64位。从图5中可以得出，PMHQT算法的通信复杂度最低，整个RFID系统的成本也越低。

图5 仿真对比：通信复杂度

4 结语

本文针对RFID系统中的防碰撞问题，在查询树算法和多叉树算法的基础上，提出了一种前缀匹配混合查询树PMHQT算法，该算法在识别标签过程中能够完全消除空闲时隙，从而减少总时隙数，更好的提高算法的吞吐率，使得算法吞吐率一直保持在0.73左右。而且为了减少阅读器和标签成本，该算法很大程度降低了通信复杂度。特别当标签数目较大时，本文提出的算法在吞吐率和通信复杂度都要优于其他算法，因此该算法具有一定的应用价值。