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

杭州电子科技大学硕士学位论文 摘要 无线射频识要j l j ( 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 技术的迅猛发展和应用需要，迫切需要阅读器在有限时间内高效准确地识别 大量标签。信号碰撞是影响r f i d 系统性能的关键，成为该领域的研究热点。在国内，传统 的防碰撞算法并不能很好地解决信号碰撞问题。针对传统防碰撞算法中普遍存在的一些问题， 本文提出相应的改进算法和设计思路，具体研究工作及创新点如下： ( 1 ) 深入研究了传统的r f i d 防碰撞算法，分析这些算法的应用背景及存在的不足。 ( 2 ) 对后退式二进制搜索算法的后退机理进行改进。后退式二进制搜索算法中，阅读器 在成功识别一个标签后，需发送a c t i v e 命令重新激活休眠标签，增加了传输的命令数，并且， 前向跳跃搜索只进行了一位碰撞前缀的处理，未能充分利用碰撞节点的信息。针对后退式搜 索算法的缺点和不足，本文提出一种自适应多叉树防碰撞算法。新算法的优化在于：修改算 法约定，通过休眠计数来控制通信状态，去掉了原有的激活命令机制，节省了一半的后退搜 索时间；动态调整指令长度，根据碰撞前缀的连续性选择合适的分叉数量，充分利用了碰撞 节点的信息，同时有效地减小了发送信息量，从而提高传输速率；只有一位碰撞位时直接识 别，减少了搜索次数。仿真表明，与后退式搜索算法相比，新算法的系统识别效率平均可达 7 6 5 ，且性能优势会随着标签数目的增多越发明显。 ( 3 ) 现有的调度方式算法需要耗费大量资源来去实时维护全网结构，系统的微小变化会 造成全网资源分配的重新调整，导致系统开销增大。本文提出一种新的多阅读器防碰撞算法， 该算法将r f i d 系统的读取过程设计为竞争，预约和传输三个阶段。在竞争阶段，阅读器通 过竞争产生簇首；在预约阶段，簇首发送预约命令安排通信小组内的受控阅读器预约通信顺 序；在传输阶段，簇首利用预约阶段获得的碰撞信息，控制选取“正确时隙”的阅读器进行 通信，从而避免阅读器间的信号碰撞，将无通信请求的阅读器置为休眠态，可以降低系统功 耗。和现有的调度方式算法相比，新算法能够提高系统的读取效率，同时降低阅读器的功耗。 ( 4 ) 最后，针对本文提出的阅读器防碰撞算法中有待进一步完善之处提出了改进方案， 并进行了描述，对今后r f i d 防碰撞算法的研究方向进行了展望。 关键词：无线射频识别，防碰撞算法，后退式搜索，调度方式，p u l s e 算法，系统效率 杭州电子科技大学硕士学位论文 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 n ( 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 ) i sak i n do ft e c h n o l o g y w h i c hm a k e su s eo faw i r e l e s sr a d i of r e q u e n c ym e t h o dt or e a l i z en 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 i c a t i o n ，n l i st e c h n o l o g yh a sb e e nu s e dw i d e l yi nt h ef i e l d so fg o o d sr e c o g n i t i o na n dd a t a c o l l e c t i o n ，w h i c hh a sm a n ya d v a n t a g e ss u c ha sh i i g l lr e c o g n i t i o na c c u r a c yr a t e ，r a p i dr e c o g n i t i o n s p e e d ，s t r o n ga n t i i n t e r f e r e n c ea b i l i t ya n dl o n gs e r v i c el i f e ，a n di tc a np e n e t r a t en o n m e t a lm a t e r i a l s a n dw o r ki nh o s t i l ee n v i r o n m e n t s 1 1 1 ec h i n e s eg o v e r n m e n tp a y sh i g ha t t e n t i o na n dr a p i d p r o m o t i o nt ot h ei n t e r n e to ft h i n g s ，a so n eo ft h et e r m i n a le n d i n g si nt h ei n t e r n e to ft h i n g s ，r f i d t e c h n o l o g yw i l lb ea p p l i e dw i d e l ya n dh a v eb r o a dd e v e l o p m e n tp r o s p e c t si nt h ef u t u r e w i t ht h er a p i dd e v e l o p m e n ta n dr e q u i r e m e n to fa p p l i c a t i o ni nr f i dt e c h n o l o g y , t h er e a d e r s n e e di d e n t i f ya g r e a tn u m b e ro ft a g se f f i c i e n t l ya n da c c u r a t e l y i nt h el i m i t e dt i m e s i g n a lc o l l i s i o ni s t h ek e yr e s t r i c t i o nt ot h ep e r f o r m a n c eo fr f i ds y s t e m ，w h i c hb e c o m e st h er e s e a r c hh o t s p o ti nt h e f i e l d s i nc h i n a , t h et r a d i t i o n a la n t i - c o l l i s i o na l g o r i t h mc o u l d n ts o l v et h ep r o b l e m so fs i g n a l c o l l i s i o nv e r yw e l l i nv i e wo fs o m ep r o b l e m se x i s t e di nt h et r a d i t i o n a la n t i - c o l l i s i o na l g o r i t h m s ， t h i st h e s i sp r o v i d e ss o m ei m p r o v e dm e t h o d sa n da l g o r i t h md e s i g n ，s p e c i f i cr e s e a r c hw o r ka n d i n n o v a t i o np o i n t sa sf o l l o w s ： ( 1 ) s t u d yd e e p l yo nt h et r a d i t i o n a lr f i da n t i c o l l i s i o na l g o r i t h m s , a n da n a l y z eo nt h e a l g o r i t h ma p p l i c a t i o nb a c k g r o u n da n dd e f i c i e n c y ( 2 ) a ni m p r o v e m e n ti sp r o p o s e dt ot h er e g r e s s i v e s t y l em e c h a n i s mo ft h er e g r e s s i v e s t y l e b i n a r ys e a r c ha l g o r i t h m i nt h er e g r e s s i v e - s t y l eb i n a r ys e a r c ha l g o r i t h m ，a f t e ri d e n t i f y i n gat a g s u c c e s s f u l l y , t h er e a d e rn e e d st os e n da c t i v eo r d e rt oa c t i v a t ed o r m a n c yt a g s ，w h i c hi n c r e a s e st h e n u m b e r so ft r a n s m i s s i o no r d e r s ，i na d d i t i o n ，t h ep r e - j u m pc o u l do n l yd e a lw i t ho n ec o l l i s i o np r e f i x ， a n df a i l st om a k ef u l lu s eo ft h ei n f o r m a t i o no fc o l l i s i o nn o d e s a g a i n s tt h es h o r t c o m i n g so f r e g r e s s i v e - s t y l es e a r c ha l g o r i t h m a na n t i c o l l i s i o na l g o r i t h mo fa d a p t i v em u l t i - t r e ei sp r o p o s e d t h e o p t i m i z a t i o n so ft h en e wa l g o r i t h ma r ea sf o l l o w s ：t h en e wa l g o r i t h mw i l lm o d i f yt h ea l g o r i t h m a p p o i n t s ，c o n t r o lc o m m u n i c a t i o n s t a t et h r o u g ht h ed o r m a n c yc o u n t ，a n dr e m o v et h eo r i g i n a l a c t i v a t i o no r d e rm e c h a n i s mw h i c hc a ns a v eh a l fo ft h er e g r e s s i v es e a r c ht i m e ；t h en e wa l g o r i t h m w i l la d j u s tt h el e n g t ho fi n s t r u c t i o n sd y n a m i c a l l y , a n dc h o o s et h ea p p r o p r i a t en u m b e ro ff o r k s f l e x i b l ya c c o r d i n gt ot h ec o n t i n u o u sc o l l i s i o n ，w h i c hm a k ef u l lu s eo ft h ei n f o r m a t i o no fc o l l i s i o n n o d e s 吼a t sm o r e ，t h en e wa l g o r i t h mw i l lr e d u c et h es e n di n f o r m a t i o ne f f e c t i v e l y , s oa st o i m p r o v et h et r a n s m i s s i o nr a t e ；d i r e c ti d e n t i f i c a t i o nw h e nt h e r ei so n l yo n ec o l l i s i o nb i t ，w h i c hw i l l r e d u c et h es e a r c ht i m e s t h es i m u l a t i o nr e s u l t ss h o wt h a t ，c o m p a r e dw i t hr e g r e s s i v es t y l es e a r c h i i a l g o r i t l l i i i ，t h es y s t e me f f i c i e n c y o ft h ep r o p o s e da l g o r i t h mi sa b o u t7 6 5 m o r e o v e r , w i t ht h e n u m b e ro ft a g si n c r e a s i n g , t h es u p e r i o r i t yo f t h ep e r f o r m a n c ei sm o r eo b v i o u s ( 3 ) t h ee x i s t i n gs c h e d u l i n ga l g o r i t h m sn e e dt oc o n s u m eal o t o fr e s o u r c e st om a i n t a i nt h e s 仃u c t u r eo ft h ew h o l en e t w o r kr e a l t i m e l y , s m a l lc h a n g e si nt h es y s t e mw i l lc a u s e t h er e d i s t r i b u t i o n o fn e t w o t kr e s o u 】r c e s ，a n d i n c r e a s et h ec o s to ft h es y s t e m an o v e lm u l t i 。r e a d e ra l g o r i t h m a n t i c o l l i s i o ni sp r o p o s e d ，w h i c hd i v i d e st h er e a d i n gp r o c e s so fr f i ds y s t e m i n t ot h r e es t a g e s i n c l u d i n gc o m p e t i t i o n ，a p p o i n t m e n ta n dt r a n s m i s s i o n i nt h es t a g eo fc o m p e t i t i o n ，t h ec l u s t e rh e a d o c c u r si nt h ec o m p e t i t i o na m o n gr e a d e r s ；i nt h es t a g eo fr e s e r v a t i o n ，c l u s t e r h e a ds e n d sa l l a p p o i n t m e n tc o m m a n dt ot h ec o n t r o l l e dr e a d e r sw i t h i nt h eg r o u p t oa p p o i n t m e n tc o m m u l l l c a t l o n o r d e r ：i i lm es t 矩r co ft r a n s m i s s i o n ，c l u s t e rh e a dc o n t r o l st h er e a d e r sw h i c hs e l e c tt h ec o r r e c tt i m e s l o t st oc o m m u n i c a t eb yu t i l i z i n go ft h ec o l l i s i o no fi n f o r m a t i o nf r o mt h es t a g eo fr e s e r v a t i o n ，t h i s w a vc a i la v o i dt h es i g n a lc o l l i s i o na m o n gr e a d e r s ，t h er e a d e r so f n oc o m m u n i c a t i o nr e q u e s ta r es e t t 0d o m l a r l c ys t a t e ，w h i c hw i l lr e d u c et h ep o w e rc o n s u m p t i o no ft h es y s t e m c o m p a r e dw i t ht h e e x i s t i n gs c h e d u l i n ga l g o r i t h m s ，t h en e wa l g o r i t h mi m p r o v e st h er e a d i n ge f f i c i e n c y , a n dm e a n w h i l e r e d u c e st h ep o w e rc o n s u m p t i o n f 4 ) f i n a l l y ，i nv i e wo ft h ep r o b l e m se x i s t i n gi nt h er e a d e ra 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 h s h o u l db e 如r m e ri m p r o v e d ，w ep r o p o s em o d i f i e dp l a n sa n dd e s c r i p t i o n ，a n dp r o s p e c tt h e f u t u r e f e s e a r c hd i r e c t i o no fa n t i c o l l i s i o na l g o r i t h m si nr f i ds y s t e m s k e y w o r d s ：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 ，a n t i - c o l l i s i o n a l g o r i t h m s ，r e g r e s s i v e 。s t y l e s e a r c h ， s c h e d u l i n ga p p r o a c h , p u l s ea l g o r i t h m ，s y s t e me f f i c i e n c y i i i 杭州电子科技大学硕士学位论文 第1 章绪论 1 1 研究背景和应用 温总理的“感知中国”，奥巴马的“物联网经济促进论，i b m 的“智慧地球 ，日本的 “i - j a p a n ，这些战略的提出无不标志着物联网已经从战略高度走向了产业化应用【l 】。物联网 在我国已被列为五大新兴战略性产业之一，并且被写入“政府工作报告 。物联网的应用已经 扩展到多个行业领域，包括安防、电力、交通、医疗卫生、工业控制、农业、环境监测、金 融服务业等。 作为物联网核心技术的r f i d 技术，被世界公认为2 l 世纪的十大重要技术之一1 2 】。该技 术具有抗干扰能力强、信息量大、可穿透非金属材料和使用寿命长等优点，能够快速、准确、 实时地收集并处理信息，被广泛应用于生产制造、设备管理、物流跟踪、自动收费和身份识 别等领域。在沃尔玛、宝洁、波音公司等在内的商业巨头的积极推动下，正飞速发展。 通常用到的自动识别技术有磁卡技术、条码技术、智能卡( i c 卡) 技术、生物识别技术、 光学字符识别技术和r f i d 技术，其中，r f i d 技术所具有的独特优势如下i l 】： ( 1 ) 无需人工干预，可实现非接触式识别和无源操作； ( 2 ) 能进行多目标识别及高速移动物体的识别； ( 3 ) 体积小，易封装； ( 4 ) 抗污染能力强，可实现穿透性识别； ( 5 ) 无机械磨损，使用寿命长，可工作在油渍、灰尘污染等恶劣环境； ( 6 ) 数据安全性更高，电子标签有密码保护机制，并且阅读器与电子标签间可通过相互 认证来实现安全通信和存储，还可通过算法实现进一步安全管理，如d e s 、r s a 、d s a 、m d 5 等。 早期r f i d 技术继承雷达的概念，最早应用于第二次世界大战中，但因成本和技术原因， 一直未得到广泛应用。其技术发展主要历经以下几个阶段： ( 1 ) 2 0 世纪5 0 年代，这段时期是r f i d 技术的应用和探索阶段。雷达技术的改进催生出 了r f i d 技术，h a r r i s 的在“使用可模式化的被动反应器的无线电波传送系统”中提出了信号 模式化理论和被动标签的概念。1 9 4 8 年，h a r r ys t o c k m a n 开展的基于反射能量的通信项目， 成为r f i d 理论研究的里程碑。 ( 2 ) 1 9 6 1 至1 9 8 0 年，r f i d 技术从理论走向应用。反向散射理论及其他电子技术( 如微 处理器和集成电路) 的发展为r f i d 技术的商业应用奠定了基础。2 0 世纪6 0 年代出现了r f i d 技术应用的第一个商业应用系统，即商品电子防盗系统( e l e c t r o n i c a r t i c l es u r v e i l l a n c e ，e a s ) 。 ( 3 ) 1 9 8 1 至1 9 9 0 年，r f i d 技术逐渐走入商业应用，相关的产品研发进入迅速发展时期。 杭州电子科技大学硕士学位论文 8 0 年代，r f i d 技术开始应用于动物的鉴别和跟踪，1 9 8 7 年，挪威将r f i d 技术应用与机动 车辆自动收费。 ( 4 ) 1 9 9 1 至2 0 0 0 年，不同r f i d 设备和系统的兼容问题引起重视，人们开始着力研究r f i d 技术标准的统一制定。1 9 9 1 年，美国铁路标准协会成立；1 9 9 4 年，美国所有的轨道车均采用 r f i d 技术；1 9 9 9 年，麻省理工学院( m i t ) 的自动识别技术中心成立，掀起了i 强i d 技术研究 的热潮。 ( 5 ) 2 l 世纪，r f i d 标准已初步形成。2 0 0 4 年底公布了第二代r f i d 技术标准，2 0 0 3 年， 沃尔玛宣布将采用r f i d 技术追踪其供应链系统中的商品，拉开了r f i d 技术在开放系统中应 用的序幕，r f i d 技术的逐渐走向成熟。 在信息化高速发展的社会，如何提升数据信息采集的效率和准确度成为每个行业共同关 注的焦点，r f i d 技术无疑在这方面跨出了一大步。r f i d 技术与通信和互联网技术相结合， 实现全网范围内的物品跟踪和信息管理，被广泛应用于生产制造业、物流管理和公共信息服 务等领域，可以大幅度提高管理效率，方便人们的生活。2 0 世纪9 0 年代以来，随着r f i d 设 备的生产规模不断扩大以及大规模集成电路的迅速发展，使得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 技术的研究主要围绕在电子标签成本、技术标准、 关键技术和系统应用等方面。 ( 1 ) 电子标签成本 电子标签主要由天线、标签芯片和射频接口组成，作为r f i d 系统的核心，其成本制约 着r f i d 技术的应用与发展。根据能量供应方式的不同可以将电子标签分为无源( 被动式) 、 半无源( 半被动式) 和有源( 主动式) 三种类型。2 0 0 3 年高频( h i g hf r e q u e n c y , h f ) 频段的无 源电子标签平均价格为9 l 美分，超高频( u l t r ah i g hf r e q u e n c y , u h f ) 频段的无源电子标签平均 价格为5 7 美分。可见，电子标签的成本仍是制约r f i d 技术广泛应用的关键，只有降低标签 成本，才能在满足供应需求的同时，推动r f i d 技术的全面应用，从而为人们提供更加舒适 便捷的信息服务。近年来，r f i d 芯片设计与制造技术的发展使得芯片功耗更低，作用距离更 远，读写速度与可靠性更高，标签成本也将不断降低。电子标签封装技术和印刷、造纸、包 装等技术相结合，以及石墨烯、碳纳米管等新材料正取代传统的硅，芯片制造成本继续降低， 将促进r f i d 电子标签的大规模生产，从而进一步降低电子标签价格。 2 杭州电子科技大学硕士学位论文 ( 2 ) 技术标准嘲 目前r f i d 技术在世界范围内发展十分迅猛，已经在国际很多大公司中进入实用阶段。 为了推动r f i d 技术在全球范围内的发展，形成统一化的全球性标准已成为业界认同的趋势， 相关的标准包括通信频率、物理特性、数据格式和元数据等。但是，市场上并没有统一化的 标准，不同供应商所生产的产品相互不兼容。目前r f i d 技术标准主要包括以下三种：欧美 的e p c g l o b a l 、日本的u i d ( u b i q u i t o u si d e n t i f i c a t i o n s ) 和i s o i e c 系列。这三个标准间实力相 当，分别有政府和大公司的支持，标准间互不兼容，标准之间的差别主要体现在防冲突算法、 通信方式和数据格式这几个方面。国际标准化组织正在积极推动r f i d 应用层面的互联互通， 目前各标准体系正在积极发展和推广自己的标准，各标准间出现了部分融合。 在r f i d 技术标准化的制定过程中，我国采用参照或引用i s o 等国际标准并作相应本地 化修改的方式来制定我国的国家标准，并且已经有了一定的基础。2 0 0 5 年l o 月，我国成立 了电子标签工作组，积极开展具有自主知识产权的国家标准的制定。制订了集成电路卡模 块技术规范、建设事业i c 卡应用技术等应用标准，并进行了广泛应用。在制定技术标准 上，我国已经把制定我国的r f i d 标准列入到国家标准制定计划，并且，我国r f i d 标准的起 草工作已经依照i s o i e c l 5 6 9 3 系列标准完成，在频率规划上，我国也进行了大量实验，目前， 我国已经基本完成了r f i d 国家标准的体系框架搭建工作。 一 ( 3 ) 关键技术 目前，对r f i d 系统关键技术的研究主要集中在天线设计与制造、安全和隐私、频率选 择技术、低功耗技术及防碰撞技术等方面【4 1 ，有关这几方面技术的研究将在本文的第二章中 进行详细介绍。 ( 4 ) 系统应用 1 ) 供应链应用 信息的准确性和及时性是供应链与物流管理的关键，这也是r f i d 技术最突出的优点之 一。r f i d 技术应用于商业供应链中，实现对原材料采购、半成品和成品生产制造、运输、仓 储、配送、上架与最终销售，甚至退货处理等所有供应链的环节进行实时监控，可以准确获 取各种产品的相关信息，例如种类、生产商、生产时间、地点、尺寸、颜色、数量、到达地 和接受者等，极大地提高自动化程度，大幅降低差错率，显著提高供应链的透明度和管理效 率。 在生产线的自动化过程控制方面，德国将r f i d 系统应用在汽车装配线上，从而保证汽 车在流水线各个位置能准确地完成装配任务。摩托罗拉公司采用r f i d 技术实现生产工序的 自动识别控制，很多国际化大型工厂的生产制造和自动化流水线上使用了r f i d 技术，进行 物品跟踪和生产监控，改进了生产方式，提高了生产效率，降低了成本。 2 ) 防伪 目前使用的防伪技术主要包括特种制版印刷防伪、荧光防伪、激光防伪、磁性防伪等， 这些技术在一定程度上发挥着防伪作用。而r f i d 技术具有难伪造、成本低、信息反馈性、 皇 杭州电子科技大学硕士学位论文 易于识别性、密码唯一性等优点，使用r f i d 技术可以实现使用唯一的产品标识号就能与已 有的数据库系统兼容，而不用更改现行的数据管理体制，被广泛应用于防伪领域。目前，国 内外正广泛在商品、证件以及票务防伪等方面利用r f i d 技术进行了研究开发，并取得了诸 多突破【5 】( 如韩国i d r o 公司推出一款可视化r f i d 标签和阅读器) 。我国在2 0 1 0 年上海世博 会中，研发了拥有自主知识产权的芯片技术，具有先进的防伪功能，应用于世博门票中，杜 绝了假票的生存空间。 3 ) 身份识别 身份识别作为r f i d 技术的一个很重要的应用领域，近年来得到了越来越多的重视和研 究。r f i d 技术可以用于动物的跟踪管理，将电子标签封装好后植入到动物的表皮下，可以用 于对动物进行标识，并对它们的健康状况进行监测。在大型的牲畜养殖场，使用r f i d 技术 可以建立预防接种档案和饲养档案等。r f i d 技术还广泛应用于门禁系统中进行身份识别，将 电子标签嵌入身份证或护照等证件中，可以快速识别出入人员的身份，简化了人员出入的手 续，为安全管理提供便利，也提高了工作效率。我国的第二代居民身份证、学生证优惠卡就 是采用了r f i d 技术，实现了非接触式的机器自动读取，提高识别效率。 4 ) 智能交通 r f i d 技术在交通管理中的应用有：车辆自动识别系统、公交车辆管理、停车场管理、不 停车收费等。高速公路自动收费系统是r f i d 技术最为成功的应用之一，人工收费及i c 卡停 车收费的方式将逐渐被淘汰。在行驶的汽车内安装无线射频标签，当车辆通过收费站时不需 要停车便会自动进行缴费，香港“驾易通 采用的就是r f i d 技术，该技术的使用提高了计 费效率和车行速度，避免了交通拥挤问题。自2 0 1 0 年8 月以来，上海黄埔区在公务用车上装 r f i d 监控系统，使得公务车使用费用较之前节约了2 4 ，2 0 11 深圳大运会上也成功实现在 大运专用车上安装4 万张r f i d 技术的电子车证。r f i d 技术利用无线电磁波来传输相关的识 别信息，不受空间限制，可以快速地进行追踪和数据交换，完成自动识别和自动化管理，免 除了人工干预，在节省人力的情况的同时，也极大提高了工作效率。 1 3 本文的主要工作及结构安排 论文针对r f i d 系统中普遍存在的信号碰撞问题，在分析研究现有的r f i d 标签防碰撞算 法和阅读器防碰撞算法的基础上，分别探讨研究了新的防碰撞算法，主要完成了以下两方面 工作： ( 1 ) 探讨标签防碰撞算法 后退式搜索算法在完成一个标签的识别后，返回到它上一层节点即父结点进行搜索，有 效利用了搜索过程中的二进制树节点的信息，具有较高的搜索效率。但是该算法所采用的后 退搜索和前向搜索相结合的方式并未充分利用碰撞节点的信息，且传输的命令数较多。对此， 本文提出一种自适应多叉树防碰撞算法。新算法对后退式搜索算法的后退机理进行改进：优 化算法约定，节省了后退搜索时间；只有一位碰撞位时直接识别，减少了搜索次数；动态调 4 杭州电子科技大学硕士学位论文 整指令长度，充分利用了碰撞节点的信息，同时有效地减小了发送信息量，从而提高传输速 率。这部分研究成果撰写的论文已被计算机应用录用。 ( 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 防碰撞算法，包括算法模型、研究现状及算法分类，并分别对 a l o h a 算法、二进制树型算法、调度方式以及功率调整方式算法中的几种较为典型的防碰 撞算法进行了相应的比较、分析和总结。 第四章深入研究了后退式搜索算法，在此基础上提出一种自适应的多叉树防碰撞算法。 新算法修改了后退式算法中的算法约定，以及遇到连续碰撞位时进行四叉树分裂的策略，使 得在搜索过程中能够动态选择分叉数量，充分利用碰撞节点的信息，并减少了发送信息量， 从而优化了系统的搜索效率。最后，通过仿真验证了新算法的有效性。 第五章研究基于调度方式的阅读器防碰撞算法，并在此基础上提出一种新颖的多阅读器 防碰撞算法。新算法将数据发送过程分为三个阶段t 竞争、预约和传输。采用无线传感网中 的分簇思想，结合预约、休眠机制，将全网的阅读器信号碰撞问题划分到各个子网中，能够 有效地避免阅读器的信号干扰，提高读取效率的同时，降低阅读器的功耗。最后，从算法性 能和可行性上进行了验证。 第六章总结与展望。对本文的研究工作进行总结，分析研究的不足之处，并对未来后续 的研究工作进行了展望。 杭州电子科技大学硕士学位论文 第2 章r f i d 系统及关键技术 2 1r f i d 系统的基本组成及分类 r f i d 系统通常由阅读器、电子标签和中央信息系统三部分组成。如图2 1 所示，阅读器 通过射频信号自动识别电子标签并获取相关信息，将信息送至中央信息系统进行数据处理， 识别工作无须人工干预。 电子标签阅读器 时钟 电源l 时钟- 一- 射 ， 控 存 射 + 天频制 储 能量阿罹 频 天线 中央 线模模 器 模 + 信息 一块 块块 , i - - - - - 系统 数据 模块i f i 电池( 可选) i 图2 1 射频识别系统的结构框图 2 1 1 阅读器 阅读器是利用射频技术读写电子标签的数据和信息的设备。它通过天线实现与电子标签 间的通信，阅读器把射频信号转化为数字信息并通过中央信息系统进行数据信息的采集和处 理。 ( 1 ) 基本构成 阅读器主要由接口电路、控制模块、射频通道模块和天线等四部分构成。如图2 2 所示， 阅读器的基本结构图如下： 网l 放一 国l 半卜 接口 解码及纠错 射频振荡器h 射频接收器 电路 电路 i 微处理器、存储器、标准 接口、时钟电路 前置放大器 图2 2 阅读器的结构图 1 ) 射频通道模块主要包括射频接收器、射频处理器、射频振荡器及前置放大器四个部分， 用于在射频通信中实现调制、解调和功率放大等功能。通常射频通道模块中有两个独立信道， 6 杭州电子科技大学硕士学位论文 分别用于发送或接收射频载波信号。通过射频振荡器产生了载波信号，射频处理器将该信号 进行放大，然后由天线来发送该载波信号。射频接收器接收来自天线的r f i d 电子标签信号， 通过前置放大器和射频处理器处理后，将处理的信息传给阅读器的控制模块。 2 ) 控制模块主要由放大器、存储器、微处理器、标签接口、解码及纠错电路及时钟电路 组成。主要完成对电子标签进行读写控制操作，包括以下几个过程：控制阅读器与电子标签 的通信过程；阅读器和电子标签之间传输数据的编解码；阅读器与电子标签之间的身份认证； 与中央信息系统进行通信，并执行来自中央控制系统的指令；在一些复杂的系统应用中，控 制模块还要实现防碰撞算法和安全认证功能。阅读器以前同步码或帧同步开始通信，阅读器 和标签中均有时钟电路，将所有电路功能时序化，以便标签与阅读器之间数据传输时间的精 确性。 3 ) 天线是收发射频信号的设备，用于阅读器中来增大系统的发射功率，从而获取最大的 能量传输效果，在r f i d 系统通常至少有一根内置或外置的天线，主要用于发射或接收射频 信号，该天线的形式及数量应视具体应用而定。 4 ) 接口电路用于实现阅读器与计算机之间的数据交换，调制发射信号，并将数据传输给 电子标签，还可产生高频的发射功率，将能量提供给无源电子标签。接口电路主要包括r s 2 3 2 、 r s 4 8 5 、r j 4 5 接口及以太网接口等。 ( 2 ) 功能 阅读器是r f i d 系统信息控制和处理的重要组成部分，其主要功能如下： 1 ) 在识别范围内同时读取多个标签，并能够正确区分不同标签； 2 ) 阅读器与计算机的通信功能。阅读器通过标准接口( 如r s 2 3 2 等) 与计算机网络相连， 提供读取到的标签信息，并将其传送给计算机，实现特定功能的应用任务； 3 ) 阅读器能够读出有源标签的相关信息，同时，对于阅读器识别范围内的无源标签，阅 读器也能为其提供能量，激活标签进行通信。阅读器的识别范围是一个电磁场，该场的范围 大小取决于阅读器和标签的天线尺寸以及阅读器的功率； 4 ) 阅读器能够校验阅读器读写过程中的错误信息并进行显示。 综上所述，阅读器的功能主要包括三个方面：发送和接收功能；信息初始化处理功能； 数据交换与管理功能。 ( 3 ) 分类 按照双工方式，可分为全双工和半双工。全双工方式指r f i d 系统工作时，允许阅读器 和电子标签在同一时刻双向传送消息，半双工方式指同一时刻，仅允许阅读器向电子标签传 送命令，或电子标签向阅读器返回消息。 按照通信方式，可分为阅读器先发言( r e a d e rt a l k sf i r s t ，r t f ) 和电子标签先发言( t a gt a l k s f i r s t ，t t f ) 两种方式。根据应用的不同，r f i d 系统采用不同方式进行通信。 按照应用模式，可分为便携式、一体式、固定式和模块式阅读器。便携式阅读器指天线、 阅读器和主控机集中在一起，阅读器只有一个天线接口；一体式阅读器指阅读器和主控机集 7 杭州电子科技大学硕士学位论文 中在一个机壳内固定安装，而天线在其他地方安装；固定式阅读器指主控机与天线和阅读器 分离，天线和阅读器可分别固定安装，而主控机在其他地方安装；模块式阅读器指阅读器作 为系统设备集成的一个单元，它与主控机的接口和应用有关。 ( 4 ) 发展趋势 随着r f i d 技术的发展，r f i d 系统的性能和结构也会不断提高。未来的r f i d 阅读器将 具有以下特点：阅读器小型化、嵌入化以及便捷化；阅读器多功能以及低成本：阅读器模块 化，可以将不同协议集成在同一个阅读器模板上；多种数据接口将得到应用，包括r s 2 3 2 、 r s 4 2 2 4 8 5 、红外、u s b 、以太网口及采用相位控制技术的智能多天线接口；将实现多制式、 多频段兼容；更多新技术的应用，如码分多址技术、智能信道分配技术等；多阅读器协调与 组网技术也将成为未来的发展趋势之一。 2 1 2 电子标签 电子标签又称为射频标签、射频卡或应答器，由芯片( 包括控制模块和存储单元) 和耦合 元件( 天线) 所组成，一般附着在被标识对象上。每个r f i d 电子标签有唯一的电子编码，电子 标签中存储了标识物体的相关信息，通过无线数据通信，根据r f i d 阅读器内的程序实现自 动化读取或改写。 ( 1 ) 基本构成 图2 3 为电子标签的结构框图，从功能上，r f i d 电子标签主要由天线、标签芯片和射频 接口等组成。 图2 3 电子标签的结构框图 天线是电子标签中信号的出入口，接收阅读器发出的射频信号，并能把电子标签中经过 射频模块处理后的射频信号回传给阅读器。 射频接口模块主要包括调制器、解调器、电压调节器组成，用于对数据射频化处理。来 自逻辑控制电路的模拟信号经过调制器处理后，被加载到天线上成为射频信号，该射频信号 被传送给阅读器。解调器接收射频信号，并将载波去除，从而得到解调后的模拟信号数据。 电压调节器将阅读器的射频信号转换为直流电源，并储存在大电容中，由稳压电路为其提供 稳定的供应电源。 r 杭州电子科技大学硕士学位论文 芯片主要用于对存储信息进行编解码并对其进行控制，包括