2 2 2 2007 年 4 月 第 30 卷 第 2 期 北 京 邮 电 大 学 学 报 Journal of Beijing University of Posts and Telecommunications Apr. 2007 Vol. 30 No. 2 　　文章编号 :1007 5321 (2007) 02 0059 04 射频识别系统中的防碰撞算法设计 王晓华 , 　周晓光 , 　孙百生 (北京邮电大学 自动化学院 , 北京 100876) 摘要 : 为了防止射频识别 (RFID) 系统中多个应答器同时向阅读器发送识别信息时产生的碰撞问题 ,提出了一种新 的算法 ———基于序列号对时隙数运算的排序算法. 该算法通过应答器序列号对争用周期时隙数的运算结果 ,获得 应答器在争用帧内相应时隙的发送位 ,从而利用填充过的争用帧确定各个应答器在整个数据发送周期内的发送顺 序 ,给不同的应答器分配不同的发送时序. 计算机仿真表明 ,该算法可以有效解决射频识别系统中多目标识别的防 碰撞问题 ,且适用于应答器数目较多的场合. 关 　键 　词 : 射频识别 ; 序列号 ; 时隙数 ; 运算 ; 排序 中图分类号 : TN92 　　　　文献标识码 : A The Design of Anti Collision Algorithm in RFID System WAN G Xiao hua , 　ZHOU Xiao guang , 　SUN Bai sheng (School of Automation , Beijing University of Posts and Telecommunications , Beijing 100876 , China) Abstract : In order to avoid signal collision occurs when more than one transponder send the recognition information to the reader with function of radio frequency identification ( RFID) , a compositor algo rithm based on identification( ID) operating to timeslot number is proposed. The sent bits will be ob tained in corresponding timeslots of the competitive frame for all transponders when used the algorithm by operating result of transponders’identifications to the timeslot number of competitive frame. So it can confirm the sending order of all transponders in the whole data sending period by the filled com petitive frame and distribute different sending orders to different transponders. The computer simula tion shows that the new algorithm is more effective to solve the problem of anti collision for multi target recognition in RFID system compared with other existed anti Key words : radio frequency identification ; identification ; timeslot number ; operating ; compositor collision algorithms. 1 　RFID 简介 射频识别技术 ( RFID ,radio frequency identifica tion) 是一种非接触式自动识别技术 , 可以通过射频 信号自动识别目标对象 ,获取相关数据 ,无需人工接 触 、光学可视 ,操作简单快捷. RFID 系统一般包括应答器 、阅读器和计算机 通信网络 3 个部分 (如图 1 所示) , 应答器存储待识 别对象的相关信息 ,通常附着在待识别对象上 ;阅读 器是利用射频信号读/ 写应答器存储信息的设备 ;计 算机通信网络通常用于对数据进行管理 , 完成通信 传输功能[1 ] . 射频识别系统工作时 , 经常会有多个应答器同 时处于阅读器的工作范围内. 当多个应答器同时向 阅读器发送识别信息时 , 由于所有的应答器都使用 同一传输信道 ,所以在应答器发送信息的过程中经 收稿日期 : 2006 基金项目 : 信息产业部 2004 年信息产业科研 ( 民品) 计划项目 ( 2004XK110005) ; 北京市物流系统与技术重点实验室开放课题 03 20 (2005 KF1006) 作者简介 : 王晓华 (1978 —) , 女 , 博士生 , E mail :anwenxiaohua @163. com. 

06 北 京 邮 电 大 学 学 报 　　　　　　　　　　　　　　　　　第 30 卷 常会发生碰撞 ,造成应答器信息相互干扰 ,使阅读器 无法正确接收和识别应答器[2 ] . 2 个参数 , 即同步时钟参数和争用周期时隙数) , 激 活其作用范围内的所有应答器. 图 1 　RFID 系统结构 2 　实现防碰撞技术的软硬件方法 防碰撞技术是 RFID 技术中的关键技术 , 通常 可以从硬件和软件 2 个方面实现. 硬件实现主要是 采用多址识别技术如空分多路 ( SDMA) 法 、频分多 路 ( FDMA) 法 、时分多路 ( TDMA) 法等实现 ,优点是 响应时间较小 、速度快 ,但是以增加系统复杂性和提 高成本为代价 , 系统比较复杂 ; 如果用软件方法实 现 ,则成本较低 ,系统设计简单 、易于修改 ,但是响应 时间相对较长[3 5 ] . 3 　基于序列号对时隙数运算的排序算法 　　基于序列号对时隙数运算的排序算法是时分复用 方法的一种. 该算法简单 ,响应速度较快 ,适用于射频 识别系统中含有 1 个阅读器和多个应答器的情况. 3 1 　系统工作流程 使用该算法的系统 , 通常按照 5 个步骤完成阅 读器和应答器之间的数据通信. 2) 应答器接收信道争用开始指令 ,进行时钟同 步 ,同步进入信道争用周期. 3) 所有应答器利用该算法确定自己的发送时 隙和发送位 ,并在争用周期内发送的争用数据帧相 应时隙的相应发送位填充数据“1”. 4) 应答器监听争用数据帧 ,确定自己在整个数 据发送周期内的发送顺序. 5) 进入数据传送周期 ,各应答器按照已确定的 发送顺序在对应的周期内发送数据. 每个应答器发 送数据后 ,阅读器都会在数据接收后发送休眠指令 , 使应答器处于休眠状态. 3 2 　算法步骤 基于序列号对时隙数运算的排序算法的流程如 下 :在争用周期内 ,算法首先利用应答器序列号除以 争用周期时隙数所得的余数确定应答器在争用数据 帧内的发送时隙 ;其次 ,利用应答器序列号除以争用 周期时隙数所得的商确定应答器在争用帧内相应时 隙的发送位 ,然后在争用周期内发送的争用数据帧 的相应时隙相应发送位填充数据“1”;最后利用填充 过的争用数据帧确定应答器在整个数据发送周期内 的发送顺序 (即应答器的发送顺序 = 其发送位及其 前面各发送位中“1”的总数) , 从而给不同序列号的 应答器分配不同的发送时序. 1) 阅读器发送信道争用开始指令 (该指令带有 该算法的实现过程如图 2 所示. 设应答器序列 图 2 　基于序列号对时隙数运算的排序算法演示 

1 1 ; 第 2 期 　　　　　　　　　　　　王晓华等 : 射频识别系统中的防碰撞算法设计 16 号如图所示 ,争用周期时隙数为 4 (最小时隙为时隙 0) ,发送数据为 4 位 (b3b2b1b0) ,应答器序列号除以 争用周期时隙数所得余数和商 分 别 简 称 为 余 数 和商. 3 3 　算法分析 设应答器序列号长度为 L ID (序列号以二进制 形式表示) ,应答器 j 的序列号为 Ij , 应答器数量为 M ( M ≤2 L ID ) , 信道争用开始指令的发送时间为 T0 ,休眠指令的发送时间为 T 1 , 数据发送周期的数 据帧长度为 T ; 争用周期的时隙数为 M TS ( M 2 TS ≥ 2 L ID) ,时隙长度为 t (设每个时隙内的发送数据长度 为 M TS位 ,位时间长度为 t b , 即 t = M TS t b) , 时隙 i 内有 Pi 个应答器要发送数据 ;应答器 j 在争用周期 内的发送时隙为 S j , 发送位为 Dj , 序列号对 M TS的 商为 Q j ,应答器 j 在整个数据发送周期中的发送顺 序 T j ,则 S j = Ij %M TS Q j = Ij/ M TS 应答器 j 在 S j 时隙内的发送位 Dj 参照表 1 所 示的发送数据. 表 1 　发送数据参照表 Q j 1 2 3 发送位 D j 最低位 次低位 倒数第 3 位 Q j 4 ⁝ N 发送位 D j 倒数第 4 位 ⁝ 倒数第 N 位 　　 Pi = 争用数据帧中 i 时隙内 1 的个数 T j = ∑ Pi + ∑ i S j i = 1 i = S , Q ≤Q j i Pi j (争用数据帧中应答器 j 发送位及该发送位前面各 位中 1 的总数. ) 系统效率 E 为 E = M T T0 + M TS t + M T + M T1 = M T T 0 + M 2 TS t b + M T + M T1 (1) 分析式 (1) 可知 , 在 T0 、T1 、T 固定的情况下 , E 主要取决于 M TS、数据争用周期的 t b 和 M . 4 　计算机仿真 用计算机模拟该算法 ,验证算法的性能. 根据式 (1) 进行仿真 ,取 T0 = 0 05 s , t b = 0 001 1 s , T1 = 0 05 s , 可以得到 M 与 E 的关系 s , T = 0 (如图 3 所示) 及 M TS与 E 的关系图 (如图 4 所示) . 由图 3 可知 , 对于时隙数固定的系统而言 , 当 M 较少时 , E 会随着 M 的增加而快速增加 ;当应答 器数目较多时 , E 会随着 M 的增大而缓慢增大 ; 而 M 接近满荷时 ,时隙数对 E 没有显著影响. 但是对 于同一系统 ,如果取不同的时隙数 ,则随着时隙数的 增大 , E 会有所下降 ,这是因为时间利用率下降了. 图 3 　M 与 E 的关系 图 4 　M TS与 E 的关系 由图 4 可知 ,对于应答器数目固定的系统而言 , 效率会随着时隙数的增多而缓慢下降 , 这是因为时 间的利用率降低了 ;而对于时隙数固定的系统而言 , E 会随着应答器数目的增多而有所提高. 综上所述 , 只要选取合适的时隙数和应答器数 TS) ,就可以优 量 (即接近于系统满负荷情况 M = M 2 化系统性能. 5 　结 　论 本算法利用序列号对时隙数的运算 , 有效地给 所有应答器分配了发送时序 , 解决了射频识别系统 中多目标识别的反碰撞问题 , 且适用于应答器数量 较多 、实时性要求高的场合. 但是该算法要求应答 器在各周期内时间精确同步. 

26 北 京 邮 电 大 学 学 报 　　　　　　　　　　　　　　　　　第 30 卷 参考文献 : 1 　Finkenzeller K. 射频识别 (RFID) 技术 ———无线电感应 的应答器和非接触 IC 卡的原理与应用 M . 陈大才 , 译. 北京 : 电子工业出版社 , 2001 : 148 149. 2 　吴春华 , 陈军. 动态 ALOHA 法在解决 RFID 反碰撞 问题中的应用J . 电子器件 , 2003 , 26 (6) : 173 176. Wu Chunhua , Chen J un. Application of dynamic ALO HA algorithm in solving anti collision problem in RFID system J . Electronic A pparatus , 2003 , 26 ( 6) : 173 176. 3 　沈宇超 , 沈树群 , 樊荣 , 等. 一种用于多目标实时识 别的防碰撞算法 ———射频识别系统中的关键技术 J . 北京邮电大学学报 , 1999 , 22 (1) : 10 Shen Yuchao , Shen Shuqun , Fan Rong , et al. A anti 14. target algorithm for multi collision method in RFID systemJ . Journal of Bei of Posts and Telecommunications , 1999 , 22(1) : 10 recognition key jing University 14. 4 　沈宇超 , 沈树群 , 王海波 , 等. 射频识别系统中的防 碰撞算法设计J . 电子科学学刊 , 1999 , 21 (9) : 702 705. Shen Yuchao , Shen Shuqun , Wang Haibo , et al. Anti collision algorithm design in RFID system J . Journal of Electronic Science , 1999 , 21(9) : 702 705. collision algorithm for multi 5 　Shen Yuchao , Wang Haibo , Shen Shuqun , et al. A New target real time recogni anti tion in RFID systemJ . Journal of China Universities of Posts and Telecommunications , 2000 , 7(3) : 64 69. 　 开放式综合业务体系结构的研究 　　研究单位 : 北京邮电大学网络与交换技术国家重点实验室 研究人员 : 杨放春 　王红熳 　闫丹凤 　徐 　鹏 　李静林 　龙湘明 　武 　威 　蒋现新 　徐九韵 　李 　凯 熊文剑 　翟晓波 　饶少阳 　王三海 　刘润杰 　王晓庆 　喻志虎 结题时间 : 2006 年 3 月 本课题由国家自然科学基金资助. 本课题针对目前电信网络技术面临的问题 ,围绕开放式综合业务支撑网络体系结构进行研究 ,主要研究 内容包括开放式综合业务支撑网络体系结构模型 、业务运行环境和管理机制 、业务生成环境 、公共会话模型 和协议转换算法 、业务支撑网络的管理和安全性问题 、业务部署算法和营运模型等. 主要成果如下 :开放式 综合业务支撑网络体系结构的形式化建模方法 SDriCView ,基于 Parlay 、网格和 SOA 技术融合的下一代网络 业务控制和生成体系 ,基于两容器的新型业务执行环境技术 ,支持脚本和 API 的多层次业务生成方法 ,基于 软交换的通用会话模型 ,下一代网络话务理论 ,下一代网络安全控制机制 ,支持网络层间映射的 QoS 模型 , 基于免疫学原理的业务冲突检测和解决方法以及智能网演进策略等. 本课题成果形成专著 9 本 ,发表文章 89 篇 ,被《SCI》收录 5 篇 ,被《Ei》收录 24 篇 ,被《ISTP》收录 14 篇 ; 申请发明专利 19 项 ,其中已授权专利 8 项 ;指导完成与本课题相关的博士后 1 名 ,博士生 15 名 ,硕士生 20 名.