基于三维空气质量监测系统的非均匀分簇算法

于大为1，董茜茜，张 昀，于舒娟

(1.苏州信息职业技术学院，江苏 苏州 215200；2.南京邮电大学 电子与光学工程学院，南京 210003)

0 引言

随着工业和交通运输业的飞速发展，大量的有害物质被排到空气中，空气污染问题愈发的凸显。空气污染不仅在生活上给我们带来了危害，还增加了各种疾病的爆发概率，同时也给自然环境带来很多毁灭性的影响。环境监测是环境保护工作的重要组成部分，而空气质量监测是其中的一个重要环节。空气质量监测是对空气中污染物浓度的高低进行实时检测，给出空气的质量状况、污染指数、对人体健康影响的预告。当前，作为新时期物联网的典型案例，利用无线传感器网络(Wireless Sensor Network, WSN)实现大气环境自动监测已经得到广泛关注和应用[1-2]。空气质量检测的环境复杂，地域广阔，传感器节点经常被随机撒布在偏远地区、野外等人员难以到达地区，节点依靠干电池供电，部署后便无法对其进行回收或充能处理。因此，在空气监测系统无线传感网的设计中，需要引入分簇和路径规划策略，保证节点能量的高效和均衡使用，从而延长网络的生命周期。

为降低空气质量监测系统无线传感网中的通信能耗，基于分簇路由协议的策略受到广泛使用。所谓分簇，如图1所示将整个传感器网络划分为相对独立的若干区域，每个区域内包含簇首和簇成员两种类型的节点，簇成员节点负责感知数据，并将收集到的数据发送至簇首，簇首将簇成员传输过来的数据进行融合处理，然后以单跳或者多跳的形式传输给基站(Base Station,BS)。如今，许多研究人员已经提出多种分簇路由算法[3-9]。W.Heinzelman等人提出了一种经典的低功能自适应分簇协议(low energy adaptive clustering hierarchy, LEACH)[3]，该协议以轮为单位分为簇的建立和数据传输两个阶段。在簇建立阶段，根据阈值随机选择一定数量的节点担任簇首，这极可能造成簇首分布过于集中，造成网络局部瘫痪。而在传输数据时，簇首以单跳的形式将融合后的簇内数据传输给基站，能耗不均，存在严重的“热区”效应[4]。LEACH协议每一轮都要执行簇的重构，带来较大的通信开销。A.Ray等人[5]研究了一种基于改进K-means算法的节能聚类协议EECPK-means，该协议使用中心算法来改善初始质心选择过程，最终平衡簇首的负载，延长网络寿命。李成法等[6]提出了一个分布式非均匀分簇算法EEUC，以候选簇首离基站的距离为参数计算非均匀竞争半径，使靠近基站的簇首的簇规模更小，为簇首预留更多的能量用于数据转发。章力等[7]针对传感器节点均匀分布的窖池测温无线传感网络，利用差分进化算法选择固定数目的簇首，并对簇首和簇成员节点采用能量异构的策略。分簇一旦确立，网络运转过程中不再执行选簇的机制。

图1 无线传感网分簇路由协议示意图

本文在参考上述文献的基础上，根据空气质量监测无线传感网络规模较大、节点分布不均的特点，以节点覆盖率为目标建立函数优化模型，并采用差分进化算法对其优化；通过计算簇首的竞争半径，构造大小不等的簇；为了节省通信开销，网络运转过程中根据选簇频率和节点编号更换簇首节点。仿真实验表明，本文提出的分簇路由算法能够有效均衡空气质量检测系统无线传感网络的能耗，延长网络生命周期。

1 网络系统模型

根据图2所示的空气质量监测系统中传感器节点的分布，本文假设网络模型如下：在L×W×H的空间中，随机撒布N个传感器节点 ,其中L、W和H分别表示监测区域的长度、宽度和高度。用Ci表示第i个传感器节点，相应的节点集合为C={C1,C2,…,CN}，N=|C|。用CHj表示第j个簇首节点，相应的簇首节点节为CH={CH1,CH2,…,CHj}，我们假设：

1)所有传感器节点和BS在随机撒布后位置不再发生移动。

2)BS位于网络中心，其计算能力和能量均不受限制。

3)所有节点的能量同构且具有唯一的标识(ID)，具备数据融合能力，能够感知自己的剩余能量。

图2 空气质量监测系统传感器节点分布

参照文献[10]构造能量模型，无线通信传输l比特信息经过距离d0时所消耗的能量如式(1)所示：

(1)

其中:l为数据比特数，d为通信距离；Eelec，εfs和Emp表示系统在运转时电路的能量消耗，Eelec由数字编码方式、调制过程、滤波方法以及地域情况等因素决定，而εfsd2和εmpd4与传输者与接收者的距离和允许的误码率范围有关。无线通信接收l比特的信息时的能耗如式(2)所示:

ER(l)=lEelec

(2)

2 算法描述

2.1 簇首数目的确定

网络系统模型如上节所示，假设簇首数目为K，则平均簇内成员节点个数为N/K-1，簇首节点和簇成员节点的能耗分别为：

(3)

(4)

其中:EDA表示融合单位比特数据消耗的能量，dave表示簇首和基站两两之间的平均距离，dtoCH为簇成员节点到其簇首得距离。

在三维空气质量监测系统中，假设每个簇的覆盖区域为以簇首为中心的圆球且节点均匀分布，节点分布的概率密度为ρ=(x,y,z)=1/((L*W*H)/K)，则簇成员节点到簇首距离的数学期望为：

(5)

再假设区域内每个簇为半径近似R的圆球，即：

(6)

将公式(6)代入公式(5)，可得：

(7)

从而可得网络运转中每轮消耗的能量约为：

(8)

将公式(7)代入公式(8)，并将总能量对K求导，得出K的最优值为式(9)。

(9)

2.2 簇首坐标的优化

在空气质量监测系统簇首定位模型中，由于靠近基站的簇首需要转发额外的数据信息，很容易造成能量空洞的问题。我们采用非均匀的分簇机制。通过不同的成簇半径，使得簇规模越靠近基站越小。因此，靠近簇首的基站可以预留更多的能量用于转发其他簇首的数据。参考文献[6]，成簇半径定义为：

(10)

其中:dmax、dmin分别表示簇成员节点距离基站的最大值和最小值，d(Ci,BS)表示簇首Ci到基站的距离，Rmax表示节点间通信半径，c为0～1内的常数，用来控制成簇半径在(1-c)Rmax。

差分进化算法主要用于求解全局优化问题，是一种动态跟踪、随机搜索的智能进化算法。其主要分为两个阶段：初始化阶段、进化阶段。在本文簇首坐标优化问题初始化阶段，采用实数编码，则初始种群可根据公式(11)随机产生：

(11)

进化阶段包含变异、交叉和选择个操作步骤。其中变异采用如式(12)所示的策略，得到子代变异个体vi(G+1)。其中，xt1(G)表示第G代种群的第t1个个体；t1、t2、t3、t4、t5∈{1,2,…,NP}，且互不相等；F为缩放因子。

vi(G+1)=xt1(G)+F·(xt2(G)-xt3(G))+

F·(xt4(G)-xt5(G))

(12)

种群完成变异操作后，将变异个体vi(G+1)与目标个体xi(G)通常采用Binomial实验方式生成个体ui(G)，这一过程称之为交叉操作。值得注意的是，交叉操作的操作对象不再针对整个个体，而是按每个个体向量的分量进行的。交叉操作的公式如下：种群完成变异操作后，将变异个体vi(G+1)与目标个体xi(G)通常采用Binomial实验方式生成个体ui(G)，这一过程称之为交叉操作。值得注意的是，交叉操作的操作对象不再针对整个个体，而是按每个个体向量的分量进行的。交叉操作的公式如下：

(13)

式中，CR为交叉概率，是区间[0,1]内的一个常数；jrand是属于集合{1,2,…,D}的随机整数。

经过变异交叉后，生成的试验个体ui(G+1)与目标个体xi(G)参照式(14)竞争选择，生成下一代个体矢量。

(14)

(15)

最终通过差分进化算法得到最优簇首节点，然后计算各自的成簇半径，并对各簇内节点按照到对应簇首的距离编号(ID)，距离越近编号越小。

2.3 簇首更换机制

LEACH协议被麻省理工学院W.Heinzelman等人[3]提出，是最早的低功耗动态分簇自适应路由协议，是应用最广泛的协议，也是后面很多学者提出的大部分路由协议的基础。LEACH协议首次在无线传感网的运转中提出“轮”的概念，基本思想是：设定无线传感器网络中一次完整的数据采集为一轮，包括簇的建立和簇间数据传输两个阶段。每一轮簇首在簇的建立阶段以预先设定的阈值为选择标准，通过随机的方式产生。LEACH协议的优点是采用随机选举避免簇首能量过分消耗，缺点是网络运转过程中可能出现簇首分布不均的情况，距离汇聚节点过远的簇首能量消耗过大，簇首节点通信范围内覆盖不到的孤立节点个数过多。为了解决无线传感器网络多跳路由中容易产生的“热区”问题，一种非均匀分簇路由协议-EEUC协议被提出[6]。该协议与LEACH协议的最大差别是不需要在全局范围内选举簇首，仅需在局部范围内实现簇首竞选。EEUC协议每一轮也是由簇的建立和数据传输两个阶段构成。EEUC协议是当前比较有代表性的一个非均匀分簇路由协议，它的优势是利用大小不一的簇规模，通过均衡减少网络节点能耗，延长了网络的生命周期。它的缺陷是在候选簇首的抉择上对地理位置和剩余能量等因素缺乏考虑，网络动态性适用性较差。

在LEACH 协议和EEUC协议中，每轮均需要频繁选取簇首或候选簇首，簇的结构随着轮数动态变化，大量的广播消息消耗了过多的通信能量。因此本文所提算法设定选簇频率f以降低建簇开销。同时为了保证网络正常工作，每轮运转中都需要检查当前簇首的剩余能量。如果簇首的剩余能量低于能量阈值，则选择簇中ID最小且剩余能量大于阈值的节点作为新的簇首。新的簇首节点向簇内成员节点发送广播信息，通知簇内成员节点自己下一轮当选为簇首节点。图3示例具有ID号的传感器节点的排序。能量阈值根据存活节点的信息由下式给出：

(16)

其中:countlive是存活节点总个数。

图3 根据节点编号更换簇首示意图

2.4 簇首间路由协议

簇首对簇内的信息融合处理后以多跳的方式传送给基站，中间转发节点的选取和EEUC算法相同，在此不再赘述。针对空气质量监测系统无线传感网络，本文所设计的非均匀分簇算法如图4所示。

图4 分簇算法流程图

3 仿真实验

为了验证本文所提算法在空气质量检测系统无线传感网中的性能，利用Matlab仿真平台经过100次蒙特卡罗实验对该算法进行评估与分析，并将其与LEACH和EEUC协议进行比较。实验中所用的参数如表1所示。

根据3.1小节对最优簇首数目的推导，在本文仿真的网络环境下，最优簇首数目Kopt=25。因此在差分进化算法寻找最优簇首坐标阶段，种群规模NP=25。参照文献[7]，差分进化迭代次数Iternum=800，F=0.6，CR=0.01。适应度函数以最大化节点的覆盖率为目标，但在网络运转过程中，仍会出现簇首节点通信范围内覆盖不到的区域，定义此区域内的节点为孤立节点。表2给出了3种协议孤立节点个数随着网络运转轮数的变化情况，本文所提算法用NEW代表。从表中可以看出，由于LEACH协议簇首分布不均，造成孤立节点数远大于其他两种算法，节点利用率低。EEUC和本文所提算法孤立节点个数相差不大，但在前300轮生存时间内，本文在所提算法节点利用率均高于LEACH 83%，也比EEUC提高了60%，从而采集信息的区域范围更广。

表1 实验参数

表2 孤立节点个数比较

本文提出根据剩余能量和节点编号动态更换簇首的机制，和EEUC相比，省去了每轮选簇首和构造簇结构的通信开销。通过对簇首能耗方差的比较，可以直观地比较其能耗的均衡度，有效避免出现能量空洞问题的出现，从而延长网络生命周期。图5(a)比较了这3种算法中簇首能耗的方差，其中横坐标是在网络生命周期内随机抽取的10轮。可以看出，本文所提算法和EEUC的方差波动浮动很小且相差不大，但均低于LEACH协议的方差。为了进一步比较本文所提算法和EEUC簇首能耗的优劣，通过计算图5(a)所示实验中对应簇首的剩余能量均值，其值如图5(b)所示，可以得出本文算的簇首能耗较EEUC更低，从而可以延长节点的生存周期。

图5 簇首能耗的相关比较

图5从孤立节点个数和簇首的能耗两个方面比较了3种算法。图6针对整个网络，从全局的角度出发，比较网络生命周期。给出了3种算法网络存活节点个数随着运转轮数变化的关系。可以看出，本文所提算法能够显著延长了第一个节点的死亡时间，整个网络生命周期相较于LEACH和EEUC，分别提高了约55.6%和14.8%。由此可知本文所提算法能够更好地均衡网络能耗，延长网络的生命周期。

图6 存活节点个数随网络运转变化图

4 结束语

本文从提高空气质量检测系统无线传感网的网络生命周期出发，提出一种基于差分改进的非均匀分簇路由算法。本文所提算法有以下主要创新点:1)推导三维空间无线传感网最优簇首的计算，固定数目的簇首简化分簇机制，节省节点间传输广播消息的能耗；2)以高节点覆盖率为目标函数，同时考虑去除覆盖冗余，利用差分进化算法寻找最优簇首坐标，减少簇首节点分布不合理带来的能耗不均，孤立节点过多等问题；3)以成簇频率和簇首编号来减少频繁选簇，不仅可以解决簇首能耗不均导致的能量空洞问题，还可以均衡网络中所有节点的能耗。通过仿真实验证明，该算法能够提高节点的利用率，有效延长空气质量检测系统无线传感的网络生命周期。