Fast and Reliable Missing Tag Detection for Multiple-Group RFID Systems 翻译

摘要

​ 近年来，射频识别（RFID）技术已被应用于各种场景。在一些实际的RFID应用中，带有标签的物品可以分为多个组。因此，高效、准确地检测各组的丢失标签至关重要。因此，本文主要研究多组RFID系统中的丢失标签检测问题，并在此基础上提出了三种不同的协议。首先，我们提出了一个智能多组丢失标签检测协议，该协议充分利用了预期的单时隙。然后，提出了一种增强的多组丢失标签检测协议，该协议可以显著节省广播和响应时间。最后，设计了一个准确、快速的多组丢失标签检测协议，其检测可靠性约为100%。理论分析和大量仿真结果验证了本文提出的协议优于其他协议。

1 介绍

1.1 背景

​ 近十年来，射频识别（RFID）技术取得了巨大的成就。RFID技术具有使用寿命长、效率高、安全性高、容量大等特点。这些特点使得RFID技术广泛应用于各个行业，如物流跟踪，仓库管理，零售业，以及医学领域。

​ RFID应用程序中通常会部署多个带有大量标签的阅读器，并提供一个后端服务器来实现计算和存储功能。每个阅读器配备一个或多个天线，可以收集其询问范围内的标签发送的响应。一般来说，标签可以根据通信方式分为两类：被动标签和主动标签。被动标签没有电源，依靠阅读器发出的电磁信号进行回复，而主动标签有内部电源，基于此可以直接回复阅读器。后端服务器存储所有标签的ID，并通过高性能计算能力向阅读器提供实时指令。

​ 作为RFID应用中的关键技术之一，丢失标签检测可以应用于各种场景，例如大型仓库中的丢失货物检测和物流中的丢失物体检测。幸运的是，RFID技术的出现为这个棘手的问题提供了完美的解决方案。RFID系统可以通过丢失标签检测及时感知丢失物体。

​ 如今，随着用户需求的增加，RFID系统的规模不断扩大。带有RFID标签的物品通常可以根据不同的要求和特征（如品牌、尺寸和材料）分为多个组。例如，对丢失的贵重物品（如珠宝）的检测应该比普通的更可靠。因此，本文主要研究在不同群体中高效可靠的丢失标签检测。

1.2 问题和解决方案

​ 近年来，丢失标签检测问题得到了广泛的研究。大多数方案都基于帧时隙Aloha协议[16]、[18]、[29]，以减少数据碰撞。特别是，在[27]中引入了Bloom过滤器，以检测多组多区域RFID系统中丢失的标签，这比以前的工作更有效。Bloom过滤器是一种数据结构，可以有效地确定集合中是否存在元素。然而，可以观察到，在基于Bloom过滤器的方案中，无法避免不可用的时隙（即，空时隙和大部分碰撞时隙），导致检测效率低下。此外，大多数基于帧时隙Aloha的协议都会遇到由通信模式引起的缺陷。受观察结果的启发，充分利用每个可用时隙（即单时隙）来提高检测效率是本文非常关注的问题。

​ 为此，本文提出了三种协议来检测多组RFID系统中丢失的标签。首先，提出了一种智能多群丢失标签检测协议,提出了一种利用期望单时隙实现丢失标签检测的AMD算法。与传统的基于Bloom过滤器的方案相比，AMD协议的检测效率可以大大提高。其次，提出了一种改进的多组丢失标签检测协议（EMD），该协议避免了预期帧向量的广播，进一步提高了检测效率。最后，提出了一种准确、快速的多组丢失标签检测协议（AEMD）。AEMD协议首先将预定义的内置向量写入标签存储器，然后当阅读器广播的组ID匹配时，每个标签使用标签时隙将预先写入的向量发送给阅读器。之后，阅读器通过OR操作将一个标签时隙中的所有响应组合成一个复合向量，如果复合向量中的任何位为“0”，则可以检测到丢失的标签事件。由于每个标签的预定义内建向量的唯一性，AEMD协议的效率可以大大提高，可靠性可以接近100%。这三个协议都来自同一个来源，致力于提高时隙的利用效率。

1.3 主要贡献

​ 本文的主要贡献总结如下。

​ （1）首先，提出了AMD协议，与基于Bloom过滤器的方案相比，AMD协议利用了预期的单时隙，提高了检测效率。

​ （2）其次，提出了EMD协议，该协议避免了预期帧向量的广播，进一步提高了检测效率。

​ （3）第三，提出了AEMD协议，该协议通过预写消息保证了检测的可靠性，大大提高了检测效率。

​ （4）第四，对参数优化进行了充分的理论分析，以分别最大限度地提高AMD和EMD协议的检测效率。

​ （5）最后，进行了大量仿真，结果表明了所提协议的有效性。

​ 本文的其余部分组织如下。第二节回顾相关著作。第三节介绍了系统模型并阐述了问题。AMD协议在第四节设计，我们在第五节介绍EMD协议。第六节详细介绍了拟议的AEMD。在第七节，我们进行了广泛的绩效评估。最后，第八节对本文进行总结。

2 相关工作

​ 近几年来，RFID技术得到了广泛的研究，涌现出了大量优秀的作品[3]、[12]、[15]、[25]，推动了物联网的快速发展,（物联网）[7]、[23]、[24]。丢失标签监控的研究一般可分为两类：概率丢失标签检测（即丢失标签检测）[13]，,[26]和确定性丢失标签检测（即丢失标签识别）[4]，[6]。然后，简单介绍了相关工作。

2.1 丢失标签检测

​ 在满足可靠性要求的前提下，丢失标签检测的目标是检测RFID系统中是否存在丢失标签。丢失标签检测倾向于检测丢失标签事件，而丢失标签识别需要识别所有丢失标签。因此，在某些实际场景中，丢失标签检测通常更灵活、更有效。

​ 提出了第一个概率检测协议TRP[19]，该协议通过比较位图中的预期时隙与系统中标签的实际响应来检测丢失标签事件。当预期的非空时隙实际为空时，可以检测到缺少标签事件。Shahzad和Liu[16]提出了RUN协议来检测丢失的标签事件，同时考虑了意外标签的影响。RUN协议将预计算帧中的所有时隙与OR帧中的相应时隙进行比较，以检测丢失的标签事件。当任何时隙在预计算帧中为1，但在OR帧中为0时，都可以检测到缺少标签事件。RUN协议可以在带有意外标签的更恶劣环境中工作。Yu等人[26]提出了BMTD协议，该协议引入了Bloom过滤器来检测丢失的标签。BMTD协议首先使用多个种子构造一个Bloom过滤器向量来停用意外标签，避免意外标签参与检测询问。然后在第二阶段，通过收集标签响应，采用Bloom过滤器检测丢失标签事件。Yu等人[27]随后提出了三种协议，它们也基于Bloom过滤器来检测多组多区域RFID系统中丢失的标签。对三种协议的参数进行了不同的优化，以实现不同的检测效率。

2.2 丢失标签识别

​ 丢失标签识别的目的是准确识别所有丢失标签，这往往比丢失标签检测更耗时。因此，丢失标签识别适合于高精度的要求。

​ Li等人[6]设计了一系列丢失标签识别协议。最好的方法是完全移除轮询阶段，并迭代执行帧阶段。帧用于验证标签的存在，然后可以识别未收到响应的丢失标签。Liu等人[11]提出了SMTI协议，该协议通过多次散列将空时隙和碰撞时隙位图中的预期单时隙，从而实现更好的时间效率。同时，SMTI协议也讨论了信道丢失的不完全情况。[17]中提出了ProTaR协议，该协议利用标签ID的部分位来描述标签的唯一性。然后，避免了冗余比特的传输，以提高时间效率。阅读器构造的位向量可以减少碰撞的影响，充分利用标签响应。Yu等人[28]首先在COTS RFID系统中提出P2M协议，以询问标签并收集其EPC，并且可以识别EPC不存在的丢失标签。然后，为了进一步提高时间效率，提出了P2P协议，该协议使用Select命令对每个时隙中的标签进行奇异化，以避免碰撞事件。

3 系统模型和问题定义

3.1 系统模型

​ 如图1所示，认为大规模RFID系统由后端服务器、阅读器和G组RFID标签组成。每个RFID标签都标有一个组ID和一个唯一的96位ID，组ID指示它所属的组，而该ID可用于身份验证。阅读器知道所有标签的ID和组ID，并且可以根据哈希函数预测每个时隙的状态。虽然每个组中都会不时发生丢失标签事件，但阅读器不知道哪些标签丢失，也不知道丢失标签的数量。在这样一个多组RFID系统中，每个组中发生的丢失标签事件都应该被及时检测到，以减少损失。请注意，对于大型多组RFID系统，我们提出的协议可以很容易地扩展到多阅读器场景，其中阅读器可以通过后端服务器进行调度和同步。

​ 基于帧时隙Aloha协议[16]、[18]、[29]，阅读器和标签之间的通信由多个时隙帧组成，每个时隙帧包括多个时隙。根据是否存在标签响应，可以将时隙分为三类：空时隙、单时隙和碰撞时隙。空时隙表示没有标签响应，单时隙表示只有一个标签响应，碰撞时隙表示时隙中同时存在多个标签响应。此外，这些时隙还可以根据它们可以传输的消息分为三类：短时隙、长时隙和标签时隙。短时隙ts表示用于传输1bit信息，表示为tl的长时隙可用于传输8位消息，表示为ttag的标签时隙可用于传输96位消息，它们分别设置为ts=0.4毫秒、tl=0.8毫秒和ttag=2.4毫秒。

3.2 问题定义

​ 本文的目的是检测多组RFID系统中每个组的丢失标签事件，如图1所示。对于任意群g（1≤ g≤ G） ，我们使用Ng表示标签的数量，mg表示丢失标签的数量，Mg表示丢失标签数量的阈值。那么，本文要解决的问题可以定义如下。

​ 定义 1：对于多组 RFID 系统，给定组 g(1 ≤ g ≤ G) 所需的检测可靠性 αg，当丢失标签的数量 mg 等于或大于阈值 Mg，需要以Pg >= αg的概率检测到丢失标签事件。

​ 为了有效地解决定义1中定义的问题，本文设计了三个协议，它们试图充分利用每个可用时隙。接下来，我们将详细介绍这些协议。

4 AMD协议

​ 现有的大部分丢失标签检测工作都采用帧时隙aloha协议，这会导致一帧中存在大量的空时隙和冲突时隙，并且时间效率相对较低。因此，设计了一种智能多组丢失标签检测协议AMD，该协议利用预期的单时隙来检测丢失标签。

4.1 协议描述

​ 阅读器首先通过使用带有随机种子 R 的散列函数将组中的所有标签映射到 fg 位数组来构造组 g(1 ≤ g ≤ G) 的预期帧向量 Vg。Vg 中仅由一个标签映射的位设置为“1”，否则设置为“0”。换句话说，“1”代表预期的单时隙，并且,“0”表示预期的非单时隙。

​ 然后，阅读器逐组广播组ID，参数<fg, R> 和向量Vg给标签。如果一个标签接收到它所属的组ID，它通过计算H（ID，R）mod fg来选择Vg中的一个位，其中H（·）是哈希函数，它将使用标签时隙向阅读器发送响应。响应为96位，由一个“1”位和95个“0”位组成。由于在Vg广播后，每个标签可以获取向量Vg中的所有位状态，因此标签可以计算其所选位之前的“1”位的数量。然后，也可以得到标签i的选中位在所有“1”位中的索引，记为Xi。因此，标签响应中“1”位的索引由(Xi mod 96)确定。此外，用于传输响应的标签时隙的索引也可以通过 X i / 96 Xi/96 Xi/96获得。在接收到标签时隙中的所有响应后，阅读器执行 OR 操作将响应组合成一个 96 位的复合向量。如果复合向量中预期为“1”的位实际上是“0”，可以得出结论，g组中存在丢失标签事件，该组的检测立即终止。上述过程可以在每组中执行多次，以进一步提高检测可靠性。

4.2 AMD说明

​ 图2示出了任意组g的AMD协议的图示。假设有八个标签，帧大小fg为10，标签8丢失。阅读器器首先将所有标签映射到一个10位的数组，通过使用随机种子R对标签id进行散列来构造预期的帧向量Vg。标签2、3、6和8分别映射到单时隙，其数量显然是4。在接收到组ID和预期的帧向量Vg之后，这四个标签中的每一个都向阅读器发送4位响应。每个标签响应中“1”位的索引由Vg的所有“1”位中所选位的索引确定。如图2所示，标签2、3和6的响应分别为“1000”、“0010”和“0100”。然后，阅读器通过OR运算将所有响应组合成一个复合向量。复合向量中的第四位是“0”，因为标签8正在丢失，它不会响应阅读器。然后，在该组中报告丢失标签事件，阅读器立即终止对该组的检测，并转向对下一组的检测。

4.3 性能分析

​ 对于任意群g（1≤ g≤ G） ，有Ng标签，帧大小为fg。然后，预期帧向量Ps的单时隙的比率可以计算为
P s = C 1 N g ⋅ 1 f g ⋅ ( 1 − 1 f g ) N g − 1 ≈ N g f g ⋅ e − N g − 1 f g ( 1 ) P_s=C_1^{N_g}· \frac{1}{f_g}·(1-\frac{1}{f_g})^{N_g-1} ≈\frac{N_g}{f_g}·e^{-\frac{N_g-1}{f_g}}\qquad\qquad\qquad(1) Ps​=C1Ng​​⋅fg​1​⋅(1−fg​1​)Ng​−1≈fg​Ng​​⋅e−fg​Ng​−1​(1)
​ 单时隙Ps的比率大约为1e(≈36.8%）通过它的衍生物，因此我们有了AMD协议的NG=fg，目的是最大限度地利用预期的单时隙。当 Ng = fg 通过其导数时，单时隙的比率 Ps 可以接近 1/e (≈36.8%)，因此我们有 Ng = fg 用于 AMD 协议，旨在最大限度地利用预期的单时隙。

​ 我们认为有 rg 轮来检测 g 组中的丢失标签事件。 然后，以下定理确定 rg 的最佳值，以最小化检测时间，同时满足所需的检测可靠性。

​ 定理1：g组中探测轮数的最佳值，表示为 r g ∗ r^*_g rg∗​，当满足所需的可靠率时，以最小化检测时间。可靠率为
r g ∗ = [ l n ( 1 − α g ) m g ⋅ l n ( 1 − 1 e ) ] （ 向 上 取 整 ） ( 2 ) r^*_g= [\frac{ln(1-α_g)}{m_g·ln(1-\frac{1}{e})}]（向上取整）\qquad \qquad(2) rg∗​=[mg​⋅ln(1−e1​)ln(1−αg​)​]（向上取整）(2)
​ 证明：对于任意一轮，可以观察到只有1/e个标签可以被有效地询问。然后，可以获得在当前轮中一个标签丢失没有被检测到的概率Pn：
P n = C 1 N g ⋅ 1 f g ⋅ ( 1 − ( 1 − 1 f g ) N g − 1 ) ≈ 1 − 1 e ( 1 ) P_n=C_1^{N_g}· \frac{1}{f_g}·(1-(1-\frac{1}{f_g})^{N_g-1}) ≈1-\frac{1}{e}\qquad\qquad\qquad(1) Pn​=C1Ng​​⋅fg​1​⋅(1−(1−fg​1​)Ng​−1)≈1−e1​(1)
​ 在rg轮检测之后，仍然没有检测到丢失标签事件的概率可以推导为 ( 1 − 1 e ) m g r g (1-\frac{1}{e})^{m_gr_g} (1−e1​)mg​rg​。给定g组所需的检测可靠性αg，我们有：
1 − ( 1 − 1 e ) m g r g ≥ α g ( 4 ) 1- (1-\frac{1}{e})^{m_gr_g} ≥ α_g \qquad\qquad(4) 1−(1−e1​)mg​rg​≥αg​(4)
​ 然后对（4）进行整理后可得 r g ≥ l n ( 1 − α g ) m g ⋅ l n 1 − 1 e r_g≥\frac{ln(1-α_g)}{m_g·ln1-\frac{1}{e}} rg​≥mg​⋅ln1−e1​ln(1−αg​)​。因此可得 r g ∗ = l n ( 1 − α g ) m g ⋅ l n 1 − 1 e r^*_g=\frac{ln(1-α_g)}{m_g·ln1-\frac{1}{e}} rg∗​=mg​⋅ln1−e1​ln(1−αg​)​，在满足检测可靠性要求的情况下，可以最大限度地缩短检测时间。由于 r g ∗ r^*_g rg∗​是整数，对结果进行向下取整。

​ 我们使用 T A M D T_{AMD} TAMD​表示AMD协议的总检测时间，它由两部分组成：阅读器的查询时间 T A M D B T^B_{AMD} TAMDB​和标签回复时间 T A M D R T^R_{AMD} TAMDR​。对于g组的任意一轮，广播参数的时间和预期帧向量可以计算为 ( 1 + f g 96 ) ⋅ t t a g (1+\frac{f_g}{96})·t_{tag} (1+96fg​​)⋅ttag​，标签响应的时间可以计算为 f g 96 e ⋅ t t a g \frac{f_g}{96e}·t_{tag} 96efg​​⋅ttag​。然后，广播时间TB AMD和响应时间TR AMD可以导出为：
T A M D B = r g ⋅ ∑ g = 1 G ( 1 + f g 96 ) ⋅ t t a g T A M D R = r g ⋅ ∑ g = 1 G ( f g 96 e ) ⋅ t t a g ( 5 ) T^B_{AMD}=r_g·\sum^G_{g=1}(1+\frac{f_g}{96})·t_{tag}\\ T^R_{AMD}=r_g·\sum^G_{g=1}(\frac{f_g}{96e})·t_{tag} \qquad\qquad(5) TAMDB​=rg​⋅g=1∑G​(1+96fg​​)⋅ttag​TAMDR​=rg​⋅g=1∑G​(96efg​​)⋅ttag​(5)
​ 最后，可以得到AMD协议的总检测时间:
T A M D = T A M D B + T A M D R = r g ⋅ ∑ g = 1 G ( 1 + f g 96 ) ⋅ t t a g + r g ⋅ ∑ g = 1 G ( f g 96 e ) ⋅ t t a g = r g ⋅ ∑ g = 1 G ( 1 + f g 96 + f g 96 e ) ⋅ t t a g T_{AMD}=T^B_{AMD}+T^R_{AMD}\\ =r_g·\sum^G_{g=1}(1+\frac{f_g}{96})·t_{tag} +r_g·\sum^G_{g=1}(\frac{f_g}{96e})·t_{tag}\\ =r_g·\sum^G_{g=1}(1+\frac{f_g}{96}+\frac{f_g}{96e})·t_{tag} TAMD​=TAMDB​+TAMDR​=rg​⋅g=1∑G​(1+96fg​​)⋅ttag​+rg​⋅g=1∑G​(96efg​​)⋅ttag​=rg​⋅g=1∑G​(1+96fg​​+96efg​​)⋅ttag​

5 EMD协议

​ AMD协议通过充分利用预期的单时隙，在多组RFID系统中实现高效的丢失标签检测，大大缩短了响应时间。然而，AMD协议的预期帧向量广播仍然很耗时。然后，设计了一种增强的多组丢失标签检测协议EMD，避免了期望帧向量的传播，提高了时间效率。

5.1 协议描述

​ 阅读器首先通过使用带有随机种子 R 的散列函数将组中的所有标签映射到 fg 位数组来构造组 g(1 ≤ g ≤ G) 的预期帧向量 Vg。Vg 中至少有一个标签映射的位设置为“1”，没有标签映射的位设置为“0”。然后，阅读器逐组向标签广播组ID、帧大小fg和随机种子R。然后，组ID匹配的标签i执行H（ID，R）mod fg，其结果被记录为Yi。然后，它选择一个标签时隙向阅读器发送96位响应，该响应由一个“1”位和95个“0”位组成。标签时隙索引由 Yi/96确定,响应的“1”位的索引由（Yi mod 96）确定。之后，阅读器将一个标签时隙中的所有响应组合成一个组合响应向量V g，用于g组。然后，当一个位在Vg中为“0”，而在Vg中为“1”时，可以检测到g组中的丢失标签事件，并且该组的检测立即终止。还可以多次执行每组检测，以提高检测可靠性。之后，通过广播组ID、参数和随机种子R来启动下一个组检测。将迭代执行上述过程，直到完成所有组检测。

5.2 EMD说明

​ 如图3所示，假设g组中有八个标签，并且这些标签被映射到10位阵列以构造预期的帧向量Vg。然后，连续广播组id和参数。之后，接收到匹配的组ID的每个标签使用随机种子R执行哈希函数，以选择标签时隙并向阅读器发送10位响应。从图3可以看出，标签1被映射到第三个时隙，该时隙是预期的冲突时隙，然后它将向阅读器发送第三位为“1”的10位响应。类似地，标签2响应的第一位是“1”，标签3响应的第六位是“1”，依此类推。然而，标签8丢失，它不会向阅读器发送任何响应。然后，阅读器通过OR操作将该标签时隙中的所有响应合并成一个复合向量Vg。与预期的帧向量相比，可以发现第九位在Vg中为“0”，但在Vg中为“1”，这表明缺少标签8。然后，阅读器立即终止对该组的检测，报告丢失标签事件，并转到下一组检测。

5.3 性能分析

​ 如第IV-C节所述，当帧大小等于任意组g（1≤ g≤ G）中的标签数量时，可以最大化单时隙的比率，即fg=Ng。为了提高预期单时隙的利用率，EMD协议中还采用了fg=Ng。除了单个时隙之外，可以观察到，当碰撞时隙仅由多个丢失的标签映射时，也可以检测到丢失的标签事件；该时隙称为同质时隙，定义如下。

​ 定义2：同质时隙：时隙仅由丢失标签映射的话，其数量大于一。

​ 因此，只有将丢失的标签映射到预期的单时隙或同质时隙时，才能检测到丢失的标签事件。

​ 我们认为，G组仍然存在rg轮来检测丢失的标签。以下定理确定了rg的最佳值，以最小化检测时间，同时满足所需的检测可靠性。

​ 定理2：g组中探测轮数的最佳值，表示为r∗g、 在满足检测可靠性要求的前提下，最大限度地缩短了检测时间：
r g ∗ = [ l n ( 1 − α g ) l n ( ( 1 − 1 e ) m g + 1 − 1 e ⋅ ∑ i = 2 m g ( i m g ) ( 1 f g ) i ) ] （ 向 上 取 整 ） ( 7 ) r^*_g= [\frac{ln(1-α_g)}{ln((1-\frac{1}{e})^{m_g}+1-\frac{1}{e}·\sum^{m_g}_{i=2}(^{m_g}_i){}(\frac{1}{f_g})^i)}]（向上取整）\qquad \qquad(7) rg∗​=[ln((1−e1​)mg​+1−e1​⋅∑i=2mg​​(img​​)(fg​1​)i)ln(1−αg​)​]（向上取整）(7)
​ 证明：对于组 g 中的任意轮，丢失标签映射到预期单时隙的概率为 1/e ，这意味着它可以被正确检测到。通过单时隙在当前轮次中无法正确检测到丢失标签事件的概率是 ( 1 − 1 e ) m g (1-\frac{1}{e})^{m_g} (1−e1​)mg​。考虑到丢失标签的数量相对较少，当前一轮中同质时隙Ph的比例可以计算为：
P h = ∑ i = 2 m g ( i m g ) ( 1 f g ) i ( 1 − 1 f g ) N g − i ≈ 1 e ∑ i = 2 m g ( i m g ) ( 1 f g ) i ( 8 ) P_h=\sum^{m_g}_{i=2}(^{m_g}_i)(\frac{1}{f_g})^i(1-\frac{1}{f_g})^{N_g-i}≈\frac{1}{e}\sum^{m_g}_{i=2}(^{m_g}_i)(\frac{1}{f_g})^i \qquad\qquad (8) Ph​=i=2∑mg​​(img​​)(fg​1​)i(1−fg​1​)Ng​−i≈e1​i=2∑mg​​(img​​)(fg​1​)i(8)

​ 在rg轮检测之后，仍然没有检测到错丢失标签事件的概率Pu可以推导为
P u = ( ( 1 − 1 e m g ) + 1 − P h ) = ( ( 1 − 1 e m g ) + 1 − 1 e ∑ i = 2 m g ( i m g ) ( 1 f g ) i ) r g ( 9 ) P_u=((1-\frac{1}{e}^{m_g})+1-P_h)\\ =((1-\frac{1}{e}^{m_g})+1-\frac{1}{e}\sum^{m_g}_{i=2}(^{m_g}_i)(\frac{1}{f_g})^i )^{r_g} \qquad\qquad (9) Pu​=((1−e1​mg​)+1−Ph​)=((1−e1​mg​)+1−e1​i=2∑mg​​(img​​)(fg​1​)i)rg​(9)
​ 给定所需的检测可靠性αg，我们可得
1 − P u ≥ α g ( 10 ) 1 − ( ( 1 − 1 e m g ) + 1 − 1 e ∑ i = 2 m g ( i m g ) ( 1 f g ) i ) r g ≥ α g ( 11 ) 1-P_u ≥ α_g \qquad\qquad(10)\\ 1-((1-\frac{1}{e}^{m_g})+1-\frac{1}{e}\sum^{m_g}_{i=2}(^{m_g}_i)(\frac{1}{f_g})^i )^{r_g} ≥α_g\qquad\qquad (11) 1−Pu​≥αg​(10)1−((1−e1​mg​)+1−e1​i=2∑mg​​(img​​)(fg​1​)i)rg​≥αg​(11)
​ 然后可通过（11）得到r_g，从而可得到 r g ∗ r^*_g rg∗​是最优的，它可以在满足所需可靠性的同时最大限度地缩短检测时间。与AMD协议相比，EMD协议避免了预期帧向量的广播，提高了广播效率。虽然预期的非单时隙也通过标签传输，增加了响应的时间成本，但是避免预期帧向量的广播的效果比增加响应时间成本的效果更大。

​ 与AMD协议相比，EMD协议避免了预期帧向量的广播，提高了广播效率。 虽然期望的非单子时隙也是通过标签传输的，增加了响应的时间成本，但避免广播期望帧向量的效果大于响应时间成本的增加。 因此，与 AMD 协议相比，EMD 的时间效率可以大大提高。

​ 我们用TEMD来表示总检测时间； TEMD 由阅读器询问时间和标签响应时间组成。 对于任意一轮的组 g，一个标签时隙就足以广播命令。 标签响应时间可以计算为fg/96·ttag。 然后，TEMD可以推导出为
T E M D = r g ⋅ ∑ g = 1 G ( 1 + f g 96 ) ⋅ t t a g ( 12 ) T_EMD=r_g·\sum^G_{g=1}(1+\frac{f_g}{96})·t_{tag} \qquad\qquad (12) TE​MD=rg​⋅g=1∑G​(1+96fg​​)⋅ttag​(12)
​ 因此，EMD 协议通过式（6）和式（12）的 AMD 协议相比，可以节省 r g ⋅ ∑ g = 1 G f g 96 e r_g·\sum^{G}_{g=1}\frac{f_g}{96e} rg​⋅∑g=1G​96efg​​的时间成本，大大提高了 EMD 协议的检测效率。

6 AEMD协议

6.1 准备

​ 在描述协议之前，我们首先简要介绍一下内存库。（C1G2）RFID标准,[1] 指定RFID阅读器和标签之间的交互和通信规则。根据C1G2协议，标签包含四个不同的内存库，称为MemBank，用于存储特定信息。MemBank-0、MemBank-1和MemBank-2分别用于存储密码、电子产品代码（EPC，即标签ID）和TID号，而MemBank-3用于存储用户可以读写和定制的数据。

​ 为了避免时隙浪费，提高检测效率，充分利用每个时隙是检测丢失标签的关键。为此，我们基于可定制的MemBank-3设计了一个准确、快速的多组丢失标签检测协议AEMD，该协议可以将每个标签分配到一个唯一的时隙。特别是，AEMD协议包括两个阶段：（1）分配阶段和（2）检测阶段。下面将详细介绍AEMD协议。

6.2 分配阶段

​ 为了指定每个标签的唯一性，我们为每个标签分配一个标签序列。由于标签时隙可用于传输96位消息，标签序列的大小设置为96位。特别地，如果标签数量大于 96，则将一个组中的标签划分为 Ng/96 (1 ≤ g ≤ G) 子组，以区分每个标签。因此，组 ID、子组索引和 96 位标签序列完全组成了称为内置向量的可定制消息，这些消息将写入标签内存中，其中组 ID 和子组索引指示哪个组和标签所在的子群，标签序列就是将要发送给阅读器的响应。 组ID由用户确定，子组索引和标签序列由以下描述确定。

​ 首先，一组中的所有标签按照阅读器预先知道的标签ID升序排列。 然后，标签序列的第一个标签的第一位设置为“1”，其他所有位设置为“0”。 第二个标签的标签序列的第二位设置为“1”，其他所有位设置为“0”。 之后，可以通过类似的方式建立一个组中所有标签的标签序列。显然一个标签序列只能处理 96 个标签。因此，如果组中的标签数大于96， l o g 2 ( N g 96 + 1 ) log_2(\frac{N_g}{96}+1) log2​(96Ng​​+1)位以表示 N g 96 \frac{N_g}{96} 96Ng​​个子组是必要的。因此，子组索引的长度为 l o g 2 ( N g 96 + 1 ) log_2(\frac{N_g}{96}+1) log2​(96Ng​​+1)。属于一个子组的标签的子组索引相同，但标签序列不同。 因此，子组索引和标签序列可以唯一地标签该组中的每个标签。 然后将组ID、子组索引和标签序列合并到内置向量中，然后写入标签的MemBank-3。 需要注意的是，写操作可以根据C1G2协议通过写命令来实现。 此外，此阶段离线执行且仅启动一次。

​ 如图4所示，我们以g组（1≤ G≤ G）为例，说明AEMD协议。假设有 Ng = 480 个标签，子组索引的长度为 log2(Ng / 96 +1) = 3。那么，前 96 个标签的子组索引设置为“000”， 第二个 96 个标签设置为“001”，以此类推。 此外，将所有标签序列初始化为零，然后将每个子组中第一个标签的标签序列的第一位设置为“1”，将第二个标签的标签序列的第二位设置为“1”，以此类推 . 之后，通过写入操作将内置向量（每个向量由组 ID、子组索引和标签序列组成）写入标签内存。

6.3 检测阶段

​ 阅读器通过连续广播组ID和子组索引来查询不同组中的标签。每个标签都可以根据组ID和子组索引确认它所属的子组。然后，该子组中的每个标签将使用标签时隙将其96位标签序列传输给阅读器。之后，阅读器通过OR操作将标签时隙中的这些标签序列组合成96位向量。由于所有标签ID都是预先知道的，所以阅读器可以预测向量中每个位的状态。如果预期为“1”的任何位为“0”，则阅读器报告该组中的丢失标签事件，并立即终止对该组的检测，并转到下一组检测。如果一个组中没有报告丢失标签事件，则可以认为该组中丢失标签的数量小于阈值。

6.4 性能分析

​ 这里我们使用TAEMD来表示AEMD协议的检测时间。显然，AEMD协议的检测时间由两部分组成，即，阅读器的询问时间和标签响应时间。对于任意群g（1≤ g≤ G） ，阅读器需要广播组ID和子组索引来查询所有标签，这将导致 N g 96 ⋅ t t a g \frac{N_g}{96}·t_{tag} 96Ng​​⋅ttag​。然后，所有组TB AEMD的广播时间可以导出为
T A E M D B = ∑ g = 1 G N g 96 ⋅ t t a g ( 13 ) T^B_{AEMD}=\sum^G_{g=1}\frac{N_g}{96}·t_{tag} \qquad\qquad(13) TAEMDB​=g=1∑G​96Ng​​⋅ttag​(13)
​ 在接收到组ID和子组索引后，位于该子组中的每个标记使用标记槽将96位标记序列发送给读取器。然后，一组的响应时间可获得为Ng / 96,·ttag和所有组的总响应时间TR AEMD可导出为
T A E M D R = ∑ g = 1 G N g 96 ⋅ t t a g ( 14 ) T^R_{AEMD}=\sum^G_{g=1}\frac{N_g}{96}·t_{tag} \qquad\qquad(14) TAEMDR​=g=1∑G​96Ng​​⋅ttag​(14)
​ 然后，AEMD协议的总检测时间可以很容易地推导出来
T A E M D = T A E M D B + T A E M D R = ∑ g = 1 G ( N g 48 ) ⋅ t t a g ( 15 ) T_{AEMD}=T^B_{AEMD}+T^R_{AEMD}=\sum^G_{g=1}(\frac{N_g}{48})·t_tag \qquad\qquad (15) TAEMD​=TAEMDB​+TAEMDR​=g=1∑G​(48Ng​​)⋅tt​ag(15)
​ 此外，AEMD协议的检测可靠性可以接近100%，因为每个标签都有一个唯一的certificationmark，它是基于组ID、子组索引和标签序列的组合。

7 性能评估

​ 在本节中，根据检测时间和实际检测可靠性这两个指标来评估所提出协议的性能。检测时间表示执行所有组检测时的总时间消耗，以秒为单位。然而，实际检测可靠性表示检测到缺失标签事件时的检测次数与每组总检测次数的比率。然后，绩效评估将根据这两个标准进行扩展。此外，本文还实现了在[27]中性能最好的GAB检测和SMTD+CC[10]进行比较。

7.1 检测时间

7.1.1 具有不同可靠性要求的标签总数的影响

​ 图5描述了具有不同可靠性要求的系统中标签总数的影响。这里将系统中的标签总数设置为 10 个不同的值，即 42 500 + (i − 1) × 5000(1 ≤ i ≤ 10)，每组的标签数量不同，设置为 2000 + (i - 1) × 500 + (g - 1) × 500(1 ≤ g ≤ 10)，其中 i 表示值的顺序，g 表示组索引。如图5所示，在不同的可靠性要求下，我们提出的三种协议比GAB detect和SMTD+CC具有更好的检测效率，并且效率提高显著。一个关键原因是所提出的协议利用标签时隙来代替短时隙进行响应。此外，在多组多区域RFID系统中采用GAB检测，部署多个读卡器，工作量大，耗时长。由于每个组标签的总体大小不同，在SMTD+CC中同时检测多个组必然会导致每个组的效率低于最佳水平。此外，AEMD协议的性能优于AMD和EMD协议，因为我们在AEMD协议的标签内存中为每个标签分配了一个唯一的内置向量。还可以观察到，随着标签总数的增加，所有协议的时间消耗都会增加。

7.1.2 不同阈值下所需检测可靠性的影响

​ 图6显示了所需的检测可靠性对缺失标签数量的不同阈值的检测时间的影响。在这里，每个组中的标签数量是不同的，而丢失标签的阈值是相同的。所需的检测可靠性设置为0.72至0.99，间隔为0.03。仿真结果表明，在这种情况下，所提出的三种协议仍然显著优于GAB检测和SMTD+CC，并且随着所需检测可靠性的增加，所有协议的时间开销都会增加。

7.1.3 丢失标签数量的影响

​ 图7示出了丢失标签的数量对具有不同所需可靠性的检测时间的影响。这里，每个组中的阈值设置为M=1，每个组中缺失的标签数分别为1到10。可以看出，最大的区别是，三种协议的时间消耗随着丢失标签数量的增加而减少，而GAB检测和SMTD+CC的时间消耗几乎保持不变。这是因为GAB detect需要收集系统中的所有标签响应来实现检测，而当检测到缺失标签事件时，提议的协议将立即终止。在SMTD+CC中，批检测往往依赖于最慢的组。需要注意的是，当缺失标签的数量较大时，EMD协议的时间效率优于AEMD协议。

7.2 实际检测可靠性

7.2.1 标签总数对实际检测可靠性的影响

​ 图8描述了所提出的三种协议的实际检测可靠性，GAB检测和SMTD+CC具有不同的检测可靠性要求。这里，每个组标签群体是不同的，并且每个组所需的检测可靠性是相同的。结果表明，这五种协议都能完全满足所需的检测可靠性。此外，AEMD协议的检测可靠性无论要求的检测可靠性如何，都可以达到100%，这是由于预写的内置向量的唯一性造成的。

7.2.2 各组所需检测可靠性的不同影响

​ 图9描述了在具有不同阈值的每组中不同所需检测可靠性的影响。这里需要的检测可靠性在不同的组中设置为 0.72 + (g − 1) × 0.03(1 ≤ g ≤ 10)，其中 g 是组索引，并且每个组的标签种群是相同的。 可以观察到，这五种协议都可以完全满足每组所需的检测可靠性。 仿真结果证明了所提出协议的可靠性。 同样，AEMD 协议仍然具有最高的可靠性。

8结论

​ 本文提出了多组丢失标签检测问题。然后，要求在最短时间内检测各组中的丢失标签事件。为此，本文提出了三个协议。首先，设计了AMD协议，该协议充分利用预期的单时隙来检测每个组丢失的标签。然后，设计了EMD协议，与AMD协议相比，EMD协议避免了预期帧向量的广播，进一步提高了检测效率。最后，设计了AEMD协议，通过在标签存储器中写入预定义的向量，实现了高效、准确的检测。然后，优化参数以最大限度地提高检测效率，并进行了大量仿真，仿真结果证明了所提出协议的有效性。