《二进制树搜索算法》由会员分享，可在线阅读，更多相关《二进制树搜索算法（23页珍藏版）》请在金锄头文库上搜索。
1、课程回顾课程回顾RFID技术RFID组成RFID工作原理在在RFID系统，因为多个读写器和多个标签造成的系统，因为多个读写器和多个标签造成的读写器之间和标签之间的互相干扰，统称为碰撞。读写器之间和标签之间的互相干扰，统称为碰撞。什么是碰撞什么是碰撞碰撞的类型碰撞的类型1.读写器碰撞读写器碰撞2.标签碰撞标签碰撞防碰撞算法 2.2 RFID技术RFID工作原理l现有的基于现有的基于TDMA防冲突算法可以分为防冲突算法可以分为基于基于ALOHA的算法和的算法和基于二进制树基于二进制树两种类型。两种类型。 2.2 RFID技术RFID工作原理Binary-Tree(二进制树二进制树)算法简介算法简介
2、纯纯ALOHA防冲突算法防冲突算法分时隙的分时隙的ALOHA防冲突算法（防冲突算法（S-ALOHA）Dynamic Binary-Tree 算法算法标签防碰撞方法在算法执行过程中，读写器要多次发送命令给电子标签，每次命令都把标签分成两组，多次分组后最终得到唯一的一个标签。在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。Binary-Tree(二进制树)算法 2.2 RFID技术RFID工作原理001100000100何为何为“二进制树二进制树”？101100001110?射频卡1射频卡2读写
3、器译码曼彻斯特码曼彻斯特码( (ManchersterMancherster) )可在多卡同时响应时，译出错误码字，可以按可在多卡同时响应时，译出错误码字，可以按位识别出碰撞。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。位识别出碰撞。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。如何确定碰撞的准确比特位置？如何确定碰撞的准确比特位置？二进制树搜索算法的实现步骤如下：二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。范例：范例：A:10100111B:10110101C:10101111D:10111101R
4、:11111111R:11111111R表示阅读器二进制树搜索算法的实现步骤如下：二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。范例：范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示阅读器101?1?1二进制树搜索算法的实现步骤如下：二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内
5、的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。（3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。范例：范例：A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111R表示阅读器R:10101111101?1?1搜寻标签过程A:10100111C:10101111R:10101111R:10101111送REQUEST（10101111）命令，标签A和C应答。解码数据为1010?11
6、1,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得10100111?R表示阅读器R:10100111范例：范例：A:10100111C:10101111R:10100111R:10100111 送REQUEST（10100111）命令，只有标签A应答。没有发生碰撞，阅读器对标签A进行阅读操作。R表示阅读器可以识别AB:10110101D:10111101二进制树搜索算法的实现步骤如下：二进制树搜索算法的实现步骤如下：（1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。（2）读写器对收到的标签进行相应，如果出现不一致的现象（即有的序列号位
7、为0，有的序列号该位为1），则可判断有碰撞。（3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。（4）识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对读写器发送的查询命令不进行响应。（5）重复步骤1 ，选出序列号倒数第二的标签。（6）多次循环完后完成所有标签的识别。Improved Anti-collision Algorithm搜寻过程搜寻过程第一次搜寻第二次搜寻第三次搜寻第四次搜寻第五次搜寻发送序号接收序号TagATagBTagCTagD1010011110110101101011111011110111111111101?
8、1?11010111110100111101011111010?1111010011110100111识别TagA10110101101011111011110111111111101?1?11010111110101111识别TagCImproved Anti-collision Algorithm搜寻过程搜寻过程第六次搜寻第七次搜寻第八次搜寻第九次搜寻第十次搜寻发送序号接收序号TagATagBTagC TagD1011010110111101111111111011?10110110101101101011011110110111101识别TagB识别TagD二进制搜索算法的工作流程是：出
9、现不一致的现象出现不一致的现象射频卡进入读写器的工作范围，读写器发出一个最大序列号让所射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们的序列号到读写器的接收有射频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。模块。读写器对比射频卡响应的序列号的相同位数上的数。读写器对比射频卡响应的序列号的相同位数上的数。即有的序列号该位即有的序列号该位为为0 0，而有的序列，而有的序列号该位为号该位为1 1把有不一致位的数从最高位到低位依次置把有不一致位的数从最高位到低位依次置O O再输出系列号，再输出系列号，即依次排除序列号大的数，至读写器对比射频卡响应的
10、序即依次排除序列号大的数，至读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。列号的相同位数上的数完全一致时，说明无碰撞。选出序列号最小的数后，对该标签进行数据交换，然后选出序列号最小的数后，对该标签进行数据交换，然后使该卡进入使该卡进入“无声无声”状态。状态。Y YN N算法性能分析：算法性能分析：l为了从N个标签中找出唯一一个标签，需要进行多次请求，其平均次数L为：lL=log2N+1l则基本二进制树算法识别N个标签所需的总查询次数为：SUM(N)=N(log2N+1）l查询次数是一个关于N和L的增函数，要识别一个标签，请求次数L随着N值的增大而迅速增加。并且标签每次响应
11、阅读器的请求命令时所传的ID都是完整ID。19Dynamic Binary-Tree 算法l在在Basic Binary-Tree算法中，标签每次回送给算法中，标签每次回送给阅读器的序列号必须是全序列号。然而标签的阅读器的序列号必须是全序列号。然而标签的序列号并不只是由单字节构成，而是根据实际序列号并不只是由单字节构成，而是根据实际需要可能长达需要可能长达 10 多个字节。对于这种长序列多个字节。对于这种长序列号的标签，假如每次都完整的传输其号的标签，假如每次都完整的传输其 ID 值，需值，需要传输的数据量很大，再加上阅读器也是以同要传输的数据量很大，再加上阅读器也是以同样长度的样长度的 ID
12、 值作为参数互相传递，则会花费很值作为参数互相传递，则会花费很长的时间，造成识别延迟，降低系统效率。长的时间，造成识别延迟，降低系统效率。l为减少标签和阅读器之间传输的数据量，提高为减少标签和阅读器之间传输的数据量，提高阅读器的识别效率，在阅读器的识别效率，在Basic Binary-Tree算法算法的基础上，提出了一种改进的防碰撞算法，称的基础上，提出了一种改进的防碰撞算法，称其为其为Dynamic Binary-Tree 算法。算法。 2.2 RFID技术RFID工作原理l现有的基于现有的基于TDMA防冲突算法可以分为防冲突算法可以分为基于基于ALOHA的算法和的算法和基于二进制树基于二进
13、制树两种类型。两种类型。 2.2 RFID技术RFID工作原理Binary-Tree(二进制树二进制树)算法简介算法简介纯纯ALOHA防冲突算法防冲突算法分时隙的分时隙的ALOHA防冲突算法（防冲突算法（S-ALOHA）Dynamic Binary-Tree 算法算法标签防碰撞方法21RFID碰撞的概念碰撞的概念防冲突算法分类防冲突算法分类详细描述详细描述ALOHA算法、基于帧的分时算法、基于帧的分时隙的隙的ALOHA算法、二进制树算法。算法、二进制树算法。重点掌握作业：作业：在在RFID数据传输的工作方式有哪三种？数据传输的工作方式有哪三种？什么是多路存取的工作方式？什么是多路存取的工作方式？现有的现有的RFID防碰撞都基于哪种算法？防碰撞都基于哪种算法？23THANKSTHANKS相关知识点及重难点下载相关知识点及重难点下载
