自适应动态时隙ALOHA防碰撞算法的研究

宋依青,高正中,盛惠兴

（1.常州工学院 计算机信息工程学院，江苏 常州 213002;2.河海大学 计算机与信息学院，江苏 常州 213022;3.江苏省输配电装备技术重点实验室，江苏 常州 213022）

无线射频识别技术RFID(Radio Frequency Identification)是利用射频信号和空间耦合(电感或电磁耦合)传输特性自动识别目标物体的技术。RFID系统由电子应答器和阅读器组成，阅读器负责发送广播并接收标签的标识信息；应答器收到广播命令后将自身标识信息发送给阅读器[1]。但在RFID系统工作时，可能会有一个以上的应答器同时处在阅读器的作用范围内。如果有两个或两个以上的应答器同时发送数据，则会出现通信冲突，产生传输数据相互干扰、发生碰撞。在RFID系统中，一般采用时分多址TDMA(Time Division Multiple Access)的方法来解决碰撞问题，这是一种把整个可供使用的通路容量按时间分配给多个用户的技术[2]。目前现有的防碰撞算法可以分为基于ALOHA机制算法和基于二进制退避机制算法。本文提出一种改进的自适应帧时隙ALOHA防碰撞算法，以进一步提高系统的识别效率。

1 关键问题解析

通常在帧时隙ALOHA防碰撞算法中，当应答器的数量变得很大时，系统效率开始降低。由数学分析可知,在一个时隙中发生碰撞的概率满足二项式分布[3,4]：

因此，在一个读周期中估计能正常传输数据的应答器为：

式中,N为帧长度，n为没有被读到的应答器，r为被读取到的应答器。

由此可以得到系统效率的计算公式[5-7]：

根据式(4)推导可知,当帧长度为N时，达到系统效率最高的应答器数量为：

当应答器数为n时，最佳帧长度为：

当n很大时，式(6)可以根据泰勒级数化简得到：

根据推导结果得到一个重要的结论:当应答器的数量和帧长度大体相当时，系统效率将达到最大化。

2 算法流程

时隙是指应答器与阅读器进行数据交互的一小段时间，如果在一个时隙中只有唯一的一个应答器与阅读器进行通信，则称为唯一时隙；如果在一个时隙中没有应答器与阅读器进行通信，则称为空时隙；如果在一个时隙中有两个或两个以上应答器与阅读器进行通信，则称为碰撞时隙。阅读器完成一轮完整的识别过程称为一个圈周期，圈周期等于唯一时隙、空时隙和碰撞时隙时间之和[8]。图1为改进的自适应帧时隙ALOHA防碰撞算法流程图。

在电子应答器进入阅读器射频作用范围内之后，阅读器先通过预设定的帧长度进行时隙分配。当判断当前

图1 改进的自适应帧时隙ALOHA防碰撞算法流程图

防碰撞算法的两个关键问题是：(1)精确地计算出与阅读器作用范围内的电子标签的数量；(2)根据电子标签的数量合理调整帧长时隙为空时隙时，即该时隙没有应答器应答则空时隙计数器C碰加1，立即结束该时隙；当判断当前时隙为碰撞时隙时，即该时隙内有多个应答器要传输数据则碰撞时隙计数器C空加1，立即结束该时隙；当判断当前时隙为唯一时隙时，即该时隙内只有一个应答器要传输数据，阅读器读取应答器内数据并存储该应答器ID号，发送一个已读信号给应答器，当下一圈周期询问到该应答器时，该应答器不再响应也不再要求发送数据给阅读器，已读信号将在应答器离开射频作用场后消失。当圈周期结束后，通过空时隙和碰撞时隙计数值估计射频作用场内的应答器数量并调整帧长度。

3 算法仿真及结果分析

在改进的自适应帧时隙ALOHA防碰撞算法仿真算法中，采用了128固定时隙、256固定时隙以及圈周期估计法与本文算法进行了横向对比，结果如图2所示。由图可以看到，128固定时隙法在应答器数量达到300时曲线折线明显，碰撞概率开始增加，系统效率下降显著；256固定时隙法效果同样不好。很明显由于圈周期估计法和本文算法都采用的是动态时隙调整所以效果明显好于固定时隙方法。但是圈周期估计法，在圈周期期间无论发生怎样的碰撞都必须执行完周期操作，系统资源浪费严重。本文算法使系统吞吐率达到了约42.5%，大大提高了系统吞吐率。度。本文提出的自适应动态时隙ALOHA防碰撞算法能够很好地兼顾以上两点，利用实时调整帧长度，使得射频作用场内的应答器数与时隙数能达到最佳匹配，来提高时隙分配效率和系统效率。

图2 改进的自适应帧时隙ALOHA防碰撞算法仿真图

[1]FINKENZELLER K.射频识别(RFID)技 术(第二版)[M].北京:电子工业出版社,2001.

[2]单承赣，单玉峰，姚磊等编著.射频识别(RFID)原理与应用[M].北京:电子工业出版社,2008.

[3]皮扬，刘长江.动态分配时隙ALOHA的抗碰撞算法[J].计算机工程，2009(4):270-272.

[4]吴伟贞.RFID系统的防冲突算法设计及其实现方法研究[D].厦门：厦门大学,2008.

[5]陈涛.基于RFID的防冲突算法的设计与实现[D].武汉：武汉理工大学,2009.

[6]王中祥.基于时隙ALOHA的RFID多标签防碰撞算法的研究与实现[D].上海：复旦大学,2009.

[7]孟淑玲.射频识别系统中防冲突算法的研究[D].天津：天津大学,2009.

[8]李瑾.无线射频识别(RFID)防碰撞算法的研究和仿真[D].北京：北京交通大学,2007.