RFID防碰撞算法应用研究

高增貊，路 勇

（北京交通大学 电子信息工程学院，北京 100044）

射频识别技术（RFID, Radio Frequency Identification），又称无线射频识别，是一种基于应答器与读写器间无线通信的自动识别技术。RFID通过无线信号实现识别目标，读取目标数据和修改目标数据。射频识别系统主要包括两部分，读写器和应答器。

在单一读写器和多个应答器存在的系统下，很容易出现多个应答器同时响应读写器的情况，这会影响读写器的正常工作，所以选择适当的防碰撞算法对于应用RFID系统具有重大意义。

1 防碰撞经典算法

1.1 随机思想算法

1.1.1 帧时隙ALOHA（SFA）算法

时隙ALOHA算法[1]首先定义一个统一的帧长度，这个帧由若干个时隙组成，时隙的长度就是应答器接收到读写器广播信号后发送应答的时间。

当应答器首次接受到读写器的广播信号的时候，应答器会随机选择一个时隙，当到时间到此时隙时，应答器返回应答信息。此时的各个时隙内存在的应答器数量可分为3类，因此操作也分为3类。

（1）第1类是没有应答器，那么就直接到下一个时隙。

（2）第2类是有两个或以上应答器，此时多个应答器发送应答信号，那么读写器就不能够完成识别，因此也会继续下一个时隙。

（3）第3类是有一个应答器，此时读写器成功识别应答信息，之后会发送选择信号，对此应答器进行读写，完成后会进入下一个广播周期。

只有之前选择应答器被操作完后，其他在读写器范围内的应答器才能进行一个新的寻呼过程。

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

动态帧时隙ALOHA算法[1]是对帧时隙算法的改进，由于帧时隙算法的吞吐率不稳定，只有在时隙数和应答器数相等的情况下才能够有比较良好的表现，所以动态帧时隙ALOHA算法针对这种情况进行改进。

当每个时隙内都存在两个或者两个以上的应答器时，读写器此帧内没有读取到任何应答信息，所以下一次会调整每帧内时隙数量（1, 2, 8, …），即帧长度，直到唯一的应答器被识别。此种情况使得读写器产生帧的时隙数会随着应答器数量变化，因此使得效率一直保持比较好的状态。

1.1.3 动态随机数算法

动态随机算法[2]的原理和动态帧时隙ALOHA算法类似。每次的读写器寻呼都会发送一个Q值，每个应答器会在1～2(q-1)范围内随机选取一个计数。如果应答器的计数为0，则返回应答信息。读写器会对接收到的应答信息进行如图1所示。

图1 随机数Q值变化示意图

（1）如果有一个应答，则发送命令领每个应答器内计数都做减1处理，然后进入下一个接收周期。

（2）如果有多个应答，则增加Q值，并且从新分配应答器计数，然后进入下一个接收周期。

（3）如果没有应答，则减小Q值（保持大于0），并且从新分配应答器计数，然后进入下一个接收周期。

1.2 基于二分搜索的确定算法

1.2.1 二分搜索算法

二分搜索算法（Binary Search）[1]的整个寻呼机制不同于上述的所有随机方法。首先，二分搜索算法需要确定具体的碰撞的位置，如果用常规的0和1代替高低电平，即不归零码表示信号，那么当出现多个应答器碰撞的时候，接收的信息也能够读出，但是此时接收到的信号是多个应答器信号叠加结果，接收器接收到的信号是错误的，如图2所示。

图2 无基带编码导致接收错误

对于此问题的解决方法就是对信号进行编码，通常采用曼彻斯特码。曼彻斯特码的0和1表示如图3所示。

图3 曼彻斯特码

如果对于信号进行曼彻斯特编码，那么对于存在碰撞的情况就会很容易的检测出来，因为产生碰撞的地方会无法解码，具体情况如图4所示。

图4 采用曼彻斯特码检测碰撞位

对于二分搜索算法实现，首先应答器都有唯一的二进制序列作为自身的ID，之后读写器会用同样长度的发送序列以及如下指令配合进行筛选：

（1）REQUEST指令：发送一个二进制序列给应答器，如果应答器的数字序列小于读写器发送过来的序列，则应答器把自己的序列返回给读写器。

（2）SELECT指令：发送一个通过算法决定的序列给应答器，如果应答器的序列与发送过来的序列相等，此应答器被选中。

（3）READ指令：对选中的应答器内的数据进行操作。

（4）UNSELECT指令：取消之前被选择的应答器的被选择状态和使应答器灭活，此时应答器不会响应REQUEST指令。

每个周期，读写器首先发送REQUEST指令，一般发送同样长度的最大二进制序列，即全1序列。此时所有的应答器都会把自己的序列返回给读写器，根据译码，能够检测出碰撞位，根据最高碰撞位，改变下一次命令REQUEST发送的序列，改变规则是：首先，基序列是上一次的发送序列，把此序列的最高的碰撞位置定位为0，此序列的最高碰撞位之前的各位值和发生碰撞的应答器ID对应位保持一致，新的发送序列因此会变小，因此每次改变序列会减少选中的应答器，直到选中一个应答器完成一次识别。然后，识别出的应答器会被SELECT，READ和UNSELECT操作，因此之后这个应答器不会再响应REQUEST命令。重复此流程直到所有的应答器都被识别，整个流程如图5所示。

图5 二分搜索算法流程

1.2.2 动态二分搜索算法

动态二分搜索算法[1]是对上述的二分搜索算法的裁剪，区别在于读写器每次发送的REQUEST命令发送的二进制序列和应答器回复的二进制序列。此算法中，每次REQUEST发送的二进制序列是上一次碰撞最高位和其前面位的处理部分，而应答器返回的是上一次碰撞最高位之后后面的部分，这样能够大量减少冗余序列的发送。

2 算法仿真分析

本文对于上述的两个经典算法，动态帧时隙ALOHA和动态二分搜索算法，进行了MATLAB仿真，所得的结果主要是针对不同应答器个数的情况下，读写器的寻呼次数比较。

对二分搜索算法在不同长度序列下，同时识别1～100个应答器的模拟仿真，比较序列长度和寻呼次数是否存在关系，如图6所示。图中表明序列长度和寻呼性能在此数量应答器情况下无明显关系，但是按照二分搜索算法原理可知道序列长度决定了识别范围。假设初始的序列长度为L，那么二分搜索算法的防碰撞范围是1-2(L-1)。

图6 序列长度和寻呼次数

之后对于动态帧时隙ALOHA（DFSA）算法和动态二叉树搜索（DBS）算法进行了仿真比较，如图7所示。DFS算法初始帧时隙是24个，之后指数4会根据碰撞结果增加或减小；DBS初始的序列长度为8位。如图7所示，在应答器数目较少的情况下，DBS算法表现出了良好的搜索性能，随着应答器数量的增加，DFS的曲线追了上来，到100之后已经优于了DBS算法。当两个算法的复杂度是不一样的，由第二部分介绍原理时可以了解到，DBS的设计难度要高于DFS，因为DBS实现中需要添加曼彻斯特码的编码解码模块，而DFS只需要分配随机的时隙即可。因此在实际应用中，DFS会比较容易实现。

3 结束语

图7 动态帧时隙ALOHA算法和动态二叉树搜索算法进行了仿真比较

本文介绍了RFID经典的防碰撞算法，并对其中经典的动态帧时隙ALOHA算法和动态二分搜索算法进行了仿真分析，从寻呼次数的角度分析了两者在性能上的优缺点。可以看出，动态帧时隙ALOHA算法实现简单，寻呼次数和应答器个数存在稳定的线性关系；动态二分搜索算法需要编码解码帮助识别碰撞位。能够在应答器较少的情况下产生优秀的识别性能，但是性能会随着应答器数量的增加而恶化。

除了经典算法外，可以根据需要选择改进算法。对于随机类算法，都是基于动态帧时隙ALOHA算法的改进算法，可以从分组[3]，预估标签[4]等角度去改进；对于确定性的二分搜索算法可以通过编码方式变化[5]，记录碰撞位[6]操作等减弱动态二分搜索算法大量应答器情况下的恶化效果。

在RFID应用于各类产品的时候，防碰撞算法的选择不可避免，针对应用环境的不同，选择适应的防碰撞算法能够更有效地完成识别。

[1]Klaus Finkenzeller . RFID HANDBOOK FUNDAMENTALS AND APPLICATIONS IN CONTACTLESS SMART CARDS,RADIO FREQUENCY IDENTIFICATION AND NEARFIELD COMMUNICATION (3nd Edition)[M], John Wiley& Sons Ltd, 2010.

[2]刘 佳，张有光.基于时隙的RFID防碰撞算法分析[J].通信与网络，2007（5）：95-96.

[3]尹 君，何怡刚，李 兵，邓 晓，谭阳红，肖迎群.基于分组动态帧时隙的RFID防碰撞算法[J].计算机工程，2009，20（35）：267-269.

[4]陈春明，冯玉田，付良成. RFID动态帧时隙防冲突改进算法研究[J].电子技术应用，2013（1）：86-89.

[5]李世煜，冯全源，鲁 飞.基于BIBD(4,2,1)的防碰撞算法[J].计算机工程，2009，3（35）：279-281.

[6]王 雪，钱志鸿，胡正超，李奕男.基于二叉树的RFID防碰撞算法的研究[J].通信学报，2010，6（31）：49-57.