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

1 射频识别系统介绍

射频识别技术(Radio Frequency Identification，RFID)是一种非接触式自动识别技术，与传统的识别方式相比，它无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处理，具有操作方便快捷、存储数据量大、保密性好、反应时间短、对环境适应性强等优点，现在已广泛应用于工业自动化、商业自动化和交通运输管理等领域，成为当前IT业研究的热点技术之一。

典型的RFID系统主要包括三个部分：电子标签(tag)、读写器(Read)和应用系统(如图1)。电子标签放置在被识别的对象上，是RFID系统真正的数据载体。通常电子标签处于休眠状态，一旦进入读写器作用范围内就会被激活，并与读写器进行无线射频方式的非接触式双向数据通信，以达到识别并交换数据的目的。此外，许多读写器还都有附加的通信接口，以便将所获的数据传给应用系统进行进一步的处理。

2 系统防碰撞

RFID系统工作时，当有2个或2个以上的电子标签同时在同一个读写器的作用范围内向读写器发送数据的时候，就会出现信号的干扰，这个干扰就称为碰撞，其结果将会导致该次传输的失败，因为必须采用适当的技术防止碰撞的产生。

3 ALOHA算法及仿真结果

目前有多种防碰撞算法，主要分为ALOHA算法和树形分解算法。由于树形分解法有时会使某些标签的识别延迟可能比较长，所以ALOHA算法因具有简单易实现等优点而成为应用最广的算法之一。ALOHA算法是在ALOHA思想的基础上，根据RFID系统的特点和技术要求不断改进形成的算法体系。它的本质是分离标签的应答时间，使标签在不同的时隙内发送应答。一旦发生碰撞，一般采取退避原则，等待下一循环周期发送应答。ALOHA算法又分为帧时隙ALOHA算法、动态帧时隙ALOHA算法和分组帧时隙ALOHA算法等。

3.1 帧时隙ALOHA算法

帧时隙ALOHA(Framed slotted Aloha，FSA)算法是基于通信领域的ALOHA协议提出的。在FSA中，"帧"(Frame)是由读写器定义的一段时间长度，其中包含若干时隙。标签在每个帧内随机选择一个时隙发送数据。所有标签应答同步，即只能在时隙(Slot)开始点向读写器发送信息，每个标签发送的时隙是随机选择的。时隙可以分为三类：空闲时隙、应答时隙和碰撞时隙。在空闲时隙中没有识别任何标签，应答时隙中可以正确识别一个标签。当一个时隙中有多个标签同时发送应答时就会产生碰撞，形成碰撞时隙。碰撞的标签退出当前循环，等待参与新的帧循环。

读写器当前使用帧的长度为N，标签数为n，在一个时隙中存在r个标签的概率为：

当r=1时，表示一个时隙只有一个标签，即成功读取的时隙。因此，在一个阅读周期中读取标签数的期望值为：

　　其中，

　　表示只有一个标签占据一个时隙的时隙总数。其中帧长度为N，标签总数为n。

系统效率为PN:

图2示出了当帧的长度为256时的系统效率。当我们要想获得最大效率时，使得：

根据上式可推出当帧的长度为N时，效率最高的标签响应数为：

　　当标签数为n时，帧长度的最佳值为： 　　当n很大时，将上式泰勒尔展开：

因此，当标签数量与帧时隙数相同时，读写器的识读效率最高。标签数量与帧时隙数不匹配时，识读效率会大大下降。如标签数远小于帧时隙数，会造成大量的空闲时隙数;而当标签数量远高于帧时隙数时，则会产生过多的碰撞时隙;这两种情况都会导致识别效率的降低。

3.2 动态帧时隙ALOHA算法

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

目前，主要有两种估计标签数的方法。第一种方法是在发生冲突时，一个时隙中至少有两个标签发生碰撞。标签的估计函数为：

N代表当前帧的长度，C0表示空闲时隙，C1表示成功时隙，Ck表示碰撞时隙数。当冲突较频繁时，这种估计方法的相对估计误差较大，但具有方法简单等优点。

　　另一种方法是基于时隙二项分布来估计标签数。假设N代表当前帧的长度，n表示标签数。标签选择各个时隙数是等概率的，同一个时隙内出现r个标签的概率，根据二项分布原理，得：

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

在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所示。

4 结束语

本文基于ALOHA算法，分别对帧时隙算法和动态帧时隙算法进行研究和分析，并提出一种利用二进制树形分组的时隙ALHOA算法。对提出的分组算法和传统的动态帧时隙算法进行比较。当标签数过大时，采用此方法有利于提高系统效率，并减少了计算和操作的复杂度。