Missing Tag Identification in COTS RFID Systems: Bridging the Gap between Theory and Practice 翻译

名称：在COTS RFID系统中，丢失标签识别：弥补理论和实际的鸿沟

来源：IEEE TRANSACTIONS ON MOBILE COMPUTING

地址：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8585054

翻译

1 摘要和介绍

2 系统模型和问题描述

3 P2M : Point-To-MultiPoint Missing Tag Identification

​ 在本节中，我们将介绍第一个与Gen2兼容的协议，点对多点Q-query及其在识别缺失标签中的应用，然后展示参数配置和时间成本计算。

3.1 Point-to-Multipoint Q-Query

​ Gen2标准规定了阅读器如何查询标签。首先，阅读器发送一个查询命令来启动查询。此命令包含反向散射链路频率（BLF）、标签到阅读器的编码方法和用于指定此查询轮中时隙数的Q参数。通过参数Q，每个标签能够通过选择0-2^Q -1 中的随机值来确定其响应时隙，时隙计数器=此值。如果该计数器等于0，则标签立即回复16位随机数（RN16）；否则应保持沉默。当从标签接收到RN16时，阅读器发送包含解码的RN16的ACK以确认该标签。如果标签确认阅读器对标签RN16的正确性，则标签将其EPC反向散射到阅读器。随后，阅读器发出QueryRep命令标签减少其时隙计数器，计数器等于0的标签用另一个RN16回复，表示新时隙的开始。图1示出了Q查询过程，并显示了两个连续命令（如T1、T2和T3）之间存在等待时间。

​ 由于阅读器可以通过Q查询收集其覆盖范围内存在的标签的所有EPC，因此它将收集的EPC与数据库中记录的EPC进行比较。如果收集的EPC集合中不存在一些记录的EPC，则这些标签丢失，因此可以由阅读器识别。这种比较是在Q-query结束时进行的。P2M优于现有的工作，因为它们需要从COTS阅读器无法获取的所有时隙状态的知识。P2M中的主要问题是何时应该终止Q查询。

3.2 编码方法

​ 对低成本、小尺寸和无电池标签的追求严重限制了它们的计算和硬件能力。因此，以一种极其简单和健壮的方式对数据进行编码和解码是非常重要和必要的。实际上，Reader-to-rag的符号是振幅调制脉冲间隔编码（PIE）符号，模拟比较器足以对其进行解码。如图 2 所示，PIE 中的符号‘0’包含两个长度相同的区间，即开机和关机（PW：脉冲宽度）。Tari（A类参考区间）是data-0的持续时间，而data-1的持续时间是data-0的x倍，x∈[0.5,1]。Tari值可设置为6.25、12.5或25 μs，对应于160、80和40 kbps的速率。与轻量级标签不同，阅读器具有很强的解码能力。Gen2标准规定了tag-to-reader链接的四种编码方法：FM0、M2（Miller2）、M4（Miller4）和M8（Miller8）。数据速率取决于BLF和使用的编码方法。例如，如果BLF为320 kHz，则FM0、M2、M4和M8的数据速率分别为320/1、320/2=160、320/4=80、320/8=40 kbps。

3.3 参数Q的配置

​ 从Q-query的描述中，我们可以观察到它本质上是一个随机访问过程，标签在询问开始时随机设置其各自的计数器。阅读器无法预测标签选取的值。考虑任意时隙i，将有三种状态：

• 如果只有一个标签应答，即该标签唯一地选择值i，则它是一个单时隙；
• 如果有多个标签应答，即这些标签选取的值i，则为冲突时隙；
• 如果没有标签应答，即没有标签选择值i，则为空时隙。

​ 我们在图1中进行说明，其中一个标签在第一个时隙中应答，然后两个标签和无标签分别在第二和第三个时隙中应答。

​ 在这些状态中，只有单时隙对EPC收集有用，而碰撞和空时隙则无用，因此自然优化标准是以高概率确保询问中存在n个单时隙，这意味着不会发生碰撞。从技术上讲，Q查询过程可以表述为经典的Ball-into-Bins（球放到桶中）问题。具体来说，n个标签是球和2^Q的值（或插槽）是箱子。为了避免高概率碰撞，需要将2^Q设置为f(n^2)。通过这个理论结果的指导，我们将Q设置为2logn，其中log表示以2为底的对数。在这种配置下，Q-query持续n^2时隙。

​ 通过这种设置，我们的点对多点协议就足以知道单时隙，这非常适合今天的COTS设备。相比之下，我们注意到现有的工作要求阅读器报告空插槽，这在当前的COTS设备中是不受支持的。

3.4 循环持续时间的计算

​ 如图1所示，三种类型的时隙在其时隙持续时间上不同。因此，询问持续时间计算的第一步是计算每种类型中的时隙数。回想我们设置Q=2 log n，以确保没有冲突，并且这有m个丢失标签，那么，在询问中将有n-m个单时隙和n^2-n+m个空时隙，因此，关键是计算单时隙和空时隙的大小。为此，我们进一步放大图1中的每个时隙，并获得以下观察结果：

• 单时隙大小：单时隙由RN16、ACK、EPC以及命令间时间T1和T2组成。因此可以计算一个单时隙的大小为 A C K ⋅ T a r i + R N 16 + E P C B L F / j + 2 ( T 1 + T 2 ) ACK·Tari+\frac{RN16+EPC}{BLF/j}+2(T_1+T_2) ACK⋅Tari+BLF/jRN16+EPC​+2(T1​+T2​)，其中j∈{1,2,3,4}表示不同的tag-to-reader编码方式。
• 空时隙大小：一个空时隙包含两个命令间隔T1和T3，因此其长度等于T1+T3。
• 时隙间时间：查询开始时有一个查询命令，任意两个连续时隙之间有一个QueryRep，所以整个查询的总时隙间时间应该是(Query + (n^2-1) · QueryRep)·Tari

​ 根据这些观察结果，现在我们能够确定P2M的总体询问时间为
( n − m ) ⋅ ( A C K ⋅ T a r i + R N 16 + E P C B L F / j + 2 ( T 1 + T 2 ) ) + ( Q u e r y + ( n 2 − 1 ) ⋅ Q u e r y R e p ) ⋅ T a r i + ( n 2 − n + m ) ( T 1 + T 3 ) (n-m)·(ACK·Tari+\frac{RN16+EPC}{BLF/j} + 2(T_1+T_2))+\\(Query+(n^2-1)·QueryRep)·Tari+(n^2-n+m)(T_1+T_3) (n−m)⋅(ACK⋅Tari+BLF/jRN16+EPC​+2(T1​+T2​))+(Query+(n2−1)⋅QueryRep)⋅Tari+(n2−n+m)(T1​+T3​)

4 P2P : Point-To-Point Missing Tag Identifucation

​ 我们前面提出的第一个命题遵循点对多点范式。由于其随机性，多个标签可能同时回复RN16，导致在阅读器端解码失败。处理标签碰撞的步骤，P2M将Q设置为2 log n，这会导致大量的空时隙和浪费时间。为了在提高时间效率的同时避免碰撞事件，我们提出了一种点对点的P2P模式，它能够在每个时隙中对标签进行奇点化。如图3所示，阅读器不能控制P2M中标签的响应时隙，从而使其遭受碰撞。相反，P2P可以分配应答顺序并避免碰撞，例如标签1-5按顺序在时隙1到5中应答。在接下来的内容中，我们首先阐述丢失标签识别过程，然后演示如何构建有效的bitmask。

4.1 Point-to-Point Selective Query

​ Gen2标准提供了一个Select命令，允许阅读器根据用户定义的标准有选择地读取标签的子集。如图4所示，选择性查询包括两个阶段：标签过滤和标签查询。首先，阅读器发出一个指定bitmask的Select，并且将由标签执行的操作。在接收Select时，每个标签都会检查reader-to-tagbitmask是否匹配。如果是，它将断言其标志变量SL；否则，它将取消SL。通过仔细设计bitmask，我们可以确保只有一个标签可以通过bitmask比较，这将在稍后介绍。然后阅读器进一步发送一个Query，该Query指定带有确定的SL的标签来应答。由于在P2P中只有一个标签满足要求，因此该标签是唯一一个使用其RN16响应查询的标签。随后，阅读器使用解码的RN16发送ACK，并准备接收该标签的EPC。当此查询完成时，阅读器将重复上述过程以逐个读取标签。

​ P2P的理想特性是它能够指定一个单独的标签来回复。如果此标签没有响应，则阅读器将知道其不存在。因此，P2P可以在n次选择性查询后识别所有m个丢失的标签。此外，P2P还可以在最多n - m个选择性查询中检测缺失的标签。

4.2 计算总体P2P执行时间

​ 如图1和图4所示，当前标签上的P2P选择性查询的长度包含Select、T4、查询和长度等于P2M中长度的单时隙。如果查询到缺少的标签，则此查询持续时间的组和几乎与之前的相同，只是时隙持续时间变为空时隙大小，而不是单插槽大小。因此，回想第3.4节，我们知道这需要P2P时间是 ( S e l e c t + Q u e r y + A C K ) ⋅ T a r i + R N 16 + E P C B L F / j + T 4 + 2 ( T 1 + T 2 ) (Select+Query+ACK)·Tari+\frac{RN16+EPC}{BLF/j}+T_4+2(T_1+T_2) (Select+Query+ACK)⋅Tari+BLF/jRN16+EPC​+T4​+2(T1​+T2​)，以实现对当前标签的选择性查询。其中j∈{1,2,3,4}表示不同的tag-to-reader编码方式。因此，P2P的总体时间成本是
( n − m ) ⋅ ( ( S e l e c t + Q u e r y + A C K ) ⋅ T a r i + R N 16 + E P C B L F / j + T 4 + 2 ( T 1 + T 2 ) ) + m ( ( Q u e r y + S e l e c t ) ⋅ T a r i + T 4 + T 1 + T 3 ) (n-m)·((Select+Query+ACK)·Tari+\frac{RN16+EPC}{BLF/j}+T_4+2(T_1+T_2))+\\m((Query+Select)·Tari+T_4+T_1+T_3) (n−m)⋅((Select+Query+ACK)⋅Tari+BLF/jRN16+EPC​+T4​+2(T1​+T2​))+m((Query+Select)⋅Tari+T4​+T1​+T3​)
​ 在描述了P2P的过程之后，我们接下来将解释如何在我们的丢失标签识别协议中设计P2P中的关键功能Select。

4.3 Select Function

​ Select命令中有六个必填字段，如图5所示，我们将介绍与我们的设计相关的五个字段。

1. Action指定了表1中列出的八种类型的标签行为。在我们的场景中，我们使用第一种类型，即Action = 00 0 2 000_2 0002​来指定标签操作。具体来说，与接收到的bitmask匹配的标签（称为匹配标签）将断言SL，而其他标签（称为不匹配标签）将取消断言SL。
2. MemBank表示标签将搜索哪个标签内存模型，以与接收到的bitmask进行比较。MemBank= 0 0 2 00_2 002​是保留内存，用于存储与标签相关的密码。如果MemBank=01_2；10_2; 11_2然后，标签在存储标签EPC的EPC内存库、指定永久标签和制造商特定信息的TID内存库、可使用用户定义数据写入的用户内存库 中搜索bitmask。本文中我们采用了EPC内存库，即MemBank = 01_2。
3. Pointer记录所选 MemBank 中的起始位位置以进行bitmask比较。
4. Length指定bitmask长度。如果 MemBank = M，Pointer = p 和 Length = l，那么标签将bitmask与其内存模型 M 中从第 p 位到第 (p+l-1) 位开始的位进行比较。
5. Mask 记录位字符串的bitmask内容。 标签将其与其内存中的指定位字符串进行比较。

​ 从上面的描述中，我们观察到MemBank、Pointer和Length的组合指定了标签需要在其内存中搜索的位字符串的位置，而Mask记录了标签将与位字符串进行比较的bitmask内容。因此，我们用BM来表示一个bitmask，即 B M = ( M , p , l , M a s k ) BM=(M,p,l,Mask) BM=(M,p,l,Mask)。

​ 在P2P中，我们通过设置MemBank=01_2从标签EPC构建bitmask。EPC是唯一的，并且已经存储在标签中，因此P2P不需要向标签写入新数据。我们通过一个例子来进一步说明它的应用。如图6所示，阅读器发送将EPC 1010指定为bitmask的Select。收到此命令后，每个标签检查其EPC中从第一位到第四位的位字符串，并将其与Mask中接收到的位字符串进行比较。因为只有灰色标签符合条件，所以它将断言其SL并等待传入的查询，而其他标签将保持沉默。我们在图7中展示了这个例子的Java实现。由于标签EPC从内存中的第32位开始，因此实现中的Pointer设置为0x20。

​ 到目前为止，我们已经介绍了P2P的框架和Select功能，剩下的最后一个问题是如何有效地配置bitmask，即Mask。

4.4 bitmask选择

​ 回想一下，在P2P中，阅读器试图在每个插槽中将标签与其他标签区分开来。为此，一种直接的方法是将Mask设置为标签EPC，如图6中的示例所示。虽然这样的配置是有效的，但效率很低。回想图5，选择命令的长度为45位，不包括Mask。如果我们在Mask中使用96位EPC，它是其他字段的两倍以上，占整个Select的三分之二。如果我们能使用更短的Mask，效率就会提高。例如，将图 6 中的 Select 重新配置为 Pointer = 00000000_2, Length = 00000001_2, Mask = 1_2 当标签将其 EPC 的第一位与 Mask 进行比较时，我们可以使灰色标签成为唯一满足要求的标签为 1bit Mask而不是前 4 位。

​ 受上述示例的启发，我们开发了使用标签EPC的一部分而不是整个来构建bitmask的潜力。虽然96 ~ 496位EPC可以由ImpinJ Monza Tag支持，但本文中我们使用96位EPC，但我们的工作可以直接用于EPC长度超过96位的场景。我们知道96-bits的字符串可以唯一确定 2 96 = 7.9 ∗ 1 0 28 2^{96} = 7.9 * 10^{28} 296=7.9∗1028。由于一个系统中标签的数量通常比这个数量小得多，因此与总共2^96个EPC相比，Gen2系统中当前的EPC是稀疏的。我们可以利用这种稀疏性来设计更有效的bitmask选择方法。注意，对于EPC较长的标签，例如496位EPC，其效率更为显著。（因为2^496的基数更大，系统中的EPC更稀疏）。

4.4.1 一种确定性bitmask选择算法

​ 我们首先设计了一个确定性算法，其核心思想是只使用标签EPC的一部分作为位掩码，以便只有一个标签匹配。字段Length和Pointer指定位字符串在标签内存中的长度和起始位置，将与接收到的bitmask进行比较，我们分别用l和p表示它们。由于我们从一个a log n - bits的EPC中选择一个长为l的连续bits，l可以等于一个1到a log n中的数，并且EPC中有a log n - l + 1个段，相应的p=0：a log n - l。例如，如果图6中的l = 2，则灰色标签从左到右有三段，即10、01、10。因此，我们可以通过下面的三维搜索（算法 1）在每个时隙中找到一个最优的bitmask，即可以在一个时隙中使标签奇异的最短位掩码。在算法中，x(p, l)表示在标签x的EPC中从第p位到第p + l -1位的字符串； a = E P C l o g n a=\frac{EPC}{logn} a=lognEPC​。该算法的核心步骤是如下所述：输出指定Pointer、Length和Mask的最短bitmask。

• 首先，让l=1，我们从n个标签中任意选择一个。
• 第二，给定l和这个标签EPC，我们将它的第一个l位段（即最左侧）与其他n - 1标签EPC进行比较。
• 如果我们发现该段是唯一的，它可以用作bitmask和Pointer=00000000_2，则搜索过程将终止；否则，该标签在时间上被视为无用，我们从n - 1标签中选择另一个标签，将其第一个l位段与其他n - 1标签EPC中的l位段进行比较。此步骤将一直运行，直到找到唯一的l位段或任何两个标签都相互比较过为止。
• 第三，如果在第二步中找不到唯一的l位段，我们将用第二个l位段重复第二步中的操作。如果这次成功，则将该段分配给Mask，Pointer=00000001_2；否则我们设置l=l+1。如果找到bitmask或l=a log n，则第三步停止。如果找到一个bitmask，也就是说，我们可以有选择地查询与该bitmask匹配的标签，然后算法继续运行以查找另一个标签的bitmask。

​ 根据以上描述，我们可以将算法中的三个维度解释为：

• 比较任意两个标签；
• 将Pointer p从0滑动 a log n - l；
• Incrementing l from 1 to a log n.

​ 我们的算法可以确定地找到一个最佳位掩码。现在我们分析它的计算复杂性。如前所述，我们算法的复杂性可分解为三个部分：1）O(n^2)为每个(p,l)的操作比较；2）O(log n ^ 2) 表示（p, l）的合并；3）该算法需要为所有n个标签找到一个bitmaks。总体计算复杂度总计为 O ( n 3 ( l o g n ) 2 ) O(n^3(logn)^2) O(n3(logn)2)。

4.4.2 一种概率bitmask选择算法

​ 接下来，我们设计了一种概率bitmask选择算法，以确保具有所需成功概率的唯一bitmask。与确定性算法相比，概率算法有三个优点：

• 降低了复杂性。在最坏的情况下，概率方案将复杂性从O(n³)降低到O(n²)。在实践中，收益可能更为显著。特别是对于计算能力有限的手持移动阅读器，需要较低的复杂度。
• 可调精度。作为期望的特性，可以调整概率算法的精度，以在精度、计算和通信开销之间取得平衡。
• 更好的适用性。即使数据库中没有记录新的标签，概率算法也可用于识别丢失的标签，但确定性算法无法执行此任务。这将在本节末尾讨论。

​ 在概率算法中，我们将标签EPC划分为 ∣ E P C ∣ l \frac{|EPC|}{l} l∣EPC∣​非重叠段，即 a l o g n l \frac{a logn}{l} lalogn​段。例如：如果图6中的l=2假设EPC为四位长，则黑色标签0111从左到右有两个这样的段，即01和11。该方法在算法2中正式说明，其操作如下：

• 首先，我们设置l和另一个参数z，z代表该算法的执行轮数。稍后将介绍如何配置参数。
• 其次，我们任意选择一个标记并选择其EPC的第一个（最左侧）段。然后，我们将该片段与其他n - 1标签进行比较。如果该段是唯一的，我们将其用作bitmask并设置Pointer = 00000000_2，则算法停止；否则，我们选择第二段，并重复上述操作。当找到唯一段或执行的轮数超过z时，算法终止。

​ 显然，概率方法的复杂性是O(n·z)，其中 z ≤ a l o g n l z≤\frac{alogn}{l} z≤lalogn​，为了在P2P中找到所有标签的bitmask，该方法需要运行n次，因此总体复杂度为 O ( n 2 ⋅ l o g n ) O(n^2·logn) O(n2⋅logn)。

​ 接下来，我们将分析参数配置。由于EPC中的每个位实际上是随机生成的，因此 a l o g n l \frac{a logn}{l} lalogn​非重叠段的字符串是相互独立的。如果前k - 1轮失败，算法将运行k轮，其中k ≤ z，因此执行轮数的概率分布（定义为k）可以表示为几何分布。

​ 考虑一个任意的轮次，为所有n个标签找到唯一的bitmask等于所选的l位段彼此不同的事件。这一事件发生的概率是 e − n 2 2 l + 1 e^{-\frac{n^2}{2^{l+1}}} e−2l+1n2​，因此，我们有
P r ( K = k ) = ( 1 − e − n 2 2 l + 1 ) ⋅ e − n 2 2 l + 1 P_r(K=k)=(1-e^{-\frac{n^2}{2^{l+1}}})·e^{-\frac{n^2}{2^{l+1}}} Pr​(K=k)=(1−e−2l+1n2​)⋅e−2l+1n2​
​ 因此，z轮后的成功概率（定义为Ps）可计算为
P s = ∑ k = 1 z ( 1 − e − n 2 2 l + 1 ) ⋅ e − n 2 2 l + 1 = 1 − ( 1 − e − n 2 2 l + 1 ) z P_s=\sum_{k=1}^z(1-e^{-\frac{n^2}{2^{l+1}}})·e^{-\frac{n^2}{2^{l+1}}}=1-(1-e^{-\frac{n^2}{2^{l+1}}})^z Ps​=k=1∑z​(1−e−2l+1n2​)⋅e−2l+1n2​=1−(1−e−2l+1n2​)z
​ 用a表示为n个标签找到bitmask所需的成功概率，我们可以得到l和z的关系：
P s = a = = > l o g ( 1 − a ) = z l o g ( 1 − e − n 2 2 l + 1 ) ( 1 ) P_s = a ==>log(1-a)=zlog(1-e^{-\frac{n^2}{2^{l+1}}})\qquad\qquad(1) Ps​=a==>log(1−a)=zlog(1−e−2l+1n2​)(1)
​ 要求解这个方程，我们可以首先指定l或z的值，然后导出另一个。Ps随l和z单调增加，因此选择l和z表示计算复杂度和通信开销之间的折衷。例如，设z=1，当l达到其最大值 l o g ( n 2 − l n a ) log(\frac{n^2}{-lna}) log(−lnan2​)复杂性将降低到O(1)。如果设a=0.99、n=2¹⁰,则 l o g ( n 2 − l n a ) − 1 ≈ 26 log(\frac{n^2}{-lna})-1≈26 log(−lnan2​)−1≈26。相反，如果让z= 96 l \frac{96}{l} l96​在相同的要求下，我们有l=20，然和z=4。请注意，l的值不能超过标签EPC的长度。

4.5 用新标签识别丢失的标签

​ 在这一部分中，我们将讨论是否可以使用P2P来识别场景中缺少的标签，因为新标签的出现并没有记录在数据库中。为此，我们研究了两种情况：使用确定性算法的P2P和使用概率算法的P2P。

​ 在第一种情况下，P2P不能用于这种共存场景，因为确定性算法必须搜索数据库中标签的所有epc，以找到唯一的bitmask，而新标签的bitmask不会被记录。因此，一些新标签也可能与选定的位掩码匹配，与已知标签的响应发生冲突，从而导致P2P失败。

​ 在第二种情况下，如果可以估计新标签的数量或者阅读器知道新标签填充的范围，则P2P可以适用于共存场景。假设新标签填充的上界为u，给定所需的a，我们可以根据以下等式计算所需的bitmask长度l和执行轮数，以使识别概率至少为a
l o g ( 1 − a ) = z l o g ( 1 − e ( n + u ) 2 2 l + 1 ) log(1-a)=zlog(1-e^{\frac{(n+u)^2}{2^{l+1}}}) log(1−a)=zlog(1−e2l+1(n+u)2​)
​ 注意，当标签EPC为96位长时，如果l=96，P2P可以确定地识别所有丢失的标签。

5 实验

5.1 实施设置

​ COTS Gen2设备。在我们的实现中，我们使用一个ImpinJ R420阅读器和20个ImpinJ Monza-4 UHF标签。这些设备完全按照Gen2标准编译。丢失标签识别程序是用ImpinJ SDK v.1.28.0.1. Java编写的。特别是，ImpinJ R420阅读器支持Q查询和选择性查询。ImpinJ Monza-4标签具有96位EPC。

​ Parameters。阅读器的传输功率设置为30 dbm，其接收灵敏度为 -70 dbm。我们实现了三种tag-to-reader的编码方法：M2、M4、M8。由于ImpinJ阅读器可以支持三种组合，我们将tag-to-reader的链接速率从M2的320 kbps更改为M4的68.5 kbps，到M8的21.33 kbps。在PMP中，我们设置Q=2 logn，其中n是Gen2系统中的标签数量，分别设置为5、10和20。我们将调查报告确定性和概率性bitmask选择方法的正确性，但将前者用于P2P的实现，而后者将用于系统可扩展的后续实验。

5.2 实施结果

​ 我们评估了所提出的丢失标签识别协议，即P2M和P2P的性能。我们想指出的是，本文的重点是相同设置下的性能比较，而不是最大化吞吐量。

​ 协议调查。在进行正式比较之前，我们首先介绍确定性bitmask选择方法的工作原理。我们从n=5个标签开始，其EPC列在表2的第一列中，即标签x1-x5。运行算法1，我们可以首先设置bitmask BM=(000_2,6,1,0_2)查询标签x3，然后使用BM=(000_2,9,1,0_2)，BM=(000_2,11,1,0_2)，BM=(000_2,37,1,0_2)，BM=(000_2,39,1,0_2)依次查询标签x4、x1、x2、x5。也就是说，在这种情况下，P2P使用一位bitmask就足够了。为了说明，我们以为例，其中仅搜索标签EPC的前两个字符，如图8所示。将此示例与之前的示例进行比较，我们可以观察到在EPCW中搜索更多位置将产生更短的位掩码。

​ 我们进一步执行算法1，为分别对应于表2中前两列和所有标签的n=10和=20的情况构建bitmask。n=5，10，20的结果由表3、表4和表5分别显示。请注意，我们在P2P中使用MemBank=000_2，我们只列出(p,l,Mask)为便于说明。

​ 协议比较。从这一部分开始，我们开始使用确定性bitmask选择方法比较P2M和P2P的性能，在识别所有缺失标签和检测ImpinJ阅读器支持的三种不同tag-to-reader编码方法（即M2、M4和M8）下的第一个缺失标签所花费的执行时间。

​ 首先，我们研究了标签总体数量n对P2M和P2P性能的影响。为此，我们修正了缺失标签的数量m=0，同时将n从5增加到10，再增加到20。如图9所示，P2P可以在明显少于P2M的时间内查询所有标签，并且性能增益随着系统中标签数量的增加而飙升。同时，P2M的执行时间比P2P有更大的增长。例如，在图9a中，当标签填充为5时，P2P比P2M好1.5倍。当有20个标签时，这个数字增加到5倍。P2P的性能增益来自点对点设计，因为它能够在每个时隙中成功读取标签，但P2M平均需要O(n)个时隙才能访问标签。

​ 其次，我们将研究P2M和P2P在系统中不同的缺失标签数量下的性能。为此，我们固定了总标签数n=20，同时将丢失标签数m更改为m=4，6，8，12。实验结果如图10所示。从这些结果中，我们可以观察到以下现象：

• 整体表现：P2P显著优于P2M。具体而言，如图10a所示，PMP的识别成本在0.56 s和1.49 s之间，那是P2P的2.8倍到5.4倍。在另一种tag-to-reader的速率中，P2P比P2M至少获得3.3倍的性能增益。这主要是由于点对点查询范式按顺序读取标签，而P2M需要更多的时间来处理碰撞。
• 缺失标签的影响：随着缺失标签数量的增加，P2M的执行时间比P2P显著减少。例如，在图10a中，P2M的减少为62.2%，是P2P的2.4倍。这可以解释为：丢失标签的增加减少了P2M中的标签间的碰撞，但由于P2P采用点对点查询，因此对P2P的影响较小。

​ 在与上述相同的设置下，我们进一步比较了P2M和P2P的缺失标签检测时间，即查找第一个缺失标签所花费的时间。从图11可以观察到，P2P能够在比P2M更短的时间内检测到第一丢失的标签。特别是，当有12个丢失的标签时，使用M2的P2M查找第一个丢失的标签所需的时间几乎是P2P的7倍。使用M4和M8时，它们之间的性能差距达到8以上。看图10和11，我们还可以发现，P2P的检测时间显著缩短，特别是在存在更多缺失标签的情况下，而P2M的检测时间没有改变。这种差异是由于P2P和P2M的性质造成的，前者可以了解每个时隙中是否存在标签，但后者在整个帧执行之前无法知道标签状态。也就是说，在最坏的情况下，P2P可以在探测n - m个标记后找到丢失的标签，而P2M则需要查询所有n个标签。

​ 概率bitmask选择方法的正确性：在使用20个ImpinJ标签实现了P2M和P2P之后，我们开始确认本部分中概率bitmask选择方法的正确性。再次查看表2，其中列出了20个标签EPC，我们首先检查算法2是否适用于5个标签场景。为了评估概率方法的可靠性，我们设置α=0.99和0.999，并将算法2运行 1 1 − α \frac{1}{1-α} 1−α1​次。每次我们从20个标签EPC中随机选择5个。如果标签之间的bitmask冲突出现不止一次，则我们认为算法2失败。我们在表6中记录了满足所需概率的l和z的组合。结果表明，随着α的增加，算法2需要使用更长的bitmask或运行更长的轮次，这与分析结果是一致的。此外，给定a，l或z的增加可以产生另一个较小的值，从而确认通信开销和计算复杂性之间的折衷。

​ 为了评估系统规模的影响，我们将标签数量从50个增加到300个，步长为50，并随机生成标签EPC。从结果中，我们观察到，随着标签数量的增加，算法2可以达到所需的概率a。由于最大bitmask长度可以通过z=1从（1）直接计算，在表7中，我们只列出了使算法2成功的最小bitmask长度和执行轮数的组合。我们可以发现，当系统扩展或所需的成功概率变得更高时，bitmask长度或执行轮数都会增加，这与分析结果相对应。

​ 大系统下的性能评估。我们进一步展示了所提出的协议的时间效率是如何随着系统规模的扩大而变化的。为此，我们按照ImpinJ阅读器的Gen2标准和规范设置参数如下：Tari=12:5ms，BLF=640 kHz。我们分别使用FM0和M4作为tag-to-reader链接的编码方法。因此，由r定义的数据速率是1/BLF和4/BLF。持续时间为T1 = T3 = max(2.75Tari, 10r)、T2=3r 和 T4=5.4r。当所需bitmask长度l为27、29、31、33、36且概率算法z的执行轮等于1时，我们将整个标签的数量从500变为10000，并设置a=0.999。此外，将r定义为缺失标签数量与总标签数量的比率，我们将其设置为0.3和0.6。我们在表8和表9中列出了结果。

​ 我们可以观察到，P2M的执行时间的增量遵循总体标签数量的平方模式。这种模式在P2P中是线性的。因此，P2P比P2M具有更高的时间效率。我们还可以发现，丢失标签的比率r对P2P的影响比P2M更大。这是因为在P2P中，r的增加导致成功时隙的减少和空时隙的增加。空时隙比成功时隙短。但由于P2M中r的增加导致空时隙的变化，其数量级为O(n)，明显小于空插槽的原始数量，即O(n²)。

6 相关工作

​ 在本节中，我们简要总结了现有的丢失标签监控协议，这些协议可分为两类：概率检测和确定性识别。

​ 概率丢失标签检测。这种类型的协议以预定义的概率检测丢失的标签事件。Tan等人发起了丢失标签检测的研究，并在[22]中提出了一种称为TRP的解决方案。为了检测丢失的标签事件，TRP首先通过使用哈希函数来预测标签的响应时隙来构建虚拟位图，并将其与从总体中的标签响应测量的实际时隙状态进行比较。如果预期的忙（单例或冲突）插槽结果为空，则与此插槽对应的标签被视为不存在。因为当丢失标签的数量很少时，碰撞时隙只有丢少标记的概率很低，所以碰撞时隙不如单时隙有用。鉴于单重时隙的重要性，后续工作[23]，[24]采用多个种子将空时隙和冲突时隙调整为单重时隙，这增加了检测概率，从而提高了时间效率。随后，未知标签的存在将使空时隙成为映射为繁忙的丢失标签，并将干扰检测。为了处理干扰，工作[25]和Yu等人[26]分别在未知标签大小的检测中扩展帧大小，并从已知标签设计Bloom过滤器以抑制未知标签。考虑一种不同的应用场景，Yu等人[27]设计了几种基于Bloom Filter的方法来检测RFID系统中的丢失标签，其中多类别标签分布在多个区域中。最近，Yang等人[28]开发了一个标签上的散列函数，需要将离线计算的散列值写入所有标签，并说明如何使用该函数以概率方式检测丢失的标签。

​ 确定性丢失标签识别。确定性协议是为了准确地识别哪些标签不存在。Li等人在[29]中开发了一系列识别协议，分别通过协调2个碰撞时隙和迭代停用已验证存在的标签，逐步降低时间成本。张等人。 在 [30] 中提出了识别协议，该协议存储和比较所有轮次中标签响应的位图，并在所有位图中查找相应位的变化，以确定存在和不存在的标签。Liu等人[31]基本上将[23]中的多种子方法与[29]中基于deactive的方法相结合，以提高识别性能。随后，Liu等人[32]通过协调2-碰撞和3-碰撞时隙以及过滤空的和不可协调的碰撞时隙来进一步增强先前的工作，以提高时间效率。最近，人们利用物理层信息来加速丢失标签的识别。Zheng等人[33]测量每个时隙中信号强度的变化，并使用压缩感知对丢失标签的识别进行建模，从而将时间成本降低到与丢失标签总体相同的数量级。相比之下，Chen等人[34]利用每个时隙中信号强度的变化构造了一个Bloom过滤器，它可以在处理任意数量的丢失标签时实现类似的时间效率。与以前的工作相比，本文的创新之处在于，我们设计了bitmask选择方法，并使用COTS RFID设备进行确定性丢失标签识别，而不需要在标签上使用哈希函数，也不需要将哈希值写入标签。

7 结论

​ 在本文中，我们提出了两个协议，支持使用COTS RFID阅读器和标签的丢失标签识别服务。具体地说，我们首先使用Q-query开发了一个点对多点协议，该协议在模拟帧时隙Aloha范例中运行，用于收集标签EPC。如果收集的EPC集合不包含其EPC，则可以找到缺少的标签。然后，我们设计了一个点对点协议，该协议使用bitmask在每个时隙中指定一个要回复的标签，这样可以避免标签响应碰撞，并提高时间效率。此外，我们还提出了两种位掩码选择方法来构建紧凑的bitmask。所提出的协议在ImpinJ阅读器和标签中实现，广泛的结果表明，它们能够完成丢失标签的识别任务。