引言

RFID（Radio Frequency Identification，射频识别）是一种使用无线通信实现的非接触式自动识别技术[1]。典型RFID系统主要由标签（Tag）和阅读器（Reader）两部分组成[1]。根据供电方式的不同，标签可以分为有源标签和无源标签。与无源标签相比，有源标签需要小型锂电池配合使用，虽然体积较大，但是它可以工作于主动方式，资源更丰富，能实现更复杂的功能，近些年来在一些领域得到了广泛应用。

碰撞问题分为阅读器碰撞与标签碰撞[3]，由于标签数量大于阅读器的情况更加普遍，当大量标签进入阅读器感应范围时，不同标签就会因为竞争信道产生碰撞，因此标签防碰撞算法是近来研究的热点。解决碰撞问题常用如下方法：SDMA(空分多址) 、FDMA (频分多址)、CDMA (码分多址) 和TDMA (时分多址)，但是鉴于标签的资源有限、低功耗及成本考虑，RFID系统一般采用基于TDMA的方法[3]，又分为两大类——确定性算法和概率性算法。概率性算法又称ALOHA算法，它分为纯ALOHA、SA（Slotted ALOHA，时隙ALOHA）、FSA（Framed Slotted ALOHA，帧时隙ALOHA）、DFSA（Dynamic Framed Slotted ALOHA，动态帧时隙ALOHA）、GFSA（Grouped Framed Slotted ALOHA，分组动态帧时隙ALOHA）。本文在GFSA的基础上提出一种基于CSMACA机制的PGFSA （PreGrouped Framed Slotted ALOHA，预分组GFSA)防碰撞算法。

1 AOLHA防碰撞算法介绍

1.1 纯ALOHA算法

纯ALOHA算法[5]是一种最基本的防碰撞算法，无需标签间同步，实现简单，采用“标签先讲”的方式。当标签进入阅读器感应范围就自动向阅读器发送自身信息，这样不同标签就可能在同一时间向阅读器传输数据时发生碰撞。碰撞形式分为部分碰撞和完全碰撞，碰撞后采取随机退避的方式等待下一次发射。

1.2 SA算法

SA算法[5]在纯ALOHA算法的基础上对标签的发射时刻进行调整，把时间域分成离散的多个时隙(Slot)，每个时隙长度大于标签上传数据的时间，并由阅读器对标签进行同步控制，使标签只能在各时隙起始处发射。可以推断出，SA算法发生碰撞时只有完全碰撞，吞吐率提高了一倍。随着系统效率的提高，要付出标签同步的代价，同时标签也需要计算时隙。

1.3 FSA算法

FSA算法在时隙ALOHA算法的基础上，将L个时隙打包成一帧，就形成了帧时隙ALOHA算法。L为帧长，即每帧中含有的时隙个数，每个标签在每帧中只随机发射一次信息。开始识别标签后，由阅读器向周围标签广播帧长L，标签从0~L-1中随机选择一个时隙响应阅读器。如果发生碰撞，要等到下一帧继续选择时隙发射。

1.4 DFSA算法

在实际应用中，阅读器周围标签的数量是随机变化的，只有帧长L随待读标签数量n动态变化，L等于n时系统识别效率才达到最高[5]，这就是DFSA算法。在DFSA算法中，阅读器要根据接收到标签数据的情况对碰撞情况作出判断，调整帧长L。

1.5 GFSA算法

当标签数量远远大于帧长时，DFSA算法的系统效率将急剧下降，DFSA算法中帧长L最大只能为256。这时，就出现了GFSA算法，GFSA算法对标签进行分组，每次只有一组标签响应阅读器，每组标签仍然按照DFSA算法向阅读器发射数据。

2 基于CSMACA机制的PGFSA防碰撞算法

传统GFSA算法往往是阅读器对标签进行分组，根据标签个数估计算法[2]估算出标签个数后，向标签发射组号，每次只选通其中一组标签响应，这是一种样本训练机制，需要标签先发射一段时间后，阅读器才能估计出标签个数并分组，这样存在一定的延时性，而且估计算法很难准确计算出当前标签个数。与传统训练分组方法不同，PGFSA算法在待识别标签端预先分组，阅读器每次选通一组标签响应。这样减小了延时，并且不需要复杂的标签个数估计算法。

如果标签具有发现碰撞能力，标签就可以避免冲突时发送数据从而降低发生碰撞的概率。这就是CSMACA（Carrier Sense Multiple Access with Collision Avoidance，载波监听多路访问避免碰撞）机制，其基本思想是：每个标签在发送数据前，先监听信道上有无其他标签正在发送信息，如果信道空闲则发送数据，否则暂时不发送数据，随机退避一段时间后再重新监听信道状态。于是，本文在此基础上提出了基于CSMACA机制的PGFSA防碰撞算法。

3 算法设计与实现

在基于CSMACA机制的PGFSA防碰撞算法中，阅读器的流程图如图1所示，向进入感应范围的标签广播选通某组标签响应的命令，此选通命令含有初始化的帧长信息，然后等待该组标签向阅读器发射数据，接收标签数据过程中实时估计标签个数，并调整帧长向选通的标签广播实时的帧长信息，最后判断是否该组标签信息已经全部上传到阅读器。如果全部上传，则广播选通下一组标签的命令，依次循环，直至所有组的标签均被识别。标签的流程图如图2所示，预分组完毕的标签进入阅读器感应范围后，待接收到阅读器的选通命令后，判断是否与自身组号匹配。若匹配，则随机选择相应帧长中的一个时隙向阅读器发射数据，发射时采用基于CCA（ClearChannel Assessment，空闲信道评估）的CSMACA机制，发生碰撞随机退避后重发；若未匹配，则等待下一次选通命令，依次循环，直至所有标签上传完毕，进入下一轮选通发射。

图1 阅读器流程图2 标签流程

该防碰撞算法的程序在2.4 GHz频段的有源RFID系统中实现，其硬件采用基于德州仪器CC2530的方案。CC2530是一款2.4 GHz集成增强型工业级8051内核和射频模块的SoC芯片，符合IEEE 802.15.4标准，为了实现IEEE 802.15.4中的CSMACA机制，CC2530具有CCA的功能。另外，它支持半双工无线通信，可以实现非同时的射频收发[4]。

4 算法仿真与性能分析

评价基于ALOHA的防碰撞算法的指标主要有以下三个：吞吐率（S）、平均数据交换量（G）和平均延时（D）。其中，吞吐率反应的是信道利用率，平均数据交换量反应的是阅读器与标签双向通信的数据量，即系统负载。如果标签发生碰撞，吞吐率会受到直接影响，碰撞程度越恶劣，吞吐率越低，从而信道利用率就越低，造成系统资源的浪费。

纯ALOHA算法的系统吞吐率S的计算公式为：S = G·ｅ(-2G)，G表示单位时间内平均交换的数据包量[3]。当数据包量G=0.5时，系统吞吐率S得到最大值为18.4%，S与G的具体关系如图3所示。

图3 纯ALOHA算法S与G的关系

时隙ALOHA算法的系统吞吐率S的计算公式为：S=G·ｅ(-G)，G表示单位时间内平均交换的数据包量[3]。当数据包量G=1时，系统吞吐率S得到最大值为36.8%，S与G的具体关系如图4所示。

图4时隙ALOHA算法S与G的关系

帧时隙ALOHA算法的系统吞吐率S的计算公式为：S=(n/L)·(1-1/L)n-1，n为待识别标签个数，L为帧长[3]。当L=n时，系统吞吐率S得到最大值约为36.8%，L分别取32、64、96、128、192、256时的情况下，S与n的具体关系如图5所示。

图5 不同帧的情况下帧时隙算法S与n的关系

动态帧时隙ALOHA算法与帧时隙ALOHA相比，帧长是随标签个数变化的[6]。这就需要阅读器实时对标签碰撞情况作出判断，判断标签的个数，从而调整帧长，使得帧长等于估计的标签个数，这样它的系统吞吐率也达到最大值36.8%。但实际情况中标签个数的估计不可能准确无误，使得系统吞吐率维持在接近36.8%的范围[3]。

当待识别标签个数大于256并且持续增大时，由于标签个数估计算法难以实时快速准确判断出标签的总个数，动态帧时隙ALOHA算法的性能就会急剧下降，这时，需要引入分组动态帧时隙ALOHA算法[3]。传统分组机制，往往采用先进行样本训练，然后由复杂标签估计算法判断出大概标签个数，阅读器对标签进行分组，然后各组标签按照DFSA算法响应。可以看出，复杂的标签估计算法需要占用阅读器很多资源，并且样本训练增大了延时，因此，基于传统分组机制的GFSA算法未必适合在实际工程项目中应用。本文提出的基于CSMACA机制的PGFSA防碰撞算法，采用预先给标签分组，并且结合了CSMACA机制的优势，使得该算法在实际工程项目中表现出不错的性能。

5 实验结果

本实验在CC2530的平台上实现，阅读器端要编写成功识别标签个数累计的测试代码，并通过串口显示，使用了1个阅读器，300个标签进行测试，平均分为3组，每组100个，组号分别为1、2、3。阅读器每次选通其中一组标签响应，每组标签大约需要10 s左右的时间可以全部被阅读器识别，串口显示结果如图6所示，每行数据为1个标签发射的数据，每行第9个字节为识别标签累计个数，第10、11字节为标签ID；如果不进行预分组测试，300个标签大于帧长的最大值256，系统识别效率较低，碰撞急剧增多，存在一直不能被识别的标签。

实验说明，本文提出的基于CSMACA机制的PGFSA防碰撞算法是切实可行的，而且效果良好。

图6 串口显示结果

结语

本文在分析了多种ALOHA防碰撞算法的基础上，提出了基于CSMACA机制的PGFSA防碰撞算法，它是一种应用于有源RFID系统上改进的GFSA防碰撞算法。其中，预分组的方法与传统训练分组相比，延时性减小，算法结构更简单，减少了功耗，但此方法有自身的适用范围，需要已知待识别标签的位置分布规律。该算法在有源RFID系统中得以实现，不仅从算法仿真中可以看到其较高的性能，而且在实验中也得到验证。因此，基于CSMACA机制的PGFSA防碰撞算法在特定的RFID系统中将发挥越来越大的作用。