rfid标签.doc

一种改进的RFID防碰撞时隙ALOHA算法摘 要:在RFID系统中，多标签引起的冲突一直是影响系统性能的问题。本文在分析ALOHA 算法的基础上，提出一种分组动态帧时隙ALOHA算法。根据冲突情况,从数学角度对动态帧时隙ALOHA算法的标签数作出实时估计,动态地改变帧长或对标签进行分组来降低标签发生碰撞的概率,从而提高识别的效率。关键词：射频识别；ALOHA算法；防碰撞A kind of enhanced slotted ALOHA algorithm for Anti-collision in RFID systemAbstract:In the RFID system, the conflict caused by the multi-label has been affecting system performance.This paper proposed a grouping dynamic framed slotted ALOHA algorithm based on the analysis of ALOHA algorithm.According to the conflict situation,to make real-time estimates the number of tags on the dynamic framed slotted ALOHA algorithm from the mathematical point of view,Dynamically change the frame length or the labels are grouped to reduce the label probability of collisions, thereby improving the efficiency of the recognition.1 引言射频识别技术(Radio Frequency Identification)是自动识别技术的一种，近几年发展非常迅速。射频识别技术的工作方式是利用射频方式进行非接触双向通信，以达到识别目标对象并交换数据。同其它自动识别技术相比，射频识别技术有许多特点，如：无需光学可视、非接触、数据存储容量大、并能同时识别大量数据等，因此它可广泛应用到门禁控制、物流跟踪、仓储管理等领域。RFID 系统最大的难题在于多标签碰撞时较低的标签数据识读率，多标签碰撞是指当多个标签同时存在于同一个射频信道内时，阅读器无法读取标签数据的现象，其结果将会导致该次传输的失败，因为必须采用适当的技术防止碰撞的产生.1目前有多种防碰撞算法，主要分为ALOHA算法和树形分解算法。由于树形分解法有时会使某些标签的识别延迟可能比较长，所以ALOHA算法因具有简单易实现等优点而成为应用最广的算法之一。文中将对ALOHA算法进行详细研究，并针对如何降低识别冲突标签时延和减少标签碰撞次数方面进行改进，从而提高识别效率。2 防冲撞算法介绍2. 1Aloha算法在Aloha算法中当标签进入读写器范围时,电子标签自动地向读写器广播自己的ID(即唯一标识自身的数据,一般情况下为定长),在发送数据时如果有其他的标签也在发送数据,那么将会发生信号冲突,读写器将不能正确地识别标签的ID号。读写器在检查到信号冲突时,将发送一个停止发送信号的命令让所有标签停止当前发送并随机等待一个时间后再发送自己信息。纯Aloha算法较简单、易实现,但标签之间发生信号冲突的概率很大,系统的识别率较低。2.2帧时隙 ALOHA帧时隙 ALOHA(Framed Slotted ALOHA, FSA)算法是一种随机时分多址方式的用户信息通信收发算法。FSA 算法的信息帧时分多址如图 1 所示。 图 1 FSA算法的信息帧时分多址该算法将信道用信息帧表示，其中,帧是指由阅读器要求的包含若干时隙的时间间隔。信息帧可以分成多个时隙，其中，时隙是指标签发送自身标识的时间长度。当一个时隙只被一个标签占有时，阅读器才会正确识别该标签，而当一个时隙内有 2 个或 2 个以上标签时，会发生碰撞，读写器无法正确识别，若时隙为空则跳过。如此循环,至到所有的标签都被识别。帧的大小是固定的,所以如果在某一时刻标签的个数远大于帧中时隙的个数,则在一个帧中发生碰撞的几率将被提高,被浪费的时隙也将增多,从而延长了识别所有标签的时间。1-22.3 动态帧时隙ALOHA算法为使系统效率最优，提出动态帧时隙ALOHA(Dynamic Framed Slotted ALOHA，DFSA)算法，使得帧时隙数等于参与循环的标签数。DFSA每帧时隙数可以根据标签数的变化及时调整，使得标签数量与帧时隙数匹配。在开始新一个帧循环时，读写器要对参与帧循环的标签数进行估计，这个过程在整个算法中发挥着重要的作用。如果所估计的标签数与实际情况相差甚远，那么算法的效率就会发生大幅的下降，这样就影响了系统的稳定性。 目前，主要有以下三种估计标签数的方法。第一种是利用切比雪夫不等式估计标签数目。 第二种方法是基于时隙二项分布来估计标签数。假设N代表当前帧的长度，n表示标签数。标签选择各个时隙数是等概率的，同一个时隙内出现r个标签的概率，根据二项分布原理，得： 第三种方法是在发生冲突时，一个时隙中至少有两个标签发生碰撞。标签的估计函数为： N代表当前帧的长度， 表示空闲时隙， 表示成功时隙， 示碰撞时隙数。当冲突较频繁时，这种估计方法的相对估计误差较大，但具有方法简单等优点。3-43 改进的算法分组动态帧时隙的ALOHA算法是在 DFSA 算法的基础上提出的，针对大规模标签进行快速识别的一种改进型算法。此算法很好地改善了标签识读效率问题，即使有大量标签同时存在，该算法也能线性地增加请求时间来识读标签。3.1算法分析及数学模型在帧时隙 ALOHA 算法中，随着标签个数的增加，系统的吞吐率呈下降趋势。假设时隙数 N，标签总数为 n，根据统计学的原理，有 r 个标签选择 1 个时隙的概率为 当r=1时，表示一个时隙只有一个标签，即成功读取的时隙。因此，在一个阅读周期中读取标签数的期望值为：其中， 表示只有一个标签占据一个时隙的时隙总数。其中帧长度为N，标签总数为n。系统效率为： 当我们要想获得最大效率时，使得： 根据上式可推出当帧的长度为N时，效率最高的标签响应数为： 当标签数为n时，帧长度的最佳值为： 当n很大时，将上式泰勒尔展开： 以上推导证明：当待识别标签数与帧长度基本相当时，系统吞吐率最大，即一个帧长度识别周期中能够成功识别的标签数最多。图 2 给出了 L 取不同值时系统效率的仿真结果。另一方面，读写器能设定的时隙数通常是定值，如 1, 8,16, 32, 64, 128, 256。因此，读写器根据上一轮识别过程结束后，剩余未识别标签个数中选择 1 个数作为下一帧的长度，具体选择标准：当碰撞的时隙数高于 70%的总时隙数时，下一帧长度加倍；当空时隙数高于 30%的总时隙数时，下一帧长度减半；当到来的标签数n急剧增加,而一帧的时隙数不可能无限增加时,用下式将标签分成M组,只允许一组标签相应请求命令,以使系统仍能工作在最大吞吐量下： ，式中为读写器能分配的最大时隙,这里取256。表1显示了未识别标签个数与最佳帧长下分组的个数的关系。表1 未识别标签个数对应的帧长度和分组情况 未识别标签个数 帧长 组数70814163557074688 23451212611256256256128643216842111111文中介绍了三种标签的估算方法，为减小RFID系统的复杂性，使用估计函数来确定标签数量。得到值后，由式计算出M值，若，则对标签进行分组；若,则不分组。4 仿真结果分析仿真实验采用Matlab 7平台,记录标签数从0到1 000递增变化时的系统效率和读取标签所花时间(用读取标签所用的总时隙数来衡量),对改进算法、动态帧时隙ALOHA算法、固定帧时隙的ALOHA算法三者进行比较。初始时,动态帧时隙ALOHA和改进算法帧长度都是8,而固定帧时隙ALOHA的帧长度即为允许的最大帧长256.从图3可见,改进的动态帧时隙ALOHA算法在标签数量大于500时,仍能以35 %上下的吞吐量工作,而固定时隙的ALOHA算法性能则急剧恶化.在图4中,固定帧时隙的ALOHA算法需要最多时间;改进算法需要最少的时间,在大量标签的情况下,具有明显的优势,当标签数量增加到1000左右时,所用时间与前者相比几乎减少了一半;动态帧时隙的ALOHA算法在标签数量较少时(小于500),性能与改进算法接近,但是在标签总数超过500以后,所需的时隙数大量增加,几乎没有时间上的优势.仿真结果显示改进算法在标签数量很大时,吞吐量可提高100 %,标签读取时间下降近50 %.因此,这种算法对于短时间需要读取大量标签的实时RFID系统具有良好的适用性。参考文献1 Finkenzeller K. 射频识别技术M. 3 版. 吴晓峰, 陈大才, 译.北京: 电子工业出版社, 2006.2 陆端，等. 改进ALOHA算法在RFID多目标识别中的应用J. 微计算机信息, 2006,22(11):3徐圆圆,刘禹.基于Aloha算法的帧长及分组数改进研究J.计算机应用,2008,28(3)：588- 5904 Vogt H.Multiple object identification with passive RFID tagsM.IEEE Intern