摘要】RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数 据通信，从而达到自动识别的目的随着RFID技术的发展，如何实现同时与多个目标之间 的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制 RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法 在各种已出现的算法当中，主要分为基于ALOHA的防碰撞算法和基于二进制防碰撞的算法， 本文分为三个方面，首先是基于ALOHA的防碰撞算法的理论研究比较，其次着重将现有的二 进制树算法进行了归纳，汇总为基本算法、动态算法、退避式算法三类，阐述了各个算法的 思路，并对其进行了性能评价；最后，在现有的三类防碰撞算法的基础上，提出了一种新的 改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果关键词】：射频识别；防碰撞算法比较；新型二进制树算法正文：1. 基于ALOHA算法的防碰撞算法分析对于RHD系统来说TDMA法在防碰撞中应用量最大TDMA法又分为标 签驱动法和阅读器驱动法，标签驱动法中主要有代表性的算法是基于ALOHA的 防碰撞算法主要有ALOHA算法、时隙ALOHA算法、动态时隙ALOHA算法、 优化的帧时隙(AFSA)算法和EDFSA算法。
下面对这几种算法进行分析比较1. 1纯ALOHA算法首先纯ALOHA算法是一种非常简单的时分复用算法，用于实时性不高的场合，只能 用于只读标签中，这类标签只存储一些标签的序列号等数据这种算法多采取“标签先发言” 的方式，即标签一进入阅读器的阅读区域就自动向阅读器发送其自身的ID信息并且在一 个周期性的循环中将这些数据不断地发送给阅读器，数据的传输时间只是重复时间的一小部 分，以致在传输之间产生相当长的间歇各个标签的重复时间之间的差别很小，两个标签以 一定的概率在不同的时间段上设置它们的数据，使数据包传送时不发生碰撞对同一个标签 来说它的发送数据帧的时间也是随机的ALOHA算法的基本思想是在标签发送数据的过程 中，若有其他标签也在发送数据，那么发生信号重叠从而导致完全碰撞或部分碰撞图1-1 给出了 ALOHA算法标签发送数据部分碰撞和完全碰撞情况的不意图标签1标签2标签3 图1-1纯ALOHA算法示意图接收部分碰撞完全碰撞阅读器检测接收到的信号来判断有无碰撞一旦发生碰撞，阅读器就发送命令让标签停止发 送，随机等待一段时间后再重新发送以减少碰撞，如果没有碰撞，阅读器发送一个应答信号 给标签，标签从此转入休眠状态。
而对于无接收功能的标签，标签收不到阅读器发送的碰撞 信息或者应答信息，在检测期间一直重复地发送自己的信息，直到识别过程结束纯ALOHA 存在的一个严重问题是存在错误判决的问题，即对同一个标签，如果连续多次发生碰撞，这 将导致阅读器出现错误判断，认为这个标签不在自己的作用范围纯ALOHA存在的另一个 问题是数据帧的发送过程中发生碰撞的概率很大纯ALOHA算法的标签读取过程可以总结如下：(1) 各个标签随机地在某时间点上发送信息2) 阅读器检测收到的信息，判断是成功接收还是发生碰撞3) 标签在发送完信息后等待随机长时间再重新发送信息4) 若假设一帧信息的长度为To,起始时间为t0则当另一帧的起始时间匚满足关系式(3-1) 时碰撞发生，即：~T0 -li -?o +To (1-1)为了 了解纯ALOHA算法的标签读取过程，下面分析它的标签读取性能为了分析方便首先定义如下两个参数：(1) 吞吐率S：代表有效传输的实际总数据率，即单位时间内标签成功完成通信的平均次数2) 输入负载G：表示发送的总数据率，即％时间内标签平均到达次数因此，吞吐率S可以 表示为输入负载G与传送成功率的乘积，即S = GPe (1-2)其中Pe是到达的标签能成功完成通信的概率。
由概率论知识可知，每秒钟发送的信息帧的数目服从泊松分布，因此t秒 钟发送行个数据帧的概率为：心)=(加)e"'/"! (1-3)其中2为每秒钟平均发送的总的信息帧数，此时输入负载为：G = AT0 (1-4)则在时间2T0内没有发送信息的概率为：Pe=P(n=O)\t=2T=e~^T =e~2G (1-5)这样，就可以得到纯ALOHA算法的吞吐率为: S = GPe= Ge 2C (1-6)当G=0. 5时，吞吐率S达到最大值0. 184o当G>0.5时性能急剧恶化，系统进入不稳定 状态因为必须尽量使G不要太大，这样只能改小％,同时也要注意由于标签自身的问题不 能检测碰撞，因此只能重发，重发次数不一定越多越好，因为重发次数多了，会使得输入负 载过大，碰撞率增加，因此要选适当的退避区间由上分析可知ALOHA算法的主要特点是各个标签发射时间不需要同步，是完全随机 的，当标签的数量不多时它可以很好地工作缺点是数据帧发送过程中碰撞发生的概率很大, 碰撞周期是2%,而且由于受标签的费用及其大小的限制，它不能自己检测碰撞，只能通过 接收阅读器的命令判断有无碰撞当数据业务繁忙，发生碰撞的概率增多时，性能急剧下降, 信道最佳利用率只有18. 4%。
但是ALOHA法由于它实现起来比较简单，能够作为防碰撞 的方法，适用于只读标签系统1. 2时隙ALOHA算法使纯ALOHA算法对比较小的吞吐率最佳化的途径就是时隙ALOHA(SlottedALOHA)算法 如图3. 3所不，这种算法在ALOHA算法的基础上把时间分成多个离散的时隙(slot),并且 每个时隙的长度要大于标签回复的数据长度，每个时隙长度由系统时钟控制，各控制单元必 须与此时钟同步对于RFID系统，标签只在规定的同步时隙内才能传输数据包，对所有的 标签所必须的同步山阅读器控制，标签只能在每个时隙内发送数据标签1标签2标签3接收正确接收 完全碰撞图1-2时隙ALOHA算法示意图从上图可以看出，每个时隙存在以下三种情况：(1) 无标签响应：在此时隙内没有标签发送2) —个标签响应：在此时隙内只有一个标签发送，标签能够被正确识别；(3) 多个标签响应：在此时隙内有多个标签发送，产生碰撞与纯ALOHA算法的分析方法相同，可以得到在一个时隙起点处没有其他标 签发送信号的概率为：Pe=e° (1-7)因此，可以得到时隙ALOHA算法的吞吐率为：S=GPe= Ge ° (1-8)当G=1时，系统的吞吐率可以达到最大值0. 368,由此可见时隙ALOHA算法的系统吞吐 率比纯ALOHA算法提高了 1倍。
缺点是需要同步时钟，且标签能够计算时隙1. 3帧时隙ALOHA算法ALOHA算法的另一种扩展算法是帧时隙(Framed Slotted)ALOHA算法，简称FSA算法 它是在时隙ALOHA算法的基础上把IV个时隙组成一帧,标签在每个帧内随机选择一个时隙 发送数据，如图1-3所示这种算法适于传输信息量较大的场合，与时隙ALOHA算法相同， FSA算法也需要一个同步开销一个帧包含多个时隙，每个时隙的长度要足够让一个标签 回答完，具体时间由阅读器定义在阅读器发送读取命令后，要等待一定时间等待标签的回 答当在一个时隙中只有一个标签回答时，阅读器可以分辨出标签；当在一个时隙中没有标 签回答时，跳过此时隙：当在一个时隙中有多个标签时，发生碰撞，需要重新开始读取过程FSA算法存在的缺点是，当标签数量远远大于时隙个数时，读取标签的时间将会大大增加， 而当标签个数远远小于时隙个数时，会造成时隙的浪费总的来说，FSA算法的主要特点 如下：(1) 把IV个时隙打包成一帧；(2) 标签在每IV个时隙中随机选择一个时隙发送一次信息；(3) 该方法需要阅读器和标签之间的同步操作，每个时隙需要与阅读器进行同步，每一帧的 最大时隙数IV为某默认值，需要预先设定。
1. 4动态帧时隙ALOHA算法时隙ALOHA算法的吞吐率在输入负载G为1时达到最大如果输入负载小于1,则会 造成空时隙的数目增加，浪费宝贵的标签读取时间；如果输入负载大于1,则会造成碰撞的 时隙数增加，造成处于一个单独时隙发送成功的标签概率比较小，因此同样需要准备更多的 时隙，这样同样会降低系统的实时性弥补的方法就是使用动态的时隙数，这是一种改进的 FSA算法该算法中，阅读器能动态改变(增加或减少)下一次阅读循环中每帧的时隙个数IV, 这种算法称为动态帧时隙(DynamicFramed Slotted ALOHA)算法，简称DFSA算法一帧内 的时隙数目IV能根据阅读区域中的标签数目而动态改变，或者通过增加时隙数以减少帧中的 碰撞数目，或者在空时隙很多时减少IV以节省时间该算法的具体步骤如下：(1) 标签进入阅读器的读取范围后，接收到阅读器的开始识别命令后进入识别状态，并且在 开始识别命令中包含了初始的时隙数IV2) 进入识别状态的标签随机选择一个时隙(内部伪随机数发生器产生)，同时将自己的时隙计 数器复位为1；(3) 当标签随机选择的时隙数等于时隙计数器时，标签向阅读器发送数据，当标签的时隙数 不等于时隙计数器时，它将保留自己的时隙数并等待下一个命令。
此时，可能出现下列情况: 情况1：当阅读器没有检测到标签的响应时，将发送结束时隙命令处于识别状态而没有响 应的标签接收到命令后把自己的时隙计数器加1,然后重复步骤(3)情况2：当阅读器检测到多个标签的响应碰撞时，将发送结束时隙命令处于识别状态的标 签接收到命令后把自己的时隙计数器加1,然后重复步骤(3)情况3：当阅读器接收到一个标签的正确回复时，阅读器将发送下一时隙命令，处于识别状 态的所有标签的时隙计数器都加1,刚响应过的标签收到正确的休眠命令后将进入休眠状态, 否则标签将继续停留在识别状态，跳到步骤(3)继续循环下去4) 当阅读器检测到时隙数量等于命令中规定的循环长度IV时，本次循环结束阅读器发送 开始识别命令进入步骤(2)开始新的循环，新的循坏长度IV是阅读器根据前一次循环中碰撞 数量动态优化调整后产生的关于动态调整循环长度IV的方法也有很多不同的算法，一种是 根据IV个时隙中发生碰撞的时隙数、没有响应的时隙数等来判断的如当发生碰撞的时隙数 大于某一上限值时，将每帧的总时隙数IV增加，当发生碰撞的时隙数小于某一个下限值时将 每帧的总时隙数IV减少另外一种算法是，阅读器用初始一帧内时隙数N(N较小)开始发送 读取命令，如果在这次循环中没有一个标签回答，阅读器就增加一帧内时隙数，直到至少一 个标签被识别，然后阅读器再从初始时隙数N开始新一轮循环。
在DFSA算法中，每帧中 的时隙个数IV都是动态产生的，因此解决了 FSA算法中时隙的浪费问题由此可以看出这 种算法简单、易实现,且能充分适应标签数量的动态变化，非常适合在RFID技术中使用t2411. 5优化的帧时隙ALOHA算法优化的帧时隙(AdvancedFramedSlotted)ALOHA简称为AFSA算法这种算法使用可动 态调整时隙的数量oAFSA算法通过估计标签的数量来确定合适的帧大小，以此来识别标签 所以它比FSA算法更有效在AFSA中，阅读器利用读循环的结果：空时隙的数量、有一个标签的时隙数量和发 生碰撞的时隙数量的信息来预测标签的数量AFSA算法预测标签数量的公式是切比雪夫不 等式提出的随机变量X的随机试验结果在某个特定坏境非常接近于彳的期望值预计标签 数量时就是利用这个值这样通过度量真实结果与预期结果之间的差异并使差异最小化来预 测标签的数量在AFSA算法中，假设标签在其它读循坏中己经响应AFSA算法计算通过改变帧大小 要读到99%的标签需要多少时隙，然后它选。