一种有效的RFID防碰撞方法
- 格式：ppt
- 大小：730.50 KB
- 文档页数：11
下载文档原格式
合集下载
RFID系统防碰撞算法
收稿日期:2009-05-02;修回日期:2009-07-30作者简介:王铖岑(1986-),女,江苏如皋人,硕士研究生,研究方向为企业信息化;导师:邓建明,博士,硕士生导师,研究方向为软件理论及软件工程。
RFID 系统防碰撞算法王铖岑(东南大学软件学院,江苏南京210096)摘 要:无线射频识别(RFID )系统经过多年的发展已经成为人们日常生产、生活中重要的一部分了。
在RFID 系统的研究中,防碰撞(Anti -collision )是一个重要的问题,并且会在很大程度上影响RFID 系统的性能。
针对三种不同的碰撞类型对防碰撞算法进行了分类,其中有些算法已经成为了工业界的标准。
另外,对RFID 系统中一些特殊应用中的防碰撞算法进行了介绍。
通过完整的综述,希望读者能够了解防碰撞算法进展,掌握防碰撞算法未来的研究方向。
关键词:无线射频识别;防碰撞;时间片;多读写器中图分类:TP391.44 文献标识码:A 文章编号:1673-629X (2010)01-0029-04RFID Anti -collision :Standards ,Algorithms and ProtocolsWAN G Cheng 2cen(College of S oftware Engineering ,S outheast University ,Nanjing 210096,China )Abstract :With years of rapid development ,radio frequency identification (RFID )systems have been playing an important role both in our daily life and work.In the research area of RFID systems ,anti -collision is one of the major problems ,and has a great influence on the performance of RFID systems.According to different types of collisions ,categorizes various proposed anti -collision algorithms ,some of which have been adopted as industry standards.In addition ,presents some anti -collision algorithms tailored for special applications.Through the survey ,hope that audiences can get an explicit view of the state -of -art of anti -collision algorithms ,and know how to pursue the future research.K ey w ords :radio frequency identification ;anti -collision ;timeslot ;multi -reader0 引 言无线射频识别(Radio Frequency Identification ,RFID )技术是一种非接触式的自动识别技术,它通过射频信号自动识别目标对象并获取相关数据的信息。
RFID防碰撞技术
17
四、防碰撞算法
1 防碰撞的基本算法ALOHA
aloha[əˈloʊhə]int.夏威 夷人问候语，欢迎，再见;
ALOHA算法是一种随机接入方法，其基本思想是采取标 签先发言的方式，当标签进入读写器的识别区域内时就 自动向读写器发送其自身的ID号，在标签发送数据的过 程中，若有其他标签也在发送数据，将会发生信号重叠， 从而导致冲突。读写器检测接收到的信号有无冲突，一 旦发生冲突，读写器就发送命令让标签停止发送，随机 等待一段时间后再重新发送以减少冲突。
以开始传输信息。读写器以一个帧为周期发送查询命令，当电 子标签接收到读写器的请求命令时，每个标签通过随机挑选一 个时隙发送信息给读写器。
若一个时隙只被唯一标签选中，则此时隙中标签传输的信息 被读写器成功接收，标签被正确识别。若两个或两个以上标签 选择了同一时隙发送，则就会产生冲突，这些同时发送信息的 标签就不能被读写器成功识别。
曼彻斯特编码，常用于局域网传输。曼彻斯特编码将时钟和数据包含在数 据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，每位 编码中有一跳变，不存在直流分量，因此具有自同步能力和良好的抗干扰性 能。但每一个码元都被调成两个电平，所以数据传输速率只有调制速率的 1/2。
29
2.1 数据编码(信源编码)(第六章)
31
四、防碰撞算法
“识别”有多个标签----防碰撞指令规则
（3）READ-DATA——读出数据。选中的射频卡将存储的数据发 送给读写器。
(4)UNSELECT ——取消选择。取消一个事先选中的射频卡，射频卡进
入"无声"状态，在这种状态下射频卡完全是非激活的，对收到的REQUEST 命令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作 用范围再进入，以实行复位。
四、防碰撞算法
1 防碰撞的基本算法ALOHA
aloha[əˈloʊhə]int.夏威 夷人问候语，欢迎，再见;
ALOHA算法是一种随机接入方法，其基本思想是采取标 签先发言的方式，当标签进入读写器的识别区域内时就 自动向读写器发送其自身的ID号，在标签发送数据的过 程中，若有其他标签也在发送数据，将会发生信号重叠， 从而导致冲突。读写器检测接收到的信号有无冲突，一 旦发生冲突，读写器就发送命令让标签停止发送，随机 等待一段时间后再重新发送以减少冲突。
以开始传输信息。读写器以一个帧为周期发送查询命令，当电 子标签接收到读写器的请求命令时，每个标签通过随机挑选一 个时隙发送信息给读写器。
若一个时隙只被唯一标签选中，则此时隙中标签传输的信息 被读写器成功接收，标签被正确识别。若两个或两个以上标签 选择了同一时隙发送，则就会产生冲突，这些同时发送信息的 标签就不能被读写器成功识别。
曼彻斯特编码，常用于局域网传输。曼彻斯特编码将时钟和数据包含在数 据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，每位 编码中有一跳变，不存在直流分量，因此具有自同步能力和良好的抗干扰性 能。但每一个码元都被调成两个电平，所以数据传输速率只有调制速率的 1/2。
29
2.1 数据编码(信源编码)(第六章)
31
四、防碰撞算法
“识别”有多个标签----防碰撞指令规则
（3）READ-DATA——读出数据。选中的射频卡将存储的数据发 送给读写器。
(4)UNSELECT ——取消选择。取消一个事先选中的射频卡，射频卡进
入"无声"状态，在这种状态下射频卡完全是非激活的，对收到的REQUEST 命令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作 用范围再进入，以实行复位。
RFID防碰撞算法
RFID防碰撞算法综述【摘要】射频识别技术RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。
随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。
采用时分多路存取技术，相关的算法有ALOHA法、时隙ALOHA法、二进制搜索法、动态二进制搜索法等。
在各种算法当中，二进制树算法因为它识别应答器的确定性，成为了应用最广泛的一种，多个国际标准均对其进行了规定，这推动了防碰撞算法的发展，全文针对RFID系统二进制树防碰撞算法，进行了理论与实践方面的探讨。
【关键词】：射频识别；防碰撞算法；读写器；应答器；Abstract: RFID is a newly developed technology which communicates through the non-contact RF signal，so as to achieve objective automatic identification．Along with the development of RFID technology，how to realize Data Exchange accurately among Multiple Targets at the same time becomes the key problem of RFID technology．RFID anti-collision algorithm is the solution to the above mentioned problems．In TDMA, there are several anti-collision algorithms, such as ALOHA, Slotted ALOHA, Binary Search, Dynamic Binary Search and so on.Key Words：RFID；Anti-collision；Read／Write Devices；Transponders1、RFID技术简介自动设备识别技术是目前国际上发展很快的一项新技术，英文名称为Automatic Equipment Identification，简称AEI，它通过一些先进的技术手段，实现人们对各种设备在不同状态下的自动识别和管理。
RFID防碰撞算法摘要
RFID防碰撞算法摘要RFID防碰撞算法学习RFID中的碰撞问题主要分为两类：⼀是阅读器碰撞问题，它产⽣于同⼀个物理区域内存在多个不同的阅读器，它们以同⼀频率同时与区域内的标签通信⽽引起的冲突。
另⼀类是标签碰撞问题，如过标签同事处于阅读器的有效⼯作区内时，可能会发⽣多个标签同时发送信号的情况，这时要求阅读器能在很短的时间内识别多个标签，由于阅读器和标签通信共享⽆线信道，阅读器或标签的信号可能发⽣信道争⽤，信号互相⼲扰等问题，使阅读器不能正确识别标签。
在实际使⽤中，多标签碰撞是造成⼲扰的主要原因。
基本多地址接⼊⽅法频分多址FDMA（ Frequency Division Multiple Access）是通过使⽤不同的频段，实现信号的同时传输。
对于RFID系统来说，可以使⽤频率可调的电⼦标签。
这样完全可以防⽌碰撞，但是这需要阅读器为每个接收通路配备单独的接收通道，对阅读器的性能要求过⾼，成本过⾼，只适合在特殊场合使⽤。
空分多址SDMA（Space Division Multiple Access）是利⽤空间范围的分割实现通信的同时进⾏。
这是⼀种很古⽼的多址⽅法。
要达到SDMA的效果，要求单个阅读器作⽤范围很⼩，为此，可以把⼤量阅读器和天线覆盖⾯积并排安置在⼀个阵列中，使得单个阅读器的通信容量在相邻的区域内可重复使⽤。
当电⼦标签经过这个阵列时，与之最近的阅读器便可与之通信，由于每个阅读器的影响范围很⼩，使得相邻阅读器⼯作范围内的其他电⼦标签可以正常⼯作不受影响。
空分多址SDMA技术，由于需要安装有⾃适应定向天线的读写器，其复杂度很⾼，成本也过⾼，⽽且识别速度较慢，故此技术仅被应⽤于某些特殊的领域。
码分多址CDMA （Code Division Multiple Access）是最新发展起来的⼀种多址⽅式，它的应⽤范围很⼴，但是却不适合RFID系统。
CDMA技术基于扩频通信，即需要把要传送的信号先扩频，再编码调制，发送的是宽带信号。
RFID标签防碰撞算法及详细研究
常见RFID防碰撞算法有哪几种？比较各自的优缺点，详细论述其中一种算法的工作原理。
1.RFID简介射频识别技术(Radio Frequency Id,RFID)是一种非接触式自动识别技术，与传统的识别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处理，具有操作方便快捷、存储数据量大、保密性好、反应时间短、对环境适应性强等优点，现在已广泛应用于工业自动化，商业自动化和交通运输管理等领域，成为当前IT业研究的热点技术之一。
典型的RFID系统主要包括三个部分：电子标签(Tag)、阅读器(Reader)和数据处理o电子标签放置在被识别的对象上，是RFID系统真正的数据载体。
通常电子标签处于休眠状态，一旦进入阅读器作用范围之内就会被激活，并与阅读器进行无线射频方式的非接触式双向数据通信，以达到识别并交换数据的目的。
此外，许多阅读器还都有附加的通信接口，以便将所获得的数据传进给数据处理子系统进行进一步的数据处理。
2.系统防碰撞RFID系统工作的时候，当有2个或2个以上的电子标签同时在同—个阅读器的作用范围内向阅读器发送数据的时候就会出现信号韵干扰，这个干扰被称为碰撞(collision)，其结果将会导致该次数据传输的失败，因此必须采用适当的技术防止碰撞的产生。
从多个电子标签到—个阅读器的通信称为多路存取。
多路存取中有四种方法可以将不同的标签信号分开：空分多路法(SDMA)、频分多路法（FDMA)、对分多路法（TDMA)和码分多路法(CDMA)。
针对RFID系统低成本、较少硬件资源和数据传输速度以及数据可靠性的要求，TDMA构成了RFID系统防碰撞算法最为广泛使用的一族。
TDMA是把整个可供使用的通路容量按时间分配给多个用户的技术，可分为电子标签控制法和阅读器控制法。
电子标签控制法主要有ALOHA法，阅读器控制法有轮询法和二进制搜索法。
2.1 空分多路法(SDMA)空分多路法(Space Division Multiple Access，SDMA)是在分离的空间范围内实现多个目标识别。
RFID防碰撞
多址技术在射频识别系统工作时，通常会有一个以上的射频标签同时处在阅读器的作用范围内，这样如果有两个或两个以上的标签同时发送数据，就会导致通信上的冲突。
为了防止这些冲突的产生，射频识别系统中需要设计相应的防碰撞技术。
在通信中我们称这种技术为多址技术。
多址通信(Multiple Access Communication)是指在各个竞争用户中，共享通信信道容量的通信方式。
多址通信相当于ISO 参考模型中的数据链路层的一部分，有时直接称作媒质寻址控制(MAC)，常见的多址媒质有卫星通信信道、地面无线电信道、电缆和光缆等。
多数寻址使用的多址媒质是广播信道。
在广播信道中，信号由一个能被许多接收机接收的发射机产生。
每种多址媒质具有不同的特性，其特性影响多址协议的设计。
通常根据多址通信的性能参数来评价一个系统。
多址通信系统的主要性能参数是:平均通过量、平均分组时延和稳定性。
对于一个好的多址协议设计而言，系统的平均通过量和平均分组时延越小越好，并且在较长时间内，平均通过量和延迟性基本保持不变。
解决这些问题的方法有四种:空分多址法(SDMA-Space Division Multiple Access)、频分多址法(FDMA-Frequency Division Multiple Acess),时分多址法(TDMA-Time Division Multiple Access)和码分多址法(CDMA-Code Division Multiple Access)。
1. 空分多址法是在分离的空间范围内重新使用确定的资源(通信容量)的技术。
实现方法有两种:一种方法是使单个阅读器之间的相互作用距离明显减少，把大量的阅读器和天线的覆盖面积并排地安置在一个阵列之中，当标签经过这个阵列时与之最近的阅读器可以与之进行通信;另一种方法是在阅读器上利用一个电子控制定向天线，该天线的方向图直接对准某个标签(自适应的SDMA ，所有不同的标签可以根据它在阅读器作用范围内的角度位置区分开来)。
RFID防碰撞技术
RFID防碰撞技术RFID读写器正常情况下一个时间点只能对磁场中的一张RFID卡进行读或写操作，但是实际应用中经常有当多张卡片同时进入读写器的射频场，读写器怎么处理呢?读写器需要选出特定的一张卡片进行读或写操作，这就是标签防碰撞。
防碰撞机制是RFID技术中特有的问题。
在接触式IC卡的操作中是不存在冲突的，因为接触式智能卡的读写器有一个专门的卡座，而且一个卡座只能插一张卡片，不存在读写器同时面对两张以上卡片的问题。
常见的非接触式RFID 卡中的防冲突机制主要有以下几种：1、面向比特的防冲突机制高频的ISO14443A使用这种防冲突机制，其原理是基于卡片有一个全球唯一的序列号。
比如Mifare1卡，每张卡片有一个全球唯一的32位二进制序列号。
显而易见，卡号的每一位上不是“1”就是“0”，而且由于是全世界唯一，所以任何两张卡片的序列号总有一位的值是不一样的，也就说总存在某一位，一张卡片上是“0”，而另一张卡片上是“1”。
当两张以上卡片同时进入射频场，读写器向射频场发出卡呼叫命令，问射频场中有没有卡片。
这些卡片同时回答“有卡片”;然后读写器发送防冲突命令“把你们的卡号告诉我”，收到命令后所有卡片同时回送自己的卡号。
可能这些卡片卡号的前几位都是一样的。
比如前四位都是1010，第五位上有一张卡片是“0”而其他卡片是“1”，于是所有卡片在一起说自己的第五位卡号的时候，由于有卡片说“0”，有卡片说“1”，读写器听出来发生了冲突。
读写器检测到冲突后，对射频场中的卡片说，让卡号前四位是“1010”，第五位是“1”的卡片继续说自己的卡号，其他的卡片不要发言了。
结果第五位是“1”的卡片继续发言，可能第五位是“1”的卡片不止一张，于是在这些卡片回送卡号的过程中又发生了冲突，读写器仍然用上面的办法让冲突位是“1”的卡片继续发言，其他卡片禁止发言，最终经过多次的防冲突循环，当只剩下一张卡片的时候，就没有冲突了，最后胜出的卡片把自己完整的卡号回送给读写器，读写器发出卡选择命令，这张卡片就被选中了，而其他卡片只有等待下次卡呼叫时才能再次参与防冲突过程。
RFID的防碰撞算法-赵江波
谢 谢！
目的是为了改善QT协议的性能。 在QT协议的识别过程中，当阅读器发送长度 为k的请求字符串S给标签时，ID前缀与S匹配 的标签将会传回它的位K+1,…，N的部分ID号 给阅读器，其中N是ID号的长度。如果碰撞发 生，阅读器会发送请求位字符串S0和S1给标签。 Choi等人在文献[20]中研究表明，请求位字符 串S0和S1与前k位相同，而与最后一位不同。 基于这个发现提出了BSQTA和BSCTTA协议， 通过使用2个响应的时隙，来减少识别的时间。
赵江波
主要内容： （1）RFID系统的碰撞问题 （2）阅读器防碰撞 （3）标签防碰撞 （4）结论
在无线射频识别（RFID）系统中，阅读器通过给附有 识别标签的物品发射无线射频信号来识别物品。 RFID 系统也存在信号干扰问题，主要有 两类：
（1）阅读器碰撞 （2）标签碰撞
防碰撞协议
Reader collision
HiQ分级的控制结构由 阅读器、R-servers和Qservers组成。 当某个阅读器需要发送 信息给它的识别区域内 的标签时，它必须首先 从它的主R-server处请求 资源，即频率信道和时 隙。阅读器只有在主Rserver分配于一个时隙 内的具体频率信道之后， 才能够发送信息。
（1）Class 1 Generation 2 UHF标准是EPCglobal提 出的。整个分配频带被分成若干个信道，一个阅 读器只能使用一个信道来进行通信。 （2）阅读器和标签分开使用载波频率。即阅读器 （或标签）将只会与阅读器（或标签）发生碰撞。 （3）EPCglobal Gen2协议能够解决阅读器的碰撞。 因为大部分低成本的阅读器没有频率选择能力， 标签碰撞的问题仍然存在。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第一种方法主要根据参数E来判断未读标签的数量，其公式为：
第二种方法根据参数E和S来判断标签的数量，其公式为： 空余时隙参数选择最优的帧长度(Choosing an Optimal Frame Size)
假设有n个未读的标签，那些已经被成功读取的标签，其时隙 占用概率为1/N，应此根据公式，帧的利用率为：
1、绪论
在RFID系统中主要有两种类型的防碰撞算法：确定模型和 随机模型。确定性模型通过较少碰撞的标签数量来解决碰 撞。随机模型通常基于ALOHA协议，标签可以在任意的时 隙想读卡器发送信息，当碰撞发生时，碰撞的标签可暂停 发送它们的ID号，改在下一次读卡循环时重新发送。
There are two main types of anti-collision algorithms in RFID systems: deterministic and stochastic models. The deterministic model resolves collisions by muting subsets of tags that are involved in a collision. The stochastic model is often based on an ALOHA-like protocol in which the tags send their data at a random time period. When collisions occur, the tags that are involved in collisions retransmit their ID in the next read cycle.
要求得最大的利用率，将对上式求偏导得：
如此可以求出下一轮最佳的帧长度和时隙N。
5、仿真和结果分析
我们一开始设定帧的长度为16个时隙，观察8个空时隙的结果如图二 所示：
从图中可看出在n=10的时候，标签的概率是最大的，那么我们认为 标签的总数为10.
图三为帧利用率的仿真结果，从图中可知，当时隙N和标签个数相 当的时候，每帧的时隙利用率最高。
图一演示了防碰撞算法的执行过程：
在这个过程中，读卡器先发送一个广播命令REQ(N=4)，标 签产生随机号，在时隙2，标签1、3同时发送ID号到读卡 器，此时读卡器成功读取标签2、4，发送ACK信号以示应 答。
在第二轮读卡过程，读卡器再发送一个广播命令REQ(N=2)， 然后成功读取标签ID。
3、未读标签数量的估计( Estimate of Tag Quantity)
2、系统模型(System Model)
本文提出的防碰撞算法是基于动态ALOHA算法的，它可以动 态的改变帧长度。算法的执行过程分为三个部分：
Step 1：读卡器发送广播命令开始第一轮读卡(read cycle)，这 个广播命令包含一个表示帧大小的参数N，标签接到命令后产 生随机号，准备应答。 Step 2：标签随意的选择一个时隙，将标签产生的随机号发送 到读卡器。 Step 3：读卡器发送ACK应答信号给那些成功读取了信息的标 签，其中ACK信号还作为KILL信号，将那些已经被读取信息 的标签进入休眠状态。
在第一轮读卡过后，读卡器应用了N个时隙，根据应答信息可 知有E个空时隙(E empty slots)，S个成功时隙(S successful slots)， C个冲突时隙(C collision slots)，E+S+C=N。而我们判断还有多 少个卡没被读取就是基于以上三个参数(E, S, and C)。本文提 出了两种方法估计未读标签的数量：
第二种方法根据参数E和S来判断标签的数量，其公式为： 空余时隙参数选择最优的帧长度(Choosing an Optimal Frame Size)
假设有n个未读的标签，那些已经被成功读取的标签，其时隙 占用概率为1/N，应此根据公式，帧的利用率为：
1、绪论
在RFID系统中主要有两种类型的防碰撞算法：确定模型和 随机模型。确定性模型通过较少碰撞的标签数量来解决碰 撞。随机模型通常基于ALOHA协议，标签可以在任意的时 隙想读卡器发送信息，当碰撞发生时，碰撞的标签可暂停 发送它们的ID号，改在下一次读卡循环时重新发送。
There are two main types of anti-collision algorithms in RFID systems: deterministic and stochastic models. The deterministic model resolves collisions by muting subsets of tags that are involved in a collision. The stochastic model is often based on an ALOHA-like protocol in which the tags send their data at a random time period. When collisions occur, the tags that are involved in collisions retransmit their ID in the next read cycle.
要求得最大的利用率，将对上式求偏导得：
如此可以求出下一轮最佳的帧长度和时隙N。
5、仿真和结果分析
我们一开始设定帧的长度为16个时隙，观察8个空时隙的结果如图二 所示：
从图中可看出在n=10的时候，标签的概率是最大的，那么我们认为 标签的总数为10.
图三为帧利用率的仿真结果，从图中可知，当时隙N和标签个数相 当的时候，每帧的时隙利用率最高。
图一演示了防碰撞算法的执行过程：
在这个过程中，读卡器先发送一个广播命令REQ(N=4)，标 签产生随机号，在时隙2，标签1、3同时发送ID号到读卡 器，此时读卡器成功读取标签2、4，发送ACK信号以示应 答。
在第二轮读卡过程，读卡器再发送一个广播命令REQ(N=2)， 然后成功读取标签ID。
3、未读标签数量的估计( Estimate of Tag Quantity)
2、系统模型(System Model)
本文提出的防碰撞算法是基于动态ALOHA算法的，它可以动 态的改变帧长度。算法的执行过程分为三个部分：
Step 1：读卡器发送广播命令开始第一轮读卡(read cycle)，这 个广播命令包含一个表示帧大小的参数N，标签接到命令后产 生随机号，准备应答。 Step 2：标签随意的选择一个时隙，将标签产生的随机号发送 到读卡器。 Step 3：读卡器发送ACK应答信号给那些成功读取了信息的标 签，其中ACK信号还作为KILL信号，将那些已经被读取信息 的标签进入休眠状态。
在第一轮读卡过后，读卡器应用了N个时隙，根据应答信息可 知有E个空时隙(E empty slots)，S个成功时隙(S successful slots)， C个冲突时隙(C collision slots)，E+S+C=N。而我们判断还有多 少个卡没被读取就是基于以上三个参数(E, S, and C)。本文提 出了两种方法估计未读标签的数量：