（电工理论与新技术专业论文）rfid二进制树防碰撞算法的研究与实现.pdf

r f l d 二进制树防碰掩算法的研究o j 实现 a b s t r a c t r f i di san e w l yd e v e l o p e dt e c h n o l o g yw h i c hc o m m u n i c a t e st h r o u g ht h e n o n c o n t a c tr fs i g n a l ，s oa st oa c h i e v eo b j e c t i v ea u t o m a t i ci d e n t i f i c a t i o n a l o n gw i t ht h ed e v e l o p m e n to fr f i dt e c h n o l o g y ，h o w t or e a l i z ed a t ae x c h a n g e a c c u r a t e l ya m o n gm u l t i p l et a r g e t sa t t h es a m et i m eb e c o m e st h ek e yp r o b l e mo f r f i dt e c h n o l o g y r f i da n t i - c o l l i s i o na l g o r i t h mi st h es o l u t i o nt ot h ea b o v e m e n t i o n e dp r o b l e m s i na l lt h ea l g o r i t h m s ，b i n a r ya l g o r i t h mi sm o s tw i d e l yu s e da s a ni n t e r n a t i o n a ls t a n d a r df b ri t se x a c t n e s so fi d e n t i n c a t i o n i n t e r n a t i o n a ls t a n d a r d s h a v ep u tf o r w a r dm a n yr e g u l a t i o n so nb i n a r ya l g o r i t h m i tn o to n l yp r o m o t e st h e d e v e l o p m e n to fa n t i c o u i s i o na l g o r i t h m ，b u ta l s ob “n g st h ec o n f l i c tt o au n i l f i e d s o l u t i o n t r a d i t i o n a l i d e a si ng e n e r a la r eh a n d l e db ym c u a l o n gw i t ht h ed e v e l o p m e n t o fr f i dt e c h n o l o g y ，a ni m p o n a n td i r e c t i o ni nt h ef u t u r ei st h ef i e l dp r o g r a m m a b l e g a t e sa r r a yf p g a a sk i n do fi n t e g r a t e dc i r c u i t st h a tc a n b ep r o g r a m m e di nt h ef i e l d ， f p g ai sf a s ta n dp r o g r a m m a b l e a l lt h e s ea d v a n t a g e so p e nu pan e we f 诧c t i v ew a y o fr f i da n t i c o l l i s i o na r i t h m e t i c i nv i e wo ft h ea b o v ep r o b l e m s ，t h i sp a p e rp r o b e si n t ot h er f i ds y s t e mb i n a r y p r e v e n tc o l l i s i o nf r o mt h ep e r s p e c t i v e so f b o t ht h e o r ya n dp r a c t i c e i tc a n b ed i v i d e d i n t ot h r e ea s p e c t s ：6 r s t l y ，t h e o r e t i c a lr e s e a r c ho nb i n a r ya l g o r i t h m i ts u m su pa l lt h e b i n a r ya l g o r i t h m si nb e i n ga n dg a t h e rt ot h r e ec a t e g o r y ss u c ha sb a s i ca l g o r i t h m ， d y n a m i ca l g o r i t h ma n db a c k o f fa l g o r i t h m m o r e o v e r ，i te x p o u n d st h ei d e ao ft h e v a r i o u sa l g o r i t h m sa n de v a l u e st h e i rp e r f 6 r m a n c e ； s e c o n d a r y ， i ti n t r o d u c e sa n i m p r o v e dv e r s i o no fa l g o r i t h mo nt h eb a s i so fs p e c i n cs t a n d a r d t h i sa l g o r i t h mh a s f a s t r e c o g n i t i o n ，h i g he f n c i e n c y a n d g r e a t l yi m p r o v e d t h ei d e n t i f i c a t i o n r e s u l t s t h i r d l y ，i m p l e m e n t a t i o no fa l g o r i t h mw i t hf p g a w i t ha p p l i c a t i o nm o d e l s i m s i m u l a t i o ns o f t w a r et os i m u l a t i o n t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h m c a ne f k c t i v e l yi d e n t i f yt h et r a n s p o n d e ra n df p g ac a na c h i e v es p e e d so fm o r et h a n 2 0 0 m i tm e e t st h en e e d so fm o s ta p p l i c a t i o n s t h i sp a p e rs h e dl i g h to nt h ed e v e l o p m e n to fn e wg e n e r a t i o n so fr f i d t e c h n o l o g y t h e r e f o r e ；i ti n d e e ds h o w sg r e a tt h e o r e t i c a ld e p t ha n da p p l i c a t i o nv a l u e k e yw o r d s ：r f i d ；a n t i - c o l l i s i o n ；r e a d w r i t ed e v i c e s ；t r a n s p o n d e r s ；f p g a 。 i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： i 勾奇矗日期：1 奸年巧月2 6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密商。 ( 请在以上相应方框内打“”) 作者签名：i 勺毒盘 导师签名：0 a 日期： 日期： 3 研年万月 日 年r 月弘日 硕十学位论文 1 1r f i d 技术简介 第l 章绪论 自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为 a u t o m a t i ce q u i p m e n ti d e n t i fi c a t i o n ，简称a e i ，它通过一些先进的技术手段，实 现人们对各种设备在不同状态下的自动识别和管理【l l 。 目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两 种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领 域的应用更具体的名称为射频识别，英文名为r a d i of r e q u e n c yi d e n t i f i c a t i o n ，简 写为r f i d i 2 1 。 r f i d 技术通过射频方式进行非接触的双向通信，达到自动识别的目的，它 源起于上世纪四五十年代，最初是基于雷达与微波理论的发展，自从上世纪九十 年代以来，r f i d 技术快速发展，得到了广泛的应用，进入新世纪后，各个国家， 组织还有企业都加大了对r f i d 技术的投入，生产了大批相应的产品，在多个领 域有了成功的应用案例。r f i d 被誉为二十一世纪的十大战略性产业之一，可以 预想，未来r f i d 技术的发展空间是无限广阔的。 1 2r f i d 系统 1 2 1r f i d 系统组成 根据实际应用环境，r f i d 系统结构有多种不同分法，一般来说，一个典型 r f i d 系统包括三个部分：前端信息载体，数据交换环节，后端应用环境【3 】。 在具体应用中，前端信息载体有多个名称，如标签( t a g ) ，智能标签( s m a r t l a b e l s ) ，射频卡( r fc a r d ) 等，本文建议采用应答器( t r a n s p o n d e r ) 这种更具普 遍意义的说法。在r f i d 系统中，应答器放置在待识别的物体上，它内部存储的 信息表征着该物品的独一性，因此是r f i d 系统真j 下的数据载体。通常来说，应 答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据 传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以 这些性能为依据的，例如根据存储器可将应答器分为e e p r o m ，f r o m ( 铁电存储 器) ，s r a m ( 静态随机存储器) ，根据信息注入方式可分为集成电路固化，现场有 线改写，现场无线改写，根据电源供给方式分为无源，半无源，有源。一般来说， 应用最广泛的是无源+ 集成电路固化+ 静态随机存储的应答器。由于在r f i d 系 统中，应答器是大规模生产的，所以应答器的主要考虑因素是生产成本，降低成 r f i d 二进制树防碰掩算法的研究j 实现 本的手段有缩小芯片面积，采用更精细的芯片切割技术，更先进的封装技术，以 及新型天线技术，甚至于找到硅材料的替代品等。应答器的典型产品有t i 公司 的6 0 0 0 系列，p h i l i p s 公司的i c o d e 等。 数据交换环节即r f i d 系统中的读出写入设备，它是系统的核心部件，是后 端应用环境和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫 描器，阅读器，编程器等，本文建议采用读写器( r e a d w r i t ed e v i c e ) 这种更具 普遍意义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中 写入信息。根据天线与读写器模块的分离与否，读写器可以分为分离式和集成式， 但无论哪种读写器，其基本结构都是类似的，从硬件部分来说，典型的读写器由 三块组成：射频通道模块，控制处理模块，天线。 后端应用环境主要完成数据信息的存储及处理，它实质上就是一个数据管理 系统，也是一个全局控制系统，一般由p c 机或者工作站组成，同时也包括了应 用软件在内，整个后端应用环境负责接收来自读写器的数据，并进行存储以及相 应的处理，协同调节多个读写器的工作，该部分在应用中常称为中间件( s a v a n t ) ， 它扩展了r f i d 系统的应用范围和应用能力，是未来r f i d 系统智能化，大型化 发展的有力技术支撑，是r f i d 技术发展的重要方式。微软公司近年来也介入了 r f i d 技术领域，所瞄准的就是r f i d 系统后端应用的相关软件和服务。 综上所述，一个典型的r f i d 系统的组成如图所示： 1 2 2r f i d 系统分类 图1 1r f i d 系统组成 r f i d 系统依据不同的标准，可以分为很多类别，各个不同的r f i d 系统， 在工作方式和应用范围上，有着各自不同的特点，在应用时要根据实际需要来选 择。几种典型的分类方式如下所示： 硕上学位论文 根据作用距离的远近，r f i d 系统可以分为如下三个方面： ( 1 ) 密耦合：典型的作用范围为0 lc m 。 ( 2 ) 遥耦合：典型的作用范围为l c m 1 m 。 ( 3 ) 远距离系统：典型的作用范围为l 10 m 。 根据工作频率的大小，r f i d 系统可以分为如下四个方面1 4 l ： ( 1 ) 低频：3 0 3 0 0 k h z ，典型应用为1 3 4 k h z 。 ( 2 ) 高频：3 3 0 m h z ，典型应用为1 3 5 6 m h z ( 3 ) 超高频：3 0 0 m h z 5 8 g h z ，典型应用为2 4 g 。 ( 4 ) 混频：多个频率的混合使用，典型应用为1 3 4 k h z + 4 3 0 m h z 。 根据应答器供电方式，r f i d 系统可以分为三个方面： ( 1 ) 无源系统：由读写器负责给应答器供电。 ( 2 ) 半无源系统：应答器内的电池仅做辅助作用。 ( 3 ) 有源系统：应答器内置电池负责供给工作电压。 1 2 3r f i d 系统工作原理 r f i d 是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路， 无线电广播，通信原理等多方面知识。 r f l d 系统中，读写器将要发送的信号调制到载波上，经由射频通道，通过 天线发送出去，应答器上的电压根据载波的变化而变化，将该电压信号进行整流 和滤波后，得到解调后的数据，这是下行链路的过程，应答器传输的数据的变化 控制应答器天线上负载电阻的通断，从而促使读写器天线上电压的变化，从而实 现了数据的上行链路传输。在数据的双向传输过程中，是通过电磁场的相互感应 来实现的，该过程也可以用变压器的模型来予以参考。同时，根据r f i d 系统的 不同，在供电方式上有无源或者有源，调制方式上有幅度调制或者相位调制，数 据读取上有电感耦合或者反向散射等区别【5 1 。 1 3r f i d 技术现状及其发展 1 3 1r f i d 技术应用 做为一种新兴的自动识别技术，r f i d 近年来发展很快，在国内国外都取得 了广泛的应用，主要体现在以下几个领域【6 1 。 ( 1 ) 物流管理 物流管理是r f i d 技术最具应用前景的领域，近年来提出了一个物联网的概 念，意在将全球所有的物品信息都用唯一的电子代码来表示，从而将这些物品都 联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产品，用户， 企业和政府之间建立起一个新型的，开放的，全球性的物品网络。这个方面的典 r f i d _ 二进制树防碰掩算法的研究j 实现 型例子是沃尔玛，作为全球最大的零售商，沃尔玛要求在产品上贴上电子标签， 来做为物品识别的根据，从而大大节约了成本，也带动了r f i d 技术的发展。但 是该应用涉及到的方面太广，技术难度很大，目前还在研究当中。 ( 2 ) 身份识别 利用r f i d 技术，将应答器嵌入到身份证，护照等各种证件当中，甚至植入 动物皮毛，用来跟踪和识别目标。这方面应用的典型例子是我国目前实行的二代 身份证，它基于i s o i e c1 4 4 4 3 标准定义的t y p eb 类型卡。r f i d 在身份识别 方面的主要问题是频段的局限性，一般使用的是l3 5 k h z 和1 3 5 6 m h z 的工作频 率，这是因为过高的频段容易带来对人体有害的电磁辐射。 ( 3 ) 防伪应用 应答器在防伪应用中有识别快速，伪造难，成本低等优点，再加上安全认证 和加密功能，就可以大大提高伪造的难度和成本，同时，在识别的时刻，可以通 过读写器的快速阅读功能，在瞬间得出所有物品的信息，并加以记录和处理。目 前在日本和欧洲已经有了类似的应用。 ( 4 ) 交通管理 交通管理是r f i d 最先应用的领域，目前已经拥有了成熟的技术，它利用了 应答器便捷快速识别，可靠性高，安全性强的特点，目前主要应用范围是电子车 票，高速公路收费等方面，在我国深圳，基于r f i d 技术的高速公路收费系统已 经得到了成功的应用。 r f i d 技术的应用远不止以上提及的四个方面，它在诸如生产线自动化管理， 门禁系统，新生婴儿防错管理，地理信息标识等多个方面都有着广泛应用，可以 毫不夸张的说，r f i d 技术有着良好的发展前景，它孕育的经济效益将是超乎想 像的。 1 3 2r f i d 标准统一化 r f i d 最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范， 因此制约了该项技术在大规模系统中的应用，随着r f i d 技术的发展，参与到其 中的国家，组织，企业也越来越多，目前形成了国际标准化组织i s o ，泛在i d 中心u i d ，全球电子产品代码管理中心e p c 三大标准体系，这些标准涉及到r f i d 系统的物理结构，通信协议，防碰撞算法，应用系统接口协议等等多个方面的内 容，它们针对不同的频率，基于不同的工作原理，甚至在同样的应用背景下也有 着巨大的协议上的区别。而要建立一个全球互联的r f i d 产品网络，实现r f i d 技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着r f i d 技术的应 用越发广泛，有识之士都意识到并着手解决这个问题，目前主要有两种思路，一 是生产出适应于不同标准，多制式兼容的r f i d 产品，二是制定一个统一的r f i d 硕十学位论文 技术标准。但是r f i d 本身的技术难度，以及标准带来的经济利益的冲突，使得 该目标实施起来非常困难。由此可见，标准统一化问题的重要性与困难性是并存 的，这将是一个任重而道远的过程。 1 3 3r f i d 防碰撞算法 随着r f i d 技术的发展，多目标识别成为了一个很重要的应用方向，特别在 目标跟踪，物品识别，访问控制等操作中，利用r f i d 技术，对附着在不同目标 上的应答器快速可靠的进行识别，从而大大提高了定位的精确度，管理的自动化， 促进了整个产业链的发展。因此，如何保证迅速快捷，又安全可靠的同时识别多 个目标，就成为了r f i d 技术发展的关键性技术。在r f i d 系统中，当工作范围 内同时出现了多个读写器和多个应答器时，读写器与读写器之间，应答器与应答 器之间的相互干扰，称r f i d 系统发生了碰撞【7 1 ，从而导致数据不能正确的传输， 信息无法得到正确的读取，一方面影响了产品的识别，另一方面还可能导致信息 的泄露。在全球信息安全意识广泛普及的背景下，可靠的安全机制成为了r f i d 技术发展的关键性制约因素，如何有效的解决r f i d 系统的碰撞问题，成为了 r f i d 技术的关键，对此就需要采用一定的防碰撞算法来对其进行处理。目前关 于防碰撞算法的研究还在进行当中，理论成果已经得出了很多，许多国际标准也 对一些成熟的算法进行了规定，但是无论在理论效率还是实际应用上，都还存在 很大的改进空间。 1 4 课题提出的背景及其意义 早期的r f i d 技术很少涉及到防碰撞问题，而在近年来，随着r f i d 技术的 发展，应用范围的扩大，使得防碰撞问题日益成为制约r f i d 发展的关键技术， 原因有两个，首先，早期的r f i d 一般是近距离感应耦合式系统，其操作频率及 功率普遍较低，读取的速度慢，范围小，所以也较少有发生碰撞的可能，而目前 r f i d 应用中多目标识别成为了主流方向，这就要求实现在多个物品中正确的识 别出单个目标；其次，早期的r f i d 应用没有统一的规范，各个厂家的r f i d 产 品也仅是应用在单个的系统当中，不存在碰撞的可能，而近年来r f i d 应用迅速 发展，各个不同r f i d 制造商的产品之间的不兼容，也带来了碰撞问题。总之， 由于多目标识别应用的需要，r f i d 系统防碰撞问题成为了关键技术，为了解决 碰撞，可以从硬件和软件两方面着手，由于r f i d 系统的大规模应用限制了成本， 所以，硬件实现是不实际的，因此就需要采用一定的防碰撞算法来予以解决。 依前所述，r f i d 系统碰撞主要有两种情况，读写器碰撞和应答器碰撞，读 写器碰撞是一个应答器同时收到不同读写器发出的命令，应答器碰撞是一个读写 器同时给不同应答器发送命令。在实际的应用当中，应答器由于其低成本的优越 r f i d 二进制树防碰捕算法的研究j 实现 性，从而得到大量的生产，而读写器往往是固定在系统的某处，来识别多个应答 器，所以碰撞的主要情况是应答器碰撞，即一个读写器的工作范围内同时出现了 多个应答器，并且对该读写器发出的命令同时予以响应，从而导致读写器无法正 确的识别出一个应答器，称该现象为发生了应答器碰撞。解决碰撞的过程相应的 被称为防碰撞，如前所述，该防碰撞过程主要从软件的角度来予以解决，称为防 碰撞算法1 8 l 。 在上述前提下，基于应答器的确定型二进制树防碰撞算法是目前最好的一种 选择，对其进行研究，是最有实际应用价值的，所以，本文将对其进行理论分析 与具体实现，在研究过程中，注重与新一代智能r f i d 系统的结合，应用拥有强 大功能的f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 做为算法运行的微处理器，这 种思路将是未来r f i d 技术发展的重要方向，r f i d 技术中的关键算法与先进的 电子技术f p g a 的结合，将为r f i d 技术的应用拓开广阔的前景。 1 5 本文的主要工作 本文将在r f i d 技术的前提下，结合当前数字电路设计的主流思路，重点研 究r f i d 的关键技术防碰撞算法，并主要着眼于其中基于应答器的确定性算法， 即二进制树防碰撞算法，在理论分析的基础上，对其进行具体实现。 基于上述考虑，论文将分四章来予以讲述，文章结构与内容安排如下： 第1 章：绪论。系统的介绍了r f i d 技术，描述了典型r f i d 系统的结构组 成，提出了r f i d 系统的分类思想，讲述了r f i d 系统的工作原理，以及其应用 范围，重点强调了r f i d 技术的现状和所面临的主要问题，由此体现了研究r f i d 关键技术防碰撞算法的意义，明确了本文的主要研究内容。 第2 章：现有r f i d 二进制树防碰撞算法。概要性的描述了r f i d 防碰撞算 法，对其进行了分类，重点介绍其中的二进制树防碰撞算法，研究了三种最基本 的二进制树算法，对其进行了原理阐述，性能分析，以及实例演示。 第3 章：改进型二进制树防碰撞算法。二进制树防碰撞算法在多个国际标准 中均有规定，基于i s 0 1 4 4 4 3 标准的t y p ea 是其中的一个典型例子，本章首先 介绍了涉及到二进制树防碰撞算法的几个标准，其次详细研究了i s o l 4 4 4 3 标准 对二进制树防碰撞算法的规定，最后提出了在此基础上的改进算法，这也是本章 的重点。 第4 章：f p g a 实现改进型二进制树防碰撞算法。f p g a 技术是目前数字电 路设计的主流思路，利用f p g a 做主处理器，是r f i d 技术发展的方向，本章探 讨了这一想法，介绍了f p g a 技术的相关要点，并应用f p g a ，实现了改进型二 进制树防碰撞算法。 硕 学位论文 第2 章现有r f i d 二进制树防碰撞算法 2 1r f i d 防碰撞算法概述 r f i d 系统的数据通信双方是读写器和应答器，在实际的r f i d 系统工作时， 可能会出现同时多个读写器和多个应答器共存的情况，毫无疑问，此时系统的数 据交换就会出现信道与时序上的重叠，也就是发生了碰撞，在多个读写器与多个 应答器的射频识别系统中，存在着两种形式的冲突方式，一种是同一应答器同时 收到不同读写器发出的命令，另一种是同一个读写器同时收到多个不同应答器返 回的数据，前者我们称为读写器碰撞，后者称为应答器碰撞【9 】，在实际应用当中， 一般是读写器做为主设备，来识别多个应答器，所以发生读写器碰撞的应用场合 是不多的，因此下文将着重研究应答器碰撞。 在上述前提下，有两种类型的通信方式，一种是读写器发送的数据同时被多 个应答器接收，称为“无线广播”，另一种是多个应答器的数据同时传送给读写器， 称为“多路存取”，两者都是无线电技术中长期面临的难题，同时也发展出一系列 相应的解决思路，一般来说分为四种，即空分多路( s d m a ) ，码分多路( c d m a ) ， 频分多路( f d m a ) ，时分多路( t d m a ) 1 0 l ，从r f i d 系统的通信形式，功耗，系 统复杂性以及成本多方面综合考虑，时分多路法是最有实际应用价值的，它也是 目前r f i d 防碰撞算法应用中最广泛的一类，时分多路法的基本思想是把整个可 供使用的通路容量按时间分配给多个用户，从而达到在不同时隙将各个应答器一 一识别出来的目的【1 1 1 。时分多路法按照能量的供给者可以分为两大类，一类是 应答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中r f i d 系统分 类思路中的有源系统和无源系统，根据实际应用情况，无源系统是应用最广泛的 一类，所以下文重点研究读写器驱动型的时分多路法。 在该类读写器驱动型时分多路法中，目前最常用的防碰撞算法有两种，一类 是基于时隙a l o h a 的统计型算法，另一类是基于二进制树的确定型算法，统计 型算法的意义是在一定的时隙范围内，系统有可能识别出所有应答器【i2 1 ，确定 型算法的最大优点是，在一定的时隙范围内，系统一定可以将所有的应答器一一 识别出来【1 3 1 。从应用的角度来说，正确有效的识别是实际所需要的，因此下文 将着重于二进制树防碰撞算法的研究。 r f l d 二进制树防碰掩算法的研究j 实现 2 2r f i d 二进制树防碰撞算法概述 2 2 1 基本概念 在r f i d 防碰撞算法中，二进制树算法是目前应用最广泛的一族，之所以称 为“二进制树”，是因为在算法执行过程中，读写器要多次发送命令给应答器，每 次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这个分 组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分 叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。 为了便于描述算法，声明一些基本概念如下： 首先，在r f i d 系统当中，每个应答器都是独一无二的，它们的独立性通过 唯一的自身序列号来体现，该序列号在不同的标准中有不同的名称，如e p c 标 准中称其为电子产品代码e p c ，即英文e l e c t r o n i cp r o d u c tc o d e 的缩写l 4 】， i s 0 1 4 4 4 3 标准中称其为唯一标识码u i d ，即英文u n i q u ei d e n t m e r 的缩写【1 5 1 。 事实上，这些都是对应答器序列号的名称描述，因为下文涉及到的防碰撞算法是 普遍意义上的，既包括了e p c 标准中的规定，也包括了i s o 标准中的规定，因 此在本文对普遍意义上的防碰撞算法的描述过程中，统一用序列号s n ( s e r i a l n u m b e r ) 来描述上述概念( 这里要注意的是，在3 2 描述i s o l 4 4 4 3 标准二进制树 算法时，为尊重原文，保留了u i d 的说法) ，同时，序列号的长度，格式，以 及编码方式也是各个标准各自差异的，为了说明的便利，统一定义为8 位长度的 二进制码。如图2 1 所示。 m s b l s b b 8b 7b 6b 5b 4b 3b 2b 1 图2 1 厕答器序歹u 号数据格式 读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部 位，此时的传输顺序定义为：先发送低位，再发送高位。 在读写器或者应答器内部，对数据进行比较时，遵循这样的原则，即按位依 次比较，先比较低位，再比较高位，约定0 1 ，根据这个比较顺序，在判断大小 时，低位数据优先，即两数a ，b 相比较，从低位开始的第一个不相等位的大小 决定了两数的大小，只有当两个数的全部位均相等时，两数才相等。 2 2 2 性能指标 定义碰撞解决时期c r i ，即c o l l i s i o nr e s o l u t i o ni n t e r v a l 【16 1 ，即解决一个读写 器工作范围内碰撞所需要的时隙数，对二进制树算法的评价，一些常用的性能指 标如下所示1 7 l ： 8 硕十学位论文 首先是算法执行效率，7 ，定义如下：在算法执行过程，一共厶个时隙，识别 了n 个应答器，则刁= 刀厶表示算法的执行效率。 分析如下： 刀= l ，显而易见，在第一个时隙内不发生碰撞，可以成功识别该应答器， o = l 。 刀2 ，由于应答器序列号的唯一性，将有碰撞发生，在一个时隙内发生碰 撞的概率p 是一个随机事件，在n 个应答器信息包中i 个发生碰撞的概率为： 9 ( ，1 ) ：f ? 1 p ( 1 一p ) 疗一f o f 月 ( 2 1 ) i 给出i 个碰撞，则c r i 的长度为： 三”i f = 1 + 三j + 三f l 疗2 ( 2 2 ) 其中1 是n 个信息包最初的一个时隙，三，是i 个碰撞的顺利传输的时隙，厶一- 是n i 个无碰撞传输的时隙。 由上式可知，厶是逐渐递归的，通过递归可得： n ln 1 + 9 ( 刀) 厶+ 9 ( 刀) 厶一t 厶= 一l 一) 一9 ( 玎) ( 2 3 ) 一一i l + 9 ( 珂) + 9 一，( 行) 似 刀2 1 一q o ( 玎) 一9 ( 刀) 根据式( ) ，上式可化为： 三一= - + 差( ： e i _ 筠刀2 c 2 4 ， 由此可见，厶是关于p 的函数，则玎= 胛厶也是关于p 的函数，一般情况下， 可以参考二项分布，将p 取为1 2 。 算法的第二个重要的性能指标是稳定性，显然，基于t d m a 的二进制树防 碰撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期c r i ，定义一 个随机变量三( 七) ，表示第k 个c r i 的长度，这些( 七)七= o ，l ，2 一形成一 个马尔可夫链( m a r k o vc h a i n ) ，因为第七+ 1 个c r i 的长度由它开始的第一个时 隙传输的信息，也就是在k 个c r i 区间内到达的信息包决定的，所以，如果马 尔可夫链满足遍历性分布，那么这个系统就可以说是稳定的。 马尔可夫链遍历性分布要满足下列两个条件【1 7 1 ： ( 1 ) ie l 三( i j + 1 ) 一三( 七) i i ( 七) = l( 2 5 ) ( 2 ) l i m s u p e i 三( 七+ 1 ) i ( 三( 七) = f ) i o ( 2 6 ) 这里有： r f i d 二进制树防碰掩算法的研究j 实现 e 【三( 七+ 1 ) l ( ( 七) = 叫= 厶昱 ( 2 7 ) n = o 三。也就是n 个信息包从发生碰撞开始传输的c r i 区间长度的数学期望，旯是 在一个时隙内到达这个系统信息包的期望值，该过程属于泊松过程【l 9 1 。 一般来说，在二进制树防碰撞算法中，系统都能够满足马尔可夫链的两个遍 历性分布条件，即作为一种确定型的算法，二进制树防碰撞算法是稳定的。 算法的第三个重要性能是系统通信复杂度，显而易见，系统的通信双方是读 写器与应答器，则通信复杂度也应该从这两方面着手考虑，即读写器与应答器各 自发送的数据位的位数。该指标的评价标准是基于能量消耗的角度的，即发送的 数据信息量越少，则整个系统消耗的能量也越少，这显然是一个理想的效果。 2 2 3 算法分类 在基本的二进制树搜索算法的基础上，有多种形式的二进制树搜索算法，它 们之间主要的区别在于命令的数据形式，主要有两点。 ( 1 ) 命令参数是1 b i t 数据，还是多b i t 数据。 ( 2 ) 命令参数长度是固定的，还是变化的。 图2 2 是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按照 命令参数分为1b i t 和多b i t ，根据传输的命令参数的长度分为定长二进制树和动 态二进制树两种，根据二进制树遍历时是一轮前进到底的还是退避返回的分为前 进二进制树和退避二进制树两种。需要说明的是，这只是一个大略的分类法，主 要目的在于说明二进制树分类的基本原则。事实上，分类所得的这些算法中也有 互相重合的，如动态二进制树算法既可以采用前进思路，也可以采用退避思路。 另外，在具体应用时，可能还存在多种不同的说法，如lb i t 长二进制树中还有 修正二进制树m b b t ，加强二进制树e b b t 等区别【2 0 1 。 图2 2 二进制树算法分类 硕士学位论文 2 3 基本二进制树防碰撞算法 2 3 1 算法思路 定义两个具有普遍意义的命令来描述算法： ( 1 ) 请求命令r e q u e s t ( s n ) ：该命令携带一个参数s n ，应答器接收到该命 令，将自身的s n 与接收到的s n 比较，若小于或者等于，则该应答器回送其s n 给读写器。注：r e q u e s t ( s n ) 初始值设为r e q u e s t ( 1 1 1 11 11 1 ) 。 ( 2 ) 休眠命令s l e e p ( s n ) ：该命令携带一个参数s n ，应答器接收到该命 令，将自身的s n 与接收到的s n 比较，若等于，则该应答器被选中，进入休眠 状态，也即是不再响应r e q u e s t 命令，除非该应答器通过先离开读写器工作范围 再进入的方式重新上电，才可以再次响应r e q u e s t 命令。 基本二进制树算法的流程图如图2 3 所示： 图2 3 基本二进制树算法流程 基本二进制树算法的步骤如下： ( 1 ) 应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答 器的序列号均小于该最大序列号，所以在同一时刻将自身序列号返回给读写器。 r f i d 二进制树防碰掩算法的研究j 实现 ( 2 )由于应答器序列号的唯一性，当应答器数目不小于两个时，必然发生 碰撞发生碰撞时，将最大序列号中对应的碰撞起始位设置为o ，低于该位者不 变，高于该位者设置为l 。 ( 3 )读写器将处理后的序列号发送给应答器，应答器序列号与该值比较， 小于或等于该值者，将自身序列号返回给读写器。 ( 4 )循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进 行正常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不再 响应读写器请求命令。也就是说，下一次读写器再发最大序列号时，该应答器不 再响应。 ( 5 ) 重复上述过程，即可按序列号从小到大依次识别出各个应答器。 注：第五步时，从步骤1 开始重复，也就是说，读写器识别完一个应答器后， 将重新发送原始的最大序列号。 2 3 2 实例演示 根据上述分析，下面给出一个基本二进制树搜索算法的实例演示，如图2 4 所示。 假设r f i d 系统中有一个读写器r ，四个应答器t l ( 10 1 0 0 10 1 ) ，t 2 ( 1 0 l0 1 10 1 ) ，t 3 ( 1 10 10 10 1 ) ，t 4 ( 1 11 0 1 10 1 ) ，在某一时刻，四个应答器 同时进入读写器的工作范围之内，读写器发出命令，四个应答器同时响应，由于 其序列号s n 的唯一性，将发生应答器碰撞，从而启动防碰撞循环，分析如下： r e q u e s t ( 1 1 l l l l l l ) 像一j - i 、 r c q u c s t ( 1 lll o l 0 1 )r e q u e s t ( 1 0 1 0 i1 0 1 ) 心 形 ； 太、 ： 2 ：3 r c q s t ( 1l l o o l 0 1 ) ： 形_ j _ s - 州- 。- o o ，。t ，s l “1 1 0 l o l o ”s i p ( 1 0 l o l1 0 1 ) 图2 4 基本二进制树算法实例 硕士学位论文 注：图中共有四轮循环，依次识别出四个应答器，分别以不同格式的线条表 示，并加有循环轮次的数字标识。 ( 1 ) 启动第一轮循环，读写器发送r e q u e s t ( 1 l l l1 11 1 ) 命令，所有应答器响 应该命令，将自身序列号与该s n ( 1 l1 ll l1 1 ) 比较，均小于该值，于是所有应 答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在 读写器接收端发生碰撞，读写器检测到返回数据为l x x x x l o l ，其中x 表示该 位发生了碰撞，读写器做如下处理：将碰撞起始位d 4 位置0 ，低于该位者不变， 高于该位者置l ，得到1 1l l0 l0 1 ，作为下一次r e q u e s t 命令携带的参数值，即 r e q u e s t ( 1 11 1o l0 1 ) 。 ( 2 ) 读写器发送r e q u e s t ( 1 11 1 0 1 0 1 ) 命令，所有应答器响应该命令，将自 身序列号与该s n ( 1 11 10 l0 1 ) 比较，其中t 1 ( 1o l0 0 10 1 ) ，t 3 ( 1 l0 1 0 10 1 ) 的 序列号小于该值，则t l ，t 3 返回自身序列号给读写器，在读写器接收端发生碰 撞，读写器检测到返回数据为1 x x x o l0 1 ，读写器做如下处理：将碰撞起始位 d 5 位置o ，低于该位者不变，高于该位者置l ，得到1 1 lo o l 0 1 ，作为下一次r e q u e s t 命令携带的参数值，即r e q u e s t ( 1 1 1 0 0 1 0 1 ) 。 ( 3 ) 读写器发送r e q u e s t ( 1 11 0 0 10 1 ) 命令，所有应答器响应该命令，将自 身序列号与该s n ( 1 110 0 l0 1 ) 比较，其中t l ( 10 1 0 0 l0 1 ) 的序列号小于该值， 则t l 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返 回数据为10 10 0 1 0 1 ，读写器做如下处理：将该数值作为下一次s l e e p 命令携带的 参数值，即s l e e p ( 10 10 0 10 1 ) 。 ( 4 ) 读写器发送s l e e p ( 1 0 1 0 0 1 0 1 ) 命令，所有应答器响应该命令，将自身 序列号与该s n ( 10 l0 0 1 11 ) 比较，其中t 1 ( 1o l0 0 10 1 ) 的序列号等于该值，则 t 1 执行该命令，进入休眠状态，即除非重新上电，否则不再响应r e q u e s t 命令。 ( 5 ) 启动第二轮循环，读写器发送r e q u e s t ( 1 11 l1 11 1 ) 命令，除t 1 外所有 应答器响应该命令，将自身序列号与该s n ( 1 11 11 l1 1 ) 比较，均小于该值，于 是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的 序列号在读写器接收端发生碰撞，读写器检测到返回数据为1 x x x x l0 1 ，其中x 表示该位发生了碰撞，读写器做如下处理：将碰撞起始位d 4 位置o ，低于该位 者不变，高于该位者置1 ，得到1 11 10 10 1 ，作为下一次r e q u e s t 命令携带的参数 值，即r e q u e s t ( 1 11 1 0 10 1 ) 。 ( 6 ) 读写器发送r e q u e s t ( 1 11 1 0 1 0 1 ) 命令，除t l 外所有应答器响应该命 令，将自身序列号与该s n ( 11 l10 10 1 ) 比较，其中t 3 ( 1 l0 1 o l0 1 ) 的序列号小 于该值，则t 3 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器 检测到返回数据为1 1 0 l 0 10 1 ，读写器做如下处理：将该数值作为下一次s l e e p 命令携带的参数值，即s l e e p ( 1 1 0 1 0 1 0 1 ) 。 r f i