一种面向无线传感器网络能量均衡问题的优化方法

摘要

本发明公开了一种面向无线传感器网络能量均衡问题的优化方法，该算法在执行优化过程，分为三个阶段：首先在第一阶段优化过程中，以收敛性选择机制为主导，选择收敛性较好的解。然后，在第二阶段优化过程中，利用多样性维护机制来保留多样性较好的解。此外，利用综合度量方法旨在保证种群进化在第三阶段优化过程中解的收敛性与多样性的平衡。为了验证所设计算法的优越性，将其在基准测试函数上与另外五种先进的高维多目标优化算法进行了仿真比较。并且，最终的仿真结果实现了预期的效果要求。

说明书

技术领域

本发明属于人工智能领域，将无线传感器网络能量均衡问题归结为一个高维多目标优化问题(Many-objective optimization problems,MaOPs)，并设计一种高效高维多目标优化算法来优化求解无线传感器网络能量均衡问题。

背景技术

物联网技术的快速发展衍生出无线传感器网络(Wireless Sensor Network，WSN)，WSN是由数千个分散的微低功耗传感器节点和一个无线通信汇聚节点组成的自组织多跳网络系统，也是无线通信的重要组成部分。它们对于许多应用程序都极具应用价值，例如医疗保健应用程序、民用应用程序和军事应用程序。无线传感器网络节点可以收集物理区域的信息，然后将其进行处理并传输到基站。然而，在无线传感器网络中需要考虑许多需求，比如低延迟的数据传输、长生命周期的系统以及易于处理的平稳部署。因此，网络中传感器节点的主要目标是实现数据的快速处理、事件检测和数据传输。传感器网络节点中的电池在环境传感、军事监视、国土防御等应用中难以更换，因此，无线传感器网络存在能量消耗问题，网络中的能量消耗主要体现在计算、传感和通信方面。

针对WSN的特点，国内外学者提出了一些先进的低功耗路由协议，能提高网络生命周期。根据其拓扑结构，将无线传感器分为平面路由协议和分层路由协议(集群路由协议)。分层路由协议作为WSN路由协议的一个重要研究分支，具有降低能耗，延长网络生存周期，最小化时延等优点，这使目前的WSN路由协议成为研究的重点和热点。该分层协议不仅有利于分布式算法的应用，而且适用于大规模的网络应用。为此设计一种高效的数据传输和转发机制对WSN具有重要意义。Heinzelman等人提出的低能耗自适应聚类层次(LEACH)协议。Kulik提出了SPIN协议，Ossama提出了HEED协议。LEACH作为第一个被提出来的分层路由协议，具有降低能耗、延长周期、操作简单等优势，从而引申出许多分层路由协议。因此，选择LEACH协议进行研究具有一定的优势和典型性。

LEACH作为最初的分层路由协议，提出了网络集群的概念。其主要思想是将网络划分为不同规模的簇，并选择节点作为簇头，有效地平衡网络的能耗。然而，LEACH协议也存在簇内不均匀性、簇头选择随机性、网络周期较短等问题。

国内外学者提出了利用优化算法来优化LEACH的性能，并取得了相应的结果。Cui等人提出了一种结合质心策略的蝙蝠算法(WHCBA),通过将WHCBA协议集成到LEACH协议中，提出了两阶段簇头节点选择策略来减少能耗。Cai提出了一种改进的融合曲线策略快速三角翻转蝙蝠算法，提高了选择簇头的局部和全局搜索能力，延长了网络的生存期。Jourdan首次采用遗传算法优化WSN的能量。使用二进制代码将节点划分为簇头节点和簇成员节点。然后利用遗传算法选择最优染色体，通过染色体解码得到最优网络。

近年来，随着人工智能的兴起，学者们提出了利用优化算法来优化LEACH的性能，并取得了相应的结果。Cui等人提出了一种结合质心策略的蝙蝠算法(WHCBA),通过将WHCBA协议集成到LEACH协议中，提出了两阶段簇头节点选择策略来减少能耗。Cai提出了一种改进的融合曲线策略快速三角翻转蝙蝠算法，提高了选择簇头的局部和全局搜索能力，延长了网络的生存期。Jourdan首次采用遗传算法优化WSN的能量。使用二进制代码将节点划分为簇头节点和簇成员节点。然后利用遗传算法选择最优染色体，通过染色体解码得到最优网络。

本发明将无线传感器网络能量均衡问题归结为一个高维多目标优化问题(Many-objective optimization problems,MaOPs)，并考虑将簇成员节点到簇头节点的距离，簇头节点到基站的距离，网络总能耗与网络能耗负载均衡作为待优化的四个目标，同时设计了一种面向无线传感器网络能量均衡问题的高维多目标多阶段优化算法。该算法主要分为三个部分:第一阶段为收敛性优化、第二阶段为多样性优化和第三级为综合性优化。然而，优化的每个阶段目的都是使种群向最优方向进化，保证最终获得种群解的收敛性和多样性平衡。具体的原理细节将在下面的内容中描述。

发明内容

本发明提出了一种面向无线传感器网络能量均衡问题的高维多目标多阶段优化算法(Many-objective Algorithm with Stage Optimization,MaOEA-MuS)，其特征在于所提出的算法在执行优化过程，分为三个阶段：首先在第一阶段优化过程中，以收敛性选择机制为主导，选择收敛性较好的解。然后，在第二阶段优化过程中，利用多样性维护机制来保留多样性较好的解。此外，利用综合度量方法旨在保证种群进化在第三阶段优化过程中获得求解方案的收敛性与多样性的平衡。

(1)MaOEA-MuS算法框架

在设计的求解面向无线传感器网络能量均衡问题算法中，首先，初始化一个随机种群，采用一般的遗传操作生成子代个体，如模拟二进制交叉(Simulation BinaryCrossover,SBX)和多项式变异(Polynomial Mutation,PM)。然后执行分阶段优化操作：在第一阶段，为了加快获得无线传感器网络能量均衡问题解决方案，促使得到更好收敛性的种群，采用I

Step1：初始化种群P及相关参数；

Step2:利用模拟二进制和多项式变异等操作作用于种群P从而产生子代个体Q；

Step3:然后依次采用分阶段优化选择机制，挑选收敛性和多样性较好的解；

Step4:反复执行Step3直至达到最大迭代次数，输出最优解，作为无线传感器网络能量均衡方案。

(2)阶段优化一：收敛性优化

在第一个优化阶段，旨在挑选具有收敛性好的种群个体进入下一代，I

其中，M表示为簇成员节点到簇头节点的距离，簇头节点到基站的距离，网络总能耗与网络能耗负载均衡待优化的四个目标；x

Step1：输入父代种群V和子代种群W；

Step2：依据pareto支配关系验证两种群中个体支配情况。如果非支配解位于V种群中，则相应的解将被保留。否则，将非支配解从W移动至V种群中；

Step3:计算种群V中所有个体I

Step4:按照I

Step5:输出此次迭代优化最优解V；

Step6:利用SBX和PM等操作产生新的子代个体W；

Step7:完成此次迭代，检查是否满足算法结束条件，如果不满足就转至Step2。

(3)阶段优化二：多样性优化

由于在MaOEA后期阶段选择压力的降低，多样性维护机制一直是解决MaOPs的挑战。而基于距离的多样性度量机制近年来逐渐被证明在解决MaOPs中是有效的，并开始广泛使用。受此启发，MaOEA-MuS算法采用L

Step1：输入父代种群W和子代种群A；

Step2：依据pareto支配关系验证两种群中个体支配情况。如果非支配解位于W种群中，则相应的解将被保留。否则，将非支配解从A移动至W种群中；

Step3:计算种群W中所有个体L

Step4:按照L

Step5:输出此次迭代优化最优解决方案W；

Step6:利用SBX和PM等遗传操作产生新的子代个体；

Step7:完成此次迭代，检查是否满足算法结束条件，如果不满足就转至Step2。

(4)阶段优化三：综合性优化

一方面为了再次验证经过两个阶段的优化过程，所获得的解决方案是否基本满足收敛性和多样性。在第三阶段优化过程中采用了一种综合的选择度量机制增强种群进化后期的选择压力。反转世代距离(Inverse Generation Distance,IGD)度量作为一种综合评价方法，在许多研究中被广泛用于衡量算法性能。这里我将其作为第三阶段的优化度量选择机制。具体地，IGD的计算公式如下：

其中，n是理想无线传感器网络能量均衡问题解决方案PF*中解的个数，d

Step1：输入父代种群A和子代种群R；

Step2：依据pareto支配关系验证两种群中个体支配情况。如果非支配解位于A种群中，则相应的解将被保留。否则，将非支配解从R移动至A种群中；

Step3:计算种群A中所有个体IGD值；

Step4:按照IGD值依次进行升序排序，并且删除种群中IGD值最差的个体；

Step5:输出此次迭代优化最优解A；

Step6:利用SBX和PM等遗传操作产生新的子代个体；

Step7:完成此次迭代，检查是否满足算法结束条件，如果不满足就转至Step2。

通过以上多阶段优化操作，将会设计的MaOEA-MuS算法与常见的三种先进MaOEAs进行比较，如NSGA-III、PICEA-g、SPEA/R。最终结果表明，MaOEA-MuS算法在求解无线传感器网络能量均衡问题的过程中，具有最多存活节点数量及节点剩余能量，即在执行过程中消耗了更少的能量，可以很好地延长生命周期。不仅减少了簇成员节点到簇头节点的通信距离,也减少簇头结点到基站节点的距离。来避免通信过程中的能源浪费，提高能源的使用效率，从而达到延长网络生存周期的目的。MaOEA-MuS算法存活节点数最多，网络生存周期最长。其主要原因是多阶段优化策略合理优化簇头的选择，让网络能量消耗更加均衡，从而减少网络总能量消耗。

附图说明

图1：LEACH协议流程图。

图2：MaOEA-MuS算法流程图。

具体实施方式

下面结合相关附图对本发明进行解释和阐述：

(1)测试函数

本发明为验证MaOEA-MuS算法在优化求解无线传感器网络能量均衡问题性能，选用MaF1-MaF9基准问题用于测量算法性能，这是广泛使用的测试函数DTLZ的改进版本。这9个测试函数在复杂帕累托解、不规则帕累托最优前沿、多峰等环境下被证明能有效验证算法性能。因为每个MaF测试问题在目标空间的维度包含不同的问题规模,在提出的方法中，每一代的进化过程，计算欧式距离或角度之前,我们需对每个目标值的解都进行归一化处理，其中每个解的第i个目标值都除以2i，i＝1,…,M。具体来说，每个问题都在不同的目标数5、8、10和15上测试和执行。群体大小分别对应设置为210、156、275和135。为了使结果令人信服，每个测试问题独立运行20次。

(2)参数设置

为了检验我们所设计算法的性能效果的有效性，分别将MaOEA-MuS与多种性能效果高效的算法进行了比较，包括NSGA-III、PICEA-g和SPEA/R。同时为了得到令人信服的结果，所有的关键参数都是按照它们的原始文献设置的。本文的所有实验均在处理器为IntelCore i5,CPU频率为3.10GHZ，内存为4G,操作系统为Windows10,软件版本为Matlab 2016b环境下运行，算法平台使用PlatEMOv1.6。并且对于不同目标数量的问题，这里我们也采用不同的种群大小。当目标数为3、5、8、10和15时，种群大小分别设置为91、210、156、275和135。而NSGA-III和PICEA-g都分别采用双层参考点机制，SBX和PM的概率分别为1和1/D(D表示决策变量的维度)。最大迭代次数被视为所有算法的停止条件，被设置为10000。此外，每个算法对所有测试函数都独立执行20次。并且无线传感器网络仿真参数设置如表1所示。

表1无线传感器网络仿真参数设置

(3)相关算法比较

本发明选用综合性评价指标IGD作为无线传感器网络能量均衡性能指标，具体的比较结果如表1所示，对MaF函数测试集进行了20次独立仿真，得到的性能指标IGD的均值和标准差。并且高亮显示了不同测试实例的最佳结果。基于Wilcoxon的秩和Friedman统计检验，标签“+”、“-”和“＝”分别表示不同算法得到的结果优于、劣于或等于我们的方法得到的结果。

表2不同算法在DTLZ上对IGD值比较结果

根据表1中的观察，设计的方法MaOEA-MuS在36次比较中的20次中获得了最佳结果；PICEA-g在11次比较中表现最佳；NSGA-III和SPEA/R分别在4个和2个问题上取得了最佳结果。因此，这些可以解释我们的方法与其他算法相比具有良好的性能优势。特别是，当MaF1有5，8，15个目标时NSGA-III和PICEA-g的性能明显优于MaOEA-MuS。这是因为NSGA-III和PICEA-g的选择策略在进化的某些阶段具有先进性。此外，它们在处理MaOPs的复杂PF方面也有比较好的表现。因此，MaOEA-MuS无法在MaF5上获得所有目标的最佳结果。然而，对于剩余的MaF函数，可以发现比较算法的最佳性能仅类似于MaOEA-MuS。这主要是因为多阶段选择机制可以有效地选择分布性和收敛性更好的无线传感器网络能量均衡解决方案。所涉及的算法采用单一阶段的帕累托排序或分解方法来选择更好的解决方案，引导种群向一个获得更好的无线传感器网络能量均衡问题解决方案的方向进化，不能为真正的帕累托最优前沿提供足够的选择压力。

因此，总体上MaOEA-MuS的性能效果优于NSGA-III、PICEA-g和SPEA/R算法性能，而这几种算法已经被证明在求解无线传感器网络能量均衡问题上具有明显的有效性，从而说明MaOEA-MuS在求解无线传感器网络能量均衡问题上具有更优越的性能。