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是整体效率 的上限值 ，因此 当前整体效率接 近全局 最 优．