混沌鲸鱼优化算法在WSNs覆盖优化中的应用*

王 鑫, 张 菁

(上海工程技术大学 电子电气工程学院，上海 201600)

0 引 言

随着信息技术的发展，无线传感器网络(wireless sensor networks，WSNs)受到越来越多的关注，并广泛应用于社会日常生活中[1～3]。WSNs节点的部署在WSNs的研究中占据重要地位，影响网络能耗的高低，对网络使用寿命有着直接影响。过高的部署密度会提高网络覆盖率，但伴随着大量冗余节点，增加了能量损耗，因此,如何对网络节点的部署优化已成为WSNs研究中亟需解决的重要问题[4,5]。

现阶段，智能优化算法已被广泛应用于WSNs传感器节点的覆盖优化问题中。文献[6]提出一种萤火虫算法的覆盖优化方法，有效给出节点网络覆盖优化方案，但对移动距离的考量缺乏全面性。文献[7]将节点有效覆盖率作为优化因子构造目标函数，提高了收敛速度和网络节点覆盖率，但对平衡全局探索和局部开发能力缺乏考虑。文献[8]采用一种混合策略改进蚁狮算法对节点部署优化，覆盖率同其他算法相比更高，且优化节点分布更加均匀，但收敛速度有待进一步提高。文献[9]使用一种带状区域的WSNs覆盖部署方法，根据同基站的距离优化簇头节点的数目，有效提高了节点覆盖率，降低了能耗，但对节点覆盖冗余还需进一步考虑。综上所述，WSNs传感器节点的覆盖优化主要集中在如何加快收敛速度、提高网络覆盖率、降低网络能耗等问题中，最终延长网络使用寿命。

本文针对WSNs节点冗余、生命周期短暂等问题，提出一种混合策略改进鲸鱼优化算法(whale optimization algorithm，WOA)的覆盖优化方法。首先提出一种改进Tent混沌映射对种群初始化问题改进，使搜索空间的解分布更加均匀，然后引入莱维飞行对鲸鱼位置更新进行扰动操作，避免算法出现局部最优。

1 WSNs节点覆盖模型

设有面积为S=L×P的二维矩形WSNs监测区域，随机部署N个同构传感器，节点集合为Z={z1,z2,…,zi,…,zN}，每个节点的感知半径Rs和通信半径Rc均一致，Rs≤2Rc。集合中zi的位置坐标为(xi,yi),i=1,2,…,N。传感器节点的感知范围可视为半径为Rs的圆形区域，故可将监测区域转换成m×n个待覆盖的目标点，其集合为K=(xj,yj)，每个目标点的中心点为覆盖优化的目标位置。

设监测区域中zi点位置坐标为zi=(xi,yi)，目标点Qj位置坐标为Qj=(xj,yj)，有节点与目标点间距离为

(1)

目标点被传感器节点感知的概率p(zi,Qj)为

(2)

监测区域中，因目标点可同时被多个传感器节点感知，则WSNs对任意目标点的感知概率为

(3)

该区域中，覆盖率Rcov表示为节点集合Z覆盖的目标点数和该监测区域总目标点数的比值，定义为

(4)

将式(4)作为混沌鲸鱼优化算法(chaotics whale optimization algorithm，CWOA)求解WSNs覆盖优化问题的目标函数，即利用CWOA求解覆盖率Rcov最大值以提高WSNs的覆盖质量，降低节点冗余。

2 CWOA

2.1 基本WOA

WOA是基于座头鲸觅食行为提出的优化算法,依据座头鲸觅食行为的特点，可分为三个阶段：包围猎物、气泡网狩猎和搜索猎物。

2.1.1 包围猎物

在包围猎物阶段，首先需要确定猎物位置再进行包围，WOA假定当前阶段的最优位置为目标猎物的位置，鲸鱼群其它鲸鱼向当前最优位置移动，该描述用数学模型表达为

D=|C·X*(t)-X(t)|

(5)

X(t+1)=X*(t)-A·D

(6)

式中D为当前最优解和搜索目标的距离向量，X*(t)为最优解的位置，X*(t)为搜索目标的位置；t为当前迭代次数；A,C为系数向量，定义为

A=2ar-a

(7)

C=2r

(8)

式中a随迭代次数从2线性递减至0，r为[0,1]中的随机数。

2.1.2 气泡网狩猎

座头鲸的捕食攻击行为，按照WOA可分为螺旋式位置更新和收缩包围两种方式，用数学模型表达有

X(t+1)=D*eblcos(2πl)+X*(t)

(9)

D*=|X*(t)-X(t)|

(10)

式中D*为座头鲸与目标猎物之间的距离；l为[0,1]中的随机数；b为定义对数螺旋形状的常量参数。

为模拟座头鲸在螺旋移动的同时缩小包围，设p为[0,1]中的随机数，则收缩包围和螺旋位置更新的数学模型为

(11)

2.1.3 搜索猎物

在搜索猎物阶段，鲸鱼根据各自位置随机搜索猎物，增强算法对监测区域搜索的全面性，数学模型为

D=|C·Xrand-X(t)|

(12)

X(t+1)=Xrand(t)-A·D

(13)

式中Xrand(t)为种群中座头鲸的随机位置。

2.2 混沌映射初始化

混沌映射具有随机性和遍历性的特性，能更加全面地搜索监测区域，利用该特性对鲸鱼算法的种群初始化，可有效解决普通鲸鱼优化算法中的随机初始化分布不均匀的问题，提高算法在搜索过程中的搜索效率。结合混沌理论和鲸鱼优化算法，在文献[10]中可知帐篷映射(tent map)对WOA搜索性能的提升在所有混沌映射中的最优。故本文选择Tent混沌映射初始化鲸鱼种群，定义为

(14)

式中xn∈[0,1]，系统参数μ=1.99时，Tent混沌映射均匀分布。

虽然Tent混沌映射对WOA搜索性能的提升最优，但映射的迭代过程中存在小周期和不稳定周期，均会迭代到不动点0。为解决上述问题，提出一种将随机因子引入种群位置更新中，定义为

(15)

加入随机因子，使Tent混沌映射在迭代到小周期和不稳定周期时重新进入混沌状态，有效地解决了迭代到不动点的问题，使映射更具遍历性。

2.3 莱维飞行扰动

莱维分布为在动物觅食过程中，下一步行动由当前位置和状态进行预测，可通过数学模型表示。莱维飞行能增加种群多样性和扩大搜索范围，因此采用莱维飞行的智能优化算法更容易跳出局部最优点[11]。

在基本WOA中，随迭代次数的增加座头鲸会向适应度较高的个体靠近，导致算法容易出现局部最优现象。因此，引入莱维飞行对寻优过程中位置更新进行扰动操作，避免算法出线早熟收敛现象。位置更新公式为

Xl(t)=X(t)+α⊕Levy(λ)

(16)

式中Xl(t)为扰动后的位置；⊕为点乘；Levy(λ)为随机搜索路径，表现为随机幂次形式的概率密度函数，即

Levy-u=t-λ，1<λ≤3

(17)

对与莱维分布的随机步长s，使用Mantegna算法进行模拟，公式为

s=μ/|v|1/β

(18)

(19)

为使莱维飞行扰动后的位置优于原位置，对比扰动后和原有位置的适应度，择优选择是否更新位置，数学模型为

(20)

3 覆盖优化策略

基于CWOA的WSNs覆盖优化目标为：使目标监测区域的节点覆盖率Rcov最大化，即将所部署的传感器节点位置优化，求得节点的最优位置。覆盖优化问题可视为以节点覆盖率Rcov为目标函数的高维寻优问题，而节点的搜寻过程，则可视为座头鲸觅食过程中的包围猎物、气泡网狩猎、搜索猎物的行为，所得最优解即各传感器节点部署的目标位置。算法中每头座头鲸代表一种覆盖分布，设节点数为N,则个体维度为2N，其中第2i和第2i-1分别代表节点的横坐标和纵坐标。算法流程如图1所示。

图1 基于CWOA的WSNs覆盖优化

具体算法步骤如下：1)输入WSNs监测区域和CWOA的相关参数；2)将混沌理论结合鲸鱼算法，在监测领域中选择Tent混沌映射初始化鲸鱼种群的个体位置；3)以覆盖率Rcov作为求解WSNs覆盖优化问题的目标函数，利用式(4)计算种群适应度，求得种群当前全局最优解的位置；4)判断随机数p是否高于0.5，若不是,则转Step5;若是,则根据式(9)使鲸鱼在螺旋移动的同时缩小包围；5)根据式(6)更新种群个体向最优个体移动的位置；6)引入莱维飞行，对种群更新后位置使用式(15)进行扰动，并同原位置适应度比较，择优选择；7)判断算法中迭代次数i是否达到最大次数，若是,则输出最优解停止迭代，即输出最优覆盖率和对应节点的位置坐标；若不是，则跳转步骤(3)继续迭代。

4 仿真实验与分析

4.1 实验环境

为验证所提CWOA在WSNs传感器节点覆盖优化的性能，将CWOA同基本鲸鱼优化算法WOA、蚁狮优化(ant lion optimization,ALO)算法和萤火虫算法(firely algorithm,FA)对覆盖优化的性能比较。其中，分别在实验中对各算法选择相同的试验参数。

4.2 实验结果

1)与FA对比

取相同实验参数设置，设监测区域为50 m×50 m的二维平面，传感器节点个数N=30，其感知半径Rs=5 m，通信半径Rc=10 m，迭代次数取1 000次。对比CWOA和FA的覆盖优化程度，覆盖率—迭代次数的变化趋势如图2所示，覆盖优化后节点部署如图3所示，FA、CWOA覆盖率分别为86.1 %和91.3 %。

图2 覆盖优化迭代曲线

图3 优化后节点部署

2)与ALO算法对比

取相同实验参数设置，设监测区域为200 m×200 m的二维平面，传感器节点个数N=50，其感知半径Rs=20 m，通信半径Rc=40 m，迭代次数取1 000次。对比CWOA和ALO算法的覆盖优化程度，覆盖率—迭代次数的变化趋势如图4所示，覆盖优化后节点部署如图5所示，ALO算法、CWOA覆盖率分别为96.7 %和97.4 %。

图4 覆盖优化迭代曲线

图5 优化后节点部署

3)与WOA对比

取相同实验参数设置，设监测区域为100 m×100 m的二维平面，传感器节点个数N=40，其感知半径Rs=10 m，通信半径Rc=20 m，迭代次数取1 000次。对比CWOA和FA的覆盖优化程度，覆盖率—迭代次数的变化趋势如图6所示，覆盖优化后节点部署如图7所示，WOA、CWOA覆盖率分别为92.7 %和95.9 %。

图6 覆盖优化迭代曲线

图7 优化后节点部署

对比不同算法的覆盖优化性能，可见本文所提优化方法在收敛速度和节点覆盖率上更优，充分证明了所提算法对网络覆盖的优化效果。

5 结 论

本文针对WSNs中传感器节点分布不均匀引起的节点覆盖冗余、覆盖率低等问题，提出一种CWOA的传感器覆盖优化方法。该方法在基本鲸鱼算法的基础上，结合混沌理论，选择Tent混沌映射初始化鲸鱼种群，增加种群多样性，有效解决种群随机初始化分布不均匀的问题；引入莱维飞行对寻优过程中位置更新进行扰动操作，避免了算法出线早熟收敛现象。仿真结果表明：同三种常用的覆盖优化算法对比分析，在分别取相同参数情况下，所提改进鲸鱼算法的覆盖优化性能更优，有效提升收敛速度和精度，增加网络覆盖率、降低节点覆盖冗余度。