基于ALOHA算法的防碰撞算法分析-射频识别论文.doc

【摘要】RFID是目前正快速发展的一项新技术，它通过射频信号进行非接触式的双向数据通信，从而达到自动识别的目的。随着RFID技术的发展，如何实现同时与多个目标之间的正确的数据交换，即解决RFID系统中多个读写器和应答器之间的数据碰撞，成为了限制RFID技术发展的难题，采用合理的算法来有效的解决该问题，称为RFID系统的防碰撞算法。在各种已出现的算法当中，主要分为基于ALOHA的防碰撞算法和基于二进制防碰撞的算法，本文分为三个方面，首先是基于ALOHA的防碰撞算法的理论研究比较，其次着重将现有的二进制树算法进行了归纳，汇总为基本算法、动态算法、退避式算法三类，阐述了各个算法的思路，并对其进行了性能评价；最后，在现有的三类防碰撞算法的基础上，提出了一种新的改进型二进制树算法，该算法识别速度快，执行效率高，极大的改进了识别效果。【关键词】：射频识别；防碰撞算法比较；新型二进制树算法正文：1.基于ALOHA算法的防碰撞算法分析对于RFID系统来说TDMA法在防碰撞中应用量最大。TDMA法又分为标签驱动法和阅读器驱动法，标签驱动法中主要有代表性的算法是基于ALOHA的防碰撞算法。主要有ALOHA算法、时隙ALOHA算法、动态时隙ALOHA算法、优化的帧时隙(AFSA)算法和EDFSA算法。下面对这几种算法进行分析比较。1．1纯ALOHA算法首先纯ALOHA算法是一种非常简单的时分复用算法，用于实时性不高的场合，只能用于只读标签中，这类标签只存储一些标签的序列号等数据。这种算法多采取“标签先发言”的方式，即标签一进入阅读器的阅读区域就自动向阅读器发送其自身的ID信息。并且在一个周期性的循环中将这些数据不断地发送给阅读器，数据的传输时间只是重复时间的一小部分，以致在传输之间产生相当长的间歇。各个标签的重复时间之间的差别很小，两个标签以一定的概率在不同的时间段上设置它们的数据，使数据包传送时不发生碰撞。对同一个标签来说它的发送数据帧的时间也是随机的。ALOHA算法的基本思想是在标签发送数据的过程中，若有其他标签也在发送数据，那么发生信号重叠从而导致完全碰撞或部分碰撞。图1-1给出了ALOHA算法标签发送数据部分碰撞和完全碰撞情况的示意图。标签1B标签标签1比哦啊标签2标签3接收部分碰撞完全碰撞图1-1纯ALOHA算法示意图阅读器检测接收到的信号来判断有无碰撞。一旦发生碰撞，阅读器就发送命令让标签停止发送，随机等待一段时间后再重新发送以减少碰撞，如果没有碰撞，阅读器发送一个应答信号给标签，标签从此转入休眠状态。而对于无接收功能的标签，标签收不到阅读器发送的碰撞信息或者应答信息，在检测期间一直重复地发送自己的信息，直到识别过程结束。纯ALOHA存在的一个严重问题是存在错误判决的问题，即对同一个标签，如果连续多次发生碰撞，这将导致阅读器出现错误判断，认为这个标签不在自己的作用范围。纯ALOHA存在的另一个问题是数据帧的发送过程中发生碰撞的概率很大。纯ALOHA算法的标签读取过程可以总结如下：(1)各个标签随机地在某时间点上发送信息。(2)阅读器检测收到的信息，判断是成功接收还是发生碰撞。(3)标签在发送完信息后等待随机长时间再重新发送信息。(4)若假设一帧信息的长度为To，起始时间为。则当另一帧的起始时间满足关系式(3-1)时碰撞发生，即：（1-1）为了了解纯ALOHA算法的标签读取过程，下面分析它的标签读取性能。为了分析方便首先定义如下两个参数：(1)吞吐率S：代表有效传输的实际总数据率，即单位时间内标签成功完成通信的平均次数。(2)输入负载G：表示发送的总数据率，即时间内标签平均到达次数。因此，吞吐率S可以表示为输入负载G与传送成功率的乘积，即（1-2）其中是到达的标签能成功完成通信的概率。由概率论知识可知，每秒钟发送的信息帧的数目服从泊松分布，因此t秒钟发送行个数据帧的概率为：（1-3）其中为每秒钟平均发送的总的信息帧数，此时输入负载为：（1-4）则在时间内没有发送信息的概率为:（1-5）这样，就可以得到纯ALOHA算法的吞吐率为：（1-6）当G=0．5时，吞吐率S达到最大值0．184。当G>0.5时性能急剧恶化，系统进入不稳定状态。因为必须尽量使G不要太大，这样只能改小,同时也要注意由于标签自身的问题不能检测碰撞，因此只能重发，重发次数不一定越多越好，因为重发次数多了，会使得输入负载过大，碰撞率增加，因此要选适当的退避区间。由上分析可知ALOHA算法的主要特点是各个标签发射时间不需要同步，是完全随机的，当标签的数量不多时它可以很好地工作。缺点是数据帧发送过程中碰撞发生的概率很大，碰撞周期是，而且由于受标签的费用及其大小的限制，它不能自己检测碰撞，只能通过接收阅读器的命令判断有无碰撞。当数据业务繁忙，发生碰撞的概率增多时，性能急剧下降，信道最