（通信与信息系统专业论文）rfid系统及反碰撞算法的研究与设计.pdf

摘要 r f i d ( 射频识别) 是一种非接触式的自动识别技术。它利用射频信号的空间耦 合( 交变磁场或电场) 实现无接触信息传递以达到对静止和运动物体的识别。具有 信息量大、读取距离远、可同时读取多张卡片等优点，被广泛应用于门禁、物流、 管理等领域。目前r f i d 已经成为国内外重要的研究开发领域。 论文的工作主要包括两部分。 一是对基于i s o i e c l 8 0 0 0 6t y p eb 协议的射频识别系统进行研究，采用模 块化和结构化编程的思想，以v e r i l o gh d l 编程语言，在f p g a 上对基于此协议 的r f i d 阅读器的基带数字信号处理模块进行设计，主要包括主控制器状态机模 块、f m 0 解码器、c r c 检错和编码、曼彻斯特编码器，先入先出存储器、异步 收发机等。本文提出了基于i s o i e c l 8 0 0 0 6 标准的r f i d 系统阅读器数字处理部 分的单芯片解决方案，具有速度快、电路形式简单、移植方便等优点，系统基带 传送速率可达4 0 k b p s 。 二是对r f i d 设计中的一项关键技术反碰撞算法进行了研究。本文对 a l o h a 法，时隙a l o h a 法，动态时隙a l o h a 法，二进制树型搜索算法等几 种不同的反碰撞算法进行了比较和分析，并在此基础上，总结出每种算法的性能 和适用的情况，在f p g a 上设计了基于时隙a l o h a 算法和二进制树搜索算法的 系统模型，该设计具有高可靠性、模块化的特点，且便于二次开发。仿真结果表 明了该模型的正确性和稳定性。 关键词：射频识别反碰撞算法时隙a l o h a 算法二进制树型搜索算法 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 t i f i c a t i o n ) i sak i n do fn o n t o u c h i n ga u t o m a t i c i d e n t i f y i n gt e c h n o l o g y i tc a l li d e n t i f ym o v i n go rq u i e to b j e c t su t i l i z i n gt h e s p a c e - c o u p l i n gi n d u c t i o np r i n c i p l eo f a l t e r n a t i v em a g n e t i ca n d o re l e c t r o n i cf i e l d i t h a sm a n yp r o m i s i n gf e a t u r e ss u c ha s l a r g ei n f o r m a t i o nc a p a c i t y , l o n ge f f e c t i v e d i s t a n c ea n dm u l t i p l et a g so p e r a t i o na n di sw i d e l yu s e di na c c e s sc o n t r o l ，l o g i s t i c sa n d o t h e rm a n a g e m e n ta r e a r f i dh a sb e c o m eac o m m o na n di m p o r t a n tr e s e a r c ha n d d e v e l o p m e n ta r e aa l lo v e rt h ew o r l d 1 1 1 ew o r ko ft h i sp a p e rc a nb ed i v i d e di n t ot w op a r t s f i r s t t h er f i ds y s t e m b a s e do ni s o i e c18 0 0 0 6t y p eb p r o t o c o li sd i s c u s s e d ，t h eb a s e b a n dd i g i t a ls i g n a l s p r o c e s s i n gm o d u l eo f t h er f i dr e a d e ri sd e s i g n e db a s e do nf p g a i nt h ed e s i g n , i t f o l l o w st h ep r i n c i p l eo fm o d u l a r i z a t i o na n ds t r u c t u r e dp r o g r a m m i n g t h ep r o g r a m l a n g u a g ei sv e r i l o gh d l t h ed e s i g no fh a r d w a r ec o n t a i n sm a i nc o n t r o l l e rs t a t e m a c h i n e ，c r ce l i o rd e t e c t i o nm o d u l e ，f m 0d e c o d e r , c r cc o d e ra n de r r o rd e t e c t i o n m o d u l e ，m a n c h e s t e rc o d e r , f i f o ，u a r ta n ds oo n t h i sp a p e rp r o p o s e s a s i n g l e - c h i ps o l u t i o n o ft h ed i g i t a l l o g i cp a r t o ft h er f i dr e a d e rb a s e do n i s o i e c18 0 0 0 6p r o t o c 0 1 i ti sp r o v i d e dw i t hf a s t e rp r o c e s s i n gr a t e ，s i m p l e rc i r c u i t r y a n ds t r o n g e rt r a n s f o r m a b i l i t y t h eb a s e b a n dt r a n s m i s s i o nr a t ei s4 0k b p s t h ea n t i - c o l l i s i o na l g o r i t h m s w h i c hi so n eo fk e yt e c h n o l o g i e s ，i sa l s od i s c u s s e d t h i sp a p e rc o m p a r e sa n da n a l y z e sl o t so fa l g o r i t h m ；i n c l u d ea l o h aa l g o r i t h m , s l o t t e da l o h aa l g o r i t h m , d y n a m i cs l o t t e da l o h aa l g o r i t h ma n db i n a r yt r e e a l 舒t 1 1 1 1 1 e v e r yk i n do fa l g o r i t h mp e r f o r m a n c ea sw e l la st h e i rs u i t a b l es i t u a t i o na r e c o n c l u d e do nt h eb a s i so ft h ec o m p a r i s o na n da n a l y s e t h es y s t e mm o d e lo fs l o t t e d a l o h aa l g o r i t h ma n db i n a r yt r e ea l g r i t h mb a s e do nf p g a sa lea l s op r o v i d e d t h e s e d e s i g n sh a v ea d v a n t a g ei nr e i l a b i l i t ya n dm o d u l a r i z a t i o n ，a n dc a nb er e d v e l o p e de a s i l y i tc a r r i e so nt h es i m u l a t i o nt ot h e s et w om o d u l e so fa l g o r i t h m t h er e s u l t so ft h e s i m u l a t i o ni n d i c a t et h a tt h i sd e s i g ni ss t a b l e ，r e l i a b l e k e yw o r d s ： r f i d ，a n t i - c o l l i s i o na l g o r i t h m ，s - 6 d o h aa l g o r i t h m ，b i n a r yt r e ea l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 磺究成果，除了文巾特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得叁鲞蕉鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：一王j 袭夫 签字日期：多鲫窘年月乡日 学位论文版权使用授权书 本学位论文 乍者完全了解基童苤堂有关保留、使用学位论文的规定。 特授权墨窒盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部f j 或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：上 导师签名： 签字飘期：劢孑年胃占酲 签字匿蓑：疹参g 年；周；墨 第一章绪论 第一章绪论帚一早三百下匕 射频识别技术是2 0 世纪9 0 年代开始兴起的一种自动识别技术，它将数据存 储在一块硅芯片中，数据载体与一个所属的阅读器之间的数据进行非接触传输。 这项技术作为一种快速、实时、准确采集与处理信息的高新技术和信息标准化的 基础，被列为本世纪十大重要的技术之一【1 1 ，得到市场的广泛认可，已经逐渐发 展成为一个独立的跨学科的专业领域。 1 1 射频识别技术概述 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 ) 的缩写，是自动 识别技术的一种【2 】，它是一项利用射频信号通过空间耦合( 交变磁场或电磁场) 实 现无接触信息传递并通过所传递的信息达到识别目的的技术，可识别高速运动物 体并可同时识别多个目标【3 】。r f i d 系统中射频标签上包含了存有产品信息的i c 芯片与天线组成的射频电路，通过天线接收来自专用阅读器所发射的射频信号， 应答出标签芯片中所包含的数据信息，并可送入主计算机进行处理，从而实现产 品非接触式的识别、7 查找与管理。同时r f i d 还具有移动数据库的特性。 随着大规模集成电路技术的进步以及生产规模的不断扩大，应用射频识别技 术的产品成本将会不断降低，其应用领域也将越来越广泛。所以有人说，r f i d 有可能发展成为今后全球商品或物流中最广为采用的技术之一【4 】。 1 2 与其他自动识别技术的比较 在当今社会，自动识别技术在商业、生产、流通等多个领域得到了快速的普 及和推广，给我们的生活带来了巨大的变化5 1 。自动识别系统主要有：条形码系 统、光学符号识别系统、生物识别系统( 例如语音识别、指纹法识别系统) 、以及 新兴的射频识别( r f i d ) 系统等。自动识别方法的目的和实质是提供一种物品信息 的载体。表1 1 给出了各种识别系统的优缺点比较。 第一章绪论 表1 1 各种识别系统的优缺点比较4 】 泌 条形码光学符号语音识别生物技术i c 卡 r f i d 表示测量法 典型的数据 1 1 0 01 一l o ol 扣6 4 k1 6 - - 6 4 k 量字节 数据密度小小高高很高很高 机器阅读的 好好费时间费时间好好 可读性 个人阅读的受制约简单容易简单容易 困难不可能不可能 可读性 受污染潮湿 很严重 很严重 可能 没有影响 影响 ( 接触) 受光遮盖影全部失全部失效可能没有影响 响效 受方向和位很小很小一个插入没有影响 置影响方向 用坏磨损有条件有条件的接触没有影响 的 购置费很少一般很高很高很少一般 工作费用很少很少无 无一般无 未经准许的容易容易可能不可能不可能不可能 复制修改 阅读速度低低很低很低低很快 4 s3 s 5 s5 1 0 s- 4 s一0 5 s 传输最大距 0 5 0 c m i ) b i n ，其中b i n 代表二进制，g r e y 代 表格雷码， 1 代表左移1 位， 表示按位异或，这样可以获得较好的速度 2 3 】。 采用格雷码是防止同步两个时钟域的异步信号产生的亚稳态。由当前的读地址得 到下一周期的读地址，格雷码变换为读指针，经过两级由写时钟控制的d 触发 器进行同步，采用两级同步是防止亚稳态的发生，将读指针与写指针进行比较比 较得到满标志。空标志位的得到与此类似。图4 8 是f i f o 模块仿真的结果。 2 7 第四章r f i d 系统设计 圈4 - 8 f i f o 模块仿真波形 4 2 6 通用异步收发机( u a r t ) u a r t ( 通用异步收发器1 是广泛使用的串行数据传输协议。u a r t 允许在串行 链路上进行全双工的通信。专用的u a r t 集成电路如8 2 5 0 8 2 5 1 ，n s l 6 4 5 0 等 已经相当复杂 ，有些含有许多辅助的模块，比如f i f o ，在本设计中只需要用 到u a r t 的几个基本功能，使用专用芯片会造成资源浪费和成本提高，所以将 所需要的u a r t 功能集成到f p g a 内部从而简化了整个系统电路，提高了可 靠性、稳定性和灵括性。本系统中u a r t 的作用是将并行的数据转变为串行数 据以1 0 k h z 的波特率发送给上位机。 u a r t 的基本特点是：在信号线上有2 种状态，可分别用逻辑l ( 高电平) 和逻 辑0 ( 低电平) 来区分。在发送器空闲时，数据线应保持在逻辑高电平状态。发送 器是通过发送起始位而开始一个字符传送，起始位使数据线处于逻辑0 状态，提 示接收罂数据传输即将开始。数据位一般为8 位一个字节的数据( 也有6 位、7 位的情况) ，低位( l s a ) 在前，高位( m s b ) 在后。校验位一般用来判断接收的数据 位有无错误，一般是奇偶校验。停止位在最后，用以标志一个字符传送的结束， 它对应于逻辑1 状态。u a r t 数据帧格式同如表4 2 所示。 s t a r td od ld 2d 3酣d 5d 6d 7p s t o p 起始位 数据位 奇偶校验位停止位 u a r t 的设计包括发送模块，接收模块，波特率发生器。串口使用标准的 r s 2 3 2 ，波特率为1 0 k h z 数据由1 为起始位，8 位数据，1 位奇偶校验和1 位 停止位组成。系统的框图如图4 - 9 所示。( 系统中并未设计总线控制器，而是将 第四章r f i d 系统设计 上位机的输入和输出分开表示，以便清楚的表示结果。) ! _ i _ 一 ；卜_ 一 发送模块l j总线控制器o 一 l 广r 一i l 一i r 一r j 。1 。 p 霖器j止二二= ! ；i p c j 件 卜j _ - - 厂上：厂一 _ 一 接收模块 卜! 波特率发生器一 i一i一!。，j 1，j 图4 - 9u a r t 系统结构框图 下面分别论述u a r t 中几个模块的设计以及功能。 发送模块：发送模块主要是对从目标器件接收到的8 位并行数据进行并串转 换并发送。u a r t 串行发送器模块框图如图4 1 0 所示。 一d i n 一发送器控制和状态l t 髓一 - r 一 童! t b r l 一t s r _ 一s d o ， 1一1一 图4 - 1 0u a r t 串行发送器模块框图 从框图可以看出，串行发送器中包含有一个8 位t b r ( 发送保持寄存器) 和一 个8 位t s r ( 发送移位寄存器) 。复位时，引脚t k e 为高电平。当数据载人到t s r 之后，引脚t r e 变为低电平。发送完毕，t r e 变为高电平。当侦测到输入写使 能有效时，自动使能串行数据发送过程。首先传送1 位的起始位( 逻辑电平0 ) ， 同时t b r 中的数据自动地并行载人到t s r 中。然后，定长的数据位从t s r 中移 出，接着是校验位。最后，产生停止位( 逻辑电平1 ) ，标志着一帧的结束。串行 数据帧将以内部时钟频率的1 1 6 传送。如果t b r 中内容不空，当一个串行数 据帧传送结束后，紧接着发送下一个数据帧。这种自动的流程使得数据帧以背靠 背的方式发送，提高了数据传输的带宽。当没有数据发送时，s d o 引脚保持高 电平【2 6 1 。图4 1 l 是接收模块状态图。 第四章r f i d 系统设计 t s r = t b r t 眭= o 毋一竺、 1 d l e i 萝 1 。 奄 譬j j 、一js t o p t r e = 1 奇偶校 验位 图4 - 1 1u a r t 发送器状态转移图 最后1 位数 据未移入 接收模块：接收模块的作用是接收从串行输入端口发送的异步数据，进行串 并转换并发送。u a r t 串行接收器模块框图如图4 1 2 所示。 一d o u t 一 接收器控制和状态一_ r e a d y 一 图4 - 1 2u a r t 串行接收器模块框图 接收器包含一个8 位r b r 和r s r 。r b r 的状态可以通过引脚r e a d y 来表 示。当r b r 中的数据有效时，r e a d y 变为高电平，表明可以取回数据。r x d 在没有数据发送时，保持高电平，当数据起始位到来时，变为低电平。当系统侦 测到r x d 为8 个周期低电平时，表示侦测倒起始位，计1 6 个时钟周期，便开始 接收数据，当8 位数据移位输入r s r 结束，接收校验位，并对r s r 中的数据进 行奇偶校验，如果正确，则接收停止位“1 ，否则报错，如果接收到停止位将 r s r 中数据移入r b r ，并将r e a d y 信号置位，否则报错 2 6 】。图4 1 3 是接收模 块状态图。 3 0 第四章r f d 系统设计 r x 肛1 r e a d y - 1 s t o p i ：e d y = 1 1 6 姆铀 奇偶校 验 图4 - 1 3 u a r t 接收器状态转移图 m n ，黧默 波特率发生器：u a r t 的接收和发送是按照相同的波特率进行收发的。波 特率发生器就是分频器，它产生的时钟频率不是波特率时钟频率，而是波特 率时钟频率的1 6 倍，目的是为在接收时进行精确地采样，以提出异步的串 行数据。根据给定的晶振时钟和要求的波特率算出渡特率分频数。u a r t 模 块的仿真如图4 1 4 所示。 4 2 7 曼彻斯特编码模块 图4 - t 4 u a r t 仿真波形 i s o i e c l 8 0 0 0 - 6 t y p e b 协议规定基带数据发送采用曼彻斯特编码格式。曼 彻斯特码是对每个二进制代码分别利用两个具有2 个不同相位的二进制新码去 取代的码i ” ，编码规则如图4 1 5 所示。 第四章r f i d 系统设计 逻辑0 曼彻斯特编码叭逻辑l 曼彻斯特编码1 0 崮4 1 5 曼彻斯特编玛规则 例如n i l e 码为1 0 1 1 0 0 1 ，经过编码后变为1 0 0 1 1 0 1 0 0 1 0 1 1 0 。如图4 一1 6 所 广 广一l 广 撤事洽号 ：1 ：o1 1 11 oio ：1 nlmnlr 1 冉 罔4 - 1 6 曼彻斯特码编码翻吓 这种编码既能提供足够的定时分量，义无直流飘移，编码过程简单。同时 便于进行r f i d 系统的二进制树反碰掩算法的实现。编码模块的仿真如图4 - j7 所示。 罔4 17 曼彻斯特编码j _ 荽块竹n 渡形 第四章r f i d 系统设计 4 2 8 系统的仿真与综合 上面已经对系统的主要模块进行了设计，并验证正确，本节将对完整的系统 进行仿真和综合。 令标签识别码为8 位2 进制码，1 0 0 1 叭1 1 加上c r c 校验为2 4 位二进制码， 1 0 0 1 们i 】1 1 1 10 0 1 10 1 0 11 1 1 0 ，转变为f m 0 码为1 1 0 10 1 0 01 叭10 0 1 10 0 1 10 0 1 1 0 1 0 10 0 1 1 们0 01 0 1 10 0 1 10 0 1 0 。加上帧头后输入为0 0 0 00 1 0 10 1 0 10 10 l0 1 0 1 0 0 0 1 】0 1 l0 0 0 11 1 0 10 1 0 01 0 1 10 0 1 10 0 1 10 0 1 10 1 0 10 0 1 10 1 0 01 0 1 l0 0 1 10 0 1 0 ， 串行输入，频率为4 0 k h z 。仿真波形如图4 - 18 所示。 图4 - 18r e i d 系统仿真波形 令输入时钟频率为8 0 k h z ，分频产生4 0 k h z 和1 0 k h z ，( 一般f p g a 的晶振 频率为1 0 0 m i t z 或5 0 m h z ，但为了便于观察，所以仿真时采用较小的输入时钟， 这样还可以采用较小的分频数) 。当输八信号到来后，经过一段时间处理后，t r e 信号由高电平跳变“0 ”，标志着开始输出，由波形可以看到在下个周期开始串行 输出到上位机，输出的频率为输入周期的1 6 倍，输出数据为开始位“0 ”开始， 然后是8 位标签识别码】0 0 1 0 1 1 1 ，由低位到高位串行输出，然后是奇偶校验位 “1 ”，晟后是结束位i ，同时”e 跳变到高电平标志着输出结束。由波形看到， 该系统能正确的识别出输入的标签识别码。同时系统周期的发送请求信号，频率 为1 0 k h z 。表4 3 给出了r f i d 系统的综台报告。 l o g i cu t i l i z a t i o n u s e d n u m b e r o fs l i c e s2 4 3 n u m b e r o f f l i p f l o p s 3 2 1 n u m b e r o f 4 i n p u t l u t 4 2 4 n u m b 目o f e d i o b s5 6 第五章反碰撞算法的研究与硬件设计 第五章反碰撞算法的研究与硬件设计 在射频识别系统工作时，可能会有一个以上的标签同时处于阅读器的作用范 围内，在阅读器的作用范围内有多个标签的数据同时传输给阅读器的这种通信方 式叫做多路存取。每个通信通路拥有规定的通路容量。这种通路容量是由这个通 信通路的最大数据率，以及供它使用的时间片来确定的。分配给每个标签的通论 容量必须满足：当多个标签同时把数据传输给一个单独的阅读器时不能出现干 扰，也就是我们所说的碰撞【4 】。在无线电技术中，对于多路存取的情况，有很多 方法把不同用户的信号区分开，基本上常用的四种方法：空分多路( s d m a ) ， 频分多路( f d m a ) ，时分多路( t d m a ) ，码分多路( c d m a ) 。而对于r f i d 系 统，只存在着很短的动作周期，这种周期可能会被比较长的静止间歇中断。在阅 读器和应答器之间的传输通路上具有很高的突发系数。因此一般r f i d 系统采用 数据包存取方法：按实际所需要的那样来分配通路容量的时间。这就要求在通信 过程中，必须可靠的防止由于标签的数据在阅读器的接收器中互相冲突从而不能 读出。 r f i d 系统的防冲突法一般采用时分多路法。时分多路( t d m a t i m ed o m a i n m u l t i p l e a c c e s s ) 是把整个可供使用的通路容量按时间分配各多个用户的技术。 t d m 首先在数字移动无线电系统范围内推广使用。对射频识别系统来说，t d m a 构成了防冲突法最大量的一族【4 】。这种方法又可分为应答器控制( 应答器驱动) 和阅读器控制( 询问驱动) 。 应答器控制法的工作是非同步的，因为这里对阅读器的数据传输没有控制。 应答器控制法很慢而且也不灵活，但结构简单，常见的a l o h a 法就是一种 应答器控制法。 阅读器控制法是以阅读器作为主控制器，这种方法可以同步进行观察，因为 这里所有的标签同时由阅读器进行和检查控制，通过一种规定的算法，在阅 读器的作用范围内首先选择较大的标签组中的一个标签，然后在选择的标签 和阅读器之间进行通信。当通信结束后，为了选择另外一个标签，应该解除 原来的通信关系，因为在同一时间内总是只建立起一个通信关系。阅读器控 制的方法可以再划分为轮询法和二进制搜索算法。所有这些方法都以一个独 特的序列号来识别标签为基础。轮询法需要一个含有所有可能用到的序列号 的清单。对所有的序列号依次被阅读器询问，直至某个有相同序列号的标签 响应时为止。然而，这个过程依赖于标签的数目，可能会很慢。因此只适用 第五章反碰撞算法的研究与硬件设计 于作用区中标签数目比较少的情况。二进制搜索算法是最灵活也是最广泛推 广使用的方法。对这种方法来说，为了从一组标签中选择一个阅读器发出 一个请求命令有意识的将标签序列号传输时的数据冲突引导到阅读器上，在 二进制搜索算法的视线中起决定作用的是：阅读器所使用的合适的信号编码 必须能够确定冲突的准确比特位。 下面将相对几个常用反碰撞算法进行研究分析。 5 1 纯a l o h a 算法 a l o h a 法在多路存取方法中是最简单的，只要有一个数据包提供使用，这 个数据包就立即发送给阅读器。这种方法是应答器控制的。它只适用于只读应菩 器。通常，这类标签只有一些数据传输给阅读器，并且是在个周期循环中将这 些数据发送给阅读器。数据传输时间只是循环周期的- - d , 部分，所以在传输之间 产生相当大的间歇，此外，各个标签的循环周期的差别可以忽略不计。所咀，可 咀通过对两个标签在不同时间段上设置他们的数据，使数据不冲突h 。数据交换 的时间过程如图5 - i 所示。 学雀 i 图5 - 1a l o h a 算法示意图 如上图所示，假设某一标签在t 时刻出现，其持续时间为t ，那么在( t - t h t + t ) 的区域内不能有其它的标签传输信息，否则将发生碰撞，也就是为了避免碰撞在 毗t 为中心的2 t 区间内不能有其它标签出现，因此a l o h a 算法中冲突周期是 2 t 。 下面对系统的性能进行分析，数据包交换量