（微电子学与固体电子学专业论文）射频识别系统（rfid）防冲突算法研究与vlsi实现.pdf

堕堑鎏三些盔：三兰鎏圭耋堡篓兰 abstract r a d i o f r e q u e n c y i d e n t i f i c a t i o n ( r f t d ) s y s t e m sh a v ee m e r g e da sab e t t e rs o l u t i o nf o r automatic i d e n t i f i c a t i o n b e c a u s go fi t se x c e l l e n t performance,it h a sb e e n c o n s i d e r e da st h er 觚e c t substitutet ow a d i t i o u a lo b j e c ti d e n t i f i c a t i o nt e c h n i q u e s s u c ha sb a rc o d e sa n dv i s u a lr e c o g n i t i o n a l t h o u g h t h e existing s t a n d a r d sf o rr f i dh a v en o t b e e nu n i f i e da n dt h ec o s t sa r es t i l lh i 曲，r f i d w i l l c h a n g eo l l f l i v e si nt h e v e r yr e c e n tf u t u r e r f d 协g i s a p a r a d i g m w h e r e e v e r y p r o d u c t h a sa u n i q u e t a g a t t a c h e d t o i l t a g r e a d e r i s u s e dt o r e a dt h e informations t o r e di nt h et a g s ( t h e i ri d e n t i f i c a t i o n s ，i d s ) ，o rt 0w r i t ed a t ai n t o t h e m o n eb i gp m b l e mi st oi d e n t i f ym u l t i p l eo b j e c t sw i t h i nt h er a n g eo f a t a gl k l e r i f a l lt h e t a g ss e n dt h e i ri d sa tt h es a m et i m e ，c o l l i s i o nh a p p e n sa tm e 协gr e a d e ra n dn ot a gc a nb e i d e n t i f i e d , w h i c h l e a d s t o t h er e w a n s m i s s i o n o f t a g i d s i t r e s u l t s i n w a s t a g e o f b a n d w i d t h a n d a l li n c r e a s ei nt h et o t a ld d a yi ni d e n t i f y i n ga l lt h eo b j e c t s s oa l la p p r o p r i a t em e t h o di sn e e d e d t 0r e s o l v et h i sk i n do f m u l t i - a e e c s sc o m m u n i c a t i o ni nr f i ds y s t e m sa n dt og e tt h et a g sb e i n g q u i c k l ya n de f f e c t i v e l yi d e n t i f i e d 1 h et h e s i si sm a i n l yf o c u s e do nt h ea n t i - c o l l i s i o na l g o r i t h m sf o rr f i ds y s t e m s t h e ya l e c o n s i d e r e d t o b e c o m p a t i b l e w i t h c o n s t r a i n t s o n t h e d e s i g n o f t a g s ，s u c h a s l a c k o f b a t t e r y , l o w c o s t , l e s sc o m p l e x i t y , l o wm e m o r y , m i n i m u mc o m p u t a t i o np o w e r , e r e t h ep a p e rs t u d i e dt h e e x i s t i n ga l g o r i t h m s ，d i s c u s s e dt h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s ，a n da n a l y z e dt h e i r c o m p l e x i t yr e q u i r e m e n tf o r t h ec i r c u i td e s i g n t h et w oo p t i m a lo b j e c t i v e sf o rr f l da n t i - c o u i s i o na l g o r i t h m sa l el i s t e db e l o w ： 1 1 h et i m et a k e nf o ri d e n t i f i c a t i o no f a l lt h et a g ss h o u l db ea ss h o r ta sp o s s i b l e i e t h ei t e m t i o n sf o r s e a r c hm u s tb em i n i m z e d ； 2 n l eh i t st r a n s f e r r e df r o mt a g si nt h ea n t i - c o l l i s i o np r o o c e s ss h o u l db ea sf e wa s p o s s i b l e t oo v e l c o l n et h ed e f i c i e n c yo fe x i s t i n g a p p r o a c h e s ，t h i s t h e s i s p r o p o s e dan e w d e t e r m i n i s t i ca l g o r i t h m , b c d s0 3 r e a d t h - f i r s tc o l l i s i o n - b i t - s p l i td y n a m i cs e a r c ha l g o r i t h m ) a f t e rh a v i n ge x p l a i n e di ti nas i m p l ew a y , am o d e lo fa n t i - c o l l i s i o nm e c h a n i s mu s i n g m a t l a bi sp r o p o s e da n dal a r g en u m b e ro fe x p e r i m e n 俗a l ef i n i s h e df o rp e r f o r m a n c e c o m p a r i s o nw i t ht h eo t h e r s t h er e s u l t ss h o wt h a tt h ea l g o r i t h md e c r e a s e sa b o m7 0 o f s e a r c ht i m e ；a n dt h eb i t st r a n s f e r r e df r o mt a g si s5 0 l e s sw h e nt h ef i a n ea d d i t i o n a l i i 晴尔滨 二业大学_ l 学硕士学位论文 1 1 课题来源 第1 章绪论 本课题来源于哈尔滨工业大学深圳研究生院片上系统研究中心的自行研发项h 项目名称是：射频识别系统c r f i d ) 。 1 2 课题研究的目的及意义 几年前，条型码在识别系统领域引起了场革命并得到，广泛应用。今天，这种 条型识别技术在越来越多的情况下已经不再能够满足人们的需求。条型码价格低廉， 但它的不足之处很多，如读取速度暖、存储能力小、工作距离近、穿透| 生弱、适应性 不强以及不能改写等等。 一种技术上最佳的解决方案足将数据存储在一块硅芯片里。在臼常生活中，具有 触点排的i c 卡( 电话i c 卡、银行卡等) 是电子数据载体的最普通的结构。然而，对i c # 来说，在许多情况下，机械触点的接通是才i 可靠的，数据载体与一个所属的读写器 之间的数据进行非接触式传输将灵活得多，载体工作时所需要的能量可以通过读写器 非接触地传输来获取。 非接触识别已经逐步发展成为个独立的跨学科的专业领域。这个专业领域与任 何传统学科都不相同，它将大量来自完全不同专业领域的技术结合到一起：电磁学、 半导体技术、数据保护和密码学、电信、制造技术和许多专业应用领域。 根据使用的能量和数据传输的方式，我们也把非接触的识别系统称作射频识别系 统，r f i d 删i of r e q u e l l c yi d 训f i c a t i o n ) 。作为条形码的下一代完美替代产品，r f d 技术拥有众多条码技术所不具备的优势：防水、防磁、耐高温、使用寿命长、穿透性 强、读取速度快、距离远、存储数据能力大、数据可加密、存储信息可以更改等等。 r f t d 最引人注目的特生是能提供更细致、更精确的产品供货信息，并能实现货物补 充流程的自动化。 般来说，射频识别系统由电子标签、读写器和信息网络系统i 部分组成。电_ f 二 标签是产品全球唯一电子代码( 也称为产品的电子序列号) 的载体，附着于可跟踪的 物品上，在全球流通。读写器( 也称为阅读器) 与信息网络系统相连，是读取标签中 的产品序列号并将其输入信息网络系统获取该产品对应信息的工具。信息网络系统由 童尘鎏三些查茎三兰璧圭耋堡堡兰 今年，g a 咖e r 选出2 0 0 5 年十人热门技术，其中射频识别标签( r f i d 魄s ) 榜上有 名。g a 咖e r 这样描述r f i d ：“到2 0 1 2 年，射频识别( r f l d ) 和类似的无线射频芯片会 有所变化，从供应链管理技术演变成能够带给消费者附加价值的应用，例如找寻对象 所在位置和状况回报等。可以预期的足，r f l d 电予标签的成本会刚氐到使得此项技 术的实施变得理所当然的地步。使用r f i d ，可以追踪产品的生命周期，提供更多、 更深入的过程资料记录。电子标签可以嵌入到不耐久存的产品装运设施中，以便存货 物从仓库运往商店上架的途中，监视温度、震动、腐坏和其他因素的变化。” 日前，r f 已成为i t 业界研究的热点，被视为i t 业的下一个“金矿”。各大软 硬件j 商，包括i b m 、m 0 t o r o l a 、p h i i i p s 、1 1 、m i 咖f 【、o m c l e 、s u n 、b e a 、s a p 等在内的几百家跨国企业都对r f d 技术及其应用表现出了浓厚的兴趣，相继投入大 景研发经费，推出了各自的软件或硬件产品及系统应用解决方案。在应用领域，以 w a l m a n 、u p s 、g n l e 吮等为代表的大批企业已经开始准备采用r f d 技术对业务系 统进行改造，以提高企业的工作效率并为客户提供各种增值服务。 1 3 国内外相关技术发展现状 1 3 1 国外的r f 标准之争 由于目前还没有正式应用的r f _ 【d 产品国际标准( 包括在各个频段) ，因此，各 个厂家推出的r f l d 产品互不兼容，造成了r f i d 产品在不同市场和麻用上的混乱和 孤立。以r f d 标签与阅读器之间进行无线通信的频段为例，其频段达5 种之多，分 别是13 5 k h z 、13 5 6 m h z 、8 6 0 曲6 0 删h f ) 、2 4 5 g h z 以及5 8 g h 眨。每个频段都 有其特色有其缺陷。前两者技术最成熟，使用最广，但通信速度过慢，传输距离也不 够长；后二者频段高，通信距离远，耗电量也大。 标准不统一已成为制约r f i d 发展的重要因素之。由于每个r f l d 标签中都有 一个唯一的序列号( i d ) ，如果它的数据格式有很多种类耳互不兼容，那么使用不同的 标准这个问题将涉及到各个国家自身的利益和安全。目前的现状是美国e p ca o b a l 和日本“泛亚中心”两大标准组织互不兼容，一个是总部设在美国麻省理学院 的a u 的mc e n t e r ，另一个是日本的i j b i q u i 0 0 i 膳dq 删h d ) 。前者的领导组织是美 国的e p cg 1 0 b a l 协会，提出了e p c 电子产品编码标准。旗下有沃尔玛集团、英国 哈尔滨工业大学工学硕士学位论文 本地网络和全球互联网组成，是实现信息管理、信息流通的功能模块。信息网络系统 可以在全球互联网的基础上，通过管理软件系统以及对象命名解析服务( 0 n s ) 和实体 标记语言( p m l ) 来实现全球“实物互联”。 r f l ：d 技术的应用前景非常之广。泛： 畜牧业在牲畜的耳朵罩放置r f i d 芯片，可以对牲畜进行专门的管理。如多 奶牛或少奶牛，该牲畜喜欢吃什么饲料，食量大小，身体状况等。 大会的门镜系统一大会门票、公园门票的识别。这些既可防伪，又可大大提高 安全性。 洗衣的标签一由于r f i d 的防水、耐高温等特点，它和条码标签不一样，刈保 持洗涤过程中，标签完好无损。 汽车防盗在汽车钥匙里安装rr f d 芯片，使得该钥匙无法被仿造重配，从 而提高了汽车防盗的安全陛。 图书标签采用r f d 技术，可以解决图书放错架子时很难寻找的麻烦，通过 对图书架上图书的扫描，从获取的信息可以对次序不对的书籍报警。r f i d 技术用于 图书管理还可实现自动送书和还书等。 服装专卖店的库存管理r f d 信息在配送中心、仓库和销售店间互相传递， 可以获得哪些服装受顾客欢迎的信息，以便实施调运及进货。 各类商品的防伪如扣日j 机墨盒，烟酒的防伪防假，药品除防伪防假外，还可 实旌库存管理，检查过期或缺失药品等。 码头集装箱管理、托盘管理、机场行李管理、生产流水线管理、特流线配送管理 等。 r f d 可以用来追踪和管理几乎所有物理对象，越来越多零售商和制造商都在关 心和支持这项技术的发展j _ 了应用。然而，由于目前标准不统一、成本还很高等原因， 该技术在市场上尚未得到大规模的应用。为了获得期望的效果，关于r f i d 技术的进 一步研究和各种标准的统一是当前的焦点【2 】。 2 0 0 2 年底，计算机世界i 二一篇名为“展望2 0 0 3 年，网络等十人前沿技术提 前预览”的i t 贺岁文章将r f l d 技术列为第五大i t 前沿技术。 2 0 0 3 年3 月，专业技术市场咨询公司g a m l e r 在“s 娜p o s i u r nn x p o2 0 0 3 ”上预 测，r f i d t a 萨) 技术属于最近2 5 年( 2 0 0 5 2 0 0 8 年) 将逐渐开始大规模应用的 技术。根据虹犯顾问集团的预测，到2 0 0 8 年r f i d 仅在全球供应链领域的市场需求 就将达到4 0 亿美元。 2 0 0 4 年初，美国有线新闻网公布了即将于2 0 0 4 年出现并对人类生活产生巨大影 响的1 0 项技术，其中，r f i d 名列第三。 童尘鎏三些查茎三兰璧圭耋堡堡兰 今年，g a r m e r 选出2 0 0 5 年十人热门技术，其中射频识别标签( r f i dt a g s ) 榜上有 名。g a r t n e r 这样描述r f i d ：“到2 0 1 2 年，射频识别( r f l d ) 和类似的无线射频芯片会 有所变化，从供应链管理技术演变成能够带给消费者附加价值的应用，例如找寻对象 所在位置和状况回报等。可以预期的足，r f i d 电予标签的成本会降低到使得此项技 术的实施变得理所当然的地步。使用r f i d ，可以追踪产品的生命周期，提供更多、 更深入的过程资料记录。电子标签可以嵌入到不耐久存的产品装运设施中，以便存货 物从仓库运往商店上架的途中，监视温度、震动、腐坏和其他因素的变化。” 日前，r f i d 已成为i t 业界研究的热点，被视为i t 业的下一个“金矿”。各大软 硬件j 商，包括i b m 、m o t o r o l a 、p h i l i p s 、t i 、m i c r o s o f t 、o r a c l e 、s u n 、b e a 、s a p 等在内的几百家跨国企业都对r f i d 技术及其应用表现出了浓厚的兴趣，相继投入大 景研发经费，推出了各自的软件或硬件产品及系统应用解决方案。在应用领域，以 w a l m a r t 、u p s 、g i l l e t t e 等为代表的大批企业已经开始准备采用r f i d 技术对业务系 统进行改造，以提高企业的工作效率并为客户提供各种增值服务。 1 3 国内外相关技术发展现状 1 3 1 国外的r f i d 标准之争 由于目前还没有正式应用的r f i d 产品国际标准( 包括在各个频段) ，因此，各 个厂家推出的r f l d 产品互不兼容，造成了r f i d 产品在不同市场和麻用上的混乱和 孤立。以r f i d 标签与阅读器之间进行无线通信的频段为例，其频段达5 种之多，分 别是13 5 k h z 、13 5 6 m h z 、8 6 0 9 6 0 m h z ( u h f ) 、2 a 5 g h z 以及5 8 g h z 。每个频段都 有其特色有其缺陷。前两者技术最成熟，使用最广，但通信速度过慢，传输距离也不 够长；后二者频段高，通信距离远，耗电量也大。 标准不统一已成为制约r f i d 发展的重要因素之。由于每个r f l d 标签中都有 一个唯一的序列号( i d ) ，如果它的数据格式有很多种类耳互不兼容，那么使用不同的 标准这个问题将涉及到各个国家自身的利益和安全。目前的现状是美国e p cg l o b a l 和日本“泛亚中心”两大标准组织互不兼容，一个是总部设在美国麻省理学院 的a u t o i dc e n t e r ，另一个是日本的u b i q u i t o u s1 dc e n t e r ( u r d ) 。前者的领导组织是美 国的e p cg l o b a l 协会，提出了e p c 电子产品编码标准。旗下有沃尔玛集团、英国 t e s c o 等1 0 0 多家欧美的零售流通念峨同时有i b m 、微软、飞利浦、a u t o 。i dl a b 等公司研究所提供技术支持；后者主要由日本厂商组成，有日本电子厂商、信息企业 和印刷公司等，总计达3 0 0 多家。该中心实际上就是日本有关电了标签的标准化组 哈尔滨工业大学工学硕士学位论文 织，提出了u i d 编码体系。 e t 本u i d 标准和欧美的e p c 标准在使用的无线频段、信息位数和应用领域等方 面有许多不同点。例如，日本的电子标签采用的频段为2 a 5 g h z 和1 3 5 6 m h z ，欧美 的e p c 标准采用u h f 频, 殴( 8 6 0 - - 9 6 0 m h z ) 。一本u i d 电子标签的信息位数为1 2 8 位，e p c 标准的位数为9 6 位；u i d 的电子标签标准可用于库存管理、信息发送和接 收以及产品和零部件的跟踪管理等，e p c 标准侧重于物流和库存管理。 除此之外，欧美阵营内部就e p c 标准的争夺从r f i d 标准制定机构e p cg l o b a l 诞生之日起，就一刻都没有停止过。2 0 0 4 年4 月，飞利浦、德州仪器等1 3 家厂商联 合向e p cg l o b a l 提出了新的r f i d 标准提案，至此仅e p c 标准就有三家提案在角 逐。提出不同提案的三家组织分别为r f i d 专业公司a l i e n 科技( q 提案) ，飞利浦和 德州仪器联盟( u n i f i e dg r o u p ) ，以及e m 、m a r r i e s 、a l m e l 及其他一些小型企业所组 成的联合体口盯f o n c et e a m ) 。由于三大提案都基于i s 0 1 8 0 0 0 6 a ，因而技术方面 存在着广泛的相似之处，不过它们之间的差异也足以改变整个r f 产、i k 链的格局。 1 3 2 国内r f i d 研究现状 中国是世界上最大的产品制造基地，当中国制造的产品走向世界的时候，在产品 上粘贴的r f i d 标签也必定要符合世界通用标准。囝内由于涉足r f i d 时间较晚，在 标准制定、技术储备和 、才培养等方面与国外存在较火的差距。 国外对r f i d 标准的利益之争已经进入了准白热化阶段，中国自己的r f i d 标准 制定过程必须加速，并应在国际标准制定中扮演重要角色。在技术标准策划制定的同 时，国内r f i d 的技术储备、研发和产业化工作也应咖】大力度，力争以较短的t 时问跻 身世界一流水平。 2 0 0 4 年2 月，中国国家标准化管理委员会宣布成立电子标签国家标准工作组， 负责起草、制定中国有关电子标签的国家标准。2 0 0 4 年4 月底，中国企业加入了 r f i d 的全球化标准组织e p cg l o b a l ，同期，e p cg l o b a lc h i n a 成立。与此吲时，日 本的r f l d 标准化组织t - e n g i n e 论坛与中国企业实华开电子商务有限公司合作成立了 基于日本u i d 标准技术的实验塞1 l i d 中国中，i i , 。 中国电子标签国家标准化工作组正在制定的中国r f d 标准，包括r f i d 技术本 身的标准( 如芯片、天线、频率等方面) ，以及r f i d 的各种应用标准，如在物流、 身份识别、交通收费等各领域的应用标准。如何让国家标准与未来的国际标准相互兼 容，让贴着r f i d 标签的中国产品顺利在世界范围中流通，是当前晕要而急需解决的 问题。特别是在中国，这个未来全球制造业的中心，其一举一动牵动了国际标准的未 哈尔傧上业大学工学硕上学位论文 织，提出了u i d 编码体系。 i _ l 本u 标准和欧美的e p c 标准在使用的无线频段、信息位数和应用领域等方 面有许多不同点。例如，日本的电子标签采用的频段为2 a s g h z 和1 3 5 6 m t - i z ，欧美 的e p c 标准采用u h f 频段( 8 6 睢9 印m l z ) 。h 本u 1 d 电子标签的信息位数为1 2 8 位，e p c 标准的位数为9 6 位；u i d 的电予标签标准可用于库存管理、信息发送和接 收以及产品和零部件的跟踪管理等，e p c 标准侧重丁物流和库存管理。 除此之乡h ，欧美阵营内部就e p c 标准的争夺从r f i d 标准制定机构e p cg l o b a l 诞生之日起，就一刻都没有停止过。2 0 0 4 年4 月，飞利浦、德州仪器等1 3 家厂商鞋 合向e p cg l o b a l 提出了新的r f i d 标准提案，至此仅e p c 标准就有三家提案在角 逐。提出不同提案的三家组织分别为r f i d 专业公司a e e n 科技( q 提案) ，e 利浦和 德州 义器联盟( u n i f i e dg r o u p ) ，以及e m 、m a c s 、a t m e l 及其他一些小型企业所组 成的联合制s 0 e r f o r m n n e et e a m ) 。由于三大提案都基于i s 0 18 0 0 0 , 6 a ，区i 而技术方面 存辅广泛的相似之处，不过它们之闻的葺异也足以改变整个r f l d 产业链的 局。 1 3 2 国内r f i d 研究现状 中国是世界上最大的产品制造基地，当中国制造的产品走向世界的时候，侄产品 上粘贴的r f i d 标签也必定要符合世界通用标准。国内由于涉足r f i d 时间较晚，在 标准制定、技术储备和人，d 培养等方面与国外存在较火的差距。 国外对r f i d 标准的利益之争已经毪久了准白热化阶段，中国自己的r f i d 标准 制定过程必须加速，并应在国际标准制定中扮演重要角色。在技术标准策划制定的同 时，国内r f i d 的技术储备、研发和产业化工作也应加大力度，力争以较短的时问跻 身世界流水甲。 2 0 0 4 年2 月，中国国家标准化管理委员会宣布成立电子标签国瓤, t e g t ：作组， 负责起草、制定中国有关电子标签的国家标准。2 0 0 4 年4 月底，中国企业加入了 r f i d 的全球化标准组织e p cg l o l 】a l ，同期，e p cg l o b a lc h i n a 成立。与此同时，日 本的r f i d 标准化组织t - e n g i n e 论坛与中国食业实华开电子商务有限公司台作成立了 基于日本u 标准技术的实验室一h d 中国中心。 中国电子标签国家标准化工作组正在制定的中国r f i d 初守隹，包括r f i d 技术本 身的标谁( 如芯片、天线、频率等方面) ，以发r f i d 的各种应用标准，如在物流、 身份识别、交通收费等各领域的应用标准。如何让国家标准与未来的国际标准相互激 容，让贴着r f i d 标签的中国产品顺利右世界范围中流通，是当日# 晕要而急需解决的 问题。特别是在中国，这个未来全球制造业的中心，其一举动牵动了国际标准的朱 问题。特别是在中国，这个未来全球制造业的中心，其一举一动牵动了国际标准的朱 哈尔演工业大学工学硕士学位论文 来走向。 为此，国际标准化管理委员会下达了电子标签国家标准的起草任务， j 前，电了 标签的国家系列标准包括： 标准i s 0 以e c l 5 6 9 3 部分 识别卡无触点的集成电路卡 项目编号2 0 0 3 0 1 7 5 一t _ 3 3 9 识另卡无触点的集成电路卡 项目编号2 0 0 3 0 1 7 6 p 3 3 9 识别卡无触点的集成电路卡 项目编号2 0 0 3 叭7 7 t _ 3 3 9 邻近式卡第l 部分：物理规范 邻近式膏第2 部分：空气接口和初始化 邻近式卡第3 部分：防冲突和传输协议 射频识别技术应用规范第l 部分：电子标签 项目编号2 0 0 3 0 4 4 4 t 4 4 3 射频识别技术应用规范第2 部分：读写器终端 以上关于r h d 标准与技术规范的内容摘自文献【3 】。 除了标准制定之外，影响r f i d 产业发展的另外一个重要因素就是对其技术的进 一步研究。当前，关于r f i d 技术的研究工作主要集中在频率选择、天线设计、防冲 突技术以及安全与隐私保护等方面。 1 4 防冲突技术 在r f i d 系统中，通常在读写器的可识别区域内会有多个电子标签待识别。如果 这些电子标签同时向读写器发送信息( 这种通信形式被称作多路存取) ，则这螳信号 在读写器端会产生干扰，严重时会导致错误识别，这种现象称为冲突或碰撩，见图 1 1 。 长久以来，在无线电技术中的多路存取问题是众所周知的。为了将不同的用户信 号互相分开，使它们无冲突地完成通信，基本上有四种不同的方法：空分多址、频分 多址、时分多址以及码分多址。使用这些方法，将不间断的数据流传输给用户，一次 分配的通路容量应保持足够长的时间，如同通信所需要的那样。 r f d 系统巾的多路存取技术的实现对电子标签和读写器提出了一些要求，必须 可靠地防止由于电子标签的数据( 包) 在读写器的接收端互相冲突而不能读出，且读 取的时间越短越好。在r f i d 系统中的多路存取技术被称作防冲突法，也叫反碰撺 法。 哈尔滨工业大学1 学硕士学位论文 图1 - 1r f d 系统中的多路存取与冲突 1 1 川邱1 e a o c e s s a n d 0 0 u k 油j i l r 皿咖 一些已经非常成熟的无线通信多路存取技术并不能直接应用到r f 【d 系统中( 如 i e e e 8 0 2 1 1 ) ，这是由被动标签的无电池、低成本、内存小、功耗低、设计复杂度 低、彼此之问不能通信等要求决定的。 因此，人们开始研究针对r f i d 这种应用的多路存取机制，提出了一些防冲突算 法。 1 5 主要研究内容及论文结构 ( 1 ) 本文在全面研究已有的两大类防冲突算法基础上，讨论了它们的优缺点， 并从硬件实现角度分析了它们对电子标签设计复杂度的要求。 f 2 1 提出了一种新的防冲突算法，称为基于广度优先的冲突位分解动态搜索算 法。使用m a l l a b 对采用该算法的防冲突机制建模，完成了大量实验。通过实验结 果与已有算法进行_ 性能比较。 f 3 ) 最后，本文对采用该算法的防冲突模块完成了r t l 级设计，功能仿真正确 后进行了电路综合。在时钟频率为1 0 0 m k 、电压1 g vr ，面积为o 0 3 6 m i n l ，功耗 1 5 9 m w 。 论文结构安排如下： 第一章是绪论。 第二章对已有的两大类防冲突算法进行了综述，讨论分析了它们各自的优缺点。 第三章在对确定洼防冲突算法总结的基础卜，提出了一种新的算法。通过实验与 之前算法进行了性能比较。 第四章对本文提出的新算法硬件设计实现。 最后是论文的结论。 哈尔滨工业大学工学硕士学位论文 第2 章r f i d 防冲突算法研究 2 1r f i d 防冲突法 r f i d 系统的工作频牢主要有1 3 5 k h z 、1 3 5 6 m h z 、8 6 0 - - 0 6 0 m h z 、2 4 5 g h z 、 5 8 g h z 等多个频段。不同的国家和地区对频率分配和最大发射功率的规定是不同 的，在某些地区，某些频段的r f i d 产品可能被禁止使用。在这赌频段中，以 1 3 5 k h z 和1 3 5 6 m h z 频段的产品最为成熟，处于8 6 0 - - - 9 6 ( 0 内的u h f 频段的产 品因为工作距离远且最可能成为全球通用的频段而最受重视、发展最快。 r f i d 标签可分为有源和无源两类，有源标签接有电源或者内置电池，可以主动 与读写器通信，所以也称为主动标签；无源标签没有自己的能量来源，完全靠读写器 发送来的电磁波能量实现其t 作，也称为被动标签。无源标签是最简便、最理想的方 式。 由于每个电子标签含有可被识别的唯一信息( 序列号) ，如果只有一个电子标签 位于读写器的可读范围内，这将不需要其他的命令形式就可以直接在读写器和标签之 间建立通信。而如果有多个电子标签同时位于个读写器的可读范围内，则电子标签 的应答信号( 其序列号) 在读写器处接收到的某些位就会互相干扰形成冲突，即读写 器无法获知究竟什么序列号的标签处于作用范围内。为了防止这些冲突的产生， r f l d 系统中需要设置一定的相关协议来解决冲突问题，这种协议也叫做防冲突法。 多路存取的防冲突方法有四种基本不同的方法：空分多f f h ( s d m a ) 法、频分多路 f f m a ) 法、时分多路f r d m a ) 法和码分多路( c d m a ) 法。 由于r f i d 系统的特点，r f i d 的防冲突方法主要采用时分多址访问m a l 方 式。这是因为考虑到了电子标签的低功耗、低存储能力、低价格、尽量少的计算能力 等要求，以至于电子标签的内部电路及其天线部分不可能做成适用s d m a 、f d m a 或c d m a 那么复杂功能的设计。 实际使用过程中，鉴于多个电子标签将工作在同一频率，多个读写器之问工作 范雨重叠将造成冲突。文献【6 】提出了种叫做“c o l o r w a v e ”的算法以解决多读写器 发送请求时造成的冲突问题，给各个读写器分配“颜色”，不同的颜色对应不同的有 效工作时隙，其思想也是t d m a 。 当多个同一工作频率的电了标签处于同一个读写器作用范围内时，在没有采取 多址访问控制机制情况f ，信息传输过程将产生冲突，导致信息读取失败。根据电子 哈尔滨工业大学工学硕士学位论史 标签工作频段的不同，人们提出了不同的防冲突算法。 需要考虑到的是，之前的许多解决多路存取冲突问题的成熟方法由于r f d 系统 的各种限制不能被直接搬来使用。这些限制可以归结为以下： ( 1 ) 无源标签没有内置电源，需要读写器在对其发送请求或命令时发送的电磁 波来产生标签的应答能最，因此标签功耗要低； ( 2 ) 读写器作用范围内的标签数无法预知； ( 3 ) 标签问不能彼此通信，所有关于防冲突的解决方法需要在读写器端完成； ( 4 ) 实际应用中电子标签有限的内存与计算能力要求算法在标签端设计不能太 复杂。 日前，在高频廿哟频段，标签的防冲突算法般采用a l o h a 相关协议。使用 a l o h a 协议的标签，通过选择经过一个随机时间向读写器传送信息的方法，来避免 冲突，绝大多数高频读写器能同时扫描几十个电子标签。在超高频r 【】王 f 1 频段，现在 的主要研究趋向是采用树分义搜索算法来防冲突。 目前所有面向r h d 系统应用的) m a 方式的防冲突算法的研究可以被归结为 两大类：一类是非确定性( 或称概率性) 的防冲突算法，另一类是确定性的防冲突算 法。 此外，对于多路存取的防冲突方式来说，性能评估是贯彻始终的。对于r f i d 的 特殊应用，识别所有标签的总时间及能量消耗更是我们考虑的重点。在此列出期望的 r f d 系统防冲突算法要达到的性能： ( 1 ) 识别总时间越短越好。一个可量化的标准就是算法的搜索次数越少越好： ( 2 ) 识别过程标签功耗越少越好。这是无源标签想要广泛应用的必然要求。具 体来说，在防冲突过程中标签与读写器之间的应答次数及每次信息量越少越好； ( 3 ) 可靠性和完整性。读写器应该可以对作用范围内的所有标签可靠地、完全 地完成识别； 本章针对解决被动无源标签间的冲突，即一个读写器来识别阅读作用范围内未知 个数的标签的问题，对目前已有的这两大类防冲突算法( 都属于t d m a 方式) 进行 r 深入的研究及分析，并从硬件实现的角度分析了它们对电子标签设计复杂度的要 求。 2 2 非确定性的防冲突算法 概括来说，非确定生类的防冲突算法是在a l o h a 法基础上的研究与改进。这 类算法要求读写器作用范围内的电子标签依据自己的序列号随机产生应答时间，到达 哈尔滨上业大学上学硕士学位论义 时读写器时如果有冲突，则电子标签要等到下一轮时间段到来时再重新产生其响应时 间。在经过一些时间8 l 2 后非确定性的防冲突算法可以以一定的概率完成对作用范围 内的一定数量的标签的识别。i s 0 1 5 6 9 3 标准就采用了这类方法。电子标签发 h 数据 后就可置于临时的睡眠状态，过上一段时间后，再被唤醒。也就是说读写器发出一个 时隙信号，使电子标签依据自己的序列号随机产牛个延时后开始应答，应答后的电 子标签将自动进入休眠状态。目前已有的产品( 如1 3 5 6 m h z 的0 8 0 m c m o s 工艺的 r f i d i i ”) 采用的就是这类防冲突算法。 2 2 1a l o h a 法 a l o h a 法是2 0 世纪7 0 年代早期由夏威夷大学开发的a l o h a 协议种无 线电通信网络，用于将数据传输到夏威夷一发展起来的多路存取法。 最初的a l o h a 系统被设计用来在使用分组无线电系统的孤立节点之间建立通 信。术语分组( 或称为帧) 指的是在一次传输中的信息广播。终端连接着一个无线电 通道，后者轮流将终端传来的信息转播给一个称为m c n e h u n e 的中枢站点。站点使用 相同的频率广招种贞，因此，媒体( 天空) 实际上被共享。以相同的频率同时广播两个 不同帧的任何尝试都将使双方的信号遭到破坏，结果是没有一个传输能够获得成功。 a l o h a 协议( 也称作纯a l o h a 法) 的工作原理非常简单。基本上，它允许站 点在任何时刻进行广播，期f 果两个信号发生碰撞，那也没关系，各站点只需等待一段 随机时间后重试。 冲突的检测也相当容易。m e n e h u n e 在接收到帧时发送一个确认，它使用一个不 同的频率以免干扰进入的信号。如果一个站点收到确认，它将认为它的帧已经传送成 功。否则，它假定发生了一次冲突，于是等待重传。由于每个站点等待的时间是随机 的，所以两个或两个以上站点等待相等时间的机会很小，从而也就阿氐了发生第- 2 次 冲突的几率。如果真的发生第二次冲突( 很可能是和另一个站点) ，站点还是应用相 同的规则：等待随机时间以后重传。 这种睛况卜，不仅是在两个站点同时发送时会发生冲突，两个传输帧即使只有一 点点重叠也会发生冲突。无论是整删! a 都被破坏 ，还是只损坏了帧的- - + 部分，结 果都是样的，数据会被丢弃，常规的做法是重传整1 呻贞。 对于r f i d 系统中的应用，只要有一个数据包提供使用，这个数据包就立即从电 子标签发送至喇；写器去。因此，这种处理本身与电子标签控制的、随机的t d m a 法 有关。 i 蜊, t y , e n 用于只读电子标签中。这类电子标签通常只有一一些数据( q - 列号) 传 哈尔滨上业大学工学硕士学位论文 输给读写器，并且是在一个周期性的循环中将这些数据发送给读写器的，数据传输时 间只是重复时间的一部分，以致在传输之间产生相当长的间隔。各个电子标签的重复 时问之间的差别是微不足道的，所以存在着一定的概率，两个电子标签阅以在不同的 时间段上设置它们的数据，使数据包不相互碰撞。 南表 1 ( 摘自文献 1 ) 的实验结果可见，采用a l o h a 法的读写器要保证 9 9 9 的可靠眭辩识8 个电子标签需要2 7 0 秒，并且这个时间将随着标签数的增多而 迅速增加。 表2 1 读出作用范围内所有电子标签平均所需时间 嘞l e2 _ 1a v e r a g e 幽咖i d 酬p8 l l t | i e 切g s 访f 蒯e r 勺胁甜o m l r a n g e 读写器作用范围内的电子 平均时问9 9 的可靠性9 9 孵6 的可靠性 标签数量 2 个标签 1 5 0 f t l s3 5 0 i n s5 0 0 m s 3 个标签 2 5 0 m s 5 5 0 m s8 0 0 m s 4 个标签 3 伽l n 】s7 5 0 m s1 ( ) 0 s 5 个标箍 4 0 0 m s9 0 0 m s1 2 5 s 6 个标签5 伽e n s1 2 0 s1 加s 7 个标签 6 5 0 m s1 5 0 s2 0 d s 8 个标签8 0 0 m s1 8 0 s2 ，7 0 s 2 _ 2 2 时隙a i o h a 法 a l o h a 法非常简单，应用于r f l d 系统对标签设计复杂度要求也很低，但其实 际工作性能太差，并不能被r f i d 系统所采用。 让我们深入分析一下冲突发生的条件。如前所述，只要两个传输的任何部分重替 在一起，就会发生冲突。假设一次传输所需要的时间为t ，并且有两个站点要发送 帧，则两个站点成功地完成传输总共需要的时间是2 t 。 接下来考虑任意一个长度为2 t 的时问段。除非个站点在时间段开始时启动传 输，否则要在时间段结束之前完成两个传输是不可能的。因此，允许站点在任意时刻 进行发送有可能会浪费2 t 的时问，如图2 1 中曲的纯p h a 法的传输示意图。 作为另一种方案，我们把时间划分成t 单位长度的时间段，并要求站点只能在 时问段的开始处启动传输，如图2 1 中b ) 所示。这样，只有两个站点都准备在同一个 时间段进行传输时，才会发生冲突。与纯a l o h a 法相比，在那种情况f ，如果第 二个站点在准备好帧后立刻传送，就会发生冲突。 哈尔滨工业大学工学硕士学位论文 图2 - 2 a l o h a 法和时隙a l o h a 法的成功率 f i g ；2 - 2 t h es u c c e s s p o s s i b i l i t y b y a l o h a a n d s l o t t e d a l o h a 为了使电子标签同步并受到控制，该方法选定了一组命令： r e q u e s t ：这个命令使在读写器作用范围内的所有电子标签同步，并促使电 子标签在下一个时隙里将它的序列号传输给读写器。 s e l e c t ( s n r ) ( 序列号) ：将一个( 事先确定的) 序列号作为参数广播给作用 范围内的各电子标签。具有此序列号的电子标签以此为执行写入和读出命令的独就开 关( 选择) ，具有其他序列号的电子标签只对r e q u e s t ( 请求) 命令应答。 r e a d - d a t a ：被选中的电子标签将存储的数据发送给读写器( 在实际系统 中，还要有写入、鉴别等命令) 。 处于等待状态的读写器在周期循环的时隙内发送一们青求命令。 下面举例说明采用以上命令的时隙a l o h a 法防冲突过程： 假设有5 个8 位序列号的电子标签在同一时间里进入了读写器的作用范围内( 见 图2 - 3 ) ，设本例系统