基于帧的时隙ALOHA算法

 在S～ALOHA算法的基础上，将若干个时隙组织为一帧，阅读器按照帧为单元进行识别，就形成了基于帧的时隙ALOHA(FSA)防冲突算法。在FSA 算法中，每一帧开始时，阅读器广播帧的长度厂'指明F一帧所包含的时隙个数，并激活其识别区域中的所有杨：签。每个标签在接收到帧长厂之后随机独立地在0～俨l)中选择一个整数作为自己发送标识符的时隙序号，并将这个序号存在寄存器SN中。在下一帧的每一个时隙中，阅读器通过时隙开始命令启动一个新的时隙，如果标签SN的值等于零则立即发送标识符号，如果不等于零则将其SN值减l而不发送标识符。对于标签而言，如果标识符发送成功(即无冲突发生)，则该标签立即进入休眠状态，在之后的时隙不再活动；如果有冲突发生，则该标签进入等待状态，在下一帧中在重新选择一个时隙发送标识符。阅读器不断重复以上过程，随到在某一帧中没有收到任何标签信号，则认为所有标签均被识别。因此，在FSA算法，存在三种状态时隙：空时隙(没有标签响应)、单时隙(只有一一个标签响应)和冲突时隙(不止一个标签响应)。只有在单时隙中，阅读器能够成功识别一个标签，其他的时隙则无法识别标签。FSA算法的模型如图4．3所示，FSA算法逻辑简单，且每个标签在帧内只随机发送一次，能够有效地降低冲突的概率。FSA算法是目前RFID系统中最常用的一种基于Al．OHA的防冲突算法。

    表4．1给出了FSA算法的～l个具体的例子，描述FSA算法的执行过程…。
在这个例子中，每一帧有四个时隙。假设有六个标签参与识别的过程，每个标签的ID均是长度为5比特的二进制字符串。赞法的执行过程如下：
    1)阅读器发送REQUEST命令，代表‘帧的开始，并使标签与阅读器同步。
    2)当标签接收到阅读器的REQUEST命令后，标签在第0帧中随机的选择四个时隙中的一个时隙传输自己的ID给阅读器。在此例中，在第0帧，阅读器只在第一个时隙中成功i!：别了标签ID为Oll l0的标签；第：二个时隙和第四个时隙有冲突产生，无法识别标签；第三个时隙为空时隙，无标签响应。
    3)被成功识别的标签可以通过SELECT命令对标签执行读／写数据。在接下来的帧中，该标签将不再响应REQUEsT命令。
    4)阅读器重复发送REQUEST命令，直到所有的标签均被成功识别为止。
 FSA算法中帧的长度是固定的，当标签个数远大于帧的长度时，发生冲突
的概率会增大，识别标签的时间会极大地增加；相反，当标签个数远小于帧的长度时，会造成时隙的巨大浪费，也会增加识别的时问。理论上可以证明，只有当帧的长度等于阅读器场内标签的数目时，FSA的才能获得最佳的识别性能，使得信道利用率达到36．8％。但是实际应用中标签的数目往往是未知的，并且可能是动态变化的，这给FSA的帧长设置带来了挑战。为了解决FSA算法的局限性，关于设置FSA帧长的研究不断涌现，动态自适应设置帧长度的算法应运而生。目前常见的帧长调整方法有两种：一种方法是EPC Classl Generation2标准中设计的Q算法，Q算法也是现有的RFID系统中普遍采用的帧长调整算法；另一种方法是根据前一帧标签响应中获取的空时隙数目，冲突时隙数目和单时隙数目，来估计当前的标签数目，从而设置下一帧的最优长度。
    在Q算法中，当一帧出现过多的冲突时隙时，阅读器会提前结束该帧并重
新发送一个更大的帧；当一个帧出现过多的空闲时隙时，阅读器也会提前结束该帧，重新启动一个更小的帧，Q算法的模型如图4．4所示陋]。
    在图4．4中，阅读器维持‘个浮点型帧参数Q如，其初始值为4．0(Q如四合五入之后的值，即round(Q如))；C为一个常量，取值区问为0．1～0．5；Query 为帧开始命令，其输入为Q，J、‘播的帧长为(2Q_I)。处于激活状态的标签一旦接收到阅读器的Query命令，就会重新选择自己回复的时隙序号。Qm的调节
过程如下：如果前一个时隙没有标签回复(空时隙)，Qm减去常量C，最小保证为0；如果前一个时隙有多个标签回复(冲突时隙)，Q南加上常量C，最大保证为15；如果前一个时隙只有一个标签回复(单时隙)，瓯保持不变。最后，阅读器根据新的Q=round(Q协)来决定继续该帧还是重新启动新的一帧。Q算法
能够自适应地调整帧长，识别效率高，在超高频识别系统中得到了广泛的应用。
    为了更好地设置帧的长度，可以根据前一帧标签的响应情况，获取空的时隙数目、发生冲突的时隙数目和成功识别标签的时隙数目，估算当前的标签数
目，来设置下一帧的最优帧长。这也就是基二f动态帧长的时隙ALOtlA协议。在动态帧长的时隙ALOHA协议中，阅读器通过估算标签的数量设置帧长，提高基于帧的时隙ALOHA防冲突算法的性能。通过优化帧长，FSA算法的信道
利用率最大率达到36．8％。如图4．5所示㈦，当帧长L等于未识别标签的数目时，信道利用率最大为36．8％。
    基于ALOHA的防冲突算法简单，并H．兼顾了公平性。但是，标签存在饿死的问题。当一个标签选择的时隙总是冲突时隙，则该标签可能永远无法被识别。