RFID中解决无线信道争用问题的防碰撞算法研究
3 查询树算法(QT)
“QT(Query Tree)查询树算法基于标签ID号来分裂一组发生碰撞的标签。”在每一轮传输中，读写器向标签发送一个比特串的查询信息。读写器的一系列查询比特串记录在队列Q中。初始化队列Q为两个1位比特比特串0和1，读写器从Q中取出一个比特串，用以查询信息。若此查询信息与某标签的序列号ID的前缀信息相同，则此标签响应读写器的命令，传输自己的ID给读写器。如果读写器发送的查询比特串X1X2 X3…Xt(Xi∈{0，1}，t小于标签序列号ID的长度)，有多个标签同时响应读写器的查询信息，即发生了碰撞，则在此查询比特串后面增加一位，将X1X2X3…Xt0和X1X2X3…Xt1压入队列Q中。读写器下次将分别用这两个比特串作为查询信息，前面发生碰撞的标签将分为两个部分。一部分将响应查询比特串X1X2X3…Xt0，另一部分将响应查询比特串X1X2X3…Xt1。依此方法不断地增加比特串位数，直至收到响应但没有碰撞情况发生或无响应的情况，这样读写器就能够识别出所有的标签。本文引用地址：http://www.eepw.com.cn/article/153511.htm
查询树算法用队列Q存储查询信息，标签不必存储序列号ID以外的无关信息，这样，标签就具有更简单的功能，可降低标签成本，因此，QT算法是无记忆的算法。图2所示是QT算法的一个示意图。系统中的标签ID号为0010、1110和1101。
4 改进型算法
4．1 改进型算法思想
读写器引入一个堆栈S来存储二又树发生碰撞时右子树节点信息，一个队列Q来存储无碰撞发生时的查询前缀。
设标签序列号ID是长为L的二进制数，读写器查询前缀是长度不大于L的二进制数。那么，读写器发送查询前缀，使其作用范围内标签将自己的序列号ID与查询前缀相比较。如果查询前缀与标签自最高位开始的部分比特串相同，则标签回复序列号ID剩余的部分比特串给读写器。初始时，二叉树只有根节点，读写器的堆栈为空，队列Q为空。
4．2 改进型算法流程
第一步，由读写器在初始时发送查询前缀(1位的二进制数“0”)，此时有以下几种情况：
(1)如果只有一个标签响应，即无碰撞发生，此时可为根节点添加左子节点(表示二进制数0)，将此查询前缀“0”送入队列Q，跳转到第四步。
(2)如果有多于一个的标签响应，即发生了碰撞，此时可为根节点添加左子节点(表示二进制数0)，并把0送入堆栈S；然后为节点0添加左子节点00和右子节点01。将01送入堆栈S，再跳转到第三步，以00为查询前缀。
(3)如果无标签响应，跳转到第二步。
第二步，读写器发送查询前缀(1位的二进制数“1”)，此时也有如下几种情况：
(1)若有标签响应且无碰撞发生，则为根节点添加右子节点(表示二进制数1)，将查询前缀“1”送入队列Q中，跳转到第四步。
(2)若有碰撞发生，则为根节点添加右子节点(表示二进制数1)，并把1送人堆栈S；然后为节点1添加左子节点10和右子节点11。将11送入堆栈S，以10为查询前缀。
(3)若无标签响应，说明读写器作用范围内无标签存在或者系统可能出现故障，识别流程结束。
第三步，读写器发送查询前缀。若收到响应且无碰撞发生，则将此查询前缀送入Q；若有碰撞发生，则分别添加左子树和右子树，右子树压入堆栈S，左子树作为新的查询前缀，重复步骤第三步；如无标签响应，则从堆栈S中弹出一个元素作为查询前缀，重复第三步。
第四步，当读写器成功识别某标签，先与读写器进行通信，然后使标签进入“无声”状态，即此标签不再响应读写器的查询。从堆栈S中弹出一个元素作为查询前缀，重复第三步，直至所有的标签被识别出来。
4．3 改进型算法实例
假设系统内有四个待识别的标签，其序列号ID分别为0010、0100、1010、1101。其首次识别过程如表1所列。
首先，读写器发送查询前缀0，标签0010和0100响应，发生碰撞，将0送入堆栈S；添加左子节电00和右子节点01，将01送入堆栈S，以00作为新的查询前缀。读写器发送查询前缀00，此时只有标签0010响应，将查询前缀00送入队列Q；此标签被成功识别，与读写器通信完毕后，进入“无声”状态。从堆栈S中弹出01，作为新的查询前缀，此时只有标签0100响应，将查询前缀01送入队列Q；此标签被成功识别。
然后再从堆栈S中弹出0，作为新的查询前缀，此时无标签响应，因此读写器以1为查询前缀。标签1010和1101响应，发生了碰撞，将1送入堆栈S；添加左子节点10和右子节点11，将11送入堆栈S，以10作为新的查询前缀。读写器发送查询前缀10，此时只有标签1010响应，将查询前缀10送入队列Q；此标签被成功识别。从堆栈S中弹出11，作为新的查询前缀，此时只有标签1101响应，将查询前缀11送入队列Q；此标签被成功识别。
评论