基于改进天牛须搜索算法的传感器网络覆盖优化策略_宋大鹏.pdf

2023 年第 3 期计算机与数字工程总第 401期2023 年第 3期计算机与数字工程Computer&Digital EngineeringVol.51No.3收稿日期：2022年8月12日，修回日期：2022年9月23日基金项目：国家自然科学基金项目（编号：61903163）；江苏省高校自然科学基金项目（编号：18KJB520010，19KJB510023）资助。作者简介：宋大鹏，男，硕士，研究方向：传感器网络覆盖技术。1引言移 动 传 感 器 网 络（Mobile Sensor Networks，MSNs）由很多具有特定功能的传感器节点通过移动自组织方式形成的网络系统1，可用于国防监控，环境监测和交通等许多领域。区域覆盖率2是衡量移动传感器网络质量（Quality of Service，QoS）的一个重要指标。实际部署时，为了保证系统的鲁棒性，往往增加节点的部署密度，但冗余节点存在感知区域重叠导致网络功耗增加，降低了网络整体性能3。因此，需要获取最佳的网络覆盖，让一些节点暂时休眠以备不时之需。在移动传感器网络覆盖优化领域，许多学者采用了一些智能算法来处理，如粒子群优化（PSO）算法4、人工蜂群（ABC）算法5、蚁狮（ALO）算法6、遗传（GA）算法7、蚁群优化（ACO）算法8等，来获得全局搜索结果。随着问题研究的深入，提出了许多改进算法。在文献 9 中，为了提高粒子群算法的全局搜索能力，在基本粒子群算法中引入了混沌逻辑。文献 10 在混沌逻辑的基础上，提出了种群进基于改进天牛须搜索算法的传感器网络覆盖优化策略宋大鹏杨晓飞王俊叶辉（江苏科技大学电子信息学院镇江212100）摘要为了有效提高移动传感器网络的节点覆盖率，提出一种基于改进天牛须搜索（Improved Beetle AntennaeSearch，IBAS）算法的网络覆盖优化方法。经典天牛须搜索算法根据“食物”气味强弱和利用左右两个“触须”开展搜索觅食。首先通过在搜索阶段引入改进步长和随机方向函数对其进行改进，以平衡算法的全局探索与局部开发能力，使算法能够有效跳出局部最优；其次，采用基于当前最优值的侦查策略，提高算法的收敛速度与精度；最后进行了算法性能讨论和仿真实验。结果表明，相较其它算法，IBAS算法不仅提高了网络节点的覆盖率，而且使得节点分布更加均匀。关键词移动传感器网络；覆盖优化；天牛须搜索算法；改进步长中图分类号TP393DOI：10.3969/j.issn.1672-9722.2023.03.001Coverage Optimization of Sensor Network Based on ImprovedBeetle Antennae Search AlgorithmSONG DapengYANG XiaofeiWANG JunYE Hui（School of Electronic Information，Jiangsu University of Science and Technology，Zhenjiang212100）AbstractIn order to effectively improve the coverage ratio of mobile sensor networks，an optimization method based on theImproved Beetle Antennae Search（IBAS）algorithm is proposed.The beetle can use the left and right tentacles to smell andsearch for food.Firstly，an improved step size and random direction function are introduced into the paper to balance the global andlocal exploration capabilities of the algorithm in the search phase，so that it can effectively jump out of the local optimum.Secondly，the detection strategy based on the current optimal value is adopted to improve the convergence speed and accuracy.Finally，simulation experiment and discussion are made.The results show that，compared with other algorithms，this algorithm not only can improve the coverage ratio，but also make the node distribution more uniform.Key Wordsmobile sensor networks，coverage optimization，beetle antennae search algorithm，improved step sizeClass NumberTP393539第 51 卷化度和相对聚集度来控制惯性权重。在文献 11中，提出了一种自适应优化算法来优化每个粒子的位置信息，以增强局部搜索能力。文献 12 在算法的迭代过程中引入了碰撞反弹策略，以保证粒子群优化算法的多样性，克服了粒子群优化算法在优化阶段陷入局部最优的弱点。文献 13 中引入了一种动态加速因子策略来搜索局部极值位置，引导其跳出局部最优，但复杂度较高。文献 14 采用混合节点，引入Voronoi多边形的特征来寻找覆盖孔，其大小可以通过轮盘赌来确定。最后采用蜂群算法求解最优覆盖率，对覆盖空洞进行定位和补偿，但收敛速度较慢。文献 15 提出了一种基于混合策略的改进蚁狮算法。利用收缩因子提高了算法的搜索遍历性，加快了算法的收敛速度。虽然上述学者提出了多种改进算法，但存在种群规模较为庞大，且易陷入局部最优难以跳出等问题，为了实现移动传感器网络的覆盖率最大化，同时使得覆盖更加均匀，本文提出了一种改进型的天牛须搜索算法（IBAS）。通过选用较少的种群规模，利用改进步长和随机方向等函数来平衡全局搜索和局部开发，从而摆脱“早熟”现象，以及基于当前最优值的侦查策略，提高了算法的收敛速度。2相关问题描述移动传感器网络利用移动节点的传感器感知周围信息，需要通过优化算法来设置节点的最佳移动位置来使得传感器网络的整体感知覆盖率最大化。为了解决移动传感器网络的覆盖优化问题，文中建立了各种数学模型。2.1模型分析假设MSNs是同构的，每个传感器都有相同的通信半径Rc和感知半径Rs，且Rc=2Rs16。在面积为LH的监测区域内，随机部署N个传感器节点S=s1,s2,s3,sN，传感器节点si的坐标为()xi,yi，监测区域中任意一点tj的坐标为()xj,yj，i,j(1,2,N)，则节点si到点tj的欧氏距离为d(si,tj)=(xi-xj)2-(yi-yj)2（1）在不失一般性的前提下，建立概率感知模型 1718，假定目标点被传感器节点监测到的概率是确定的，即监测到为1，否则为0，这是一种离散化的理想状态模型，一定程度上符合 MSNs的真实覆盖情况。则节点si对目标点tj的监测概率为p(si,tj)=1，d()si,tjRs0，otherwise（2）因此，可得所有节点对点tj的联合感知半径为punion()sall,tj=i=1LHp(si,tj)（3）2.2覆盖率文中所提覆盖率是指所有工作节点覆盖的面积与监测区域总面积的比值，是评价传感器网络QoS的一项重要性能指标。移动节点的部署位置将很大程度上决定网络覆盖率。为了便于计算感知面积大小，文中将监测区域分为LH个网格，因此，可以将MSNs覆盖率定义为被感知到的网格个数与网格总个数的比值1920：parea=j=1LHpunion()sall,tjLH（4）从而，MSNs的最佳网络覆盖问题可以转化为以式（4）为目标函数的覆盖率parea的优化求解问题。3算法设计针对当前部分智能算法在求解移动传感器网络覆盖问题上存在的收敛速度慢、易陷入局部极值和算法复杂度高的问题，本文提出了基于改进型天牛须搜索方法的网络覆盖优化求解算法。3.1天牛须搜索算法经典天牛须搜索算法（BAS）是2017年Jiang等 21 受到天牛觅食原理的启发，提出的一种优化算法。天牛利用两只长触角，如果左触角获得的气味强度高于右触角，则往左搜索，反之往右搜索。该算法不需要知道函数的具体形式和梯度信息，就可以实现高效的全局寻优。相比于粒子群和人工蜂群等算法，该算法的优势在于只需要一个个体，可以使运算量大大降低。3.2算法改进过程1）天牛的觅食行为可转化为n维移动传感器区域内对目标函数的全局寻优。设置天牛质心在网络中的位置为X，其左右两须分别位于质心两侧，分别为XL和XR，(X、XL、XR)Rn。2）为了提高算法的局部搜索能力，天牛每次前进的方向是随机的，因而从天牛右须指向左须的向量也是随机的，这样可以避免陷入局部最优而停滞。建立n维单位随机向量并做归一化处理：?dir=rands(n,1)rands(n,1)（5）式（5）中rands(n,1)表示生成n维随机向量宋大鹏等：基于改进天牛须搜索算法的传感器网络覆盖优化策略5402023 年第 3 期计算机与数字工程左须、右须的位置分别为XLk=Xk-?dir*D/2XRk=Xk+?dir*D/2（6）式中为第k迭代次数；Xk表示天牛在第k次迭代时的质心坐标；XLk和XRk分别表示天牛左须和右须在第k次迭代时的区域坐标，D为两须间距。3）本文将式（4）作为算法的目标函数fun(X)，确定左右触角气味的强度，即适应度值大小。分别将左、右须的坐标代入式（4）中，计算出对应的适应度函数值f(XL)和f(XR)：f(XL)=fun(XL)f(XR)=fun(XR)（7）4）根据左、右须的适应度值的大小关系确定下一步的前进方向：Xk+1=Xk-k?dir sign(f(XL)-f(XR)（8）其中k表示天牛前进时的步长，Xk+1表示第k次迭代计算后更新的质心坐标位置，sign(.)表示符号函数，当f(XL)f(XR)时，sign(.)为负，反之为正。5）为了提高全局搜索能力，天牛前进时的步长大小需要进行改进，初期阶段步长要足够的大，并且随着时间的推移，步长逐渐减小：k+1=*k（9）其中，是步长的衰减系数，0,1，k+1是第k次迭代更新后的步长。根据上式（5）（9）迭代循环，直到满足终止条件，所得到的天牛质心位置X，即为目标函数的最优解，即最优覆盖率时的节点坐标位置，所设计的改进天牛须搜索算法（IBAS）的流程图如图1所示。3.3算法性能分析本文采用蒙特卡洛15模拟方法验证IBAS算法的收敛性，为了减轻算法随机性造成的影响，设置50 个节点，感知半径Rs为 12，最大迭代次数为1000，进行30次独立实验，实验数据表如下。由表 1可以看出，本文 IBAS最终可以满足覆盖的要求，实验中的最好覆盖率为98.29%，最差覆盖率为92.36%，而平均覆盖率达到了95.71%。且实验中样本的方差仅仅只有0.00024，表明其波动很小，优化算法的结果很稳定。同时，为了保证算法的绝对收敛，防止算法在最优附近“徘徊”，本文设置最大迭代次数，当算法达到最优且不再变化时或算法满足最大迭代次数时，停止该算法。建立目标函数初始化天牛须算法参数更新随机方向计算天牛左须、右须坐标计算两须的目标函数值更新质心坐标并计算适应度值适应度值提高否改进步长是否记录天牛质心位置满足终止条件是输出最优解和天牛位置图1天牛须搜索算法流程图表1随机实验覆盖率统计结果分析次数30数量50半径12最好98.29%最差92.36%均值95.71%方差0.000244仿真