云环境下异构无线传感器网络节点调度改进算法*

刘东平，马利亚，杨 军

(1.宁夏大学 数学计算机学院，宁夏 银川750021;2.宁夏医科大学 总医院，宁夏 银川750000;3.宁夏大学 计算机网络管理中心，宁夏 银川750021)

0 引 言

传统无线传感器网络(wireless sensor networks，WSNs)监测区域范围有限、节点类型与感知数据类型单一、节点产生感知数据量小，网络异构性不突出。在大规模WSNs 中网络异构性较传统WSNs 更加突出，表现为网络监测区域变大、节点数量众多、感知数据格式、节点地位不同［1］，对节点调度提出了新的要求。

传统节点调度算法比如LEACH［2］算法在簇头生成阶段未考虑节点剩余能量信息，成簇不均匀，没有对融合数据有效性判断，并且在大规模WSNs 环境下随着数据量增加，算法执行时间必定延长，无法及时对节点进行调度。为解决大规模WSNs 环境下节点能耗过快，算法效率低等问题，孙韩林等人［3］提出一种基于云计算的WSNs 体系架构，通过在WSNs 中加入云节点并将其组织成云，云端进行数据处理。不足是架构只给出了数据处理，未对WSNs 中能量与簇分布进行研究。Khandakar Ahmed 等人［4］提出一种云计算与WSNs 结合模式，通过事件匹配器与代理在云端查找对应存储数据，不足是模式仅给出了数据如何进行存储与查询，未对WSNs 具体的能量与簇分布进行研究。刘宏宇等人［5］提出通过云计算对WSNs 数据进行统一管理，用户直接通过云平台管理数据，不足是该方案未对WSNs 能量与分簇进行研究。

通过对以上文献总结得出，在大规模WSNs 环境下，云计算与节点调度结合算法主要针对数据处理，对WSNs 节点能量与簇分布研究较少。本文在此研究基础上，提出基于云计算的异构WSNs 节点调度模型及其改进算法，模型通过将本地节点的算法执行迁移至云端，云端利用节点调度改进算法，动态生成节点调度方案，对节点进行动态调度。

1 改进调度模型与算法设计

1.1 改进节点调度模型设计

在初始阶段，节点将自己状态信息发送到基站，基站通过网关将状态信息上传到云端，云端运行改进调度算法，生成节点调度方案控制信息，通过网关与基站下发至对应节点，控制相应节点成簇。成簇后，节点首先将感知数据进行簇头融合(考虑在簇头融合是为减少无效信息传输，降低对网络带宽要求)，并上传到该簇头所在区域基站，基站将融合数据上传至网关，最终由网关上传数据至云端并在云端进行处理。同时，云端记录接收上传网关编号，在下次控制数据发送时通过该网关下达。调度模型如图1 所示。

图1 调度模型Fig 1 Schedule model

由于节点异构性，不同节点产生的数据类型格式不同，会影响云端算法执行的效率。算法对不同节点数据类型进行了统一，分为融合数据与控制数据。融合数据为簇头融合数据，控制数据为云端调度方案数据。

1.2 改进调度算法

改进算法中，节点将自己的状态信息通过网关上传至云端，云端根据状态信息判断节点当前簇头选举轮数是否满足第一轮或未收到簇头通告次数是否等于最大规定次数。如满足，则选用只考虑添加剩余能量因子的算法选取簇头;如不满足，则除考虑节点剩余能量外，还考虑节点与簇头距离、节点与基站距离、上一轮与节点处于同一簇成员个数等因素，通过云端对每个节点执行评估函数选取簇头。簇头选取成功后，云端通过网关发送控制消息，指定相应节点成为簇头，控制簇头发送簇头通告给其它节点，节点如未收到簇头通告信息，则节点未收到簇头通告值(NO_CH_ROUND++)自增1。节点收到通告后，根据通告信号强度，发送加入请求给簇头，同时，在请求中携带自己的剩余能量、与簇头和基站距离(距离可以使用RSSI［6］定位算法求出)、与节点上一轮处于同一簇成员个数等信息。簇头收到信息后经过网关直接上传至云端并更新自己状态信息，云端根据节点加入请求中携带的与簇头距离信息，判断请求节点是否处于均匀分簇半径R(R 为簇最优半径)内，如果小于等于R，则记录该节点编号，以便控制该节点加入簇，同时记录加入簇的簇成员数目。如果簇成员数目达到(1－f)/f 个(f 为簇头节点比例)，则云端控制簇头不再接受其它节点加入该簇。当簇成员数目达到规定数目后，云端控制簇头发送TDMA 时隙片段给簇成员，簇成员根据TDMA 消息，发送数据给簇头，云端对该簇头收集的历史数据进行分析，生成发送阈值θ，并发送给簇头。簇头将融合数据与θ 作比较，如大于θ，则发送;否则，不发送。

1)剩余能量

算法在初始簇头选取时，云端仅参考剩余能量因子Energys/Energyt，具体见公式(1)

从式(1)可知，能量因子在第一轮节点能量相同时相同，在后期簇头选取时，剩余能量多的节点能量因子较大，对阈值T(ni)的影响就大，有更大概率当选为簇头。

在下轮簇头选取时，簇头及时将节点加入簇请求报文中携带的剩余能量、与待加入簇头距离、基站距离、上一轮与该节点同簇节点数目等信息上传至云端并更新自己状态信息，云端参考更新信息，结合模拟退火算法，利用评估函数，即式(2)，求取每个节点的评估函数值，云端优先选取评估函数值较大者为下一轮簇头。

记E(ni)为节点ni目前的剩余能量，Dtosink(ni)为节点i 与基站距离，Dtocluster(ni)为节点i 与待加入簇头距离，N(ni)表示与节点i 上一轮处于同一簇的成员数目，属于簇cj的节点ni被选为下一轮簇头的评估函数为

式中 pe，pd，pc，pn分别代表节点的剩余能量、节点距基站距离、节点距待加入簇头距离、上一轮与节点同簇成员数，fe，fd，fc，fn分别为各自的权重，pe，pd，pc，pn如下式

式(3)求取在cj簇内各个簇成员节点的剩余能量信息;式(4)求取在cj簇内节点距离基站的信息，采用倒数是因为离基站越近的簇成员越有可能成为簇头;式(5)求取在cj簇内节点距离簇头的信息，采用倒数是因为距离簇头越近的簇成员越有可能成为下一轮簇头，因为距离越近能量消耗越少，而且下轮簇成员距离新簇头距离更加接近;式(6)求取在cj簇内各个节点上一轮处于同一簇成员数，求取倒数是因为上一轮处于同一簇成员越多，该节点担任簇头后消耗的能量就越多，所以，Nni∈cj(ni)的选取应该越小越好，pn(ni，cj)对评估函数的影响就会更大，即上一轮同簇成员少的节点有更大概率担任簇头。

与第一轮簇头选取算法不同的是，第一轮以后的簇头选取算法不单考虑节点的剩余能量，还兼容考虑簇头更新信息。网络运行一段时间后可能出现网络无簇头的情况，云端判断NO_CH_ROUND 是否达到设定的阈值，如达到则重新利用式(1)进行簇头选取。

2)均匀分簇

首先，介绍有效覆盖面积，在WSNs 中，一块区域有可能被多个节点所覆盖，如图2 所示，节点n1的有效覆盖面积Sn1为节点n1的覆盖面积减去重复覆盖区域面积Sc的50%，即。其次，如图3 所示，在相邻节点的覆盖拓扑中，当节点ni所覆盖的区域是一个边长为r 的正六边形时，节点ni所覆盖的无缝面积最大［7］，即Sa=6×在改进算法中，假设簇头比例为f，监测节点个数为n，则簇头个数为f×n，每一个簇包含簇成员数目为，假设节点分布在一个面积为S的监测区域中，则每一个簇所占区域面积为S/(f×n)，根据最大覆盖面积，每一个簇的面积为Sa，则Sa=S/(f×n)，所以可得簇最优半径为所以，为达到对监测区域的完整覆盖，需要设置簇头间距在［2R(1－sin α)，2R(1+sin α)］之间，规定只有在簇头R 以内的节点才能成为该簇成员，而且，簇头记录加入簇请求节点数目，直到节点数目达到个，然后，拒绝其它节点加入，这样，不仅簇成员与簇头之间的距离被限制在一个理想范围内，而且，簇被均匀分布在监测区域，弥补了随机成簇的缺点。

图2 节点有效覆盖面积Fig 2 Effective area covered by node

图3 节点最大覆盖面积Fig 3 The maximum coverage area of node

3)预测传输

改进数据传输算法使用单跳与多跳结合的带预测的传输方式传输融合数据。云端对簇头历史数据进行并行分析，生成允许发送阈值θ，然后将阈值发送给簇头，簇头将待发送融合数据与阈值相比较，如大于阈值，则发送;否则，不发送。算法执行流程如图4 所示。

2 仿真模型搭建

仿真软件使用OMNET++，配合使用无线传感器仿真框架MiXim 来实现能量模型和信号衰减。硬件模型使用德州仪器提供的2.4 GHz IEEE802.15.4 无线收发芯片CC2420［8］，其它参数根据文献［9］设定见表1。

表1 硬件基本参数Fig 1 Basic parameters of hardware

3 结果与分析

3.1 节点调度结果与分析

实验将50 个节点随机分布在500 m×500 m 的正方形场景中，设置簇头个数为5，各节点初始能量相同，各个节点分别对LEACH、LEACH—C、改进调度算法进行仿真，当所有节点能量耗尽时仿真结束，结果如图5 ～图10 所示。

图4 改进算法流程图Fig 4 Flow chart of improved algorithm

图5 剩余节点信息Fig 5 Remaining node information

图6 剩余能量信息Fig 6 Remaining energy information

图7 均匀分簇作用后剩余节点信息Fig 7 Remaining node information after uniform clustering

图8 均匀分簇作用后剩余能量信息Fig 8 Residual energy information after uniform clustering effect

图9 剩余能量作用后剩余节点信息Fig 9 Remaining node information after remaining energy effect

图10 剩余能量作用后剩余能量信息Fig 10 Remaining energy information after remaining energy effect

从图5 与图6 可以看出:三种算法中效果最好的是LEACH—C 算法，其次为改进算法，最差为LEACH 算法。LEACH—C 算法使用集中式簇头选择，避免了簇头通告与节点加入请求，节省了能量，由于节点能耗大致相同，所以，在后期节点几乎在同一时间死亡。改进算法节点在第一轮剩余能量因子相同，在开始效果与LEACH 算法相同，在第一轮后由于不只考虑节点的剩余能量，而且加入了距离和同一簇成员数目等信息，从剩余能量和数据传输能耗上降低了节点能耗。在成簇上使用均匀分簇，均衡了簇头负载，在后期传输数据上更加注重数据有效性，节省了能量，在剩余节点与能量上效果优于LEACH 算法。由于采用了云计算，节点需要传输状态与位置信息给云端，会造成部分能量消耗，效果没有LEACH—C 算法好，不过在大规模WSNs 环境下，改进算法能够比LEACH—C 算法更快地实现对WSNs的控制和数据的高效处理。从图7 与图8 可以看出:单独在均匀分簇方面进行改进效果略优于LEACH 算法，由于单独考虑均匀分簇，没有加入剩余能量，会出现剩余能量少的节点担任簇头，但由于采用了均匀分簇，每个簇成员数目都大致相同，簇头负载相对均衡，减少了某些簇内簇成员多，对簇头负载过重的情况，与LEACH 算法相比降低了簇头能量消耗的速度，在效果上略优于LEACH 算法。从图9和图10 可以看出:单独在剩余能量方面进行改进效果优于LEACH 算法，由于簇头选择时每次都选择能量多的、位置距离簇头和基站近的节点担任簇头，避免了能量少的节点优先担任簇头，缩短了数据传输距离，降低了发送能耗，最终降低了簇头死亡率。由于降低了簇头死亡率，所以，整个簇内的能耗均匀地分布到每个节点上，提高了节点存活率。

3.2 融合数据处理结果与分析

3.2.1 融合数据处理

融合数据处理主要统计在不同融合数据量情况下，云端并行处理融合数据耗时，并由此推测大数据环境下异构数据处理效率。

数据由网关上传至云端HDFS 采用分块进行存储，实验数据对比见表2，实验结果见图11。

表2 融合数据处理耗时对比表Fig 2 Time consuming comparison of fused data processing

图11 融合数据处理耗时对比Fig 11 Comparison of time consuming of fused data processing

3.2.2 融合数据处理结果分析

从图11 可以看出:随着数据量增大，并行环境下数据处理耗时相对稳定，维持在50 s 左右，但对于单机串行环境下数据处理耗时会随着数据量增加而上升。这是由于云端环境基于Hadoop 分布式并行处理，当数据量增加时，耗时并不会显著增加;相反，对于单机串行处理环境，主机之间的任务并行程度低，随着数据量增加，任务耗时也会相应上升。实验结果说明:并行数据处理相对单机串行数据处理在处理大规模环境下海量数据效率更高。

4 结 论

从实验结果可以得出:改进调度算法在剩余能量与存活节点数目上，相比于LEACH 算法分别提高了28%和34%左右。说明改进算法确实可以有效地减少节点能量消耗，延长网络生存周期。在融合数据处理耗时方面，并行环境下数据量的大小变化对处理耗时的影响比较小，单机串行环境下处理耗时受数据量大小变化影响较大。通过实验对比，得出云环境下的融合数据处理对大规模WSNs 下产生的海量数据具有很好的处理效率。

［1］ 潘巨龙.无线传感器网络的异构性研究［J］.航空计算技术，2007，37(2):124－126.

［2］ 魏玉宏，孔韦韦.一种基于LEACH 协议高效节能的数据融合算法［J］.传感器与微系统，2015，34(6):148－150.

［3］ 孙韩林，张 鹏，闫 峥，等.一种基于云计算的无线传感网体系结构［J］.计算机应用研究，2013，30(12):3720－3723.

［4］ Ahmed K，Gregory M.Integrating wireless sensor networks with cloud computing［C］∥Seventh International Conference on Mobile Ad－Hoc and Sensor Networks，IEEE，2011:364－366.

［5］ 刘宏宇.基于无线传感器网络的森林环境监测云平台研究与实现［D］.北京:中国林业科学研究院，2012.

［6］ 方 震，郭 鹏，张玉国.基于RSSI 测距分析［J］.传感技术学报，2007，20(11):2526－2530.

［7］ Wang X，Yang Y，Zhang Z.A virtual rhomb grid－based movement－assisted sensor deployment algorithm in wireless sensor networks［C］∥International Multi－Symposiums on Computer and Computational Sciences，Harbin:IEEE Computer Society，2006:491－495.

［8］ 赵 海，刘 铮，纪书杰.一种无线传感器网络节点的设计与实现［［J］.东北大学学报:自然科学版，2009，30(6):809－812.

［9］ TI Instruments.2.4 GHz IEEE 802.15.4/Zig Bee－ready RF transceiver(Rev.B)Datasheet［EB/OL］.［2012—10—15］.http:∥www.ti.com/product/cc2420.