帧时隙ALOHA防碰撞算法仿真与研究

2012-12-20蔡增玉谭前进李娜娜

中原工学院学报 2012年6期

冯媛，蔡增玉，谭前进，李娜娜

（1.郑州轻工业学院，郑州450002；2.大连海洋大学经济管理学院，辽宁大连116023）

射频识别（RFID）是一种非接触式自动识别技术，它利用无线射频信号进行非接触双向通信，实现对特定物体的自动识别，具有识别距离远、抗干扰性强、可同时识别多个目标等优点，近年来得到了广泛应用［1］.当阅读器识别区域内存在多个标签时，如果它们同时向阅读器发送标识信息，阅读器无法同时识别这些标识信息，就产生了标签冲突，解决此冲突的方法称为防碰撞算法.标签防碰撞算法对于RFID系统的识别能力至关重要，是RFID系统的关键［2］.目前，高频段的防碰撞算法一般采用ALOHA协议以及改进的ALOHA算法.本文在对帧时隙ALOHA研究的基础上，实现了基于MATLAB的帧时隙ALOHA仿真算法，并研究了帧时隙ALOHA中标签数量、帧长度、识别时间、系统效率、系统负载等参数之间的关系，为相关应用系统的设计提供了参考.

1 帧时隙ALOHA算法分析

1.1 ALOHA算法

所有多路存取方法中，最简单的方法是纯ALOHA算法.纯ALOHA算法的基本原理是：当标签进入阅读器工作区域并被激活后，标签随机选择某个时间发送信息，阅读器根据接收到的信号判断其有无碰撞发生，若发生碰撞，则发送命令让标签停止发送，标签等待随机时间，再重新发送标签自身序列号，以减少碰撞［3］.当标签数目很少时，纯ALOHA算法能表现出良好的性能；但是，随着标签数目的增加，信道占有率增加到一定阈值后，其执行性能就变得相当差.纯ALOHA算法的优点是算法简单，易于理解和实现；缺点是冲突发生的概率很大［4］，存在错误判决问题.本文针对这些问题，提出了一些扩展的方法来改善识别算法在RFID系统中的可行性和有效性，其中比较典型的有时隙ALOHA算法、帧时隙ALOHA算法等.

1.2 帧时隙ALOHA算法

时隙ALOHA算法基于纯ALOHA算法，把识别时间分成多个时隙，被识别标签只能在时隙的开始传输数据.如果在一个时隙内有多个标签响应，阅读器就会检测多个标签的响应而产生冲突，这时阅读器通知标签在下一轮循环中重新选择时隙发送数据，直至所有的标签都被识别出来.这样，在一个时隙内，只能单个标签成功发送或多个标签发生冲突，避免了纯ALOHA算法的部分冲突的情况.因为标签只在确定的时隙中传输数据，所以该算法的冲突发生概率仅为纯ALOHA算法的一半，而系统的数据吞吐性能却增加一倍［5］.时隙ALOHA算法避免了纯ALOHA算法的部分冲突，提高了信道利用率.

帧时隙ALOHA算法是时隙ALOHA算法的扩展.帧时隙算法是将若干个时隙组合成一帧，标签选择某一帧中的某个时隙向读写器传输数据［5］.帧时隙ALOHA算法对系统要求较简单，识别速度较快，在很多国际和国内RFID标准中被采用.帧时隙ALOHA算法在阅读器发出读取命令后，等待标签应答：当一个时隙中仅有一个标签应答时，该标签被正确识别；当一个时隙中没有标签应答时，该时隙为空时隙；当一个时隙中有2个或2个以上的标签应答时，则发生冲突，该时隙中标签不能被识别，所有未被识别的标签需要重新选择时隙来应答，直到所有标签被识别.

1.3 帧时隙ALOHA算法理论分析

假设一帧含有N个时隙（为便于讨论，用N表示帧长），共有n个待检测的标签，每个标签以均等的概率1／N来随机选择一帧中的某个时隙发送数据，可以得到在一个时隙里有k个标签同时发送数据的概率服从二项分布，即：

在帧时隙ALOHA算法中，当在一个时隙内只发送一个标签数据时，标签才能被阅读器正确识别，所以在一个时隙内正确识别一个标签的概率为P（1）.每帧包含N个时隙，所以系统的吞吐率T（n，N）为：

T（n，N）＝一帧中识别出的标签数／当前帧的帧长＝N＊P（1）／N＝P（1）

通过数学运算可以推出，当N≥1，且n≈N时，系统吞吐率达到最大，为36.8%.

2 帧时隙ALOHA算法仿真分析

笔者进行了基于MATLAB的帧时隙ALOHA算法仿真，通过仿真模拟了帧时隙ALOHA算法的防碰撞过程.为了便于分析，设定读取一个RFID标签信息的时间等于一个时隙的时长.

2.1 标签数量对识别时间的影响

参数设定：时隙数固定为256，标签的数量从1个增加到1 000个，仿真次数为10次.统计得到系统中标签数量增加时识别所有标签所用的总时隙数量的变化情况，如图1所示.当系统中标签的数量较少时，识别所有标签的总用时较短，说明读写器识别率较高；识别时间增长比较缓慢，说明标签的成功识别率基本稳定；随着标签数量的增加，当标签数量超过300个后，识别所有标签的总时隙数以较大幅度增加，标签的成功识别率以较大幅度降低.

图1 标签数量与识别时间的关系图

仿真结论1：当标签数大于每帧的时隙数后，识别读写器范围内所有标签的总用时会随着标签数量的增加而显著增大.

2.2 帧长度对识别时间的影响

参数设定：标签的数量固定为30个，一帧中最大时隙数设为120，仿真次数为100次.统计在不同的最大时隙数量下识别30个标签的总用时的变化情况，得到标签数量和帧长度的对应关系，如图2所示.从图2可得出，当一帧中的时隙数小于10时，识别30个标签的总用时非常多；随着一帧中的时隙数的增加，识别所有标签的总用时急剧减少；当帧长度为12～20个时隙时，帧时隙ALOHA算法的性能最好，识别所有标签的总用时最短；当一帧中的时隙数从20增加到120时，识别所有标签的总用时增加.

图2 帧长度与识别时间的关系图

仿真结论2：当时隙数由远小于标签数逐渐变大时，系统识别所有标签所用的时间将会急剧减少；而在标签数远小于时隙数时，虽然多个标签发生冲突的次数将会减少，但是一帧中的时隙数相对较多，导致识别所有标签的总用时依然较多，从而造成时隙的浪费.因此，每帧的时隙数与标签数不宜相差太大.

2.3 系统效率和标签数的关系

一帧中时隙数固定为256，标签的数量固定为100～800个，仿真次数为10次.统计随着标签数量的增加系统效率的变化，得到标签数量和帧长度的对应关系，如图3所示.当系统中标签的数量较少（小于256个）时，系统效率较低；随着标签数量的增加，系统效率快速增长；当标签数量到达256个时，系统效率到达最大，为36%；当标签数量超过256个后，系统的效率缓慢下降.

图3 系统效率与标签数的关系图

仿真结论3：当标签数大于或小于每帧的时隙数时，系统的效率较低；当标签数等于每帧的时隙数时，系统的效率达到最大值，与前面理论分析相同.

2.4 系统负载与吞吐量

一帧中时隙数固定为64，系统负载从0增加到4，仿真次数为50次.统计随着系统负载的增加系统负载与吞吐量的对应关系，如图4所示.当系统负载小于0.5时，系统吞吐量较低；随着负载的增加，系统吞吐量快速增长；当系统负载在1附近时，系统吞吐量到达最大；当系统负载大于1时，随着系统负载的增加，吞吐量逐渐下降.