一种基于多目标进化的无线传感器网络的信号重构算法

张朝霞 蒋 勇 李丽霞 罗智勇

（湖南化工职业技术学院，湖南 株洲 412004）

无线传感器网络是一种多跳、自组织的无线通信网络，部署了大量能量受限的传感器节点[1]。具有快速展开和抗毁性强等特点，可广泛应用于军事侦察、医疗监护、工业生产、环境监测、农业养殖等领域。

WSN 一般采用分簇路由方式，具有拓扑管理方便、数据融合简单和节省能量等优点。如图1 所示，在分簇路由算法中，通常将网络划分为若干个簇，即为具有某种关联的网络节点集合。每个簇由一个簇头和多个簇内成员组成，由簇头与基站通信。

图1 无线传感器网络的拓扑结构

LEACH 协议是Heinzelman W[2]等最早提出的用于WSN 中分簇路由协议，它采用等概率循环随机选择簇头，通过簇成员节点根据簇头广播信号强度加入分簇的方式形成分簇。Handy MJ[3]引入了能量因素，对LEACH 算法中节点当选为簇头的阈值计算进行改进，提出了DCHS 算法来延长了网络生存时间。Heinzelman W.[4]针对LEACH 协议每轮产生簇头数目和位置不确定的缺陷，提出LEACH-C(LEACH-centralized)和LEACH-F(LEACH-fixed)。每个节点把自身信息报告给基站，由基站根据收到的信息来选择簇头，并将分簇结构和簇头集合广播出去。Younis O.等人提出HEED (Hybrid Energy-efficient Distributed Clustering)[5]，簇头的产生主要依赖主、次两个参数，分别依赖于剩余能量和簇内通信代价。能产生分布均匀的簇头和更加合理的网络拓扑[6]。LEACH 路由算法的分簇思想对后续提出的分簇路由算法产生了较大的促进作用。

本文提出基于多目标进化的无线传感器网络分簇信号重构算法，基于LEACH 算法，主要对无线传感器网络中的簇头节点个数、节点剩余能量、分簇空间分布、和总能耗四个方面进行分析评价。包括：首先建立基于多目标进化的系统模型；再进行种群初始化，选择交叉和动态变异等操作，得出最优的分簇重构解决方案，并通过实验仿真进行验证。

1 系统模型

传感器节点通常能量受限。为了延长网络生存时间，簇头一定要周期性更新。而分簇的结构、大小以及数量取决于簇头的选择方法、数量和位置。因此，簇头的选择方法要依据以下准则：（1）簇内成员到簇头的通信代价；（2）簇头的空间分布；（3）节点剩余能量；（4）能耗均衡。基于以上准则进行建模。

1.1分簇紧密度

针对上述准则（2）（3）定义分簇紧密度fT如下：

其中，K为分簇个数，Ci和Cj分别为第i 和第j 个簇。为第i 个簇内成员n 到簇头的距离。为簇头i 到簇头j的距离。由分簇紧密度表达式可知，当簇头分布越分散，同时簇内成员到簇头之间的距离越小时，fT越小。

1.2 能耗模型

针对上述准则（4）之节能的目标，建立能耗模型并给出总能耗计算方法。如图2 所示，当传输距离为d 时，在一定信噪比（Signal-to-Noise Ratio，SNR）条件下传输L-bit 数据的能耗为：

图2 能耗模型

根据发送端和接收端之间的距离远近，我们选择不同的传输模型(即采用Efs或是Emp)。Eelec发送/接收端传输每bit 数据的电路能耗。接收端每接收1bit 数据的能耗为ERX=Eelec。

为简化模型，做如下假设：

（1）n 个传感器节点随机分布在M×M的方形区域内，数据汇聚节点（Sink）位于监测区域的中央。

（2）考虑到网络开销的能耗远小于传输数据的能耗，本文仅考虑了数据传输的能耗。

（3）通信过程中不存在重连和数据传输错误，且节点传输的数据存在冗余。

基于上述假设，我们可以得出一个时间轮中簇头节点的能耗如下：

其中，K 为分簇个数，EDA为数据融合每bit的能耗，dCHN-SINK为簇头节点到sink 节点的距离，R(i)为数据融合率，第i 个簇内数据融合率可表述为：

式（4）中，Cnodes(i)簇内节点个数，b 为一个仅依赖于Cnodes(i)的常数。R(i)的期望值为：

一个时间轮中普通节点的能耗如下：

其中dCN-CHN为普通节点到簇头节点之间的距离，其期望值[8]为：

其中ρ(x,y)为节点分布函数，本文假设节点服从均匀分布，因此，ρ(x,y)=1/(M2/K)。

联合上述（3）-（7）式可以得出一个时间轮中总能耗如下：

1.3 适应度函数

衡量一个进化算法成功与否的重要标准是选取一个合适的适应度函数，它影响着进化的方向。因此，根据上述簇头的选择方法必须遵循的4 条准则设计适应度函数如下：

其中，ECHN_average为簇头节点平均剩余能量，α 为权重因子，其大小可由用户根据工程实践中的实际需要进行调整。

1.4 多目标进化模型

进化算法是一种通过模拟生物自然进化过程的随机搜索算法，利用它能有效的解决该问题。本文针对WSN的自身特点，建立基于多目标进化的WSN 分簇信号重构分析模型。主要步骤包括初始种群的获取，基因编码，适应度计算，根据条件进行选择，交叉和变异，得出最优解决方案。

1.4.1 获取初始种群和基因编码

首先，监测网络区域内所有节点完成定位和统一后，发送广播消息，消息内容包括节点ID、位置信息和一个长度为L（L 为正整数）的二进制随机序列。当Sink 收到所有节点的广播消息后，则逐位读取随机序列中的值，并构造成一个矩阵H0，，元素等于0 或1）是ID 为i的节点所发送的随机序列的第j 位；仅当hij为“1”时表示节点i 被选成簇头，否则不是簇头。列向量表示为一种可能的分簇结构，即，一个只含一条染色体的个体，L 个个体构成初始种群，用矩阵H0表示。

1.4.2 选择交叉与变异

Sink 节点对每个个体进行评估，分别计算出各个个体的评估值，并保存评估值的最小值Fmin。根据每一个个体的评估值来对初始种群进行二进制锦标赛选择，交叉和变异，构成新的矩阵H1，

具体步骤如下：

首先，对矩阵H0中的每个元素以概率P 进行运算。

最后，用H1替换H0重复执行上述步骤，一直到Fmin达到一个稳定值，即达到满足终止条件时，Fmin对应的个体即为最优的分簇结构。

2 仿真结果分析

仿真过程中，假设100 个节点随机分布在100mm×100mm的监测区域内，Sink 节点位于监测区域的中央，节点采集的数据大小为1bit，10%的节点的初始能量为0.8J，其余节点的初始剩余能量为0.4J。表1 给出了部分仿真参数。

表1 仿真参数

仿真对比更具说服性，在对LEACH 协议进行仿真前，先用本文信号重构算法给出最优分簇的个数，确定节点选为簇头的概率，再进行对比分析。如图3 所示，用本文提出的多目标分簇信号重构算法在稳定后，分簇个数能产生和LEACH 协议数目相近的分簇。簇头的平均剩余能量一定程度上反映了网络的存活时间。通过实验仿真，如图4 所示，本文提出的分簇信号重构方法选择的簇头平均剩余能量要高于LEACH 协议。根据两种算法选择的簇头平均剩余能量情况，可推测出LEACH 分簇下会存在能耗不均匀。因此，将两种算法的总能耗进行对比分析。如图5 所示，仿真结果表明，本文提出的算法的总耗能低于LEACH 算法。

图3 分簇个数情况

图4 簇头节点平均剩余能量情况

图5 总能耗情况

3 结论

针对无线传感器网络的分簇信号重构算法的研究问题，提出基于多目标进化的分簇信号重构分析方法。主要考虑分簇头节点个数、簇空间分布、节点剩余能量和网络总能耗四个因素对基于LEACH的无线传感器网络分簇信号重构算法进行优化改进，并给出了较优的分簇个数和分簇结构。相同条件下对最后以LEACH 协议为例进行分析，实验仿真结果表明，本文提出的方法能给出较优的分簇信号重构方案。