基于时隙的RFID防碰撞算法分析
2008-03-17
作者：刘 佳， 张有光
摘 要：介绍了几种常见的基于时隙" title="时隙">时隙的防碰撞算法" title="防碰撞算法">防碰撞算法：帧时隙ALOHA算法和时隙随机算法，并通过仿真,比较分析这些算法识别所用总时隙和对系统吞吐性能的影响。
关键词：RFID 防碰撞 时隙
无线射频识别技术（RFID）是一种非接触的自动识别技术，因其具有识别距离远、穿透能力强、多物体识别、抗污染等优点，现已广泛应用于工业自动化、商业自动化、交通运输控制管理、产品证件防伪、防盗等众多领域，成为当前IT业研究的热点技术之一。
RFID系统一般由标签(Tag)和读写器" title="读写器">读写器(Reader)两个部分组成。在系统工作时，当有多个标签同时发送数据时就会出现碰撞，其结果会导致传输失败。因此需制定适当的防碰撞算法，避免或减少碰撞，从而有效地提高系统性能。一般防碰撞算法可以分为随机型和决定型。本文主要研究随机防碰撞算法中常见的两类算法：帧时隙ALOHA算法及其改进型的、时隙随机算法。
1 帧时隙ALOHA算法
在RFID系统中，帧时隙ALOHA算法的“帧”是由读写器定义的一段时间长度，其中包含若干时隙。时隙指标签收到读写器命令后，发送标识的时间长度。标签被随机分配到一个时隙应答，当一个时隙中分配到多个标签时就产生碰撞。根据帧内时隙数是否变化分为固定帧时隙ALOHA算法和动态帧时隙ALOHA算法。
1.1 固定帧时隙ALOHA算法
固定帧时隙ALOHA（FFSA）算法是最基本的一种算法，每帧时隙数的大小都一样。识别过程开始时，由读写器向识别场内所有标签发送一个包含时隙数L的命令。这些标签收到命令后，将其时隙计数器复位为1，开始记录时隙数，同时从1~L中选择一个数做为其时隙数值。当时隙计数器值与标签随机选择的时隙数值相同时，标签向读写器发出应答信息。若标签被读写器成功识别，则退出识别系统。一个帧完成后，读写器开始时隙数同样为L的新帧。
FFSA算法设计简单，但缺点是如果标签数远远多于固定的时隙数，会产生过多碰撞；反之，会产生较多空闲时隙，造成资源浪费。只有在标签数与时隙数差不多的一段时间内，系统吞吐率" title="吞吐率">吞吐率最大" title="最大">最大。可见，由于FFSA算法的时隙数不能随着标签数而变化，系统无法获得稳定的吞吐率。为改善这一缺点，提出一种改进算法——动态帧时隙ALOHA算法。
1.2 动态帧时隙ALOHA算法
动态帧时隙ALOHA（DFSA）算法是每帧时隙数都会根据标签数的不同而变化。为获得系统最大吞吐率，DFSA算法需要在识别过程中估算标签数，用以确定匹配时隙数。在标签总数未知的情况下,当初始时隙数L<16时，第一次读取过程通常不能识别出标签。因此为节约初始时间，设置初始时隙数Linit=16[1]。
标签估算的方法有很多种[2-4]，例如：
(1)估算出参与识别的标签总数。设时隙数为L，标签数为n，则一个帧中碰撞时隙率Cratio=1-(1-
)n(1+
)[2]。在读写器识别过程中，已知当前帧时隙数为L，并且可以统计出该帧时隙碰撞率Cratio，采用逼近算法，可以估算出n。
（2）直接估算出未识别的标签数。当系统达到最大吞吐率时，一个时隙的碰撞率Ctags=0.418 0[2]，因此一个时隙碰撞的标签数Ctags=
=2.392 2[2]。读写器在识别过程中，统计前一个帧的时隙碰撞数Ncoll，则未识别标签数nest=2.392 2×Ncoll。
得到未识别标签估计数nest后，从理论上讲最优的时隙数L应该等于nest[2]，但在实际应用中，读写器能够设定的时隙数是定值，通常为1，8，16，32，64，128，256。因此，读写器需要根据nest从以上几个数中选择一个数作为下一帧的时隙数。对250个以内不同数目的标签，选择不同时隙数，计算一个帧的吞吐率。对不同标签数选择吞吐率最大所对应的时隙数如图1所示，得到标签数与匹配时隙数的对应关系如表1所示。这样就可以在估算出未识别标签数之后，在下一帧中选择匹配的时隙数，从而提高系统吞吐率。
表1时隙数与标签数的对应关系
L
nest
1
0~1
8
2~11
16
12~22
32
23~45
64
46~89
128
90~176
256
>176
1.3 带延迟的帧时隙ALOHA算法
帧时隙ALOHA算法中,若帧时隙数远远小于标签数，在匹配前系统吞吐率很低。为了在时隙数与标签数匹配前，提高当前帧的吞吐率，引入了延迟机制，即当标签随机选择的时隙数与时隙计数器数值相同时，标签并不立即应答读写器，而是延迟若干时隙（从0~7的范围内选择）后再发出应答信息[5]。
图2是设定初始时隙为16，对比不同标签数（标签数大于16）下第一个帧的吞吐率。由图2看出，带延迟的算法的确可以提高一帧的吞吐率，然而延迟算法只有在标签数多而时隙数少的情况下才有利于提高系统吞吐率。在相反的情况下，延迟算法在减少碰撞时隙的同时，产生过多的空闲时隙，不能提高系统的吞吐率。
1.4 分组帧时隙ALOHA算法
帧时隙ALOHA算法局限于每帧最大时隙数为256。当标签数远远大于256时，系统无法通过增大时隙数来提高吞吐率。为解决这个问题，在DFSA算法的基础上提出分组帧时隙ALOHA算法（GFSA）。参考文献[3]中说明，当标签数多于354时将全部标签分成两组或者更多组，读写器分别对每组标签进行识别，从而可以很好地提高系统的吞吐率。图3为普通DFSA算法与分组GFSA算法在标签数多于400时识别所用的总时隙数的比较，初始时隙设为256。图3的结果表明，标签数越多，分组算法GFSA的优越性越明显。但是这种算法需要在原有的DFSA算法上做很多修改，例如读写器命令需要加入分组参数，标签需要确定并保存自己的分组序号，这使得实现变得有些困难。
2 时隙随机算法（SR）
时隙随机算法没有帧的概念，取而代之的是识别周期。识别周期是指读写器两次发送开始识别命令（Query）的时间间隔。SR算法同样是令标签选择时隙应答，但区别在于，帧时隙ALOHA算法在一个帧所有时隙完成之后才能更改时隙数，使未识别标签重新选择时隙；而SR算法在一个识别周期内可以随时更改时隙数，让未识别标签重新选择，实现了时隙数的自适应过程。
以ISO/IEC 18000-6 Type C[5]为例，识别过程由读写器发送Query命令开始，命令包含时隙参数Q。标签从0~2Q-1范围内随机选择一个数作为自己的槽计数器值。当槽计数器值等于0时，标签应答。若标签被读写器成功识别，则退出识别系统。
读写器通过发送开始下一个时隙的命令（QueryRep），令标签的槽计数器值减1，若槽计数器值为0(前一个时隙碰撞的标签)，则将其记为最大值(7FFFh)。当读写器认为需要更改时隙数时，发送更改时隙参数的命令(QueryAdjust)，令原有Q值加1或减1，这时标签会重新产生槽计数器值。
时隙数的自适应过程是通过发送QueryAdjust命令实现的。读写器根据几个时隙的识别情况（而非一个周期），增加或减少时隙参数Q，使之能够及时有效地反映标签数的动态变化。一种简单的Q值算法是在读写器中设计一个参数Qfp作为Q的浮点数。每次读写器都根据标签的应答情况更改Qfp值，然后将Qfp四舍五入为一个整数值。若这个整数不同于之前的Q值，则读写器发送QueryAdjust命令，令Q等于这个整数;否则读写器不改变Q值，发送QueryRep命令。其过程如图4所示。其中C为Qfp的变化步长。一般来说，Q与C成反比，因此可以取C=0.8/Q[6]。初始时隙数与DFSA算法相同，取16，即Q=4。
3 仿真分析
图5、图6分别描述了识别一定数目的标签所需要的总时隙数和系统吞吐率。图中，FFSA 128和FFSA 256分别代表采用128和256时隙数的固定帧时隙ALOHA算法；DFSA I和DFSA II分别代表采用1.2节第一种标签估计算法和第二种标签估计算法的动态帧时隙ALOHA算法；SR算法代表时隙随机算法，其Q值算法采用第2节所述方法。
从图5、图6中可以看出，若采用时隙数为128的FFSA算法，当标签数超过300时，识别标签所需的时隙总数迅速增长。同样采用时隙数为256的FFSA算法，时隙总数也呈现迅速增长的趋势。FFSA算法的系统吞吐率较低而且吞吐性能不稳定。
若采用DFSA算法，识别标签所需的时隙总数略有下降。当标签数少于600时，系统吞吐率较高而且相对稳定；当标签数大于600时，由于受到最大时隙数256的限制，系统吞吐率开始下降。此时可以通过GFSA算法提高系统吞吐率。仿真中采用两种不同估算标签算法的DFSA算法，其性能差不多。但从实现角度讲，DFSA II算法更好一些，因为它容易实现。
SR算法作为另外一类基于时隙的防碰撞算法，其性能远远优于前面几种算法。SR算法采用时隙数自适应机制，不仅减少碰撞时隙和空闲时隙产生，而且使碰撞标签可以及时重新参与识别。SR算法的最大时隙数可达215，在实际应用中，即便识别很大数量的标签时，也不会受到时隙数的限制。采用SR算法系统吞吐率最高且保持在一个定值左右。特别在识别很大数量的标签时，SR算法识别标签所用的总时隙数比DFSA算法减少很多。
总之，在RFID系统中，基于时隙的防碰撞算法关心的首要问题都是使时隙数与标签数相匹配，这样才能提高系统吞吐率。对于文中分析的两类算法，帧时隙ALOHA算法设计简单，适合于识别数量在600个以内的标签；时隙随机算法相对复杂一些，但系统吞吐率高而且性能稳定，特别适合识别很大数量的标签。
参考文献
[1] 吴晶，熊璋，王晔. 利用动态时间槽分配的多目标防冲突射频识别.北京航空航天大学学报，2005，31(6).
[2] CHA J R， KIM J H. Novel anti-collision algorithms for fast object identification in RFID System. The 11th Inter-national Conference on Parallel and Distributed Systems, 2005.
[3] LEE S R， JOO S D， LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identifica-tion.The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2005.
[4] VOGT H. Multiple object identification with passive RFID tags. Department of Computer Science Swiss Federal Inst-itute of Technology.2002.
[5] ISO/IEC 18000-6.
[6] CHRISTIAN F, MATTHIAS W. Comparison of transm-ission schemes for framed ALOHA based RFID protocols. The International Symposium on Applications and the In-ternet Workshops, 2005.