（电路与系统专业论文）rfid系统基aloha标签防冲突算法的研究.pdf

摘要 标签防冲突技术是r f i d 系统中最关键的技术之一，即当有多个标签同时向 阅读器发送数据时，阅读器能否正确地识别标签。随着f u f i d 技术的发展，标签 冲突已经成为急需解决的问题之一。标签防冲突算法主要包括随机性算法和确定 性算法两种类型。确定性算法( 主要是树形搜索算法) 识别准确度高，对硬件的 要求高，不容易实现。随机性算法主要是基于a i o h a 的算法，现有的a 1 0 h a 算法 存在系统吞吐率较低，无法识别处于冲突状态的标签，不适合用于标签数量大的 场合等缺点。 本文在对现有的标签防冲突技术进行了详细的分析和比较后，提出了一种新 的基于分组算法的标签防冲突算法( n e wg r o u pf r 唧e ds l o t t e da l o h a ，n g f s a ) 。 本文主要的创新点如下： ( 1 ) 对已有的分组算法的分组数调整方法进行了优化，优化后的分组算法 避免了在组内发生时隙浪费的现象，使分组算法的系统吞吐率维持在一个稳定的 状态； ( 2 ) 在深入分析现有随机性算法之后，在分组算法的理论基础上，提出了 一种新颖的基于分组算法的标签防冲突算法刊g f s a ，该算法在处理冲突时 隙内的标签时，采用了栈的思想，通过对冲突时隙内的标签进行再次分组，并结 合栈的入栈和出栈操作，逐步完成对冲突时隙内的标签的识别。 仿真结果表明，本文提出的n g f s a 算法使系统的吞吐率得到了进一步的提 高，能够识别出冲突时隙内的所有标签，适合用于标签数量大的场合。 关键词：射频识别；防冲突算法；标签冲突；时隙a l o h a ；分组 a bs t r a c t t a g sr e a d i n ga n t i c o l i i s i o nt e c h n o l o g yi so n eo ft h em o s tc r i t i c a l t e c h n o i o g i e si n t h ei 讧i ds y s t e m s ，t 1 1 a ti s ，、h e t h e rt h e 他a d e ri d e n t i 母t 1 1 et a gc o r r e c t i yw h e nt h e r e 撒 m u i t i p i et a g ss e n d i n gc i a t at 0t h e 诧a d e rs i m u l t a n e o u s i y w i t ht h ed e v e i o p m e n to f i 强i dt e c h n o i o g y t a g - c o l l i s i o ni sb e c o m i n go n eo ft 1 1 es e r i o u sp r o b l e m sn e e d e dt ob e s o l v e d t h ga n t i - c o l i i s i o na l g o r i t h r i l s i i l c l u d em n d o ma l g o r i t h ma n dd e t e n n i n i s t i c a l g o r i t h m t h ei d e n t i f i c a t i o na c c u m c y o fd e t e m i n i s t i ca l g o r i t h m ( m a i n i yt r l c es e a r c h a l g o r i t h m ) i sr e l a t i v e l yh i g h ，b u ti ti sd i 衢c u i tt 0 陀a l i z eb e c a u s eo fh i 曲r e q u i r c m 锄t s f o rt h eh a r d w a r c r 锄d o ma l g o r i m mi sm a i n l yb a s e do na l o h aa l g o r i t h m s ，t l l e e x i s t i n ga l o h aa l g o r i t h m sh a v el o ws y s t e mt h r o u g l l p u t ，w h i c hd on o ti d e n t i 母t l l et a g i nas t a t eo fc o n f l i c t 锄di su n s u i t a b l ef o rt h es i t u a t i o no fl 盯g en u m b c ro ft a g s a r e r 锄a 1 ) r z m g 锄dc o m p 撕n go ft h ee x i s t i n gm d o ma l g o t h m s ，an e wt a g a n t i - c o i l i s i o na i g o r i t h mw h i c hb a s e do nt l l e 目0 u pa l o h aa l g o r i t l l m o n g f s ai s p r o p o s e di nt h i sp a p e r t h ei 肌o v a t i v ep o i n t so f t h i sp a p e r i n c l u d e ： ( 1 ) t h eg r o u pa d j u 鲫m e n tm e t h o do f t h ee x i s t i n gg r o u pa l g o r i t l l mi so p t i m i z e d ； m eo p t i m i z e da l g o r i m mw h o s es y s t e mt h m u g h p u tm a i n t a i n sas t a b l es 协t e ，i ta l s o a v o i d s 、 馏圆t i n gt i m es i o ti nt t l eg r o u p ； ( 2 ) a r e rt 1 1 e 锄a l y s i so ft h e 似i s t i n g 舢d o ma l g o r i t h m s ，an e wi m p r 0 v e dg r o u p a l o h aa l g o r i t h m - - - n g f s ai sp r o p o s e db a s e do nt h ep 化v i o u ss t u d i e si i lt h i sp a p e r 、h i c hu s e st h ei d e a so fs t a c k 锄d 他- 伊o u p st i i et a g sw h i c ha r ci nt 1 1 ec o n f l i c tt i m e - s 1 0 t ， i tc o m b i n e dw i t ht 1 1 e0 p e r a t i o no fs t a c kt oi d e n t i f yt h ec o n f l i c t i n gt a g ss t e pb ys t e p t 1 1 e 他s u l to fs i m u l a t i o ns h o w st h a t ，t h i sn e wa l g o r i t h m 、 ，h i c hi sn o to n l ys u i t sf o r t h es i t u a t i o nw i t hal a r g cn u m b e ro ft a g s ，b u ta l s oa b l et 0i d e n t i 母a l l 也et a g si nt i l e c o n n i c tt i m e - s l o t ，缸恤e ri m p r 0 v i n gt h es y s t e mt h r o u g h p u t k e yw o r d s ：r f i d ，舳t i - c o l l i s i o na l g o r i 廿啪，魄c o ll i s i o n ，s 1 0 ta l o h a ，g r o u p 第一章绪论 1 1r f i d 技术简介 第一章绪论 射频识别( r a d i of r e q u e n c yi d e n t i f i c a t i ，l u i d ) 技术是一种非接触式的自 动识别技术，它通过射频信号自动地识别目标对象并获取相关数据，识别过程无 需人工干预，可应用于各种恶劣的环境中。 r f i d 系统主要由三部分组成；电子标签、阅读器和数据管理系统。其中， 电子标签芯片具有数据存储区，用于存储待识别物品的标识信息：阅读器在其识 别范围内以非接触方式将电子标签内保存的信息读取出来；数据管理系统用来存 储数据，以便于完成目标识别。r f d 系统还带有天线，用于发射和接收射频信 号，一般情况下天线内置在电子标签和阅读器中。r f i d 技术的基本工作原理是： 电子标签进入阅读器产生的磁场后，凭借感应电流获得能量使标签内部电路开始 工作，标签发送出存储在芯片中的产品信息( 无源标签) ，或者主动发送某一频 率的信号( 有源标签) ；阅读器读取信息并解码后，传送至数据管理系统进行相 关的数据处理i l j 。 表卜li 心d 技术发展情况一览闱 雷达技术的改进与应用催生了r f i d 技术，1 9 4 8 年奠定了i 汀i d 技术 1 9 4 l 1 9 5 0 年 的理论基础： 1 9 5 l 1 9 6 0 年 早期i 心i d 技术的探索阶段，主要处于实验室的研究； 1 9 6 l 1 9 7 0 年i u f i d 技术的理论得到进一步发展，开始了一必应用尝试： r f d 技术和产品研发处于一个大发展阶段，各种r f i d 测试得到加 1 9 7 l 1 9 8 0 年 速，开始了一地早期的l 强l d 应用： 1 9 8 l 1 9 9 0 年r f i d 技术与产品进入到商用阶段，各种应用系统开始出现； r f d 技术的标准化问题日趋得到重视，i 玎d 产品得到广泛采用， 1 9 9 卜2 0 0 0 年 r f d 产品逐渐成为人们生活中的一部分； r f d 产品种类更加丰富，有源电子标签、无缘电子标签和半有源电 子标签均得到发展，电子标签成本不断降低，规模应用行业扩大。 2 0 0 1 年至今i u f d 技术的理论得到丰富和完善，单芯片电子标签、多电子标签识 别、无线可读可写、无源电子标签的远距离识别、适应高速移动的 r f i d 系统正在成为现实。 第一章绪论 r f i d 技术并不是一种全新的技术，其直接继承了雷达的概念，并由此发展 而来。其应用最早可以追溯到第二次世界大战时期，英国空军利用该技术来辨别 敌我之间的战机。表1 1 给出了近七十年以来r f i d 技术发展的过程。 值得注意的是目前随着微电子、计算机以及网络技术的发展，r f i d 技术应 用的范围和深度都得到了快速的发展。目前l u i d 技术已经发展到一个非常关键 的阶段，就是形成全球统一标准的阶段；虽然大规模应用还尚未形成，很多l u i d 技术的相关系统也还是试验或带有验证性质的，但是l u i d 技术走向大规模应用 的发展趋势已经逐渐明朗。在上世纪九十年代，美国在两次海湾战争中对r f i d 技术的成功应用，以及近年来全球有影响的大企业计划在其零售商店和货栈开始 使用r f m 系统，使得r f i d 技术在近几年迅速成为全球瞩目的焦点，并被列为 2 1 世纪最有前途的重要产业和应用技术之一2 j i j j 。 1 2r f i d 技术的应用 1 2 1 国外应用状况 目前i 强i d 技术已经在社会的各个方面得到了应用。其中，以美国的技术最 为成熟，其无论是标准的制定，还是相关软件和硬件的研发以及应用的推广，都 走在了世界的前列。在物流零售业方面，u p s 、d h l 、f e d e x 等国际物流巨头都 在积极试验l 强l d 技术，同时沃尔玛、麦德隆等大超市也在积极推动r f d 技术 的应用；在生产线的自动化及过程控制方面，德国b m w 公司将l u i d 系统应用 在汽车装配线上，以保证能够准确地完成装配任务；m o t o r o l a 公司采用了r f d 技术的自动识别工序控制系统，提高了生产效率；在公共交通领域，高速公路不 停车收费系统已被广泛实施，同时电子月票已经在各国得到了广泛的应用和推 广，德国汉莎航空公司则开始试用射频卡( 电子标签) 作为飞机票，改变了传统 的机票购销方式，简化了机场入关手续；在货物跟踪管理及监控方面，欧盟早在 1 9 9 7 年就要求当年开始生产的新车型必须具有基于射频识别技术的防盗系统； 在动物的跟踪及管理方面，包括澳大利亚在内的许多发达国家都已经采用了射频 识别技术，通过对牲畜个体识别。保证牲畜大规模疾病爆发期间对感染者的有效 跟踪及对未感染者进行隔离控制：同时在美国、欧洲、新加坡等已有图书馆利用 l u i d 技术实现自动租、借、还书等功能的成功案例：美国国防部已与其上万的 供应商正在对军事物资进行电子标签标识与识别1 3 】【4 】【5 1 。 整体来说，目前r f i d 技术在国外( 主要是在欧美发达国家) 得到充分的发 展与应用，其始终引领着全球r f i d 技术应用的潮流。 第一章绪论 1 2 2 国内应用状况 目前国内的应用主要集中在身份识别( 如二代身份证、大学生购票证、门票、 门禁等) 、交通管理( 不停车收费、公交调度、铁路车皮管理、军车车牌管理) 、 危险品管理( 如液化气钢瓶) 等领域，其他领域均在试点尚未大规模应用。 国内的射频识别行业经过十几年的发展到如今已经初具规模，l 玎l d 产业链 已经基本形成。铁路系统早在9 0 年代中期就采用了铁路车辆车号自动识别系统； 深圳海关从1 9 9 7 年起则采用了“自动车辆识别管理系统”，对过境车辆进行管理； 北京高速公路电子不停车收费系统已于2 0 0 9 年5 月1 日进入正式运行阶段；同 时2 0 1 0 年4 月，浙江省为配合上海世博会的举办，开通了省内首条不停车收费 的高速公路。与此同时，已于2 0 l o 年5 月1 日开幕的上海世博会充分利用了l u i d 技术，广泛应用于世博会的门票、物流配送、展馆预约、证件管理、电子车牌等 诸多方面。中国移动将在全球首次推出内置r f i d 模块的手机电子门票，并和交 通银行在园区内提供手机电子支付，提供手机票和手机支付功能，充分展现信息 技术给日常生活带来的便捷1 2 】1 6 】。 相信随着国内r f i d 技术的不断发展和研究的不断深入，未来r f i d 技术在 国内也会得到广泛的应用和大规模的推广，使人们的生活变得更加便捷。 1 3 标签防冲突技术的研究现状 目前，射频识别技术在国内外的发展相当迅速；但在应用上没有国外的广泛， 这主要是因为国内开展相关的研究起步较晚。欧洲、美国和日本在r f i d 技术的 研究上各有千秋，分别制定了自己的射频识别技术的频率标准和技术规范，其研 究相对也比较先进及成熟。 目前解决r f i d 系统多标签冲突的算法主要采用时分多路机制，其大致可分 为两大类：一类是随机性方式，如：a l o h a 算法；另一类是确定性方式，如：树 型搜索算法。在随机性方式中，采取分离标签的应答时间的方式，使标签在不同 的时隙内发送应答。一旦发生冲突，一般采取退避原则，等待下一循环周期发送 应答；在确定性方式中，阅读器将标签组不断划分为更小的子集，直至找出唯一 的一个标签与其通倒6 】【7 】。 国内外对确定性防冲突算法的研究主要集中在二进制树搜索算法，阅读器在 识别处于其区域内的标签时，平均每个标签被搜索的次数为三= l o g ，刀+ l ( n 为 总的标签数量) 【7 1 。文献【8 】提出动态二进制的搜索算法，还有学者提出基于树型 3 第一章绪论 搜索算法和二叉树型结构的q t 算法协议【9 1 ，以及后退式二进制防冲突算法1 1 0 】。 总的来讲，现有的确定性防冲突算法存在阅读器未充分利用过去的识别信息，算 法性能需要进一步提升的缺点。 对于随机性算法，国内外开展的研究相对比较多。在r f i d 系统中，a l o h a 算法的基本工作过程为：阅读器发送问询命令后，问询区内标签以随机概率p 应 答。由于应答传输的时间很短，所以各个标签可能在不同的时间段传输其信息。 该算法简单，但效率较低，最大信息吞吐率为1 8 4 【5 】。对于较少的数据包来说， 传输信道的大部分时间没有被利用：扩大数据包交换量时，标签之间的冲突立刻 明显增加，8 0 以上的传输通路没有利用。文献【1 1 】提出帧时隙a l o h a 算法，将 阅读器的问询帧分为若干个时隙，问询区内的标签随机选择一个时隙进行应答。 由于标签数未知，该算法的关键在于确定每帧的最优时隙数以及确定询问过程终 止的时间，文献【1 2 】提出基于随机帧的a l o h a 算法与此基本相似。f u k u m i z u y 【b 】 等提出在单个阅读器与多标签识别过程中，采用时域码分多路复用以及出错重传 技术来处理。由于时域信道和c d m a 序列码选择的高度随机性，能有效地避免 冲突的产生。同时，实验表明采用出错重传机制使得最终识别失误率仅 1 9 1 0 5 【i3 1 。 目前，国内外对随机类l u i d 多标签防冲突算法的研究，主要是对a i o h a 算 法进行研究，纯a l o h a 算法和时隙a l o h a 算法的最大信道利用率分别为1 8 4 和 3 6 8 【5 1 ，目前的研究大多集中在基于上述算法进行改进，文献【1 4 】提出了采用动 态分配时隙的方法解决多标签冲突问题；国内有学者【1 5 】提出的改进的时隙a l o h a 协议实质上与h e r a i dv o 甄提出的时隙a l o h a 算法原理是类似的。目前常用随机 性标签防冲突算法主要有动态时隙a l o h a 算法、帧时隙a l o h a 算法、动态帧时隙 a l o h a 算法【1 6 】等，其识别效率有所改善，但随着标签数量的增加，系统效率会急 剧降低，难于胜任未来物联网对大量标签快速识别的要求。也有学者【r 7 】【1 8 】提出 分组帧时隙a l o h a 算法，该算法虽然适合标签数量大的识别场合，且其系统吞吐 率也较高，但是无法识别处于冲突状态的标签，因此也不适用于标签数量大且对 识别时间要求高的场合。 1 4 本文的研究内容与结构 本文主要介绍了射频识别( r f i d ) 技术的基本原理和现有基于a i o h a 的多标 签识别防冲突算法，并提出一种新颖的基于分组算法的改进型标签防冲突算法一 - n g f s a ，可以识别出冲突时隙内的所有标签，适用于标签数量较多的场合， 进一步提升了系统的吞吐率。 j 4 第一章绪论 本文的组织结构如下： 第一章简要介绍了射频识别技术及国内外的应用和研究状况以及本文的主 要内容安排。 第二章介绍了l 心i d 系统结构和工作原理以及r f i d 系统中的数据传输方式。 第三章介绍了r f i d 防冲突问题及相关标准协议。 第四章分析研究了目前已有的a l o h a 防冲突算法，并对已有的分组算法进行 了优化。 第五章在现有算法的基础上，提出了一种基于分组算法的新的防冲突算法一 - n g f s a ，该算法结合了栈的思想，能够识别出冲突时隙内的标签，同时系统 的吞吐率也得到了提高，最后利用m 棚，a b 软件对其进行分析，并与现有的其 他算法进行了比较。 第六章是总结与展望，对本文的工作进行总结与展望。 第二章r f i d 系统的组成与工作原理 第二章i 心i d 系统的组成与工作原理 2 1r f i d 系统的基本组件 一个基本的i 强i d 系统一般是由阅读器( r e a d e r ) 、电子标签( t a g ) 和数据 管理系统( d a t a b a s e ) 三部分组成【5 】，如图2 1 所示。 图2 1 基本的泐系统框图 2 1 1 阅读器( r e a d e r ) 在l 玎i d 系统中，阅读器是其最基本的构件之一，其主要负责对电子标签进 行读取或写入的操作。数据管理系统的作用是存储电子标签信息。 阅读器主要完成功能包括：1 ) 在规定的技术条件下，完成阅读器与标签之 间的双向通信；2 ) 通过标准接口与计算机网络连接，并提供阅读器的识别码和 读出的标签信息，以实现多阅读器在系统网络中的运行；3 ) 实现多标签的识别， 具备防冲突功能；4 ) 可用于固定和移动标签的识别：5 ) 能够校验识别过程中的 错误信息：6 ) 对于有源系统，阅读器能够标识电池的相关信息【6 】。 综上所述，阅读器的功能主要包括是与标签进行通信的发送和接收功能、对 接收到的信息进行处理和传送信息到数据管理系统中。 2 1 2 电子标签( t a g ) 电子标签是l u i d 系统中存储可识别数据的电子装置，通常安装在被识别对 6 第二章炯d 系统的组成与工作原理 象的表面之上。系统工作时阅读器发出询问信号，电子标签收到查询信号后将 其一部分整流为直流电源供标签内部的电路工作，另一部分信号被电子标签内部 保存的数据信息调制后返回阅读器【1 j 。 目前大多数电子标签都属于只读标签，也有可多次读写的标签，只读标签内 部存储的数据在生产时就已经写入，用户不可更改，这种标签具有一个优点，那 即是消除了偶然或恶意重写标签数据造成的危险。可读写标签虽然允许多次读写 数据，但其成本相对来说较剐。丌。 2 2r f i d 系统的分类 在实际应用中，f u f i d 系统一般是根据标签的类型来分类，r f i d 系统主要有 以下几种分类： 1 根据标签的工作能量来源分类 根据标签在工作时所需能量的来源不同，可以把i 江i d 系统分成无源、有源 和半有源三种系统。 无源系统的标签不带电池，利用阅读器发射的电磁波进行耦合为自身提供能 量。这种标签具有体积小、重量轻、寿命长等优点，但它的识别距离有限制，一 般是几十厘米，而且需要有较大发射功率的阅读器；有源系统的标签在其内部带 有电池，为标签提供工作能量，能够主动发射信号，这种标签的优点是识别距离 较长，但其寿命较短且成本较高：半有源系统的标签也带有电池，电池的作用是 为标签内部的电路提供电源，标签本身并不主动发射能量。其性能介于有源和无 源之间f 5 】1 7 】。 2 根据标签的数据调制方式分类 根据标签的数据调制方式的不同，可以把l 心i d 系统分为主动式、半主动式 和被动式系统。 通常主动式系统能够依靠自身携带的能量源主动地向阅读器发送数据，而阅 读器只是被动的接受标签发送来的信息；被动式系统的原理是阅读器不断地发射 载波，标签依靠阅读器发送的载波激活，然后借助载波返回其携带的信息；半被 动式系统中的标签本身携带有能量源，但只是对标签自身的电路提供能量，并不 通过其自身的能量发送信息【5 】【刀。 3 根据标签的可读写性分类 根据标签的可读写性，可以把f u f i d 系统分为只读、一次写入多次读出和可 多次读写三种系统。 只读系统使用的标签是只读标签，标签内部的存储器为只读存储器，这种标 7 第二章r 兀d 系统的组成与工作原理 签在生产时写入信息，且不可更改；一次写入多次读出系统使用的标签为一次写 入多次读出的标签，一旦用户写入信息后则不可更改，但可以多次读取，此种标 签在实际应用中比较常见；可读写系统的标签内部的存储器为非易失可编程记忆 存储器，可以多次写入读出，但此种标签造价也相对较高1 5 】【7 1 。 4 根据系统的工作时序分类 根据l u i d 系统的工作时序，可以将l u l d 系统分为标签先讲和阅读器先讲 两种系统。 标签先讲系统也就是标签首先向阅读器发送自己的信息，待阅读器确认其合 法后再读取信息；阅读器先讲系统则是阅读器先发送信息，使处于其识别范围内 的合法标签收到其命令后，能够合理地安排识别时间，这种方式有利采用防冲突 算法，使系统的识别效率大大提高1 5 】【7 】。 5 根据标签的工作频率分类 根据标签工作的频率不同，可以将l 强i d 系统分为低频、高频、超高频和微 波系统。 低频系统工作的频率范围为3 0 3 0 0 k h z ，常见的工作频率为1 2 5k h z 、 1 3 4 2 l ( 1 电；高频系统工作的频率范围为3 3 0 m h z ，常见的工作频率为1 3 5 6 m ： 超高频系统工作的频率范围为3 0 0 一9 6 8 m h z ，典型的工作频率为8 6 9 5 m h z 、 9 1 5 m h z ：微波系统的工作频率范围为2 4 5 5 8 g h z ，典型的工作频率为 2 4 5 g h z 【5 】f 7 】。 2 3r f i d 系统的数据传输原理 r f i d 系统的基本原理是利用空间电磁感应或电磁反向散射耦合来进行通 信，实现自动识别出被标记的对象的目的。r f i d 系统的基本工作方法是在被识 别的物体上安装l 玎i d 标签，当被识别对象进入阅读器的识别范围时，标签和阅 读器之间建立起无线通信链路，标签向阅读器发送自身的信息，比如标签的编号 和标签本身存储的数据信息等，阅读器接收这些信息并对其进行解码，然后传给 数据管理系统进行后台处理，从而完成对目标的识别过程【4 1 。 2 3 1l 讧i d 系统数据传输模型 r f i d 系统的数据传输模型主要有电磁感应和电磁反向散射耦合两种形式， 图2 2 和图2 3 为其原理示意图。 所谓电磁感应其实就是变压器模型，通过空间高频交变磁场实现耦合，依据 的是电磁感应定律，如图2 2 所示。电磁感应工作方式一般适用于中、低频的识 第二章r 兀d 系统的组成与工作原理 别距离比较近的射频系统。这种工作方式典型的工作频率主要有1 2 5 l 此、2 2 5 k h z 以及1 3 5 6 m h z 。这种方式的识别范围一般小于l m ，实际应用比较广泛的是 o 。1 5 c m l 6 1 。 图2 - 2 电磁感应 图2 3 电磁反向散射耦合 电磁反向散射耦合的工作方式是首先通过阅读器天线发射出电磁波，碰到目 标后反射，反射回来的信号携带有目标信息，其主要的依据是电磁波的空间传播 规律，如图2 3 所示。这种电磁波传播方式一般适用于高频、超高频和微波频段 工作的射频识别系统。这种方式典型的工作频率为4 3 3 m h z 、9 1 5 m h z 以及 2 4 5 g h z 。此种方式的识别范围一般大于l m ，实际工作常用的典型距离为 3 10 m 【6 1 。 2 3 2 数据的编码方式 在r f d 系统的数据传输中，常用的数据调制解调方式主要有幅移键控 ( a s k ) 、频移键控( f s k ) 和相移键控( p s k ) 三种方式。为了简化电子标签 设计的复杂性和成本，大多数r f i d 系统采用的是a s k 调制方式【6 1 。 数据编码又称为基带数据编码，一方面便于数据传输，另一方面可以对传输 的数据进行加密。常用的数据编码方式【6 】有反向不归零( n r z ) 编码、曼侧斯特 ( m a n c h e 妣r ) 编码、差动双向( d b p ) 编码、米勒( m i l l e r ) 编码、单极性归零 ( u n i p o l 盯l 屹) 编码、差动编码、脉冲宽度调制( p w m ) 编码、脉冲位置( p p m ) 编码等方式，如图2 - 4 所示j 。 1 ) n r z 编码：高电平代表l ，低电平代表0 ； 2 ) m 狮c h e s t e r 编码：在半个比特周期处的边沿负跳变代表l ，半个比特 周期处的边沿正跳变代表0 。m a n c h e s t e r 编码采用负载波的负载调制 或者反向散射调制时通常用于由标签向阅读器发送数据，因为这有利于 发现所传送数据的错误( 采用比特位检测) ： 3 ) 单极性归零码：在半个比特周期处的边沿负跳变代表l ，而整个比特 9 第二章i 羽d 系统的组成与工作原理 周期全为低时代表0 ： 4 ) 差动双向编码：在半个比特周期处的边沿任意跳变代表0 ，没有跳变 的代表l ，并且在每个比特周期的开始出，电平都要反向： 5 ) 米勒编码：在半个比特周期处的边沿任意跳变代表l ，而在下一个周 期内不变的代表0 ，连续的0 在每个比特周期开始处发生跳变； 6 ) 差动编码：在差动编码中，传送l 时电平发生跳变，而传送0 时 电平保持不变。 n l 屹编码 m 础s 暇编码 u n i p o l a rl 江编码 d b p 编码 m i l l 盯编码 差动编码 图2 - 4 数据编码方式( 数据为l o l l 0 0 l o ) 2 3 3 数据的完整性 数据的完整性是描述在数据传送过程中数据的内在关联一致性。在l 心i d 系 统中，由于是非接触式传播，数据在传送过程中很容易受到干扰，导致传送的数 据发生改变，通常采用的解决方法是对接收到的数据进行检错和纠错【6 】。 在实际应用中，最常用的检验方法有奇偶检验法、纵向冗余检验法、循环冗 余检验法等，通常一旦系统发现接收的数据有误，立即启动纠错措施或者放弃接 收到的错误数据，并要求重新发送数据。 ( 1 ) 奇偶检验法：在数据传输时，把校验位加进要传送的数据中，在接收 端采用与发送端相同的检验方法对收到的数据进行检验，并同发送端的数据校 验，若检验出校验位不符，则说明发生错误，可以采用奇校验或偶校验。这种方 法由于简单而得到广泛的应用，但其缺点就是识错能力低，若采用奇校验，发生 错误的位数为偶数时则系统无法检验出错误【5 儿6 1 。 1 0 第二章r f i d 系统的组成与工作原理 ( 2 ) 纵向冗余检验法：把要传输数据的所有字节经过x o r 操作产生一个 x o r 检验和的值，将此值附在数据的后面发送，在接收端对接收到的数据和校 验位进行校验，其结果应为零，若为其他结果则表明传输过程中发生错误。此法 比较简单，可以快速算出x o r 校验和，但是对于出现多个错误时，则不适用， 故其比较适用于数据较短的传输。在r f i d 系统中，由于标签的容量一般不大， 故此检验方法还是比较合适的1 2 j i7 1 。 ( 3 ) 循环冗余检验( c r c ) 法：对要传送的数据附加校验位，校验位由即 将传送的数据生成，接收端在收到数据后重新按先前的校验位生成方法生成校验 位，并与接收到的校验位相比较，判断是否发生错误。在r f i d 系统中，比较常 用的校验位是8 位或者1 2 位的c r c 。这种检验方法识别传输错误的性能很好， 但是其不能改正错误【l 】。 2 4r f i d 系统的干扰与抗干扰 在l 讧i d 系统中，标签和阅读器之间的数据传输过程中存在着干扰的问题。 干扰造成的直接后果就是标签不能被正确的识别【5 j 。 标签在收到阅读器发送的信息后可能会发生的错误有：1 ) 错误地响应阅读 器；2 ) 工作状态发生混乱；3 ) 错误地进入休眠状态【l 】o 阅读器在接收标签发送的数据时可能会发生的错误有：1 ) 接收到非法标签 发送的信息；2 ) 对标签产生误判【l j 。 通常采用的抗干扰措施有：1 ) 标签与阅读器事先约定检验数据完整性的方 法，对接收到的数据进行检验；2 ) 采用抗干扰能力强的数据编码方式，提高系 统抗干扰的能力；3 ) 通过数据完整性的检验，纠正因干扰而出现的错误数据：4 ) 多次发送数据，通过对比保留判断为正确的数据【5 】。 2 5 本章小结 本章首先介绍了i 强i d 系统的组成部分和工作原理，并对阅读器、标签及系 统的分类进行了详细的介绍，同时讲述了l 讧i d 系统中的数据传输原理，并介绍 了l 玎i d 系统在实际应用中存在干扰的问题。 第三章i t 兀d 系统标签防冲突机制及标准介绍 第三章l 强i d 系统标签防冲突机制及标准介绍 3 1 标签冲突介绍 在r f i d 系统的应用过程中，经常会有多个阅读器和多个标签的应用场合， 这会产生标签之间或阅读器之间的相互干扰，从而导致通信过程的间断，这种现 象称为冲突( c o l l i s i o n ) 。总的来说，冲突分为标签冲突和阅读器冲突。 阅读器1 o 阅读器2 的干扰范围 _ 电子标签 、。一一一， 图3 1 阅读器的冲突问题 2 的识别范围 图3 1 为阅读器冲突，一个标签位于两个以上阅读器的询问范围内，多个阅 读器同时尝试与标签进行通信时，会对标签产生干扰，导致无法成功识别【。 阅读器的干扰范围 o 的识别范围 阅读器 电子标签 图3 - 2 标签冲突问题 图3 2 为标签冲突，多个标签位于一个阅读器的识别范围内，当它们在同一 1 2 第三章r f i d 系统标签防冲突机制及标准介绍 时刻与阅读器进行通信时，阅读器将无法分辨与哪个标签进行通信，产生标签之 间的冲突【1 1 。 3 2 标签防冲突算法 当多个电子标签工作在同一频率并处在同一个阅读器的识别范围内时，如果 此时没有采用防冲突算法进行控制，标签就会同时对阅读器发送的指令产生响 应，随后标签同时向阅读器发送信息，就会产生信道争用问题，阅读器就不能正 确的识别目标，从而使阅读器发生误判，即发生了标签冲突。 目前在多个阅读器和多个标签的系统中，主要存在着两种形式的冲突：1 ) 一个阅读器同时收到多个标签发送的响应信息；2 ) 一个标签同时收到多个不同 阅读器发送的指令。这两种情况在实际应用中都应该尽量避免发生，本文研究的 是第一种情况。在l u i d 系统中，系统工作时存在着两种基本的通信方式：1 ) 由阅读器到标签的通信；2 ) 由标签到阅读器的通信【4 】。 对于多个标签同时向阅读器发送信息而产生的冲突，如果阅读器不能正确地 处理，便会从标签那里获得错误的信息，这在实际应用中是绝对不允许的，这种 标签冲突需要相关的防冲突算法来解决，这就是本文研究的主要问题。 在射频识别系统中，标签冲突问题的解决方法主要有下面几种：1 ) 空分多 路法( s p a c ed i v i s i o nm u i t i p l ea c c e s s ，s d m a ) ；2 ) 频分多路法( f r c q u e n c yd i v i s i o n m u l t i p l e a c c e s s ，f d m a ) ；3 ) 时分多路法( t i m ed i v i s i o nm u l t i p l e a c c e s s ，t d m a ) ： 4 ) 码分多路法( c o d ed i v i s i o nm u l t i p l e a c c e s s ，c d m a ) 【5 1 。下面对上述常用的 几种多路存取方式进行简单的介绍。 ( 1 ) 空分多路法( s d m a ) s d m a 法的实现方法有两种：一是把阅读器的识别范围按空间区域进行划 分，然后把多个阅读器放入划好的阵列中，当标签进入不同的阅读器的识别范围 内时，就可以在空间上将标签区分；另一种是把阅读器的天线设置成为一个相控 阵天线，使天线的方向对准某一标签，这样就可以根据标签在阅读器作用范围内 的角度来区分。该方法的缺点是阅读器的天线系统较复杂，实现费用较高。因此 该技术一般应用在一些特殊的行业上，例如大型马拉松比赛1 5 】。 ( 2 ) 频分多路法( f d m a ) f d m a 法是指提供给l u i d 使用的传输通道是由若干个不同载波频率的通道 组成。通常情况下，阅读器到标签( 下行链路) 的频率是固定的，其提供标签工 作所需能量和传输指令数据的信号。对于标签到阅读器( 上行链路) 可以采用不 同于下行链路的、独立的副载波来进行数据的传送。此方法的缺点是阅读器的成 j 1 3 第三章r 兀d 系统标签防冲突机制及标准介绍 本较高，这主要是由于不同频率的上行链路要求阅读器有多个单独的接收器。这 种方法被限制应用在极少的特殊的应用上【6 】。 ( 3 ) 码分多路法( c d m a ) c d m a 是基于扩频通信技术发展起来的新的无线通信技术，其包含扩频与码 分多址两个概念。扩频是对信息带宽的扩展，把本身具有一定信号带宽并且需要 传送的数据，用一个远远大于其带宽的高速伪随机码进行调制，使被传送信号的 带宽扩展，然后经过载波调制后发送。接收端使用的伪随机码与发送端相同，对 接收到的带宽信号进行处理，将收到的宽带信号转换成原来的窄带信号( 数据信 息) 即解扩，从而实现通信过程。其缺点是频带利用率低、信道容量较小，且其 技术较为复杂，因此也很难在盯i d 系统中广泛推广，目前主要应用在移动通信 系统方面【刀。 ( 4 ) 时分多路法( t d m a ) t d m a 法是指把整个可供使用的通道容量按时间分配给多个用户使用的技 术。t d m a 技术最早应用在数字移动系统中并得到推广，也是r f i d 系统的防冲 突技术中得到应用最广泛的一种。 t d m a 法的具体实现【5 】包括标签驱动法( 标签控制) 和阅读器驱动法( 阅读 器控制) ，如图3 3 所示。 标签控制法的工作是非同步的，因为这里不存在对阅读器的数据传输进行控 制，比如a i o h a 算法。根据标签在成功传送完数据之后是否能按照阅读器的信号 不再发送自身的信息，可以区分为开关断开法和非开关法。 阅读器控制法是指所有的标签同时由阅读器进行控制，通过设定的算法，在 阅读器的识别范围内首先选中待识别标签中的一个，然后完成该标签和阅读器之 间的通信。由于同一时间内能建立一个通信关系，所以在完成通信后应解除与此 标签的通信关系，然后继续选择其他标签进行通信。因此，阅读器控制法也叫定 时双工传输法。 阅读器控制法可以再分为轮询法和二进制搜索法【5 1 。轮询法需要用到所有可 能被识别的标签的序列号清单，阅读器对标签进行依次询问，一直到某个有相同 序列号的标签为止。不过此法过于依赖标签的数量，标签比较多时效率较低，一 般适用于标签数量较少的场合。 t d m a 法由于其应用简单，容易实现对较大数量标签的识别，所以目前的 l u i d 系统的标签防冲突算法都是采用t d m a 法来实现。目前常用的标签防冲突 算法主要有二进制树形算法和a l o h a 算法两种。 1 4 第三章r f i d 系统标签防冲突机制及标准介绍 图3 - 3t i ) m a 防冲突技术的划分 3 2 1 二进制树形算法 在二进制树形算法中，二进制搜索算法是目前使用最广泛和最灵活的一种方 法。为了从多个标签中选择一个，阅读器发出一个请求命令有意识地将传输标签 序列号时的数据冲突引导到阅读器上，通过阅读器判断是否有冲突发生。如果有 冲突，则缩小范围进行进一步的搜索【9 】。 图3 - 4 二进制树形算法原理 二进制搜索算法的基本原理是：首先将处于冲突状态的标签分成左0 右 l 的两个子集，先查询左子集0 内的标签，若没有发生冲突，则成功识别 出标签；若存在标签冲突，则将左子集o 再次分为左0 0 右0 l 的两个 第三章l 嗣d 系统标签防冲突机制及标准介绍 子集，按照此原理依次类推，直到识别出左子集0 内的所有标签为止；然后 再按上述步骤继续查询右子集l ，这样可以识别出所有的标签【9 】。二进制树形 算法的原理如图3 - 4 所示。 二进制树形防冲突算法的搜索效率较高，但当标签数量较多时系统效率依然 较低。有学者【1 9 】在此基础上进行了改进，提出了后退式二进制树形等改进型的算 法，该算法的查询命令包含有一个额外指令，标签的i d 在不大于这个额外指令 值的情况下才响应，阅读器对每次发送的指令值进行存储。在识别开始时，阅读 器发送的指令值全部为l ，此时所有标签均响应，若有冲突发生，则系统由高位 到低位检测出最高冲突位，将该位置0 ，同时保持该位置之前的高位不变，其 后的低位全置o ，此时该数值即为阅读器发送的下一条查询命令的指令值，重 复上述操作，直到成功地识别出一个标签。完成一个标签的识别后，系统采取后 退策略，当后退到指令值全为l 时，也即代表着完成了所有标签的识别。 后退式二进制算法是二进制搜索算法的改进算法，其识别n 个标签的查询总 次数为2 n + 1 次；且该算法对阅读器的要求比较高，要求阅读器必须准确地识别 到标签的冲突位，这在实际应用中不易实现。 3 2 2a l o h a 算法 a l o h a 算法是一种随机接入算法，一般用于只读阅读器的f u f i d 系统中，这 种算法多采取“标签先发言的方式，标签一旦进入阅读器的识别范围就自动向 阅读器发送其自身携带的信息，随即标签和阅读器开始通信。在标签发送数据的 过程中，若有其他标签也在发送数据，那么发生信号重叠从而导致完全冲突或部 分冲突。阅读器对接收到的信号进行检测来判断有无冲突发生。一旦发生冲突， 阅读器就发送命令让标签停止发送，随机等待一段时后再重新发送以减少冲突 【2 0 1 。a l o h a 算法的数据传输和冲突原理如图3 5 所示。 数据包。 口口口 数据包2 口口口口 公共信道口口圈口口 传输成功 部分冲突 完全冲突 图3 5a i o h a 簋法的数据传输原理 1 6 第三章i t 兀d 系统标签防冲突机制及标准介绍 在r f i d 系统中，采用的a l o h a 算法主要有纯a l o h a 算法、时隙a l o h a 算法 和动态时隙的a l o h a 算法。采用纯a l o h a 算法的系统的最大吞吐率只有1 8 4 ， 这对于标签数量较小的情况，系统的公共信道利用率比较低：而当标签数量较多 时，则发生冲突的概率会大幅增加，会浪费系统超过8 0 的容量【2 1 1 。对上述a l o h a 算法的缺点，人们也做出了一定的研究并对其进行了改善以提高采用a l o h a 算法 的f u p i d 系统的效率，例如时隙a i o h a 算法和动态时隙a l