基于能量感知决策树和增强boosting的网络数据聚合模型

杜玉香, 陈 欣

(1.广州南洋理工职业学院 智能工程学院, 广东 广州 510925; 2.遵义师范学院 信息工程学院, 贵州 遵义 563006)

0 引言

无线传感器网络[1](WSN)由多个小型传感器节点组成,可对物理环境信息进行监测和采集,并在基站处管理采集到的数据．其优点是可靠性较强,数据采集灵活且检测精度高．广泛应用于环境监测、灾难管理、安全、军事和医疗等领域．但传感器节点在电量和处理能力方面存在限制,电量约束方面更容易造成WSN的故障[2-3]．由于传感器节点的不完美性,需要密集放置传感器节点,以提高采集数据的质量．但节点密度较高会造成很多节点感测到相同的数据,产生冗余．因此,如何去除冗余,提高WSN数据聚合是一个亟待解决的问题．学者们对此也进行了大量的研究．如Singh[4]通过基于链的数据采集和传输处理,采用自然启发优化(NIO)以最小化WSN中的传输成本和开销．Huthiafa等人[5]提出了多移动代理迭代规划(SMIP)方法,以改善数据采集性能,最大限度降低能量消耗．陈宏滨等人[6]提出一种基于能量平衡的动态分簇算法,该方法考虑了节点基于距离与剩余能量的竞争机制,并将各簇内节点数据依据竞争进行分级,以提高无线传感器网络在数据采集过程中节点能耗的均衡性．陈琪等人[7]提出了一种基于节点分级的混合多跳数据采集(HMDC)算法,基于数据量将节点划分成簇,簇内采用分级思想进行多跳传输．刘持超等人[8]提出了一种基于网状无线网络的高炉炉缸温度场无线数据采集系统．

在设计WSN数据采集方法时,应考虑分布式系统架构和通过无线连接的动态接入[9-10]．以往方法在数据聚合过程中存在能耗较高、时间消耗过久、数据聚合准确度较低和延迟较高等问题．在对传感器节点进行连续数据聚合的过程中,节点的能量水平会下降．为此,本文提出了一种能量高效的数据聚合方案,将节点分为高能量节点和低能量节点,低能量传感器节点将数据发送至高能量传感器节点,实现能量感知的数据聚合．本文主要工作创新总结如下:

1) 提出了使用决策树桩和增强boosting的概念来执行节点分类的模型，使用决策树桩作为模型中的弱分类器,将传感器节点分为高能量节点或低能量节点；

2) 为降低训练误差,提高节点分类性能,提出的模型中应用了增强boosting提升分类,对弱分类器的结果进行合并,并计算训练误差,因此,提供了误差最小化的强分类结果；

3) 为延长WSN的工作寿命,低能量传感器节点将数据包发送至邻近的高能量传感器节点,汇聚节点采集来自所有高能量传感器节点的数据,由此提高了数据聚合性能,最大限度降低延迟．

1 整体模型

1.1 传感器节点与簇头

(1)

(a) 一般系统模型 (b) 簇头信息 图1 模型与簇头

1.2 模型方法概述

本文方法的整体流程如图2所示,该模型将传感器节点随机分布在无线网络中,然后,计算WSN中每个传感器节点的剩余能量．模型基于弱分类器的结果执行增强boosting来提升分类效果,使用决策树桩作为弱分类器．决策树桩通过阈值将传感器节点分为高能量节点和低能量节点．接着,通过增强boosting对所有弱分类器的结果进行合并,从而以更高的准确率将节点分为高能量节点或低能量节点．在分类操作结束后,WSN中的低能量节点将聚合数据发送至高能量节点．最后,汇聚节点采集来自高能量传感器的数据,并将聚合数据发送至基站．

图2 整体流程图

在提出的模型中,利用增强boosting提升分类的模型如图3所示,其作用是将弱决策树桩转变为强分类器,使WSN中节点分类的误差率最小化[11]．具体来说,增强boosting是一种集成方法,通过合并n个弱决策树桩的结果来提高节点分类准确度．具体方法：首先,取一定数量的传感器节点作为输入．然后,计算传感器节点的剩余能量,为每个输入传感器节点生成弱决策树桩结果,这些弱分类器通过增强boosting集成为一个强分类器．最终,投票分类的形式获得高能量节点和低能量节点．

图3 本文提升分类的流程图

一般adaboost未排序的特征很多,生成的弱假设也很多,其弱假设的选择一直棘手问题,与一般adaboost集成不一样,本文的增强boosting只选择一个排序特征,因此生成的弱假设数量只有1个,明显减小了弱假设的搜索空间,其示意图如图4所示．这样处理的优点是很少情况下或者不需要进行弱假设选择,从而加速了整个模型的弱学习过程,可以在更少的轮次获得更佳结果,从而得到更好的节点分类结果．

图4 一般adaboost与本文增强boosting示意图

2 传感器节点分类与数据聚合

2.1 传感器节点分类

弱决策树桩为单级决策树,包含1棵决策树,以及连接到多个终端节点的根节点,基于剩余能量为每个输入传感器节点生成分类结果[12]．假设WSN中所有传感器节点在初始放置时的能量水平相等,在提出的模型中,将每个传感器节点的能量计算为功率和时间的乘积,即

ASi=[Power*Time]

(2)

式中ASi为传感器节点的能量水平．由于节点的传感特性,其能量水平会逐渐降低,传感器节点的剩余能量可估计为

RASi=[Atot-Acon]

(3)

式中RASi表示传感器节点的剩余能量,Atot表示节点的总能量,Acon表示节点已消耗的能量．

根据计算出的剩余能量水平,在所提模型中使用弱决策树桩对传感器节点进行分类．首先,弱决策树桩先定义剩余能量水平的阈值．然后,将每个传感器节点的剩余能量水平与阈值相比,若节点的剩余能量水平RASi大于阈值δ,则将传感器节点Si分类为高能量节点．否则,将传感器节点Si分类为低能量节点．由此,弱决策树桩分类器结果[13]可计算为

(4)

式中LighEN为高能量节点,LowEN为低能量节点,RASi为传感器节点剩余能量水平,δ为阈值．

弱决策树桩将所有输入传感器节点分入不同类别．然而,弱决策树桩中包含一些训练误差,会降低节点分类准确度．为了提高准确度,本文在所提模型中采用了增强boosting模型．增强boosting模型将n个弱决策树桩结果合并为强分类器结果,

(5)

式中β表示强分类器输出,wi表示所有弱决策树桩分类器的输出．其后,增强boosting模型向所有弱决策树桩分类器结果分配相似权重,

(6)

式中bt表示向弱输出分配的权值．通过增强boosting模型确定的决策树桩的训练误差为

ter=(yi-wi)2

(7)

式中ter表示训练误差,yi表示弱决策树桩分类器的实际结果．基于评估出的训练误差,对增强boosting模型中的每个弱决策树桩结果的权值进行更新．若弱决策树桩对传感器节点进行了精确分类,则降低其权重．若弱决策树桩将传感器节点错误分类,则将其权重最大化．bt表示弱决策树桩的更新后权重．则强分类结果可计算为

(8)

为改善节点分类性能,最大限度降低误差,增强boosting模型增加了不同分类之间的间隔．强分类器的结果遵循以下间隔

(9)

式中an≥0,αn表示松弛变量,y表示分类的间隔．大于间隔的结果意味着将全部传感器节点分入某个特定类别时,可实现WSN中准确的节点分类(误警率非常低)．

由此,将传感器节点分类为高能量节点和低能量节点．分类处理后,低能量传感器节点通过计算Manhattan距离[14],将数据包发送至邻近的高能量传感器节点．传感器节点之间的距离计算如下

(10)

式中Dij表示两个传感器节点Si和Sj之间的Manhattan距离．计算出距离后,低能量传感器节点将数据广播至邻近的高能量传感器节点．最后,汇聚节点高效采集无线网络中高能量传感器节点的所有数据包．

2.2 数据聚合

所提数据聚合的步骤流程如以下算法所示．通过上述步骤,所提模型提供较好的节点分类准确度,消耗较短时间,且将训练误差最小化．通过分类得到高能量节点和低能量节点后,模型寻找距离最近的高能量节点,以在WSN中对传感数据包进行聚合．与传统方法先比,提出的模型通过较少的能量消耗即可采集所有数据包,可实现能量高效的数据聚合．

算法1 基于能量感知决策树和增强boosting的数据聚合.

输入: 传感器节点S1,S2,…,SN,数据包dp1,dp2,…,dpM

输出: 实现能量高效的数据聚合

1.Begin

2.for 每个传感器节点si

3.利用式(4)得到弱决策树桩w结果;

4.利用式(5)合并所有弱决策树桩结果wi

5.利用式(6)进行加权;

6.利用式(7)估计出训练误差ter

7.更新权重bt

8.寻找具有最小训练误差的弱分类器;

10.对WSN中所有传感器节点si进行分类;

11. End if

12. 利用式(8)和式(9)返回强节点分类结果;

13. End for

14.利用式(10)计算Manhattan距离;

15.识别距离最近的高能量节点;

16. 低能量节点将数据包发送至高能量节点;

17.汇聚节点对来自高能量节点的数据包进行聚合,

并发送至基站;

18.End

3 仿真实验与分析

为进行实验评估,本文在NS3网络模拟器[15]中实施了提出的模型,考虑的方形区域为1200 m×1200 m．仿真参数如表1所示．实验针对不同数量的传感器节点和数据包,从能量消耗、数据聚合准确度、网络工作寿命、延迟和数据聚合时间方面评估了提出的模型的有效性．并与自然启发优化(NIO)的数据采集模型[4],以及节点分级混合多跳数据采集(HMDC)模型[7]进行比较．

表1 仿真参数列表

3.1 能量消耗比较

能量消耗EC决定了WSN中传感器节点采集数据包所耗费的能量,其定义为

EC=N*eng(Si)

(11)

式中,N表示仿真过程中的传感器节点总数,eng(Si)表示网络中单个节点采集数据所耗费的能量．

1) 模型:传感器节点数量为50,单个传感器节点使用能量为0.45J,则总能耗EC=50×0.45J=23J．

2) NIO方法:传感器节点数量为50,单个传感器节点使用能量为0.62 J,则总能耗EC=50×0.62J=31 J．

3) HMDC方法:传感器节点数量为50,单个传感器节点使用能量为0.59 J,则总能耗EC=50×0.59 J=29 J．

对于不同数量的传感器节点(范围50～500个),使用不同方法的能耗结果如表2所示．从中可发现,在不同数量的传感器节点下,与NIO和HMDC相比,本文模型使用最小能量在WSN中完成可靠的数据采集．这得益于增强boosting模型处理,利用增强boosting模型识别出高能量节点,从而在无线网络中进行高效的传感数据包采集．利用选出的高剩余能量节点,避免链路故障,降低了数据包重传次数．因此,与其他模型相比,所提模型最大限度减少了传感器节点在WSN中采集数据包时的能量消耗,数据采集的能耗比NIO和HMDC分别低约26%和17%．

表2 能量消耗仿真结果

3.2 网络工作寿命比较

网络工作寿命NL计算为执行数据聚合的高能量节点数量与传感器节点总数量之比

(12)

式中,N表示传感器节点总数量,NH表示进行数据采集的高能量传感器节点数量．

网络工作寿命的计算结果如下:本文模型传感器节点数量为50个,选择的高能量传感器节点数量为48个,则网络工作寿命计算为96%;NIO传感器节点数量为50个,选择的高能量传感器节点数量为41个,网络工作寿命为82%．HMDC的传感器节点数量为50个,选择的高能量传感器节点数量为43个,网络工作寿命为86%．

表3给出了不同的传感器节点数量(范围50～500个),使用不同模型在数据采集过程中的网络工作寿命的比较．可发现,与NIO和HMDC相比,本文模型的网络工作寿命性能更优,分别提高了9%和10%．这主要是因为所提方法能够快速准确寻找到具有更高剩余能量的传感器节点以在WSN中进行数据采集,从而获得更高的网络工作寿命．

表3 网络工作寿命的结果比较

3.3 数据聚合准确度比较

数据聚合准确度ACC一般定义为通过汇聚节点正确聚合的数据包数量在传输数据包总数量中的占比．定义如下,

(13)

式中,ND表示正确采集的数据包数量,ndp表示数据包总数量．

本文模型汇聚节点正确采集的数据包数量为24,发送的总数据包数量为25,其ACC为96%．依据式(12),NIO和HMDC的ACC分别为84%和76%．表4给出了不同数量的数据包(范围25～250),各模型的数据聚合准确度结果．从中可发现,与NIO和HMDC相比,本文模型的数据聚合准确度分别提升了10%和16%．对于不同数量的数据包,所提模型均取得了更高的数据聚合准确度．所提模型使用增强boosting模型,将无线网络中的每个节点分类为高能量节点或低能量节点．基于节点分类结果,提出的模型仅使用较高能量的节点进行WSN中的数据采集,这有助于准确采集不同节点的数据,防止信息丢失．

表4 数据聚合准确度的仿真结果

3.4 延迟性能比较

延迟定义为在WSN中进行数据聚合时的期望时长与实际时长之差．数据聚合过程中,延迟越低,则效率越高．当数据包数量为25,本文模型完成数据聚合的期望时长为9 ms．实际数据聚合时长为11 ms．则延迟计算为2 ms．对于NIO模型,完成数据聚合的期望时长为15 ms．实际数据聚合时长为20 ms．其延迟为5 ms,HMDC完成数据聚合的期望时长为15 ms,实际数据聚合时长为18 ms,因此延迟为3 ms．

表5给出了对于不同数量的数据包(范围25～250个),使用不同模型的延迟比较．从中可发现,本文模型在不同输入数量下延迟均低于NIO和HMDC,延迟至少缩短了30%．这是主要是因为所提模型可以在较短时间内将WSN中的传感器节点分为高能量节点和低能量节点,通过将数据包发送至邻近高能量节点执行高效数据聚合,减少了延迟时间．

表5 延迟性能比较

3.5 网络连通性

图5 各方法的网络连通性比较

一般情况下,网络拓扑在相对短的时间内不会发生变化．网络连通性基于此条件,用于评估网络数据传输的连通性．在网络给定时刻,首先,选择一个初始节点,然后依次搜索直接连接的节点、二进制跳连接的节点和三跳连接的节点,直到连接到初始节点的节点数不再进一步增加,如图5所示,随着模拟迭代次数的增加,NIO模型的网络连通率较低且不稳定,介于0.2～0.75之间,这主要是因为自然启发方法的解较大程度上取决于初始解的优劣．而本文模型的网络连通率较高且更稳定,介于0.5～0.75之间,这主要得益于能量感知树和增强boosting明显提升了节点分类性能,训练的误差得到控制,数据的传输变得稳定．HMDC模型的指数总体上最高且最稳定,但在某些点上有一些较大的波动,介于0.45～0.8之间．总体而言,本文模型的网络连通性最好．

4 结论与展望

本文提出了WSN中基于能量感知决策树桩和增强boosting提升节点分类的数据聚合模型,通过节点分类改善数据采集性能,同时最大限度降低能量消耗,且具有较稳定的网络连通性．此外,与其他方法相比,所提模型降低了WSN中传感器节点采集数据包所消耗的能量,增加在WSN中被选择执行数据采集的高能量传感器节点的数量占比,在多个方面表现更优．