460 计算机学 报 2013年 0 出了一套RFID标签读取性能的概率模型，基于时 隙ALOHA协议设计出优化的标签识别参数，相比 8 传统的识别机制更为有效地提升了识别的性能， 2.2RFID的标签数量估算机制 0.2 随着RFID应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 0.1 掘提供数据基础.在这种情况下，RFD系统不需要 逐个识别标签，仅仅需要快速获取扫描范围内标签 100 200 300 400 的统计信息，其中一个关键的信息就是标签数量.此 顿长f 外，基于动态帧长的时隙ALOHA协议也需要估算 图2给定标签数目n=100,信道使用效率与帧长f的关系 标签的大体数量来决定动态帧的长度.因此，近年来 1.0 出现了很多关注于如何快速、精确地估算标签数目 的研究工作，其核心思想主要是使用基于随机算法 0.8 罗 的时隙ALOHA协议来实现估算，研究者们意识 到，尽管时隙ALOHA协议是以随机的方式让标签 0.6 选择时隙进行数据传输，然而从统计意义上来看，整 0.4 个空时隙、单时隙以及冲突时隙的分布事实上是符 合二项分布的.当对时隙的采样次数足够多时，完全 0.2 可以基于二项分布规律来估算出实际参与标签的数 量.基于上述思路，文献[13]提出了一套快速而可靠 20 40 60 80 100 顿长f 的标签数量估算机制，以一种实用的方式实现了 RFID标签的快速统计.其主要思想为：假设在某一 图3随着标签数目n变化，使用最优帧长f·=n 对应的信道使用效率 轮中帧的长度为f,空时隙的数目会随着实际参与 的标签数n增加而减少，冲突时隙的数目会随着标 上述提到的协议与防冲突算法多数是在较为理 签数n增加而增加，而单时隙的数目会随着标签数 想的部署环境下得出，并未充分考虑实际应用环境 n增加先增加再减少，因此，空时隙（冲突时隙）的 下所遇到的种种雄题，例如，标签的频繁移动、多个 数目与标签数存在明确的单调减（增）关系.该文作 RFID阅读器之间的信号干扰、RFID标签传输的信 者基于二项分布的概率模型给出了空时隙与冲突时 号衰减以及多径效应等.因此，一些研究工作开始关 隙的数值期望计算公式，提出了空时隙与冲突时隙 注并尝试解决上述问题.鉴于之前的研究工作大多 相结合的估算算法，并通过重复采样的手段有效降 关注于解决标签之间的传输冲突问题，并未考虑到 低了估算的误差.研究者们通过进一步研究发现，尽 多个阅读器之间以及标签与阅读器之间的信号干 管单时隙数目与标签数目不存在单调关系，无法利 扰，文献[9-10]在多个RFID阅读器环境下提出了 用单时隙数目推算出确切的标签数目，但是3种时 优化的阅读器激活与调度机制，使得多个阅读器能 隙的数目结合起来能够指导系统更精确地估算标签 够协作地识别标签，有效避免信号的传输冲突.考虑 数目.文献[14]根据观察到的3种时隙的数目提出 到单个RFID阅读器的有效读取范围相对有限，文 了一套后验概率模型，基于最大化后验概率的决策 献[11]利用“时空关联”关系提出了性能高效的连续 来更精确地实现标签数量估算机制.上述机制均需 扫描机制，来实现对大规模部署标签的快速识别.之 要对3种时隙进行大量采样来提高估算的精确度， 前大部分的研究工作主要考虑在相对理想状态下针 事实上，完全可以借助其它参量来更快速有效地估 对静态环境设计优化的标签识别机制，并未考虑移 算标签数目.我们在文献[15]中提出了一种基于 动环境以及传输环境中普遍存在的信号衰诚对标签 Ball-and-Bin概率模型的快速估算方法.其核心思想 识别性能带来的影响.有鉴于此，我们针对上述问题 在于：每个标签会随机选择位置回复，系统可以通过 开展了相应的研究工作，文献[12]针对移动环境下 观察第一个标签回复的位置来估算最有可能造成该 持续变化的信号衰减情形，基于跨层优化的思路提 事件发生的标签数量.该文从理论上建立了概率模460 计 算 机 学 报 图 2 给定标签数 目，z一100，信道使用效率与帧长 ，的关系 趔 _K Ⅲ【苷 薰 槲 较 旺 图 3 随着标签数 目 变化 ，使用 最优 帧长厂 — 对 应的信道使用效率 上述 提 到 的协议 与 防冲 突算法 多数 是在 较 为理 想 的部署 环境 下 得 出 ，并 未 充 分 考 虑实 际应 用 环 境 下所 遇 到 的种 种 难 题 ，例 如 ，标 签 的频 繁 移 动 、多 个 RFID阅读器之间的信号干扰、RFID标签传输 的信 号衰减以及多径效应等．因此 ，一些研究工作开始关 注并 尝试 解决 上 述 问 题．鉴 于 之 前 的研 究 工 作 大 多 关 注于解 决 标签 之 间 的 传输 冲 突 问题 ，并 未 考 虑 到 多个 阅读 器 之 间 以及 标 签 与 阅 读 器 之 间 的 信 号 干 扰 ，文献 [-9一lo3在 多 个 RFID 阅读 器 环 境 下 提 出 了 优 化 的阅读 器激 活 与 调 度 机 制 ，使 得 多 个 阅 读 器 能 够 协作 地识 别标 签 ，有效 避 免信号 的传输 冲突 ．考 虑 到 单个 RFID 阅读 器 的有 效 读 取 范 围相 对 有 限 ，文 献[11]利用“时空关联”关系提出了性能高效的连续 扫 描机 制 ，来实 现对 大 规模 部署 标签 的快 速识 别 ．之 前大部分的研究工作主要考虑在相对理想状态下针 对 静 态环 境设 计优 化 的标 签 识 别 机 制 ，并 未 考 虑 移 动环境以及传输环境中普遍存在的信号衰减对标签 识别 性能 带来 的影 响．有鉴 于此 ，我 们针 对上 述 问题 开展 了相应的研究工作 ，文献 [12]针对移动环境下 持续变化 的信号衰减情形，基于跨层优化 的思路提 出 了一套 RFID标 签 读 取 性 能 的概 率 模 型 ，基 于 时 隙 ALOHA协 议设 计 出优 化 的标 签识 别 参 数 ，相 比 传统 的识 别机 制 更为 有效 地提 升 了识别 的性 能． 2．2 RFID 的标签 数 量估算 机 制 随 着 RFID应 用 的进 一 步 拓 展 ，某 些 应 用 仅 需 要获 取 一些 统计 性信 息来 为上 层 的数据 分析 以及 挖 掘提 供 数据基 础 ．在 这 种 情况 下 ，RFID 系统 不 需 要 逐个 识 别标 签 ，仅 仅 需 要 快 速 获 取 扫描 范 围 内标 签 的统计 信息 ，其 中一个 关键 的信息 就是 标签数 量 ．此 外 ，基于 动态 帧长 的时隙 ALOHA 协议 也 需 要估 算 标 签 的大体 数量 来决 定动 态 帧 的长度 ．因此 ，近 年来 出现 了很 多关注 于 如 何 快 速 、精 确 地估 算 标 签 数 目 的研 究 工作 ，其 核 心思 想 主 要 是 使 用基 于 随机 算 法 的时 隙 ALoHA 协 议 来 实 现 估 算 ．研 究 者 们 意 识 到 ，尽 管 时隙 ALOHA协 议是 以随机 的方 式 让标 签 选 择 时隙进 行数 据 传输 ，然 而从统 计 意义上 来 看 ，整 个 空 时隙 、单 时隙 以及 冲 突时 隙 的分 布 事 实 上 是符 合 二项 分布 的．当对 时 隙 的采样次 数 足够 多时 ，完全 可 以基 于 二项 分布 规律 来估 算 出实 际参 与标签 的数 量 ．基 于上 述思 路 ，文献 [-13]提 出 了一 套快 速而 可靠 的标签 数 量 估 算 机 制 ，以 一 种 实 用 的 方 式 实 现 了 RFID标 签 的快速 统 计．其 主要 思 想 为 ：假 设 在 某 一 轮 中帧 的长度 为 厂，空 时 隙 的 数 目会 随着 实 际 参 与 的标 签数 n增加 而减 少 ，冲 突 时 隙 的数 目会 随 着 标 签数 增 加 而增加 ，而 单 时 隙 的数 目会 随 着 标 签 数 n增加 先增 加 再 减 少 ，因 此 ，空 时 隙 (冲 突 时 隙 )的 数 目与标 签数 存在 明确 的单 调 减 (增 )关 系．该 文 作 者基 于二 项分 布 的概 率模 型 给出 了空 时隙与 冲 突时 隙 的数值 期 望计算 公 式 ，提 出 了 空 时 隙与 冲突 时 隙 相结 合 的估算 算 法 ，并 通 过 重 复 采样 的手 段 有 效 降 低 了估算 的误差 ．研究 者们 通 过进 一步 研究 发现 ，尽 管 单时 隙数 目与标 签 数 目不 存 在 单 调 关 系 ，无 法 利 用 单时 隙数 目推 算 出 确 切 的标 签 数 目，但 是 3种 时 隙的数 目结 合起 来 能够 指导 系统更 精 确地估 算 标签 数 目．文献 [-14]根据 观 察 到 的 3种 时 隙 的数 目提 出 了一套 后验 概率 模 型 ，基 于最 大 化 后 验 概率 的决 策 来更精确地实现标签数量估算机 制．上述机制 均需 要对 3种时隙进行大量采样来提高估算 的精确度 ， 事实上，完全可以借 助其它参量来更快速有效地估 算标签数 目．我 们在 文献 [15]中提 出了一 种基 于 Ball—and—Bin概率模型的快速估算方法．其核心思想 在 于 ：每个 标 签会 随机 选择 位置 回复 ，系 统可 以通 过 观察第一个标签 回复的位置来估算最有可能造成该 事件 发 生 的标签 数量 ．该 文 从 理论 上建 立 了概 率 模