快速自适应多叉树防碰撞算法的研究

侯加兵，吕家云，霍文强

（巢湖学院，安徽 合肥 238000）

1 概述

随着物联网技术的快速发展，无线射频技术（Radio Frequency Identification，RFID）[1]因具有非接触性、快速方便、可靠性等特点，被公认为物联网识别的关键技术，已广泛应用于各个领域.中心机房作为信息基础设施的核心区域，为信息化的安全、可靠、稳定的运行保驾护航，因此，针对中心机房关键设备的全方位实时监测显得尤为重要，RFID技术因其自身的特点可满足需求.RFID通常有阅读器和标签组成，在机房环境下，因需对多个设备进行监测，就出现RFID阅读器同时读取多个标签，这样会出现信号碰撞现象，如何实现RFID对机房关键设备实时监测，既要阅读器同时读取多个标签又要保证数据实时传输，对RFID的防碰撞算法提出更高的要求.

传统的防碰撞算法主要分为两类，一类是基于ALOHA的不确定算法，主要代表算法有时隙ALOHA、动态时隙ALOHA和帧时隙ALOHA算法等[2]；另一类是基于树的确定算法，主要代表算法有二叉树、动态叉树、混合查询树等[3].ALOHA算法在多标签的情况下，易出现“标签饥饿”现象，而树的算法则会产生很长的识别时延，研究人员通过研究分别提出了自适应多叉树算法[4][5]、无空闲时隙的动态多叉树查询树RFID防碰撞算法[6]和后位退锁式RFID自适应多叉树防碰撞算法[7]，这些算法快速识别标签，减少标签方面得到很大的改进，但还不能满足机房关键设备实时监测数据的高速、安全、稳定性能要求.

为满足机房实时监测的要求，重点对标签防碰撞算法进行研究，本文在自适应多叉树算法基础上，提出一种快速自适应多叉树（Fast Adaptive Multi-Tree Search，FAMS）防碰撞算法.该算法在防碰撞之前先对标签数进行估计，根据实际环境进行多叉树快速处理.

2 快速自适应多叉树防碰撞算法原理

有源标签显著地提高了RFID系统通信距离，在一定范围内阅读器与多个待识别标签同时通信时，很有可能就会产生标签碰撞.在中心机房环境的实际应用中，需要RFID系统对中心机房的关键设备进行全天候监控和管理，这就对RFID提出了更高的响应需求[8].

根据标签特征，标签的长度一般是固定的，每个位（BIT）出现概率基本相同，标签越多出现的碰撞的概率越大，以快速先验作为标签估计的条件，可以快速避免标签碰撞，提高RFID安全性能.具体算法描述如下：

定义1标签参数为Sum（t），若将一天分成若干个t时段，该时间段的标签数量为Sum（t），并对该标签数据保存作为初始搜索依据，在完成所有标签识别之后，将根据识别的标签数I（t）进行更新，即：

其中，Sum’（t）为更新后的标签数量；β∈[0，1]为更新率，其值的大小根据RFID系统标签访问的规律性来确定.一般标签数量变化不大时，β就越小，相反，则越大.

定义2碰撞因子U=NC/N，U∈[0，1]，Nc表示碰撞比特数，N表示比特数.其值越大，说明碰撞标签越多，反之，则碰撞标签越少.根据碰撞因子，可以估计在时隙X中，发生碰撞的标签数C（x）满足：

由于标签长度在一定的范围内，若碰撞标签数量较多时，U=1，C(x)无解，则无法进行标签估计，可采用标签随机分布特性进行标签估计.

定义3根据多叉树搜索公式得到[9][10]，若时隙为x，搜索深度为H（x），那么时隙节点数则为2H(X)，第m时隙内的标签数为：

依据该算法，在初始状态下，无法估计标签数量时，可通过Sum(t)进行标签估计并确定多叉树的叉数.在执行搜索算法时，若是碰撞时隙，利用碰撞因子U进行标签估计，若标签因子过大（U=1），则通过标签的随机分布特性进行标签估计，完成对标签的搜索和识别.

3 算法性能分析

在机房环境通过RFID技术对关键设备的监控和管理，对于RFID技术本身来说主要是要可靠地保证监测数据稳定性传输[11]，本文主要通过计算总时隙数和吞吐率，对FAMS算法进行分析.

假设系统内有Nc个待识别的标签，此时时段参考标签数为Sum(t)，标签估计准确率为

为使RFID系统具有最大的吞吐率，搜索叉数L应与标签数Nc一致.

4 仿真实验与分析

下面通过Matlab验证本算法的模拟效果，标签数量随机产生，长度为128bit，仿真结果取相同条件下100次实验的平均值，见图1、图2.

图1 时隙数

图2 吞吐率

通过仿真数据显示，标签总数在100以内时，时隙数较小，吞吐率较大，标签总数超过100以后，则时隙数快速增大，吞吐率也出现明显下降，实验结论得出在标签总数100以内，本算法性能较好.中心机房的关键设备一般指核心交换机、路由设备、UPS、精密空调、重要服务器和存储设备，数量基本上不超过30台，本算法很好地满足机房环境监测需求.

5 结束语

本文利用机房标签读写频率和标签数量相对固定的环境下，采用标签快速搜索技术，结合标签分布的先验知识和碰撞规律，提出一种基于快速自适应的多叉树防碰撞算法.该算法通过快速生成树算法准确地估计标签数量，能够快速、方便、准确地防标签碰撞，使得RFID阅读器能够稳定、高效地搜索和识别标签，能够满足RFID技术对机房关键设备全生期周期的需要[12].文中通过理论分析、仿真验证，证明采用FASM算法的RFID适应于智能机房场景的需要.