（通信与信息系统专业论文）rfid编码分组防碰撞算法.pdf

独创性声明 i ii ii if i lli f lli ij iilll y 18 9 4 5 6 6 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：抹彩铭 2 口j 年乡月，矽j 日 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期下j j ( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密口。 学位论文作者签名：球；乞旃 如f f 年占月f 争日 指导教师签名： ) 史 2 。r 年衫月，9r 江苏人学硕士学位论文 摘要 射频识别技术( 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 系统的工作原理和防碰撞算法原理的基础上， 研究了e p c 编码方案和同本u i d 标准编码方案，提出了标签编码方案的唯一性、 简单性、可扩展性、保密性与安全性、永久性原则；给出了快递行业快件编码方 案和零售业商品编码方案，为编码分组算法提供理论前提。提出了编码分组的二 进制防碰撞算法，针对零售业编码方案阐述了编码分段和标签分组的具体方案， 阐述了算法的原理和识别流程，设计了算法命令，进行了算法演示，根据零售业 物品编码构成，构建了一个由数据长度为1 6 b i t s 的1 0 0 个标签组成的标签组，模 拟实际使用环境对编码分组的防碰撞算法进行了验证，验证的过程分为识别每一 个标签和统计编码中某段数据为指定值的标签数量，并对识别和统计所需的阅读 器查询次数和总信息量进行了计算。验证表明，编码分组二进制算法的阅读器查 询次数、总信息量要少于二进制算法，提高了系统工作效率。 关键词：射频识别技术，编码，分组，防碰撞算法 a b s t r a c t r 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 o n ，r f i d ) h a sa w i d er a n g eo fa p p l i c a t i o n si n e v e r yi n d u s t r y h o w e v e r ，s o m ep r o b l e m ss t i l ln e e d t ob ea d d r e s s e da n dt a gc o l l i s i o ni s o n eo ft h eb o t t l e n e c k so fr e s t r i c t i n gt h er f i dt e c h n o l o g yi np r a c t i c a l a tp r e s e n t ，b i n a r ya n di t sd e r i v a t i v ea l g o r i t h mi sal a b e lc o d ew h i c hh a sn o t h i n g t od ow i t ht h ei t e m sa n dl a b e li n f o r m a t i o ni t s e l f h o w e v e r ，t h eo n l y i d e n t i f i c a t i o n c o d ep r o d u c e db yt a gc o d i n gs t a n d a r ds y s t e ma r ef o l l o w i n gt h ec e r t a i nl a wa n de a c h p a r a g r a p ho fc o d eh a ss p e c i f i cd a t am e a n i n g t h ew a yt oi m p r o v et h eb i n a r y a l g o r i t h mi s t ou s et h ei n f o r m a t i o ni nt h es t a n d a r dc o d e sw h i c hc a nr e a l i z e t h e p o s s i b l ed i r e c t i o n s o fh i g hr e c o g n i t i o nr a t ea n dl o wc o m p l e x i t yb i n a r yp r e v e n t c o l l i s i o na l g o r i t h m t h e r e f o r e ，i nt h eb a s i co fa n a l y z i n ga n ds t u d y i n gt h er f i ds y s t e mp r i n c i p l ea n d p r e v e n tc o l l i s i o np r i n c i p l ea l g o r i t h m ，t h i sa r t i c l ed or e a c h o nt h ee p cc o d i n gs c h e m e a n dj a p a ns t a n d a r dc o d i n gs c h e m eu i da n dp r o p o s eu n i q u e n e s so fc o d i n gs c h e m e ， s i m p l i c i t y ，e x p a n s i b i l i t y ，p r i v a c ya n ds e c u r i t y ，p e r m a n e n tp r i n c i p l eo f t h el a b e l t h e e x p r e s si n d u s t r ye x p r e s sc o d i n gs c h e m ea n dr e t a i l c o d i n gs c h e m ei sg i v e ni n t h i s p a p e rw h i c hp r o v i d et h e o r e t i c a lp r e m i s ea l g o r i t h mf o r c o d eg r o u p t h eb i n a r yc o d i n g g r o u p i n gp r e v e n tc o l l i s i o na l g o r i t h m i sp r o p o s e di nt h i sp a p e ra n dt h ec o n c r e t ep l a no f t h ec o d es e g m e n ta n dt a g sg r o u p e di se x p o u n d e dw h i c ha i ma tr e t a i lc o d i n gs c h e m e t h ep r i n c i p l eo fa l g o r i t h ma n dr e c o g n i t i o np r o c e s si s e l a b o r a t e da n da l g o r i t h m c o m m a n di sd e s i g n e da n dd e m o n s t r a t e d a c c o r d i n gt ot h ef o r mo f r e t a i li t e m sc o d i n g ， al a b e lg r o u pw h i c hi sc o m p o s e do fal e n g t ho fd a t af o r 16b i t so f10 0t a g si s c o n s t r u c t e di nt h i sp a p e r c o d i n gg r o u p i n gp r e v e n tc o l l i s i o na l g o r i t h mw a s v e r i f i e di n s i m u l a t et h ea c t u a le n v i r o n m e n t t h ev a l i d a t i o np r o c e s si sd i v i d e di n t oi d e n t i f i c a t i o n o fe a c hl a b e la n ds t a t i s t i c sf o re n c o d e dd a t ai nac e r t a i nn u m b e ro ft a g ss p e c i f i e d v a l u e s t h et o t a la m o u n to fi n f o r m a t i o na n dt h en u m b e ro f r e a d e r sw h i c hn e e d e dt ob e i d e n t i f i e da n dq u e r i e da r ec a l c u l a t e d i ti sp r o v e dt h a tr e a d e rq u e r i e sa n dt h et o t a l n u m b e ro fi n f o r m a t i o no ft h ec o d i n gg r o u pb i n a r ya l g o r i t h mi sl e s st h a nt h eb i n a r y a l g o r i t h mw h i c hi m p r o v e dt h es y s t e mw o r ke f f i c i e n c y k e yw o r d s ：r f i d ，c o d i n g ，g r o u p i n g ，a n t i c o l l i s i o na l g o r i t h m 1 1 1 江苏大学硕士学位论文 目录 第一章绪论一l 1 1r f i d 系统中的碰撞问题1 1 2r f i d 的防碰撞算法2 1 3 论文的主要研究内容3 第二章r f i d 系统5 2 1r f i d 系统的组成5 2 2r f i d 系统基本工作流程6 2 3 射频识别系统的物理基础7 2 3 1 基带编码8 2 3 2 数据传输的完整性8 2 4r f i d 系统的碰撞与多址技术9 2 4 1r f i d 系统的碰撞分类9 2 4 2 多址技术lo 2 4 3 时分多路法分析及改进方向1 2 2 5 本章小结1 3 第三章r f i d 编码标准研究1 4 3 1 现行电子标签编码标准结构分析1 4 3 2 1e p c 编码体系15 3 2 2e p c 编码体系与通用结构1 6 3 2 3 日本u i d 标准编码体系18 3 3 标签编码原则的提出1 9 3 4 快递行业标签编码方案设计19 3 5 零售业商品编码方案设计2 2 3 6 本章小结2 4 第四章编码分组二进制算法2 5 4 1 防碰撞算法设计原则2 5 4 2 二进制及其衍生算法研究2 5 4 2 1 基本二进制数防碰撞算法2 5 4 江苏大学硕士学位论文 4 2 2 动态二进制防碰撞算法：2 7 4 2 3 退避式二进制树防碰撞算法2 8 4 3 各种r f i d 算法优缺点分析3 0 4 3 1 二进制及其衍生算法的优缺点3 0 4 3 2 其他分组算法的优缺点一3 0 4 4 编码分组二进制算法3 l 4 4 1 编码分段与标签分层分组3 1 4 4 2 算法思路和识别流程3 3 4 4 3 算法命令设计3 4 4 4 4 算法演示3 4 4 4 5 算法性能分析3 5 4 5 本章小结3 6 第五章算法验证与性能分析3 7 5 1 算法验证j 3 7 5 1 1 标签组的编码标准3 7 5 1 2 厂商与产品的对应关系4 0 5 1 3 储存区域定义4 0 5 1 4 命令设计4 l 5 1 5 完整的标签组，4 l 5 1 6 算法流程一4 2 5 2 性能分析4 5 5 2 1 阅读器寻呼次数4 5 5 2 2 传输信息量。4 6 5 2 3 原因分析4 6 5 3 本章小结4 7 第六章总结与展望4 8 致谢4 9 参考文献5 0 攻读硕士学位期间发表的论文5 3 江苏人学硕士学位论文 第一章绪论 射频识别技剁1 。2 1 ( 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 ) 起源于上世纪9 0 年代，是一种通过空间耦合利用射频信号进行无接触信息传递进行多目标识别的 无线通信技术。在行李包裹追踪、旅客机票、自动高速公路收费、铁路车皮识别、 资产跟踪、公共交通、物流管理、动物识别跟踪、门禁安全等领域有着广泛的 应用，被认为是未来信息社会建设的一项基础技术。为了实现管理信息化、提高 物流和供应链管理水平、降低成本、参与国际经济和增强企业竞争力，r f i d 是 一项必不可少的技术手段和工具1 3 。5 l 。与任何一项科学技术一样，在r f i d 技术的 发展过程中，仍然存在和出现着很多需要解决的问题，r f i d 数据通信中的防碰 撞就是其中的重要问题之一。 1 1r f i d 系统中的碰撞问题 r f i d 系统的数据通信分为阅读器到电子标签问的通信和电子标签到阅读器 问的通信。在实际应用过程中会出现同时多个阅读器和多个电子标签出于同一场 合的情况，此时系统的数据交换就可能发生碰撞，冲突形式如下：不同阅读器同 时向一电子标签发送命令，这种碰撞被称为阅读器碰撞。另一种是多个电子标签 同时向同一阅读器发送数据，这种碰撞被称为电子标签碰撞。阅读器碰撞问题并 不多见，本文着重讨论电子标签碰撞，电子标签碰撞又被称为标签碰撞。 标签的碰撞导致阅读器无法正确识别标签，读取标签信息，导致系统识别效 率的下降，使系统处理重复识别、处理失效标签等流程复杂化。当r f i d 应用于 物流、仓储管理、工业自动化等需多目标识别的场合时因标签的碰撞造成的后果 也越严重。 物品的信息存储有两种方式，一种是存储在数据库罩，标签上只存储无意义 的唯一标示码，在需要的时候经授权后到数据库中查询与标签对应的物品信息， 一种是直接存储在标签里。目前，常采取第一种方式。 第一种信息存储方式能够有效保护物品的信息安全，个人隐私和商业机密， 这种方式需要阅读器与数据库服务器相连接，无法直接得知物品的信息。 江苏大学硕士学位论文 第二种信息存储方式无法有效保护物品的信息安全，个人信息和商业机密极 容易被窃取，这种存储方式带来的好处是不需要通过查询数据库就能直接使用或 显示信息。 1 2r f i d 的防碰撞算法 对于标签碰撞问题，国内外的算法主要分为基于时隙a l o h a 的随机型算法 和基于二进制树的确定型算法。 二进制搜索算法的主要思路是让标签之间能够严格同步并且使用曼彻斯特 编码的通信方式让读写器能够检测到碰撞并确定碰撞的位数，根据位数设置相应 的命令，让一部分标签停止响应，接着继续响应，如此反复指导辨别出唯一的标 签，这是二进制算法中的经典算法之一。动态二进制搜索算法1 6 l 对二进制搜索算 法进行了改进，对没有发生冲突的旧位只传送一次。这样就减少了重传的数据， 提高了效率，大大减少了传输时延。基于返回式二进制树形搜索的防碰撞算法1 7 】 是在二进制搜索算法的基础上进行改进，当阅读器检测不到碰撞时，可用返回式 从上一层r e q u e s t 命令获得下一次的r e q u e s t 命令，分析结果表明该算法能 够有效迅速地识别标签。文献【8 】对二进制搜索算法防碰撞过程进行了具体的研 究。还有一些算法对二进制搜索算法进行了其他方向的改进f 9 1 4 1 。 q t 算法f 1 5 - 1 7 1 是一种无记忆算法，除了记忆自己的i d 信息外标签无需记忆 其它任何信息，该算法的构成包括多周期的寻呼和响应，如果有两个或者多个以 上标签的前缀信息相同，在每个循环周期里，在前缀的信息基础上加上0 或1 ， 阅读器继续寻呼。f z h o u 等人【1 8 j 通过减少发生碰撞的标签的响应次数，减少标 签的能耗对寻呼树算法进行了改进。b h a n d a r in 等人依据e p c 编码对寻呼树进 行拆分处理，进一步改进q t 算法，提出了智能的寻呼树算法【l9 1 ，该算法比q t 算法的优势在于简化了标签的电路、降低标签传送的比特位数，减少标签碰撞次 数。单承赣等人在文献【2 0 l 中提出了利用二时隙方法，对寻呼树算法加以改进， 大大减少阅读器的寻呼次数，降低了标签识别传输的比特数。 a l o h a 算法【2 1 1 是一种随机接入方法，阅读器的识别区域内的标签获得足够能 量后就立刻发送自身的i d 号给阅读器，如果发生数据冲突就重新选择一个时隙 发送，直到数据传输成功。时隙a l o h a 2 2 1 ( f r a m e ds l o t t e da l o h a ，f s a ) 算法是基 于通信领域的a l o h a 协议提出的。在f s a 中，”帧”( f r a m e ) 足由读写器定义的 2 江苏大学硕士学位论文 段时问长度，其中包含若干时隙。标签在每个帧内随机选择一个时隙发送数据。 所有标签戍答同步，即只能在时隙( s l o t ) 丌始点向读写器发送信息，每个标签发 送的时隙是随机选择的。时隙可以分为三类：空闲时隙、应答时隙和碰撞时隙。 在空闲时隙中没有识别任f j 标签，应答时隙中可以i f 确识别一个标签。当一个时 隙中有多个标签同时发送戍答时就会产生碰撞，形成碰撞时隙。碰捕的标签退出 当前循环，等待参与新的帧循j 不。文献1 2 3 l 是对时隙a l o h a 算法的具体应用。动态 时隙a l o h a 算法1 2 4 l 改进了a l o h a 及时隙a l o h a 算法中时隙不可变的缺点，提高了 增加了算法的吞吐量。根据帧长度越长，发生碰撞概率越小的原理，l e i a nl i u 提出了帧时隙a l o h a 算法1 2 5 】，这种算法提高了吞吐量，但增加了系统的时延。 在此基础上产生了调整帧长度的方法，该方法对阅读器范围内的标签数目进行估 算并以此设定下一帧的长度【2 6 j 。j a e r y o n gc h a 等人改进了帧时隙a l o h a 算法， 提出了动态帧时隙a l o h a 算法1 2 ”。关于分组的理论有：根据电子标签在空间 分布上的距离远近进行分纠2 8 l ；根据电子标签比特为之和的奇偶性对标签进行 分组【2 9 1 ；依据电子标签进入阅读器范围内的时问段进行分组【3 0 】；f r a n k y e o n g s u n gl i n 在文献1 3 】j 中提出先根据a l o h a 算法对阅读器范围内的标签数 目进行估算，根据标签的数量和比特码长度合理地对标签进行分组。然后根据标 签识别的具体情况采取a l o h a 算法或者二进制算法来解决碰撞问题，从而识 别标签。 1 3 论文的主要研究内容 目前，二进制及其衍生算法利用的是与标签代表的物品本身信息无关的标签 编码。但在标签编码标准体系下产生的唯一标识码，都遵循着一定的规律，编码 的每段数据都有具体的代表意义，怎样利用这些编码标准中的数据规律，提高系 统效率是本文研究的主要内容。 本文分析了两种标签编码方案，提出了标签编码原则，给出了快递行业快件 标签编码的方案和零售业物品编码的建议；在物品信息储存在标签内的基础上， 提出了基于标签编码标准对标签进行分组的理论并进行了实例验证，通过实例证 明了从系统整体角度出发主动处理多标签碰撞问题比传统的被动处理碰撞能够 更加有效的减少阅读器的查询次数和系统的通信量，提高了系统的识别效率，降 低系统复杂度。 江苏大学硕士学位论文 全文分为六章，具体结构安排如下： 第一章：绪论。主要概述了本课题的研究背景与意义，以及r f i d 防碰撞算 法的国内外发展现状和课题的主要研究内容。 第二章：r f i d 系统。详细分析了r f i d 系统，包括r e i d 系统的结构和构成， r f i d 系统的工作原理，以及各类防碰撞算法。 第三章：r f i d 编码标准研究。在分析e p c 编码方案和同本u i d 标准编码 方案的基础上，提出了标签编码方案的唯一性、简单性、可扩展性、保密性与安 全性、永久性原则；针对标签编码各数据段定义要符合行业内实际要求的特点， 对快递行业的公司数量，公司服务点的分布情况、服务点的业务量进行了统计， 在研究中国邮编体系构成的基础上，提出了以公司代码、收发货人所在区域的邮 编、序列号为构成的快递行业快件编码方案，并对各数据段的内容、长度根据实 际使用及需求情况进行了定义；从零售业行业的商品库存管理、店内商品管理的 需求角度出发，给出了零售业商品编码基本信息的方案，为编码分组算法提供了 标签编码方案。 第四章：本章研究了经典二进制防碰撞算法、动态二进制防碰撞算法、退避 式二进制防碰撞算法，通过对各种r f i d 算法优缺点的分析发现这些算法都没有 利用标签编码数据本身的信息并在此基础上提出了给定编码标准环境下的基于 标签编码的结构对标签进行分层分组进行碰撞处理的算法，给出了对标签数据进 行分段和分组的依据和方法，阐述了算法的思路和流程，对算法进行了命令设计 和算法演示。 第五章：依据零售业标签编码方案构建了一个由数据长度为1 6 b i t s 的1 0 0 个标签组成的标签组，模拟实际应用环境对编码分组二进制算法进行了验证和性 能分析，验证的过程分为识别每一个标签和统计编码中某段数据为指定值的标签 数量，并对识别和统计所需的阅读器查询次数和总信息量进行了计算。 第六章：总结与展望。对全文进行了总结，指出了本文的创新点，并对进 一步的研究工作提出展望。 4 江苏大学硕+ 学位论文 第二章r f i d 系统 2 1r f i d 系统的组成 最基本的r f i d 系统由标签、阅读器、计算机通信网络三部分组成。图2 一l 为r f i d 系统的基本组成1 3 2 l 。 p 1 卜 m- - t 发射模块卜 1卜 无 标 c c 无 线 签 线 几 机 厂 u - - i 接收模块卜 图2 1r f i d 系统基本组成图 标签：又被称为电子标签或智能标签，它由芯片和天线两部分组成，可 供识别的目标信息存储在芯片中。有些r f i d 标签支持读写功能，能够随时 更新目标物体的信息。根据工作频率的不同【3 3 1 ，标签可分为低频标签( 工 作频率范围为3 0 k h z 3 0 0 k h z 。典型工作频率有：1 2 5 k h z ，l3 3 k h z ) ，中 高频标签( 工作频率一般为3 m h z 3 0 m h z 。典型工作频率为：1 3 5 6 m h z ) ， 超高频标签( 微波电子标签，典型工作频率为：4 3 3 9 2 m h z ，8 6 2 ( 9 0 2 ) 9 2 8 m h z ，2 4 5 g h z ，5 8 g h z ) ；根据供电方式的不同，标签可分为无源标 签、半有源标签、有源标签，无源标签内部不带电池，需靠外界提供能量 才能正常工作，半有源标签在需要的时候由内部电池供电，有源标签则通 过标签自带的内部电池进行供电。此外，标签可封装成卡片式标签、纸状 标签、线形标签，圆形标签等，以适用于各种不同需求的场合。 阅读器：典型的阅读器包含有高频模块( 发送器和接收器) 、控制单元以 及阅读器天线。此外，许多阅读器还有附加的接v i ( r s 2 3 2 、r s 4 8 5 、以太网 接口等) ，以便将所获得的数据传向应用系统或从应用系统接收命令。 电子标签与阅读器构成的射频识别系统归根到底是为应用服务的，应用 的需求可能是多种多样，各不相同的。阅读器与应用系统之间的接口a p i 通常用一组可由应用系统开发工具( 如v c + + ，v b ，p b 等) 调用的标准接口 函数来表示。标准接口函数的功能大致包括以下四个方面。 ( 1 ) 应用系统根据需要可能向阅读器发出阅读器配置命令； 江苏人学硕十学位论文 ( 2 ) 阅读器向应用系统返回的所有可能的阅读器当前的配置状态； ( 3 ) 应用系统向阅读器可能发送的各种命令； ( 4 ) 阅读器向应用系统可能返回的所有可能命令的执行结果。 完善的射频识别技术标准也包括阅读器与应用程序之间的标准接口规 定。例如：a n s in c i t s 2 5 6 2 0 0 l ，i s 0 18 0 0 0 系列射频识别国际标准等均 对阅读器与应用程序接口a p i 做出了明确规定。 计算机通信网络：对数据进行管理，完成通信传输功能，在必要的时 候读写器可以通过标准接口与计算机通信网络连接，以便实现通信和数据 传输功能。 2 2r fid 系统基本工作流程 阅读器通过发射天线向外发射发射特定频率的射频信号，电子标签进入到发 射天线的工作范围时获得能量被激活，电子标签通过天线向外发送自身的编码等 信息代码，系统通过接收天线接收到电子标签发出的载波信号后就通过天线的调 节器传送给阅读器；阅读器对接收到的信号进行解码后就再送往后台的电脑主控 制器中去，电脑控制器会据逻辑运算判断此标签的合法性，并针对不同的设定做 出相应的处理和控制，同时发出指令信号控制执行机构的动作。如图2 2 所示。 6 江苏大学硕士学位论文 阅读器 i 与阅读器 l 进行通信 结束 图2 2 射频识别系统工作流程图 2 3 射频识别系统的物理基础 电子标签 阅读器对要传递给电子标签的数据进行信号编码、调制，然后通过通路( 传 输介质) 把信号传送给电子标签，电子标签对收到的信号进行解调和译码，这是 阅读器和电子标签之间的数据传输所必要的三个主要功能块。 基带编码是为了使要传输的信息和它的信号表示尽可能地与传输介质的性 能相匹配，防止信息受干扰或发生碰撞以及对某些信号特性的蓄意改变，用某种 程序来保护信息。调制是使高频载波的振幅、频率或相位与调制的基带信号相关 的信号处理过程。在射频识别系统中唯一采用的传输介质是磁场和电磁波。解调 7 江苏大学硕十学位论文 则是另外的调制过程，用于基带信号的再生。信号解码的任务包括两点：从基带 编码中恢复原来的信息，识别和标识传输错误。 2 3 1 基带编码 射频识别系统使用基带编码。通常使用的有： ( 1 ) n r z ( 反向不归零制编码) ； ( 2 ) 曼彻斯特编码； ( 3 ) 单极归零制编码； ( 4 ) 差动双相编码( d b p ) ； ( 5 ) 米勒编码； ( 6 ) 差动编码和脉冲一间隙编码( p p ) 。 其中曼彻斯特编码能够对数据的碰撞进行定位，常作为从电子标签到阅读器 进行信息传输的一种编码方法。 2 3 2 数据传输的完整性 数字通信过程中，因系统特性不良及信道噪声，将会使传输信号失真，产生 误码。通常使用校验的方法来识别传输错误，启动校正措施。常用的校验方法有： 奇偶校验、x o r 、c r c1 3 2 。4 1 。 ( 1 ) 奇偶校验 奇偶校验的特点是简单、应用广泛。通过把一个奇偶校验位组合到每一个传 输的字节中。在传输前，接收端和发送端要统一奇或偶的校验方法，这种简单的 方法的缺点是识别错误的能力低。可以识别错误改变的奇位个，无法识别错误的 偶位个数次； ( 2 ) 纵向冗余校验( l r c ) 纵向冗余校验的x o r 校验和的计算简单、快速。主要用于快速校验小的数 据块，常用于小容量的标签。原理是把一个数据的所有数据字节递归，经过x o r 选通后既可以产生x o r 校验和。但是l r c 不很可靠，多个错误可能相互抵消； ( 3 ) 循环冗余校验法( c r c ) c r c 校验识别传输错误的可靠性很高，但不能校正错误。c r c 校验附加一 些校验位( 典型值为4 位、8 位、1 2 位、1 6 位、3 2 位) 在要传送的数据块上， 8 江苏人学硕士学位论文 这些校验位由该数据块算出并随同数据块一并传送。在接收端，对收到的数据块 重新按规定的算法计算c r c 校验和，从而判定传输过程是否出错。1 6 位c r c 校验适合校验4 k b 大小的数据块。在射频识别系统中传输的数据块一般都比这 个长度小，所以可以采用1 2 位和8 位的c r c 校验。 2 4r f i d 系统的碰撞与多址技术 2 4 1r f i d 系统的碰撞分类 射频识别系统通过无线电进行通信，两个基本通信过程为从阅读器到标签和 从标签到阅读器之间的通信。在同一个射频识别系统中，阅读器和标签在同一个 通信信道中传递数据，因此极有可能在数据传输的过程中发生数据碰撞，数据碰 撞的直接后果就是系统必须花费大量的时间来处理发生碰撞的数据，甚至会带来 无法正确识别有效范围内的所有标签的严重后果。通常，在射频识别系统中存在 如下两种碰掩情况： ( 1 ) 标签碰撞。当一个阅读器有效范围内的两个或者多个标签同时响应阅 读器的指令向阅读器发送信息时，不可避免的发生信号冲突，这时阅读器就无法 识别标签。如图2 3 所示。 阅读器工作范围 图2 3 多标签碰撞 。 阅读器 口 标签 ( 2 ) 阅读器碰撞。阅读器碰撞的本质其实就是阅读器之间的协调问题，一 般而言，阅读器碰撞分一下两种情况。 第一种：阅读器的阅读区域相互重叠，信号相互干扰，一个阅读器信号的传 输会使其他阅读器无法正常工作。 9 江苏人学硕士学位论文 第二种：多个阅读器和一个标签之问的碰撞。当多个阅读器试图向其公共范 围内的一个标签发出指令时就发生了命令碰撞，使得标签无法正确识别指令。 阅读器碰撞在实际使用中并不常见，但仍然有很多学者试图解决这个问题。 本文主要研究的对象为单阅读器情况下的多标签碰撞问题，解决这个问题的 主要有两种手段：一是增大带宽提高数据传输量，二是减少碰撞，增大识别效率。 因为带宽的有限性，第一种方法并不实用，所以必须增大系统的识别效率。r f i d 系统中利用一些防碰撞算法来解决系统碰撞问题，这些算法的通过设置一系列的 相关的命令来防止碰撞的发生。 2 4 2 多址技术 从标签到读写器的通信称为多路存取，无线通信系统中多路存取一般具有这 几种形式：空分多路法( s d m a ) 、时分多路法( t d m a ) 、频分多路法( f d m a ) 、 码分多路法( c d m a ) 。下面分析一下这些多路存取的方法和特点。 ( 1 ) 空分多路法( s d m a ) 3 6 - 3 7 】。空分多路法是在分离的空间范围内进行 多个目标识别的技术。一种方式是将读写器和天线的作用距离按空间区域进行划 分，把多个阅读器和天线放置在这个阵列中。这样，当标签进入不同的阅读器范 围时，就可以从空间上将电子标签区别开来。实现的另外一种方式可以在阅读器 上安装一个相控阵天线，使天线的方向性图对准某个电子标签，这样，根据阅读 器不同的工作区域可以区别开不同的电子标签。s d m a 技术的缺点是天线系统 的复杂带来的高实施费用。因此，这种防碰撞法的应用相当有限，通常局限于一 些不计成本的特殊的应用场合。图2 4 就是一种使用定向天线的自适应的空分多 路法的示意图。 图2 4 使用定向天线的自适应的空分多路法 1 0 江苏大学硕十学位论文 ( 2 ) 频分多路法( f d m a ) 1 3 8 j 。频分多路法是把若干个使用不同载波频率 的传输通路同时供通信用户使用的技术。通常情况下，采用f d m a 的射频识别 系统阅读器用于发射信号和传递能量的频率足固定的，同时，阅读器上配有多个 接收机，用于接收不同的电子标签，每个接收机都有自己的工作频率，只响应同 工作频率的电子标签。通过这种一一对应的方式来区别工作区域内的电子标签。 f d m a 的一个缺点是阅读器的成本非常高，因为每个接收通路必须有自己的 单独的接收器。不仅如此，这种方法还占用了更加有限的频率资源。因此，这种 反碰撞方法也有着极大的限制性，仅用于少数特定场合。 ( 3 ) 时分多路法( t d m a ) 1 3 纠。时分多路发是把整个可供使用的通路容量 按时问分配给多个用户的技术。t d m a 首先在数字移动无线电系统的范围内推 广使用并得到成功。对于射频识别系统而言，t d m a 构成了防碰撞法的最大量 一族。这种方法又可分为应答器控制( 应答器驱动) 和阅读器控制( 询问驱动) 法。因为对阅读器的数据传输没有控制，应答器控制法的工作是非同步的。但可 以同步进行观察，因为所有的应答器同时由阅读器进行控制和检查，大多数应用 采用由阅读器为主控制器的控制方法，这种用阅读器控制的方法也称作定时双工 传输法。如图2 5 所示。 图2 5 时分防碰撞算法分类 江苏人学硕士学位论文 在上述3 中防碰撞算法中，空分多址和时分多址实现成本高，多用在军事等 重要场合。大量使用标签的快递、零售等民用领域，还是以时分多址的方法为主。 2 4 3 时分多路法分析及改进方向 综上所述，目前应用较为普遍的防碰撞算法：二进制树的确定性算法和a l o h a 的不确定性算法，属于时分多路的方法。其中，二进制树的确定性算法主要有二 进制搜索( b i n a r ys e a r c h ) 和动态二进制搜索( d y n a m i cb i n a r ys e a r c h ) 算法， 此外还有智能的寻呼树算法( i n t e l l i g e n t q u e r yt r e e ) 、自适应的被动标签防碰撞 算法( a d a p t i v em e m o r y l e s st a ga n t i c o l l i s i o n p r o t o c 0 1 ) 以及基于返回式二进制树 形搜索的反碰撞算法等；a l o h a 的算法有a l o h a 算法、时隙a l o h a 算法( s l o t t e d a l o h a ) 、动态时隙a l o h a 算法( d y n a m i cs l o t t e d a l o h a ) 。此外还有帧时隙a l o h a 算法( f r a m e s l o t t e da l o h a ) 、动态帧时隙a l o h a 算法( d y n a m i cf r a m e s l o t t e d a l o h a ) 等。 a l o h a 算法简单易实现，但存在“标签饥渴”( 即漏读) 和错误判决等问题， 识别时间较长，信道利用率低( 最大3 6 ) ；二进制算法的优点在于识别率达到 了1 0 0 ，理论上只要时问足够多，二进制算法就能识别全部的标签。现有的二 进制算法和在二进制基础上改进的衍生算法，利用标签碰撞的编码位数和位置为 依据制定阅读器发出的下一次命令参数，这些算法要求在标签中添加计数器、计 时器、寄存器等，增加了标签的复杂度和功耗。因此，阅读器的查询次数、查询 附带的参数，系统的总通信量，标签结构的复杂度等就成为了二进制算法性能的 衡量指标。 和a l o h a 算法相比，二进制算法的高识别率是显著的优点。如何在不增加标 签结构复杂度的基础上，降低阅读器的查询次数和系统的总通信量，减少系统工 作量，提高系统工作效率，改进二进制算法，是本文的主要研究内容。 目前，二进制及其衍生算法利用的唯一标识码，是与物品信息无关的标签编 码，随机产生没有一定的规律。但在标签编码标准体系下产生的唯一标识码，都 遵循着一定的规律，编码的每段数据都有具体的代表意义，利用标准编码中的信 息，可以作为改进二进制算法的手段，是实现高识别率、低复杂度二进制防碰撞 算法的可能的方向。 1 2 江苏大学硕士学位论文 2 5 本章小结 本章简要闸述了r f i d 系统的结构和组成、r f i d 系统的工作原理和工作的 基本操作流程，分析了数据传输完整性中的奇偶校验、纵向冗余校验( l r c ) 和 循环冗余校验法( c r c ) 三种方法，这些都是防碰撞算法研究的系统环境。在射 频识别系统空分多路法( s d m a ) 、时分多路法( t d m a ) 、频分多路法( f d m a ) 、 码分多路法( c d m a ) 四种防碰撞多址技术中，重点分析了应用较为普遍的时分 多路法的两种经典防碰撞算法：二进制算法和a l o h a 算法的优缺点。相比较之 下，二进制算法在识别率方面有更多的优越性( 理论上，只要时间足够长，识别 率可达1 0 0 ) ，因此，本文以改进的二进制防碰撞算法为研究目的，减少阅读 器查询次数、降低系统总通信量，为时分多址防碰撞算法，寻求一种新的、识别 率高、耗时少的标签防碰撞算法。利用标准编码的规律性，是实现这种算法的可 能方向。因此，有必要在研究二进制的改进碰撞算法之前，对编码标准进行分析 讨论。 江苏大学硕士学位论文 第三章r f i d 编码标准研究 当前r f i d 还未形成统一的编码标准，市场为多种标准并存的局面。除了 i s o 、e p cg l o b a l l 4 0 4 6 】等欧美的标准化组织外，日本u i dc e n t e r ，中国、韩国也 在积极研究、制定相关的r f i d 标准。e p cg l o b a l 是由u c c 和e a n 联合发起 的非盈利性机构，全球最大的零售商沃尔玛连锁集团、英国t e s c o 等1 0 0 多家 美国和欧洲的流通企业都是e p c 的成员，同时由美国i b m 公司、微软、a u t o i d l a b 等进行技术研究支持。日本u i d 主导日本r f i d 标准研究与应用的组织是 t 引擎论坛( t e n g i n ef o r u m ) ，该论坛已经拥有5 0 0 多家成员，成员绝大多数 是日本厂商，如n e c 、目立、东芝等，少部分来自国外的厂商，如微软、三星、 l g 和s k t 。 本章选取e p c 标准和u i d 标准进行研究分析，构建编码原则，提取通用结 构，进行快递行业和零售业商品标签编码基本构成的设计，为利用标准编码的规 律性、实现高识别率、低复