进制树搜索算法.ppt

课程回顾,RFID技术 RFID组成 RFID工作原理,在RFID系统，因为多个读写器和多个标签造成的读写器之间和标签之间的互相干扰，统称为碰撞。,1.读写器碰撞 2.标签碰撞,防碰撞算法,2.2 RFID技术 RFID工作原理,现有的基于TDMA防冲突算法可以分为基于ALOHA的算法和基于二进制树两种类型。,2.2 RFID技术 RFID工作原理,Binary-Tree(二进制树)算法简介,纯ALOHA防冲突算法,分时隙的ALOHA防冲突算法（S-ALOHA）,Dynamic Binary-Tree 算法,标签防碰撞方法,在算法执行过程中，读写器要多次发送命令给电子标签，每次命令都把标签分成两组，多次分组后最终得到唯一的一个标签。在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。,Binary-Tree(二进制树)算法,2.2 RFID技术 RFID工作原理,何为“二进制树”？,曼彻斯特码(Mancherster)可在多卡同时响应时，译出错误码字，可以按位识别出碰撞。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。,如何确定碰撞的准确比特位置？,二进制树搜索算法的实现步骤如下：,（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。,范例：,A:10100111,B:10110101,C:10101111,D:10111101,R:11111111,R:11111111,R表示阅读器,二进制树搜索算法的实现步骤如下：,（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。,范例：,A:10100111,B:10110101,C:10101111,D:10111101,R:11111111,R:11111111,R表示阅读器,101?1?1,二进制树搜索算法的实现步骤如下：,（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。 （3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。,范例：,A:10100111,B:10110101,C:10101111,D:10111101,R:11111111,R:11111111,R表示阅读器,R:10101111,101?1?1,搜寻标签过程,A:10100111,C:10101111,R:10101111,R:10101111,送REQUEST（10101111）命令，标签A和C应答。解码数据为1010?111,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得10100111,?,R表示阅读器,R:10100111,范例：,A:10100111,C:10101111,R:10100111,R:10100111,送REQUEST（10100111）命令，只有标签A应答。没有发生碰撞，阅读器对标签A进行阅读操作。,R表示阅读器,可以识别A,B:10110101,D:10111101,二进制树搜索算法的实现步骤如下：,（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行相应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。 （3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。 （4）识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对读写器发送的查询命令不进行响应。 （5）重复步骤1 ，选出序列号倒数第二的标签。 （6）多次循环完后完成所有标签的识别。,Improved Anti-collision Algorithm搜寻过程,10100111,10110101,10101111,10111101,11111111,101?1?1,10101111,10100111,10101111,1010?111,10100111,10100111,识别TagA,10110101,10101111,10111101,11111111,101?1?1,10101111,10101111,识别TagC,Improved Anti-collision Algorithm搜寻过程,10110101,10111101,11111111,1011?101,10110101,10110101,10111101,10111101,识别TagB,识别TagD,二进制搜索算法的工作流程是：,算法性能分析：,为了从N个标签中找出唯一一个标签，需要进行多次请求，其平均次数L为： L=log2N+1 则基本二进制树算法识别N个标签所需的总查询次数为：SUM(N)=N(log2N+1） 查询次数是一个关于N和L的增函数，要识别一个标签，请求次数L随着N值的增大而迅速增加。并且标签每次响应阅读器的请求命令时所传的ID都是完整ID。,19,Dynamic Binary-Tree 算法,在Basic Binary-Tree算法中，标签每次回送给阅读器的序列号必须是全序列号。然而标签的序列号并不只是由单字节构成，而是根据实际需要可能长达 10 多个字节。对于这种长序列号的标签，假如每次都完整的传输其 ID 值，需要传输的数据量很大，再加上阅读器也是以同样长度的 ID 值作为参数互相传递，则会花费很长的时间，造成识别延迟，降低系统效率。 为减少标签和阅读器之间传输的数据量，提高阅读器的识别效率，在Basic Binary-Tree算法的基础上，提出了一种改进的防碰撞算法，称其为Dynamic Binary-Tree 算法。,2.2 RFID技术 RFID工作原理,现有的基于TDMA防冲突算法可以分为基于ALOHA的算法和基于二进制树两种类型。,2.2 RFID技术 RFID工作原理,Binary-Tree(二进制树)算法简介,纯ALOHA防冲突算法,分时隙的ALOHA防冲突算法（S-ALOHA）,Dynamic Binary-Tree 算法,标签防碰撞方法