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

一种新型RFID树形碰撞位识别防碰撞算法探究 　　摘要摘要：多标签防碰撞算法在射频识别系统应用中发挥着重要作用。目前比较有代表性的树形防碰撞算法都存在识别周期过长、空闲时隙、碰撞时隙过多的问题。针对上述问题，提出了一种根据碰撞位分布特征，调整碰撞节点分叉数的防碰撞算法。仿真及实验结果表明，该方法能减少空闲时隙和碰撞时隙数量，提高查询效率及时隙吞吐量，满足实际需求 关键词关键词：射频识别；防碰撞算法；碰撞位识别 DOIDOI：10.11907/rjdk.162854 中图分类号：TP312 文献标识码：A文章编号文章编号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（k1/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（k1/n，L） L=1L1 （6） 根据公式（6）可得总时隙期望为T0（n）=1+B∑∞l=0BlP（k1/n，L）（7） 同理可得碰撞时隙期望为 C0（n）=∑∞l=0BlP（k1/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时使用二叉树查询算法，m2时使用四叉树查询算法 如图2所示，以0000、0001、0010、00