进制树搜索算法

《进制树搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程回顾RFID技术☆RFID组成RFID工作原理在RFID系统，因为多个读写器和多个标签造成的读写器之间和标签之间的互相干扰，统称为碰撞。什么是碰撞碰撞的类型1.读写器碰撞2.标签碰撞防碰撞算法2.2RFID技术RFID工作原理现有的基于TDMA防冲突算法可以分为基于ALOHA的算法和基于二进制树两种类型。2.2RFID技术RFID工作原理Binary-Tree(二进制树)算法简介纯ALOHA防冲突算法分时隙的ALOHA防冲突算法（S-ALOHA）DynamicBinary-Tree算法标签防碰撞方法☆在算

2、法执行过程中，读写器要多次发送命令给电子标签，每次命令都把标签分成两组，多次分组后最终得到唯一的一个标签。在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。Binary-Tree(二进制树)算法☆2.2RFID技术RFID工作原理001100000100何为“二进制树”？101100001110??????射频卡1射频卡2读写器译码曼彻斯特码(Mancherster)可在多卡同时响应时，译出错误码字，可以按位

3、识别出碰撞。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。如何确定碰撞的准确比特位置？二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示阅读器二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行响

4、应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示阅读器101??1?1二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。（3）确定有碰撞后，把有不一致位的

5、数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示阅读器R:10101111101??1?1搜寻标签过程A:10100111C:10101111R:10101111R:10101111送REQUEST（10101111）命令，标签A和C应答。解码数据为1010?111,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得10100111?R表示阅读器R:10100

6、111范例：A:10100111C:10101111R:10100111R:10100111送REQUEST（10100111）命令，只有标签A应答。没有发生碰撞，阅读器对标签A进行阅读操作。R表示阅读器可以识别AB:10110101D:10111101二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行相应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。（3）确定有碰撞后

7、，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。（4）识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对读写器发送的查询命令不进行响应。（5）重复步骤1，选出序列号倒数第二的标签。（6）多次循环完后完成所有标签的识别。ImprovedAnti-collisionAlgorithm搜寻过程第一次搜寻第二次搜寻第三次搜寻第四次搜寻第五次搜寻发送序号接收序号TagATagBTagCTagD101001111011010110101111101111011111111

8、1101??1?11010111110100111101011111010?1111010011110100111识别TagA10110101101011111011110111111111101??1?11010111110101111识别TagCImprovedAnti-collisionAlgorithm搜寻过程第六次搜寻第七次搜寻第八次搜寻第九次搜寻第十次搜寻发送序号接收序号TagATagB