一种RFID系统中基于自适应混合查询树的标签防碰撞方法

摘要

本发明涉及一种RFID系统中基于自适应混合查询树的标签防碰撞方法，该方法首先建立对电子标签Tag的电子产品码EPC进行二进制向三进制的转换方法，给出构造三叉查询树进行标签识别的方法，根据EPC码的长度取值，构造混合查询树方法来解决二叉树与三叉树并存的问题，最后针对标签的可移动性，设置加入与离开机制，得到自适应的混合查询树的标签防碰撞方法。本发明的优点在于使用三叉树方法在基于树型结构的标签防碰撞方法中具有最优化的性能，解决了EPC码不能完全三进制转换的问题，克服了由于标签移动造成的识别困难，可以很好的降低识别时延，减少碰撞及空闲过程，适用于存在大规模可移动标签的射频识别场景。

主权项

一种RFID系统中的基于自适应混合查询树的标签防碰撞方法，其特征在于步骤如下：步骤1：将阅读器接收范围内的电子标签Tag的电子产品码EPC码进行二进制EPC₂向三进制EPC₃的转换，构造查询树；所述二进制EPC₂向三进制EPC₃的转换是：在二进制EPC₂码向三进制EPC₃码转换时，只转换EPC₂码起始长度为3的整数倍部分，其余部分依然作二进制处理，转换公式为：x_i×2²+x_i+1×2¹+x_i+3×2⁰＝y_j×3¹+y_j+1×3⁰；其中x对应二进制EPC₂码，y对应三进制EPC₃码，i＝{1,4,9...3k+1},k∈{1,2,...L/3‑1}，j＝{1,3,5...2t+1},t∈{1,2,...l/2‑1}，L为EPC₂码的长度，l为EPC₃码的长度，两者之间的关系必须满足l/2＝L/3；当转换前EPC₂码的长度为3的整数倍，则利用转换后的EPC₃码，构造三叉查询树，执行步骤2；当转换前EPC₂码的长度不为3的整数倍，将前面属于3的整数倍部分转换为EPC₃码，利用转换后的EPC₃码和剩余EPC₂码，构造混合查询树，执行步骤3；步骤2基于三叉查询树的标签防碰撞过程：阅读器拥有的查询请求队列Q，依次向标签发送查询请求，根据标签响应情况来识别相应的标签，并进行标签防碰撞过程的自适应调节：当只有唯一一个标签响应查询请求时，阅读器直接识别标签，将相应查询请求对列送入标签可识别过程的队列yQ₁中；当有多个标签同时响应查询请求时，阅读器不直接识别标签产生碰撞，将相应查询请求对列送入标签碰撞过程的队列yQ₂中，并在原请求序列中分别附加{0,1,2}，作为新的查询请求放入Q中；当若没有标签响应时，将查询请求对列放入空闲过程的队列yQ₃中；重复步骤2，直至队列Q为空本步骤结束，标签识别完毕；步骤3：基于混合查询树的标签防碰撞过程，EPC₂码是3的整数倍部分依然采用三叉查询方法处理，根据剩余EPC₂码的剩余位数分为两种情况来处理，并进行标签防碰撞过程的自适应调节：当剩余1位二进制序列时，若只有1个标签响应，则直接识别，若有2个标签响应，则通过判别最后一位二进制是‘0’还是‘1’来进行识别；当剩余2位二进制序列时，则必须添加新的查询请求，在原请求后附加{0,1}，并用二叉查询树方法处理；在上述标签防碰撞过程中，对于RFID系统中标签的移动，设置相应的加入与离开机制，来自适应调节标签的防碰撞过程，具体机制如下：加入机制：当有标签加入时，利用空闲过程来识别新加入的标签，其中又可分为可识别和碰撞两种情况，如果发生碰撞采用混合查询树方法进行处理；离开机制：当有标签移出阅读器读取范围后，根据树型结构中空闲节点的数目，分为以下几种情况处理：（a）当有三个孩子节点时，其中一个为可识别，另两个为空闲，则父亲节点为可识别，可清除所有对孩子节点的查询；（b）当有三个孩子节点时，其中三个为空闲，则父亲节点为空闲，可清除所有对孩子节点的查询，并再次判断其父亲节点的兄弟节点的情况；（c）当有两个孩子节点时，其中一个为可识别，另一个为空闲，则父亲节点为可识别，可清除所有对孩子节点的查询；（d）当有两个孩子节点时，其中两个为空闲，则父亲节点为空闲，可清除所有对孩子节点的查询，并再次判断其父亲节点的兄弟节点的情况。