２１０２００９．４５（３）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
ＲＦＩＤ系统防碰撞算法比较分析及其改进算法
吴跃前，辜大光，范振粤，杜明辉
ＷＵＹｕｅ－ｑｉａｎ，ＧＵＤａ—ｇｕａｎｇ，ＦＡＮＺｈｅｎ－ｙｕｅ，ＤＵＭｉｎｇ－ｈｕｉ
华南理工大学电子与信息学院，广州５１０６４１
ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｍｕｎｉｃａｔｉｏｎａｎｄＥｌｅｃｔｒｏｎｉｃＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｔｈＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ５１０６４１，Ｃｈｉｎａ
Ｅ—ｍａｉｌ：ｙｑｗｕｃｈｅｎｇ＠１６３．ｃｏｒｎ
ＷＵＹｕｅ－ｑｉａｎ。ＧＵＤａ－ｇｕａｎｇ，ＦＡＮＺｈｅｎ－ｙｕｅ．ｅｔａ１．Ｃｏｍｐａｒｉｓｏｎａｎｄａｎａｌｙｓｉｓｏｆａｎｔｉ－ｃｏｌｌｉｓｉｏｎｉｎＲＦＩＤｓｙｓｔｅｍａｎｄｉｍ—ｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．２００９。４５（３）：２１０－２１３．
Ａｂｓｔｒａｃｔ：Ａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｉｓａｋｅｙｔｅｃｈｎｉｑｕｅｉｎｔｈｅＲＦＩＤｓｙｓｔｅｍ．Ｔｈｅｅｌｅｍｅｎｔａｒｙｂｉｎａｒｙｓｅａｒｃｈａｌｇｏｒｉｔｈｍａｎｄｓｏｍｅｉｍ—
ｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓａｒｅｃｏｍｐａｒｅｄａｎｄａｎａｌｙｚｅｄｑｕａｎｔｉｆｉｅｄｉｎｄｅｔａｉｌ，ａｎｄａｎｏｖｅｌｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏ－ｒｉｔｈｍｃａｎｍａｋｅｔｈｅｐｒｏｇｒｅｓｓｔｈａｔ。ｔｈｅｔｏｔａｌｔｉｍｅｓｏｆｃｏｍｍａｎｄａｎｄｔｈｅｌｅｎｇｔｈｏｆｐａｒａｍｅｔｅｒａｐｐｅｎｄｅｄｗｉｔｈｅｖｅｒｙｃｏｍｍａｎｄａｒｅｄｅｃｒｅａｓｅｅｆｆｅｃｔｉｖｅｌｙ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｐｅｒｆｏｒｍａｎｃｅｓｈｏｗｓｔｈｅａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅ．
Ｋｅｙｗｏｒｄｓ：ＲａｄｉｏＦｒｅｑｕｅｎｃｙＩｄｅｎｔｉｆｉｃａｔｉｏｎ（ＲＦＩＤ）；ａｎｔｉ—ｃｏｌｌｉｓｉｏｎ；ｂｉｎａｒｙｓｅａｒｃｈａｌｇｏｒｉｔｈｍ
摘要：防碰撞算法是ＲＦＩＤ系统中的一项关键技术。在对基本二进制搜索算法及其各种改进算法进行详细的定量分析的基础上提出了一种改进算法。该算法能有效地降低命令发送的总次数和减少每次命令所附带的参数长度。仿真结果表明了该算法的有效性。关键词：射频识别；防碰撞；二进制搜索算法
ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００９．０３．０６３文章编譬：１００２—８３３１（２００９）０３—０２１０－０４文献标识码：Ａ中图分类号＇：ＴＰ３０１
ｌ引言
ＲＦＩＤ（射频识别）技术是一种无线自动识别技术，又称为电子标签技术。与传统的条形码识别技术相比，ＲＦＩＤ技术具有穿透性、无需人工干预、快速扫描、安全性高、数据记忆容量大、抗污染和耐久性等优点，其已经广泛应用于交通、物流、安全、防伪、生产控制和零售等行业Ｉｌ翊。近年来巨大的市场需求使ＲＦＩＤ技术迅速地发展起来。基于ＲＦＩＤ和Ｉｎｔｅｒｎｅｔ技术构建起来的物联网概念一经提出便得到各国政府的重视和支持。并且已经取得相当进展“ｌ。
一般地，在同—个ＲＦＩＤ系统中所有的射频标签都工作在相同的频率段。因此，如果阅读器的作用范围内有多个标签存在，同一时刻可能有多个标签获得能量并向阅读器发送信息，这样就会出现互相干扰，使读写器不能正确识别标签，称为标签冲突或碰撞（Ｃｏｌｌｉｓｉｏｎ）。因此。需要一种防碰撞技术来识别多个标签，解决碰撞的算法称为防碰撞算法。传统的解决防碰撞问题基本上有四种方法：空分多址（ＳＤＭＡ）、频分多址（ＦＤ—ＭＡ）、码分多址（ＣＤＭＡ）和时分多址（ＴＤＭＡ）１３－４３。目前，考虑各种方法的实现复杂度和成本价格等因素，时分多址（ＴＤＭＡ）算法是射频识别系统防碰撞问题的常用方法。基于ＴＤＭＡ的防碰撞算法主要有两种：二进制搜索算法和ＡＬＯＨＡ算法。ＡＬＯＨＡ算法采用无规则的时分多址，也称随机多址。其操作简便，便于实际应用，但ＡＬＯＨＡ算法随着标签数量的扩大，性能将会急剧恶化１４１。二进制搜索算法的电路实现相对复杂，但算法识别率较高。基于动态二进制搜索的防碰撞算法是ＩＳＯ／ＩＥＣ标准推荐使用的算法之』。
主要有两个指标衡量防碰撞算法的优劣：一个是平均最小时延，通过识别每个标签所需的平均比特数来反映；另一个是平均功率消耗，通过识别过程中平均每个标签发送的比特数来反映旧。以平均最小时延作为主要指标，对各种二进制搜索防碰撞算法进行定量分析，并在此基础上提出改进算法。仿真结果汪明了此改进算法是非常有效的。
２ＲＦＩＤ防碰撞算法
二进制搜索防碰撞算法采用比特冲突监测协议作为防碰撞方案１４１。其需要阅读器能够确定碰撞的准确比特位置。因此，必须选用合适的编码。曼彻斯特编码（Ｍａｎｃｈｅｓｔｅｒ）可在多个标签同时响应时按位识别出碰撞位，这样町以根据碰撞的位置，按一定规则重新搜索标签。现行二进制搜索算法中标签响应发送回阅读器的数据都采用曼彻斯特编码。
以下分析假设标签ＩＤ号的长度为Ｎ，按位表示为【ⅣＮ—ＩⅣ＿２…１１。现有Ｑ个标签待识别，第一次检测时共有Ｐ个冲突位。
２．１基本二进制搜索算法
２．１．１算法思凫ｉ
基本二进制搜索算法的主要思想是阅读器发送一长度为Ⅳ的序列号，各个标签将自身的ＩＤ号与接收的序列号比较。其
作者简介：吴跃前（１９８３一），男，硕士，主要研究领域为射频识别、语音识别；辜大光（１９８５一），男，硕士，主要研究领域为射频识别、蓝牙通信；范振粤（１９８３一），男，硕士，主要研究领域为射频识别、嵌入式；杜明辉（１９６２一），男，教授，博士生导师，主要研究领域为无线网络、图像处理。
收籍１３期：２００８－０１－０４修回日期：２００８－０４－２４
万方数据
吴跃前，辜大光，范振粤，等：ＲＦＩＤ系统防碰撞算法比较分析及其改进算法
二进制数值小于或者等于该序列号的标签将回送自身的ＩＤ号
给阅读器，否则不作响应。这样可以缩小预选标签的范围。其基本处理流程为：
步骤１初始化。阅读器发送—个序列号为全ｌ的请求命令，所有标签同时响应并把其自身的ＩＤ号发送回给阅读器。阅读器检测出最高冲突位，假设为第肘（肘＜Ⅳ）位，据此阅读器将
得到下次清求命令的序列号参数。该序列号的前（Ⅳ－肘）位与响应的ＩＤ号的前（Ⅳ埘）相同，第肘位为０，后面（肌１）为全ｌ。
步骤２阅读器将步骤１得到的新的序列号参数发送出去，各个标签将自身的ＩＤ号与接收的序列号比较，其二进制数值小于或者等于该序列号的标签将回送自身的ＩＤ号给阅读器，否则不作响应。阅读器根据以上算法思想获得下一次清求命令的序列号参数。
重复步骤２直到只有１个标签响应为止。识别该标签后再对该标签进行去活化（ＵＮＳＥＬＥＣＴ命令），接着回到步骤１循环，直到识别出所有标签为止。
２．１．２算法分析
一次命令发送和响应过程的等效时间长度包括命令本身编码的长度、命令参数长度和标签响应该次命令的数据长度。对算法进行分析时主要考虑识别出所有标签时命令发送的总次数、命令参数长度和标签响应数据长度。
基本二进制搜索算法搜索到第一个标签发送的命令次数为：
Ｌ（Ｑ）＝呻（Ｑ）】＋ｌ（１）基本二进制搜索在检测到第一个标签后对其进行去活化再从头开始搜索。此时有待识别的标签是ｐ一１个。因此搜索到刍ｇ－＇Ａ＇－标签的命令次数是：
￡（Ｑ一１）＝【１ｂ（９—１）】＋ｌ（２）
所以搜索完全部标签所需发送的命令次数为：
０
强乞ｆ［１ｂ（ｇ）】＋ｌＪ（３）ｑ＝ｌ
阅读器发送一次命令的参数长度为Ⅳ，标签响应一次命令的长度也是Ⅳ。
２．２基本二进制搜索算法的改进
基本二进制搜索算法主要存在两方面的冗余信息。第一，巷本二进制搜索算法在识别出一个标签之后将从头开始下一轮的识别，没有利用之前已经获得的预选标签的范围信息。第二，基本二进制搜索算法阅读器的请求命令中最高冲突位后的所有比特位都被置…１’，因而这部分编码对标签的识别不能提供任何的信息；而标签返ｌ旦Ｊ的包括最高冲突位在内的前部分比特位对于阅读器也是知的。因此传输序列号各自的互补部分是多余的。
２．２．１基于返Ｉ口Ｉ式的二进制树形搜索算法嘲
该算法是针对第—方面而提出的改进算法。该算法的主要思想是当阅读器识别出—个标签之后，不是从头开始以全１作为下一次清求命令的序列号参数。而是根据上一次清求命令的序列号参数来获得。上一次请求命令是将之前的最高冲突位置为ｏ，这一次的请求命令则是将之前的最高冲突位置为１，这样将可以立刻识别出下—个标签，极大地加快了识别的过程。
该算法搜索到全部Ｑ个标签的总的发送命令的次数为闭：
Ｔ＝２Ｑ－１（４）
其较基本二进制搜索算法的搜索次数是数量级上的减少。２．２．２动态二进制搜索算法附，田
该算法是针对第二方面而提出的改进算法。其主要思想是当阅凑器检测到最高冲突位（假没为第肘）后，下一次阅读器请求命令的序列号参数是最高冲突位之前的（Ⅳ一肘）位加上Ｉ位“０”，共＾Ｌ朋＋ｌ位。各个标签将自身ＩＤ号的前Ｎ—Ｍ＋Ｉ位与之比较，相同的标签将回送其序列号的后面朋ｒ－１位。
很容易得出，一次命令的发送和响应过程中，发送命令参数长度和标签响应数据的长度的和为Ⅳ。因此动态二进制搜索算法较基本二进制搜索算法在传输数据量和所需时间上的减少可达５０％。
２．２．３多状态二进制搜索算法１４１
该算法是针对第二方面而提出的改进算法。其主要思想是阅读器只发送最高冲突位的位置信息。为了充分利用已经得到的冲突信息，该算法引入了休眠计数的方法。其设定标签有三种状态：待命态、休眠态和去活态。标签中设有一个休眠计数器。计数器的值为０时该标签处于待命态，大于０为休眠态，去活态是指阅渎器已经识别出该标签，并发送去活化命令让其不再响应以后阅读器发送的命令。阅读器在检测到最高冲突位后（假设为第Ｍ位），下一次发送请求命令的序列号参数格式是（ｘ，肘），｜）｜ｆ是—个比特，是０或者１。此时处于待命状态的各个标签检测自身的ＩＤ号的第肘位，如果该位是ｘ。则其将自身ＩＤ号的后面朋ｒ－１位发送四给阅读器，否则该标签将从待命状态转入休眠态，休眠值为ｌ。原来处于休眠态的标签不作响应，并且其休眠值都增加１。阅读器从接收的肛一１位数据中检测到新的最高冲突位，按以上格式继续进行搜索，直到检测到一个标签。接着其发送一次激活的命令，将休眠值为１的标签转为待命态，并按返回式二进制树形搜索的方法修改ｘ值返回搜索，将立刻识别到第二个标签。
由于阅读器发送的序列号参数只是冲突的位置信息，该算法能极大地减少发送的数据量。其发送一次命令的参数长度为（［１ｂ（Ⅳ）１＋１），标签响应的数据长度是胁．１，肼是此次命令发送的最高冲突位位置值。
但因为该算法搜索的过程中伴随着激活命令的发送过程，因此其将比返回式搜索多出一些时间上的开销。
该算法搜索到全部Ｑ个标签的总的发送请求命令的次数和需要发送的激活命令的次数分别为：
ＴＩ＝２Ｑ－１，Ｔ２＝２Ｑ一２（５）因此总的命令次数是：
Ｔ＝ＴＩ＋Ｔ２＝４Ｑ一３（６）２．２．４引入预处理的‘进制搜索算法［ｓｌ
该算法的主要思想是在常用的算法运行之前进行一次预处理。阅读器发送第一次清求命令后，所有标签都将自己的ＩＤ发送ｔ＂ｌ来，阅读器一次性榆测到所有的冲突位。其将冲突位记为１，非冲突位记为０。并将此』ｖ比特标志数据发送给标签。各个标签按照此标志数据将ＩＤ号对应的冲突位数据抽取出来作为其新的ＩＤ号与阅读器通信。这样，如果ＩＤ号不完全冲突，对于任一种算法，阅读器和标签发送的数据量都将减少。
３改进算法
多状态二进制搜索算法的仿真效果对于动态二进制搜索算法是—个很大的改进。作者在对多状态二进制搜索算法进行分析研究的基础提出了一种改进算法，并将其命名为改进的多
万方数据
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
状态二进制搜索算法。该算法在原先的多状态二进制搜索算法上做出了两方面的改进。
（１）发送命令次数的减少。这主要通过修改休眠计数的策略来获得。修改后的算法将不再需要发送激活命令。这样将节省一半的命令数。该策略为：
①如果阅读器发送请求命令的序列号参数中的ｘ是０，则处于待命态的标签若其ｌＤ号的第Ｍ位是Ｏ就要做出响应，否则转入休眠态，休眠计数值为ｌ。其他处于休眠态的标签其休眠值皆加１。
②如果阅读器发送请求命令的序列号参数中的ｘ是ｌ，则所有标签的休眠计数值皆减ｌ。原先休眠值为１的标签将转为待命态。这时处于待命态的标签，如果其第肘位的值为１，则其要将ＩＤ号后面Ｍ一１位数据发送ｌ旦ｌ给阅读器。
（２）请求命令所带参数的比特长度和标签响应命令数据长度的减少。本算法引进上述介绍的预处理过程。因此若ＩＤ号不完全冲突，则预处理后标签每次响应命令的数据长度必然减少。此外，本算法对预处理过后的冲突位进行再编码将町以进一步减少请求命令所带参数的比特长度。多状态二进制搜索算法发送请求命令时的参数长度为（曲（Ⅳ）】＋１ｏ而本算法若预处理过后的新的ＩＤ号长度为Ｐ（Ｐ＜Ｎ），则新的请求命令所带参数的长度为（【ｌｂ（尸）】＋ｌｏ
假设现有５个标签需要识别，它们的ＩＤ号分别是：
标签１：０１０１０１１００ｌＯｌ
标签２：０１０１０１１０１ｌ０ｌ
标签３：Ｏｌｌｌ０１ｌＯ０１０１
标签４：０１１０叭ｌＯ１００１
标签５：０１０ｌ０１１０００Ｏｌ
其识别过程如图１。
在搜索的过程中，用—个后进先出的堆栈来记录发送的冲突位信息。堆栈的元素是—个结构体，含有两个成员：ＩＸ，加。Ⅸ，柳是请求命令发送的参数。当检测到最高冲突位膨时，令Ｘ－－－－Ｏ，将｛０，椰入栈。当识别出一个标签时检测栈项元素的ｘ值。如果是０，则将ｘ改为１，下一次请求命令为ｆ１，棚；如果是１，则将栈顶出栈，继续检测当前栈的栈顶元素的ｘ值，以此类推。栈的长度为０时表示搜索完毕。
由于该算法不需要发送激活命令，故总的发送命令次数为：ｚ’－丁１＝２Ｑ一１（７）阅读器发送一次命令的参数长度为（呻（Ｐ）】＋１），（刚Ｖ）。标签响应的数据长度为朋Ｌ１。
明显，改进的多状态二进制搜索算法比其他算法具有更大的优势。
４仿真及其结果分析
对以下４种算法进行了仿真，它们分别是基于返回式树形搜索的动态二进制搜索算法、多状态二进制搜索算法、未引入预处理的改进多状态二进制搜索算法、引入预处理的改进多状态二进制搜索算法。
ＥＰＣ标准推荐的一种编码长度为９６ｂｉｔ。其格式为８ｂｉｔ版本号（Ｖｅｒｓｉｏｎ）、２８ｂｉｔ域名管理（ＥＰＣＭａｎａｇｅｒ）、２４ｂｉｔ对象名称（Ｏｂｊｅｃｔ）和３６ｂｉｔ物品序列号（ＳｅｒｉａｌＮｕｍｂｅｒ）。命令的编码长度采用ＩＳＯ／ＩＣＥ１４４４３标准制定的９ｂｉ一。
仿真采用的一个量化指标是平均识别一个标签所需的比特数：
ＡｖｅｒａｇｅＢｉｔ：．ＣｏｍｍａｎｄＬｅｎｇｔｈ＋ＳｅｎｄＬｅｎｂ，ｔｈ＋ＲｅｃｅｉｖｅＬｅｎｇｔｈ（８）
川
Ⅳ是待识别的总的标签数目。ＣｏｍｍａｎｄＬｅｎｇｔｈ是指完成所有标
图１改进算法的标签识刖过程万方数据
吴跃前，辜大光，范振粤，等：ＲＦＩＤ系统防碰撞算法比较分析及其改进算法２００９。４５（３）２１３
签搜索命令发送本身的总长度，ＳｅｎｄＬｅｎｇｔｈ是指完成所有标签搜索阅读器发送命令的参数的总长度，ＲｅｃｅｉｖｅＬｅｎｇｔｈ是指完成所有标签搜索标签响应命令的总长度。
仿真所需的９６ｂｉｔＩＤ号是随机产生的。它按以下方法产生：如果要识别Ⅳ个标签，则在Ｎｘｌ５０００的数目范围中分别随机产生』、ｒ个２８ｂｉｔ随机数、２４ｂｉｔ随机数和３６ｂｉｔ随机数作为Ⅳ个标签ＩＤ号的后面８８位编码，ＩＤ号的前８位是版本号设为同样数据。对于—个商店的物流管理，其商品配送过程中各个商品的ＩＤ号大部分都是一样的。Ｎｘｌ５０００的数目范围随机产生Ⅳ个ＩＤ号足以模拟实际的配送跟踪过程。对３种情况分别进行仿真。第一种是同一种商品，只有Ｓｅｒｉａｌ（３６ｂｉｔ）不同，其他编码是一样的；第二种是不同商品，Ｏｂｊｅｃｔ和Ｓｅｒｉａｌ是不同的，其他编码相同；第三种是除了版本一样，其他都不一样。
仿真结果分别如图２～图４所示。
标签数目Ｎ／＋
图２各标签ＳｅｒｉａｌＮｕｍｂｅｒ不同的情况
下各算法的性能比较
标签数目Ⅳ，个
图３各标签ＳｅｒｉａｌＮｕｍｂｅｒ和Ｏｂｊｅｃｔ不同的
情况下各算法的性能比较
标签数目Ｍ个
图４各标签ＳｅｒｉａｌＮｕｍｂｅｒ，Ｏｂｊｅｃｔ和ＥＰＣ均
不同的情况下各算法的性能比较
基于返回式树形搜索的动态二进制搜索算法是ＩＳＯ／ＩＥＣｌ４４４３标准的推荐算法。由仿真结果可知，多状态二进制搜索算法、未引入预处理的改进多状态二进制搜索算法和引入预处理的改进多状态二进制搜索算法在三种情况下都体现出比标准推荐算法更好的性能。同时，由图也可以得知以下结论：（１）改进多状态二进制搜索算法由于不需发送激活命令，其平均识别一个标签比原先的多状态二进制搜索算法要少将近２０ｂｉｔ。
（２）在三种情况下，当待识别标签数目大于１０时，引入预处理的改进多状态二进制搜索算法明显比其他算法具有更好的性能。特别地，第二种情况（图３）是商品配送中较为常见的情况，其表示待识别的同一家公司生产的不同的商品。在这种情况下，引入预处理的改进多状态二进制搜索算法比起其他算法有极具吸引力的性能优势。当待识别标签数目大于２０时，其平均识别—个标签比起标准推荐算法要少１１０ｂｉｔ，节省超过５０％；其比起多状态二进制搜索算法要少５０ｂｉｔ，节省３３％左右。
（３）标准推荐算法运行时，每次阅读器发送命令，各个没有去活化的标签均要响应该次命令。而改进算法是只有处于待命状态的标签才去响应该次命令，相比之下，改进算法的平均功耗会大大降低。
５结论
研究了ＲＦＩＤ系统中的防碰撞算法，对基本二进制搜索算法及其改进算法进行了详细的定量分析，在此基础上提出了一种改进算法。该算法能有效地降低命令发送的总次数和减少每次命令所附带的参数长度。实验证明改进的多状态二进制搜索算法能够迅速有效地识别出电子标签。该算法对于大批量物品跟踪和管理具有重大的意义。
参考文献：
【ｌ】宁焕生，张瑜，刘芳丽，等冲国物联网信息服务系统研究田．电子学报，２００６，１２Ａ：２５１４－２５１７．
【２１ＦｉｎｋｅｎｚｅｌｌｅｒＫ．ＲＦＩＤ－ＨＡＮＤＢＯＯＫ，ｆｕｎｄａｍｅｎｔａｌｓａｎｄ印ｐｌｉｃａｔｉｏｎｓｉｎｃｏｎｔａｅｆｌｅｓｓＳｌｌｌａｒｔｃａｒｄｓｉｄｅｎｔｉｆｉｃａｔｉｏｎ［Ｍ］．２ｎｄｅｄ．ｉｓ．１．】：Ｗｉｌｅｙ＆ＳｏｎｓＬｔｄ，２００３．
【３】３余松森，詹宜巨，彭卫东．基于返回式索引的二进制树形搜索反碰撞算法及其实现叽计算机工程与应用，２００４，４０（１６）：２６－－２８．
【４１姜丽芬，卢桂章，辛运帷．射频识别系统中的防碰撞算法研究田．计算机工程与应用，２００７，４３（１５）：２９—３２．
【５１ＩＳＯｔＩＥＣ１４４４３－３ｉｄｅｎｔｉｆｉｃａｔｉｏｎｃａｒｄｓｃｏｎｔａｃｔｌｅｓｓｉｎｔｅｇｒａｔｅｄｃｉｒｃｕｉｔ（ｓ）ｃａｒｄｓ－ｐｒｏｘｉｍｉｔｙｃａｒｄｓ，ｐａｒｔ３：ｉｎｉｔｉａｌｉｚａｔｉｏｎａｎｄａｎｔｉｃｏｌｌｉｓｉｏｎ［Ｓ］．２００３．【６】ＨｕｓｈＤＲ，ＷｏｏｄＣ．ＡｎａｌｙｓｉｓｏｆｔｒｅｅａｌｇｏｒｉｔｈｍｓｆｏｒＲＦＩＤａｒｂｉｔｒａ－ｔｉｏｎｔＣ！ｌｎｓｒｒ１９９８。Ｃ缸Ｉｂｒｉｄｇｅ，ＭＡ，ＵＳＡ，１９９８，２９（１１）：１６－２１．
【７】７ＳｈｉｈＤｏｎｇ—ｈｅｒ，ＳｕｎＰｏ－ｌｉｎｇ，ＹｅｎＤＣ．ＴａｘｏｎｏｍｙａｎｄｓｕｒｖｅｙｏｆＲＦＩＤａｎｔｉ－ｃｏｉｌｉｓｉｏｎｐｒｏｔｏｃｏｌｓ［Ｊ］．ＣｏｍｐｕｔｅｒＣｏｕｍｍｕｎｉｅａｔｉｏｎｓ．２０（）６．２９（１１）：２１５０－２１６６．
【８１ＣｈｏｉＪＨ，ＬｅｅＤ，ＹｏｕｎＹ．Ｓｃａｎｎｉｎｇ—ｂａｓｅｄｐｒｅ—ｐｒｏｃｅｓｓｉｎｇｆｏｒｅｎ－
ｈａｎｃｅｄ
ｔａｇ
ａｎｔｉ－ｃｏｌｌｉｓｉｏｎｐｒｏｔｏｃｏｌｓ［Ｃ］／／ＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＣｏｍｍｕｎｉｃａｔｉｏｎｓａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｉｅｓ，ＩＳＣＩＴ’０６，２００６：１２０７－１２１１．
＆ｈ
万方数据
RFID系统防碰撞算法比较分析及其改进算法
作者：吴跃前， 辜大光， 范振粤， 杜明辉， WU Yue-qian， GU Da-guang， FAN Zhen-yue，DU Ming-hui
作者单位：华南理工大学,电子与信息学院,广州,510641
刊名：
计算机工程与应用
英文刊名：COMPUTER ENGINEERING AND APPLICATIONS
年，卷(期)：2009，45(3)
引用次数：0次
参考文献(8条)
1.宁焕生.张瑜.刘芳丽冲国物联网信息服务系统研究 2006
2.Finkenzeller K.RFID-HANDBOOK fundamentals and applications in cantactless smart cards
identification 2003
3.余松森.詹宜巨.彭卫东.赵振宇基于后退式索引的二进制树形搜索反碰撞算法及其实现[期刊论文]-计算机工程与应用 2004(16)
4.姜丽芬.卢桂章.辛运帏射频识别系统中的防碰撞算法研究[期刊论文]-计算机工程与应用 2007(15)
5.ISO/IEC 14443-3.identification cards contactless integrated circuit(s) cards-proximity cards,part 3:initializatian and antieollision 2003
6.Hush D R.Wood C Analysis of tree algorithms for RFID arbitration 1998
7.Shih Dong-her.Sun Po-ling.Yen D C Taxonomy and survey of RFID anti-collision protocols 2006(11)
8.Choi J H.Lee D.Youn Y Scanning-based pre-processing for enhanced tag anti-collision protocoh 2006
相似文献(10条)
1.期刊论文张捍东.张淳.ZHANG Han Dong.ZHANG Chun一种适合多协议防碰撞的射频识别阅读器设计-电子技术
应用2009,35(6)
针对目前市场上射频识别阅读器只能识别单协议标签的情况,设计了一种能够识别ISO/IEC15693和ISO/IEC14443-3 TYPE A两种协议标签的射频识别阅读器.采用TI公司的13.56 MHz频段下的芯片S6700作为射频模块,现场可编程逻辑器件作为控制器,和单片机相比,减少了外围电路.同时针对同时读取多标签的情况,提出了一种改进的动态二进制防碰撞算法,用计数器保存标签的休眠程度,理论分析和仿真结果表明其性能优于动态二进制算法.
2.学位论文汪盛虎射频识别技术中防碰撞算法及认证协议研究2008
射频识别技术是一项从上世纪八十年代开始逐步走向成熟的自动识别技术。与其它自动识别技术相比，RFID技术以其特有的无接触、抗干扰能力强等优点，逐渐成为自动识别技术中最受欢迎的技术之一，并被广泛地应用于各个领域。射频识别系统数据传输的完整性一直是研究的重点，主要是多卡识别问题。随着射频识别系统的推进和发展，它的安全性也逐渐引起了人们的关注，身份认证是系统安全的第一道屏障，对整个系统的安全性具有十分重要的作用。 本文归纳总结射频识别技术的主要特点、发展现状，以及存在的问题，对目前主流的射频识别国际标准进行研究和比较，详细分析了射频识别系统的工作原理。重点研究射频识别技术中的防碰撞算法和认证协议。 针对射频识别的多卡识别问题，本文主要对防碰撞算法进行研究，重点讨论基于TDMA的RFID阅读器控制的防碰撞算法，主要有基于ALOHA算法的普通帧时隙ALOHA算法(BFSA)，动态帧时隙ALOHA算法(DFSA)，增强型动态帧时隙舡ALOHA算法(EDFSA)，并对各种算法进行详细的分析和仿真。 为了提高识别效率，在帧时隙ALOHA算法的基础上，研究设计了快速检测读取帧时隙ALOHA防碰撞算法(FDRA)，对新算法进行分析和仿真。将各个基于ALOHA防碰撞算法进行仿真，并进行性能的分析和比对，仿真结果表明FDRA在识别的效率上有明显的优势。 为了阻止潜在的风险并增强消费者隐私，本文总结RFID安全与隐私方面的问题，分析并概括RFID隐私威胁与安全需求。对几种基于Hash协议的RFID认证协议从安全性、所占用的存储空间和认证所需计算量三方而进行详细地分析，指出它们的优缺点。分析研究基于Hash的改进认证协议，对新的认证协议进行分析，并与其他基于Hash的RFID认证协议对比，分析结果表明改进认证协议在安全性综合性能优于其它协议，具有较好的应用前景。
3.学位论文宁兆熙900M RFID射频识别系统中通讯物理接口和防碰撞方法2003
射频识别(RFID)在当前已经有很广泛的应用，并且低频率的射频识别系统已经得到足够的开发和了解，而高频的射频识别系统的应用和开发还没能达到足够的程度。低频率的射频识别系统采用磁场的工作方式，工作距离比较近，无源应答器获得能量一般采用磁场耦合的方式。而高频率的射频识别系统采用电场的工作方式，工作距离比较远，无源应答器获得能量只能通过天线接收的方式。从低频率的射频识别系统研究中得到的很多应用方法和知识无法在高频率射频识别系统中使用。由于高频率射频识别系统中应答器发送到阅读器的信号传输一般采用的是反向散射的方式，因此要以反向散射的特点为基础，结合适用有效的射频信号接口，设计新的适合的防碰撞方法，和有效的通讯协议设计。 由于传统的方式的局限性，以及根据高频率射频识别系统中应答器发送到阅读器的信号传输一般采用的是反向散射调制的方式。因此根据：1。采用新的编码降低高频射频识别系统中硬件设计的困难。2。采用新的编码方式，有利于进行高频射频识别系统中最常用的反向散射方式。应当根据上面的两点设计更加有效的射频信号接口。 RFID中的防碰撞方法技术是RFID通讯协议的基础，现有的防碰撞方法已经经过了很长时间的发展，但是仍然有改进的余地，特别是在高频射频识别系统中常用的反向散射调制过程中。 现在的防碰撞方法一般可以分成两大类：ALOHA法和二进制搜索算法。因此现有的通讯协议也基本都按照这两种基本方法进行扩展而来。这里使用的新方法和新协议将有机融合这两种方法，可以看到的是，这里使用的Type A方法是ALOHA方法，但有机融合了二进制搜索方法的好处，而这里使用的Type B是二进制搜索方法，但是有机融合了时隙ALOHA方法的好处。 对于RFID系统来说，需要一套完整的通讯协议的系统才能正常的进行工作，通讯协议的基础在于防碰撞方法的使用。在一定的防碰撞方法的基础上，结合具体的物理接口的使用，已经进行具体化的规定，这样就得到了通讯协议。这里提出的两种通讯协议是分别按照这里提出的两种防碰撞方法，结合这里提出的物理接口等方面的内容形成的，其中又具体增加了如何进行RFID中Tag的Memory的读写操作的问题。 本文提出了可用于高频射频识别系统的一种信号接口，两种防碰撞方法，两种具体的通讯协
议。
4.学位论文吕俊射频识别技术（RFID）防碰撞算法研究2005
射频识别(Radio Frequency Identification，RFID)技术是从上世纪80年代走向成熟的一项自动识别技术，近年来发展十分迅速。射频识别技术可以用来识别和跟踪几乎所有物理对象，并由此可以构建一个容纳和连结世界上所有物品的广泛的智能网络，RFID技术发展带来的影响将改变我们的生活，给全世界带来一场新的技术革命。 本文介绍了射频识别技术的发展状况，讲解了射频识别系统的结构、基本工作原理以及系统数据传输的编码方式与校验方法。对射频识别的关键技术防碰撞算法作了深入的研究。 防碰撞算法也就是利用多路存取法，使得射频识别系统中的阅读器和电子标签之间数据能够完整的传输。空分多路法、频分多路法和码分多路法在射频识别系统的应用均受到一定的限制。目前在射频识别系统中，主要是采用时分多路法的原理，使每个电子标签在单独的某个时隙内占用信道与阅读器进行通信，防止碰撞产生。时分多路防碰撞算法主要有ALOHA算法和二进制搜索算法等。这些防碰撞算法协议均不成熟，还存在很大的改进余地。设计一种识别速度快且识别正确率高的防碰撞算法是本论文的研究目的。
本论文的创新之处在于通过对射频识别系统的各种防碰撞算法(包括ALOHA算法、时隙ALOHA算法、动态时隙ALOHA算法、随机二进制树形搜索算法、二进制树形搜索算法等)的研究，在分析它们的特点及存在的缺点后，采用按位检测碰撞暂停通信的方法对二进制树形搜索算法进行了改进，改进后的算法比其他的算法信道利用率更高，耗时更少，准确率达到100％，有助于推动射频识别技术的发展。
5.学位论文李世煜射频识别（RFID）系统防碰撞算法研究与设计2008
无线射频识别技术(Radio Frequency Identification，RFID)是一种非接触数据自动采集技术，它以空间电磁波为传输媒介从而达到双向通信、自动识别的目的。由于具有工作环境要求低，自动高速识别，准确实时批量，成本低、寿命长，更适合与各种自动化处理设备配合使用等显著优点
，RFID被称为第三代识别技术，是目前发展最为迅速、潜力最大的新兴技术之一。 标签防碰撞技术是射频识别系统的关键技术之一，它决定着系统的识别速度和识别效率，是实现多目标快速识别这一RFID发展趋势的前提条件。本文首先简述了RFID的一些基本概念，然后介绍了RFID的碰撞问题和当前流行的标签防碰撞算法。在总结分析查询树算法、动态查询树算法、二进制搜索算法等确定性标签防碰撞算法的基础上，针对研究得出的结论，给出了两种新型确定性标签防碰撞算法：分层深度搜索树形算法和基于BIBD(6，4，3，2，1)的确定性防碰撞算法。 分层深度搜索树形算法是在动态查询树算法基础上给出的新型算法。由于采用了深度搜索、堆栈记忆、后退机制的原则，阅读器和标签不需重复发送已知信息，最大化的减少了传送冗余信息的数量。系统不采用Manchester编码，提高了一倍的传码效率。算法查询时间随标签增加慢速线性增长，尤其适用于标签数量多、标签ID长度较长的识别环境。 基于BIBD(6，4，3，2，1)的确定性防碰撞算法是以二进制搜索算法和平衡不完全区组设计BIBD(6，4，3，2，1)为基础的新型算法。将标签分节，每节只包含BIBD(6，4，3，2，1)的子集。由BIBD(6，4，3，2，1)子集的特性，阅读器能迅速判断出存在的子集情况。系统通过逐节识读达到快速识别的目的。 数学分析和仿真结果表明本文给出的两种新型算法性能显著优于既有经典确定性算法，尤其适用于多标签RFID应用环境。 文末简要介绍了阅读器碰撞问题并给出了一种简单的时序开关防碰撞方法。
6.期刊论文赵灵军.周超英.ZHAO Ling-jun.ZHOU Chao-ying基于ISO 15693协议的防碰撞算法及其实现-微计算
机信息2008,24(26)
多个电子标签被识别时发生碰撞是射频识别(RFID)技术中的关键问题.ISO15693协议中描述的防碰撞算法是基于16个时隙,就其理论而言相对简单,但是在实际的应用中,由于其严格的时序要求,实现比较困难.针对多个电子标签被识别时发生碰撞的射频识别(RFID)关键技术问题,本文提出一种完全符合ISO15693协议的推挽式二进制搜索算法,并在性能方面与ALOHA算法作了简单的比较.最后阐述了本算法在ARM处理器S3C2410中的软硬件的实现过程.
7.期刊论文邹和仕.解光军高频电子标签的防碰撞算法研究-计算机工程与应用2009,45(26)
多张电子标签的防碰撞技术是射频识别中的一个关键技术,防碰撞算法的好坏直接影响着RFID系统处理多张电子标签的能力.研究了高频电子标签的防碰撞原理,在二进制搜索算法和时隙SLOTS算法的基础上提出了动态混合算法和类八进制搜索算法,并对算法进行了性能分析.实验结果表明,这两种算法具有更优越的性能.
8.期刊论文焦传海.王可人.JIAO Chuan-hai.WANG Ke-ren多枝查询树协议在解决射频识别碰撞问题中的应用-电
讯技术2008,48(3)
数据碰撞是影响射频识别(RFID)系统识别效率的主要因素.目前,常用的防碰撞算法是ALOHA算法和二进制树搜索算法,但这两类算法都还不能完全解决标签碰撞问题,尤其是当待识别的标签数量较大且标签ID序列号较长时,识别速度相当慢.为此提出一种多枝查询树协议,采用均衡不完全区组设计(BIBD)对标签ID进行编码,并用16位的BIBD码作为读写器查询前缀符号.理论分析和仿真结果表明,这种协议的性能较传统的防碰撞协议有明显改善.
9.期刊论文王建伟.赵玉萍.Timo Korhonen.Wang Jian-wei.Zhao Yu-ping.Timo Korhonen RFID系统防碰撞协议研
究——设计与优化-电子与信息学报2009,31(1)
碰撞问题是影响射频识别(RFID)系统读取效率的关键问题.该文提出了两种新的防碰撞协议--CDCA协议和CDCA-2D协议,并且对两种协议进行了详细的理论分析和优化.新协议将RFID系统的读取过程分为两个阶段,利用第1阶段的碰撞检测信息实现在第2个阶段的无碰撞通信.仿真结果表明,和目前国际上流行的RFID防碰撞算法相比,两种新协议极大地提高了读取的效率.
10.学位论文刘拓晟RFID防碰撞算法的研究2009
无线射频识别技术（Radio Frequency Identification，RFID），或称射频识别技术，作为一种快速、实时、准确采集与处理信息的高新技术和信息标准化的基础被列为本世纪十大重要技术之一，可广泛的应用到各个领域。这是因为RFID具有的无接触的优点，并且携带的数据比传统的条形码更多。但作为一种新兴的应用技术，RFID的应用中还存在一些不足如：识别准确率不高，RFID标准化进程缓慢等。其中，标签碰撞和阅读器碰撞带来的标签识别效率不高是RFID技术中最重要的问题之一。研究快速、准确、有效防碰撞问题的解决方案已经成为一个非常有意义的课题，它对RFID技术的发展有着至关重要的作用。 本文介绍了射频识别技术的基本原理、结构、特点及其相关的基础理论知识，特别对数据传输中的防碰撞问题进行了深入的研究。在射频识别系统中的阅读器作用范围内，有多个标签要求通信而发生碰撞问题，而解决这个问题必须要用到多路存取法。近年来，防碰撞算法一般采用时分多路。采用时分多路法的算法有ALOHA算法、时隙ALOHA算法、二进制树型搜索算法等防碰撞算法，文章分析了各自特点以及存在的缺点。
射频识别技术在当前已经有很广泛的应用，并且低频率的射频识别系统已经得到足够的开发和了解，而高频的射频识别系统的应用和开发还没能达到足够的程度。由于高频率射频识别系统中应答器发送到阅读器的信号传输一般采用的是反向散射的方式，因此要以反向散射的特点为基础设计新的适合的防碰撞方法。在对国内外文献额搜索、整理、分析和综合的基础上，对标签的防碰撞问题作了深入的研究。 文中提出了两中基于码分多址的防碰撞算法。一种是基于扩频ALOHA的防碰撞算法，此算法在保留原有ALOHA防碰撞算法的机理上，结合码分多址技术的扩频特性形成的，同时引入LS码
，使得此算法具有基带宽，信号间干扰小，较高的系统吞吐量、算法简洁便于实现。另一种是一种基于预约ALOHA的码分多址防碰撞算法，此算法是码分多址技术的基础上，结合预约ALOHA的竞争机理形成。在这个算法中，上行信道被划分为多个独立的码分信道，每个码分信道采用预约ALOHA的竞争机制。文中给出了算法的马尔可夫模型。此算法具有抗衰落能力强、保密性强、系统吞吐量大等优点。文章对两种算法进行了数学分析，并用MATLAB对系统吞吐量性能进行了仿真。
本文链接：https://www.doczj.com/doc/d16283973.html,/Periodical_jsjgcyyy200903063.aspx
下载时间：2010年1月14日