PDF《RFID数 据管 理：算法 、》

第36卷 第3期2013年 3月计算机学报CHI NES E J OURNAL OF COMPUTERS Vo l _3

6 NO .

3 M a r .

2 O1

3 1 R F I D数 据管理 : 算法 、 协议 与性 能评测 谢磊殷亚凤 陈曦陆桑璐 陈道蓄 ( 南京大学计算机软件新技术 国家重点实验室 南京

2 1

0 0

9 3 ) 摘要随着物联网关键理论及技术 的发展 , R F I D作为物联 网的核心支撑技术 , 成为物联 网领域备受关 注的研究 热点之一. 文 中以 R F I D的数据管理为切入点 , 从算法 、 协议 以及性 能评测 3个层 面对 R F I D 的研 究工作进 行 阐述 与分析 , 着重介 绍了 R F I D的防冲突算法 、 认证 与隐私保护协议 以及真实环境下 系统 的性能评测 与分析等方 面的研 究 成果 及进展. 最后 展望了未来的研究方 向. 关键词 射频识别 ;

数据管理 ;

防冲突算法 ;

认证与隐私保护 ;

性能优化 ;

物联 网中图法分类号TP393DOI号10.3724/SP.J.1016.2013.00457RFI D Da t a M a na g e m e nt :Al g o r i t hm s ,Pr o t o c o l s a nd Pe r f o r m a n c e Ev a l u a t i o n XI E Le i YI N Ya ― Fe ng CH EN Xi LU Sa ng ― Lu CH EN Da o ― Xu ( S t a t e Ke y L a b o r a t o r y f o r No v e l S

0 f t wa r e T e c h n o l o g y,Na n j i n g U n i v e r s i t y,Na n j i n g

2 1

0 0

9 3 ) Ab s t r a c t W i t h t he d e v e l o pme nt o f c r i t i c a l t he o r i e s a nd t e c hno l og i e s i n I n t e r n e t o f Thi ng s ( I OT) ,a s a k e y s u p p o r t i n g t e c h n o l o g y,RF I D h a s b e c o me o n e o f t h e h o t s p o t s i n t h e f i e l d o f I n t e r n e t o f Th i ng s .Fo c us i n g o n RFI D d a t a ma n a g e me n t ,t h i s pa p e r d e s c r i b e s a nd a na l y z e s t he r e ― s e a r c h wo r k o n t hr e e a s pe c t s:a l g or i t hm ,pr o t o c ol a n d pe r f o r ma n c e e va l ua t i on . I n t hi s pa pe r ,we i n t r od uc e t he r e s e a r c h p r og r e s s i n RFI D wi t h a nt i ― c ol l i s i o n a l go r i t h m .a ut h e nt i c a t i o n a nd pr i v a c y p r o t e c t i on p r o t oc ol s ,a s we l l a s p e r f o r ma nc e e v a l ua t i o n of RFI D s ys t e m s i n r e a l i s t i c s e t t i ng s .Fi ― n a l l y,we o ut l oo k t he f u t u r e r e s e a r c h di r e c t i o ns a nd c on c l ud e . Ke y wo r d s RFI D ;

d a t a ma n a ge m e nt ;

a n t i ― c o l l i s i on a l go r i t hm ;

a ut h e nt i c a t i o n a nd p r i v a c y p r ot e c t i o n;

p e r f o r m a n c e o p t i m i z a t i o n;

I n t e r n e t o f Th i n g s 引目随着 物联网 时代的来 临,新一代IT技术将 被充 分 运用 在各 行各业 之中. 射 频识 别(RF I D) 作为物联 网应用 的一 项核心支 撑技术,在学术界与工业界已经 得到 广泛 关注.目前 , R F I D 技术 正在越来越频繁地 出现 在大 量 的物联 网应 用中,包括物 流管 理、电子支 付、RFID护照、安全访问控 制、目标 监测与追踪 等.随着 RF I D 的技 术原 理被 进 一步 深 入理 解、廉价的RF I D组件 相继 出现以及 RF I D 的安 全得到保障,RF I D技术将会在物联 网应 用中发挥越来越重要 的作用 . 物联网的核 心理 念是 在普 适 环境 下 实现 物一 物 相联 , 即通过对物理世界信息化、 网络化 , 将传统上 分离的物理世 界 与信 息世 界 实现 互联与整 合.这就需要将 智能 嵌入到每一个物理对象当中, 并且提供 一种有效 的、低成本的通 信 方式 , RF I D技术的出现 收稿 日期 :

2 0

1 2 ―

0 2 ―

0 8 ;

最终修改稿收到 日期 :

2 0

1 2 ―

0 5 ―

2 7 . 本课题得到国家 九七 三 重点基础研究 发展规划项 目基金(

2 0

0 9 C B

3 2

0 7

0 5 ) 、 国家 自然科学基金(

6 1

1 0

0 1

9 6 ,

6 1

0 7

3 0

2 8 ,

6 1

0 2

1 0

6 2 ) 以及江苏省 自然科学基金 ( B K

2 O

1 1

5 5

9 ) 资助. 谢磊,男,1982年生 , 博士 , 讲师 , 中国计算机 学会( C C F ) 会员 , 主要研究方向为传感器网络 、 R F I D系统 、 车联 网、 高性能计算. E - ma i l :l x i e @n i U . e d u . c n . 殷亚凤, 女,

1 9

8 9年生 , 博士研究 生,中国计算机学会 ( C C F ) 学生会员 , 主要研究方向为 RF I D . 陈曦,男,1988年生 , 硕士研究生 , 中国计算机学会( C C F ) 学生会员 , 主要研究 方 向为 RF I D . 陆桑璐 , 女,1970年生 , 博士 , 教授 , 博士生导师 , 中国计算机 学会 ( CC F ) 会员 , 主要研究领域为 普适 计算 、 分布式计算 、 传感器网络. 陈道蓄 , 男,1947年生 , 教授 , 博士生导师 , 中国计算 机学会 ( C C F) 高级会员 , 主要研究领域为普适计算、 分布式计算、 计算机 网络.

4 5

8 计算机学报正好满 足 了这 一需求.RFID是 一种非接触式的自动识别 技术 , 它通过射频 信号自动 识别目标 对象并获取相 关 数据 , 识别 工作 无 须人 工干 预. 作为一种 简单的无 线系统,RFID系统 只有 两个基本器件 , 一个是阅读器 , 另 一个是标 签. 其基本 工作原 理是 : 阅读 器 以广播方式连续向周 围发送携带能量 的基准信号 , 感应到能量的标签通过调制 电路信号以反射的方式 向阅读 器返回自身 携带的数 据,阅读 器对接收到的数据进行解码 , 并 传给 主机进行处理. 通过 上述方 式,RF I D 系统 能够 提供有效的身 份信息(Identity)和地 址信息(Location).相比于其它智能系统,RFID系统 具有 如下 鲜 明特点 : (

1 ) 能 够实 现非接触 式 的快速 自动识 别;

(2)标签内能 够永久存储一定大小 的数 据;

(3)标签内含 一定数目的逻 辑 门能 够 进行 简单 的逻 辑处 理;

(4)标签具有普通无线设备的物理 属性 ;

(

5 ) 标签成本低廉,可以大量部署.因此,作为物联网感 知识别层面的一项关键技术,RFID技术能够使得物联 网中的每一个物体被 唯一 地识 别,并且 能 够携 带规 范而 具有 互用 性 的信 息,在无源的情况 下有 效 实现 被动 智能 , 为 物一 物相 联 提供根 本保 障.在物联 网环 境下,RF I D 系统被部署和应用的根本目的是 : 针 对具 体 的应用 需求,对被标 识 的物 理 对象进行合理有效 的信息收集 , 为上层应用提供最 基本的数据支持. 因此 , 任何一种具体的 RF I D应用 都 依赖 于对RFID数据实现有效的数 据管理.所谓数据管理是指结合 RF I D系统的应用需求实现有效 且有针对 性 的数据 收集、分析挖 掘 以及 数据安全保障等操 作.在现有 的物 联 网体 系架构 中,数据 管理 起 着承 上启 下 的关键 作用:一方面,物联网需要 从感 知到的海量 原始 数据中提取有 效信息并进行管理,为上层 的特 定应 用 提供 数据 支撑 ;

另 一方 面,物联 网需 要结 合具 体 的数 据管 理需 求来 组织 感 知识 别层 面的众多节 点,在网络 层 面进 行优 化调 度 与资 源配 置,以更有效地指导下层协议与算法 的设计实现. 基 于上 述认识 , 本文关 注RF I D数据管理问题 , 以数据管理的核心技术为切入点 , 分别从 RF I D的防冲突算 法、RFID的认 证与隐私 保护协议以及 真实环境 下RFID系统数据收集的性能评测与分析3个 方 面对 R F I D数据 管理技术 的研 究与进展进 行分析与讨论 . 图1展示了上 述 3个 方面研究问题 之 间的逻辑层次关系. 其中, 研究防冲突算法的目的是 为MAC层 提供 一套 快速的标 签识 别机制, 实现RF I D数 据管 理的高效性;

研究安全协议的目的 是 为数据 管 理提供 基本的安 全保障,能够有效地 实现认证并 且保 护用户隐私,实现RFID数 据管理的可信性;

对RFID系统 进行 性能 评测 与分析,其目的 在 于验证 在 真实 环境 下物 理层 的关 键 因素对 系统 识别性能 的影 响,确保数 据 管理 的可 靠性 . 深入 探究 三者之间的联 系,我们 发现任一研 究 问题 均对其余二者产生 影响:防冲突 算法能够提供 最根本的数 据传输支持 , 安全 协 议能 够实 现必 要 的安全 保障,性能评 测 能够 验证 在 真实 环境 下的系统 运行性能. 上述三方面研 究 问题 与RFID系统 协议栈的对 应关系如图1所示 , 可 以看 到 三者 之间相 互 联系 , 又各 有侧 重. 图1各研 究问题之I司的逻 辑层次关系本文第

2 节 主要 介绍RFID的标 签 识别 协议与防冲 突算法 , 着重阐述 R F I D标签 识别机制 、 数 目估 算 机制 以及 轮 询机 制方面的研究 工作;

第3节 主要介绍RFID的认 证与隐私 保护协议,对RF I D 的安全与隐私 问题 进行探讨与分析,并对RF I D 安全方面的三类 主 流技术 进行总结;

第4节 对真实环境下RFID系统性 能 的评 测与分析 方面的研 究工作进行介绍;

第5节 对RF I D 数据管理相关的其它开放性问题 的研 究 进展 进行总结;

第6节 展望RFID未来的研 究方 向;

最后 对全 文进 行 总结 .

2 RF I D标签识别协议 与防冲突算 法2.1RFID的标 签识 别协 议在通常 的RF I D 应用中,大量的RF I D 标签往往被广泛地部署在指定区域 中. 为了能够快速有效 地 识别 这些 标签,阅读 器需要在RFID标 签识别协议中使用一套有效的防冲突算法来逐一读取这些标 签.在无线 通信 环境 下,普通 的无 线设 备 主要基 于载 波侦听多路访 问/ 冲突避免 ( C S MA / C A) 的竞争机 制来实现多个设备之间的通信 , 如802.11协议. 与 普通的无线 节点不 同, RF I D 标签是极为简单 的无 线 设备 , 标签上的资源极 其有限,不能够 自发 地通 过 3期 谢 磊等 : RF I D数 据管理 : 算法 、 协议与性能评测

4 5

9 调节 自身 的无线传 输机会来避免标签 间的传输 冲突. 具体 来说 , 标签 没有 足够 的处 理能 力 与能源 来实 现上述竞争机制, 避免通信冲突. 鉴于 R F I D的系统 特点,RFID标签识别协议需要具备如下性质:(1)简单 . 由于 RF I D标签 上 的计 算、存储资源极其 有限,标签识 别协 议 的处理 逻辑 ( 包括 执行 流程 和状 态迁 移关 系)需要尽可能简单 ;

(

2 ) 高效.面对 大量 的RFID标 签,标签识 别协议需要提供轻量级的通 信 机制 , 尽 可能避 免不 必要 的控 制报 文 的传输 , 确保 传输 的高吞吐率与低延迟性. 目前 的RFID防冲突 算法 主要 分为两大类:基于二 进制 树 的防 冲突算 法l_】]和基 于AL OHA 的防冲突算法 _

3 ] . 前者利用二叉 搜索树,按照递 归 的方 式将 冲突 的标签集 合划 分为两个标签子集 , 对于可能产生冲突的相关标签集合 , 采用沉默 的方式来解 决 冲突 问题 . 划分 子集的方 法包括随机 二进制树算 法 和查询 二进 制树 算法 . 文献[1]提出了一 套 自适应 的基 于树 形结 构 的防 冲突算 法来 实现 有效 的标 签识 别.文献 E

2 ] 提 出了一套 基 于查询 树结 构 的智能 遍历机制,能够以低延迟的方式实现标签的识别.AL OHA协 议最 早被 用在 分组 无线 网络 中实 现 随机 访 问机制 . 在RFID系统 中,为了提 高标签识 别 的效 率,文献 [

3 ―

4 ] 提出了时隙AL OHA 协议来有效解决冲突 , 实 现标 签的高效识别.时隙AL OHA 协议将若 干个 时 隙组织 为一 帧,在每 一帧 开始 时,阅读器 广播帧的长度 . 厂,即当前帧所包含的时隙个数, 并通 过发 送连 续的电磁 波来 激活扫描范围内所 有标签.每个 标签 在接 收到 帧长 - 厂之 后 随机 独立 地 在第

1 ~ ,个时隙中选择一个时隙发送标识符. 如果成........