《rfid标签》由会员分享，可在线阅读，更多相关《rfid标签（7页珍藏版）》请在金锄头文库上搜索。
1、一种改进的一种改进的 RFIDRFID 防碰撞时隙防碰撞时隙 ALOHAALOHA 算法算法摘 要:在 RFID 系统中，多标签引起的冲突一直是影响系统性能的问题。本文在 分析 ALOHA 算法的基础上，提出一种分组动态帧时隙 ALOHA 算法。根据冲突情 况,从数学角度对动态帧时隙 ALOHA 算法的标签数作出实时估计,动态地改变帧 长或对标签进行分组来降低标签发生碰撞的概率,从而提高识别的效率。关键词：射频识别；ALOHA 算法；防碰撞A kind of enhanced slotted ALOHA algorithm for Anti-collision in RFID systemAb
2、stract:In the RFID system, the conflict caused by the multi-label h as been affecting system performance.This paper proposed a grouping d ynamic framed slotted ALOHA algorithm based on the analysis of ALOHA algorithm.According to the conflict situation,to make real-time estim ates the number of tags
3、 on the dynamic framed slotted ALOHA algorithm from the mathematical point of view,Dynamically change the frame leng th or the labels are grouped to reduce the label probability of colli sions, thereby improving the efficiency of the recognition.1 引言 射频识别技术(Radio Frequency Identification)是自动识别技术的一种，
4、近几年发展非常 迅速。射频识别技术的工作方式是利用射频方式进行非接触双向通信，以达到识别目标对 象并交换数据。同其它自动识别技术相比，射频识别技术有许多特点，如：无需光学可视、 非接触、数据存储容量大、并能同时识别大量数据等，因此它可广泛应用到门禁控制、物 流跟踪、仓储管理等领域。RFID 系统最大的难题在于多标签碰撞时较低的标签数据识读 率，多标签碰撞是指当多个标签同时存在于同一个射频信道内时，阅读器无法读取标签数 据的现象，其结果将会导致该次传输的失败，因为必须采用适当的技术防止碰撞的产生.1目前有多种防碰撞算法，主要分为 ALOHA 算法和树形分解算法。由于树形分解法有 时会使某些标签的
5、识别延迟可能比较长，所以 ALOHA 算法因具有简单易实现等优点而成 为应用最广的算法之一。文中将对 ALOHA 算法进行详细研究，并针对如何降低识别冲突 标签时延和减少标签碰撞次数方面进行改进，从而提高识别效率。 2 防冲撞算法介绍2. 1 Aloha 算法 在 Aloha 算法中当标签进入读写器范围时,电子标签自动地向读写器广播自己的 ID(即 唯一标识自身的数据,一般情况下为定长),在发送数据时如果有其他的标签也在发送数据,那 么将会发生信号冲突,读写器将不能正确地识别标签的 ID 号。读写器在检查到信号冲突时, 将发送一个停止发送信号的命令让所有标签停止当前发送并随机等待一个时间后再发
6、送自 己信息。纯 Aloha 算法较简单、易实现,但标签之间发生信号冲突的概率很大,系统的识别率较低。 2.2 帧时隙 ALOHA 帧时隙 ALOHA(Framed Slotted ALOHA, FSA)算法是一种随机时分多址方式的用户信息通 信收发算法。FSA 算法的信息帧时分多址如图 1 所示。图 1 FSA 算法的信息帧时分多址该算法将信道用信息帧表示，其中,帧是指由阅读器要求的包含若干时隙的时间间隔。信息 帧可以分成多个时隙，其中，时隙是指标签发送自身标识的时间长度。当一个时隙只被一 个标签占有时，阅读器才会正确识别该标签，而当一个时隙内有 2 个或 2 个以上标签时， 会发生碰撞，读
7、写器无法正确识别，若时隙为空则跳过。如此循环,至到所有的标签都被识 别。帧的大小是固定的,所以如果在某一时刻标签的个数远大于帧中时隙的个数,则在一个帧 中发生碰撞的几率将被提高,被浪费的时隙也将增多,从而延长了识别所有标签的时间。1-22.3 动态帧时隙 ALOHA 算法 为使系统效率最优，提出动态帧时隙 ALOHA(Dynamic Framed Slotted ALOHA，DFSA)算 法，使得帧时隙数等于参与循环的标签数。DFSA 每帧时隙数可以根据标签数的变化及时 调整，使得标签数量与帧时隙数匹配。在开始新一个帧循环时，读写器要对参与帧循环的 标签数进行估计，这个过程在整个算法中发挥着重
8、要的作用。如果所估计的标签数与实际 情况相差甚远，那么算法的效率就会发生大幅的下降，这样就影响了系统的稳定性。目前，主要有以下三种估计标签数的方法。 第一种是利用切比雪夫不等式估计标签数目。 knNnNnNnkvd cccaaa cccN10,2,1,010min,第二种方法是基于时隙二项分布来估计标签数。假设 N 代表当前帧的长度，n 表示标 签数。标签选择各个时隙数是等概率的，同一个时隙内出现 r 个标签的概率，根据二项分布原理，得： 11,111 nNnNNrnrB第三种方法是在发生冲突时，一个时隙中至少有两个标签发生碰撞。标签的估计函数为：kklbcccccN2,110N 代表当前帧的
9、长度， 表示空闲时隙， 表示成功时隙， 示碰撞时隙数。当冲突0c1ckc较频繁时，这种估计方法的相对估计误差较大，但具有方法简单等优点。3-43 改进的算法 分组动态帧时隙的 ALOHA 算法是在 DFSA 算法的基础上提出的，针对大规模标签进行 快速识别的一种改进型算法。此算法很好地改善了标签识读效率问题，即使有大量标签同 时存在，该算法也能线性地增加请求时间来识读标签。 3.1 算法分析及数学模型 在帧时隙 ALOHA 算法中，随着标签个数的增加，系统的吞吐率呈下降趋势。假设时隙数 N，标签总数为 n，根据统计学的原理，有 r 个标签选择 1 个时隙的概率为 rnNnNNrnrB 1111
10、,当 r=1 时，表示一个时隙只有一个标签，即成功读取的时隙。因此，在一个阅读周期中读取标签数的期望值为：11,11111 nNnnN NNnNBNa其中， 表示只有一个标签占据一个时隙的时隙总数。其中帧长度为 N，标签总数为nNa,1n。系统效率为： NP1,111 nnNNNNn NaP帧长度成功识别的标签数当我们要想获得最大效率时，使得： NNNn NNdndPnnN11ln1111111011ln11111 NnNNn根据上式可推出当帧的长度为 N 时，效率最高的标签响应数为： Nn11ln1当标签数为 n 时，帧长度的最佳值为：111nneeN当 n 很大时，将上式泰勒尔展开：1,
11、1 11111 nnnnN以上推导证明：当待识别标签数与帧长度基本相当时，系统吞吐率最大，即一个帧长度识 别周期中能够成功识别的标签数最多。图 2 给出了 L 取不同值时系统效率的仿真结果。另一方面，读写器能设定的时隙数通常是定值，如 1, 8,16, 32, 64, 128, 256。因此，读写器 根据上一轮识别过程结束后，剩余未识别标签个数中选择 1 个数作为下一帧的长度，具体 选择标准：当碰撞的时隙数高于 70%的总时隙数时，下一帧长度加倍；当空时隙数高于 30%的总时隙数时，下一帧长度减半；当到来的标签数 n 急剧增加,而一帧的时隙数不可能 无限增加时,用下式将标签分成 M 组,只允许
12、一组标签相应请求命令,以使系统仍能工作在最 大吞吐量下：，maxNnM 式中为读写器能分配的最大时隙,这里取 256。maxN表 1 显示了未识别标签个数与最佳帧长下分组的个数的关系。文中介绍了三种标签的估算方法，为减小 RFID 系统的复杂性，使用估计函数kccn21来确定标签数量。得到值后，由式计算出 M 值，若，则对标签进行分组；若n0M ,则不分组。0M 4 仿真结果分析 仿真实验采用 Matlab 7 平台,记录标签数从 0 到 1 000 递增变化时的系统效率和读取标签所 花时间(用读取标签所用的总时隙数来衡量),对改进算法、动态帧时隙 ALOHA 算法、固定 帧时隙的 ALOHA
13、 算法三者进行比较。初始时,动态帧时隙 ALOHA 和改进算法帧长度都是 8,而固定帧时隙 ALOHA 的帧长度即为允许的最大帧长 256.从图 3 可见,改进的动态帧时隙 ALOHA 算法在标签数量大于 500 时,仍能以 35 %上下的吞吐量工作,而固定时隙的 ALOHA 算法性能则急剧恶化.在图 4 中,固定帧时隙的 ALOHA 算法需要最多时间;改进算法需要最 少的时间,在大量标签的情况下,具有明显的优势,当标签数量增加到 1000 左右时,所用时间与 前者相比几乎减少了一半;动态帧时隙的 ALOHA 算法在标签数量较少时(小于 500),性能与 改进算法接近,但是在标签总数超过 50
14、0 以后,所需的时隙数大量增加,几乎没有时间上的优 势.表表 1 未识别标签个数对应的帧长度和分组情况未识别标签个数对应的帧长度和分组情况未识别标签个数 帧长 组数7081416 355707 177254 89176 4688 2345 1212 611256 256 256 128 64 32 16 84 2 1 1 1 1 1 1仿真结果显示改进算法在标签数量很大时,吞吐量可提高 100 %,标签读取时间下降近 50 %. 因此,这种算法对于短时间需要读取大量标签的实时 RFID 系统具有良好的适用性。 参考文献1 Finkenzeller K. 射频识别技术M. 3 版. 吴晓峰, 陈
15、大才, 译.北京: 电子工业出版社, 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 International Conference on Systems，Man and Cybernet-ics.Tunisia：IEEE Press，20025 LEE S R,JOO S D, LEE C W. An enhanced dynamicframed slotted ALOHA algorithm for RFID tagidentification.IEEE Computer Society, 2005C.
