word某某 理工学院本科生毕业设计论文学院系：计算机与信息工程学院专业： 通信工程 学生： 乔军惠指导教师：路新华完成日期 2012 年 4 月某某理工学院本科毕业设计论文RFID二进制树防碰撞算法设计学 院系： 计算机与信息工程学院专 业：通信工程 学 生 姓 名： 乔军惠 学 号：指 导 教 师职称：路新华讲师评 阅 教 师：完 成 日 期：2012年4月 某某理工学院Nanyang Institute of TechnologyRFID二进制树防碰撞算法设计【摘要】射频识别技术RFID是目前正快速开展的一项新技术，它通过射频信号进展非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的开展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术开展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种算法当中，二进制树算法因为它识别应答器确实定性，成为了应用最广泛的一种，多个国际标准均对其进展了规定，这推动了防碰撞算法的开展，但是也带来了解决思路不统一的矛盾。在传统思路中，一般是通过单片机来进展算法处理，随着RFID技术的开展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID系统二进制树防碰撞算法，进展了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进展了归纳，汇总为根本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进展了性能评价；其次，在现有的三类防碰撞算法的根底上，提出了一种新的改良型二进制树算法，该算法识别速度快，执行效率高，极大的改良了识别效果。【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列AbstractRFID is anewly developedtechnologywhich municates through thecontact RF signal，so asto achieve objective automatic identificationAlong with the development of RFID technology，how to realize Data Exchange accurately amongMultiple Targets at the same time bees the key problem of RFID technologyRFID anti-collision algorithm is the solution to the above mentioned problemsIn all the algorithms，binary algorithm is most widely used as an international standard fbr its exactness ofidentincationInternational standards have put forward manyregulations on binary algorithmIt not onlypromotes the development of anticoUision algorithm，but also b“ngs the conflict to a unilFied solutionTraditionalideas in general are handled byMCUAlong with the development ofRFID technology，an imponant direction in the future is the field programmable gates arrayFPGAAs kindof integrated circuitsthatcanbe programmed in the field，FPGA is fast and programmableAll these adVantagesopenup anewef active way ofRFIDanticollisionarithmeticIn viewof the above problems，this paperprobes into the RFID systembinary prevent collisionfrom the perspectives ofboth theory and practiceIt canbediVided into three aspects：6rstly，theoretical researchon binary algorithmIt sums up all thebinary algorithms in being and gather to three categorys suchas Basic algorithm， Dynamic algorithm and Backoff algorithmMoreoVer，it Expounds the idea of the various algorithms and evalues their perf6rmance； secondary，it introduces an improved version of algorithm onthe basis of specinc standardThis algorithm has fast recognition， high efnciency and greatly improvedthe identification resultsKey Words：RFID；Anticollision；ReadWriteDeVices；Transponders；FPGA目 录1 引言611 RFID技术简介612 RFID系统6121 RFID系统组成6122 RFID系统分类7123 RFID系统工作原理813 RFID技术现状与其开展8131 RFID技术应用8132 RFID标准统一化9133 RFID防碰撞算法914课题提出的背景与其意义915本文的主要工作102 现有RFID二进制树防碰撞算法1121 RFID防碰撞算法概述1122 RFID二进制树防碰撞算法概述11221根本概念11222性能指标12223算法分类1323根本二进制树防碰撞算法14231算法思路14232实例演示15233性能评价1724动态二进制树防碰撞算法19241算法思路19242实例演示21243性能评价2225退避式二进制树防碰撞算法22251算法思路22252实例演示24253性能评价2526本章小结253 改良型二进制树防碰撞算法2531涉与二进制树算法的国际标准25311 IS0 1569325312 IS0144432632 IS014443标准二进制树防碰撞算法27321根本概念27322算法思路2833改良型二进制树防碰撞算法32331改良方向32332根本概念32334实例演示3734本章小结394 FPGA实现改良型二进制树防碰撞算法4041 FPGA技术40411 FPGA简介40412 FPGA设计流程40413 FPGA设计工具42414 FPGA设计语言45415 TestBench验证平台4542 RFID系统中的防碰撞模块4643 FPGA实现算法流程4644曼彻斯特解码模块4745命令处理模块50451请求命令处理50452防碰撞命令处理51453选择命令处理53454去选择命令处理5346命令选择模块5347数据存储模块5548密勒编码模块5649模块连接57410 本章小结58结论58致谢621引言11 RFID技术简介自动设备识别技术是目前国际上开展很快的一项新技术，英文名称为AutomaticEquipmentIdentif ication，简称AEI，它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理【ll】。目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领域的应用更具体的名称为射频识别，英文名为RadioFrequencyIdentification，简写为RFIDI21。RFID技术通过射频方式进展非接触的双向通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与微波理论的开展，自从上世纪九十年代以来，RFID技术快速开展，得到了广泛的应用，进入新世纪后，各个国家，组织还有企业都加大了对RFID技术的投入，生产了大批相应的产品，在多个领域有了成功的应用案例。RFID被誉为二十一世纪的十大战略性产业之一，可以预想，未来RFID技术的开展空间是无限广阔的。12 RFID系统121 RFID系统组成根据实际应用环境，RFID系统结构有多种不同分法，一般来说，一个典型RFID系统包括三个局部：前端信息载体，数据交换环节，后端应用环境【3】。在具体应用中，前端信息载体有多个名称，如标签(Tag)，智能标签(SmartLabels)，射频卡(RFCard)等，本文建议采用应答器(Transponder)这种更具普遍意义的说法。在RFID系统中，应答器放置在待识别的物体上，它内部存储的信息表征着该物品的独一性。通常来说，应答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存储器可将应答器分为EEPROM，FROM(铁电存储器)，SRAM(静态随机存储器)，根据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源供应方式分为无源，半无源，有源。一般来说，应用最广泛的是无源+集成电路固化+静态随机存储的应答器。由于在RFID系统中，应答器是大规模生产的。应答器的典型产品有TI公司的6000系列，Philips公司的ICODE等。数据交换环节即RFID系统中的读出写入设备，它是系统的核心部件，是后端应用环境和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫描器，阅读器，编程器等，本文建议采用读写器(ReadWriteDevice)这种更具普遍意义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中写入信息。根据天线与读写器模块的别离与否，读写器可以分为别离式和集成式，但无论哪种读