RFID防碰撞.doc

防碰撞算法在RFID系统中，假设为单个标签完成将其ID号完整地发送给读写器所需的时间，定义系统负载G为时长内某读写器识别范围内标签的平均到达数量，吞吐量为时长内与某个读写器成功完成通信的平均标签数量。 ALOHA时隙算法中，加入频域判读，根据频域反应的标签数量决定时隙的大小，如果标签数是个位，时隙可以减小，如果大于十位，则增大标签发送时隙。在标签到达服从泊松分布的条件下，吞吐量和系统负载G具有如式(1)的关系： STSSGSSGe= (1) 其中表示时隙ALOHA算法的吞吐量。由上式，当时，而且当时，系统将处于不稳定的区域，无法满足某些情况下的实际需要。ALOHA系统中平均交换数据包量G可以用最简单的方法从一个数据包的传输持续时间计算出来式中：n = 1、2、3、是系统中的应答器的数量，rn = 0、1、2、是在观察时间T内由应答器n发送的数据包的数量。传输通路的平均吞吐率S，可由较缓的数据包量G得出，公式为：如果观察交换的数据包量G和吞吐率S的关系，那么当G = 0.5时，S的最大值为18.4%时隙ALOHA，与简单ALOHA发相比，可能出现碰撞的时间只有一半那么多。假设数据包大小一样（因传输时间一样），并且两个应答器在时间间隔内要把数据包传输给阅读器，那么在使用简单的ALOHA法时总会出现相互碰撞，由于在使用时隙ALOHA法时数据包的传输总是在同步的时隙内才开始，所以发生碰撞的时间区间缩短到，因此，可得出对时隙ALOHA法的吞吐率为：对时隙ALOHA法来说，交换数据包量在G=1时吞吐率S达到最大值为36.8%。动态帧时隙（DFSA-Dynamic Framed Slotted ALOHA）泊松分布：随机变量X可能取值为0，1，2，而各个取值的概率为：其中是常数，则称X服从参数为的泊松分布。记为EPC Gen2标准中的防碰撞算法采用帧时隙ALOHA算法，即由读写器定义一段时间长度，其中包含若干时隙。当标签收到读写器命令后，被随机分配到一个时隙应答，当一个时隙中分配到多个标签是酒产生碰撞。读写器通过Query、QueryAdjust和QueryRep等命令的组合和其中所包含的参数Q值的调整规则，是防碰撞算法的自适应性得以进一步深化和发展。EPC Gen2的防碰撞算法是在动态帧时隙算法基础上改进的时隙随机Aloha算法，该算法没有帧的概念，取而代之的是识别周期，即读写器两次发送Query指令的间隔。时隙随机算法同样需要标签随机选择响应时隙，区别在于，该算法可以在识别周期内的任何时刻更改时隙数，使未识别标签重新选择响应时隙，以实现识别时隙的自适应。由于成本要求，标签寄存器很难突破8位的限制，因此识别帧长不能大于256。不考虑捕获效应即当若干标签的应答冲突时，若一个标签离RFID读写器很近，则可能因其信号较强而覆盖其他标签的信号,则读写器附近的所有标签都服从相同的统计规律；且在同一帧中的标签在各个时隙发送数据的机会均等，则r个标签出现在某个给定时隙概率服从二项分布，记为定义系统的吞吐量，注意到，二项分布：某事件发生k次的概率为，记，即有：，k = 0,1,2,n.。注意到刚好是二项式的展开式中出现的那一项，故我们称随机变量X服从参数为n，p的二项分布。记为n 吞吐量S等于在帧的发送时间T0内成功发送的平均帧数。n 网络负载G等于在T0内总共发送的平均帧数。 GS4 吞吐率 S, 网络负载G 吞吐率 S = GP发送成功，P为发送一帧不受冲突影响的概率； 冲突危险区，Fig. 4-2 P发送成功=P连续两个到达间隔T0=(P到达间隔T0) 2 一个帧时内产生k帧的概率：Prk = ，两个帧时平均产生2G个帧，在冲突危险区内无其它帧产生的概率为：P0 = e-2G，所以 S = Ge-2G；Fig. 4-3 效率：信道利用率只有18.4%. 信道效率 冲突危险区是纯ALOHA的一半，所以P0 = e-G，S = Ge-G； 与纯ALOHA协议相比，降低了产生冲突的概率，信道利用率最高为36.8%。在有关 ALOHA 系统的文献中，一般都使用这样两个归一化的参数。它们是： （1）吞吐量S 这又称为吞吐率，它等于在帧的发送时间 TO 内成功发送的平均帧数。显然，0 S 1 ， 而 S1 是极限情况。在 S1 时，帧一个接一个地发送出去，帧与帧之间没有空隙。这种情况虽然使信道的利用最为充分，但在众多用户随机发送帧的情况下是不可能实现的。但是，可以用 S 接近于 1 的程度来衡量信道的利用率是否充分。 在稳定的情况下，在时间 TO 内到达系统的平均帧数（即输入负载）应等于吞吐量 S。 （2）网络负载（Offered load）G 从网络的角度看，G 等于在 TO 内总共发送的平均帧数。这里包括发送成功的帧和因冲突未发送成功而重发的帧。显然，G S，而只有在不发生冲突时， G 才等于 S。还应注意到， G 可以远大于 1 。 例如，G 10，表示在 TO 时间内网络共发送了 10 个帧，这当然会导致很多的冲突。 在稳定状态下，吞吐量 S 与网络负载 G 的关系为： SG P发送成功 （4-18）这里 P发送成功 是一个帧发送成功的概率，它实际上就是发送成功的帧在所发送的帧的总数中所占的比例。从 图4-8 可看出，若帧 4 要发送成功，帧 3 和帧 4 的时间间隔应大于 TO，同时帧 4 和帧 5 的时间间隔也要大于 TO。因此， P发送成功 = P 连续两个到达时间间隔 TO = ( P到达时间间隔 TO )2 （4-19）因为已假定了到达是泊松过程，所以到达时间间隔的概率密度应如附录 A 的（A-18）式那样，即 a（t）= le-lt （4-20）其中 l 是帧的平均到达率。很明显，现在 l = G / TO。于是可以求出：（4-21）将这个结果代人（4-19）式，得出一个帧发送成功的概率为： P发送成功 e2G （4-22）再代人（4-18）式，得出最后的吞吐量公式： S = G e2G （4-23）这就是Abramson于1970年首次推导出的著名公式。 当 G0.5 时，S 0.5el 0.184。这是吞吐量 S 可能达到的极大值。这点从 图4-9 的吞吐量曲线可以看得很清楚。用求极值的方法也可很容易地得出这一结论。 （4-23）式是在假设系统工作在稳定状态下推导出来的。然而 图4-9 所示的曲线在 G 值大于 0.5 呈现负的斜率，因而这段区域是不稳定的。关于这点可做如下解释。设系统工作在 G 0.5 的某一个点上（ G ，S ）。假定现在由于某种原因使网络负载 G 增大了一些。根据图中的曲线，吞吐量应下降。这表明成功发送的帧数减少而发生冲突的帧数则增加。这种情况就引起更多的重传，因而使网络负载 G 进一步增大。这样恶性循环的结果，使工作点迅速沿曲线下降，直到吞吐量下降到零为止。这时，网络负载达到很大的数值。数据帧不断地发送、冲突、重传，但是并无有用的输出。整个系统完全不能工作了。可见，在纯 ALOHA 系统中，网络负载 G 一定不能超过 0.5。 一个理想随机接入系统的吞吐量 S 的极限值是 1 。但纯 ALOHA 的吞吐量的极大值只能达到理想值的 18.4 % 。实际上为安全起见，纯 ALOHA 的吞吐量 S 不应超过 10 %。这就是为什么在纯 ALOHA 出现之后，又提出了多种改进的 ALOHA 系统。 虽然如此，在许多情况下，当需要进行突发式的交互性的数据通信时，采用纯 ALOHA 这样的方式可能既简单又便宜。当年夏威夷大学进行的实验也正是为这种环境而设计的。现在假定许多异步终端通过多点线路连到主机，线路的数据率为 4800 b/s。设每份报文有