基于超限快速决策树的无线多媒体传感器网络路由优化方法

刘 松

(安徽商贸职业技术学院电子商务学院,芜湖 241000)

无线多媒体传感器网络(WMSNs)可有效感知视频图像等多媒体信息,具有精度高、数据传输量大、可靠性高等优势[1],普遍应用于环境检测、交通监控等领域[2]。由于WMSNs在输出过程中存在网络时延、时延抖动与能量失衡的问题[3],导致多媒体数据流传输质量下降。因此,研究一种优质的WMSNs路由优化方法具有重要意义。相关文献对此进行了很多探讨,并取得了一定成果。文献[4]提出基于改进蚁群算法的无线传感器网络路由方法,通过伪随机比例规则优化状态转移函数改进蚁群算法,优化路由的角度信息的相关参数,并计算相应距离,避免路由的无关路径,以及节点能量的浪费,最后通过更新信息素优化路由路径。该方法可以提升节点的均衡程度,但节点能量消耗较多,无法有效降低路由能耗,存在一定局限性。文献[5]提出一种能量与路径约束的无线传感网络路由优化,针对网络路由中单一路径问题,通过均衡网络负载均衡节点和能源因素,构建高速的传输路径,并根据能量因子保证能量的合理分布,完成优化研究。该方法降低了节点路由中所需要的能耗,但路由路径单一,并未全面解决该问题,存在优化效果较差的问题。针对上述方法中存在路径单一、能耗较高的问题,本文提出基于超限快速决策树的无线多媒体传感器网络路由优化方法,以满足WMSNs路由优化需求,确定关键参数,以关键变量为超限快速学习机输入值,利用学习机训练输出路由优化结果,完成网络路由优化。

1 WMSNs路由优化方法

1.1 WMSNs路由模型

为实现无线多媒体传感器网络路由优化,首先构建路由模型,确定路由变量的参数。模型构建时,将全部节点任意均匀分布在X×Y区域内。其中,不同节点的信号覆盖以r为半径的圆形区域范围内。各节点有且仅有一个编号[6],同时,不同节点可分别经由GPS等定位技术和信息交换技术确定自身所处区域坐标和邻居节点、sink节点的区域坐标。通过数学形式化语言表示WMSNs路由,表示为G(V,H,W)

其中,式(1)为设置节点的有限集合,式(2)为目标链路组合,式(3)代表所有节点的属性值,v i和v m分别表示编号为i的节点和sink节点,,代表sink节点,v i和v j在处于相互传输范围内,H ＝V×V,各链路(vi,v j) ∈H均包含一组属性值。δ代表链路标记,δtd,δdj,δlp,δer,δtr分别代表td、dJ、lp、er、tr属性下的链路。

若(xi,y i) 和(xj,y j) 分别表示节点v i和v j的区域坐标,d ij为两者间的距离

在G(V,H,W) 内,利用式(5)描述可获取节点v i的邻居节点集

其中,Z i表示邻居节点集,r代表以避免数据包向sink节点传输过程产生的循环路径[7],此时以F i表示节点v i的前向邻居节点集

其中,d js表示v j同sink节点间的距离,d is表示v i同sink节点间的距离。若v j为v i的前向邻居节点,即可通过l′ij表示两者间的链路,即同意由v i向v j搜索路径,但拒绝由v j向v i搜索路径。以N(V′,H′,W′)表示G(V,H,W) 的子图,。N(V′,H′,W′) 即为WMSNs路由模型。

1.2 基于超限快速决策树的路由优化

针对构建的WMSNs路由模型,采用超限快速决策树对其参数进行有效的确定和优化。

1.2.1 基于决策树的特征变量选择 作为多棵决策树集成的学习算法,随机森林算法既可实现目标分类,也可用于确定变量关键度[8]。随机森林算法中,基于外带网络数据分类的变量分析算法使用最为普遍,该算法逐一对网络数据内的各变量增添相应噪声[9],当经过决策树的网络数据准确度下降后,需要借助均值确定变量关键度。本文确定的特征变量中,影响无线多媒体传感器网络路由的参数包括:网络传输带宽、网络延迟、延迟抖动以及丢包率,采用超限快速决策树选择关键参数。

(1)生成随机森林。针对K个初始样本,利用Bootstrap抽样技术任意抽取K′个样本。基于K′个样本构建决策树c k(k＝1,2,…,p),剩余的K－K′个样本构建袋外数据,oob代表袋外数据属性,k表示数据数量。在决策树各节点处抽取WMSNs路由质量初始变量集的m个变量,计算不同变量内的信息量,由m个变量内确定一个分类性能最优的变量实施节点分裂。

各决策树自然生长时省略剪枝过程[10],重复以上过程p次,由此得到包含p棵决策树的随机森林为

(2)针对随机森林内的各决策树s k,利用实施分类,并确定WMSNs路由样本的分类正确率R k。

(3)以λl表示训练基中各初始变量,逐一将随机噪声引入,λl,将新获取的袋外数据表示为。利用不同s k对实施分类处理,同时确定WMSNs路由样本的分类正确率。

(4)确定λl的关键度V I

通过随机森林中递归特征消除算法确定变量关键度,同时以此为依据进行排序,由此利用递归特征消除算法确定关键变量[11]。随机森林—递归特征消除算法流程如图1所示。

图1 随机森林递归特征消除算法流程

在随机森林—递归特征消除中,首先设置初始变量训练数据集合

其中,ζ1,ζ2,…,ζn代表初始变量训练数据集合中的组成因子。

确定训练集合中变量的关键度

其中,v代表训练集合中变量的关键度系数。

根据得到的确定的变量关键度,确定其是否符合终止条件,得到更新后的变量即为训练的样本

其中,t c代表更新的时间窗,g代表更新过程中的比例因子。

基于初始变量训练数据集,通过随机森林确定变量关键度且进行排序;逐次清除关键度最小变量,同时通过剩余变量再次测试随机森林的分类准确性。依次迭代,确定各次分类准确率值,此时全部变量序列搜索完成。由此获取全部关键度排序与对应不同变量数量的分类准确率。

通过随机森林递归特征消除算法在WMSNs路由质量变量内确定关键变量,既可降低输入数据的维数,又可提升分类结果准确率。WMSNs路由对传输速率、可靠性以及能量均衡等多项变量参数较为敏感,利用决策树算法能够在不同路由变量中选取出关键变量——传输速率、能量均衡,以其为优化目标[12],构建WMSNs路由多目标优化函数。

(1)传输速率。节点v i在香农定理标准下,以上限传输速率向其前向邻居v j传输数据包,传输速率的主要影响因素为信噪比SNR。以SNRij表示l′ij的SNR 值,得

其中,w ij和d ij分别表示同v i、v j具有相关性的常数和两者间的距离长度,ξ、χi和π分别表示天线增益、v i的发射信号功率和网络内噪声信号功率。以表示l′ij的信道传输速率上限,计算过程为

其中,表示l′ij的带宽,Əij表示信道传输速率的固定值。

由整体网络角度分析,路径Pkm的传输速率上限受l′ij传输速率下限直接影响,由此得到链路容量的最优化目标函数maxC

根据式(14)得到路径传输速率的最优化目标函数maxf i(x)

(2)能量均衡。网络路由中节点运动时需要的能量是实现优化的重要部分。因此,本文对其中的节点能量进行均衡。节点能量消耗[13]包括发射端与接收端运行时的耗损。以防止部分节点能量消耗过高造成WMSNs能量缺失,在数据包传输过程中需充分降低并均衡节点能耗。发射端与接收端能量消耗计算过程

其中,γ和φ分别表示数据包长度和1 bit数据包传输所消耗的能量,表示发射端能量消耗,表示接收端能量消耗,ρ表示能量确实比例。

得到发射端的能耗同d ij间成正比例相关[14]。基于降低节点能耗实现节点能耗均衡的角度分析,节点路由区域中存在能量浪费的问题,此时,构建能量均衡的最优化目标函数为

基于上述描述,能够得到多目标路由优化函数

根据上述确定的路由关键参数变量,将关键变量作为超限快速学习机的输入,通过超限快速学习机训练,得到WMSNs路由优化结果。在无线多媒体传感器网络路由优化中,确定关键参数之后通过超限快速学习机训练,得到的最终的优化输出结果。

1.2.2 超限快速学习机 作为单隐层前馈神经网络的求解算法,超限快速学习机以学习效率快、参数设置简单等优势,在各领域中普遍使用[15-16]。本文将路由关键参数输入超限快速学习机中,以实现路由的优化。

若学习机内包含N个随机样本(Xi,t i),其中X i＝[X i1,X i2,…,X in]T＝R n,t i＝t[i1,t i2,…,t im]T＝R m。利用式(13)表示包含L个隐层节点的单隐层神经网络为

其中,βi和λ x() 分别表示输出权重和集合函数,W i和b i分别表示输入权重和第i个隐层的偏置。单隐层神经网络学习以输出误差最低为学习目标

其中,U和T分别表示隐层接待输出的期望输出。

在超限学习机内,若W i与b i被随机确定,即得到了唯一路由值,确定输出权重,完成路由优化。

2 实验分析

2.1 实验方案

为验证本文构建优化方法的实际应用效果,实验中设置WMSNs路由节点数据,其节点部署如图2所示。传感器节点均匀分布式在150 m×150 m 区域内,节点数量为400个。其中,源节点数量为2个,处于网络边缘区域(矩形区域),sink节点数量为2个,处于网络中心区域(三角形区域)。在确定若干条路径后,模拟传输10 000个数据。实验从变量选择与能量消耗方面验证本文方法的性能。

图2 WMSNs节点部署

2.2 实验结果分析

2.2.1 路由优化测试结果分析 实验中,本文方法由WMSNs内路由初始变量内确定关键变量。每次清除关键度排序,在最后一位变量后需再次确定分类准确性。分类准确性同变量数量间的相关性如图3所示。可知,在变量数量为9的条件下,即为初始变量集。在非关键变量被逐一清除后,分类准确率在整体上表现为逐渐上升的趋势;变量数量降至2～3个时,得到的准确率最高,达到98%以上。变量数量继续下降,达到1个时,分类准确率显著下降,降至93%以下,这是由于变量的过度清除导致关键变量被删除。由此说明本文方法具有较高的分类精度,能够得到合适的科学变量数量,提升最终路由优化效果。

图3 分类准确率与变量数量间的相关性分析

采用本文方法优化网络路由,得到源节点同sink节点之间的最优路由,结果如图4所示。本文方法可确保源节点存在一个以上目标节点,且能够得到最优数据传输路径,确保实验对象数据传输速率最优,且达到整体能量消耗最低。

图4 路由优化结果

2.2.2 能量测试 为进一步验证本文方法的应用性能,对比文献[4]中基于改进蚁群算法的无线传感器网络路由方法和文献[5]中基于能量与路径约束的路由优化方法,路由优化结果的能量消耗如图5所示。

图5 能量消耗对比

在源节点传输的数据包数量较少(低于300)的条件下,三种方法的在路由优化过程中的能量消耗差异较小,均低于150 J。随着源节点传输数据包数量的提升,三种方法能量消耗逐渐提升,文献[4]的方法在传输数据包数量低于600时,能量消耗低于本文方法,文献[5]的路由优化方法在数据包数量高于600后,能量消耗显著提升。可知,本文方法的能量消耗最低。

WMSNs内节点能耗均衡程度可通过节点剩余能量方差描述,采用三种方法优化实验对象内路由节点的剩余能量,所得结果见表1。在实验对象内源节点与sink节点数量逐渐提升的条件下,三种方法路由优化时实验对象节点剩余能量方差均呈现逐渐提升趋势,但采用本文方法优化条件下,实验对象节点剩余能量的方差明显偏小,这表示本文方法在路由优化过程中的能耗更加均衡。

表1 剩余能量方差对比

3 结论

本文提出基于超限快速决策树的无线多媒体传感器网络路由优化方法,通过确定传感器网络路由中的参数,借助决策树算法确定路由中关键影响参数,将关键参数作为最终优化值输入超限快速学习机,完成研究目的。实验验证了本文方法所选的关键参数能够完成路由优化,有效提升了数据传输速率,且降低了能量消耗。本文设计方法虽然在现阶段能够有效降低无线多媒体传感器网络路由的能耗,但在复杂的网络传输过程中,其参数始终变化,如何使优化的关键参数保持稳定是未来研究中的重点问题。