一种改进的RFID防碰撞时隙ALOHA算法

马翠红，赵 跃，杨友良，孟凡伟

(河北联合大学，河北唐山063009)

0 引言

目前有多种防碰撞算法，主要分为ALOHA算法和树形分解算法。由于树形分解法有时会使某些标签的识别延迟可能比较长，所以ALOHA算法因具有简单易实现等优点而成为应用最广的算法之一。文中将对ALOHA算法进行详细研究，并针对如何降低识别冲突标签时延和减少标签碰撞次数方面进行改进，从而提高识别效率。

1 防冲撞算法介绍

1.1 Aloha算法

在Aloha算法中当标签进入读写器范围时，电子标签自动地向读写器广播自己的ID(即唯一标识自身的数据，一般情况下为定长)，在发送数据时如果有其他的标签也在发送数据，那么将会发生信号冲突，读写器将不能正确地识别标签的ID号。读写器在检查到信号冲突时，将发送一个停止发送信号的命令让所有标签停止当前发送并随机等待一个时间后再发送自己信息。纯Aloha算法较简单、易实现，但标签之间发生信号冲突的概率很大，系统的识别率较低。

图1 FSA算法的信息帧时分多址

1.2 帧时隙ALOHA

帧时隙ALOHA(Framed Slotted ALOHA，FSA)算法是一种随机时分多址方式的用户信息通信收发算法。FSA算法的信息帧时分多址如图1所示。

该算法将信道用信息帧表示，其中，帧是指由阅读器要求的包含若干时隙的时间间隔。信息帧可以分成多个时隙，其中，时隙是指标签发送自身标识的时间长度。当一个时隙只被一个标签占有时，阅读器才会正确识别该标签，而当一个时隙内有2个或2个以上标签时，会发生碰撞，读写器无法正确识别，若时隙为空则跳过。如此循环，至到所有的标签都被识别。帧的大小是固定的，所以如果在某一时刻标签的个数远大于帧中时隙的个数，则在一个帧中发生碰撞的几率将被提高，被浪费的时隙也将增多，从而延长了识别所有标签的时间。［1-2］

1.3 动态帧时隙ALOHA算法

为使系统效率最优，提出动态帧时隙ALOHA(Dynamic Framed Slotted ALOHA，DFSA)算法，使得帧时隙数等于参与循环的标签数。DFSA每帧时隙数可以根据标签数的变化及时调整，使得标签数量与帧时隙数匹配。在开始新一个帧循环时，读写器要对参与帧循环的标签数进行估计，这个过程在整个算法中发挥着重要的作用。如果所估计的标签数与实际情况相差甚远，那么算法的效率就会发生大幅的下降，这样就影响了系统的稳定性。

目前，主要有以下三种估计标签数的方法。

第一种是利用切比雪夫不等式估计标签数目。

第二种方法是基于时隙二项分布来估计标签数。假设N代表当前帧的长度，n表示标签数。标签选择各个时隙数是等概率的，同一个时隙内出现r个标签的概率，根据二项分布原理得:

A：我生孩子的时候是在国内生的。因为顺产，我在医院住了三天就出院了，当时生孩子的时候是5月份，但是天气已经很热了，所以家里一直保持着恒温24摄氏度。我并没有坐月子，孩子也在出生7天左右就带他出门晒太阳了。很多国外妈妈生产后一周就上班了，他们没有坐月子一说。

第三种方法是在发生冲突时，一个时隙中至少有两个标签发生碰撞。标签的估计函数为:

N代表当前帧的长度，c0表示空闲时隙，c1表示成功时隙，ck表示碰撞时隙数。当冲突较频繁时，这种估计方法的相对估计误差较大，但具有方法简单等优点。［3-4］

2 改进的算法

分组动态帧时隙的ALOHA算法是在DFSA算法的基础上提出的，针对大规模标签进行快速识别的一种改进型算法。此算法很好地改善了标签识读效率问题，即使有大量标签同时存在，该算法也能线性地增加请求时间来识读标签。

2.1 算法分析及数学模型

在帧时隙ALOHA算法中，随着标签个数的增加，系统的吞吐率呈下降趋势。假设时隙数N，标签总数为n，根据统计学的原理，有r个标签选择1个时隙的概率为

当r=1时，表示一个时隙只有一个标签，即成功读取的时隙。因此，在一个阅读周期中读取标签数的期望值为:

当我们要想获得最大效率时，使得:

根据上式可推出当帧的长度为N时，效率最高的标签响应数为:

当标签数为n时，帧长度的最佳值为:

当n很大时，将上式泰勒尔展开:

图2 标签数目与吞吐率的关系

以上推导证明:当待识别标签数与帧长度基本相当时，系统吞吐率最大，即一个帧长度识别周期中能够成功识别的标签数最多。图2给出了L取不同值时系统效率的仿真结果。

另一方面，读写器能设定的时隙数通常是定值，如1，8，16，32，64，128，256。因此，读写器根据上一轮识别过程结束后，剩余未识别标签个数中选择 1个数作为下一帧的长度，具体选择标准:当碰撞的时隙数高于70%的总时隙数时，下一帧长度加倍;当空时隙数高于30%的总时隙数时，下一帧长度减半;当到来的标签数n急剧增加，而一帧的时隙数不可能无限增加时，用下式将标签分成M组，只允许一组标签相应请求命令，以使系统仍能工作在最大吞吐量下:

M=n/Nmax，式中Nmax为读写器能分配的最大时隙，这里取256。

表1显示了未识别标签个数与最佳帧长下分组的个数的关系。

表1 未识别标签个数对应的帧长度和分组情况

文中介绍了三种标签的估算方法，为减小RFID系统的复杂性，使用n=c1+2ck估计函数来确定标签数量。得到n值后，由式计算出M值，若M=0，则对标签进行分组;若M≠0，则不分组。

3 仿真结果分析

仿真实验采用Matlab 7平台，记录标签数从0到1 000递增变化时的系统效率和读取标签所花时间(用读取标签所用的总时隙数来衡量)，对改进算法、动态帧时隙ALOHA算法、固定帧时隙的ALOHA算法三者进行比较。初始时，动态帧时隙ALOHA和改进算法帧长度都是8，而固定帧时隙ALOHA的帧长度即为允许的最大帧长256.从图3可见，改进的动态帧时隙ALOHA算法在标签数量大于500时，仍能以35%上下的吞吐量工作，而固定时隙的ALOHA算法性能则急剧恶化.在图4中，固定帧时隙的ALOHA算法需要最多时间;改进算法需要最少的时间，在大量标签的情况下，具有明显的优势，当标签数量增加到1000左右时，所用时间与前者相比几乎减少了一半;动态帧时隙的ALOHA算法在标签数量较少时(小于500)，性能与改进算法接近，但是在标签总数超过500以后，所需的时隙数大量增加，几乎没有时间上的优势。

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

图4 标签数目与时隙数的关系

仿真结果显示改进算法在标签数量很大时，吞吐量可提高100%，标签读取时间下降近50%.因此，这种算法对于短时间需要读取大量标签的实时RFID系统具有良好的适用性。

［1］ Finkenzeller K.射频识别技术［M］.3版.吴晓峰，陈大才，译.北京:电子工业出版社，2006.

［2］ 陆端，等.改进ALOHA算法在RFID多目标识别中的应用［J］.微计算机信息，2006，22(11).

［3］ 徐圆圆，刘禹.基于Aloha算法的帧长及分组数改进研究［J］.计算机应用，2008，28(3):588－590.

［4］ Vogt H.Multiple object identification with passive RFID tags［M］.IEEE International Conference on Systems，Man and Cybernet－ics.Tunisia: IEEE Press，2002.

［5］ LEE SR，JOO SD，LEE CW.An enhanced dynamicframed slotted ALOHA algorithm for RFID tagidentification.IEEE Computer Society，2005［C］.