标签防冲撞算法设计

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

1 基于标签卡号无序性的防冲撞算法

　　对于如公路收费亭的车辆识别，标签的卡号是无序的(相互间不关联)，此时用动态调整二进制树形搜索法，能快速实现标签数据读写。该算法用Manchester编码准确判别位碰撞，并保持后退式二进制树算法的后退机理。

　　1.1 Manchester编码与防冲撞

　　该编码采用以下规则：

　　(1)逻辑“1”表示下降沿跳变。
　　(2)逻辑“0”表示上升沿跳变。
　　(3)若无状态跳变，作为错误被识别。
　　当多个标签同时返回的数位有不同之值时，上升和下降沿互相抵消，以至无状态跳变，阅读器知该位出现碰撞，产生了错误。
      利用Manchester编码识别碰撞位，如图1所示。假如有两个标签，其ID号为10011111和10111011，利用Manchester可识别出D5和D2位碰撞。
　　(a)标签1的ID为10011111
　　(b)标签2的ID为10111011
　　(c)阅读接收的ID碰撞为10×11×11

　　1.2 防碰撞指令规则

　　(1)Request(DATA)，请求指令。DATA长度小于或等于标签ID长度。ID值与DATA匹配的标签回送其ID值给阅读器。如Request(10)表示ID开始两位为10的所有标签应答。并规定发送Request(1)后射频场内所有非“静默”状态下的标签都应答。

　　(2)Select(ID)，选择指令。与Select携带ID值相同的标签被激活，该ID值与标签ID值长度相同。

　　(3)Read-Write，读写指令。读写被Select激活的标签。

　　(4)Quiet(DATA)，静默指令。对匹配标签进行静默操作，使其不对阅读器任何指令作出反应。当标签离开阅读器的作用范围(等于没有供应能量)后复位。

　　1.3 动态调整二进制树形搜索法

　　1.3.1 算法机理

　　该算法保持后退式二进制树形搜索算法[3]的后退机理：

　　碰撞发生时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，实现标签的有序读取。但具有以下2个特点：
　　(1)指令长度动态调整，只发送位数高于或等于冲突位的指令位。

　　(2)基于一位冲突直接识别，当只探测到一位碰撞位时，可直接识别出2个标签ID数据。如射频场内有两个标签10101101, 10100101，阅读器探测到的返回数据为1010x101，因为只有一位冲突位，所以阅读器可直接确定射频场存在2个标签10101101, 10100101。

　　1.3.2 算法步骤

　　(1)阅读器发送Request(1)，区域内所有标签应答。

　　(2)检测是否有1位碰撞发生。当无碰撞或只有1位碰撞位时，直接识别标签。若有多位碰撞发生，将碰撞的最高位置0，高于该位的数值位不变，低于该位的数值位忽略，得到下一次Request命令所需的DATA参数。重复步骤(2)直到识别出两个标签。

　　(3)识别标签后，根据确知的ID值对标签逐个进行Select激活，然后根据需要进行Read-Write操作，之后用Quiet指令使该标签进入静默状态屏蔽掉。并判断刚才发送指令是否为Request(1)，若为Request(1)则发送结束。否则，下一次Request命令的DATA参数，采用后退策略，由其相邻的上次发送指令确定，继续步骤(2)。

　　1.3.3 算法实现

　　假设ID值为8位，阅读器作用范围内有8个标签。开始时，阅读器对区域内标签处于未知状态，发送Request(1)，令区域内所有标签应答，具体的查询过程如表1所示。

　　表1 动态调整搜索法标签查询过程

　　在表1中，“xx”表示碰撞位；“------”表示标签不响应；“^^^^”表示标签已被屏蔽为静默状态。每次查询出ID值后即对标签进行屏蔽。当第7次执行指令为Request(1)全返回指令，而只有2个标签应答，可知所有标签查询完毕。此时可据确知的8个标签ID值，按需进行其他操作。从表1可知用动态调整搜索法识别8个标签只需发送7次指令，而后退式算法[3]需要2×8-1=15次。可见动态调整搜索法的工作效率有了很大改进。

　　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/IEC 18000-6B协议[2]的应用中进行查询次数的比较。为保持与协议规范一致，将使用协议相关功能指令GROUP_SELECT_EQ, READ/WRITE, DATA_READ [2] 分别取代第1.2节的指令Request, Read-Write, Quiet同时用FM0编码[2]取代Manchester码。假设标签ID长度为16，用Matlab编程可得到仿真结果的比较如图2所示。

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

　　由图2可知，当标签数量较少时，探测到一位碰撞几率不大，动态调整算法比后退式算法只有稍微优势，而当标签数量明显增多时，标签ID值比较接近，探测到一位碰撞的几率较大，M较大，动态调整算法效率明显优于后退式算法。而ISO/IEC 18000-6B协议的类二进制搜索算法是随机产生0,1信号进行搜索，不能实现有效的有序性读取，仿真结果也表明其识别能力显著低于动态调整搜索法。可见，动态调整搜索法可被有效用于ISO/IEC 18000-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悬崖(Hamming cliffs)，相邻整数的二进制编码可能具有较大的Hamming距离。例如2个标签卡号分别为01111和10000，碰撞位数为5，要轮询25-1+1=17次才读完这两标签，可见效率很低。从图3可看出只有标签数量较大时，吞吐率K受碰撞位数影响不大，能克服Hamming悬崖，此时K基本介于1～2之间，效果比动态调整搜索法最优吞吐率K=1要好。

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

3 结束语

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

　　(文/华南理工大学电子与信息学院，谢振华，赖声礼，陈 鹏)