摘要
射频识别（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
[键入文字]
第1章引言
1.1课题研究背景
无线射频识别（Radio Frequency Identification，RFID）技术是一种从二十世纪90年代兴起的一种非接触的自动识别技术。它的工作原理是利用射频信号和空间耦合传输特性进行非接触式双向通信，实现对被识别物体的自动识别并获取相关数据[1]。
RFID系统由射频读卡器，标签和软件系统组成。随着物联网的兴起，RFID系统被广泛应用于物流，仓储等领域。例如，射频读卡器被安装在手机中，通过3G网络或者WiFi网络提供服务。用户可以通过查询贴在电影海报上的标签，从网上获得这部电影的相关信息，然后用户可以观看这部电影的预告片或者决定是否要购买电影票。另外，通过读取贴在超市货架产品上的RFID 标签，消费者可以获得产品的重要信息，诸如产地，使用方法，有效期等。
作为又快又准的信息采集与处理技术，RFID技术被世界公认为21世纪十大重要技术之一，它是继移动通讯技术，互联网技术之后影响全球经济与人民生活的一项革命性技术[2]。RFID系统有诸多的优点，如射频读卡器可以覆盖较大的范围，在这范围内获得多个标签的信息。同时RFID的标签包含的信息容量要比传统的条形码多。另外，它具有精度高，抗干扰能力强，使用寿命长，覆盖范围广，适应环境能力强等优点。随着RFID技术的不断发展，在物流，交通，零售等领域将占有举足轻重的地位，具有广阔的应用前景。
近年来，国内外都非常重视RFID技术的研发与运用[3]。自2003年，美国国防部与沃尔玛开始推动RFID应用以来，RFID取得了飞速的发展。2007年到2009年，全球RFID市场进入了快速增长阶段，其年均增长率超过50%，在此之后保持着平稳的增长态势[4]。在欧美等发达国家，RFID技术的研究与应用已经达到相当高的水平，例如，日本索尼公司利用RFID技术，将RFID标签与闭路电视摄像头相互整合来检测库存，提高了安全性[5]；西班牙利用RFID精简了医药供应链；荷兰采用RFID标签来监控花的栽培过程。
相对于发达的欧美国家，我国国内的RFID技术的研究与应用还处于落后阶段。但是在某些领域内已经有所应用，如交通，物流等领域。随着RFID的深入研究及应用普及，我国的RFID将大规模的运用。
1.2课题研究意义
作为一种新兴的技术，RFID虽然有着诸多优点，但是还存在一些不足，例如：RFID系统的识别率不高，标准不统一，标准进程缓慢，成本偏高等。现在，统一RFID技术的标准是当前的一个焦点问题。因为存在标签碰撞和阅读器碰撞，标签识别率较低，这对于研究快速，准确，有效的防碰撞问题是一个非常有意义的课题。
RFID系统中的碰撞问题主要有两类。第一种是标签碰撞，第二种是阅读器碰撞。本文主要探讨阅读器碰撞以及针对它的防碰撞算法。
在RFID应用系统中，阅读器是读取标签中的信息并将其输入软件系统来获取该产品对应信息的工具。由于功率的限制，每个阅读器的读写范围都是有限的，这个范围称作询问区，只有在询问区内，标签和阅读器才能进行通信。当需要大面积部署阅读器时，多个阅读器之间的询问区域会产生重叠，这样就产生了同频干扰，此时阅读器之间会出现信息碰撞问题。由阅读器的操作而引起的阅读器之间的相互干扰被称为阅读器碰撞。
在实际的应用中，由于阅读器网络的拓扑结构基本不变，所以可以通过给阅读器分配不同的频率或者时隙，碰撞问题将得到有效解决。另外，为了获得最优解，我们可以利用遗传算法来解决，从而将阅读器的网络布局最优化。
1.3国内外研究现状
1.3.1国内研究阅读器反碰撞现状
Kim.J等人将RFID阅读器网络分成具有一定层次的阅读器簇结构[6]，根据一定的权值动态调整每一簇间询问半径，在保证区域内所有标签均被覆盖的前提下，减少阅读器簇间的询问重叠区域，从而最小化阅读器网络中的阅读器碰撞。该方案在现实中难以实施，因为RFID应用环境非常复杂，阅读器簇间询问半径的动态调整策略难以确定。Anusha S.和Iyer S.针对仓储应用中大量物品的识别和追踪问题，采用手持阅读器策略来一次对所有物品进行识别[7]。在给定的应用环境和相应特性阅读器的情况下，该系统能自动生成关于所有阅读器数量，方位安排和移动式等布局信息。但是该方案在阅读器询问区一旦出现混淆情形下，就会失效。R.E.Bellamn和S.E.Dreyfus提出了Q-Learning算法，
- 2 -
该算法是在一个分等级的在线学习算法[8]，通过学习阅读器碰撞模型动态的解决RFID系统中阅读器碰撞问题。其思想类似于无线传感器网络中的分簇算法。这种方法如果应用在RFID系统中，将存在下面的问题：协议保持多层结构需要额外的开销。对于移动的阅读器来说，网络拓扑结构不确定的变化将会改变Q学习算法的多级结构。这就需要重新分配时隙，讲话去更多时间并使系统无效。
1.3.2国外研究阅读器反碰撞现状
田景贺，范玉顺等人针对密集阅读器环境下的RFID阅读器碰撞情况提出了一种阅读器碰撞问题的集中控制方法[9]。该方法根据平面图着色理论，将密集阅读器网络的阅读器防碰撞问题等效为阅读器网路的时隙分配问题，并建立了解决阅读器碰撞问题的神经网络模型，并引入了模拟退火策略及混沌思想对阅读器防碰撞神经网络模型进行求解。与现有的分布式防碰撞算法相比，该方法能够保证阅读器具有更多的标签时间和更高的标签扫描频度；徐雪慧，李玲远等人基于图着色算法提出一种改进的算法[10]，这种算法的主要思想是：阅读器采用两个通道，一个用于控制通道（阅读器之间通信），一个为数据通道（阅读器与标签之间通信），把阅读器和射频标签的信号传输分割开，这样碰撞只能在标签与标签之间或者阅读器与阅读器之间发生。这种分割使阅读器和射频标签信号在不同的频道上传输，解决了阅读器间的干扰。
- 3 -
第2章RFID系统概述
2.1RFID系统组成
2.1.1RFID系统组成
RFID系统由三部分组成[11]：阅读器（Reader），电子标签（Tag）和软件系统。如图2-1为RFID系统的构成图。
图2-1 射频识别（RFID）系统基本组成
标签即射频卡，每个电子标签都是有一个唯一可识别码，所以它可以用来代表它所附着的物体。电子标签的存储单元在K bits量级，它的反复读写的次数在10000次以上。
RFID标签分为主动式（Active）和被动式（Passive）两种。主动式标签中含有内置电池，可以主动向邻近的阅读器发送射频信号。被动标签内不含电池，无法独立发射信号，它的工作与否主要靠是否接收到阅读器发出的电磁波信号，该类标签可以将电磁能量转化为提供它工作的能量。它们之间的区别如表1所示。
- 4 -
表 1 主动标签与被动标签性能比较
阅读器用于读写电子标签的信息，主要任务是控制阅读器向标签发射信号或读取来自标签的信号，并对信号进行解码，而后送至软件系统进行处理。
软件系统由人对计算机进行控制来完成数据信息的存储及管理。它通过网络与分散在各地的阅读器通信，实时获取阅读器捕获到的电子标签信息。
2.1.2RFID系统的基本工作流程
RFID系统工作流程[12]如下：
(1)无线电载波信号通过阅读器的天线向外发射。
(2)如果电子标签在发射天线的覆盖范围内，则它被激活，将标签内的信
息通过天线传给发射天线。
(3)系统的接收天线接收电子标签发出的载波信号，经天线的调节器传输
给阅读器，阅读器对接收到的信号进行解调与解码，然后送到软件系
统处理。
(4)软件系统的程序通过判断标签的合法性，针对不同的情况作出相应的
处理和控制，完成对应的动作。
- 5 -
第3章阅读器碰撞
3.1阅读器碰撞含义
阅读器碰撞是指：多个阅读器同时与一个标签通信，导致标签无法识别是哪个阅读器发送的请求信号；也包括相邻的阅读器在同一时刻使用相同的频率与其覆盖区域内的标签通信而引起的频率碰撞。
3.2阅读器碰撞的主要特点
RFID网络中，阅读器之间的碰撞主要有下列特点：
(1)当多个阅读器发送的请求信号在某标签处产生碰撞时，该处的信号会
变得非常混乱，从而导致标签无法识别由任何阅读器发出的信号。
(2)本文研究的RFID标签是被动式标签。标签在被阅读器请求信号激活
后才能通信，并且标签不参与阅读器的防碰撞过程。
(3)隐蔽节点问题，是阅读器碰撞的一个方面。两个阅读器不再相互监听
范围内而在标签处产生信号干扰时，载波监听机制失效。
3.3阅读器碰撞问题分析
3.3.1多阅读器与标签之间的干扰
当多个阅读器同时阅读同一个标签时，引起了多阅读器到标签之间的干扰，该类干扰分两种情况。一种是两个阅读器与阅读器范围重叠，如图3-1所示。
- 6 -
- 7 -
标签
图 3-1 阅读器与标签碰撞
从阅读器R1和R2发射的信号可能在射频标签T1处产生干扰。在这种情况下，标签T1不能芥末任何查询信号并且阅读器R1和R2都不能阅读T1。另外一种两个阅读器阅读范围没有重叠，如图3-2所示。
读写器
标签
图 3-2 阅读范围不重叠的多阅读器对标签的干扰
虽然阅读器的读取范围没有重叠，但是处于相互感应范围之内，且他们同时利用同一频率与标签T1通信，阅读器R2发射的信号对阅读器R1发射的 信号在标签T1出产生干扰，将降低他们之间的通信质量。
3.3.2 阅读器与阅读器之间的干扰
多阅读器与标签之间的干扰，即标签干扰是指：当一个阅读器发射的较强的信号与标签反射给另一个阅读器的微弱信号产生干扰，这就引起阅读器与阅读器之间的干扰。
如图3-3所示，阅读器R1位于阅读器R2干扰区内，标签T1在R2的覆
- 8 -
盖范围内。当标签T1反射回的微弱信号传输给阅读器R1的过程中，很容易被阅读器R2发射的强信号干扰。这时，R1很难读取到T1返回的正确信号。对于该类干扰来说，阅读器的询问区域的重叠并不是必须的。
标签
图 3-3 阅读器与阅读器之间的干扰
3.4 RFID 阅读器网络问题
随着RFID 技术的广泛应用，在同一场合有多个阅读器连接在一起同时工作的情况越来越多，于是出现了阅读器网络问题。由于阅读器网络节点与传统的无线传感器网络有很多相似之处，因此阅读器网络也有传统无线网络通信的一些问题，如隐藏终端和暴露终端问题。所以，在设计阅读器防碰撞算法的时候需要充分考虑阅读器之间的碰撞的情况，以提高阅读器的工作效率。所以在此有必要对阅读器网络中阅读器节点的隐藏终端和暴露终端的基本概念，解决方法[16][17]等加以阐述。
3.4.1 隐藏终端
3.4.1.1 阅读器隐藏终端问题
隐藏终端是指在接收阅读器的覆盖范围内而在发送阅读器的覆盖范围外的阅读器。由于听不到发送阅读器的发送信号，隐藏终端可能向同一个接受阅读器发送分组，导致分组在接收阅读器处产生碰撞。碰撞发生后阅读器要重传碰撞的分组，导致信道的利用率降低。
阅读器A的覆盖范围
图3-4 隐藏终端C
如上图3-4所示，阅读器A和C同时想发送数据给阅读器B，但A和C 都不在对方的覆盖范围内。所以当A发送数据给B时，C并未检测到A也在发送数据，会认为目前网络中无数据传送，会将数据发送给B。这样，A和C 同时将数据发送给B，使得数据在B处产生冲突，最终导致发送的数据不可用。这种因传送距离而发生误判的问题称尾隐藏终端问题。
为了解决上述问题，可以使用请求发送信号（Request to Send，RTS）和清除发送（Clear to Send，CTS）的控制信息来避免冲突。当A要向B发送数据时，先发送一个控制报文RTS：B接收到RTS后，以CTS控制报文回应：A收到CTS后才开始向B发送报文，如果A没有收到CTS，A认为发送碰撞，重新发送RTS。这样隐发送终端C能够听到B发送的CTS，知道A要向B发送报文，C延迟发送，这样解决了隐发送终端问题。
3.4.2暴露终端
3.4.2.1阅读器暴露终端问题
暴露终端是指在发送阅读器的覆盖范围内而且在接受阅读器的覆盖范围外的阅读器。暴露终端因听到发送阅读器的发送信号而可能延迟发送。然而它是在接收阅读器的覆盖范围之外，它的发送不会造成碰撞。这就引入了不必要的时延。
- 9 -
图3-5 暴露终端C
暴露终端与应藏终端问题不同，当一个终端要发送数据给另一个终端时，因邻近终端也正在发送数据，影响了原来终端的数据传送。如上图3-5所示，4个终端A，B，C，D，其中A，D均不在对方的传送范围内，而B，C均在彼此的覆盖范围内。因此，当B正传送数据给A时，C是不能将数据发送给D的，因为C会检测到B正在发送数据。如果其他发送数据的话，就会影响B 的数据发送。而事实上，C是可以正确无误地将数据发给D的，因为D在C 的覆盖范围内。
- 10 -
第4章阅读器防碰撞技术
4.1防碰撞算法研究分类
针对标签碰撞问题与阅读器碰撞问题，分别提出了对应的算法，称为标签防碰撞算法与阅读器防碰撞算法。如图4-1为RFID系统防碰撞算法的整体研究框架。
防冲突算法
标签
阅读器标签驱动
读写器
驱动
基于有效
范围
基于调度
确定性
随机性
轮询
图4-1防碰撞算法研究路线
在RFID系统碰撞问题中，标签防碰撞算法是研究比较多的，如图4-2是标签防碰撞算法分类。其解决方法主要分为：频分多址（FDNA），码分多址（CDMA），时分多址（TDMA）和空分多址（SDMA）[16][17]。
- 11 -
图4-2 RFID标签防碰撞算法
频分多址（FDMA，Frequency Division Multiple Access），是利用不同信道传输信号以避免信号碰撞的一种方法，即阅读器将一定的频率范围分为更细的频道，不同的阅读器采用不同的信道与标签进行通信。
时分多址（TDMA，Time Division Multiple Access），是防信号碰撞中族常使用，也最成熟的一项技术，其原理是利用时间的差异，将可以使用的通讯时需分配给不同的阅读器进行数据传输，排定先后顺序后依序与标签进行通信。这类似于凸轮中的图形着色问题，是一个NP-hard问题。对于RFID系统，TDMA称为防碰撞算法最大的一族。
载波监听多路访问（CSMA,Carry Sense Multiple Access）。在RFID网络中，像其他的无线网络一样，存在隐蔽节点问题。不再互相侦听范围内的阅读器在标签处发生干扰，因此仅仅依靠载波监听无法避免RFID网络中的碰撞问题。
码分多址（CDMA，Code Division Multiple Access）需要在射频标签上增设额外的电路，大大增加了标签的成本，并且给网络中所有的标签分配码是一件复杂的工作。因此CDMA不是一种成本低并且有效的方法。
空分多址（SDMA，Space Division Multiple Access）主要实现方式是在阅读器上使用相控阵天线作为电子控制定向天线，使天线的反向图一次对准作用范围内不同的标签，从而实现多路村粗。由于天线的规模限制，只有频率在850MHz以上时，SDMA才可以在RFID中应用，而且复杂的天线将造成相对高的成本。因此，这种方法只适用于一些特定场合。
- 12 -
4.2阅读器防碰撞基本原理
由于标签含有可被识别的唯一序列号，RFID系统可以容易得获取信息[18]。如果仅存在唯一的标签在某个阅读器的覆盖范围内，则阅读器可以直接获
取标签的信息；如果有多个标签在一个阅读器的覆盖范围内，在信道共用，频率相同的情况下，它们同时将信号传给阅读器的，这时各信号之间互相干扰，信道争用问题随之产生，数据发生碰撞，从而导致阅读器和标签之间的无效通信。为了防止这些碰撞，RFID系统中需要设置一定的相关命令以解决碰撞问题，这些命令被称为“防碰撞算法”（Anti-collision algorithms）。
解决标签碰撞问题和阅读器碰撞问题的方法分别称为标签防碰撞算法和阅读器防碰撞算法。
4.3阅读器防碰撞算法研究与分类
阅读器能够顺利获取在其覆盖范围内的电子标签信息，以及对信息的读写操作。目前，主要通过采用时分多址（TDMA）原理，使每个电子标签在单独的某个时隙内占用信道与阅读器进行通信，防止碰撞产生。
目前，无论国内还是国外，研究RFID阅读器反碰撞算法都很少。主要的反碰撞算法主要分为以下两大类:其一是基于调度（Scheduling-based），其二是基于有效范围（Coverage-Based）。对于前者，其核心思想是防止阅读器同时发送信号给标签，以此避免发生碰撞，该类算法一直是反碰撞算法的主流。对于后者，其核心思想是将阅读器之间的重叠区域减小来降低发生碰撞的概率，相对于基于调度的方案来说，该类算法比较少。反碰撞算法分类如图4-3所示。
- 13 -
图4-3 阅读器反碰撞算法分类
4.3.1基于有效范围的反碰撞算法
目前，基于有效范围的反碰撞算法主要有LLCR（Low-Energy Localized Clustering for RFID networks）[19]和w-LCR（weighted Localized Clustering for RFID networks）[6]，这类算法主要手段是改变阅读器的发射功率，其核心目的是调节它的通信范围，从而减小阅读器与阅读器之间的重叠区，最终达到降低阅读器之间的碰撞概率的效果。
4.3.1.1LLCR算法
LLCR[19]算法主要通过调整RFID阅读器的聚类半径R，使得代价函数f r r rΦΦΦ最小，从而降低阅读器之间的碰撞。聚类半径模型如图(1,2,3,1,2,3)
4-4所示，半径R的大小由公式（1）决定。该算法一共分为两个阶段。第一阶段为初始阶段，第二阶段为聚类半径调节阶段。在初始阶段中，其核心任务是
- 14 -
- 15 -
找到中心点CRDP 以及聚类半径R ；在聚类半径调节阶段，其主要任务是在一定条件2i r 下，通过调节控制代价函数f ，使其达到最小。
123R N CRDP N CRDP N CRDP =++
（1） 3
23111(1,2,3,1,2,3)123k k k triangle k k k E f r r r r S E ==ΦΦΦ=Φ-∑∑ （2）
222()()i CRDP i CRDP i r x x y y =-+-
（3）
图 4-4 LLCR 算法模型
R ，r i 2，(1,2,3,1,2,3)f r r r ΦΦΦ，如公式（1）（2）（3）所示。其中k E 表示阅读器的能量，阅读器所能覆盖的范围，triangle S 为三角形的面积，r i 为中心
点CRDP 到位于三角形各顶点阅读器的距离，F i 为三角形各顶角的度数。
4.3.1.2 w-LCR
w-LCR 算法与LLCR 算法模型一样，前者是对后者的改进版本。它们之间的区别在于，计算公式增加了触发函数与激励函数，从而代价函数f 得到了平衡，增加了算法的鲁棒性。从稳定性和效率方面来说，w-LCR 要比LLCR
强的多。
4.3.2基于调度的反碰撞算法
目前阅读器反碰撞算法的主要方法是基于调度的反碰撞算法，很多阅读器的反碰撞算法都属于基于调度的方法，其核心思想是防止阅读器同时给标签发送信号，以此达到避免阅读器之间的碰撞。
4.3.2.1ETSI EN 302 208(CSMA)[20]算法
该协议是由欧洲电信标准协会（E uropean T elecommunications S tandandards Institute 简称ETS）提出的RFID标准，称为“电磁兼容和无线电频谱事项”。欧洲RFID标准规定的阅读器频率范围是865MHz～868MHz，带宽为200KHz，最低子带的中心频率是865.1MHz，共有15个频点，从865.1MHz每个200KHz到867.9MHz。同时，如表对于200KHz带宽内的频谱功率分布有着严格要求。
表2频谱功率分布
CSMA算法是欧盟采用的RFID阅读器反碰撞标准，该算法采用CSMA机制。该RFID标准规定，阅读器在发出命令前，必须先侦听该频点是否已经被占用。如果有信道空闲，则马上传输数据。否则，不能在该频点发出请求，要采取退避策略。上表是侦听的载波功率阈值。当阅读器竹内在865.1MHz～865.6MHz频段内工作时，必须先侦听该频段内的已存在的载波功率。如果监听到的载波功率-83dBm，那么阅读器就不能利用该频段工作，必须跳到其他的频点继续侦听。直到找到一个空闲的频点才能工作。以此来看，避免两台阅读器同时工作在同一频点而产生的干扰是该项标准的主要目的。
该算法与传统的CSMA协议相似，实施比较容易。但是，这种“先侦听后发送”的机制，并不能完全规避多阅读器与标签之间的额碰撞。阅读器可能无法通过载波监听到碰撞的发生，并且由于该算法无法解决传统无线网络隐终端和暴露终端的问题，所以此标准的效率不是很高。如图所示，R1处于阅读器R2的感应范围之外，但是A发出的信号与B发出的信号在标签T1出产生碰撞。
- 16 -
读写器
标签
图4-5 ETSI EN 302 208 协议对RFID阅读器碰撞问题缺陷
4.3.2.2Class I Generation 2 UHF算法
Class I Generation 2 UHF[21]由EPCGlobal起草使用的频分复用算法，是超高频的第二代标准。它分别使用阅读器传输和标签传输，那样使得阅读器只与阅读器产生碰撞而不会与标签发生碰撞，而标签也只与标签产生碰撞与不会与阅读器产生碰撞。这样分开处理，解决了阅读器与阅读器碰撞，因为阅读器数据传输与标签传输是在独立的信道中进行的。
但是由于标签没有频率选择功能，当两个不同的频率同时去读同一个标签时，还是会产生阅读器对标签的碰撞。因此在这个标准中多阅读器对标签的碰撞还是不能避免的。
4.3.2.3Colorwave算法
Colorwave[22]算法是由James Waldrop, Daniel W.Engels 和Sanjay E.Sarma 提出的。它是一种基于TDMA的分布式防碰撞算法。在Colorwave算法中，RFID系统的网络被当作一个图，阅读器被认为是一个节点。为了给网络中每个阅读器不同的颜色，Colorwave利用DCS（Distributed Color Selection）和VDCS（Variable－Maximum Distributed Color Selection）为阅读器网络着色。在Colorwave算法中，颜色代表阅读器传输的时隙。具体算法是：每个阅读器选择任意一个时隙（颜色）发送请求信号，然后在属于自己的时隙中读取标签信息。如果某个阅读器选择的时隙与邻近的阅读器选择的时隙相同，那么它们之间就会产生碰撞。当检测到碰撞发生时，阅读器会选择另一个新的时隙（颜色）试图传输，并且发送一个‘kick’信息给它的邻近阅读器。这个‘kick’信息被用来告诉邻近的阅读器，‘我’已经开始选择新的时隙（颜色），如此往复进行下去。
- 17 -
虽然Colorwave算法能够有效的解决阅读器碰撞算法，但是它仅适用于静态的拓扑结构网。对于动态环境，一个节点的变动将会导致整个阅读器网络的变化。另外，Colorwave算法同样要求时间同步，然而在Ad Hoc网络中，实现同步是比较困难的工作。
因为TDMA调度需要阅读器支持同步及高移动性能，这样会产生大量的通信调度开销，所以Colorwave算法不适用于移动式RFID阅读器。另外更为糟糕的是Colorwave没有使用多信道来传输信息，所以阅读器的会产生较长的等待时间。阅读器较长的等待时间会导致吞吐量降低。
4.3.2.4Pulse算法
Pulse[23]算法将控制信道与数据信道分离。数据信道被用来在阅读器与标签之间通信，控制信道被用来在阅读器之间通信。采用这种机制后，在控制信道上的控制信息传输不会影响到数据信道上数据信息的传输。在Pulse算法中，当阅读器与标签通信时，阅读器会通过控制信道定期的向它几百米之外的范围发送‘beacon’信息。接收到‘beacon’消息的阅读器将不会立即与标签通信，而是选择等待，直到它不再接收到任何‘beacon’消息为止。
通过Pulse算法，任何一种碰撞问题都可以避免，同时它也符合移动式RFID阅读器的使用环境。然而，因为邻近阅读器在阅读器的干扰范围内，它将被强制禁止读取任何标签信息，这样就浪费了信道资源。
另外，Pulse算法作为一种性能比较优越的算法，它成功避免了阅读器网络的隐终端和暴露终端问题，因此效率得到了提高。但是Pulse算法周期性的发送信息给邻近的阅读器，将加快阅读器的能耗。虽然Pulse算法在效率方面都有了很大的提高，但是并没有完全解决隐终端和暴露终端的问题。
4.3.2.5DiCa（Distributed Tag Access with Collision-Avoidance）算法
DiCa[24]算法与前面的算法比较，它不要求集中协调和全局的时间同步。由于DiCa是Pulse的改进版本，所以DiCa和Pulse有很多相似之处，例如，它们都是用两个独立的信道来传输信息和数据。不同之处在于DiCa在读取数据时不再是周期性地发送信息给周边的邻居阅读器，而是在读取数据结束后再发送读取结束信息，这样在控制能耗方面可以取得很好的效果，另外DiCa很好地处理隐终端和暴露终端问题，这样很大程度上提高了阅读处理数据的效率。
但是DiCa算法在采取退避算法时，为考虑阅读器的具体位置，不管阅读器之间是否存在干扰区域都直接进行退避，如图4-6所示。由于A和C没有重叠区域，它们之间不存在干扰，也就是说A和C是不可能发送碰撞，所以采
- 18 -
- 19 -
取退避算法实际上是浪费了时间，因为在B 完成数据读取后，A 和C 可以马上进入读取数据的状态，这样在读取数据的时间上造成了一定的浪费。
阅读器
读取范围感应范围
图 4-6 DiCa 算法缺陷之一
同时在阅读器竞争数据信道的控制权的时候也未考虑其公平性的问题。如图4-8所示，如果A 和C 先要求读取数据，而在退避的时候刚好C 取得优先权而进入数据读取状态，因为退避是随机选择时间，这样对于A 来说是不公平的。
阅读器
读取范围
感应范围
图 4-7 DiCa 缺陷之二
4.3.2.6 HiQ （Hierarchical Q —Learning Algorithm ）与SA （Simulated
Annealing Algorithm ）
HiQ [25]算法试图使用最少的可利用频率资源使尽可能多的阅读器在同一时间工作来提高整个系统的效率。HiQ 是一种异质在线学习算法和解决阅读器动态碰撞的算法模型。
HiQ 算法总共有三层，分别为：阅读器，R-Server 和Q-Server 。利用Q-
自适应多叉树防碰撞算法研究 摘要该文提出了一种自适应多叉树防碰撞算法。新算法在动态二叉树和四叉树搜索算法的基础上，利用曼彻斯特编码可以准确识别碰撞位的特性，通过计算碰撞因子，估计标签数量，从而自适应地调整搜索叉数，即在标签数较多的节点上选择动态四叉树搜索，而在标签数较少时选择动态二叉树搜索。理论和仿真分析表明：新算法克服了动态二叉树和四叉树搜索算法的缺点，在减少碰撞时隙数的基础上，又减少了空闲时隙数，大幅度地提高了搜索效率和时隙的吞吐量，具有一定的创新性和适用性。 关键词射频识别；防碰撞算法；多叉树搜索； 中图分类号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