基于改进粒子群算法的无线传感器网络覆盖优化

梁俊卿

摘 要： 为了解决粒子群算法的无线传感器网络覆盖方法存在的容易出现局部收敛的问题，提出基于改进粒子群的无线传感器网络覆盖优化方法。分析基本粒子群算法进行无线传感器网络覆盖优化的过程，找出其存在的局部收敛问题，通过采用拟万有引力和库仑力两种拟物方案，在粒子速度进化过程中融入拟物力，对基本粒子群算法的速度修正过程实施优化，避免粒子群算法出现局部收敛问题，降低重复覆盖率，完成无线传感器网络覆盖优化。实验结果表明，改进粒子群算法具有更快的收敛效率，对无线传感网络的覆盖优化效果更好。

关键词： 粒子群算法； 无线传感器； 网络覆盖； 收敛效率

中图分类号： TN711?34； TP212.9 文献标识码： A 文章编号： 1004?373X（2017）17?0032?04

Wireless sensor network coverage optimization based on

improved particle swarm optimization

LIANG Junqing

（Institute of Computer Engineering， Qingdao University of Technology， Qingdao 266033， China）

Abstract： Since the traditional wireless sensor network coverage methods are prone to produce local convergence， a method of wireless sensor network coverage optimization based on improved particle swarm optimization is proposed. The process of wireless sensor network coverage optimization based on particle swarm optimization is analyzed to find out the local convergence problem. The schemes of quasi universal gravitation and quasi Coulomb force are used to integrate into the quasi physical force in process of particle velocity evolutionary. The velocity correction process of basic particle swarm optimization algorithm is optimized to avoid the local convergence problem of particle swarm algorithm， reduce the coverage of duplication， and realize the wireless sensor network coverage optimization. The experimental results show that the improved particle swarm optimization algorithm has fast convergence efficiency， and perfect coverage optimization effect for wireless sensor networks.

Keywords： particle swarm optimization algorithm； wireless sensor； network coverage； convergence efficiency

0 引 言

随着科学技术的高速发展，无线传感器网络在工业、农业以及军事等领域具有重要的应用价值。无线网络应用时的网络覆盖问题决定了网络监测质量[1]。高效的无线传感节点分布方案可增强无线传感网络的覆盖率，提高传感器网络资源的利用率，最大化网络使用周期。传统无线传感网络节点分布方法部署了大量的静态节点，这些节点无法解决地形环境以及部署方式的干扰，导致网络通信出现冲突问题[2]，而部署移动传感节点能够解决网络通信冲突问题。受到移动节点成本因素的干扰，应对移动节点位置实施优化，通过有限的节点实现最高的無线传感网络覆盖率，成为相关学者分析的热点问题。

当前基本粒子群算法的无线传感器网络覆盖优化方法存在容易陷入局部收敛的问题，因此，提出基于改进粒子群算法的无线传感器网络覆盖优化方法，实现传感节点的有效部署，最大化传感网络的覆盖率和使用率。

1 改进粒子群算法的无线传感器网络覆盖优化

1.1 基本粒子群算法的无线传感器网络覆盖优化

1.1.1 基本粒子群算法

粒子群算法是一种优化算法，其内各粒子同解区域的一个解对应，粒子按照同伴和自身的检索经验，对当前的位置和速度实施修正[3]。若粒子群中存在个粒子，粒子会按照式（1）对自身位置和速度实施修正：

（1）

式中：和分别用于描述第个粒子的位置和速度；用于描述粒子的过往最佳位置；用于描述全部粒子的过往最佳位置；以及取中的任意数；用于描述惯性权重，也就是学习因子，本文设置其值为1。

1.1.2 粒子编码

进行粒子编码是对粒子的位置和速度实施编码，若无线传感网络内的各点都包括两个位置坐标，将网络覆盖率当成优化目标[4]，则无线传感网络节点最佳分布位置的维数空间是将粒子编码也看成是容量为的向量。向量内的各分量用于描述传感器节点的或方向的位置。各粒子位置的编码如下：endprint

（2）

各粒子速度的编码为：

（3）

粒子群内的全部粒子的位置和速度编码都一致，并独立运算各粒子的位置和速度向量。

1.1.3 适应度函数

对无线传感器网络覆盖实施优化，全面分析网络覆盖率和移动距离的网络覆盖优化目标函数，即适应度函数为：

（4）

式中：Cov用于描述覆盖率；Dis用于描述传感器节点移动距离；用于描述目标范围中的传感器节点数；用于描述目标范围是的矩形区域边长；和分别用于描述覆盖率和移动距离占据的权重。

式（4）综合分析了无线传感网络覆盖区域以及传感节点数量的变化情况。

1.1.4 算法流程

基本粒子群算法流程具体如下：

（1） 对算法参数和传感器节点属性进行初始化设置。

（2） 对粒子群实施初始化设置，在目标区域中，采用个随机数组成个传感器节点的初始位置基于该位置组成的向量对总体粒子群内全部粒子的位置向量实施初始化设置[5]，则粒子群内全部粒子的位置向量为。设置粒子初始速度是0，粒子群内全部粒子的速度向量为。

（3） 采用式（4）的适应度函数运算粒子的适应度值。

（4） 对粒子的速度和位置实施迭代调整，如果算法进行第次迭代，则全部粒子检索的历史最佳位置是用最佳位置替换全局最佳位置gbest。算法进行第次迭代时，采用位置和速度更新方差对全部粒子的位置和速度进行修正，并设置粒子的速度上下限分别是以及位置的上下限分别是posMax以及posMin。

（5） 循环迭代，分析是否符合终止规范要求。若符合，则算法结束，输出全局最佳位置；否则，循环迭代，运行步骤（3）。

1.2 改进粒子群算法的无线传感网络覆盖优化

上述分析的基本粒子群算法在迭代收敛过程中容易出现局部最佳解问题，为了实现无线传感器网络覆盖的优化，本文融合拟物力算法以及粒子群算法提出拟物力导向粒子群算法的无线传感器网络覆盖优化方法，其通过拟物力对粒子群算法的速度修正过程实施优化[6]，提高收敛效率，均衡传感节点间的距离，降低重复覆盖率。

1.2.1 拟物力算法原理

本文针对无线传感器网络区域覆盖问题，提出拟万有引力和库仑力两种拟物方案。

（1） 拟万有引力模型。通过网格法将目标范围均衡地分割成个像素，将各像素作为一个质点，构成个质点，将各传感器节点当成感知半径是的圆。若无线传感网络中没有被覆盖的质点对临近的圆是有价值的，则基于万有引力模型设置第个质点对第个圆的拟万有引力函数为：

（5）

式中：用于描述质点到圆心的距离；用于描述圆的质量；用于描述没有被覆盖的质点对圆形成的引力；对引力的作用区域进行约束[7]。

（2） 构建库仑力模型。各传感器节点当成感知半径为的圆间库仑力，在质点没有被完全覆盖的情况下，不存在库仑力，而当全部质点都被覆盖的情况下，存在的库仑力能够确保圆中的传感节点部署均衡[8]，降低重复覆盖问题，获取最佳的覆盖结果。设置圆间相互排斥的库仑力函数为：

（6）

式中：以及是圆形成的电量；用于描述两个圆心间的距离，可将排斥力的作用区域限制在邻居节点之间。

1.2.2 拟物力导向粒子群覆盖优化方案

拟物力算法可对移动传感节点的散布过程实施调控，通过拟万有引力和库仑力对传感节点的距离实施有效调控，降低重复覆盖率。

（1） 拟物力导向粒子群优化方案设计

融合拟物力算法以及粒子群算法提出拟物力导向粒子群优化方案，分析式（1）可得，粒子群算法的粒子速度进化同粒子最佳位置以及粒子群的最佳位置相关，而粒子的原始位置和速度是随机产生的，若粒子数量较低，则优化效果较差，部分粒子会产生偏离最佳解的退化问题[9]。因此，为了提高粒子群算法的收敛效率，控制粒子向全局最佳解方向进化，拟物力导向粒子群优化方法在粒子速度进化过程中融入了拟物力，具体过程可描述为：

（7）

式中：是粒子的速度；是粒子的历史最佳位置；是粒子自身加速度权重系数；为全局加速度权重系数；是惯性系数；和分别是拟万有引力和库仑力的加速因子；是拟万有引力的价值力因子，其采用式（5）运算出个粒子内的个传感节点对某个像素的万有引力函数值，再采用式（8）运算个像素的万有引力函数值和：

（8）

是庫仑力的价值力因子，其采用式（6）运算出各粒子内某个传感节点对其他传感节点的库仑力函数值，再采用式（9）运算该节点对其他节点的库仑力函数和：

（9）

（2） 拟物力导向粒子群算法的运行过程

在基本粒子群算法内融入拟万有引力以及库仑力，能够降低无线传感网络的重复覆盖问题，提高收敛效率，具体过程为：

① 初始化粒子种群数任意形成个原始解和个原始速度，运算各粒子的原始覆盖率；

② 修正各粒子的速度和位置，运算各粒子新位置的覆盖率；

③ 如果粒子覆盖率高于历史最佳值pbest，则将pbest设置成即刻的适应度；

④ 基于粒子的历史最佳解pbest检索全局最佳值gbest；

⑤ 分析周围是否完全覆盖，融入拟万有引力以及库仑力；

⑥ 循环运行步骤（2）～步骤（5），直至符合终止规范。

2 实验结果与分析

2.1 覆盖性能分析

为了检测本文方法的覆盖性能，在不同原始节点部署状态下，分别进行10次独立的优化实验，本文方法和基本粒子群算法的平均覆盖率、400次迭代平均耗时、平均网络均匀度以及各节点的平均移动距离见表1。endprint

分析表1可得，本文方法的覆盖率比基本粒子群算法提升了8%，并且平均网络均衡度也较低，说明本文方法部署下的无线传感网络的节点分布和能耗更为均衡，并且各节点的平均移动距离降低了4.63 m，解决了节点移动产生的能耗问题。

2.2 覆盖优化效率的分析

实验设置某无线传感器网络的种群数量是13，传感节点的传感半径是2.3 m，分别采用本文方法和基本粒子群算法对无线传感器网络实施覆盖优化，优化后的传感节点位置数据如图1所示。

分析图1可得，基本粒子群算法到达收敛的迭代次数为375次，而本文方法到达收敛的迭代次数为265次，收敛效率提升了34.6%，说明本文方法具有更快的收敛效率，使无线传感器网络覆盖优化效率得到提高。

2.3 不同感知半径下各方法的覆盖性能

实验检测不同感知半径下，本文方法和基本粒子群算法的覆盖率以及迭代次数的变化情况见图2。

分析图2（a）能够看出，本文方法的覆盖率高于基本粒子群方法，当感知半径低于2 m时，两种方法的覆盖率较为相近，当感知半径高于5 m时，两种方法都实现了完全覆盖。分析图2（b）可得，在相同感知半径状态下，本文方法的收敛次数低于基本粒子群算法，具有较强的寻优性能。综合分析图2中的结果可得，本文方法比基本粒子群算法的覆盖率高，迭代次数低，主要是因为本文方法在基本粒子群算法的基礎上融入了拟物力算法，降低了重复覆盖率，提升了覆盖率和收敛率，具有更高的覆盖优化性能。

3 结 论

为了解决基本粒子群算法在迭代收敛过程中出现的局部最佳解问题，本文提出改进粒子群的无线传感器网络覆盖优化方法，该方法拥有较高的全局搜索性能，可更快地获取全局最佳解，增强无线传感器网络的有效覆盖率。

参考文献

[1] 冯秀芳，吕淑芳.基于RSSI和分步粒子群算法的无线传感器网络定位算法[J].控制与决策，2014，29（11）：1966?1972.

[2] 王伟，朱娟娟，万家山，等.基于混沌量子粒子群算法的无线传感器网络覆盖优化[J].传感技术学报，2016，29（2）：290?296.

[3] 丁旭，吴晓蓓，黄成.基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J].电子学报，2016，44（4）：967?973.

[4] 谢佳华，刘军.无线网络通信覆盖优化仿真研究[J].计算机仿真，2015，32（6）：271?275.

[5] 仲元昌，陈锋，李发传，等.大规模无线传感器网络覆盖优化算法[J].传感器与微系统，2014，33（11）：117?120.

[6] 陈麓屹，张翼，戴国勇.融合信任机制和蜜蜂交配优化算法的无线传感器网络能耗均衡分簇方法[J].科学技术与工程，2015，15（3）：105?110.

[7] 王康，王峰，蒋馥珍.基于分跳跳距和粒子群优化算法的DV?Hop定位算法改进[J].计算机测量与控制，2014，22（3）：810?812.

[8] 王芳芳.无线传感器网络中一种基于遗传算法的路由算法研究[J].科技通报，2016，32（5）：82?85.

[9] 陈树，钱成.一种多目标的覆盖优化策略在WSNs中的应用[J].传感器与微系统，2014，33（10）：151?154.endprint