RFID防碰撞算法研究与改进

引言

射频识别技术(Radio Frequency Identification，RFID)是上世纪80年代逐渐走向成熟的自动识别技术。它通过射频信号进行非接触式双向通信交换数据，以达到自动识别目标对象并获取相关数据。RFID可实现多目标的快速、动态、非接触性识别，广泛应用于物流、制造、医疗、交通等领域。

RFID主要由阅读器(Reader)和标签(Tag)两部分组成。在阅读器和标签的通信过程中，如有两个或多个标签处于Reader的可读范围内，由于它们共用同一无线信道且频率相同，因此当它们同时给阅读器发送数据时将出现信道争用，造成发送的数据干扰或冲突，从而导致阅读器不能正确读出数据。解决上述问题的方法称为反碰撞算法。反碰撞技术是RFID的关键技术之一。反碰撞算法让RFID中Reader与Tag之间的数据快速、可靠地传输。反碰撞算法设计的优劣很大程度上决定了RFlD系统性能。

1 纯Aloha算法

在P-ALOHA(Pure Aloha)中，任一标签进入阅读器的可读区域时，立即以定长信息包形式，将欲发送出去的数据送入信道。如果没有冲突出现，则认为是成功发射；若在发送过稗中其它标签也进入可读区域并发生碰撞，则随机独立地重新排定碰撞信息包，再一次重发，直至发射成功。如图1所示：



我们定义易碰撞期Tc为当前信包发送时刻附近另一标签进入信道发生碰撞的一段时间。若标签信包长度为T(时间表示)，如图2所示，在P—Aloha中Tc=2T。信道吞吐量是Aloha算法重要的性能指标，用Sp表示。它是信包进入信道的速率G的
函数，我们从图2可以看到P—A10ha的最大信道利用率为18．4％，其性能不理想。

2 时隙Aloha算法

S-Aloha(Slotted Aloha)只是把P-Aloha算法的时间轴离散化成若干时隙。要求信包长度小于或等于时隙长，且标签只能在时隙开始时刻开始发送信包。该算法的Tc=T，是P-Aloha的一半，故发生碰撞的概率减少一半。

信道吞吐量ss可以表示成信包进入信道的速率G的函数。从图4看出S-AIoha的最大信道利用率为36．8％，是P-ALOHA的两倍。但当阅读器范围内标签数目多时，要交换的信包量增加而吞吐率却快速下降甚至为零。



3 帧时隙Aloha

在S-Aloha基础上，把它的每个时隙进一步分割成若干时隙并打包成帧，就是FSA(Framed Slot Aloha)。由于标签在帧内只随机发送一次信包，因此就更一步降低了信包碰撞的概率。



FSA算法中帧时隙的长度是固定的，而实际应用中标签的数量未知，且是动态变化。因此当标签数量远大于时隙个数时，读取标签的时间将会大大增加，而在标签个数远小于时隙个数时，会造成时隙的浪费。

4 动态帧时隙Aioha(DFSA)算法

由于FSA算法的局限性，我们提出根据标签的数目，改变帧内时隙的大小，使得识别效率总是处于最优。设：帧时隙的长度为m，标签数为n，标签在帧内时隙的分布为二项式分布；则一个时隙内有k个标签的概率为：



由于帧内时隙地位一样、几率均等，故p=l/m；因此一个时隙内有一个标签的概率为：



在一个读周期内，一个时隙内只有一个标签的总时隙数(有效时隙数)为：



定义系统的吞吐率(即有效时隙数占总时隙数的比率)：



(6)式说明效率E取决于时隙数m和标签数n。令dE/dn=0，可以得到吞吐率最佳时，m．n须满足的条件：



当m，n满足(7)时系统吞吐率最大，因此我们可以根据标签数量n动态调整时隙数m。下面的关键问题就是怎样提前估计动态标签数量n。
我们知道时隙只有三种状态：空闲状态(无标签进入该时隙)、发送状态(只有一个标签进入该时隙)和碰撞状态(多个标签进入该时隙)。下面分别用Psuc，Pjuc，Pcoll表示。



为了估计标签数量，我们引入碰撞率Cr：碰撞的时隙数目与帧长度的比值。



经过一个读周期后，可以知道当前帧长度和碰撞率Cr，把m和Cr代A(11)就可以得到标签数量n。

5 动态帧时隙Aloha算法仿真及结

按照ISO／IEC 18000-6帧的结构，假定帧的长度为32bit,分别对帧长为128、256的FSA及DFSA的识别时间用matlab进行仿真。并让标签数量从0到800变化。



从图7我们可以看到当标签数量较少时，该算法没有明显的优越性。但随着标签数目的增多其识别时间与标签数量近似线形变化。因此该算法实现简单，尤其是大量标签的场合，具有良好的动态特性，在大规模的商业配送中有一定的实用价值。

6 结束语

本文针对射频识别系统中存在的关键性问题一防捧撞问题进行了研究，提出一种改进的动态ALOHA算法，有一定的创新性，并通过仿真，达到了较为满意的效果。由于缺乏大量的实际检验数据，算法的实际效果还有待在实际应用中进一步的检验。

本文作者创新点：通过对射频识别系统防碰撞算法的研究，提出一种改进的Aolha算法，通过提前估计标签数量，调整帧长度使系统效率最佳，改善了Aloha算法不能适用于大规模标签的场合。

作者：万红    来源：《微计算机信息》2009年第25卷