3期 谢磊等：RFD数据管理：算法、协议与性能评测 461 型，并证明了其正确性和性能的上界.实验表明，在 标签的标识符ID,每传输一个ID后，阅读器会等 给定精度要求的情况下，该方法明显快于现有其它 待对应的标签返回一个短暂的响应消息，如果接收 方法.此外，为了解决单个标签被多次读取的问题， 到响应，则推断该标签存在于扫描范围内，否则认为 文献[16们提出了一套“复制不敏感”的估算机制来实 该标签丢失，然而，上述方案存在如下弊病：(1)与 现更精确的标签数量统计.文献[17]提出了一个自 时隙ALOHA协议不太兼容；(2)长达96bit的ID 适应的基于划分的估算机制，该机制基于几何分布 传输使得整体扫描时间过长，降低了系统的效率.因 规律让单个标签选择同一帧中的多个时隙进行传 此，研究者们针对上述问题开展了深入的研究，其目 输，使得每个标签有1/2的概率选择第t一1个时 标为基于时隙ALOHA协议设计出一套有效的标 隙，有效解决了单个标签被多次读取的问题.表2对 签轮询机制，尽可能地减少整体扫描时间。 上述研究工作的特点进行了总结和比较， 研究发现，在时隙ALOHA协议的每一轮中， 表2标签数量估算算法的特点总结与比较 处于激活状态的标签会“随机”地在帧中选择一个时 估算算法 与时腺ALOHA 隙进行传输.然而，由于标签的简易性，真正的随机 协议兼容性 估算参考的指标 概率模型 性很难得到实现.事实上，标签的芯片逻辑实现了一 文款[13] 兼容 空时隙与冲突时 二项分布 个“伪随机”的操作：在每一轮中阅读器广播一个随 隙的数目 基于二项分布的 机数r,每个被激活的标签接收到，后随即结合本 文献[14] 兼容 3种时隙的数目 后验概率模型 地的标识符ID进行散列操作，计算出伪随机数s作 文献[15] 兼容 第一个标签回复 的位置 二项分布 为选定的时隙序号，这里s=hash(ID,r)modf,f 文献[16-17] 不兼容 冲突时隙出现的 几何分布 是帧的长度.上述的“伪随机性”意味着，对于任一标 边缘位置 签，一旦阅读器广播的数值？以及帧的长度∫确定 除了对标签数量进行简单估算之外，一些研究 下来，该标签在帧中相应的位置即被确定，这就使得 工作者开始探究如何在RFID系统上实现更为复杂 对标签的有效轮询成为可能.在实施扫描之前，阅读 的数据分析与挖掘机制.文献[18]着力研究面对大 器可以预先根据指定集合内各标签在帧中对应的位 量的RFID标签，如何在不需要读取所有标签具体 置为每个时隙计算出期望的结果：空时隙(0)、单时 信息的前提下快速定位出最热门的标签类别.该文 隙(1)或者冲突时隙(C).对于某一时隙，如果该时 基于分组测试(Group Testing)的理念，提出了有效 隙期望为单时隙但实际无响应，则表明对应于该时 的随机算法来解决上述问题.文献[19]面向流量追 隙的标签丢失；如果该时隙期望为冲突时隙但实际 踪一类的应用问题，针对动态移动的标签集合提出 无响应，则表明对应于该时隙的所有标签丢失.图4 了保障隐私的快速估算机制.该机制能够快速统计 给出了基于时隙ALOHA协议的轮询机制示意图. 在时域(t,t2)内从地点A移动到地点B的标签数 如图所示，在标签A~H中，虚线标识丢失的标签， 目，从而在无需读取确切标签ID信息的前提下有 实线标识存在的标签.当标签E、F以及H丢失时， 效地进行流量追踪。总体而言，目前该方面的研究成 其对应的时隙实际观察到的状态变成空时隙(0)，此 果相对较少，随着RFID数据管理技术以及相关应 时可以判定标签丢失.但对于标签C丢失的情况， 用的进一步拓展，基于RFID的数据分析与挖掘机 由于标签B、D的存在，使得对应时隙实际观察到的 制必将得到更为广泛的关注与深人的研究。 状态仍为冲突时隙(C),未能判断出标签C丢失的 2.3RFID的标签轮询机制 情况，导致假阳性误判(False Positive).上述轮询机 某些RFID应用并不需要获取全部RFID标签 标签A标签B标签C标签D标签E标签F标签G标签H 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失.例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 期望的 状态 0010c00 …c11oo 清点指定的货物，确定是否存在货物丢失.在这种情 况下，假设所有的货物都贴有唯一标识的RFID标 签，能否有效地实现标签的轮询机制成为与此密切 轮询判断 未能判断出标 标签E 相关的问题.最简单直接的方案便是设计一种类似 的结果 签C丢失，假 阳性误判 标签F丢失标签H丢失 于“点名”的机制：阅读器根据清单内容接连地广播 图4基于时隙ALOHA协议的轮询机制示意图3期 谢 磊等 ：RFID数据管理 ：算法 、协议 与性 能评 测 461 型 ，并 证 明 了其 正 确 性 和性 能 的上 界 ．实 验 表 明 ，在 给定精 度 要求 的情 况 下 ，该 方 法 明显 快 于 现有 其 它 方法 ．此外 ，为 了解 决 单 个 标 签 被 多 次读 取 的 问题 ， 文献 [16]提 出了一套 “复 制不 敏感 ”的估 算 机制来 实 现更精确的标签数量统计．文献[17]提出了一个 自 适 应 的基 于划分 的估 算 机 制 ，该 机 制基 于几 何 分 布 规律让单个标签选择 同一 帧中的多个时 隙进行传 输 ，使 得 每 个 标 签 有 1／2的 概 率 选 择 第 一1个 时 隙 ，有 效解 决 了单个 标签 被 多次读 取 的问题 ．表 2对 上 述研 究 工作 的特 点进行 了总结 和 比较． 表 2 标签数量估 算算法的特点总结与 比较 估算算法 与 协 H~ 议兼 A 容 LO 性 HA 估算参考 的指标 概率模型 除 了对标签数量进行简单估算之外 ，一些研究 工作 者 开始探 究 如何 在 RFID 系统 上实 现更 为复 杂 的数 据 分析 与挖 掘机 制 ．文 献 E18]着 力 研 究 面 对 大 量的 RFID标签 ，如何在不需要读取所有标签具体 信 息 的前提 下快 速 定 位 出最 热 门 的标 签 类 别．该 文 基 于分 组测 试 (GroupTesting)的理 念 ，提 出 了有 效 的随机 算法 来解 决 上述 问题 ．文 献 [19]面 向流 量 追 踪 一类 的应 用 问题 ，针 对 动 态 移 动 的标 签 集 合 提 出 了保 障隐私 的快 速 估算 机 制 ．该 机制 能 够 快 速 统 计 在 时域 ( ，tz)内从 地 点 A 移 动到 地 点 B的 标 签 数 目，从而 在无 需 读 取 确 切 标 签 ID 信 息 的 前 提 下 有 效 地进 行 流量追 踪．总体 而言 ，目前 该方 面 的研究 成 果 相对 较少 ，随 着 RFID 数 据 管 理 技 术 以及 相 关 应 用 的进 一步 拓 展 ，基 于 RFID 的数 据 分 析 与 挖 掘 机 制 必将 得 到更为 广泛 的关 注 与深入 的研 究． 2．3 RFID的标签 轮 询机 制 某 些 RFID应 用并 不需 要 获 取 全部 RFID标 签 的标 识 信息 ，仅需 要对 指定 集合 内的标签 进行 轮询 ， 来确 认 标签 的状 态是存 在 或丢 失．例 如 ，对仓 库管 理 应 用而 言 ，出入库 之 前 管 理 员 需要 根 据 货 物 清 单 来 清点指定的货物 ，确定是否存在货物丢失．在这种情 况下 ，假设所有 的货物都贴有唯一标识 的 RFID标 签 ，能否有效地实现标签 的轮询机制成为与此密切 相关 的问题．最简单直接的方案便是设计一种类似 于“点名 ”的机制 ：阅读 器 根 据 清单 内容 接 连 地 广 播 标签 的标 识符 ID，每 传 输 一 个 ID 后 ，阅 读 器会 等 待对 应 的标签 返 回一 个 短 暂 的 响应 消 息．如 果 接 收 到 响应 ，则 推 断该标 签存 在 于扫描 范 围 内，否 则认 为 该标 签丢 失．然 而 ，上 述 方 案 存 在 如 下 弊 病 ：(1)与 时 隙 ALOHA 协议不 太兼 容 ；(2)长达 96bit的 ID 传输使得整体扫描时间过长 ，降低了系统的效率．因 此 ，研究 者 们针 对上 述 问题 开 展 了深 入 的研究 ，其 目 标为基 于 时 隙 ALOHA 协 议 设 计 出一 套 有 效 的 标 签轮 询机 制 ，尽 可 能地减 少整 体扫 描 时间． 研 究 发现 ，在 时 隙 ALOHA 协 议 的 每 一 轮 中 ， 处 于激 活状 态 的标 签会 “随机 ”地在 帧 中选择 一个 时 隙进行 传输 ．然 而 ，由于 标签 的简 易 性 ，真 正 的随机 性 很难 得 到实现 ．事 实上 ，标签 的芯 片逻 辑实 现 了一 个 “伪 随机 ”的操 作 ：在 每 一 轮 中 阅读 器 广 播 一个 随 机数 r，每个 被 激 活 的标 签 接 收 到 r后 随 即结 合 本 地 的标 识 符 ID 进行 散列 操作 ，计算 出伪 随机数 S作 为选定 的时 隙序 号 ，这里 S—hash(ID，r)roodf，f 是 帧 的长度 ．上 述 的“伪 随机性 ”意 味着 ，对于 任一标 签 ，一旦 阅读器 广播 的数 值 r以及 帧 的 长 度 ．厂确定 下 来 ，该 标 签在 帧 中相应 的位 置 即被 确定 ，这 就使得 对 标签 的有 效轮 询成 为可 能．在实施 扫描 之前 ，阅读 器 可 以预先 根据 指定 集合 内各 标签 在 帧中对应 的位 置为 每个 时隙计 算 出期 望 的结 果 ：空 时 隙 (O)、单 时 隙(1)或者冲突时隙(C)．对 于某一时隙 ，如果该 时 隙期望 为单 时 隙但 实 际 无 响应 ，则 表 明对 应 于 该 时 隙 的标 签 丢失 ；如果 该 时 隙 期 望 为 冲 突时 隙 但 实 际 无 响应 ，则 表 明对 应 于该 时 隙 的所 有 标 签 丢失 ．图 4 给出 了基 于时 隙 ALOHA 协议 的轮询 机 制 示 意 图． 如 图所 示 ，在标 签 A～H 中 ，虚线 标 识 丢失 的标 签 ， 实 线标 识存 在 的标 签 ．当标 签 E、F以及 H 丢失 时 ， 其 对应 的时 隙实际 观察 到的状 态变 成 空时 隙(O)，此 时可 以判定 标 签 丢 失 ．但 对 于 标 签 C丢 失 的情 况 ， 由于标签 B、D的存在 ，使得对应时隙实际观察到的 状 态仍 为 冲突 时 隙 (C)，未 能 判 断 出标 签 C丢失 的 情 况 ，导 致假 阳性 误判 (FalsePositive)．上述 轮 询机 i 、 ’照’ 囤} 睡一 、 、 ． ＼ } ／ lOlol c oI… lcll o 旺Ⅱ王旺[二Ⅱ口珂 呈失 双 图 4 基 于时 隙 ALOHA协议 的轮询机制示 意图