基于标签序列号扩展分组的防碰撞算法

王博文

(中煤科工集团重庆研究院有限公司,重庆 400039)

0 引言

将射频识别(radio frequency identification,RFID)读写器置于多个标签构成的区域内时，读写器的线圈会产生磁场，使该区域的所有标签都开始向读写器发送标签的序列号(下文简称ID)等标签信息。当两个以上标签在同一时刻同时向读写器发送数据，就会产生通信冲突[1-2]。通信冲突在读写器端表现，为接收的帧错误，也称为标签通信碰撞。由于标签之间不能互相通信，并且标签不具备检测冲突的功能，所以冲突判断必须由读写器完成。

防碰撞算法能够将读写器覆盖区域的标签ID区分开来，使读写器能准确地识别标签。所以，防碰撞算法也是RFID标签识别研究的重点。现有的RFID防碰撞算法大致分为以下几类:美国夏威夷研究计划高等算术高级学习(advanced learning on higher arithmetic,ALOHA)算法、时隙ALOHA算法、动态时隙ALOHA算法、二进制树形搜索算法。总体来说，ALOHA算法是一种非确定的方法，由电子标签控制发送时间[3]。而二进制树形搜索算法由读写器来控制标签发送时间，是一种确定的方法。

1 现有的防碰撞算法

1.1 ALOHA算法

ALOHA算法有纯ALOHA算法和时隙ALOHA两种。纯ALOHA算法是通过标签随机发送ID信息至读写器，避免大概率的冲突，对具体的时隙没有要求。纯ALOHA算法标签信息冲突如图1所示。

图1 纯ALOHA算法标签信息冲突示意图

时隙ALOHA算法是让标签在读写器分配的时隙内随机发出ID信息至读写器。这种方式避免了纯ALOHA算法的部分碰撞问题[4]。时隙ALOHA算法标签信息冲突如图2所示。

图2 时隙ALOHA算法标签信息冲突示意图

1.2 基于曼彻斯特编码的二进制树形搜索算法

曼彻斯特编码如图3所示。

图3 曼彻斯特编码示意图

该算法主要基于曼彻斯特编码来识别标签ID信息的冲突位[4-5]。如果两个或者多个标签向读写器发送的比特位有不同值，则读写器接收到的多标签ID叠加信息码中上升沿和下降沿互相抵消。根据该编码规则，就将其判断为误码，从而识别出冲突的比特位。基于曼彻斯特编码的标签信息碰撞容错图如图4所示。

图4 基于曼彻斯特编码的标签信息碰撞容错图

二进制树形搜索法的基本思想是将冲突中的标签按照二叉树形状划分为若干个子集。由于每个冲突的位由0和1两个子集组成，所以通过遍历整个二叉树，就可以让读写器依次访问到每个标签[6]。

基于二叉树模型的标签冲突子集如图5所示。

图5 基于二叉树模型的标签冲突子集图

1.3 几种算法的评析

ALOHA算法原理是当标签的信息发生冲突时，读写器控制标签随机延迟一段时间再次发送标签ID，直到没有冲突为止。这种算法在标签数量较少时，具有较高的实用价值。但是标签数量过多会导致标签冲突频繁，时延划分过长会导致个别标签响应时间过长，使个别标签出现饥饿现象[7]。个别标签响应时间过长，会让读写器认为当前的标签已经读取，从而出现误判现象。

在二进制树形搜索算法中，读写器一次性只能读取一个标签ID。当标签ID过长时，通过树形遍历的方式过于繁琐。该算法和当前的标签进行信息交互后要立即发送静默指令使该标签进入休眠状态，直到重复上电(读写器重新激活标签区域的磁场)才能正常工作[8]。

基于以上原因，本文提出了基于标签序列号扩展分组的防碰撞算法。该算法的实现较为复杂，需要在读写器和标签两端同时实现匹配的功能。但是其可以处理多标签冲突问题，且一次处理可以读取多个标签。

2 基于标签序列号扩展分组的防碰撞算法

在二进制树形搜索算法的基础上，本文引入了一种基于标签序列号扩展分组的防碰撞协议。该防碰撞协议同样基于曼彻斯特编码原理，对读写器覆盖区域的标签ID所构成的集合按照冲突的(binary digit,BIT)(这里称为窗口大小)进行分组。通过分组再分组的递归方式，实现标签ID的准确识别[7]。

2.1 扩展分组的防碰撞算法举例

读写器读取到多个标签的信息之后，根据曼彻斯特编码原理检查冲突的BIT位。当冲突的标签ID信息BIT位确定之后，再根据冲突的BIT位来划分标签的子集[10]。在该算法中，读写器检测到标签序列号冲突后，依据冲突的BIT位按照一定的窗口大小(Wsize≥2)将标签ID划分为若干子集。然后，读写器会将包含了冲突BIT位的掩码发送给标签。标签收到后，按照位扩展3～8译码器的原理，将原始ID号连同冲突BIT位的转换码一起发送给读写器。

标签ID连续碰撞位算法举例如表1所示。

表1 标签ID连续碰撞位算法举例

读写器收到转换码后解析转换码，同时将窗口向右移动，再次将解析后的冲突BIT位连同下个窗口冲突的BIT位一起发送给标签；依次迭代，直到所有的冲突BIT位都被解析。至此，读写器所覆盖区域的标签ID号识别完成。

第三步，标签立即发送自身的ID+扩展码，标签序列号列表如表2所示。

表2 标签序列号列表

读写器将掩码+信息码发送到标签，目的是为了让标签接收到读写器下发的指令后，匹配掩码中对应信息码中比特位为1的ID位。匹配通过后，将ID发送至读写器；否则不发送。

扩展码的位数(窗口大小)根据标签的ID及标签的个数确定，窗口太大会导致扩展码的长度过长，影响通信效率、窗口太小就会导致频繁分组，造成信道利用率不高。

标签序列号转换码列表如表3所示。根据表3将转换码转变为原码，解析出标签冲突的前2位信息。

表3 标签序列号转换码列表

标签ID冲突原码与转换码的公式为:

L转换码= 2L原码，L原码≥2

(1)

D转换码= (1≪N原码)|D0

(2)

式中:N原码为原码值；D0为全零的转换码。

标签ID非连续碰撞位算法举例如表4所示。

表4 标签ID非连续碰撞位算法举例

2.2 扩展分组的防碰撞算法描述

①读写器置于标签所在的区域之后，立即发送索取标签ID命令111…111(长度位标签ID的比特位数)。标签收到相关命令后，立即发送自身的ID给读写器，读写器收到后检测冲突的BIT位。

②读写器从冲突位的高位开始取窗口的Lw的长度，发送Lw长度的掩码DM至标签端。其中，Lw≤Lx≤L原码。Dx冲突码中前Lw个冲突位x置1，其他BIT位全部置0,得到DM掩码。

举例:Dx(100XXX000XXX1000XXXX11111)、D原码(1001000000011000001111111)

当窗口大小Lw为3时:DM(0001110000001000000000000)。

当前读写器发送指令:DM1，后面的1标志当前为冲突位掩码。

③标签收到读写器发送的掩码后，立即发送自身的ID和扩展码至读写器，扩展码查表2得到。

④读写器收到标签发送的ID和扩展码之后，判断扩展码的冲突码D′X；D′X经过译码得到原码,从而判断Dx冲突码中前面Lw长度的码字集合A。

A=∑dn,n≤L转换码

集合A中包含了所有Lw长度的标签冲突码字，其中可能存在不同的标签发送了同一个码字dn。

⑤读写器将A中码字取出d0。因为d0是标签T0ID中的码字，所以将d0最后一个BIT位X3之前的码字取出，作为信息码HX发送至标签，以此检索标签T0。标签T0可能是一个集合，因为不同标签可能包含相同的头部HX。扩展分组的防碰撞算法流程如图6所示。

图6 扩展分组的防碰撞算法流程图

读写器发送指令DM0HX0…0。0表示当前为信息位掩码。DM中1的个数等于HX的长度，Hx后面补0补足ID长度。

⑥标签收到读写器在步骤⑤发送的指令后，立即反馈自己的ID给读写器，读写器检查是否再次冲突。如果没有冲突，直接到步骤⑧；如果再次冲突,读写器判断生成最新的冲突码序列，按照窗口大小取冲突码的头部，将冲突码的头部映射为相应的掩码，将掩码DM和Hx标签头码字发送至冲突的标签[9-11]。

读写器发送指令:DM1HX

⑦标签收到读写器在步骤⑥下发的指令后，立即反馈自身的ID和扩展码；读写器接收到扩展码后进一步解码得到冲突位的ID集合A′，重复⑤直到最后一个标签没有冲突时结束[12]。

⑨根据扩展码解析出标签的ID信息，并与当前的标签进行信息交换。回到步骤⑤，取出A中的元素进行下一步查询。

2.3 扩展分组防碰撞算法与现有算法的对比

扩展分组防碰撞算法是利用曼彻斯特编码对错误码的解析，通过读写器、标签两端的协议，让标签对冲突码进行一步步扩展，从而让读写器快速识别出多标签ID的方法。该方法与现有的二进制树形搜索算法相比，完成所有标签识别的指令交互，总次数得到了明显的压缩。指令交互次数对比如表5所示。

表5 指令交互次数对比

该算法通过增加指令编码的复杂度，扩展了标签的ID位数。当标签ID个数小于冲突位窗口大小时，仅用2次完成所有标签的识别。当标签的ID位数越长，该算法的效率越优，弥补了二进制树形搜索算法由于标签ID过长导致的指令交互次数过多、时延过长的问题。

3 结论

该算法通过将多个标签的冲突码按照一定的窗口大小进行解析。解析出来的冲突码作为分组的集合进行分组。对已经解析出来的冲突码作为查询条件进行标签ID的查询，直到检索的标签没有发生冲突为止。该算法需要在读写器和标签两端同时实现，协议复杂但一次查询可以识别出多个标签的ID，大大降低了读写器和标签之间的指令交互次数，节省了访问时间，具有较高的实用价值。