一种基于时隙ALOHA的RFID系统防碰撞算法

1、引言

RFID射频识别是一种非接触式的自动识别技术，它通过射频信号自动识别目标对象并获取相关数据。典型的RFID系统主要包括两部分：读写器(Reader) 和标签(Tag)。

在射频识别系统工作时，在读写器的作用范围内，可能会有多个应答器（标签）存在，这些应答器的数据同时传送到读写器时出现冲突即数据碰撞，导致读写器无法读出数据。现阶段RFID系统应用中，基于TDMA的防碰撞算法目前有两种:基于比特位的二进制搜索算法和基于时隙的ALOHA 算法。二进制搜索算法需要阅读器能够确定碰撞的准确的比特位置,这就需要阅读器对所有标签的准确的同步,而这种同步在实现时是困难的；ALOHA算法在应用中随着标签数量的扩大,性能将急剧恶化^[2]。因此,本文提出了一种改进的基于时隙ALOHA的防碰撞算法, 通过限制响应标签的数量，降低了冲突发生的可能性，提高了标签的识别效率，有效解决了ALOHA算法的这方面的局限性。

2、现有的ALOHA防碰撞算法^[3]

2.1 纯ALOHA（pure-ALOHA）

ALOHA是多路存取中最简单的方法，它是一种随机接入算法，这种算法多采取“标签先发言”的方式，即标签进入读写器的阅读区域就自动向读写器发送其自身的ID，随即标签和读写器间开始通信。在标签发送数据的过程中，若有其他标签也在发送数据，那么发生信号重叠从而导致完全冲突或部分冲突。读写器检测接收到的信号来判断有无冲突。一旦发生冲突，读写器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。

纯ALOHA存在的一个严重问题是数据帧F的发送过程中，冲突发生的概率很大，其冲突期为2F。理论上，纯ALOHA算法的信道最大利用率只有18.4%。此外，RFID系统中标签不具有载波监听发现冲突的能力，只能通过接收读写器的命令来判断有无冲突。

2.2 时隙ALOHA（Slotted-ALOHA）

Slotted-ALOHA算法是在纯ALOHA算法的基础上把时间分成多个离散时隙，标签只能在每个时隙的分界处才能发送数据。这样标签或成功发送或完全冲突，避免了纯ALOHA算法中的部分冲突，使冲突期减少一半，提高了信道的利用率，达到36.8%，使纯ALOHA算法的两倍。但是这种方法需要一个同步时钟，使得读写器阅读区域内所有标签的时隙同步。

2.3 帧-时隙ALOHA（Framed-Slotted ALOHA）

Frame-Slotted ALOHA算法是在时隙ALOHA算法的基础上把N个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据。

3、改进算法

胡建赟等人^[4]在分析RFID系统识别过程后，在固定时隙数量，不同数量应答器的情况下，将时隙的数量固定在25个，应答器的最大数量设为30个，得到了在25个时隙数时，系统中标签数量大于一帧所含的时隙数时，识别成功率急速下降的结果。因此，本文提出的算法，通过制定一定的规则来限制响应阅读器请求命令的标签数量，以达到提高阅读器的识别效率，降低识别所有标签所使用的时隙数的目的。

本文算法通过比较标签序列号的一部分比特位，以限制响应请求命令的标签数。阅读器向标签发送比较的开始位、比较位的长度和比较的基准值。标签收到这些数据后，将自己的部分序列号与规定的比较基准值相比较，若小于基准值，则该标签响应阅读器。例如，假设标签的序列号为8位二进制数，比较的开始位是比特位5，比较位的长度是3，比较的基准值是100₂。如有一标签A的序列号为10011101₂，根据以上的比较信息，可知该标签用来比较的序列号部分为“011₂”，小于比较基准值100₂，则标签A响应阅读器。若另有一标签B的序列号为01101001₂，易知，该标签将不响应阅读器。

阅读器的识别成功率在标签数大于一帧所含时隙数时，大幅降低，所以，本文提出的算法并不是在任何时候都需要使用的。限制该算法使用的条件是发生冲突的标签数与发送的标签数的比率。如果，该比率大于参考值，则采用本文提出的算法，否则，所有的标签都响应阅读器。Tae-Wook Hwang等人^[5]提出过以上类似的算法，他采用的比率概念是发生冲突的时隙数与一帧所含时隙数的比值，但本算法采用了完全不一样的比率概念。仿真结果显示，采用本文的比率概念后，所使用的时隙数比Tae-Wook Hwang等人的时隙数降低了将近20%。

式1表达了本算法中比率概念及比率与参考值之间的关系。

R=C/T≥γ                           （1）

其中，C是发生冲突的标签数,T是发送的标签数，γ是参考值，它决定了是否采用本文提出的算法来限制响应阅读器的标签数量。图1所示的为算法流程图。

图1本文提出的算法的流程图     

4、仿真结果分析

在仿真过程中，设定了一帧所含的时隙数是256，比较位的长度是3，比较的基准值是100₂，每次比较的开始位随机产生。当R值大于等于γ时，采用本文提出的算法，限制响应阅读器的标签数；R值小于γ时，所有标签响应阅读器。在以上的条件下，本仿真实验考察了γ在取不同值时，标签数从1逐渐增加到1000，阅读器识别所有标签所使用的时隙数的情况。表1所示的为仿真实验中的参数的取值情况。其中S_0.5 ~ S₁为仿真结果图中不同参数下纵坐标对应的值。

表1 仿真试验中的参数       

在第一个仿真中，γ（gamma）值分别取了：0.5、0.6、0.7、0.8、0.9、1，由式（1）可知，R的值必定是小于等于1的，当R等于1的时候，说明所有标签都发生冲突，这种概率在实际情况下是很小的。从图1的流程图可知，当阅读器计算得到R的值大于等于γ（gamma）时，将采用本文提出的算法，所以当γ（gamma）=1的时候，是永远不会采用到本文提出的算法，也就是说，阅读器在识别标签的过程中，没有使用本文的算法，即γ（gamma）=1的曲线对应的是普通算法情况下，阅读器识别所有标签所使用的时隙数。γ（gamma）分别取值0.5、0.6、0.7、0.8、0.9时的曲线，对应了使用本文提出的算法时，阅读器识别所有标签所使用的时隙数情况。从图2可以看出，当标签数达到600个左右的时候，普通算法所消耗的时隙数急速上升，而本文提出的算法的时隙数曲线变化斜率基本保持不变，并且当标签数大于600以后，可以明显地看出本文提出的算法所使用的时隙数比普通算法的时隙数少使用了很多，充分体现出本文提出的算法比普通算法优越。另外，从图2也可以看到，当γ（gamma）=0.8且拥有大量标签时，阅读器识别所有标签所使用的时隙数是最少的。从图3可以非常明显的看出，当标签数=990时，γ（gamma）分别取0.5、0.6、0.7、0.8、0.9、1（普通算法）的情况下，γ（gamma）=0.8时，使用的时隙数最少，比采用普通算法少了大约1300个，降低了约41%左右。

图2 γ（gamma）取不同值时所使用的时隙数变化曲线

图3 标签数=990时，γ取不同值时所使用的时隙数比较

在第二个仿真中，一帧所含的时隙数（N）分别取256、128和64，并且在这三种情况下，分别使用了普通算法和本文提出的算法。目的是了解一帧所含时隙数的取值情况对阅读器识别标签过程中使用时隙数的影响，同时观察本文提出的算法是否优越。从图4可以看出，当N=256时，使用的时隙数最少。当N=128时，在标签数大于300的情况下，应用本文提出的算法所使用的时隙数曲线的斜率约为5，而普通算法的曲线斜率约达到47，由此可知，后者的曲线增加速率约为前者的10倍，即所使用的时隙数随着标签数量的增加，其增加的速率在应用普通算法时约为应用本文算法时的10倍。当N=64时，也可以得到相应的比较情况。所以，通过第二个仿真试验，验证了本文提出的算法较之普通算法其性能是优越的。

图4 在一帧所含时隙数不同的情况下，应用本文提出的算法和普通算法时所使用的时隙数的比较

5、结论

本文作者创新点在于提出一种RFID系统防碰撞改进算法，该算法针对在RFID防碰撞算法中，ALOHA算法在应用中有随着标签数量的增加,性能急剧恶化的缺点，将冲突发生的比率与参考值γ相比较后，通过比较部分标签序列号的方法，限制响应阅读器的标签数量，从而提高了识别标签过程的性能。一系列的仿真结果显示了本文所提出的改进算法比普通算法识别标签所使用的时隙数少，性能优越。

参考文献(References)：

1、李宝山，射频识别系统防碰撞技术的研究，包头钢铁学院学报，2005.12

2、陈博，一种类二进制搜索的RFID系统反碰撞算法及其实现，电子器件，2006.3

3、陈香，张思东，薛小平，RFID防碰撞技术的研究，电脑与电信（PCCom），2006.4

4、胡建赟，李强，闵昊，时隙ALOHA法在RFID系统防碰撞问题中的应用，应用科学学报，2005.9

5、Tae-Wook Hwang,Byong-Gyo Lee, Young Soo Kim, Doug Young Suh and Jin Sang Kim, Improved Anti-collision Scheme FOR High Speed Identification in RFID System, Proceeding of the First International Conference on Innovative Computing, Information and Control,2006

6、胡圣波，郑志平。一种井下RFID定位系统的读卡器防碰撞算法[J]。微计算机信息，2006，9-2：185-187