基于分组动态帧时隙ALOHA防碰撞算法研究

2013-10-31宋瑞玲高仲合

通信技术 2013年7期

宋瑞玲，高仲合

（曲阜师范大学计算机科学学院，山东日照 276826）

0 引言

射频识别（RFID，Radio Frequency Identification）是一种使用射频通信实现的非接触式自动识别技术[1]。根据射频耦合方式的不同[2]，RFID可以分为电感耦合方式和反向散射耦合方式，根据供电方式的不同，标签又可以分为主动式标签和被动式标签。典型的RFID系统主要由标签（Tag）、阅读器（Reader）和天线（Antenna）3部分组成[3]，阅读器和电子标签之间信号传输是通过阅读器和电子标签上的天线耦合来完成的，信息交互通常是采用询问-问答的方式。目前，RFID技术由于其自身免接触、识别距离远、可以同时识别多个运动物体等优点而广泛应用于多个领域。

电子标签碰撞问题是指当阅读器向工作场区内的一组电子标签发出查询指令时，有2个或2个以上的电子标签同时响应阅读器的查询，返回信息产生相互干扰，从而导致阅读器不能正确识别其中任何一个电子标签的信息，为了解决这个问题，必须采用防碰撞算法。防碰撞算法一般采用时分多址方式，目前采用ALOHA算法和二进制搜索树型算法来解决读写器碰撞[4]。基于ALOHA的算法简单易行而被广泛应用。基于ALOHA算法有纯ALOHA算法、帧时隙 ALOHA算法、动态帧时隙 ALOHA算法[5]（DFSA，Dynamic Frame Slotted ALOHA Algorithm）分组的动态帧时隙 ALOHA算法[6]。本文介绍的算法是在分组的动态帧时隙 ALOHA算法的基础上提出来的。

1 多种防碰撞技术

1.1 纯ALOHA算法

纯ALOHA算法的思想很简单，即只要有数据待发，就可以发送，向阅读器发送数据是随机的，不需要同步，并且没有检测机制，虽然实现起来简单，但是发生碰撞的几率很大。所以纯ALOHA算法的信道利用率不高，吞吐率最大约18.4%。

1.2 时隙ALOHA算法

时隙算法是在纯 ALOAH算法的基础上改进的，时隙ALOHA算法是将时间分为多个离散时隙，标签只能在时隙的起始发送数据，这种算法必须有全局的时间同步。该算法相比于纯ALOHA算法，信道利用率理论上能提高一倍。但是，该算法只是在电子标签较少时，才能表现出较好的性能，在标签数增多时系统性能会急剧恶化。系统的吞吐率 S和帧产生率G的关系如图1所示。

图1 纯ALOHA和时隙的ALOHA算法吞吐率

由图1可以看到纯ALOHA算法当G=0.5时吞吐率S达到最大约是18.4%，时隙ALOHA算法当G=1时吞吐率最大约36.8%。

1.3 帧时隙ALOHA算法

帧时隙ALOHA算法是在时隙ALOHA算法的基础上提出的，将N个时隙组成一帧，标签在N个时隙中随机选择一个时隙发送信息。帧时隙要求阅读器和标签数之间的同步操作，并且每帧的最大时隙数N需要预先设定。读写器附近所有标签服从相同的统计规律，且在同一帧的标签机会均等，则 r个标签出现在某个给定时隙概率服从二项分布。

令一帧的时隙数为N，标签数为n,则有r个标签发生在某一时隙的概率是:

某个时隙中只有一个标签发生的概率为:

则所有标签中被成功读取的标签数为:

系统的吞吐率:

对式（4）求导数，得出到:

所以当阅读器的帧时隙数跟标签数目相等时，系统吞吐率最大。N的不同取值对应的系统吞吐率如图2所示。

图2 不同帧长对应吞吐率

1.4 动态帧时隙ALOHA算法（DFSA）

由式（5）知帧长和标签数相等时系统吞吐率最大，但是帧时隙ALOHA算法由于帧长固定会出现标签数量和帧长不均衡问题，问了解决这个问题，出现了动态帧时隙ALOHA算法，它的思想是根据前一阵的读取结果动态减少或增加下一帧的时隙数。

有一点值得注意，就是阅读器设定的帧时隙数是定值[7]，如 1、8、16、32、64、128、256。所以我们经常根据上一轮估算未识读的标签数以如下方法来确定下一帧长，如表1所示。

表1 不同标签个数对应帧长度

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

2.1 分组动态帧时隙算法

在动态帧时隙算法中，由于硬件的限制，帧长并不能无限的增大，目前所允许的最大帧长一般不大于256。如果标签数量增加到远远大于256时，由图2可以看到系统吞吐率明显在下降。分组动态帧时隙算法思想是先估算未读标签的数量[8]，如果标签数小于256，直接利用动态帧时隙算法使帧长度尽可能的接近标签数；如果大于256就把要识读的标签先分组,每次只识别其中的一组，从而改善标签过多系统吞吐率下降的问题。

2.2 算法思想

传统的分组算法，阅读器把标签分成若干组，然后一组一组地将标签识别出来，在每一组中阅读器必须不断的调整帧的长度，直到这一组的标签被全部识别。

本文改进算法的思路:

1）阅读器估读待识别的标签数目N，阅读器发送包含此标签数目信息的Detect指令。

2）如果 N>256的话，这里帧长取最大帧长度256，转到步骤3；否则依据表1确定帧长度，直接响应，然后转到步骤4。

3）每个标签从1-N中随机的选择一个数字载入时隙计数器，然后数字小于等于256的数字去响应相应的阅读器时隙，大于256的暂时不响应（可以看成是分成两组，小于等于256的一组，大于256是一组）。

4）统计该识别周期中一共正确识别的标签数Nr，用N减去Nr得出未识别的标签数目（N=N-Nr），如果未识别的标签数为零，说明全部识别，否则跳到步骤2。

算法流程图如图3所示。

图3 算法流程

2.3 仿真结果

利用Matlab仿真平台，最大帧长度取得是256，仿真结果如图4、图5 所示。图4记录标签在0～1000变化时，改进后的动态帧时隙ALOHA算法所消耗的时隙数，并和动态帧时隙ALOHA算法，分组的动态帧时隙ALOHA算法作了对比。可以看出当标签数量大时改进后的算法有明显优势。图5仿真了改进后分组动态帧时隙ALOHA算法系统吞吐率，可见在此算法中，系统吞吐率随标签数量的增多几乎不变，一直稳定在36%附近。