一种改进的分组帧时隙ALOHA算法

管小卫，傅 伟，蒋道霞

GUAN Xiao-wei, FU Wei, JIANG Dao-xia

(江苏财经职业技术学院 计算机技术与艺术设计系，淮安 223003)

0 引言

射频识别（RFID）是一种非接触式自动识别技术。一个RFID系统[1]由阅读器和标签构成，现已广泛应用在防伪防盗、物流管理、交通管理等多个领域。在汽车防盗定位系统中，给每个汽车安装一个标签，当汽车进入识别区时，若多个标签同时响应阅读器发送的查询信息，标签之间必然发生碰撞。为了解决多标签碰撞问题，系统需要采用相应的防碰撞算法来解决。目前解决多标签冲突问题的算法都是基于时分多址（TDMA）技术，主要有两种类型的防碰撞算法：一种是基于二进制树结构的确定性算法[2～4]，这类算法主要通过递归方法将冲突的标签分成两个子集，逐渐缩小范围，直到能正确识别出标签。但该类防碰撞算法需要阅读器准确的检测出发生数据碰撞的比特位置。另一种是基于ALOHA的不确定性算法[5,6]，这类算法的缺点是时隙浪费、吞吐量低。

由于汽车进入阅读器识别区的时间较短，且在不同的时间段车流量有较大变化，若采用帧时隙ALOHA算法，当汽车数量较少时将造成时隙浪费，在汽车数量远大于时隙数时，碰撞概率增加，系统的识别率将急剧下降。对于分组帧时隙ALOHA算法的研究，S.R.Lee[7]等人提出的分组帧时隙ALOHA算法是将帧长设为最大，当标签数量大于最大帧长时再将标签分组，在标签数量较少时造成时隙浪费；尹君[8]等人提出了基于分组动态帧时隙的RFID防碰撞算法，根据标签距离阅读器的距离将标签分组，需在标签内加入晶体管，提高了标签的复杂度和成本；张学军[9]等人提出的基于标签识别码分组的连续识别防碰撞算法研究是基于标签编码分组的二进制树结构确定性防碰撞算法；苏恒阳[10]等人提出的改进的动态时隙自适应条件的方法将标签分组，但在分组前需确定标签数，阅读器需对标签数进行评估。在本系统中，标签先进入阅读器识别区一般也先离开，因此可采用先到先识别的方式，将标签按照进入识别区的时间进行分组，先识别最先进入识别区的组，以提高标签识别率。基于上述分析，本文提出了一种基于时间段分组的帧时隙ALOHA算法，仿真结果表明,本方法能有效提高系统的吞吐量，减少时隙浪费。

1 ALOHA防碰撞算法分析研究

1.1 经典ALOHA算法

图1 经典ALOHA算法模拟图

在经典ALOHA算法中，当标签进入阅读器识别区后，标签自动向阅读器发送自己的ID，如果在此时间段内没有其他标签发送ID到阅读器，那么阅读器就能正确识别此标签，否则将不能正确识别，产生冲突。当冲突发生时，阅读器将发送一条命令让所有的标签停止当前的发送，等待一个随机的时间后重发自己的ID，直到所有标签被正确识别后，整个循环才停止。经典ALOHA算法思想简单，随机性大，冲突率高，如图1所示，当标签2和标签3发送自己ID时，由于时间间隔小于T0，就发生冲突，信道利用率较低，吞吐率最大约为18.4%。

1.2 时隙ALOHA算法

时隙ALOHA算法是在经典ALOHA算法基础上的扩展，改进的思想是将时间分成多个离散的时隙，且每个时隙大于标签响应的时间长度，标签只能在每个时隙起始发送数据，阅读器控制在同步时隙内传送数据。由于时隙ALOHA算法数据帧固定，不能根据实际标签数量来调整帧的大小，所以只有在标签较少时，性能表现良好，标签数量增多时，系统性能急剧恶化，系统性能不稳定。与经典ALOHA算法相比，信道利用率理论上能提高一倍，吞吐率最大约为36.8%。

1.3 静态帧时隙ALOHA算法

帧时隙ALOHA算法是在时隙ALOHA算法基础上的改进，阅读器将一帧分成N个时隙，每个时隙的长度大于标签的响应时间。标签接到阅读器的请求信号后，在N个时隙中随机选择一个时隙通信。该方法需要阅读器和标签之间的同步操作，并且帧的最大时隙数N预先设定。该算法适用于传输数据量较大的场合，当标签数远大于阅读器的帧时隙数时，在帧周期内会频繁发生标签碰撞，识别标签的时间将会大大增加，当标签数远小于阅读器的帧时隙数时，会造成时隙的浪费，当标签数和阅读器的帧时隙数时相等时，系统的吞吐率最大。

1.4 动态帧时隙ALOHA算法

动态帧时隙ALOHA算法是基于静态帧时隙ALOHA算法的改进，它根据标签数和时隙数等信息来动态调整帧长度，从而克服静态帧时隙ALOHA算法的缺点。当标签数大于时隙数时，通过加大帧长度来较少碰撞；当标签数小于时隙数时，则会减小帧长度，从而避免时隙浪费。动态帧时隙ALOHA算法能提高标签的识别率，但是由于硬件条件的限制，不能无限增加帧长度（通常一帧不超过256个时隙）。因此，当标签数量较大时，帧长度也随之变大，增加系统的工作负担。

2 基于时间段分组的帧时隙ALOHA算法

2.1 算法的基本思想

首先根据标签进入阅读器识别区的时间顺序将标签分组，然后再利用帧时隙ALOHA算法对组内的标签进行识别。算法的标签分组机制如图2所示。

图2 标签分组机制

每个标签分配一个时间分组计数器，阅读器每隔时间分组周期T向识别区内的标签群发送时间分组指令，在此时间段内到达的所有标签具有相同的时间分组值。标签的时间分组值初始化为0，每收到一次分组指令后所有时间分组值都加1。因此，时间分组值越大表示标签越先进入识别区，所以阅读器先识别时间分组值最大的标签群。

2.2 最佳帧长度

令一帧的时隙数为L，标签总数为n，有x个标签选择同一时隙的概率P为：

在一帧的识别周期后，成功识别标签的时隙数期望值为：

规定系统的吞吐率为：

本文提出的基于时间段分组的帧时隙ALOHA算法中，首先根据标签进入阅读器识别区的时间顺序将标签分成N组，然后再利用帧时隙ALOHA算法对组内的标签进行识别。由以上公式可得，分组后系统的吞吐率S为：

对式（4）求导：

令式（5）值为0，通过解上述方程式，可得出最佳帧长度为：

当n很大时，通过泰勒级数简化式（6）得：

由以上公式可知，当每个分组的标签数与帧长度大约相等时，在一个识别周期内能识别的标签数最多，即系统获得最大吞吐率。当车速在40km/h～60km/h时，阅读器识别区内的车辆数约为200，一辆汽车从进入识别区到离开一般为10秒，可设时间分组周期T的值为2秒（当车速提高时，可通过适当减小T的值来减少组内的标签数），将车辆近似均分为5组，每组标签数量在25～45之间，所以本文帧长度设为32。

2.3 算法的实现流程

在如图3所示的算法实现流程图中，首先阅读器的时间段命令参数R的值初始化为1；标签未进入阅读器识别区时，标签时间段分组数D的值初始化为0，进入识别区后，每接收一次时间段分组指令后值都加1；然后，阅读器发送激活信号，将其识别区内时间段分组数与时间段命令参数相等的标签激活，激活的标签采用ALOHA算法传送信息，步骤如下：

图3 基于时间段分组的帧时隙ALOHA算法实现流程

1）首批进入阅读器识别区的标签若无发生碰撞（全部给出应答信号），即被激活，则R值仍为1；若标签碰撞，即在一个时间段分组周期内无法识别所有标签，则R值加1，转步骤2）执行。

2）标签继续接收阅读器分组指令，在上个时间段分组周期内未被识别的标签D值加1，若仍与R值相等，标签继续发送应答信号；在一个时间段分组周期内无发生标签碰撞，R值减1，阅读器发送激活信号，将D=R的标签激活后继续识别标签。若上一个时间段分组周期里有未被识别的标签，那么新进入识别区的标签时间分组值D加1，但不接收激活信号，直到其时间段分组值D与时间段命令参数R相等时才接收激活信号。

最后，阅读器向已识别的标签发送去激活信号，标签不再接收激活信号，等待一定的时间之后，将时间段分组数D设置为0，可再次接收阅读器发生的激活信号；未识别的标签，若在连续两个分组周期内没有接收到时间段分组指令，则将时间段分组数D设置为0。

3 仿真分析研究

在汽车防盗定位系统中，汽车标签数量一般在100～250之间，假设汽车在阅读器识别区内的停留时间为10秒，将阅读器的时间段分组周期设置为2秒，识别区内的标签被近似均分为5组，每组标签数量在25～45之间，帧长度L的取值按2的幂次方递增，标签数与不同帧长度和分组数具体设定值如表1所示。

表1 标签数与不同帧长度和分组数

为了验证本文的提出的算法性能，分析标签数n、帧长度L以及分组时在不同取值系统的吞吐率，这里取值为0～300，利用MATLAB对算法的设计和性能进行仿真和分析。

图4 采用不同的帧长度时系统吞吐率比较

帧长度L取不同值时系统吞吐率的仿真结果如图4所示。当帧长度L=16，标签数n在50-100之间时，系统获得较高吞吐率；同时，随着标签数量的增加，若不进行分组，系统的吞吐率会急剧下降。本系统中每组标签数量在25～45之间，与32相近，所以取帧长度L=32，系统的吞吐率最高，且比较稳定，与推导的最优帧长度相符。

本算法是对帧时隙ALOHA算法的一种改进，所以分别与帧长度为128和256的帧时隙ALOHA算法进行比较，仿真结果如图5所示。

图5 两种算法吞吐率比较

仿真结果表明，基于时间段分组的帧时隙ALOHA算法在标签数量n在100～250之间时系统的吞吐率最优且稳定；当标签数量n在130～210时，优于帧时隙ALOHA算法，车速在60km/h～80km/h时，本算法优于帧时隙ALOHA算法，具有明显的性能优势，有效地提高了系统的吞吐率。

4 结论

针对汽车防盗定位系统，本文对帧时隙ALOHA算法做了改进，根据标签进入阅读器识别区的时间顺序将标签进行分组，提出一种基于时间段分组的帧时隙ALOHA防碰撞算法。仿真结果表明：在一个阅读器识别区内车辆数量在100～250之间，采用本算法具有明显的优势，系统的吞吐率最优且稳定，大大提高了汽车标签的识别率。

[1]周晓光,王晓华,王伟.射频识别（RFID）系统设计.仿真与应用[M].北京:人民邮电出版社,2008:119-135.

[2]Myung J,Lee W,Srivastava J.Adaptive Binary Splitting for Efficient RFID Tag Anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.

[3]Kim S H,Park P G An Efficient Tree-based Tag Anticollision Protocol for RFID Systems[J].IEEE Trans,on Letters,2007,11(5):449-451.

[4]Lai Yuan-Cheng, Lin Chih-Chung. A Pair-resolution Blocking Algorithm on Adaptive Binary Splitting for RFID System[J].IEEE Communications Letters,2008,12(6):432-434.

[5]孟淑玲.射频识别系统中防冲突算法的研究[D].天津.2008.5.

[6]LEE D,CHOI J,LEE W,et al.A time-optimal anticollision algo-rithm for FSA-based RFID systems[J].ETRI Journal,2011,33(3):458-461.

[7]S.R.Lee,S.D.Joo,C.W.Lee. An enhance dynamic framed slotted ALOHA algorithm for RFID tag identification[J].Mobile and Ubiquitous Systems:Networking and Services,MobiQuitous Jul.2005:166-172.

[8]尹君,何怡刚,李兵,邓晓,谭阳红,肖迎群.基于分组动态帧时隙的RFID防碰撞算法[J].计算机工程,2009,35(20):267-269.

[9]张学军,王娟等,王锁萍.基于标签识别码分组的连续识别防碰撞算法研究[J].电子与信息学报.2011,(05).

[10]苏恒阳,谭英丽.改进的RFID动态帧时隙ALOHA算法[J].计算机仿真,2011,28(8):148-152.DOI:10.3969/j.issn.1006-9348.2011.08.036.