RFID数据管理：算法、协议与性能评测（南京大学：谢磊、殷亚凤、陈曦、陆桑璐、陈道蓄）

第36卷第3期 计算机学报 Vol.36 No.3 2013年3月 CHINESE JOURNAL OF COMPUTERS Mar.2013 RFD数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 (南京大学计算机软件新技术国家重点实验室南京210093) 摘要随着物联网关键理论及技术的发展，RFD作为物联网的核心支撑技术，成为物联网领域备受关注的研究 热点之一.文中以RFID的数据管理为切人点，从算法、协议以及性能评测3个层面对RFD的研究工作进行阐述 与分析，者重介绍了RFD的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展，最后展望了未来的研究方向. 关键词射频识别；数据管理：防冲突算法：认证与隐私保护；性能优化；物联网 中图法分类号TP393 D0I号10.3724/sP.J.1016.2013.00457 RFID Data Management:Algorithms,Protocols and Performance Evaluation XIE Lei YIN Ya-Feng CHEN Xi LU Sang-Lu CHEN Dao-Xu (State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093) Abstract With the development of critical theories and technologies in Internet of Things (IOT),as a key supporting technology,RFID has become one of the hotspots in the field of Internet of Things.Focusing on RFID data management,this paper describes and analyzes the re- search work on three aspects:algorithm,protocol and performance evaluation.In this paper,we introduce the research progress in RFID with anti-collision algorithm,authentication and privacy protection protocols,as well as performance evaluation of RFID systems in realistic settings.Fi- nally,we outlook the future research directions and conclude. Keywords RFID;data management;anti-collision algorithm;authentication and privacy protec- tion;performance optimization;Internet of Things 追踪等.随着RFID的技术原理被进一步深人理解、 引言 廉价的RFID组件相继出现以及RFID的安全得到 保障，RFID技术将会在物联网应用中发挥越来越 随着“物联网”时代的来临，新一代T技术将 重要的作用. 被充分运用在各行各业之中.射频识别(RFD)作为 物联网的核心理念是在普适环境下实现“物物 物联网应用的一项核心支撑技术，在学术界与工业 相联”，即通过对物理世界信息化、网络化，将传统上 界已经得到广泛关注.目前，RFD技术正在越来越 分离的物理世界与信息世界实现互联与整合.这就 频繁地出现在大量的物联网应用中，包括物流管理、 需要将“智能”嵌入到每一个物理对象当中，并且提供 电子支付、RFD护照、安全访问控制、目标监测与 一种有效的、低成本的通信方式，RFID技术的出现 牧稿日期：2012-02-08：最终修改稿收到日期：2012-05-27.本课题得到国家“九七三”重点基础研究发展规划项目基金(2009CB320705)、国家 自然科学基金(61100196,61073028,61021062)以及江苏省自然科学基金(BK2011559)资助.谢磊，男，1982年生，博士，讲师，中国计算机 学会(CCF)会员，主要研究方向为传感器网络、RFID系统、车联网、高性能计算.E-mail:lxie@ju,edu.cn殿亚凤，女，l989年生，博士研究 生，中国计算机学会(CCF)学生会员，主要研究方向为RFID.陈曦，男，1988年生，硕士研究生，中国计算机学会(CCF)学生会员，主要研究 方向为RFID.陆秦璐，女，1970年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为普适计算、分布式计算、传感 器网络.陈道蓄，男，1947年生，数授，博士生导师，中国计算机学会(C℃)高级会员，主要研究领域为普适计算、分布式计算、计算机网络

第 36卷 第 3期 2013年 3月 计 算 机 学 报 CHINESE JOURNAL OF COMPUTERS Vol_36 NO．3 M ar． 2O13 1 RFID数据管理 ：算法 、协议与性能评测 谢 磊 殷亚凤 陈 曦 陆桑璐 陈道蓄 (南京大学计算机软件新技术 国家重点实验室 南京 210093) 摘 要 随着物联网关键理论及技术 的发展 ，RFID作为物联 网的核心支撑技术 ，成为物联 网领域备受关 注的研究 热点之一．文 中以 RFID的数据管理为切入点 ，从算法 、协议 以及性 能评测 3个层 面对 RFID 的研 究工作进 行 阐述 与分析 ，着重介 绍了 RFID的防冲突算法 、认证 与隐私保护协议 以及真实环境下 系统 的性能评测 与分析等方 面的研 究 成果 及进展．最后 展望了未来的研究方 向． 关键词 射频识别 ；数据管理 ；防冲突算法 ；认证与隐私保护 ；性能优化 ；物联 网 中 图 法 分 类 号 TP393 DOI号 10．3724／SP．J．1016．2013．00457 RFID Data M anagem ent：Algorithm s，Protocolsand Perform ance Evaluation XIE Lei YIN Ya—Feng CH EN Xi LU Sang—Lu CH EN Dao—Xu (StateKeyLaboratoryforNovelS0ftwareTechnology，NanjingUniversity，Nanjing 210093) Abstract W ith the development of critical theories and technologies in Internet of Things (IOT)，as a key supporting technology，RFID has become one ofthe hotspots in the field of InternetofThings．Focusing on RFID datamanagement，thispaperdescribes and analyzesthere— search work on threeaspects：algorithm ，protocoland performanceevaluation． In thispaper，we introducetheresearch progressin RFID with anti—collision algorithm ．authentication andprivacy protection protocols，aswellasperformanceevaluation ofRFID system sin realisticsettings．Fi— nally，we outlook thefutureresearch directionsand conclude． Keywords RFID ；datamanagem ent；anti—collision algorithm ；authentication and privacyprotec tion；perform anceoptim ization；InternetofThings 引 目 随 着 “物 联 网”时 代 的来 临 ，新 一 代 IT 技 术将 被充 分 运用 在各 行各业 之 中．射 频识 别 (RFID)作 为 物联 网应用 的一 项 核 心支 撑 技 术 ，在 学 术 界 与 工 业 界 已经 得到 广泛 关 注．目前 ，RFID 技术 正 在 越 来 越 频 繁地 出现 在大 量 的物联 网应 用 中 ，包 括物 流管 理 、 电子支 付 、RFID 护 照 、安 全 访 问控 制 、目标 监 测 与 追踪 等 ．随着 RFID 的技 术原 理被 进 一步 深 入理 解 、 廉 价 的 RFID组件 相继 出 现 以及 RFID 的安 全 得 到 保 障 ，RFID技 术 将 会 在 物联 网应 用 中 发 挥 越 来 越 重要 的作用 。 物 联 网 的核 心理 念是 在普 适 环境 下 实现 “物一物 相联”，即通过对物理世界信息化、网络化 ，将传统上 分 离 的 物 理世 界 与信 息世 界 实现 互 联 与整 合 ．这 就 需要将“智能”嵌入到每一个物理对象当中，并且提供 一 种 有效 的 、低 成 本 的通 信 方式 ，RFID技 术 的 出现 收稿 日期 ：2012—02—08；最终修改稿收到 日期 ：2012—05—27．本课题得到国家 “九七 三”重点基础研究 发展规划项 目基金(2009CB320705)、国家 自然科学基金(61100196，61073028，61021062)以及江苏省 自然科学基金 (BK2O11559)资助．谢 磊 ，男 ，1982年生 ，博士 ，讲师 ，中国计算机 学会(CCF)会员 ，主要研究方向为传感器网络 、RFID系统 、车联 网、高性能计算．E-mail：lxie@niU．edu．cn．殷亚凤，女，1989年生 ，博士研究 生 ，中国计算机学会 (CCF)学生会员 ，主要研究方向为 RFID．陈 曦 ，男 ，1988年生 ，硕士研究生 ，中国计算机学会(CCF)学生会员 ，主要研究 方 向为 RFID．陆桑璐 ，女 ，1970年生 ，博士 ，教授 ，博士生导师 ，中国计算机 学会 (CCF)会员 ，主要研究领域为 普适 计算 、分布式计算 、传 感 器 网络．陈道蓄 ，男 ，1947年生 ，教授 ，博士生导师 ，中国计算 机学会 (CCF)高级会员 ，主要研究领域为普适计算、分布式计算、计算机 网络．

458 计算机学报 2013年 正好满足了这一需求.RFID是一种非接触式的自 为数据管理提供基本的安全保障，能够有效地实现 动识别技术，它通过射频信号自动识别目标对象并 认证并且保护用户隐私，实现RFID数据管理的可 获取相关数据，识别工作无须人工干预.作为一种简 信性；对RFID系统进行性能评测与分析，其目的在 单的无线系统，RFID系统只有两个基本器件，一个 于验证在真实环境下物理层的关键因素对系统识别刷 是阅读器，另一个是标签.其基本工作原理是：阅读器 性能的影响，确保数据管理的可靠性.深入探究三者 以广播方式连续向周围发送携带能量的基准信号， 之间的联系，我们发现任一研究问题均对其余二者 感应到能量的标签通过调制电路信号以反射的方式 产生影响：防冲突算法能够提供最根本的数据传输 向阅读器返回自身携带的数据，阅读器对接收到的 支持，安全协议能够实现必要的安全保障，性能评测 数据进行解码，并传给主机进行处理.通过上述方 能够验证在真实环境下的系统运行性能.上述三方 式，RFID系统能够提供有效的身份信息(Identity) 面研究问题与RFID系统协议栈的对应关系如图1 和地址信息(Location).相比于其它智能系统， 所示，可以看到三者之间相互联系，又各有侧重. RFID系统具有如下鲜明特点：(1)能够实现非接触 RFD数据管理 式的快速自动识别；(2)标签内能够永久存储一定 可靠性 高效性 可信性 大小的数据：(3)标签内含一定数目的逻辑门能够 价 进行简单的逻辑处理；(4)标签具有普通无线设备 性能 防冲突 安全 的物理属性：(5)标签成本低廉，可以大量部署.因 评测 算法 协议 此，作为物联网感知识别层面的一项关键技术， RFID技术能够使得物联网中的每一个物体被唯一 物理层 媒体访问 控制层 应用层 地识别，并且能够携带规范而具有互用性的信息，在 RFID系统协议栈 无源的情况下有效实现“被动智能”，为“物-物相联” 提供根本保障。 图1各研究问题之间的逻辑层次关系 在物联网环境下，RFID系统被部署和应用的 本文第2节主要介绍RFID的标签识别协议与 根本目的是：针对具体的应用需求，对被标识的物理 防冲突算法，着重阐述RFID标签识别机制、数目估 对象进行合理有效的信息收集，为上层应用提供最 算机制以及轮询机制方面的研究工作：第3节主要 基本的数据支持.因此，任何一种具体的RFD应用 介绍RFID的认证与隐私保护协议，对RFID的安 都依赖于对RFID数据实现有效的数据管理.所谓 全与隐私问题进行探讨与分析，并对RFID安全方 数据管理是指结合RFID系统的应用需求实现有效 面的三类主流技术进行总结；第4节对真实环境下 且有针对性的数据收集、分析挖掘以及数据安全保 RFID系统性能的评测与分析方面的研究工作进行 障等操作.在现有的物联网体系架构中，数据管理起 介绍；第5节对RFID数据管理相关的其它开放性 着承上启下的关键作用：一方面，物联网需要从感知 问题的研究进展进行总结；第6节展望RFID未来 到的海量原始数据中提取有效信息并进行管理，为 的研究方向；最后对全文进行总结 上层的特定应用提供数据支撑；另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 2RFID标签识别协议与防冲突算法 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现. 2.1RFID的标签识别协议 基于上述认识，本文关注RFID数据管理问题， 在通常的RFID应用中，大量的RFID标签往 以数据管理的核心技术为切入点，分别从RFID的 往被广泛地部署在指定区域中.为了能够快速有效 防冲突算法、RFID的认证与隐私保护协议以及真 地识别这些标签，阅读器需要在RFID标签识别协 实环境下RFID系统数据收集的性能评测与分析 议中使用一套有效的防冲突算法来逐一读取这些标 3个方面对RFID数据管理技术的研究与进展进行 签.在无线通信环境下，普通的无线设备主要基于载 分析与讨论.图1展示了上述3个方面研究问题之 波侦听多路访问/冲突避免(CSMA/CA)的竞争机 间的逻辑层次关系.其中，研究防冲突算法的目的是 制来实现多个设备之间的通信，如802.11协议.与 为MAC层提供一套快速的标签识别机制，实现 普通的无线节点不同，RFID标签是极为简单的无 RFID数据管理的高效性；研究安全协议的目的是 线设备，标签上的资源极其有限，不能够自发地通过

458 计 算 机 学 报 正 好满 足 了这 一 需 求 ．RFID是 一 种 非 接 触 式 的 自 动 识别 技术 ，它 通 过 射频 信 号 自动 识 别 目标 对 象 并 获 取相 关 数据 ，识别 工作 无 须人 工干 预．作 为 一种 简 单 的无 线 系 统 ，RFID 系统 只有 两 个 基 本 器件 ，一 个 是 阅读器 ，另 一个是标 签．其基本 工作原 理是 ：阅读 器 以广播方式连续向周 围发送携带能量 的基准信号 ， 感应到能量的标签通过调制 电路信号以反射的方式 向阅读 器 返 回 自身 携 带 的数 据 ，阅读 器 对 接 收 到 的 数据进行解码 ，并 传给 主机进行处理．通过 上述方 式 ，RFID 系统 能够 提 供 有 效 的身 份 信 息 (Identity) 和地 址 信 息 (Location)．相 比 于 其 它 智 能 系 统 ， RFID 系统 具有 如下 鲜 明特点 ：(1)能 够实 现 非 接触 式 的快速 自动识 别 ；(2)标 签 内能 够 永 久 存 储 一 定 大小 的数 据 ；(3)标 签 内含 一 定 数 目的逻 辑 门能 够 进行 简单 的逻 辑处 理 ；(4)标 签 具 有 普 通 无 线 设 备 的物理 属性 ；(5)标 签 成 本 低 廉 ，可 以 大 量 部 署 ．因 此 ，作 为 物 联 网感 知 识 别 层 面 的 一 项 关 键 技 术 ， RFID技术能够使得物联 网中的每一个物体被 唯一 地识 别 ，并且 能 够携 带规 范而 具有 互用 性 的信 息 ，在 无 源 的情况 下有 效 实现 “被动 智 能”，为 “物一物相 联 ” 提 供根 本保 障 ． 在 物联 网环 境 下 ，RFID 系 统 被 部 署 和 应 用 的 根 本 目的是 ：针 对具 体 的应用 需 求 ，对 被标 识 的物 理 对象进行合理有效 的信息收集 ，为上层应用提供最 基本的数据支持．因此 ，任何一种具体的 RFID应用 都 依赖 于 对 RFID 数 据 实 现 有 效 的数 据 管 理 ．所 谓 数据管理是指结合 RFID系统的应用需求实现有效 且 有 针对 性 的数据 收 集 、分 析挖 掘 以及 数 据 安 全 保 障等操 作 ．在 现有 的物 联 网体 系架构 中 ，数据 管理 起 着承 上启 下 的关键 作 用 ：一 方 面 ，物 联 网需要 从感 知 到 的海量 原始 数 据 中 提 取有 效 信 息 并 进 行 管 理 ，为 上层 的特 定应 用 提供 数据 支撑 ；另 一方 面 ，物联 网需 要结 合具 体 的数 据管 理需 求来 组织 感 知识 别层 面 的 众 多节 点 ，在 网络 层 面进 行优 化调 度 与资 源配 置 ，以 更有效地指导下层协议与算法 的设计实现． 基 于上 述认识 ，本文关 注 RFID数 据 管 理 问题 ， 以数据管理的核心技术为切入点 ，分别从 RFID的 防 冲突算 法 、RFID 的认 证 与 隐私 保 护 协 议 以及 真 实 环境 下 RFID 系 统 数 据 收 集 的 性 能 评 测 与 分 析 3个 方 面对 RFID数据 管 理 技术 的研 究 与 进 展进 行 分 析 与讨论 ．图 1展 示 了上 述 3个 方 面 研 究 问题 之 间的逻辑层次关系．其中，研究防冲突算法的目的是 为 MAC层 提供 一套 快 速 的标 签识 别 机 制，实 现 RFID数 据管 理 的 高 效 性 ；研 究 安 全 协 议 的 目的 是 为数据 管 理提供 基 本 的安 全 保 障 ，能 够 有 效地 实 现 认 证并 且保 护 用 户 隐 私 ，实 现 RFID数 据 管 理 的 可 信 性 ；对 RFID 系统 进行 性能 评测 与 分 析 ，其 目的 在 于验证 在 真实 环境 下物 理层 的关 键 因素对 系统 识 别 性能 的影 响 ，确保数 据 管理 的可 靠性 ．深入 探究 三 者 之 间的联 系 ，我们 发 现 任 一研 究 问题 均 对 其 余 二 者 产生 影 响 ：防冲突 算 法 能 够 提供 最 根 本 的数 据 传 输 支持 ，安全 协 议能 够实 现必 要 的安全 保 障 ，性 能评 测 能够 验证 在 真实 环境 下 的 系统 运 行 性 能．上 述 三 方 面研 究 问题 与 RFID 系统 协 议 栈 的对 应 关 系 如 图 1 所示 ，可 以看 到 三者 之间相 互 联系 ，又各 有侧 重． 图 1 各研 究 问 题 之 I司的逻 辑 层 次 关 系 本 文第 2节 主要 介 绍 RFID的标 签 识别 协 议 与 防冲 突算法 ，着 重 阐述 RFID标签 识 别 机制 、数 目估 算 机制 以及 轮 询机 制 方 面 的研究 工 作 ；第 3节 主 要 介 绍 RFID 的认 证 与 隐私 保 护 协 议 ，对 RFID 的 安 全 与 隐私 问题 进 行 探 讨 与 分 析 ，并 对 RFID 安 全 方 面 的三类 主 流技术 进 行 总 结 ；第 4节 对 真 实 环 境 下 RFID 系统性 能 的评 测 与 分析 方 面 的研 究 工 作 进 行 介 绍 ；第 5节 对 RFID 数 据 管 理 相 关 的 其 它 开 放 性 问题 的研 究 进展 进 行 总 结 ；第 6节 展 望 RFID 未 来 的研 究方 向 ；最后 对全 文进 行 总结 ． 2 RFID标签识别协议 与防冲突算 法 2．1 RFID的标 签识 别协 议 在 通常 的 RFID 应 用 中 ，大 量 的 RFID 标 签 往 往被广泛地部署在指定区域 中．为了能够快速有效 地 识别 这些 标 签 ，阅读 器 需 要 在 RFID标 签 识 别 协 议 中使用一套有效的防冲突算法来逐一读取这些标 签 ．在 无线 通信 环境 下 ，普通 的无 线设 备 主要基 于载 波侦听多路访 问／冲突避免 (CSMA／CA)的竞争机 制来实现多个设备之间的通信 ，如 802．11协议．与 普通的无线 节点不 同，RFID 标签是极为简单 的无 线 设备 ，标 签 上 的资源极 其 有 限 ，不 能够 自发 地通 过

3期 谢磊等：RFD数据管理：算法、协议与性能评测 459 调节自身的无线传输机会来避免标签间的传输冲 表1两类防冲突算法的优缺点比较 突.具体来说，标签没有足够的处理能力与能源来实 基于二进制树防冲突算法基于ALOHA防冲突算法 现上述竞争机制，避免通信冲突.鉴于RFD的系统 使用随机算法，算法实现逻粗简 通常使用确定性的算法， 特点，RFID标签识别协议需要具备如下性质： 算法实现逻辑简单：基于 单：平均情况下，标签识别性能良 优点 (1)简单.由于RFID标签上的计算、存储资源极其 查询树结构的算法不需 好：随机算法使得各时隙的结果 要存储中间状态变量 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 有限，标签识别协议的处理逻辑（包括执行流程和状 算法的随机性导致存在“饿死”问 态迁移关系)需要尽可能简单；(2)高效.面对大量 对基于查询树结构的算 题，某些标签可能永远选择不到 的RFID标签，标签识别协议需要提供轻量级的通 缺点 法，标签识别的时延受扫 描范围内标签ID的分 单时隙进行传输：最环情况下，标 布以及ID的长度影响 签识别的时延趋向于十∞，其性 信机制，尽可能避免不必要的控制报文的传输，确保 能无法保障 传输的高吞吐率与低延迟性。 隙，导致时隙的浪费；如果帧长过小，则该帧大部分 目前的RFID防冲突算法主要分为两大类：基 时隙会出现标签传输冲突，导致大部分标签需要在 于二进制树的防冲突算法1]和基于ALOHA的防 下一帧重传.因此，研究者们对该问题进行了深入研 冲突算法[3]，前者利用二叉搜索树，按照递归的方 究.文献[5]分析了在时隙ALOHA协议中采用动 式将冲突的标签集合划分为两个标签子集，对于可 态帧长的方法对读取性能的影响.文献[6]基于贝叶 能产生冲突的相关标签集合，采用沉默的方式来解 斯的概率模型提出了优化动态帧长的决策机制.文 决冲突问题.划分子集的方法包括随机二进制树算 献[7]利用马尔可夫过程来对读取过程进行建模，并 法和查询二进制树算法.文献[1]提出了一套自适应 且由此计算出读取过程中应该使用的一系列优化的 的基于树形结构的防冲突算法来实现有效的标签识 帧长.文献[8]进一步针对最大化信道使用效率的目 别.文献[2]提出了-一套基于查询树结构的智能遍历 标推导出优化的动态帧长，该文指出，如果每一轮中 机制，能够以低延迟的方式实现标签的识别. 帧长与当前未读取的标签数相同，则整个信道能够 ALOHA协议最早被用在分组无线网络中实现随机 达到最大的使用效率.其原理阐述如下：假设当前标 访问机制.在RFID系统中，为了提高标签识别的效 签数目为n,帧长为f；由于标签对时隙的选择符合 率，文献[3-4]提出了时隙ALOHA协议来有效解 二项分布，则根据二项分布，当前帧中单时隙的期望 决冲突，实现标签的高效识别.时隙ALOHA协议 数目为E[n]=n×(1一1/f)-1,为了最大化信道 将若干个时隙组织为一帧，在每一帧开始时，阅读器 的使用效率，即单时隙数目在当前帧中的比例 广播帧的长度f,即当前帧所包含的时隙个数，并通 n/f,我们采用求极值的方法计算f的取值，即 过发送连续的电磁波来激活扫描范围内所有标签. 每个标签在接收到帧长f之后随机独立地在第1~ E[m]f=0→∫·=n,得到此时信道的使用效率 8f f个时隙中选择一个时隙发送标识符.如果成功，即 为n/f”→1/e.对于上述性质，我们在图2和图3 无冲突发生，该标签进入静默状态；如果有冲突发 中给出更为形象的描述，图2展示了给定标签数目 生，则该标签将继续等待在下一帧中再选择一个时 n=100,帧长f变化对信道使用效率的影响.可以 隙重新发送标识符.因此，每一帧的时隙会存在如下 看到当帧长∫由小及大变化时，信道的使用效率逐 3种情况之一：(1)空时隙(Empty Slot).没有任何 渐增大后又逐渐减小，在f=100时取到最大值1/e. 一个标签选中该时隙；(2)单时隙(Singleton Slot).. 图3展示了随着标签数目n变化，使用最优帧长 仅有唯一一个标签选中该时隙；(3)冲突时隙 f·=n对信道使用效率的影响.可以看到当n取值 (Collision Slot).多个标签选中该时隙.上述每种时 较小时，所达到的最优效率大于1/e,例如，当仅有 隙所包含的信息量各不相同.目前，时隙ALOHA 一个标签时(n一1)，帧长为1可以达到最优效率 协议已经成为RFID系统在EPC-CIG2标准下使用 100%.当n逐渐增大时，其最优效率快速收敛到 的通信协议.在表1中，我们分别从优缺点两个方面 1/e.这就意味着，当n>5时，每一轮帧长f取值为 对上述两种防冲突算法进行了比较，总体而言，两者 当前待读的标签数n时，使用效率趋向于1/e,可以 在性能与功能实现方面各有利弊， 达到当前每一轮的局部最优效率.如果在识别过程 对于时隙ALOHA协议而言，每一轮所采用的 中每一轮都使用该策略，则整体效率可接近1/e.由 帧长对总体的识别性能至关重要.对于给定的待读 于1/e是整体效率的上限值，因此当前整体效率接 标签集合，如果帧长过大，则该帧大部分时隙为空时 近全局最优

3期 谢 磊等 ：RFID数 据管理 ：算法 、协议与性能评测 459 调节 自身 的无线传 输机会来避免标签 间的传输 冲 突．具体 来说 ，标签 没有 足够 的处 理能 力 与能源 来实 现上述竞争机制，避免通信冲突．鉴于 RFID的系统 特 点 ，RFID 标 签 识 别 协 议 需 要 具 备 如 下 性 质 ： (1)简单 ．由于 RFID标签 上 的计 算 、存 储 资 源 极其 有 限 ，标 签识 别协 议 的处理 逻辑 (包括 执行 流程 和状 态迁 移关 系 )需 要 尽 可 能 简单 ；(2)高 效 ．面对 大量 的 RFID标 签 ，标 签识 别 协 议 需 要 提 供 轻 量 级 的通 信 机制 ，尽 可能避 免不 必要 的控 制报 文 的传输 ，确保 传输 的高吞吐率与低延迟性． 目前 的 RFID 防 冲突 算法 主要 分 为 两 大 类 ：基 于二 进制 树 的防 冲突算 法 l_】]和基 于 ALOHA 的 防 冲 突算法 _3]．前 者 利 用 二叉 搜 索 树 ，按 照递 归 的方 式将 冲突 的标签集 合划 分 为 两 个 标 签 子集 ，对 于 可 能产生冲突的相关标签集合 ，采用沉默 的方式来解 决 冲突 问题 ．划分 子 集 的方 法 包 括 随机 二 进 制 树算 法 和查询 二进 制树 算法 ．文 献 [1]提 出 了一 套 自适应 的基 于树 形结 构 的防 冲突算 法来 实现 有效 的标 签识 别 ．文献 E2]提 出了一套 基 于查询 树结 构 的智能 遍 历 机 制 ，能 够 以 低 延 迟 的 方 式 实 现 标 签 的 识 别 ． ALOHA协 议最 早被 用在 分组 无线 网络 中实 现 随机 访 问机制 ．在 RFID系统 中 ，为 了提 高 标 签识 别 的效 率 ，文献 [3—4]提 出 了 时 隙 ALOHA 协 议 来 有 效 解 决 冲突 ，实 现标 签 的 高 效 识 别 ．时 隙 ALOHA 协 议 将若 干个 时 隙组织 为一 帧 ，在每 一帧 开始 时 ，阅读器 广播帧的长度 ．厂，即当前帧所包含的时隙个数，并通 过发 送连 续 的 电磁 波来 激 活 扫 描 范 围 内所 有 标 签 ． 每个 标签 在接 收到 帧长 -厂之 后 随机 独立 地 在第 1～ ，个时隙中选择一个时隙发送标识符．如果成功 ，即 无 冲突发 生 ，该 标 签 进 入 静 默 状 态 ；如果 有 冲 突发 生 ，则该标签将继续等待在下一 帧中再选择一个 时 隙重新发送标识符．因此 ，每一帧的时隙会存在如下 3种 情 况之 一 ：(1)空 时 隙 (EmptySlot)．没 有 任 何 一 个 标签 选 中该时 隙 ；(2)单 时 隙 (SingletonSlot)． 仅有 唯 一 一 个 标 签 选 中 该 时 隙 ；(3)冲 突 时 隙 (CollisionSlot)．多个标 签 选 中该 时 隙．上 述 每 种 时 隙所包含 的信息量各 不相 同．目前 ，时隙 ALOHA 协议 已经 成为 RFID系统 在 EPC—c1G2标 准下 使用 的通信 协 议．在 表 1中 ，我们 分别从 优 缺点 两个 方面 对上述两种防冲突算法进行 了比较 ，总体而言 ，两者 在性 能与 功能 实现 方 面各有 利弊 ． 对于时隙 ALOHA协议而言 ，每一轮所采用 的 帧长对总体的识别性能至关 重要．对于给定 的待读 标签集合 ，如果帧长过大 ，则该帧大部分时隙为空时 表 1 两类防冲突算法的优 缺点比较 基 于二进制树 防冲突算法 基于 ALOHA 防冲突算 法 莩妻孽要塞譬 墨焉 卺磊譬 优点 誊笙 l辋 萋需孬：嚣 葫 缮巢芬 要存储中间状态变量 茬 翌 慧I 篓惹 缺点鎏布以及I内D的篷长度影响分军 凳毽～螽；’，”：霍 隙 ，导致 时 隙的浪 费 ；如 果 帧 长 过 小 ，则该 帧 大部 分 时 隙会 出现标 签传 输 冲 突 ，导 致 大 部 分标 签 需 要 在 下 一帧重 传 ．因此 ，研究 者们 对该 问题 进行 了深入 研 究 ．文献 [5]分 析 了在 时 隙 ALOHA 协议 中采 用 动 态 帧长 的方 法对读 取性 能 的影 响．文 献E6]基 于 贝 叶 斯 的概率 模 型提 出 了优 化 动 态 帧 长 的决 策 机 制．文 献 [7]利 用 马尔可 夫过 程来 对读取 过 程进行 建模 ，并 且 由此计 算 出读取 过程 中应 该使 用 的一系列 优化 的 帧 长．文 献 [8]进一 步针 对最 大化 信道 使用效 率 的 目 标 推导 出优 化 的动态 帧长 ，该文 指 出 ，如果 每一 轮 中 帧 长与 当前 未读取 的标 签 数 相 同 ，则 整个 信 道 能 够 达到最大的使用效率．其原理阐述如下：假设 当前标 签数 目为 ，帧长为 -厂；由于标签对时隙的选择符合 二项 分布 ，则 根据 二项分 布 ，当前 帧 中单时 隙的期 望 数 目为 E[ ]一 ×(1—1／f)一 ；为了最大化信道 的使 用 效 率 ，即单 时 隙 数 目在 当前 帧 中 的 比例 ／f，我 们 采 用 求 极 值 的 方 法 计 算 -厂的 取 值 ，即 aF r ] ／ 一0一 f 一 ，得 到此 时信道 的使用效率 Uj 为 m／f 一 1／e．对 于 上述 性 质 ，我们 在 图 2和 图 3 中给 出更 为形 象 的描 述 ．图 2展 示 了给定 标 签 数 目 7"／z100，帧长 厂变化对信道使用效率的影响．可 以 看到当帧长 厂由小及大变化 时，信道的使用效率逐 渐增 大后 又逐 渐减 小 ，在 ．厂一100时取 到最 大值 1／e． 图 3展 示 了 随 着 标 签 数 目 n变 化 ，使 用 最 优 帧 长 f 一 对信 道使 用效 率 的影 响．可 以看 到 当 n取 值 较小 时 ，所达 到 的最 优 效 率 大 于 1／e，例 如 ，当仅 有 一 个 标签 时 ( 一 1)，帧 长 为 1可 以 达 到 最 优 效 率 100 ．当 逐 渐 增 大 时 ，其 最 优 效 率 快 速 收 敛 到 1／e．这 就意 味着 ，当 > 5时 ，每 一 轮 帧长 ．厂取 值 为 当前待读 的标签数 n时，使用效率趋 向于 1／e，可 以 达到当前每一轮的局部最优效率．如果在识别过程 中每一轮都使用该策略 ，则整体效率可接近 1／e．由 于 1／e是整体效率 的上限值 ，因此 当前整体效率接 近全局 最 优．

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概率模型的快速估算方法．其核心思想 在 于 ：每个 标 签会 随机 选择 位置 回复 ，系 统可 以通 过 观察第一个标签 回复的位置来估算最有可能造成该 事件 发 生 的标签 数量 ．该 文 从 理论 上建 立 了概 率 模

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协议 的轮询机制示 意图

462 计 算机 学报 2013年 制为进一步的研究工作提供了一个理论基础 而言，其安全问题是指存在伪造标签时，如何有效地 基于上述认识，文献[20]对面向大规模标签监 对标签进行认证；其隐私问题是指存在恶意阅读器 控应用中的一个重要问题进行了研究：如何在大量 时，如何防止阅读器对标签的非法访问，来有效地保 标签中快速定位出丢失的标签.该文利用时隙 护用户的隐私.在常用的网络安全解决方案中，已经 ALOHA协议的伪随机性，基于轮询机制提出了多 存在成熟的加解密算法如DES、AES、RSA、椭圆曲 种协议，能够快速有效地定位丢失的标签.针对由电 线密码等，这些算法构成了对称密钥加密以及公开 池供电的大规模主动标签实时信息收集的问题，文 密钥加密中的支撑技术，能够有效地实现加密与鉴 献[21]设计了一套高效节能的轮询协议.该协议基 别功能，抵制非法读取、伪装哄骗、重放攻击等安全 于标签排序(Tag-Ordering)的编码方式，使得所消 威胁，具有良好的安全性.但实现上述算法需要较多 耗的能量比通常的轮询协议下降一个数量级.该协 的逻辑处理单元，如AES需要大约20000~30000 议进一步采用基于分块的布鲁姆过滤器(Bloom 个逻辑门，RSA、椭圆曲线密码等公钥密码算法则需 Filter)来提高轮询机制的性能，在不影响整体扫描 要更多的逻辑门.而RFID标签受到低成本限制，通 时间的前提下显著降低了能耗.文猷[22]针对上述 常只能拥有大约5000~10000个逻辑门，并且这些 问题进一步提出了基于单级Hash与多级Hash的 逻辑门主要用于实现一些最基本的标签功能，仅剩 轮询机制，显著地降低了信息收集的时间.文献[23] 少许可用于实现安全功能.此外，RFID标签上的存 基于轮询协议提出了一套批处理的认证机制，无需 储资源也非常受限，通常标签的EPC区仅能存储 通过逐个识别的方式来认证标签，通常情况下，为了 96bit数据，用户区仅能存储512bit数据.RFID标 实现对大量标签的认证，阅读器需要对标签逐一识 签极其有限的计算资源难以支持上述复杂的加解密 别并认证，这种方式需要耗费大量的通信开销与扫 算法的实现.因此，对RFID系统而言，其安全与隐 描时间.基于轮询协议的伪随机性，该批处理认证 私保障机制所面临的最大挑战在于：如何以一种轻 机制提出了一套快速的认证算法，能够极大地降低 量级的方式在资源极其受限的RFD系统上实现认 认证的扫描时间与通信开销.由于该机制基于时隙 证与隐私保护协议.下面我们从基于物理方法的安 ALOHA的随机算法进行认证，因此存在假阳性误 全保护机制、基于对称密钥加密的协议以及基于 判，但是该机制能够以概率的形式确保未检测到的 Hash函数的协议等几个方面来具体阐述相关研究 伪造标签所占比例被控制在指定國值范围内.上述 成果 研究工作的轮询机制都对应于扫描范围内的所有标 3.2基于物理方法的安全保护机制 签，如果仅需要对扫描范围内标签的一个子集进行 RFID的隐私问题是由阅读器识别标签时无需 轮询，这些机制将很难适用.因此，针对大规模标签 认证引起的.在没有隐私保障机制的情况下，阅读器 部署情况下搜索特定标签集合的问题，文献[24]基 可以随意地对标签进行秘密扫描，获取标签信息；对 于布鲁姆过滤器提出了一套两阶段的快速搜索算 于无法直接获取信息的加密标签则可以根据反馈的 法，能够在指定的假阳性误判率的范围内有效降低 加密信息进行跟踪，获得用户的地点信息，综合整理 通信开销与时延.总体来说，RFID的轮询机制基于 就形成了对用户个人信息的盘点，为了保护RFID 时隙ALOHA协议中的伪随机操作来进行轮询，能 用户隐私，一种简单直接的手段便是基于物理方法 够有效避免对标签逐一识别带来的额外开销，但同 的安全保护机制，具体而言，主要包括灭活操作、静 时也存在假阳性误判的效应，系统可以借助相应的 电屏蔽、主动干扰以及阻塞法等. 优化机制来降低假阳性误判的概率 灭活(K1)操作是一种简单暴力的方法，阅读 器通过向标签发送一个指定的PIN码来执行杀死 3 RFID的认证与隐私保护机制 命令，命令执行完后标签就失效了，不再对阅读器的 查询做出回应.显然，完全地让标签失效并不是一个 3.1RFID的安全与隐私问题 合理的解决方案.文献[25]提出可以只让标签中唯 在物联网应用中，对RFID系统实现有效数据 一识别码失效而保留产品类型标识码的数据部分， 管理的前提在于保障RFID数据的安全性与私密 这样就可以避免标签被跟踪，但是该方案使标签失 性.RFD系统的安全威胁主要来自于阅读器对标 去了唯一标识物品的特性，文献[26]提出采用全新 签的非法访问以及伪造标签的存在.对RFID系统 的标识符重新对标签进行标识的方案，原有的标识

462 计 算 机 学 报 制 为进 一 步 的研 究 工作 提供 了一 个 理论基 础 ． 基于上述认识 ，文献E203对 面向大规模标签监 控 应用 中的一 个 重要 问题 进 行 了研 究 ：如 何 在 大 量 标 签 中 快 速 定 位 出 丢 失 的 标 签 ．该 文 利 用 时 隙 ALoHA协议 的伪 随机 性 ，基 于 轮询 机 制 提 出 了多 种协议 ，能够快 速 有效 地定 位 丢失 的标签 ．针 对 由电 池供 电 的大规 模 主 动标 签 实 时 信 息 收 集 的 问 题 ，文 献[21]设 计 了一 套 高效 节 能 的轮 询 协 议．该 协 议 基 于标 签排 序 (Tag—Ordering)的编 码 方 式 ，使 得 所 消 耗 的能量 比通 常 的 轮 询协 议 下 降一 个 数 量 级 ．该 协 议进 一 步 采 用 基 于 分 块 的 布 鲁 姆 过 滤 器 (Bloom Filter)来 提高 轮 询机 制 的性 能 ，在 不 影 响 整 体 扫 描 时 间的前 提下 显 著 降低 了能 耗 ．文 献 [22]针 对 上 述 问题 进 一步 提 出了 基 于单 级 Hash与 多级 Hash的 轮询 机 制 ，显 著地 降低 了信 息 收集 的 时间．文献 [23] 基 于轮 询协议 提 出 了 一套 批 处 理 的认 证 机 制 ，无 需 通过 逐个 识别 的方式来 认 证标 签．通 常情况 下 ，为 了 实现 对 大量标 签 的 认证 ，阅 读 器 需 要对 标 签 逐 一 识 别并认 证 ，这 种 方 式需 要 耗 费 大 量 的通 信 开 销 与 扫 描 时 间．基 于 轮 询 协 议 的伪 随 机 性 ，该批 处 理 认 证 机制 提 出 了一套 快 速 的认 证 算 法 ，能 够极 大地 降低 认证 的扫描 时 间与 通 信 开销 ．由于 该 机制 基 于 时 隙 ALOHA 的 随机 算 法 进 行认 证 ，因此 存 在 假 阳性 误 判 ，但 是 该机 制 能够 以概 率 的形 式 确保 未检 测 到 的 伪造 标 签所 占比例 被 控 制 在指 定 阈值 范 围 内．上 述 研究 工 作 的轮询 机制 都对 应 于扫描 范 围 内的所 有标 签 ，如果 仅需 要对 扫描 范 围 内标 签 的 一个 子集 进 行 轮询 ，这 些机 制将 很 难 适 用 ．因 此 ，针 对 大规 模 标 签 部署 情 况下 搜索 特定 标 签 集 合 的 问题 ，文 献 [24]基 于 布鲁 姆 过 滤 器 提 出 了一 套 两 阶 段 的快 速 搜 索 算 法 ，能够 在 指定 的假 阳性 误 判 率 的范 围 内有 效 降低 通信 开 销 与时延 ．总体 来 说 ，RFID 的轮 询 机 制基 于 时 隙 ALOHA协 议 中 的伪随 机操 作 来 进 行 轮 询 ，能 够 有效 避免 对标 签 逐 一 识 别 带 来 的额 外 开 销 ，但 同 时也存 在假 阳性 误 判 的效 应 ，系 统 可 以借 助 相 应 的 优 化机 制来 降低 假 阳性误 判 的概 率． 3 RFID的认证 与隐私保 护机制 3．1 RFID的 安全 与 隐私 问题 在 物 联 网应 用 中 ，对 RFID 系 统 实 现有 效 数 据 管 理 的前 提 在 于 保 障 RFID 数 据 的 安 全 性 与 私 密 性 ．RFID系统 的 安 全 威 胁 主要 来 自于 阅 读 器 对 标 签 的非 法访 问 以及 伪 造 标 签 的存 在 ．对 RFID 系 统 而言 ，其安 全 问题是 指存 在 伪造标 签 时 ，如 何有 效地 对 标 签进 行认 证 ；其 隐 私 问题 是 指 存 在 恶 意 阅 读器 时 ，如 何 防止 阅读 器对标 签 的非 法访 问 ，来 有效 地保 护用 户 的隐私 ．在 常用 的 网络安 全解 决方 案 中 ，已经 存 在 成熟 的加 解 密 算法 如 DES、AES、RSA、椭 圆曲 线密 码等 ，这些 算 法 构 成 了对 称 密 钥 加 密 以及 公 开 密钥 加密 中的支撑 技 术 ，能够 有 效 地 实 现 加 密 与 鉴 别功 能 ，抵制 非法 读 取 、伪 装 哄 骗 、重 放 攻 击 等 安 全 威胁 ，具 有 良好 的安全 性．但 实 现上述 算 法需要 较 多 的逻 辑 处 理 单 元 ，如 AES需 要 大 约 20000～ 30000 个逻 辑 门 ，RSA、椭 圆 曲线 密码 等公 钥 密码算 法 则需 要更 多 的逻辑 门．而 RFID 标签受 到 低 成本 限制 ，通 常 只能 拥 有 大 约 5000～10000个 逻 辑 门 ，并 且 这 些 逻辑 门主要 用于 实 现 一些 最 基 本 的标 签 功 能 ，仅 剩 少许 可用 于实现 安 全 功 能．此 外 ，RFID标 签 上 的存 储 资源也 非 常 受 限 ，通 常 标 签 的 EPC 区 仅 能 存 储 96bit数 据 ，用户 区仅 能存 储 512bit数 据 ．RFID 标 签极 其有 限的计算 资源难 以支 持上 述 复杂 的加解 密 算法 的实现 ．因此 ，对 RFID 系 统 而 言 ，其 安 全 与 隐 私保 障机制 所 面临 的 最 大挑 战在 于 ：如何 以一 种 轻 量级 的方 式 在资 源极 其受 限 的 RFID 系统 上 实 现认 证 与 隐私保 护协 议 ．下 面 我 们从 基 于 物理 方 法 的安 全保 护 机 制 、基 于 对 称 密 钥 加 密 的协 议 以 及 基 于 Hash函数 的协 议 等几 个 方 面 来 具 体 阐述 相 关 研 究 成 果． 3．2 基 于 物理 方法 的安 全保 护机 制 RFID的 隐私 问题 是 由阅读 器 识别 标 签 时无 需 认 证 引起 的．在 没有 隐私保 障机制 的情 况下 ，阅读器 可 以随意地 对标 签进 行秘 密 扫描 ，获取 标 签信息 ；对 于无法 直接 获取 信 息 的加 密 标签则 可 以根 据反 馈 的 加 密信 息进 行跟 踪 ，获得 用户 的地 点信 息 ，综合 整理 就 形成 了对 用 户 个 人 信 息 的 盘 点．为 了保 护 RFID 用 户 隐私 ，一种 简单 直接 的手 段 便 是 基 于 物理 方 法 的安全 保 护机制 ，具 体 而 言 ，主要 包 括灭 活操 作 、静 电屏蔽 、主动 干扰 以及 阻塞法 等 ． 灭 活 (Kil1)操 作 是 一 种 简 单 暴 力 的方 法 ，阅读 器 通过 向标签 发送 一个 指 定 的 PIN 码 来 执 行 杀 死 命令 ，命令执行完后标签就失效了，不再对 阅读器的 查 询做 出回应 ．显然 ，完 全地 让标 签失 效并 不是 一 个 合理的解决方案．文献 E25]提 出可 以只让标签中唯 一 识别 码 失效 而保 留产 品类 型 标 识 码 的数 据 部 分 ， 这 样 就可 以避 免标 签 被 跟 踪 ，但 是 该 方 案 使 标 签 失 去 了唯一 标识 物 品的 特 性．文 献 E26]提 出采 用 全 新 的标识 符 重新 对标 签 进 行 标 识 的 方 案 ，原 有 的 标 识

3期 谢磊等：RFD数据管理：算法、协议与性能评测 463 符可以在物品被回收等情况下重新被激活使用.由 RFID标签实现有效认证，但却无法保护标签的隐 此来看，灭活操作使标签丧失功能，不可能再被重 私.由于在步骤1标签需要事先将标识号T:发送至 用，从而阻止对标签的任意读取和跟踪；而需要考虑 阅读器，所有邻近的阅读器都能够读取该标识信息， 到重用的场合可以采取休眠(Sleep)机制[2]，原理与 这种方式完全暴露了标签的隐私；另一方面，如果不 前者相似，但是实施休眠机制的标签可以被唤醒再 发送标识号T:,则阅读器很难迅速地定位到对应的 次使用，静电屏蔽是指将标签放人具有静电屏蔽功 密钥：来支持后续操作.为了在实现认证的同时保 能的容器中，使其不能与外界进行电磁耦合，阻止标 障隐私，事实上存在一种简单直接但性能低下的方 签被扫描，这种方法需要一个额外的物理设备，如法 法：相比于算法1，标签无需传输标识T:,而是直接 拉第网罩.主动干扰是指通过一个设备主动广播干 根据接收的挑战数R发送加密密文C=E[R].阅 扰信号来阻止或破坏附近的非授权阅读器对标签的 读器接收到加密密文C后，在本地遍历所有可能的 读写操作.文献[27]提出了一套基于掩码的主动干 k:计算C,=E,[R],如果存在某个，使得C:=C,则 扰机制.当阅读器在读取标签ID时，标签周围的保 通常情况下该密钥对应的标签即为当前认证的标签. 护设备会同时传输一串掩码序列信号，最终阅读器 假设搜索空间存在n个标签，该算法密钥搜索的时间 接收到标识符ID与掩码相混杂的信号.这种机制 复杂度为O(n),当n数值很大时，其搜索时间开销是 使得授权的阅读器能够使用该掩码序列有效恢复标 巨大的，针对上述问题，很多研究工作开始关注于如 签的标识符，而未授权的阅读器由于无法获取该掩 何根据加密密文进行快速的数据搜索.文献[30]提出 码序列的模式，从而无法对接收的混杂信号进行有 了基于对称密钥的加密数据搜索系统.文献[31-32] 效恢复.阻塞法采用一个特殊的阻止标签，通过设定 也提出了基于加密数据库的查询系统.我们也在该 的标签冲突算法来阻止未授权的阅读器读取那些受 方面开展了研究工作，文献[33]通过在标签上维护 保护的标签.文献[28]提出了上述阻止标签的理念， 一个单调增的计数器，从而利用二叉搜索方案来进 通过编入标签的可修改位来保护隐私，若隐私位为 行快速的搜索，将时间复杂度降低至O(logn), ‘0'表示可公开扫描，为‘1’则表示是私有区域.当阅 在基于对称密钥加密协议中，当密钥k:的长度 读器访问私有区域时，采用一个特殊的阻止标签来 足够大时（不小于128位），仅仅根据比特串R和C 实行干扰，从而阻止未授权的阅读器非法读取受保 是很难在短时间内使用普通的计算设备推算出密钥 护的标签. :的，协议安全性高.但是，由于RFID标签成本的 33基于对称密钥加密的协议 限制，标签内部存储单元通常少于512bit,逻辑门的 公开密钥加密算法虽然功能强大，能够有效地 数目也相当受限，实际使用在RFID系统中的比特 实现加密、电子签名等机制，但由于其复杂的计算操 串R和C以及密钥k,的长度都远小于达到正常安 作使其根本无法在资源异常受限的RFID系统上实 全标准所期望的数目.例如，德州仪器公司研发了用 现.因此，RFID系统往往借助于逻辑较为简单的对 于汽车防盗系统中的加密RFID标签，出于标签成 称密钥加密算法来实现安全与隐私保障机制.具体 本的考虑，挑战数R与密钥k:的长度仅为40bit,标签 来说，基于对称密钥加密的协议可以用来对标签进 响应结果C仅为24bit.在这种情况下完全可以通 行有效认证.在该协议中，任一标签与阅读器共享一 过逆向工程、密码破解等技术来破解该加密系统.针 个对称密钥.算法1阐述了使用对称密钥加密算法 对上述问题，研究者们提出了各种轻量级解决方案 对RFID标签进行认证的过程2]， 来保障安全性.其中，DESL3是在传统的加密协议 算法1.使用对称密钥加密算法对RFID标 DES基础上为适应.小型计算设备（如RFID标签）要 签进行认证 求的一种轻量级的扩展，是一套超低成本的加密算 1.标签向阅读器发送数值T,表明身份 法.HIGHT[35]是一种分组加密算法，它使用64位 2.阅读器生成一个随机的比特串R,发送至标签。 的分组块和128位的密钥，子密钥只在加密和解密 3.标签用密钥.：对比特串R进行加密，计算C= 的运行过程中被生成，对硬件资源的要求很低， E.[R],将C发送至标签， 3.4基于Hash函数的协议 4.阅读器本地计算C=E,[R],验证是否有C=C,若 相比于对称密钥加密协议，采用Hash函数可 是，则标签被成功认证 以在多数情况下实现等效的安全机制，且实现逻辑 上述基于对称密钥加密的协议虽然能够对 会大为简化.因此，近年来很多研究工作关注于在

3期 谢 磊等 ：RFID数据管理 ：算法 、协议 与性 能评 测 463 符 可 以在物 品被 回收 等 情况 下 重新 被 激 活 使 用．由 此 来看 ，灭 活 操 作 使 标 签 丧 失 功 能 ，不 可 能再 被 重 用 ，从 而 阻止对标 签 的任 意读 取和 跟踪 ；而需 要考 虑 到 重用 的场 合可 以采 取休 眠 (Sleep)机制 [2 ，原 理与 前 者相 似 ，但 是 实施 休 眠 机 制 的 标 签 可 以被 唤 醒 再 次 使用 ．静 电屏蔽 是 指 将 标 签 放 人具 有 静 电屏 蔽 功 能的容器中，使其不能与外界进行电磁耦合 ，阻止标 签 被扫 描 ，这 种方 法需 要一 个额 外 的物 理设备 ，如 法 拉第 网罩．主动 干扰 是 指 通 过 一个 设 备 主 动 广 播 干 扰信号来 阻止或破坏附近的非授权阅读器对标签的 读 写操作 ．文 献 [-27]提 出了 一 套基 于掩 码 的主 动 干 扰机 制 ．当阅读器 在读 取标 签 ID 时 ，标签 周 围 的保 护设 备会 同时传 输 一 串掩 码 序 列 信 号 ，最 终 阅 读 器 接 收到标 识 符 ID 与 掩 码 相 混 杂 的 信 号 ．这 种 机 制 使得授权 的阅读器能够使用该掩码序列有效恢复标 签 的标识 符 ，而未 授 权 的 阅读 器 由 于无 法 获 取 该掩 码序 列 的模式 ，从 而 无 法对 接 收 的混 杂 信 号 进 行有 效恢 复．阻塞 法采 用一个 特 殊 的阻止 标签 ，通 过设定 的标 签 冲突算 法来 阻止 未授 权 的 阅读 器读 取那 些受 保护 的标 签．文献 [-281提 出 了上 述 阻止标 签 的理念 ， 通过 编人 标签 的 可修 改 位 来 保 护 隐 私 ，若 隐 私位 为 ‘0’表 示 可公 开扫 描 ，为 ‘l’则表示 是 私有 区域 ．当阅 读 器访 问私有 区域 时 ，采用 一 个 特 殊 的阻 止标 签 来 实行 干扰 ，从 而阻 止 未授 权 的 阅读 器 非 法 读 取受 保 护 的标 签 ． 3．3 基 于对 称密 钥加 密的 协议 公 开密 钥 加 密算 法 虽 然 功 能强 大 ，能 够 有效 地 实现加 密 、电子 签名 等机 制 ，但 由于其 复杂 的计 算操 作 使其 根本 无法 在 资源异 常 受 限 的 RFID系 统上 实 现．因此 ，RFID 系统往 往 借 助 于逻 辑 较 为 简单 的对 称 密钥 加 密算法 来 实 现 安 全 与 隐 私保 障机 制 ．具 体 来 说 ，基 于对称 密钥 加 密 的协 议 可 以用来 对 标 签 进 行 有效 认证 ．在 该协 议 中 ，任 一标 签与 阅读器 共 享一 个对称密钥．算法 1阐述 了使用对称密钥加密算法 对 RFID标 签进 行认证 的过程 _2． 算法 1． 使用对称密 钥加密算 法对 RFID标 签 进行 认证 ． 1．标签 向阅读 器发送 数值 表 明身份 ． 2．阅读器生成一 个随机的 比特 串 R，发送至标签． 3．标 签 用 密 钥 k对 比 特 串 R 进 行 加 密 ，计 算 C— Ek[R]，将 C发送至标签 ． 4．阅读器本地计算 C 一 [R]，验证 是否有 C—C ，若 是 ，则标 签被成功认证． 上述基 于 对称 密 钥 加 密 的 协议 虽 然 能 够 对 RFID标签 实 现 有 效 认 证 ，但 却 无 法 保 护 标 签 的 隐 私．由于在 步骤 1标 签需要 事 先将 标 识 号 T 发 送 至 阅读器 ，所 有邻 近 的阅读器 都 能够读 取该 标识 信息 ， 这 种方 式完 全暴 露 了标签 的 隐私 ；另 一方 面 ，如果不 发 送标 识号 T ，则 阅读 器很 难迅 速 地定 位 到 对应 的 密 钥 k来 支持 后续 操 作．为 了 在实 现 认 证 的 同 时保 障隐私 ，事 实上存 在 一 种 简 单 直接 但 性 能 低 下 的方 法 ：相 比于算 法 1，标 签 无需 传 输 标 识 ，而 是直 接 根据接收的挑战数 R发送加密密文 C—E [R]．阅 读 器接 收到 加密 密文 c后 ，在 本 地 遍历 所 有 可 能 的 忌计 算 C —Ek[R]，如果 存 在某个 k使 得 C 一C，则 通 常情 况下该密钥 对应 的标签 即为 当前认证 的标签 ． 假设搜 索空 间存 在 个标签 ，该 算法密 钥搜索 的时 间 复杂度 为 0()，当 n数值很 大时 ，其 搜索 时间 开销是 巨大 的．针对上 述 问题 ，很 多研 究 工作 开 始关 注 于如 何根据加密密文进行快速的数据搜索．文献[301提出 了基于对称密钥 的加密数据搜索系统．文献1-31—321 也 提 出了基 于加 密数 据 库 的查 询 系统 ．我们 也 在 该 方 面开展 了研 究 工作 ，文 献 [-331通 过 在标 签上 维 护 一 个 单 调增 的计 数器 ，从 而 利 用 二 叉搜 索方 案 来 进 行快 速 的搜 索 ，将 时 间复杂 度降低 至 O(1og，z)． 在基 于对 称密 钥 加 密协 议 中 ，当密 钥 k的长 度 足够 大 时 (不 小于 128位 )，仅仅 根 据 比特 串 R 和 C 是很 难在 短 时间 内使用 普通 的计算 设 备推算 出密 钥 k。的，协议安全性高．但是 ，由于 RFID标签成本的 限制 ，标 签 内部 存储 单元 通 常少 于 512bit，逻 辑 门的 数 目也相 当受 限 ，实 际使 用 在 RFID 系 统 中 的 比特 串 R 和 c 以及 密 钥 k的 长度 都 远 小 于 达 到 正 常 安 全标 准所 期望 的数 目．例 如 ，德州仪 器公 司研 发 了用 于汽 车 防 盗 系 统 中的 加 密 RFID标 签 ，出于标 签 成 本 的考 虑 ，挑战数 R与密钥 k的长度仅为 40bit，标 签 响应结 果 C仅 为 24bit．在 这 种 情 况 下 完 全 可 以 通 过逆 向工 程 、密 码破 解等 技术来 破 解该 加密 系统．针 对上述 问题 ，研究者们提 出了各种轻量级解决方案 来保障安全性．其中，DESL[3]是在传统的加密协议 DES基 础上 为适应 小 型计算 设备 (如 RFID标 签)要 求 的一 种轻 量级 的扩 展 ，是 一 套超 低 成 本 的加 密算 法 ．HIGHTl_3。。是 一 种 分 组 加 密 算 法 ，它 使 用 64位 的分组 块 和 128位 的密钥 ，子 密钥 只在 加 密 和解 密 的运行过程 中被生成 ，对硬件资源的要求很低． 3．4 基 于 Hash函数的协 议 相 比于对称 密钥加密协议，采用 Hash函数可 以在多数情况下实现等效 的安全机制，且实现逻辑 会 大为 简化 ．因此 ，近 年 来 很 多 研 究 工 作 关 注 于 在

464 计算 机 学 2013年 RFID系统中采用基于Hash函数的协议来实现一 多次扫描标签，使得标签与阅读器之间失去同步，导 套足够轻量级的安全与隐私保障机制.尽管Hash 致阅读器在认证时无法设定每个可能的标签ID需 函数的逻辑实现已经相对简单，但是由于RFID标 要的计算次数，使系统无法正常工作。 签的资源稀缺性，Hash函数的常用逻辑实现还是 表3对上述3种方案从效果、适用范围以及标 超出标签的资源限制.为此，需要确保实现Hash函 签所需资源3个方面进行了具体的比较.可以看出， 数的逻辑电路足够简单.研究发现[2o],Hash数值可 3种方案各有利弊，需要根据具体的应用需求与资 以从一个预先存储的随机比特序列中推导：首先，使 源限制条件来选择合理的安全与隐私保障方案，目 用离线的随机数生成器以标签ID为种子生成一个 前，国内的研究者们也在RFID的安全与隐私保障 200bit的随机序列，将其存储在标签内部；该比特 方面开展了深入的研究.文献[39]分析了已有的各 序列首尾相连形成一个逻辑上的环结构：当执行 种RFID安全机制，重点介绍了基于密码技术的 Hash操作H(ID,r)时，即在上述环结构序列中返 RFID安全协议，分析了这些协议的缺陷，讨论了基 回第个比特以后一串指定长度的比特序列.这样， 于可证明的安全性理论来设计和分析RFID安全协 200个随机比特组成的序列可以返回200个不同的 议的模型和方法.文献[40]定义了供应链环境下 Hash数值，在通常情况下足够满足一般的应用 RFID通信协议必须满足的安全需求，提出了一个 需求， 可以满足这些安全需求的通用可组合安全模型， 基于Hash函数的安全协议主要包括Hash 设计了一个可以实现该模型的轻量级RFID通信 Lock协议、随机化Hash-Lock协议以及Hash链协 协议。 议等.Hash-Lock协议[3们使用了metaID(标签密钥 的Hash值)代替真实的标签ID,来有效地对阅读 表33种方案的比较 效果 适用范围 标签所需资源 器进行认证，从而避免标签信息泄露.然而，由于 基于物理方标签实现逻辑非常适用于对处理能对标签的资源要 metaID对特定的标签始终保持不变，因此标签每次 法的安全保简单，不需要标签力非常有限的被求非常低，需要 护机制 自身实现安全与隐动标签进行安全额外的设备提供 响应都使用固定的metaID,容易受到追踪和重放攻 私保障 保护的场合 安全隐私保障 击.随机化Hash-Lock协议[3]采用了基于随机数的 基于对称密标签实现逻辑较适用于主动标签对标签资源要 询问/应答机制：在阅读器请求访问标签时，标签先 钥加密的为复杂，能有效实或处理能力较强求较高 协议 现加密、解密操作 的被动标签需要 用伪随机数生成器生成一个随机数R,然后计算其 进行加密，解密 的场合 ID和R的Hash值Hkey(ID‖R),最后将随机数R 基于Hash 标签实现逻辑较适用于处理能力对标签的资源 与该Hash值发送给阅读器.阅读器在后台数据库 函数的协议为简单，具有“前向较弱的被动标签要求低 中进行穷举搜索，计算所有ID和R的Hash值 安全性”，不能实需要认证的场合 现加密、解密操作 Hke(ID‖R),将匹配成功的ID发送给标签，实现 解锁，上述这种方式能够避免标签每次响应固定模 3.5 其它解决方案 式的信息，故而不能对其进行跟踪.但是，随机化 近年来，为了更有效地防止针对RFID系统的 Hash-Lock协议不能防止重放攻击.攻击者完全可以 黑客攻击，一些研究者开始关注入侵检测系统在 窃听随机数R以及对应的Hash值Hkey(ID‖R), RFID系统中的应用.由于RFID标签处理能力非常 从而在阅读器查询时重放该响应伪装为该标签，其 有限，不可能在标签上实现人侵检测的逻辑.因此， 次，阅读器端的穷举搜索使得该方法缺乏很强的可 文献[41]基于小理电池装置设计了一套RFID守护 扩展性.Hash链协议[3s]是基于共享秘密的询问/应 系统.该系统集成了多种安全机制，包括密钥管理、 答协议，在该协议中，标签和阅读器共享两个Hash 访问控制、认证以及审计功能，尽管集成了多种安全 函数G和H以及一个随机的初始化标识符s1.当阅 功能，该系统却很容易出现单点失效的问题：一旦守 读器请求访问标签时，标签返回当前标识符一 护系统被攻克，整个RFID网络都被暴露在各种攻 G(s),同时更新当前标识符为5t+1=H(5).阅读器 击隐患之下.文献[42]进一步提出了一个人侵检测 根据获得的r值查找数据库对标签进行认证，并更 系统模型Deckard,用来检测标签所有权的改变.该 新s值与标签保持同步.该方法利用Hash函数的 系统是RFID入侵检测系统的早期研究工作之一. “前向安全性”使得标签响应的结果随每次查询不停 文献[43]基于RFID系统设计了一套入侵检测系统 更新，有效防止了重放攻击.但是，攻击者可以恶意 安全框架，在RFID阅读器层面以及中间件层面实

464 计 算 机 学 报 RFID 系统 中采 用 基 于 Hash函数 的协 议 来 实 现 一 套足 够轻 量 级 的 安 全 与 隐 私 保 障机 制．尽 管 Hash 函数 的逻 辑实 现 已 经相 对 简单 ，但 是 由于 RFID 标 签 的资 源稀 缺 性 ，Hash函数 的 常 用 逻 辑 实 现 还 是 超 出标 签 的资源 限制 ．为 此 ，需要 确 保 实 现 Hash函 数 的逻辑 电路足 够简 单．研究 发 现 _2 ，Hash数值 可 以从 一个 预 先存 储 的随机 比特 序列 中推导 ：首先 ，使 用离 线 的 随机数 生成 器 以标 签 ID 为种 子 生 成一 个 200bit的随机 序 列 ，将 其 存 储 在 标 签 内部 ；该 比特 序列 首 尾 相 连 形 成 一 个 逻 辑 上 的 环 结 构 ；当 执 行 Hash操作 H(ID，r)时 ，即在 上 述 环 结 构 序 列 中返 回第 r个 比特 以后 一 串指定 长度 的 比特 序列 ．这 样 ， 200个 随机 比特组 成 的序列 可 以返 回 200个 不 同 的 Hash数值 ，在 通 常 情况 下 足 够 满 足 一 般 的应 用 需求 ． 基 于 Hash函 数 的 安 全 协 议 主 要 包 括 Hash— Lock协议 、随机化 Hash—Lock协 议 以及 Hash链协 议 等．Hash—Lock协议 _3明使 用 了 metaID(标 签 密钥 的 Hash值 )代 替 真 实 的标 签 ID，来 有 效 地 对 阅读 器 进 行 认 证 ，从 而 避 免 标 签 信 息 泄 露．然 而 ，由 于 metaID 对 特定 的标 签始 终保 持 不变 ，因此标 签每 次 响应都 使用 固定 的 metaID，容 易受 到追 踪和 重放 攻 击 ．随 机化 Hash—Lock协议 [3采 用 了基 于随 机数 的 询 问／应答机制 ：在 阅读器请求访 问标签时，标签先 用 伪 随 机数 生 成 器 生 成一 个 随 机 数 R，然 后 计 算 其 ID 和 R 的 Hash值 Hkev(ID llR)，最 后将 随 机 数 R 与该 Hash值 发送 给 阅读 器．阅读 器 在 后 台数 据 库 中进 行 穷 举 搜 索 ，计 算 所 有 ID 和 R 的 Hash值 Hkev(IDllR)，将 匹配成功 的 ID发送给标 签 ，实现 解 锁 ．上述 这种 方 式 能 够避 免 标 签 每 次 响 应 固定 模 式 的信 息 ，故而 不能 对其进 行跟踪．但是 ，随机 化 Hash—Lock协议 不能防止 重放攻击 ．攻 击者完全 可 以 窃听随机数 R 以及 对应 的 Hash值 Hkev(ID 1lR)， 从 而 在 阅读器 查 询 时重 放 该 响 应 伪 装 为 该 标 签．其 次 ，阅读 器端 的穷 举 搜 索使 得 该 方法 缺 乏 很 强 的可 扩展 性 ．Hash链 协议 8]是 基 于共 享 秘 密 的询 问／应 答协 议 ，在该 协议 中 ，标 签 和 阅读 器 共 享 两 个 Hash 函数 G和 H 以及 一个 随 机 的初始 化标 识符 s．当 阅 读器请 求访 问标签 时，标 签返 回当前标识 符 — G(s)，同时更新 当前标识符为 +一H(s)．阅读器 根据 获 得 的 值查 找 数 据 库对 标 签 进 行 认 证 ，并 更 新 s值与标签保持 同步．该方法利用 Hash函数 的 “前 向安全性”使得标签响应的结果随每次查询不停 更新 ，有 效 防止 了 重放 攻 击 ．但 是 ，攻 击 者 可 以 恶 意 多次 扫 描标签 ，使 得标 签与 阅读 器之 间失去 同步 ，导 致 阅读 器在认 证 时无 法设 定 每个 可 能 的 标签 ID 需 要 的计算 次数 ，使 系统 无法 正 常工作 ． 表 3对 上 述 3种 方 案从 效 果 、适 用 范 围 以及 标 签所 需 资源 3个 方 面进行 了具 体 的 比较 ．可 以看 出 ， 3种 方 案 各 有 利 弊 ，需 要 根 据 具 体 的应 用 需 求 与 资 源 限制 条件来 选 择 合 理 的安 全 与 隐私 保 障 方 案．目 前 ，国内 的研 究 者 们 也 在 RFID 的安 全 与 隐私 保 障 方 面开 展 了深入 的研 究 ．文献 [39]分 析 了 已有 的各 种 RFID 安 全 机 制 ，重 点 介 绍 了 基 于 密 码 技 术 的 RFID安全 协议 ，分 析 了这 些 协 议 的 缺 陷 ，讨 论 了基 于可证 明 的安全 性理 论来 设计 和 分 析 RFID安 全协 议 的模 型 和 方 法 ．文 献 E403定 义 了 供 应 链 环 境 下 RFID通 信 协议 必 须 满 足 的 安 全 需 求 ，提 出 了一 个 可 以满足这些 安全 需求 的通用 可组 合安 全模 型 ， 设 计 了 一 个 可 以 实 现 该 模 型 的 轻 量 级 RFID通 信 协 议． 表 3 3种 方 案 的 b 较 效果 适用范 围 标签所需资源 基于物理方 标签实现逻辑非常 适用于对处理能 对标签的资源要 法 的安全保 简单，不需要 标签 力非常有 限的被 求非 常 低，需 要 护机制 自身实现安全与隐 动标签进行安全 额外的设备提供 私保障 保护的场合 安全隐私保障 基于对称密 标签 实 现 逻 辑 较 适用于主动标签 对标 签 资 源 要 钥 加 密 的 为复杂 ，能有 效实 或处理能力较强 求较 高 协议 现加密 、解密操作 的被动标签需要 进 行 加 密 、解 密 的场合 基于 Hash 标签 实 现 逻 辑 较 适用于处理能力 对标 签 的 资 源 函数 的协议 为简单 ，具有“前 向 较弱的被动标签 要求低 安 全 性”，不 能 实 需要认证的场合 现 加 密 、解密 操 作 3．5 其 它解 决方 案 近年 来 ，为 了更 有 效 地 防 止 针 对 RFID 系 统 的 黑客 攻 击 ，一 些 研 究 者 开 始 关 注 入 侵 检 测 系 统 在 RFID 系统 中 的应 用 ．由于 RFID标 签处 理 能力 非常 有 限 ，不 可能 在标 签 上 实 现 入 侵 检 测 的 逻辑 ．因 此 ， 文献 [41]基 于小 型 电池装 置设 计 了一 套 RFID守 护 系统 ．该 系统 集成 了 多种 安 全 机 制 ，包 括 密 钥 管 理 、 访问控制 、认证以及审计功能 ，尽管集成了多种安全 功能，该系统却很容易出现单点失效的问题 ：一旦守 护系统被攻克，整个 RFID 网络都被暴露在各种攻 击隐患之下．文献[42]进一步提出 了一个入侵检测 系 统模 型 Deckard，用来 检测 标 签 所 有 权 的改 变 ．该 系统是 RFID入 侵 检 测 系 统 的 早 期 研 究 工 作 之 一 ． 文献E435基于 RFID系统设计了一套入侵检测系统 安 全框 架 ，在 RFID 阅读 器 层 面 以及 中 间件 层 面 实

3期 谢磊等：RFID数据管理：算法、协议与性能评测 465 现了入侵检测的功能.该系统利用阅读器之间的通 (4)标签的分布与部署.对阅读器的发射功率而言， 信来获取攻击检测所需的审计信息，将RFD阅读 功率过小，阅读器有效通信范围减小，使得某些标签 器作为“看门狗”来从周围的阅读器与标签中收集所 无法被激活，或者由于反射信号能量过小，低于信噪 需信息，提供了一套更为泛化的安全框架来检测多 比从而使阅读器无法有效识别；功率过大，阅读器有 样化的RFID攻击.总体说来，随着RFID的进一步 效通信范围增大，使得某些标签反射的信号能量增 广泛应用，RFID系统的入侵检测方案将会受到越 大，导致标签之间的信号干扰增大.对能量吸收、路 来越多的关注。 径损耗、多径效应而言，这三者都会引起信号衰弱， 大幅度降低发射信号到达标签的能量以及反射信号 4 真实环境下RFID系统的 到达阅读器的能量，导致信号难以识别，对信号干扰 性能评测与分析 而言，标签与标签之间、标签与阅读器之间、阅读器 与阅读器之间都存在发射/反射信号的干扰，导致 很多RFID的前期研究工作主要考虑在相对理 比特差错，降低传输效率.对标签的分布与部署而 想的传输环境下如何对RFID数据收集算法与协议 言，标签部署过于密集，会导致阅读器的发射能量 参数进行优化，并通过模拟实验来验证其性能.事实 被充分稀释，并且反射信号间的干扰与能量吸收 上，对于RFID系统而言，真实传输环境中的一些物 会加剧：过于稀疏会导致其超出阅读器扫描范围； 理因素包括路径损耗、能量吸收、信号干扰等给物理 而对于单个标签，如果标签平面（即标签天线方向） 层的信号传输带来了极大的不可靠性，由此对基于·与能量穿透方向平行，则无法产生足够强度的反射 防冲突算法的RFID数据收集机制的性能也带来了 信号，应使标签平面与能量穿透方向尽可能正交，表 很大的影响.具体说来，真实传输环境下影响RFD 4具体阐述了这些因素对RFID系统具体性能参数 系统性能的关键因素包括：(1)阅读器的发射功率； 的影响，包括RFID系统的扫描范围、阅读速率以及 (2)能量吸收、路径损耗、多径效应；(3)信号干扰； 能量消耗。 表4关键因素对系统性能各指标的影响 扫描范围 阅读速率 能址消耗 阅读器的发射 功率过小，阅读器有效通信范围域 功率过小，使得某些标签无法被激活或有效 功率过小，能量消耗小：功率过大， 功率 小：功率过大，阅读器有效通信范围 识别，降低阅读速率，功率过大，使得部分标 能量消耗大 增大 签反射信号强度增大，导致标签间信号干扰 增大，降低阅读速率 能量吸收、路径 会！起信号衰减，诚小阅读器有效使得正常通信范围内某些标签无法被徽活或 使得阅读器必须要增加功率来补偿 损耗、多径效应 通信范围 有效识别，降低阅读速率 传输中信号能量损失，增加能耗 信号干扰 某些标签反射信号会受到干扰无法 导致传输比特差错，降低阅读速率 阅读器需要合理湖整功率来避免过 被有效识别，阅读器有效通信范围 多信号干扰，会改变阅读器能量 减小 消耗 标签的分布与 标签的密集部署会影响阅读器天线 如果使标签天线方向与能量穿透方向尽可能标签分布部署不合理会使得阅读器 部署 的电磁场分布，改变阅读器有效通 正交，读取效率增大，阅读速率提升，否则，阅 必须要增加功率来提升反射信号强 信范固 读速率下降 度，增加能耗 上述因素在真实传输环境下的普遍存在性使得 性能，并且由于物理层与MAC层没有进行有效整 理想情况下推导出的算法与优化参数在实际情况下 合，导致明显的性能下降.文献[46]利用简单、经验 的性能很难得到保障.因此，目前该领域的很多研究 性的实验手段验证了当前RFID系统识别标签的各 工作者关注在真实应用环境下对RFID系统实际性 项性能参数，作者通过在不同的传输环境下（包括自 能的测试与分析.为了说明物理层差错对EPC 由空间、接近水、接近金属环境)，改变通信距离检验 C1G2RFID系统的影响，文献[44]给出了模拟实验 了各项性能参数.文献[47]针对RFID系统给出了 结果，证明了物理层的比特差错极大地降低了系统 一个综合的性能基准，通过这些基准能够描述在真 的整体性能.文献[45]在真实环境设置下检验了 实环境下RFID系统的运作效率.文献[48]在真实 RFID系统的读取性能，确定了导致整体性能和可 环境设定下对RFID系统性能进行了验证，发现在 靠性降低的物理层因素.他们发现物理层实际的环 阅读器的有效探测范围内存在两个不同的区域：主 境参数以及相关配置参数的设置极大地影响了读取 探测区域和次探测区域.主探测区域是指靠近读取

3期 谢 磊等 ：RFID数据管理 ：算法 、协议 与性能评测 465 现 了入侵 检测 的 功能 ．该 系统 利 用 阅读 器 之 间 的通 信来 获取攻 击 检 测 所 需 的审 计 信 息 ，将 RFID 阅读 器作 为“看 门狗”来 从周 围的阅读 器 与标签 中收集所 需信 息 ，提供 了一 套 更 为泛 化 的安 全 框 架 来 检测 多 样化 的 RFID攻 击．总体 说 来 ，随 着 RFID 的进一 步 广泛应用，RFID系统 的入侵检测方 案将会受到越 来越 多 的关 注． 4 真 实环境 下 RFID系统的 性 能评测 与分析 很 多 RFID的前期 研究 工作 主要 考 虑 在相 对 理 想 的传 输环 境下 如何 对 RFID数 据 收集 算 法 与协 议 参 数进 行优 化 ，并通过 模 拟实验 来 验证其 性 能．事 实 上 ，对 于 RFID 系统而 言 ，真实传 输 环境 中的 一些 物 理 因素包括路径损耗 、能量吸收、信号干扰等给物理 层的信号传输带来 了极大的不可靠性 ，由此对基于 防冲 突算法 的 RFID数 据 收集机 制 的性 能 也 带来 了 很 大 的影 响．具 体 说来 ，真实 传 输 环境 下 影 响 RFID 系统性 能 的关键 因素包 括 ：(1)阅读 器 的发 射 功 率 ； (2)能量 吸 收 、路径 损 耗 、多径 效 应 ；(3)信 号 干 扰 ； (4)标签 的分 布与 部 署．对 阅读 器 的发射 功 率 而 言 ， 功率 过小 ，阅读 器 有效通 信 范 围减 小 ，使得某 些标 签 无法被激活 ，或者 由于反射信号能量过小 ，低于信噪 比从 而使 阅读 器无 法有 效识 别 ；功 率过 大 ，阅读器 有 效通 信 范 围增 大 ，使 得某 些 标 签 反 射 的 信 号 能量 增 大 ，导致标签之间的信号干扰增大．对能量 吸收、路 径损耗 、多径效应而言 ，这三者都会引起信号衰弱 ， 大幅度降低发射信号到达标签的能量 以及反射信号 到达阅读器的能量 ，导致信号难 以识别．对信号干扰 而言，标签与标签之间、标签与阅读器之 间、阅读器 与 阅读 器之 间都 存 在 发 射 ／反 射 信 号 的干 扰 ，导 致 比特差 错 ，降低传输效 率．对标签 的分布与部署而 言 ，标签 部 署 过 于 密 集 ，会 导 致 阅读 器 的 发 射 能 量 被充分稀释 ，并且 反射信 号间 的干扰 与能量 吸收 会 加 剧 ；过 于稀疏 会 导 致 其 超 出阅 读 器 扫 描 范 围 ； 而对 于 单个 标 签 ，如 果标 签 平 面 (即标 签 天 线方 向) 与能量 穿 透方 向平 行 ，则 无 法 产 生 足够 强 度 的 反射 信号 ，应使标签平面与能量穿透方向尽可能正交．表 4具 体 阐述 了这 些 因素 对 RFID 系统 具体 性 能 参 数 的影 响 ，包 括 RFID 系统 的扫描 范 围 、阅读 速率 以及 能量 消耗 ． 表 4 关键 因素对 系统性 能各 指标 的影响 上述 因素在真实传输环境下的普遍存在性使得 理想 情况 下推 导 出的算 法 与优化 参数 在实 际情 况下 的性 能很 难得 到保 障．因此 ，目前 该 领域 的很 多研究 工作 者关 注在 真 实应用 环境 下对 RFID 系统 实 际性 能 的测 试 与 分 析 ．为 了 说 明 物 理 层 差 错 对 EPC— CIG2RFID 系统 的影 响 ，文 献 [44]给 出 了模 拟 实 验 结果 ，证 明 了物理 层 的 比特 差 错 极 大 地 降 低 了 系统 的整体性 能．文献 E45]在 真实环 境设 置下检 验 了 RFID系统的读取性 能，确定 了导致整 体性能和可 靠性降低的物理层 因素．他们发现物理层 实际的环 境参数以及相关配置参数的设置极大地影响了读取 性 能 ，并 且 由于物 理 层 与 MAC层 没有 进 行 有 效 整 合 ，导致明显的性能下 降．文献 E46]利用简单、经验 性 的实验 手段 验证 了当前 RFID 系统 识别 标签 的各 项性能参数 ，作者通过在不同的传输环境下(包括 自 由空 间 、接近 水 、接 近金 属环 境)，改 变 通信距 离检 验 了各项性能参数．文献[47]针对 RFID系统给出 了 一 个综合 的性能基 准，通过这些基准能够描述在真 实环境下 RFID系统的运作效率．文献 E48]在真实 环境设定下对 RFID系统性能进行了验证 ，发现在 阅读器的有效探测范 围内存在两个不 同的区域：主 探测区域和次探测 区域．主探测区域是指靠近读取

466 计算机学 报 2013年 器的一段探测区域，在该区域内具有很高的标签识 传感网定位等.其中，GPS定位与蜂赛基站定位主 别概率（接近100%）：次探测区域是指从主探测区 要用于室外定位，WLAN定位、传感网定位主要用 域末端延伸至有效识别范围边缘的一段探测区域， 于室内定位，RFD定位技术以低成本、非接触性 在该区域内标签识别率依照线性关系降低为0.文 通信等特点，有望成为室内定位技术的首选，目前 献[49-50]研究了在真实传输环境下阅读器发射功 的室内定位系统大多基于RSSI(Received Signal 率对大规模标签识别性能的影响，通过实验发现， Strength Indicator)来辅助定位，其基本原理是：已 RFID标签在激活状态与非激活状态之间存在一个 知发射信号的强度，接收方根据接收到的信号强度， 中间状态(Lossy State),对识别性能影响很大.由此 估算出通信双方的距离.而在实际情况下，无线信号 作者提出了自动功率调节算法，进一步降低了阅读 在空间传播时能量的衰减不仅受传播距离的影响， 器的总体能耗与扫描时延.文献[51]通过真实实验 还受到多径效应、传播的方向性、复杂的室内结构、 发现，当阅读器功率被调整至合理范围时，可以利用 随机流动的人员等诸多不确定因素的影响，利用 遏止效应(Capture Effect)来有效地将冲突时隙转 RSSI作为位置感知数据进行室内定位存在较多的 化为单时隙，由此提出了渐进的扫描算法来优化读 困难.但是由于RSSI极易获取，不需要额外的设 取性能.文献[52]提出了无源RFID系统中能量有 备，相比于其它定位技术成本非常低，因此当前主流 效的物理层设计方法，在前向链路中为使标签获得 的RFID定位技术都是基于RSSI进行定位.其中比 更多能量，结合ASK调制提出了一种新的用于无 较典型的代表是SpotON系统与LANDMARC系 源RFID系统的能量有效的数据编码方法.上述研 统.SpotON系统s基于阅读器与目标标签构造了 究成果表明，RFID在MAC层、应用层方面的研究 一个无线感知环境，通过聚合算法减少信号强度误 需要充分结合物理层的实际传输特性；否则，理想情 差，并利用信号传播模型求解阅读器与目标标签的 况下设计出的算法与协议将与实际的情况严重不 距离，最后利用三角定位算法对目标在三维空间进 符，无法达到预期的性能要求. 行定位.整体而言，SpotON是一个实验性的原型系 总体来说，为了有效避免或降低物理环境因素 统，无论是距离估计还是误差处理都停留在比较粗 对系统性能各指标的影响，目前的有效方法主要包 糙的阶段.LANDMARC系统s]在已知位置引入参 括以下几个方面：(1)调整阅读器功率.通过合理调 考标签，通过对比目标标签与参考标签的RSSI值， 整阅读器功率，补偿信号衰减的同时有效避免干扰， 来确定物理坐标关系，最终确定目标标签坐标. 优化系统性能：(2)优化协议参数.设置优化的协议 LANDMARC通过将参考标签部署到实际应用场 参数（如帧长、传输速率）来优化读取性能；(3)规划 景中，实时同步地对参考标签和目标标签进行能量 部署方案.通过调整标签的部署位置、方向以及增 值测算，可以最大限度减少多径效应以及电离体对 加冗余标签的方式来提升识别性能；(4)改善物理 电磁波的影响，接近精确的定位效果.该系统在较少 层设计.采用更合理的编码/解码方案以及通信频 阅读器的条件下提高了系统的定位精度，同时也大 段来提高数据传输可靠性 大降低了系统成本，除了使用RFID实现定位机制 之外，一些研究者开始关注基于RFID定位信息的 5 其它开放性问题 查询技术研究.文献[55]提出了一种新颖的RFID 系统框架结构，依靠位置相对固定的标签来定位携 上述RFID数据管理方面的研究工作主要关注 带移动式阅读器的监控对象，从而支持高效的移动 如何能够快速、有效地识别标签的标识信息.事实 范围查询.该文提出了此场景下移动对象位置查询 上，从数据管理的角度来看，除了标签的标识信息， 的一种概率模型，并给出了有效的定位方法， RFID系统还能够提供一类非常重要的信息，那就 5.2基于RFD的移动行为感知 是标签的反射信号强度，通过对反射信号强度数据 现有的移动行为监测主要是基于摄像头获取视 进行有效处理与合理利用，RFID系统能够实现定 频图像来实现的，此类方案具有如下缺点：(1)感知 位、追踪以及移动行为感知等机制 设备价格昂贵，一些专业摄像头动辄成百上千元； 5.1基于RFID的定位机制 (2)获取数据量大质低，存在大量冗余数据，无法实 目前的定位系统主要包括GPS(Global Posi- 时抽取信息与有效利用.研究者们发现，当人体经过 tioning System)定位、蜂窝基站定位、WLAN定位、 RFID阅读器天线与标签之间的空间时，由于人体

466 计 算 机 学 报 器 的一段 探测 区域 ，在该 区域 内具 有 很 高 的标 签 识 别 概 率 (接 近 100 )；次 探 测 区 域 是 指 从 主 探 测 区 域 末 端延 伸至 有效 识 别 范 围边 缘 的一 段 探 测 区域 ， 在 该 区域 内标 签 识别 率 依 照 线 性 关 系 降 低 为 0．文 献[-49—50]研究了在真 实传输 环境下 阅读器发射功 率 对 大规 模 标 签 识 别 性 能 的影 响 ，通 过 实 验 发 现 ， RFID标 签在 激 活状态 与 非 激 活状 态 之 间存 在 一个 中间状 态 (LossyState)，对 识别 性 能影 响很 大．由此 作 者 提 出了 自动功 率 调 节 算 法 ，进 一 步 降 低 了阅 读 器 的 总体 能耗 与扫 描 时 延．文 献 E51]通 过 真 实 实 验 发 现 ，当 阅读器 功率 被 调整 至合 理 范围时 ，可 以利 用 遏 止效 应 (CaptureEffect)来 有 效 地 将 冲 突 时 隙 转 化为单时隙，由此提出了渐进 的扫描算法来优化读 取 性能 ．文献 [52]提 出 了无 源 RFID 系统 中 能量 有 效 的物 理层 设计 方 法 ，在 前 向链 路 中为 使 标 签 获得 更 多能 量 ，结 合 ASK 调 制 提 出 了一 种 新 的 用 于无 源 RFID系 统 的能 量 有 效 的 数 据 编 码 方 法 ．上 述 研 究 成果 表 明 ，RFID在 MAC层 、应 用 层 方 面 的研 究 需 要充 分结 合 物理层 的实 际传 输 特性 ；否 则 ，理 想情 况 下设 计 出 的 算 法 与协 议 将 与 实 际 的 情 况 严 重 不 符 ，无法 达 到预 期 的性 能 要求 ． 总体 来说 ，为 了有 效 避 免 或 降低 物 理 环 境 因 素 对 系统 性能 各指 标 的 影 响 ，目前 的有 效 方 法 主要 包 括 以下 几个 方 面 ：(1)调 整 阅读 器 功率 ．通过 合 理调 整 阅读 器功 率 ，补偿 信号 衰减 的 同时 有效 避免 干扰 ， 优 化 系统性 能 ；(2)优化 协 议参 数 ．设 置 优 化 的协议 参 数 (如帧 长 、传输 速率 )来 优 化读 取 性 能 ；(3)规 划 部 署 方 案 ．通 过 调 整 标 签 的部 署 位 置 、方 向 以 及增 加 冗余 标签 的 方 式 来 提 升 识 别 性 能 ；(4)改 善 物 理 层 设计 ．采 用 更 合 理 的编 码 ／解 码 方 案 以及 通 信 频 段 来提 高数 据 传输 可靠 性． 5 其它开放性 问题 上述 RFID数据 管 理方 面 的研究 工 作 主要 关 注 如何 能够 快 速 、有 效 地 识 别 标 签 的标 识 信 息 ．事 实 上，从数据管理的角度来看 ，除了标签的标识信息 ， RFID系统还 能够 提供一类非 常重 要的信息 ，那就 是标签的反射信号强度．通过对反射信号强度数据 进行有效处理 与合理利用 ，RFID系统能够 实现定 位、追踪以及移动行为感知等机制． 5．1 基 于 RFID的 定位 机制 目前 的定 位系 统主要 包括 GPS(GlobalPosi— tioningSystem)定位 、蜂窝基站定位 、WLAN定位 、 传感 网定位等．其 中，GPS定位 与蜂 窝基站定位 主 要 用 于室 外定 位 ，WLAN定 位 、传 感 网定 位 主 要 用 于室 内定 位．RFID定 位 技 术 以 低 成 本 、非 接 触 性 通 信 等 特 点 ，有 望 成 为 室 内定 位 技 术 的首 选 ．目前 的室 内定 位 系 统 大 多 基 于 RSSI(ReceivedSignal StrengthIndicator)来 辅 助 定 位 ，其 基 本 原 理 是 ：已 知发射信号 的强度 ，接收方根据接 收到的信号强度 ， 估 算 出通信 双 方 的距 离 ．而 在实 际情 况下 ，无线 信号 在 空 问传播 时 能量 的衰 减 不 仅 受 传播 距 离 的影 响 ， 还 受 到多径 效 应 、传 播 的 方 向 性 、复 杂 的 室 内结 构 、 随机 流 动 的人 员 等 诸 多 不 确 定 因 素 的影 响 ，利 用 RSSI作 为位 置感 知 数 据 进 行 室 内定 位 存 在 较 多 的 困难 ．但 是 由 于 RSSI极 易 获 取 ，不 需 要 额 外 的设 备 ，相 比于 其它 定位 技术 成本 非 常低 ，因此 当前 主流 的 RFID定位 技术 都 是基 于 RSSI进行 定位 ．其 中比 较 典 型 的代 表 是 SpotON 系统 与 LANDMARC 系 统 ．SpotON 系 统l5。基 于 阅读 器 与 目标 标 签 构 造 了 一 个无 线感 知 环境 ，通 过 聚 合 算 法 减 少 信 号 强度 误 差 ，并利用信号传播模 型求解 阅读器与 目标标签 的 距 离 ，最后 利用 三 角定 位 算 法 对 目标 在 三 维 空 间进 行 定位 ．整 体而 言 ，SpotON 是 一 个 实验 性 的原 型 系 统 ，无论 是 距离 估计 还 是 误 差 处 理 都停 留 在 比较 粗 糙 的 阶段．LANDMARC系统 ¨5]在 已知位 置 引入 参 考标签 ，通过对 比目标标签与参考标签的 RSSI值 ， 来 确 定 物 理 坐 标 关 系 ，最 终 确 定 目标 标 签 坐 标 ． LANDMARC通 过 将 参 考 标 签 部 署 到 实 际应 用 场 景 中 ，实 时同步 地 对参 考 标 签 和 目标 标 签 进 行 能量 值 测算 ，可 以最 大 限 度减 少 多径 效 应 以及 电 离 体对 电磁 波 的影 响 ，接 近精确 的定位效 果 ．该 系统在 较 少 阅读器 的条 件 下提 高 了系 统 的定 位精 度 ，同时 也 大 大降低 了系统成本．除了使用 RFID实 现定 位机 制 之外 ，一些 研究 者 开始 关 注基 于 RFID定 位 信 息 的 查 询 技术 研 究．文 献 E55]提 出 了一 种 新 颖 的 RFID 系统 框架 结构 ，依 靠 位 置相 对 固定 的标 签 来 定 位 携 带移 动式 阅读 器 的监 控 对 象 ，从 而 支 持 高 效 的 移 动 范 围查询 ．该 文提 出 了此 场 景下 移 动 对 象 位 置 查 询 的一 种概 率模 型 ，并给 出了有效 的 定位方 法 。 5．2 基 于 RF1D的移 动 行为 感知 现有 的移 动 行为监 测 主要 是基 于摄 像头 获取 视 频 图像来 实 现 的 ，此类 方 案具 有 如下 缺 点 ：(1)感 知 设备价格 昂贵，一些 专业摄像头 动辄成百上 千元 ； (2)获取数据量大质低 ，存在大量冗余数据 ，无法实 时抽取信息与有效利用．研究者们发现 ，当人体经过 RFID阅读 器 天 线 与 标 签 之 间 的 空 间 时 ，由于 人 体