一种新型的RFID的防碰撞算法

于洪涛，王祖良，王少飞，曹闯乐，马可欣

（西京学院，陕西 西安 710123）

0 引 言

在现代科技不断快速发展下，自动识别系统越来越受到人们的青睐。射频识别（Radio Frequency Identification,RFID）是一种近距离无线电通信技术，具有成本低廉、传输速度快且可以对多个目标进行响应识别的特点，其作为一种自动识别技术已被广泛应用在商品识别和数据采集等各个领域[1]。因此，对RFID的防碰撞算法的研究对提高系统的信道利用率具有重要意义。RFID系统由阅读器、射频标签和天线组成。其原理是：阅读器首先通过自身携带或外置的天线源源不断地发送无线电信号，当标签放进属于天线的作业范围之内时，它通过电感耦合和电磁反向散射耦合产生能量，使标签获得能量传递本身数据信息，阅读器携带的数据编码等信息通过内置天线发送出去[2]，接收天线接收标签发送的载波信号对其进行解调和解码，然后将其发送回计算机系统进行相关处理[3]。标签可以说是RFID系统中的重要组成部分之一，原因是它内部存储着自身的数据信息，但是，在数据识别和传输的过程中，它受到很多方面的干扰，导致数据识别和传输的质量和效率较低。一般来说，造成这种现象的主要原因是，各种阅读器和标签中存在的外部干扰因素是同时存在的，因此很容易在数据信息传输通道中发生冲突，导致质量和效率低下。为了解决这个问题，本文提出了防冲突算法。

根据标签的响应方式，防冲突算法通常分为不确定性算法和确定性算法两种。

在不确定性算法中主要为ALOHA算法。ALOHA算法的机制是标签源源不断地发送自身数据信息给阅读器，当发生冲突时，阅读器会下达命令阻止标签发送信号，此时，标签进入一个“待命”时间段，这个时间段也是随机的，“待命”时间结束，标签继续发送信号给阅读器。

确定性算法有二进制树算法，其机制是阅读器首先设置限制条件，只有满足条件的标签才可以发送信号并被阅读器识别。譬如有00和01两个标签，阅读器首先发送“0”比特串，然后将比特串“1”放进堆栈中，因为两个标签的首位都是0，所以同时响应阅读器从而产生碰撞。阅读器继续发送“00”比特串，并将“01”压入栈中，此时标签ID为“00”响应阅读器的请求，标签识别成功，接下来堆栈中的“01”标签被弹出，其作为请求比特串从而被成功识别。

1 ALOHA算法

1.1 纯ALOHA算法

当电子标签被放置到阅读器作业范围之中时，会将自身携带的数据信息发送给阅读器，但是此时若有其他标签也在向阅读器发送信号就会发生冲突，造成碰撞。在纯ALOHA算法中发生碰撞之后，阅读器会发出命令让标签停止发送信号给自身，进入一个不确定的“待命”时间段，标签只有在过了这个时间段之后才可以重新发送数据信息给阅读器，这个时间段的时间范围是不固定的，所以标签再次发送信号的时间也是随机的，这样就大大减小了碰撞的概率。

1.2 时隙ALOHA算法

时隙ALOHA算法与纯ALOHA算法不同的是，它将时间段分为多个离散可等帧长也可不等帧长的时隙[4]，这些时隙由阅读器分配，且每个标签都必须在所分配时隙的开始处传递自己的信息。因此，时隙ALOHA算法是一种随机查询驱动的TDMA防冲突算法。因为标签只能在阅读器分配的时隙中传输数据，即要么标签成功识别，要么发生碰撞，与纯ALOHA算法相比，减小了碰撞周期，标签被识别的成功率得到了显著增加。但是，时隙ALOHA算法在标签发生冲突之后，仍会通过随机时间延迟进行分发和重新传输数据。

1.3 动态帧时隙ALOHA算法

传统时隙ALOHA算法的帧长是固定的，一帧可以包含多个时隙，也就是说其时隙数也是确定的。那么即使当有大量的标签待被阅读器识别时，其时隙数也不会发生改变。这样就存在一个问题：当标签的基数很大时，若时隙数设置的很小就可能会造成碰撞；若标签为数不多，时隙数很大，又会造成时隙的多余，从而造成浪费[5]。动态帧时隙ALOHA算法成功解决了这个问题，它可以根据标签基数动态更改一个帧内的时隙数，当标签基数很大时，可以通过增加时隙数避免碰撞的发生。其具体算法推理如下：

假设F是帧长，N是系统要识别的全部标签数量，OVSF码长设为d，则在单个时隙中可以在d个OVSF码中检测到n个标签的概率为：

从式（8）可以看出，当设置的帧长与标签总数近似相等时，系统的信道利用率最高[6]，此时的吞吐量最大值为：

动态帧时隙ALOHA算法较时隙ALOHA算法的优点是：当标签基数很大时，仍能使信道利用率维持在36%，时隙ALOHA算法因其时隙数固定，所以当标签数量增大时，其发生碰撞的可能性会增加，信道利用率也会大幅度下降。

2 改进的动态帧时隙ALOHA算法

时隙ALOHA算法是一种随机查询驱动的TDMA防冲突算法，本文在运用TDMA技术的基础上，结合码分多址（CDMA）技术提出了一种新的帧时隙ALOHA算法，主要推导如下：

由式（3）可得系统的吞吐量，将d设为2，即OVSF码长为2时，吞吐量可表示为：

对N求导，令式子为零，可得：

当标签数量趋近于无穷大时，系统吞吐量为：

由式（12）可知，新型帧时隙ALOHA算法的吞吐率达到了将近84%，比原来的帧时隙ALOHA算法提升近2倍，可见这种算法能够更好地提高系统的信道利用率。

3 实验结果及分析

因纯ALOHA算法和时隙ALOHA算法在当网络负载即标签基数很大时，其吞吐量基本为零，所以对这4种算法两两进行分析。在图1中，可以看到纯ALOHA算法的吞吐量在16%左右，时隙ALOHA算法吞吐量为36%，吞吐量提高了近一倍。但这两种算法在标签基数很大时，吞吐量均急剧减小直至为零。从图2的实验结果可看出：动态帧时隙ALOHA算法吞吐量在标签基数很大时，依然可以维持36%的吞吐量，这是因为较帧时隙ALOHA算法，动态帧时隙ALOHA算法根据标签的总量实时动态修正更改帧长[7]，这样就大大减小了碰撞的概率。所以即使当标签的基数很大时，动态帧时隙算法依然可以保证有足够的时隙供标签选择，因此可以维持吞吐量保持稳定。新型动态帧时隙ALOHA算法在帧时隙算法的基础上进一步做了修改，将CDMA技术与TDMA技术相结合，从图2可以看出，吞吐量保持在84%左右，与帧时隙ALOHA算法相比提高了近2.3倍。这是因为新型动态帧时隙ALOHA算法在将时间分为离散的多个时隙后，又结合了CDMA，也就是在同一个时隙中可以识别两个标签[8]，摆脱了帧时隙ALOHA算法单个时隙只能识别单个标签的束缚[9]，大大减小了碰撞的概率，从而提高了系统的信道利用率。

图1 纯ALOHA算法和时隙ALOHA算法吞吐量仿真

图2 动态帧时隙和新型动态帧时隙ALOHA算法吞吐量仿真

4 结 语

本文在帧时隙ALOHA防碰撞算法的基础上提出了一种新的基于CDMA和TDMA技术相结合的防碰撞算法，该算法的吞吐量较改进之前的算法提高了近2.3倍，提高了系统的信道利用率[10]。实验结果证明，如果增加码长，系统的吞吐量可以不断增加，但是由于考虑到资源浪费和研发费用问题，不宜增加过多，要根据具体的标签基数选择码长，做到识别效率高且又不会浪费资源。