基于RFID的电子标签防碰撞技术的研究.ppt

下图是纯ALOHA算法和Slotted ALOHA 算法吞吐率对比图： 七、ALOHA算法简介 3、Frame Slotted ALOHA算法（FSA） ALOHA 的另一种改进算法是帧时隙 ALOHA 算法（FSA）。 它是在Slotted ALOHA 算法的基础上把 N 个相同的时隙组成一帧，且在整个电子标签识别过程中，帧的大小是固定的，帧中的每个时隙足够一个电子标签与阅读器进行完通信，该算法也称为固定帧时隙 ALOHA 算法。 该算法比较适用于传输信息量较大的场合，和Slotted ALOHA 算法一样，帧时隙 ALOHA 算法同样需要一个同步开销。 七、ALOHA算法简介 FSA算法步骤如下： 首先由阅读器把帧长度 N 发送给电子标签，电子标签则产生[1，N]之间的随机数，接下来各电子标签选择相应的时隙，与阅读器进行通信； 如果当前时隙与电子标签随机产生的数相同，电子标签则响应阅读器的命令，若不同，标签则继续等待。 假如当前时隙内仅有一个电子标签响应，阅读器就读取该标签发送的数据，读取完了以后就使该标签处于“无声”状态。 如果当前时隙内有多个标签响应，则该时隙内的数据就出现了碰撞，此时阅读器会通知该时隙内的标签，让它们在下一轮帧循环中重新产生随机数参与通信。 逐帧循环，直到识别出所有电子标签为止。 七、ALOHA算法简介 FSA算法性能分析： 假设帧长度为 N（也即时隙数为N），有 n 个需要识别的标签，则一个时隙中有 k 个标签响应的概率服从二项分布： 其中p=1/N为标签选择该时隙的概率，所以上式可以化简为： 则一帧中能够识别出来的标签数目为： 七、ALOHA算法简介 FSA算法性能分析： 则系统效率= 一帧中识别出来的标签的数目/帧长度，就等于： 一帧结束后，成功时隙数（只有一个标签响应的时隙数）、空闲时隙数（没有标签响应的时隙数）、碰撞时隙数（有两个或两个以上标签响应的时隙数）的期望分别为： 七、ALOHA算法简介 FSA算法性能分析： 为了使得系统效率最优，让 对n求导，使得 由上式可知：当知道n的大小时，就可以求出使系统效率最大时相应的帧长度值，从而动态的改变帧长度的大小。 七、ALOHA算法简介 FSA算法性能分析: 由 ，可得： 当n较大时，根据泰勒级数，上式可以化简为： 所以当帧长度与待识别标签数目大致相等时，系统效率最高，因此可得到下面的动态帧时隙ALOHA算法（Dynamic FSA）。 七、ALOHA算法简介 下图是Frame Slotted ALOHA 算法当N=n时算法效率与标签数量的关系图： 七、ALOHA算法简介 4、Dynamic FSA 算法 该算法根据上一读写周期中统计的成功识别的时隙数、发生碰撞的时隙数、空闲时隙数信息来调整下一读写周期的帧长度。下面先介绍两种简单的调整方法。 第一种：根据统计信息，当碰撞时隙数达到规定的上限时，读写器增大下一帧的长度；当碰撞时隙数少于规定的下限时，读写器减少下一帧时隙数。使用该方法当标签规模不大时，读写器使用较短的帧长度就能快速识别标签，而当标签数量很多时，读写器不得不增加帧长度以减少碰撞次数。 七、ALOHA算法简介 第二种： 读写器以 2 或 4 个时隙数为一帧开始，如果没有一个标签能够成功识别，读写器增加帧长度开始下一轮读写周期。重复上述过程直到至少有一个标签被成功识别。当有一个标签成功识别后，读写器立刻停止当前的读写周期，然后读写器再以开始时最小的帧长度开始下一轮读写识别。 上述两种算法通过动态调整帧长度，系统的吞吐率相比帧时隙算法获得了一定程度的改善，但是还有改善的余地。 根据前面的推导可以得出，当标签数与帧长度差不多相同的时候，系统的吞吐率达到最大值，因此可以通过估计剩余未读标签数来动态调整帧长，使帧长跟随标签数的变化而变化。 七、ALOHA算法简介 对剩余标签数的估计通常有以下几种方法（其中C0、C1、C2分别表示空闲时隙数、成功识别的时隙数和碰撞时隙数。） 七、ALOHA算法简介 Nleft=2C2，这是剩余标签数的下限，该方法只考虑到 2 个标签发生碰撞的情况，但是实际中有可能 3 个或 3 个以上的标签在同一个时隙内发生碰撞。 2.Nleft=2.39C2，假设标签响应服从泊松分布，其中，2.39 为一个时隙上可能的标签数数学期望值，为静态估计算法。 3.Nleft=N-C1，其中N满足 ，其中