单阅读器移动RFID系统下改进的标签防碰撞算法

李欣怡 李晓武 游进国 贾连印 丁家满 李润鑫

（昆明理工大学信息工程与自动化学院）

随着社会的发展，物联网技术已逐步渗透到人们的生活中，它使物体和机械能够互联并共享收集到的信息［1］。 射频识别技术（RFID）作为物联网技术的感知层，发挥着重要的作用。在RFID 识别过程中，阅读器识别区域内有若干标签随机分布， 当一个以上的标签同时与阅读器进行通信时，它们的反向散射信号相互抵消，导致阅读器不能获取任何信息，这被称为碰撞。 在没有任何机制或措施协调阅读器和标签之间通信过程的情况下，阅读器将无法正确读取标签ID 号，那么此次识别过程失败，进入再次识别过程，一直重复以上步骤，直到阅读器识别范围内的所有标签都被成功识别为止［2］。

目前常用的标签防碰撞算法主要分为两类，分别是基于树的确定性防碰撞算法和基于ALOHA 的随机性防碰撞算法［3］。基于树的确定性防碰撞算法识别效率较高，但由于要遍历所有标签，所花时间较长；基于ALOHA 的随机性防碰撞算法虽然简单，但是容易产生“标签饥饿”现象，随着标签数量的增多，系统吞吐率也逐步下降。

笔者提出一种将两类算法相结合的方法，整合了两类算法各自的优势，同时使用尾码应答机制减少传输所需的时间成本，将该方法应用于单阅读器移动RFID 系统中， 通过理论分析和MATLAB 仿真实验验证，改进后的算法能降低时间成本，使系统性能有一定提高。

1 单阅读器移动RFID 系统

单阅读器移动RFID 系统是单个阅读器采用移动方法去识别一个区域内标签的系统［4］。 这种单阅读器移动RFID 系统只适用于中小型区域的标签识别，因为如果待识别区域过大，那么通过移动阅读器让大区域内的标签都能进入阅读器信号区并被识别需要花费较多的时间［5］。 该系统的模型如图1 所示，待识别区域A 内随机分布着若干待识别的标签，阅读器识别区域为P，使用者手持单阅读器沿固定路径移动识别标签。

图1 单阅读器移动RFID 系统场景

在本文的识别过程中，采用尾码应答机制可以减少传输时间成本，标签不需要发送完整的ID号给阅读器，只需要发送小长度尾码即可。

2 RFID 系统中传统的标签防碰撞算法

2.1 帧时隙ALOHA（FSA）算法

帧时隙ALOHA 算法在时隙ALOHA 算法的基础上引入了帧的概念，其主要思想是：将若干个时隙组成一个帧，帧指的是阅读器两次请求操作之间的时间间隔， 标签只能随机在0-L-1 内选择一个时隙和阅读器进行通信。 该协议的时隙存在3 种情况：空闲时隙,即没有标签进行响应；碰撞时隙， 在某个时隙有大于一个的标签同时对阅读器进行响应，就会产生标签信息的碰撞［6］；成功时隙，有且仅有一个标签响应，阅读器能成功读取到标签信息。 未被成功识别的标签，需要在下一轮中重新进行识别。

下面举例对该算法进行说明，设帧长L 为3，待识别区域内有5 个标签。 表1 是帧时隙ALOHA 算法的工作过程。

表1 帧时隙ALOHA 算法工作过程

2.2 动态帧时隙ALOHA（DFSA）算法

动态帧时隙ALOHA 算法是在帧时隙ALOHA 算法上改进得来的，帧时隙ALOHA 算法中，由于帧长固定不变，当标签数量和帧长相差较大时，系统性能很差。动态帧时隙ALOHA 算法中，如果使帧长和标签数量近似相等，系统吞吐率能维持在最大值。 具体解决办法是根据预估标签数量动态调整下一帧帧长，如果该帧中碰撞时隙较多，那么增加下一帧的帧长，反之减小下一帧的帧长。

2.3 二进制搜索（BS）算法

二进制搜索算法采用比特冲突检测协议作为防碰撞方案［7］。 阅读器以二进制序号为参数向标签发送请求命令，收到命令的标签将自己的序号与阅读器发送的序号作比较，如果自己的序号小于等于阅读器发送的序号，就将自己的编码发送给阅读器，阅读器逐位识别相应的标签［8］。如果标签之间发生碰撞，阅读器根据碰撞位减小序号继续搜索；如果标签之间没发生碰撞，则成功识别到一个标签，阅读器以初始序号为参数重新开始搜索，直至所有标签搜索完毕。

2.4 后退式二进制搜索（BBS）算法

后退式二进制搜索算法是二进制搜索算法的一种改进。 改进的思路是：当一个标签成功被识别后，阅读器不会返回到原始的碰撞节点继续搜索，它将退回到节点的上层，即父节点［9］。

假 设 有 4 个 标 签:Tag1 10110010，Tag2 10100011，Tag3 10110011，Tag4 11100011。后退式二进制搜索算法识别流程如图2 所示。

图2 后退式二进制搜索算法识别流程

3 单阅读器移动RFID 系统下FSA 和BBS 结合的标签防碰撞算法

3.1 算法流程

工作原理为：在待识别区域内，手持单阅读器沿固定路径对标签进行识别。 阅读器发送读取标签尾码指令，在应答区域内的标签生成一个小于等于帧大小的随机数，随机时隙数为0 的标签将自己的尾码发给阅读器。

RFID 阅读器以帧时隙ALOHA 算法接收标签发送过来的尾码，阅读器有3 种响应情况：

a. 空闲时隙（slot_idle）。 信号区内没有标签尾码选择该时隙与阅读器进行通信，阅读器读取不到任何信息。

b. 成功时隙（slot_succ）。 信号区内只有一个标签尾码选择该时隙与阅读器进行通信，阅读器能成功读取到该标签尾码信息。 阅读器将该尾码与尾码表进行比较， 如果该尾码未在尾码表中，则该标签为全新标签，阅读器发送读取剩余信息的指令， 收到剩余信息后进行整合并置静默；若该尾码已出现在尾码表中，则将该标签判定为已识别标签，不作任何处理。

c. 碰撞时隙（slot_coll）。 信号区内多个标签尾码选择该时隙与阅读器进行通信，标签尾码之间发生碰撞，此时阅读器采用BBS 算法对碰撞时隙的各个标签进行处理，阅读器通过对尾码的编号进行按位搜索，收到命令的标签尾码将自己的序号与阅读器发送的序号进行对比，如果小于等于阅读器发送的序号，则将自己的尾码序号发给阅读器，若继续发生碰撞，阅读器减小序号继续搜索；若没发生碰撞，阅读器成功识别一个标签尾码，对成功识别的标签尾码处理步骤和成功时隙一样， 直至碰撞时隙的所有标签处理完毕，进入下一个时隙，碰撞时隙处理流程如图3 所示。

图3 改进算法碰撞时隙处理流程

3.2 系统性能分析

3.2.1 帧时隙ALOHA 算法性能分析

在帧长为64 的一帧中，各时隙的概率如图4所示。

图4 各时隙概率图

系统效率为：

系统所需时隙数为：

对式（5）求导可得，当待识别标签n 与帧长N 近似相等时，系统获得最大吞吐率。 这意味着可以通过设置帧长来优化瞬时吞吐率［10］。

3.2.2 后退式二进制搜索算法性能分析

在BBS 算法中，假设待识别区域内有n 个标签，算法完成对n 个标签的搜索需要的次数为S（n），计算如下：

成功识别所有标签的系统效率为：

3.2.3 改进算法性能分析

整个标签的产品电子代码 （EPC 码） 为64位，传输识别整个标签需要1 时隙，文中取16 位的尾码，则传输识别标签尾码只需0.25 个时隙。

设待识别区域内的标签数量为n，帧长为N，尾码长为L_suffix，尾码重复出现的概率为：

计算可得， 当尾码长16 位、 标签数为100时，尾码重复出现的概率仅0.072 78%。 在本文中一个尾码传输并识别只需要花费0.25 个时隙，为了更直观地比较系统性能，在改进算法中由于重复识别而浪费的时间忽略不计。 而重复出现的尾码中为不同标签的概率更低，因此在文中重复出现的标签判定为已识别标签。

每次成功时隙识别一个标签，则碰撞时隙处理的标签数为：

其中，n_coll 为碰撞时隙处理的标签数，n_succ 为成功时隙处理的标签数。

碰撞时隙的标签用后退式二进制搜索算法进行处理， 处理所有碰撞时隙标签所需的时间为：

则改进算法所需要的时间成本为：

改进算法的系统效率为：

3.3 改进算法仿真结果分析

采用MATLAB 进行仿真实验， 标签数为500，标签EPC 码为64 位，每次传输识别一个标签需要1 个时隙。 DFSA 算法中初始帧长为256，用Schoute 估算法预估标签数量； 改进算法中采用固定帧时隙帧长为256，尾码为16 位，每次传输识别一个标签尾码需0.25 个时隙。

不同算法时间成本对比如图5 所示。

图5 不同算法时间成本对比

由图5 可以看出， 识别相同数量的标签，改进算法所需的时间成本比传统单一算法低很多。

不同算法系统效率对比如图6 所示。

图6 不同算法系统效率对比

由图6 可以看出， 识别相同数量的标签，动态帧时隙ALOHA 算法的系统效率仅为30%左右， 后退式二进制搜索算法的系统效率保持为50%左右， 而改进算法的系统效率最高可达60%，且一直保持在50%以上。

4 结束语

在分析帧时隙ALOHA 算法和后退式二进制搜索算法的基础上，将两类算法结合在单阅读器移动RFID 系统中使用。 改进算法吸取了帧时隙ALOHA 算法识别时间较短和后退式二进制搜索算法标签识别率高的优势，使用尾码应答机制减少时间成本。 通过对改进算法的仿真，单阅读器移动RFID 系统所花费的时间成本有所下降，而系统效率有一定提升。