技术研发 Technology Research 电子技 术 基于ALOHA算法 的RF I D防碰 撞技术研究 于 佳 肖明 萍 (燕 山大学 ，信 息科 学与工程学 院) 摘 要 ：在RFID系统 中，由于多标签 引起 的冲 突一直是影 响系统性 能 的主 要 问题 。ALOHA算法是解 决标签碰撞 问 题最有 效的方法之 一 。当系 统 中标签 数过 多时 ，帧 时隙ALOHA算法 和动态 帧时 隙ALOHA算法 ，都会 降低 系统效率 。因 此我们 提 出一种利 用二进制 树形分组 的 时隙ALHOA算法 。 由于只 需要对标 签进行 简单分 组就可 以有 效的提 高ALOHA算 法 的效 率 ，所 以此方法更具有实 际意义 。 关键词：射频识别 ；ALOHA算法 ；防碰撞 Study on RFID A nti-collision Technology Based on A Lo H A Algorithm (College of information science and engineering，Yanshan University、 Yu Jia XiaoLiping Abst r act：In RFID system ，one of the im portant problem s is the collision am ong tags，which lowers the e伍 ciency of the system ．A LOHA algorithm iS one of the m ost effective m ethods to solve the collision problem ．BOth Frame Slot ALoHA algorithm and Dynamic Framed Slotted Aloha algorithm will reduce the system e伍 ciency when there are thousands of tags． W orking on th e im provem ent of the grouping m ethods，w e propose an algorithm nam ed split—ALOHA w ith a novel gr ouping method that split tags as a binary tree．As only simple division of tags can effectively enhance the e伍 ciency of ALOHA algorithm ．SO this m ethod has m ore practica1 significance． ， Key words：radio frequency identifieation(RFID)；AL0HA algorithm；anti—collision 1射频识别系统介绍 射频识别技术 (Radio Frequency Identification， RFID)是一种非 接触式 自动识别 技术 ，与传统 的识 别方 式相 比，它无需直 接接触 、无需 光学可 视 、无 需人 工干 预 即可完 成信息输 入和 处理 ，具 有操作 方便快 捷 、存 储 数据 量大 、保密性 好 、反应时 间短 、对 环境适 应性 强等 优点 ，现在 已广泛应用于工业 自动化、商业 自动化和交通 运输 管理等领 域 ，成为 当前 IT业 研究 的热 点技 术之 一 。 典型的RFID系统主要包括三个 部分： 电子标签 (tag)、 读 写器 (Read)和应用系统 (如图1)。电子标签 放置在 被 识别 的对 象上 ，是RFID系统 真正 的数据载 体 。通 常 电 子标签 处于休眠状 态 ，一旦进入 读写 器作用 范 围内就会 被激活 ，并与读 写器进 行无线射 频方 式的 非接 触 式双 向 数据通信 ， 以达 到识别 并交换数 据 的 目的 。此 外 ，许多 读 写器还 都有 附加的通信 接 口， 以便将 所获 的数据传 给 应用 系统进行进 一步 的处理 。 图1 RDID系统的基本组成 2系统防碰撞 RFID系统工 作时 ，当有2个或 2个 以上 的电子标签 同 时在 同一个读 写器 的作用 范围 内向读写器 发送数 据 的时 候 ，就 会 出现 信号 的干扰 ，这个干 扰就称 为碰撞 ，其 结 果将会 导致 该次传输 的失败 ，因为必须采 用适 当的技 术 防 止 碰 撞 的 产 生 。 3 ALOHA算法及仿真结果 目前有 多种 防碰撞算法 ，主要分为ALOHA算法和 树形 分解算法 。由于树形分解法有时会使某些标签的识别延迟 可 能 比较长 ，所 以ALOHA算法 因具有简单易实现等优 点而 成 为应用 最广 的算法之 一 。ALOHA算法是在ALOHA思想 的 基 础上 ，根据RFID系统 的特 点和技术 要求不 断改进 形成 的算法 体系 。它 的本质是 分离标 签 的应 答时 间 ，使标 签 在 不 同的 时隙 内发 送应答 。一 旦发 生碰 撞 ，一般采 取退 避 原则 ，等待下 一循环周期发送 应答 。ALOHA算法又分为 帧 时隙ALOHA算法 、动态帧 时 隙ALOHA算法和 分组帧 时隙 ALOHA算 法等。 3．1帧时隙ALOHA算法 帧时隙ALOHA(Framed Slotted Aloha，FSA)算法是 基于通信领域 的AL0HA协议提出的。在FSA中， 帧 (Frame) 是 由读 写器 定义 的一段 时间长度 ，其 中包含 若干 时隙 。 标签在 每个 帧 内随机选择 一个 时隙 发送数据 。所有 标签 应 答 同步 ，即只能在 时隙 (Slot)开 始点 向读写器发 送信 息 ，每 个标签 发送 的时 隙是 随机 选择 的 。时隙可 以分为 三类 ：空闲时隙、应答 时隙和碰撞时隙 。在空闲时隙中没 有识 别任何 标签 ，应答 时隙 中可 以正确识别 一个标 签 。 当一个时隙中有多个标签 同时发送应答时就会产 生碰撞 ， 形成碰 撞 时隙 。碰 撞 的标签退 出当前循环 ，等待参 与新 的帧循环 。 读写 器 当前 使用帧 的长度 为N，标签数 为n，在 一个 时隙中存在r个标签的概率为： f r1_f『J]f 一 一 ～ l,．JLNJt． N,J 当r=1时 ，表 示 一个 时 隙只 有一 个标 签 ，即成 功读 取 的时 隙。 因此 ，在 一个 阅读周期 中读取 标签数 的期望 'IR J~： 目 ，n：Ⅳ． ，(1)：Ⅳ f 1i1一一1 1 斋 N八 N 其 中， a 表示只有一个标签 占据一个 时隙的时隙总 数 。其 中帧长度 为N，标签总数为n。 系统 效率 为PN：。：墨塑二全堡篷鱼堡二 堕堕 堕堕 墼 帧 的 大 小 ： Ⅳ 

技术研发 Technology Research 电子技 术 ， 、 I 帧的长度为256I f ＼ ＼ 、 l ＼ J | | t ／ f ＼ ＼ ＼ ＼ 。＼ ＼ 标 签 敦 目 图2帧时隙ALOHA算法的系统效率 图2示 出了当帧 的长度 为256时的系统效率 。当我们 要想获得最大效率时 ，使得： ：(1一l／Ⅳr +硼 一1，Ⅳ 一l， Ⅳ1 =(卜l／Ⅳr {l+nln(1一l／N)} ：0 根据上式可推 出当帧 的长度为N时 ，效率最高的标签 响应数为： r 1 ] l ln(1—1／N)j 、 l 当标签数为n时，帧长度的最佳值为： 了 3．3 分组帧 时隙ALOHA算法 在RFID系 统中 ，我们经 常使用动 态帧 时隙ALOHA算 法 。但是 由于最大帧时隙数有限制 。当标签数量过大时， 我 们不能无 限制地增加帧 的时隙数 。因此提 出了分 组帧 时隙ALOHA(Group Framed Slotted Aloha，GFSA)算法。 将 ．Lj 分 组的 目的是要 限制标签 的应 答数量 ，使得参 与识 别循环的标签与帧的时隙数匹配。在GFSA算法中，如果估 计 出待识别的标签数超过 了最大帧时隙数所能匹配 的范围 时，保证每一组的待识别标签与最大帧时隙数相匹配 。 式 泰 勒 尔 展 开 Ⅳ ； ； …… … 立 - 怕锻 》 ． 出 I。 籀 》 ．； ‘ 《 … ’ 薹 —+_1组标签l — e一2组标签I —岳_4组标签f 8组标箦l — 标 签 数 目 图3帧时隙ALOHA算法的系统效率 在 图3中，无论是采用一组还是 两组 ，都会达到同样 当n很 大 时 ， 的期望系统效率的标签数： 一 256 256 八7 一 ) ：”( )(·一 厂 " - ' ~ - - ： ： 变化及 时调整 ，使得标 签数量 与帧时 隙数 匹配 。在 开始 是在发生冲突时，一个时隙 中至少有两个标签 发生碰撞 。 N代表 当前帧的长度 ，Co表示空闲时隙，Cl表示成功时 的相对估计误差较大，但具有方法简单等优 点。 设N代表 当前帧的长度 ，n表示标 签数 。标签 选择各个 时 ， ‘lrJt,-~Jt, Ⅳ』 { 由上式我们可 以得到n=354。如 果未识别标签数大于 354时，为达到最佳系统效率 ，我们将标签分成两组。 我们提 出的分组算 法是基 于最大帧 时隙数为256的动 态帧时隙ALOHA算法。在算法 中，首先定义 ： (1)为达到最大系统效率，通过获取最后一个阅读 帧 的结果 (O或 是1)来决 定对分组标签 进行响应 ，以确 定新循环帧的大小。 (2)为减d~RFID系统 的复杂性 ，通过使用 n--c，+2c 估计 函数来确定标签 数量 。 (3)利 用 上 面推 导 出 的n=354，作 为 分 组 的 条件 。 当系统 内标签数量 比较小时 ，则使 用最大帧 时隙数 为256的动态帧时隙ALOHA算法 。一旦标签数量超过 了354 时 ，则使用分组帧时隙ALOHA 算法，来限制系统 内的响应 的标签数量 。过程如图4所示 。 图4 提出的分组算法流程 图 (参见下页) 我们 利用 二进制树形分解法对标签进行分组 ，如 图5 所示 。二进 制树形 结构可 以有效地 对未识别标 签进行搜 索 。对分 组后 ，获取 最后一个 阅读帧的结果 (O或是 1) 来判断是否继续分组。如果结果是1，表 示达 到时隙分离 条件 ，需要对标签继续进行分组，直到结构是0为止 。如 果结果是0，表示未达 到时隙分离条件 ，并采用动态帧时 隙ALOHA算法对标签进行识别 。 图5二进制树形结构分解 图 (参见下页) 对 提 出的算 法进行 了仿真 。结果表 明：当标签数小 于354时，分组帧时隙ALOHA算法采用动态帧 时隙ALOHA算 法 ；当标签 数大于354时 ，分组帧 时隙ALOHA算 法对标签 数进行 分组识别 。所 以标签数越多 ，分组帧时隙ALOHA算 

技术研发 Technology Research 电子技 术 ELEC TRo N IC TECH N 0 LoG Y 的时隙ALHOA算法 。对提 出的分组算法和传统 的动 态帧时 隙算法 进行 比较 。当标签 数过大 时 ，采 用此方 法有利 于 提高系统效率 ，并减 少了计 算和操 作的复杂度 。 。 Cl 参考文献 ： [1]游战清 ，等．无线射频 技术 (RFID)理论与应用 [M]． Cl 北京 ：电子工业 出版社 2004． [2]陆端 ，等．改进ALOHA算法在RFID多 目标识别中的应 用 [J]．微计算机信 息，2006，22(11)： [3] 5ia Zhai and Gi-Nam Wang． An anti—colliSion algorithm USing two—functioned estimation for RFID tags[C]／／ Procs． ICCSA(4)，2005：702—711． [4] LEE S R，joo S D， LEE C W．An enhanced dynamic framed S1otted ALOHA algorithm for RFID tag identification．IEEE Computer Society，2005[C]． [53 Vogt H．Multiple object identification with pasSive RFID tags． 2002 IEEE International Conference on Systems， Man and CybernetiCS． October 2002ICI． [6] Vogt H． Efficient object identification with passire RFID tags[C]／／Procs．Pervasive 2002．98—1 13． 作者简介 ： 于佳 1982生，汉族，06级研究生，通信与信 息系统专业， 研究方 向：射频识别 系统 中防碰撞 算法的研 究。 ● 图4提 出的分组算法流程 图 达 到 时 隙 分 离 条 件 未 达 到 时 隙 分 离 条 件 。 采 用 动 态 帧 时 隙 ALOHA算 法 图5 二 进 制 树 形结 构 分 解 图 法所使用的时隙数越少 ，效率越高 。如 图6所示 。 3000 2500 2000 皿 霎㈣ 茁 1 000 500 ／ — ／ ／ 。 ／ _／ ／ ／／ ， ／／ ／／ ， _，／ l 】 m aW-， 1 l 动态ALOI．．~算法 l I I ： 1 0 0 100 200 300 400 500 600 700 800 900 1 000 标 签 数 目 图6 两 种 算 法 的 比较 4 结 束 语 本文基 于ALOHA算法，分别对帧时隙算法和 动态 帧时 隙算法进行研究和分析 ，并提出一种利用二进制树形分组