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

孙 笠

（北京邮电大学国际学院物联网工程 北京 100876）

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

孙 笠

（北京邮电大学国际学院物联网工程 北京 100876）

引言

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

1.防冲撞算法介绍

1.1 ALOHA算法

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

1.2 帧时隙ALOHA

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

1.3 动态帧时隙ALOHA算法

目前，主要有以下三种估计标签数的方法。第一种是利用切比雪夫不等式估计标签数目。

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

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

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

2.改进的算法

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

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

其中，aN,n 1表示只有一个标签占据一个时隙的时隙总数。其中帧长度为N，标签总数为n。系统效率为PN：

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

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

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

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

以上推导证明：当待识别标签数与帧长度基本相当时，系统吞吐率最大，即一个帧长度识别周期中能够成功识别的标签数最多。

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

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

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

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

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

3 仿真结果分析

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

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