基于随机森林的链路质量预测

刘琳岚，高声荣，舒坚

（1. 南昌航空大学信息工程学院，江西 南昌 330063；2. 南昌航空大学软件学院，江西 南昌 330063）

1 引言

无线传感器网络（WSN, wireless sensor network）是一种由各种具有感知能力、计算能力和通信能力的廉价微型传感器节点通过无线通信的方式以自组织形式构成的网络[1]。由于被监测区域的复杂性和不确定性[2]，如果数据分组在低质量链路上进行传输，当节点之间进行通信时就容易丢失数据，从而引发消息重传，虽有重传机制保证数据分组的完整性，但这易导致传输效率的下降和能耗的增加。通过链路质量预测选择高质量链路进行通信，不仅可以保障数据的可靠传输，还可以降低节点的能耗，延长网络寿命。因此，降低节点能耗、提高能源利用率的关键在于提高节点间通信效率。

在通信过程中，准确的链路质量预测是保证上层协议（数据链路层的MAC协议、网络层的路由协议、网络管理层的拓扑控制等）性能的基础，对路由协议的设计者而言至关重要[3]。因此，建立一个良好的WSN链路质量预测机制，进而动态地调整路由协议，保证数据正确传输显得十分必要[4]。本文研究链路质量预测方法，为上层路由选择提供参考。

2 相关研究

无线传感器网络由于节点移动、多径衰落、噪声和干扰等因素影响导致无线链路动态变化，实时、准确的链路质量预测面临巨大挑战，吸引了国内外学者的广泛关注和深入研究。目前，主要有基于链路特性、基于概率估计理论和基于智能学习的方法。

2.1 基于链路特性的方法

此类方法主要是采用硬件参数接收信号强度指示（RSSI, received signal strength indicator）、链路质量指示（LQI, link quality indicator）、信噪比（SNR,signal to noise ratio）对链路质量进行预测。文献[5]使用一种帧计数器 meter，能够在低功率无线传感器网络中实现精确和实时的链路评估，当存在信道竞争和共存干扰时，使用分布式轻量级方法统计损坏的数据帧数，并将其应用到 4-Bit评估器中，实验结果表明，该方法能够提高链路质量评估的准确性和实时性。文献[6]为了解决输电检测系统中对上层通信网络的链路质量问题，通过分析WSN的网络特征，同时依据跳数、网络环境，在路由建立阶段选择最优下一跳节点。文献[7]提出了一种简单、准确、低成本的链路质量估计技术，适用于资源受限的WSN场景，并通过卡尔曼滤波和模糊逻辑优化了低成本下RSSI和LQI对链路质量的影响，最后在锅炉厂的实验场景中，以2种不同的速率实现流式传输，实验结果表明，该方法以较小时延为代价实现了无差错传输。文献[8]提出了一种综合性的链路质量度量方法——三角度量（Triangle），利用几何学的方法，结合分组接收率（PRR, packet reception rate）、LQI和SNR信息来衡量链路质量，能通过较少的链路探测分组快速且可靠地评估链路质量。

2.2 基于概率估计理论的方法

此类方法主要是通过发送大量的探测分组，计算接收端的分组接收率。文献[9]基于常用的对数正态路径损耗模型，将由 SNR表征的无线链路质量分解为具有不同特性的2个部分：时变非线性部分和非平稳随机部分。通过对这2个部分的分别处理，提出了一种新的链路质量估计方法——WNN-LQE，获得链路质量的置信区间。文献[10]将指数加权移动平均（EWMA, exponentially weighted moving average）数学模型应用到链路质量评估中，解决数据分组传输速率的不稳定问题，实验结果表明，通过在EWMA模型中建立相关参数，可以调节评估结果的灵敏性和稳定性，以达到特定环境下的要求。文献[11]中的 4-Bit采用期望传输次数（ETX,expected transmission count）作为指标的评估器，使用 4-Bit刻画物理层、链路层和网络层的状况，选择RSSI、LQI指标，同时考虑了链路的非对称性，实验结果表明，该评估方法可以在大幅度减少能量消耗的同时提高准确性。然而，重传数据分组数并未将信道质量与平稳性考虑在内。

2.3 基于智能学习的方法

此类方法主要采用机器学习[12]和模式匹配等智能学习方法进行建模。文献[13]采用一种基于支持向量机的多分类链路质量评估机制，选择 RSSI和LQI作为评估参数，根据PRR将链路质量分为5个等级，该模型可以使用较少数量的探测数据分组准确地估计出当前的链路质量。文献[14]使用一种基于模式匹配的方法来预测链路质量变化，将链路的SNR值存储到邻居节点，以获得SNR的时间序列，当需要对链路的未来状态进行预测时，节点使用互相关函数查找过去与当前时刻相匹配的SNR，但文中只使用了SNR来度量链路质量，并不能反映出链路的真实情况，且实验只与线性预测模型进行对比，也不能很好地反映出模型的性能。

上述研究为解决链路质量预测问题提供了相关的经验和思路。其中，基于链路特性的方法主要是使用物理层参数预测链路质量，其所需的参数获取简单，可以直接从节点中读取，但节点本身存在校准误差；基于概率估计理论的方法需要发送大量的探测分组，对链路的长期度量较为准确，但对链路的短期变化不敏感；基于智能学习的方法通过数据驱动能够挖掘出数据之间潜在的特征，是未来研究的一个趋势。

本文采用无监督聚类高斯混合模型（GMM,Gaussian mixed model）划分链路质量等级，作为链路质量的评价指标；采用零相位分量分析（ZCA,zero-phase component analysis）白化方法对数据进行预处理，去除样本间的相关性；应用随机森林分类（RFC, random forest classifier）算法评估链路质量等级；通过链路质量的时序信息，应用随机森林回归（RFR, random forest regression）算法预测下一时刻的链路质量等级。

3 链路质量等级的划分

根据不同距离下链路PRR分布的不同，将链路的通信范围划分为3个不同的区域，分别为连通区、过渡区和不连通区。传统方法中评判链路质量的优劣是通过计算PRR值，而不同的文献中划分的等级数不同，划分等级的标准也不同。本文应用 GMM无监督聚类方法，将PRR值划分为5个等级，等级划分的标准由GMM学习得到。

GMM 根据高斯概率密度函数来判断样本是否属于该高斯模型，每个高斯模型都对应着一种类别，通过样本的输入计算出概率密度，与设定好的阈值相比较，从而确定样本所属的类别。由于GMM具有多个模型，划分更为精细，适用于多类别的划分。样本集的高斯混合分布和概率密度函数分别为

其中，式(1)为高斯混合分布，该分布由k个混合高斯模型组成，jΣ为协方差矩阵，ui为第i个高斯模型均值向量，jα为混合系数，且式(2)为第j个高斯模型的概率密度函数。

似然函数的求解采用最大期望（EM, expectation maximum）算法进行迭代，具体的步骤如下。

步骤 1 初始化高斯混合分布的模型参数{(αj,

步骤2 E步：依据当前模型参数，计算PRRi各混合成分的后验概率，即

步骤4 重复步骤2和步骤3，直到每一个高斯分布的均值和方差收敛，再将样本划入相应的等级中。

4 链路质量评估

采用 ZCA白化方法去除冗余样本，采用Bootstrap重抽样方法生成不同的数据集；对数据集进行训练，生成多棵链路质量决策树，组合构成RFC模型，评估链路质量。

4.1 样本数据预处理

传感器节点收集到的物理层数据（RSSI、LOI、SNR）和链路层数据（PRR）之间存在着相关性。文献[15]指出，PRR较高的链路中，其RSSI也较高的概率为95%，RSSI与PRR是相关的；文献[16]指出，LQI与PRR具有较强的相关性，由LQI可以估计PRR值。由于样本数据各特征之间存在着相关性，若直接将样本数据用于训练会存在冗余现象，因此本节采用白化的方法降低样本数据之间的相关性，经白化处理后的数据特征之间相关性降低，且所有特征具有相同的方差。

常用的白化处理方法包括主成分分析（PCA,principal component analysis）白化和ZCA白化。PCA白化是将数据进行 PCA处理，使处理后数据的协方差矩阵为单位矩阵；ZCA白化是在PCA白化的基础上进行一个选择操作，通过将 PCA处理后的旋转矩阵左乘特征矩阵，将数据旋转回去，保留数据的所有特征，使 ZCA白化后的数据更接近原始数据，ZCA白化的具体步骤如下。

步骤1 计算数据集的协方差矩阵Σ为

其中，m为数据集样本的个数，(i)x 为物理层参数特征组成的向量。

步骤2 求出数据集的协方差矩阵Σ后，计算出协方差矩阵Σ的特征向量，按列排放组成矩阵U，即

其中，u1是最大的特征值对应的特征向量，n是特征的个数，特征值越大，代表着该特征包含的信息越多。

步骤3 将向量u组成新基，得到数据集旋转后的结果xrot为

步骤4 对数据集进行PCA白化，如式(11)所示。经 PCA白化后，数据所有特征具有相同的方差，其中，iλ是xrot协方差矩阵中对角元素的值。

步骤5 将PCA处理后的旋转矩阵左乘特征矩阵，得到ZCA白化，如式(12)所示。ZCA白化保留了数据的所有特征，使 ZCA白化后的数据更加接近原始数据。

4.2 构建评估模型

上述获得的样本空间中，应用 ZCA白化去除了样本之间的相关性，并用GMM无监督聚类算法得到了链路质量等级。由于链路质量是由多个因素共同决定的，而链路质量等级能够很好地反映出链路的好坏，通过链路质量等级的确定可以实现链路质量的评估。因此，链路质量评估是根据多个因素确定链路质量等级的，其实质就是一个多分类问题。本文利用RFC算法在分类问题上的优势，且不容易出现过拟合的特点，构建链路质量评估模型。首先通过Bootstrap重抽样方法构建不同的数据集，对每一个数据集分别训练生成链路质量决策树，然后对决策树的结果进行组合投票产生最优分类，最终得到链路质量等级。模型将链路物理层的参数组成的向量作为输入，将评估出来的链路质量等级值作为输出，输入向量 I nputi的组成为

在生成决策树的过程中，由于采用 Bootstrap重抽样方法从原始数据中抽取训练集，有63%的数据会被重复抽取，而37%的数据从未抽取，未抽取的数据叫作袋外数据（OOB, out of bag）。用OOB来检验决策树的分类效果，得到的误差为袋外数据误差（OOBE, out of bag error）[17]。袋外数据误差用于计算决策树的平均误分率，可以得到 OOB误差估计。将w棵决策树的误差估计值取平均，可以得到随机森林的泛化误差估计值，OOBE越小，随机森林算法的分类性能越好。

RFC通过构造训练集之间的差异增加分类模型间的差异性，从而提高组合模型的泛化能力。通过w轮训练，得到w棵决策树分类模型序列最后组合成一个多分类模型系统。基于RFC的评估模型，最终的输出结果采用投票方式产生。

其中，H(x)表示组合分类模型；hi(x)表示第i棵决策树分类模型；Y表示输出变量，即链路质量等级值；I(⋅)表示示性函数。

5 链路质量预测

采用RFR算法对各个实际场景构建模型，建模过程如图1所示。

图1 基于随机森林回归算法的链路质量预测过程

利用 Bootstrap方法从训练样本集Sk(k=1,… ,n)中进行w次抽样，组成w个样本子集，每个子集中的元素都不完全相同，对每个样本子集分别构建回归树，并在测试集中对模型进行预测，预测结果需要w棵回归树共同决定。

5.1 样本集的构建

RFC评估模型的输出为链路质量等级值lv = { lv1, lv2,… ,l vn}，其中，lvn为第n个时刻评估模型输出的等级值。利用滑动窗口将lv变换成样本集，其中，为预测模型的输入，yk= l vk+n-1为标签值，k为样本集的序号，n为滑动窗口的大小，窗口的滑动步长为1。

5.2 回归树生成

回归树的生成就是递归地构建二叉树的过程，对回归树采用平方误差最小化原则，利用分类与回归树（CART, classification and regression tree）中的回归树算法生成一棵回归树，共生成w棵回归树，从而形成“森林”。为了保证回归树的多样性，降低树之间的相似性，从而保证随机森林模型不容易产生过拟合问题。在回归树的构建过程中，从M个影响链路质量等级的特征中随机选取m个作为随机特征变量，用来构建回归树，m在模型中是一个超参数，对最终的结果有一定的影响。随机森林中回归树数量w也是模型的一个超参数，超参数之间的组合会对最终的预测效果产生重要的影响。在不同的实验场景中，最优组合也是不同的，根据经验值所构建的随机森林并不适合每个实验场景。因此，本文采用网格搜索算法对超参数进行优化，网格搜索算法将会遍历所有变量可能的取值，计算出每种可能性对应的目标值，从而选出变量最优的组合。回归树生成算法如算法1所示。

算法1 回归树生成算法

输入 训练数据集D

输出 回归树f(x)

步骤1 选择最优切分变量j与切分点s，求解

步骤 2 用选定的(j,s)划分区域并确定相应的输出值为

步骤3 继续对2个子区域调用步骤1和步骤2，直到子区域不能继续划分，生成叶子节点。

步骤 4 将输入空间划分为M个区域R1,R2,… ,RM，生成回归树为

5.3 预测阶段

当w棵回归树模型构建完成后，采用测试集数据对链路质量进行预测。将测试集中的6个物理层参数作为链路质量预测模型的输入，分别为得到各回归树模型预测的等级序列。基于RFR算法的预测模型最终输出的链路质量等级值是各回归树模型的均值。

其中，Yk为链路质量组合预测模型，fi(xk)为第i棵回归树预测模型。

5.4 模型评价

本文采用五折交叉验证法将样本数据集划分为5个大小相似的子集，每个子集在划分的过程中保持数据分布的一致性。在训练过程中，将4个子集的并集作为训练集，剩下的作为测试集，进行 5次训练，对5次预测的结果取均值作为最终的预测结果。采用均方误差（MSE, mean square error）评价预测模型的优劣，即

其中，lvk为模型的预测值，yk为测试集中的真实值。MSE越小，模型的预测值与真实值的差异越小，模型的性能越好。

6 实验设计与分析

在数据收集过程中，选用美国 Crossbow公司的Telos B节点，并采用如图2所示的无线传感器网络链路质量测试平台对收集到的数据进行分析，数据的预处理和模型的构建通过使用服务器上的Python平台实现。

图2 无线传感器网络链路质量测试平台

6.1 实验参数设置与数据收集

实验场景的设置主要从 WSN的常用场景出发，考虑了在真实的环境中可能会遇到的干扰，例如无线电波、障碍物、邻近信道等。因此本文设定了4个实验场景，有校园广场、校园室内走廊、校园小树林和校园停车场，具体的实验场景分别如图3～图6所示，在每个场景都部署了一个小型的星型WSN网络。其中，校园广场、校园小树林和校园停车场部署了9个节点，一个为Sink节点，8个为感知节点；校园室内走廊部署了 5个节点，一个为 Sink节点，4个为感知节点；节点间距均为10 m。校园广场、校园小树林和校园停车场按照如图7所示的星型网络部署实验节点，校园室内走廊按照如图8所示的位置部署实验节点，实验参数设置如表1所示。

图3 校园广场实验场景

图4 校园室内走廊实验场景

图5 校园小树林实验场景

图6 校园停车场实验场景

图7 星型网络部署

图8 室内走廊部署

表1 实验参数设置

6.2 实验结果分析

为了保证数据的多样性与可靠性，本文通过连续几天的测量获得不同场景下的PRR，其部分结果分别如图9～图12所示。

图9 校园广场节点1的PRR

图10 校园室内走廊节点2的PRR

图11 校园小树林4个节点的PRR

图12 校园停车场节点6的PRR

校园广场场景中比较空旷且干扰源较少，在相同的距离下链路整体表现近似，因此选用节点1描述该场景的链路质量。由图9可知，校园广场实验场景的PRR大部分都在0.8以上，链路质量处于较高水平，且稳定性较好，这是由于广场比较空旷且干扰源较少。选用节点2描述校园室内走廊场景的链路质量，由图10可知，在0～25 s链路呈现较高的波动性和突发性，之后链路趋于平稳，这是因为该时段有人员的走动对链路产生了干扰。由图 11可知，链路质量整体波动较大，节点7和节点8的PRR在0.1～0.5之间波动，链路质量处于较差水平，这是因为该场景中的主要干扰源是树木，且分布无规律，容易产生干扰，节点 1和节点 2距离 Sink节点的距离相同，但处于不同的方向，其PRR也呈现出不同的波动情况，这是由于不同方向上树木的遮挡情况不同。选用节点6描述校园停车场场景的链路质量，由图12可知，链路的PRR在0～0.9之间波动，链路有着较大的波动性和突发性，这是因为该场景中有建筑物和车辆的遮挡，且时常有车辆进出停车场，车辆上移动设备所产生的无线信号会对链路产生干扰。

为了进一步验证RFR模型的预测性能，在4种实验场景下，将RFR模型与EWMA模型、Triangle模型、支持向量回归机（SVR, support vector regression）模型和线性回归（LR, linear regression）模型进行对比，其中，EWMA和Triangle为传统学习方法，LR和SVR为常见的机器学习方法。各个场景下的预测值与真实值的对比分别如图 13～图 16所示，从图13、图14和图16可知，链路大部分时间都是处于1、2等级链路，链路质量较好，5个模型都能预测出链路的状况，但是当链路发生突变时，RFR模型能够预测出链路的突变情况，模型的准确性较好；从图15可知，此时的链路主要是在4、5等级波动，链路质量较差，但 RFR模型仍能捕捉到链路的变化，模型的准确性好，并能够适应环境的变化。

图13 校园广场的实验预测结果

图14 校园室内走廊的实验预测结果

图15 校园小树林的实验预测结果

图16 校园停车场的实验预测结果

为进一步精确对比预测模型的预测效果，计算了预测模型在不同实验场景下的MSE，其结果如表2所示。

表2 4种实验场景下的MSE

由表2可知，在4种实验场景中，EWMA模型的MSE最大，有着较大的预测误差，Triangle模型和 EWMA模型的预测效果均不如机器学习模型。校园停车场、校园室内走廊和校园广场实验场景中，RFR模型的预测性能均明显优于EWMA模型、Triangle模型、SVR模型和LR模型，其中，校园室内走廊和校园广场是较为稳定的实验场景，Triangle模型、SVR模型和LR模型均具有较高的预测准确性，但是在校园停车场实验场景中，由于车辆的运动和车载无线设备的干扰，链路出现了一定程度的波动，且呈现出突发性，导致SVR模型和LR模型的预测效果均不理想，但RFR模型却能及时地预测出链路的波动情况，有着更好的抗干扰能力。和其他场景相比，校园广场和校园室内走廊场景中 RFR模型的MSE均较小，取得了较好的预测效果，尤其是在校园广场场景中，RFR模型的 MSE最小，其预测效果优于校园室内走廊场景。这是因为在校园室内走廊中，会有人员来回走动，对链路造成干扰，导致链路不稳定。在校园小树林场景中，由于受到树木的直接遮挡和多径效应的影响，链路质量处于较差的水平，相比其他3个实验场景，各预测模型的预测误差均有增加，但RFR模型的MSE最小，有着更好的预测效果。

在不同的时间段设计了4种实验场景，通过收集不同干扰源下的链路质量测试模型性能。实验结果表明，RFR预测模型在4种场景中表现良好，均有较高的预测准确性，体现出模型拥有良好的泛化能力。

在校园广场实验场景中验证模型的预测时间，5个模型的平均预测时间如表3所示。

表3 5个模型的平均预测时间

由表3可知，EWMA模型的预测时间最小，其为传统模型，计算量最少。RFR模型通过构造多棵回归树，保证了模型的预测准确性，但并未大量增加平均预测时间，和 SVR模型处于一个量级上，就链路质量预测问题而言，增加的时间处于可接受范围。

7 结束语

本文采用GMM划分链路质量等级，用于评价链路质量；运用ZCA白化去除样本之间的冗余性，经白化处理后的数据之间相关性较低，且所有特征具有相同的方差；基于 RFC构建链路质量评估模型，使用Bootstrap重抽样方法生成不同的数据集，训练后生成多棵链路质量决策树，组合构成RFC模型；通过链路质量的时序信息，应用RFR构建预测模型，预测下一时刻的链路质量等级，采用 MSE评价预测模型的优劣。4种真实实验场景中的预测结果表明，与 EWMA模型、Triangle模型、SVR模型和LR模型相比，RFR模型具有较高的预测准确性和较良好的泛化性能。