RFID系统,研究趋势和挑战_第八章

1、Tree-Based Anti-Collision Protocols for RFID Tags8.1 Introduction8.2 Principles of Tree-Based Anti-Collision Protocols8.3 Tree Protocols in the Existing RFID Specifications8.4 Practical Issues and Transmission Errors8.5 Cooperative Readers and Generalized Arbitration Spaces8.6 ConclusionRFID中基于树型的防碰

2、撞协议8.1 整体介绍8.2 基于树型的防碰撞协议的原则8.3 在现存FRID规范中的树型协议8.4 实际中的问题和发送中的错误8.5合作的阅读器和通常的仲裁空间8.6 总结RFID系统主要由系统主要由阅读器阅读器和和标签标签组成组成系统构建阅读器（阅读器（Reader）标签（标签（Tag）被动式标签（被动式标签（Passive Tag）：因内部没有电源设备又被称为无源标签无源标签。内部的集成电路通过接收由阅读器发出的电磁波进行驱动，向阅读器发送数据。主动标签（主动标签（Active Tag）:因标签内部携带电源又被称为有源标签有源标签（电池供（电池供电的具有非常低的功耗标记）电的具有非常低的

3、功耗标记）。也被称为询问器，收发器，是能够与标签通信，能从标签读出信息或将信息写入其中。半主动标签（半主动标签（Semi-active Tag）:使用电池，用于感测/加工，但不用于通信标签分类 读写器发送一个探测帧，根据探测帧的内容，标签决定是否回应。如果多个回复同时到达读写器，这时就发生标签碰撞，导致阅读器无法读取。注意，标签碰撞问题发生在阅读器处。如果一个标签在多个阅读器的范围内，两个或多个阅读器同时发送信息，导致这个标签无法正确收到任何一个阅读器的信息，就发生阅读器碰撞。通信模式标签碰撞阅读器碰撞两种碰撞 标签碰撞通过防碰撞协议来解决。仲裁协议的目的是划分每个标签的发送时间(也就是进行时

4、间调度)，使得最终每个标签能成功发送回复。另外，仲裁协议并不彻底解决碰撞，而是解决可能需要的部分冲突。 阅读器碰撞成为一个在阅读器密度较高时的重要问题，主要在于要合理分配通信资源（时间，频率），以减少它们之间的干扰。解决办法 本章将介绍一类基于二进制树的防碰撞协议。这种协议用在多址接入的单信道中，一个阅读器收到来自多个标签的回复。本质上，在遇到碰撞时该协议递归地解决碰撞，直到所有的标签成功发送回复给阅读器。 碰撞树型协议 我们假设一个标签在距离一个阅读器为D的范围内，那它将无差错地收到来自阅读器的请求帧。它的数据包也将成功地被阅读器接收。多址接入的信道模型，就意味着如果多个标签同时在阅读器的接

5、受范围内传送信息，那阅读器将不会正确收到任何传输来数据包。 K个标签在同一时隙发送数据，阅读器在该时隙感受到的信道为：闲置（I） 如果K=0 没响应成功响应（S） 如果K=1冲突（C） 如果K1 系统模型系统模型时隙1：标签 同时发送，发生碰撞时隙2：标签 同时发送，发生碰撞时隙3：没有标签发送，空闲时隙4：标签 发送，成功 如图，一个标签只有在阅读器发送请求帧时才会发送应答帧，在接收到请求帧1后，标签 发送应答帧。如果两个标签同时发送数据，那他们的数据将发生碰撞，然后阅读器将在下一请求帧中向标签做出反馈。阅读器发出请求帧2时，便携带了上一时隙结果（此处为冲突）的反馈信息给标签。1231112

6、23系统模型 如果没有发生错误，仲裁协议的效率将用发送时间和信息量来衡量。如果这里有n个标签，我们关心识别所有标签的平均时间 。定义为一个随机变量 ，它代表执行仲裁算法的一个特定实例所消耗的时间，包含两个部分， 1.用来发送请求帧， 2.用于标签发送数据。 我们假设阅读器发送请求帧的时间为零，而只关注标签发送数据的时隙。由于请求帧不消耗时间，则一个仲裁协议的执行效率被定义为效率： nTnTnnTn基本树型协议 基于树型的协议已成为一个解决共享媒介多址接入问题的方法。一个阅读器发送一个请求帧给标签并要求标签做出回复。由于阅读器并不知道标签的ID，于是它在请求帧中要求标签做出回复，但未指定具体是哪

7、个标签。因此多个标签都有资格发送回复。检测到冲突后，阅读器知道至少有两个标签发送了回复。由于阅读器仍不知道这些标签的数量和ID，于是就采用随机选择的方法。冲突之后，每个标签都要投掷一枚硬币来产生一个0或1，阅读器在下一帧时只要求产生只为0（或者为1）的标签发送回复。这个过程将持续直到两个标签产生不同的随机数。 我们定义碰撞重合度为检测到冲突时发送数据的标签数量；节点的深度代表节点离根节点的距离；每一个节点都有唯一的一个与之相关联的字符串，称为地址。如果属于某个时隙 的标签被允许发送数据，就表明在这个时隙 一个地址 （节点）被启用（使能）。isis 基本树型协议 在时隙 ，根节点（深度为0）启用

8、，所有8个标签都发送数据，阅读器检测到碰撞。根节点的地址为空，用表示。每个标签投掷一枚硬币，在此情况下， 得到0。在时隙 ，根节点的左侧子节点被启用， 被允许发送数据。注意此时在时隙 启用的节点的深度为1且地址为0。标签 - 在 时隙 投掷出1，属于深度为1的另一个节点（地址为1）。在时隙 发生冲突后，标签 再一次投掷硬币，只有 得到0， 得到1。因此当地址为00的节点被启用，只有 发送数据且被阅读器正确接收。在一次正确传输之后，在时隙 同深度的另一个地址为01的节点被启用。1S2s4812s3214s 基本树型协议阅读器端算法标签端算法基本树型协议 该算法的一个好处

9、是自组织为每个标签分配地址。也就是说，通过这次冲突解决，阅读器以后可以实现和特定的标签进行通信。阅读器可以通过分配给标签一个短地址代替完整的地址，这个短地址是标签被成功识别时所在的树节点的地址。例如图中标签 的自组织短地址是011.3改进的树型协议（1） 如果一些节点对应两个以上的标签，那么这个节点被启用时必然导致冲突，所以这些节点应当在树遍历时被跳过。如，在经历过一个冲突时隙和一个空闲时隙 之后，地址为111的节点将产生冲突，因此在空闲帧 之后，标签应该立即投掷一枚硬币，时隙 应该从地址1110开始。这个算法被称为修正二叉树（MBT）。12s13s11S12s改进的树型协议（2） 在早期，研

10、究者认为知道冲突重合度可以加速解决冲突。Capetanakis在研究中发现二进制树型算法在解决小冲突重合度非常有效，应用这个发现，他设计了 一种针对响应的标签数量呈泊松分布的动态树型协议。第一步致力于估计冲突重合度。在得到冲突重合度后开始第二步，将未识别的标签随机分为若干组，然后在每组中使用基本树型协议。附：这个分布是泊松研究二项分布的渐近公式是时提出来的。泊松分布P ()中只有一个参数 ，它既是泊松分布的均值，也是泊松分布的方差。在实际事例中，当一个随机事件，例如某电话交换台收到的呼叫、来到某公共汽车站的乘客、某放射性物质发射出的粒子等，以固定的平均瞬时速率 (或称密度)随机且独立地出现时，

11、那么这个事件在单位时间（面积或体积）内出现的次数或个数就近似地服从泊松分布。因此泊松分布在管理科学，运筹学以及自然科学的某些问题中都占有重要的地位。改进的树型协议（3） 考虑到随机接入的标签发送时呈泊松分布，于是每当有一个冲突和连续两次成功传输发生时，树就裁剪，因此称为裁剪树型协议（CBT）。例如，在CBT算法中，开始于时隙 终止于 ，导致三个标签被识别。阅读器注意到三个标签选择了0，因此最初选择1的标签的数量的预估值为3。这意味着启动地址为1的节点 （深度为1的节点）很有可能产生冲突，因此应该启用一个更深的节点，如启动地址为10（深度为2）的节点，于是就跳过了深度为1的节点，一个时隙就被省了

12、下来。1s6s树型仲裁算法的框架假设在发送初始化帧时，每一个标签随机生成一个实数，均匀分布在0,1)之间，这个随机数被认为是一种标识，用 表示标签 生成的标识。用 =（ .）来表示 分数部分的二进制形式，那么每一个 都是一个无限长的二进制串并且： 可以被理解为一个无限长的随机二进制串，来存储每一个以0.5的概率生成的 （0或1）。iriix321iiixxxiririjxir 例如，在一开始的碰撞之后，地址为0的结点被激活，因此所有节点中只有生成随机数在0,0.5)之间的结点才能做出响应。依此类推。在图中，用一个确定的地址来激活树结点，相当于使生成随机数在0,1)的某个子区间的标签使能。例如：

13、当地址为10时，在时隙 把生成随机数位于0.5,0.75)区间的节点激活，让其传输。一般地，如果节点的地址为： ，当它被激活时，相当于使能生成随机数位于b,c)区间的结点。其中：8skaaaa.21一个长方形标示对应时隙的使能区间，阴影部分表示冲突，长方形被标记为 表示在对应的使能区间仅包含标签 。ii 树型仲裁算法的框架 在一次CBT算法的实例终止之后，我们可以得到标签数量n对应的估计值 ，我们可以通过这个值来得出还有多少个标签需要处理。 如：在前六个时隙中，第一次CBT实例结束之后，阅读器在使能区间0,0.5)发现了三个标签，如果n是在使能区间0,1)的标签个数，在0,0.5)区间的标签的

14、期望数为k = 0.5n，由于k=3，我们可以估计 = k/0.5=6，因此在未处理区间0.5,1)的标签期望个数为3。第二次CBT算法在标签 被处理后结束，这时,阅读器发现有5个标识位于区间0,0.75)，这样就可以得出初始的标签总数为： =5/0.75=6.67，然而其他待识别的位于0.75, 1）标签个数的估计值为(5/0.75)*0.25=1.67。 n n n 5 树型仲裁算法的框架 通常，假设k个已处理的标签，并且其标识位于区间0,p)，然后有n-k个未处理标签，其标识位于区间p,1)。考虑到标识的生成过程,阅读器可以预测：在n（n为未知数）个均匀分布在0,1)区间的标识中，有k个

15、标识位于0,p)，那么出现以上事件的概率为 ： 对于给定的k，p，我们可以得到最大似然估计值：它不一定是整数，但这个估计值是准确的，因为E |n = n，然而它的误差为： 在仲裁程序执行过程中，p的值会逐渐增大，这会使得方差Var |n减小，因此得到的估计值会越来越精确。n n 树型仲裁算法的框架 利用基于生成标识的架构，研究员制定了几套仲裁协议，每一个协议处理冲突都比传统的二叉树协议快，特别是区间估计解决冲突(IECR)被认为是最快的冲突解决方案。让我们假设在一次CBT实例终止时，观察k个标志在0,p)解析。基于对碰撞重合度的估计 ，下一个启用区间为p,p+ p)。如果检测到冲突，启动一个新

16、的CBT实例并重复该过程。如果在p,p+ p)只有一个标记或无标记，那么把下一个时隙为作为这次CBT的终止时隙，并且重新估计/启用新的区间。 IECR的速度相关于CBT实例终止后对使能区间长度的优化选择。IECR解决碰撞的速度渐进等价于对用于对泊松分布的先到先得（FCFS）树型算法。当n很大时，第二启用区间的长度应该是： ，其中k是一个CBT实例终止后的在区间0,p)上识别标签数量。其时间效率为： kp26. 1树型仲裁算法的框架 由于一般区间a,b)限制为实数以及每一个实数都由无限长的二进制编码来表示，使得RFID中的IECR算法不是直接实现的。如果没有有限整数i,使得对于所有ji，有 =0

17、，那么一个 X 0,1)实数的二进制表示为X= .就为无限长。由于区间被描述成无限长的二进制数字，优化选择的长度p可能导致一些使能区间不能有效的包含在阅读器发送的探测帧中。 另一种被称为估计二叉树(EBT)的算法更适用于RFID标签。在EBT中，启用的区间长度等于 ，其中L是一个整数。这样选择的好处是每个启用的区间对应于在演化的二进制树中的单一的结点，这样可以使区间比较紧凑，使树中的地址和实际区间相对应。一个CBT实例终止后，只需要决定如何选择 L。最直接的方法，就是使获取单一回复的可能性最大： 最后，一个关于标签数量规模的先验信息可以提高算法的效率。例如，如果已知标签的数量 大于1，那么最初

18、的探测帧不需要启用整个0,1)区间，可以从在区间0,1.26/ )开始。这种方法可以在初始阶段避免发生碰撞，直到第一次CBT实例终止，并且产生第一个估计值 。 lxxx. 021minnminnjxn 数据说明 在IECR中，如果n先被告知，每个CBT实例终止后，就可以准确知道留在区间p,1)未解析的标签数量。可以看出EBT优于MBT，MBT优于基本的二进制树算法。如果先不知道标签数量规模，那么EBT和IECR的效率随标签数量的增加而提高。也可以看出EBT换取时间效率所付出的代价是和IECR相关的。有部分或全部关于n的信息，可以提高性能，当n为先验已知的，效率随n的增加而减少。这是因为标签数量

19、较少时，先知道标签数n比对剩于区间未解析的标签数的估计更有价值。但先验信息的优势会随着n的增加而减少。 RFID规范中的树型协议 两种基于树型的协议，用在EPCglobal第一代标签中：Class 0和Class 1。 在许多应用中，第一代标签和相关的协议已经被第二代Class 1标签所取代。除了这两种协议，其他标准的树型协议是ISO 18000-6AEPCglobal Class 0 协议 原来我们假设标签能够产生随机数，当作标记用在防碰撞协议中。EPCglobal 0类标签不用随机数，而是依赖于每个标签唯一的ID号。如果标签的ID有L位比特，则ID 在【0，1）区间用二进制表示为 。 例如

20、，由于标签 第一位比特都是0，在时隙 允许发送，而其他的标签 的第一位为1.因此，我们可以推出 的ID是00.， 的ID 是1110.。lxxx.21lxxx.0212s8416321 EPCglobal Class 0 协议Class 0 协议用一位接一位的比特询问应答：（1）阅读器开始发送一个特殊的空序列，收到序列的标签回复自己ID的第一位比特。（2）如果回复的比特都是0或者1，那么阅读器接受到的就是0或者1。然后，阅读器再发送下一位。（3）如果一些标签发送的是0其他的标签发送的是1，则阅读检测器同时能到0和1。接着它会随机决定发送0或者1。（4）如果第一位和阅读器发送的比特相同的标签就发

21、送第二位比特，如果和阅读器发送的比特不同的标签就沉默，直到下一个特殊的空序列再开始发送。 例如：假设每个标签有5位比特的地址，分别是X( ) = 00100, X( )=01010, X( ) = 01100. 代表 的地址，假设在时隙 后，阅读器选择发送一个0，在 后发送0，则标签 发送 =1，同样的方式发送 =0， =0。 在第五位被读后， 就近入沉默。于是阅读器再次发送空序列，之后收到了0和1，接着在下一时隙发送0，然后接收到1，于是再发送1，接着又接受0和1，再发送0，这样就最后得到 的最后两位。对剩下标签的解析也用同样的方式。123)(ixi11s2s4x5x123x EPCglob

22、al Class 0 协议注意：（1）没有空闲时隙。因为这里没有发生碰撞，而只是0和1的组合，阅读器每次回传的是在现在标签里有的比特值。（2）实际上，每一个标签默认处于睡眠状态，阅读器发送复位信号来唤醒它们。在复位信号以后，阅读器发送一个标志序列使标签标准化，只有标准化后，一个标签才能接受到阅读器的命令。（3）除了0和1，空序列以外，规范还定义了阅读器发送的其他命令。注意，在复位/标准命令发送后才到达的标签不能加入正在实行的树型协议，需要等待下一组复位/标准命令。因此，为了能够读到后到达的标签，阅读器应该频繁地发布标准化命令，这也影响了防碰撞协议的速度。（4）阅读器用的短的命令（0，1，和空信

23、号）确保每一个标签被解析后重新从树的根开始遍历。一般来说，短的阅读器命令减少了树形协议的灵活性。 EPCglobal Class 1 协议 Class 0 标签的一个严重缺点是：他们是厂家写的，因此这个协议不会预先考虑到在标签里写新数据。这也是引入Class 1 标签主要原因之一。和Class 0 标签不同，在Class 1中阅读器发送命令数据包以及标签回复整个数据包。每个读取命令有一个同步序列。因此，在原则上，迟到的标签可以加入仲裁协议。阅读器命令里含更多内容使遍历树更加灵活，但代价是协议的单个时隙持续时间（含阅读器命令和标签应答）比Class 0长得多。 Class 1规范用提供的命令来支

24、持基于树的协议，但不具体指定遍历树的方式。阅读器可以使用PingID命令，这命令包括：一个指针【PTR】 ，它指向标签标识符的一个位置（或位索引）和一个长度的位掩码值【VALUE】。如果标签ID中由【PTR】指示位置值和VALUE匹配，则有权回复请求帧。 EPCglobal Class 1 协议 例如，如果PTR = 1和位掩码为“11 ”，那么ID是x11 的标签（其中x可以是0或1） 就可以发送。但是，不是所有具和位掩码匹配的标签立刻发送一个应答。阅读器在探测帧终止时构造8个容器，分别标记为000 ， 001 ， 010 ， 111 。可以和位掩码匹配的标签，使用其ID的下三位来决定是否发

25、送答复。 如，在一个位掩码为X11探测帧发送后，地址x11010的标签将在第三个容器发送回复。在这样仲裁框架里，一个探测帧同时使能8个区间。此外，位掩码集合适用于多重估计，如在EBT，也加快了标签解析。 这两个EPCglobal第一代的Class 0和Class 1类标签，以及相关的仲裁协议，逐渐被第二代Class 1标签取代，它使用ALOHA协议的一个变形。放弃这些树型协议的一个主要原因是他们很难处理后来到达的标签。令牌（标志）生成 上面描述的两个实行树协议的RFID，在标签中不依赖产生的随机数。但随机比特位用于无源标签不成问题，并已被用于基于ALOHA协议的第2代Class1 标签中。因此

26、，基于树的RFID协议的未来版本可以依靠随机生成的比特而不是ID。从安全的角度来看也是重要的。如果ID标识位用于仲裁，则与标签ID对应的令牌（标志）可能不均匀的分配在0,1）之间。当令牌均匀地分布在0，1）之间时，EBT比BT提供了更好的平均性能。否则，使用统计估计是无效的，且EBT可能比基本二进制树协议更慢。 如：有五个标签并且他们的ID在0.25，0.5）之间。如果用二进制树的基本算法，那么当所有的标签被解析了，下一个启用的区间为0.5，1），这将导致一个空闲的响应，该算法将终止。相反，如果应用EBT，标签被解析后，该算法继续估计标签的基数并使能比0. 5，1）小的区间，所以，它需要更多的

27、时间来终止仲裁协议。一个随机化标签标志的方法是阅读器使用一个预先定义的随机的比特位排列。这种排列可以用来在EBT算法开始之前打乱地址，从而随机化在冲突解决中所用的前缀。传输错误 之前所描述的协议假设运行在没有信道错误的情况下，但信道的错误以不同方式影响这些协议。可以将错误划分为发生在标签处和阅读器处的错误。发生在标签处的错误 在标签处的错误导致标签不能回复阅读器。我们将MAC协议层上的错误分为两种类型：静态的错误和动态的错误。静态错误发生在整个冲突解决期间，标签处在一个“盲点”（盲点就是该标签在阅读器的范围以外），所以在整个会话中标签没有收到请求帧。设 表示发生静态误差的概率。另一方面，由于动

28、态错误，使得由阅读器发送的每个请求帧以概率（1- ）被标签正确接收，以概率 不能正确接收。从物理层角度来看，静态错误由信号深度失真造成，而动态误差是由噪声引起的。标签 静态（动态）误差的概率表示为 ( )。通常当i j时，每个 并且 。 spdpdpidipsipsjpdjpsipdip发生在标签处的错误 静态错误对协议的影响是简单的，标签不参与阅读器的会话。有人可能会认为，出现静态错误时，标签处于“盲点“-距离阅读器近但链路质量却很差。如果一个标签在一个会话中的盲点并不一定意味着该标签处于另一个会话的盲点，并且标签可以移动。 在图中，标签 不在阅读器 的范围中，而在阅读器 的范围中。4ARB

29、R发生在标签处的错误 动态错误对树型协议的影响较为复杂。假设阅读器实行基本树型协议，没有任何由MBT引进的估计或优化。如图，假设标签 在时隙 中没有正确地收到探测帧，而是在时隙 正确收到了探测帧。因此，阅读器观察到一个空闲时隙 。可以验证，冲突解决会话结束，这个标签不会收到一个请求帧可以使它有资格发送一个回复。阅读器认为区间0，0.5）为已解决，然而处于该区间的的标签 却未解析。注意，在无差错的情况下一个未解决的标签是不可能收到一个请求帧通知它其所属的区间已被解析。336s6s7s发生在标签处的错误 有两种方法可以来减小动态错误的影响。 第一种方法：即使区间0，p）已认为被解决，阅读器仍然启用

30、这个区间或询问它的一些子区间是否有剩下的标签。 第二个方法：如果令牌在0，p）区间的标签还没有被解析，而阅读器发出信号认为已经解决了区间0，p），那么这个标签就再次生成令牌，均匀分布在P，1）区间。 第二个方法表明在带有启动区间的框架（如IECR或EBT）中的估计需要改变，由于未解决的区间在统计学上不同于已解决的区间。另外，如果只是的基于标志不同，则重新生成的标志可能导致无法解决的冲突。例如， 为 .， 为 .，也就是说，它们仅在第一位不同。如果标签 在区间0,0.5）错过了，可在0. 5，1）再生成令牌，忽略第一位。然而，这样做意味着它在碰撞解析过程中不能与 区分。因此，阅读器重新启用一些先

31、前已被解决的区间会更加合适。 1321 xx2320 xx12发生在标签处的错误 基本二进制树算法对标签处的错误是健壮的，然而标签处的错误对改进的二叉树来说是很严重的。如，有两个标签 ，令牌分别为 = 0.1和 = 0.2。假设第一个使能0,1）区间的请求帧被 和 正确接收，随后阅读器检测到碰撞。接下来，产生第二个使能0,0.5）区间的请求帧，其中一个标签没有收到。一种情况：MBT算法将进入无尽的会话，阅读器从0.25,0.5) 开始使能越来越小的子区间,但只得到空闲回答。另一种情况：如果一个有估计的树型算法被应用，例如EBT（不使用MBT），算法对错误也表现健壮,但估计不会那么精确。1122

32、1r2r发生在标签处的错误 对于静态错误,阅读器错过一个标签的概率是 动态错误以概率 发生,错过一个标签的可能性与 没有直接的关系。如：有两个标签，令牌分别是 在【0，0.5)， 在【0.5，1）。用 表示标签 没有在会话中被阅读器读到。假设两个标签发生动态错误的概率是相同的。 表示 被错过， 被成功读取的概率。 两个标签都被错过的概率由 给出: spdpdp12ii21rp1221rP 第一个 是两个标签的都没有收到使能【0,1)区间的探测帧。第二个式子表示两个标签都收到了第一个探测帧，但 没有收到使能【0，0.5)区间的探测帧， 没有收到使能【0.5，1）区间的探测帧。用类似的方式,可以得

33、到以下的概率：2dP12发生在标签处的错误 错过的边缘概率为： 1在 错过条件下 错过的概率：12 这与 显然是不相同的。从中可以看出，如果遍历树的层次越深,也就是使能区间越小，那么标签被错过的几率会越小。这是因为对于一个深度较大的树, 更多的请求帧会到达标签，因此标签回应的机会也较高。以此我们可以预测，树型协议处理发生在签处的错误比较可靠，因为这些协议使用请求帧较多,正好与ALOHA协议发送相对较少的请求帧的方式相反。1rP发生在阅读器处的错误 阅读器不理想的接收会导致在阅读器处对信道状态产生错误的解释。如，如果只有一个标签发送, 阅读器没有收到正确的包，它可能被解释为空闲(不够接收功率)或

34、碰撞(传输存在,但不是可解码)。下图显示了发生在阅读器处的错误模型。 代表通道u被视为通道v的概率。在理想情况中我们认为 = 1 且 = 0 ，如果 。假设没有发送时却产生有效的单一的输出的概率 为0。 的实际值取决于底层物理环境，如噪声和衰落。 uuPuuPuvPuvPispu发生在阅读器处的错误 可以验证，基本二进制树算法在考虑阅读器错误时也依旧健壮，但对于MBT则是严重的。同错误发生在标签处一样,发生在阅读器处的错误也影响了在EBT中进行估计的正确性。如果使用基本的二进制树，当 0 0，所其他的 = 0的时候，则不会有错过的标签。如果 三个有一个为正数，则标签可以被错过。实际中，错误既会

35、发生在标签处和也会发生在阅读器处。为了缓解标签错过的问题，应该结合上述两种方法。协议制定者可能更喜欢使用阅读器重新启用已经被使能过的区间，因为这种方式对标签的智能化要求最小。scPicPuvPsiPciPcsP移动标签的处理 RFID标签的一个特别重要的场景是对于一个给定的读写器，标签进入/走出阅读器覆盖的区域，如有标签的物品放在传送带上时。这也使得协议操作不理想，但在某种程度上，它与静态/动态错误对协议的影响又不相同。图(a)中阅读器覆盖的传送带总长度为L，并且标签在传送带上移动。另一个有用的表示方法图(b)，一个给定的区间被使能，则一个条纹长度为L的二维仲裁空间被启用。如果标签均匀分布在传

36、送带上，不管传送带是否移动，一个条纹总是包含相同数量的标签。移动标签的处理 基本二进制树算法在标签进入/走出阅读器范围的情况中是健壮的，因为这相当于在标签处的阅读错误。如图，在 时，读写器检测到由 和 发送产生的碰撞，并且开始去解决这一冲突。 的令牌在0，0.5)，而 和 的令牌在(0.5，1)。在 时就解决了 。但是，在 时， 当阅读器使能 所在的区间时，标签 已经不在它的范围内了。另外，一个新的标签 却已经到来。 2t1t3t111222332移动标签的处理 与算法性能相关的一个重要参数是标签密度，即单位时间进入读写器范围内的标签数量。同样，这个密度也等于单位时间内走出阅读器范围的标签数量

37、.当标签密度小时，碰撞会很快地解决并且标签被错过的概率很低。随着密度的增加，未解析的标签的平均百分比会增加。 在一些情况中, 平均数据包到达率代表了给定算法的最大稳定吞吐量。在传送带上，如果数据包直到给定的期限(即标签离开读写器覆盖的区域)才发送，它就会被丢掉。数据包的期限 为 =L/v，v代表传送带的速度。数据包丢掉率是标签的密度和期限 的函数。 通过这样分析得到的最重要参数也许是走出阅读器的范围但未被解析的标签密度。也就是说,丢失标签问题应该通过在传送带上部署多个读写器来解决。从阅读器 范围走出的未解析标签的密度就是进入阅读器 范围的待解析标签密度。因此，在传送带上单位时间的标签数量，可以

38、确定为了保持丢失的标签数低于一定值所需的读写器的数量。 ARBR合作读写器和广义仲裁空间 1.二维仲裁空间2. 进一步的说明与多维仲裁二维仲裁空间 如图所示，读写器 和 能够通过专用连接线分享信息，它使用有线或射频接口而不同于与标签通信。另外，也可以认为这两个读写器是一个常见的分布式天线控制器。这些读写器通过下列方法与彼此相互合作：（a）他们协调传输为了避免读者碰撞（b）他们交换阅读过程中标签的相关信息。ARBR二维仲裁空间 让Tu表示的一组标记读写器的范围是u = A, B 。一般来说，设置的TA和TB是不同的。我们假设密集的标签同一区域内覆盖这两个读写器，这种假设下的RFID系统是非常强大

39、的，标记的密度显著依赖于使用场景和物理设备，就像一个仓库或者商店。二维仲裁空间 仲裁算法： (1） 发出一个最初的请求帧（记为A），标签从Ta开始回复。 （2）接下来 发送另一个请求帧（记为B），标签从Tb回复。我们定义接下来的集合：S1=Ta/Tab，S2=Tab，S3=Tb/Tab。 这两个最初的请求帧是用来让每个标签清楚Sj属于集。例如，一个标签收到从 发送的请求帧，而不是 ，这样他就属于S1。 在这两个最初的请求帧之后，这个仲裁将变为三个独立的碰撞解析过程继续进行，分别地对应每个Si的集。ARBRARBR二维仲裁空间 对S2集合的仲裁可以由两个读写器中任意一个执行，仲裁协议在一个会话集

40、Si的不间断的时间内只运行Si集。每组可以有多个会话，例如表示i-th集的会话j-th。例如,读写器可以协调运行的会话序列如下: ，T3.1，T2.2，1.用 表示集 的基数， 表示在会话 解决标签数量。ininiSji,Kji,二维仲裁空间 据每个读写器不同的覆盖范围引入空间划分，有助于碰撞的解决，因为它本质上把标签分成了更小的组。如此一个分割界定提出了以下简单的解决方案：运行三个会话1,1，2,1，3,1 ，在每个会话中所有的标签从一个给定的集开始解决，也就是说，Ki1=ni ，这样的一个解决方案功非常限制读写器间的合作，而且n1，n2，是独立完成的。 二维空间仲裁的关键思想是，除了维度随

41、机生成令牌的位置，另一个维度用来解决标签之间的碰撞。作为Si类似的符号，让S1只覆盖 ，S2覆盖Ra和Rb，S3只覆盖Rb。因为标签均匀分布在两个读写器覆盖面积内，一个标签属于Si的概率是=Si/S，S=S1+S2+S3。考虑读写器是不移动的，他们在运行一个特定的初始化过程期间已经估计了重叠的范围，从而估计出 。ARBRBRAR二维仲裁空间 复合随机过程表示:标签是随机分布的，在一个二维空间中令牌是随机分布在区间0,1)。对于一个给定的标签,随机的令牌代表它的x坐标和y坐标是随机放置。二维仲裁空间 横坐标代表随机标记的尺寸，而纵坐标代表空间位置的标记。如果两个标签是在同一空间集Si中,然后他们

42、的唯一可以区分的途径是在仲裁过程中通过使用随机的令牌。在另一方面,如果标签 Si, Sj和ij,那么这两个标签不需要使用随机的令牌来区别。二维仲裁空间 取代单独的估计 ，可以使用下面的方法。考虑到标签均匀分布在总覆盖面积的两个读写器，读写器可以分享他们在观察时间内的信息，可以获得以下总数的估计标签n=n1+n2+n3 。 使用这个总数的估计,估计基数可以获得每个标签集的 如下：二维仲裁空间 估计(使用上标)将被称为合作估计的。为了评估其正确性,它的方差可以估计如下：另一种选择是使用非合作估计,每组Si分别计算：和方差的估计决定如下：二维仲裁空间 估计方差的数值例子如图所示。目前解决间隔的值观察的 = 0.1， = 0.25， = 0.3。读写器之间的距离d由读写器之间重叠的覆盖区域控制，从而得到概率