简论确定性确定性标签防冲突改善算法要求

【摘 要】基于二进制树搜索方法的确定性标签防冲突算法和基于ALOHA算法的随机标签防冲突算法是解决RFID系统标签防冲突问题两种主要方法。针对确定性标签防冲突算法在标签数目较多及标签与阅读器之间通信数据量较大时，读取标签延时较长的缺点，本文提出了一种改进算法。通过仿真比较发现，新算法的效率明显提高。
【关键字】RFID；标签；防冲突；改进算法
在RFID系统中，解决标签防冲突问题主要有两种方法：确定性标签防冲突算法（基于二进制树搜索方法）和随机标签防冲突算法（基于ALOHA算法）。在RFID系统ISO/IEC的标准中，有三种确定性标签防冲突算法：在ISO 14443标准中，TYPE A使用的是二进制树搜索算法；在ISO 18000-3标准中，MODE2使用的是FTDMA（Frequency Time Division Multiple Access）算法[3]；在ISO 18000-6标准中，TYPE B使用的是二进制树搜索算法[4]。确定性标签防冲突算法在系统中标签数目较多时仍能够正确的辨识标签，但其也有自身不可避免的缺点，如在标签数目较多及标签与阅读器之间通信数据量较大时，读取标签延时较长。鉴于此，本文提出了一种改进的解决方案。

1.二进制树型搜索算法（BS）

二进制树型搜索算法（Binary Search，BS）是时分多路算法的一种，依其运算思想，每发生一次冲突，就进行一次分枝（即形成两个子集），按照这种方式递归下去，直至最下面的分枝只有一个信息包或无剩余信息包。若在某时隙发生冲突，所有的包都不再占用信道，直到冲突问题解决[5]。
二进制搜索算法的核心，是利用逐步减少发生冲突的位的方法来完成对标签的辨识[6]。该算法的前提条件是阅读器能够准确地找到发生冲突的位，因此，在二进制搜索算法中，标签返回的信号编码格式使用曼彻斯特编码。该编码是通过在每个信号比特中间引入跳变的方式来表示不同数值和同步信息：逻辑“0”代表一个负电平到正电平的跳变，而逻辑“1”则相反，“不发生变化”的这个状态在数据传输过程中是不允许存在的。所以，当标签返回信号被阅读器接收后，阅读器判断某个（某些）位发生相互冲突的判断条件，就是这些位信号的状态是否发生变化，若没发生变化，则此位发生了冲突。按照该思路，采用BS算法从N个标签中辨识出一个标签所需的迭代次数为：

2.改进型动态二进制算法

我们研究二进制搜索算法的特点后发现：算法的迭代次数以及每次迭代传输的数据量的大小决定确定性标签算法的性能。因此，本文提出一种改进的确定性标签防冲突算法—改进型动态二进制搜索算法（Improvement Dynamic Binary Search， IDBS）。当标签出现连续冲突位时，该算法可有效提高阅读器辨识标签速度，我们对其规定如下：
首先标签必须以曼彻斯作为返回信号的编码，同时其要具备有和二进制搜索算法相同的重要相关命令（“请求”、“选择”、“读/写”和“去选择”命令）。此改进型动态二进制搜索算法有以下两个主要改进：
一是若冲突位只有一个，由于二进制位具有互斥性，则发生冲突位时，阅读器能辨别出来两个标签而不需要再次发送请求信号。
二是发生连续位的冲突时，不单单将最高冲突位置“0”，而是将所有位都置为“0”，仅保留最低冲突位的值，并将该值作为第二次命令的参数。若此时只有最后位有冲突，则可以同时辨识出两个标签。阅读器将前一个请求命令的参数加1后作为下一个请求命令进行发送，如此重复下去，直至所有标签都被辨识出来。
我们检测设某种物品标签的最高两位仅代表其种类（如超市中的苹果），后八位则代表该物品的具体属性（如此类苹果的等），我们的目的就是要从这些类似的物品标签中辨识出每一个物品的特有属性，现以下表中的5个标签为例来说明IDBS算法的过程：
首先，阅读器发送请求命令，在此我们检测设其命令参数为“l”，接收到该命令的所有标签都响应阅读器，该阅读器能够接收到编码为“1010？？？001”的数据。依据曼彻斯特原理，阅读器在Bit5、Bit4和 Bit3位检测到标签的返回信号，并发现在在此3个位发生了冲突。但由于Bit5、Bit4均为高位，依据改进型动态二进制搜索算法，Bit5和Bit4两位的值将被置“0”，而高于Bit5的两个位，Bit7和Bit6位，其值分别为“1”和“0”。

3.算法的复杂度

从上表能看出，系统中发生1个冲突位时，系统中的标签数目为2，则阅读器发送的命令次数为：
（6）
同理，当n=2时，系统中的最大标签数目为4，阅读器需要发送命令的次数为：
（7）
经数学递推可知，当系统中最大标签数目为，也即出现n个连续的位

摘自：毕业论文的格式www.udooo.com

冲突时，使用改进型动态二进制搜索算法，阅读器辨识所有标签的重复次数
（8）
所以，辨识单个标签所需要的重复次数为
（9）
即使N很大时，平均只需要1次，就可以辨识一个标签，从理论上讲，该算法相比BS算法，能够减少重复次数，即使和BDBS算法相比较，也能减少一半的重复次数。

4.几种确定性标签防冲突算法的仿真比较

在此，我们不妨检测设一个标签ID长度为8bit，共需辨识个这样的标签，我们依次根据式（3）、（5）和（8），使用Matlab仿真BS、BDBS和IDBS的算法，各算法在不同标签数量下的重复次数比较结果如图所示（检测定n为发生冲突的位数，N为标签数量，S为算法重复次数）。
由图2可以清楚的看到，BS算法的迭代次数随着标签数目的增加急剧增长，而BDBS算法和IDBS算法先标签数目较小时的迭代量相差不大，但当标签数目增长时，差距也越来越明显。IDBS相比较其他算法，特别在标签数目越大的情况下，其性能优势越发明显。

5.结束语

本文提出一种能使重复次数减小的算法——改进型动态二进制树搜索算法（IDBS），这一算法效率比动态二进制成倍地提高，特别在标签数目较多的情况下。在实际生活中，阅读器会遇到需要辨识同批或同类物品，如超市或者大型仓库安装的管理阅读器，由于相同批次货物的辨识码总是大同小异，常规算法较难辨识和区分，而使用该算法来解决标签冲突问题的效果将较为明显。