RFID 系统防碰撞中的二进制矩阵搜索

1、引言 RFID 射频识别技术，是应用无线电波来自动识别单个商品的技术总称。随着自动识别技术的发展，无线射频识别（RFID）技术逐渐兴起，对供应链管理、物流、生产控制和零售等领域产生重要影响，并将成为未来自动识别技术的主流。RFID 技术是利用射频信号和空间耦合（电感或电磁耦合）传输特性自动识别目标物体的技术。RFID 系统一般由电子标签（应答器，Tag）和阅读器（读头，Reader）组成[1]。当阅读器的射频场作用范围内存在多个标签，并有两个或者两个以上的标签同时响应阅读器时将会产生冲突，称为碰撞。解决碰撞问题的算法称为反冲撞算法。 按照防碰撞算法中应答器的响应方式，防碰撞算法通常分为不确定算法和确定性算法两种。不确定性算法现在存在的有ALOHA 算法、分隙ALOHA 算法，信道的最佳利用率分别为18.4%、36.8%,但随着标签数量的扩大，性能将激剧恶化。确定性算法中应答器利用随机时间响应读写器的命令，是读写器根据应答器ID 的惟一性来选择标签进行通信。最简单的确定性算法是二进制树机制。Klaus Fikenzeller 的二进制树形搜索算法，从N 个标签中识别单个标签平均需要log2N 1次。由于ALOHA 算法不适宜大规模标签读取，所以实际应用中主要采用二进制树形搜索算法。该算法特点为：碰撞发生时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，实现标签的有序读取。但其发送指令长度比较固定，信道利用率不高，仍需进一步改善。而目前其它基于二进制树形搜索改进的算法，虽然可以动态调整发送指令的长度，但效率并没有提高，或者说提高不多。本文提出二进制矩阵搜索算法，不仅可以动态调整发送指令长度，提高阅读器的智能性，而且大大提高了算法的效率。 2、二进制矩阵搜索算法 2.1 算法机理 该算法保持后退式二进制树形搜索算法的后退机理：碰撞发生时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，实现标签的有序读取。但具有以下特点[2]： （1）指令长度动态调整，只发送位数高于或等于冲突位的指令位。 (2)基于一位冲突直接识别，当只探测到一位碰撞位时，可直接识别出 2个标签 ID 数据。如射频场内有两个标签10011000-ic/" title="10011000">10011000, 10011001-ic/" title="10011001">10011001，阅读器探测到的返回数据为1001100x-ic/" title="1001100x">1001100x，因为只有一位冲突位，所以阅读器可直接确定射频场存在2个标签10011000-ic/" title="10011000">10011000, 10011001-ic/" title="10011001">10011001。 2.2 算法步骤 (1)阅读器发送 Request(1)，区域内所有标签应答。 (2)检测是否有 1 位碰撞发生。当无碰撞或只有 1 位碰撞位时，直接识别标签。若有多位碰撞发生，将碰撞的最高位置 0，高于该位的数值位不变，低于该位的数值位忽略，得到下一次Request命令所需的 DATA 参数。Request(DATA,nvb1,m1,nvb2,m2,……,nvbn,mn)：满足nvb1位为m1，nvb2位为m2，…，nvbn位为mn，且前n位为DATA的标签应答，当识别出标签后，根据确知的 ID 值对标签逐个进行 Select激活，然后根据需要进行 Read-Write 操作，之后用 Quiet 指令使该标签进入静默状态屏蔽掉。 (3)识别标签后，从最后一个碰撞位开始向前推，每发送一次Request命令，就有一个碰撞位加1，当所有的碰撞位均为1时，返回(1)，具体算法实例如下。 2.3 算法实现假设 ID 值为8位，阅读器作用范围内有8个标签。开始时，阅读器对区域内标签处于未知状态，发送 Request(1)，令区域内所有标签应答，二进制矩阵搜索算法中矩阵的每一行代表一个标签，其中矩阵①、②的第一行代表阅读器接收到的数据。“-----”代表标签不响应，“~~~~~”代表标签处于静默状态。矩阵③、④、⑤、⑥显示的标签为根据3.1中特点（2）直接识别出的两个标签，每次查询出 ID 值后即对标签进行屏蔽。当第 6 次执行指令Request(1)时，其为全返回指令，而只有2个标签应答，可知所有标签查询完毕。具体实现过程如下： （1）阅读器发送Request(1),阅读器作用范围内所有标签应答，阅读器接收到的数据为X011X0X,第2，6，8位数据发生碰撞。 （2）令第2位数据为0，发送Request(10,2,0),第2位为0且前两位为10的标签应答。阅读器接收到的数据为10011X0X,第6，8位数据发生碰撞。 （3）令第6位数据为0，发送Request(100110,2,0,6,0),第2，6位为0，且前6位为100110的标签应答，阅读器接收的数据为1001100x-ic/" title="1001100x">1001100x，根据2.1中特点（2）直接识别出的两个标签，即矩阵③中的两个标签。 （4）识别出两个标签后，返回Request命令中最后一个碰撞位，并且最后一个碰撞位加1，即第6位加1，阅读器发送Request(100111,2,0,6,1),第2位为0，第6位为1，且前6位为100111的标签响应。阅读器接收的数据为1001110X，根据2.1中特点（2）直接识别出的两个标签，即矩阵④中的两个标签。 （5）识别出两个标签后继续返回上一个碰撞位，使上一个碰撞位加1，即第2位加1，阅读器发送Request(110111,2,1,6,1),即第2位为1，第6位也为1，前6位为110111的标签响应，阅读器接收的数据为1101110X，根据2.1中特点（2）直接识别出的两个标签，即矩阵⑤中的两个标签。 （6）此时，所有的碰撞位均为1，所以进行下一个循环，发送Request(1),阅读器作用范围内所有非静默标签应答，阅读器收到的数据为1101100X，只有一个碰撞位，所以根据2.1中特点 （2）直接识别出的两个标签，即矩阵⑥中的两个标签。3 、算法比较 后退式二进制树形搜索算法分辨N 个标签共需要S(N)  (2N 1)个Request命令时隙[3]。跳跃式动态树形反碰撞算法分辨N 个标签也需要S(N)  (2N 1)个Request命令时隙[4]；类二进制搜索法分辨N 个标签需要的Request命令时隙数为S(N)  N * n（n为标签位数）[5]；由于动态调整二进制搜索法是基于后退式算法，因此在最不理想的情况下，也可保持N 个标签的查询次数为2N 1。当射频场中碰撞的标签数量N 较大，此时识别出1位碰撞的几率较大。设在整个识别过程中探测到n 次只有1个碰撞位，通过动态调整二进制树形搜索法的直接识别相当于比后退式算法减少2 n次查询指令，此时查询次数为]。 由于二进制矩阵搜索法每次查询时都是在最后一个碰撞位处直接加1，然后再进行查询，如图2中，调用Request(100110，2，0，6，0)后接下来调用Request(100111，2，0，6，1)，而不是直接按动态调整搜索法那样直接调用Request(10，2，0)，所以二进制矩阵搜索法的查询次数比动态调整搜索法少N /8，即为。因此该算法比后退式二进制树形搜索算法、跳跃式动态树形反碰撞算法，动态调整二进制树形搜索法，跳跃式类二进制搜索法的效率都有所提高。