基于RFID防碰撞算法综述摘要：无线射频识别(Radio Frequency Identification, RFID)技术作为当下最重要的科技之一， 以其广泛的应用性将有越来越大的发展前景，RFID技术也由 于其非接触的特性，遇到了多目标识别过程中的信息碰撞问 题现对Aloha类防碰撞算法、二进制树防碰撞算法以及改 进算法进行分析关键词：RFID；防碰撞算法；Aloha；二进制树 RFID系统在识别过程中会有一个普遍的问题，那就是对 象冲突，当在同一时间内有若干个电子标签同时请求识别 是，阅读器不能正确区别出来，这样当多个电子标签同时发 送数据的时候，就会出现数据的干扰导致数据传输失败，这 就是文章要研究的防碰撞问题为了解决这一问题，提高系 统的性能，需要制定有效的防碰撞算法，所以防碰撞算法是 RFID系统的研究核心现有的防碰撞算法包括：Aloha类防碰撞算法，又称为 随机性算法；二进制树防碰撞算法，又称为确定性算法；改 进算法，在原有的基础上设计出性能更优的算法1基于Aloha类防碰撞算法ALOHA (Additive Link On line Hawaii)算法算是出 现比较早的防碰撞算法，它是采取随机多址方式。
作为无线 通信协议，ALOHA算法研究取得成功后被广泛利用在理想 状态下，利用ALOHA类防碰撞算法，系统最高吞吐率是36. 8% 但是在实际应用中，由于各种因素的干扰，系统的识别效率 很难迗到理想的状态1. 1纯Aloha算法纯ALOHA算法也叫基本ALOHA算法，是一种比较容易的 时分多址算法当标签进入阅读器的工作范围内，标签获取 能量被激活，向阅读器发送储存在标签内部的数据信息在 这个过程中，假如有两个标签一同向阅读器发送信息，就会 产生信息冲突，造成完全碰撞；而当一个标签正在向阅读器 发送过程中，另一个标签开始信息传送，这种情况下就会出 现标签部分碰撞只有标签单独在一个时间内进行信息传输 时才能让阅读器正常识别，不会出现碰撞情况使用纯ALOHA 算法，系统最大吞吐率只有18. 4%,标签发生碰撞概率比能 够正确识别概率要大得多1.2时隙Aloha算法与帧时隙Aloha算法由于ALOHA算法中，标签发送数据时间是随机性的，导 致完全碰撞或者部分碰撞于是将纯ALOHA算法进行优化， 得到了时隙ALOHA算法这种算法是把时间划分成若干等长 时隙（每个时隙长度满足一个标签成功发送完数据），标签 通过不同时隙向阅读器发送数据，如此一来，就能避免部分 碰撞的产生，从而总体上缩减了产生碰撞的次数。
时隙Aloha.算法采用分割时隙思想，避免了标签的部分碰撞，只有成功 识别和完全碰撞情况，成倍地提高了信道利用率但要划分 时隙就要解决一个同步问题，在系统中要有同步时钟，使阅 读器作用范围内的所有标签达到时隙同步该算法的系统吞 吐率可迗到36.8%，比纯Aloha算法效果提高了 一倍尽管时隙ALOHA算法在信道利用率上比纯ALOHA算法得 到一定改进，可是标签发生碰撞的概率依然很大，发生碰撞 后的标签会随机接着发送数据，进而影响其他标签的读取， 为了避免这种情况，于是研究出了帧时隙ALOHA算法这种 方法是把多个时隙组成一个帧，在每一个帧内，标签任意选 择其中一个时隙发送数据，但只可以发送一次在某一个时 隙内，当标签发生了完全碰撞，将会处于休眠状态，等到下 一帧进行读取，这样不会影响本帧内其他标签的正常读取 算法中每一帧的时隙数都是固定的，并且时隙长会大于一个 标签成功发送完信息的时间这样，阅读器发送读取指令后， 假如一个时隙内仅有一个标签响应，则成功读取标签数据； 如果时隙内没有一个标签，就会掠过此时隙；如果存在许多 标签的话，产生了碰撞后自动等到下一帧的到来，再选择其 他时隙2基于二进制树防碰撞算法二进制树防碰撞算法通过电子标签具有唯一的二进制 编码来查询区别。
此算法工作原理是将产生了碰撞的电子标 签分为0、1两个子集，首先从子集0开始搜寻，要是没有 碰撞产生，说明成功识别如果产生了碰撞，就将碰撞的标 签再分成00与01两个子集，再从00子集开始搜寻，重复 执行操作0子集的标签完全成功识别后，转向1子集搜寻， 直至把全部标签都识别完，任务结束2.1二进制搜索算法与动态二进制搜索算法与ALOHA类算法不同的是，使用二进制搜索算法需要用 到标签自身的序列号和阅读器的查询指令号当标签序列号 与阅读器查询指令相同时，标签产生响应要是仅有一个标 签做出响应，那么成功识别如果存在若干个标签一同做出 响应，阅读器会根据碰撞位情况修正查询指令，经过不断修 正查询命令来识别出所有标签动态二进制搜索(DBS, Dynamic Binary Search)算法 是对二进制搜索算法进行优化的使用二进制搜索算法，整 个标签序列号需要多次被传输，并且阅读器发送的REQUEST 指令数据位也多，从而会造成查询时间增加，出错频率也跟 着提高动态二进制搜索算法能很好减少数据位冗余，但是 它的运行流程与二进制搜索算法基本相同，只是修改了 REQUEST 指令2.2锁位后退二进制搜索算法与跳跃式动态二进制搜算算法锁位后退二进制搜索算法也是在二进制搜索算法基础 上得到优化的，虽然动态二进制搜索算法能减少数据传输 量，但是并不能减少搜索次数。
锁位后退二进制搜索算法的 工作原理是当阅读器成功识别出一个标签后，阅读器不需要 重新发送REQUEST指令，而是直接根据上一层的锁位分组退 回到上一层，也就是返回根节点，这样显然会减少搜索次数跳跃式动态二进制搜索算法在动态二进制搜索算法和 锁位后退算法的基础上结合而成的，涵盖了两种算法的优 点，既减少了数据冗余位的发送，也减少了搜索次数，同时 缩短了查询时间，也提高了标签识别效率跳跃式搜索算法比二进制搜索以及锁位后退搜索需要 的查询次数少，比动态搜索算法数据传输量又少，整体性能 相对来说是最好3改进算法为了使识别效率更好，不少学者在原有的基础上，提出 了新的改进算法，有学者提出了优化帧内时隙长度的策略， 并通过马尔科夫建模实现对标签的读取周期数迖到减少的 目的同时，基于二进制树的防碰撞算法也有很多学者在研 究，并且在其基础上提出了不少改进算法，如改进的返回式 动态二进制算法、NTA算法、EMBT算法和二叉树搜算算法等， 相比之前的动态二进制搜算算法，在平均比特数上，实现了 大大的减少，提高了识别效率最近，有学者提出GDRA(geometric distribution reader anticollision)拓扑方案，利用筛选几何概率分布函数来实现阅读器碰撞问题最 小化，它能提供更高的吞吐量，符合EPC国际标准，在不需 要额外的硬件条件就可在真实的RFID系统中实现功能。
4结语相比之下，Aloha类算法操作简单，识别时间短，但稳 定性不足，系统利用率最高也只能迗到36. 8%,并且当标签 数量增加时，系统的识别效率将下降的很快二进制算法虽 然识别效率高，稳定性也较好，但是操作复杂，识别时间较 长改进算法在原有的基础上，实现新的突破，在准确度、 信道利用率、稳定性等方面寻求改善，是未来的研究方向之。