2.2动态帧时隙（DFSA）算法

DFSA算法为提高标签识读效率改变了帧长度，依据识别标签的时隙数目和产生碰撞的时隙数目等一些信息来决定帧长度，所以DFSA基本上可以解决BFSA标签识别效率低的问题。由于改变帧长度的方法不同，DFSA算法分为几个不同的版本，在此我们将简要介绍两种常用的方法【1】

第一种DFSA算法依据空时隙、产生碰撞时隙以及只有一个标签时隙的数目来规定帧长度。【1】。当产生碰撞的时隙数目超过上限时，阅读器就会加长帧长度；如果产生碰撞的可能性比下限还小，阅读器就会减小帧长度。由于阅读器以最小的帧长度开始一个阅读周期，所以当标签数量很少时，阅读器可以不增加帧长度而有效的识别所有标签；而当标签数量很大时，阅读器改变帧长度以减小产生碰撞的可能性。

第二种算法以一个时隙数为二或四的起始帧长度开始一个阅读周期。如果在前一个阅读周期没有识别到标签信息，阅读器将会增加帧长度同时进入下一个阅读周期，并且一直重复这个过程直至有至少一个标签被识别。如果只有一个标签被识别，阅读器将立即停止当前的阅读周期，并且以最小的起始帧长度开始阅读另一个标签的信息。

由于阅读器根据标签的数目来规定帧长度， DFSA算法可以有效地识别标签。然而，当有大量标签同时存在时，由于该算法只是确定地去改变帧长度，所以并不能完全避免标签碰撞。在第二种方法中，当标签数目很少时，阅读器可以几乎没有碰撞地识别所有标签，但是当数量很大时，由于该算法经常在识别完一个标签后就以最小的起始帧长度开始下一个读写周期，因此阅读器就需要依照指数规律增加时隙数目来识别所有标签，而不管还有多少标签还没有识别。

2.3 改进的动态帧时隙ALOHA算法（AFSA）

AFSA算法首先估计识读范围内的标签数目，然后根据估计的标签数目选择一个合适的帧长度去识别标签，所以AFSA算法要比BFSA算法能够更有效地减少碰撞。

AFSA算法利用一个阅读周期中空时隙、只有一个标签的时隙和产生碰撞的时隙数目来估计标签的数目，并且使用一个方程形式的函数来估计标签数目。Chebyshev不等式告诉我们，一次随机实验的结果中包含的那个随机变化的X值往往在某一方面最接近于X的理想值，对标签数目的估计函数正是利用了这个性质。因此，估计函数正是通过测量真实值和预期值之间的差别来估计标签的数目从而使这种差距变得最小。

对标签数目的估计使用了阅读周期中的帧长度以及前一个阅读周期的结果（c0，c1，c2）之间的等式关系，其中c0,c1,c2分别代表空时隙、只有一个标签的时隙和产生碰撞的时隙的数目。在这个等式中，<a^N，n_0，a^N，n_1，a^N，n₂>分别是预期空时隙、只有一个标签的时隙和产生碰撞的时隙的数目，其中N和n分别表示帧长度和标签数目。

AFSA算法假设标签已经在其他的阅读周期中产生了阅读响应，并且计算出需要多少时隙来阅读99%的标签从而来改变帧长度，然后算法选择一个需要最少时隙数的帧长度。由于AFSA算法估计了标签数目并且选择一个能最小化产生碰撞可能性的帧长度，所以要比其他的防碰撞算法更为有效。然而AFSA算法也有一个同样的问题，那就是不能随着标签数目的增加而随机地增加帧长度，因此，该算法在标签数目比较少的时候效果比较好，但是，当标签数目很大时，就会变的不那麽有效果。另外，这种方法不适用于一次性标签。

3.增强型动态帧时隙ALOHA算法（EDFSA）的提出

之前的帧时隙ALOHA算法通过改变来提高标签识读率，然而随着标签数目变得大过帧长度时，标签碰撞的可能性就会急剧增加。如果不把响应的标签数目限制在近似等于我们即将在接下来的文章中解释的帧长度时，这个问题很难得以解决，在第三部分中，我们提出了一种增强型动态帧时隙ALOHA算法来解决这个问题。

3.1 EDFSA算法的描述

如果我们能够估计出未读标签的数目，那么就可以最大化系统效率，或者说使标签碰撞的可能性降至最低。通常来讲，当标签数量很大时，我们可以增加帧长度来降低标签碰撞的几率。当未读标签数目太大以至于不能达到较高的系统效率时，由于我们不能随机地增加帧长度，就必须限制未读标签的数目从而选择最佳的标签数目来响应已规定好的帧长度。当标签数目太小从而不能达到理想的系统效率时，我们又必须减小帧长度。在这里，系统效率的定义是只有一个标签的时隙数目在当前帧长度中占的比例，并且是使用EDFSA算法中的估计标签数目和帧长度计算得来的。另外，估计的未读标签数目可以通过方程（1）中的估计函数来获得。

EDFSA算法首先估计未读标签的数目，相比于给定的最大帧长度，假如算法确定未读标签的数目远远大于可以获得最佳系统效率的数目，那么就利用最大帧长度将未读的标签分成几个部分，并且只允许一组标签在同一个阅读周期中响应。在该算法中，一旦应该响应的标签数目确定以后，我们就可以计算响应的标签数目在所有未识别标签中占有的比例。利用这个比例，阅读器请求对按模数操作余数为0的所有未读标签进行响应。在每个阅读周期中，阅读器都对未读的标签数目进行估计并且计算可以在下一个产生最大吞吐量分组数目。

如果当前帧长度大于可以给系统带来最佳效率的帧长度时，阅读器就会开始减小帧长度以使系统在识读估计的未读标签数目时达到最佳状态。

像BFSA算法一样，当阅读器限制了相应标签的数目时，阅读器在广播请求信息中会向标签发送标签的组数及一个随机数字。标签接受到请求后根据接收到的随机数字和自身的序列号产生一个新的数字，并且将新产生的数和字标签的组数将进行相除，只有余数为零的标签可以对阅读器的请求响应。当估计标签的数目低于一个极限的时候，阅读器便不会对未读标签进行分组，并且调整帧长度。这就意味着阅读器以一个帧长度、一个随机数字和标签组数来广播一个阅读请求，在每一个阅读周期结束后，阅读器估计未读标签的数目并且调整自己的帧长度，这个过程一直持续到所有的标签都被识别。

3.2 EDFSA算法的分析

在这一部分我们将给出当响应的标签数目增加并且帧长度固定的时候系统效率怎样进行改变，然后引出一种可以使系统效率最大化的情况。

一般来讲，在帧时隙ALOHA防碰撞算法中，当响应标签的数目变得越来越大时，系统效率就会开始降低，假设阅读器使用的帧长度是N，响应标签的数目为n，r个标签存在于一个给定时隙的几率遵循一个如下的二项式分布：

然而，一个阅读周期中预期读取的标签数目可以由下面的式子求出：

其中a₁^N，n表示r个标签在帧长度为N，未读标签数为n时占用的时隙数，这样系统效率就可以由以下的式子计算得出：

图2给出了帧长度为256时系统效率和标签数目之间的关系【3】【7】

我们可以利用对式（3）取微分生成的方程式得到使系统效率最高的标签数目。

对以上的方程式求解，就可以得到一个当帧长度为N时的理想响应标签数目。

当标签数目为n时，最佳帧长度的值可以由下式得出：

当n的值很大的时候，可以使用泰勒级数简化上式如下所示：

由上式可看到，当标签数目和帧长度基本相同时，可以的到最高的系统效率【3】。

从图2和式8可以d得到这样一个结论，如果我们将响应的标签数目限制在和帧长度相接近的时候，就可以达到最高的系统效率。如果未读标签的数目非常大（也就是说，大于帧长度），我们可以通过对标签分组来限制标签响应，并且运用求模运算，只允许一组标签进行响应，分组数和模数可以由下式求得：

本文中，考虑到执行过程的复杂性，我们假设EDFSA算法使用2的幂数（2，4，8……）来对标签进行分组，这样求模运算就可以简单地由移位寄存器来完成。图3给出了当帧长度设定为N=256时，系统效率随着标签数目增加的变化关系。在图3中我们可以看到，当未读标签的数目和帧长度比较接近的时候，系统效率可以达到最大值36.8%。

根据图3可以选定一个能够得到更高系统效率的具体的标签组数。

当未读标签的数目接近于或是小于帧长度时，即便不使用求模运算，不减小帧长度，也可以得到较高的系统效率。图4给出了当帧长度变化时系统效率的变化情况。

EDFSA算法选择的帧长度和模数要比其它任意两个量的组合都能够提供更高的系统效率。比如，由图3可知，不管我们采用的是模2运算还是模1运算，产生相同系统效率的标签数目是相同的，该值可由下式得出：

也可以将上式写成下面的这种形式：

因此，我们可以得出：

当未读标签数目略大于354时，为了达到最佳的系统效率，我们就需要将这些标签分为两组；而当未读标签的数目略小于354时，我们就必须使每个未读标签都进行响应。这样做，就可以一直使系统效率保持在34.6%和36.8之间，规律总结如表1所示：

4.EDFSA算法的性能分析

这一部分给出了当标签数目从0变化到1000时EDFSA算法性能的变化。因此，根据未读标签的数目，EDFSA算法不是改变帧长度就是将标签分组并且只让一组标签响应，下面我们将仔细地观察当标签数目从0变化到200时EDFSA算法性能的变化.

我们将EDFSA算法同BFSA算法以及采用第一种增加帧长度方法的DFSA算法进行比较。下文中，采用第一种增加帧长度方法的DFSA算法简称为“增值方法”，并且假设每种算法的最大帧长度为256，然后BFSA算法使用256个时隙的固定帧长度，增值方法则在16和256个时隙之间增加帧长度。在增值方法中，在产生碰撞的时隙数大于当前帧长度的70%时，假设帧长度将加倍。同时，当空时隙数大于当前帧长度的30%时，假设阅读器会将当前的帧长度减半。在EDFSA算法中，假设初始帧长度为128个时隙。当一个阅读周期中没有标签时，我们假设所有的标签已经被识读并结束仿真。为了得到结果，仿真程序将运行1000次，并且对这1000个结果取平均值。

4.1算法只需要改变帧长度的情况

图5显示了当标签数目从0变化到200的过程中每个算法的性能。由于上一个阅读周期用于确定所有标签已经被识读，因此BFSA需要重复至少两个阅读周期，故BFSA算法在这种情况下比其它两种算法要使用更多的时隙。

在增值方法中，阅读标签所需的时隙数随着标签的增加而线性增长。这是因为该算法在产生碰撞的几率较高时会增加帧长度，较低时会减小帧长度。由于初始帧长度被设置为128，当标签数目很小时，EDFSA算法读取标签所需的时隙数要多于增值方法。然而，当标签数目大于120的时候，EDFSA算法将开始展现较强的性能，这是因为相对于增值方法，EDFSA算法可以较快地调整其帧长度。

4.2算法需要使用求模运算的情况

当EDFSA需要进行求模运算时，我们来比较每个算法的性能。图6展示了标签从0增长到1000时每种算法的性能。从图中可以观察到，随着标签数目的增加，BFSA算法和增值算法识读标签所需的时隙数都会成指数规律增加，而EDFSA算法只是成线性规律增加，并且，同帧长度相比，由于太多的标签在进入时隙，大部分的时隙都被标签碰撞所浪费了。

由于增值方法可以在未读标签数目变小的时候减小帧长度，而BFSA算法则不管未读标签的数目怎样变化都保持同样的帧长度，增值方法表现出来比BFSA算法更好的性能。

EDFSA算法识读标签所用的时隙数随着标签数目的增长而成线性关系增加，这是因为不管未读标签的数目为多少，EDFSA算法都可以将系统效率保持在34.6%和36.8之间的一个平均数上。从图6中我们可以观察到，当标签数是1000的时候，EDFSA算法的性能分别比BFSA算法和增值方法改进了100%和85%，由于本算法所需的时隙数是线性增长的，而其它两种方法则是按指数规律增长，所以如果标签数目更大些的话，就可以发现本算法的性能会更好。

5.结论

鉴于传统RFID防碰撞算法识读标签时需要的时隙数随着标签数目的增加将会成指数规律增加，本文提出了一种增强型的动态帧时隙ALOHA算法（EDFSA），解决了这一问题。该算法首先估计未读标签的数目，并且只允许一部分标签响应从而来产生最佳的系统效率，当标签数目相对于给定的最大帧长度太大时，可以用求模运算来完成，而当标签数目相对于给定的帧长度太小时，系统的效率便不是最佳，从而需要减小帧长度使得系统效率保持在最佳状态。

为了执行过程的简单化，帧长度和模数都使用的是2的幂数。尽管在选择帧长度和幂数上还有一些限制，系统效率还是可以保持在34.6%和36.8%之间。这就意味着随着标签数目的增加，识读标签所需的时隙数一直是线性增加的。使用帧时隙ALOHA算法时系统的理论效率是36.8%，为了证明本文提出算法的有效性，我们进行计算机仿真并且发现当标签数为1000

点赞