南阳理工学院本科生毕业设计（论文）
学院（系）：计算机与信息工程学院
专业：通信工程
学生：乔军惠
指导教师：路新华
完成日期 2012 年 4 月
南阳理工学院本科毕业设计（论文）RFID二进制树防碰撞算法设计
学院（系）：计算机与信息工程学院
专业：通信工程
学生姓名：乔军惠
学号：104060820064
指导教师（职称）：路新华（讲师）
评阅教师：
完成日期：2012年4月
南阳理工学院
Nanyang Institute of Technology
RFID二进制树防碰撞算法设计
【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID 系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。
【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列
Abstract
RFID is anewly developedtechnologywhich communicates through the—contact RF signal，so asto achieve objective automatic identification．Along with the development of RFID technology，how to realize Data Exchange accurately amongMultiple Targets at the same time becomes the key problem of RFID technology．RFID anti-collision algorithm is the solution to the above mentioned problems．In all the algorithms，binary algorithm is most widely used as an international standard fbr its exactness ofidentincation．International standards have put forward manyregulations on binary algorithm．It not onlypromotes the development of anti．coUision algorithm，but also b“ngs the conflict to a unilFied solution．Traditionalideas in general are handled byMCU．Along with the development ofRFID technology，an imponant direction in the f．uture is the field programmable gates arrayFPGA．As kindof integrated circuitsthatcanbe programmed in the field，FPGA is fast and programmable．All these adVantagesopenup anewef active way ofRFIDanti．collisionarithmetic．In viewof the above problems，this paperprobes into the RFID systembinary prevent collisionf．rom the perspectives ofboth theory and practice．It canbediVided into three aspects：6rstly，theoretical researchon binary algorithm．It sums up all thebinary algorithms in being and gather to three categorys suchas Basic algorithm，Dynamic algorithm and Backoff algorithm．MoreoVer，it Expounds the idea of the various algorithms and evalues their perf6rmance；secondary，it introduces an improved version of algorithm onthe basis of specinc standard．This algorithm has f．ast recognition，high efnciency and greatly improved the identification results．
Key Words：RFID；Anticollision；Read／Write DeVices；Transponders；FPGA
目录
1 引言 (6)
1．1RFID技术简介 (6)
1．2RFID系统 (6)
1．2．1 RFID系统组成 (6)
1．2．2 RFID系统分类 (7)
1．2．3 RFID系统工作原理 (8)
1．3RFID技术现状及其发展 (8)
1．3．1RFID技术应用 (8)
1．3．2 RFID标准统一化 (9)
1．3．3 RFID防碰撞算法 (9)
1．4课题提出的背景及其意义 (9)
1．5本文的主要工作 (10)
2 现有RFID二进制树防碰撞算法 (11)
2．1RFID防碰撞算法概述 (11)
2．2RFID二进制树防碰撞算法概述 (11)
2．2．1基本概念 (11)
2．2．2性能指标 (12)
2．2．3算法分类 (13)
2．3基本二进制树防碰撞算法 (14)
2．3．1算法思路 (14)
2．3．2实例演示 (15)
2．3．3性能评价 (17)
2．4动态二进制树防碰撞算法 (19)
2．4．1算法思路 (19)
2．4．2实例演示 (21)
2．4．3性能评价 (22)
2．5退避式二进制树防碰撞算法 (22)
2．5．1算法思路 (22)
2．5．2实例演示 (24)
2．5．3性能评价 (25)
2．6本章小结 (25)
3 改进型二进制树防碰撞算法 (25)
3．1涉及二进制树算法的国际标准 (25)
3．1．1 IS0 15693 (25)
3．1．2 IS014443 (26)
3．2IS014443标准二进制树防碰撞算法 (27)
3．2．1基本概念 (27)
3．2．2算法思路 (28)
3．3改进型二进制树防碰撞算法 (32)
3．3．1改进方向 (32)
3．3．2基本概念 (32)
3．3．4实例演示 (37)
3．4本章小结 (39)
4 FPGA实现改进型二进制树防碰撞算法 (40)
4．1FPGA技术 (40)
4．1．1 FPGA简介 (40)
4．1．2 FPGA设计流程 (40)
4．1．3 FPGA设计工具 (42)
4．1．4 FPGA设计语言 (45)
4．1．5 TestBench验证平台 (45)
4．2RFID系统中的防碰撞模块 (46)
4．3FPGA实现算法流程 (46)
4．4曼彻斯特解码模块 (47)
4．5命令处理模块 (50)
4．5．1请求命令处理 (50)
4．5．2防碰撞命令处理 (51)
4．5．3选择命令处理 (53)
4．5．4去选择命令处理 (53)
4．6命令选择模块 (53)
4．7数据存储模块 (55)
4．8密勒编码模块 (56)
4．9模块连接 (57)
4．10本章小结 (58)
结论 (58)
致谢 (62)
1 引言
1．1 RFID技术简介
自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为Automatic Equipment Identif ication，简称AEI，它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理【ll】。
目前，应用最广泛的自动识别技术大致可以分为光学技术和无线电技术两种，其中光学技术普遍应用于条形码和摄像两大类，而无线电技术在自动识别领域的应用更具体的名称为射频识别，英文名为Radio Frequency Identification，简写为RFIDI21。RFID技术通过射频方式进行非接触的双向通信，达到自动识别的目的，它源起于上世纪四五十年代，最初是基于雷达与微波理论的发展，自从上世纪九十年代以来，RFID技术快速发展，得到了广泛的应用，进入新世纪后，各个国家，组织还有企业都加大了对RFID技术的投入，生产了大批相应的产品，在多个领域有了成功的应用案例。RFID被誉为二十一世纪的十大战略性产业之一，可以预想，未来RFID技术的发展空间是无限广阔的。
1．2 RFID系统
1．2．1 RFID系统组成
根据实际应用环境，RFID系统结构有多种不同分法，一般来说，一个典型RFID系统包括三个部分：前端信息载体，数据交换环节，后端应用环境【3】。在具体应用中，前端信息载体有多个名称，如标签(Tag)，智能标签(Smart Labels)，射频卡(RF Card)等，本文建议采用应答器(Transponder)这种更具普遍意义的说法。在RFID系统中，应答器放置在待识别的物体上，它内部存储的信息表征着该物品的独一性。通常来说，应答器由耦合元件和微电子芯片组成，主要电气性能为工作频率，读写能力，数据传输率，信息数据存储量，防碰撞能力，信息安全性能等，应答器的分类也是以这些性能为依据的，例如根据存储器可将应答器分为EEPROM，FROM(铁电存储器)，SRAM(静态随机存储器)，根据信息注入方式可分为集成电路固化，现场线改写，现场无线改写，根据电源供给方式分为无源，半无源，有源。一般来说，应用最广泛的是无源+集成电路固化+静态随机存储的应答器。由于在RFID系统中，应答器是大规模生产的。应答器的典型产品有TI公司的6000系列，Philips公司的I·CODE等。数据交换环节即RFID系统中的读出写入设备，它是系统的核心部件，是后端应用环境和前端信息载体的数据通道，在实际应用中，往往被称为查询器，扫描器，阅读器，编程器等，本文建议采用读写器(Read／Write Device)这种更具普遍意义的说法，这样既包括了从应答器中读出信息，同时也包括了向应答器中写入信息。根据天线与读写器模块的分离与否，读写器可以分为分离式和集成式，但无论哪种读写器，其基本结构都是类似的，从硬件部分来说，典型的读写器由三块组成：射频通道模块，控制处理模块，天线。后端应用环境主要完成数据信息的存储及处理，
它实质上就是一个数据管理系统，也是一个全局控制系统，一般由PC机或者工作站组成，同时也包括了应用软件在内，整个后端应用环境负责接收来自读写器的数据，并进行存储以及相应的处理，协同调节多个读写器的工作，该部分在应用中常称为中间件(Savant)，它扩展了RFID系统的应用范围和应用能力，是未来RFID系统智能化，大型化发展的有力技术支撑，是RFID技术发展的重要方式。微软公司近年来也介入了
RFID技术领域，所瞄准的就是RFID系统后端应用的相关软件和服务。
综上所述，一个典型的RFID系统的组成如图所示：
图1.1 RFID 系统组成
1．2．2 RFID系统分类
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．3 RFID系统工作原理
RFID是一门多学科综合技术，涉及到电磁场理论，数字电路，模拟电路，无线电广播，通信原理等多方面知识RFlD系统中，读写器将要发送的信号调制到载波上，经由射频通道，通过天线发送出去，应答器上的电压根据载波的变化而变化，将该电压信号进行整流和滤波后，得到解调后的数据，这是下行链路的过程，应答器传输的数据的变化控制应答器天线上负载电阻的通断，从而促使读写器天线上电压的变化，从而实现了数据的上行链路传输。在数据的双向传输过程中，是通过电磁场的相互感应来实现的，该过程也可以用变压器的模型来予以参考。同时，根据RFID系统的不同，在供电方式上有无源或者有源，调制方式上有幅度调制或者相位调制，数据读取上有电感耦合或者反向散射等区别【5】。
1．3 RFID技术现状及其发展
1．3．1 RFID技术应用
做为一种新兴的自动识别技术，RFID近年来发展很快，在国内国外都取得了广泛的应用，主要体现在以下几个领域【6】。
(1)物流管理．
物流管理是RFID技术最具应用前景的领域，近年来提出了一个物联网的概念，意在将全球所有的物品信息都用唯一的电子代码来表示，从而将这些物品都联系在一起，可以随时随地的识别，追踪，管理这些物品，最终在产品，用户，企业和政府之间建立但是该应用涉及到的方面太广，技术难度很大，目前还在研究当中。
(2)身份识别
利用RFID技术，将应答器嵌入到身份证，护照等各种证件当中，甚至植入动物皮毛，用来跟踪和识别目标。这方面应用的典型例子是我国目前实行的二代身份证，它基于ISO／IEC14443标准定义的TYPE B类型卡。RFID在身份识别方面的主要问题是频段的局限性，一般使用的是l35KHz和13．56MHz的工作频率，这是因为过高的频段容易带来对人体有害的电磁辐射。
(3)防伪应用
应答器在防伪应用中有识别快速，伪造难，成本低等优点，再加上安全认证和加密功能，就可以大大提高伪造的难度和成本，同时，在识别的时刻，可以通过读写器的快速阅读功能，在瞬间得出所有物品的信息，并加以记录和处理。目前在日本和欧洲已经有了类似的应用。
(4)交通管理
交通管理是RFID最先应用的领域，目前已经拥有了成熟的技术，它利用了应答器便捷快速识别，可靠性高，安全性强的特点，目前主要应用范围是电子车票，高速公路收费等方面，在我国深圳，基于RFID技术的高速公路收费系统已经得到了成功的应用。RFID技术的应用远不止以上提及的四个方面，它在诸如生产线自动化管理，门禁系统，新生婴儿防错管理，地理信息标识等多个方面都有着广泛应用，可以毫不夸张的说，RFID技术有着良好的发展前景，它孕育的
经济效益将是超乎想像的。
1．3．2 RFID标准统一化
RFID最初是各个厂家在各自的独立标准下开发出来的，缺乏统一的规范，因此制约了该项技术在大规模系统中的应用，随着RFID技术的发展，参与到其中的国家，组织，企业也越来越多，目前形成了国际标准化组织ISO，泛在ID 中心UID，全球电子产品代码管理中心EPC三大标准体系，这些标准涉及到RFID 系统的物理结构，通信协议，防碰撞算法，应用系统接口协议等等多个方面的内容，它们针对不同的频率，基于不同的工作原理，甚至在同样的应用背景下也有着巨大的协议上的区别。而要建立一个全球互联的RFID产品网络，实现RFID 技术的飞跃发展，就必须解决标准不统一的难题，近年来，随着RFID技术的应用越发广泛，有识之士都意识到并着手解决这个问题，目前主要有两种思路，一是生产出适应于不同标准，多制式兼容的RFID产品，二是制定一个统一的RFID 硕十学位论技术标准。但是RFID本身的技术难度，以及标准带来的经济利益的冲突，使得该目标实施起来非常困难。由此可见，标准统一化问题的重要性与困难性是并存的，这将是一个任重而道远的过程。
1．3．3 RFID防碰撞算法
随着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．1 RFID防碰撞算法概述
RFID系统的数据通信双方是读写器和应答器，在实际的RFID系统工作时，可能会出现同时多个读写器和多个应答器共存的情况，毫无疑问，此时系统的数据交换就会出现信道与时序上的重叠，也就是发生了碰撞，在多个读写器与多个应答器的射频识别系统中，存在着两种形式的冲突方式，一种是同一应答器同时收到不同读写器发出的命令，另一种是同一个读写器同时收到多个不同应答器返回的数据，前者我们称为读写器碰撞，后者称为应答器碰撞【9】，在实际应用当中，一般是读写器做为主设备，来识别多个应答器，所以发生读写器碰撞的应用场合是不多的，因此下文将着重研究应答器碰撞。
在上述前提下，有两种类型的通信方式，一种是读写器发送的数据同时被多个应答器接收，称为“无线广播”，另一种是多个应答器的数据同时传送给读写器，称为“多路存取”，两者都是无线电技术中长期面临的难题，同时也发展出一系列相应的解决思路，一般来说分为四种，即空分多路(SDMA)，码分多路(CDMA),频分多路(FDMA)，时分多路(TDMA)，从RFID系统的通信形式、功耗、系统复杂性以及成本多方面综合考虑，时分多路法是最有实际应用价值的，它也是目前RFID防碰撞算法应用中最广泛的一类，时分多路法的基本思想是把整个可供使用的通路容量按时间分配给多个用户，从而达到在不同时隙将各个应答器一一识别出来的目的【11】。时分多路法按照能量的供给者可以分为两大类，一类是应答器驱动型，另一类是读写器驱动型，这也正是对应了第一章中RFID 系统分类思路中的有源系统和无源系统，根据实际应用情况，无源系统是应用最广泛的一类，所以下文重点研究读写器驱动型的时分多路法。在该类读写器驱动型时分多路法中，目前最常用的防碰撞算法有两种，一类是基于时隙ALOHA的统计型算法，另一类是基于二进制树的确定型算法，统计型算法的意义是在一定的时隙范围内，系统有可能识别出所有应答器，确定型算法的最大优点是，在一定的时隙范围内，系统一定可以将所有的应答器一一识别出来【13】。从应用的角度来说，正确有效的识别是实际所需要的，因此下文将着重于二进制树防碰撞算法的研究。
2．2 RFID二进制树防碰撞算法概述
2．2．1基本概念
在RFID防碰撞算法中，二进制树算法是目前应用最广泛的一种，之所以称为“二进制树”，是因为在算法执行过程中，读写器要多次发送命令给应答器，每次命令都把应答器分成两组，多次分组后最终得到唯一的一个应答器，在这个分组过程中，将对应的命令参数以节点的形式存储起来，就可以得到一个数据的分叉树，而所有的这些数据节点又是以二进制的形式出现的，所以称为“二进制树”。
为了便于描述算法，声明一些基本概念如下：首先，在RFID系统当中，每个应答器都是独一无二的，它们的独立性通过唯一的自身序列号来体现，该序列号在不同的标准中有不同的名称，如EPC标准中称其为电子产品代码EPC，即英文ElectronicProduct Code的缩写，IS014443标准中称其为唯一标识码UID，即英文Unique Identmer的缩写【15】。事实上，这些都是对应答器序列号的名称描述，因为下文涉及到的防碰撞算法是普遍意义上的，既包括了EPC标准中的规定，也包括了ISO标准中的规定，因此在本文对普遍意义上的防碰撞算法的描述过程中，统一用序列号SN(SerialNumber)来描述上述概念，同时，序列号的长度，格式，以及编码方式也是各个标准各自差异的，为了说明的便利，统一定义为8位长度的
二进制码。如图2．1所示。
图2．1 应答器序列号数据格式
读写器与应答器之间进行数据交换时，往往要传输序列号的部分或者全部位，此时的传输顺序定义为：先发送低位，再发送高位。在读写器或者应答器内部，对数据进行比较时，遵循这样的原则，即按位依次比较，先比较低位，再比较高位，约定0<1，根据这个比较顺序，在判断大小时，低位数据优先，即两数A，B相比较，从低位开始的第一个不相等位的大小决定了两数的大小，只有当两个数的全部位均相等时，两数才相等。
2．2．2性能指标
定义碰撞解决时期CRI，即Collision Resolution Interval【16】，即解决一个读写器工作范围内碰撞所需要的时隙数，对二进制树算法的评价，一些常用的性能指标如下所示【17】：
首先是算法执行效率，定义如下：在算法执行过程，一共个时隙，识别了n个应答器，则=n/表示算法的执行效率。
分析如下：n=l，显而易见，在第一个时隙内不发生碰撞，可以成功识别该应答器，=1。
n≥2，由于应答器序列号的唯一性，将有碰撞发生，在一个时隙内发生碰撞的概率p是一个随机事件，在n个应答器信息包中i个发生碰撞的概率为：
给出i个碰撞，则CRI的长度为：
其中1是n个信息包最初的一个时隙，是i个碰撞的顺利传输的时隙，
是n-i个无碰撞传输的时隙。
由上式可知，是逐渐递归的，通过递归可得：
根据式(2.3)，上式可化为：
由此可见，是关于p的函数，则=n/也是关于p的函数，一般情况下，可以参考二项分布，将p取为1／2。
算法的第二个重要的性能指标是稳定性，显然，基于TDMA的二进制树防碰撞算法是沿着时间轴线来执行协议的，有一系列的碰撞解决时期CRI，定义一个随机变量，表示第k个CRI的长度，这些…………形成一个马尔可夫链(Markovchain)，因为第个CRI的长度由它开始的第一个时隙传输的信息，也就是在k个CRI区间内到达的信息包决定的，所以，如果马尔可夫链满足遍历性分布，那么这个系统就可以说是稳定的。
马尔可夫链遍历性分布要满足下列两个条件【18】：
这里有：
也就是n个信息包从发生碰撞开始传输的CRI区间长度的数学期望，是
在一个时隙内到达这个系统信息包的期望值，该过程属于泊松过程【l9】。一般来说，
在二进制树防碰撞算法中，系统都能够满足马尔可夫链的两个遍历性分布条件，即作为一种确定型的算法，二进制树防碰撞算法是稳定的。算法的第三个重要性能是系统通信复杂度，显而易见，系统的通信双方是读写器与应答器，则通信复杂度也应该从这两方面着手考虑，即读写器与应答器各自发送的数据位的位数。该指标的评价标准是基于能量消耗的角度的，即发送的数据信息量越少，则整个系统消耗的能量也越少，这显然是一个理想的效果。
2．2．3算法分类
在基本的二进制树搜索算法的基础上，有多种形式的二进制树搜索算法，它
们之间主要的区别在于命令的数据形式，主要有两点。
(1)命令参数是1bit数据，还是多bit数据。
(2)命令参数长度是固定的，还是变化的。
图2．2是一个二进制树搜索算法的分类图，在基本二进制树的基础上，按照命令参数分为1bit和多bit，根据传输的命令参数的长度分为定长二进制树和动态二进制树两种，根据二进制树遍历时是一轮前进到底的还是退避返回的分为前进二进制树和退避二进制树两种。需要说明的是，这只是一个大略的分类法，主要目的在于说明二进制树分类的基本原则。事实上，分类所得的这些算法中也有互相重合的，如动态二进制树算法既可以采用前进思路，也可以采用退避思路。另外，在具体应用时，可能还存在多种不同的说法，如lbit长二进制树中还有修正二进制树MBBT，加强二进制树EBBT等区别【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
(10l01101)，T3(11010101)，T4(11101101)，在某一时刻，四个应答器
同时进入读写器的工作范围之内，读写器发出命令，四个应答器同时响应，由于其序列号SN的唯一性，将发生应答器碰撞，从而启动防碰撞循环，分析如下：
图2.4 基本二进制树算法实例
注：图中共有四轮循环，依次识别出四个应答器，分别以不同格式的线条表示，并加有循环轮次的数字标识。
(1)启动第一轮循环，读写器发送Request(1lll1111)命令，所有应答器响应该命令，将自身序列号与该SN(1l1l1111)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为lXXXXl0l，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者不变，高于该位者置l，得到11ll0l01，作为下一次Request命令携带的参数值，即Request(11110l01)。
(2)读写器发送Request(11110101)命令，所有应答器响应该命令，将自身序列号与该SN(11110l01)比较，其中T1(10l00101)，T3(1l010101)的序列号小于该值，则Tl，T3返回自身序列号给读写器，在读写器接收端发生碰撞，读写器检测到返回数据为1XXX0l01，读写器做如下处理：将碰撞起始位D5位置0，低于该位者不变，高于该位者置l，得到11l00l01，作为下一次Request命令携带的参数值，即Request(11100101)。
(3)读写器发送Request(11100101)命令，所有应答器响应该命令，将自身序列号与该SN(111 00l01)比较，其中Tl(10100l01)的序列号小于该值，则Tl 返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为10100101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(10100101)。
(4)读写器发送Sleep(10100101)命令，所有应答器响应该命令，将自身序列号与该SN(10l00111)比较，其中T1(10l00101)的序列号等于该值，则T1执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。
(5)启动第二轮循环，读写器发送Request(111l1111)命令，除T1外所有应答器响应该命令，将自身序列号与该SN(11111l11)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1XXXXl01，其中X表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D4位置0，低于该位者不变，高于该位者置1，得到11110101，作为下一次Request命令携带的参数值，即Request(11110101)。
(6)读写器发送Request(11110101)命令，．除Tl外所有应答器响应该命令，将自身序列号与该SN(11l10101)比较，其中T3(1l010l01)的序列号小于该值，则T3返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为110l0101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(11010101)。
(7)读写器发送Sleep(1l010101)命令，所有应答器响应该命令，将自身序列号与该SN(110l
0101)比较，其中T3(11010101)的序列号等于该值，则T3执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。
(8)启动第三轮循环，读写器发送Request(11111111)命令，除T1，T3外所有应答器响应该命令，将自身序列号与该SN(1111ll11)比较，均小于该值，于是所有应答器均返回自身序列号给读写器，因为序列号的唯一性，应答器返回的序列号在读写器接收端发生碰撞，读写器检测到返回数据为1X101101，其中x 表示该位发生了碰撞，读写器做如下处理：将碰撞起始位D7位置0，低于该位者不变，高于该位者置1，得到10101101，作为下一次Request命令携带的参数值，即Request(10101101)。
(9)读写器发送Request(10101101)命令，除Tl，T3外所有应答器响应该命令，将自身序列号与该SN(10101101)比较，其中T2(10101101)的序列号等于该值，则T2返回自身序列号给读写器，在读写器接收端不发生碰撞，读写器检测到返回数据为l0101101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(10101101)。
(10)读写器发送Sleep(10101101)命令，所有应答器响应，将自身序列号与该SN(10101101)比较，其中T2(10101101)的序列号等于该值，则T2执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。
(11)启动第四轮循环，读写器发送Request(1l111111)命令，除Tl，T3，T2外所有应答器响应该命令，将自身序列号与该SN(11l1l111)比较，均小于该值，则所有应答器均返回自身序列号给读写器，因为只有应答器T4返回数据，所以在读写器接收端不发生碰撞，读写器检测到返回数据为11101101，读写器做如下处理：将该数值作为下一次Sleep命令携带的参数值，即Sleep(1l1 01101)。
(12)读写器发送Sleep(1ll 01101)命令，所有应答器响应，将自身序列号与该SN(11101l01)比较，其中T4(1l1 01101)的序列号等于该值，则T4执行该命令，进入休眠状态，即除非重新上电，否则不再响应Request命令。
2．3．3性能评价
假设工作范围内有N个应答器存在，通过基本二进制树搜索算法进行防碰撞操作，依次识别出所有应答器。循环次数定义为在整个防碰撞循环过程中的循
环轮次，也即是二进制树的遍历次数。根据前面的分析可知，做为一种确定性的算法，基本二进制树一轮循环总能识别出一个应答器，所以在n个应答器的前提下，经过n次循环可以识别出N个应答器，所以整个过程中的循环次数为n．搜索次数定义为算法执行命令的次数。也即是二进制树的节点数目。该值可以用式子来表示【21】，其中Integ表示取整。
通信时间t定义为数据交换的时间，也即是命令执行的时间。假设有n个应答器，从读写器到应答器的传输时间为tl，反之为t2．总时间为t，则传输的总时间t可以用式2.8来表示【22】：
数学归纳法证明如下：
假设只有一个应答器，则读写器发送命令，应答器响应，无碰撞，识别出应答器。
假设有两个应答器，则读写器发送命令，两个应答器响应，发生碰撞，为第一次过程，该时间为：
读写器修改命令参数，发出命令，仅一个应答器响应，则识别出该应答器，这一次过程时间与前一次一致，读写器再发送命令，最后一个应答器响应，得到识别，时间也是一样的，则总时间为：
当有n个应答器时，假设识别总时间为：
则当n+1个应答器时，读写器首先发送命令，应答器全体响应，发生碰撞，这个过程时间为：
读写器修改命令参数，发出命令，k个应答器响应，余下p个不响应，k+p=n+l，则识别出该k个应答器需要时间为：
再识别余下p个需要时间为：
则这两者时间之和为：
加上前一次的．t1+t2，总时间为：
得证。
因为基本二进制树算法中每次传输的序列号SN长度相同，，所以有：
基本二进制树搜索算法是所有二进制树算法的基础，分析基本二进制树搜索算法的性能可知，对于固定数目的应答器，二进制树算法的性能主要取决于二进制树的节点数目和单次传输命令参数的时间，事实上，二进制树的节点数目与应答器分组的思路是直接相关的，而单次传输命令参数的时间则取决于该命令包含的数据位数。所以，要改善二进制树算法的性能，就必须从这两点着手，现有的二进制树搜索算法有很多种，它们都是在基本二进制树搜索算法的基础上加以改进得来的，根据前述分析，主要的改进思路有两个：
(1)减少每次通信过程中的数据传输位数。
(2)减少应答器分组的询问次数。
本文中，定义根据第一个思路得来的算法为动态二进制树，它的一个典型应用为ISOl4443 TYPE-A二进制树搜索算法。定义根据第二个思路得来的算法为退避式二进制树，它的一个典型应用为EPC二进制树搜索算法。
2．4动态二进制树防碰撞算法
2．4．1算法思路
定义两个具有普遍意义的命令来描述算法：
(1)请求命令Request()，该命令携带一个参数SN，长度为
，应答器接收到该命令，将自身的SN中的前1～x位与接收到的
比较，若两者相等，则该答器返回其SN的剩余位给读写器。注：Request()初始值设为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) 由于应答器序列号的唯一性，当应答器数目不小于两个时，必然发生碰
自适应多叉树防碰撞算法研究 摘要该文提出了一种自适应多叉树防碰撞算法。新算法在动态二叉树和四叉树搜索算法的基础上，利用曼彻斯特编码可以准确识别碰撞位的特性，通过计算碰撞因子，估计标签数量，从而自适应地调整搜索叉数，即在标签数较多的节点上选择动态四叉树搜索，而在标签数较少时选择动态二叉树搜索。理论和仿真分析表明：新算法克服了动态二叉树和四叉树搜索算法的缺点，在减少碰撞时隙数的基础上，又减少了空闲时隙数，大幅度地提高了搜索效率和时隙的吞吐量，具有一定的创新性和适用性。 关键词射频识别；防碰撞算法；多叉树搜索； 中图分类号TP301.6文章标识码 A An Adaptive Anti-collision Algorithm Based on Multi-tree Search Abstract A new adaptive anti-collision algorithm based on multi-tree search is proposed in this paper. Because Manchester code can identify the position of collision, the new algorithm can adjust the number of search tree adaptively by using the information of probability of collision. That is to say ，when the number of tags is large，the new algorithm use four-tree search. Conversely, the new algorithm use binary-tree search. Theory and computer simulations show that the new anti-collision algorithm which overcomes the disadvantages of binary-tree and four-tree algorithms can decrease effectively collision timeslots and idle timeslots and improve the throughput of timeslots. Key words Radio Frequency Identification (RFID)；Anti-collision algorithm；Multi-tree search； 1 引言 射频识别（RFID）是20世纪90年代兴起并逐渐走向成熟的一种非接触式的自动识别技术，在物流、跟踪、定位等领域已得到广泛应用。其中，用于解决读写器作用范围内多标签识别问题的防碰撞算法已成为该领域研究的热点之一。 标签防碰撞算法主要解决在读写器有效通信范围内，多个标签同时与读写器进行通信的问题。常用的防碰撞算法一般可以分为两类，一种是基于时隙随机分配的ALOHA算法[1]，包括动态时隙ALOHA(DSA)算法[1]，分群时隙ALOHA算法(GSA)[2]和标签估计算法(TEM)[3]等。其特点是，算法简单，便于实现，适用于低成本RFID系统。但由于该类算法的时隙是随机分配的，即存在一定的可能性，某一标签在相当长一段时间内无法识别，即“Tag starvation”问题，所以这类方法被称为可能性方法。另一类是基于二叉树搜索(BS)算法[1]，包括动态二叉树搜索(DBS)算法[1]，自适应二叉树搜索算法(ABS)[4-6]和自适应查询树算法(AQS)[7]等。该类算法比较复杂，识别时间较长，但不存在“Tag starvation”问题，故被称为确定性方法。 值得注意的是，当待识别标签数量较多时，基于二叉树的搜索算法由于频频出现碰撞，且每次碰撞只产生两个分支，搜索效率较低。文献[8]为此提出了一种基于四叉树的搜索算法。虽然该算法在搜索的初期可以有效地减少碰撞，但随着搜索范围和标签的数量的减小，会产生大量的空闲时隙，因此搜索效率并没有得到提高。 本文在动态二叉树（DBS）和四叉树（DFS）搜索算法的基础上，利用曼彻斯特编码可以准确的识别碰撞位的特性，通过计算碰撞因子，估计标签数量，从而自适应地调整搜索叉______________________ 1
精心整理 平桥区2015年棚户区改造“金桂园”项目 塔式起重机与建筑物防碰撞专项施工方案 一、工程概况 本工程位于信阳市平桥区中心大道与平西路交叉口，经八路西。建筑面积5660019层，地下?《塔机使用说明书》 三、防碰撞施工措施 （一）塔吊在水平面方向的防碰撞措施 1.低位塔吊的起重臂端部与高位塔吊塔身之间防碰撞措施。 塔吊在现场的定位布置是关键，可通过严格控制两台塔吊之间的位置关系，来预防
低位塔吊的起重臂端部碰撞高位塔吊塔身。依据《塔式起重机安全规程》（GB5144-94）中的10.5之规定“两台起重机之间的最小架设距离应保证处于低位的起重机的臂架端部与另一台起重机的塔身之间至少有2米的距离”。由塔吊现场平面布置可知，四台塔吊中，相邻塔吊的距离均大于各自起重臂长度，即满足了施工需要，又克服了处于低位的塔吊的起重臂端部与高位的塔吊塔身之间的碰撞。 1. 2. ）中的 部与另一台起重机的塔身之间至少有2米的距离”。 3、为避免塔吊在使用及停止期间与建筑物发生碰撞，塔机必须用回转限位器，回转限位器有多组触点，用一组控制大臂转到一定角度回转电机不会再转，另一组经过一个开关接回转制动，第二组触点调的比第一组离楼更近一点，也就是第二组触点动作时，回转制动也就动作，锁住大臂，想往高层建筑相反的方向转就关掉开关，
另可在回转齿圈要转到建筑物处塞上一个木方，左右方向都塞，在塔吊与建筑物要接触的位置可安装一个轮胎，以减少塔吊与建筑物发生碰撞时的危害。 （三）塔吊防风措施 1、发生六级以上的大风,各机停止作业,同时小车收回止,离塔身5m处,吊钩离小车间距离2m处,钢丝绳不能挂在吊钩上。 2,互相 避让。 3 4 5 6 7 8 9 13 四、作业前必须做到： 1. 塔吊司机、地面指挥员必须熟悉所操作塔吊的性能，并严格执行说明书有关规定和“塔吊十不吊”。 2. 塔吊司机、地面指挥员在作业前检查对讲机电池电量是否充分，频道是否一致，声音是否清楚，必须保证正常使用。
一防碰撞的基本算法ALOHA 1. 纯-ALOHA(PureALOHA)法 即标签只要有数据发送请求就立即发送出去，而不管无线信道中是否已有数据在传输。它是无线网络中最早采用的多址技术，也是最为简单的一种方法。在RFID系统中，这种方法仅适用于只读标签(Read only tag)。 ALOHA系统所采用的多址方式基于TDMA，是一种无规则的时分多址，或者叫随机多址。用于实时性不高的场合 基本思想很简单：当用户想要发送数据帧时，它就可以在任何时候发送。有可能发生冲突。 冲突导致传输不成功。得不到确认或者本身侦听到错误。 等待随机长时间重发。 通信量越大，碰撞的可能性也越大。主要特点是各个标签发射时间不需要同步，是完全随机的，实现起来比较简单。当标签不多时它可以很好的工作。缺点就是数据帧发送过程中碰撞发生的概率很大。 经过分析，ALOHA法的最大吞吐率只有18.4％，80％以上的信道容量没有被利用。对于较小的数据包量，无线信道的大部分时间没有被利用，而随着数据包量的增加，标签碰撞的概率又会明显增加。 2.时隙ALOHA法 为了提高接入系统的吞吐量，可将时间划分为一段段等长的时隙，记为T0。规定数据帧只能在时隙的开始才能发送出去。 如果一个时隙内只有一个站点到达，则该分组会传输成功；如果有多于一个的分组到达，将会发生碰撞。 和纯ALOHA一样，发生碰撞后，各标签仍是经过随机时延后分散重发的。 如果有许多标签处于阅读器的作用范围内，在最不利的情况下，经过多次搜索也可能没有发现序列号，因为没有唯一的标签能单独处于一个时隙之中而发送成功。因此，需要准备足够大量的时隙，这样做法降低了防碰撞算法的性能。
日 进贤九颂山河沁河园 3.1期 塔 吊 防 碰 撞 施 工 方 案 职务: 职务: 职务: 昌建建设集团有限公司 二 0 一七年五月 一、工程概况 进贤九颂山河沁河园 3.1 期工程位于进贤县民和镇胜利北路 299 号，总建筑面积111171.6川，由江西铭立房地产开发有限公司投资建 设，其设计单位为广州宝贤华瀚建筑工程设计有限公司，勘察单位为 核工业江西工程勘察总院 ,监批准: 审核: 编制: 技术负责人 项目经理 项目技术负责人
理单位为江西恒信建设监理咨询有限公司,施工单位为昌建建设集团有限公司。本工程为群体建筑，共包含10栋单体建筑，结构为框架剪力墙结构,基础为灌注桩基础，层数为2-33层，其中52#楼南北朝向，建筑面积为21083.42 m2,框架剪力墙结构、层数为33 层，建筑高度为99.0m ，53#、58#楼东西朝向，建筑面积为1273.81 m,框架结构、层数为2层，建筑高度为8.65m , 55#楼南北朝向，建筑面积为20395.39 m,框架剪力墙结构、层数为33层，建筑高度为99.0m , 56#楼南北朝向，建筑面积为13728.39 m,框架 剪力墙结构、层数为33 层，建筑高度为99.8m ，57#楼南北朝向，建筑面积为3493.42 m,框架结构、层数为3层，建筑高度为11.1m,59# 楼南北朝向，建筑面积为20784.15 m,框架剪力墙结构、层数为32 层，建筑高度为98.4m,760#楼南北朝向，建筑面积为822.75川，框 架结构、层数为2 层，建筑高度为8.65m,61# 楼东西朝向，建筑面积为923.89川，框架结构、层数为2层，建筑高度为8.65m。本工程垫层混凝土强度为C15 ，基础混凝土强度为C30 ，主体梁、板、墙、柱混凝土强度为 C25 、C30 、C35 。
常见RFID防碰撞算法有哪几种？比较各自的优缺点，详细论述其中一种算法的工作原理。 1.RFID简介 射频识别技术(Radio Frequency Id,RFID)是一种非接触式自动识别技术，与传统的识 别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处 理，具有操作方便快捷、存储数据量大、保密性好、反应时间短、对环境适应性强等优点， 现在已广泛应用于工业自动化，商业自动化和交通运输管理等领域，成为当前IT业研究的热 点技术之一。典型的RFID系统主要包括三个部分：电子标签(Tag)、阅读器(Reader)和数据 处理o电子标签放置在被识别的对象上，是RFID系统真正的数据载体。通常电子标签处于休 眠状态，一旦进入阅读器作用范围之内就会被激活，并与阅读器进行无线射频方式的非接触 式双向数据通信，以达到识别并交换数据的目的。此外，许多阅读器还都有附加的通信接口， 以便将所获得的数据传进给数据处理子系统进行进一步的数据处理。 2.系统防碰撞 RFID系统工作的时候，当有2个或2个以上的电子标签同时在同—个阅读器的作用范围内 向阅读器发送数据的时候就会出现信号韵干扰，这个干扰被称为碰撞(collision)，其结果 将会导致该次数据传输的失败，因此必须采用适当的技术防止碰撞的产生。 从多个电子标签到—个阅读器的通信称为多路存取。多路存取中有四种方法可以将不同 的标签信号分开：空分多路法(SDMA)、频分多路法（FDMA)、对分多路法（TDMA)和码分多路 法(CDMA)。针对RFID系统低成本、较少硬件资源和数据传输速度以及数据可靠性的要求，TDMA 构成了RFID系统防碰撞算法最为广泛使用的一族。 TDMA是把整个可供使用的通路容量按时间分配给多个用户的技术，可分为电子标签控制 法和阅读器控制法。电子标签控制法主要有ALOHA法，阅读器控制法有轮询法和二进制搜索 法。 2.1 空分多路法(SDMA) 空分多路法(Space Division Multiple Access，SDMA)是在分离的空间范围内实现多个 目标识别。其实现的方法有两种：一种方法是将读写器和天线之间的作用距离按空间区域进 行划分，把大量的读写器和天线安置在一个天线阵列中。当标签进入这个天线阵列的覆盖范 围后，与之距离最近的读写器对该标签进行识别。由于每个天线的覆盖范围较小，相邻的读 写器识别范围内的标签同样可以进行识别而不受到相邻的干扰，如果多个标签根据在天线阵 列中的空间位置的不同，可以同时被识别。另外一种方法是，读写器利用一个相控阵天线， 通过让天线的方向性图对准单独的标签，这样标签根据其在读写器作用范围内的角度位置的 不同而区别开来。空分多路法的缺点是需要使用复杂的天线系统，会大幅提高RFID设备的成 本，因此这种方法只适用于一些特殊的应用场合。 2.2 频分多路法(FDMA) 频分多路法(Frequency Division Multiple Access，FDMA)是把若干个使用不同载波频
RFI D 技术中防碰撞算法研究与改进 曹新宇 杨虹蓁 赵云峰 (北华航天工业学院电子工程系,河北廊坊065000) 摘 要:本文研究了射频识别技术中的防碰撞算法,介绍了几种标准搜索算法,提出了标签分区的改进算法,并且利用软件进行了仿真,仿真结果表明此改进算法能明显提高效率和稳定性。关键词:射频识别;防碰撞算法;A LOH A 中图分类号:T N911.23 文献标识码:A 文章编号:1673-7938(2010)01-0006-03 收稿日期:2009-09-07 作者简介:曹新宇(1977-),男,讲师,硕士,吉林省吉林市人,从事无线通信,微波技术研究。 0 引 言 无线射频识别(RFI D ,Radio Frequency Identifica 2tion )技术是近年来应用发展迅速的一种利用射频通 讯方式实现的无线非接触式身份识别技术。在无线电技术中,多路存取的问题是众所周知的。如果有多个RFI D 标签接收到电磁波并同时发送信息,则标签阅读器接收到的信号就会互相干扰,不可避免地出现标签阅读冲突问题。识别过程中这种不可避免的多数据传输产生的冲突即碰撞问题严重影响了系统的性能。因此,如何解决碰撞问题成为RFI D 系统的关键技术之一。目前解决RFI D 标签阅读冲突问题主要是基于两种防冲突算法:基于时隙A LO 2H A 的防冲突算法和基于树结构的防冲突算法。其 中,前者是采用随机选择发送时间的方式,系统识别的可靠性相对差一些,但易于设计兑现。后者则采用二叉树的搜索算法,系统识别的可靠性较高,但系统兑现时硬件设计较为复杂。因此,低成本的RFI D 标签一般是采用基于时隙A LOH A 的防冲突算法来设计的,如何提高该算法系统识别的效率和吞吐量是应用系统研究重点。1 算法原理 1.1 帧时隙A LOH A 标签防碰撞算法 帧时隙Aloha (Framed Slotted Aloha ,FS A )算法的基本思想是在时间域上进一步离散,将时间划分为不同的离散帧,每帧由若干可用时隙组成。标签在每个帧内随机选择一个时隙发送数据。读写器判断 标签是否被识别,发生碰撞的标签进入下一识别周期,直到所有标签被识别。这种算法适于传输信息量较大的场合,与时隙A LOH A 算法相同,该算法也需要一个同步开销。FS A 算法存在一个缺点,当标签数量远大于时隙个数时,读取标签的时间将会大大增加,而在标签个数远小于时隙个数时,会造成时隙的浪费。 1.2 动态帧时隙A LOH A 算法 动态帧时隙A LOH A (DFS A )算法是每帧时隙数都会根据标签数的不同而变化。根据每帧中的空闲和碰撞情况动态调整帧长以提高识别效率。读写器首先给标签提供较小的帧长,如果碰撞较多,就在下个识别周期增大帧长,直到至少识别一个标签为止。为获得系统最大吞吐率,DFS A 算法需要在识别过程中估算标签数,用以确定匹配时隙数。标签估算的方法有很多种,例如: 1.2.1 估算出参与识别的标签总数 设时隙数为L ,标签数为n ,则一个帧中碰撞时隙率C ratio =1-1-1 L n 1+ n L -1 。在读写器识 别过程中,已知当前帧时隙数为L ,并且可以统计出该帧时隙碰撞率C ratio ,采用逼近算法,可以估算出 n 。 1.2.2 直接估算出未识别的标签数 当系统达到最大吞吐率时,一个时隙的碰撞率 C slot =0.4180,因此一个时隙碰撞的标签数C tags = 1 C slot =2.3922。读写器在识别过程中,统计前一个帧 的时隙碰撞数N coll ,则未识别标签数N est =2.3922× N coll 。 第20卷第1期2010年2月 北华航天工业学院学报Journal of N orth China Institute of Aerospace Engineering V ol 120N o 11 Feb 12010
南阳理工学院本科生毕业设计（论文） 学院（系）：计算机与信息工程学院 专业：通信工程 学生：乔军惠 指导教师：路新华 完成日期 2012 年 4 月
南阳理工学院本科毕业设计（论文）RFID二进制树防碰撞算法设计 学院（系）：计算机与信息工程学院 专业：通信工程 学生姓名：乔军惠 学号：104060820064 指导教师（职称）：路新华（讲师） 评阅教师： 完成日期：2012年4月 南阳理工学院 Nanyang Institute of Technology
RFID二进制树防碰撞算法设计 【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID 系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。 【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列 Abstract RFID is anewly developedtechnologywhich communicates through the—contact RF signal，so asto achieve objective automatic identification．Along with the development of RFID technology，how to realize Data Exchange accurately amongMultiple Targets at the same time becomes the key problem of RFID technology．RFID anti-collision algorithm is the solution to the above mentioned problems．In all the algorithms，binary algorithm is most widely used as an international standard fbr its exactness ofidentincation．International standards have put forward manyregulations on binary algorithm．It not onlypromotes the development of anti．coUision algorithm，but also b“ngs the conflict to a unilFied solution．Traditionalideas in general are handled byMCU．Along with the development ofRFID technology，an imponant direction in the f．uture is the field programmable gates arrayFPGA．As kindof integrated circuitsthatcanbe programmed in the field，FPGA is fast and programmable．All these adVantagesopenup anewef active way ofRFIDanti．collisionarithmetic．In viewof the above problems，this paperprobes into the RFID systembinary prevent collisionf．rom the perspectives ofboth theory and practice．It canbediVided into three aspects：6rstly，theoretical researchon binary algorithm．It sums up all thebinary algorithms in being and gather to three categorys suchas Basic algorithm，Dynamic algorithm and Backoff algorithm．MoreoVer，it Expounds the idea of the various algorithms and evalues their perf6rmance；secondary，it introduces an improved version of algorithm onthe basis of specinc standard．This algorithm has f．ast recognition，high efnciency and greatly improved the identification results． Key Words：RFID；Anticollision；Read／Write DeVices；Transponders；FPGA
东岭地产海棠兰庭塔机防碰撞报警系统 实施方案 项目名称：东岭地产6-08地块海棠兰庭 建设公司：陕西东岭房地产开发有限公司 监理单位：陕西建科建设管理有限公司 施工单位：陕西关中建设工程有限公司 陕西关中建设工程有限公司 2016-3-10
一、工程概况 二、编制说明 根据西安市建设工程质量安全监督站文件市建质发（2008）14号《西安市建设工程质量安全监督站关于加强群塔管理避免相互碰撞的通知》根据通知第二条和第四条凡在我市建筑施工现场安装两台（含两台）以上塔式起重机，必须在施工组织设计时统筹安排，避免塔吊之间或塔吊和其他建筑物，构筑物之间相互碰撞。要求两塔吊间距不能满足要求时必须安装塔吊防碰撞系统。 三、方案概述 SPS塔吊群智能防碰撞系统主要功能包括塔吊之间的碰撞报警和塔吊区域保护两个方面。 3.1、塔吊间碰撞报警 （1）塔臂之间碰撞报警 两塔吊等高时，他们的塔臂之间（包括后臂）可能会发生相互碰撞，SPS 可以在两塔吊塔臂接近时发出报警信号，提醒司机谨慎操作。如下图。
塔臂之间碰撞示意图 （2）塔臂与塔身碰撞报警 两塔吊不等高时，低塔吊塔臂有可能与高塔吊塔身发生碰撞，SPS可在低塔吊塔臂接近高塔吊塔身时发出报警，提醒司机谨慎操作。如下图。 塔臂与塔身碰撞示意图 （3）塔臂与钢丝绳碰撞报警 两塔吊不等高时，低塔吊塔臂有可能和高塔吊钢丝绳发生碰撞，SPS可在低塔吊塔臂接近高塔吊钢丝绳时发出报警，提醒司机谨慎操作。如下图
塔臂与钢丝绳碰撞示意图 3.2、塔吊区域保护 （1）塔臂区域保护 可限制塔臂进入某些特定区域，防止塔臂与建筑物、电线杆等静止障碍物发生碰撞。如下图。 塔臂区域保护意图图吊钩区域保护示意图 （2）吊钩区域保护 可限制吊钩进入某些特定区域，防止钢丝绳、吊钩及所吊重物与特定物体发生碰撞或者重物追落到特定区域。 四、SPS系统性能 与同类产品相比较，SPS塔吊群智能防碰撞系统具有以下特点： 5.1、算法先进，确保报警信号及时发出。 5.2、附加安装，不改变塔吊原有线路和结构，不会产生任何负面效果。
第31卷第6期电子与信息学报Vol.31No.6 2009年6月Journal of Electronics & Information Technology Jun. 2009 基于二叉树分解的自适应防碰撞算法 丁治国①②郭立②朱学永①汪赵华② ①(解放军电子工程学院网络中心合肥 230037) ②(中国科学技术大学电子科学与技术系合肥 230027) 摘要：该文提出了一种基于二叉树分解的自适应防碰撞算法。新算法利用标签EPC的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。通过引入碰撞堆栈，并根据时隙状态自适应得调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。 关键词：射频识别；防碰撞算法；二叉树分解；碰撞堆栈 中图分类号：TN91 文献标识码：A 文章编号：1009-5896(2009)06-1395-05 An Adaptive Anti-collision Algorithm Based on Binary-Tree Disassembly Ding Zhi-guo①②Guo Li②Zhu Xue-yong①Wang Zhao-hua② ①(Center of Network, Electronic Engineering Institute PLA, Hefei, 230037, China) ②(Department of Electronic Science and Technology, USTC, Hefei, 230027, China) Abstract: A new adaptive anti-collision algorithm based on binary-tree disassembly is proposed in this paper. In order to enhance the search efficiency, a big and complex binary-tree is disassembled to several small and simple binary-trees by estimating the distributing of tags. The introduction of the collision stack, as well as adjusting the search paths adaptively based on the state of slots, the performance of the new algorithm is improved further, including reducing the search timeslots and improving the throughput of timeslots. Theory and computer simulations show that the new anti-collision algorithm is practical, especially when the number of tags is large. Key words: Radio Frequency IDentification (RFID); Anti-collision algorithm；Binary-tree disassembly; Collision stack 1引言 射频识别(RFID)是20世纪90年代兴起并逐渐走向成熟的一种非接触式的自动识别技术，在物流、跟踪、定位等领域已得到广泛应用。其中，用于解决读写器作用范围内多标签识别问题的防碰撞算法已成为该领域研究的热点之一。 标签防碰撞算法主要解决在读写器有效通信范围内，多个标签同时与读写器进行通信的问题。常用的防碰撞算法一般可以分为两类，一种是基于时隙随机分配的ALOHA算法[1]，包括动态时隙ALOHA(DSA)算法[1]，分群时隙ALOHA 算法(GSA)[2]和标签估计算法(TEM)[3]等。其特点是，算法简单，便于实现，适用于低成本RFID系统。但由于该类算法的时隙是随机分配的，即存在一定的可能性，某一标签在相当长的一段时间内无法识别，即“tag starvation”问题，所以这类方法被称为可能性方法。另一类是基于二进制树搜索(BS)算法[1]，包括动态二进制搜索(DBS)算法[1]，自适应二 2008-07-02收到，2008-12-08改回 高等学校博士学科点专项科研基金(20020358033)资助课题叉树搜索算法(ABS)[46]?，自适应查询树算法(AQS)[7]、返回式搜索算法(BackTrack)[8]和后退索引搜索算法[9]等。该类算法比较复杂，识别时间较长，但不存在“tag starvation”问题，又被称为确定性方法。 本文提出了一种基于二叉树分解的自适应防碰撞算法。新算法在二叉树搜索算法的基础上，利用标签EPC (Electronic Product Code，即电子产品代码)的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。通过引入碰撞堆栈，并根据时隙状态自适应地调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。 2防碰撞算法原理及相关的研究成果 对于一个特定的RFID系统来说，任意一个RFID标签都有一个唯一确定的EPC。读写器通过获取标签的EPC来确认标签的身份。当读写器作用范围内有多个未识别的标签时，
南阳理工学院 本科生毕业设计（论文） 学院（系）：计算机与信息工程学院 专业：通信工程 学生：乔军惠 指导教师：路新华 完成日期 2012 年 4 月 南阳理工学院本科毕业设计（论文）RFID二进制树防碰撞算法设计
学院（系）：计算机与信息工程学院 专业：通信工程 学生姓名：乔军惠 学号： 1 指导教师（职称）：路新华（讲师） 评阅教师： 完成日期：2012年4月 南阳理工学院 Nanyang Institute of Technology RFID二进制树防碰撞算法设计 【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，但是也带来了解决思路不统一的矛盾。在传统思路中，一般是通过单片机来进行算法处理，随着RFID技术的发展，未来的一个重要方向是现场可编程门阵列FPGA，做为一种现场可编程的专用集成电路，FPGA拥有高速度，可编程等多个适应于算法处理的优点，从而为RFID防碰撞算法问题开辟了新的有效途径根据上述分析，全文针对RFID系统二进制树防碰撞算法，进行了理论与实践方面的探讨，主要分为三个方面，首先是二进制树算法的理论研究，将现有的二进制树算法进行了归纳，汇总为基本算法，动态算法，退避式算法三类，阐述了各个算法的思路，对其进行了性能评价；其次，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。 【关键词】：射频识别；防碰撞算法；读写器；应答器；现场可编程门阵列 Abstract RFID is anewly developedtechnologywhich communicates through the—contact RF signal，so asto achieve objective automatic identification．Along with the development of RFID technology，how to realize Data Exchange accurately amongMultiple Targets at the same time becomes the key problem of RFID technology．RFID anti-collision algorithm is the solution to the above mentioned problems．In all the algorithms，binary algorithm is most widely used as an international standard fbr its exactness ofidentincation．International standards have put forward manyregulations on binary algorithm．It not onlypromotes the development of anti．coUision algorithm，but
摘要 射频识别（Radio Frequency Identify，RFID）技术是一种无线通信技术。多目标识别是RFID技术的优点，同时也是一项富有挑战性的技术。阅读器碰撞是RFID技术的关键性问题，它会影响RFID的读取速度。本文主要介绍基于调度和基于有效范围的阅读器反碰撞算法，如LLCR，Colowave，Pulse等，并对它们做了总体比较与评价。 关键词: 射频识别；阅读器碰撞；基于调度；基于有效范围 Abstract RFID is regarded as a wireless communication technology, which possesses many advantages. Multi-target identification is both the advantage and the challenge of RFID technology. Reader collision ,which affects the speed of RFID,is a key problem of RFID technology. The main part of the paper focuses on the scheduling-based and coverage-based reader anti-collision algorithms, such as LLCR, Colorwave, Pulse, etc. Meanwhile the overall comparison and estimation of the algorithms is given Keywords: RFID; Reader collision; Scheduling-based; Coverage-based I
RFID中防碰撞算法研究 RFID(Radio Frequency Identification),即射频识别,是20世纪90年代兴起的非接触式的自动识别技术,它通过射频信号自动识别目标对象并获取相关数据。RFID系统在货物跟踪和库存管理等物流供应链等方面发挥了越来越重要的作用,为物流供应链管理提供了最便捷有效的实施方案。其应用包括产品认证、质量控制、仓储管理、物流供应、偷盗检测以及自动结账等诸多方面,而且未来RFID市场的潜力仍不可估量。RFID技术中无人工干预和可复用两大特点体现了它巨大的潜力和应用前景。 随着RFID标签价格的进一步降低,RFID技术将更具优势和吸引力。本文围绕RFID系统防碰撞算法展开研究。首先对RFID的发展历程、分类、特点、国内外研究和发展现状、在物流管理中的实践意义和应用障碍、防碰撞算法研究现状进行简单的介绍。在简单介绍了RFID系统结构和工作流程的基础上对其中的关键技术之一——标签防碰撞算法进行重点讨论,概述了防冲突方案,对现有的两大类防碰撞算法进行分析比较。 进一步对ALOHA算法及其发展的算法进行仿真分析,在已有的随机算法的基础上提出了一种改进算法,并通过MATLAB仿真加以验证。论文的重点是第3章和第4章,详细分析和比较固定帧时隙ALOHA算法和动态帧时隙ALOHA算法;并针对读写器与标签通信时的防碰撞问题设计了一个改进的动态帧时隙ALOHA算法。在标签数很多的情况下,通过估算现有标签数目,将标签分组,然后每组标签分别调用动态帧时隙ALOHA算法,通过估算每组中发生碰撞的时隙数动态调整每帧时隙数,从而提高了系统效率,增强了系统的稳定性。在此基础上,应用MATLAB工具对改进算法进行了仿真,并对仿真结果进行了比较、分析,验证了模型的正确性和可行性。 最后对本文的研究成果和存在的不足进行了总结和分析,为进一步研究提出展望。
科技信息 1.引言RFID （Radio Frequency Identification ）是一种非接触式自动识别技术，它利用射频信号与空间耦合及传输特性来双向通信，实现对物体自动识别与信息采集。由于超高频（UHF ）860～960MHz 具有读写速度快、识别距离远、抗干扰能力强、标签小等优点，对UHF 频段的相关技术研究已成为全球RFID 产业和研究部门关注的热点。 一个典型的RFID 系统由读写器(Reader)、电子标签(Tag ，简称标签)、天线(Antenna)以及数据处理系统组成。标签可以存储被识别物体的相关信息，读写器通过射频信号与标签进行通信，并与后端数据库进行连接。而当RFID 系统工作时，读写器的周围存在多个标签，就可能有两个或两个以上的标签同时向读写器发送数据，从而产生通信冲突，导致阅读器无法读出数据，这就是所谓的碰撞。解决碰撞问题的算法称为防碰撞算法。比较经典的两类基本方法是：ALOHA 算法和二进制搜索算法。 2.UHF 频段RFID 系统防碰撞算法对于UHF 频段的RFID 系统，由于信号识别的距离远，覆盖的范围广，因而需要识别的标签数量大，所以更需要良好的防碰撞算法以减少冲突，达到快速、准确识别多个标签的目的。 针对UHF 频段，主要的国际标准是ISO/IEC18000-6协议，它包括Type A 、B 、C 三种类型。如表1所示它们之间的主要区别在于编码方式及防碰撞算法的不同。 表1ISO/IEC18000-6标准三种类型比较技术特征 类型 工作频率调制方式编码方式数据速率 防碰撞算法 其中R→T 表示于阅读器向标签发送数据，T→R 表示标签向阅读器发送数据 R→T T→R R→T T→R R→T T→R TYPE A 860～960MHZ ASK 反向散射PIE FM033kbps 40kbps ALOHA TYPE B 曼彻斯特FM010kbps or 40kbps 40kbps 二进制树 TYPE C PIE FM0or Miller 26.7～128kbps FM0:40～640kbps Miller:5～320kbps 时隙随机防碰撞 TYPE A 采用的是一种动态时隙ALOHA 算法防碰撞协议，电子标签内部需要有随机数发生器和比较器，设计相对简单。ALOHA 算法本质上是基于概率的，在确定时间内依靠一定的概率分辨出所有读写器工作范围内的电子标签，但如果在识别区域内的电子标签的数目相对开始识别命令中指定的初始时隙数较多时，防冲突的过程就会比较长，这是TYPE A 防冲突机制的不足之处。Type B 应用的防冲突机制要较Type A 的更有效一些，但防碰撞的效率会随应答器的数量增多而下降，而且该算法时延长，泄露的信息较多，安全性差。TYPE C 应用的防碰撞算法是时隙随机防碰撞仲裁机制，是动态ALOHA 算法的改进，在帧大小调整方面比以往动态帧时隙ALOHA 算法有很大改进。它具有较高的阅读速率，在美国已达到1500标签/秒,欧洲可达600标签/秒，同时也适合在高密度多个读写器的环境下工作。因此本文重点分析该算法及其改进方法。 3.ISO18000-6C 标准防碰撞算法分析3.1算法描述 ISO/IEC 18000-6C 标准采用的是时隙随机ALOHA 算法，该标准已经成为全球性超高频RFID 主流规范之一，该算法流程如图1所示。 图1算法流程 Query 包含一个时隙计数参数Q,当接收到一条Query 命令时,在进 入识别区域内的所有标签中随机选取2Q 个标签,参与的标签应在含(0,2Q -1)范围内选出一个随机数,并将这个数置入它们的时隙计数器,若进 入识别范围的标签数m 小于2Q 则随机数取值(0,m)。选到零值的标签应转移到应答(Reply)状态,开始与阅读器的数据交换。选到非零数的标签应转移到仲裁(Arbitrate)状态,并等待下一条Query Adjust 或Query Rep 命令。其他没有得到时隙计数器值的标签仍然保持休眠状态。 然后,处于仲裁和应答状态的标签,接收一条Query Adjust 命令时,Q 值调整(增大、减小或不变),然后在含(0,2Q -1)范围内选出一个随机数,置入它们的时隙计数器。选到零值的标签应转移到应答状态,并立即回答。选到非零值的标签应移到仲裁状态,并等待下一条Query Adjust 或Query Rep 命令。处于仲裁状态的标签每接收到一条Query Rep 命令时,他们的时隙计数器值减1一次。时隙计数器调整后,值为0的标签转移到应答状态,并立即与阅读器进行数据交换。 在一个轮询周期中，每个时隙内的标签响应有三种情况：没有标签响应（空时隙）；有一个标签响应（没有碰撞的时隙）；有一个以上的标签响应（碰撞时隙）。设标签数量为x ，阅读器通过Query 命令来产生随机 数Q 所给出的时隙数为A=2Q 。对于每个时隙而言，某个标签在其中响 应的概率为A -1 ，该标签不在其中响应的概率为(1-A -1)。共有x 个标签，可以看成对每个时隙进行x 次试验，上述情况符合二项分布B(x,A -1 )。在多标签识别过程中，标签数比较多。因此，x 很大而A -1很小，此时，二项分布近似为泊松分布。泊松分布参数： λ=n ×p =x ×1A （1） 则一个时隙内有k 个标签响应的概率为： P k =λk k ! e -λ（2） 由式(2)可知，在一个时隙内一个标签响应的概率为： P 1=λ×e -λ （3）一个时隙内有一个标签响应也就是没有发生碰撞，此时标签被识别出。对式（3）求导，可以证明，当x=A 时，P1取最大值为0.3679。也就是说，当标签数与时隙数相等时，时隙利用率最大，最大时隙利用率为0.3679。 3.2算法分析 ISO/IEC 18000-6C 标准算法虽然比其它Aloha 算法性能上有很大改进，但仍然存在一些缺陷： （1）仍存在某个标签永远都无法被识别的现象。假设有一个标签和另外一个标签同时响应读写器，这两个标签反射UHF 频段RFID 系统中的防碰撞算法研究 车晓明1封志宏1李高科2 （1.兰州交通大学电子与信息工程学院 2.中国铁道科学研究院电子计算技术研究所） ［摘要］电子标签的“碰撞”在RFID 系统中是一个很常见的问题，特别是在UHF 频段，如何有效地解决这一问题显得尤为重要。本文主要对ISO/IEC 18000-6中A 、B 、C 三种模式进行了分析，比较其优缺点，并对ISO/IEC 18000-6C 协议进行了详细的研究，提出了改进其防碰撞算法的思路。［关键词］RFID 防碰撞时隙ALOHA 算法时隙不完全竞争算法 （下转第588页） — —593