读写器的防碰撞算法

摘要射频识别(RadioFrequencyIdentify,RFID)技术是一种无线通信技术。多目标识别是RFID技术的优点，同时也是一项富有挑战性的技术。阅读器碰撞是RFID技术的关键性问题，它会影响RFID的读取速度。本文主要介绍基于调度和基于有效范围的阅读器反碰撞算法，如LLCR，Colowave，Pulse等，并对它们做了总体比较与评价。关键词：射频识别；阅读器碰撞；基于调度；基于有效范围AbstractRFIDisregardedasawirelesscommunicationtechnology,whichpossessesmanyadvantages.Multi-targetidentificationisboththeadvantageandthechallengeofRFIDtechnology.Readercollision,whichaffectsthespeedofRFID,isakeyproblemofRFIDtechnology.Themainpartofthepaperfocusesonthescheduling-basedandcoverage-basedreaderanti-collisionalgorithms,suchasLLCR,Colorwave,Pulse,etc.MeanwhiletheoverallcomparisonandestimationofthealgorithmsisgivenKeywords:RFID;Readercollision;Scheduling-based;Coverage-based第1章引言1.1课题研究背景无线射频识别(RadioFrequencyIdentification,RFID)技术是一种从二十世纪90年代兴起的一种非接触的自动识别技术。它的工作原理是利用射频信号和空间耦合传输特性进行非接触式双向通信，实现对被识别物体的自动识别并获取相关数据［1］。RFID系统由射频读卡器，标签和软件系统组成。随着物联网的兴起，RFID系统被广泛应用于物流，仓储等领域。例如，射频读卡器被安装在手机中，通过3G网络或者WiFi网络提供服务。用户可以通过查询贴在电影海报上的标签，从网上获得这部电影的相关信息，然后用户可以观看这部电影的预告片或者决定是否要购买电影票。另外，通过读取贴在超市货架产品上的RFID标签，消费者可以获得产品的重要信息，诸如产地，使用方法，有效期等。作为又快又准的信息采集与处理技术，RFID技术被世界公认为21世纪十大重要技术之一，它是继移动通讯技术，互联网技术之后影响全球经济与人民生活的一项革命性技术⑵。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应用环境非常复杂，阅读器簇间询问半径的动态调整策略难以确定。AnushaS.和IyerS.针对仓储应用中大量物品的识别和追踪问题，采用手持阅读器策略来一次对所有物品进行识别［7］。在给定的应用环境和相应特性阅读器的情况下，该系统能自动生成关于所有阅读器数量，方位安排和移动式等布局信息。但是该方案在阅读器询问区一旦出现混淆情形下，就会失效。R.E.Bellamn和S.E.Dreyfus提出了Q-Learning算法，该算法是在一个分等级的在线学习算法［8］，通过学习阅读器碰撞模型动态的解决RFID系统中阅读器碰撞问题。其思想类似于无线传感器网络中的分簇算法。这种方法如果应用在RFID系统中，将存在下面的问题：协议保持多层结构需要额外的开销。对于移动的阅读器来说，网络拓扑结构不确定的变化将会改变Q学习算法的多级结构。这就需要重新分配时隙，讲话去更多时间并使系统无效。1.3.2国外研究阅读器反碰撞现状田景贺，范玉顺等人针对密集阅读器环境下的RFID阅读器碰撞情况提出了一种阅读器碰撞问题的集中控制方法［9］。该方法根据平面图着色理论，将密集阅读器网络的阅读器防碰撞问题等效为阅读器网路的时隙分配问题，并建立了解决阅读器碰撞问题的神经网络模型，并引入了模拟退火策略及混沌思想对阅读器防碰撞神经网络模型进行求解。与现有的分布式防碰撞算法相比，该方法能够保证阅读器具有更多的标签时间和更高的标签扫描频度；徐雪慧，李玲远等人基于图着色算法提出一种改进的算法［10］，这种算法的主要思想是：阅读器采用两个通道，一个用于控制通道（阅读器之间通信），一个为数据通道（阅读器与标签之间通信），把阅读器和射频标签的信号传输分割开，这样碰撞只能在标签与标签之间或者阅读器与阅读器之间发生。这种分割使阅读器和射频标签信号在不同的频道上传输，解决了阅读器间的干扰。第2章RFID系统概述2.1RFID系统组成2.1.1RFID系统组成RFID系统由三部分组成［11：阅读器（Reader），电子标签（Tag）和软件系统。如图2-1为RFID系统的构成图。图2-1射频识别（RFID）系统基本组成标签即射频卡，每个电子标签都是有一个唯一可识别码，所以它可以用来代表它所附着的物体。电子标签的存储单元在Kbits量级，它的反复读写的次数在10000次以上。RFID标签分为主动式（Active）和被动式（Passive）两种。主动式标签中含有内置电池，可以主动向邻近的阅读器发送射频信号。被动标签内不含电池，无法独立发射信号，它的工作与否主要靠是否接收到阅读器发出的电磁波信号，该类标签可以将电磁能量转化为提供它工作的能量。它们之间的区别如表1所示。表1主动标签与被动标签性能比较主动标签被动标签工作方式内置电池通过电磁感应获取工作距离可达100m通常20〜40cm，最远可达3〜5m存储容量可达16KB以上通常小于128Byte信号强度要求低高价格高低工作寿命2〜4年长阅读器用于读写电子标签的信息，主要任务是控制阅读器向标签发射信号或读取来自标签的信号，并对信号进行解码，而后送至软件系统进行处理。软件系统由人对计算机进行控制来完成数据信息的存储及管理。它通过网络与分散在各地的阅读器通信，实时获取阅读器捕获到的电子标签信息。2.1.2RFID系统的基本工作流程RFID系统工作流程［12如下：无线电载波信号通过阅读器的天线向外发射。如果电子标签在发射天线的覆盖范围内，则它被激活，将标签内的信息通过天线传给发射天线。系统的接收天线接收电子标签发出的载波信号，经天线的调节器传输给阅读器，阅读器对接收到的信号进行解调与解码，然后送到软件系统处理。软件系统的程序通过判断标签的合法性，针对不同的情况作出相应的处理和控制，完成对应的动作。第3章阅读器碰撞3.1阅读器碰撞含义阅读器碰撞是指：多个阅读器同时与一个标签通信，导致标签无法识别是哪个阅读器发送的请求信号；也包括相邻的阅读器在同一时刻使用相同的频率与其覆盖区域内的标签通信而引起的频率碰撞。3.2阅读器碰撞的主要特点RFID网络中，阅读器之间的碰撞主要有下列特点：当多个阅读器发送的请求信号在某标签处产生碰撞时，该处的信号会变得非常混乱，从而导致标签无法识别由任何阅读器发出的信号。本文研究的RFID标签是被动式标签。标签在被阅读器请求信号激活后才能通信，并且标签不参与阅读器的防碰撞过程。隐蔽节点问题，是阅读器碰撞的一个方面。两个阅读器不再相互监听范围内而在标签处产生信号干扰时，载波监听机制失效。3.3阅读器碰撞问题分析3.3.1多阅读器与标签之间的干扰当多个阅读器同时阅读同一个标签时，引起了多阅读器到标签之间的十扰，该类干扰分两种情况。一种是两个阅读器与阅读器范围重叠，如图3-1所示。.■读写器I■标签o读取范围……图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的覆

读写器标签'读取范围R2干扰范围盖范围内。当标签T1反射回的微弱信号传输给阅读器R1的过程中，很容易被阅读器R2发射的强信号干扰。这时，R1很难读取到T1读写器标签'读取范围R2干扰范围图3-3阅读器与阅读器之间的干扰3.4RFID阅读器网络问题随着RFID技术的广泛应用，在同一场合有多个阅读器连接在一起同时工作的情况越来越多，于是出现了阅读器网络问题。由于阅读器网络节点与传统的无线传感器网络有很多相似之处，因此阅读器网络也有传统无线网络通信的一些问题，如隐藏终端和暴露终端问题。所以，在设计阅读器防碰撞算法的时候需要充分考虑阅读器之间的碰撞的情况，以提高阅读器的工作效率。所以在此有必要对阅读器网络中阅读器节点的隐藏终端和暴露终端的基本概念，解决方法[16][17等加以阐述。3.4.1隐藏终端3.4.1.1阅读器隐藏终端问题隐藏终端是指在接收阅读器的覆盖范围内而在发送阅读器的覆盖范围外的阅读器。由于听不到发送阅读器的发送信号，隐藏终端可能向同一个接受阅读器发送分组，导致分组在接收阅读器处产生碰撞。碰撞发生后阅读器要重传碰撞的分组，导致信道的利用率降低。

阅读器A的覆盖范围阅读器B的覆盖范围 阅读器C的覆盖范围图3-4隐藏终端C如上图3-4所示，阅读器A和C同时想发送数据给阅读器B,但A和C都不在对方的覆盖范围内。所以当A发送数据给B时，C并未检测到A也在发送数据，会认为目前网络中无数据传送，会将数据发送给B。这样，A和C同时将数据发送给B，使得数据在B处产生冲突，最终导致发送的数据不可用。这种因传送距离而发生误判的问题称尾隐藏终端问题。为了解决上述问题，可以使用请求发送信号(RequesttoSend，RTS)和清除发送(CleartoSend，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阅读器暴露终端问题暴露终端是指在发送阅读器的覆盖范围内而且在接受阅读器的覆盖范围外的阅读器。暴露终端因听到发送阅读器的发送信号而可能延迟发送。然而它是在接收阅读器的覆盖范围之外，它的发送不会造成碰撞。这就引入了不必要的时延。图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的覆盖范围内。第4章阅读器防碰撞技术4.1防碰撞算法研究分类针对标签碰撞问题与阅读器碰撞问题，分别提出了对应的算法，称为标签防碰撞算法与阅读器防碰撞算法。如图4-1为RFID系统防碰撞算法的整体研究框架。图4-1防碰撞算法研究路线在RFID系统碰撞问题中，标签防碰撞算法是研究比较多的，如图4-2是标签防碰撞算法分类。其解决方法主要分为：频分多址（FDNA），码分多址（CDMA），时分多址（TDMA）和空分多址（SDMA）[16][17JCBRQTAFrameSlottedAloha(FSA)TreeSlottedAloha(TSA)CBRQTAFrameSlottedAloha(FSA)TreeSlottedAloha(TSA)SDMAFDMATDMACDMATagAnti-collisionSlotted

AlohaBinaryTreeTrackingQueryBit-arbiree^^waikingTreeTreetrationSplittingMethod图4-2RFID标签防碰撞算法频分多址(FDMA,FrequencyDivisionMultipleAccess)，是利用不同信道传输信号以避免信号碰撞的一种方法，即阅读器将一定的频率范围分为更细的频道，不同的阅读器采用不同的信道与标签进行通信。时分多址(TDMA，TimeDivisionMultipleAccess)，是防信号碰撞中族常使用，也最成熟的一项技术，其原理是利用时间的差异，将可以使用的通讯时需分配给不同的阅读器进行数据传输，排定先后顺序后依序与标签进行通信。这类似于凸轮中的图形着色问题，是一个NP-hard问题。对于RFID系统，TDMA称为防碰撞算法最大的一族。载波监听多路访问(CSMA,CarrySenseMultipleAccess)o在RFID网络中，像其他的无线网络一样，存在隐蔽节点问题。不再互相侦听范围内的阅读器在标签处发生干扰，因此仅仅依靠载波监听无法避免RFID网络中的碰撞问题。码分多址(CDMA，CodeDivisionMultipleAccess)需要在射频标签上增设额外的电路，大大增加了标签的成本，并且给网络中所有的标签分配码是一件复杂的工作。因此CDMA不是一种成本低并且有效的方法。空分多址(SDMA，SpaceDivisionMultipleAccess)主要实现方式是在阅读器上使用相控阵天线作为电子控制定向天线，使天线的反向图一次对准作用范围内不同的标签，从而实现多路村粗。由于天线的规模限制，只有频率在850MHz以上时，SDMA才可以在RFID中应用，而且复杂的天线将造成相对高的成本。因此，这种方法只适用于一些特定场合。4.2阅读器防碰撞基本原理由于标签含有可被识别的唯一序列号，RFID系统可以容易得获取信息[18。如果仅存在唯一的标签在某个阅读器的覆盖范围内，则阅读器可以直接获取标签的信息；如果有多个标签在一个阅读器的覆盖范围内，在信道共用，频率相同的情况下，它们同时将信号传给阅读器的，这时各信号之间互相干扰，信道争用问题随之产生，数据发生碰撞，从而导致阅读器和标签之间的无效通信。为了防止这些碰撞，RFID系统中需要设置一定的相关命令以解决碰撞问题，这些命令被称为“防碰撞算法”(Anti-collisionalgorithms)o解决标签碰撞问题和阅读器碰撞问题的方法分别称为标签防碰撞算法和阅读器防碰撞算法。4.3阅读器防碰撞算法研究与分类阅读器能够顺利获取在其覆盖范围内的电子标签信息，以及对信息的读写操作。目前，主要通过采用时分多址(TDMA)原理，使每个电子标签在单独的某个时隙内占用信道与阅读器进行通信，防止碰撞产生。目前，无论国内还是国外，研究RFID阅读器反碰撞算法都很少。主要的反碰撞算法主要分为以下两大类：其一是基于调度(Scheduling-based)，其二是基于有效范围(Coverage-Based)。对于前者，其核心思想是防止阅读器同时发送信号给标签，以此避免发生碰撞，该类算法一直是反碰撞算法的主流。对于后者，其核心思想是将阅读器之间的重叠区域减小来降低发生碰撞的概率，相对于基于调度的方案来说，该类算法比较少。反碰撞算法分类如图4-3所示。

图4-3阅读器反碰撞算法分类4.3.1基于有效范围的反碰撞算法目前，基于有效范围的反碰撞算法主要有LLCR(Low-EnergyLocalizedClusteringforRFIDnetworks)[19]和口w-LCR(weightedLocalizedClusteringforRFIDnetworks)[6]，这类算法主要手段是改变阅读器的发射功率，其核心目的是调节它的通信范围，从而减小阅读器与阅读器之间的重叠区，最终达到降低阅读器之间的碰撞概率的效果。LLCR算法LLCR[19]算法主要通过调整RFID阅读器的聚类半径R，使得代价函数f(r1,r2,r3,①1,①2,①3)最小，从而降低阅读器之间的碰撞。聚类半径模型如图4-4所示，半径R的大小由公式(1)决定。该算法一共分为两个阶段。第一阶段为初始阶段，第二阶段为聚类半径调节阶段。在初始阶段中，其核心任务是

找到中心点CRDP以及聚类半径R；在聚类半径调节阶段，其主要任务是在一定条件”下，通过调节控制代价函数，，使其达到最小。iR=N1CRDP+N2CRDP+N3CRDPf(r1,r2,r3,①1,①2,①3)二1£中r2 ——S2任-八1£e53kk=1（1）（2（1）（2）r；=(xcRDpr；=(xcRDp-气)2+(ycRDp-y)2R，"，f（r1,r2,r3,①1,①2,①3），如公式（1）（2）（3）所示。其中E^表示阅读器的能量，阅读器所能覆盖的范围，striang为三角形的面积，r为中心点CRDP到位于三角形各顶点阅读器的距离，Fi•为三角形各顶角的度数。w-LCRw-LCR算法与LLCR算法模型一样，前者是对后者的改进版本。它们之间的区别在于，计算公式增加了触发函数与激励函数，从而代价函数f得到了平衡，增加了算法的鲁棒性。从稳定性和效率方面来说，w-LCR要比LLCR强的多。4.3.2基于调度的反碰撞算法目前阅读器反碰撞算法的主要方法是基于调度的反碰撞算法，很多阅读器的反碰撞算法都属于基于调度的方法，其核心思想是防止阅读器同时给标签发送信号，以此达到避免阅读器之间的碰撞。4.3.2.1ETSIEN302208(CSMA)[20算法该协议是由欧洲电信标准协会(EuropeanTelecommunicationsStandandardsInstitute简称ETS)提出的RFID标准，称为“电磁兼容和无线电频谱事项”。欧洲RFID标准规定的阅读器频率范围是865MHz〜868MHz，带宽为200KHz，最低子带的中心频率是865.1MHz，共有15个频点，从865.1MHz每个200KHz到867.9MHz。同时，如表对于200KHz带宽内的频谱功率分布有着严格要求。表2频谱功率分布传输电量载波功率阈值最高达100mW-83dBm101mW到500mW-90dBm501mW到2W-96dBmCSMA算法是欧盟采用的RFID阅读器反碰撞标准，该算法采用CSMA机制。该RFID标准规定，阅读器在发出命令前，必须先侦听该频点是否已经被占用。如果有信道空闲，则马上传输数据。否则，不能在该频点发出请求，要采取退避策略。上表是侦听的载波功率阈值。当阅读器竹内在865.1MHz〜865.6MHz频段内工作时，必须先侦听该频段内的已存在的载波功率。如果监听到的载波功率-83dBm，那么阅读器就不能利用该频段工作，必须跳到其他的频点继续侦听。直到找到一个空闲的频点才能工作。以此来看，避免两台阅读器同时工作在同一频点而产生的干扰是该项标准的主要目的。该算法与传统的CSMA协议相似，实施比较容易。但是，这种“先侦听后发送”的机制，并不能完全规避多阅读器与标签之间的额碰撞。阅读器可能无法通过载波监听到碰撞的发生，并且由于该算法无法解决传统无线网络隐终端和暴露终端的问题，所以此标准的效率不是很高。如图所示，R1处于阅读器R2的感应范围之外，但是A发出的信号与B发出的信号在标签T1出产生碰撞。图4-5ETSIEN302208协议对RFID阅读器碰撞问题缺陷ClassIGeneration2UHF算法ClassIGeneration2UHF[21]由EPCGlobal起草使用的频分复用算法，是超高频的第二代标准。它分别使用阅读器传输和标签传输，那样使得阅读器只与阅读器产生碰撞而不会与标签发生碰撞，而标签也只与标签产生碰撞与不会与阅读器产生碰撞。这样分开处理，解决了阅读器与阅读器碰撞，因为阅读器数据传输与标签传输是在独立的信道中进行的。但是由于标签没有频率选择功能，当两个不同的频率同时去读同一个标签时，还是会产生阅读器对标签的碰撞。因此在这个标准中多阅读器对标签的碰撞还是不能避免的。Colorwave算法Colorwave[22]算法是由JamesWaldrop,DanielW.Engels和SanjayE.Sarma提出的。它是一种基于TDMA的分布式防碰撞算法。在Colorwave算法中，RFID系统的网络被当作一个图，阅读器被认为是一个节点。为了给网络中每个阅读器不同的颜色，Colorwave利用DCS（DistributedColorSelection）和VDCS（Variable—MaximumDistributedColorSelection）为阅读器网络着色。在Colorwave算法中，颜色代表阅读器传输的时隙。具体算法是：每个阅读器选择任意一个时隙（颜色）发送请求信号，然后在属于自己的时隙中读取标签信息。如果某个阅读器选择的时隙与邻近的阅读器选择的时隙相同，那么它们之间就会产生碰撞。当检测到碰撞发生时，阅读器会选择另一个新的时隙（颜色）试图传输，并且发送一个'kick’信息给它的邻近阅读器。这个'kick’信息被用来告诉邻近的阅读器，'我'已经开始选择新的时隙（颜色），如此往复进行下去。虽然Colorwave算法能够有效的解决阅读器碰撞算法，但是它仅适用于静态的拓扑结构网。对于动态环境，一个节点的变动将会导致整个阅读器网络的变化。另外，Colorwave算法同样要求时间同步，然而在AdHoc网络中，实现同步是比较困难的工作。因为TDMA调度需要阅读器支持同步及高移动性能，这样会产生大量的通信调度开销，所以Colorwave算法不适用于移动式RFID阅读器。另外更为糟糕的是Colorwave没有使用多信道来传输信息，所以阅读器的会产生较长的等待时间。阅读器较长的等待时间会导致吞吐量降低。Pulse算法Pulse[23]算法将控制信道与数据信道分离。数据信道被用来在阅读器与标签之间通信，控制信道被用来在阅读器之间通信。采用这种机制后，在控制信道上的控制信息传输不会影响到数据信道上数据信息的传输。在 Pulse算法中，当阅读器与标签通信时，阅读器会通过控制信道定期的向它几百米之外的范围发送‘beacon’信息。接收到‘beacon’消息的阅读器将不会立即与标签通信，而是选择等待，直到它不再接收到任何‘beacon’消息为止。通过Pulse算法，任何一种碰撞问题都可以避免，同时它也符合移动式RFID阅读器的使用环境。然而，因为邻近阅读器在阅读器的干扰范围内，它将被强制禁止读取任何标签信息，这样就浪费了信道资源。另外，Pulse算法作为一种性能比较优越的算法，它成功避免了阅读器网络的隐终端和暴露终端问题，因此效率得到了提高。但是Pulse算法周期性的发送信息给邻近的阅读器，将加快阅读器的能耗。虽然Pulse算法在效率方面都有了很大的提高，但是并没有完全解决隐终端和暴露终端的问题。DiCa(DistributedTagAccesswithCollision-Avoidance^算法DiCa[24]算法与前面的算法比较，它不要求集中协调和全局的时间同步。由于DiCa是Pulse的改进版本，所以DiCa和Pulse有很多相似之处，例如，它们都是用两个独立的信道来传输信息和数据。不同之处在于DiCa在读取数据时不再是周期性地发送信息给周边的邻居阅读器，而是在读取数据结束后再发送读取结束信息，这样在控制能耗方面可以取得很好的效果，另外DiCa很好地处理隐终端和暴露终端问题，这样很大程度上提高了阅读处理数据的效率。但是DiCa算法在采取退避算法时，为考虑阅读器的具体位置，不管阅读器之间是否存在干扰区域都直接进行退避，如图4-6所示。由于A和C没有重叠区域，它们之间不存在干扰，也就是说A和C是不可能发送碰撞，所以采

取退避算法实际上是浪费了时间，因为在B完成数据读取后，A和C可以马上进入读取数据的状态，这样在读取数据的时间上造成了一定的浪费。阅读器■阅读器■读取范围•感应范围 图4-6DiCa算法缺陷之一同时在阅读器竞争数据信道的控制权的时候也未考虑其公平性的问题。如图4-8所示，如果A和C先要求读取数据，而在退避的时候刚好C取得优先权而进入数据读取状态，因为退避是随机选择时间，这样对于A来说是不公平的。阅读器.读取范围感应范围 图4-7DiCa缺陷之二HiQ(HierarchicalQ—LearningAlgorithm)与SA(SimulatedAnnealingAlgorithm)HiQ[25]算法试图使用最少的可利用频率资源使尽可能多的阅读器在同一时间工作来提高整个系统的效率。HiQ是一种异质在线学习算法和解决阅读器动态碰撞的算法模型。HiQ算法总共有三层，分别为：阅读器，R-Server和Q-Server。利用Q-Servers将现有的频率资源分配给R-Servers。R-Servers将这些资源分配给阅读器，同时收集阅读器的状态给Q-Servers。只有获得频率资源的阅读器可以同标签进行通信。和Colorwave一样，HiQ也要求严格的时间同步。它亦假设阅读器可以探测到标签处的碰撞。所以HiQ与Colorwave有同样的缺点。另外，用HiQ算法的系统是非常复杂的，所以这就大大增加了系统的开销。SA[26]算法主要是利用模拟退化算法，把阅读器反碰撞问题转化为信道争用的问题。与HiQ算法一样，它亦属于智能信息的处理算法，具有与HiQ算法的同样的不足。第5章算法比较5.1基于有效范围的反碰撞算法LLCR和w-LCR算法都有如下缺陷。都没有充分考虑阅读器读取数据的通信范围，不管要求阅读器读取数据超过最大范围，还是要求小于读取的门限，都会极大地消耗阅读器的功率，从而对阅读器造成极大的损害，甚至失效；阅读器必须知道自己的准确位置，这势必提高阅读器构造的复杂性；由计算公式可以看出，该公式是比较复杂的，计算的复杂性显然会导致效率和功耗的降