基于改进布谷鸟搜索算法的WSN覆盖优化策略

作者简介：李思阳（1997-），硕士研究生，从事信息物理系统与无线传感器网络的研究，772073406@qq.com。

引用本文：李思阳.基于改进布谷鸟搜索算法的WSN覆盖优化策略［J］.化工自动化及仪表，2024，51（2）：215-221；300.

DOI：10.20030/j.cnki.1000-3932.202402010

摘 要 针对传感器节点分散不均、覆盖程度低及汇聚层Sink节点冗余等问题，设计了一种双层无线传感器网络覆盖优化方法，该方法对传统布谷鸟搜索算法进行了改进。首先，在种群初始化过程中采用了量子位Bloch球面坐标，可以保持较高的多样性；其次，针对布谷鸟搜索算法的Levy飞行寻优阶段，改进候选解更新方法，随机生成每个纵向维度的新候选解；最后，基于逐维更新贪婪评价策略进行随机游动选择。通过这些改进方式提升了布谷鸟搜索算法的迭代速度和精度，避免相同维度间的干扰。实验结果表明，该改进算法与传统布谷鸟搜索算法、外推人工蜂群算法相比，传感器节点覆盖率分别提高了1.79％和9.87％，汇聚层Sink节点冗余率降低5.13％和21.28％。

关键词 双层无线传感器网络 改进布谷鸟搜索算法（ICS） 量子位Bloch球面坐标 逐维更新

中图分类号 TP29   文献标志码 A   文章编号 1000-3932（2024）02-0215-08

无线传感器网络（WSN）属于信息物理系统（Cyber Physical Systems，CPS）［1］科研领域的重要部分，当前已成为电子与信息技术领域中新兴的科研热点，与众多学科相互交叉，在医疗、军事、建筑［2］以及采矿等场景中具有较高的应用价值。无线传感器网络在结构上划分为多个部分，包括管理、汇聚和传感器节点［3］。多个WSN节点在部署后通过无线通信的方式形成一个多跳自组织网络，WSN节点负责采集和检测被测对象的信息，并将信息转发给Sink节点，Sink节点负责将收集到的数据处理、存储并转发，用户通过管理节点获取数据资源，以上功能实现所需的能量都由电池提供。多层WSN包含传感器层、汇聚层和管理层。

无线传感器通常随机进行抛洒，因此会存在覆盖盲点或集中覆盖等问题，此外还存在汇聚层Sink节点大量冗余的问题。如何提高大规模的WSN节点覆盖率，减少汇聚层Sink节点冗余，是研究大规模无线传感器网络急需解决的问题。采用适应度强、精度高的覆盖优化算法能够有效地解决这些问题。现有的方法和研究已对上述问题做了很多杰出的工作。文献［4］针对原始人工蜂群算法存在的陷入局部最优解和收敛速度慢的问题，设计了一种改进的人工蜂群算法，此算法利用一维高斯变异法提升了网络结构的合理性，改善了网络寿命。文献［5］针对原始鲸鱼算法进行了研究和改进，引入量子位球面坐标进行初始化，之后加入Levy飞行，防止产生局部最优的情况。文献［6］在传统人工鱼群算法的基础上，加入了交叉和再寻优算子来提高搜索的精度，以解决传统人工鱼群在后期寻优处理过程中准确度不高的问题。以上覆盖方式都可以很合理地增加覆盖率，但在算法迭代速率、计算准确度等方面尚有待进一步改善。因此笔者引入布谷鸟搜索（Cuckoo Search，CS）算法，将布谷鸟搜索算法进行改进来解决双层WSN覆盖优化问题。布谷鸟搜索算法的性能在全局搜索和精确度方面明显优于遗传算法［7］、模拟退火算法等，对无线传感器网络覆盖优化的适应程度也具有明显的优势。国内外学者对该算法进行了很多有效的改进并加以应用［8］，如许梦楠和陈兵提出一种按照适应度变动程度自适应调整比例因子的布谷鸟搜索算法，并将其用于车间作业调度优化［9］，该算法提高了找到最优车间作业调度方案的成功率。文献［10］提出一种全新的具有动态发现概率和步长修正因子的布谷鸟搜索算法，优化了磁滞参数辨识模型和磁流变阻尼器的均方根误差。

笔者针对CS算法存在的收敛过早、迭代慢和精度不高的问题进行了研究，提出了有效的解决策略。首先，在种群初始化时利用量子位Bloch球面坐标［11］，通过这种方式可避免种群过于单一的情况；其次，针对布谷鸟搜索算法的Levy飞行寻优阶段，改进候选解更新方法，随机生成每个纵向维度的新候选解；最后，采用逐维更新贪婪评价策略［12］来提升CS算法的迭代速度和精度，避免相同维度间的干扰。在相同环境下进行双层无线传感器网络覆盖优化时，传感器节点覆盖率明显提升，在达到相同覆盖率时，使用该算法优化后的汇聚层Sink节点冗余较少。

1 WSN覆盖模型

1.1 0/1模型及覆盖率

依据相关文献，本研究中的WSN节点模型采用0/1模型［13］。将传感器节点的目标监测区域设置为二维平面，并且将二维平面离散化为L×M的网格，每个网格大小都是1。在二维平面区域Area上，部署N个完全相同的WSN节点，WSN节点集表示为：

Node={Node，Node，…，Node} （1）

将WSN节点的感知半径和通信半径分别设置为R和R，且R≤2R，其中Node定义如下：

Node=（x，y，R）（2）

其中，（x，y）、（x，y）分别代表WSN节点和p点的坐标，二者之间的欧氏距离表示為：

d（Node，p）=（3）

目标节点被WSN节点覆盖的概率P为：

P（x，y，Node）=1，d（Node，p）≤R0，otherwise（4）

所有WSN节点Node在二维平面区域Area上的覆盖率定义为WSN节点的覆盖率与总面积的比R，计算式为：

R（Node）=（5）

笔者以式（5）为区域覆盖率的适应度函数进行优化。

1.2 汇聚层Sink节点覆盖

汇聚层Sink节点［14］用于传感器节点之间的信息管理和信息传输。根据汇聚层Sink节点的工作特点，将传感器节点作为目标节点进行覆盖，静态部署N个传感器节点，形成固定的监控区域。Sink节点占通率R定义为在传感器数量N不变的环境下，相互连通的Sink节点数目与目标传感器之间的比例，即：

R=［P（P（d（Node，Node）≤R）＞0）］/N（6）

R值越高表示目标越分散，需要的Sink节点数目越多；反之，表示Sink节点部署合理，使用较少的Sink节点就能达到覆盖要求。

2 传统布谷鸟搜索算法

CS算法是根据布谷鸟的寄生和雏育行为而提出的元启发式算法。布谷鸟的寄生雏育行为与众不同，它们将蛋放于其他鸟的鸟巢中，通过寄主的蛋来增加自己的蛋孵化成功的概率，小布谷鸟通过发出比其他幼鸟更加响亮的叫声来获取更多的食物，从而增加存活的概率。CS算法遵循以下3个规则：

a. 每只布谷鸟只孵化一次卵，随机挑选一个宿主的鸟巢存放；

b. 随机地选择一个鸟巢存放后，最优的宿主鸟巢更新保存；

c. 每次可选的宿主鸟巢数量都一定，一个宿主找到布谷鸟蛋的概率是Pa。

基于上述3个规则，候选解由鸟巢表示，将CS的基本流程划分为3个部分，如图1所示。

首先，种群初始化以后每个D维向量都可以表示一个巢，计算出所有种群个体的适应度数值，根据适应度数值选出候选解；基于以上步骤得出候选解后，使用蒙特卡洛方法通过模拟Levy飞行，在随机游动过程中得到最新候选解；再通过贪婪选择评价来保存最优解。假设CS在第r次迭代时的第m个候选解为X：

X=（x，x，…，x，…，x），j∈［1，D］（7）

之后，通过随机游动来产生新的候选解

X：

图1 布谷鸟搜索算法流程

X=X+（X-X）·（γ？茚L（β））（8）

其中，X是当前的全局最优解；γ是初始搜索步长；L（β）是Levy飞行随机游动的路径，具体可以定义为：

L（β）～（9）

其中，u、v为服从标准高斯分布的随机数；β为常数1.5；？准可表示为：

？准＝（10）

其中，τ（）为伽马函数。

最后，根据P舍弃部分候选解的同时根据随机游动产生新的解来补缺，该过程表示为：

X=X+σ·（X-X）（11）

其中，σ是算法控制缩放的系数，σ∈［0，1］；X和X分别是第r次迭代时第k个和第s个随机候选解。

更新并保留优秀的解进入下一次迭代，直到符合收敛要求，停止算法迭代。

3 算法改进

3.1 引入量子位Bloch球面坐标

传统算法初始化种群为随机初始化，为了加快收敛速度，提高解的精度，加入量子位Bloch球面坐标，扩展搜索空间和种群多样性。在量子统计中，量子位属于最小的单元，其状态可以表示为：

|φ＞=cos（θ/2）|0＞+esin（θ/2）|1＞（12）

其中，0≤θ≤π，0≤δ≤2π，这两者能够唯一确定球面上一点ρ的坐标，量子位Bloch球面如图2所示。

图2 Bloch球面坐标图

图2中：

|φ＞=［cos φsin θ ？摇 sin φcos θ？摇  cos θ］（13）

每个量子位坐标式都可以通过式（13）表示，再将量子位坐标进行划分。

在CS中，对每个布谷鸟个体都使用球面坐标进行编码，设N为种群中的第i个候选解，则编码为：

N=cos φsin θsin φsin θ   cos θ…cos φsin θsin φsin θ   cos θ（14）

其中，n代表搜索空间维数；φ=2π×rand，θ=π×rand，rand代表随机数，取值在［0，1］之间；i=1，2，…，m，m代表种群大小。

在量子位Bloch球面内的Bloch坐标有3个，各个坐标包括3个解，因此可以得到各个布谷鸟个体覆盖优化的解分别对应着x、y、z解，具体如下：

ρ=（cos φsin θ，…，cos φsin θ）ρ=（sin φsin θ，…，sin φsin θ）ρ=（cos θ，cos θ，…，cos θ）（15）

考虑到连续优化的问题，把每个布谷鸟个体中的3个解从单位空间映射到覆盖优化的解空间中去。布谷鸟个体N上的第j个量子位Bloch球面坐标为［x，y，z］，其解空间表示为：

X=0.5［b（1+x）+a（1-x）］（16）

X=0.5［b（1+y）+a（1-y）］（17）

X=0.5［b（1+z）+a（1-z）］（18）

其中，i=1，2，…，m；j=1，2，…，n；［a，b］是第j个量子位的范围。

3.2 改进Levy寻优

在Levy寻优过程中，传统布谷鸟搜索算法根据适应度函数值从X中选出最优解X，再与

X相减。改进后的布谷鸟搜索算法中的X不再根据适应度值选出，而是将X划分为30个1×80维的矩阵，其中每一个1×80维矩阵中随机的两个纵向维度的值相减得到相应数量的1×80维矩阵，再将这些矩陣重新组合得到X。新得到的X有很强的随机性，这样就大幅提升了寻优过程的可能性，获得解的精度也就更高，式（8）可变为：

X=X+（X-X）·（γ？茚L（β））（19）

3.3 采用逐维更新评价策略

在传统布谷鸟搜索算法中，尽管随机游动可以提高全局搜索能力和种群的多样性，但由于在覆盖优化实验中维度较高，传统算法用于高维度优化，对整个候选解群采用更新评价策略会影响收敛速度和解的精度。加入逐维更新评价策略可以解决这些问题，并避免相同维度之间的干扰。

在随机游动的过程中加入逐维更新评价策略，分别考虑各个维度候选解的更新，当某一个维度的解更新后，将这个解与其他维度的解组合起来得到一个新的解，采用贪婪策略评价这个新的解，只有当这个解被优化达到最优才被保留，否则放弃当前维度的解，进行下一维度的更新。考虑到在随机游动中的步长，γ更新方法是根据随机解进行更新的，不利于局部搜索，因为式（11）中控制縮放的系数σ的范围为［0，1］，限制影响了搜索的方向，将σ的可取值范围调整为

［-1，1］，使单向搜索变为双向搜索，则式（11）可变为：

X=X+σ·（X-X）（20）

3.4 总体改进

首先，在种群初始化阶段加入量子Bloch球面坐标进行初始化，将每个布谷鸟个体映射为3个候选解坐标，扩展了搜索空间和种群多样性；之后，在Levy飞行寻优过程中，改变其更新方式，由原来的选取最优候选解变为随机生成候选解，扩展寻优的可能性；最后，在随机游动过程中加入逐维更新评价策略，将各个维度的解与其他维度的解组合得出新的解，再使用贪婪评价策略对新解进行评价，如果达到最优就保留当前解，否则进行下一维度的更新，加快了迭代速度，提升了解的精度。改进后的算法流程如图3所示。

图3 ICS流程

ICS流程的具体说明如下：

a. 利用量子球面坐标进行初始化，单个个体将生成3个解，例如布谷鸟个体N上第j个量子位Bloch球面坐标为［x，y，z］T，计算每个个体的适应度值。

b. 每个鸟巢产生新的解后，与旧解进行比较，更新当前鸟巢的位置。

c. 在Levy飞行寻优阶段，选出新的候选解，选出的新解不再根据适应度值生成，而是根据随机两个纵向维度生成一个新的X，再根据X生成新解，根据发现概率P保留或舍弃。

d. 进行逐维更新，贪婪评价；对解的每一个维度进行贪婪选择，判断新解是否优于旧解，若优于旧解则更新，反之则舍弃并开始下一维度的比较。

e. 保留最优解，直到满足收敛条件时返回最优解。

4 实验设计与分析

4.1 实验环境

为了验证笔者提出的改进布谷鸟搜索算法在双层无线传感器网络覆盖优化中的性能，将ICS、CS和外推人工蜂群算法（EABC）进行对比实验。实验在MATLAB平台进行仿真，实验环境的详细参数见表1，实验在100 m×100 m的平面区域进行。为了满足R≤2R的条件，设感知半径R为

10 m，通信半径R为20 m，考虑到在汇聚层Sink节点覆盖实验中Sink节点数量会变化，动态设置汇聚层Sink节点个数为0～100个，迭代次数设为400次。

表1 实验环境参数

4.2 算法关键参数

为了使改进布谷鸟搜索算法、传统布谷鸟搜索算法和外推人工蜂群算法［15］更好地适用于无线传感器网络覆盖优化，对以上算法设定相对应的适用于覆盖优化的参数，不同算法的详细参数见表2。

4.3 传感器节点覆盖优化对比与分析

在上述实验环境下，部署35个传感器节点，在面积为100 m×100 m的平面区域里对目标节点进行覆盖优化，进行400次迭代后3种算法的迭代曲线如图4所示。

图4 算法覆盖率对比曲线

分析图4可知，测试环境相同的情况下，ICS的网络覆盖率可以达到87.95％，相较于CS算法与EABC算法，网络覆盖率分别提高了1.79％和9.87％，覆盖率得到了很大程度的提升。在迭代速度上ICS也有明显的优势，迭代到网络覆盖率为82.74％时，ICS与CS分别迭代了88次和147次，而EABC则更差，在第122次迭代时就陷入了局部最优。由此可以表明，ICS无论是在精度还是迭代速度上相较于其他两种算法具有明显的优势。

为了更直观地表现传感器节点的分布情况，采用分布图进行详细比较，如图5～8所示。

由图5可以直观地看出，初始部署的传感器节点分布极为不均匀且重复覆盖较多，有大面积空白区域没有被覆盖到。

图5 初始部署分布图

图6 EABC优化部署分布图

由图6可直观地看出，经过EABC优化后，部署情况有明显地改变，空白区域变少，重复覆盖区域也少了许多，优化有一定的效果。

图7 CS优化部署分布图

由图7可直观地看出，经过CS优化后，部署分布已经十分均匀，空白区域相较EABC优化后更少，重复覆盖区域也更少，优化效果明显。

图8 ICS优化部署分布图

由图8可直观地看出，经过ICS优化后，部署分布更加均匀，几乎已经完全覆盖，重复覆盖区域也更少，优化效果最佳。

4.4 Sink节点覆盖优化对比与分析

为了测试汇聚层Sink节点覆盖WSN节点的程度，减少汇聚层Sink节点冗余，静态部署好

1 000个传感器节点作为目标节点，形成固定监控区域，再用汇聚层Sink节点去覆盖传感器节点，在达到一定要求覆盖率的情况下，对比3种算法优化后所需要的汇聚层Sink节点数目，3种算法优化覆盖的对比如图9所示。

图9 Sink节点变化曲线

由图9可知，ICS算法达到90％覆盖率时只用到了37个汇聚层Sink节点，而CS与EABC算法分别用了39个和47个。结果表明，用ICS算法进行覆盖优化后很大程度减少了汇聚层Sink节点冗余，降低了部署汇聚层Sink节点的成本。

5 结束语

笔者针对传感器节点分散不均、覆盖程度低及汇聚层Sink节点冗余等问题，改进了传统的布谷鸟搜索算法。通过引入量子位Bloch球面坐标、改进寻优过程以及加入逐维更新策略的方法对算法进行改进，经过改进的算法在迭代速度和精度方面有很大程度的提升。

在無线传感器网络相关问题的研究中，覆盖优化问题仅是关键问题之一，要想整体提升网络生命周期需要考虑多个问题。在接下来的研究中，将能耗优化与覆盖优化相结合用以提升整个网络的生命周期可以作为一个研究方向，此外还可以向三维覆盖方向进一步研究。

参 考 文 献

［1］ ZHANG J H，ZHU Y，XIAO F X.Modelling and analysis of real-time and reliability for WSN-based CPS［J］.International Journal of Internet Protocol Technology，2019，12（2）：76-84.

［2］   BENALIA N E-H，MOHAND I S H，FERHATTALEB S，et al.MoEA-DeployWSN-SB：Three variants of multi-objective evolutionary algorithms for the deployment optimization strategy of a WSN in a smart building［J］.International Journal of Information Technology，2022，14（1）：333-344.

［3］   HAO P，CAN L，DANDAN Z，et al.Security Evaluation under Different Exchange Strategies Based on Heterogeneous CPS Model in Interdependent Sensor Networks［J］.Sensors，2020，20（21）：6123.

［4］   陈兰，王联国.极值个体引导的人工蜂群算法［J］.计算机科学与探索，2021，16（11）：2628-2641.

［5］   宋婷婷，张达敏，王依柔，等.基于改进鲸鱼优化算法的WSN覆盖优化［J］.传感技术学报，2020，33（3）：415-422.

［6］   李志武.人工鱼群算法的改进及在无线传感器网络覆盖优化的应用［D］.长沙：湖南大学，2012.

［7］   金合丽，刘半藤，陈唯，等.基于遗传算法的水下传感器网络节点部署算法研究［J］.传感技术学报，2019，

32（7）：1083-1087.

［8］   LIU P，ZHANG S J.A Novel Cuckoo Search Algorithm and Its Application［J］.Scientific Journal of Intelligent Systems Research，2021，11（9）：1071-1081.

［9］   许梦楠，陈兵.改进布谷鸟搜索算法的车间作业调度优化研究［J］.小型微型计算机系统，2021，42（9）：1826-1829.

［10］   ROSLI R，ZAMRI M.Optimization of modified Bouc-Wen model for magnetorheological damper using modified cuckoo search algorithm［J］.Journal of Vibration and Control，2021，27（17-18）：1956-1967.

［11］   李胜，张培林，李兵，等.渐近式Bloch球面搜索的量子遗传算法及其应用［J］.系统工程理论与实践，2016，36（4）：1042-1046.

［12］   张津源，张军，季伟东，等.具备自纠正和逐维学习能力的粒子群算法［J］.小型微型计算机系统，2021，

42（5）：919-926.

［13］   张微微，杨海宁.改进人工鱼群算法的无线传感器网络节点覆盖优化［J］.电子技术与软件工程，2020（12）：24-25.

［14］  ASHOK A K， PATIL B M.Systematic analysis and review of path optimization techniques in WSN with mobile sink［J］.Computer Science Review，2021，41.DOI：10.1016/J.COSREV.2021.100412.

［15］   杜振鑫，刘广钟，韩德志，等.基于全局无偏搜索策略的精英人工蜂群算法［J］.电子学报，2018，46（2）：

308-314.

（收稿日期：2023-04-03，修回日期：2024-02-01）

Optimization of Double-layer Wireless Sensor Networks Coverage

Based on Improved Cuckoo Search

LI Si-yang

（Faculty of Information Engineering and Automation， Kunming University of Science and Technology）

Abstract   Aiming at the  uneven coverage of sensor nodes and redundancy of Sink nodes in the aggregation layer，  the optimization method for two-tier wireless sensor networks coverage  based on improved cuckoo search（ICS）was proposed. Firstly， having quantum-bits Bloch spherical coordinates adopted in population  initialization to expand  search space and population diversity； secondly， in the Levy flight optimization stage of cuckoo search， having the method of updating candidate solutions improved to randomly generate new candidate solutions in each longitudinal dimension； finally， having strategy of updating the greedy evaluation dimension by dimension based  to select  random walk  so as to avoid interference  of  the same dimension， speed up iteration speed and improve  accuracy. Experimental results show that， compared with the original cuckoo algorithm and extrapolated artificial bee colony（EABC）， the sensor node coverage can be improved by 1.79% and 9.87%， and Sink node redundancy in the aggregation layer is reduced by 5.13% and 21.28%.

Key words   double-layer wireless sensor networks， ICS algorithm， quantum-bits Bloch spherical coordinates， updating dimension by dimension