RFID防碰撞算法分析与研究
来源：业务发展部 作者： 人气： 日期：2017-04-30
RFID防碰撞算法分析与研究（转载）分类：技术应用关键词：RFID； 防碰撞；Aloha算法；二进制树算法；前言无线射频识别技术 RFID (Radio Frequency Identification)是利用射频信号和空间耦合(电感或电磁耦合)传输特性自动识别目标物体的技术，RFID系统一般由电子标签和阅读器组成。阅读器负责发送广播并接收标签的标识信息；标签收到广播命令后将自身标识信息发送给阅读器。然而由于阅读器与所有标签共用一个无线信道，当阅读器识别区域内存在两个或者两个以上的标签在同一时刻向阅读器发送标识信息时，将产生碰撞，致使阅读器不能对一些标签进行识别处理；解决此碰撞的方法称为防碰撞算法。RFID防碰撞问题与计算机网络冲突问题类似。但是，由于RFID系统中的一些限制，使得传统网络中的很多标准的防碰撞技术都不适于或很难在RFID系统中应用。这些限制因素主要有：标签不具有检测冲突的功能而且标签间不能相互通信，因此冲突判决需要由阅读器来实现；标签的存储容量和计算能力有限，就要求防冲突协议尽量简单和系统开销较小，以降低其成本。RFID系统通信带宽有限，因此需要防碰撞算法尽量减少读写器和标签间传送的信息比特的数目。因此，如何在不提高RFID系统成本的前提下，提出一种快速高效的防冲突算法，以提高RFID系统的防碰撞能力同时识别多个标签的需求，从而将RFID技术大规模的应用于各行各业，是当前RFID技术亟待解决的技术难题。现有的标签防冲突算法可以分为基于ALOHA机制算法和基于二进制树机制的算法。本文将对这两类算法进行详细研究。并针对如何降低识别冲突标签时延和减少防碰撞次数方面进行改进，在二进制树算法的基础上，结合二进制搜索算法的特点，提出了一种改进的二进制防碰撞算法思想。1 RFID系统中防碰撞算法1.1 Aloha算法Aloha算法是一种随机接入方法，其基本思想是采取标签先发言的方式，当标签进入读写器的识别区域内就自动向读写器发送其自身的ID号，在标签发送数据的过程中,若有其他标签也在发送数据,那么发生信号重叠导致完全冲突或部分冲突，读写器检测接收到的信号有无冲突，一旦发生冲突，读写器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。Aloha算法模型图如图1-1所示。图1-1 Aloha算法模型纯Aloha算法虽然算法简单，易于实现，但是存在一个严重的问题就是读写器对同一个标签，如果连续多次发生冲突，这将导致读写器出现错误判断认为这个标签不在自己的作用范围。同时还存在另外一个问题其冲突概率很大，假设其数据帧为F，则冲突周期为2F。针对以上问题有人提出了多种方案来改善Aloha算法在RFID系统其可行性和识别率，Vogt. H提出了一种改进的算法是Slotted Aloha算法，该算法在Aloha算法的基础上把时间分成多个离散时隙，每个时隙长度T等于标签的数据帧长度，标签只能在每个时隙的分界处才能发送数据。这种算法避免了原来Aloha算法中的部分冲突,使冲突期减少一半，提高了信道的利用率。但是这种方法需要同步时钟，对标签要求较高，标签应有计算时隙的能力。2二进制树算法二进制树防冲突算法[3,4]的基本思想是将处于冲突的标签分成左右两个子集0和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分成00和01两个子集，依次类推，直到识别出子集0中的所有标签，再按此步骤查询子集1。图2 二进制树算法模型二进制搜索算法，是以一个的独特的序列号来识别标签为基础。其基本原理如下：读写器每次查询发送的一个比特前缀p0p1^pi，只有与这个查询前缀相符的标签才响应读写器的命令，当只有一个标签响应，读写器成功识别标签，当有多个标签响应就发生冲突，下一次循环中读写器把查询前缀增加一个比特0或1，读写器中设有一个队列Q来补充前缀，这个队列Q用0和1来初始化，读写器从Q中查询前缀并在每次循环中发送此前缀，当前缀p0p1^pi是一个冲突前缀,读写器就把查询前缀设为p0p1^pi，把前缀p0p1^pi放入队列Q，读写器继续这个操作直到队列Q为空，通过不断增加和减少查询前缀,读写器能识别其阅读区域内的所有标签。二进制搜索树算法的实现步骤如下：1.读写器广播发送最大序列号查询前缀Q让其作用范围内的标签响应，同一时刻传输它们的序列号至读写器。2.读写器对比标签响应的序列号的相同位数上的数，如果出现不一致的现象(即有的序列号该位为0,而有的序列号该位为1)，则出可判断有碰撞。确定有碰撞后，把有不一致位的数最高位置0再输出查询前缀Q，依次排除序列号大于Q的标签。3.识别出序列号最小的标签后，对其进行数据操作，然后使其进入“无声”状态，则对读写器发送的查询命令不进行响应。4.重复步骤1，选出序列号倒数第二的标签。5.多次循环完后完成所有标签的识别。假设有4个标签其序列号分别为10110010、10100011、10110011、11100011，其二进制搜索算法实现流程如表1所示：表1二进制树搜索算法实现查询前缀Q 第一次查询11111111 第二次查询10111111 第三次查询10101111标签响应 1X1X001X 101X001X 10100011标签A 10110010 10110010 标签B 10100011 10100011 10100011标签C 10110011 10110011 标签D 11100011 为减少标签发送数据所需的时间和所消耗的功率，有人提出了改进的二进制树搜索算法，其改进思路是把数据分成两部分，阅读器和标签双方各自传送其中一部分数据,可把传输的数据量减小一半，达到缩短传送时间的目的。根据二进制搜索算法的思路进行改良，当标签ID与查询前缀相符时，标签只发送其余的比特位，可以减少每次传送的位数，也可缩短传送的时间,从而缩短防碰撞执行时间。表2说明了动态二进制数搜索算法的实现过程。表2 动态二进制树搜索算法的实现过程查询前缀Q 第一次查询11111111 第二次查询0111111 第三次查询01111标签响应 1X1X001X X001X 00011标签A 10110010 10110010 标签B 10100011 10100011 10100011标签C 10110011 10110011 标签D 11100011 3 改进的RFID防碰撞算法本文提出一种改进的二进制树形RFID防碰撞算法是按位来识别标签为基础，通过阅读器来判断标签是否发生冲突。该算法思想描述如下：（1）本算法利用深度优先搜索原则来减少识别冲突标签时间，同时为减少在读写器与标签传输的信息冗余量，提高信道利用率；向读写器发送查询命令中新增冲突位C，用来标识标签的冲突位置；在开始新一轮查询时，从此冲突位置进行查询，而非从最高位开始。（2）我们约定阅读器中有个专门构建和处理二进制树图的智能函数。本算法的性能取决于标签的序列号ID的位数和读写器作用区域内的标签的数量。假设读写器作用区域内有n个标签，每个标签的ID号的位数为ｍ位。那么对于本算法来讲，识别一个标签的所需的查询次数是固定的：Ｎ1= m；则平均识别k个标签所需时间T为：T = k × m× t (t为读写器发送查询命令到标签返回１bit数据所需的时间)为了评价算法的性能，进行了仿真实验。设计仿真环境为：根据深度优先搜索思想，利用随机数产生函数生成具有64比特的ID号标签，对比使用本文提出的算法以及二进制树的所需时钟周期数。结果如图3-1所示。图3-1 时延与标签个数关系图从图中分析看出，在阅读器区域内相同数目冲突标签，采用改进的防碰撞算法，比采用二进制数算法所需的时钟周期数要少，即防碰撞过程中查询次数较少，而且区域内标签数目越多，该算法的性能优势越明显。4 总结防碰撞算法是当前RFID领域研究的热点和难点之一，本文详细研究了被业界推崇的基于Aloha算法和二进制搜索算法，这两类算法有各自的优缺点，如Aloha算法简单易实现，但存在错误判决问题，识别时间较长，信道利用率最大才为36%；二进制树搜索算法避免了错误判决问题，识别率较高，但时延长，标签的泄露信息较多，安全性差。本文提出一种改进的RFID防碰撞算法，该算法能快速、有效的识别多个标签，并且其识别时延得到大幅降低；这对于RFID技术的广泛应用具有重要的现实应用价值。
最新资讯
更多
河南省标准化和质量研究院公众号