基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法

陈 卓（信阳农林学院，河南信阳，464000）



基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法

陈 卓
（信阳农林学院，河南信阳，464000）

本文在分析传统 ALOHA 算法的基础上，提出了一种基于碰撞预检测的分组动态帧时隙 ALOHA 防碰撞算法。该算法通过分组限制响应的标签数量，并且在组内预先发送一个短暂的碰撞检测帧去检测帧内的情况，达到在阅读器与标签之间建立一个完全无碰撞信道的目的。仿真结果表明，当标签数量较大时，该算法能有效减少总数据传输量，提高识别效率。

射频识别；防碰撞算法；帧时隙；标签分组

射频识别技术（Radio Frequency Identification，RFID）是90年代开始兴起的一种自动识别技术，它利用无线射频方式在阅读器和电子标签之间进行非接触的双向数据通信，以达到信息识别的目的。当 RFID 系统运行时，常有很多处于阅读器作用范围之内的标签在同一时刻向阅读器传输信息，就不可避免地出现相互干扰的现象，称为碰撞。深入研究防碰撞算法有助于进一步提升 RFID 系统对标签的识别效率。

1　传统ALOHA 算法

目前，防碰撞算法一般采用时分多路方式（Time Division Multiple Access，TDMA），主要分为以下两类：基于二叉树的确定性算法和基于ALOHA的随机性算法。本文主要对后者进行分析。

纯 ALOHA算法是最简单最基本的一种防碰撞算法。当标签进入阅读器的识别范围内时主动向阅读器发送自身信息，阅读器只有在准确识别出一个标签后才与该标签进行通信。对于多个不同的标签来说，由于发送时间随机，不同标签的数据发送时间就可能发生冲突。这种算法容易实现，但最大吞吐率（系统效率）只有18.4%，故实际应用中很少使用。固定帧时隙 ALOHA算法（Basic Framed Slotted ALOHA，BFSA）将信道分成许多离散帧，每一帧由若干个时隙组成，大小固定不变，帧中每个时隙长度要能够完成一个标签与阅读器之间的通信。标签在每个帧内随机选择一个时隙向阅读器发送应答信息，阅读器将成功识别的标签“灭活”，不再响应后续的操作。与纯ALOHA算法相比，BFSA使冲突时间减半，将最大吞吐率提高到36.8%。但当标签数远大于时隙数时，系统耗时会大幅度增加；而当标签数远小于时隙数时，则会造成时隙浪费。动态帧时隙 ALOHA算法（Dynamic Framed Slotted ALOHA，DFSA）根据每帧中的空闲和碰撞情况动态调整帧长度，从而保证时隙数与标签数量相当，使系统获得最佳吞吐率。然而在实际应用中，由于硬件限制，帧长度不能无限增加，否则会导致系统耗时呈指数增长，识别效率急剧下降。

2　基于碰撞预检测的分组动态帧时隙ALOHA 算法

基于碰撞预检测的分组动态帧时隙ALOHA 算法（Packet Dynamic Frame Slotted ALOHA Based On Pre-detection，PDSA）是在DFSA算法的基础上提出，引入预检测和分组的环节，是一种针对大规模标签快速识别的改进型算法。

2.1算法原理及描述

本算法识别标签共分为三个阶段，分别为：标签分组、碰撞检测和信息传输。

首先估算待识别的标签数，与设定的最大帧长度Lmax=256进行对比，当待识别的标签数远大于Lmax时，将场内标签分为待命组和休眠组，规定只允许待命组标签响应且待命组标签个数定为 256个，休眠组的标签暂不响应。当待识别的标签数低于Lmax时，阅读器将不再进行分组，而只是按动态帧时隙的方法来识别标签。当阅读器限制了部分能响应阅读器查询的标签数量后，在前一帧结束和后一帧开始的中间间隔，阅读器广播分组信息及帧长，标签在接收到该信息后，设置自己的状态并生成自身的组内识别码。待识别标签的数量、帧长度与分组数有如下关系：

表1　标签数、帧长和分组数之间的关系

在分组结束后，阅读器就要对组内标签进行识别，本算法引入了碰撞预检测思想。阅读器在识别组内标签前，预先发送一个信道争用指令，以激活在其作用范围内的所有标签。标签接收指令后，需先同步时钟，然后同步进入信道争用周期。标签的随机数产生器产生一个范围为［1，N］（N为碰撞检测时隙数）的整数Nr并存储在标签寄存器中，作为时隙顺序数。进入数据传输阶段，所有标签按照各自的发送顺序，发送一个短暂检测帧，用以检测该时隙内的碰撞情况。在每个时隙中，都会有三种可能情况：碰撞时隙、空闲时隙和可读时隙。

依据碰撞检测阶段的检测结果，阅读器计算出最小的可读时隙序号，处在这个时隙内的标签就在该时隙内与阅读器进行数据交换，实现标签信息的无差错传输。标签成功识别后，阅读器就对该标签发出“灭活”指令，使其不再响应后续任何指令。阅读器向后查询次小的可读时隙序号，继续建立与标签之间的通信及操作。而那些发生碰撞或者空闲的时隙内，阅读器不再与标签通信，直接跳跃式查询。如此循环，直到阅读器作用范围内没有标签响应为止。

2.2算法性能分析

设阅读器周围有n个待识别标签，碰撞检测的时隙数为N，那么下一个时隙中出现m个标签的概率服从二项分布。

成功识别的概率为m=1时的概率P1，此时在一帧中无冲突时隙的个数Ns为：

由于在数据传输阶段是完全无碰撞的，所以系统读取标签的效率E 为：

式中，Lr为每个成功读取标签信息的时隙长度，Lc为每个碰撞检测阶段的时隙长度，将式（2）代入式（3）可得：

3　仿真

利用Matlab环境对BFSA算法、DFSA算法和PDSA算法仿真，记录三种算法在标签数从0递增到1000时，全部标签识别完成所需要消耗的时隙数和系统效率，并进行比较分析。假设一帧中最大时隙数为256，BFSA算法的固定帧长度为256，DFSA算法的帧长度动态取值为16~256。本文算法初始最小帧长度为16，且取值为20。

图1　算法所需时隙数比较

图2　算法系统效率比较

从图1中可以看出，随着标签数的增多，BFSA算法消耗的时隙数几乎呈指数增长；DFSA算法在标签数较少的时候呈一种线性关系，但超过500以后，时隙数增长趋势较快；PDSA算法在标签数小于256时，和DFSA相当，但随着标签数增大几乎保持一种线性关系，在相同标签数的情况下，PDSA算法所需的时隙数最少。从图2中可以看出，系统的识别效率在标签数大于300

以后呈下降趋势，BFSA和DFSA算法的识别效率最高能达到约36%，而PDSA算法识别效率大幅度提高，最高能达到约86%。这是因为引入了预检测和分组的环节对标签合理分组，使组内标签数目与帧长度相匹配，且充分利用了前一次检测时隙的结果，有效避免传输过程中的碰撞，从而达到一个较高的识别效率。

4　结束语

本文在分析传统 ALOHA 算法的基础上，提出了一种基于碰撞预检测的分组动态帧时隙 ALOHA 防碰撞算法。该算法通过分组的方式限制响应的标签数量，并且在组内预先发送一个短暂的碰撞检测帧去检测帧内的情况，使阅读器与标签之间建立了一个完全无碰撞的信道，有效减少总数据传输量，提高识别效率。

［1］ 李青青.RFID防碰撞算法研究［D］.南昌：南昌航空大学，2012：23-40.

［2］ 刘佳，张有光.基于时隙的RFID防碰撞算法分析［J］.电子技术应用，2007，33（5）：94-96.

［3］ 尹君，何怡刚，李兵.基于分组动态帧时隙的RFID防碰撞算法［J］.计算机工程，2009，35（20）：267-269.

［4］ 单剑峰，谢建兵，庄琴清.基于分组的动态帧时隙ALOHA防碰撞算法研究［J］.计算机技术与发展，2011，21（11）：39-45.

［5］ 江雨.物联网中的RFID标签防碰撞算法研究［D］.兰州：西北师范大学，2012：26-32.

Packet Dynamic Frame Slotted ALOHA Anti-collision Algorithm Based On Pre-detection

Chen Zhuo
（XinYang College Of Agriculture And Forestry，XinYang，464000，China）

This paper proposes a packet dynamic frame slotted ALOHA anti-collision algorithm based on Predetection by analyzing traditional ALOHA Algorithms.It can limit the number of response tags through grouping，and send a short collision-detection frame in advance to detect the in-frame situation，in order to create a collision-free channel between readers and tags.Simulation results show that，when the number of tags is large，the algorithm can effectively reduce the total amount of transferred data and inprove the identification efficiency.

RFID；anti-collision algorithm；frame slot；tag packet

陈卓（1989-），男，汉族，河南信阳人，助教，硕士研究生，研究方向为检测技术与自动化装置、电子与通信工程、传感器。