（通信与信息系统专业论文）基于物联网的智慧工厂的设计及防冲突算法研究.pdf

中文摘要中又捅要 摘要：随着信息技术的迅速发展以及市场竞争的日趋激烈，企业为了提高自身竞 争力已经做了大量的企业管理信息化、自动化等方面的工作，而物联网技术的发 展为这一工作带来了新的机遇。如何有效地将物联网技术广泛应用到企业生产经 营和管理决策中，已经成为各类企业最感兴趣的热点研究方向之一。本论文以山 东太平洋光缆公司为模型，设计并实现了一套智慧工厂管理系统，旨在为企业提 供合理的解决方案，提高企业的经营管理效率。 本论文结合企业现有管理系统的实际情况和相关技术手段，为企业量身制定 了一套智慧工厂管理系统解决方案。本系统的开发基于j 2 e e 平台和s s h 框架， 使用o r a c l e 数据库，采用b s 架构的形式，将射频识别r f i d 技术运用到企业生 产和管理决策中。系统按功能可划分为门禁管理、智能巡检、人员管理和仓储管 理四个子系统。 针对门禁管理子系统在运行中遇到的实际问题，本论文对r f i d 系统中存在的 标签冲突现象进行了深入研究，并详细研究了在二进制搜索系列算法的基础上演 变而来的基于1 6 位随机数的二进制搜索算法的基本概念和算法原理，说明其相比 传统二进制搜索算法所具有的优势的同时，也阐述了此算法的不足之处，即在电 子标签数量显著增大后算法的有效识别效率降低。为了弥补这个缺陷，作者提出 了改进后的算法，应用此改进算法可以应对任意数量电子标签的r f i d 系统，继承 其优势的同时又不存在标签容量限制。 该系统的完成可以为企业提供一个能够全面掌握员工及各类生产资料信息的 平台，同时也提供了详细的权限访问控制管理功能，便于企业按照部门划分和实 际业务需求进行权限管理和访问控制。 目前，智慧工厂管理系统已经在企业现场经过调试后安装上线，运行情况基 本良好，在一定程度上方便了企业的日常管理工作，提高了企业的经营管理效率。 并且，在2 0 1 1 年6 月于济南市举办的山东省产学研展洽会上，该系统得到了展示 的机会，展会期间受到了广泛关注。 关键词：物联网；射频识别；标签冲突；防冲突算法 分类号：t p 3 1 9 a b s t r a c t a b s t r a c t ：t h er a p i dd e v e l o p m e n to fi n f o r i n a t i o nt e c h n 0 1 0 9 ya n df i e r c ec o m p e t i t i o n f o r c ee n t e 印r i s e st oc o n s t a n t l yi m p r o v et 1 1 em a n a g e m e l l tm e t h o d sb a s e do ni n f o m a t i o n t e c h n 0 1 0 9 y v 撕o u se n t e 印r i s e sh a v ed o n ea b u n d a i l tw o r ki n o r d e rt oi m p r o v et h e i r m a l l a g e m e n te 衢c i e n c y t l l er 印i dd e v e l o p m e n to fi n t e n l e t o f 二7 r h i n g st e c h n 0 1 0 9 yb d n g s 黟e a to p p o r m n i t i e s h o wt o e f f e c t i v e l y印p l yi n t e m e t o f - t h i n g st e c h n 0 1 0 9 y t o e n t e 叩r i s ep r o d u c t i o na 1 1 dm a n a g e m e n td e c i s i o nh a sb e c o m eo n e o ft h ef o c u sp o i n t so f c u 盯e n tr e s e a r c h i nt h i st h e s i s ，s m a nf a c t o r ys y s t e mi sd e s i g n e dt op r o v i d ee n t e 印 s e w i mar e a s o n a b l es o l u t i o na n dt oi m p r o v et h em a n a g 锄e n te 衔c i e n c y h 1t l l i st h e s i s ，ac u s t o m i z e ds m a n f a c t o 巧s y s t e mi sd e v e l o p e df o r t h ee n t e 印矗s e t 1 1 i ss y s t e mi sd e v e l o p e do nj 2 e ep l a t f o m l ，u s i n gs s h 靠a i n e w o r ka n do r a c l ed a t a b a s e i 江i dt e c l l l l o l o g yi sa l s oi n v 0 1 v e df o re n t e 叩 s ep r o d u c t i o na n dm a n a g e m e n td e c i s i o n i na d d i t i o n ，a j lo v e r v i e wo ft h eo v e r a l ld e s i 髓a n d 如n c t i o n a l i t yi sd e s c 拍e d t l l es y s t e m c a l lb ed i v i d e di n t of i o u rm o d u l e sa c c o r d i n gt od i v e r s ef h n c t i o n ，a c c e s sm a i l a g e m e n t ， s t a f rm a i l a g e m e n t ，s m a r ti n s p e c t i o na n ds t o r a g em a n a g e m e n t t h eb i n a r ya n t i c o l l i s i o na 1 9 0 r i t h mi si n 仃o d u c e di nt h i st h e s i s ，i n c l u d i n gt h e e i l c o d i n gt y p ea 1 1 dm e 砸n c i p l e so ft h es 商e so fb i n a 叫s e a r c ha l g o r i t h m s t 1 1 i st h e s i s i n 仃o d u c e sa na 1 1 t i c 0 1 l i s i o na l g o r i t h mc a l l e d16 - b i tr a l l d o mn u m b e r - b a s e dq u e r yt r e e a 1 9 0 五t 1 1 h 1 t h ei n 仃o d u c t i o nn o to n l yd e s 嘶b e s 廿l e 研n c i p l e sa n da d v 锄t a g e so ft h i s a l g o r i t | 1 1 1 1 ，b u ta l s oi n v o l v e si t ss h o n a g e s t h es i 鲥f i c a n ti n c r e a s i n go ft h en u m b e ro f t a g sw i t h i nt h es y s t e mw i l lr e d u c et h ei d e n t i f i c a t i o ne 丘i c i e n c y ：l na d d i t i o n ，a ni m p r o v e d a l g o r i t h mi si n t r o d u c e dt oo v e r c o m et h i ss h o r t a g e t h ep r i n c i p l e sa n da d v a n t a g e so f t h i s i m p r o v e da l g o r i t l l ma r ea l s oi n t r o d u c e d a p p l i c a t i o no fm i si m p r o v e da l g o r i t h mh e l p s t o d e a lw i t hr f i ds y s t e mo fa 1 1 yn u m b e ro ft a g s ，w i m o u ta n yc a p a c i t y1 i m i t s s m a r tf a c t o r ys y s t 锄p r o v i d e sap l a t f o 肌i n c l u d i n ga 1 1t h ei n f o m l a t i o no ft h es t a f j f a 1 1 dp r o d u c t i o n sf o rt h ee n t e 印r i s e m o r e o v e r ，p e m i s s i o nt oa c c e s sc o n t r o lm a n a g e m e n t m o d u l ei si n v 0 1 v e di nm i ss y s t e m ，w h i c hw o u l de n h a n c et h es e c u r i t yo ft h ew h 0 1 e s y s t e m a tp r e s e n t ，t h es y s t e mh a sb e e ni n s t a l l e df o r t h ee n t e 印r i s ea n dr u n n i n gi ng e n e r a l l y g o o dc o n d i t i o n t h es y s t e mf a c i l i t a t e s t h ee n t e 叩d s em a n a g e m e n ta n di m p r o v e st h e o p e r a t i o ne m c i e n c ya t ac e n a i ne x t e n t f u r t h e 衄o r e ， o nr e s e a r c he x h i b i t i o no f s h a i l d o n gp r o v i n c eh e l di nj u n e2 0 1 1a tj i n a nc i 咄t h es m a nf a c t o r ys y s t e mh a d b e e n v p u to ne x h i b i t i o n t h es y s t e mr e c e i v e dw i d e s p r e a da t t e n t i o n d u n gt h ee x h i b i t i o n 1 ( e y w o r d s ：i n t e m e t 。f t h i 嘲r f i d ；t a gc o l l i s i o n ；a n t i c 0 1 】i s i 。na 1 9 。r i t h m c l a s s n o ：t p 3 1 9 致谢 转眼间，论文撰写工作已经到了收尾阶段，硕士阶段的学习生活即将结束， 回首这两年多的时光，在收获知识、培养能力、获得喜悦与成就感的同时，内心 更想表达的是浓浓的感恩之情。 首先，感谢我的导师刘云教授。刘老师是真正意义上的良师益友，她严谨求 实的治学态度和一丝不苟的科研精神使我受益匪浅。除了传授知识，刘老师更加 注重培养学生端正的求学态度和高效的科研方法，为学生今后的人生发展打下了 坚实的基础。而且，在刘老师慈母般的关怀照料下，在实验室就有如回家般的温 暖舒适。在此，特向恩师刘老师致以最诚挚的谢意。 感谢张振江副教授在科研项目上的悉心指导，感谢张老师在课题和论文上的 帮助和支持。另外，在找工作的过程中，学生遇到困惑的地方，张老师也会给予 最诚恳有效的指点，使学生辨明方向，少走弯路。在此，衷心地感谢张老师两年 多以来的指引和帮助。 感谢毕红军副教授，感谢孟嗣仪副教授，感诩穆海冰副教授，感谢实验室所 有老师们，他们在学业、生活和科研方面的帮助和指导使我受益良多。 感谢我的同学王开煊，张旭，王若梦，唐沁钦，王巍，他们对我的课题研究 和论文撰写工作给予了热情无私的帮助，祝愿他们工作顺利，前程似锦。 最后，感谢交大和电信学院为我提供了良好的学习和生活环境，让我能够顺 利地完成自己研究生阶段的学习。 1引言 通俗来讲，物联网实际上就是“物物相连的互联网 ，它是通过射频识别、无 线传感器网络、全球定位系统等技术手段，把任何物品都接入到互联网中，通过 互联网来通信并交换信息，以最终实现包括识别、定位、感知等功能的智能化管 理【。 物联网中非常重要的技术之一是射频识别( i 疆i d ) 技术。特别是在企业软件 领域，r f i d 将是继e i 冲、c r m 之后的又一新的增长点。我国作为全球范围内制 造业的基地，在r f i d 技术领域有着广阔的应用前景和市场空间，但我国在面向 i 讧i d 的应用集成技术研究方面还与国外存在着很大的差距，直接制约了r f i d 技 术的推广和应用【2 1 。 1 1研究背景 随着信息技术的发展，物联网( i n t e m e to ft 1 1 i n g s ，i o t ) 这个概念受到越来越 多具有战略眼光的国家首脑和企业家的关注。在计算机和互联网的大发展之后， 物联网成为世界信息产业发展的第三次浪潮，世界上很多国家都不惜斥巨资在物 联网相关领域进行深入的研究【3 1 。 欧盟于2 0 0 6 年3 月召开题为“f r o mr f i dt ot h ei n t e m e to ft 1 1 i n 2 s ”的会议， 物联网技术得到了描述，并进而制定了物联网相关技术的研究策略路线刚4 1 。之后 的2 0 0 9 年，“智慧地球”的概念被i b m 公司提出，在这个概念中，无线传感器被 嵌入到电力、轨道交通、桥梁等各行各业的应用中，并且通过统一的智能处理和 决策，达到概念中所提及的智慧状态【5 】。 2 0 0 9 年，中国政府要加大力度扶持物联网产业的发展，并提出“感知中国” 计划，在国家五大战略性产业中，物联网被提升到第二位。之后在2 0 1 0 年全国“两 会”上，温总理在政府工作报告中提出“加快物联网的研发应用”【6 1 。2 0 1 0 年 1 2 月山东省人民政府第8 6 次省政府常务会议审议并通过了山东省物联网产业 发展规划纲要( 2 0 1 1 2 0 1 5 ) ，纲要提出坚持“设施先行、创新驱动、以用兴业、 重点突破、协同发展”的原则，确立应用牵引的产业发展模式，以物联网示范工 程建设为核心，加快形成“智慧山东”基本框架。 在这样的技术大环境和政策背景下，本论文设计并实现了一套智慧工厂管理 系统，以期通过物联网技术的应用提高企业日常经营管理工作的效率。 1 2研究目的和意义 目前，大多数企业的日常管理方面的技术手段还不够完善，处于比较传统的 管理方式，制约了企业的生产效率和管理水平的提高。因此，有必要开发一套基 于物联网的智慧工厂管理系统，将迅速发展的物联网技术尤其是r f i d 技术融入到 企业生产管理中，提高企业的生产效率和现代化管理水平。 本论文拟通过设计并完成一套基于物联网的智慧工厂系统，提供门禁管理、 智能巡检、人员管理和仓储管理等功能。门禁管理系统是管理人员出入的智能化 系统，使得企业人员签到、换班的速度和效率明显提高；智能巡检系统确保了工 厂、设备、生产资料的安全，通过该系统的智能反馈，可以辅助管理人员决策； 人员管理系统实现对人员信息的动态管理，摒弃了传统的手工记录管理；仓储管 理系统帮助企业对生产原材料、设备、半成品和最终产品的统一监控和动态管理， 包括采购、出入库和销售等环节的集中管理，有利于提高企业的综合管理和决策 效率。另外，该系统还提供了详细的权限访问控制管理功能，便于企业按照部门 划分和实际业务需求进行权限管理和访问控制。 针对门禁管理系统中遇到的实际问题，本论文深入研究r f i d 系统中的标签冲 突问题以及相应的标签防冲突算法，并在基于1 6 位随机数的二进制搜索算法的基 础上提出了一个改进算法，该算法在继承其优势的同时，也弥补了其标签容量存 在限制的缺陷。 智慧工厂管理系统的完成可以为企业提供一个能够全面掌握员工及各类生产 资料信息的平台，帮助企业更方便快捷地进行生产监督、管理和决策等工作，提 高企业的经营管理效率，在同类企业中具有比较广泛的应用前景。 1 3论文的主要工作及组织结构 本文在以上章节中所讨论的研究背景及国内外研究现状之下，为甲方企业量 身制定了一套智慧工厂管理系统解决方案，并且经过安装调试后目前已经上线运 行，情况良好。并且根据在实际情况中遇到的r f i d 系统中的标签冲突问题，通过 查阅相关文献资料，进行深入探究，并提出作者的一些想法。 本文第一章介绍了智慧工厂管理系统提出的背景及其相关物联网技术的研究 背景和意义，并分析了物联网技术在国内外的研究现状及发展趋势，最后对本论 文的主要工作及组织结构进行了阐述。 第二章对本论文涉及的相关技术资料和背景知识进行了介绍。首先介绍了 j 2 e e 平台相关的理论知识，包括j 2 e e 平台基本概念、比较优势和四层模型；接 着介绍了o r a c l e 数据库的相关理论知识和相关特点、优势；然后介绍了物联网中 r f i d 技术的基本概念、工作原理和相关特点；最后介绍了r f i d 系统中的冲突现 象，引出标签冲突模型中的二进制防冲突算法并且着重进行了介绍，包括该系列 算法采取的编码方式以及二进制搜索算法、动态二进制搜索算法、后退索引二进 制搜索算法、后退索引动态二进制搜索算法的相关理论知识和算法原理。 第三章首先阐述了智慧工厂管理系统的总体设计和功能概述，然后按功能划 分为门禁管理子系统、智能巡检子系统、人员管理子系统和仓储管理子系统，并 分别对各个子系统进行功能设计、数据库设计以及相关实现的阐述。本章的最后 部分阐述了智慧工厂管理系统的运行测试过程及结果。 第四章首先介绍了基于1 6 位随机数的二进制搜索防冲突算法的基本概念和算 法原理，并且阐述了此算法的不足之处，即在电子标签数量显著增大后算法的效 率降低。然后阐述了基于1 6 位随机数的二进制搜索算法的改进算法的基本概念和 算法原理，说明其优于之前算法的原因。 第五章是对本论文研究工作和所取得成果的总结，并且在最后提出了对今后 的研究方向和工作内容的展望。 2相关技术介绍 本章对本论文涉及的相关技术资料和背景知识进行了介绍。首先介绍了j 2 e e 平台相关的理论知识，包括j 2 e e 平台基本概念、比较优势和四层模型；接着介绍 了o r a c l e 数据库的相关理论知识和相关特点、优势；然后介绍了物联网中r f i d 技术的基本概念、工作原理和相关特点；最后介绍了r f i d 系统中的冲突现象，引 出标签冲突模型中的二进制防冲突算法并且着重进行了介绍，包括该系列算法采 取的编码方式以及二进制搜索算法、动态二进制搜索算法、后退索引二进制搜索 算法、后退索引动态二进制搜索算法的相关理论知识和算法原理。 2 1 j 2 e e 平台 j 2 e e ，即j a v a 2 平台企业版( j a v a2p 1 a t f o m ，e n t e r p r i s ee d i t i o n ) ，区别于适用 于小型设备和智能卡的j 2 m e 平台( j a v a2p l a t f o 彻，m i c r oe d i t i o n ) 和适用于桌面 系统的j 2 s e 平台( j a v a2p 1 a t f o m ，s t a n d a r de d i t i o n ) ，j 2 e e 平台适用于创建服务器 应用程序和服务。 j 2 e e 是一种利用j a v a2 平台来简化企业解决方案的开发、部署和管理相关的 复杂问题的体系结构。j 2 e e 技术的基础就是核心j a v a 平台或j a v a2 平台的标准版， j 2 e e 不仅巩固了标准版中的许多优点，例如“编写一次、随处运行”的特性，方 便存取数据库的j d b c a p i 、c o r b a 技术以及能够在i n t e m e t 应用中保护数据的安 全模式等等，同时还提供了对e j b ( e n t e r p r i s ej a v a b e a n s ) 、j a v a s e r v l e t s a p i 、j s p ( j a v as e r v e rp a g e s ) 以及x m l 技术的全面支持，其最终目的就是成为一个能够 使企业开发者大幅缩短投放市场时间的体系结构【7 】。 j 2 e e 体系结构提供中间层集成框架用来满足无需太多费用而又需要高可用 性、高可靠性以及可扩展性的应用的需求。通过提供统一的开发平台，j 2 e e 降低 了开发多层应用的费用和复杂性，同时提供对现有应用程序集成强有力支持，完 全支持e n t e r p r i s ej a v a b e a n s ，有良好的向导支持打包和部署应用，添加目录支持， 增强了安全机制，提高了性能【8 】。 j 2 e e 平台为搭建具有可伸缩性、灵活性、易维护性的商务系统提供了良好的 机制【9 1 ： 1 保留现存的i t 资产：由于企业必须适应新的商业需求，利用已有的企业 信息系统方面的投资，而不是重新制定全盘方案就变得很重要。这样，一 个以渐进的( 而不是激进的，全盘否定的) 方式建立在已有系统之上的服 4 务器端平台机制是公司所需求的。这之所以成为可能是因为j 2 e e 拥有广 泛的业界支持和一些重要的企业计算领域供应商的参与。每一个供应商都 对现有的客户提供了不用废弃已有投资，进入可移植的j 2 e e 领域的升级 途径。由于基于j 2 e e 平台的产品几乎能够在任何操作系统和硬件配置上 运行，现有的操作系统和硬件也能被保留使用。 2 高效的开发：j 2 e e 允许公司把一些通用的、很繁琐的服务端任务交给中间 件供应商去完成。这样开发人员可以集中精力在如何创建商业逻辑上，相 应地缩短了开发时间。高级中间件供应商提供以下这些复杂的中间件服 务： a ) 状态管理服务：让开发人员写更少的代码，不用关心如何管理状态， 这样能够更快地完成程序开发。 b ) 持续性服务：让开发人员不用对数据访问逻辑进行编码就能编写应用 程序，能生成更轻巧，与数据库无关的应用程序，这种应用程序更易 于开发与维护。 c ) 分布式共享数据对象c a c h e 服务：让开发人员编制高性能的系统， 极大提高整体部署的伸缩性。 3 支持异构环境：j 2 e e 能够开发部署在异构环境中的可移植程序。基于j 2 e e 的应用程序不依赖任何特定操作系统、中间件、硬件。因此设计合理的基 于j 2 e e 的程序只需开发一次就可部署到各种平台。这在典型的异构企业 计算环境中是十分关键的。j 2 e e 标准也允许客户订购与j 2 e e 兼容的第三 方的现成的组件，把他们部署到异构环境中，节省了由自己制订整个方案 所需的费用。 4 可伸缩性：企业必须要选择一种服务器端平台，这种平台应能提供极佳的 可伸缩性去满足那些在他们系统上进行商业运作的大批新客户。基于j 2 e e 平台的应用程序可被部署到各种操作系统上。例如可被部署到高端u n l x 与大型机系统，这种系统单机可支持6 4 至2 5 6 个处理器( 这是n t 服务器 所望尘莫及的) 。j 2 e e 领域的供应商提供了更为广泛的负载平衡策略，能 消除系统中的瓶颈，允许多台服务器集成部署。这种部署可达数千个处理 器，实现可高度伸缩的系统，满足未来商业应用的需要。 5 稳定的可用性：一个服务器端平台必须能全天候运转以满足公司客户、合 作伙伴的需要。因为i n t e m e t 是全球化的、无处不在的，即使在夜间按计 划停机也可能造成严重损失。若是意外停机，那会有灾难性后果。j 2 e e 部 署到可靠的操作环境中，他们支持长期的可用性。一些j 2 e e 部署在 w i n d o w s 环境中，客户也可选择健壮性能更好的操作系统如s u ns o l 抓s 、 气 i b mo s 3 9 0 。最健壮的操作系统可达到9 9 9 9 9 的可用性或每年只需5 分 钟停机时间，这是实时性很强的商业系统的理想选择。 j 2 e e 使用多层的分布式应用模型，应用逻辑按功能划分为组件，各个应用组 件根据他们所在的层分布在不同的机器上。事实上，s u n 设计j 2 e e 的初衷正是为 了解决两层模式( c l i e n t s e r v e r ) 的弊端，在传统模式中，客户端担当了过多的角 色而显得臃肿，在这种模式中，第一次部署的时候比较容易，但难于升级或改进， 可伸展性也不理想，而且经常基于某种专有的协议，通常是某种数据库协议。它 使得重用业务逻辑和界面逻辑非常困难。现在j 2 e e 的多层企业级应用模型将两层 化模型中的不同层面切分成许多层。一个多层化应用能够为不同的每种服务提供 一个独立的层，以下是j 2 e e 典型的四层结构【l o j ： 运行在客户端机器上的客户层组件 运行在j 2 e e 服务器上的w 曲层组件 运行在j 2 e e 服务器上的业务逻辑层组件 运行在e i s 服务器上的企业信息系统层组件 j 2 e e 应用程序l 应用程序 客户端 j 2 e e 应用程序2 客户层! 嚣 w e b 层 业务层 图2 1j 2 e e 的四层模型 f i g u r e2 1f o u r - l a y e rm o d e lo fj 2 e e 2 2 o r a c l e 数据库 j 2 e e 服务器 数据库 服务器 o r a c l e 数据库( o r a c l ed a t a b a s e ) ，简称0 r a c l e ，是甲骨文公司的一款数据库管 6 j e 立交适叁堂亟堂僮途塞掐羞遮盔金缉 理软件系统，其管理数据的方式是关系型和面向对象为中心，0 r a c l e 在企业管理信 息系统的数据处理以及因特网和电子商务等各个领域都有着非常广泛的应用。由 于o r a c l e 数据库在数据安全性和数据完整性的控制方面有着非常优越的性能，并 且在跨操作系统或是跨硬件平台的环境中有着先对便捷安全的数据互操作能力， 所以在全球范围内0 r a c l e 的用户数量都在持续稳定增长。 o r a c l e 数据库的模式结构是“客户端服务器”模式。客户端应用程序的职责 是执行一切与用户进行交互的活动，并且接收用户反馈信息，同时向“服务器 发送请求；各种操作数据的活动以及管理数据信息则都是服务器的职责。 o r a c l e 数据库的特点： 1 o r a c l e 引入了共享s q l 的机制以及多线程体系结构，减少了系统的资源占 用，使o m c l e 在配置较低的平台上应用自如，支持相同数量的用户只需要 占用相对较少的资源。 2 0 r a c l e 提供基于角色分工的安全保密管理。在数据库的管理功能、安全性、 完整性检查等各方面都有良好的表现。 3 支持大量多媒体数据，如二进制图形、声音、动画以及多维数据结构等。 4 。提供了与第三代高级语言的接口软件p r 0 术系列，能在c ，c + + 等主语言中 嵌入s q l 语句及过程化( p u s q l ) 语句，对数据库中的数据进行操纵。加上 它有许多优秀的前台开发工具如p o w e rb u i l d 、s o l 木f o r m s 、v i s i a b a s i c 等，可以快速开发生成基于客户端p c 平台的应用程序，并具有良 好的移植性。 5 提供了新的分布式数据库能力。可通过网络较方便地读写远端数据库里的 数据，并有对称复制的技术。 2 3i 强i d 技术及防冲突问题 射频识别，即r f i d ( r a d i of r e q u e n c yi d e n t i 6 c a t i o n ) 技术，是一种自动的非 接触式的识别技术，识别的媒介是射频信号，可以在条件恶劣的环境中使用，并 且不需要人工干预，自动识别】。 r f i d 技术可以称为是2 1 世纪发展前途最光明的信息技术之一，已经得到了 全世界范围内的高度关注。中国作为世界i t 产品最主要的消费市场和生产基地， 为r f i d 技术乃至整个物联网产业的发展和应用带来了前所未有的市场空间，同时 也提供了巨大的发展机遇。相信在不远的将来，r f i d 电子标签被植入到所有的物 品中，真正实现“物物相连”的物联网【1 2 】。 r f i d 系统由电子标签、天线和读写器三部分组成。电子标签是由芯片和耦合 7 元件组成的，并且各个电子标签都有一个e p c ( e 1 e c t r o n i cp r o d u c tc o d e ) 编码，此 e p c 码是全球唯一的。将约定格式的一段数据存储到电子标签中，再把电子标签 粘贴或者嵌入到物品中，就能达到非接触识别目标对象的目的。天线负责在读写 器与电子标签之间通过射频信号传输标签中存储的数据信息。读写器按形式可以 划分为固定式和手持式，不管是什么形式，读写器的职责都是读取或写入存储在 电子标签中的数据信息【1 3 】。 与条码、磁卡、i c 卡等目前使用比较广泛的识别技术相比，r f i d 技术所具有 的优势有很多： 1 ) 识别距离远，为非接触操作，所以工作状态无需手动帮助，使用更便捷； 2 ) 没有机械磨损，故器件寿命较长，而且可以在比较恶劣的环境中工作； 3 ) 可以识别一定范围内的高速运动目标，并且支持多个电子标签同时识别； 4 ) 在读写器上有物理接口，这个接口是不对最终用户开放的，这样就保证了 读写器的安全性； 5 ) 数据安全方面，电子标签具有密码保护功能，除此之外，也可以用一些算 法实现数据部分的安全管理； 6 ) 在电子标签和读写器之间进行通信的过程中，首先进行的是一个相互认证 的过程，增强了系统的安全性。 r f i d 系统与其他识别系统的比较如表2 1 所示【1 4 】。 表2 1r f i d 系统与其他识别系统的比较 t a b l e2 1d i 虢r e n c e sb e m e e l li 强i da n do t h e ri d e n t 语c a t i o ns y s t 锄s r f i d 系统的基本工作原理：当电子标签进入读写器的响应范围，即射频信号 场时，电子标签的天线得到感应电流，然后经过升压电路的升压过程，将其作为 驱动电子标签中的芯片工作的电源，同时把芯片中储存的数据由前端电路通过天 线的射频信号发射出去。读写器通过射频信号接收电子标签中的数据信息，并对 其进行解读，然后提供给上层软件接口进行所需的应用【l5 | 。 物联网从体系上大致可以被划分为感知层、传输层和智能应用层这三个层面。 每个层面在功能和结构上都是不可或缺的，但是，处于最前端的负责信息采集的 感知层对物联网的功能能否有效实现起着基础性和决定性的作用，而在感知层中， r 竖五! 篁迪厶堂亟：堂位论塞扫苤撞苤企型 r f i d 技术无疑是最重要的技术之一。因此，r f i d 技术对物联网的有效实现起到 了决定性的作用【6 】。 防冲突技术的相关研究是目前以及将来r f l d 系统中的一个关键问题。r f i d 系统中可能发生的冲突现象可以分为两种，第一种现琢【】l 做阅读器冲突，指的是 当一个标签被放在多个阅读器的响应范围内，被这些阅读器同时读取时发生的冲 突；第二种现象叫做标签冲突【1 7 】。 阅读器作用范围 豳巴# 豳_ 一， 图2 2 粝i 签冲突模型 f i g u r e2 2t a g c o l l j s i o nm o d e l 如图2 2 所示即为标签冲突模型。当多个电子标签同时出现在同一个阅读器的 响应范围或射频信号场内时，这些电子标签将同时与阅读器进行数据传输，彼此 的信号相互干扰，导致部分电子标签不能被阅读器识别，这种冲突即为标签冲突。 为了解决这种标签冲突现象，早期的研究人员提出了一些与之对应的算法，叫做 标签防冲突算法【1 8 】。 阅读器冲突模型如图2 3 所示。当一个标签被放在多个阅读器的响应范围内， 被这些阅读器同时读取时，此标签不能区分丌来自不同阅读器的多个信号，从而 发生冲突，这种冲突即为阅读器冲突。为了解决这种阅读器冲突现象，早期的研 究人员提出了与之对应的算法，叫做阅读器防冲突算法【19 1 。 阅读器n ：。一 图2 ：j 阅读器冲突模) 弘 f i g u r e2 3r e a d e r c o l l i s i o l ln l o d e l 9 阅读器2 如图2 4 所示，防冲突算法大致分为这几类，阅读器防冲突算法不在本文的研 究范围之内，没有进行细分。同样，基于a l o h a 的随机标签防冲突算法也不在 本文研究范围，未细分【2 0 】。 i 进进 l 制 裂黎 i 搜 索心 索 l 算算 l 法法 ；进e 磊垂 黉 篓霸 喜动 法 螽态 l 厶 图2 4 防冲突算法分类 f i g u r e2 4c 1 a s s i f i c a t i o no fa 1 1 t i c o l l i s i o na l g o t h m 标签防冲突算法实际上面对的是无线通信系统中的信道冲突问题，其解决方 法大致分为以下四类【2 l 】： 频分多路( f d m a ) ：根据载波频率的不同分配传输通路，并同时提供给访问 者使用。此种方法用在r f l d 系统中，要求阅读器有多个频率不同的接收通路，并 且每个通路都有自己的标签，这种方法的缺点就是对阅读器的成本要求太高。所 以，在r f i d 系统中，频分多路的标签防冲突算法只是应用到了个别比较特殊的场 合。 空分多路( s d m a ) ：实现空分多路比较复杂，需要专有硬件支持，即电子控 制定向天线，在阅读器与标签通信过程中，天线的方向可以依次变化，以便对准 不同的标签进行读取，这种方法的缺点与频分多路方法相同，天线的复杂度需要 较高的成本。因此，空分多路的标签防冲突算法同样只能应用到个别比较特殊的 1 0 场合。 码分多路( c d m a ) ：以扩频通信技术为基础实现数据传输。码分多路方法由 两部分组成，第一部分是扩频，作用是扩展信息带宽并传输信息；第二部分是码 分，作用是解决信道标识问题。码分多路技术在无线通信技术中得到了广泛的应 用，但是在i 讧i d 系统中，由于其通信频带与码分多路所要求的频带匹配性不高， 显著提高了技术复杂度，导致此方法很难得到应用。 时分多路( t d m a ) ：从时间这个纬度把整个通路分配给多个不同的标签，在 通信形式、成本以及系统复杂度的综合考量后，此方法是在r f i d 系统的防冲突机 制中采用最为广泛的，因此，基于时分多路的防冲突算法在r f i d 系统的标签防冲 突算法中占据主流地位。 2 4二进制防冲突算法 二进制防冲突算法是目前r f i d 系统防冲突算法中应用比较广泛的一种，此算 法属于前面提到的标签防冲突算法中的时分多路方法中的一种，也被称为确定型 标签防冲突算法【2 引。二进制防冲突算法与基于a l o h a 的随机型标签防冲突算法 相比，在系统可靠性和信道利用率方面都有明显优势，尤其是对于标签数量较多 的场景中，确定型算法更加灵活【2 3 1 。从本质上讲，二进制防冲突算法是利用逐次 比较的方法，在多次比较之后，一个一个筛选出不同的电子标签识别码f 2 们。 2 4 1 编码方式 o： i l： i ： l i ii r ： i k i ， i i li i i ii ii iii 图2 5 曼彻斯特编码方式 f i g u r e2 5m a n c h e s t e re n c o d i n g 由于搜索效率高，曼彻斯特( m a n c h e s t e r ) 编码在二进制算法中得到了广泛的 应用。在m a l l c h e s t e r 编码中，位值是通过电平的改变来表示的，用下降沿表示1 ， 用上升沿表示o 。当数据传输没有发生变化时，阅读器会识别为错误【2 5 】。 标签1 的识别码 l 0 0 1 1 1 1 1 标签2 的识别码 1 0 1 1 1 0 1 1 阅读器接收的识别 1 0 x 1 1 x l l 图2 6 曼彻斯特编码发现冲突原理 f i g u r e2 6p r i n c i p l e so fc o u i s i o ni nm a n c h e s t e re n c o d i n g 在m 锄c h e s t e r 编码中，当同一时间多个标签发送的位值不同时，阅读器接收 的上升沿( 表示0 ) 和下降沿( 表示1 ) 相互抵消，这样阅读器所接收到的就是无 变化的载波信号。这种信号被阅读器识别为一种错误，并且可以通过按位回溯来 跟踪冲突产生的位置。如图2 6 所示，阅读器接收到的信号为1 0 x 11 x 11 ，x 为冲 突产生的b i t 位，这里对应的载波没有上升沿或下降沿，是连续的。 2 4 2 二进制搜索算法 在了解二进制搜索( b i n a 巧s e a r c h ) 算法的原理之前，首先来介绍几种常用的 命令【2 6 】： a ) r e q 一请求：阅读器把一个参照序列号发送给所有电子标签，标签收到 参照序列号后，与自己的序列号进行比较。如果自己的序列号小于或等于 参照序列号，标签就会把自己的序列号发送给阅读器；否则，该标签无应 答。此操作的目的是为了缩小未识别的电子标签的范围。 b ) s e i 厂一一选择：阅读器把一个确定的序列号发送给范围内的所有电子标签， 与此序列号相同的标签即进入“准备就绪”状态，等待执行接下来的其它 命令。此过程本质上就是一个选择标签的过程。 c ) r d d a t a 读取数据：被选择的标签把待传送的数据发送给阅读器，阅 读器进行读取。 d ) u n s e i 一取消选择：阅读器对之前被选择的电子标签进行取消操作，使 该标签有被选择状态进入休眠状态，处于休眠状态的标签是不可被再激活 的，不会对阅读器的r e o 命令进行应答。 1 下面对二进制搜索算法进行举例说明，阅读器响应范围内有四个电子标签， 标签的序列号都是8 位，这四个标签的序列号分别为：1 0 1 1 0 0 1 0 ，1 0 1 0 0 0 1 1 ， 1 0 1 1 0 0 1 1 ，1 1 1 0 0 0 1 1 。算法的执行过程表2 1 所示。 表2 1 二二进制搜索算法执行过程 t a b l e2 1e x e c u t i o np r o c e s so fb i n a r ys e a r c ha 1 9 0 t h m 阅读器发送的 i 迮q 命令参数 一z 譬篆墼。川 解码 己识别标签 电子标签序列号 解俏 己t 【j 别标签 以下是二进制搜索算法的操作步骤： 1 ) 阅读器对参照序列号( e p c ) 进行初始化，使其为最大值。以8 位序列号 为例，e p c 被初始化为1 1 1 1 1 1 1 1 。 2 ) 阅读器发送请求命令r e q ( e p c ) ，所有在响应范围内的电子标签拿自己 的序列号与e p c 进行比较，小于或等于e p c 的电子标签进行应答，并把 自己的序列号返回给阅读器。 3 ) 阅读器根据m a n c h e s t e r 编码对返回的序列号进行解码，检测是否有冲突发 生。如果有冲突发生，找出最高的冲突位，将此冲突位设置为o ，高于此 冲突位的保持不变，低于此冲突位的全部设置为1 ，将此序列号作为参照 13 序列号e p c ，供下一次请求命令r e q 使用，然后执行步骤( 2 ) ；如果没 有冲突发生，阅读器就可以选中处于响应状态的电子标签中序列号最小的 标签，然后执行步骤( 4 ) 。 4 ) 阅读器对被选中的标签执行r d d a t a 命令来读取数据，然后执行u n s e l 命令来取消选择，使该标签进入休眠状态。 5 ) 重复前面的步骤，直到响应范围内的所有电子标签都被识别出为止。 假设阅读器的响应范围内共有n 个电子标签，采用二进制搜索算法进行标签 识别，则阅读器识别出某个电子标签平均需要进行l o g ，n + 1 次迭代，即占用 l o g ：n + 1 个时隙，因此，阅读器最终识别出所有n 个电子标签所需要占用的时隙 总数为n f l o g ，n + 1 ) 。 2 4 3动态二进制搜索算法 在前面介绍的二进制搜索算法中，阅读器与电子标签之间每次传输的都是完 整的序列号，这样会导致在整个识别过程中，阅读器与电子标签之间需要传输大 量的数据。对于二进制搜索算法的这个缺点，早期的研究人员提出了动态二进制 搜索( d y l l 锄i cb i n a r ys e a r c h ) 算法【2 7 1 。 假设电子标签的序列号为n