二进制树搜索算法.ppt

二进制树搜索算法的实现步骤如下： （1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 二进制树搜索算法的实现步骤如下： （1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。 二进制树搜索算法的实现步骤如下： （1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行响应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。 （3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。 二进制树搜索算法的实现步骤如下： （1）读写器广播发送最大序列号查询条件Q，其作用范围内的标签在同一时刻传输他们的序列号至读写器。 （2）读写器对收到的标签进行相应，如果出现不一致的现象（即有的序列号位为0，有的序列号该位为1），则可判断有碰撞。 （3）确定有碰撞后，把有不一致位的数最高位置0再输出查询条件Q，依次排除序列号大于Q的标签。 （4）识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对读写器发送的查询命令不进行响应。 （5）重复步骤1 ，选出序列号倒数第二的标签。 （6）多次循环完后完成所有标签的识别。 算法性能分析： 为了从N个标签中找出唯一一个标签，需要进行多次请求，其平均次数L为： L=log2N+1 则基本二进制树算法识别N个标签所需的总查询次数为：SUM(N)=N·(log2N+1） 查询次数是一个关于N和L的增函数，要识别一个标签，请求次数L随着N值的增大而迅速增加。并且标签每次响应阅读器的请求命令时所传的ID都是完整ID。 作业： 在RFID数据传输的工作方式有哪三种？ 什么是多路存取的工作方式？ 现有的RFID防碰撞都基于哪种算法？ 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工作原理 001 1 0 000 01 00 何为“二进制树”？ 1 0 1 1 0 0 0 0 1 1 1 0 ?? ?? ?? 射频卡1 射频卡2 读写器译码 曼彻斯特码(Mancherster)可在多卡同时响应时，译出错误码字，可以按位识别出碰撞。这样可以根据碰撞的位置，按一定法则重新搜索射频卡。 如何确定碰撞的准确比特位置？ 范例： ABCDRRR表示阅读器 范例： ABCDRRR表示阅读器 101??1?1 范例： ABCDRRR表示阅读器 R101??1?1 搜寻标签过程 ACRR送REQUEST命令，标签A和C应答。解码数据为1010?111,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。? R表示阅读器 R范例： ACRR 送REQUEST命令，只