（计算机科学与技术专业论文）rfid抗冲突算法研究.pdf

硕l j 学位论文 摘要 无线射频识别( 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 ) 是一种非接触式的 自动识别技术，它通过射频信号自动识别目标对象并获取相关数据，识别工作无 须人工干预。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 系统原理，阐述了抗冲突技术的发展和意义，对常用的 抗冲突算法进行性能比较和分析。 针对二进制树形算法集合分裂速度慢、标签分裂不均匀问题，提出一种基于 b + 树的r f i d 抗冲突算法。本算法将冲突集合分裂成一个3 阶的b + 树，每次将 发生冲突的集合分裂成3 个子集，加快冲突集合的分裂速度。冲突集合相当于 b + 树的中间节点，每个子集分别对应于一个关键码。叶子节点或只包含一个标 签或为一个空集合。为了防止集合分裂的不均匀，引入散列函数，使集合均匀分 裂。仿真实验表明，b + 算法减少了标签冲突的发生，缩短了标签识别延时，提 高了识别性能。 通过对r f i d 系统安全性方面的研究现状的分析，在基于b + 树的抗冲 突算法的基础上，提出了一种安全的b + 树抗冲突算法，加入了对安全的考 虑，不仅在数据交换前进行安全检测而且在抗冲突算法开始前也进行安全验 证，从而在多标签情况下，系统能实现双重的安全保护，为维护r f i d 系统 的安全性提供了一个新的思路。 在基于b + 树的抗冲突算法的基础上提出了一种改进的b + 算法，在继承 b + 算法快速分裂冲突集合的优点的基础上，利用曼彻斯特编码特性和数组， 缩短每个时隙标签的传输时间，仿真实验表明，该算法缩短了识别延时，提 高了识别性能。 关键词：r fid ；b + 树；抗冲突；安全 i i r f i d 抗冲突算法研究 a b s t r a c t 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 sac o n t a c t l e s s ，1 0 wp o w e r ，a n dl o w c o s tw i r e l e s sc o m m u n i c a t i o n t e c h n o l o g y r f i de n a b l e si d e n t i 行c a t i o nf r o ma d i s t a n c e r f i do f f e r sg r e a tb e n e f i t sf o rs u p p l yc h a i nm a n a g e m e n t ，i n v e n t o r yc o n t r o l ， a n dm a n yo t h e ra p p l i c a t i o n s o w i n gt ot h es h a r e dw i r e l e s sc h a n n e lb e t w e e nt a g sa n d r e a d e rd u r i n gc o n l m u n i c a t i o n ，c o l l i s i o n sw i l lo c c u r ，w h e ni o t so f t a g sr e p l yt or e a d e f i nt h es a m et i m e i nt h i sm o m e n t ，r e a d e rc a n n o ti d e n t i f yt h er e s p o n s ew h i c hw a s g e n e r a t e db yw h i c ht a g s h o wt or e d u c et h ec o l l i s i o nr a t ei st h ek e yp o i n tt h a tc a n i n n u e n c et h ep e r f o r m a n c eo fa nr f i ds y s t e m t h e r e f o r e ，ag o o da n t i c o l l i s i o n a l g o “t h mp l a y sa ni m p o r t a n tr o l ef o ra ne 踊c i e n tr f i ds y s t e m t h ee x i s t i n ga n t i c o l l i s i o nm e t h o d sa r eu n a b l et op r o v i d eb e t t e rr e a d i n gr e s u l t s s o ，t h er e s e a r c h e si nt h i st h e s i sf o c u so nt h ea n t i c o l l i s i o nm e t h o d si nr f i d t h i s p a p e rf i r s t l yi n t r o d u c e st h ep r i n c i p l eo fr f i ds y s t e m ，e x p o u n d st h e d e v e l o p m e n ta n ds i g n i f i c a n c eo fa n t i c o l l i s i o nt e c h n o l o g yi nr f i d t h e ns o m e c o m m o na n t i c o l l i s i o na l g o r i t h m sa r es i m u l a t e da n dc o m p a r e d a ni m p r o v e da n t i c o l l i s i o na l g o r i t h mb a s e do nb + t r e ew a sp r o p o s e d i nt h e a l g o r i t h m ，t h ec o l l i s i o nt a g sa g g r e g a t i o ns p l i t si n t ot h r e es m a l l e ra g g r e g a t i o n sa t e a c hr o u n ds oa st oq u i c k e nt h er a t eo fs p l i t t i n g c o l l i s i o na g g r e g a t i o nc o r r e s p o n d s t ot h ei n t e m e d i a t en o d eo ft h eb +t r e e e a c hk e yc o r r e s p o n d st oas p l i t t e d a g g r e g a t i o n e a c hl e a fo ft h et r e ec o n t a i n so n et a go rn u l l m e a n w h i l et h i sa l g o r i t h m m a d eu s eo fh a s ho p e r a t i o nt oa v e r a g es p l i t t i n g s i m u l a t i n gr e s u l t ss h o wt h a tt h ef + a l g o r i t h mr e d u c e dc o l l i s i o n ，s h o r t e n e dt h ei d e n t i f yd e l a ya n di m p r o v e dt h ei d e n t i f y p e r f o m a n c e as e c u r ea n t i - c o l l i s i o n a l g o r i t h mb a s e do nb + t r e ew a sp r o p o s e d i ta d d s s e c u r i t yt ot h ea n t i - c o l l i s i o na l g o r i t h m i ta d v a n c e san e wi d e at h a tm a k i n gs e c u r i t y t e s tb e f - o r et h ea n t i - c o l l i s i o np r o c e s s i tc a nm a k ed o u b l ep r o t e c t i n gi nt h es i t u a t i o n o fm u l t i - t a g s a ni m p r o v e db + t r e ea n t i c o l l i s i o na l g o r i t h mw a sp r o p o s e d i ti m p r o v e st h e b + a l g o r i t h m ，a n di n h e r i t st h ea d v a n t a g e so fw h i c h i tu s e sm a n c h e s t e rc o d ea n d a r r a yt or e d u c et h et i m eo fi d e n t i f i y i n g t h es i m u l a t i o ns h o w st h a tt h ep r o p o s e d s c h e m eu s e sf e w e rt i m ef o fi n d e n t i f y i n gt a g s k e yw o r d s ：r f i d ；a n t i c o l l i s i o n ；b + t r e e ；s e c u r i t y i i i 顶i 学位论文 插图索引 图1 1r f i d 系统组成3 图1 2 电子标签4 图1 3 阅读器4 图2 1 状态转换图1 2 图2 2 纯a l o h a 算法的碰撞窗口1 7 图2 3 帧示意图17 图2 4b t 与a b s 搜索点比较图2 1 图2 5 纯a l o h a 仿真实验2 2 图2 6 总时隙仿真结果2 2 图2 7 冲突时隙仿真结果2 3 图3 1 二进制树形算法的标签分裂2 6 图3 2 二进制树形算法较差情况下的标签分裂2 7 图3 3 基于b + 树的抗冲突算法分裂过程2 7 图3 4 标签识别树3 2 图3 5 仿真结果3 4 图3 6h a s h 锁3 5 图3 7 随机h a s h 锁3 6 图3 8h a s h 链3 7 图3 9 安全的b + 算法流程3 8 图4 1 曼彻斯特编码能按位识别出碰撞位4 0 图4 2 冲突集合的树形分裂过程一4 3 图4 3 总时隙仿真实验一4 4 图4 4 冲突时隙仿真实验4 5 图4 5 延时仿真实验4 5 v i r f i d 抗冲突算法形f 究 附表索引 表2 1b f s a 的识别过程1 8 表2 2a b s 标签算法2 0 表2 3a b s 阅读器算法2 0 表3 1 标签算法3 l 表3 2 阅读器算法一3 l 表3 3 标签识别过程一览表一3 2 表4 1t i d 数组在每个时隙的值4 3 表4 2 改进的b + 算法分裂过程4 3 v n 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：江易飞 日期：加年多月弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：汪云飞 导师签名：甲碌 日期：加c y 年石月弓日 日期：矽年占月3 日 硕士学位论文 1 1 引言 第1 章绪论 r f i d ( r a d i of r e q u e n c yi d e n t i 行c a t i o n ) 即无线射频识别是一种非接触式的 自动识别技术【l 】，它通过射频信号自动识别目标对象并获取相关数据，识别工作 无须人工干预，作为条形码的无线版本，r f i d 技术具有条形码所不具备的防水、 防磁、耐高温、使用寿命长、读取距离大、标签上数据可以加密、存储数据容量 大、存储信息更改自如等优点，其应用将给零售、物流等产业带来革命性变化。 r f i d 系统的关键技术之一是标签抗冲突技术【2 】，阅读器范围内的多个标签 同时传输会引起信号冲突，从而无法正确识别标签内容，没有良好的抗冲突机制， 就无法实现多张标签的同时识别，而在r f i d 应用中多标签识别是普遍会遇到的 问题，因此r f i d 抗冲突技术至关重要，一个性能良好的标签抗冲突算法，对 r f i d 系统具有重大意义。 1 2r f i d 技术及发展 r f i d 最早曾在第二次世界大战中用来在空中作战行动中进行敌我识别【3 】， 当时英国用以确认进入机场的是否为己方的飞机，以免遭误击。 2 0 世纪9 0 年代起，这项技术被美国军方广泛使用在武器和后勤管理系统上。 美国在“伊拉克战争 中利用r f i d 对武器和物资进行了非常准确地调配，保证 了前线弹药和物资的准确供应。和以往的“充足 供应有所不同，现代化的管理 强调的是准确供应，也就是需要多少就提供多少，因为多余的供应会增加不必要 的管理成本。 许多欧美国家高速公路有电子收费站，只要凭着黏在车上的r f i d 辨识卡片， 就可直接通过收费道自动扣款，不须停车。 在香港，这一技术最为普遍的应用就是公共汽车、火车和渡船上使用的“无 接触o c t o p u s 卡，主要方便小型货物存放和自动售货等。r f i d 芯片也是北京 市一卡通工程中所采用的主要技术。 r f i d 技术能够被广泛应用在民用领域得益于两个推动力量【4 】：第一就是芯 片制造成本被大幅度降低，从起初的几十美元降低到几个美分，使得r f i d 电子 标签可以为超市的管理者接受；第二就是用户对r f i d 技术的广泛接受，欧洲最 大的超市麦德龙和美国最大的超市沃尔玛在2 0 0 3 年和2 0 0 4 年试用r f i d 的决定 加速了r f i d 技术的普及。尤其足美国零售业巨头沃尔玛要求其主要供货商使用 r f i d 标签，对r f i d 技术的推动功不可没。沃尔玛有7 0 的货物都源自中国。 r f i d 抗冲突算法研究 沃尔玛前1o o 位供货商和美国国防部花费大量资金用于把r f i d 数据编码和数据 捕捉系统整合进入信息网络之中，为供货商的生产和分配活动提供支持。 r f i d 的驱动力量是市场，这点和其他的i t 技术有所不同。普通的消费者 对r f i d 还没有一个清楚的印象，是超市和管理机构的关注让民众对r f i d 产品 产生了兴趣。 在市场需求方面，世界上最项尖的零售业巨头沃尔玛、塔斯科( t e s c o ) 、麦德 龙( m e t r o ) 要求其供应商提供的商品必须有r f i d 标签；在中间软件开发上，有微 软、甲骨文( o r a c l e ) 、s u n 等i t 巨擎宣布进军r f i d 的软件开发；在硬件设备供 应上，a l i e n 、飞利浦、德州仪器、i b m 等宣布针对日益成熟的r f i d 智能卡市 场进行战略联盟；在技术标准方面，总部设在美国麻省理工学院( m i t ) 的a u t o i dc e n t e r 和日本u b i q u i t o u si dc e n t e r 也相继提出独立适用的r f i d 技术标准。 在供应链管理和物流管理中，信息的准确性和及时性是关键，这恰恰就是电 子标签的最大优点之一。电子标签可以放置到物品的任何位置，只要在阅读器可 以读到的范围( 从几厘米到几米不等) ，就可以迅速地读出其中的数据。借助电 子标签，可以实现商品对原料、半成品、成品、运输、仓储、配送、上架、最终 销售，甚至退货处理等环节进行实时监控。这样不仅能提高自动化程度，而且可 以降低差错率，从而显著提高供应链的透明度和管理效率。 电子标签的出现，使得合理的产品库存控制和智能物流技术成为可能。一些 分析家认为，物流和生产方面的工业应用是r f i d 芯片市场发展最强劲的领域。 r f i d 对制造业将有现实促进意义，对制造业常用软件e r p 和s c m 系统来 说是一种革命性的突破，过去的物料编号无法实现对单一部件的跟踪，而今天， 物料的精确化管理却将触角伸到了每一个环节的每一个部件，无论是质量控制、 自动化管理、产品的生命周期管理都将面对过去无法想象的便利。例如，对产品 次品率的分析可以将次品来源定位在某一点，而仓库中的某一个产品也不会因为 同一类产品的数量过多而被单独过久放置。 德国麦德龙集团( m e t r o ) 在其最新建立的“r f i d 创新中心”安装了一台 n c r 的自助结帐系统，它不仅可以读取条码，还能读取无线射频识别( r f i d ) 标 签。 麦德龙集团建立的“创新中心”位于德国诺伊斯，目的是为了与合作伙伴共 同发展r f i d 技术在零售领域的应用。 安装在“创新中心的n c rf a s t l a n e 是全球首个集成了r f i d 阅读器的自 助结帐解决方案。在其目前的应用中，混合型自助结帐系统在扫描过程中同时解 除了r f i d 标签在商品中设置的安全功能，这样顾客在结完帐离_ 丌商店时就不会 引发安全警报。 2 硕上学位论文 “r f i d 创新中心 是麦德龙集团“非凡未来商店”计划的项目之一。在该 计划中，为了促进创新技术在国内乃至国际零售行业的广泛应用，麦德龙集团和 来自i t 、消费产品和服务行业的4 5 名著名合作伙伴，在真实的环境下共同测试 各种新技术在零售业的应用和相互作用。这一计划成为零售业相关技术和流程发 展以及创新的有效平台。在麦德龙集团“非凡未来商店一计划中，众多技术和先 进系统在实践中获测试和进一步发展。长远来说，该计划的目标是为零售业制订 一套能够在国际范围内实施的标准。 随着r f i d 技术的普及，标准化是其广泛获得市场接受的必要措施，同时也 是各国企业发展与国际化的一个良好契机。可以预测，如同“条形码”标准的制 定，r f i d 标准必将在各国或地区标准的基础上，形成国际统一的主流标准，同 时修改与兼容主要国家或地区的标准。 在r f i d 浪潮到来时，人类社会的生产管理效率将得到极大的提高，更多的 人力、物力将集中用于创造与改善人们生活所需的各种服务领域。 1 3 研究背景及意义 r f i d 系统是一种简单的无线系统f 5 】，只有两个基本器件，该系统用于控制、 检测和跟踪物体。系统由一个阅读器和很多标签组成如图1 1 所示。 殴1 1r f i d 系统组成 标签( t a g ) 如图1 2 所示：由耦合元件及芯片组成，每个标签具有唯一的电子 编码，附着在物体上标识目标对象。 阅读器( r e a d e r ) ：读取( 有时还可以写入) 标签信息的设备，可设计为手持式 或固定式；阅读器主要由一个r f 模块和控制单元组成，通常有内置天线，通过 射频信号与标签通信。阅读器可以通过有线连接或无线连接与计算机系统相连， 把接收到的标签信息送到主机进行相应处理。图1 3 是一个手持阅读器。 r f i d 抗冲突算法研究 图l2 电子标签 图13 阅读器 天线( a n t e n n a ) ：在标签和读取器间传递射频信号。 r f i d 技术的基本工作原理并不复杂：标签进入磁场后，接收阅读器发出的 射频信号凭借感应电流所获得的能量发送出存储在芯片中的产品信息( p a s s i v e t a g 无源标签或被动标签) ，或者主动发送某一频率的信号( a c t i v et a g ，有源 杯签或主动标签) ，阅读器读取信息并解码后，送至中央信息系统进行有关数圭瞄 处理。 电子标档有以卜几种分类： ( 1 ) 按供电方式分为有源膏和无源卡。有源 是指卡内有电池提供电源， 其作用距离较远，但寿命有限、体积较大、成本高，且不适合在恶劣环境下工作； 无源卡内无电池，它利用波束供电技术将接收到的射频能量转化为直流电源为卡 内电路供电，其作用距离相对有源卡短，但寿命长且对工作环境要求不高。 ( 2 ) 按载波频率分为低频射频卡、高频射频卡和超高频射频卡。低频射频 棼 硕l 学位论文 卡主要有1 2 5 k h z 和1 3 4 2 k h z 两种，高频射频卡频率主要为1 3 5 6 m h z ，超高 频射频卡主要为4 3 3 m h z 、9 1 5 m h z 、2 4 5 g h z 、5 8 g h z 等。低频系统主要用于 短距离、低成本的应用中，如多数的门禁控制、校园卡、动物监管、货物跟踪等。 高频系统用于需传送大量数据的应用系统；超高频系统应用于需要较长的读写距 离和高读写速度的场合，其天线波束方向较窄且价格较高，在火车监控、高速公 路收费等系统中应用。 ( 3 ) 按调制方式的不同可分为主动式和被动式。主动式射频卡用自身的射 频能量主动地发送数据给读写器；被动式射频卡使用调制散射方式发射数据，它 必须利用读写器的载波来调制自己的信号，该类技术适合用在门禁或交通应用 中，因为读写器可以确保只激活一定范围之内的射频卡。在有障碍物的情况下， 用调制散射方式，读写器的能量必须来去穿过障碍物两次。而主动方式的射频卡 发射的信号仅穿过障碍物一次，因此主动方式工作的射频卡主要用于有障碍物的 应用中，距离更远( 可达3 0 米) 。 ( 4 ) 按作用距离可分为密耦合卡( 作用距离小于l 厘米) 、近耦合卡( 作用距 离小于1 5 厘米) 、疏耦合卡( 作用距离约l 米) 和远距离卡( 作用距离从1 米到1 0 米，甚至更远) 。 ( 5 ) 按芯片分为只读卡、读写卡和c p u 卡。 r f i d 系统的冲突包括阅读器冲突【6 】和标签冲突两种。阅读器冲突是指相邻 阅读器的频率干扰造成对标签的错误识别。标签冲突是由在同一阅读器的问询范 围内的多个标签争用同一信道引发的。 在高速移动这样的场合，抗冲突技术设计的优劣很大程度上决定了射频识别 过程的耗时性能，从而制约了系统识别成功率。 标签冲突问题与计算机网络冲突问题类似。但是，由于r f i d 系统中的一些 限制，使得传统网络中的很多标准的防冲突技术都不适于或很难在r f i d 系统中 应用，这些限制因素主要有：( 1 ) 内存和计算能力的限制，由于标签的成本很低， 其计算能力十分有限，不能执行复杂计算。( 2 ) 一些标准限制了r f i d 系统中的 通信带宽，因此需要尽量减少读写器和标签间传送的信息比特的数目。( 3 ) 标签 不具有载波监听发现冲突的功能而且标签间不能相互通信。 目前的抗冲突算法包括以下几种： 频分多址接入( f d m a ) ，各个标签采用不同载波频率向阅读器传递信号。 这种方式要求阅读器和标签能够以一定的机制更换载波频率，大大增加了阅读器 和标签双发的实现复杂度，同时也要求整个系统覆盖更大的带宽。 码分多址接入( c d m a ) 【7 1 ，各个标签采用不同的调制码来对所发数据进行 调制，从而在阅读器端利用码的自相关特性对不同标签所发的数据进行解调，从 而达到抗冲突的目的。这种方式抗干扰性强，保密性好，但是标签和阅读器的电 5 r f i d 抗冲突算法研究 路复杂性较高。 时分多址接入( t d m a ) ，整个识别过程分成若干个时隙，每个标签在不同 的时隙向阅读器传递信号。这种方式实现结构相对简单，成本较低。 现在常用的抗冲突算法都属于时分多址接入【8 ，9 1 。 r f i d 的核心是抗冲突技术，这也是和接触式i c 卡的主要区别。抗冲突算法 的性能，对于一个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 抗冲突 算法，对几种常用的算法进行了性能分析和比较。 针对二进制树形算法冲突集合分裂速度慢，分裂不均匀的缺点，提出一种新 的基于b + 树的标签抗冲突算法，同时将该算法与二进制树形算法以及动态帧时 隙抗冲突算法进行性能比较。仿真实验表明，b + 算法减少了标签冲突的发生， 缩短了标签识别延时，提高了识别性能。 对r f i d 系统安全性进行研究，在基于b + 树的抗冲突算法的基础上，加入 安全机制，提出一种带有安全检测机制的b + 树标签抗冲突算法，为维护r f i d 系统安全性提供了一种新的思路，而且实现简单具有可行性。 提出一种改进的b + 算法，利用曼彻斯特编码特性和数组，减少冲突时隙， 缩短每个时隙标签的传输时间，并对其进行仿真实验，对改进的b + 算法和几种 常用的抗冲突算法进行了性能比较。 1 5 本论文的结构安排 全文共分为五章： 第一章概述r f i d 技术、组成原理、选题背景和意义以及本文的主要工作。 第二章介绍了现有的r f i d 技术标准，对常用的抗冲突算法纯a l o h a 算法、 帧时隙a l o h a 算法、二进制树形算法以及自适应的二进制树形算法分别进行介 绍。 第三章首先提出一种基于b + 树的r f i d 抗冲突算法，它具有分裂速度快， 6 硕上学位论文 冲突时隙少的优点，同时实现过程简单，降低了标签碰撞产生的延迟问题并与一 些常用的抗冲突算法进行性能仿真比较。其次，在b + 算法的基础上加入了对安 全的考虑，提出一种安全的基于b + 树的r f i d 抗冲突算法，给r f i d 系统安全协 议提出了一种新的思路，给系统提供了双重安全保护。 第四章在第三章所提出的一种基于b + 树的抗冲突算法的基础上提出一种改 进的b + 算法，本算法在继承b + 算法快速分裂冲突集合的优点的基础上，利用曼 彻斯特编码特性和数组，缩短每个时隙标签的传输时间，仿真实验表明，改进的 b + 算法与b + 算法相比，缩短了识别延时，提高了识别性能。 最后总结全文，并对下一步研究工作做出展望。 7 第2 章相关技术概述 2 1 引言 在射频识别系统中，当两个或者多个电子标签同时向同一个阅读器发送信息 时，阅读器将无法识别出任何一个标签的信息，这种现象被称为冲突。当这种情 况发生时，将导致阅读器无法正确的采集标签信息，因此标签冲突问题是r f i d 系统必须解决的关键问题之一。 按照抗冲突算法中标签的响应方式，抗冲突算法通常分为不确定算法和确定 性算法【1 0 1 两种。不确定性算法中标签利用随机时间响应读写器的命令，不确定 性算法大都基于a l o h a 机制。确定性算法大都是基于树的算法。 2 2r f i d 技术标准概述 2 2 1 现有的r f i d 标准组织 目前世界上存在众多的r f i d 标准组织【4 1 ，其中具有重要影响的有e p c g l o b a l ( 美国) 、i s o 、u b i q u i t o u si dc e n t e r ( 日本) 和e t s i ( 欧洲) 组织。另外，还 有a i m 、i p x 和中国r f i d 标准组织。 1 9 9 9 年在m i t ( 麻省里工学院) 设置了总部，设立了非营利的国际研究机 构a u t oi d 中心。2 0 0 3 年1 1 月，a u t oi d 实验室与e p c 国际分离，独立出来进 行活动。该中心策划制定i d 标签体系，以便在全球范围内都能进行每件物品的 识别。a u t oi d 还以面向全世界的公开平台的构筑和国际标准技术开发以及制定 国际标准作为其行动宗旨。 a u t oi d 实验室设立之初就有p g 、吉利、沃尔玛等1 0 4 家公司参加。而后 随着r f i d 技术的推广，现在已有4 0 l 家公司( 其中有17 家日本公司) 都在赞 助a u t oi d 实验室。欧姆龙于2 0 0 3 年4 月加入这个行列。依靠这些赞助，a u t oi d 实验室在全球设立了多处研究开发基地，其中包括美国麻省理工学院、英国剑桥 大学、澳大利亚阿德来德大学、日本庆应义塾大学、中国复旦大学等。 e p c 是由1 9 9 9 年m i t 建立的a u t o i d 中心发展而来，e p c 标准【1 1 】受到美国 政府和众多世界5 0 0 强企业的支持，在供应链物流方面处于主导地位。该组织已 开发出e p c 第一代系列标准，其中c l a s s l ( 8 6 0 m h z 9 6 0 m h z ) 是可读写的基 本类型标签，c l a s s o ( 9 0 0 m h z ) 为只读类型、c l a s s 2 为高级类型、c 1 a s s 3 为半 主动类型、c l a s s 4 为主动类型标签。当前最新二代标准e p cc l a s s lg e n 2 已逐渐 成为物流管理方面的主流标准，同时还被采纳为i s ol8 0 0 0 c 标准。 由于e p c 标准只是针对u h f 频段，它适合长距离的读写( 读取i d 可达8 m 8 硕十学位论文 左右的距离) ，因此主要应用在物流等需要长距离通信的领域。目前e p c 没有对 u h f 以外的其它频段制定标准，也就是说e p c 的主要对象是物流，特别是物流 中的流通领域，如用于购物。 u i d 是日本的标准化组织，u i d 的r f i d 标准能支持1 3 5 6 m h z 和2 4 5 g h z 频率的电子标签。u i d 标准能够与3 g 、p h s 、8 0 2 1 l 等众多网络接入方式互联。 u b i q u i t o u si d 中心设立在东京大学，以坂村健教授为核心，于2 0 0 2 年1 2 月成立，2 0 0 3 年3 月开始进行正式运作。有包括n t t 、n e c 、日立、s o n y 、富 士通等多家日本企业以理事单位或会员身份参加该中心。 u b i q u i t o u s 的意思为“泛在一或“无处不在。u b i q u i t o u si d 主张世界上 几乎所有的地方都可以使用r f i d 。u b i q u i t o u si d 在确保安全的前提下，希望能 够统一和包括a u t oi d 已得到应用的所有范围，并且为其设定了特别的整体安全 结构一一t r o n ( 一种专用的操作系统o s ) 。u b i q u i t o u si d 采用1 2 8 个存储单元 作为编码空间，在各种网络中都可以提取和查询。 e t s i 推出的欧洲r f i d 标准为e t s ie n3 0 22 0 8 ，工作频率在 8 6 5 m h z 8 6 8 m h z ，采用载波信道侦听的方式防冲突，与e p c 有差异。 在中国，r f i d 标准的制定过程有些曲折，早在2 0 0 3 年就成立了电子标签标 准工作组，但随后又停止运作。2 0 0 5 年1 2 月2 日由信息产业部牵头，正式成立 中国电子标签标准工作组。 i s o 是一个重要的r f i d 国际标准化组织，提出的系列标准包括：用于动物 识别的i s o1 l7 8 4 l s o1 17 8 5 i s o1 4 2 2 3 标准，用于集装箱识别的i s o10 3 7 4 标 准，用于非接触式智能卡的i s o10 5 3 6 1 5 6 9 3 l4 4 4 3 标准，用于项目管理的 i s o i e c1 1 7 8 4 系列标准以及可用于商品供应链的i s o1 8 0 0 0 。 2 2 2 常用r f i d 国际标准 目前常用的r f i d 国际标准【5 】主要有用于对动物识别的i s ol17 8 4 和1 l7 8 5 ， 用于非接触智能卡的i s o10 5 3 6 ( c l o s ec o u p l e dc a r d s ) 、i s ol5 6 9 3 ( v i c i n i t yc a r d s ) 、 i s o1 4 4 4 3 ( p r o x i m i t yc a r d s ) ，用于集装箱识别的i s o1 0 3 7 4 等。有些标准正在形 成和完善之中，比如用于供应链的i s o1 8 0 0 0 无源超高频部分。 i s o1 l7 8 4 和1 17 8 5 分别规定了动物识别的代码结构和技术准则，标准中没 有对应答器样式尺寸加以规定，因此可以设计成适合于所涉及的动物的各种形 式，如玻璃管状、耳标或项圈等。技术准则规定了应答器的数据传输方法和阅读 器规范。工作频率为13 4 2 k h z ，数据传输方式有全双工和半双工两种，阅读器 数据以差分双相代码表示。应答器采用f s k 调制，n r z 编码。由于存在较长的 应答器充电时间和工作频率的限制，通信速率较低。 i s o10 5 3 6 标准主要发展于l9 9 2 到l9 9 5 年间，由于这种卡的成本高，与接 9 r f l d 抗冲突算法研究 触式i c 卡相比优点很少，因此这种卡从未在市场上销售。 i s o1 4 4 4 3 和i s o1 5 6 9 3 标准在1 9 9 5 年开始操作，单个系统于1 9 9 9 年进入 市场，两项标准的完成则是在2 0 0 0 年之后。二者皆以13 5 6 m h z 交变信号为载 波频率：i s o l 5 6 9 3 读写距离较远，当然这也与应用系统的天线形状和发射功率 有关；而i s o1 4 4 4 3 读写距离稍近，但应用较广泛，目前的第二代电子身份证 采用的标准是i s o1 4 4 4 3t y p eb 协议。 i s 0 1 4 4 4 3 定义了t y p ea 、t y p eb 两种类型协议，通信速率为1 0 6 k b i t s s ， 它们的不同主要在于载波的调制深度及位的编码方式。 在1 3 5 6 m h z 的非接触式i c 卡又可分为紧耦合i c 卡( p i c c ) 和疏耦合卡 ( v i c c ) 。其读写器亦被称之为p c d 和v c d 。 从p c d 向p i c c 传送信号时，t y p ea 采用改进的m i l l e r 编码方式，调制深 度为1 0 0 的a s k 信号；t y p eb 则采用n r z 编码方式，调制深度为l o 的a s k 信号。 从p i c c 向p c d 传送信号时，二者均通过调制载波传送信号，副载波频率皆 为8 4 7 k h z 。t y p ea 采用开关键控( o n o f f k e y i n g ) 的m a n c h e s t e r 编码；t y p e b 采用n r z l 的b p s k 编码。 t y p eb 与t y p ea 相比，由于调制深度和编码方式的不同，具有传输能量 不中断、速率更高、抗干扰能力更强的优点。 i s o1 5 6 9 3 标准规定的载波频率亦为1 3 5 6 m h z ，v c d 和v i c c 全部都用a s k 调制原理，调制深度为1 0 和1 0 0 ，v i c c 必须对两种调制深度正确解码。 从v c d 向v i c c 传送信号时，编码方式为两种：“2 5 6 中取l ”和“4 中取1 。 二者皆以固定时间段内以位置编码。这两种编码方式的选择与调制深度无关。当 “2 5 6 中取1 ”编码时，1 0 的a s k 调制优先在长距离模式中使用，在这种组合 中，与载波信号的场强相比，调制波边带较低的场强允许充分利用许可的磁场强 度对i c 卡提供能量。与此相反，阅读器的“4 中取1 编码可和1o o 的a s k 调 制的组合在作用距离变短或在阅读器的附近被屏蔽时使用。 从v i c c 向v c d 传送信号时，用负载调制副载波。电阻或电容调制阻抗在 副载波频率的时钟中接通和断开，而副载波本身在m a n c h e s t e r 编码数据流的时 钟中进行调制，使用a s k 或f s k 调制。调制方法的选择是由阅读器发送的传输 协议中f l a g 字节的标记位来标明，因此，v i c c 总是支持两种方法：a s k ( 副载 波频率为4 2 4 k h z ) 和f s k ( 副载波频率为4 2 4 4 8 4 k h z ) 。数据传输速率的选择同 样由f l a g 中的位来表明，而且必须两种速率都支持：高速和低速。 i s 0l5 6 9 3 应用更加灵活，操作距离又远，更重要的是它与i s o18 0 0 0 3 兼 容，了解i s 015 6 9 3 标准对将来了解我国的国家标准是有助益的，因为我国的国 家标准肯定会与i s o1 8 0 0 0 大部分兼容。 1 0 硕十学位论文 如果在同一时间段内有多于一个的v i c c 或p i c c 同时响应，则说明发生冲 撞。 i s o1 4 4 4 3 3 规定了t y p ea 和t y p eb 的抗冲突机制。二者抗冲突机制的 原理不同：前者是基于位冲撞检测协议，而t y p eb 通过系列命令序列完成抗冲 突；i s o1 5 6 9 3 采用轮寻机制、分时查询的方式完成抗冲突机制。 抗冲突机制使得同时处于读写区内的多张卡的正确操作成为可能，只用算法 编程，阅读器即可自动选取其中一张卡进行读写操作。这样既方便了操作，也提 高了操作的速度。 如果与硬件配合，可用一些算法快速实现多卡识别，比如t i 公司的r 6 c 接 口芯片有一个解码出错指示引脚，利用它可以快速识别多张卡：当冲撞产生时引 脚电平发生变化，此时记录下用来查询的低u i d 位，然后在此低位基础上增加 查询位数，直到没有冲突发生，这样就可以识别出所有卡片。 i s o1 0 3 7 4 标准说明了基于微波应答器的集装箱自动识别系统。应答器为 有源设备，工作频率为8 5 0 m h z 9 5 0 m h z 及2 4 g h z 2 5 g h z 。只要应答器处 于此场内就会被活化并采用变形的f s k 副载波通过反向散射调制做出应答。信 号在两个副载波频率4 0 k h z 和2 0 k h z 之间被调制。此标准和i s o6 3 4 6 共同应 用于集装箱的识别，i s o6 3 4 6 规定了光学识别，i s o10 3 7 4 则用微波的方式来表 征光学识别的信息。 i s ol8 0 0 0 是一系列标准。此标准是目前最新的也是最热门的标准，原因是 它可用于商品的供应链，其中的部分标准也正