一种新型RFID树形碰撞位识别防碰撞算法研究

钱琨　潘洋　冉全

摘要摘要：多标签防碰撞算法在射频识别系统应用中发挥着重要作用。目前比较有代表性的树形防碰撞算法都存在识别周期过长、空闲时隙、碰撞时隙过多的问题。针对上述问题，提出了一种根据碰撞位分布特征，调整碰撞节点分叉数的防碰撞算法。仿真及实验结果表明，该方法能减少空闲时隙和碰撞时隙数量，提高查询效率及时隙吞吐量，满足实际需求。

关键词关键词：射频识别；防碰撞算法；碰撞位识别

DOIDOI：10.11907/rjdk.162854

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2017）005004403

0引言

射频识别（Radio frequency identification，RFID）是一种通过射频信號识别目标对象的非接触式自动识别技术，识别过程无需人为干预，在较为恶劣的条件（灰尘、水渍、油渍）下仍能正常工作[1]。最基本的RFID系统由阅读器和电子标签构成[2]。其中，电子标签是射频识别系统中储存物体信息的介质，各个电子标签内部都有唯一产品识别码来区分不同目标对象。

RFID系统应用时，由于阅读器只有一个共享信道，在有效范围内出现较多电子标签同时进行信息传输的情况下会产生通信碰撞[3]。为了阅读器能够正常读取信息，需要以某种方法令电子标签重复发送信息以避开碰撞[4]，这样就不可避免地产生了通信开销以及传输延时，影响系统效率[5]。

防碰撞算法一般分为两个类别：基于时隙分配的ALOHA算法[6]和基于二进制的树形查询算法。基于时隙分配的ALOHA算法是将时间离散化，使之变为若干时隙，当发生碰撞时，标签必须等待下一个时隙才能重新发送信息。其缺点显而易见：标签数量较多时碰撞概率会增加，有些情况下某些标签发生多次碰撞时可能长时间无法识别，出现所谓“标签饥饿”现象。基于二进制的树形查询算法根据深度优先思想，指定产生碰撞节点处查询的比特位数，将碰撞节点逐渐分裂为更小的碰撞子集，逐步缩小查询范围，最终达到识别所有标签的目的。

1典型树形查询算法

典型树形查询算法是将标签内存所携带的识别码ID与阅读器发送前缀查询进行比较、判断。首先阅读器发送查询指令，根据标签返回携带的识别码ID是否包含该前缀判断有无标签应答。若只有唯一标签应答，则将该前缀所代表的标签标记为已确认标签。若该前缀查询同时有多个标签应答，则进一步在原前缀后加入若干个比特位组成新的前缀。重复上述过程，直至最终实现所有标签都正确识别。图1是树形查询算法查询流程。

2新型碰撞位识别防碰撞算法（CBRA）

树形查询算法中，假设总时隙期望为T0（n），碰撞时隙期望为C0（n），空闲时隙期望为I0（n），系统内符合查询条件的标签数量有n个，由此可得：

T0（n）=C0（n）+I0（n）+n（1）

树形查询方法在L层分枝有标签的概率P=B-L，B为树的分叉数，L层中k个标签出现在同一时隙的概率为

P（k/n，L）=Cknpk（1-p）n-k（2）

根据公式（2）得出分枝状态分别为空闲时隙、确认时隙、碰撞时隙的概率：

P（0/n）=（1-p）n（3）

P（1/n，L）=n（1-p）n-1（4）

P（k>1/n，L）=1-（1-p）n-n（1-p）n-1（5）

设历遍到s层第i个分枝的概率为P（s/i，n），由于每次查询开始的概率P（s/i，n）=1，由此可得P（s/i，n）=1P（k>1/n，L） L=1L>1 （6）

根据公式（6）可得总时隙期望为T0（n）=1+B∑∞l=0BlP（k>1/n，L）（7）

同理可得碰撞时隙期望为

C0（n）=∑∞l=0BlP（k>1/n，L）=1B（T0（n）-1）（8）

代入式（1）则空闲时隙I0（n）为

I0（n）=B-1BT0（n）+1B-n（9）

当分叉数B=3时，总时隙T0（n）为最小值，标签识别效果最佳。树形查询结构依托于二进制，不能使用三叉树进行标签识别，因此本文对基于二进制的树形查询算法作适当改进，根据碰撞位信息判断混合使用叉树类型，而不是单一使用某种叉树，在减少碰撞时隙数量的同时避免产生大量空闲时隙，提高系统效率。

假设当前分枝符合查询条件的待识别标签为m个，任意位不发生碰撞概率为（12）m-1，则采用二叉树概率为

P（B=2）=[1-（12）m-1]（12）m-1（10）

采用四叉树概率为

P（B=4）=[1-（12）m-1]2（11）

当m=2时，二叉树以及四叉树采用的概率是相等的。即可将m=2作为临界条件，当m≤2时使用二叉树查询算法，m>2时使用四叉树查询算法。

如图2所示，以0000、0001、0010、0011、1100、1101、1110、1111八个标签为例，对比两种树形查询算法，可以发现二叉树查询算法查询深度较大而且碰撞时隙较多。四叉树查询算法虽然减少了查询深度和碰撞时隙，但会出现较多空闲时隙。

如图3所示，经过改进后的碰撞位识别防碰撞算法（Collision Bit Recognition Algorithm），根据碰撞位待识别标签数量合理使用二叉树或四叉树查询，避免空闲时隙的产生并能减少碰撞时隙和总时隙数量。

3仿真与实验结果分析

纯二叉树查询算法中，除叶节点度为0之外其余节点度均为2。假设其余节点数为m1，叶节点（待识别标签）数为m2，则总时隙数M=m1+m2。此外，根据二叉树性质可得总时隙数为各节点树之和加1，因此可得M=2m1+1，m1=m2-1。可得总时隙数和待识别数之间关系为：

M=2m2-1 （12）四叉树查询算法中，除叶节点树为0之外，其余节点树均为4。总时隙M=4m1+1，可得m2=3m1+1。将叶节点数按确认时隙和空闲时隙分别设为j1和j2，则j1+j2=3m1+1。由于存在两位连续碰撞位，因此一个碰撞时隙最多产生空闲时隙0～2个，产生2个空闲时隙时j2=2m1，可得m1=j1-1。则最大总时隙：Mmax=j1+j2+m1=2j1-3（13）当产生0个空闲时隙时，叶节点数与确认时隙数相等，即j1=3m1+1，m1=（j1-1）/3，则最小总时隙Mmin=j1+j2=（4j1-1）/3=（4m2-1）/3（14）将式（13）和（14）取均值可得：

=（5m2-5）/3（15）将式（12）与式（15）所得总时隙取均值可得碰撞位识别查询算法总时隙为：

=（11m2-8）/6（16）

通过Matlab将公式（12）、（15）、（16）进行仿真比较，得到3种算法总时隙对照图（见图4）。待识别标签数在0-500区间采样时，CBRA总时隙数始终少于纯二叉树和纯四叉树算法。

系统传输率为确认时隙与总时隙之比，待识别标签数即为确认时隙数，可得系统传输率β为：β=确认时隙确认时隙+碰撞时隙+空闲时隙=m2M（17）

同样，对比三者系统传输率，CBRA在系统传输率上也始终好于其它两种算法，如图5所示。

4结语

基于二进制的树形防碰撞算法无法达到在减少碰撞时隙的同时消除空闲时隙的目的。本文在分析二叉树、四叉树结构查询方法的基础上，吸收了两者的优点，形成一种根据当前分枝待识别标签数量，选择性地使用二叉树和四叉树进行标签查询的方法。根据仿真结果可知，该新型算法可以减少总时隙数量并提高系统传输率，具有一定的实际应用仿值。

参考文献参考文献：

[1]夏小勤，胡佳佳.基于动态树形RFID防碰撞算法的研究[J].科技广场，2014（3）：7984.

[2]江城，黄立波.基于二进制搜索的RFID标签防碰撞算法的研究[J].计算机与数字工程，2011（4）：2933.

[3]宋建华，郭亚军，韩兰胜，等.自调整混合树RFID多標签防碰撞算法[J].电子学报，2014（4）：685689.

[4]施卫东.一种改进的RFID防碰撞算法[J].科技通报，2015（4）：121123.

[5]吕敬祥，刘清，过继红.基于碰撞树的自适应多叉树RFID防碰撞算法[J].井冈山学院学报：自然科学版，2014（2）：3944.

[6]马琰，蔡丽霞，任晓娜.一种自适应帧长RFID标签防碰撞算法[J].计算机与现代化，2014（11）：113121.

责任编辑（责任编辑：杜能钢）