RFID二进制树防碰撞算法总结.docx

RFID二进制树防碰撞算法总结.docx

《RFID二进制树防碰撞算法总结.docx》由会员分享，可在线阅读，更多相关《RFID二进制树防碰撞算法总结.docx（42页珍藏版）》请在冰点文库上搜索。

RFID二进制树防碰撞算法总结

南阳理工学院

本科生毕业设计（论文）

学院（系）：

计算机与信息工程学院

专业：

通信工程

学生：

乔军惠

指导教师：

路新华

完成日期2012年4月

南阳理工学院本科毕业设计（论文）

RFID二进制树防碰撞算法设计

学院（系）：

计算机与信息工程学院

专业：

通信工程

学生姓名：

乔军惠

学号：

1

指导教师（职称）：

路新华（讲师）

评阅教师：

完成日期：

2012年4月

南阳理工学院

NanyangInstituteofTechnology

RFID二进制树防碰撞算法设计

【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。

随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。

在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。

在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。

【关键词】：

射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列

Abstract

RFIDisanewlydevelopedtechnologywhichcommunicatesthroughthe—contactRFsignal，soastoachieveobjectiveautomaticidentification．AlongwiththedevelopmentofRFIDtechnology，howtorealizeDataExchangeaccuratelyamongMultipleTargetsatthesametimebecomesthekeyproblemofRFIDtechnology．RFIDanti-collisionalgorithmisthesolutiontotheabovementionedproblems．Inallthealgorithms，binaryalgorithmismostwidelyusedasaninternationalstandardfbritsexactnessofidentincation．Internationalstandardshaveputforwardmanyregulationsonbinaryalgorithm．Itnotonlypromotesthedevelopmentofanti．coUisionalgorithm，butalsob“ngstheconflicttoaunilFiedsolution．TraditionalideasingeneralarehandledbyMCU．AlongwiththedevelopmentofRFIDtechnology，animponantdirectioninthef．utureisthefieldprogrammablegatesarrayFPGA．Askindofintegratedcircuitsthatcanbeprogrammedinthefield，FPGAisfastandprogrammable．AlltheseadVantagesopenupanewefactivewayofRFIDanti．collisionarithmetic．Inviewoftheaboveproblems，thispaperprobesintotheRFIDsystembinarypreventcollisionf．romtheperspectivesofboththeoryandpractice．ItcanbediVidedintothreeaspects：

6rstly，theoreticalresearchonbinaryalgorithm．ItsumsupallthebinaryalgorithmsinbeingandgathertothreecategoryssuchasBasicalgorithm，DynamicalgorithmandBackoffalgorithm．MoreoVer，itExpoundstheideaofthevariousalgorithmsandevaluestheirperf6rmance；secondary，itintroducesanimprovedversionofalgorithmonthebasisofspecincstandard．Thisalgorithmhasf．astrecognition，highefnciencyandgreatlyimproved

theidentificationresults．

KeyWords：

RFID；Anticollision；Read／WriteDeVices；Transponders；FPGA

1引言

1．1RFID技术简介

自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为AutomaticEquipmentIdentification，简称AEI，它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理【ll】。

目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领域的应用更具体的名称为射频识别，英文名为RadioFrequencyIdentification，简写为RFIDI21。

RFID技术通过射频方式进行非接触的双向通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与微波理论的发展，自从上世纪九十年代以来，RFID技术快速发展，得到了广泛的应用，进入新世纪后，各个国家，组织还有企业都加大了对RFID技术的投入，生产了大批相应的产品，在多个领域有了成功的应用案例。

RFID被誉为二十一世纪的十大战略性产业之一，可以预想，未来RFID技术的发展空间是无限广阔的。

1．2RFID系统

1．2．1RFID系统组成

根据实际应用环境，RFID系统结构有多种不同分法，一般来说，一个典型RFID系统包括三个部分：

前端信息载体，数据交换环节，后端应用环境【3】。

在具体应用中，前端信息载体有多个名称，如标签（Tag），智能标签（SmartLabels），射频卡（RFCard）等，本文建议采用应答器（Transponder）这种更具普遍意义的说法。

在RFID系统中，应答器放置在待识别的物体上，它内部存储的信息表征着该物品的独一性。

通常来说，应答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存储器可将应答器分为EEPROM，FROM（铁电存储器），SRAM（静态随机存储器），根据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源供给方式分为无源，半无源，有源。

一般来说，应用最广泛的是无源+集成电路固化+静态随机存储的应答器。

由于在RFID系统中，应答器是大规模生产的。

应答器的典型产品有TI公司的6000系列，Philips公司的I·CODE等。

数据交换环节即RFID系统中的读出写入设备，它是系统的核心部件，是后端应用环境和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫描器，阅读器，编程器等，本文建议采用读写器（Read／WriteDevice）这种更具普遍意义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中写入信息。

根据天线与读写器模块的分离与否，读写器可以分为分离式和集成式，但无论哪种读写器，其基本结构都是类似的，从硬件部分来说，典型的读写器由三块组成：

射频通道模块，控制处理模块，天线。

后端应用环境主要完成数据信息的存储及处理，它实质上就是一个数据管理系统，也是一个全局控制系统，一般由PC机或者工作站组成，同时也包括了应用软件在内，整个后端应用环境负责接收来自读写器的数据，并进行存储以及相应的处理，协同调节多个读写器的工作，该部分在应用中常称为中间件（Savant），它扩展了RFID系统的应用范围和应用能力，是未来RFID系统智能化，大型化发展的有力技术支撑，是RFID技术发展的重要方式。

微软公司近年来也介入了

RFID技术领域，所瞄准的就是RFID系统后端应用的相关软件和服务。

综上所述，一个典型的RFID系统的组成如图所示：

图1.1RFID系统组成

1．2．2RFID系统分类

RFID系统依据不同的标准，可以分为很多类别，各个不同的RFID系统，在工作方式和应用范围上，有着各自不同的特点，在应用时要根据实际需要来选择。

几种典型的分类方式如下所示：

根据作用距离的远近，RFID系统可以分为如下三个方面：

（1）密耦合：

典型的作用范围为0～lcm。

（2）遥耦合：

典型的作用范围为lcm～1m。

（3）远距离系统：

典型的作用范围为l～10m。

根据工作频率的大小，RFID系统可以分为如下四个方面：

（1）低频：

30～300KHz，典型应用为134KHz。

（2）高频：

3～30MHz，典型应用为13．56MHz．

（3）超高频：

300MHz~5．8GHz，典型应用为2．4G。

（4）混频：

多个频率的混合使用，典型应用为134KHz+430MHz。

根据应答器供电方式，RFID系统可以分为三个方面：

（1）无源系统：

由读写器负责给应答器供电。

（2）半无源系统：

应答器内的电池仅做辅助作用。

（3）有源系统：

应答器内置电池负责供给工作电压。

1．2．3RFID系统工作原理

RFID是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路，无线电广播，通信原理等多方面知识RFlD系统中，读写器将要发送的信号调制到载波上，经由射频通道，通过天线发送出去，应答器上的电压根据载波的变化而变化，将该电压信号进行整流和滤波后，得到解调后的数据，这是下行链路的过程，应答器传输的数据的变化控制应答器天线上负载电阻的通断，从而促使读写器天线上电压的变化，从而实现了数据的上行链路传输。

在数据的双向传输过程中，是通过电磁场的相互感应来实现的，该过程也可以用变压器的模型来予以参考。

同时，根据RFID系统的不同，在供电方式上有无源或者有源，调制方式上有幅度调制或者相位调制，数据读取上有电感耦合或者反向散射等区别【5】。

1．3RFID技术现状及其发展

1．3．1RFID技术应用

做为一种新兴的自动识别技术，RFID近年来发展很快，在国内国外都取得

了广泛的应用，主要体现在以下几个领域【6】。

（1）物流管理．

物流管理是RFID技术最具应用前景的领域，近年来提出了一个物联网的概念，意在将全球所有的物品信息都用唯一的电子代码来表示，从而将这些物品都联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产品，用户，企业和政府之间建立但是该应用涉及到的方面太广，技术难度很大，目前还在研究当中。

（2）身份识别

利用RFID技术，将应答器嵌入到身份证，护照等各种证件当中，甚至植入动物皮毛，用来跟踪和识别目标。

这方面应用的典型例子是我国目前实行的二代身份证，它基于ISO／IEC14443标准定义的TYPEB类型卡。

RFID在身份识别方面的主要问题是频段的局限性，一般使用的是l35KHz和13．56MHz的工作频率，这是因为过高的频段容易带来对人体有害的电磁辐射。

（3）防伪应用

应答器在防伪应用中有识别快速，伪造难，成本低等优点，再加上安全认证和加密功能，就可以大大提高伪造的难度和成本，同时，在识别的时刻，可以通过读写器的快速阅读功能，在瞬间得出所有物品的信息，并加以记录和处理。

目前在日本和欧洲已经有了类似的应用。

（4）交通管理

交通管理是RFID最先应用的领域，目前已经拥有了成熟的技术，它利用了应答器便捷快速识别，可靠性高，安全性强的特点，目前主要应用范围是电子车票，高速公路收费等方面，在我国深圳，基于RFID技术的高速公路收费系统已经得到了成功的应用。

RFID技术的应用远不止以上提及的四个方面，它在诸如生产线自动化管理，门禁系统，新生婴儿防错管理，地理信息标识等多个方面都有着广泛应用，可以毫不夸张的说，RFID技术有着良好的发展前景，它孕育的经济效益将是超乎想像的。

1．3．2RFID标准统一化

RFID最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范，因此制约了该项技术在大规模系统中的应用，随着RFID技术的发展，参与到其中的国家，组织，企业也越来越多，目前形成了国际标准化组织ISO，泛在ID中心UID，全球电子产品代码管理中心EPC三大标准体系，这些标准涉及到RFID系统的物理结构，通信协议，防碰撞算法，应用系统接口协议等等多个方面的内容，它们针对不同的频率，基于不同的工作原理，甚至在同样的应用背景下也有着巨大的协议上的区别。

而要建立一个全球互联的RFID产品网络，实现RFID技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着RFID技术的应

用越发广泛，有识之士都意识到并着手解决这个问题，目前主要有两种思路，一是生产出适应于不同标准，多制式兼容的RFID产品，二是制定一个统一的RFID硕十学位论技术标准。

但是RFID本身的技术难度，以及标准带来的经济利益的冲突，使得该目标实施起来非常困难。

由此可见，标准统一化问题的重要性与困难性是并存的，这将是一个任重而道远的过程。

1．3．3RFID防碰撞算法

随着RFID技术的发展，多目标识别成为了一个很重要的应用方向，特别在目标跟踪，物品识别，访问控制等操作中，利用RFID技术，对附着在不同目标上的应答器快速可靠的进行识别，从而大大提高了定位的精确度，管理的自动化促进了整个产业链的发展。

因此，如何保证迅速快捷，又安全可靠的同时识别多个目标，就成为了RFID技术发展的关键性技术。

在RFID系统中，当工作范围内同时出现了多个读写器和多个应答器时，读写器与读写器之间，应答器与应答器之间的相互干扰，称RFID系统发生了碰撞【7】，从而导致数据不能正确的传输，信息无法得到正确的读取，一方面影响了产品的识别，另一方面还可能导致信息的泄露。

在全球信息安全意识广泛普及的背景下，可靠的安全机制成为了RFID技术发展的关键性制约因素，如何有效的解决RFID系统的碰撞问题，成为了技术的关键，对此就需要采用一定的防碰撞算法来对其进行处理。

目前关于防碰撞算法的研究还在进行当中，理论成果已经得出了很多，许多国际标准也对一些成熟的算法进行了规定，但是无论在理论效率还是实际应用上，都还存在很大的改进空间。

1．4课题提出的背景及其意义

早期的RFID技术很少涉及到防碰撞问题，而在近年来，随着RFID技术的发展，应用范围的扩大，使得防碰撞问题日益成为制约RFID发展的关键技术，原因有两个，首先，早期的RFID一般是近距离感应耦合式系统，其操作频率功率普遍较低，读取的速度慢，范围小，所以也较少有发生碰撞的可能，而目前RFID应用中多目标识别成为了主流方向，这就要求实现在多个物品中正确的识别出单个目标；其次，早期的RFID应用没有统一的规范，各个厂家的RFID产品也仅是应用在单个的系统当中，不存在碰撞的可能，而近年来RFID应用迅速发展，各个不同RFID制造商的产品之间的不兼容，也带来了碰撞问题。

总之，由于多目标识别应用的需要，RFID系统防碰撞问题成为了关键技术，为了解决碰撞，可以从硬件和软件两方面着手，由于RFID系统的大规模应用限制了成本，所以，硬件实现是不实际的，因此就需要采用一定的防碰撞算法来予以解决。

依前所述，RFID系统碰撞主要有两种情况，读写器碰撞和应答器碰撞，读写器碰撞是一个应答器同时收到不同读写器发出的命令，应答器碰撞是一个读写器同时给不同应答器发送命令。

在实际的应用当中，应答器由于其低成本的优越,从而得到大量的生产，而读写器往往是固定在系统的某处，来识别多个应答器，所以碰撞的主要情况是应答器碰撞，即一个读写器的工作范围内同时出现了多个应答器，并且对该读写器发出的命令同时予以响应，从而导致读写器无法正确的识别出一个应答器，称该现象为发生了应答器碰撞。

解决碰撞的过程相应的被称为防碰撞，如前所述，该防碰撞过程主要从软件的角度来予以解决，称为防碰撞算法【8】。

在上述前提下，基于应答器的确定型二进制树防碰撞算法是目前最好的一种选择，对其进行研究，是最有实际应用价值的，所以，本文将对其进行理论分析与具体实现，在研究过程中，注重与新一代智能RFID系统的结合，应用拥有强大功能的FPGA（FieldProgrammable

GateArray）做为算法运行的微处理器，这种思路将是未来RFID技术发展的重要方向，RFID技术中的关键算法与先进的电子技术FPGA的结合，将为RFID技术的应用拓开广阔的前景。

1．5本文的主要工作

本文将在RFID技术的前提下，结合当前数字电路设计的主流思路，重点研究RFID的关键技术防碰撞算法，并主要着眼于其中基于应答器的确定性算法，即二进制树防碰撞算法，在理论分析的基础上，对其进行具体实现。

基于上述考虑，论文将分四章来予以讲述，文章结构与内容安排如下：

第1章：

绪论。

系统的介绍了RFID技术，描述了典型RFID系统的结构组成，提出了RFID系统的分类思想，讲述了RFID系统的工作原理，以及其应用范围，重点强调了RFID技术的现状和所面临的主要问题，由此体现了研究RFID关键技术防碰撞算法的意义，明确了本文的主要研究内容。

第2章：

现有RFID二进制树防碰撞算法。

概要性的描述了RFID防碰撞算法，对其进行了分类，重点介绍其中的二进制树防碰撞算法，研究了三种最基本的二进制树算法，对其进行了原理阐述，性能分析，以及实例演示。

第3章：

改进型二进制树防碰撞算法。

二进制树防碰撞算法在多个国际标准中均有规定，基于IS014443标准的TYPEA是其中的一个典型例子，本章首先介绍了涉及到二进制树防碰撞算法的几个标准，其次详细研究了ISOl4443标准对二进制树防碰撞算法的规定，最后提出了在此基础上的改进算法，这也是本章的重点。

第4章：

FPGA实现改进型二进制树防碰撞算法。

FPGA技术是目前数字电路设计的主流思路，利用FPGA做主处理器，是RFID技术发展的方向，本章探讨了这一想法，介绍了FPGA技术的相关要点，并应用FPGA，实现了改进型二进制树防碰撞算法。

2现有RFID二进制树防碰撞算法

2．1RFID防碰撞算法概述

RFID系统的数据通信双方是读写器和应答器，在实际的RFID系统工作时，可能会出现同时多个读写器和多个应答器共存的情况，毫无疑问，此时系统的数据交换就会出现信道与时序上的重叠，也就是发生了碰撞，在多个读写器与多个应答器的射频识别系统中，存在着两种形式的冲突方式，一种是同一应答器同时收到不同读写器发出的命令，另一种是同一个读写器同时收到多个不同应答器返回的数据，前者我们称为读写器碰撞，后者称为应答器碰撞【9】，在实际应用当中，一般是读写器做为主设备，来识别多个应答器，所以发生读写器碰撞的应用场合是不多的，因此下文将着重研究应答器碰撞。

在上述前提下，有两种类型的通信方式，一种是读写器发送的数据同时被多个应答器接收，称为“无线广播”，另一种是多个应答器的数据同时传送给读写器，称为“多路存取”，两者都是无线电技术中长期面临的难题，同时也发展出一系列相应的解决思路，一般来说分为四种，即空分多路（SDMA），码分多路（CDMA）,频分多路（FDMA），时分多路（TDMA），从RFID系统的通信形式、功耗、系统复杂性以及成本多方面综合考虑，时分多路法是最有实际应用价值的，它也是目前RFID防碰撞算法应用中最广泛的一类，时分多路法的基本思想是把整个可供使用的通路容量按时间分配给多个用户，从而达到在不同时隙将各个应答器一

一识别出来的目的【11】。

时分多路法按照能量的供给者可以分为两大类，一类是应答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中RFID系统分类思路中的有源系统和无源系统，根据实际应用情况，无源系统是应用最广泛的一类，所以下文重点研究读写器驱动型的时分多路法。

在该类读写器驱动型时分多路法中，目前最常用的防碰撞算法有两种，一类是基于时隙ALOHA的统计型算法，另一类是基于二进制树的确定型算法，统计型算法的意义是在一定的时隙范围内，系统有可能识别出所有应答器，确定型算法的最大优点是，在一定的时隙范围内，系统一定可以将所有的应答器一一识别出来【13】。

从应用的角度来说，正确有效的识别是实际所需要的，因此下文将着重于二进制树防碰撞算法的研究。

2．2RFID二进制树防碰撞算法概述

2．2．1基本概念

在RFID防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称为“二进制树”，是因为在算法执行过程中，读写器要多次发送命令给应答器，每次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。

为了便于描述算法，声明一些基本概念如下：

首先，在RFID系统当中，每个应答器都是独一无二的，它们的独立性通过唯一的自身序列号来体现，该序列号在不同的标准中有不同的名称，如EPC标准中称其为电子产品代码EPC，即英文ElectronicProductCode的缩写，IS014443标准中称其为唯一标识码UID，即英文UniqueIdentmer的缩写【15】。

事实上，这些都是对应答器序列号的名称描述，因为下文涉及到的防碰撞算法是普遍意义上的，既包括了EPC标准中的规定，也包括了ISO标准中的规定，因此在本文对普遍意义上的防碰撞算法的描述过程中，统一用序列号SN（SerialNumber）来描述上述概念，同时，序列号的长度，格式，以及编码方式也是各个标准各自差异的，为了说明的便利，统一定义为8位长度的

二进制码。

如图2．1所示。

图2．1应答器序列号数据格式

读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部位，此时的传输顺序定义为：

先发送低位，再发送高位。

在读写器或者应答器内部，对数据进行比较