一种改进的融合型RFID防碰撞算法研究

湖南科技大学信息与电气工程学院 郭 艳 唐志军 刘 权

1 引言

RFID技术主要是通过无线电通信，自动识别并读取相关射频信息，UHF(无源超高频)RFID系统自身的优点很多：成本小，扫描卡反应快，识别时间短，使用寿命长，重量轻，体积小，一般无磨损，不需要保养维护[1]。

目前很多国家都关注物联网RFID防碰撞技术，改进算法也层出不穷。从工程应用角度出发，防碰撞算法有很多，目前普遍使用得有以下三种：基于二进制树的确定型算法、基于Aloha的概率型算法和基于Aloha和二进制树的融合型算法[2]，本文主要分析和改进基于ALOHA和二叉树的融合型防碰撞算法的优缺点、性能稳定性及其适用条件。

2 改进算法基础

RFID防碰撞算法最常用TDMA（时频多址）方式，它简单、高效，按时间把所有通信容量分给多个用户，所以RFID系统防碰撞算法中使用最频繁[3]。

电子标签通过无线电识别后进行通信，同时确认读写器的读写或“睡眠”状态，整个识别过程中为了避免多目标识别产生碰撞形成了防碰撞算法[4]。

二叉树算法是根据估算的帧长进行分组，因为当大量标签同时出现时，采用锁位后退二叉树搜索算法[4]，当帧长相应增大，标签识别时间将明显缩短，并占用较少的存储空间；而实际应用时，标签中的寄存器所占位数都是8位[5]，采用具有唯一性的UID编码方式，按实物标签代码、序列号最高位进行分组，可以有效实现。

动态帧时隙算法中标签数据传送时，将多个时间段组成一个时隙，又将若干个时隙组合成一帧，帧的大小由RFID系统动态调整，读写器随机产生一个时隙并发送给标签，同时，标签内的时隙计数器会根据具体情况进行加1，直到时隙计数值与帧内时隙数相等时，标签开始发送数据信息，在此过程中有效避免了碰撞现象的发生。

3 BTDFSA算法分析

本文提出的改进算法，是在二叉树和动态帧时隙Aloha算法的基础上改进的融合型（BTDFSA）算法,思路是先确定估算帧长，再采用动态帧时隙Aloha区分空闲时隙和碰撞时隙，同时用二叉树算法按位识别标签信息，详细步骤为：

步骤1：在RFID系统查询范围内初始化帧长，用估算法预设标签数，采用二叉树算法根据某一实物标签代码、序列号最高位，即电子标签到读写器方向的数据传输采用曼彻斯特 (Machester) 编码方式实现估算帧长[5]，因其具有较强的编码检错能力，所以数据传输过程中容易找到标签碰撞位；

步骤2：发送问询命令，查询序列号前缀长度，并判定前缀后加0的标签是否响应，如果响应继续下一个操作步骤，否则判定前缀最后一位为1的标签是否响应，不响应标签则进入休眠状态；

步骤3：时隙位隙按位匹配，对标签进行动态帧时隙识别，发送问询命令，选择时隙，并按位查询,确认有无碰撞发生，有则开始下一步问询，无则进入步骤4；

步骤4：应答器时隙计数器加1，碰撞时隙计数器减1，进入下一轮问询；

步骤5：发送确认信息和循环指令，直至所有标签识别完成，即空闲时隙和碰撞时隙数均为0，再根据标签信息处理读写器，结束。

4 仿真分析

仿真实验得出以下结论：

（1）当标签数N为68时，获得吞吐率最大值0.693，标签数取其它值时也能使预测检验算法吞吐率稳定在0.36左右。

（2）解调RFID信号时，随着信噪比的降低，正确估计概率会有所下降，估计性能也逐渐变差， 跳周期的正确估计概率随信噪比的变化趋势明显增大。

（3）经对照分析，改进的融合型算法性能有所提升，可以有效解决RFID系统标签防碰撞问题。与其它三种算法（DFSA：动态帧时隙算法，GDFSA：分组动态帧时隙算法，FGDFSA：预测校验动态帧时隙Aloha算法）相比,改进的融合型算法(BTDFSA)的标签数据通信量比较高，如表1所示，通信复杂度比较低，如表2所示：

表1 四种算法的通信量比较值（bps）

表2 四种算法的通信复杂度比较值

5 结束语

UHF RFID系统实际应用射频卡时，成功识别实物多标签并解决其碰撞问题，是RFID系统的关键技术之一，也是物联网发展的核心环节。本文提出的改进型融合算法，识别标签的有效编码，利用二叉树算法对标签进行时隙按位匹配，在硬件方面比较容易实现。在后续工作中，将探寻如何进一步优化RFID系统标签防碰撞不确定型算法的性能。

[1]王倩.物联网+传统产业是如何被改造的[J].商学院,2015(12):50-52.

[2]周少珂,邓淼磊.ALOHA标签防碰撞算法综述[J].计算机工程与应用,2017,53(14):9-17.

[3]陈春明,冯玉田,付良成.RFID动态帧时隙防碰撞改进算法研究[J].电子技术应用,2013,39(1):86-92.

[4]He Y,Wang X.An ALOHA-based improved anti-collision algorithm for RFID systems[J].IEEE Wireless Communications,2013,20(5):152-158.

[5]Xu Y,Chen Y.An improved dynamic framed slotted ALOHA Anti-collision algorithm based on estimation method for RFID systems[C].Proceedings of the IEEE International Conference on RFID,2015.

[6]董昌.RFID阅读器的软件设计及防碰撞算法研究[D].浙江理工大学,2016.

[7]严利辉,史长琼,陈蓉等.基于奇偶分组的多周期RFID标签防碰撞算法[J].计算机工程,2016,42(2):312-315.

[8]袁开国,郝昱文,李争平等.RFID网络中基于Aloha防碰撞的标签数目的联合估计算法[J].北京邮电大学学报,2014,37(4):72-76.