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

南阳理工学院本科生毕业设计（论文）学院（系）：计算机与信息工程学院专业：通信工程学生：乔军一指导教师：路新华完成日期2012年4—月南阳理工学院本科毕业设计（论文）RFID二进制树防碰撞算法设计学院（系）：计算机与信息工程学院专业：通信工程学生姓名：乔军惠学号：104060820064指导教师（职称）：路新华（讲师）评阅教师：完成日期：2012年4月南阳理工学院NanyangInstituteofTechnologyRFID二进制树防碰撞算法设计【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列AbstractRFIDisanewlydevelopedtechnologywhichcommunicatesthroughthe—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,highefnciencyandgreatlyimprovedtheidentificationresults．KeyWords:RFID;Anticollision;Read/WriteDeVices;Transponders;FPGATOC\o"1-5"\h\z1引言61.1RFID技术简介61.2RFID系统61.2.1RFID系统组成61.2.2RFID系统分类71.2.3RFID系统工作原理81.3RFID技术现状及其发展8.3.1RFID技术应用83.2RFID标准统一化93.3RFID防碰撞算法91.4课题提出的背景及其意义91.5本文的主要工作102现有RFID二进制树防碰撞算法111RFID防碰撞算法概述112RFID二进制树防碰撞算法概述112.1基本概念112.2性能指标122.3算法分类133基本二进制树防碰撞算法143.1算法思路143.2实例演示153.3性能评价174动态二进制树防碰撞算法194.1算法思路194.2实例演示214.3性能评价225退避式二进制树防碰撞算法225.1算法思路225.2实例演示245.3性能评价252.6本章小结253改进型二进制树防碰撞算法253.1涉及二进制树算法的国际标准251.1IS015693251.2IS014443262IS014443标准二进制树防碰撞算法272.1基本概念272.2算法思路283改进型二进制树防碰撞算法323.1改进方向323.2基本概念323.4实例演示374本章小结394FPGA实现改进型二进制树防碰撞算法401FPGAi术401.1FPGA简介401.2FPGA设计流程401.3FPGA设计工具421.4FPGA设计语言451.5TestBench验证平台452RFID系统中的防碰撞模块463FPGAS现算法流程464曼彻斯特解码模块475命令处理模块505.1请求命令处理505.2防碰撞命令处理515.3选择命令处理535.4去选择命令处理536命令选择模块537数据存储模块558密勒编码模块569模块连接5710本章小结58结论58致谢621引言1.1RFID技术简介自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为AutomaticEquipmentIdentification,简称AEI,它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理【11】。目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领域的应用更具体的名称为射频识别，英文名为RadioFrequencyIdentification,简写为RFIDI21。RFID技术通过射频方式进行非接触的双向通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与微波理论的发展，自从上世纪九十年代以来，RFID技术快速发展，得到了广泛的应用，进入新世纪后，各个国家，组织还有企业都加大了对RFID技术的投入，生产了大批相应的产品，在多个领域有了成功的应用案例。RFID被誉为二十一世纪的十大战略性产业之一，可以预想，未来RFID技术的发展空间是无限广阔的。2RFID系统.1RFID系统组成根据实际应用环境，RFID系统结构有多种不同分法，一般来说，一个典型RFID系统包括三个部分：前端信息载体，数据交换环节，后端应用环境【3】。在具体应用中，前端信息载体有多个名称，如标签（Tag）,智能标签（SmartLabels）,射频卡（RFCard）等，本文建议采用应答器（Transponder）这种！（具普遍意义的说法。在RFID系统中，应答器放置在待识别的物体上，它内部存储的信息表征着该物品的独一性。通常来说，应答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存储器可将应答器分为EEPROMFROM^电存储器），SRAM1|态随机存储器），根据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源供给方式分为无源，半无源，有源。一般来说，应用最广泛的是无源+集成电路固化+静态随机存储的应答器。由于在RFID系统中，应答器是大规模生产的。应答器的典型产品有TI公司的6000系列，Philips公司的I•COD萼。数据交换环节即RFID系统中的读出写入设备，它是系统的核心部件，是后端应用环境和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫描器，阅读器，编程器等，本文建议采用读写器（Read/WriteDevice）这种更具普遍意义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中写入信息。根据天线与读写器模块的分离与否，读写器可以分为分离式和集成式，但无论哪种读写器，其基本结构都是类似的，从硬件部分来说，典型的读写器由三块组成：射频通道模块，控制处理模块，天线。后端应用环境主要完成数据信息的存储及处理，它实质上就是一个数据管理系统，也是一个全局控制系统，一般由PC机或者工作站组成，同时也包括了应用软件在内，整个后端应用环境负责接收来自读写器的数据，并进行存储以及相应的处理，协同调节多个读写器的工作，该部分在应用中常称为中间件(Savant),它扩展了RFID系统的应用范围和应用能力，是未来RFID系统智能化，大型化发展的有力技术支撑，是RFID技术发展的重要方式。微软公司近年来也介入了RFID技术领域，所瞄准的就是RFID系统后端应用的相关软件和服务。综上所述，一个典型的RFID系统的组成如图所示：图1.1RFID系统组成.2RFID系统分类RFID系统依据不同的标准，可以分为很多类别，各个不同的RFID系统，在工作方式和应用范围上，有着各自不同的特点，在应用时要根据实际需要来选择。几种典型的分类方式如下所示：根据作用距离的远近，RFID系统可以分为如下三个方面：(1)密耦合：典型的作用范围为0〜lcm。⑵遥耦合：典型的作用范围为lcm〜1m(3)远距离系统：典型的作用范围为l〜10m根据工作频率的大小，RFID系统可以分为如下四个方面：(1)低频：30〜300KHz典型应用为134KHz⑵高频：3〜30MHz典型应用为13.56MHz⑶超高频：300MHz~58GHz典型应用为2.4G⑷混频：多个频率的混合使用，典型应用为134KHz+430MHZ根据应答器供电方式，RFID系统可以分为三个方面：(1)无源系统：由读写器负责给应答器供电。⑵半无源系统：应答器内的电池仅做辅助作用。(3)有源系统：应答器内置电池负责供给工作电压。1.2.3RFID系统工作原理RFID是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路，无线电广播，通信原理等多方面知识RF1D系统中，读写器将要发送的信号调制到载波上，经由射频通道，通过天线发送出去，应答器上的电压根据载波的变化而变化，将该电压信号进行整流和滤波后，得到解调后的数据，这是下行链路的过程，应答器传输的数据的变化控制应答器天线上负载电阻的通断，从而促使读写器天线上电压的变化，从而实现了数据的上行链路传输。在数据的双向传输过程中，是通过电磁场的相互感应来实现的，该过程也可以用变压器的模型来予以参考。同时，根据RFID系统的不同，在供电方式上有无源或者有源，调制方式上有幅度调制或者相位调制，数据读取上有电感耦合或者反向散射等区别【51c1.3RFID技术现状及其发展1.3.1RFID技术应用做为一种新兴的自动识别技术，RFID近年来发展很快，在国内国外都取得了广泛的应用，主要体现在以下几个领域【6】。(1)物流管理.物流管理是RFID技术最具应用前景的领域，近年来提出了一个物联网的概念，意在将全球所有的物品信息都用唯一的电子代码来表示，从而将这些物品都联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产品，用户，企业和政府之间建立但是该应用涉及到的方面太广，技术难度很大，目前还在研究当中。(2)身份识别利用RFID技术，将应答器嵌入到身份证，护照等各种证件当中，甚至植入动物皮毛，用来跟踪和识别目标。这方面应用的典型例子是我国目前实行的二代身份证，它基于ISO/IEC14443标准定义的TYPEB类型卡。RFID在身份识别方面的主要问题是频段的局限性，一般使用的是135KHz和13.56MHz勺工作频率，这是因为过高的频段容易带来对人体有害的电磁辐射。(3)防伪应用应答器在防伪应用中有识别快速，伪造难，成本低等优点，再加上安全认证和加密功能，就可以大大提高伪造的难度和成本，同时，在识别的时刻，可以通过读写器的快速阅读功能，在瞬间得出所有物品的信息，并加以记录和处理。目前在日本和欧洲已经有了类似的应用。⑷交通管理交通管理是RFID最先应用的领域，目前已经拥有了成熟的技术，它利用了应答器便捷快速识别，可靠性高，安全性强的特点，目前主要应用范围是电子车票，高速公路收费等方面，在我国深圳，基于RFID技术的高速公路收费系统已经得到了成功的应用。RFID技术的应用远不止以上提及的四个方面，它在诸如生产线自动化管理，门禁系统，新生婴儿防错管理，地理信息标识等多个方面都有着广泛应用，可以毫不夸张的说，RFID技术有着良好的发展前景，它孕育的经济效益将是超乎想像的3.2RFID标准统一化RFID最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范，因此制约了该项技术在大规模系统中的应用，随着RFID技术的发展，参与到其中的国家，组织，企业也越来越多，目前形成了国际标准化组织ISO,泛在ID中心UID,全球电子产品代码管理中心EPC三大标准体系，这些标准涉及到RFID系统的物理结构，通信协议，防碰撞算法，应用系统接口协议等等多个方面的内容，它们针对不同的频率，基于不同的工作原理，甚至在同样的应用背景下也有着巨大的协议上的区别。而要建立一个全球互联的RFID产品网络，实现RFID技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着RFID技术的应用越发广泛，有识之士都意识到并着手解决这个问题，目前主要有两种思路，一是生产出适应于不同标准，多制式兼容的RFID产品，二是制定一个统一的RFID硕十学位论技术标准。但是RFID本身的技术难度，以及标准带来的经济利益的冲突，使得该目标实施起来非常困难。由此可见，标准统一化问题的重要性与困难性是并存的，这将是一个任重而道远的过程。3RFID防碰撞算法随着RFID技术的发展，多目标识别成为了一个很重要的应用方向，特别在目标跟踪，物品识别，访问控制等操作中，利用RFID技术，对附着在不同目标上的应答器快速可靠的进行识别，从而大大提高了定位的精确度，管理的自动化促进了整个产业链的发展。因此，如何保证迅速快捷，又安全可靠的同时识别多个目标，就成为了RFID技术发展的关键性技术。在RFID系统中，当工作范围内同时出现了多个读写器和多个应答器时，读写器与读写器之间，应答器与应答器之间的相互干扰，称RFID系统发生了碰撞【7】，从而导致数据不能正确的传输，信息无法得到正确的读取，一方面影响了产品的识别，另一方面还可能导致信息的泄露。在全球信息安全意识广泛普及的背景下，可靠的安全机制成为了RFID技术发展的关键性制约因素，如何有效的解决RFID系统的碰撞问题，成为了技术的关键，对此就需要采用一定的防碰撞算法来对其进行处理。目前关于防碰撞算法的研究还在进行当中，理论成果已经得出了很多，许多国际标准也对一些成熟的算法进行了规定，但是无论在理论效率还是实际应用上，都还存在很大的改进空间。4课题提出的背景及其意义早期的RFID技术很少涉及到防碰撞问题，而在近年来，随着RFID技术的发展，应用范围的扩大，使得防碰撞问题日益成为制约RFID发展的关键技术，原因有两个，首先，早期的RFID一般是近距离感应耦合式系统，具操作频率功率普遍较低，读取的速度慢，范围小，所以也较少有发生碰撞的可能，而目前RFID应用中多目标识别成为了主流方向，这就要求实现在多个物品中正确的识别出单个目标；其次，早期的RFID应用没有统一的规范，各个厂家的RFID产品也仅是应用在单个的系统当中，不存在碰撞的可能，而近年来RFID应用迅速发展，各个不同RFID制造商的产品之间的不兼容，也带来了碰撞问题。总之，由于多目标识别应用的需要，RFID系统防碰撞问题成为了关键技术，为了解决碰撞，可以从硬件和软件两方面着手，由于RFID系统的大规模应用限制了成本，所以，硬件实现是不实际的，因此就需要采用一定的防碰撞算法来予以解决。依前所述，RFID系统碰撞主要有两种情况，读写器碰撞和应答器碰撞，读写器碰撞是一个应答器同时收到不同读写器发出的命令，应答器碰撞是一个读写器同时给不同应答器发送命令。在实际的应用当中，应答器由于其低成本的优越，从而得到大量的生产，而读写器往往是固定在系统的某处，来识别多个应答器，所以碰撞的主要情况是应答器碰撞，即一个读写器的工作范围内同时出现了多个应答器，并且对该读写器发出的命令同时予以响应，从而导致读写器无法正确的识别出一个应答器，称该现象为发生了应答器碰撞。解决碰撞的过程相应的被称为防碰撞，如前所述，该防碰撞过程主要从软件的角度来予以解决，称为防碰撞算法【8】。在上述前提下，基于应答器的确定型二进制树防碰撞算法是目前最好的一种选择，对其进行研究，是最有实际应用价值的，所以，本文将对其进行理论分析与具体实现，在研究过程中，注重与新一代智能RFID系统的结合，应用拥有强大功能的FPGA(FieldProgrammableGateArray)做为算法运行的微处理器，这种思路将是未来RFID技术发展的重要方向，RFID技术中的关键算法与先进的电子技术FPGA勺结合，将为RFID技术的应用拓开广阔的前景。5本文的主要工作本文将在RFID技术的前提下，结合当前数字电路设计的主流思路，重点研究RFID的关键技术防碰撞算法，并主要着眼于其中基于应答器的确定性算法，即二进制树防碰撞算法，在理论分析的基础上，对其进行具体实现。基于上述考虑，论文将分四章来予以讲述，文章结构与内容安排如下：第1章：绪论。系统的介绍了RFID技术，描述了典型RFID系统的结构组成，提出了RFID系统的分类思想，讲述了RFID系统的工作原理，以及其应用范围，重点强调了RFID技术的现状和所面临的主要问题，由此体现了研究RFID关键技术防碰撞算法的意义，明确了本文的主要研究内容。第2章:现有RFID二进制树防碰撞算法。概要性的描述了RFID防碰撞算法，对其进行了分类，重点介绍其中的二进制树防碰撞算法，研究了三种最基本的二进制树算法，对其进行了原理阐述，性能分析，以及实例演示。第3章：改进型二进制树防碰撞算法。二进制树防碰撞算法在多个国际标准中均有规定，基于IS014443标准的TYPEA^其中的一个典型例子，本章首先介绍了涉及到二进制树防碰撞算法的几个标准，其次详细研究了ISOl4443标准对二进制树防碰撞算法的规定，最后提出了在此基础上的改进算法，这也是本章的重点。第4章：FPGAS现改进型二进制树防碰撞算法。FPGAfc术是目前数字电路设计的主流思路，利用FPG龈主处理器，是RFID技术发展的方向，本章探讨了这一想法，介绍了FPGAfc术的相关要点，并应用FPGA实现了改进型二进制树防碰撞算法。2现有RFID二进制树防碰撞算法1RFID防碰撞算法概述RFID系统的数据通信双方是读写器和应答器，在实际的RFID系统工作时，可能会出现同时多个读写器和多个应答器共存的情况，毫无疑问，此时系统的数据交换就会出现信道与时序上的重叠，也就是发生了碰撞，在多个读写器与多个应答器的射频识别系统中，存在着两种形式的冲突方式，一种是同一应答器同时收到不同读写器发出的命令，另一种是同一个读写器同时收到多个不同应答器返回的数据，前者我们称为读写器碰撞，后者称为应答器碰撞【9】，在实际应用当中，一般是读写器做为主设备，来识别多个应答器，所以发生读写器碰撞的应用场合是不多的，因此下文将着重研究应答器碰撞。在上述前提下，有两种类型的通信方式，一种是读写器发送的数据同时被多个应答器接收，称为“无线广播”，另一种是多个应答器的数据同时传送给读写器，称为“多路存取”，两者都是无线电技术中长期面临的难题，同时也发展出一系列相应的解决思路，一般来说分为四种，即空分多路（SDMA）码分多路（CDMA）,频分多路（FDMA）,时分多路（TDMA）从RFID系统的通信形式、功耗、系统复杂性以及成本多方面综合考虑，时分多路法是最有实际应用价值的，它也是目前RFID防碰撞算法应用中最广泛的一类，时分多路法的基本思想是把整个可供使用的通路容量按时间分配给多个用户，从而达到在不同时隙将各个应答器一一识别出来的目的【11】。时分多路法按照能量的供给者可以分为两大类，一类是应答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中RFID系统分类思路中的有源系统和无源系统，根据实际应用情况，无源系统是应用最广泛的一类，所以下文重点研究读写器驱动型的时分多路法。在该类读写器驱动型时分多路法中，目前最常用的防碰撞算法有两种，一类是基于时隙ALOHA勺统计型算法，另一类是基于二进制树的确定型算法，统计型算法的意义是在一定的时隙范围内，系统有可能识别出所有应答器，确定型算法的最大优点是，在一定的时隙范围内，系统一定可以将所有的应答器一一识别出来【13］。从应用的角度来说，正确有效的识别是实际所需要的，因此下文将着重于二进制树防碰撞算法的研究。2RFID二进制树防碰撞算法概述2.1基本概念在RFID防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称为“二进制树”，是因为在算法执行过程中，读写器要多次发送命令给应答器，每次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。为了便于描述算法，声明一些基本概念如下：首先，在RFID系统当中，每个应答器都是独一无二的，它们的独立性通过唯一的自身序列号来体现，该序列号在不同的标准中有不同的名称，如EPC标准中称其为电子产品代码EPG即英文ElectronicProductCode的缩写，IS014443标准中称其为唯一标识码UID,即英文UniqueIdentmer的缩写【15］。事实上，这些都是对应答器序列号的名称描述，因为下文涉及到的防碰撞算法是普遍意义上的，既包括了EPCB准中的规定，也包括了ISO标准中的规定，因此在本文对普遍意义上的防碰撞算法的描述过程中，统一用序列号SN(SerialNumber)来描述上述概念，同时，序列号的长度，格式，以及编码方式也是各个标准各自差异的，为了说明的便利，统一定义为8位长度的二进制码。如图2.1所示。MSB>LSBb8b7b6b5b4b3b2bl图2.1应答器序列号数据格式读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部位，此时的传输顺序定义为：先发送低位，再发送高位。在读写器或者应答器内部，对数据进行比较时，遵循这样的原则，即按位依次比较，先比较低位，再比较高位，约定0<1,根据这个比较顺序，在判断大小时，低位数据优先，即两数A,B相比较，从低位开始的第一个不相等位的大小决定了两数的大小，只有当两个数的全部位均相等时，两数才相等。2.2性能指标定义碰撞解决时期CRI,即CollisionResolutionInterval【16】，即解决一个读写器工作范围内碰撞所需要的时隙数，对二进制树算法的评价，一些常用的性能指标如下所示【17】：首先是算法执行效率=，定义如下：在算法执行过程，一共隔个时隙，识别了n个应答器，则"二n/〃表示算法的执行效率。分析如下：n=l,显而易见，在第一个时隙内不发生碰撞，可以成功识别该应答器，「二1。n>2,由于应答器序列号的唯一性，将有碰撞发生，在一个时隙内发生碰撞的概率p是一个随机事件，在n个应答器信息包中i个发生碰撞的概率为：给出i个碰撞，则CRI的长度为：|i=1+Iji+—1Kt22其中1是n个信息包最初的一个时隙，必是i个碰撞的顺利传输的时隙，乙-1

是n-i个无碰撞传输的时隙。由上式可知，心是逐渐递归的，通过递归可得:(23)1+£。(姻+£0伽)J(23)1+£[05)+。…(切必=一」印n>’1-。。伽)-勿〃)’根据式(2.3),上式可化为：2(左-1)(7)上2(左-1)(7)上打之2(2.4)由此可见，〃是关于p的函数，则==n/〃也是关于p的函数，一般情况下，可以参考二项分布，将p取为1/2。算法的第二个重要的性能指标是稳定性，显然，基于TDMA勺二进制树防碰撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期CRI,定义一个随机变量3外，表示第k个CRI的长度，这些小、A=oj,2形成一个马尔可夫链(Markovchain),因为第*+1个CRI的长度由它开始的第一个时隙传输的信息，也就是在k个CRI区间内到达的信息包决定的，所以，如果马尔可夫链满足遍历性分布，那么这个系统就可以说是稳定的。马尔可夫链遍历性分布要满足下列两个条件【18】：TOC\o"1-5"\h\z)|E[上(由+1)-£(*)]|£(6=1(2.5)(2)lirnsup£[Z(Jt+1)|<Z(Jt)=/)]<0(2.6)这里有：胤〃4+1)|(〃口=3=£乙等;P.7)〃也就是n个信息包从发生碰撞开始传输的CRI区间长度的数学期望，人是在一个时隙内到达这个系统信息包的期望值，该过程属于泊松过程【l9]。一般来说，在二进制树防碰撞算法中，系统都能够满足马尔可夫链的两个遍历性分布条件，即作为一种确定型的算法，二进制树防碰撞算法是稳定的。算法的第三个重要性能是系统通信复杂度，显而易见，系统的通信双方是读写器与应答器，则通信复杂度也应该从这两方面着手考虑，即读写器与应答器各自发送的数据位的位数。该指标的评价标准是基于能量消耗的角度的，即发送的数据信息量越少，则整个系统消耗的能量也越少，这显然是一个理想的效果。2.3算法分类在基本的二进制树搜索算法的基础上，有多种形式的二进制树搜索算法，它们之间主要的区别在于命令的数据形式，主要有两点。⑴命令参数是1bit数据，还是多bit数据。⑵命令参数长度是固定的，还是变化的。图2.2是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按照命令参数分为1bit和多bit,根据传输的命令参数的长度分为定长二进制树和动态二进制树两种，根据二进制树遍历时是一轮前进到底的还是退避返回的分为前进二进制树和退避二进制树两种。需要说明的是，这只是一个大略的分类法,主要目的在于说明二进制树分类的基本原则。事实上，分类所得的这些算法中也有互相重合的，如动态二进制树算法既可以采用前进思路，也可以采用退避思路。另外，在具体应用时，可能还存在多种不同的说法，如lbit长二进制树中还有修正二进制树MBBT加强二进制树EBB邙区别【20】。图2.2二进制树算法分类2.3基本二进制树防碰撞算法2.3.1算法思路定义两个具有普遍意义的命令来描述算法：(1)请求命令Request(SN):该命令携带一个参数SN应答器接收到该命令，将自身的SN与接收到的SN比较，若小于或者等于，则该应答器回送其SN给读写器。注：Request(SN)初始值设为Request(11111111)。(2)休眠命令Sleep(SN)：该命令携带一个参数SN应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进入休眠状态，也即是不再响应Request命令，除非该应答器通过先离开读写器工作范围再进入的方式重新上电，才可以再次响应Request命令。基本二进制树算法的流程图如图2,3所示：

图2.3基本二进制树算法流程基本二进制树算法的步骤如下：(1)应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答器的序列号均小于该最大序列号，所以在同一时刻将自身序列号返回给读写器。(2)由于应答器序列号的唯一性,当应答器数目不小于两个时,必然发生碰撞.发生碰撞时，将最大序列号中对应的碰撞起始位设置为O,低于该位者不变，高于该位者设置为l。(3)读写器将处理后的序列号发送给应答器，应答器序列号与该值比较，小于或等于该值者，将自身序列号返回给读写器。(4)循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进行正常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不再响应读写器请求命令。也就是说，下一次读写器再发最大序列号时，该应答器不再响应。(5)重复上述过程，即可按序列号从小到大依次识别出各个应答器。注：第五步时，从步骤1开始重复，也就是说，读写器识别完一个应答器后，将重新发送原始的最大序列号。2.3.2实例演示根据上述分析，下面给出一个基本二进制树搜索算法的实例演示，如图2.4所示。假设RFID系统中有一个读写器R,四个应答器Tl(10100101),T2(10101101),T3(11010101),T4(11101101),在某一时刻，四个应答器同时进入读写器的工作范围之内，读写器发出命令，四个应答器同时响应，由于其序列号SN的唯一性，将发生应答器碰撞，从而启动防碰撞循环，分析如下：图2.4基本二进制树算法实例注：图中共有四轮循环，依次识别出四个应答器，分别以不同格式的线条表示，并加有循环轮次的数字标识。(1)启动第一轮循环，读写器发送Request(11111111)命令，所有应答器响应该命令，将自身序列号与该SN(11111111)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXX101,其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0,低于该位者不变，高于该位者置1,得到11110101,作为下一次Request命令携带的参数值，即Request(11110101)。(2)读写器发送Request(11110101)命令，所有应答器响应该命令，将自身序列号与该SN(11110101)比较,其中T1(10100101),T3(11010101)的序列号小于该值，则T1,T3返回自身序列号给读写器，在读写器接收端发生碰撞，读写器检测到返回数据为1XXX0101,读写器做如下处理：将碰撞起始位D5位置0,低于该位者不变，高于该位者置1,得到11100101,作为下一次Request命令携带的参数值，即Request(11100101)。(3)读写器发送Request(11100101)命令，所有应答器响应该命令，将自身序列号与该SN(11100101)比较，其中T1(10100101)的序列号小于该值，则T1返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为10100101,读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即S1eep(10100101)。(4)读写器发送S1eep(10100101)命令，所有应答器响应该命令，将自身序列号与该SN(10100111)比较，其中T1(10100101)的序列号等于该值，则T1执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。(5)启动第二轮循环，读写器发送Request(111l1111)命令，除T1外所有应答器响应该命令，将自身序列号与该SN(11111l11)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXX101,其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0,低于该位者不变，高于该位者置1,得到11110101,作为下一次Request命令携带的参数值，即Request(11110101)。(6)读写器发送Request(11110101)命令，.除T1外所有应答器响应该命令，将自身序列号与该SN(11110101)比较，其中T3(11010101)的序列号小于该值，则T3返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为11010101,读写器做如下处理：将该数值作为下一次S1eep命令携带的参数值，即S1eep(11010101)。⑺读写器发送S1eep(11010101)命令，所有应答器响应该命令，将自身序列号与该SN(11010101)比较，其中T3(11010101)的序列号等于该值，则T3执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。(8)启动第三轮循环，读写器发送Request(11111111)命令，除T1,T3外所有应答器响应该命令，将自身序列号与该SN(11111111)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1X101101,其中x表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D7位置0,低于该位者不变，高于该位者置1,得到10101101,作为下一次Request命令携带的参数值，即Request(10101101)。(9)读写器发送Request(10101101)命令，除Tl,T3外所有应答器响应该命令，将自身序列号与该SN(10101101)比较,其中T2(10101101)的序列号等于该值，则T2返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为10101101,读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即S1eep(10101101)。(10)读写器发送S1eep(10101101)命令，所有应答器响应，将自身序列号与该SN(10101101)比较,其中T2(10101101)的序列号等于该值,则T2执行该命令,进入休眠状态，即除非重新上电，否则不再响应Request命令。(11)启动第四轮循环，读写器发送Request(11111111)命令，除Tl,T3,T2外所有应答器响应该命令，将自身序列号与该SN(11111111)比较，均小于该值，则所有应答器均返回自身序列号给读写器，因为只有应答器T4返回数据，所以在读写器接收端不发生碰撞，读写器检测到返回数据为11101101,读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即S1eep(11101101)。(12)读写器发送S1eep(11101101)命令，所有应答器响应，将自身序列号与该SN(11101101)比较，其中T4(11101101)的序列号等于该值，则T4执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。2.3.3性能评价假设工作范围内有N个应答器存在，通过基本二进制树搜索算法进行防碰撞操作，依次识别出所有应答器。循环次数m定义为在整个防碰撞循环过程中的循环轮次，也即是二进制树的遍历次数。根据前面的分析可知，做为一种确定性的算法，基本二进制树一轮循环总能识别出一个应答器，所以在n个应答器的前提下，经过n次循环可以识别出N个应答器，所以整个过程中的循环次数为n.搜索次数加定义为算法执行命令的次数。也即是二进制树的节点数目。该值可以用式子廷2八。廷即+1来表示【21】，其中Integ表示取整。通信时间t定义为数据交换的时间，也即是命令执行的时间。假设有n个应答器，从读写器到应答器的传输时间为tl,反之为t2.总时间为t,则传输的总时间t可以用式2.8来表示【22】：，=(2界-0(”+⑵(2.8)数学归纳法证明如下：假设只有一个应答器，则读写器发送命令，应答器响应，无碰撞，识别出应答器。/=ri+/in=1(2.9)假设有两个应答器，则读写器发送命令，两个应答器响应，发生碰撞，为第一次过程，该时间为：f-Zi+Zi(2.10)读写器修改命令参数，发出命令，仅一个应答器响应，则识别出该应答器，这一次过程时间与前一次一致，读写器再发送命令，最后一个应答器响应，得到识别，时间也是一样的，则总时间为：/=3(/i+h)n=2(2.11)当有n个应答器时，假设识别总时间为：/=(2打-IX^i4打)(2.12)则当n+1个应答器时，读写器首先发送命令，应答器全体响应，发生碰撞，这个过程时间为：』十门(2.13)读写器修改命令参数，发出命令，k个应答器响应，余下p个不响应，k+p=n+l,则识别出该k个应答器需要时间为：£=(盐-0(4+门)(2J4)再识别余下p个需要时间为：/=(2p-l)(/r+f2)(2J5)则这两者时间之和为：t=[2(k+p)-2](/i+门)=[2(n+l)-2](rt+n)(2J6)=2n(n+n)加上前一次的.t1+t2，总时间为:t=(2n+lX/i+n)=[2(«+1)-l]«i+n)(2J7)得证。因为基本二进制树算法中每次传输的序列号SN长度相同，门小，所以有：r=2h(2/i-l)(2.18)基本二进制树搜索算法是所有二进制树算法的基础，分析基本二进制树搜索算法的性能可知，对于固定数目的应答器，二进制树算法的性能主要取决于二进制树的节点数目和单次传输命令参数的时间，事实上，二进制树的节点数目与应答器分组的思路是直接相关的，而单次传输命令参数的时间则取决于该命令包含的数据位数。所以，要改善二进制树算法的性能，就必须从这两点着手，现有的二进制树搜索算法有很多种，它们都是在基本二进制树搜索算法的基础上加以改进得来的，根据前述分析，主要的改进思路有两个：(1)减少每次通信过程中的数据传输位数。(2)减少应答器分组的询问次数。本文中，定义根据第一个思路得来的算法为动态二进制树，它的一个典型应用为ISO14443TYPE-A匚进制树搜索算法。定义根据第二个思路得来的算法为退避式二进制树,它的一个典型应用为EPJ进制树搜索算法。2.4动态二进制树防碰撞算法2.4.1算法思路定义两个具有普遍意义的命令来描述算法：(1)请求命令Request(saj),该命令携带一个参数SN,长度为m==应答器接收到该命令，将自身的SN中的前1〜x位与接收到的比较，若两者相等，则该答器返回其SN的剩余位给读写器。注：Request(smt)初始值设为Request(1l111111),约定当参数值为全1时，应答器返回完整序列号。(2)休眠命令Sleep(SN),该命令携带一个参数SN应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进入休眠状态，也即是不再响应Request命令，除非该应答器通过先离开读写器工作范围再进入的方式重新上电，才可以再次响应Request命令。动态二进制树算法的流程与基本二进制树算法是一致的，它们的区别在于：基本二进制树算法中，应答器返回完整序列号，而动态二进制树算法中，应答器只返回序列号的有效部分；同样，基本二进制树算法中，读写器生成新Request命令时，其命令参数长度是固定为8位的，而动态二进制树算法中，该命令参数长度是根据应答器返回的序列号来动态变化的。动态二进制树算法的流程如图2.5所示：图2.5动态二进制树算法流程事实上，动态二进制树对基本二进制树的改进是基于如下考虑的，在基本二进制树的分析过程中可见，算法的核心部分即新命令参数的生成，是根据是否发生碰撞，以及碰撞位来决定的，特别是新Request命令参数的生成是由碰撞的起始位来确定的，而碰撞的起始位的得到只需要应答器序列号中包括碰撞起始位在内的部分位即可，把这些位称为序列号的有效位，同样，新Request命令参数也为包括碰撞起始位（设为0）在内的部分位，综合如下：若选择高位加碰撞起始位（设为0）,则算法为应答器序列号对应位小于这些位的数值者，返回剩余低位，若选择碰撞起始位（设为0）加低位，则算法为应答器序列号对应位等于这些位的数值者，返回剩余高位，从而读写器的新Request命令参数与应答器返回的序列号有效部分组合起来，可以得到一个完整的应答器序列号。这两种选择方式并没有本质区别，在本文中，采取其中的一种，即：读写器检测到碰撞后，将碰撞起始位置0,低位不变，从而将碰撞起始位（置为O）加低位作为新Request命令参数，应答器响应，从低位开始比较，若对应位等于该参数，则返回剩余位给读写器，如果只有个应答器响应，读写器检测到无碰撞发生，则将上一次发出的Request命令参数与应答器返回的剩余位组合起来，作为新的Sleep命令参，该参数也即是刚刚做出响应的这个应答器的序列号。注：如果上一次发出的Request为全l,则表明读写器工作范围内只有一个应答器，此时应答器返回数据为完整序列号，以该序列号作为Sleep命令参数。动态二进制树算法的步骤如下：（1）应答器进入读写器工作范围，读写器发出一个最大序列号，约定此时所有应答器均返回完整序列号，则同一时刻应答器将自身序列号发回给读写器。（2）由于应答器序列号的唯一性，当应答器数目不小于两个时，必然发生碰撞。发生碰撞时，将最大序列号中对应的碰撞起始位置为00低于该位者不变。(3)读写器将处理后的碰撞起始位与低位发送给应答器，应答器序列号与该值比较，等于该值者，将自身序列号中剩余位发回.(4)循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进行正常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不对读写器请求命令起响应。(5)重复上述过程，即可按序列号从小到大依次识别出各个应答器.2.4.2实例演示动态二进制树算法的实例演示如图2.6所示，基本设置同基本二进制树算法：图2.6动态二进制树算法实例(1)启动第一轮循环，读写器发送Request(11111111)命令，所有应答器响应该命令，按照约定，命令参数为全1时，所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXX101,其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0,低于该位者不变，得到0101,则下一次Request命令携带的参数值，即Request(0101)。(2)读写器发送Request(0101)命令，所有应答器响应，将自身序列号与该SN(0101)比较，其中T1(10100101),T3(11010101)的序列号低四位等于该值，则T1,T3返回剩余位给读写器，在读写器接收端发生碰撞，读写器检测到返回数据为1XXX,读写器做如下处理：将碰撞起始位D5位置0,低于该位者不变，得到00101,作为下一次Request命令参数值，即Request(00101)。(3)读写器发送Request(00101)命令，所有应答器响应，将自身序列号与该SN(00101)比较,其中T1(10100101)的序列号对应位等于该值，则T1返回剩余序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为101,读写器做如下处理：将上一次Request(00101)命令参数00101与返回数据101组合起来，作为下一次Sleep命令携带的参数值，即S1eep(10100101)。(4)读写器发送S1eep(10100101)命令，所有应答器响应该命令，将自身序列号与该SN(10100101)比较，其中T1(10100101)的序列号等于该值，则Tl执行该命令，进入底眠状态，即除非重新上山否则不再响应Request命令。(5)启动新一轮循环，重复上述步骤，总计12步后，依次识别出T1,T3,T2,T4,参数变化过程见图2.6中标示，具体内容不再详述。2.4.3性能评价与3.3.2基本二进制树实例图比较可知，动态二进制树算法的识别过程中，节点数目，循环轮次都是一样的，但是每次循环过程中，读写器命令与应答器指令所携带的参数都是在动态改变长度的，所以动态算法的优势主要体现在两个方面，一是算法执行过程中数据传输时间；二是算法执行过程中数据信息量。根据分析，算法执行过程中，读写器与应答器传送的数据主体是应答器的序列号，为了便于分析，假定数据交换过程中，双方只传送序列号SN则在基本算法中，读写器与应答器均传送了序列号全部长度，而在动态算法中，读写器传送序列号的部分位，应答器再传送剩余位，两者组合起来才得到全部的序列号，显然，虽然每次传送时动态算法的数据长度不同，但是在整个算法执行过程中，基本算法传送了两倍序列号，动态算法则只传送了一倍数据量，从而可知，动态算法传送的信息量是基本算法的50%,从而数据传输时间也是原基本算法的50在本例中，由于假定了应答器的序列号为8位长度二进制数，所以这个动态变化的优势并不明显，然而，事实上在实际应用中，应答器序列号长度往往是极大的，比如说常见的是96位，在这样的情况下，动态算法的优势就体现出来了。2.5退避式二进制树防碰撞算法2.5.1算法思路退避式二进制树搜索算法是对基本二进制树搜索算法的一种改进，根据2.3基本二进制树算法的分析可知，每识别一个应答器后，读写器恢复Request命令参数的初始值，重新从二进制树的根部开始执行，对此可以采取退避的思想，即每次识别出一个应答器后，算法返回其上一个父节点，而不返回整棵树的根节点。定义两个具有普遍意义的命令来描述算法：(1)请求命令Request(SN):该命令携带一个参数SN应答器接收到该命令，将自身的SN与接收到的SN比较，若小于或者等于，则该应答器回送其SN给读写器。注：Request(SN)初始值设为Request(11ll1111)。(2)休眠命令Sleep(SN)：该命令携带一个参数SN应答器接收到该命令，将自身的SN与接收到的SN比较，若等于，则该应答器被选中，进入休眠状态，即除非重新上电，否则不再响应Request命令。退避式二进制树算法的流程见图2.7,基本设置可参考基本二进制树算法：图2.7退避式二进制树算法流程如图所示，退避式二进制树算法的流程与基本算法的区别在于：基本算法中，一个应答器被识别后，重新启动新循环时，读写器返回整棵树的根节点，获取原始Request命令参数，而退避式算法中，读写器返回上一次发生碰撞节点，获取Request命令参数。事实上，退避式算法的改进是基于如下考虑的，在基本二进制树的分析过程中可见，算法之所以称为二进制树，是因为每次碰撞后，均以碰撞起始位为界，将应答器分为两个部分，形象的看，如同一棵树在进行从根部到主干到树枝的一个不断的分叉过程，所以，分叉也即是分组的理念是二进制树算法的本质所在，根据这一点，算法每次分叉到达末端之后，不再返回根部重新开始分叉，而是返回上一次分叉的节点即可重新开始新的树干，该节点也即是上一次发生碰撞的节点。采用该返回思路的二进制树算法，称为退避式二进制树算法。退避式二进制树算法的步骤如下：(1)应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答器的序列号均小于该最大序列号，所以在同一时刻将自身序列号发回给读写器。(2)由于应答器序列号的唯一性，若应答器数目不小于两个，必发生碰撞。此时将最大序列号中对应碰撞起始位置为。低于该位者不变，高于该位者置1。(3)读写器将处理后的最大序列号发送给应答器，应答器序列号与该值比较，小于或等于该值者，将自身序列号发回.(4)循环这个过程，选出一个最小序列号的应答器，与之正常通信后，命令该应答器进入休眠状态，即除非重新上电，否则不再响应读写器请求命令。(5)返回上一个发生碰撞的节点，获取该节点对应的最大序列号，重复上述过程，即可按序列号从小到大依次识别出各个应答器.2.5.2实例演示退避式二进制树算法实例演示如图2,8所示，其设置参考基本二进制树算法：图2.8退避式二进制树算法实例(1)启动第一轮循环，读写器发送Request(11111111)命令，所有应答器响应，将自身序列号与该SN(11111111)比较，均小于该值，则所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXX101,其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0,低于该位者不变，高于该位者置1,得到11110101,作为下一次Request命令参数，即Request(1110101)。(2)读写器发送Request(11110101)命令，所有应答器响应，将自身序列号与该SN(11110101)比较，其中T1(10100101),T3(11010101)的序列号小于该值，则Tl,T3返回自身序列号给读写器，在读写器接收端发生碰撞，读RFID二进制树防碰掩算法的研究与实现写器检测到返回数据为1XXX0101读写器做如下处理：将碰撞起始位D5位置0,低于该位者不变，高于该位者置1,得到11100101,作为下一次Request命令携带的参数值，即Request(11100101)。(3)读写器发送Request(11100101)命令，所有应答器响应，将自身序列号与SN(11100101)比较,其中T1(10100101)序列号小于该值,则T1返回序列号，在读写器接收端不发生碰撞，读写器检测到返回数据为10100101，做如下处理：将该值作为下一次Sleep命令参数值，即S1eep(10100101)。(4)读写器发送S1eep(10100101)命令，所有应答器响应，将自身序列号与该SN(10100111)比较，其中T1(10100101)的序列号等于该值，则T1执行该命令，进入休眠状态，即除非重新上电，否则不再对Request命令做出响应。(5)启动新一轮循环，重复上述步骤，总计12步后，依次识别出T1,T3,T2,T4,参数变化过程见图2.8中标示，具体内容不再详述。5.3性能评价与基本二进制树比较可知，退避式算法每次传送的数据信息量与基本算法是一样的，区别在于，退避式算法的传送次数，也即是所遍历的节点数目比之基本算法大大减少，假设读写器工作范围内有n个应答器，则所需节点数目为而，则可用式子2.19来表示：—=2冉-1⑵19)数学归纳法证明如下：当读写器工作范围内只有一个应答器时，显然有：ATi=1(2*2O>假设n个应答器时，有：Kl2吁I(2.21)则当系统中有n+1个应答器时，由于新增加的这个应答器与原来n个应答器的序列号均不相同，为了将其与某个匹配度最高的应答器区分开来，需要在原来二进制树中增加一个节点，由于节点之间仅存在父子关系，且仅通过两条边相连，所以有：匕“=曲+1=2(n+l)-l(2.22)得证。6本章小结本章归纳了现有的二进制树防碰撞算法，将其分为三个基本类别，分别讲述了其实现思路，进行了实例演示，并且对其做了性能分析，结果表明，动态算法和退避式算法是对基本算法的两个改进思路，具有各自的优势。3改进型二进制树防碰撞算法1涉及二进制树算法的国际标准1.1IS015693ISO15693【23】，短距离智能卡(ViciMtycouplingsmartcards)标准,读取距离可高达一分米，使用的频率为l3.56MHz它设计简单，生产成本比IS014443低，大都用来做出入控制、出勤考核等，现在很多企业使用的门禁卡大都使用这一类的标准。符合IS015693标准的信号接口部分的性能如下：工作场强：工作场的最小值为O.15A/m最大场为5A/m工作频率：工作频率为13.56MKz±7KHz调制：用2种幅值调制方式，即10%和100%调制方式。读写器应能确定用哪种方式。100%幅值调制10%的幅值调制数据编码数据编码采用脉冲位置调制。两种数据编码模式：256选1模式和4选1模式。数率：有高和低两种数率。表3.1IS015693数率逑率单一副载波双副鼓波低6.62Kbils/s&67Kbits/£高26.48Kbtis/s26,69Kbits/s3.1.2IS014443ISO是英文InternationalOrganizationForStandardization的简写，即国际标准化组织，IEC是InternationalElectromechanicalCommission的简写，即国际电子科技化委员会，JTC(JointTechCommittee)是ISO和IEC组成的一个联合技术委员会，负责ISO/IEC国际标准的起草、讨论、修正、制定、表决和公布等具体事宜，JTC分为各个子委员会SC(Subcommittee),子委员会又分为各个工作组WG(WorkGroup)其中子委员会SCl7下的WG85责ISOl4443、ISOl5693以及ISOl5693非接触式智能卡标准具体起草、讨论修正、制定、表决和最终ISO国际标准的公布【24】。ISO/IECl4443标准开始于1995年，单个系统于1999年进入市场，而其完成在2000年以后，迄今为止，ISO/IECl4443标准中的非接触式智能卡的类型可以分为TypeA和TypeB。TypeC-G目前已经暂时被列入IS014443标准，等待复议。下面简要介绍一下ISO/IECl4443标准中各个不同类型的非接触式智能卡。TypeA由Philips半导体公司首次开发和使用，在亚洲等地区，TypeA技术和产品占据了很大的市场份额。TypeA技术设计简单扼要，应用项目的开发周期可以很短，同时又能起到足够的保密作用，可以适用于非常多的应用场合。TypeB是一个开放式的非接触式智能卡标准，所有的读写操作可以由应用系统开发者定义，因此被世界上众多的智能卡厂家所广泛接受。TypeC由日本索尼公司研制。有两个主要特点，一是独特的天线结构和技术，使其读写距离可以稳定地达到10cm以上，同时其天线结构中镶嵌的特殊材料(铁氧体等材料)使其天线电磁场的读写距离非常均匀，没有“死区”现象出现，二是SON¥£接触智能卡数据写操作失败时的数据恢复功能。TypeD由Cubic公司研制，该系统的非接触方式读卡/认证速度非常快速，约为70ms左右，并且实现了数据加密技术，开创了交通系统中“刷卡”的先例。并且，Cubic将一些人体的生物特性，例如指纹、面部图案识别等融入于非接触智能卡技术中，开创了非接触智能卡生物识别的新领域。TypeE由以色列oTI公司研制，应用市场主要在欧洲和美国等地。OTI独创的一些非接触智能卡技术，可以使一个接触式智能卡提升成为一个非接触式智能卡，另外，OTI研究开发的单芯片解决方案和双模块解决方案支持接触式和非接触式(13.56MHz两种接口应用，并自动识别和转换。TypeF由欧洲LEGIC公司研制，具保密系统的产品在欧洲市场占有率达到60%以上。LEGIC保密模块包括SM05(-S)、SMlOO(-S)、SM300X400(-S)等。TypeG由中国制定，在应用层面，TypeG体现出了足够的技术先进性，但是在非接触智能卡核心技术的研发和掌握上、微电子工业基础设施和设备上，还有一段漫长的路要走。3.2IS014443标准二进制树防碰撞算法3.2.1基本概念ISO/IECl4443标准主要规定了TYEPA和TYPEBW种类型的非接触式智能卡，以13.56MH改变信号为载波频率，读写距离为0〜l0cm,通信速率均为106kb/s(9.4usperbit)。TYPEAF口TYPEB勺不同主要在于载波的调制深度和位编码方式，TYPE麻用l00%ASK调制、同步时序以及改进的米勒(Miller)编码方式，使用的是间断式调制方式，即当表示信息“l”时，表示有信号到卡，当表示信息“0”时，没有信号到卡。这种方式的优点是信息区别明显，受到干扰的机会少，不容易误操作，缺点是需要能量持续到卡；TYPEB采用采用10%ASK调制、非同步时序和不归零(NRz)编码方式，使用了一种调幅的调制方式，信息“l”和“0”的区别是在于信号的强弱，这一点容易受到外界干扰，需要采用冗余校验来解决。由上面的比较可以看出，两种技术各有优劣，这也是lSO组织确定了两种标准的原因之一。然而，在应用层面上A类有着比B类更多的厂商支持，是市场上的主流应用技术，其后续支持较好。在价格上由于A类的广泛性和芯片本身的低端设计性，A类有更大的优势。ISO/IECl4443标准由以下四个部分组成：:Physicalcharacteristics(物理特性)；:Radiofrequencypowerandsignalinterface(频谱功率和信号接口)Part3：Initializationandanti.collision(初始化和防碰撞算法)例；Part4:Transmissionprotocols(传输协议)。表3.2读写器和应答器的中英文名称及其缩写中文名EnglishName英文名翻译英文缩耳读写器ProiimityCouplingDevice近距离福合器PCD应答器ProxiraityCard近耦合卡PICC注：这里的近距离耦合器(PCD,ProximityCouplingDevice)和近耦合卡(PICC,ProximityCard)即前文的读写器和应答器，为尊重原IS014443标准，这里保留该说法。表3.3TypeA的通信信号接口

PCD到PICCPICC到PCD调喇位编码同步1一波特率，ASK]Q0%改进的miJier编码位级同步106kb/s振幅健控调制847KHz的煲裁调刎的却「载浓Manchester编码1位“帧同步E106kb/sISO14443标准在第三部分：“初始化和防碰撞算法”中，对防碰撞算法进行了规定，定义了PICC进入PCD寸的轮询，通信初始化阶段，从多卡中选取其中的一张的方法等。3.2.2算法思路PCD勺初始化，防碰撞，以及数据交换的流程如图3.1所示:图3.1ISO14443标准TYPEA类型PCD通信全过程如图所示，分为这么几个部分：PCDWPICC进行符合1SO/IEC14443.2的初始化通信。(1)PCD不断发送请求命令Rec|,检测工作范围内的PlCCo(2)PICC接收到请求命令Req,返回一个请求命令应答Atq。(3)PCD接收到来自PICC的请求命令应答Atq,表明有PICC存在。(4)PCD对该Atq进行检测，决定下一步动作。止匕时若Atq携带信息显示，PICC符合ISO14443—3,则启动位帧防碰撞循环，否则启动专用的防碰撞循环。PCDWPICC进行符合ISO/IEC14443—3的位帧防碰撞循环。(1)PCD选择级联层1,发送防碰撞命令Anti.collision。(2)PICC响应防碰撞命令Anti.co11ision,返回其UID的部分或者全部。(3)PCD根据PICC的响应，检测到碰撞，修改Anti.co11ision命令参数，发送防碰撞命令Anti.co11ision。(4)PICC响应防碰撞命令Anti.co11ision,返回其UID的部分或者全部。(5)循环3)〜4)步。(6)PCD根据PICC的响应，若检测不到碰撞，则发送Se1ect选择命令。(7)PICC接收到Se1ect选择命令，发送选择应答SAK乍为响应。(8)PCD对该SAK!行检测，决定下一步动作。若SAKf带信息显示：PICC返回的UID不完整，且未消除级联层数，则应增加级联层数，继续位帧防碰撞循环，即循环2)〜7)步。若SA侬带信息显示：PICC返回的UID完整，且清除级联层数，但是不符合IS014443—4,则PCDg送停止命令Ha1t,令PICC进入停止状态Ha1t。若SAK携带信息显示：PICC返回的UID完整，且消除级联层数，并且符合IS014443-4,则启动数据操作，即下一个环节3。PCDWPICC进行符合ISO/IEC14443.4的数据操作。(1)PCD发送请求选择应答RAts。(2)PICC接收到请求选择应答RAts,返回一个选择应答Ats。(3)PCD接收到来自PICC的选择应答Ats。(4)PCD对该Ats进行检测，决定下一步动作。若Ats携带信息显示：PICC支持协议和参数选择PPS则根据实际情况，判断是否需要进行参数修改。如果不需要进行参数修改，则执行步骤5),如果需要进行参数修改，则执行下列操作。(1)PcD发送协议和参数选择请求PPSReq(2)PICC接收该命令，修改相关参数。RFID；进制树防碰掩算法的研究’j实现(3)PICC返回协议和参数选择应答PPSResp若Ats携带信息显示：PICC不支持协议和参数选择PPS则直接进行数据交换，即步骤5)。(5)PCD与PICC进行数据交换。(6)PCD发送去选择请求命令Dese1ectReq,表示不再选择该PICC(7)PICC接收该命令，去除选择，返回去选择应答命令Dese1ectResp,表示已经去除了选择，进入HALT犬态，除非重新唤醒，否则将不再响应其它命令。(8)PCD接收去选择应答命令Dese1ectResp。总结：PCMPICC之间的通信包括上述初始化，防碰撞和数据操作三个环节，每个环节包括多个步骤，各个步骤下还可能有多个可能的分支操作，理想的操作流程为按各个步骤从上而下的执行唤醒曲令Wnk£Up唤醒曲令Wnk£Up醇用搪慵坏Ag_ooUi5丽E.cwpD«iaOper«Eif^|；图3.2Isol4443标准TYPEA类型PIcc状态转移图图中各个状态及其转移关系说明如下：(1)掉电状态(PowerOff):PICC未进入PCX作范围，没获得能量。(2)空闲状态(Idle):PICC进入PC”作范围，获得能量，PICC由掉电状态进入空闲状态，要注意的是，这里的复位Reset指的是PICC进入PCD工作场的操作过程，并非是一个具体的指令。(3)准备状态(Ready):空闲状态的PICC接收到请求命令Req,或停止状态的PICC接收到唤醒命令Halt,进入准备状态，在该状态中，完成防碰撞循环，从多张卡中选择出一张PICC(4)激活状态(Active):PICC被识别后，PCDg送选才?命令Select来选中该卡，PICC接收到该命令，进入激活状态，在该状态中，完成数据操作。(5)停止状态(Halt):处于激活状态的PICC完成数据操作后，接收到来自