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

　　射频识别系统中，当读写器的读写范围内有多个标签同时存在时，这些标签几乎同时响应读写器的指令，从而产生碰撞，使得读写器不能正确接收标签返回的信号。为解决产生的碰撞问题，必需采取相应的防碰撞技术。然而，由于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算法

　　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)所示：

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

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

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

　　但是，随着帧长的不断调整，相应的估计误差值也会随之改变，虽然已经对系统效率做出了改进，但是仅仅用固定参数u对误差进行调整还是不能更好地动态显示当前帧情况。

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

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

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