rfid中基于动态二进制的改进树型搜索算法及其实现

《rfid中基于动态二进制的改进树型搜索算法及其实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RFID中基于动态二进制的改进树型搜索算法及其实现RFID中基于动态二进制的改进树型搜索算法及其实现　引言　　随着由物联网引领的第三次全球信息化产业浪潮的不断推进，RFID（射频识别）技术已成为制造全球化、贸易全球化和物流全球化的.L.核心推动力。无线射频识别技术（RadioFrequencyIdentification，RFID）是一种利用无线射频方式在阅读器和标签之间进行非接触双向数据传输，以达到目标识别和数据交换目的的技术[1]。由于其具有非接触识别、可识别高速运动物体、抗恶劣环境、保密性强、可同时识别

2、多个识别对象等优点，射频识别技术已成为当今自动识别数据收集行业发展最快的一种技术，目前其在交通管理、仓储管理和生产线自动化管理等诸多领域得到了越来越广泛的应用。　　在RFID系统中，当有多个电子标签进入一个或多个阅读器感应区域的时候，阅读器与多个电子标签的同时通信会使得无线通信信号互相干扰，以致阅读器无法接收到正确的信息，这种情况一般称之为冲突或碰撞等。为了避免冲突的影响，RFID系统定义了一系列当冲突发生时的操作，而基于这些操作的方法就是防冲突算法[2]。　　一、典型防冲突算法　　对于要求低复杂度、低功耗以

3、及低成本的RFID系统，最为通用的防冲突机制是时分多址复用（TDMA）。目前流行的两类标签防冲突算法，主要包括随机性算法中的纯ALOHA、时隙ALOHA、动态帧时隙ALOHA算法等，确定性算法中的二进制树型搜索算法、BBT算法、QT算法等[3]。随机性防冲突算法由于随机性大，当大量标签读取时，帧冲突严重，正确率难以达到100%。相比而言，确定性防冲突算法的识别精度和识别效率有较大提高，因此被广泛应用。本文主要研究和分析基于TDMA的确定性防冲突算法，但是目前的二进制算法由于存在较大的通信量和识别延时，因此有进

4、一步改进的空间，本文的动态二进制的改进树型搜索算法便是为此而改进设计的。　　二、确定性标签防冲突算法　　确定性标签防碰撞算法是以阅读器为主动控制器，进入射频场的所有标签同时由阅读器进行控制和检查。阅读器依据标签的ID号首先向标签发射不同的询问信号或指令，阅读器根据冲突的信号，按照二叉树深度优先搜索的思想，逐步缩小搜索范围，搜索符合条件的标签，直到找到规定的射频标签。该方法杜绝了随机性算法中的标签饿死的情况，具有100%的高识别率[4]。最典型的是二进制树型搜索算法，在此基础上，又出现了逐位比较的二进制树搜索算

5、法[5]（Bit-by-BitBinaryTreeAlgorithm，BBT），问询树算法[6]（QueryBinaryTreeAlgorithm，QT）等。　　1.二进制树型搜索算法　　二进制树型搜索算法中为了能辨认出阅读器中数据碰撞的比特位的准确位置，采用的是Manchester编码[1]，该编码约定逻辑1表示发送信号由1到0的转变即下降沿跳变，而逻辑0表示发送信号由0到1的转变即上升沿跳变。若无状态跳变，视为非法数据，作为错误被识别。当两个或多个标签同时返回的某一数位有不同的值，则接收到的上升沿和下降沿

6、相互抵消，以致出现没有变化的状态，阅读器由此可判断该位出现了碰撞。假设标签1和标签2的ID分别是0716051403021110和0706151413020110，利用曼彻斯特编码能按位识别出碰撞位的示意图如图1所示。由于标签1和2是同时传送其数据，利用曼彻斯特编码阅读器解码为07X6X514X302X110，于是阅读器检测出1th，3th，5th和6th出现碰撞。　　二进制树型搜索算法是由一个阅读器和多个电子标签之间规定的相互作用（命令和电子标签）顺序（规则）构成，根据电子标签的序列号大小，按从小到到大的顺

7、序依次将所有标签识别出来。　　2.BBT算法　　采用BTT算法的标签内部都设有一个指针，初始时指针指向标签识别码的最高比特位，所有标签处于休眠状态。在每一个查询轮次，阅读器首先激活所有未识别的标签，然后发送一个查询比特0，要求所有标签返回其序列号的最高位.L.。若标签指针指向的比特和阅读器查询比特相同，则发送它识别码的下一个比特，否则标签就进入休眠状态而不再参与接下去的查询。若阅读器检测到标签的响应没有冲突，则把接收的比特作为下一步的查询比特，否则，就用1作为下一步的查询比特。当某个标签的指针指向识别码的最低

8、位，则表明一张标签被识别，从而一轮识别过程结束。而其他标签被重新激活，指针被重置，新的一轮循环开始。　　3.QT算法　　QT算法中阅读器维持了一个前缀，阅读器用这个前缀来问询标签，记为q1q2qi,只有识别码的前缀与这个问询前缀相匹配的标签才响应并发送其识别码的剩余比特qi+1qjqend，其它不匹配的标签自动进入休眠状态，等待下一次查询命令。当只有一张标签响应时，阅读器成功识别标签。若有多张标签响