（计算机系统结构专业论文）融合安全机制的rfid防碰撞算法研究.pdf

摘要 摘要 r f i d 归属于非接触自动识别技术范畴。当阅读器信号作用范围内存在两个 以上的多个标签，在同一时隙内有两个或者以上的标签向阅读器传送信息时， 信号发生干扰，标签产生冲突，这种情况称为标签冲突。 本文着重分析r f i d 系统中标签的防碰撞问题，针对防碰撞算法和安全性协 议这两项关键的技术，进行了系统的研究，提出一种新的具有较高安全性的防 碰撞算法。这种防碰撞算法融合了安全机制在内，先是由用户在用户区输入1 6 b i t 的数据，再用随机化密钥对此数据加密，存入用户区。当标签发生碰撞时，利 用基于后退式索引的二进制搜索算法进行防碰撞选择，最后选出需要的标签。 通过与随机化密钥的认证协议相结合，在进行防碰撞识别的同时，大大提高了 系统的安全性。理论分析和实验仿真结果表明，该算法具有一定的新颖性。 本文的创新主要体现在： 1 、针对现在r f i d 安全协议的一些不足，提出了一种新的随机化密钥安全 认证。 2 、在基于后退式索引的二进制树型搜索防碰撞算法的基础上加入了安全协 议，得到了一个新的防碰撞算法。 文章的最后部分做出了总结以及需要继续努力的方向。 关键词：r f i d 技术；r f i d 防碰撞算法；安全认证协议；数据加密 a b s t r a c t 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 ni san o n - c o n t a c ta u t o m a t i ci d e n t i f i c a t i o n t e c h n o l o g y t h e r ea r et a gc o l l i s i o na n dr e a d e rc o l l i s i o no fr f i d t h ea l g o r i t h mt o s o l v ec o l l i s i o ni sc a l l e da n t i - c o l l i s i o na l g o r i t h m b e c a u s et a gi sl o w - p r i c e d ，a n di t s f u n c t i o ni sl i m i t e d ，i tc a l l td i s t i n g u i s hd i f f e r e n tr e a d e r sa n dd o n tm a k ea na s s i s t a n t r o l ei nt h ec o m m u n i c a t i o n , i ta l s od o e s n ts u p p o ac o m p l i c a t e dc o m m u n i c a t i o n a g r e e m e n ta n di t sf r e q u e n c yi sl i m i t e d t h i sa r t i c l ef o c u s e so l la n a l y s i so fr f i dt a ga n t i - c o l l i s i o ns y s t e m ，t h ep r o b l e m f o ra n t i - c o l l i s i o na l g o r i t h m sa n ds e c u r i t yp r o t o c o l so ft h e s et w ok e yt e c h n o l o g i e s ， c o n d u c t e das y s t e m a t i cs t u d yp r e s e n t san e wh i g hs e c u r i t ya n t i - c o l l i s i o na l g o r i t h m a n t i - c o l l i s i o na l g o r i t h mt h a tc o m b i n e st h es e c u r i 够m e c h a n i s m s ，i n c l u d i n g ，f i r s t e n t e r e db yt h eu s e ri nt h eu s e ra r e a16 b rd a t a ，a n dt h e nr a n d o m i z e dt ot h o s ek e yd a t a e n c r y p t i o n , i n t ou s e ra r e a s w h e nat a gc o l l i s i o no c c u r s ，u s i n ga ni n d e xb a s e do n b a c k t y p ea n t i - c o l l i s i o na l g o r i t h mf o rb i n a r ys e a r c ho p t i o n s ，t h el a s te l e c t e dn e e dt o l a b e l w i 也t h er a n d o m i z a t i o nk e ya u t h e n t i c a t i o np r o t o c o lc o m b i n i n ga n t i - c o l l i s i o n i d e n t i f i e dd u r i n gt h es a m et i m e ，g r e a t l ye n h a n c et h es y s t e m ss e c u r i t y t h e o r e t i c a l a n a l y s i sa n de x p e r i m e n t a ls 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 mh a sac e r t a i n n o v e l t y t h i si n n o v a t i o ni sm a i n l yr e f l e c t e di n ： 1 , i m p r o v e dr f i db a c k - t y p ei n d e xb a s e do nab i n a r yt r e es e a r c ha n t i - c o l l i s i o n a l g o r i t h m ，o nt h eb a s i so ft h i sa l g o r i t h mb ya d d i n gas e c u r i t ya g r e e m e n t 2 , b a c k - t y p ei n d e x e sb a s e do nab i n a r yt r e es e a r c ha n t i - c o l l i s i o na l g o r i t h ma n d a d d e ds c c u r i t yp r o t o c o l s ，g e tan e wa n t i - c o l l i s i o na l g o r i t h m t h el a s tp a r to ft h ea r t i c l ep o i n t e do u tt h ep o i n to ft h i ss t u d ya n dc h a r a c t e r i s t i c s o f t h ei n n o v a t i o n , t h en e e df o rc o n t i n u e de f f o r t s k e yw o r d s ：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 m ；s e c u r i t ya u t h e n t i c a t i o n p r o t o c o l ；d a t ae n c r y p t i o n 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：锺少蚋签字日期：加i 拜、月日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权南昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：馑君蛛 导师签名： 签字日期：砀哆年7 月f 日 签字日期：月日 第l 章前言 第1 章引言 1 1 研究背景 射频识别( i 疆i d ) j 是一种非接触自动识别技术，它的目的是自动识别需要识 别的对象并获取该对象的相关数据，它利用的是无线射频信号，采用非接触双 向的通信方法。承印物和电子技术相融合的代表性产物就是r f i d 射频标签。储 存了物品信息的集成电路芯片以及射频电路都包含在承印物中，阅读器发送射 频识别信号，系统中的天线接收该信号，再通过标签应答得到标签中的信息， 同时也可以发送到后台数据库进行处理，这样一来就能完整的实现产品的射频 识别，标签的查找，物品的管理，其优势大大高于原始的条形码。因此在以后 的商品以及物流中r f i d 有可能成为一种主流技术应用其中。 现在，r f i d 不仅成为国家级省级科研的重点研究方向之一，我国十一五计 划都将其列入其中。面向信息化建设和重大应用，进行业务和技术创新，带动 核心技术与产品的研发，在下一代网络、宽带无线移动通信、数字电视、家庭 网络、智能终端、汽车计算平台、无线射频识别( i u d ) 和传感网络、网络与 信息安全、信息技术应用与数字内容等重点领域实现突破，形成一批具有自主 知识产权的核心技术和创新产品，基本满足国内应用对技术与产品需求，形成 较为完整的产业链，到2 0 2 0 年，形成较为完善的科技创新体系。r f i d 中的防 碰撞算法( 有些地方称防冲突算法) 是解决r f i d 系统中当多个标签读取数据有 冲突时，快速准确的选中需要的电子标签，从而提高整个系统的读取数据的效 率和准确率，因而成为近年来r f i d 系统的研究热点之一。 1 2 国内外研究现状 当前对r f i d 的研究主要集中在r f i d 技术标准、r f i d 标签成本、天线的 设计、r f i d 防碰撞算法以及安全与隐私权保护等方面。由于本文研究的重点是 防碰撞算法和安全性的研究，所以下面我们着重对这两方面进行介绍。在很多 时候会出现有多个标签同时存在于阅读器信号作用范围内，且同一时刻可能有2 个或多个标签向阅读器发送信息，在没有采取多址访问控制机制情况下，信息 传输过程会产生冲突，导致无法读取所需要的信息，同时标签不能被阅读器正 第l 章前言 确识别，这种情况就叫做标签碰撞。所以我们需要一种技术解决碰撞问题，使 标签能够快速准确的被系统识别，以此达到防碰撞的目的。多标签防碰撞问题 本质上是信道共享的问题，而信道冲突的问题由来己久，在现有的解决方法中 大概包括以下4 种：频分多址方法、空分多址方法、码分多址方法和时分多址 方法。在r f i d 无源标签系统中，目前广泛使用的防碰撞算法大都是时分多址方 法，即采用不同的时隙发送信息，主要有2 大类：基于二进制树的算法和基于 a l o h a 的算法。a l o h a 算法1 3 j 最初用来解决无线网络通信中数据包拥塞的问 题。随后该算法被大范围的应用在r f i d 系统中，原理是当一个标签进入阅读器 所在的区域时，标签就会自动向阅读器发送指令发生自身的i d 信息，阅读器接 收认证后，标签和阅读器才开始通信。如果系统检测到标签发生数据位的冲突， 那么冲突的标签就随机等待一段时间再重新发送所需要的数据，直到系统检测 不到有标签冲突，读取全部的标签信息。在a l o h a 算法的基础上改进出来的 算法有纯a l o h a 算法和时隙a l o h a 算法等。二进制树防碰撞算法采用的是 将标签分为不同的子集进行查询，划分子集的方法通常有两种，一种是生成随 机数0 和1 ，分为两个子集；第二种是根据标签本身就拥有u i d 信息进行划分。 二进制数防碰撞算法的基本原理是：当系统有标签冲突时，将这些冲突的标签 分成2 个子集合，分别为左子集0 和右子集1 ，刚开始先检测左子集0 ，看左子 集中是否有标签发生碰撞，如果没有发生碰撞，识别出该子集内的标签：接下 来检测右子集l ，原理跟左子集0 相同，进而识别出系统内的所有标签。现在改 进出来了二进制搜索算法、动态二进制防碰撞算法，本文用的是基于后退式索 引的二进制搜索防碰撞算法【1 7 】。在安全方面，r f i d 的安全认证协议一般被分为 重量级、重量级以及轻量级三种。重量级安全认证协议，即完善( f u l l - f l e d g e d ) 的 安全认证协议，它使用的都是d e s 、a e s 、r s a 等比较完善和安全的加密方法， 是安全协议里安全级别最高的，但由于该协议采用的都是较成熟的加密算法， 应用成本较高，所以一般只应用与大型的对安全性要求较高的领域，低成本的 r f i d 系统不太适宜采用重量级的安全认证协议。用于电子护照且基于i c a o 标 准的i e a o 认证协议属于重量级安全认证协议，安全系数很高，采用的是6 4 位 密钥的双密钥3 d e s 算法和消息认证码。轻量级安全认证协议采用简单的位运 算，虽然降低了安全性，但同时成本也得到了控制。这些位运算分别有：或、 异或、与、非和移位等。s a s i 协议和t z n i a p 协议都属于比较典型的轻量级安 全认证协议。t z m a p 协议是所有的安全协议中使用消息数最少的协议，它只需 2 第1 章前言 要两条消息就能对系统进行验证，但简单的同时也大大的降低了协议的安全性， 低端的r f i d 系统中经常应用到此协议。中量级认证协议的安全性介于重量级和 轻量级二者之间，采用的是具有一定安全强度和复杂度的杂凑运算，该协议的 安全性比较高而成本需求又低于重量级协议，因此适合领域非常广。我们所熟 知的h a s h - l o c k 和h a s h 链协议就属于该协议。h a s h l o c k 协议( s a r m a ，2 0 0 3 ) 1 3 4 3 5 】 为了避免用户信息泄漏和被追踪，它使用的是m e t a i d ( 通对标签i d 的杂凑运算 获得) 来代替标签的本身所拥有的i d 。但是该协议中m e t a i d 和本身的i d 都是固 定不变的，且传送形式是以明文的方式，因此很容易被攻击。h a s h 链协议是通 过将不同的杂凑函数应用于不同的读写器上，当读写器向标签发送认证请求时， 各个标签的应答将会不一样，应答的标签与数据库需要共享一个初始的秘密值。 该协议是针对标签的验证，无法验证阅读器的身份，如果攻击者伪装成阅读器 的话，就能顺利的获取标签的信息，该协议无法抵挡重传攻击和假冒攻击，并 且由于使用的不同的杂凑运算，系统的计算量将非常大，所以该协议也存在很 多缺点。此外，每一次标签进行认证时，后端数据库都要对系统内每一个可能 存在的标签进行杂凑运算，使其计算载荷非常大。因此，要尽快设计出一种安 全、高效和低成本的r f i d 安全认证协议。 1 3 课题来源 项目来源于广东省自然基金项目“物联网e p c 事件流处理机制问题研究 ( 0 6 0 2 3 1 3 1 ) 、广东省科技攻关项目“物联网r f i d 关键技术研究及信息平台的 集成应用( 2 0 0 5 8 1 0 1 0 1 0 0 6 ) 、“超高频r f i d 多读写器组网协调机制与防冲突技 术研究( 2 0 0 8 8 0 1 0 2 0 0 0 3 7 ) 。 1 4 研究意义 由于射频技术的这些优点，许多领域已经开始大规模的使用该技术，但是 仍然存在许多制约射频识别技术发展的因素，我们必须尽快解决好这些问题。 这些问题有：射频识别系统标准的统一化问题、射频识别系统成本问题、系统 内部数据处理能力问题、系统安全性问题和数据传输的完整性问题等等。其中 影响r f i d 发展的两个重要因素分别是数据传输的完整性问题和安全性问题，这 两个问题直接关系到整个系统性能的好坏。 3 第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 技术 的优势所在，但是同时也是r f i d 技术的难题。现代社会，各个领域对信息技术 的要求越来越高，也对技术提高工业生产，便利生活提出了更高的要求，同时 也给技术的研究提出了一些新的问题。当前由于应用的系统和标签的不同，现 有的防碰撞算法都存在各自的优缺点，但这些现有的算法都是仅仅对防碰撞进 行研究，很少有把防碰撞与安全性结合在一起的算法。如何在已有的研究成果 的基础上，提出性能更优、更实用有效的算法，进一步提高r f i d 系统的安全性 和读取的准确性，这对于r f i d 技术的推广和进一步发展，都有着十分重大的意 义。 1 5 论文主要工作 ( 1 ) 研究r f i d 系统的原理。包括基本概念、基本工作原理、r f i d 标准等。 ( 2 ) 研究r f i d 防碰撞技术原理。 ( 3 ) 研究r f i d 加密算法并应用到防碰撞算法中。 4 第1 章前言 法。 ( 4 ) 研究一种把安全机制融入到现有的防碰撞算法中的新型的防碰撞算 1 6 论文组织结构 本文共分6 章，各章内容安排如下： 第l 章引言介绍了本课题的背景、意义，课题来源。 第2 章r f i d 系统的工作原理详细讨论了r f i d 系统的工作原理。 第3 章标签防碰撞算法讨论和分析了r f i d 系统中一些典型的标签防碰撞 算法。 第4 章r f i d 的安全认证协议讨论和分析了r f i d 系统当前的一些加密算法 以及算法的优缺点。 第5 章一种新颖的r f i d 防碰撞算法的设计本章提出了一种新的防碰撞算 法，先是提出一种随机化密钥双向认证协议，然后将提出的协议与后退式二进 制防碰撞算法结合，得到一种新的防碰撞算法。 第6 章总结与展望对本论文进行了总结，并提出了今后需要继续努力的方 向。论文最后部分是参考文献”和附录。 5 第2 章r f i d 系统的t 作原理 第2 章r f i d 系统的工作原理 光线射频识别技术是从一十世纪9 0 年代兴起的种非接触的自动识别技 术，然而r f i d 并非一种新必的技术，其历史可追溯到一十世纪初。1 9 2 2 年雷 达诞生，r f i d 技术直接继承了雷达的概念，并f f l 此发展起来的一种新的自动口! 别技术。 2 1r f i d 系统 2 1 1r f i d 系统的组成 射频识别僻a d i o f r c q u c n e y i d e n t i n e a t i o n ，r f i d ) 系统 6 1 般由读写器、电子 标笠、无线以及主机等组成。根据用户不同的应用目的以及应用环境，系统的 组成会有所不同，但工作原理都是一般甫信号拉射机、信号接收机、发射天线 和接收天线这几个部分组成。下山我们分* 对它的各个组成部分分别加以说叫。 系统如图2 1 所示。 图2 1r f i d 系统构成图 ( 1 ) 信号发射机在r f i d 系统中我们最为熟知的电子标签就是信号发射 6 第2 章r f i d 系统的工作原理 机的一种，电子标签用于存储信息，并且存储在标签上的信息将通过标签自动 或者在外力的作用下发射出去，而条形码只可以存储信息不能发送信息，因此 标签比条形码更具实用性。 ( 2 ) 信号接收机信号接收机即阅读器。它的主要功能就是在标签和后端 数据库之间进行数据传输，同时还可以控制复杂信号的状态、信息的校验以及 更正等功能的实现。阅读器的复杂程序跟标签测类型和系统完成的功能是相对 应的。 ( 3 ) 编程器编程器的功能就是用户或者生产者能够通过系统向标签写入 数据。编程器一般都是预先在标签中写入数据，当标签被应用在系统的时候我 们就直接把标签附在需要被识别的物体上，这样的写入数据的方式一般都是离 线完成的。还有一种写数据的方式是在线完成数据的写入，尤其是在生产过程 中作为交互式便携数据文件来处理时。不过并不是所有的系统都需要编程器， 只有可读可写标签系统才需要使用到它。 ( 4 ) 天线标签与阅读器之间的数据传输发射接受都是靠天线来完成的， 所以系统的功率、天线的形状和相对位置将会极大的影响到数据的传输过程， 因此系统天线的设计和安装都需要专业人士来完成。 2 1 2r f i i ) 系统的耦合类型 由于r f i d 系统作用的距离比同，我们把标签天线和阅读器天线之间的耦合 分为密耦合系统【7 1 、遥耦合系统7 1 和远距离系统【7 1 这三类。 ( 1 ) 密耦合系统 密耦合系统，又称紧密祸耦合系统，利用射频标签与阅读器天线的无功近 场区之间的电感耦合( 闭合磁路) 构成的无接触空间信息传输射频通道进行工作。 其典型的工作范围为0 1 c m 。可以用介于直流和3 0 m h z 交流之间的任意频率工 作。 ( 2 ) 遥耦合系统 遥耦合系统，又称为电感无线装置，也是利用射频标签与阅读器天线的无 功近场区之间的电感耦合构成的无接触空间信息传输射频通道进行工作。其作 用距离可达h 。发送频率使用1 3 5 k h z 以下，或6 7 5 m h z 、1 3 5 6 m h z 以及 2 7 1 2 5 m h z 频率，目前大部分使用的都是这种系统。 ( 3 ) 远距离系统 7 第2 章r f i d 系统的工作原理 利用标签与阅读器天线的辐射远场区之间的电磁耦合所构成的非接触空间 信息传输射频通道进行工作的系统叫做远距离系统。典型的作用距离是从h 到 1 0 m 。典型的工作频率有：4 3 3 m h z 、9 1 5 m h z 、2 4 5 g h z 和5 8 g h z 。密耦合系 统和遥耦合系统中，阅读器与标签之间射频信号的耦合属于电感耦合。这种耦 合是根据电磁感应定律，通过空间高频交变的磁场而实现的耦合。识别作用的 距离小于l m ，典型作用距离为1 0 2 0 c m 。而远距离系统的阅读器与标签之问射 频信号的耦合则属于电磁反向散射耦合。这是一种雷达原理模型，发射出去的 电磁波，碰到目标后反射，同时携带回目标信息，依据的是电磁波空间传播规 律。识别作用距离大于l m ，典型作用距离为3 1 0 m 。 2 2r f i d 的工作原理 r f i d 的工作原理是：当电子标签进入磁场后，阅读器发射特殊的射频信号， 标签接收到该信号之后凭借从感应电流中获得的能量把本身存储的信息发送出 去，或者根据频率的不同主动发送信号，阅读器接收该信息并对数据进行解码， 再送至中央信息系统进行有关数据的处理。 2 2 1 数据传输原理 射频识别系统中的阅读器和标签之间的通信通过电磁波来实现的，按照通 信距离可分为远场和近场，a s k 、f s k 、p s k 是阅读器到标签的三种数据传输方 式，而负载调制和反向散射调制【3 】贝0 是标签到阅读器的数据传输方式。 ( 1 ) 负载调制近距离低频r f i d 系统是通过准静态场的耦合来实现的。在 这种情况下阅读器和标签之间的天线能量交换方式类似于变压器结构，称之为 负载调制。这种调制方式在1 2 5 k h z 和1 3 5 6 m h z 射频识别系统中得到了广泛的 应用。 ( 2 ) 反向散射调制反向散射调制技术是指无源标签将数据发送回阅读器所 采用的通信方式。在典型的远场，如9 1 5 m h z 和2 4 g h z 射频识别系统中，阅读 和标签之间的距离有几米，而载波波长仅有几到几十厘米，阅读器和标签之间 的能量传递方式为反方向散射调制。 2 2 2 数据传输方法 r f i d 系统中，我们选用的标签和阅读器之问的数据传输方法为以下三种： 8 第2 章r f i d 系统的工作原理 全双工、半双工以及时序法。我们对三种方法进行了比较，如图2 2 【l 】所示。所 谓半双工方式，就是通信双方设备即是发送器，也是接收器，两台设备可以相 互传送数据，但某时刻只能向一个方向传送数据。因此在半双工法中，电子 标签到阅读器的数据传输和阅读器到电子标签的数据传输是数据交替传输的。 当系统的频率低于3 0 m h z 时常常使用的方法是负载调制的半双工法。所谓全双 工方式是指通信双方设各既是发送器，也是接收器，两台设备可以同时在两个 方法上传送数据。由此可见数据在电子标签和阅读器之间的双向数据传输是同 时进行的。阅读器到电子标签的能量传输是连续的并且不决定于数据传输的方 向，这是半双工法与全双工法的共同点。时序法是把时间分为多个间隔，阅读 器到电子标签的能量传输总是在一定的间隔内进行的，而标签的能量供应也分 为一定的间隙，标签到阅读器的数据传输也是在标签能量供应间歇时进行的。 方式 f d x ( 全双工) 能量的传输 下传 、 上传 、 h d x ( 半双工) 能量的传输 下传 ， 上传 l ， l rl s e d ( 时序) 能量的传输 下传_ 一 声一 上传 l _ ， -， _ _ 图2 2 全双工，半双工，时序法的比较 2 3 编码 在人机信息交换中，用人所能感知的刺激物作为代码去表示特定意义的事 件、现象或状态，称为信号编码，也称信息编码。信号编码的作用是使要传输 的信息尽可能最佳地与传输通道的性能相匹配。这样的处理包括有对信息提供 9 第2 章r f i d 系统的工作原理 某种程度的保护，以防止信息受干扰或相碰撞。在r f i d 系统中常用的编码方法 有以下几种编码方法：n r z ( 反向不归零) 编码、曼彻斯特( m a n c h e s t e r ) 编码、 单极性归零( u n i p o l a r ) r z 编码、差动双相( d b p ) 编码、m i l l e r 编码、变形m i l l e r 编码( 见图2 4 ) 1 3 。 n r z 编码：“高”信号表示二进制l ，“低 信号表示二进制0 。但是 此码型不方便传输，原因如下：有直流，一般信道难于传输零频附近的频率分 量；收端判决门限与信号功率有关，不方便使用；不能直接用来提取位同步信 号，因为在n r z 中不含位同步信号频率成分；最后，此码的使用要求传输线有 一根接地。 ， 曼彻斯特编码：在半个比特周期的负边缘表示二进制1 ，半个比特周期的 正边缘表示二迸制0 。曼彻斯特编码在采用负载波的负载调制或者反向散射 调制时，通常用于从电子标签到读写器的数据传输，因为这有利于发现数据传 输的错误。这是因为在位长度内，“没有变化”的状态是不允许的。当多个电子标 签同时发送的数据位有不同值时，接收的上升边和下降边互相抵消，导致在整 个位长度内是不间断的副载波信号，由于该状态不允许，因此读写器利用该错 误就可以判定碰撞发生的具体位置。 单极性归零编码：在半个比特周期中的“高”信号表示二进制1 ，而持续 整个周期的低信号表示二进制0 。此码可以用来提取位同步信号。 差动双相编码( d b p ) ：在半个比特周期中的任意边缘表示二进制0 ，而没有 边缘就是二进制1 。此外在每一个比特周期开始时，电平都要反向，这样对 于接收器来说位节拍信号容易重建。 m i l l e r 编码：在半个比特周期的任意边缘表示二进制1 ，而经过下一个周 期中不变的l 电平表示二进制o 。如果连续一串0 ，则在0 比特周 期开始时产生电平交变。因此，对接收器来说，位节拍比较容易重建。 变形m i l i e r 编码：变形m i l i e r 编码相对于m i l i e r 编码来说，将其每个边沿都 用负脉冲代替，由于负脉冲的时间很短，可以保证数据传输过程中从高频场中 连续给标签提供能量。曼彻斯特编码在数据传输过程是不允许出现“没有变化 的状态，如果出现这种状态，则将其标志为传输碰撞位。如果两个或多个标签 同时发出数据的数位有不同值，则接收的上升边缘和下降边缘相互抵消，以至 这个位窗持续的时间内接收器收到的是不间断的载波信号。这种碰撞导致没有 变化的状态，从而可以按位跟踪碰撞的出现。如图2 3 所示，当阅读器得到数据 1 0 第2 章r f i d 系统的工作原理 译码为1 0 1 7 7 0 1 0 时，应用这种编码方法再加上二进制搜索算法，就可以很快的 在阅读器作用范围内找到一个唯一确定的标签。 10ll0ol 0 n r 编码 l0l? ? o l0 曼彻斯特编码 单极性归零 诅 差动双向 图2 3 曼彻斯特编码识别碰撞 标签1 标签2 阅读器上的混合信号 数据流的译码 o o0 ol oo ol oo m i l l e r 编码 变形m m e 编 000 l0 00 ol1 00l 图2 4 编码方式 第2 章r f i d 系统的工作原理 2 4c r c 校验码 使用射频技术传输数据时，很容易受到外界干扰，使传输的数据发生改变 导致错误，通常采用校验来识别错误，常用的校验方法有奇偶校验、纵向冗余 校、循环冗余校验。本文中所用的是循环冗余校验，没有纠错功能，当检测到 错后，通知标签重新再发送一遍。 c r c ( c y c l i cr e d u n d a n c yc h e c k ) 循环冗余校验码是常用的校验码，在早期 的通信中运用广泛，因为早期的通信技术不够可靠( 不可靠性的来源是通信技 术决定的，比如电磁波通信时受雷电等因素的影响) ，不可靠的通信就会带来确 认信息的困惑，这里我们举个红军和蓝军通信联合进攻山下的敌军的例子， 第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信 息，但是蓝军担心的是确认信息如果也不可靠而没有成功到达红军那里， 那自己不是很危险? 于是红军再发一条对确认的确认信息，但同样的问题还 是不能解决，红军仍然不敢贸然行动。对通信的可靠性检查就需要校验，校 验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结 果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或 者进行修复。 c r c 校验【l o 】的计算是一个循环过程。就是序列d 后附加一个检验码序列r ， 从而构成序列m 。序列d 是一个p 位的二进制数据，序列r 是一个r 位的二进 制检验码，序列m 是一个长为n = p 竹位的二进制序列。而检验码就是附加的数 据序列r 。它和c r c 的算法以及数据序列有着特定的关系，当系统因为干扰使 数据在传输中的某一位或某些位发生错误时，这种特定的关系就会被破坏，因 此要实现对数据正确性的检查，通过检查这种特定关系即可。校验序列r 是对 数据序列d 进行二进制模2 除法并取余得到的，它除以一个称为生成多项式的 ( r 1 ) 位二进制序列g ，用多项式表示为： 丝盟：烈x ) + 盟 g ( x ) g ( x ) ( 2 1 ) 其中j l j 【工) 表示将数据序列d 左移r 位，q ( x ) 代表这一除法的商，r ( x ) 为余 式。由式子( 2 1 ) 可知，传输的总数据块等于数据序列后附加校验序列r 。而 对序列m 直接进行除法并取余这个计算就是进行校验的整个过程，用式子表示 为： 1 2 第2 章r f i d 系统的工作原理 螋：q ( x ) + 塑 g ( x )g ( x ) 当式子中的r ( x ) 为0 时表示数据正确， 式是用于检错和纠错的，从这个要求出发， o ) c ( x ) 茭bx 川+ 1 = 矿+ 1 的一个因式。 ( 2 ) g ( x ) 的常数项为l 。 ( 2 2 ) 否则认为数据发生错误。因为多项 生成该多项式应能满足以下要求： ( 3 ) 对余数连续做模2 运算，应使余数循环。 下面举个例子例如：g ( x ) = x 4 + x 3 + x 2 + 1 ，( 7 ，3 ) 码，信息码1 1 0 产生的 c r c 码就是： 对于g ( x ) = x 4 + x 3 + x 2 + 1 的解释：( 都是从右往左数) x 4 就是第五位是 l ，因为没有x l 所以第2 位就是0 。1 11 0 1i1 1 0 , 0 0 0 0 ( 设a = l11 0 1 ，b = l1 0 0 0 0 0 ) 取，b 的前5 位11 0 0 0 跟a 异或得到1 0 1 ，1 0 1 加上b 没有取到的0 0 得到 1 0 10 0 ，然后跟a 异或得到0 1 0 0 1 ，也就是余数1 0 0 1 ，余数是1 0 0 1 ，所以 c r c 码是1 1 0 ，1 0 0 1 。于是标准的c r c 码是，c r c c c i t t 和c r c 1 6 ，它 们的生成多项式是： c i i 乏c c c l l l ：= x 16 + x 1 2 + x 5 + 1( 2 3 ) c r c - 1 6 = x 1 6 + x 1 5 + x 2 + l ( 2 4 ) 2 5r f i d 的技术研究 当前r f i d 的技术研究主要集中在工作频率选择、天线设计、防碰撞技术和 安全性等方面，下面针对本文的防碰撞技术和安全方面进行简单介绍【1 3 】。 2 5 1 防碰撞技术研究 r f i d 系统的防碰撞主要分为标签碰撞、阅读器干扰和标签干扰3 种。标签 碰撞就是多个标签在一个阅读器范围内，同时传输数据时造成信号干扰；阅读 器干扰是当多个阅读器处于多个同频范围内，阅读器的作用范围发生重叠，多 个阅读器与重叠的区域内的标签进行通信；标签干扰是指一个标签同时存在与 几个阅读器的重叠的作用范围内，这个重叠范围内的两个或两个以上的阅读器 同时与该标签进行通信。 1 3 第2 章r f i d 系统的工作原理 对于标签碰撞，由于频段的不同我们采取的算法也不同。当处于1 3 5 6 m h z 频段时，我们一般采用a l o h a 算法。而当处于9 1 5 m h z 的超高频( u h f ) 频段， 主要采用二进制搜索算法进行标签的防碰撞。这两种算法各有其优缺点， a l o h a 协议运算简单，但是随着标签的增加，算法的效率会越来越低。而二进 制搜索算法泄漏的信息较多，安全性较差，但算法效率高。而我们前面提到的 f d m a 方法和c d m a 方法，基于这两种访问方式的防碰撞算法主要应用。 2 5 2 安全问题 随着r f i d 在供应链中的应用越来越广泛，供应链管理发展越来越快，当中 的合作随着供应链管理的发展越来越多，用户对系统共享数据的实时性和系统 的安全性的要求日益增高。 随着把r f i d 系统逐步应到到互联网中，用户对系统共享数据的实时性问题 得到了解决，但是由于互联网的广泛性和不安全性，这种方式同时也威胁到了 系统的安全性，不法分子可以通过互联网窃取信息。r f i d 系统同其他的识别系 统相比，一个优势就在于能够实现远距离的读取，但如果系统的安全性没有达 到较高的要求，很容易在传输途中被不法份子截取信息，致使商家的敏感数据 被竞争对手获得，在市场中的竞争力也会因此被迫降低，给商家带来了重大的 经济损失，这样就失去了该系统的价值。早前研究人员发现，r f i d 的晶片可以 携带病毒，通过数据传输把病毒传染给整个系统，致使整个系统崩溃。荷兰的 研究人员已经研究出一种带病毒的晶片，该晶片通过无线数据的传输导致整个 系统中毒，更严重的是晶片还能传播给其他的电子标签。近年来，食品问题日 益增多，“三鹿奶粉”事件给社会造成了极大的影响。如果我们采用r f i d 系统 对牲畜进行跟踪，就可以保证肉类食品的质量，通过跟踪到具体的养殖场和动 物本身，随时都可以对肉类食品进行来源的查询，进而保证食品的安全。但同 时对屠宰厂的工作人员一定要严格训练，如果在屠宰的过程中把晶片不小心掉 入肉块中，将会对造成极大的影响。所以射频识别技术面临的挑战【1 2 】是比较 严峻的，主要有以下几个方面： ( 1 ) 用户标签上信息的保密性，标签不能随意被访问，这样用户的隐私才 能得以保护。 ( 2 ) 在超市中，由于射频识别系统读取的速度快，不法分子可以利用这点 对商品进行扫描和跟踪，进而窃取用户的商业机密。 1 4 第2 章r f i d 系统的工作原理 ( 3 ) 使射频识别系统能经的起各类攻击，具体的攻击有：通过标签信息的 重写，窜改了标签物品的信息；为了欺骗阅读器，使阅读器认为物品仍然存在， 伪造标签应答阅读器；由于系统的前后向信道不对称，给窃听标签信息提供了 条件；不法分子还将干扰射频识别系统的工作频率致使系统拒绝服务；发射可 以破坏标签的电磁波破坏标签等。 ( 4 ) 尽量扩大射频识别技术的应用范围，根据射频识别技术拥有的唯一标 识这个特性，尽可能的应用到各个方面。目前有商家为了避免电子标签在客户 隐私方面的问题，很多商家都采取了当客户拥有商品后把电子标签拆掉，但是 这种方法增加了系统的成本，电子标签的利用率也被迫降低，与系统的低成本 不符合。 1 5 第3 章标签的防碰撞算法 第3 章标签的防碰撞算法 基本的射频识别系统主要由标签、阅读器和天线三个部分组成。早期的系 统中，1 次只能读写1 个射频卡。所有的射频卡之间要保持一定距离，确保一 次只有一个卡在阅读器的读写区域内，这样应用起来很不方便。因为很多时候， 人们不可避免地会出现多个射频卡进入识别区域内，这个时候信号就会互相干 扰，即发生我们所说的碰撞。所以后来，人们采用具有防碰撞性能的系统，这 样系统就可以同时识别进入识别距离的所有射频卡，其并行工作方式大大提高 了系统的效率。 在r f i d 系统中有广播和多路存取这两种基本的通信方式。“广播”是系统 阅读器到电子标签的数据的读取；“多路存取 是多个标签到阅读器的数据的读 取。在同一系统中，当多个电子标签同时向阅读器发送数据时，由于资源的有 限，这些数据将会发生数据位的冲突，因此需要一种技术来解决这种数据位的 冲突问题，就是我们常说的多标签防碰撞算法。现在的防碰撞算法主要是基于 a l o h a 的算法和基于二进制搜索的算法。 3 1 基于a l o h a 的算法 3 1 1 纯a l o h a 算法 a l o h a 算、法【3 1 5 1 是一种简单的算法，它是在a l o h a 思想的基础上，根据 r f i d 系统的特点和技术要求不断改进形成的算法体系，是基于t d m a ( 时分多 路复用) 的。这种算法多采用“标签先发言 的方式，即标签一进入阅读器的 工作范围内就主动向阅读器发送其自身的u i d 。基本工作原理如下： 当标签进入阅读器的工作范围时，标签就主动向阅读器发送其自身的u i d 。 当这个工作范围内只有一个标签发送其u i d 时，阅读器就能快速准确的读出该 标签的u i d 。但是如果有两个以上的标签同时向阅读器发送其u i d ，会因为信 号重叠而出现信号干扰，从而导致信息完全冲突或者部分冲突。当发生了冲突 时，阅读器将发送命令让标签停止信息的发送，使其随机等待一段时间后再重 新发送以减少冲突。a l o h a 算法的算法模型如图3 1 所示。下面我们进行算法 分析： 1 6 第3 章标签的防碰撞算法 部分冲突完全冲突 图3 1a l o h a 算法的算法模型 其中t o 为帧的发送延时，吞吐量s 是在帧的发送时间t o 内成功发送的平均 帧数，p 。为到达的标签能够成功完成通信的概率。由概率统计的知识可知，每 秒钟发送的信息帧的数目服从泊松分布，因此t 秒钟发送n 个数据帧的概率为： p ( n ) = y p z ( 3 1 ) 其中九为平均每秒钟发送的信息帧数。则在t o 时间内，发送的总数据率为： g 矗t 0 ( 3 2 ) 在时间2 t 0 内没有发送信息的概率为： p ( n = 0 ) l t = - 2 t o ，即p e - - e 。2 砌。2 g ( 3 3 ) 则吞吐率： s = o p e = g e - 2 g ( 3 4 ) 从图中我们可以找到交换的数据包量g 与吞吐量s 之间的关系，可以看出 刚开始，随着交换的数据包的增加，