标签防冲撞算法设计

1、标签防冲撞算法设计射频识别(RFID)技术是近几年发展起来的一种自动识别技术。RFID系统一般通过阅读器识别带有唯一电子产品代码(ID)值的标签。阅读器射频场范围内标签数量较多时不同标签返回数据发生重叠，导致阅读器对接收信号解码错误，可以将其称为标签冲撞。由于TDMA时分多址方式应用简单，容易实现大量标签数据读写，因此被多数防冲撞算法采用。现有防冲撞算法主要包括ALOHA算法和树分叉算法两种。当大量标签并存时，ALOHA算法1的帧冲撞严重，易引起性能急剧恶化，不适宜大规模标签读取。所以，主要发展树分叉算法。目前树分叉算法主要有ISO/IEC18000-6B的类二进制搜索算法2、后退式二进制树形

2、搜索算法3。本文设计了一种标签防冲撞算法。1基于标签卡号无序性的防冲撞算法对于如公路收费亭的车辆识别，标签的卡号是无序的(相互间不关联)，此时用动态调整二进制树形搜索法，能快速实现标签数据读写。该算法用Manchester编码准确判别位碰撞，并保持后退式二进制树算法的后退机理。1.1Manchester编码与防冲撞该编码采用以下规则：(1)逻辑“1”表示下降沿跳变。(2)逻辑“0”表示上升沿跳变。(3)若无状态跳变，作为错误被识别。当多个标签同时返回的数位有不同之值时，上升和下降沿互相抵消，以至无状态跳变，阅读器知该位出现碰撞，产生了错误。 利用Manchester编码识别碰撞位，如图1所示。

3、假如有两个标签，其ID号为10011111和10111011，利用Manchester可识别出D5和D2位碰撞。(a)标签1的ID为10011111(b)标签2的ID为10111011(c)阅读接收的ID碰撞为101111在表1中，“xx”表示碰撞位；“-”表示标签不响应；“”表示标签已被屏蔽为静默状态。每次查询出ID值后即对标签进行屏蔽。当第7次执行指令为Request(1)全返回指令，而只有2个标签应答，可知所有标签查询完毕。此时可据确知的8个标签ID值，按需进行其他操作。从表1可知用动态调整搜索法识别8个标签只需发送7次指令，而后退式算法3需要28-1=15次。可见动态调整搜索法的工作效

4、率有了很大改进。1.4算法性能分析由于动态调整搜索法是基于后退式算法3，因此在最不理想的情况下，也可保持N个标签的查询次数为S(N)=2N-1 。当射频场中碰撞的标签数量N较大，此时识别出1位碰撞的几率较大。设在整个识别过程中探测到M次只有1个碰撞位，通过动态调整算法的直接识别相当于比后退式算法减少了2M次查询指令，此时查询次数为 S(N)=2(N-M)-1系统的有效服务率即吞吐率为 K=N/S(N)=N/(2N-2M-1)将动态调整搜索法与类二进制搜索法2，后退式算法3在ISO/IEC18000-6B协议2的应用中进行查询次数的比较。为保持与协议规范一致，将使用协议相关功能指令GROUP_S

5、ELECT_EQ,READ/WRITE,DATA_READ2分别取代第1.2节的指令Request,Read-Write,Quiet同时用FM0编码2取代Manchester码。假设标签ID长度为16，用Matlab编程可得到仿真结果的比较如图2所示。图2算法的防冲撞性能比较 由图2可知，当标签数量较少时，探测到一位碰撞几率不大，动态调整算法比后退式算法只有稍微优势，而当标签数量明显增多时，标签ID值比较接近，探测到一位碰撞的几率较大，M较大，动态调整算法效率明显优于后退式算法。而ISO/IEC18000-6B协议的类二进制搜索算法是随机产生0,1信号进行搜索，不能实现有效的有序性读取，仿真结

6、果也表明其识别能力显著低于动态调整搜索法。可见，动态调整搜索法可被有效用于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基于标签卡号连

7、续性的防冲撞算法对于如仓库的货物管理，每一批货物内标签卡号基本上是连续的，此时可用另一种防冲撞算法基于一位碰撞直接识别的轮询算法快速识别标签4。2.1轮询算法该算法保持发送指令和Manchester编码不变。(1)发送Request(1)，利用Manchester编码确定碰撞位的具体位置得到L个碰撞位；(2)将除最低碰撞位的L-1个碰撞位看作一个二进制数H，从02 L1递增，得DATA；(3)每次发完Request(DATA)后，H自增1，得出新的DATA，即实现一个轮询过程。具体过程如表2所示。表2轮询算法查询过程对于表2的8个标签，用轮询算法只需发送5次查询指令，用动态调整搜索法要发送7次

8、指令，而用后退式算法需发送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。可见，轮询算法具

9、有很大的应用潜力。根据式(4)可画出吞吐率K与标签数量N和碰撞位数L的关系曲线，如图3所示。从图3可看出，标签数量较少，而碰撞位数却很大时，吞吐率较低，此时不适合用轮询算法。这种缺陷可称为Hamming悬崖(Hammingcliffs)，相邻整数的二进制编码可能具有较大的Hamming距离。例如2个标签卡号分别为01111和10000，碰撞位数为5，要轮询25-1+1=17次才读完这两标签，可见效率很低。从图3可看出只有标签数量较大时，吞吐率K受碰撞位数影响不大，能克服Hamming悬崖，此时K基本介于12之间，效果比动态调整搜索法最优吞吐率K=1要好。对于卡号连续的标签，并不要求严格连续，只要大部分标签卡号满足一定的连续性就可有效使用轮询算法。另外，轮询算法只需使用一次Manchester编码识别碰撞位，则只需按照规则发送指令，能够大大降低系统设计的复杂性。3结