RFID二进制树防碰撞算法的研究与实现修改123

1、1 南 阳 理 工 学 院 本科生毕业设计（论文） 学院（系）：计算机与信息工程学院 专 业： 通信工程 学 生： 乔军惠 指导教师： 路新华 完成日期 2012 年 4 月 2 南南 阳阳 理理 工工 学学 院院 本本 科科 毕毕 业业 设设 计（论文）计（论文） RFIDRFID 二二进制树防碰进制树防碰撞算法设计撞算法设计 学 院（系）： 计算机与信息工程学院 专 业： 通信工程 学 生 姓 名： 乔军惠 学 号： 104060820064 指 导 教 师（职称）： 路新华（讲师） 评 阅 教 师： 完 成 日 期： 2012 年4 月 南阳理工学院 Nanyang Institute

2、of Technology 3 RFID 二进制树防碰撞算法设计 【摘要】射频识别技术 RFID是目前正快速发展的一项新技术，它通过射频信 号进行非接触式的双向数据通信，从而达到自动识别的目的。随着 RFID 技术的 发展，如何实现同时与多个目标之间的正确的数据交换，即解决 RFID 系统中多 个读写器和应答器之间的数据碰撞，成为了限制RFID 技术发展的难题，采用合 理的算法来有效的解决该问题，称为 RFID 系统的防碰撞算法。在各种算法当中， 二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国 际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思 路不统一

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

4、算法，该算法识别速度快，执行效率高，极大的改进了识别效 果。 【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列 Abstract RFID is anewly developedtechnologywhich communicates through thecontact RF signal，so asto achieve objective automatic identificationAlong with the development of RFID technology，how to realize Data Exchange accurately amongMul

5、tiple Targets at the same time becomes 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

6、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 pr

7、ogrammable 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 perspecti

8、ves 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 algori

9、thms 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 improved 4 the identification results Key Words：RFID；Anticollision；ReadWrite DeVices；Transponders；FPGA 目目 录录 1 1

10、 引言引言.6 6 11 RFID 技术简介 .6 12 RFID 系统 .6 121 RFID 系统组成.6 122 RFID 系统分类.7 123 RFID 系统工作原理.8 13 RFID 技术现状及其发展 .8 131 RFID 技术应用 .8 132 RFID 标准统一化.9 133 RFID 防碰撞算法.9 14 课题提出的背景及其意义 .9 15 本文的主要工作 .10 2 2 现有现有 RFIRFID D 二进制树二进制树防碰撞算法防碰撞算法.1111 21 RFID 防碰撞算法概述 .11 22 RFID 二进制树防碰撞算法概述 .11 221 基本概念.11 222 性能指

11、标.12 223 算法分类.13 23 基本二进制树防碰撞算法 .14 231 算法思路.14 232 实例演示.15 233 性能评价.17 24 动态二进制树防碰撞算法 .19 241 算法思路.19 242 实例演示.21 243 性能评价.22 25 退避式二进制树防碰撞算法 .22 251 算法思路.22 252 实例演示.24 253 性能评价.25 26 本章小结 .25 3 3 改进型二进改进型二进制树防碰撞制树防碰撞算法算法.2525 31 涉及二进制树算法的国际标准 .25 311 IS0 15693 .25 312 IS014443 .26 32 IS014443 标准二

12、进制树防碰撞算法 .27 321 基本概念.27 322 算法思路.28 33 改进型二进制树防碰撞算法 .32 5 331 改进方向.32 332 基本概念.32 334 实例演示.37 34 本章小结 .39 4 4 FPGAFPGA 实实现改进型二现改进型二进制树防碰进制树防碰撞算法撞算法 .4040 41 FPGA 技术 .40 411 FPGA 简介.40 412 FPGA 设计流程.40 413 FPGA 设计工具.42 414 FPGA 设计语言.45 415 TestBench 验证平台.45 42 RFID 系统中的防碰撞模块 .46 43 FPGA 实现算法流程 .46 4

13、4 曼彻斯特解码模块 .47 45 命令处理模块 .50 451 请求命令处理.50 452 防碰撞命令处理.51 453 选择命令处理.53 454 去选择命令处理.53 46 命令选择模块 .53 47 数据存储模块 .55 48 密勒编码模块 .56 49 模块连接 .57 410 本章小结.58 结论结论.5858 致谢致谢.6262 6 1 1 引言引言 1 11 1 RFIDRFID 技技术简介术简介 自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为 Automatic Equipment Identif ication，简称 AEI，它通过一些先进的技术手 段，实现人

14、们对各种设备在不同状态下的自动识别和管理【ll】 。 目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两 种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别 领域的应用更具体的名称为射频识别，英文名为 Radio Frequency Identification，简写为 RFIDI21。RFID 技术通过射频方式进行非接触的双向 通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与 微波理论的发展，自从上世纪九十年代以来，RFID 技术快速发展，得到了广泛 的应用，进入新世纪后，各个国家，组织还有企业都加大了对 RFID技术的投入， 生产了大批相

15、应的产品，在多个领域有了成功的应用案例。RFID 被誉为二十一 世纪的十大战略性产业之一，可以预想，未来 RFID 技术的发展空间是无限广阔 的。 1 12 2 RFIDRFID 系系统统 1 12 21 1 RFIDRFID 系系统组成统组成 根据实际应用环境，RFID 系统结构有多种不同分法，一般来说，一个典型 RFID 系统包括三个部分：前端信息载体，数据交换环节，后端应用环境【3】 。 在具体应用中，前端信息载体有多个名称，如标签(Tag)，智能标签(Smart Labels)，射频卡(RF Card)等，本文建议采用应答器(Transponder)这种更具普 遍意义的说法。在 RFI

16、D系统中，应答器放置在待识别的物体上，它内部存储的 信息表征着该物品的独一性。通常来说，应答器由耦合元件和微电子芯片组成， 主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞 能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存 储器可将应答器分为 EEPROM，FROM(铁电存储器)，SRAM(静态随机存储器)，根 据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源 供给方式分为无源，半无源，有源。一般来说，应用最广泛的是无源+集成电路 固化+静态随机存储的应答器。由于在 RFID 系统中，应答器是大规模生产的。 应答器的典型产品有 TI

17、公司的 6000 系列，Philips 公司的ICODE 等。数据交 换环节即 RFID 系统中的读出写入设备，它是系统的核心部件，是后端应用环境 和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫描器，阅 读器，编程器等，本文建议采用读写器(ReadWrite Device)这种更具普遍意 义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中写入 信息。根据天线与读写器模块的分离与否，读写器可以分为分离式和集成式， 但无论哪种读写器，其基本结构都是类似的，从硬件部分来说，典型的读写器 7 由三块组成：射频通道模块，控制处理模块，天线。后端应用环境主要完成数 据信息的存储

18、及处理，它实质上就是一个数据管理系统，也是一个全局控制系 统，一般由 PC机或者工作站组成，同时也包括了应用软件在内，整个后端应用 环境负责接收来自读写器的数据，并进行存储以及相应的处理，协同调节多个 读写器的工作，该部分在应用中常称为中间件(Savant)，它扩展了 RFID 系统的 应用范围和应用能力，是未来 RFID 系统智能化，大型化发展的有力技术支撑， 是 RFID技术发展的重要方式。微软公司近年来也介入了 RFID 技术领域，所瞄准的就是 RFID系统后端应用的相关软件和服务。 综上所述，一个典型的RFID 系统的组成如图所示： 图 1.1 RFID 系统组成 1 12 22 2

19、RFIDRFID 系系统分类统分类 RFID 系统依据不同的标准，可以分为很多类别，各个不同的RFID 系统，在 工作方式和应用范围上，有着各自不同的特点，在应用时要根据实际需要来选 择。几种典型的分类方式如下所示： 根据作用距离的远近，RFID 系统可以分为如下三个方面： (1)密耦合：典型的作用范围为 0lcm。 (2)遥耦合：典型的作用范围为 lcm1m。 (3)远距离系统：典型的作用范围为 l10m。 根据工作频率的大小，RFID 系统可以分为如下四个方面： (1)低频：30300KHz，典型应用为134KHz。 (2)高频：330MHz，典型应用为1356MHz (3)超高频：300

20、MHz58GHz，典型应用为24G。 (4)混频：多个频率的混合使用，典型应用为134KHz+430MHz。 根据应答器供电方式，RFID 系统可以分为三个方面： (1)无源系统：由读写器负责给应答器供电。 (2)半无源系统：应答器内的电池仅做辅助作用。 8 (3)有源系统：应答器内置电池负责供给工作电压。 1 12 23 3 RFIDRFID 系系统工作原理统工作原理 RFID 是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路， 无线电广播，通信原理等多方面知识RFlD 系统中，读写器将要发送的信号调制 到载波上，经由射频通道，通过天线发送出去，应答器上的电压根据载波的变 化而变化

21、，将该电压信号进行整流和滤波后，得到解调后的数据，这是下行链 路的过程，应答器传输的数据的变化控制应答器天线上负载电阻的通断，从而 促使读写器天线上电压的变化，从而实现了数据的上行链路传输。在数据的双 向传输过程中，是通过电磁场的相互感应来实现的，该过程也可以用变压器的 模型来予以参考。同时，根据 RFID 系统的不同，在供电方式上有无源或者有源， 调制方式上有幅度调制或者相位调制，数据读取上有电感耦合或者反向散射等 区别【5】 。 1 13 3 RFIDRFID 技技术现状及其术现状及其发展发展 1 13 31 1 RFIDRFID 技技术应用术应用 做为一种新兴的自动识别技术，RFID 近

22、年来发展很快，在国内国外都取得 了广泛的应用，主要体现在以下几个领域【6】 。 (1)物流管理 物流管理是RFID 技术最具应用前景的领域，近年来提出了一个物联网的概 念，意在将全球所有的物品信息都用唯一的电子代码来表示，从而将这些物品 都联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产品，用 户，企业和政府之间建立但是该应用涉及到的方面太广，技术难度很大，目前 还在研究当中。 (2)身份识别 利用 RFID 技术，将应答器嵌入到身份证，护照等各种证件当中，甚至植入 动物皮毛，用来跟踪和识别目标。这方面应用的典型例子是我国目前实行的二 代身份证，它基于 ISOIEC14443 标准

23、定义的 TYPE B 类型卡。RFID 在身份识 别方面的主要问题是频段的局限性，一般使用的是 l35KHz 和 1356MHz的工作 频率，这是因为过高的频段容易带来对人体有害的电磁辐射。 (3)防伪应用 应答器在防伪应用中有识别快速，伪造难，成本低等优点，再加上安全认 证和加密功能，就可以大大提高伪造的难度和成本，同时，在识别的时刻，可 以通过读写器的快速阅读功能，在瞬间得出所有物品的信息，并加以记录和处 理。目前在日本和欧洲已经有了类似的应用。 (4)交通管理 交通管理是RFID 最先应用的领域，目前已经拥有了成熟的技术，它利用了 应答器便捷快速识别，可靠性高，安全性强的特点，目前主要应

24、用范围是电子 车票，高速公路收费等方面，在我国深圳，基于 RFID 技术的高速公路收费系统 已经得到了成功的应用。RFID 技术的应用远不止以上提及的四个方面，它在诸 9 如生产线自动化管理，门禁系统，新生婴儿防错管理，地理信息标识等多个方 面都有着广泛应用，可以毫不夸张的说，RFID 技术有着良好的发展前景，它孕 育的经济效益将是超乎想像的。 1 13 32 2 RFIDRFID 标标准统一化准统一化 RFID 最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范， 因此制约了该项技术在大规模系统中的应用，随着 RFID 技术的发展，参与到其 中的国家，组织，企业也越来越多，目前形成了

25、国际标准化组织 ISO，泛在 ID 中心 UID，全球电子产品代码管理中心 EPC三大标准体系，这些标准涉及到 RFID 系统的物理结构，通信协议，防碰撞算法，应用系统接口协议等等多个方 面的内容，它们针对不同的频率，基于不同的工作原理，甚至在同样的应用背 景下也有着巨大的协议上的区别。而要建立一个全球互联的 RFID产品网络，实 现 RFID 技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着 RFID 技术的应 用越发广泛，有识之士都意识到并着手解决这个问题，目前主要有两种思路， 一是生产出适应于不同标准，多制式兼容的 RFID产品，二是制定一个统一的 RFID 硕十学位论技术标准。

26、但是 RFID 本身的技术难度，以及标准带来的经济 利益的冲突，使得该目标实施起来非常困难。由此可见，标准统一化问题的重 要性与困难性是并存的，这将是一个任重而道远的过程。 1 13 33 3 RFIDRFID 防防碰撞算法碰撞算法 随着 RFID 技术的发展，多目标识别成为了一个很重要的应用方向，特别在 目标跟踪，物品识别，访问控制等操作中，利用 RFID 技术，对附着在不同目标 上的应答器快速可靠的进行识别，从而大大提高了定位的精确度，管理的自动 化促进了整个产业链的发展。因此，如何保证迅速快捷，又安全可靠的同时识 别多个目标，就成为了 RFID 技术发展的关键性技术。在 RFID系统中，

27、当工作 范围内同时出现了多个读写器和多个应答器时，读写器与读写器之间，应答器 与应答器之间的相互干扰，称 RFID系统发生了碰撞【7】 ，从而导致数据不能正 确的传输，信息无法得到正确的读取，一方面影响了产品的识别，另一方面还 可能导致信息的泄露。在全球信息安全意识广泛普及的背景下，可靠的安全机 制成为了RFID 技术发展的关键性制约因素，如何有效的解决 RFID 系统的碰撞 问题，成为了技术的关键，对此就需要采用一定的防碰撞算法来对其进行处理。 目前关于防碰撞算法的研究还在进行当中，理论成果已经得出了很多，许多国 际标准也对一些成熟的算法进行了规定，但是无论在理论效率还是实际应用上， 都还存

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

29、近年来 RFID 应用迅速 发展，各个不同 RFID 制造商的产品之间的不兼容，也带来了碰撞问题。总之， 由于多目标识别应用的需要，RFID 系统防碰撞问题成为了关键技术，为了解决 碰撞，可以从硬件和软件两方面着手，由于 RFID 系统的大规模应用限制了成本， 所以，硬件实现是不实际的，因此就需要采用一定的防碰撞算法来予以解决。 依前所述，RFID 系统碰撞主要有两种情况，读写器碰撞和应答器碰撞，读写器 碰撞是一个应答器同时收到不同读写器发出的命令，应答器碰撞是一个读写器 同时给不同应答器发送命令。在实际的应用当中，应答器由于其低成本的优越, 从而得到大量的生产，而读写器往往是固定在系统的某处

30、，来识别多个应答器， 所以碰撞的主要情况是应答器碰撞，即一个读写器的工作范围内同时出现了多 个应答器，并且对该读写器发出的命令同时予以响应，从而导致读写器无法正 确的识别出一个应答器，称该现象为发生了应答器碰撞。解决碰撞的过程相应 的被称为防碰撞，如前所述，该防碰撞过程主要从软件的角度来予以解决，称 为防碰撞算法【8】 。 在上述前提下，基于应答器的确定型二进制树防碰撞算法是目前最好的一 种选择，对其进行研究，是最有实际应用价值的，所以，本文将对其进行理论 分析与具体实现，在研究过程中，注重与新一代智能 RFID 系统的结合，应用拥 有强大功能的 FPGA(FieldProgrammable

31、GateArray)做为算法运行的微处理器，这种思路将是未来 RFID 技术发展的重要 方向，RFID 技术中的关键算法与先进的电子技术FPGA 的结合，将为 RFID 技术 的应用拓开广阔的前景。 1 15 5 本文的主本文的主要工作要工作 本文将在 RFID 技术的前提下，结合当前数字电路设计的主流思路，重点研 究 RFID 的关键技术防碰撞算法，并主要着眼于其中基于应答器的确定性算法， 即二进制树防碰撞算法，在理论分析的基础上，对其进行具体实现。基于上述 考虑，论文将分四章来予以讲述，文章结构与内容安排如下： 第 1 章：绪论。系统的介绍了 RFID技术，描述了典型RFID 系统的结构组

32、成， 提出了 RFID 系统的分类思想，讲述了 RFID 系统的工作原理，以及其应用范围， 重点强调了RFID 技术的现状和所面临的主要问题，由此体现了研究 RFID 关键 技术防碰撞算法的意义，明确了本文的主要研究内容。 第 2 章：现有 RFID 二进制树防碰撞算法。概要性的描述了 RFID 防碰撞算 法，对其进行了分类，重点介绍其中的二进制树防碰撞算法，研究了三种最基 本的二进制树算法，对其进行了原理阐述，性能分析，以及实例演示。 第 3 章：改进型二进制树防碰撞算法。二进制树防碰撞算法在多个国际标 准中均有规定，基于 IS014443标准的 TYPEA 是其中的一个典型例子，本章首先

33、介绍了涉及到二进制树防碰撞算法的几个标准，其次详细研究了 ISOl4443标准 对二进制树防碰撞算法的规定，最后提出了在此基础上的改进算法，这也是本 章的重点。 第 4 章：FPGA 实现改进型二进制树防碰撞算法。FPGA 技术是目前数字电路 11 设计的主流思路，利用 FPGA 做主处理器，是 RFID技术发展的方向，本章探讨 了这一想法，介绍了 FPGA 技术的相关要点，并应用 FPGA，实现了改进型二进 制树防碰撞算法。 2 2 现有现有 RFIRFID D 二进制树二进制树防碰撞算法防碰撞算法 2 21 1 RFIDRFID 防防碰撞算法概碰撞算法概述述 RFID 系统的数据通信双方是

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

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

36、为两大类， 一类是应答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中 RFID 系统分类思路中的有源系统和无源系统，根据实际应用情况，无源系统是应用 最广泛的一类，所以下文重点研究读写器驱动型的时分多路法。在该类读写器 驱动型时分多路法中，目前最常用的防碰撞算法有两种，一类是基于时隙 ALOHA 的统计型算法，另一类是基于二进制树的确定型算法，统计型算法的意 义是在一定的时隙范围内，系统有可能识别出所有应答器，确定型算法的最大 优点是，在一定的时隙范围内，系统一定可以将所有的应答器一一识别出来 【13】 。从应用的角度来说，正确有效的识别是实际所需要的，因此下文将着重 于二进制树防碰撞

37、算法的研究。 2 22 2 RFIDRFID 二二进制树防碰进制树防碰撞算法概述撞算法概述 2 22 21 1 基本概念基本概念 在 RFID防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称 12 为“二进制树” ，是因为在算法执行过程中，读写器要多次发送命令给应答器， 每次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这 个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数 据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为 “二进制树” 。 为了便于描述算法，声明一些基本概念如下：首先，在 RFID系统当中，每个应 答器都是独一无二

38、的，它们的独立性通过唯一的自身序列号来体现，该序列号 在不同的标准中有不同的名称，如 EPC 标准中称其为电子产品代码 EPC，即英 文 ElectronicProduct Code 的缩写，IS014443 标准中称其为唯一标识码 UID， 即英文 Unique Identmer 的缩写【15】 。事实上，这些都是对应答器序列号的名 称描述，因为下文涉及到的防碰撞算法是普遍意义上的，既包括了 EPC 标准中 的规定，也包括了 ISO 标准中的规定，因此在本文对普遍意义上的防碰撞算法 的描述过程中，统一用序列号 SN(SerialNumber)来描述上述概念，同时，序列 号的长度，格式，以及编

39、码方式也是各个标准各自差异的，为了说明的便利， 统一定义为8 位长度的 二进制码。如图 21 所示。 图 21 应答器序列号数据格式 读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部 位，此时的传输顺序定义为：先发送低位，再发送高位。在读写器或者应答器 内部，对数据进行比较时，遵循这样的原则，即按位依次比较，先比较低位， 再比较高位，约定 01，根据这个比较顺序，在判断大小时，低位数据优先， 即两数 A，B 相比较，从低位开始的第一个不相等位的大小决定了两数的大小， 只有当两个数的全部位均相等时，两数才相等。 2 22 22 2 性能指标性能指标 定义碰撞解决时期 CRI，即

40、Collision Resolution Interval【16】 ，即解 决一个读写器工作范围内碰撞所需要的时隙数，对二进制树算法的评价，一些 常用的性能指标如下所示【17】： 首先是算法执行效率，定义如下：在算法执行过程，一共个时隙，识 别了 n 个应答器，则=n/表示算法的执行效率。 分析如下：n=l，显而易见，在第一个时隙内不发生碰撞，可以成功识别该 应答器， =1。 n2，由于应答器序列号的唯一性，将有碰撞发生，在一个时隙内发生碰 撞的概率 p 是一个随机事件，在 n 个应答器信息包中i 个发生碰撞的概率为： 13 给出 i 个碰撞，则 CRI 的长度为： 其中 1 是 n个信息包最

41、初的一个时隙， 是 i 个碰撞的顺利传输的时隙， 是 n-i 个无碰撞传输的时隙。 由上式可知，是逐渐递归的，通过递归可得： 根据式(2.3)，上式可化为： 由此可见，是关于 p 的函数，则=n/也是关于 p的函数，一般情况下， 可以参考二项分布，将 p 取为 12。 算法的第二个重要的性能指标是稳定性，显然，基于 TDMA 的二进制树防碰 撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期 CRI，定义一 个随机变量，表示第 k 个CRI 的长度，这些形成一个 马尔可夫链(Markovchain)，因为第个 CRI 的长度由它开始的第一个时隙传 输的信息，也就是在 k个 CRI 区间内

42、到达的信息包决定的，所以，如果马尔可 夫链满足遍历性分布，那么这个系统就可以说是稳定的。 马尔可夫链遍历性分布要满足下列两个条件【18】： 这里有： 也就是 n 个信息包从发生碰撞开始传输的 CRI 区间长度的数学期望， 是 在一个时隙内到达这个系统信息包的期望值，该过程属于泊松过程【l9】 。一般 来说， 在二进制树防碰撞算法中，系统都能够满足马尔可夫链的两个遍历性分布条件， 即作为一种确定型的算法，二进制树防碰撞算法是稳定的。算法的第三个重要 14 性能是系统通信复杂度，显而易见，系统的通信双方是读写器与应答器，则通 信复杂度也应该从这两方面着手考虑，即读写器与应答器各自发送的数据位的 位

43、数。该指标的评价标准是基于能量消耗的角度的，即发送的数据信息量越少， 则整个系统消耗的能量也越少，这显然是一个理想的效果。 2 22 23 3 算法分类算法分类 在基本的二进制树搜索算法的基础上，有多种形式的二进制树搜索算法， 它们之间主要的区别在于命令的数据形式，主要有两点。 (1)命令参数是1bit 数据，还是多 bit 数据。 (2)命令参数长度是固定的，还是变化的。 图 22 是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按 照命令参数分为 1bit 和多 bit，根据传输的命令参数的长度分为定长二进制树 和动态二进制树两种，根据二进制树遍历时是一轮前进到底的还是退避返回的

44、分为前进二进制树和退避二进制树两种。需要说明的是，这只是一个大略的分 类法，主要目的在于说明二进制树分类的基本原则。事实上，分类所得的这些 算法中也有互相重合的，如动态二进制树算法既可以采用前进思路，也可以采 用退避思路。另外，在具体应用时，可能还存在多种不同的说法，如 lbit长二 进制树中还有修正二进制树 MBBT，加强二进制树 EBBT等区别【20】 。 图 22 二进制树算法分类 2 23 3 基本二进基本二进制树防碰撞制树防碰撞算法算法 2 23 31 1 算法思路算法思路 定义两个具有普遍意义的命令来描述算法： (1)请求命令 Request(SN)：该命令携带一个参数 SN，应答

45、器接收到该命令， 将自身的 SN 与接收到的 SN 比较，若小于或者等于，则该应答器回送其 SN给读 写器。注：Request(SN)初始值设为Request(11111111)。 (2)休眠命令 Sleep(SN)：该命令携带一个参数 SN，应答器接收到该命令， 将自身的 SN 与接收到的 SN 比较，若等于，则该应答器被选中，进入休眠状态， 15 也即是不再响应 Request 命令，除非该应答器通过先离开读写器工作范围再进 入的方式重新上电，才可以再次响应 Request 命令。 基本二进制树算法的流程图如图 23 所示： 图 23 基本二进制树算法流程 基本二进制树算法的步骤如下： (

46、1) 应答器进入读写器工作范围，读写器发出一个最大序列号，所有应答 器的序列号均小于该最大序列号，所以在同一时刻将自身序列号返回给读写器。 (2) 由于应答器序列号的唯一性，当应答器数目不小于两个时，必然 发生碰撞发生碰撞时，将最大序列号中对应的碰撞起始位设置为 O，低于该 位者不变，高于该位者设置为 l。 (3) 读写器将处理后的序列号发送给应答器，应答器序列号与该值比较， 小于或等于该值者，将自身序列号返回给读写器。 (4) 循环这个过程，就可以选出一个最小序列号的应答器，与该应答器进 行正常通信后，发出命令使该应答器进入休眠状态，即除非重新上电，否则不 再响应读写器请求命令。也就是说，下

47、一次读写器再发最大序列号时，该应答 器不再响应。 (5)重复上述过程，即可按序列号从小到大依次识别出各个应答器。 注：第五步时，从步骤 1 开始重复，也就是说，读写器识别完一个应答器 后，将重新发送原始的最大序列号。 16 2 23 32 2 实例演示实例演示 根据上述分析，下面给出一个基本二进制树搜索算法的实例演示，如图 24 所示。 假设 RFID 系统中有一个读写器R，四个应答器Tl(10100101)，T2 (10l01101)，T3(11010101)，T4(11101101)，在某一时刻，四个应答器 同时进入读写器的工作范围之内，读写器发出命令，四个应答器同时响应，由 于 其序列号

48、 SN 的唯一性，将发生应答器碰撞，从而启动防碰撞循环，分析如下： 图 2.4 基本二进制树算法实例 注：图中共有四轮循环，依次识别出四个应答器，分别以不同格式的线条 表 示，并加有循环轮次的数字标识。 (1)启动第一轮循环，读写器发送Request(1lll1111)命令，所有应答器响 应该命令，将自身序列号与该 SN(1l1l1111)比较，均小于该值，于是所有应答 器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在 读写器接收端发生碰撞，读写器检测到返回数据为 lXXXXl0l，其中 X 表示该位 发生了碰撞，读写器做如下处理：将碰撞起始位 D4 位置0，低于该位者不变

49、， 高于该位者置 l，得到 11ll0l01，作为下一次Request 命令携带的参数值，即 Request(11110l01)。 (2)读写器发送Request(11110101)命令，所有应答器响应该命令，将自身 序列号与该 SN(11110l01)比较，其中 T1(10l00101)，T3(1l010101)的序列号小 于该值，则 Tl，T3 返回自身序列号给读写器，在读写器接收端发生碰撞，读写 器检测到返回数据为 1XXX0l01，读写器做如下处理：将碰撞起始位 D5 位置0， 低于该位者不变，高于该位者置 l，得到 11l00l01，作为下一次Request 命令 携带的参数值，即

50、Request(11100101)。 17 (3)读写器发送Request(11100101)命令，所有应答器响应该命令，将自身 序列号与该 SN(111 00l01)比较，其中 Tl(10100l01)的序列号小于该值，则 Tl 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数 据为 10100101，读写器做如下处理：将该数值作为下一次 Sleep 命令携带的参 数值，即 Sleep(10100101)。 (4)读写器发送Sleep(10100101)命令，所有应答器响应该命令，将自身序 列号与该 SN(10l00111)比较，其中 T1(10l00101)的序列号等于

51、该值，则 T1 执 行该命令，进入休眠状态，即除非重新上电，否则不再响应 Request 命令。 (5)启动第二轮循环，读写器发送Request(111l1111)命令，除 T1 外所有应 答器响应该命令，将自身序列号与该 SN(11111l11)比较，均小于该值，于是所 有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序 列号在读写器接收端发生碰撞，读写器检测到返回数据为 1XXXXl01，其中 X 表 示该位发生了碰撞，读写器做如下处理：将碰撞起始位 D4 位置0，低于该位者 不变，高于该位者置 1，得到 11110101，作为下一次Request 命令携带的参数 值，即

52、 Request(11110101)。 (6)读写器发送Request(11110101)命令， 除 Tl 外所有应答器响应该命令， 将自身序列号与该 SN(11l10101)比较，其中 T3(1l010l01)的序列号小于该值， 则 T3 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返 回数据为 110l0101，读写器做如下处理：将该数值作为下一次 Sleep 命令携带 的参数值，即 Sleep(11010101)。 (7)读写器发送Sleep(1l010101)命令，所有应答器响应该命令，将自身序 列号与该 SN(110l 0101)比较，其中 T3(11010101)

53、的序列号等于该值，则 T3 执行该命令，进 入休眠状态，即除非重新上电，否则不再响应 Request 命令。 (8)启动第三轮循环，读写器发送Request(11111111)命令，除 T1，T3 外所 有应答器响应该命令，将自身序列号与该 SN(1111ll11)比较，均小于该值，于 是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回 的序列号在读写器接收端发生碰撞，读写器检测到返回数据为 1X101101，其中 x 表示该位发生了碰撞，读写器做如下处理：将碰撞起始位 D7 位置0，低于该 位者不变，高于该位者置 1，得到 10101101，作为下一次Request 命令携

54、带的 参数值，即 Request(10101101)。 (9)读写器发送Request(10101101)命令，除 Tl，T3 外所有应答器响应该命 令，将自身序列号与该 SN(10101101)比较，其中 T2(10101101)的序列号等于该 值，则 T2 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测 到返回数据为 l0101101，读写器做如下处理：将该数值作为下一次 Sleep 命令 携带的参数值，即 Sleep(10101101)。 (10)读写器发送Sleep(10101101)命令，所有应答器响应，将自身序列号与 该 SN(10101101)比较，其中 T2(10

55、101101)的序列号等于该值，则 T2 执行该命 令，进入休眠状态，即除非重新上电，否则不再响应 Request 命令。 (11)启动第四轮循环，读写器发送Request(1l111111)命令，除 Tl，T3，T2 外所有应答器响应该命令，将自身序列号与该 SN(11l1l111)比较， 均小于该值，则所有应答器均返回自身序列号给读写器，因为只有应答器 T4 返 回数据，所以在读写器接收端不发生碰撞，读写器检测到返回数据为 11101101，读写器做如下处理：将该数值作为下一次 Sleep 命令携带的参数值， 18 即 Sleep(1l1 01101)。 (12)读写器发送Sleep(1l

56、l 01101)命令，所有应答器响应，将自身序列号 与该 SN(11101l01)比较，其中 T4(1l1 01101)的序列号等于该值，则 T4 执行该 命令，进入休眠状态，即除非重新上电，否则不再响应 Request 命令。 2 23 33 3 性能评价性能评价 假设工作范围内有 N 个应答器存在，通过基本二进制树搜索算法进行防碰 撞操作，依次识别出所有应答器。循环次数定义为在整个防碰撞循环过程中 的循环轮次，也即是二进制树的遍历次数。根据前面的分析可知，做为一种确 定性的算法，基本二进制树一轮循环总能识别出一个应答器，所以在 n 个应答 器的前提下，经过 n 次循环可以识别出 N 个应答

57、器，所以整个过程中的循环次 数为 n 搜索次数定义为算法执行命令的次数。也即是二进制树的节点数目。该 值可以用式子来表示【21】 ，其中 Integ 表示取整。 通信时间 t定义为数据交换的时间，也即是命令执行的时间。假设有 n 个 应答器，从读写器到应答器的传输时间为 tl，反之为 t2总时间为 t，则传输 的总时间 t 可以用式 2.8 来表示【22】： 数学归纳法证明如下： 假设只有一个应答器，则读写器发送命令，应答器响应，无碰撞，识别出 应答器。 假设有两个应答器，则读写器发送命令，两个应答器响应，发生碰撞，为第 一次过程，该时间为： 读写器修改命令参数，发出命令，仅一个应答器响应，则

58、识别出该应答器， 这一次过程时间与前一次一致，读写器再发送命令，最后一个应答器响应，得 到 识别，时间也是一样的，则总时间为： 当有 n 个应答器时，假设识别总时间为： 则当 n+1 个应答器时，读写器首先发送命令，应答器全体响应，发生碰撞， 这个过程时间为： 读写器修改命令参数，发出命令，k 个应答器响应，余下 p 个不响应， 19 k+p=n+l，则识别出该k 个应答器需要时间为： 再识别余下p 个需要时间为： 则这两者时间之和为： 加上前一次的t1+t2，总时间为： 得证。 因为基本二进制树算法中每次传输的序列号 SN 长度相同，所以有： 基本二进制树搜索算法是所有二进制树算法的基础，分

59、析基本二进制树搜 索算法的性能可知，对于固定数目的应答器，二进制树算法的性能主要取决于 二进制树的节点数目和单次传输命令参数的时间，事实上，二进制树的节点数 目与应答器分组的思路是直接相关的，而单次传输命令参数的时间则取决于该 命令包含的数据位数。所以，要改善二进制树算法的性能，就必须从这两点着 手，现有的二进制树搜索算法有很多种，它们都是在基本二进制树搜索算法的 基础上加以改进得来的，根据前述分析，主要的改进思路有两个： (1)减少每次通信过程中的数据传输位数。 (2)减少应答器分组的询问次数。 本文中，定义根据第一个思路得来的算法为动态二进制树，它的一个典型应 用为 ISOl4443 TY

60、PE-A 二进制树搜索算法。定义根据第二个思路得来的算法为 退避式二进制树，它的一个典型应用为 EPC 二进制树搜索算法。 2 24 4 动态二进动态二进制树防碰撞制树防碰撞算法算法 2 24 41 1 算法思路算法思路 定义两个具有普遍意义的命令来描述算法： (1)请求命令 Request()，该命令携带一个参数 SN，长度为 ，应答器接收到该命令，将自身的 SN 中的前 1x 位与接收到的 比较，若两者相等，则该答器返回其 SN 的剩余位给读写器。注： Request()初始值设为Request(1l111111)，约定当参数值为全 1 时，应答 器返回完整序列号。 (2)休眠命令 Sle