第36卷第3期 计算机学报 Vol.36 No.3 2013年3月 CHINESE JOURNAL OF COMPUTERS Mar.2013 RFID数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 (南京大学计算机软件新技术国家重点实验室南京210093) 摘要随着物联网关键理论及技术的发展,RFID作为物联网的核心支撑技术,成为物联网领域备受关注的研究 热点之一.文中以RFID的数据管理为切人点，从算法、协议以及性能评测3个层面对RFID的研究工作进行闸述 与分析，着重介绍了RFID的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展.最后展望了未来的研究方向. 关键词射频识别；数据管理；防冲突算法；认证与隐私保护；性能优化；物联网 中图法分类号TP393 DOI号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 Softuare 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的技术原理被进一步深入理解、 1引言 廉价的RFID组件相继出现以及RFID的安全得到 保障，RFID技术将会在物联网应用中发挥越来越 随着“物联网”时代的来临，新一代IT技术将 重要的作用 被充分运用在各行各业之中.射频识别(RFID)作为 物联网的核心理念是在普适环境下实现“物-物 物联网应用的一项核心支撑技术，在学术界与工业 相联”，即通过对物理世界信息化、网络化，将传统上 界已经得到广泛关注.目前，RFID技术正在越来越 分离的物理世界与信息世界实现互联与整合.这就 频繁地出现在大量的物联网应用中，包括物流管理、 需要将“智能”嵌人到每一个物理对象当中，并且提供 电子支付、RFID护照、安全访问控制、目标监测与 一种有效的、低成本的通信方式，RFID技术的出现 收稿日期：2012-02-08：最终修改稿收到日期：2012-05-27.本课题得到国家“九七三”重点基础研究发展规划项目基金(2009CB320705)、国家 自然科学基金(61100196,61073028,61021062)以及江苏省自然科学基金(BK2011559)资助.谢磊，男，1982年生，博士，讲师，中国计算机 学会(CCF)会员，主要研究方向为传感器网络、RFID系统、车联网、高性能计算.E-mail:lxie@nju.edu.cn.殷亚凤，女，1989年生，博士研究 生，中国计算机学会(CCF)学生会员，主要研究方向为RFID.陈曦，男，1988年生，硕士研究生，中国计算机学会(CCF)学生会员，主要研究 方向为RFID.陆桑璐，女，1970年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为普适计算、分布式计算、传感 器网络.陈道蓄，男，1947年生，教授，博士生导师，中国计算机学会(CCF)高级会员，主要研究领域为普适计算、分布式计算、计算机网络
书 第３６卷第３期 ２０１３年３月 计 算 机 学 报 ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３６Ｎｏ．３ Ｍａｒ．２０１３ 收稿日期：２０１２０２０８；最终修改稿收到日期：２０１２０５２７．本课题得到国家“九七三”重点基础研究发展规划项目基金（２００９ＣＢ３２０７０５）、国家 自然科学基金（６１１００１９６，６１０７３０２８，６１０２１０６２）以及江苏省自然科学基金（ＢＫ２０１１５５９）资助．谢磊，男，１９８２年生，博士，讲师，中国计算机 学会（ＣＣＦ）会员，主要研究方向为传感器网络、ＲＦＩＤ系统、车联网、高性能计算．Ｅｍａｉｌ：ｌｘｉｅ＠ｎｊｕ．ｅｄｕ．ｃｎ．殷亚凤，女，１９８９年生，博士研究 生，中国计算机学会（ＣＣＦ）学生会员，主要研究方向为ＲＦＩＤ．陈曦，男，１９８８年生，硕士研究生，中国计算机学会（ＣＣＦ）学生会员，主要研究 方向为ＲＦＩＤ．陆桑璐，女，１９７０年生，博士，教授，博士生导师，中国计算机学会（ＣＣＦ）会员，主要研究领域为普适计算、分布式计算、传感 器网络．陈道蓄，男，１９４７年生，教授，博士生导师，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为普适计算、分布式计算、计算机网络． 犚犉犐犇数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 （南京大学计算机软件新技术国家重点实验室南京２１００９３） 摘要随着物联网关键理论及技术的发展，ＲＦＩＤ作为物联网的核心支撑技术，成为物联网领域备受关注的研究 热点之一．文中以ＲＦＩＤ的数据管理为切入点，从算法、协议以及性能评测３个层面对ＲＦＩＤ的研究工作进行阐述 与分析，着重介绍了ＲＦＩＤ的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展．最后展望了未来的研究方向． 关键词射频识别；数据管理；防冲突算法；认证与隐私保护；性能优化；物联网 中图法分类号ＴＰ３９３ 犇犗犐号１０．３７２４／ＳＰ．Ｊ．１０１６．２０１３．００４５７ 犚犉犐犇犇犪狋犪犕犪狀犪犵犲犿犲狀狋：犃犾犵狅狉犻狋犺犿狊，犘狉狅狋狅犮狅犾狊犪狀犱犘犲狉犳狅狉犿犪狀犮犲犈狏犪犾狌犪狋犻狅狀 ＸＩＥＬｅｉＹＩＮＹａＦｅｎｇＣＨＥＮＸｉＬＵＳａｎｇＬｕＣＨＥＮＤａｏＸｕ （犛狋犪狋犲犓犲狔犔犪犫狅狉犪狋狅狉狔犳狅狉犖狅狏犲犾犛狅犳狋狑犪狉犲犜犲犮犺狀狅犾狅犵狔，犖犪狀犼犻狀犵犝狀犻狏犲狉狊犻狋狔，犖犪狀犼犻狀犵２１００９３） 犃犫狊狋狉犪犮狋 ＷｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｃｒｉｔｉｃａｌｔｈｅｏｒｉｅｓａｎｄｔｅｃｈｎｏｌｏｇｉｅｓｉｎＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ （ＩＯＴ），ａｓａｋｅｙｓｕｐｐｏｒｔｉｎｇｔｅｃｈｎｏｌｏｇｙ，ＲＦＩＤｈａｓｂｅｃｏｍｅｏｎｅｏｆｔｈｅｈｏｔｓｐｏｔｓｉｎｔｈｅｆｉｅｌｄｏｆ ＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ．ＦｏｃｕｓｉｎｇｏｎＲＦＩＤｄａｔａｍａｎａｇｅｍｅｎｔ，ｔｈｉｓｐａｐｅｒｄｅｓｃｒｉｂｅｓａｎｄａｎａｌｙｚｅｓｔｈｅｒｅ ｓｅａｒｃｈｗｏｒｋｏｎｔｈｒｅｅａｓｐｅｃｔｓ：ａｌｇｏｒｉｔｈｍ，ｐｒｏｔｏｃｏｌａｎｄｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅ ｉｎｔｒｏｄｕｃｅｔｈｅｒｅｓｅａｒｃｈｐｒｏｇｒｅｓｓｉｎＲＦＩＤｗｉｔｈａｎｔｉｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ，ａｕｔｈｅｎｔｉｃａｔｉｏｎａｎｄｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎｐｒｏｔｏｃｏｌｓ，ａｓｗｅｌｌａｓｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎｏｆＲＦＩＤｓｙｓｔｅｍｓｉｎｒｅａｌｉｓｔｉｃｓｅｔｔｉｎｇｓ．Ｆｉ ｎａｌｌｙ，ｗｅｏｕｔｌｏｏｋｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｓａｎｄｃｏｎｃｌｕｄｅ． 犓犲狔狑狅狉犱狊ＲＦＩＤ；ｄａｔａｍａｎａｇｅｍｅｎｔ；ａｎｔｉｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ；ａｕｔｈｅｎｔｉｃａｔｉｏｎａｎｄｐｒｉｖａｃｙｐｒｏｔｅｃ ｔｉｏｎ；ｐｅｒｆｏｒｍａｎｃｅｏｐｔｉｍｉｚａｔｉｏｎ；ＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ １引言 随着“物联网”时代的来临，新一代ＩＴ技术将 被充分运用在各行各业之中．射频识别（ＲＦＩＤ）作为 物联网应用的一项核心支撑技术，在学术界与工业 界已经得到广泛关注．目前，ＲＦＩＤ技术正在越来越 频繁地出现在大量的物联网应用中，包括物流管理、 电子支付、ＲＦＩＤ护照、安全访问控制、目标监测与 追踪等．随着ＲＦＩＤ的技术原理被进一步深入理解、 廉价的ＲＦＩＤ组件相继出现以及ＲＦＩＤ的安全得到 保障，ＲＦＩＤ技术将会在物联网应用中发挥越来越 重要的作用． 物联网的核心理念是在普适环境下实现“物物 相联”，即通过对物理世界信息化、网络化，将传统上 分离的物理世界与信息世界实现互联与整合．这就 需要将“智能”嵌入到每一个物理对象当中，并且提供 一种有效的、低成本的通信方式，ＲＦＩＤ技术的出现
458 计算 机 学报 2013年 正好满足了这一需求.RFD是一种非接触式的自 为数据管理提供基本的安全保障，能够有效地实现 动识别技术，它通过射频信号自动识别目标对象并 认证并且保护用户隐私，实现RFID数据管理的可 获取相关数据，识别工作无须人工干预.作为一种简 信性；对RFID系统进行性能评测与分析，其目的在 单的无线系统，RFID系统只有两个基本器件，一个 于验证在真实环境下物理层的关键因素对系统识别 是阅读器，另一个是标签.其基本工作原理是：阅读器 性能的影响，确保数据管理的可靠性.深入探究三者 以广播方式连续向周围发送携带能量的基准信号， 之间的联系，我们发现任一研究问题均对其余二者 感应到能量的标签通过调制电路信号以反射的方式 产生影响：防冲突算法能够提供最根本的数据传输 向阅读器返回自身携带的数据，阅读器对接收到的 支持，安全协议能够实现必要的安全保障，性能评测 数据进行解码，并传给主机进行处理.通过上述方 能够验证在真实环境下的系统运行性能，上述三方 式，RFID系统能够提供有效的身份信息(Identity) 面研究问题与RFD系统协议栈的对应关系如图1 和地址信息(Location).相比于其它智能系统， 所示，可以看到三者之间相互联系，又各有侧重 RFID系统具有如下鲜明特点：(1)能够实现非接触 RFID数据管理 式的快速自动识别；(2)标签内能够永久存储一定 可靠性 高效性 可信性 大小的数据；(3)标签内含一定数目的逻辑门能够 个 进行简单的逻辑处理；(4)标签具有普通无线设备 性能 防冲突九N 安全 的物理属性；(5)标签成本低廉，可以大量部署.因 评测 算法 协议 此，作为物联网感知识别层面的一项关键技术， RFID技术能够使得物联网中的每一个物体被唯一 物理层 媒体访问 控制层 应用层 地识别，并且能够携带规范而具有互用性的信息，在 RFID系统协议栈 无源的情况下有效实现“被动智能”，为“物-物相联” 提供根本保障 图1各研究问题之间的逻辑层次关系 在物联网环境下，RFID系统被部署和应用的 本文第2节主要介绍RFID的标签识别协议与 根本目的是：针对具体的应用需求，对被标识的物理 防冲突算法，着重阐述RFD标签识别机制、数目估 对象进行合理有效的信息收集，为上层应用提供最 算机制以及轮询机制方面的研究工作：第3节主要 基本的数据支持.因此，任何一种具体的RFD应用 介绍RFID的认证与隐私保护协议，对RFID的安 都依赖于对RFID数据实现有效的数据管理.所谓 全与隐私问题进行探讨与分析，并对RFID安全方 数据管理是指结合RFID系统的应用需求实现有效 面的三类主流技术进行总结：第4节对真实环境下 且有针对性的数据收集、分析挖掘以及数据安全保 RFID系统性能的评测与分析方面的研究工作进行 障等操作.在现有的物联网体系架构中，数据管理起 介绍：第5节对RFID数据管理相关的其它开放性 着承上启下的关键作用：一方面，物联网需要从感知 问题的研究进展进行总结；第6节展望RFID未来 到的海量原始数据中提取有效信息并进行管理，为 的研究方向；最后对全文进行总结 上层的特定应用提供数据支撑：另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 2 RFID标签识别协议与防冲突算法 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现. 2.1 RFD的标签识别协议 基于上述认识，本文关注RFID数据管理问题， 在通常的RFID应用中，大量的RFID标签往 以数据管理的核心技术为切入点，分别从RFD的 往被广泛地部署在指定区域中，为了能够快速有效 防冲突算法、RFD的认证与隐私保护协议以及真 地识别这些标签，阅读器需要在RFD标签识别协 实环境下RFD系统数据收集的性能评测与分析 议中使用一套有效的防冲突算法来逐一读取这些标 3个方面对RFID数据管理技术的研究与进展进行 签.在无线通信环境下，普通的无线设备主要基于载 分析与讨论.图1展示了上述3个方面研究问题之 波侦听多路访问/冲突避免(CSMA/CA)的竞争机 间的逻辑层次关系.其中，研究防冲突算法的目的是 制来实现多个设备之间的通信，如802.11协议.与 为MAC层提供一套快速的标签识别机制，实现 普通的无线节点不同，RFD标签是极为简单的无 RFID数据管理的高效性；研究安全协议的目的是 线设备，标签上的资源极其有限，不能够自发地通过
正好满足了这一需求．ＲＦＩＤ是一种非接触式的自 动识别技术，它通过射频信号自动识别目标对象并 获取相关数据，识别工作无须人工干预．作为一种简 单的无线系统，ＲＦＩＤ系统只有两个基本器件，一个 是阅读器，另一个是标签．其基本工作原理是：阅读器 以广播方式连续向周围发送携带能量的基准信号， 感应到能量的标签通过调制电路信号以反射的方式 向阅读器返回自身携带的数据，阅读器对接收到的 数据进行解码，并传给主机进行处理．通过上述方 式，ＲＦＩＤ系统能够提供有效的身份信息（Ｉｄｅｎｔｉｔｙ） 和地址信息（Ｌｏｃａｔｉｏｎ）．相比于其它智能系统， ＲＦＩＤ系统具有如下鲜明特点：（１）能够实现非接触 式的快速自动识别；（２）标签内能够永久存储一定 大小的数据；（３）标签内含一定数目的逻辑门能够 进行简单的逻辑处理；（４）标签具有普通无线设备 的物理属性；（５）标签成本低廉，可以大量部署．因 此，作为物联网感知识别层面的一项关键技术， ＲＦＩＤ技术能够使得物联网中的每一个物体被唯一 地识别，并且能够携带规范而具有互用性的信息，在 无源的情况下有效实现“被动智能”，为“物物相联” 提供根本保障． 在物联网环境下，ＲＦＩＤ系统被部署和应用的 根本目的是：针对具体的应用需求，对被标识的物理 对象进行合理有效的信息收集，为上层应用提供最 基本的数据支持．因此，任何一种具体的ＲＦＩＤ应用 都依赖于对ＲＦＩＤ数据实现有效的数据管理．所谓 数据管理是指结合ＲＦＩＤ系统的应用需求实现有效 且有针对性的数据收集、分析挖掘以及数据安全保 障等操作．在现有的物联网体系架构中，数据管理起 着承上启下的关键作用：一方面，物联网需要从感知 到的海量原始数据中提取有效信息并进行管理，为 上层的特定应用提供数据支撑；另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现． 基于上述认识，本文关注ＲＦＩＤ数据管理问题， 以数据管理的核心技术为切入点，分别从ＲＦＩＤ的 防冲突算法、ＲＦＩＤ的认证与隐私保护协议以及真 实环境下ＲＦＩＤ系统数据收集的性能评测与分析 ３个方面对ＲＦＩＤ数据管理技术的研究与进展进行 分析与讨论．图１展示了上述３个方面研究问题之 间的逻辑层次关系．其中，研究防冲突算法的目的是 为ＭＡＣ层提供一套快速的标签识别机制，实现 ＲＦＩＤ数据管理的高效性；研究安全协议的目的是 为数据管理提供基本的安全保障，能够有效地实现 认证并且保护用户隐私，实现ＲＦＩＤ数据管理的可 信性；对ＲＦＩＤ系统进行性能评测与分析，其目的在 于验证在真实环境下物理层的关键因素对系统识别 性能的影响，确保数据管理的可靠性．深入探究三者 之间的联系，我们发现任一研究问题均对其余二者 产生影响：防冲突算法能够提供最根本的数据传输 支持，安全协议能够实现必要的安全保障，性能评测 能够验证在真实环境下的系统运行性能．上述三方 面研究问题与ＲＦＩＤ系统协议栈的对应关系如图１ 所示，可以看到三者之间相互联系，又各有侧重． 图１各研究问题之间的逻辑层次关系 本文第２节主要介绍ＲＦＩＤ的标签识别协议与 防冲突算法，着重阐述ＲＦＩＤ标签识别机制、数目估 算机制以及轮询机制方面的研究工作；第３节主要 介绍ＲＦＩＤ的认证与隐私保护协议，对ＲＦＩＤ的安 全与隐私问题进行探讨与分析，并对ＲＦＩＤ安全方 面的三类主流技术进行总结；第４节对真实环境下 ＲＦＩＤ系统性能的评测与分析方面的研究工作进行 介绍；第５节对ＲＦＩＤ数据管理相关的其它开放性 问题的研究进展进行总结；第６节展望ＲＦＩＤ未来 的研究方向；最后对全文进行总结． ２犚犉犐犇标签识别协议与防冲突算法 ２．１犚犉犐犇的标签识别协议 在通常的ＲＦＩＤ应用中，大量的ＲＦＩＤ标签往 往被广泛地部署在指定区域中．为了能够快速有效 地识别这些标签，阅读器需要在ＲＦＩＤ标签识别协 议中使用一套有效的防冲突算法来逐一读取这些标 签．在无线通信环境下，普通的无线设备主要基于载 波侦听多路访问／冲突避免（ＣＳＭＡ／ＣＡ）的竞争机 制来实现多个设备之间的通信，如８０２．１１协议．与 普通的无线节点不同，ＲＦＩＤ标签是极为简单的无 线设备，标签上的资源极其有限，不能够自发地通过 ４５８ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 459 调节自身的无线传输机会来避免标签间的传输冲 表1两类防冲突算法的优缺点比较 突，具体来说，标签没有足够的处理能力与能源来实 基于二进制树防冲突算法基于ALOHA防冲突算法 现上述竞争机制，避免通信冲突.鉴于RFID的系统 使用随机算法，算法实现逻辑简 通常使用确定性的算法， 特点，RFID标签识别协议需要具备如下性质： 算法实现逻辑简单，基于 单，平均情况下，标签识别性能良 优点 查询树结构的算法不需 好：随机算法使得各时隙的结果 (1)简单.由于RFID标签上的计算、存储资源极其 要存储中间状态变量 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 有限，标签识别协议的处理逻辑（包括执行流程和状 算法的随机性导致存在“饿死”问 态迁移关系)需要尽可能简单；(2)高效.面对大量 对基于查询树结构的算 法，标签识别的时延受扫 题，某些标签可能永远选择不到 的RFID标签，标签识别协议需要提供轻量级的通 缺点 描范围内标签ID的分 单时隙进行传输：最坏情况下，标 布以及ID的长度影响 签识别的时延趋向于十∞，其性 信机制，尽可能避免不必要的控制报文的传输，确保 能无法保障 传输的高吞吐率与低延迟性. 隙，导致时隙的浪费：如果帧长过小，则该帧大部分 目前的RFID防冲突算法主要分为两大类：基 时隙会出现标签传输冲突，导致大部分标签需要在 于二进制树的防冲突算法[1-]和基于ALOHA的防 下一帧重传.因此，研究者们对该问题进行了深入研 冲突算法[3].前者利用二叉搜索树，按照递归的方 究.文献[5]分析了在时隙ALOHA协议中采用动 式将冲突的标签集合划分为两个标签子集，对于可 态帧长的方法对读取性能的影响.文献[6]基于贝叶 能产生冲突的相关标签集合，采用沉默的方式来解 斯的概率模型提出了优化动态帧长的决策机制.文 决冲突问题.划分子集的方法包括随机二进制树算 献[7]利用马尔可夫过程来对读取过程进行建模，并 法和查询二进制树算法.文献[1]提出了一套自适应 且由此计算出读取过程中应该使用的一系列优化的 的基于树形结构的防冲突算法来实现有效的标签识 帧长.文献[8]进一步针对最大化信道使用效率的目 别.文献[2]提出了一套基于查询树结构的智能遍历 标推导出优化的动态帧长，该文指出，如果每一轮中 机制，能够以低延迟的方式实现标签的识别. 帧长与当前未读取的标签数相同，则整个信道能够 ALOHA协议最早被用在分组无线网络中实现随机 达到最大的使用效率.其原理阐述如下：假设当前标 访问机制.在RFID系统中，为了提高标签识别的效 签数目为，帧长为f;由于标签对时隙的选择符合 率，文献[3-4]提出了时隙ALOHA协议来有效解 二项分布，则根据二项分布，当前帧中单时隙的期望 决冲突，实现标签的高效识别.时隙ALOHA协议 数目为E[m1]=n×(1一1/f)-1:为了最大化信道 将若干个时隙组织为一帧，在每一帧开始时，阅读器 的使用效率，即单时隙数目在当前帧中的比例 广播帧的长度f,即当前帧所包含的时隙个数，并通 1/f,我们采用求极值的方法计算f的取值，即 过发送连续的电磁波来激活扫描范围内所有标签. 每个标签在接收到帧长f之后随机独立地在第1一 正[]近=0→f'=m,得到此时信道的使用效率 af f个时隙中选择一个时隙发送标识符.如果成功，即 为/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-C1G2标准下使用 100%.当n逐渐增大时，其最优效率快速收敛到 的通信协议，在表1中，我们分别从优缺点两个方面 1/e.这就意味着，当n>5时，每一轮帧长f取值为 对上述两种防冲突算法进行了比较，总体而言，两者 当前待读的标签数n时，使用效率趋向于1/e,可以 在性能与功能实现方面各有利弊。 达到当前每一轮的局部最优效率.如果在识别过程 对于时隙ALOHA协议而言，每一轮所采用的 中每一轮都使用该策略，则整体效率可接近1/e.由 帧长对总体的识别性能至关重要.对于给定的待读 于1/e是整体效率的上限值，因此当前整体效率接 标签集合，如果帧长过大，则该帧大部分时隙为空时 近全局最优
调节自身的无线传输机会来避免标签间的传输冲 突．具体来说，标签没有足够的处理能力与能源来实 现上述竞争机制，避免通信冲突．鉴于ＲＦＩＤ的系统 特点，ＲＦＩＤ标签识别协议需要具备如下性质： （１）简单．由于ＲＦＩＤ标签上的计算、存储资源极其 有限，标签识别协议的处理逻辑（包括执行流程和状 态迁移关系）需要尽可能简单；（２）高效．面对大量 的ＲＦＩＤ标签，标签识别协议需要提供轻量级的通 信机制，尽可能避免不必要的控制报文的传输，确保 传输的高吞吐率与低延迟性． 目前的ＲＦＩＤ防冲突算法主要分为两大类：基 于二进制树的防冲突算法［１２］和基于ＡＬＯＨＡ的防 冲突算法［３８］．前者利用二叉搜索树，按照递归的方 式将冲突的标签集合划分为两个标签子集，对于可 能产生冲突的相关标签集合，采用沉默的方式来解 决冲突问题．划分子集的方法包括随机二进制树算 法和查询二进制树算法．文献［１］提出了一套自适应 的基于树形结构的防冲突算法来实现有效的标签识 别．文献［２］提出了一套基于查询树结构的智能遍历 机制，能够以低延迟的方式实现标签的识别． ＡＬＯＨＡ协议最早被用在分组无线网络中实现随机 访问机制．在ＲＦＩＤ系统中，为了提高标签识别的效 率，文献［３４］提出了时隙ＡＬＯＨＡ协议来有效解 决冲突，实现标签的高效识别．时隙ＡＬＯＨＡ协议 将若干个时隙组织为一帧，在每一帧开始时，阅读器 广播帧的长度犳，即当前帧所包含的时隙个数，并通 过发送连续的电磁波来激活扫描范围内所有标签． 每个标签在接收到帧长犳之后随机独立地在第１～ 犳个时隙中选择一个时隙发送标识符．如果成功，即 无冲突发生，该标签进入静默状态；如果有冲突发 生，则该标签将继续等待在下一帧中再选择一个时 隙重新发送标识符．因此，每一帧的时隙会存在如下 ３种情况之一：（１）空时隙（ＥｍｐｔｙＳｌｏｔ）．没有任何 一个标签选中该时隙；（２）单时隙（ＳｉｎｇｌｅｔｏｎＳｌｏｔ）． 仅有唯一一个标签选中该时隙；（３）冲突时隙 （ＣｏｌｌｉｓｉｏｎＳｌｏｔ）．多个标签选中该时隙．上述每种时 隙所包含的信息量各不相同．目前，时隙ＡＬＯＨＡ 协议已经成为ＲＦＩＤ系统在ＥＰＣＣ１Ｇ２标准下使用 的通信协议．在表１中，我们分别从优缺点两个方面 对上述两种防冲突算法进行了比较，总体而言，两者 在性能与功能实现方面各有利弊． 对于时隙ＡＬＯＨＡ协议而言，每一轮所采用的 帧长对总体的识别性能至关重要．对于给定的待读 标签集合，如果帧长过大，则该帧大部分时隙为空时 表１两类防冲突算法的优缺点比较 基于二进制树防冲突算法 基于ＡＬＯＨＡ防冲突算法 优点 通常使用确定性的算法， 算法实现逻辑简单；基于 查询树结构的算法不需 要存储中间状态变量 使用随机算法，算法实现逻辑简 单；平均情况下，标签识别性能良 好；随机算法使得各时隙的结果 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 缺点 对基于查询树结构的算 法，标签识别的时延受扫 描范围内标签犐犇的分 布以及犐犇的长度影响 算法的随机性导致存在“饿死”问 题，某些标签可能永远选择不到 单时隙进行传输；最坏情况下，标 签识别的时延趋向于＋∞，其性 能无法保障 隙，导致时隙的浪费；如果帧长过小，则该帧大部分 时隙会出现标签传输冲突，导致大部分标签需要在 下一帧重传．因此，研究者们对该问题进行了深入研 究．文献［５］分析了在时隙ＡＬＯＨＡ协议中采用动 态帧长的方法对读取性能的影响．文献［６］基于贝叶 斯的概率模型提出了优化动态帧长的决策机制．文 献［７］利用马尔可夫过程来对读取过程进行建模，并 且由此计算出读取过程中应该使用的一系列优化的 帧长．文献［８］进一步针对最大化信道使用效率的目 标推导出优化的动态帧长，该文指出，如果每一轮中 帧长与当前未读取的标签数相同，则整个信道能够 达到最大的使用效率．其原理阐述如下：假设当前标 签数目为狀，帧长为犳；由于标签对时隙的选择符合 二项分布，则根据二项分布，当前帧中单时隙的期望 数目为犈［狀１］＝狀×（１－１／犳）狀－１；为了最大化信道 的使用效率，即单时隙数目在当前帧中的比例 狀１／犳，我们采用求极值的方法计算犳的取值，即 !犈［狀１］／犳 !犳 ＝０→犳＝狀，得到此时信道的使用效率 为狀１／犳→１／ｅ．对于上述性质，我们在图２和图３ 中给出更为形象的描述．图２展示了给定标签数目 狀＝１００，帧长犳变化对信道使用效率的影响．可以 看到当帧长犳由小及大变化时，信道的使用效率逐 渐增大后又逐渐减小，在犳＝１００时取到最大值１／ｅ． 图３展示了随着标签数目狀变化，使用最优帧长 犳＝狀对信道使用效率的影响．可以看到当狀取值 较小时，所达到的最优效率大于１／ｅ，例如，当仅有 一个标签时（狀＝１），帧长为１可以达到最优效率 １００％．当狀逐渐增大时，其最优效率快速收敛到 １／ｅ．这就意味着，当狀＞５时，每一轮帧长犳取值为 当前待读的标签数狀时，使用效率趋向于１／ｅ，可以 达到当前每一轮的局部最优效率．如果在识别过程 中每一轮都使用该策略，则整体效率可接近１／ｅ．由 于１／ｅ是整体效率的上限值，因此当前整体效率接 近全局最优． ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４５９
460 计 算 机 学报 2013年 0.4 出了一套RFID标签读取性能的概率模型，基于时 隙ALOHA协议设计出优化的标签识别参数，相比 03 传统的识别机制更为有效地提升了识别的性能， 2.2RFD的标签数量估算机制 0.2 随着RFD应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 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 帧长∫ 的标签数量估算机制，以一种实用的方式实现了 图3随着标签数目n变化，使用最优幀长∫=n RFID标签的快速统计.其主要思想为：假设在某一 对应的信道使用效率 轮中帧的长度为∫，空时隙的数目会随着实际参与 的标签数n增加而减少，冲突时隙的数目会随着标 上述提到的协议与防冲突算法多数是在较为理 签数n增加而增加，而单时隙的数目会随着标签数 想的部署环境下得出，并未充分考虑实际应用环境 n增加先增加再减少，因此，空时隙（冲突时隙）的 下所遇到的种种难题，例如，标签的频繁移动、多个 数目与标签数存在明确的单调减（增）关系.该文作 RFID阅读器之间的信号干扰、RFID标签传输的信 者基于二项分布的概率模型给出了空时隙与冲突时 号衰减以及多径效应等.因此，一些研究工作开始关 隙的数值期望计算公式，提出了空时隙与冲突时隙 注并尝试解决上述问题.鉴于之前的研究工作大多 相结合的估算算法，并通过重复采样的手段有效降 关注于解决标签之间的传输冲突问题，并未考虑到 低了估算的误差.研究者们通过进一步研究发现，尽 多个阅读器之间以及标签与阅读器之间的信号干 管单时隙数目与标签数目不存在单调关系，无法利 扰，文献[9-10]在多个RFD阅读器环境下提出了 用单时隙数目推算出确切的标签数目，但是3种时 优化的阅读器激活与调度机制，使得多个阅读器能 隙的数目结合起来能够指导系统更精确地估算标签 够协作地识别标签，有效避免信号的传输冲突，考虑 数目.文献[14]根据观察到的3种时隙的数目提出 到单个RFD阅读器的有效读取范围相对有限，文 了一套后验概率模型，基于最大化后验概率的决策 献[11]利用“时空关联”关系提出了性能高效的连续 来更精确地实现标签数量估算机制，上述机制均需 扫描机制，来实现对大规模部署标签的快速识别.之 要对3种时隙进行大量采样来提高估算的精确度， 前大部分的研究工作主要考虑在相对理想状态下针 事实上，完全可以借助其它参量来更快速有效地估 对静态环境设计优化的标签识别机制，并未考虑移 算标签数目.我们在文献[15]中提出了一种基于 动环境以及传输环境中普遍存在的信号衰减对标签 Ball-and-Bin概率模型的快速估算方法.其核心思想 识别性能带来的影响，有鉴于此，我们针对上述问题 在于：每个标签会随机选择位置回复，系统可以通过 开展了相应的研究工作，文献[12]针对移动环境下 观察第一个标签回复的位置来估算最有可能造成该 持续变化的信号衰减情形，基于跨层优化的思路提 事件发生的标签数量.该文从理论上建立了概率模
图２给定标签数目狀＝１００，信道使用效率与帧长犳的关系 图３随着标签数目狀变化，使用最优帧长犳＝狀 对应的信道使用效率 上述提到的协议与防冲突算法多数是在较为理 想的部署环境下得出，并未充分考虑实际应用环境 下所遇到的种种难题，例如，标签的频繁移动、多个 ＲＦＩＤ阅读器之间的信号干扰、ＲＦＩＤ标签传输的信 号衰减以及多径效应等．因此，一些研究工作开始关 注并尝试解决上述问题．鉴于之前的研究工作大多 关注于解决标签之间的传输冲突问题，并未考虑到 多个阅读器之间以及标签与阅读器之间的信号干 扰，文献［９１０］在多个ＲＦＩＤ阅读器环境下提出了 优化的阅读器激活与调度机制，使得多个阅读器能 够协作地识别标签，有效避免信号的传输冲突．考虑 到单个ＲＦＩＤ阅读器的有效读取范围相对有限，文 献［１１］利用“时空关联”关系提出了性能高效的连续 扫描机制，来实现对大规模部署标签的快速识别．之 前大部分的研究工作主要考虑在相对理想状态下针 对静态环境设计优化的标签识别机制，并未考虑移 动环境以及传输环境中普遍存在的信号衰减对标签 识别性能带来的影响．有鉴于此，我们针对上述问题 开展了相应的研究工作，文献［１２］针对移动环境下 持续变化的信号衰减情形，基于跨层优化的思路提 出了一套ＲＦＩＤ标签读取性能的概率模型，基于时 隙ＡＬＯＨＡ协议设计出优化的标签识别参数，相比 传统的识别机制更为有效地提升了识别的性能． ２．２犚犉犐犇的标签数量估算机制 随着ＲＦＩＤ应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 掘提供数据基础．在这种情况下，ＲＦＩＤ系统不需要 逐个识别标签，仅仅需要快速获取扫描范围内标签 的统计信息，其中一个关键的信息就是标签数量．此 外，基于动态帧长的时隙ＡＬＯＨＡ协议也需要估算 标签的大体数量来决定动态帧的长度．因此，近年来 出现了很多关注于如何快速、精确地估算标签数目 的研究工作，其核心思想主要是使用基于随机算法 的时隙ＡＬＯＨＡ协议来实现估算．研究者们意识 到，尽管时隙ＡＬＯＨＡ协议是以随机的方式让标签 选择时隙进行数据传输，然而从统计意义上来看，整 个空时隙、单时隙以及冲突时隙的分布事实上是符 合二项分布的．当对时隙的采样次数足够多时，完全 可以基于二项分布规律来估算出实际参与标签的数 量．基于上述思路，文献［１３］提出了一套快速而可靠 的标签数量估算机制，以一种实用的方式实现了 ＲＦＩＤ标签的快速统计．其主要思想为：假设在某一 轮中帧的长度为犳，空时隙的数目会随着实际参与 的标签数狀增加而减少，冲突时隙的数目会随着标 签数狀增加而增加，而单时隙的数目会随着标签数 狀增加先增加再减少，因此，空时隙（冲突时隙）的 数目与标签数存在明确的单调减（增）关系．该文作 者基于二项分布的概率模型给出了空时隙与冲突时 隙的数值期望计算公式，提出了空时隙与冲突时隙 相结合的估算算法，并通过重复采样的手段有效降 低了估算的误差．研究者们通过进一步研究发现，尽 管单时隙数目与标签数目不存在单调关系，无法利 用单时隙数目推算出确切的标签数目，但是３种时 隙的数目结合起来能够指导系统更精确地估算标签 数目．文献［１４］根据观察到的３种时隙的数目提出 了一套后验概率模型，基于最大化后验概率的决策 来更精确地实现标签数量估算机制．上述机制均需 要对３种时隙进行大量采样来提高估算的精确度， 事实上，完全可以借助其它参量来更快速有效地估 算标签数目．我们在文献［１５］中提出了一种基于 ＢａｌｌａｎｄＢｉｎ概率模型的快速估算方法．其核心思想 在于：每个标签会随机选择位置回复，系统可以通过 观察第一个标签回复的位置来估算最有可能造成该 事件发生的标签数量．该文从理论上建立了概率模 ４６０ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 461 型，并证明了其正确性和性能的上界.实验表明，在 标签的标识符ID,每传输一个ID后，阅读器会等 给定精度要求的情况下，该方法明显快于现有其它 待对应的标签返回一个短暂的响应消息.如果接收 方法.此外，为了解决单个标签被多次读取的问题， 到响应，则推断该标签存在于扫描范围内，否则认为 文献[16]提出了一套“复制不敏感”的估算机制来实 该标签丢失.然而，上述方案存在如下弊病：(1)与 现更精确的标签数量统计.文献[17]提出了一个自 时隙ALOHA协议不太兼容：(2)长达96bit的ID 适应的基于划分的估算机制，该机制基于几何分布 传输使得整体扫描时间过长，降低了系统的效率.因 规律让单个标签选择同一帧中的多个时隙进行传 此，研究者们针对上述问题开展了深入的研究，其目 输，使得每个标签有1/2的概率选择第1一1个时 标为基于时隙ALOHA协议设计出一套有效的标 隙，有效解决了单个标签被多次读取的问题.表2对 签轮询机制，尽可能地减少整体扫描时间， 上述研究工作的特点进行了总结和比较 研究发现，在时隙ALOHA协议的每一轮中， 处于激活状态的标签会“随机”地在帧中选择一个时 表2标签数量估算算法的特点总结与比较 隙进行传输.然而，由于标签的简易性，真正的随机 估算算法 与时隙ALOHA 估算参考的指标 概率模型 协议兼容性 性很难得到实现.事实上，标签的芯片逻辑实现了一 文献[13] 兼容 空时隙与冲突时 二项分布 个“伪随机”的操作：在每一轮中阅读器广播一个随 隙的数目 机数r,每个被激活的标签接收到r后随即结合本 文献[14] 兼容 3种时隙的数目 基于二项分布的 后验概率模型 地的标识符D进行散列操作，计算出伪随机数s作 文献[15] 兼容 第一个标签回复 的位置 二项分布 为选定的时隙序号，这里s=hash(ID,r)modf,f 文献[16-17] 不兼容 冲突时隙出现的 几何分布 是帧的长度，上述的“伪随机性”意味着，对于任一标 边缘位置 签，一旦阅读器广播的数值r以及帧的长度f确定 除了对标签数量进行简单估算之外，一些研究 下来，该标签在帧中相应的位置即被确定，这就使得 工作者开始探究如何在RFID系统上实现更为复杂 对标签的有效轮询成为可能.在实施扫描之前，阅读 的数据分析与挖掘机制.文献[18]着力研究面对大 器可以预先根据指定集合内各标签在帧中对应的位 量的RFID标签，如何在不需要读取所有标签具体 置为每个时隙计算出期望的结果：空时隙(0)、单时 信息的前提下快速定位出最热门的标签类别.该文 隙(1)或者冲突时隙(C).对于某一时隙，如果该时 基于分组测试(Group Testing)的理念，提出了有效 隙期望为单时隙但实际无响应，则表明对应于该时 的随机算法来解决上述问题.文献[19]面向流量追 隙的标签丢失；如果该时隙期望为冲突时隙但实际 踪一类的应用问题，针对动态移动的标签集合提出 无响应，则表明对应于该时隙的所有标签丢失.图4 了保障隐私的快速估算机制.该机制能够快速统计 给出了基于时隙ALOHA协议的轮询机制示意图， 在时域(t1,t2)内从地点A移动到地点B的标签数 如图所示，在标签A~H中，虚线标识丢失的标签， 目，从而在无需读取确切标签ID信息的前提下有 实线标识存在的标签.当标签E、F以及H丢失时， 效地进行流量追踪.总体而言，目前该方面的研究成 其对应的时隙实际观察到的状态变成空时隙(0)，此 果相对较少，随着RFD数据管理技术以及相关应 时可以判定标签丢失.但对于标签C丢失的情况， 用的进一步拓展，基于RFID的数据分析与挖掘机 由于标签B、D的存在，使得对应时隙实际观察到的 制必将得到更为广泛的关注与深入的研究 状态仍为冲突时隙(C),未能判断出标签C丢失的 2.3RFD的标签轮询机制 情况，导致假阳性误判(False Positive).上述轮询机 某些RFD应用并不需要获取全部RFID标签 -=-=- 标签A标签B标签C标签D 标签E标签F标签G标签H! 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失.例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 期望的 状态 清点指定的货物，确定是否存在货物丢失.在这种情 况下，假设所有的货物都贴有唯一标识的RFD标 实际观察 的状态 o 0 1 o c oo 01000 签，能否有效地实现标签的轮询机制成为与此密切 轮询判断 末能判断出标 标签E, 相关的问题.最简单直接的方案便是设计一种类似 的结果 签C丢失，假 阳性误判 标签F丢失标签H丢失 于“点名”的机制：阅读器根据清单内容接连地广播 图4基于时隙ALOHA协议的轮询机制示意图
型，并证明了其正确性和性能的上界．实验表明，在 给定精度要求的情况下，该方法明显快于现有其它 方法．此外，为了解决单个标签被多次读取的问题， 文献［１６］提出了一套“复制不敏感”的估算机制来实 现更精确的标签数量统计．文献［１７］提出了一个自 适应的基于划分的估算机制，该机制基于几何分布 规律让单个标签选择同一帧中的多个时隙进行传 输，使得每个标签有１／２狋的概率选择第狋－１个时 隙，有效解决了单个标签被多次读取的问题．表２对 上述研究工作的特点进行了总结和比较． 表２标签数量估算算法的特点总结与比较 估算算法与时隙ＡＬＯＨＡ 协议兼容性 估算参考的指标 概率模型 文献［１３］ 兼容 空时隙与冲突时 隙的数目 二项分布 文献［１４］ 兼容 ３种时隙的数目 基于二项分布的 后验概率模型 文献［１５］ 兼容 第一个标签回复 的位置 二项分布 文献［１６１７］ 不兼容 冲突时隙出现的 边缘位置 几何分布 除了对标签数量进行简单估算之外，一些研究 工作者开始探究如何在ＲＦＩＤ系统上实现更为复杂 的数据分析与挖掘机制．文献［１８］着力研究面对大 量的ＲＦＩＤ标签，如何在不需要读取所有标签具体 信息的前提下快速定位出最热门的标签类别．该文 基于分组测试（ＧｒｏｕｐＴｅｓｔｉｎｇ）的理念，提出了有效 的随机算法来解决上述问题．文献［１９］面向流量追 踪一类的应用问题，针对动态移动的标签集合提出 了保障隐私的快速估算机制．该机制能够快速统计 在时域（狋１，狋２）内从地点Ａ移动到地点Ｂ的标签数 目，从而在无需读取确切标签犐犇信息的前提下有 效地进行流量追踪．总体而言，目前该方面的研究成 果相对较少，随着ＲＦＩＤ数据管理技术以及相关应 用的进一步拓展，基于ＲＦＩＤ的数据分析与挖掘机 制必将得到更为广泛的关注与深入的研究． ２．３犚犉犐犇的标签轮询机制 某些ＲＦＩＤ应用并不需要获取全部ＲＦＩＤ标签 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失．例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 清点指定的货物，确定是否存在货物丢失．在这种情 况下，假设所有的货物都贴有唯一标识的ＲＦＩＤ标 签，能否有效地实现标签的轮询机制成为与此密切 相关的问题．最简单直接的方案便是设计一种类似 于“点名”的机制：阅读器根据清单内容接连地广播 标签的标识符犐犇，每传输一个犐犇后，阅读器会等 待对应的标签返回一个短暂的响应消息．如果接收 到响应，则推断该标签存在于扫描范围内，否则认为 该标签丢失．然而，上述方案存在如下弊病：（１）与 时隙ＡＬＯＨＡ协议不太兼容；（２）长达９６ｂｉｔ的犐犇 传输使得整体扫描时间过长，降低了系统的效率．因 此，研究者们针对上述问题开展了深入的研究，其目 标为基于时隙ＡＬＯＨＡ协议设计出一套有效的标 签轮询机制，尽可能地减少整体扫描时间． 图４基于时隙ＡＬＯＨＡ协议的轮询机制示意图 研究发现，在时隙ＡＬＯＨＡ协议的每一轮中， 处于激活状态的标签会“随机”地在帧中选择一个时 隙进行传输．然而，由于标签的简易性，真正的随机 性很难得到实现．事实上，标签的芯片逻辑实现了一 个“伪随机”的操作：在每一轮中阅读器广播一个随 机数狉，每个被激活的标签接收到狉后随即结合本 地的标识符犐犇进行散列操作，计算出伪随机数狊作 为选定的时隙序号，这里狊＝ｈａｓｈ（犐犇，狉）ｍｏｄ犳，犳 是帧的长度．上述的“伪随机性”意味着，对于任一标 签，一旦阅读器广播的数值狉以及帧的长度犳确定 下来，该标签在帧中相应的位置即被确定，这就使得 对标签的有效轮询成为可能．在实施扫描之前，阅读 器可以预先根据指定集合内各标签在帧中对应的位 置为每个时隙计算出期望的结果：空时隙（０）、单时 隙（１）或者冲突时隙（犆）．对于某一时隙，如果该时 隙期望为单时隙但实际无响应，则表明对应于该时 隙的标签丢失；如果该时隙期望为冲突时隙但实际 无响应，则表明对应于该时隙的所有标签丢失．图４ 给出了基于时隙ＡＬＯＨＡ协议的轮询机制示意图． 如图所示，在标签Ａ～Ｈ中，虚线标识丢失的标签， 实线标识存在的标签．当标签Ｅ、Ｆ以及Ｈ丢失时， 其对应的时隙实际观察到的状态变成空时隙（０），此 时可以判定标签丢失．但对于标签Ｃ丢失的情况， 由于标签Ｂ、Ｄ的存在，使得对应时隙实际观察到的 状态仍为冲突时隙（犆），未能判断出标签Ｃ丢失的 情况，导致假阳性误判（ＦａｌｓｅＰｏｓｉｔｉｖｅ）．上述轮询机 ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４６１
462 计算 机 学报 2013年 制为进一步的研究工作提供了一个理论基础. 而言，其安全问题是指存在伪造标签时，如何有效地 基于上述认识，文献[20]对面向大规模标签监 对标签进行认证：其隐私问题是指存在恶意阅读器 控应用中的一个重要问题进行了研究：如何在大量 时，如何防止阅读器对标签的非法访问，来有效地保 标签中快速定位出丢失的标签.该文利用时隙 护用户的隐私.在常用的网络安全解决方案中，已经 ALOHA协议的伪随机性，基于轮询机制提出了多 存在成熟的加解密算法如DES、AES、RSA、椭圆曲 种协议，能够快速有效地定位丢失的标签.针对由电 线密码等，这些算法构成了对称密钥加密以及公开 池供电的大规模主动标签实时信息收集的问题，文 密钥加密中的支撑技术，能够有效地实现加密与鉴 献[21]设计了一套高效节能的轮询协议.该协议基 别功能，抵制非法读取、伪装哄骗、重放攻击等安全 于标签排序(Tag-Ordering)的编码方式，使得所消 威胁，具有良好的安全性.但实现上述算法需要较多 耗的能量比通常的轮询协议下降一个数量级.该协 的逻辑处理单元，如AES需要大约20000~30000 议进一步采用基于分块的布鲁姆过滤器(Bloom 个逻辑门，RSA、椭圆曲线密码等公钥密码算法则需 Filter)来提高轮询机制的性能，在不影响整体扫描 要更多的逻辑门.而RFD标签受到低成本限制，通 时间的前提下显著降低了能耗.文献[22]针对上述 常只能拥有大约5000~10000个逻辑门，并且这些 问题进一步提出了基于单级Hash与多级Hash的 逻辑门主要用于实现一些最基本的标签功能，仅剩 轮询机制，显著地降低了信息收集的时间.文献[23] 少许可用于实现安全功能.此外，RFD标签上的存 基于轮询协议提出了一套批处理的认证机制，无需 储资源也非常受限，通常标签的EPC区仅能存储 通过逐个识别的方式来认证标签.通常情况下，为了 96bit数据，用户区仅能存储512bit数据.RFID标 实现对大量标签的认证，阅读器需要对标签逐一识 签极其有限的计算资源难以支持上述复杂的加解密 别并认证，这种方式需要耗费大量的通信开销与扫 算法的实现.因此，对RFD系统而言，其安全与隐 描时间.基于轮询协议的伪随机性，该批处理认证 私保障机制所面临的最大挑战在于：如何以一种轻 机制提出了一套快速的认证算法，能够极大地降低 量级的方式在资源极其受限的RFID系统上实现认 认证的扫描时间与通信开销.由于该机制基于时隙 证与隐私保护协议.下面我们从基于物理方法的安 ALOHA的随机算法进行认证，因此存在假阳性误 全保护机制、基于对称密钥加密的协议以及基于 判，但是该机制能够以概率的形式确保未检测到的 Hash函数的协议等几个方面来具体阐述相关研究 伪造标签所占比例被控制在指定阈值范围内.上述 成果 研究工作的轮询机制都对应于扫描范围内的所有标 3.2基于物理方法的安全保护机制 签，如果仅需要对扫描范围内标签的一个子集进行 RFD的隐私问题是由阅读器识别标签时无需 轮询，这些机制将很难适用.因此，针对大规模标签 认证引起的.在没有隐私保障机制的情况下，阅读器 部署情况下搜索特定标签集合的问题，文献[24]基 可以随意地对标签进行秘密扫描，获取标签信息；对 于布鲁姆过滤器提出了一套两阶段的快速搜索算 于无法直接获取信息的加密标签则可以根据反馈的 法，能够在指定的假阳性误判率的范围内有效降低 加密信息进行跟踪，获得用户的地点信息，综合整理 通信开销与时延.总体来说，RFID的轮询机制基于 就形成了对用户个人信息的盘点.为了保护RFID 时隙ALOHA协议中的伪随机操作来进行轮询，能 用户隐私，一种简单直接的手段便是基于物理方法 够有效避免对标签逐一识别带来的额外开销，但同 的安全保护机制，具体而言，主要包括灭活操作、静 时也存在假阳性误判的效应，系统可以借助相应的 电屏蔽、主动干扰以及阻塞法等. 优化机制来降低假阳性误判的概率」 灭活(Kl)操作是一种简单暴力的方法，阅读 器通过向标签发送一个指定的PIN码来执行杀死 3 RFID的认证与隐私保护机制 命令，命令执行完后标签就失效了，不再对阅读器的 查询做出回应，显然，完全地让标签失效并不是一个 3.1 RFD的安全与隐私问题 合理的解决方案.文献[25]提出可以只让标签中唯 在物联网应用中，对RFID系统实现有效数据 一识别码失效而保留产品类型标识码的数据部分， 管理的前提在于保障RFID数据的安全性与私密 这样就可以避免标签被跟踪，但是该方案使标签失 性.RFID系统的安全威胁主要来自于阅读器对标 去了唯一标识物品的特性.文献[26]提出采用全新 签的非法访问以及伪造标签的存在.对RFID系统 的标识符重新对标签进行标识的方案，原有的标识
制为进一步的研究工作提供了一个理论基础． 基于上述认识，文献［２０］对面向大规模标签监 控应用中的一个重要问题进行了研究：如何在大量 标签中快速定位出丢失的标签．该文利用时隙 ＡＬＯＨＡ协议的伪随机性，基于轮询机制提出了多 种协议，能够快速有效地定位丢失的标签．针对由电 池供电的大规模主动标签实时信息收集的问题，文 献［２１］设计了一套高效节能的轮询协议．该协议基 于标签排序（ＴａｇＯｒｄｅｒｉｎｇ）的编码方式，使得所消 耗的能量比通常的轮询协议下降一个数量级．该协 议进一步采用基于分块的布鲁姆过滤器（Ｂｌｏｏｍ Ｆｉｌｔｅｒ）来提高轮询机制的性能，在不影响整体扫描 时间的前提下显著降低了能耗．文献［２２］针对上述 问题进一步提出了基于单级Ｈａｓｈ与多级Ｈａｓｈ的 轮询机制，显著地降低了信息收集的时间．文献［２３］ 基于轮询协议提出了一套批处理的认证机制，无需 通过逐个识别的方式来认证标签．通常情况下，为了 实现对大量标签的认证，阅读器需要对标签逐一识 别并认证，这种方式需要耗费大量的通信开销与扫 描时间．基于轮询协议的伪随机性，该批处理认证 机制提出了一套快速的认证算法，能够极大地降低 认证的扫描时间与通信开销．由于该机制基于时隙 ＡＬＯＨＡ的随机算法进行认证，因此存在假阳性误 判，但是该机制能够以概率的形式确保未检测到的 伪造标签所占比例被控制在指定阈值范围内．上述 研究工作的轮询机制都对应于扫描范围内的所有标 签，如果仅需要对扫描范围内标签的一个子集进行 轮询，这些机制将很难适用．因此，针对大规模标签 部署情况下搜索特定标签集合的问题，文献［２４］基 于布鲁姆过滤器提出了一套两阶段的快速搜索算 法，能够在指定的假阳性误判率的范围内有效降低 通信开销与时延．总体来说，ＲＦＩＤ的轮询机制基于 时隙ＡＬＯＨＡ协议中的伪随机操作来进行轮询，能 够有效避免对标签逐一识别带来的额外开销，但同 时也存在假阳性误判的效应，系统可以借助相应的 优化机制来降低假阳性误判的概率． ３犚犉犐犇的认证与隐私保护机制 ３．１犚犉犐犇的安全与隐私问题 在物联网应用中，对ＲＦＩＤ系统实现有效数据 管理的前提在于保障ＲＦＩＤ数据的安全性与私密 性．ＲＦＩＤ系统的安全威胁主要来自于阅读器对标 签的非法访问以及伪造标签的存在．对ＲＦＩＤ系统 而言，其安全问题是指存在伪造标签时，如何有效地 对标签进行认证；其隐私问题是指存在恶意阅读器 时，如何防止阅读器对标签的非法访问，来有效地保 护用户的隐私．在常用的网络安全解决方案中，已经 存在成熟的加解密算法如ＤＥＳ、ＡＥＳ、ＲＳＡ、椭圆曲 线密码等，这些算法构成了对称密钥加密以及公开 密钥加密中的支撑技术，能够有效地实现加密与鉴 别功能，抵制非法读取、伪装哄骗、重放攻击等安全 威胁，具有良好的安全性．但实现上述算法需要较多 的逻辑处理单元，如ＡＥＳ需要大约２００００～３００００ 个逻辑门，ＲＳＡ、椭圆曲线密码等公钥密码算法则需 要更多的逻辑门．而ＲＦＩＤ标签受到低成本限制，通 常只能拥有大约５０００～１００００个逻辑门，并且这些 逻辑门主要用于实现一些最基本的标签功能，仅剩 少许可用于实现安全功能．此外，ＲＦＩＤ标签上的存 储资源也非常受限，通常标签的ＥＰＣ区仅能存储 ９６ｂｉｔ数据，用户区仅能存储５１２ｂｉｔ数据．ＲＦＩＤ标 签极其有限的计算资源难以支持上述复杂的加解密 算法的实现．因此，对ＲＦＩＤ系统而言，其安全与隐 私保障机制所面临的最大挑战在于：如何以一种轻 量级的方式在资源极其受限的ＲＦＩＤ系统上实现认 证与隐私保护协议．下面我们从基于物理方法的安 全保护机制、基于对称密钥加密的协议以及基于 Ｈａｓｈ函数的协议等几个方面来具体阐述相关研究 成果．３．２基于物理方法的安全保护机制 ＲＦＩＤ的隐私问题是由阅读器识别标签时无需 认证引起的．在没有隐私保障机制的情况下，阅读器 可以随意地对标签进行秘密扫描，获取标签信息；对 于无法直接获取信息的加密标签则可以根据反馈的 加密信息进行跟踪，获得用户的地点信息，综合整理 就形成了对用户个人信息的盘点．为了保护ＲＦＩＤ 用户隐私，一种简单直接的手段便是基于物理方法 的安全保护机制，具体而言，主要包括灭活操作、静 电屏蔽、主动干扰以及阻塞法等． 灭活（Ｋｉｌｌ）操作是一种简单暴力的方法，阅读 器通过向标签发送一个指定的ＰＩＮ码来执行杀死 命令，命令执行完后标签就失效了，不再对阅读器的 查询做出回应．显然，完全地让标签失效并不是一个 合理的解决方案．文献［２５］提出可以只让标签中唯 一识别码失效而保留产品类型标识码的数据部分， 这样就可以避免标签被跟踪，但是该方案使标签失 去了唯一标识物品的特性．文献［２６］提出采用全新 的标识符重新对标签进行标识的方案，原有的标识 ４６２ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 463 符可以在物品被回收等情况下重新被激活使用.由 RFID标签实现有效认证，但却无法保护标签的隐 此来看，灭活操作使标签丧失功能，不可能再被重 私.由于在步骤1标签需要事先将标识号T:发送至 用，从而阻止对标签的任意读取和跟踪；而需要考虑 阅读器，所有邻近的阅读器都能够读取该标识信息， 到重用的场合可以采取休眠(Sleep)机制2)，原理与 这种方式完全暴露了标签的隐私：另一方面，如果不 前者相似，但是实施休眠机制的标签可以被唤醒再 发送标识号T,,则阅读器很难迅速地定位到对应的 次使用.静电屏蔽是指将标签放入具有静电屏蔽功 密钥k:来支持后续操作.为了在实现认证的同时保 能的容器中，使其不能与外界进行电磁耦合，阻止标 障隐私，事实上存在一种简单直接但性能低下的方 签被扫描，这种方法需要一个额外的物理设备，如法 法：相比于算法1，标签无需传输标识T:,而是直接 拉第网罩.主动干扰是指通过一个设备主动广播干 根据接收的挑战数R发送加密密文C=E。[R].阅 扰信号来阻止或破坏附近的非授权阅读器对标签的 读器接收到加密密文C后，在本地遍历所有可能的 读写操作.文献[27]提出了一套基于掩码的主动干 k计算C:=E[R],如果存在某个k:使得C:=C,则 扰机制.当阅读器在读取标签ID时，标签周围的保 通常情况下该密钥对应的标签即为当前认证的标签 护设备会同时传输一串掩码序列信号，最终阅读器 假设搜索空间存在个标签，该算法密钥搜索的时间 接收到标识符ID与掩码相混杂的信号.这种机制 复杂度为O(n),当n数值很大时，其搜索时间开销是 使得授权的阅读器能够使用该掩码序列有效恢复标 巨大的.针对上述问题，很多研究工作开始关注于如 签的标识符，而未授权的阅读器由于无法获取该掩 何根据加密密文进行快速的数据搜索.文献[30]提出 码序列的模式，从而无法对接收的混杂信号进行有 了基于对称密钥的加密数据搜索系统.文献[31-32] 效恢复.阻塞法采用一个特殊的阻止标签，通过设定 也提出了基于加密数据库的查询系统.我们也在该 的标签冲突算法来阻止未授权的阅读器读取那些受 方面开展了研究工作，文献[33]通过在标签上维护 保护的标签.文献[28]提出了上述阻止标签的理念， 一个单调增的计数器，从而利用二叉搜索方案来进 通过编入标签的可修改位来保护隐私，若隐私位为 行快速的搜索，将时间复杂度降低至O(logn). “0'表示可公开扫描，为‘1？则表示是私有区域.当阅 在基于对称密钥加密协议中，当密钥：的长度 读器访问私有区域时，采用一个特殊的阻止标签来 足够大时（不小于128位），仅仅根据比特串R和C 实行干扰，从而阻止未授权的阅读器非法读取受保 是很难在短时间内使用普通的计算设备推算出密钥 护的标签。 k:的，协议安全性高，但是，由于RFD标签成本的 3.3基于对称密钥加密的协议 限制，标签内部存储单元通常少于512bit,逻辑门的 公开密钥加密算法虽然功能强大，能够有效地 数目也相当受限，实际使用在RFD系统中的比特 实现加密、电子签名等机制，但由于其复杂的计算操 串R和C以及密钥k:的长度都远小于达到正常安 作使其根本无法在资源异常受限的RFID系统上实 全标准所期望的数目.例如，德州仪器公司研发了用 现.因此，RFID系统往往借助于逻辑较为简单的对 于汽车防盗系统中的加密RFID标签，出于标签成 称密钥加密算法来实现安全与隐私保障机制.具体 本的考虑，挑战数R与密钥k:的长度仅为40bit,标签 来说，基于对称密钥加密的协议可以用来对标签进 响应结果C仅为24bit.在这种情况下完全可以通 行有效认证.在该协议中，任一标签与阅读器共享一 过逆向工程、密码破解等技术来破解该加密系统，针 个对称密钥.算法1阐述了使用对称密钥加密算法 对上述问题，研究者们提出了各种轻量级解决方案 对RFID标签进行认证的过程[2] 来保障安全性.其中，DESL[3)是在传统的加密协议 算法1.使用对称密钥加密算法对RFID标 DES基础上为适应小型计算设备（如RFID标签）要 签进行认证， 求的一种轻量级的扩展，是一套超低成本的加密算 1.标签向阅读器发送数值T,表明身份。 法.HIGHT3)是一种分组加密算法，它使用64位 2.阅读器生成一个随机的比特串R,发送至标签 的分组块和128位的密钥，子密钥只在加密和解密 3.标签用密钥k对比特串R进行加密，计算C= 的运行过程中被生成，对硬件资源的要求很低。 E[R],将C发送至标签. 3.4基于Hash函数的协议 4.阅读器本地计算C=E,[R],验证是否有C=C,若 相比于对称密钥加密协议，采用Hash函数可 是，则标签被成功认证. 以在多数情况下实现等效的安全机制，且实现逻辑 上述基于对称密钥加密的协议虽然能够对 会大为简化.因此，近年来很多研究工作关注于在
符可以在物品被回收等情况下重新被激活使用．由 此来看，灭活操作使标签丧失功能，不可能再被重 用，从而阻止对标签的任意读取和跟踪；而需要考虑 到重用的场合可以采取休眠（Ｓｌｅｅｐ）机制［２６］，原理与 前者相似，但是实施休眠机制的标签可以被唤醒再 次使用．静电屏蔽是指将标签放入具有静电屏蔽功 能的容器中，使其不能与外界进行电磁耦合，阻止标 签被扫描，这种方法需要一个额外的物理设备，如法 拉第网罩．主动干扰是指通过一个设备主动广播干 扰信号来阻止或破坏附近的非授权阅读器对标签的 读写操作．文献［２７］提出了一套基于掩码的主动干 扰机制．当阅读器在读取标签犐犇时，标签周围的保 护设备会同时传输一串掩码序列信号，最终阅读器 接收到标识符犐犇与掩码相混杂的信号．这种机制 使得授权的阅读器能够使用该掩码序列有效恢复标 签的标识符，而未授权的阅读器由于无法获取该掩 码序列的模式，从而无法对接收的混杂信号进行有 效恢复．阻塞法采用一个特殊的阻止标签，通过设定 的标签冲突算法来阻止未授权的阅读器读取那些受 保护的标签．文献［２８］提出了上述阻止标签的理念， 通过编入标签的可修改位来保护隐私，若隐私位为 ‘０’表示可公开扫描，为‘１’则表示是私有区域．当阅 读器访问私有区域时，采用一个特殊的阻止标签来 实行干扰，从而阻止未授权的阅读器非法读取受保 护的标签． ３．３基于对称密钥加密的协议 公开密钥加密算法虽然功能强大，能够有效地 实现加密、电子签名等机制，但由于其复杂的计算操 作使其根本无法在资源异常受限的ＲＦＩＤ系统上实 现．因此，ＲＦＩＤ系统往往借助于逻辑较为简单的对 称密钥加密算法来实现安全与隐私保障机制．具体 来说，基于对称密钥加密的协议可以用来对标签进 行有效认证．在该协议中，任一标签与阅读器共享一 个对称密钥．算法１阐述了使用对称密钥加密算法 对ＲＦＩＤ标签进行认证的过程［２９］． 算法１．使用对称密钥加密算法对ＲＦＩＤ标 签进行认证． １．标签向阅读器发送数值犜犻表明身份． ２．阅读器生成一个随机的比特串犚，发送至标签． ３．标签用密钥犽犻对比特串犚进行加密，计算犆＝ 犈犽犻［犚］，将犆发送至标签． ４．阅读器本地计算犆′＝犈犽犻［犚］，验证是否有犆＝犆′，若 是，则标签被成功认证． 上述基于对称密钥加密的协议虽然能够对 ＲＦＩＤ标签实现有效认证，但却无法保护标签的隐 私．由于在步骤１标签需要事先将标识号犜犻发送至 阅读器，所有邻近的阅读器都能够读取该标识信息， 这种方式完全暴露了标签的隐私；另一方面，如果不 发送标识号犜犻，则阅读器很难迅速地定位到对应的 密钥犽犻来支持后续操作．为了在实现认证的同时保 障隐私，事实上存在一种简单直接但性能低下的方 法：相比于算法１，标签无需传输标识犜犻，而是直接 根据接收的挑战数犚发送加密密文犆＝犈犽犻［犚］．阅 读器接收到加密密文犆后，在本地遍历所有可能的 犽犻计算犆犻＝犈犽犻［犚］，如果存在某个犽犻使得犆犻＝犆，则 通常情况下该密钥对应的标签即为当前认证的标签． 假设搜索空间存在狀个标签，该算法密钥搜索的时间 复杂度为犗（狀），当狀数值很大时，其搜索时间开销是 巨大的．针对上述问题，很多研究工作开始关注于如 何根据加密密文进行快速的数据搜索．文献［３０］提出 了基于对称密钥的加密数据搜索系统．文献［３１３２］ 也提出了基于加密数据库的查询系统．我们也在该 方面开展了研究工作，文献［３３］通过在标签上维护 一个单调增的计数器，从而利用二叉搜索方案来进 行快速的搜索，将时间复杂度降低至犗（ｌｏｇ狀）． 在基于对称密钥加密协议中，当密钥犽犻的长度 足够大时（不小于１２８位），仅仅根据比特串犚和犆 是很难在短时间内使用普通的计算设备推算出密钥 犽犻的，协议安全性高．但是，由于ＲＦＩＤ标签成本的 限制，标签内部存储单元通常少于５１２ｂｉｔ，逻辑门的 数目也相当受限，实际使用在ＲＦＩＤ系统中的比特 串犚和犆以及密钥犽犻的长度都远小于达到正常安 全标准所期望的数目．例如，德州仪器公司研发了用 于汽车防盗系统中的加密ＲＦＩＤ标签，出于标签成 本的考虑，挑战数犚与密钥犽犻的长度仅为４０ｂｉｔ，标签 响应结果犆仅为２４ｂｉｔ．在这种情况下完全可以通 过逆向工程、密码破解等技术来破解该加密系统．针 对上述问题，研究者们提出了各种轻量级解决方案 来保障安全性．其中，ＤＥＳＬ［３４］是在传统的加密协议 ＤＥＳ基础上为适应小型计算设备（如ＲＦＩＤ标签）要 求的一种轻量级的扩展，是一套超低成本的加密算 法．ＨＩＧＨＴ［３５］是一种分组加密算法，它使用６４位 的分组块和１２８位的密钥，子密钥只在加密和解密 的运行过程中被生成，对硬件资源的要求很低． ３．４基于犎犪狊犺函数的协议 相比于对称密钥加密协议，采用Ｈａｓｈ函数可 以在多数情况下实现等效的安全机制，且实现逻辑 会大为简化．因此，近年来很多研究工作关注于在 ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４６３
464 计算 机 学 报 2013年 RFID系统中采用基于Hash函数的协议来实现一 多次扫描标签，使得标签与阅读器之间失去同步，导 套足够轻量级的安全与隐私保障机制.尽管Hash 致阅读器在认证时无法设定每个可能的标签ID需 函数的逻辑实现已经相对简单，但是由于RFID标 要的计算次数，使系统无法正常工作， 签的资源稀缺性，Hash函数的常用逻辑实现还是 表3对上述3种方案从效果、适用范围以及标 超出标签的资源限制.为此，需要确保实现Hash函 签所需资源3个方面进行了具体的比较.可以看出， 数的逻辑电路足够简单.研究发现2o],Hash数值可 3种方案各有利弊，需要根据具体的应用需求与资 以从一个预先存储的随机比特序列中推导：首先，使 源限制条件来选择合理的安全与隐私保障方案.目 用离线的随机数生成器以标签D为种子生成一个 前，国内的研究者们也在RFID的安全与隐私保障 200bit的随机序列，将其存储在标签内部；该比特 方面开展了深入的研究.文献[39]分析了已有的各 序列首尾相连形成一个逻辑上的环结构；当执行 种RFID安全机制，重点介绍了基于密码技术的 Hash操作H(ID,r)时，即在上述环结构序列中返 RFID安全协议，分析了这些协议的缺陷，讨论了基 回第个比特以后一串指定长度的比特序列.这样， 于可证明的安全性理论来设计和分析RFID安全协 200个随机比特组成的序列可以返回200个不同的 议的模型和方法.文献[40]定义了供应链环境下 Hash数值，在通常情况下足够满足一般的应用 RFID通信协议必须满足的安全需求，提出了一个 需求. 可以满足这些安全需求的通用可组合安全模型， 基于Hash函数的安全协议主要包括Hash- 设计了一个可以实现该模型的轻量级RFID通信 Lock协议、随机化Hash-Lock协议以及Hash链协 协议 议等.Hash-Lock协议[as]使用了metaID(标签密钥 的Hash值)代替真实的标签ID,来有效地对阅读 表33种方案的比较 器进行认证，从而避免标签信息泄露.然而，由于 效果 适用范围 标签所需资源 基于物理方标签实现逻辑非常适用于对处理能对标签的资源要 metaID对特定的标签始终保持不变，因此标签每次 法的安全保简单，不需要标签力非常有限的被求非常低，需要 响应都使用固定的metaID,容易受到追踪和重放攻 护机制 自身实现安全与隐动标签进行安全 额外的设备提供 私保障 保护的场合 安全隐私保障 击.随机化Hash-Lock协议[)采用了基于随机数的 基于对称密标签实现逻辑较适用于主动标签对标签资源要 询问/应答机制：在阅读器请求访问标签时，标签先 钥加密的为复杂，能有效实或处理能力较强求较高 协议 现加密、解密操作 的被动标签需要 用伪随机数生成器生成一个随机数R,然后计算其 进行加密、解密 的场合 ID和R的Hash值Hkcw(ID‖R),最后将随机数R 基于Hash标签实现逻辑较适用于处理能力对标签的资源 与该Hash值发送给阅读器.阅读器在后台数据库 函数的协议为简单，其有“前向较弱的被动标签要求低 中进行穷举搜索，计算所有ID和R的Hash值 安全性”，不能实需要认证的场合 现加密，解密操作 Hkey(ID‖R),将匹配成功的ID发送给标签，实现 解锁.上述这种方式能够避免标签每次响应固定模 3.5 其它解决方案 式的信息，故而不能对其进行跟踪.但是，随机化 近年来，为了更有效地防止针对RFID系统的 Hash-Lock协议不能防止重放攻击.攻击者完全可以 黑客攻击，一些研究者开始关注入侵检测系统在 窃听随机数R以及对应的Hash值Hkew(IDIR), RFID系统中的应用.由于RFID标签处理能力非常 从而在阅读器查询时重放该响应伪装为该标签.其 有限，不可能在标签上实现入侵检测的逻辑.因此， 次，阅读器端的穷举搜索使得该方法缺乏很强的可 文献[41]基于小型电池装置设计了一套RFID守护 扩展性.Hash链协议[s8]是基于共享秘密的询问/应 系统.该系统集成了多种安全机制，包括密钥管理、 答协议，在该协议中，标签和阅读器共享两个Hash 访问控制、认证以及审计功能，尽管集成了多种安全 函数G和H以及一个随机的初始化标识符s1.当阅 功能，该系统却很容易出现单点失效的问题：一旦守 读器请求访问标签时，标签返回当前标识符.= 护系统被攻克，整个RFD网络都被暴露在各种攻 G(s),同时更新当前标识符为s+1=H(s).阅读器 击隐患之下.文献[42]进一步提出了一个入侵检测 根据获得的“值查找数据库对标签进行认证，并更 系统模型Deckard,用来检测标签所有权的改变.该 新s值与标签保持同步.该方法利用Hash函数的 系统是RFD入侵检测系统的早期研究工作之一 “前向安全性”使得标签响应的结果随每次查询不停 文献[43]基于RFID系统设计了一套入侵检测系统 更新，有效防止了重放攻击，但是，攻击者可以恶意 安全框架，在RFID阅读器层面以及中间件层面实
ＲＦＩＤ系统中采用基于Ｈａｓｈ函数的协议来实现一 套足够轻量级的安全与隐私保障机制．尽管Ｈａｓｈ 函数的逻辑实现已经相对简单，但是由于ＲＦＩＤ标 签的资源稀缺性，Ｈａｓｈ函数的常用逻辑实现还是 超出标签的资源限制．为此，需要确保实现Ｈａｓｈ函 数的逻辑电路足够简单．研究发现［２０］，Ｈａｓｈ数值可 以从一个预先存储的随机比特序列中推导：首先，使 用离线的随机数生成器以标签犐犇为种子生成一个 ２００ｂｉｔ的随机序列，将其存储在标签内部；该比特 序列首尾相连形成一个逻辑上的环结构；当执行 Ｈａｓｈ操作犎（犐犇，狉）时，即在上述环结构序列中返 回第狉个比特以后一串指定长度的比特序列．这样， ２００个随机比特组成的序列可以返回２００个不同的 Ｈａｓｈ数值，在通常情况下足够满足一般的应用 需求．基于Ｈａｓｈ函数的安全协议主要包括Ｈａｓｈ Ｌｏｃｋ协议、随机化ＨａｓｈＬｏｃｋ协议以及Ｈａｓｈ链协 议等．ＨａｓｈＬｏｃｋ协议［３６］使用了犿犲狋犪犐犇（标签密钥 的Ｈａｓｈ值）代替真实的标签犐犇，来有效地对阅读 器进行认证，从而避免标签信息泄露．然而，由于 犿犲狋犪犐犇对特定的标签始终保持不变，因此标签每次 响应都使用固定的犿犲狋犪犐犇，容易受到追踪和重放攻 击．随机化ＨａｓｈＬｏｃｋ协议［３７］采用了基于随机数的 询问／应答机制：在阅读器请求访问标签时，标签先 用伪随机数生成器生成一个随机数犚，然后计算其 犐犇和犚的Ｈａｓｈ值犎ｋｅｙ（犐犇‖犚），最后将随机数犚 与该Ｈａｓｈ值发送给阅读器．阅读器在后台数据库 中进行穷举搜索，计算所有犐犇和犚的Ｈａｓｈ值 犎ｋｅｙ（犐犇‖犚），将匹配成功的犐犇发送给标签，实现 解锁．上述这种方式能够避免标签每次响应固定模 式的信息，故而不能对其进行跟踪．但是，随机化 ＨａｓｈＬｏｃｋ协议不能防止重放攻击．攻击者完全可以 窃听随机数犚以及对应的Ｈａｓｈ值犎ｋｅｙ（犐犇‖犚）， 从而在阅读器查询时重放该响应伪装为该标签．其 次，阅读器端的穷举搜索使得该方法缺乏很强的可 扩展性．Ｈａｓｈ链协议［３８］是基于共享秘密的询问／应 答协议，在该协议中，标签和阅读器共享两个Ｈａｓｈ 函数犌和犎以及一个随机的初始化标识符狊１．当阅 读器请求访问标签时，标签返回当前标识符狉犽＝ 犌（狊犽），同时更新当前标识符为狊犽＋１＝犎（狊犽）．阅读器 根据获得的狉犽值查找数据库对标签进行认证，并更 新狊值与标签保持同步．该方法利用Ｈａｓｈ函数的 “前向安全性”使得标签响应的结果随每次查询不停 更新，有效防止了重放攻击．但是，攻击者可以恶意 多次扫描标签，使得标签与阅读器之间失去同步，导 致阅读器在认证时无法设定每个可能的标签犐犇需 要的计算次数，使系统无法正常工作． 表３对上述３种方案从效果、适用范围以及标 签所需资源３个方面进行了具体的比较．可以看出， ３种方案各有利弊，需要根据具体的应用需求与资 源限制条件来选择合理的安全与隐私保障方案．目 前，国内的研究者们也在ＲＦＩＤ的安全与隐私保障 方面开展了深入的研究．文献［３９］分析了已有的各 种ＲＦＩＤ安全机制，重点介绍了基于密码技术的 ＲＦＩＤ安全协议，分析了这些协议的缺陷，讨论了基 于可证明的安全性理论来设计和分析ＲＦＩＤ安全协 议的模型和方法．文献［４０］定义了供应链环境下 ＲＦＩＤ通信协议必须满足的安全需求，提出了一个 可以满足这些安全需求的通用可组合安全模型， 设计了一个可以实现该模型的轻量级ＲＦＩＤ通信 协议． 表３３种方案的比较 效果 适用范围 标签所需资源 基于物理方 法的安全保 护机制 标签实现逻辑非常 简单，不需要标签 自身实现安全与隐 私保障 适用于对处理能 力非常有限的被 动标签进行安全 保护的场合 对标签的资源要 求非常低，需要 额外的设备提供 安全隐私保障 基于对称密 钥加密的 协议 标签实现逻辑较 为复杂，能有效实 现加密、解密操作 适用于主动标签 或处理能力较强 的被动标签需要 进行加密、解密 的场合 对标签资源要 求较高 基于Ｈａｓｈ 函数的协议 标签实现逻辑较 为简单，具有“前向 安全性”，不能实 现加密、解密操作 适用于处理能力 较弱的被动标签 需要认证的场合 对标签的资源 要求低 ３．５其它解决方案 近年来，为了更有效地防止针对ＲＦＩＤ系统的 黑客攻击，一些研究者开始关注入侵检测系统在 ＲＦＩＤ系统中的应用．由于ＲＦＩＤ标签处理能力非常 有限，不可能在标签上实现入侵检测的逻辑．因此， 文献［４１］基于小型电池装置设计了一套ＲＦＩＤ守护 系统．该系统集成了多种安全机制，包括密钥管理、 访问控制、认证以及审计功能，尽管集成了多种安全 功能，该系统却很容易出现单点失效的问题：一旦守 护系统被攻克，整个ＲＦＩＤ网络都被暴露在各种攻 击隐患之下．文献［４２］进一步提出了一个入侵检测 系统模型Ｄｅｃｋａｒｄ，用来检测标签所有权的改变．该 系统是ＲＦＩＤ入侵检测系统的早期研究工作之一． 文献［４３］基于ＲＦＩＤ系统设计了一套入侵检测系统 安全框架，在ＲＦＩＤ阅读器层面以及中间件层面实 ４６４ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 465 现了入侵检测的功能.该系统利用阅读器之间的通 (4)标签的分布与部署.对阅读器的发射功率而言， 信来获取攻击检测所需的审计信息，将RFD阅读 功率过小，阅读器有效通信范围减小，使得某些标签 器作为“看门狗”来从周围的阅读器与标签中收集所 无法被激活，或者由于反射信号能量过小，低于信噪 需信息，提供了一套更为泛化的安全框架来检测多 比从而使阅读器无法有效识别；功率过大，阅读器有 样化的RFID攻击.总体说来，随着RFID的进一步 效通信范围增大，使得某些标签反射的信号能量增 广泛应用，RFD系统的入侵检测方案将会受到越 大，导致标签之间的信号干扰增大.对能量吸收、路 来越多的关注。 径损耗、多径效应而言，这三者都会引起信号衰弱， 大幅度降低发射信号到达标签的能量以及反射信号 4 真实环境下RFID系统的 到达阅读器的能量，导致信号难以识别.对信号干扰 性能评测与分析 而言，标签与标签之间、标签与阅读器之间、阅读器 与阅读器之间都存在发射/反射信号的干扰，导致 很多RFID的前期研究工作主要考虑在相对理 比特差错，降低传输效率.对标签的分布与部署而 想的传输环境下如何对RFID数据收集算法与协议 言，标签部署过于密集，会导致阅读器的发射能量 参数进行优化，并通过模拟实验来验证其性能.事实 被充分稀释，并且反射信号间的干扰与能量吸收 上，对于RFID系统而言，真实传输环境中的一些物 会加剧；过于稀疏会导致其超出阅读器扫描范围： 理因素包括路径损耗、能量吸收、信号干扰等给物理 而对于单个标签，如果标签平面（即标签天线方向） 层的信号传输带来了极大的不可靠性，由此对基于 与能量穿透方向平行，则无法产生足够强度的反射 防冲突算法的RFD数据收集机制的性能也带来了 信号，应使标签平面与能量穿透方向尽可能正交.表 很大的影响.具体说来，真实传输环境下影响RFID 4具体阐述了这些因素对RFID系统具体性能参数 系统性能的关键因素包括：(1)阅读器的发射功率； 的影响，包括RFID系统的扫描范围、阅读速率以及 (2)能量吸收、路径损耗、多径效应；(3)信号干扰： 能量消耗。 表4关键因素对系统性能各指标的影响 扫描范围 阅读速率 能量消耗 阅读器的发射 功率过小，阅读器有效通信范围减 功奉过小，使得某些标签无法被激活或有效 功率过小，能量消耗小：功率过大， 功率 小：功率过大，阅读器有效通信范围 识别，降低阅读速率：功率过大，使得部分标 能量消耗大 增大 签反射信号强度增大，导致标签间信号干扰 增大，降低阅读速率 能量吸收、路径 会引起信号衰减，减小阅读器有效 使得正常通信范围内某些标签无法被激活或 使得阅读器必须要增加功率来补偿 损耗、多径效应 通信范围 有效识别，降低阅读速率 传输中信号能量损失，增加能耗 信号干扰 某些标签反射信号会受到干扰无法 导致传输比特差错，降低阅读速率 阅读器需要合理调整功率来避免过 被有效识别，阅读器有效通信范固 多信号干扰，会改变阅读器能量 减小 消耗 标签的分布与 标签的密集部署会影响阅读器天线 如果使标签天线方向与能量穿透方向尽可能 标签分布部署不合理会使得阅读器 部署 的电磁场分布，改变阅读器有效通 正交，读取效率增大，阅读速率提升：否则，阅 必须要增加功率来提升反射信号强 信范固 读速率下降 度，增加能耗 上述因素在真实传输环境下的普遍存在性使得 性能，并且由于物理层与MAC层没有进行有效整 理想情况下推导出的算法与优化参数在实际情况下 合，导致明显的性能下降.文献[46]利用简单、经验 的性能很难得到保障.因此，目前该领域的很多研究 性的实验手段验证了当前RFD系统识别标签的各 工作者关注在真实应用环境下对RFD系统实际性 项性能参数，作者通过在不同的传输环境下（包括自 能的测试与分析.为了说明物理层差错对EPC 由空间、接近水，接近金属环境)，改变通信距离检验 C1G2RFID系统的影响，文献[44幻给出了模拟实验 了各项性能参数.文献[47]针对RFID系统给出了 结果，证明了物理层的比特差错极大地降低了系统 一个综合的性能基准，通过这些基准能够描述在真 的整体性能.文献[45]在真实环境设置下检验了 实环境下RFID系统的运作效率.文献[48]在真实 RFID系统的读取性能，确定了导致整体性能和可 环境设定下对RFD系统性能进行了验证，发现在 靠性降低的物理层因素.他们发现物理层实际的环 阅读器的有效探测范围内存在两个不同的区域：主 境参数以及相关配置参数的设置极大地影响了读取 探测区域和次探测区域.主探测区域是指靠近读取
现了入侵检测的功能．该系统利用阅读器之间的通 信来获取攻击检测所需的审计信息，将ＲＦＩＤ阅读 器作为“看门狗”来从周围的阅读器与标签中收集所 需信息，提供了一套更为泛化的安全框架来检测多 样化的ＲＦＩＤ攻击．总体说来，随着ＲＦＩＤ的进一步 广泛应用，ＲＦＩＤ系统的入侵检测方案将会受到越 来越多的关注． ４真实环境下犚犉犐犇系统的 性能评测与分析 很多ＲＦＩＤ的前期研究工作主要考虑在相对理 想的传输环境下如何对ＲＦＩＤ数据收集算法与协议 参数进行优化，并通过模拟实验来验证其性能．事实 上，对于ＲＦＩＤ系统而言，真实传输环境中的一些物 理因素包括路径损耗、能量吸收、信号干扰等给物理 层的信号传输带来了极大的不可靠性，由此对基于 防冲突算法的ＲＦＩＤ数据收集机制的性能也带来了 很大的影响．具体说来，真实传输环境下影响ＲＦＩＤ 系统性能的关键因素包括：（１）阅读器的发射功率； （２）能量吸收、路径损耗、多径效应；（３）信号干扰； （４）标签的分布与部署．对阅读器的发射功率而言， 功率过小，阅读器有效通信范围减小，使得某些标签 无法被激活，或者由于反射信号能量过小，低于信噪 比从而使阅读器无法有效识别；功率过大，阅读器有 效通信范围增大，使得某些标签反射的信号能量增 大，导致标签之间的信号干扰增大．对能量吸收、路 径损耗、多径效应而言，这三者都会引起信号衰弱， 大幅度降低发射信号到达标签的能量以及反射信号 到达阅读器的能量，导致信号难以识别．对信号干扰 而言，标签与标签之间、标签与阅读器之间、阅读器 与阅读器之间都存在发射／反射信号的干扰，导致 比特差错，降低传输效率．对标签的分布与部署而 言，标签部署过于密集，会导致阅读器的发射能量 被充分稀释，并且反射信号间的干扰与能量吸收 会加剧；过于稀疏会导致其超出阅读器扫描范围； 而对于单个标签，如果标签平面（即标签天线方向） 与能量穿透方向平行，则无法产生足够强度的反射 信号，应使标签平面与能量穿透方向尽可能正交．表 ４具体阐述了这些因素对ＲＦＩＤ系统具体性能参数 的影响，包括ＲＦＩＤ系统的扫描范围、阅读速率以及 能量消耗． 表４关键因素对系统性能各指标的影响 扫描范围 阅读速率 能量消耗 阅读器的发射 功率 功率过小，阅读器有效通信范围减 小；功率过大，阅读器有效通信范围 增大 功率过小，使得某些标签无法被激活或有效 识别，降低阅读速率；功率过大，使得部分标 签反射信号强度增大，导致标签间信号干扰 增大，降低阅读速率 功率过小，能量消耗小；功率过大， 能量消耗大 能量吸收、路径 损耗、多径效应 会引起信号衰减，减小阅读器有效 通信范围 使得正常通信范围内某些标签无法被激活或 有效识别，降低阅读速率 使得阅读器必须要增加功率来补偿 传输中信号能量损失，增加能耗 信号干扰 某些标签反射信号会受到干扰无法 被有效识别，阅读器有效通信范围 减小 导致传输比特差错，降低阅读速率 阅读器需要合理调整功率来避免过 多信号干扰，会改变阅读器能量 消耗 标签的分布与 部署 标签的密集部署会影响阅读器天线 的电磁场分布，改变阅读器有效通 信范围 如果使标签天线方向与能量穿透方向尽可能 正交，读取效率增大，阅读速率提升；否则，阅 读速率下降 标签分布部署不合理会使得阅读器 必须要增加功率来提升反射信号强 度，增加能耗 上述因素在真实传输环境下的普遍存在性使得 理想情况下推导出的算法与优化参数在实际情况下 的性能很难得到保障．因此，目前该领域的很多研究 工作者关注在真实应用环境下对ＲＦＩＤ系统实际性 能的测试与分析．为了说明物理层差错对ＥＰＣ Ｃ１Ｇ２ＲＦＩＤ系统的影响，文献［４４］给出了模拟实验 结果，证明了物理层的比特差错极大地降低了系统 的整体性能．文献［４５］在真实环境设置下检验了 ＲＦＩＤ系统的读取性能，确定了导致整体性能和可 靠性降低的物理层因素．他们发现物理层实际的环 境参数以及相关配置参数的设置极大地影响了读取 性能，并且由于物理层与ＭＡＣ层没有进行有效整 合，导致明显的性能下降．文献［４６］利用简单、经验 性的实验手段验证了当前ＲＦＩＤ系统识别标签的各 项性能参数，作者通过在不同的传输环境下（包括自 由空间、接近水、接近金属环境），改变通信距离检验 了各项性能参数．文献［４７］针对ＲＦＩＤ系统给出了 一个综合的性能基准，通过这些基准能够描述在真 实环境下ＲＦＩＤ系统的运作效率．文献［４８］在真实 环境设定下对ＲＦＩＤ系统性能进行了验证，发现在 阅读器的有效探测范围内存在两个不同的区域：主 探测区域和次探测区域．主探测区域是指靠近读取 ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４６５
466 计算 机 学报 2013年 器的一段探测区域，在该区域内具有很高的标签识 传感网定位等.其中，GPS定位与蜂窝基站定位主 别概率（接近100%）：次探测区域是指从主探测区 要用于室外定位，WLAN定位、传感网定位主要用 域末端延伸至有效识别范围边缘的一段探测区域， 于室内定位.RFID定位技术以低成本、非接触性 在该区域内标签识别率依照线性关系降低为0.文 通信等特点，有望成为室内定位技术的首选.目前 献[49-50]研究了在真实传输环境下阅读器发射功 的室内定位系统大多基于RSSI(Received Signal 率对大规模标签识别性能的影响，通过实验发现， Strength Indicator)来辅助定位，其基本原理是：已 RFID标签在激活状态与非激活状态之间存在一个 知发射信号的强度，接收方根据接收到的信号强度， 中间状态(Lossy State),对识别性能影响很大.由此 估算出通信双方的距离.而在实际情况下，无线信号 作者提出了自动功率调节算法，进一步降低了阅读 在空间传播时能量的衰减不仅受传播距离的影响， 器的总体能耗与扫描时延.文献[51]通过真实实验 还受到多径效应、传播的方向性、复杂的室内结构、 发现，当阅读器功率被调整至合理范围时，可以利用 随机流动的人员等诸多不确定因素的影响，利用 遏止效应(Capture Effect)来有效地将冲突时隙转 RSSI作为位置感知数据进行室内定位存在较多的 化为单时隙，由此提出了渐进的扫描算法来优化读 困难.但是由于RSSI极易获取，不需要额外的设 取性能.文献[52]提出了无源RFD系统中能量有 备，相比于其它定位技术成本非常低，因此当前主流 效的物理层设计方法，在前向链路中为使标签获得 的RFID定位技术都是基于RSSI进行定位.其中比 更多能量，结合ASK调制提出了一种新的用于无 较典型的代表是SpotON系统与LANDMARC系 源RFID系统的能量有效的数据编码方法，上述研 统.SpotON系统[s3]基于阅读器与目标标签构造了 究成果表明，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基于RFD的定位机制 (2)获取数据量大质低，存在大量冗余数据，无法实 目前的定位系统主要包括GPS(Global Posi- 时抽取信息与有效利用.研究者们发现，当人体经过 tioning System)定位、蜂窝基站定位、WLAN定位、 RFID阅读器天线与标签之间的空间时，由于人体
器的一段探测区域，在该区域内具有很高的标签识 别概率（接近１００％）；次探测区域是指从主探测区 域末端延伸至有效识别范围边缘的一段探测区域， 在该区域内标签识别率依照线性关系降低为０．文 献［４９５０］研究了在真实传输环境下阅读器发射功 率对大规模标签识别性能的影响，通过实验发现， ＲＦＩＤ标签在激活状态与非激活状态之间存在一个 中间状态（ＬｏｓｓｙＳｔａｔｅ），对识别性能影响很大．由此 作者提出了自动功率调节算法，进一步降低了阅读 器的总体能耗与扫描时延．文献［５１］通过真实实验 发现，当阅读器功率被调整至合理范围时，可以利用 遏止效应（ＣａｐｔｕｒｅＥｆｆｅｃｔ）来有效地将冲突时隙转 化为单时隙，由此提出了渐进的扫描算法来优化读 取性能．文献［５２］提出了无源ＲＦＩＤ系统中能量有 效的物理层设计方法，在前向链路中为使标签获得 更多能量，结合ＡＳＫ调制提出了一种新的用于无 源ＲＦＩＤ系统的能量有效的数据编码方法．上述研 究成果表明，ＲＦＩＤ在ＭＡＣ层、应用层方面的研究 需要充分结合物理层的实际传输特性；否则，理想情 况下设计出的算法与协议将与实际的情况严重不 符，无法达到预期的性能要求． 总体来说，为了有效避免或降低物理环境因素 对系统性能各指标的影响，目前的有效方法主要包 括以下几个方面：（１）调整阅读器功率．通过合理调 整阅读器功率，补偿信号衰减的同时有效避免干扰， 优化系统性能；（２）优化协议参数．设置优化的协议 参数（如帧长、传输速率）来优化读取性能；（３）规划 部署方案．通过调整标签的部署位置、方向以及增 加冗余标签的方式来提升识别性能；（４）改善物理 层设计．采用更合理的编码／解码方案以及通信频 段来提高数据传输可靠性． ５其它开放性问题 上述ＲＦＩＤ数据管理方面的研究工作主要关注 如何能够快速、有效地识别标签的标识信息．事实 上，从数据管理的角度来看，除了标签的标识信息， ＲＦＩＤ系统还能够提供一类非常重要的信息，那就 是标签的反射信号强度．通过对反射信号强度数据 进行有效处理与合理利用，ＲＦＩＤ系统能够实现定 位、追踪以及移动行为感知等机制． ５．１基于犚犉犐犇的定位机制 目前的定位系统主要包括ＧＰＳ（ＧｌｏｂａｌＰｏｓｉ ｔｉｏｎｉｎｇＳｙｓｔｅｍ）定位、蜂窝基站定位、ＷＬＡＮ定位、 传感网定位等．其中，ＧＰＳ定位与蜂窝基站定位主 要用于室外定位，ＷＬＡＮ定位、传感网定位主要用 于室内定位．ＲＦＩＤ定位技术以低成本、非接触性 通信等特点，有望成为室内定位技术的首选．目前 的室内定位系统大多基于ＲＳＳＩ（ＲｅｃｅｉｖｅｄＳｉｇｎａｌ ＳｔｒｅｎｇｔｈＩｎｄｉｃａｔｏｒ）来辅助定位，其基本原理是：已 知发射信号的强度，接收方根据接收到的信号强度， 估算出通信双方的距离．而在实际情况下，无线信号 在空间传播时能量的衰减不仅受传播距离的影响， 还受到多径效应、传播的方向性、复杂的室内结构、 随机流动的人员等诸多不确定因素的影响，利用 ＲＳＳＩ作为位置感知数据进行室内定位存在较多的 困难．但是由于ＲＳＳＩ极易获取，不需要额外的设 备，相比于其它定位技术成本非常低，因此当前主流 的ＲＦＩＤ定位技术都是基于ＲＳＳＩ进行定位．其中比 较典型的代表是ＳｐｏｔＯＮ系统与ＬＡＮＤＭＡＲＣ系 统．ＳｐｏｔＯＮ系统［５３］基于阅读器与目标标签构造了 一个无线感知环境，通过聚合算法减少信号强度误 差，并利用信号传播模型求解阅读器与目标标签的 距离，最后利用三角定位算法对目标在三维空间进 行定位．整体而言，ＳｐｏｔＯＮ是一个实验性的原型系 统，无论是距离估计还是误差处理都停留在比较粗 糙的阶段．ＬＡＮＤＭＡＲＣ系统［５４］在已知位置引入参 考标签，通过对比目标标签与参考标签的ＲＳＳＩ值， 来确定物理坐标关系，最终确定目标标签坐标． ＬＡＮＤＭＡＲＣ通过将参考标签部署到实际应用场 景中，实时同步地对参考标签和目标标签进行能量 值测算，可以最大限度减少多径效应以及电离体对 电磁波的影响，接近精确的定位效果．该系统在较少 阅读器的条件下提高了系统的定位精度，同时也大 大降低了系统成本．除了使用ＲＦＩＤ实现定位机制 之外，一些研究者开始关注基于ＲＦＩＤ定位信息的 查询技术研究．文献［５５］提出了一种新颖的ＲＦＩＤ 系统框架结构，依靠位置相对固定的标签来定位携 带移动式阅读器的监控对象，从而支持高效的移动 范围查询．该文提出了此场景下移动对象位置查询 的一种概率模型，并给出了有效的定位方法． ５．２基于犚犉犐犇的移动行为感知 现有的移动行为监测主要是基于摄像头获取视 频图像来实现的，此类方案具有如下缺点：（１）感知 设备价格昂贵，一些专业摄像头动辄成百上千元； （２）获取数据量大质低，存在大量冗余数据，无法实 时抽取信息与有效利用．研究者们发现，当人体经过 ＲＦＩＤ阅读器天线与标签之间的空间时，由于人体 ４６６ 计 算 机 学 报 ２０１３年