基于RFID的防冲突算法

的防冲突算法陈涛武汉理工大学信息工程学院，武汉(430000)E-mail：[e-mail]摘要：在RFID系统中,如果有两个或两个以上的电子标签同时向读写器发送数据，则会出现通信冲突或数据相互干扰，若不能正确识别电子标签的数据包，系统就会产生错误。为解决多个标签同时与阅读器交换数据所引起的碰撞问题,必须采用一定的防碰撞算法,标签防碰撞技术是RFID系统中的关键技术。本文围绕RFID系统防碰撞算法展开研究。在简单介绍了RFID系统结构和工作流程的基础上对其中的关键技术之一--标签防碰撞算法进行重点讨论，概述了防冲突方案，在已有的ALOHA算法的基础上提出了一种改进算法，提高了标签的识别效率。性能分析表明,该算法比已有的二进制及动态二进制反碰撞算法具有更明显的优势。关键词：RFID；ALOHA；防冲突算法中图分类号：TP3021．引言RFID（RadioFrequencyIdentification），即射频识别，是20世纪90年代兴起的非接触式的自动识别技术，它通过射频信号自动识别目标对象并获取相关数据。RFID系统在货物跟踪和库存管理等物流供应链等方面发挥了越来越重要的作用，为物流供应链管理提供了最便捷有效的实施方案。其应用包括产品认证、质量控制、仓储管理、物流供应、偷盗检测以及自动结账等诸多方面，而且未来RFID市场的潜力仍不可估量。RFID技术中无人工干预和可复用两大特点体现了它巨大的潜力和应用前景。随着RFID标签价格的进一步降低，RFID技术将更具优势和吸引力。为了消除或减少RFID系统中的碰撞问题，许多研究人员进行了不懈的努力，提出了多种不同的防碰撞算法，新的算法还在不断涌现。综合而言，目前业界推崇的防碰撞方法主要有ALOHA法和二进制树形搜索法，这些算法各有优缺点。评价防碰撞算法优劣的指标有：防碰撞速度，准确率，信道利用率，稳定性，安全性和成本等[1]。本文在广泛阅读的基础上对防碰撞算法的研究现状进行了深入分析，对各类ALOHA算法的优劣进行了综合评价，并提出了改进算法的设想。2.ALOHA算法ALOHA算法由于其简单、易实现的特点被广泛应用在RFID系统中。ALOHA算法基于TDMA思想，是一种概率算法，属于电子标签控制算法.当电子标签进人读写器的作用范围内，就自动向阅读器发送自身的序列号，随即与阅读器开始通信.在一个电子标签向读写器发送信息的过程中，如果另外一个电子标签也在发送数据，就会产生信息碰撞.ALOHA算法分为纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法和动态帧时隙ALOHA算法[2]。2.1纯ALOHA算法即最初的ALOHA算法，是所有的多路存取方法中最简单的方法。这种算法没有检测机制也没有恢复机制，只是以一定的概率确保标签发出的数据帧无误地被阅读器接收。这种方法仅用于只读标签中。这类标签通常只有一些数据（序列号）传输给阅读器，并且是在一个周期性的循环中将这些数据发送给阅读器。数据传输时间只是重复时间的一小部分，以致在传输之间产生相当长的间歇。此外，各个标签的重复时间之间的差别微不足道。所以存在着一定的概率，两个标签可以在不同的时间段内设置它们的数据，使数据包不互相冲突。如果两个信号发生冲突，各站点只需等待一段随机时间后重试。纯ALOHA系统中，不仅在两个标签同时发送数据帧时会发生冲突，两个传输帧即使只有一点重叠也会发生冲突。无论整个帧都被破坏，还是只损坏帧的一小部分，数据都会被丢弃，常规的做法是重传整个帧。2.2时隙ALOHA算法（SA）时隙ALOHA将纯ALOHA算法中标签信息发送的时间离散化：（1）时间域被分为离散的时间间隔，即时隙（slots）；（2）标签发送信息的起始点不能任意，只能在一个时隙的起始处；（3）标签传送的信息要么不冲突，要么完全冲突；（4）标签信息的发送需要阅读器对其进行同步；（5）与纯算法相比，冲突的区间缩小了一半，信道利用率提高了一倍。与纯法相比，可能出现冲突的时间只有一半。假设数据包大小一样，因而传输时间t相同，并且两个标签在时间间隔T≦2τ内把数据包传输给阅读器，那么使用纯ALOHA法总会出现相互冲突。由于在使用时隙ALOHA法时数据包的传送总是在同步的时隙内才开始，所以发生冲突的时间区域缩短到T=τ，因此可得出对时隙法的吞吐率S为：()GSGe−=⋅由上式可知，交换的数据包量在G=1时，最大吞吐率S为36.8%。这一简单的改进，使信道利用率增加一倍。2.3帧时隙ALOHA算法在RFID系统中，帧时隙ALOHA算法的“帧”是由读写器定义的一段时间长度，其中包含若干时隙。时隙指标签收到读写器命令后，发送标识的时间长度。标签被随机分配到一个时隙中应答，当一个时隙中分配到多个标签时就产生碰撞。根据帧内时隙数是否发生变化分为固定帧时隙ALOHA算法和动态帧时隙ALOHA算法。2.3.1固定帧时隙ALOHA算法（FFSA）帧时隙ALOHA算法在时隙ALOHA算法基础上时间域进一步离散。具体操作如下：（1）将N个时隙打包成一个帧，帧大小固定，在整个标签识别过程中不改变帧的大小，每一帧的最大时隙数N需要预先设定，为某默认值；（2）阅读器把帧的大小和在帧中用来选择时隙的随机数发送给标签。每个标签通过利用这些随机号码来选择时隙号码，并且标签在每一个帧（即N个时隙）中只随机发送一次信息。2.3.2带延迟的帧时隙ALOHA算法带延迟的帧时隙ALOHA算法是固定帧时隙ALOHA算法的改进型算法。帧时隙ALOHA算法中，若帧时隙数远远小于标签数，在匹配前系统吞吐率很低。为了在时隙数与标签数匹配前，提高当前帧的吞吐率，引入了延迟机制，即当标签随机选择的时隙数与时隙计数器数值相同时，标签并不立即应答读写器，而是延迟若干时隙（从0—7的范围内选择）后再发出应答信息。2.3.3分组帧时隙ALOHA算法帧时隙ALOHA算法局限于每帧最大时隙数为256。当标签数远远大于256时，系统无法通过增大时隙数来提高吞吐率。为解决这个问题，在DFSA算法的基础上提出分组帧时隙ALOHA算法（GFSA）。参考文献中说明，当标签数多于354时将全部标签分成两组或者更多组，读写器分别对每组标签进行识别，从而可以很好地提高系统的吞吐率。图2.14为普通DFSA算法与分组GFSA算法在标签数多于400时识别所用的总时隙数的比较，初始时隙设为256。标签数越多，分组算法GFSA的优越性越明显。但是这种算法需要在原有的DFSA算法上做很多修改，例如读写器命令需要加入分组参数，标签需要确定并保存自己的分组序号，这使得实现变得有些困难。3.帧时隙ALOHA改进算法流程由于传统的ALOHA算法和帧时隙ALOHA算法存在系统吞吐率低，在大量数据交换时系统性能急剧下降的缺点。本章在综合现有的几种ALOHA算法的基础上，结合RFID系统的信息传输特性，提出一种用于RFID系统中的改进的动态帧时隙ALOHA算法，本章结合RFID系统的信息传输特性，提出一种用于RFID系统中的改进的动态帧时隙ALOHA算法。试验表明，该算法可应用于ISO18000-6标准的TypeA中的基于动态帧时隙ALOHA算法的防碰撞方案框架中[3]。本算法的基本思想是RFID读写器以某个初始的帧长发送请求命令，通过正确识别的标签数和帧长估算现场标签数，根据碰撞时隙数和系统碰撞率来估计未识别标签数，然后根据未识别标签数调整帧长：如果未识别标签数小于使系统吞吐率达到最大值的数量，那么减少帧长，否则增加帧长；如果未识别标签数超出了系统允许的最大值，那么用取模的方法将标签分成几个子集，再按以上的方法进行读取。每一个读取周期里，读写器都估计现场的未识别标签数，调整帧长，以保证系统能以最大的效率（吞吐率）进行工作[4]。（1）算法主流程初始化参数：N=N0：N0为帧长的初始值，一般根据具体的应用模式进行设定，由于帧长太小不符合实际应用，故一般首先设N0为8，并且变化规律为2的指数次幂。阅读周期内初始化：C=C1=C2=0：初始化碰撞计数和正确接收计数；S1otCounter=N：初始化阅读器的时隙计数；①阅读器发送以N为参数的清点指令，等待标签回复；②接到的回复可能被判断为以下三种情形：a)碰撞：碰撞计数加一：C2++；b)正确接收：正确接收计数加一：C1++；c)无信号：无动作；任意情况下，阅读器时隙计数减一：SlotCounter--；③SlotCounter==0？a)Yes：C2==0？i)Yes：结束本次清点。ii)No：调用帧长度调整子程序重新设定N，返回步骤(1)；b)No：发送指令，进入下一时隙，返回步骤③；（2）帧长度调整子程序：02e=2N=round(e*C)初始化参数：；；①搜索()0efN,N′=曲线（利用计算好的数据查表3.2）：()0efN,N=即公式（4-6）；②2Nround(e*C)′′=；③0N==N′？Yes：02N=N-C，帧长度调整子程序结束。No：0N=N′，返回步骤1。（3）算法流程描述图1.改进算法流程图（4）分组子程序通过上面分析可知，DFSA不适用于有大量标签的情况，为了解决这一问题，参考BinaryTree算法，可以先将标签分组，使每组中只含有较少量标签，然后针对每组标签再算法进行读取，这样就可以解决DFSA算法读取大量标签的问题。具体实现过程为：①当到来的标签数n急剧增加，根据maxMn/N=（式中Nmax取值256）将标签分成M组。标签有一个随机数生成器，可生成1到M之间的随机数，这个随机数代表着分组的组数，在阅读器发送分组命令时，标签随机选择一个数字即选择一个组组内进行回答。②阅读器从第1组开始读取标签，在组内采用DFSA算法解决标签碰撞问题当读取完该组内所有标签后，将组数加1，重复这一步骤。4.总结本文先从整体上提出了ALOHA防碰撞算法的基本思想，然后对算法过程进行了详细的描述，再次给出了未识别标签估算子程序和改进算法流程图，碰撞问题中不仅包括多标签之间的冲突，还有标签与阅读器之间的冲突以及阅读器之间的冲突，要使防碰撞问题得到彻底而全面的解决，需要根据实际应用情况结合三类冲突问题综合考虑，这条路还比较艰辛，需要在以后的工作当中继续研究，继续学习。参考文献[1]陈新河.无线射频识别（RFID）技术发展综述.信息技术与标准化，2005（7）：20-24[2]李宝山.基于动态ALOHA算法的RFID反碰撞技术.无线电工程，2007，37（2）：3-5.[3]程文青，赵梦欣，徐晶.改进的RFID动态时隙ALOHA算法.华中科技大学学报（自然科学版），2007，35（6）：14-16.[4]刘长征，熊璋，王剑昆.基于智能标签的射频识别系统的研究和实现[J].计算机工程，2003（11）.ResearchOnAnti-collisionAlgorithminRFIDChenTaoSchoolofInformationEngineering,WuhanUniversityofTechnology,Wuhan(430000)AbstractIntheRFIDsystem,iftwoormoreoftheRFIDelectronictagsatthesametimetransmitdatatoreader，therewillbecommunicationconflict,datainterferewitheachother.Inthereceiverofreader,thedatapacketsofelectronictagcannotbecorrectlyidentifiedandcreateerrors.Theanti-collisionalgorithmisusedtoavoidthedatacoll