张雪 秦宇祺 张倩倩 黄鹏

摘 要：根据无线传感器网络（WSN）节点在随机部署时存在聚集程度高导致覆盖率低的问题，提出一种改进的自适应灰狼优化算法，并将其应用于无线传感器网络节点的优化覆盖。首先，建立WSN覆盖优化的数学模型;其次，在灰狼优化（GWO）算法中，使用一种非线性收敛因子公式，动态调整算法的全局搜索能力;最后，利用自适应调整策略提高GWO算法的收敛速度。仿真实验表明，将改进的自适应灰狼优化算法应用于无线传感器网络覆盖优化中，比标准灰狼优化算法效果更好，有更快的优化速度，并且网络覆盖率有些许提高。

关键词：无线传感器网络; 覆盖率;灰狼优化算法;非线性收敛因子;自适应;数学模型

中图分类号：TP393文献标识码：A文章编号：2095-1302（2019）10-00-04

0 引 言

随着计算机网络技术的迅速发展，无线传感器网络（Wireless Sensor Network，WSN）应运而生。由大量能量有限的传感器节点以自组织和多跳的方式构成的无线传感器网络以协作感知、采集、处理传感网络覆盖区域被感知对象的信息，并最终把这些信息发送至网络所有者。覆盖控制一直是无线传感器网络的重要问题，它反映了一个无线传感器网络某区域被检测和跟踪的状况。覆盖控制能够合理分配网络资源，从而優化网络覆盖性能[1-2]。近年来，WSN广泛应用于军事、智能交通、环境监控、医疗卫生等领域。但在实际应用中，因为物理环境有所限制，传感器节点多采用随机部署的方式进行播撒，因此存在覆盖盲区，不能有效覆盖待监测区域，从而影响整个无线网络的监控能力。对WSN网络来说，能够及时检测网络覆盖率是否最优并做出有效调整是基本问题，若此问题能够得到有效解决，则网络中数据的传输质量能够明显提高，从而减少网络资源浪费，延长生命周期[3]。

群体智能算法提出了新的思路来解决WSN覆盖优化问题，近年来大量学者将群体智能算法应用于WSN覆盖控制中并研究其性能[4-5]。文献[6]采用遗传算法优化WSN覆盖网络，优化效果较好，但是算法整体上偏复杂，收敛速度较慢。文献[7]提出一种基于划分搜索空间的粒子群优化（Particle Swarm Optimization，PSO）算法，该算法全局收敛能力强，能够快速找到覆盖率较高的WSN网络部署模型，但是算法优化后极易陷入局部最优。文献[8]将变异因子引入适应度差的鱼群个体中，提出一种改进的人工鱼群算法，在WSN网络覆盖优化中取得了较好的优化效果，提高了网络覆盖率，但是节点覆盖冗余度较高。

近几年，大量学者比较关注灰狼优化（Grey Wolf Optimizer，GWO）算法。灰狼优化算法是Mirjalili[9]等人于2014年提出的一种新的群体智能算法，具有模型简单、参数设置较少、寻优性能较好等优点。研究结果表明，GWO算法明显比PSO算法和遗传算法的优化性能更好。因此，GWO算法在多传感器训练[10]、面波参数优化[11]、K-均值聚类优化[12]等领域中有着广泛应用。

虽然GWO算法得到了广泛关注，但也存在一些缺点，如收敛速度慢、全局搜索能力弱等，且在不断迭代中，GWO算法易陷入局部最优。因此，本文提出一种改进的自适应灰狼优化（Self-Adaption Grey Wolf Optimizer，SAGWO）算法，将非线性收敛因子引入GWO算法，以此平衡算法的局部搜索精度与全局搜索能力，并结合适应度构造自适应位置更新策略，提高算法收敛速度。将改进的SAGWO算法应用于无线传感网络覆盖中，并通过实验与基本GWO进行比较。从实验结果可看出，改进的SAGWO算法性能更好，优化效果更好。

1 WSN覆盖模型

无线传感器网络中每个传感节点的覆盖范围都以自身为中心，有着固定半径的圆形区域，因此所有传感器节点对监测区域的总覆盖率用公式求解比较困难。为了简化区域内的覆盖率求解问题，待监测区域可被离散化为m×n个像素点，假设有x个像素点被无线传感器网络覆盖，则覆盖率可表示为x/（m×n）。

假设WSN网络中每个传感器节点的测量半径r与通信半径rs相同，且每个传感器节点覆盖范围是半径为r的圆形区域。被测区域是二维平面M，将这个二维平面离散化为m×n个像素点，无线传感器网络中有N个传感器节点，被测区域内传感器节点集合为，

2 基本灰狼优化算法    

灰狼算法是受到狼群猎食行为的启发，通过模仿狼群中的等级制度与猎食策略提出的一种智能优化算法。

视种群中每个个体为一个解，在D维搜索空间中，第i只灰狼个体的位置为，i=1， 2， ...， N，N为种群规模，选择当前最优解、次最优解、第三最优解所在的狼（分别标记为α，β，δ狼，其余个体标记为ω狼），猎食过程中，狼群在α，β，δ狼的引导下，向食物位置（全局最优解）逼近。

3 改进的SAGWO算法

3.1 非线性收敛因子策略

群体智能算法都存在易陷入局部最优的问题，种群的多样性通过全局搜索能力来保证。而局部搜索能力强则能够保证算法对于局部的精确搜索，且大大加快了算法的优化速度。因此，灰狼优化算法中的全局搜索能力和局部搜索能力之间的平衡极其重要。

采用非线性收敛策略，GWO算法的收敛因子a随着迭代次数呈非线性递减，在初期将a的衰减程度降低，可更好地找到全局最优解，而到了后期，将a的衰减程度提高，则能够更加准确地找到局部最优解，避免陷入局部最优。

3.2 自适应调整策略

GWO算法中适应度值是重要参数。在灰狼个体进行寻优的过程中，α，β，δ的位置对于寻找全局最优的重要性不言而喻。但在GWO算法中，位置更新时并未表现出α，β，δ之间真实的相对关系，仅仅简单地求解其平均值，使搜索范围扩大，减缓了优化速度。

4 SAGWO算法用于WSN覆盖优化

本文设计的改进的SAGWO算法的优化目标：求解无线传感器网络覆盖优化的目标函数的最大值，输出SAGWO优化后的覆盖率，得到待测区域内所有传感节点优化部署后的分布位置。

灰狼种群中包含多个灰狼个体，且每个灰狼个体拥有相同的维数，待测区域为二维平面，则灰狼个体的维数为传感节点数的2倍，其中第2d-1维表示第d个传感器节点的横坐标，第2d维表示第d个传感器节点的纵坐标。

4.1 算法步骤

WSN覆盖优化步骤如下。

（1）设置算法参数：种群规模N、最大迭代次数tmax及a，A，C等参数。

（2）初始化种群X（x1， x2， ...， xD），即随机产生N个智能个体的位置。

（3）计算初始种群中每个灰狼个体的适应度值，选取适应度值前三的个体并分别设置为Xα，Xβ，Xδ。

（4）通过式（8）计算控制参数a的值，根据式（5）更新A，C的值。

（5）由式（9）更新位置。

（6）再次计算每个灰狼适应度值，并更新Xα，Xβ，Xδ，然后选取适应度值较好的灰狼个体。

（7）判断是否满足结束条件。若不满足，则迭代次数加1，返回（3）;若满足，则结束，并输出Xα。

4.2 算法流程

SAGWO算法覆盖优化流程如图1所示。

5 仿真实验与分析 

5.1 实验环境

为了验证本文基于改进的SAGWO算法WSN覆盖优化的性能进行仿真实验。实验的运行环境为Intel? CoreTM i5-4210U CPU @ 1.70 GHz，2.39 GHz，内存8 GB，Windows 1064位操作系统，仿真软件采用Matlab R2016a。

5.2 參数设置与实验结果分析

设监测区域为50 m×50 m的二维平面，将该区域离散化为26×26个像素点。无线传感器节点数为70，节点的感知半径r =5 m，通信半径[17]rs=2r =10 m，算法最大迭代次数Max_iteration=200。

无线传感器网络节点随机部署后，标准GWO算法与改进的SAGWO算法进行迭代优化后的覆盖率对比如图2所示。初始部署如图3所示，GWO优化覆盖如图4所示，SAGWO优化覆盖如图5所示。可以看出，经两种算法优化后的节点覆盖率均有明显提高，SAGWO算法的节点覆盖率甚至达到95%以上。

GWO算法优化后的覆盖率为92.24%，而SAGWO算法优化后的覆盖率为97.78%，SAGWO算法对比GWO算法覆盖率提升了5.54%，节点在待测区域内分布较均匀，但仍有部分区域节点过于聚集。

由于SAGWO算法中引入了非线性收敛因子和自适应位置更新策略，在优化无线传感器节点覆盖率上表现优异，具有优越的全局寻优能力，避免陷入局部最优（即早熟），同时，收敛速度也明显提高，当迭代次数达到30代时，已找到较为优异的值。

从上述实验结果可以看出，SAGWO算法适应性强，优化速度较快，将该算法应用于无线传感网络覆盖优化问题中，能够使网络覆盖率得到明显提高，从而减少覆盖盲区。

6 结 语

本文分析了GWO算法的基本原理和不足之处，在此基础上提出一种改进的SAGWO算法，该算法引入非线性收敛因子，以此避免陷入局部最优，加强了全局搜索能力。同时，结合适应度值，提出自适应位置调整策略，加快了算法的收敛速度，并将SAGWO算法应用于无线传感器网络的节点部署问题中。实验结果表明，SAGWO算法有效避免了陷入局部最优，且加快了收敛速度，对比基本GWO算法，SAGWO算法对无线传感器网络优化后的覆盖率提升了5%，应用适应性强。因此，本文设计的SAGWO算法在一定程度上提高了WSN网络的覆盖性能，但在应用过程中出现了部分区域节点过于聚集的情况，今后的研究方向应使WSN覆盖更为均匀，减少节点聚集的区域。

参 考 文 献

[1] WANG B.Coverage problems in sensor networks： a survey [J]. ACM computing surveys，2011，43（4）： 1-53.

[2]周则顺.无线传感器网络覆盖与连通优化算法的研究[D].武汉：武汉理工大学，2013.

[3] WANG Y，WANG R C，CHENG X.Improved multipath routing with WNN for the open networks [J]. The journal of China universities of posts and telecommunications，2008，15（2）： 107-113.

[4] YOON Y，KIM Y-H.An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks [J]. IEEE transactions on cybernetics，2013，43（5）： 1473-1483.

[5] AKBARZADEH V，GAGNE C，PARIZEAU M，et al. Probabilistic sensing model for sensor placement optimization based on line-of-sight coverage [J]. IEEE transactions on instrumentation and measurement，2013，62（2）： 293-303.

[6]贾杰，陈剑，常桂然，等.无线传感器网络中基于遗传算法的优化覆盖机制[J].控制与决策，2007，22（11）： 1289-1292.

[7]曹剑炜，陈庆奎，庄松林，等.UPSO：基于划分空间粒子群优化的WSN动态覆盖优化算法[J].计算机科学，2014，41（6）： 255-257.

[8]王明亮，闵新力，薛君志.基于改进人工鱼群算法的WSN覆盖优化策略[J].微电子学与计算机，2015，32（6）： 78-81.

[9] MIRJALILI S，MIRJLILI S M，LEWIS A. Grey wolf optimizer [J]. Advances in engineering software，2014，69（7）：46-61.

[10] MIRJALILI S. How effective is the grey wolf optimizer in training multilayer perceptrons [J]. Applied intelligent，2015，42（2）：608-619.

[11] SONG X，TANG L，ZHAO S，et al.Grey wolf optimizer for parameter estimation in surface waves [J]. Soil dynamics and earthquake engineering，2015，75（5）：147-157.

[12]杨红光，刘建生.一种结合灰狼优化和K-均值的混合聚类算法[J].江西理工大学学报，2015，36（5）：85-89.

[13]张娟.基于粒子群优化算法的无线传感器网络节能覆盖研究[D].上海：华东理工大学，2014.

[14] PANDA G，PRADHAM P M，MAJHI B.IIR system identification using cat swarm optimization [J]. Expert systems with applications，2011，38（10）：12671-12683.

[15]郭振州，劉然，拱长青，等.基于灰狼算法的改进研究[J].计算机应用研究，2017，34（12）：3603.

[16]张悦，孙惠香，魏政磊，等.具有自适应调整策略的混沌灰狼优化算法[J].计算机科学，2017，44（11A）： 119-122.

[17] ZHANG H，HOU J.Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc & sensor wireless networks，2005，1（2）：89-124.