二进制树搜索算法ppt课件_第1页
二进制树搜索算法ppt课件_第2页
二进制树搜索算法ppt课件_第3页
二进制树搜索算法ppt课件_第4页
二进制树搜索算法ppt课件_第5页
已阅读5页,还剩18页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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、码曼彻斯特码曼彻斯特码(Mancherster)(Mancherster)可在多卡同时响应时,译出错可在多卡同时响应时,译出错误码字,可以按位识别出碰撞。这样可以根据碰撞的位置误码字,可以按位识别出碰撞。这样可以根据碰撞的位置,按一定法则重新搜索射频卡。,按一定法则重新搜索射频卡。如何确定碰撞的准确比特位置?如何确定碰撞的准确比特位置?二进制树搜索算法的实现步骤如下:二进制树搜索算法的实现步骤如下:(1读写器广播发送最大序列号查询条件Q,其作用范围内的标签在同一时刻传输他们的序列号至读写器。范例:范例:A:10100111B:10110101C:10101111D:10111101R:1111

4、1111R: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送REQUEST10101111命令,标签A和C应答。解码数据为1010?111,发生碰撞,算法做下如下,

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

7、碰撞。(3确定有碰撞后,把有不一致位的数最高位置0再输出查询条件Q,依次排除序列号大于Q的标签。(4识别出序列号最小的标签后,对其进行数据操作,然后使其进入“无声形状,则对读写器发送的查询命令不进行响应。(5重复步骤1 ,选出序列号倒数第二的标签。(6多次循环完后完成所有标签的识别。Improved Anti-collision Algorithm搜寻过程搜寻过程第一次搜寻第二次搜寻第三次搜寻第四次搜寻第五次搜寻发送序号接收序号TagATagBTagCTagD1010011110110101101011111011110111111111101?1?1101011111010011110101

8、1111010?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值的增大而迅速增加。并且标签每次响应阅读器的请求命令时所传的ID都是完整ID。19Dy

11、namic Binary-Tree 算法l在在Basic Binary-Tree算法中,标签每次回送给算法中,标签每次回送给阅读器的序列号必须是全序列号。然而标签的阅读器的序列号必须是全序列号。然而标签的序列号并不只是由单字节构成,而是根据实际序列号并不只是由单字节构成,而是根据实际需要可能长达需要可能长达 10 多个字节。对于这种长序列多个字节。对于这种长序列号的标签,假如每次都完整的传输其号的标签,假如每次都完整的传输其 ID 值,需值,需要传输的数据量很大,再加上阅读器也是以同要传输的数据量很大,再加上阅读器也是以同样长度的样长度的 ID 值作为参数互相传递,则会花费很值作为参数互相传递

12、,则会花费很长的时间,造成识别延迟,降低系统效率。长的时间,造成识别延迟,降低系统效率。l为减少标签和阅读器之间传输的数据量,提高为减少标签和阅读器之间传输的数据量,提高阅读器的识别效率,在阅读器的识别效率,在Basic Binary-Tree算法算法的基础上,提出了一种改进的防碰撞算法,称的基础上,提出了一种改进的防碰撞算法,称其为其为Dynamic Binary-Tree 算法。算法。 2.2 RFID技术RFID工作原理l现有的基于现有的基于TDMA防冲突算法可以分为基于防冲突算法可以分为基于ALOHA的算法和基于二进制树两种类型。的算法和基于二进制树两种类型。 2.2 RFID技术RFID工作原理Binary-Tree(二进制树二进制树)算法简介算法简介纯纯ALOHA防冲突算法防冲突算法分时隙的分时隙的AL

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论