标签防冲撞算法设计

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

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

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

　　1.1Manchester编码与防冲撞

　　该编码采用以下规则：

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