RFID动态帧时隙防冲撞改进算法研究

陈春明,冯玉田，付良成

（上海大学 通信与信息工程学院，上海 200072）

射频识别系统中，当读写器的读写范围内有多个标签同时存在时，这些标签几乎同时响应读写器的指令，从而产生碰撞，使得读写器不能正确接收标签返回的信号。为解决产生的碰撞问题，必需采取相应的防碰撞技术。然而，由于RFID系统的特殊性，标签无源、存储能力有限并且不具有载波监听能力，防碰撞算法主要考虑系统的效率、能耗等问题。目前已有一些方法来解决标签碰撞[1]。其中比较关键的是如何用防碰撞算法快速和有效地将标签全部识别出来。纵观已有的标签防碰撞方法，主要分为基于树形的搜索防碰撞算法和基于ALOHA的算法[2]。树形算法主要通过遍历所有碰撞的节点，检测出碰撞后让它分成两个分支，直到检测到所有标签的ID都不存在碰撞便识别完成[3]。基于ALOHA的一类算法在RFID系统中也得到了广泛的应用。ALOHA算法类主要分为纯ALOHA算法、时隙ALOHA算法和动态帧时隙ALOHA[4]。动态帧时隙最大的特点是帧的长度可根据标签的具体情况而改变，从而保证效率的最大化。

1 动态帧时隙ALOHA的防碰撞算法分析

ALOHA类算法最初是从纯ALOHA算法，标签发送数据遇到碰撞则延时发送，系统效率最大能到18.4%。后来将发送时间离散化,分成若干时隙，在各时隙内发送数据也即时隙ALOHA算法，如此，因去掉了不完全碰撞，系统效率最高达到36.8%，而遇到大量标签时效率会急剧下降。之后改进得到帧时隙算法，在时隙算法的基础上将若干个时隙组成一帧，标签在与读写器通信时随机选择一个时隙发送数据，帧长度由读写器设定，该算法的理论最大效率也是36.8%，不过可以分成若干帧来识别所有标签。

1.1 动态帧时隙ALOHA算法

为使系统吞吐量达到最大，假设每一帧的时隙数目为M，还未读取的标签数为n。当一个时隙只有一个标签的应答时，读取标签成功。以概率论分布统计的构造成功率的数学模型，成功时隙的统计概率为: ,

其中ps为传输同路的吞吐率，M为一帧的时隙数 (帧长)，n为阅读器范围内未识别的标签数。固定n对M求导：

1.2 标签估计

目前已经出现了多种标签数目估计的方法，此类估计方法大都基于将各个时隙分为没有标签的空时隙，只有一个标签的独占时隙以及被两个或多个标签占用的碰撞时隙的模型设计。因为每个碰撞时隙至少有两个或两个以上的标签响应，假设前一帧检测下来有C个碰撞时隙，Lower bound method[5]则以每个碰撞时隙有最少的两个标签来估计，也即用N=2·C来估计阅读范围内未识别的标签数量。该算法的误差源于它只考虑了两个标签碰撞的有偏估计，在标签数量比较多的情况下效率很低。FRITS C.Schoute[6]在lowerbound基础上做了改进，考虑到每个时隙标签大于3个的情形。通过构造泊松过程分布函数，当标签数等于帧长的情况下得到N=2.39·C。即，用N=2.39·C来估计未识别的标签数量，该值比lowerbound算法更为准确，但只是静态估计不能动态反应当前帧碰撞情况。

Vogt[7]后来又提出一种不同的估计方法，根据切比雪夫不等式：一个涉及随机变量的随机试验过程其输出很可能在该变量的期望值附近。因此，可以用读取结果与期望值之间的取得最短距离时的数值来估计标签数目。估计模型如式(3)所示：

其中，c0、c1、ck为实际测得的成功、空闲、碰撞时隙数值。

在标签数量 N取值范围[c0+2ck,…,2(c1+2ck)]内找到最小的ε值，所对应的N就是估计的标签数量。

除此之外，还有基于Bayesian理论的后验概率估计方法[5],其系统效率有所提高但计算复杂度也变得很高。ISO-18000-6C标准中使用的Q算法[8]对系统的吞吐率作了一定的改进。但是，既然是估计算法就必然会存在估计误差，估计算法的效果影响着系统效率。为改善估计误差对系统效率的影响，本文提出了改进方法。

2 FBC_DFSA算法及其仿真

时隙帧识别法都涉及到标签估计，但这些估计算法显然都存在误差。因此，本文提出FBC_DFSA算法，用估计算法得到的标签数来设置帧长，在进行一轮识别后得到的测量结果反馈到前面估计得到的标签数目，与其进行对比，检验估计算法的准确性并做出调整。本算法的原理模型如图2所示。

首先看一下基于空闲时隙、成功时隙、碰撞时隙的一系列标签估计，假设n个标签在某个帧选择了其中第i个时隙的标签数目，概率分布为：

M为一帧内时隙数。如果该时隙为碰撞时隙,x≥2。得到x标签选择识别时隙的概率分布为:

可得到选择时隙i标签数目的平均值：

其实可以看到，当 e=2和e=2.39时，分别为 lowerbound和Schoute估计结果。Vogt方法是通过比较一个向量组中与期望值的距离来得到最佳标签数，Bayesian算法用后验概率分布来估计识别的标签数目。但是，基于向量空间的搜索法 (Vogt)和基于后验概率分布法(Bayesian)尽管在系统效率上有些改进，但是计算复杂度也比较大[9]。如图3算法模型，基于lowerbound和Schoute的标签估计DFSA方法来验证FBC_DFSA算法。值也会随之改变，虽然已经对系统效率做出了改进，但是仅仅用固定参数u对误差进行调整还是不能更好地动态显示当前帧情况。

因此，本文尝试用一个随误差改变而自动调整的动态变量来代替u，提出了动态反馈调整动态帧时隙算法DFBC_DFSA。以下实验选择了用动态调整参数α|F1-F0|来代替u进行算法的仿真，其中，F1为后来计算的测量帧长，F0为之前估计的帧长，α则是调整因子。当α=1

图3 FBC_DFSA算法模型

基于FBC-DFSA算法模型，再结合蒙特卡洛法的思路建立了模拟标签识别的数学模型，并在MATLAB的环境下进行了仿真实验，图4给出了采用Lowerbound、Schoute以及FBC_DFSA算法时系统效率的仿真结果。

从结果可以看到，在绝大多数标签情况下，FBC方法的系统吞吐率都要好于其他算法。

FBC_DFSA在标签数接近帧长大小处还是能取得吞吐率的最大值，在标签数不等于帧长的情况下，能够对误差做出调整，从而也可以进一步提高系统效率。但是反观FBC_DFSA算法模型，可以看到一个比较关键的调整参数u，u参数决定了检测估计结果与当前检测结果之间的误差调整幅度。因此，u的大小会影响整个系统的识别效率。设定初始帧长之后，在MATLAB软件环境下进行仿真实验，实验部分结果如图5所示。可以发现，在初始帧长固定的情况下，当标签数改变时，改变参数u能够相应地影响系统效率。

但是，随着帧长的不断调整，相应的估计误差时，得到结果如图6所示。

可以看到，此时尽管在某些标签数量情况下，DFBC方法的效率不及固定参数u的FBC效率，但是从整体效果上看，特别是当标签数目大于1 000后，DFBC方法的效率都有所提高，几乎都能围绕在0.35左右，系统的吐率表现更加稳定。

理论上讲，在识别帧长与未识别的标签数相近时，系统的效率能达到最高，但是如何得到当前阅读范围内的标签数目便成了一个极为重要的问题。本文分析了一系列的标签估计算法后，考虑到标签估计算法的估计误差问题,为有效地减小估计误差并对识别帧长做出调整，提出了一种基于上述改进思路的新方法，也即FBC和DFBC动态帧时隙防碰撞算法。通过检测后的反馈数据与之前的估计帧长作对比，可以动态地描述和调整相应的帧长。从系统效率的仿真实验中看出，改进算法在不增加过多的计算复杂度的情况下使系统效率得到了相应的提高。而且本算法的机理可以拓展到基于其他标签估计的动态帧时隙算法上去(像Vogt、Bayesian等)。基于FBC/DFBC的算法也能够较为方便地应用到具体的RFID系统通信协议中去，从而在工程上真正改善RFID系统的效率。

[1]FINKENZELLER K.RFID Handbook[C].Radio-Frequency Identifications Fundamentals and Applications,2nd ed.New York:wiley,2003.

[2]MYUNG J,LEE W,SRIVASTAVA J,Adaptive binary splitting for efficient RFID tag anti-collision[J].IEEE Commun.Left,2006,10(3):144-146.

[3]Bai Chengsen,Zhu Jiang.Research on an RFID anti-collision improved algorithm based on binary search[J].International Conference on Computer Application and System Modelling(ICCASM),2010(6):430-432.

[4]程良伦，林伟勇.一种稳定高效的动态帧时隙ALOHA算法[J].计算机应用研究，2009，26(1)：85-91.

[5]FLOERKEMEIER C.Transmission control scheme for fast RFID object identification[C].IEEE International Conference on Pervasive Computing and Communications Workshops(PERCOMW),2006.

[6]SCHOUTE F C.Dynamic frame length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[7]VOGT H.Efficient object identification with passive RFID tags[C].in Proc.Int.Conf.Pervasive Computing,2002:98-113.

[8]韩振伟,宋克非.射频识别防碰撞Q算法的分析与改进[J].计算机工程与设计，2011,32(7),2313-2318.

[9]Wu Haifeng,Zeng Yu.Tag estimate and frame length for dynamic frame slotted ALOHA anti-collision RFID system[J].Acta Automatic SINCA,2010,36(4):620-624.