英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

基于多个阅读器的射频识别系统的快速高效的标签查询

摘要-RFID技术已经应用于各种应用之中,如库存控制和供应链管理。在本文中,我们探讨标签查询定位问题是应用于大型RFID系统，其中包含多个RFID阅读器。首先假定一组特定的标签,在本系统中实现标签定位查询。首先，在许多实际应用中，标签定位查询是很重要；其次就是在数据库中查询标签的时间应该是很短的。到目前为止，大多数对于RFID标签查询定位的研究是没有考虑RFID阅读器之间的电磁干扰,但这将极大地影响的标签查询定位准确度和精度。同时，若考虑RFID阅读器彼此之间的干扰，那基于RFID定位识别系统的解决方案将会很难实现。本文我们提出一个利用标签搜索协议的方案来解决阅读器之间的干扰,来减少干扰，实现快速的定位和定位的精度以及RFID阅读器在互不相干扰或是将干扰降到最低的调度方案。我们提出一个新技术能快速的定位查询标签所在的位置信息。其中协议的执行时间将受到阅读器的调度方案的限制。但对于阅读器在时间上的调度认识一个问题。最后我们设计启发式算法来找到一个可行的阅读器调度的解决方案。仿真结果表明：性能优越的查询协议与现有的协议相比,该协议减少的执行时间超过40%。

I．引言

无线射频识别技术（RFID）已被广泛的应用于各个领域来提高管理效率，包括库存管理、仓库管理、供应链跟踪、智能运输系统等。在许多应用程序中，我们需要知道哪些标签是系统给定的参考标签。对参考标签的搜索我们称之为标签定位查询。因此，在许多实际应用中标签的定位查询十分钟重要的。例如，一个大型仓库，要对仓库储存的大量不同的产品进行管理，不同的产品对应不同的制造商。制造商可能对仓库产品进行检查回收（如有缺陷的产品）。仓库里产品的实时动态是不方便手动查询定位的。因此射频识别技术，无接触式的定位查询更能提高查询定位的效率、操作也十分简单方便。

直觉上，RFID标签定位技术关键是可以采用标签识别协议来解决。近年来，诸多学者对标签识别协议的研究投入了大量的研究工作。目前，我们的RFID系统可以准确地收集出现在系统查询范围内所有标签的ID。之后对所收集到的标签进行比较分析进而达到所欲想的结果。然而，这种方法在时间上是非常耗时间的。此外，RFID系统动态更改时间就要求我们每次的启动查询操作都要查询定位系统内所有的标签ID。或许是期望可以提高时间效率，只有收集新到来的标签后再进行查询操作，这种方法在时间上确实可以大大减少。但相应的未知标签的识别问题本身就是一个具有挑战性的问题。到目前为止仍没有彻底的研究去解决此类问题。

之前对标签搜索是由郑洁和李娜发起的。他们提出了一个两阶段标签搜索Cats协议之间不考虑RFID阅读器干扰，他们使用布隆滤波器测试标签是否存在于系统中。在第一阶段，利用布隆滤波器和其他相应的过滤器得到想要的参数。标签在接收滤波器的参数时，使用滤波器来确定他们所得到的参数与之前预定的是否一致。在第二阶段，阅读器从标签搜集的信息中，通过构造一个虚拟的布隆滤波器，以去除系统内外的干扰。在滤波后结果相对准确时，系统中所搜索到标签才相对精确。然而，这种方法并不适用于多个阅读器进行标签的搜索查询。因为系统所要查询的标签的数量可能会大大超一个RFID阅读器所查询标签的上限。此外，Cats协议木有考虑多个阅读器之间的电磁干扰，它假设所有的RFID阅读器是一个整体。事实上，由于附近的RFID阅读器之间存在干扰，阅读器需要在不同的时间工作，因此在实际情况下，阅读器并不能同步工作。在这种情况下，如果我们直接应用标签搜索协议，它提出的时间效率将是不可预计的，因为这两个阶段需要执行几次，这实际上不必要的。

在本文中考虑到RFID阅读器之间的干扰，我们研究多阅读器的RFID系统的搜索问题。我们看到，虽然整个系统标签的数量可能是巨大的，但在一个阅读器所能感应的范围内的标签数量是有限的。因此，我们可以快速测试已被标记的标签所在阅读器感应的范围内，在使用布隆滤波器对数据进行滤波来去除干扰。因此，我们提出的标签搜索协议基于两个方面：1)系统所搜索的标签至少被一个阅读器所感应到。2）如果标签所在位置超出所有阅读器感应的范围外，需要从系统中标记出来。在这个协议中，我们测试想要的标签在每一个阅读器的感应范围内信号强弱。在标签不及格的存在性测试之中，所有的阅读器被排除在搜索列表和剩余的搜索结果之外。

多阅读器的RFID系统中阅读器之间的干扰问题迎来了新的挑战。首先，因为布隆滤波器的假阳性的特点（即系统中的每一个标签都有可能错误的认为是布隆滤波器），我们应该减少参与搜索过程的阅读器数量来减少布隆滤波器所需的搜索精度。第二，除了阅读器的数量，阅读器的执行时间也会影响搜索协议的准确性。我们制定的最低时间内阅读器调度的标签搜索协议和证明它存在的困难程度。然后，我们开发一个启发式算法来解决这个问题，首先找到一个最小子集的阅读器调度去覆盖整个RFID系统，然后再找到一个带有图着色技术的阅读器调度方案。

本文主要做出的贡献有以下三点。第一，我们提出一个快速标签搜索协议，考虑了阅读器之间的干扰存在于多个阅读器射频识别系统中。第二，我们制定的最低时间阅读器调度的标签搜索协议的问题主要集中在于它NP困难度。然后我们提出了一个启发式算法来解决这个问题。第三，我们进行大量的模拟，已验证标签搜索协议的性能的优越性。

本文的其余部分的组织如下，在第二部分中，我们回顾相关工作。第三节中我们描述系统的模型和问题陈述。第四节详细的介绍了标签搜索协议。第六节定义和解决了最低调度阅读器问题以及部分仿真结果报告。最后第七节我们给出了一些结论。

II．相关工作

早期工作主要关注RFID系统中标签识别，旨在解决由碰撞引起的多个标签同时被RFID阅读器所检测到的冲突问题。现有的RFID识别洗衣大致可以分为两类：ALOHA-based和Tree-based。在ALOHA-based协议中，阅读器和标签之间的通信可以分为多个帧。每一帧进一步分为同步时间槽。每个标签中随机选择一个时间回复阅读器在同一位置检测到的信号。但没有一个是可以成功的识别检测出的。在基于树协议测试中，阅读器查询标签，将标签分为两个子集用更少的标签去回复阅读器所检测到的信号。如果在传输过程中发生信号的碰撞冲突，分裂过程一直持续到只有一个标签在其中一个子集中。若是在这种情况下，标签的检测是成功的。虽然标签识别协议可以用来解决标签搜索问题，但由于他们的效率十分低下，信号传输是十分耗费时间的。目前平均识别吞吐量为每秒几百个标签。

郑洁和李娜发起标签搜索项目并研究提出了一个两阶段标签搜索协议，假定所有的阅读器都是同步的。在第一阶段的协议中，要求构造布隆过滤器，并设置参考标签和K1哈希函数以及种子数S1。在接收到布隆过滤器过滤的标签后，检查它是否存在具有相同K1哈希函数和中子数S1。标签通过存在测试后其中保持活跃的候选标签参与下一阶段的测试。如在下一阶段测试不合格的标签将被舍弃。在第二阶段，阅读器传输一个随机的种子S1和K2只是值的多少。再根据哈希函数选出的标签来对阅读器感应信号作出响应。阅读器然后从候选标签中构造出一个手机回复帧长度相同的布隆过滤器，过滤器的元素标记为“1”对应的插槽是否为非空或是标记值是否为0。对于每一个想要的标签，它的存在于系统中，需要检查构造布隆过滤器，通过测试和标签是否包含在结果之中。然而，我们的工作木有考虑到在多个阅读器之间存在的干扰。相比之下，本文考虑到每个阅读器之间的干扰，进而实现共同优化搜索的的准确性和阅读器调度实现时间的效率高。

近年来一些学者研究关注阅读器调度在RFID识别系统中应用得到突破性的进展，如沃尔德罗普等。他提出了colorwave分布式算法,试图将颜色应用于RFID系统中，这样不同阅读器之间的干扰将会得到不同的颜色。 Zhou et al提出了基于STDMA的阅读器调度的算法（空间时分多址），试图最小化所需的总时间。慢慢还有一些研究学者也将为他们的解决方案扩展到多通道的场景。如唐家璇等，他提出了覆盆子的概念。旨在是系统工作在一个长期稳定的到达阅读器所能标记的区域。在最近的一次工作中，唐等提出了一个调度算法为阅读器最大化服务标记的次数能够达到很高的范围。同时也能避免阅读器之间的相互干扰。目前阅读器调度标记识别标签的总体目标是提高识别吞吐量，因此他们风愿意安排尽可能多的阅读器同时工作。然而，在我们的协议中，我们要求达到共同优化搜索准确性和阅读器调度的总执行时间最小化。有事宁愿使用尽可能少的阅读器来缩短标签存在测试的时间。

III．系统模型和问题陈述

1. 系统模型

在我们的系统模型中，该系统被分为三个部分：后端服务器、RFID阅读器、电子标签。后端服务器发送给参数（如帧大小和随机种子）给阅读器。并安排他们工作在不同的时间避免发生碰撞。RFID阅读器通过高速网路连接到后端服务器。并从后端服务器于带有参数的标签进行通信，接收并报告从标签到服务器手机的回复信号。系统中的标签是可以主动标记或是被动标记。

RFID阅读器和标签之间的通信是采用帧槽ALOHA协议。[3] 阅读器开始通过发送命令或查询标签进行通信,并相应地标记回复阅读器。通信可分为不同的层次。在每一帧的开始，阅读器传输两个参数，帧尺寸fr和一个随机种子给标签。在接收这些参数标记计算器槽数sc=H(IDt | | r)，H是一个统一的哈希函数和IDt是t的ID标签。

我们假设在一个框架中每一个标签可以多次回复阅读器，和之前一样[7]，可以通过让标签存储不同的哈希函数,生成多个槽索引和相同的随机种子[7],[21]。在实现中,在每一帧的开始阅读器传输一个额外的参数k告诉标签选择k索引和回复阅读器的选择k插槽。槽索引只计算sci=Hi(IDt | | r)( 1 le; i le; k)，在这个范围1 le; i le; k里哈希函数预存储标签。阅读器也可以使用相同的哈希函数集，从而确切知道插槽标记t将回复哪个标签。

在不同时间段根据标签回复阅读器的数量是持续变化的。在传统框架ALOHA协议,标签向阅读器传递他们的id。我们用时间tid表示标签传送了一个标签id。如果木有标签回顾阅读器的位置。我们称之为空槽，其持续的是用te表示。在我们的协议中,阅读器只需要检测一个插槽是否为空。为了实现这一目标,标签可以传输一个比特响应阅读器。通常在multi-reader的RFID系统中有tidgt;tb gt;t e。在射频识别系统中，阅读器之间的干扰导致附近的阅读器之间发生电磁碰撞。我们考虑两种类型的碰撞在附近的阅读器之间:

Reader-Tag碰撞:如图1所示(a)。如果标签t是在阅读器的审讯范围，同时也在阅读器B的干扰范围内,其回复阅读器信号可能有来自阅读器Ｂ的干扰。我们称之为Reader－Tag碰撞(RTcs)。

Reader-Reader碰撞:如图1所示(b),如果标签t同时被两个阅读器Ａ和Ｂ所捕获到,那么它不能正确解码相关命令并发送给阅读器。我们称之为Reader－Reader碰撞(RRcs)。

因此，系统中的阅读器应该仔细计划工作时间，利用在不同的时间工作来避免这两种碰撞。

1. 问题陈述

在前一节中给出的系统模型，我们现在制定标签搜索问题。目前，在RFID系统中表示集合中所有的标签T = { t1,hellip;、tn }和集合中所有的RFID阅读器R = { r1,hellip;hellip;,r l }以及集合中表示预定的标签集合W = { w1,hellip;,wm }。然后，标签搜索问题就是找到WT和RT之间的交集，试图将安排阅读器所需的时间尽可能的减少。有时容忍一些叫养性的错误在误差范围内是可以接受的结果。其中由alpha;表示假阳性率的门槛，我们试图找到这样的一组T，（Tsupe;W T）T出现的几率都包含在alpha;中。例如，当alpha;=0 .05，|W| = 1000，WT实际上包含了500个标签，那么T中标签不应该超过(1000minus;500)lowast;0.05 = 25个，但实际上并不是这样。

IV．TSIM：MULTI-READER RFID系统中标签搜索

　A．两个直观的解决方案

我们先给两个直观的方法来解决在multi-reader RFID系统中标签搜索的问题。在第一个解决方案中，我们直接收集IDs系统中所有的标签,并通过比较T和w找到结果。我们使用最先进的RFID阅读器的调度算法识别[8]－[11]。与单个阅读器调度相比，多个阅读器可以并行工作，从而大大提高了标签识别的吞吐量。这种方法可以获取准确的结果。然而，所花费的时间相比之下会变得较长。在本文中我们称这种方法为收集的方法。在第二个解决方案中，我们在multi-reader环境中采用CATS协议[7]，但考虑阅读器之间的干扰。CATS协议有两个阶段，当考虑干扰时，系统中的阅读器应该被安排在不同的时间段工作，假设所有的阅读器在安排调度中总轮的次数是Ｎ，如果我们用CATS协议来解决标签搜索问题，就需要执行两个阶段中的Ｎ个回合。不可避免的增加了搜索的时长。本文中我们称这种方法为CATS-M，意思就是此方法考虑到多个阅读器之间的干扰。但是需要我们注意的是该方法包含假阳性误差，其中为了满足假阳性率的要求，那些假阳性率单一变化的阅读器拍除外应该重新计算系统的假阳性率。

B．合理的解决方案

我们现在描述的标签搜索协议多是涉及到多个阅读器存在的RFID系统，在本节中，我们假设RFID阅读器已经获得调度。但如何获得一个最优的阅读器调度将在第五节进行讨论。

TSIM设计是出于两个观察，首先，如果想要标记t是在系统中。即tisin;W t,那么它必

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[150300]，资料为PDF文档或Word文档，PDF文档可免费转换为Word