基于改进布谷鸟搜索算法对水质监测无线传感器部署的优化

胡 坚，胡峰俊，张 红，朱 颖

(1.浙江经贸职业技术学院 信息技术系， 浙江 杭州 310018； 2.浙江树人大学 信息科技学院，浙江 杭州310015)

无线传感器网络(wireless sensor networks，WSNs)是一种分布式传感网络，它的末梢是可以感知和检查一定范围的静止或移动的传感器节点[1-2]。WSNs中的传感器通过无线方式通信，可以跟互联网进行有线或无线方式的连接进而形成一个多跳的自组织网络系统，由于其密集型和随机分布等特点，被广泛应用于环境监测、医疗护理、目标跟踪及交通控制等领域[3-6]。传统传感器节点部署的随机性和盲目性使传感器对目标区域不能进行有效合理的监测，合理的传感器部署方案成为WSNs系统中重点关注的环节。

传感器网络部署是一个优化问题[7]。一个水质监测系统要实现好的监测效果需要对水质监测无线传感器进行合理的部署。目前，众多研究者对WSNs网络部署进行了深入研究，针对不同水域情况，采用适当优化策略对特定区域的传感器节点进行部署，在保证传感器覆盖率最大化的条件下，尽可能少地使用传感器，实现资源的最大化利用。霍慧慧等[8-9]用果蝇算法和鱼群算法对传感器节点进行优化布局，并取得了不错的效果；刘维亭等[10]采用混沌粒子群算法覆盖优化无线传感器网络，该算法的寻优速度较快，但仍旧没有摆脱粒子群算法易陷入局部极值点的缺点；彭丽英[11]提出了基于改进的蚁群算法优化网络节点，该方法局部搜索能力强，但搜索速度较慢。随着优化算法研究的深入，越来越多的优化技术应用于WSNs网络优化部署中。

布谷鸟搜索(cuckoo search， CS)算法是一种全局性能优异的群智能优化算法[12]。为进一步提升CS算法的全局优化性能，提出Momentum-CS、RMSprop-CS与Adam-CS三种改进算法，并将其应用于水质监测无线传感器网络优化部署，以无线传感器网络覆盖率最大为优化目标，布谷鸟个体作为单个传感器，模拟雏鸟不被寄主发现的过程。仿真结果表明，改进的布谷鸟搜索算法在水质监测无线传感器网络优化部署问题中效果提升明显，验证了采用改进布谷鸟搜索算法的有效性。

图1 无线传感器部署示意图Fig.1 Schematic diagram of wireless sensor deployment

1 传感器网络节点部署模型

无线传感器网络在水下环境监测应用广泛，图1所示为水质监测无线传感器节点部署示意图。在无线传感器节点部署问题中，通常采用增加传感器数量以提高水域环境中的网络覆盖问题。然而部署过多传感器会产生大量冗余节点，造成数据传输冲突，浪费资源且影响网络稳定性。因此，在传感器网络布局阶段，同时考虑节点数目和网络覆盖率。

假设每个传感器都有相同的通信半径和感知半径，设s={s1，s2，s3…sn}是一组无线传感器集合，(xi，yi)为集合中任意一个无线传感器节点si的坐标，(xj，yj)为监测区域中任意一点sj的坐标，则节点si到点sj的欧氏距离定义为：

(1)

将监测区域A离散化为个网格点，坐标为(x，y)的K点，判断K点是否被传感器节点si所覆盖，可用式(2)表示：

(2)

对任意的坐标点(x，y)，只要节点C集中存在一个传感器节点使得pcov(x，y，ci)=1，则说明该点至少被一个传感器节点所覆盖，则节点集的联合测量覆盖率Pcov(C)为：

(3)

再把小格点简化成网格点后，无线传感器网络覆盖率定义为被发现的网格个数占总网格个数的比例，即：

(4)

为便于采用优化算法解决水质监测无线传感器网络优化部署问题，定义目标函数如下：

(5)

2 布谷鸟搜索算法

布谷鸟搜索(cuckoo search， CS)算法是由英国学者Yang于2009年受布谷鸟巢寄生育雏行为的启发提出的群智能优化算法[13]。CS算法通过模拟布谷鸟巢寄生育雏行为，结合鸟类、果蝇等的莱维飞行(Lévy flights)机制进行寻优操作，能够快速有效地找到问题的最优解。CS算法的关键参数仅为外来鸟蛋被发现的概率和种群数目，整个算法操作简单、易于实现。CS算法利用莱维飞行进行全局搜索，具有良好的全局寻优能力。为了模拟布谷鸟寻窝的方式，需要设定以下3种理性的状态：1)每只布谷鸟每次随机选择一个巢并且产生一个卵；2)在随机选择的一组寄生巢中，最好的寄生巢将会被保留到下一代；3)可利用的寄生巢数量是固定的，寄生巢的主人能发现一个外来鸟蛋的概率为Pa。

CS算法包括全局搜索的随机游走和局部随机游走，假设一个布谷鸟为x=[x1，x2，…，xD]，则全局搜索的随机游走如式(6)所示[14]：

xg+1，i=xg，i+∂⊕L(ψ) (i=1，2，…n)。

(6)

其中：xg，i表示个鸟巢在第g代的鸟巢位置；⊕表示点对点乘法；∂表示步长控制量即

∂=∂0(xg，i-xbest)。

(7)

其中：xbest为当前最优解；L(ψ)表示莱维随机搜索路径，其是一种随机运动，服从莱维概率分布：

Lévy～σ2=t-ψ(1≤ψ≤3)。

(8)

为方便计算，采用式(9)生成Lévy随机数：

(9)

综上，布谷鸟按式(10)更新位置：

(10)

CS算法按一定概率pa丢弃部分解后，采用式(11)局部随机游走重新生成相同数量的新解:

xg+1，i=xg，i+r(xg，j-xg，k) 。

(11)

其中，r是缩放因子，是(0，1)区间内的均匀分布随机数；xg，i、xg，k表示g代的两个随机数。CS算法流程图如图2所示。

3 布谷鸟搜索算法的改进

CS算法与其他群智能优化算法一样，其优化性能仍存在提升空间。影响CS算法性能的是莱维飞行步长控制量和淘汰概率的选择。CS算法中布谷鸟优胜劣汰的过程是一个不断迭代用优的可行解取代较差可行解的过程，因此提出采用梯度下降法搜索全局最优解的方法。本文通过用动量梯度下降法(gradientdescent with momentum)、均方根算法(root mean square prop)、Adam优化算法(adam optimization algorithm)改进CS算法以提升CS算法的全局优化性能。

3.1 动量梯度下降法

图2 CS算法流程图Fig.2 CS algorithm flowchart

动量梯度下降法的基本思想是计算梯度的指数加权平均数，并利用该梯度更新权重。采用动量梯度下降法改进布谷鸟搜索算法中莱维飞行步长，记作Momentum-CS。该算法中采用动量梯度下降思想更新莱维飞行步长，即每次步长的更新由前一步的步长变化和当前阶段的步长变化共同来决定，如式(12)所示：

Δlx=β1Δlx，t-1+(1-β1)Δlx，t

Δly=β1Δly，t-1+(1-β1)Δly，t

lx=l-ηΔlx

ly=l-ηΔly。

(12)

3.2 均方根算法

均方根算法(root mean square prop， RMSprop)是在梯度下降中，缓解纵向学习率且加速横向学习率，使下降速度变快。采用均方根算法改进布谷鸟搜索算法中莱维飞行步长，记作RMSprop-CS，如式(13)所示：

(13)

其中，dx表示步长在x轴方向的变化率；dy表示步长在y轴方向的变化率；β2是缩放因子；为防止分母为零，保证CS算法稳定，ε是趋于0的正数。

3.3 Adam优化算法

为结合动量梯度下降法与均方根算法的优势，采用Adam优化算法进行CS算法的改进，记作Adam-CS。在Adam-CS中，改进算法融合了动量梯度下降法与均方根算法，并增加修正偏差，在此基础上，采用自适应淘汰概率进一步提升算法的性能。布谷鸟搜索算法中莱维飞行步长更新采用Adam思想：

(14)

由于Adam-CS算法迭代优化过程存在噪声干扰，随着迭代次数的增加，固定淘汰概率值易导致优化结果在最优解附近摆动但不易精确收敛。通常情况，淘汰概率越小易使算法收敛到全局最优解，较大的淘汰概率接受较大步伐。基于此，设计式(15)所示自适应淘汰概率，保证pa在迭代初期具有较大淘汰概率，迭代后期算法开始收敛时具有较小淘汰概率。

pa=0.95iterationpa，0。

(15)

其中，pa，0为初始淘汰概率；iteration为迭代次数，随着iteration的增加，pa成指数下降。

4 仿真实验

本文在监测水域的二维平面内，运用布谷鸟搜索算法对节点进行优化部署。以网络覆盖率最优为目标，采用Adam-CS算法对水质监测无线传感器节点部署进行优化，实现固定同构无线传感器节点下最大化覆盖率。在长宽均为100 m的水域内，以2 m为边长划分网格以计算覆盖率。参数设置如下：传感器半径为10 m、迭代次数为200、最小覆盖率为40%、初始淘汰概率为0.25、β1与β2均为0.9、ε为10～8。改进的CS算法中，步长控制量与淘汰概率pa随迭代次数变化。终止条件为满足最大迭代次数或低于设定覆盖率时结束优化，获得最优解。

图3所示为实验随机生成的30个传感器节点，可以看出，原始传感器分布杂乱，在随机分配传感器的条件下，覆盖率比较低，只有52.17%，难以满足实际工作中传感器网络全方位覆盖的需求。

图4为采用Adam-CS算法优化之后的传感器最优位置分布图。可以看出，优化后的传感器位置分布比较均匀，传感器重合度降低，覆盖率达到90.35%，根据优化得到的水质传感器位置部署传感器节点，可有效提高传感器网络的监测性能。

图3 传感器网络随机分布Fig.3 Randomly distributed of the sensor network

图4 Adam-CS算法传感器优化部署Fig.4 Adam-CS algorithm for sensor optimization deployment

进一步验证改进CS算法的性能，采用CS、Momentum-CS、RMSprop-CS和Adam-CS四种算法进行水质传感器部署优化。4种算法均在相同区域面积部署相同数量及大小的水质监测无线传感器节点。表1中记录了20次独立实验获取的性能指标平均值。图5为4种算法优化传感器网络部署的网络覆盖率与迭代次数的变化曲线。

由表1可知，采用4种算法优化水质监测无线传感器节点部署取得的平均覆盖率均高于随机部署的52.17%，表明采用CS及改进算法优化水质监测无线传感器节点部署是有效的。此外，对比表1中4种算法的优化性能，Momentum-CS与RMSprop-CS相对CS算法的覆盖率指标均有提升，而Adam-CS算法的覆盖率是最高的，达到90.35%，可见Adam-CS算法对于无线传感器节点优化部署问题效果最优。由表1可知，Adam-CS算法平均耗时为57.4 s，优化速度相对其余3种算法更快。图5直观地显示出Adam-CS算法优化无线传感器节点部署取得的网络覆盖率最高、效率更优。

为进一步验证Adam-CS算法优化水质监测无线传感器部署的性能，将Adam-CS算法优化结果与EABC和ESCA算法[15]优化结果进行比较。监测水域仍为长宽100 m的二维正方形平面，该水域中分别放入V=50和V=46个同构传感器节点，Adam-CS、EABC与ESCA优化覆盖率结果如表2所示。由表2可知，在V=50情况下，Adam-CS取得覆盖率相比EABC算法提高了7.61%，很大程度上缩减了无线传感器的覆盖盲区。通过反复实验得知，Adam-CS仅部署30个节点便使覆盖率达到90.35%，相对减小了20个传感器节点；何庆等[15]指出ESCA算法优化达到98.58%的覆盖率很接近，表现出优异的优化性能,能，本研究中Adam-CS的优化结果与此相仿。综上所述，Adam-CS算法能有效地进行水质监测传感器优化部署。

表1 四种算法优化性能对比

Table 1 Comparison of optimization performance of 4 algorithms

算法Algorithm平均覆盖率Average coverage/%最高覆盖率Maximum coverage/%最低覆盖率Minimum coverage/%平均耗时Average time/s最大迭代数Maximum iterated algebraCS83.8986.4679.2192.3138M-CS86.9787.3982.9470.5100RM-CS87.6889.7784.3787.2135A-CS90.3592.2598.9757.498

M-CS，Momentum-CS；RM-CS，RMSprop-CS；A-CS，Adam-CS。

图5 覆盖率趋势图Fig.5 Coverage trend chart

表2 Adam-CS、EABC与ESCA优化覆盖率结果对比

Table 2 Comparison of Adam-CS， EABC and ESCA on optimized coverage results %

算法Algorithm覆盖率CoverageV=50V=46A-CS98.4798.12EABC90.8690.86ESCA98.5897.26

5 结论

针对水质监测无线传感器随机部署网络覆盖率低的问题，采用CS算法进行传感器节点部署优化。为了提升优化性能，文章提出了Momentum-CS、RMSprop-CS与Adam-CS三种改进算法，并将应用于长宽为100 m水域的传感器节点部署优化仿真实验。Adam-CS算法采用动量梯度下降法使寻优过程易跳出局部最优；同时，RMSprop-CS算法引入加快了寻优过程中寻优步长变化，且淘汰率自适应改变都将有效改善CS算法优化性能。仿真结果表明，Adam-CS算法能在98次迭代过程中获得90.35%的网络覆盖率，改进的布谷鸟搜索算法对于水环境监测中无线传感器节点部署具有指导意义。