无线射频识别技术（ＲＦＩＤ）是一种非接触的自动识别技术，因其具有识别距离远、穿透能力强、多物体识别、抗污染等优点，现已广泛应用于工业自动化、商业自动化、交通运输控制管理、产品证件防伪、防盗等众多领域，成为当前ＩＴ业研究的热点技术之一。
ＲＦＩＤ系统一般由标签（Ｔａｇ）和读写器（Ｒｅａｄｅｒ）两个部分组成。在系统工作时，当有多个标签同时发送数据时就会出现碰撞，其结果会导致传输失败。因此需制定适当的防碰撞算法，避免或减少碰撞，从而有效地提高系统性能。一般防碰撞算法可以分为随机型和决定型。本文主要研究随机防碰撞算法中常见的两类算法：帧时隙ＡＬＯＨＡ算法及其改进型的、时隙随机算法。
１帧时隙ＡＬＯＨＡ算法
在ＲＦＩＤ系统中，帧时隙ＡＬＯＨＡ算法的“帧”是由读写器定义的一段时间长度，其中包含若干时隙。时隙指标签收到读写器命令后，发送标识的时间长度。标签被随机分配到一个时隙应答，当一个时隙中分配到多个标签时就产生碰撞。根据帧内时隙数是否变化分为固定帧时隙ＡＬＯＨＡ算法和动态帧时隙ＡＬＯＨＡ算法。
１．１固定帧时隙ＡＬＯＨＡ算法
固定帧时隙ＡＬＯＨＡ（ＦＦＳＡ）算法是最基本的一种算法，每帧时隙数的大小都一样。识别过程开始时，由读写器向识别场内所有标签发送一个包含时隙数Ｌ的命令。这些标签收到命令后，将其时隙计数器复位为１，开始记录时隙数，同时从１￣Ｌ中选择一个数做为其时隙数值。当时隙计数器值与标签随机选择的时隙数值相同时，标签向读写器发出应答信息。若标签被读写器成功识别，则退出识别系统。一个帧完成后，读写器开始时隙数同样为Ｌ的新帧。
ＦＦＳＡ算法设计简单，但缺点是如果标签数远远多于固定的时隙数，会产生过多碰撞；反之，会产生较多空闲时隙，造成资源浪费。只有在标签数与时隙数差不多的一段时间内，系统吞吐率最大。可见，由于ＦＦＳＡ算法的时隙数不能随着标签数而变化，系统无法获得稳定的吞吐率。为改善这一缺点，提出一种改进算法——
—动态帧时隙ＡＬＯＨＡ算法。
１．２动态帧时隙ＡＬＯＨＡ算法
动态帧时隙ＡＬＯＨＡ（ＤＦＳＡ）算法是每帧时隙数都会根据标签数的不同而变化。为获得系统最大吞吐率，ＤＦＳＡ算法需要在识别过程中估算标签数，用以确定匹配时隙数。在标签总数未知的情况下，当初始时隙数Ｌ＜１６时，第一次读取过程通常不能识别出标签。因此为节约初始时间，设置初始时隙数Ｌｉｎｉｔ＝１６［１］。
标签估算的方法有很多种［２－４］，例如：
（１）估算出参与识别的标签总数。设时隙数为Ｌ，标
签数为ｎ，则一个帧中碰撞时隙率Ｃｒａｔｉｏ＝１－（１－１
Ｌ
）ｎ（１＋ｎ
Ｌ－１
）［２］。在读写器识别过程中，已知当前帧时隙数为Ｌ，并且可以统计出该帧时隙碰撞率Ｃｒａｔｉｏ，采用逼近算法，可以估算出ｎ。
（２）直接估算出未识别的标签数。当系统达到最大吞吐率时，一个时隙的碰撞率Ｃｔａｇｓ＝０．４１８０［２］，因此一个时
隙碰撞的标签数Ｃｔａｇｓ＝１
Ｃｒａｔｅ
＝２．３９２２［２］。读写器在识别过程中，统计前一个帧的时隙碰撞数Ｎｃｏｌｌ，则未识别标签数ｎｅｓｔ＝２．３９２２×Ｎｃｏｌｌ。
得到未识别标签估计数ｎｅｓｔ后，从理论上讲最优的时隙数Ｌ应该等于ｎｅｓｔ［２］，但在实际应用中，读写器能够设定的时隙数是定值，通常为１，８，１６，３２，６４，１２８，２５６。因此，读写器需要根据ｎｅｓｔ从以上几个数中选择一个数作为下一帧的时隙数。对２５０个以内不同数目的标签，选择不同时隙数，计算一个帧的吞吐率。对不同标签数选择吞吐率最大所对应的时隙数如图１所示，得到标签数与匹配时隙数的对应关系如表１所示。这样就可以在估算出未识别标签数之后，在下一帧中选择匹配的时隙数，从而提高系统吞吐率。
１．３带延迟的帧时隙ＡＬＯＨＡ算法
帧时隙ＡＬＯＨＡ算法中，若帧时隙数远远小于标签
基于时隙的ＲＦＩＤ防碰撞算法分析＊
刘佳，张有光
（北京航空航天大学电子信息工程学院，北京１０００８３）
摘要：介绍了几种常见的基于时隙的防碰撞算法：帧时隙ＡＬＯＨＡ算法和时隙随机算法，并通过仿真，比较分析这些算法识别所用总时隙和对系统吞吐性能的影响。
关键词：ＲＦＩＤ防碰撞时隙
＊国家８６３计划：无线射频关键技术研究与开发，编号：２００５ＡＡ４２００５０
Ｌｎｅｓｔ１０￣１８２￣１１１６１２￣２２３２２３￣４５６４４６￣８９１２８９０￣１７６２５６
＞１７６
表１时隙数与标签数的对应关系
数，在匹配前系统吞吐率很低。为了在时隙数与标签数匹配前，提高当前帧的吞吐率，引入了延迟机制，即当标签随机选择的时隙数与时隙计数器数值相同时，标签并不立即应答读写器，而是延迟若干时隙（从０￣７的范围内选择）后再发出应答信息［５］。
图２是设定初始时隙为１６，对比不同标签数（标签数大于１６）下第一个帧的吞吐率。由图２看出，带延迟的算法的确可以提高一帧的吞吐率，然而延迟算法只有在标签数多而时隙数少的情况下才有利于提高系统吞吐率。在相反的情况下，延迟算法在减少碰撞时隙的同
时，产生过多的空闲时隙，不能提高系统的吞吐率。
１．４分组帧时隙ＡＬＯＨＡ算法
帧时隙ＡＬＯＨＡ算法局限于每帧最大时隙数为２５６。当标签数远远大于２５６时，系统无法通过增大时隙数来提高吞吐率。为解决这个问题，在ＤＦＳＡ算法的基础上提出分组帧时隙ＡＬＯＨＡ算法（ＧＦＳＡ）。参考文献［３］中说明，当标签数多于３５４时将全部标签分成两组或者更多组，读写器分别对每组标签进行识别，从而可以很好地提高系统的吞吐率。图３为普通ＤＦＳＡ算法与分组
ＧＦＳＡ算法在标签数多于４００时识别所用的总时隙数的
比较，初始时隙设为２５６。图３的结果表明，标签数越多，分组算法ＧＦＳＡ的优越性越明显。但是这种算法需要在原有的ＤＦＳＡ算法上做很多修改，例如读写器命令
需要加入分组参数，标签需要确定并保存自己的分组序号，这使得实现变得有些困难。
２时隙随机算法（ＳＲ）
时隙随机算法没有帧的概念，取而代之的是识别周期。识别周期是指读写器两次发送开始识别命令（Ｑｕｅｒｙ）的时间间隔。ＳＲ算法同样是令标签选择时隙应答，但区别在于，帧时隙ＡＬＯＨＡ算法在一个帧所有时隙完成之后才能更改时隙数，使未识别标签重新选择时隙；而ＳＲ算法在一个识别周期内可以随时更改时隙数，让未识别标签重新选择，实现了时隙数的自适应过程。
以ＩＳＯ／ＩＥＣ１８０００－６ＴｙｐｅＣ［５］为例，识别过程由读写器发送Ｑｕｅｒｙ命令开始，命令包含时隙参数Ｑ。标签从０￣２Ｑ－１范围内随机选择一个数作为自己的槽计数器值。当槽计数器值等于０时，标签应答。若标签被读写器成功识别，则退出识别系统。
读写器通过发送开始下一个时隙的命令（ＱｕｅｒｙＲｅｐ），令标签的槽计数器值减１，若槽计数器值为
０（前一个时隙碰撞的标签），则将其记为最大值（７ＦＦＦｈ）。
当读写器认为需要更改
时
隙数时，发送更改时隙参数的命令（ＱｕｅｒｙＡｄｊｕｓｔ），令原有Ｑ值加１或减１，这时标签会
重新产生槽计数器值。
时隙数的自适应过程是通过发送ＱｕｅｒｙＡｄｊｕｓｔ命令实现的。读写器根据几个时隙的识别情况（而非一个周期），增加或减少时隙参数Ｑ，使之能够及时有效地反映标签数的动态变化。一种简单的Ｑ值算法是在读写器中设计一个参数Ｑｆｐ作为Ｑ的浮点数。每次读写器都根据标签的应答情况更改Ｑｆｐ值，然后将Ｑｆｐ四舍五入为一个整数值。若这个整数不同于之前的Ｑ值，则读写器发送ＱｕｅｒｙＡｄｊｕｓｔ命令，令Ｑ等于这个整数；否则读写器不改变Ｑ值，发送ＱｕｅｒｙＲｅｐ命令。其过程如图４所示。其中Ｃ为Ｑｆｐ的变化步长。一般来说，Ｑ与Ｃ成反比，因此可以取Ｃ＝０．８／Ｑ［６］。初始时隙数与ＤＦＳＡ算法相同，取１６，即Ｑ＝４。
３仿真分析
图５、图６分别描述了识别一定数目的标签所需要的总时隙数和系统吞吐率。图中，ＦＦＳＡ１２８和ＦＦＳＡ２５６分别代表采用１２８和２５６时隙数的固定帧时隙ＡＬＯＨＡ算法；ＤＦＳＡＩ和ＤＦＳＡＩＩ分别代表采用１．２节第一种标签估计算法和第二种标签估计算法的动态帧时隙ＡＬＯＨＡ算法；ＳＲ算法代表时隙随机算法，其Ｑ值算法采用第２节所述方法。
从图５、图６中可以看出，若采用时隙数为１２８的ＦＦＳＡ算法，当标签数超过３００时，识别标签所需的时隙总数迅速增长。同样采用时隙数为２５６的ＦＦＳＡ算法，时隙总数也呈现迅速增长的趋势。ＦＦＳＡ算法的系统吞吐率较低而且吞吐性能不稳定。
若采用ＤＦＳＡ算法，识别标签所需的时隙总数略有下降。当标签数少于６００时，系统吞吐率较高而且相对稳定；当标签数大于６００时，由于受到最大时隙数２５６的限制，系统吞吐率开始下降。此时可以通过ＧＦＳＡ算法提高系统吞吐率。仿真中采用两种不同估算标签算法的ＤＦＳＡ算法，其性能差不多。但从实现角度讲，ＤＦＳＡＩＩ算法更好一些，因为它容易实现。
ＳＲ算法作为另外一类基于时隙的防碰撞算法，其性能远远优于前面几种算法。ＳＲ算法采用时隙数自适应机制，不仅减少碰撞时隙和空闲时隙产生，而且使碰撞标签可以及时重新参与识别。ＳＲ算法的最大时隙数可达２１５，在实际应用中，即便识别很大数量的标签时，也不会受到时隙数的限制。采用ＳＲ算法系统吞吐率最高且保持在一个定值左右。特别在识别很大数量的标签时，ＳＲ算法识别标签所用的总时隙数比ＤＦＳＡ算法减少很多。
总之，在ＲＦＩＤ系统中，基于时隙的防碰撞算法关心的首要问题都是使时隙数与标签数相匹配，这样才能提高系统吞吐率。对于文中分析的两类算法，帧时隙ＡＬＯＨＡ算法设计简单，适合于识别数量在６００个以内的标签；时隙随机算法相对复杂一些，但系统吞吐率高而且性能稳定，特别适合识别很大数量的标签。
参考文献
［１］吴晶，熊璋，王晔．利用动态时间槽分配的多目标防冲突射频识别．北京航空航天大学学报，２００５，３１（６）．［２］ＣＨＡＪＲ，ＫＩＭＪＨ．Ｎｏｖｅｌａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｓｆｏｒｆａｓｔｏｂｊｅｃｔｉｄｅｎｔｉｆｉｃａｔｉｏｎｉｎＲＦＩＤＳｙｓｔｅｍ．Ｔｈｅ１１ｔｈＩｎｔｅｒ－
ｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ，
２００５．（下转第１００页）
（上接第９６页）
［３］ＬＥＥＳＲ，ＪＯＯＳＤ，ＬＥＥＣＷ．Ａｎｅｎｈａｎｃｅｄｄｙｎａｍｉｃ
ｆｒａｍｅｄｓｌｏｔｔｅｄＡＬＯＨＡａｌｇｏｒｉｔｈｍｆｏｒＲＦＩＤｔａｇｉｄｅｎｔｉｆｉｃａ－ｔｉｏｎ．ＴｈｅＳｅｃｏｎｄＡｎｎｕａｌＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＭｏ－ｂｉｌｅ
ａｎｄＵｂｉｑｕｉｔｏｕｓＳｙｓｔｅｍｓ：ＮｅｔｗｏｒｋｉｎｇａｎｄＳｅｒｖｉｃｅｓ，２００５．［４］ＶＯＧＴＨ．ＭｕｌｔｉｐｌｅｏｂｊｅｃｔｉｄｅｎｔｉｆｉｃａｔｉｏｎｗｉｔｈｐａｓｓｉｖｅＲＦＩＤ
ｔａｇｓ．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅＳｗｉｓｓＦｅｄｅｒａｌＩｎｓｔ－
ｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ．２００２．［５］ＩＳＯ／ＩＥＣ１８０００－６．
［６］ＣＨＲＩＳＴＩＡＮＦ，ＭＡＴＴＨＩＡＳＷ．Ｃｏｍｐａｒｉｓｏｎｏｆｔｒａｎｓｍ－
ｉｓｓｉｏｎｓｃｈｅｍｅｓｆｏｒｆｒａｍｅｄＡＬＯＨＡｂａｓｅｄＲＦＩＤｐｒｏｔｏｃｏｌｓ．ＴｈｅＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＡｐｐｌｉｃａｔｉｏｎｓａｎｄｔｈｅＩｎ－ｔｅｒｎｅｔＷｏｒｋｓｈｏｐｓ，２００５．
（收稿日期：２００６－１１－１１）
ｃ．２００微秒后
，
ＮＲＦ２４０１进入监视状态，等待数据包的到来；
ｄ．当接收到正确的数据包（正确的地址和ＣＲＣ校
验码），ＮＲＦ２４０１自动把字头、
地址和ＣＲＣ校验位移去；ｅ．ＮＲＦ２４０１通过把ＤＲ１（这个引脚引起微控制器中
断）置高通知微控制器；
ｆ．微控制器把数据从ＮＲＦ２４０１移出；
ｇ．所有数据移完，ＮＲＦ２４０１把ＤＲ１置低，此时，如
果ＣＥ为高，则等待下一个数据包，如果ＣＥ为低，开始其他工作流程。
ＳｈｏｃｋＢｕｒｓｔ接收和发送的流程框图如图７和图８所
示。最终，无线点菜系统数据接收端正确接收点菜发送端发射来的点菜代码，并处理成计算机所能识别的数据传送给后台服务器进行处理。
该无线点菜系统成本低廉、设计简单、易于实现，经实际调试验证完全可用。通过该系统的研发架构，可以
得到一种用无线片上系统ＮＲＦ２４Ｅ１芯片来进行短距离无线组网的简易可行的设计方法。可以预见，随着无线网络的不断发展和应用普及，无线片上系统以其独特的优势，其应用必将不断扩展，而ＮＲＦ２４Ｅ１作为目前主流、典型、优秀的无线片上系统，在未来的无线领域中将发挥更大的作用。参考文献
［１］（美）ＲＡＳＨＩＮＫＡＲ．Ｐ等著，孙海平，丁键译．系统芯片
（ＳｏＣ）验证方法与技术［Ｍ］．北京：电子工业出版社，２００５．［２］潘琢金，施国君．Ｃ８０５１Ｆｘｘｘ高速ＳＯＣ单片机原理及应用
［Ｍ］．北京：北京航空航天大学出版社，２００２．
［３］黄智伟．射频集成电路芯片原理与应用电路设计［Ｍ］．
北京：电子工业出版社，２００４．
［４］李健．无线点菜系统的研究［Ｄ］．天津大学硕士学位论
文，２００４．
［５］许剑．基于无线片上系统的家庭网络控制系统的研究
与设计［Ｄ］．浙江大学硕士学位论文，２００６．
［６］延涛．基于ｎＲＦ２４Ｅ１芯片的通用遥控器原型样机的设
计［Ｄ］．西北工业大学硕士学位论文，２００５．
（收稿日期：２００６－１１－２０）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!