第ｌ９卷 Ｖｏ１．１９ 第１９期 Ｎｏ．１９ 电子设计工程 Ｅｌｅｃｔｒｏｎｉｃ Ｄｅｓｉｇｎ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１１年１０月 Ｏｃｔ．２０１１
ＲＦＩＤ高频读写器防碰撞算法研究
邓一文，张红雨，张鹏程，向舸
（电子科技大学电子工程学院，四川成都６１１７３１）
摘要：基于对ＲＦＩＤ（无线射频识别，Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）高频读写器防碰撞性能提高的目的，介绍了二进制
搜索算法原理，并基于二进制搜索算法详尽研究了一种符合ＩＳＯ／ＩＥＣ ｌ４４４３Ａ规范的比特帧防碰撞算法，比特帧防碰 撞算法能有效的实现高频读写器的防碰撞功能。此方法为解决ＲＦＩＤ高频防碰撞问题，提高高频读写器性能具有重
要的实用意义和指导意义。
关键词：ＲｎＤ；二进制搜索算法；读写器；比特帧放碰撞
中图分类号：ＴＰ２９ 文献标识码：Ａ 文章编号：１６７４—６２３６（２０１１）１９—００３１—０４
Ｓｔｕｄｙ Ｏｉｌ ｔｈｅ ａｎｔｉ．ｃｏｌｌｉｓｉＯＨ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ＲＦＩＤ ｒｅａｄ／ｗｒｉｔｅ ｄｅｖｉｃｅ
ＤＥＮＧ Ｙｉ－ｗｅｎ，ＺＨＡＮＧ Ｈｏｎｇ－ｙｕ，ＺＨＡＮＧ Ｐｅｎｇ—ｃｈｅｎｇ，ＸＩＡＮＧ Ｇｅ
（Ｓｃｈｏｏｌ ｏｆＥｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅ ，Ｕｎ＆ｅｒｓｉｔｙｏｆＥｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ ＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａ，Ｃｈｅｎｇｄｕ ６１１７３１，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｐｕｒｐｏｓｅｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）Ｈｉｇｈ—Ｆｒｅｑｕｅｎｃｙ ｒｅａｄ／ｗｒｉｔｅ ｄｅｖｉｃｅ．Ｔｈｅ ｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｗａｓ ｉｎｔｒｏｄｕｃｅｄ．Ｔｈｅ ｂｉｔｅ ｆｒａｍｅ ａｎｔｉ－ｃｏｌｌｉｓｉｏｎ ｗａｓ ｓｔｕｄｉｅｄ ｏｎ ｉｎ ｄｅｔａｉｌ，ｗｈｉｃｈ ｉｓ ｂａｓｅｄ ｏｎ ｔｈｅ
ｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ａｎｄ ｆｏｌｌｏｗｅｄ ｔｈｅ ＩＳＯ／ＩＥＣ １４４４３Ａ ｐｒｏｔｏｃｏ１．Ｔｈｅ ｂｉｔｅ ｆｒａｍｅ ａｎｔｉ－ｃｏｌｌｉｓｉｏｎ ｃａｎ ｖｅｒｉｆｙ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ
ａｎｔｉ－ｃｏｌｌｉｓｉｏｎ ｏｆ ＨＦ ｒｅａｄ／ｗｒｉｔｅ ｄｅｖｉｃｅ ａｖａｉｌａｂＩｖ．Ｔｈｉｓ ｍｅｔｈｏｄ ｔｏ ＳＯｌＶｅ ｔｈｅ ｈｉｇｈ－ｆｒｅｑｕｅｎｃｙ ＲＦＩＤ ａｎｔｉ－ｅｏｌｌｉｓｉｏｎ ｐｒｏｂｌｅｍｓ ａｎｄ
ｉｍｐｒｏｖｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ＨＦ ｒｅａｄ／ｗｒｉｔｅ ｄｅｖｉｃｅ ｈａｓ ｉｍｐｏｒｔａｎｔ ａｐｐｌｉｃａｔｉｏｎ ｓｉｇｎｉｆｉｃａｎｃｅ ａｎｄ ｄｉｒｅｃｔｉｖｅ ｓｉｇｎｉｆｉｃａｎｃｅ
Ｋｅｙ ｗｏｒｄｓ：ＲＦＩＤ；ｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ；ｒｅａｄ／ｗｒｉｔｅ ｄｅｖｉｃｅ；ｂｉｔｅ ｆｒａｍｅ ａｎｔｉ—ｃｏｌｌｉｓｉｏｎ
Ｒ兀Ｄ技术是一种非接触式的自动识别技术。在ＲＦＩＤ系
统工作时．当有多个标签同时向读写器发送数据时．由于传
输信号的相互干扰，会造成数据无法读取。这就必须通过一 定的方法。以使读写器能够正确的完成与所有标签的通信，
这些方法就叫做防碰撞算法。随着物联网的应用领域越来越
广泛。能适用于各种基于ＩＳＯ／ＩＥＣ １４４４３ Ａ标准、低成本、小 尺寸、高性能的非接触式高频通信的应用场合也越来越多。
所使用到的标签数量也越来越大。因此提高高频读写器的防
碰撞能力成为提高读卡器性能关键【Ｉ】。 文中便对符合ＩＳ０／ＩＥＣ １４４４３ Ａ规范的高频读写器运用
的防碰撞方法所基于的二进制搜索算法进行了介绍。并对实
际所运用到的比特防碰撞方法进行了详细的研究．对在防碰 撞过程中读写器与标签的通信方法进行了分析，详细说明了
比特帧防冲突的具体流程。
１二进制搜索算法
１．１二进制搜索算法简介 ＲＦＩＤ冲突问题与计算机网络、无线电通信冲突问题都
有相似之处。在无线电通信系统中，常用的多路存取方法一
般有：空分多路法（ＳＤＭＡ）、频分多路法（ＦＤＭＡ）、码分多路法
收稿日期：２０１１－０６—２０ 稿件编号：２０１１０６０８９ （ＣＤＭＡ）及时分多路法（ＴＤＭＡ），这些方法都可以被借鉴，但
在ＲＦＩＤ这个特殊系统中，空分多路法、频分多路法、码分多
路法在技术实施上比较困难［２１，对读写器和标签的要求很高，
需要支付的成本也相当高。只限制在少数的特殊应用场合。
在诸多防冲突算法中．只有ＴＤＭＡ应用得非常广泛。
ＴＤＭＡ是把整个可供使用的通路容量按时问分配给多 个标签的技术．读写器与各个标签分别在不同的时间里通
信。尽管是在不同的时间通信，但由于整个时间很短，以致用
户感觉不到时间浪费，从而可以被认为读写器对各个标签的
读写是“同时”进行的。
在ＩＳＯ／ＩＥＣ １４４４３ Ａ规范中，便采用了ＴＭＤＡ防冲突算
法中的二进制搜索算法。 １．２二进制搜索算法原理
二进制搜索算法是以标签的唯一序列号为基础来实现
防冲突的。当多个标签同时向读写器发送序列号时，读写器 能判断出数据冲突位的准确位置。由于冲突位只能是“ｌ”和
…０’，然后强迫是…１’或…０’的标签暂时退出．以此类推。在判
断完整个序列号之后，将得到唯一的序列号［３１。 能使得读写器能判断数据冲突位的准确位置的编码是
二进制搜索算法的必要前提。Ｍａｎｃｈｅｓｔｅｒ编码就具有这种性
质。图１是ＮＲＺ编码和Ｍａｎｃｈｅｓｔｅｒ编码发生冲突时的比较。
作者简介：邓一文（１９８５一），男，四川成都人，硕士研究生。研究方向：嵌入式系统与ＲＦＩＤ系统。
一
３１— 《电子设计工程）２０１ １年第１９期
ＮＲＺ编码 标签１ ｎ厂］ １ ０ ｌ １ ０ ０ 标签２厂］厂］ １ １ Ｏ １ １ ０ 混合信号广——］ １ １ ｌ １ １ ｏ
图ｌ ＮＲＺ和Ｍａｎｃｈｅｓｔｅｒ码发生冲突时的差异 Ｆｉｇ．１ Ｔｈｅ ｄｉｆｅｒｅｎｃｅ ｂｅｔｗｅｅｎ ＮＲＺ ａｎｄ Ｍａｎｃｈｅｒｓｔｅｒ
由图ｌ可知，对于ＮＲＺ码，混合信号不能反映出异常的
状态。而当Ｍａｎｃｈｅｓｔｅｒ编码有不同的值时．接受到的整个位
都是高电平，这种状态未作规定，导致一种错误．读写器可根
据错误判断出冲突发生在第几位。因此，Ｍａｎｃｈｅｓｔｅｒ编码可以
实现按位跟踪冲突｝圳。
假设标签序列号为ｎ位，并且标签在接到读写器的指令 后能在同一时刻将序列号传送给读写器．以准确的检测到冲
突位的位置。下面是算法执行过程：
１）读写器发送“请求”指令，参数为１ｌ…１（ｎ个１），这时
所有标签将应答。读写器检测收到的信号．若没有标签，继续
发送“请求”指令；若只有一个标签应答，选择该标签，并与其
完成读写操作，操作后令其退出，接着继续发送“请求”指令。 ２）若有不止一个标签，标签向读写器传送的序列号将发
生冲突，这时读写器利用Ｍａｎｃｈｅｓｔｅｒ编码的特性识别出序列
号发生冲突的位置，并将接收到的序列号的最高冲突位置
“０”，高于该位的值不变，低于该位的值将全部设为“ｌ”，得到
下一步请求命令的参数。
３）在上一步的基础上发送请求命令，这是由于请求命令
的参数限制了一部分标签的应答，有可能只有一个标签应
答，若不止一个，则重复第２）步，这样不断地缩小待选择的标
签，直到成功识别出一个标签。选择该标签。并与其完成读写 操作，操作后令其退出。
４）回到上一个结点处继续发送“请求”指令。不断地循
环，直到识别出所有的标签啊。
下面通过实际例子来说明二进制搜索算法的原理：
设有４个标签，它们的序列号分别为ｌｌ００ １１００、１０００
Ｏ１００、１０００ ０ｌ１Ｏ和１０００ １１００。当读写器发送请求指令（参数 ｌ１１１ １１ｌ１）时，４个标签将同时向读写器发送序列号，这时在
第ｌ位、第３位、第６位产生冲突，读写器接收到的序列号为 １ＸＯ０ Ｘ１Ｘ０，Ｘ为发生冲突的未知位，从而判断有冲突产生。
下～次请求指令的参数将最高冲突位置“０”．高于该位的值
不变．低于该位的值将全部设为“１”，得到“１０１１ １１１１”，以此
为参数继续发送“请求”指令，以此类推，
直到识别出一个标签。具体过程见表１（Ｘ表示冲突位）
完成一个标签之后，会继续请求下一个标签。这时读写 器不是从最开始搜索，而是根据已有的信息，从上一级的冲
突位开始搜索即读写器发送的请求指令参数不是“ｌ１１１
ｌ１１１”而是“１０ｏ０ Ｏｌ１１”。表２是搜索第二个标签的执行过程。
在读写器轮询过程中，返回的序列号并非全部的序列
一３２一 表１二进制搜索算法执行过程 Ｔａｂ・１ ＴＩ他ｐｒｏｃｅｓｓ ｏｆｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ
表２二进制搜索算法执行过程ｆ第二步） Ｔａｂ．２ Ｔｈｅｐｒｏｃｅｓｓｏｆｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ（Ｓｔｅｐ ２１
号，而是序列号中未知的其他ｂｉｔ值，这样就可以减少二进制
搜索法在防冲突运算中所要传输的数据量和所需的时间。在
ＲＦＩＤ系统中，当射频场内出现冲突时，根据智能卡内标签芯
片ＵＩＤ序列号从高到低一次次筛选出某一射频卡，进行后续
的操作。二进制搜索法的特点在于稳定性好，准确度高，但是
硬件实现比较麻烦。随着冲突标签的越多、标签序列号越长，
总的防碰撞执行时问也越长。二进制搜索算法为了从Ⅳ个标
签中找出唯一一个标签，需要进行多次请求。其平均次数为：
Ｌ＝ｌｏｇ２Ｎ＋ｌ由公式可知，找出一个标签的请求次数将会随着
Ⅳ的增加而迅速增加旧。
２比特帧防冲突
ＩＳＯ￣ＥＣ １４４４３Ａ中提出的比特帧防冲突便是基于二进
制搜索算法所提出的一种有效实用的防冲突方法。
在ＩＳ０，ＩＥＣ ｌ４４４３ Ａ中指定了以下几个指令来管理 ＰＩＣＣ（标签）与ＰＣＤ（读写器）的通信：ＲＥＱＡ请求命令，ＡＴＱＡ
应答，ＡＮＴＩＣＯＬＨＳＩＯＮ，ＳＥＬＥＣＴ，ＳＡＫ应答。 ＰＣＤ设备（读写器）发送ＲＥＱＡ请求命令，ＲＥＱＡ命令数 据组成如表３所示。
表３ ＲＥＱＡ数据Ｔａｂ．３Ｄａｔａ ｏｆＲＥＱＡ
ＲＥＱＡ帧包括以下内容：
１）通信起始位Ｓ
２）位数据，低位先发送，ＲＥＱＡ的命令代码是“０ｘ２６”
３）通信结束位Ｅ ＰＩＣＣ接收到ＲＥＱＡ命令后，在ＰＣＤ能量场内所有ＨＣＣ
同时发出ＡＴＱＡ应答，ＡＴＱＡ应答数据组成如表４所示。 码 。Ｌ．］。 。瑞』０几 厂 ¨［：： ＝＝ 』０几。厂
霁一