基于遗传优化的神经网络分簇路由算法*

隋春江，李 晖

（沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870）

0 引 言

无线传感器网络（WSN）是由许多小型低功耗的传感器节点部署在目标监测区域内所组成的自组织网络系统，是一种研究广泛并融合多个学科领域的信息获取和信息处理技术，主要对监测目标进行数据感知、数据收集和数据处理[1]，并把数据处理的结果及时反馈到终端用户，在健康医疗、智能家居、环境监测和城市交通等领域有着广泛的应用[2-3]。尤其是在近几年，随着5G时代的来临，无线传感器网络的应用前景越来越好，其中WSN应用于车联网技术将会是未来研究的热点。车联网主要通过车与车间的互联来计算不同车辆之间的最佳行驶路线并及时汇报道路状况和道路周边信息，有效缓解交通堵塞现象。然而，由于传感器节点布置后电池不能进行充电，从而导致传感器节点的能量十分有限。因此，在无线传感器网络中，如何有效地节约能量，提高能量利用率，成为WSN的重点研究内容之一[4]。

目前，在无线传感器网络分簇路由算法中，基于层次化的分簇路由算法是减缓簇首能量消耗速率的一种有效方法。其中，LEACH算法是Heinzelman等人在2002年提出的一种经典的无线传感器网络分簇路由算法[5]，主要思想是依据预先给定好的概率选择簇首，使每个传感器节点轮流充当簇首，从而降低节点能量消耗，达到延长无线传感器网络生存时间的目的。但是，由于随机性选择簇首，低能量的节点也可能被选为簇首，从而导致簇首节点的能量过早消失。有人针对以上存在的问题提出了一种集中式的分簇路由算法LEACH-C[6]，是在每个周期开始阶段时把所有传感器节点的位置信息和剩余能量信息传输到基站，然后基站计算所有节点的平均能量值，把其中能量高于平均能量的节点作为备选节点，最后利用模拟退火算法寻找节点位置的最优解，以此减缓簇首节点能量损耗速率，延长网络生存时间。但是，每个周期传感器节点都要向基站发送数据信息，造成了传感器节点能量不必要的损耗。文献[7]提出了一种能耗均衡的多跳路由算法，充分考虑节点的能量和位置因素，一定程度上减少了簇首能量消耗速率，提高了无线传感器网络的生命周期。还有专家学者将智能优化算法引入到无线传感器网络聚类分簇算法中，如文献[8]是一种结合节点的剩余能量、位置信息和节点密度等因素提出的人工蜂群分簇路由算法，得到的簇首部署更均衡，有效缓解了能量衰减速率，大大延长了无线传感器网络的生存时间，但是自身存在寻优能力差、无法快速收敛等问题。文献[9]是在LEACH算法基础上将单跳通信方式改为多跳通信方式，并提出了一种基于遗传算法的优化网络拓扑算法。文献[10]是在智能算法基础上引入BP神经网络的知识，提出一种在无线传感器网络中应用粒子群优化的BP神经网络分簇路由算法。该算法由于BP神经网络的权值和阈值是利用PSO算法进行优化得到的，因而可有效融合原始数据，有效减少数据传输，进而延长WSN的生存时间。

分析以上文献，无线传感器网络分簇路由算法在选举簇首时存在簇首选择不合理的情况，无线传感器网络的生存时间有待进一步提高。为此，本文提出一种基于遗传优化的BP神经网络分簇路由算法，将传感器节点比作为神经网络中的神经元，通过遗传算法优化的BP神经网络选择簇首节点，解决簇首选择不合理所造成网络能量损耗过快的问题，从而实现增加无线传感器网络能量利用率、延长无线传感器网络生存时间的目的。

1 算法概念

1.1 遗传算法

1969年，Holland教授首次提出遗传算法的概念。它是一种遵循“物竞天择，适者生存”的自然选择机制，通过在科学和生产实践中模拟自然演化机制找出最符合问题需求的最优解。它的原理为把种群个体看成需要解决问题的参数编码，通过重复迭代进行选择、交叉、突变等遗传操作产生下一代个体，适应度函数值小的个体将会被淘汰，适应度函数值大的个体具有更高的生存概率，得到的个体具有符合优化搜索目标最优解的性质，是一种全局优化的自组织和自学习的概率型算法。GA查找最优解的流程是从编码构成初始种群开始，然后对群体中的个体进行适应度函数值评估来完成选择操作，新个体的产生是由GA在个体间进行交叉和变异操作实现的，遵从优胜劣汰的进化过程，最终得到最优解。主要步骤如下：

（1）选择：从种群中选择优胜的种群个体，淘汰劣质的种群个体。通过选择操作把优良的种群个体直接或间接地遗传到下一代，是抉择优良个体的关键一步。

（2）交叉：交叉操作是遗传算法起核心作用的操作。交叉操作是把两个属于父代个体的部分基因交叉重组而重新生成新个体的操作。

（3）变异：变异是对群体中的个体串上的某些基因值做改变，以使遗传算法可维持种群的多样性，防止出现未成熟收敛现象。

1.2 BP神经网络

通过搭建BP神经网络来完成对簇首节点和普通节点特征的分类任务。BP神经网络是一种按误差传播训练的多层前馈网络。神经网络由两部分组成：信息的正向传输和误差的反向传输。神经网络中分布大量的神经元节点，各神经元之间通过权值和阈值连接形成三层神经网络结构，包括一个输入层、一个隐含层和一个输出层。BP神经网络能够逼近任意非线性映射关系，具有很好的分类能力，能很好地完成基于无线传感器节点特征的分类工作。图1是三层BP神经网络的模型。

图1 三层BP神经网络模型

图1 中，神经网络的输入层为X1到Xn，Wij、Wjk分别为输入层和隐含层之间的神经元权值与隐含层和输出层之间的神经元权值，Y1到Ym是经过BP神经网络优化所得的输出结果。BP神经网络采用一种非线性映射并行管理机制，具有很强的高度自学能力和很好的泛化能力，能够快速逼近任意非线性映射[11]。但是，BP神经网络也存在一定的不足，例如BP神经网络需要训练大量样本数据才可以确定初始权值和阈值相关参数，导致BP神经网络学习速度慢，易陷于局部极小值。

2 算法流程

在无线传感器网络中应用GABP算法时，BP神经网络的拓扑结构需要根据无线传感器网络的拓扑结构来确定。利用LEACH算法把无线传感器网络规划为多个分簇，所得到的每个分簇分别对应于每个BP神经网络模型结构。BP神经网络输入层的个数为分簇成员节点的个数，输出层为簇首的个数。LEACH算法选择簇首的过程是先对每个节点生成一个0到1的随机数，如果该随机数小于阈值，则该节点当选为簇首[12]，而GABP算法是利用遗传优化的BP神经网络收敛速度快、泛化能力强等特点来选择簇首。GABP算法的工作流程图如图2所示。

图2 GABP算法的工作流程

主要包括以下三大步骤。

步骤1：首先对种群进行初始化，通过无线传感器网络拓扑结构确定BP神经网络拓扑结构，然后利用GA优化的BP神经网络对权值和阈值进行编码，得到初始种群。

步骤2：确定最优BP神经网络参数。遗传算法依据BP神经网络的实际输出和期望输出的误差更新种群中的个体。通过GA的复制、交叉和变异步骤产生新的种群，并判断此时的情况是否需要重复迭代。如果达到条件，则把得到的最优解传递到BP神经网络中进行训练；否则，需要重复迭代，直到满足最优解为止。

步骤3：训练BP神经网络。遗传算法对BP神经网络的权值和阈值进行优化，不断进行网络的训练，直到得到确定的参数为止，然后进行无线传感器网络簇首选择的过程。

GABP算法具体过程如下：

（1）根据无线传感器网络确定BP神经网络结构模型，初始化BP神经网络的权值和阈值，然后根据式（1）确定隐含层的节点个数。

式中l为隐含层节点个数，n为输入节点数，m为输出节点数，a为1到10之间的调节常数。通过多次试验来确定隐含层节点数。

（2）将步骤1初始化的权值和阈值传递给遗传算法，计算适应度函数值并把适应度值大的个体进行交叉、变异等操作，更新种群，判断是否满足条件，如满足则执行步骤3，否则，重复迭代直到满足条件终止。其中，适应度函数计算为：

式中d(i)为节点传输距离，En_res表示节点n剩余的能量，EN_res表示所有节点剩余能量，D(i)为邻居节点密度，a、β、μ为权值系数，且α+β+μ=1。

（2）将步骤2产生的最优解传递到BP神经网络中，BP神经网络中的误差en是由预测输出Yn和实际输出On决定的，计算方法为：

式中，n为输出层数量，且n=1,2,…,m。

（4）根据误差en更新阈值和权值。

式中，wij表示为神经网络输入层第i个神经元与隐含层第j个神经元之间的权值，Hi是神经网络输入层数值。

式中，wjk表示为神经网络隐含层j个神经元与输出层第k个神经元之间的权值，Hj为隐含层输出。

（5）假如经过BP神经网络处理得到的输出误差en达到事先设定好的理想值，则终止算法继续运行，否则返回步骤3继续执行。

3 仿真结果与分析

为了验证所提算法的效果，本文选择Matlab2016a工作环境进行仿真，且计算机所采用的硬件配置为英特尔酷睿i5处理器和4 GB运行内存。实验仿真是在100 m×100 m的区域随机部署100个传感器节点，主要仿真参数设置如表1所示。

表1 仿真参数设置

本文分别从节点存活数量、传输到基站的数据量、能量消耗三个方面进行仿真分析对比，得到如图3、图4和图5的仿真结果。

图3 LEACH和GABP算法存活节点关系

从图3可以看出，随着时间的增加，GABP算法节点存活数量始终高于LEACH算法节点存活数量，说明GABP算法在簇首选择方面效果要优于LEACH算法。

图4 LEACH和GABP数据传输班对比

图4 是对基站接收簇首节点数据传输量进行对比，可以看出本文所提算法相比于LEACH算法，基站接收数量值更大。这是由于GABP算法利用遗传算法对BP神经网络的权值和阈值进行优化，可以找到全局最优解，提高选举簇首的有效性。

图5 LEACH和GABP算法能量消耗对比

从图5中可知，随着迭代次数的增加，LEACH算法相比于GABP算法能量消耗速率更大，这是因为遗传算法优化的BP神经网络算法能够更好地融合传感器节点的数据，减少数据传输量，从而提高网络的生存时间。

4 结 语

本文在无线传感器网络拓扑结构基础上，提出一种基于遗传算法优化BP神经网络的分簇路由算法。GABP算法利用GA优化了BP神经网络的权值和阈值，有效提高了BP神经网络的收敛速度和泛化能力，使之簇首选择更合理。与经典的LEACH算法进行综合对比，GABP算法簇首选择过程更优，达到了延长无线传感器网络生存时间的目的。