RFID中解决无线信道争用问题的防碰撞算法研究

查询树算法用队列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；此标签被成功识别。
最后从标签中弹出1，作为新的查询前缀，无标签响应，结束识别流程。
如上所述，通过表1中所列的首轮识别后，队列Q中的查询前缀为[00，01，10，11]。当读写器再次需要识别其作用范围内的标签时，就可直接发送队列Q中的查询前缀，这样，标签能够被快速地识别出来。

5 各种算法的Matlab仿真
下面采用Matlab下仿真系统通信量的方法来比较各个算法的效率。在识别相同标签属的前提下占用的比特数越高，则说明其通信量越大，对系统要求越高。

图3和图4均是在标签长度L=8的情况下所进行的仿真结果，其中图3在识别100个标签时，二进制搜索算法通信量约为7 500 b，动态二进制搜索算法通信量约为4 300 b；图4则在识别100个标签时，查询树算法在通信量约为1 3 600 b，改进型算法通信量约为2 100 b情况下的仿真结果。
依据在标签长度为8 b时所仿真出的图3和图4所示的通信量数据，可以采用相同的仿真方法较容易地得出各种防碰撞方法在不同标签长度下的通信量数据，综合总结如表2所列。