宋大鹏 杨晓飞 王 俊 叶 辉
（江苏科技大学电子信息学院 镇江 212100）
移动传感器网络（Mobile Sensor Networks，MSNs）由很多具有特定功能的传感器节点通过移动自组织方式形成的网络系统［1］，可用于国防监控，环境监测和交通等许多领域。区域覆盖率［2］是衡量移动传感器网络质量（Quality of Service，QoS）的一个重要指标。实际部署时，为了保证系统的鲁棒性，往往增加节点的部署密度，但冗余节点存在感知区域重叠导致网络功耗增加，降低了网络整体性能［3］。因此，需要获取最佳的网络覆盖，让一些节点暂时休眠以备不时之需。
在移动传感器网络覆盖优化领域，许多学者采用了一些智能算法来处理，如粒子群优化（PSO）算法［4］、人工蜂群（ABC）算法［5］、蚁狮（ALO）算法［6］、遗传（GA）算法［7］、蚁群优化（ACO）算法［8］等，来获得全局搜索结果。随着问题研究的深入，提出了许多改进算法。在文献［9］中，为了提高粒子群算法的全局搜索能力，在基本粒子群算法中引入了混沌逻辑。文献［10］在混沌逻辑的基础上，提出了种群进化度和相对聚集度来控制惯性权重。在文献［11］中，提出了一种自适应优化算法来优化每个粒子的位置信息，以增强局部搜索能力。文献［12］在算法的迭代过程中引入了碰撞反弹策略，以保证粒子群优化算法的多样性，克服了粒子群优化算法在优化阶段陷入局部最优的弱点。文献［13］中引入了一种动态加速因子策略来搜索局部极值位置，引导其跳出局部最优，但复杂度较高。文献［14］采用混合节点，引入Voronoi多边形的特征来寻找覆盖孔，其大小可以通过轮盘赌来确定。最后采用蜂群算法求解最优覆盖率，对覆盖空洞进行定位和补偿，但收敛速度较慢。文献［15］提出了一种基于混合策略的改进蚁狮算法。利用收缩因子提高了算法的搜索遍历性，加快了算法的收敛速度。
虽然上述学者提出了多种改进算法，但存在种群规模较为庞大，且易陷入局部最优难以跳出等问题，为了实现移动传感器网络的覆盖率最大化，同时使得覆盖更加均匀，本文提出了一种改进型的天牛须搜索算法（IBAS）。通过选用较少的种群规模，利用改进步长和随机方向等函数来平衡全局搜索和局部开发，从而摆脱“早熟”现象，以及基于当前最优值的侦查策略，提高了算法的收敛速度。
移动传感器网络利用移动节点的传感器感知周围信息，需要通过优化算法来设置节点的最佳移动位置来使得传感器网络的整体感知覆盖率最大化。为了解决移动传感器网络的覆盖优化问题，文中建立了各种数学模型。
2.1 模型分析
假设MSNs 是同构的，每个传感器都有相同的通信半径Rc和感知半径Rs，且Rc=2Rs［16］。在面积为L×H 的监测区域内，随机部署N 个传感器节点S={s1,s2,s3,…,sN}，传感器节点si的坐标为(xi,yi)，监测区域中任意一点tj的坐标为(xj,yj)，i,j∈(1,2,…,N)，则节点si到点tj的欧氏距离为
在不失一般性的前提下，建立概率感知模型［17～18］，假定目标点被传感器节点监测到的概率是确定的，即监测到为1，否则为0，这是一种离散化的理想状态模型，一定程度上符合MSNs 的真实覆盖情况。则节点si对目标点tj的监测概率为因此，可得所有节点对点tj的联合感知半径为
2.2 覆盖率
文中所提覆盖率是指所有工作节点覆盖的面积与监测区域总面积的比值，是评价传感器网络QoS 的一项重要性能指标。移动节点的部署位置将很大程度上决定网络覆盖率。为了便于计算感知面积大小，文中将监测区域分为L×H个网格，因此，可以将MSNs 覆盖率定义为被感知到的网格个数与网格总个数的比值［19～20］：
从而，MSNs 的最佳网络覆盖问题可以转化为以式（4）为目标函数的覆盖率parea的优化求解问题。
针对当前部分智能算法在求解移动传感器网络覆盖问题上存在的收敛速度慢、易陷入局部极值和算法复杂度高的问题，本文提出了基于改进型天牛须搜索方法的网络覆盖优化求解算法。
3.1 天牛须搜索算法
经典天牛须搜索算法（BAS）是2017年Jiang等［21］受到天牛觅食原理的启发，提出的一种优化算法。天牛利用两只长触角，如果左触角获得的气味强度高于右触角，则往左搜索，反之往右搜索。该算法不需要知道函数的具体形式和梯度信息，就可以实现高效的全局寻优。相比于粒子群和人工蜂群等算法，该算法的优势在于只需要一个个体，可以使运算量大大降低。
3.2 算法改进过程
1）天牛的觅食行为可转化为n 维移动传感器区域内对目标函数的全局寻优。设置天牛质心在网络中的位置为X，其左右两须分别位于质心两侧，分别为XL和XR，(X、XL、XR)∈Rn。
2）为了提高算法的局部搜索能力，天牛每次前进的方向是随机的，因而从天牛右须指向左须的向量也是随机的，这样可以避免陷入局部最优而停滞。
建立n维单位随机向量并做归一化处理：
式（5）中rands(n,1)表示生成n维随机向量左须、右须的位置分别为
式中为第k迭代次数；
Xk表示天牛在第k次迭代时的质心坐标；
XLk和XRk分别表示天牛左须和右须在第k次迭代时的区域坐标，D为两须间距。
3）本文将式（4）作为算法的目标函数fun(X)，确定左右触角气味的强度，即适应度值大小。分别将左、右须的坐标代入式（4）中，计算出对应的适应度函数值f(XL)和f(XR)：
4）根据左、右须的适应度值的大小关系确定下一步的前进方向：
其中δk表示天牛前进时的步长，Xk+1表示第k次迭代计算后更新的质心坐标位置，sign(.)表示符号函数，当f(XL)≥f(XR)时，sign(.)为负，反之为正。
5）为了提高全局搜索能力，天牛前进时的步长大小需要进行改进，初期阶段步长要足够的大，并且随着时间的推移，步长逐渐减小：
其中，μ是步长的衰减系数，μ∈[0,1]，δk+1是第k次迭代更新后的步长。
根据上式（5）～（9）迭代循环，直到满足终止条件，所得到的天牛质心位置X，即为目标函数的最优解，即最优覆盖率时的节点坐标位置，所设计的改进天牛须搜索算法（IBAS）的流程图如图1所示。
图1 天牛须搜索算法流程图
3.3 算法性能分析
本文采用蒙特卡洛［15］模拟方法验证IBAS 算法的收敛性，为了减轻算法随机性造成的影响，设置50 个节点，感知半径Rs为12，最大迭代次数为1000，进行30次独立实验，实验数据表如下。
由表1 可以看出，本文IBAS 最终可以满足覆盖的要求，实验中的最好覆盖率为98.29%，最差覆盖率为92.36%，而平均覆盖率达到了95.71%。且实验中样本的方差仅仅只有0.00024，表明其波动很小，优化算法的结果很稳定。
表1 随机实验覆盖率统计结果分析
同时，为了保证算法的绝对收敛，防止算法在最优附近“徘徊”，本文设置最大迭代次数，当算法达到最优且不再变化时或算法满足最大迭代次数时，停止该算法。
为了验证算法的性能，假设移动传感器网络监测区域为100×100m 的正方形区域，将其离散化为100×100个网格，在这个区域内随机放置45个传感器节点，每个传感器节点的感知半径Rs为10m，通信半径Rc为20m。IBAS 算法的参数为：步长δ=2*Rs，μ=0.95，最大迭代次数为500次。
4.1 算法均匀度分析
均匀度［20］是衡量网络QoS 的一项重要指标。覆盖均匀度可以保证节点的分布均匀，这样可以使网络能量消耗相对均衡。均匀度一般用相邻节点间距离的标准差来表示。如式（11），标准差越小则覆盖的均匀性就越好。U是整个网络的均匀度。U越小，网络覆盖的均匀性越好。
其中：n 为节点总数；
m 为节点i 的邻近节点总数；
mi为节点i 的邻近节点；
Di,j为节点i 和邻近节点j之间的距离；
Mi为节点i与其所有邻近节点之间距离的平均值；
Ui为节点i的邻近节点均匀度。
如图2和图3分别所示是初始部署节点时和经IBAS 算法优化后的网络覆盖率图像。如果节点间的距离小于或等于通信半径，则互为邻近节点。
图2 初始部署节点
图3 IBAS算法优化
对比图2 和图3，可以直观地观察到网络的覆盖均匀度特征，这两个图说明了我们的IBAS 算法优化的初始分布和后分布的节点分布情况。与图2相比，可以直观地看出，图3中的网络覆盖更加均匀。由于在初始分布时，有许多覆盖和未覆盖的冗余区域。根据式（10）和（11），网络均匀度可计算得出为3.531。而经过IBAS 算法优化后的节点分布更加均匀，其值为2.714，比初始分布低0.817，这与我们从图2和图3中观察到的结果一致。
但由于均匀度反映的是节点的分布程度，即节点间距离的标准差，当节点全部聚集在一起，彼此间的距离没有较大波动，或节点彼此间没有联系时，均匀度就达不到反映均匀程度的理想效果，所以引入均匀率V，即区域覆盖率与均匀度的比值。
Parea为整体网络的覆盖率，V为整体网络的均匀率。当V越大时，则网络整体覆盖越均匀。
根据式（4）可以计算得出图2 和图3 的覆盖率分别为70.80%和91.21%，根据式（12）可以得出其均匀率分别为20.05%和33.61%，相较于初始布点时的均匀率提高了13.56%，由此可以看出经IBAS算法优化后节点覆盖更均匀。
4.2 与其它算法性能对比实验
为了进一步验证IBAS 覆盖优化策略的性能，将本文算法与文献［4］中提出的粒子群PSO算法和文献［13］基于动态加速因子的改进粒子群PSO-DAC 算法，以及文献［21］中提出的标准BAS算法进行实验数据对比。
从表2 展示的结果可以看出，采用IBAS 算法的移动传感器网络覆盖率达到了91.21%，与标准PSO 算法相比提高了11.18%，与改进PSO_DAC 算法相比提高了8.71%，与标准BAS 算法相比提高了4.34%，网络覆盖率得到了明显的改善。而IBAS算法的均匀率为33.61%，相较于PSO 算法、PSO_DAC算法和标准BAS 算法分别提高了9.59%、6.51%和5.01%，由此可见整体网络覆盖更均匀。
表2 相同节点数量的优化覆盖率
为了更加直观地观察覆盖效果，将上述实验结果输出，分别得到45 个初始节点时，PSO 算法、PSO_DAC 算法和标准BAS 算法的直观覆盖效果，如图4～图6所示。
图4 标准PSO算法优化
图5 PSO_DAC算法优化
图6 BAS算法优化
从上面几种算法对应的优化覆盖图可以看出，利用智能算法进行优化后，空白区域逐渐消失，节点分布趋于平均，其中本文提出IBAS 算法的优化效果最佳。
由图7 可以看出：IBSA 算法能够稳定收敛，达到算法的最大覆盖率，最终区域内的覆盖率稳定在91.21%，均匀率为33.61%；
标准BAS 算法的最终覆盖率可以达到86.87%，均匀率为28.60%；
PSO 算法很容易陷入了局部最优，结果导致最终的覆盖率并未超过85%，仅达到了80.03%，均匀率为24.09%；
而PSO_DAC 算法，在基础的粒子群算法上使用动态加速因子的方法来改进局部搜索的能力，虽然覆盖率有所提高，但实验结果表明其最终结果仍不理想，仅为83.50%，均匀率为27.46%。
图7 不同算法迭代收敛对比
4.3 不同网络规模下的对比实验
为进一步验证IBAS 算法在移动传感器网络覆盖中的优化效果，与标准PSO、改进PSO_DAC 算法，以及标准BAS算法在不同网络规模下进行了对比实验，配置参数不变，得到的结果如表3 所示。其中U为均匀度，V为均匀率。
表3 不同节点数量的优化覆盖率
从表3 和图8 中可以看出，在相同配置、不同节点数的条件下，IBAS 算法的覆盖率和均匀率均高于 PSO 算法、PSO_DAC 算法和标准BAS 算法。IBAS 算法不管是在节点数量较多时，还是在节点数较少时均比其他几种算法能更加有效地提高移动传感器网络覆盖率，由此可以说明IBAS 算法的局部搜索能力更强，更容易克服“早熟”，网络覆盖效果更好，覆盖更均匀。
图8 不同节点数的覆盖率对比图
针对移动传感器网络覆盖率问题，本文提出一种改进天牛须搜索（IBAS）算法来解决传感器节点的覆盖优化问题。通过引入步长改进，随机方向函数，以及利用当前最优值的侦查策略来对经典BAS算法进行改进。通过对IBAS算法进行性能讨论和与其它算法进行比对，结果表明：该算法结构简单，不仅提高了搜索空间的遍历性，避免了易陷入局部极值的缺点，而且提升了网络的稳定性和覆盖率，具有较好的实用效果。
猜你喜欢网络覆盖覆盖率天牛民政部等16部门：到2025年村级综合服务设施覆盖率超80%今日农业(2022年15期)2022-09-20我国全面实施种业振兴行动 农作物良种覆盖率超过96%今日农业(2021年21期)2021-11-26天牛到底有多牛小哥白尼(野生动物)(2021年1期)2021-07-16黑黄花天牛小学生必读(低年级版)(2018年10期)2019-01-04巨型昆虫——天牛故事作文·低年级(2018年10期)2018-10-25TD-LTE网络覆盖质量评估浅谈消费导刊(2017年24期)2018-01-31基于感知数据分析的传感器网络覆盖控制电子测试(2017年11期)2017-12-15浅析并线区段的GSM-R网络覆盖调整铁道通信信号(2016年4期)2016-06-01基于喷丸随机模型的表面覆盖率计算方法西南交通大学学报(2016年6期)2016-05-04TD-LTE网络覆盖的分析方法研究互联网天地(2016年2期)2016-05-04
