标签防冲撞算法设计

图2算法的防冲撞性能比较

由图2可知，当标签数量较少时，探测到一位碰撞几率不大，动态调整算法比后退式算法只有稍微优势，而当标签数量明显增多时，标签ID值比较接近，探测到一位碰撞的几率较大，M较大，动态调整算法效率明显优于后退式算法。而ISO/IEC18000-6B协议的类二进制搜索算法是随机产生0,1信号进行搜索，不能实现有效的有序性读取，仿真结果也表明其识别能力显著低于动态调整搜索法。可见，动态调整搜索法可被有效用于ISO/IEC18000-6B协议的标签冲突问题解决。

　　尤其当2 ^L 个标签第1次发送Request(1)识别指令只探测出L个碰撞位时，可知识别过程中将出现连续的1位碰撞，此时M=2 ^L /2=2 ^L-1 ,S(N)=2(2 ^L -2 ^L-1)-1=2 ^L -1,K=2 ^L/S(N)=1。对比后退式算法需要发送S(2 ^{L )}=2 ^L+1-1次查询指令，而系统吞吐率为K=0.5。动态调整算法在最优情况下，效率是后退式算法的倍数。同时，动态调整算法对指令长度进行了动态调整，可以有效地减小发送信息量提高发送速率。

　　2基于标签卡号连续性的防冲撞算法

　　对于如仓库的货物管理，每一批货物内标签卡号基本上是连续的，此时可用另一种防冲撞算法基于一位碰撞直接识别的轮询算法快速识别标签[4]。

　　2.1轮询算法

　　该算法保持发送指令和Manchester编码不变。(1)发送Request(1)，利用Manchester编码确定碰撞位的具体位置得到L个碰撞位；(2)将除最低碰撞位的L-1个碰撞位看作一个二进制数H，从0~2 ^L−1递增，得DATA；(3)每次发完Request(DATA)后，H自增1，得出新的DATA，即实现一个轮询过程。具体过程如表2所示。

　　表2轮询算法查询过程

　　对于表2的8个标签，用轮询算法只需发送5次查询指令，用动态调整搜索法要发送7次指令，而用后退式算法需发送15次。可见，对于卡号连续的情况，轮询算法能更有效地实现标签防冲撞。

　　2.2算法性能分析

　　对于卡号连续的N个标签，探测到L个碰撞位时，发送的查询指令次数为
　　S(N)=2 ^L-1+1

　　系统的有效服务率即吞吐率为
　　K=N/S(N)=N/(2 ^L-1+1)

　　可知查询次数S(N)只与碰撞位数L有关，而与标签总数无关，吞吐率K不仅与碰撞位数有关还与标签总数有关。特别地，令待识别的标签卡号从0开始，与1.3节介绍的动态调整算法的比较如表3所示。

　　表3算法比较

　　从表3可看出在最优情况下，轮询算法可使吞吐率K达到2，而动态调整搜索法的最优吞吐率K为1，后退式算法[3]的吞吐率K为0.5。可见，轮询算法具有很大的应用潜力。

　　根据式(4)可画出吞吐率K与标签数量N和碰撞位数L的关系曲线，如图3所示。

从图3可看出，标签数量较少，而碰撞位数却很大时，吞吐率较低，此时不适合用轮询算法。这种缺陷可称为Hamming悬崖(Hammingcliffs)，相邻整数的二进制编码可能具有较大的Hamming距离。例如2个标签卡号分别为01111和10000，碰撞位数为5，要轮询25-1+1=17次才读完这两标签，可见效率很低。从图3可看出只有标签数量较大时，吞吐率K受碰撞位数影响不大，能克服Hamming悬崖，此时K基本介于1～2之间，效果比动态调整搜索法最优吞吐率K=1要好。

　　对于卡号连续的标签，并不要求严格连续，只要大部分标签卡号满足一定的连续性就可有效使用轮询算法。另外，轮询算法只需使用一次Manchester编码识别碰撞位，则只需按照规则发送指令，能够大大降低系统设计的复杂性。

3结束语

　　本文针对RFID技术日益严重的标签冲撞问题，指出对一般冲突情况，可用动态调整搜索法进行防冲撞，并通过对比表明该算法能有效应用于ISO/IEC18000-6B相关协议的RFID系统中，而当具备一定先验知识，了解到待识别标签卡号满足一定连续性，且数量较大时，可用轮询算法进行有效的防冲撞处理。