公安巡检数据采集终端中防碰撞算法的研究与应用

贾岩岩 陆华 桂林大

【摘要】 主要阐述了RFID系统中电子标签的防碰撞问题，分析了常用的防碰撞技术ALOHA算法。结合公安巡检数据采集终端的实际情况，给出了改进型ALOHA算法的实现过程，该算法简单有效，实用性强，提高了系统数据的吞吐率。

【关键词】 RFID标签 防碰撞 ALOHA算法 改进型一、引言

当前社会发展与经济建设进入全面提速阶段，国民的生活水平得到进一步的提高，社会公共安全越来越收到广泛的关注，尤其是近几年来我国发生的暴力恐怖事件， 因此提高对巡警和巡防队员的有效管理，对于降低犯罪，保障公共安全越来越重要。

无线射频识别技术[1] （Radio Frequency Identification， RFID），或称射频识别技术。作为一种快速、准确、实时采集与处理信息的高新技术[2]，RFID被列为本世纪十大重要技术之一[3]，其在公安巡检领域也得到了广泛的应用。无线电技术中，多路存取的问题是众所周知的。如果有多个RFID标签接收到电磁波并同时发送反馈信息，则标签阅读器接收到的信号就会相互干扰，发生数据碰撞[4]。因此，如何解决数据碰撞问题成为了RFID系统的关键技术之一[5]。

目前，应用于射频识别系统中的防碰撞技术主要有空分多址（SDMA）、频分多址（FDMA）、码分多址（CDMA）和时分多址（TDMA）等。由于时分多址法的成本较低，易于实现，所以是目前最为常用的防碰撞技术。本文主要描述基于TDMA的RFID ALOHA随机延时防碰撞算法。

二、ALOHA防碰撞算法

ALOHA算法是一种不确定性算法，其检测时间和延迟时间都是随机分布的，主要应用于主动式标签，包括纯ALOHA算法、时隙ALOHA算法和自适应时隙ALOHA算法。它的基本原理为，当信息源标签发送的数据包发生碰撞时，标签就会产生一个随机延时，然后再次尝试数据包的发送，重复此操作，直到发送成功。

2.1纯ALOHA算法

纯ALOHA算法是一种最简单最基本的防碰撞算法，它不具有碰撞检测及恢复机制，只是在概率上保证标签发送的数据被阅读器准确接收。它采用的是“标签先发言”（TTF， Tag Talk First）方式。即当标签处于阅读器的作用范围时，标签就会主动发送自身的信息数据包，当多个标签的数据同时到达阅读器就会造成数据帧的破坏，各个标签将随机延长一段时间后进行重新发送。标签1产生了数据并立即发送，接着标签3也开始发送数据，这样标签1和标签3就发生了部分碰撞，而如果两个标签恰巧在同一时刻发送数据，就将发送完全碰撞。

该算法的优点是，无需同步，各标签发送时间完全随机，比较容易实现，尤其是当标签较少时能够进行很好的工作，但缺点是延时时间选择困难，如果设置过大，则阅读器的识别时间就会变长，若设置过小，系统发生重复碰撞的几率就会大增，需要退避的次数也会过多。

性能分析：公共信道上在单位时间T内平均发送的数据帧数G和传输通路的吞吐率S的计算公式见式（1）和式（2）。

（1）

（2）

式中，n为系统中标签的数量，rn是T时间内由标签n发送的数据帧数。

由以上公式可以得出S的极大值，即当G=0.5时，吞吐率S的最大值Smax=1/2e（约为0.184），说明纯ALOHA的最大信道利用率是18.4%。

2.2时隙ALOHA算法

时隙ALOHA算法和纯ALOHA算法的区别在于，将时间分割成了一个个等长离散的时隙，时隙Tslot等于或者略大于一个数据包的长度T0，并且只有当时隙开始时每个标签才被允许发送数据帧，这样一来，一旦发生了数据碰撞，就是完全碰撞，不会发生部分碰撞的情况，见图2。

时隙ALOHA算法中，S与G的关系为：

S=Ge-G

2.3动态时隙ALOHA算法

在时隙ALOHA算法中，时间轴被划分的时隙数N是固定不变的，且容易实现，但是在公安巡检数据采集终端的实际应用环境中，进入阅读器作用范围的电子标签的数量是动态改变的，阅读器不能主动根据电子标签的数量调整时隙数的大小，这将导致公安巡检数据采集终端性能不稳，甚至造成电子标签的信息漏读。动态时隙ALOHA算法能够根据标签发生碰撞的数量动态地改变时隙数N的大小。当时隙数小于标签数量时，阅读器根据发生碰撞的标签数适当增加时隙数，反之，当时隙数大于标签数量时，阅读器能适当地减少数据帧的时隙数。动态ALOHA算法能保证数据帧的时隙数与标签数量基本一致，使系统效率达到最佳。

2.4 改进型ALOHA算法

RFID系统中的标签只能通过接收阅读器的指令来判断是否发生了数据碰撞，导致系统信道利用率很低。若标签能够自主判断是否会发生数据碰撞，再选择发送数据，就可以大大降低数据发生碰撞的概率，进而使信道利用率增加。改进型ALOHA算法是在时隙ALOHA算法的基础上增加了数据碰撞避免机制[6]，各标签首先进行标签同步，当信道被其他标签占用时继续监听，直到信道空闲将自身数据立即发送出去，若发生数据碰撞，则随机延迟一段时隙后重新监听。由于改进型ALOHA算法采用了实时信道监听，这就要求标签具有主动发送信息的能力，所以改进型ALOHA算法仅适用于有源电子标签的防碰撞。公安巡检数据采集终端采用的正是有源电子标签，有源电子标签增加了阅读器的读取距离，不仅缩短了阅读器的读取时间，而且提高了读取效率[7]。

三、公安巡检数据采集终端中防碰撞算法的实现

公安巡检数据采集终端中阅读器与标签通信运用握手协议进行数据交换[8]，标签进入阅读器搜索范围时被激活，当标签监听到信道空闲时发送自身数据，发送成功后进行灭活处理。

具体实现步骤如下：

（1）阅读器发送广播信息帧；

（2）处于阅读器作用范围内的所有标签将接收广播信息帧，未被识别的标签（即处于休眠状态）自主唤醒，同时监听信道状态，等待发送自身数据；

（3）当标签监听到信道空闲时，将自身数据发送出去，并继续侦听阅读器返回的数据帧；

（4）若标签成功占用了信道，阅读器接收后会返回应答，标签收到应答后进入休眠模式（即灭活）。若未能成功占用信道，标签即随机延时一段时隙，继续监听信道等待重新发送。

（5）阅读器再次发送广播信息进行下一次通信。

四、结语

改进的ALOHA数据防碰撞算法，即在标签发送数据之前先监听信道是否被占用，再决定是否发送数据。仿真结果表明：改进型ALOHA算法优于动态ALOHA和时隙ALOHA算法，最大数据吞吐率达到53%。在公安巡检数据采集终端的实际应用中，改进型ALOHA算法完全能够满足要求，且易于实现，成本较低，达到了比较好的效果。

陈业龙（1973-），男，本科，工程师，主要研究方向：通信技术及物联网应用开发

贾岩岩（1987-），通信作者，男，硕士研究生，助理工程师，主要研究方向：无线通信系统中的信号处理技术

陆华（1985-），男，硕士研究生，助理工程师，主要研究方向：信号处理和传输技术