基于ALOHA算法的RFID防碰撞技术研究

作者：时间：2009-10-23来源：网络收藏

3．2 动态帧时隙ALOHA算法
为使系统效率最优，提出动态帧时隙ALOHA(DynamicFramed Slotted Aloha，DFSA)算法，使得帧时隙数等于参与循环的标签数。DFSA每帧时隙数可以根据标签数的变化及时调整，使得标签数量与帧时隙数匹配。在开始新一个帧循环时，读写器要对参与帧循环的标签数进行估计，这个过程在整个算法中发挥着重要的作用。如果所估计的标签数与实际情况相差甚远，那么算法的效率就会发生大幅的下降，这样就影响了系统的稳定性。
目前，主要有两种估计标签数的方法。第一种方法是在发生冲突时，一个时隙中至少有两个标签发生碰撞。标签的估计函数为：

N代表当前帧的长度，C0表示空闲时隙，C1表示成功时隙，Ck表示碰撞时隙数。当冲突较频繁时，这种估计方法的相对估计误差较大，但具有方法简单等优点。
另一种方法是基于时隙二项分布来估计标签数。假设N代表当前帧的长度，n表示标签数。标签选择各个时隙数是等概率的，同一个时隙内出现r个标签的概率，根据二项分布原理，得：

利用切比雪夫不等式估计标签数目。

本文引用地址：http://www.eepw.com.cn/article/157800.htm

3．3 分组帧时隙ALOHA算法
在RFID系统中，我们经常使用动态帧时隙ALOHA算
法。但是由于最大帧时隙数有限制。当标签数量过大时，我们不能无限制地增加帧的时隙数。因此提出了分组帧时隙ALOHA(Group Framed Slotted Aloha，GFSA)算法。分组的目的是要限制标签的应答数量，使得参与识别循环的标签与帧的时隙数匹配。在GFSA算法中，如果估计出待识别的标签数超过了最大帧时隙数所能匹配的范围时，保证每一组的待识别标签与最大帧时隙数相匹配。

在图3中，无论是采用一组还是两组，都会达到同样的期望系统效率的标签数：

由上式我们可以得到n=354。如果未识别标签数大于354时，为达到最佳系统效率，我们将标签分成两组。我们提出的分组算法是基于最大帧时隙数为256的动态帧时隙ALOHA算法。在算法中，首先定义：
(1)为达到最大系统效率，通过获取最后一个阅读帧的结果(0或是1)来决定对分组标签进行响应，以确定新循环帧的大小。
(2)为减小RFID系统的复杂性，通过使用n=c1+2ck估计函数来确定标签数量。
(3)利用上面推导出的n=354，作为分组的条件。当系统内标签数量比较小时，则使用最大帧时隙数为256的动态帧时隙ALOHA算法。一旦标签数量超过了354时，则使用分组帧时隙ALOHA算法，来限制系统内的响应的标签数量。过程如图4所示。

我们利用二进制树形分解法对标签进行分组，如图5所示。二进制树形结构可以有效地对未识别标签进行搜索。对分组后，获取最后一个阅读帧的结果(0或是1)来判断是否继续分组。如果结果是1，表示达到时隙分离条件，需要对标签继续进行分组，直到结构是0为止。如果结果是0，表示未达到时隙分离条件，并采用动态帧时隙ALOHA算法对标签进行识别。
对提出的算法进行了仿真。结果表明：当标签数小于354时，分组帧时隙ALOHA算法采用动态帧时隙ALOHA算法；当标签数大于354时，分组帧时隙ALOHA算法对标签数进行分组识别。所以标签数越多，分组帧时隙ALOHA算法所使用的时隙数越少，效率越高。如图6所示。