UHF频段RFID系统防碰撞算法研究

摘要：防碰撞技术是决定RFID系统性能的关键因素之一,特别是UHF频段,防碰撞性能决定着多目标的识别率、识别速度。本文着重研究UHF频段RFID系统防碰撞解决方案和算法改进题目,探讨盘存周期内总时隙数的选取,并对系统效率进行仿真,提出简单易行的进步系统效率的方法。

1 引言

射频识别技术(RFID，Radio Frequency Identification)是一种非接触的自动识别技术，与条形码识别相比，具有识别间隔长、无需人工干预、存储容量大等特点。根据RFID 系统调制载波频率不同，RFID系统可以分为低频(30~300kHz)、高频(3~30MHz)、超高频UHF(300-960MHz)以及微波频段(2.4~5.8GHz)。完整的RFID 系统包括四部分：射频卡/标签(Tag)、读写器(Reader)和天线(Antenna)、主机治理系统和网络。很多应用场合，在读写器信号作用范围内需要对多个物体进行识别，此时多个标签与读写器之间的通讯，存在信道争用题目。传统的信道争用，其解决的方法大致可以分为如下4种：空分多址(SDMA)、频分多址(FDMA)、码分多址(CDMA)和时分多址(TDMA)。

但在RFID 系统中，除了受复杂性和本钱的制约，还要解决本身通讯的因素，如无源标签需其提供能量、标签总数未知、碰撞判决需读写器控制、防碰撞协议要简单易实现等。

在 RFID 无源标签系统中，目前广泛使用的防碰撞算法大都是基于TDMA，比较经典的两类基本方法是：基于Aloha 算法和基于二进制树搜索算法。对于UHF 频段的RFID 系统，信号识别的间隔远，覆盖的范围广，因而需识别的标签数目大，若识别的物体有一定的速度，更需要良好的防碰撞算法以减少冲突达到快速、正确识别多个目标的目的。

2 UHF 频段RFID 系统防碰撞方案

在 UHF 工作频段，主要是ISO/IEC 18000-6(针对频率为860~960MHz 用于物品治理的无接触通讯空中接口参数)标准，包括A、B、C(EPC Class1 Gen2 标准纳进18000-6C)三种类型。如表1 所示它们采用的防碰撞算法也都不同，均是基本算法的改进应用。TYPE A 采用的是一种动态时隙ALOHA 算法防碰撞协议。标签内硬件需有随机数发生器和比较器，设计相对简单。TYPE A 防碰撞机制的不足之处是：若标签数目与初始时隙数相差较大时，防碰撞的过程会比较长。TYPE B 应用的防碰撞机制要较TYPE A 的更有效一些，它利用随机产生的0、1 信号达到了二进制树形搜索的效果，但防碰撞的效率会随标签数目增多而下降。TYPE C 应用的防碰撞算法是时隙随机防碰撞仲裁机制，是动态时隙ALOHA 算法的改进，在帧大小调整方面与以往动态帧时隙ALOHA 算法有很大改进，目前没有找到这样调整的理论依据。但它具有较高的阅读速率，在美国已达到1500 标签/秒，欧洲可达到600 标签/秒[1];同时也适合在高密度多个读写器环境下工作。

3 算法改进探讨与分析

为了缩短二进制树搜索算法的查询时间和返回信息比特数，有人提出了动态二进制搜索算法，还有很多研究者提出其他新奇的改进的方法。如文献[2]提出修剪枝的二进制树形搜索，文献[3]提出基于返回式二进制树形搜索。也有将二进制树搜索算法和ALOHA 算法结合起来[4]，共同实现系统的高效率。由于ALOHA 算法简单，易实现，且对标签数目变化有较好的适应，因而得到广泛应用，同时不断被优化和改进，因此本文重点分析ALOHA算法的改进和仿真。最基本的 ALOHA 算法存在部分碰撞和完全碰撞，导致碰撞发生的概率很大，其碰撞期为数据帧的两倍。并且最大系统吞吐率仅为18.4%。为了进步系统吞吐率和改善它的可行性和有效性，文献[5]提出时隙 ALOHA 和帧时隙ALOHA 算法，并且很多研究者试图找出帧大小的选取、估测未读标签的数目[6]。上节中提到的TYPE C 采用的正是帧时隙ALOHA算法的应用改进，可以实现对大量标签的识别，但是在实际应用中，总是希看系统的识别效率尽可能高，系统的开销尽可能小，因此，占用的时隙数也会相应减少，实际工作的效率也会进步。

4 仿真结果

仿真实验采用 Matlab 7 平台，研究标签盘存动态时隙大小对系统效率的影响。记录标签数从0 到600 变化时(以2Q 递增变化)系统效率变化曲线，为算法的改进提供理论的基础。为了使系统保持较高的效率，必须动态改变帧时隙大小，并且通过反馈估算标签数目，当帧时隙大小与待读标签数目相当时，此时系统的效率最大。

假设不考虑捕捉效应(指若干标签的应答碰撞时，离RFID 读写器较近的标签可能因其信号较强而覆盖其他标签的信号)N 为轮询的时隙长度，n 为某时刻读写器信号范围内未读标签数，r 个标签出现在某个给定时隙概率服从二项分布为[6]：

由图 1 所示，采用总固定时隙数时，当标签数越大时，采用的时隙数相对增大，系统的效率才会保持较高水平，当达到一定数目时，系统效率又会下降，需要再次调整总时隙数。

图 1 系统效率与标签数目关系曲线

对(2)式求导可知，

由(4)式知，标签数目越大时，当总时隙数和未读标签数目约相等时，系统的效率最高，若采取合适的反馈，公道的估算方法，使Q 动态变化，可以使系统效率明显增大，理想情况可达到如图2 所示。

图2 理想的系统效率曲线

若采取合适的反馈，公道的估算方法，使Q 动态变化，可以使系统效率明显增大，理想情况可达到如图2 所示。若估算的标签数n 小于当前时隙数N，减小帧中时隙数，若n 大于当前时隙数，需增加时隙数N，而反馈量采用何种参数，如何实际取值，可以根据实验和环境来调整、测试、验证。由于估测标签的数目取决于采取的估测方法，且系统实现较为复杂，本文提出采用时隙联合空闲率门限和碰撞率门限调整当前采用的时隙帧数，具体可行结合实验进一步验证可行性。

5 总结

本文分析了 UHF 频段RFID 的防碰撞方案，并具体仿真了算法的改进途径和更新时隙的方法，提出联合考虑空闲率和碰撞率的方法，调整总时隙数，能够让系统的效率大大进步，需要进一步结合实验验证。但从RFID 系统应用的角度来看，目前的防碰撞算法的识别率、识别速度、信道利用率(突破36.8%的系统效率限制)有待进一步进步，也需加强对安全和个人隐私等方面的考虑。在算法优化改进时，进一步考虑功率消耗和模拟实际信道建模等。为配合多个目标、高速运动物体的识别等复杂系统的应用，这些方面需作更深进的研究。

1