改进自适应粒子群算法在WSN覆盖优化中的应用论文

改进自适应粒子群算法在WSN覆盖优化中的应用论文

　　随着计算机网络技术的迅速发展，无线传感器网络(WSN)应运而生。无线传感器网络由多个功能相同或不同的终端传感器节点、路由器和协调器通过自建网络互连的方式组成，它们通过无线通信的方式完成目标监测和信息交互。

　　目前，WSN 网络的节点部署方式可以分为确定性节点部署和自组织节点部署，由于在实际应用中，确定性部署方式存在局限性，自组织节点部署方式得到了广泛的应用。对一个WSN 网络来说，如果能及时检测网络的覆盖率并做有效的调整，能够提高网络中数据的传输质量，减少资源浪费，延长网络生命周期。

　　近年来，许多国内外学者对WSN 网络的覆盖优化策略进行了大量的研究和改进：文献设计了基于共轭梯度法的改进人工萤火虫算法，对WSN 网络节点进行优化后，节点分布均匀，覆盖率较高，但是边界盲区较多;文献提出了基于分群和视野动态调整的改进鱼群算法指导WSN 网络传感器节点的部署，它能使节点较均匀地分布于整个监测区域，相比基本人工鱼群算法的优化结果，覆盖率提高了17.4%;文献在视野自适应变化的基础上将变异因子引入适应度差的个体中，提出了一种改进人工鱼群算法，在WSN 网络覆盖优化应用中取得了不错的效果，提高了网络的覆盖率，然而节点覆盖冗余度较高;文献提出了一种人工鱼群算法与模式搜索法相结合的混合算法，优化后节点覆盖均匀，但存在许多较大盲区;文献通过引入混沌初始化、自适应步长以及视野的机制对人工鱼群算法算法做相应改进，提高了优化稳定性，获得了较高的网络覆盖率，但是边界存在较多盲区，中心冗余度较高;文献提出了一种基于划分搜索空间的粒子群优化算法，算法全局收敛能力较强，能够快速找到覆盖率较高的WSN 网络节点分布，然而算法优化后期局部搜索能力较弱;文献则采用混沌逃逸粒子群优化算法对WSN 网络覆盖率进行优化，效率较高，收敛速度快，但覆盖率较低;文献设计了一种基于逐维判断PSO 算法值的WSN 网络覆盖优化策略，优化效果较理想。

　　然而，这些WSN 网络覆盖优化算法都有一些不足之处，比如改进的人工鱼群算法和萤火虫算法的收敛速度缓慢，虽然能得到较高的WSN 网络覆盖率，但运行时间较长，而改进的粒子群算法虽然收敛速度快，但是稳定性较低，局部搜索能力较差，优化后WSN 网络覆盖率不理想。

　　针对以上算法的不足以及WSN 网络覆盖优化目标，本文设计了基于碰撞回弹策略的一种惯性因子动态变化的自适应粒子群优化算法并应用于WSN 网络的覆盖优化当中，最后通过实验结果验证了本文算法的优越性。

　　1 WSN 覆盖模型

　　1.1 问题分析

　　①由于WSN 网络中每个传感器节点的覆盖范围都是以自身为中心固定半径的圆内，所有传感器节点对监测区域的总覆盖率难以用公式求解，所以，为了简化区域内的覆盖问题，被测区域可以离散化为m × n 个像素点，假设有x 个像素点被WSN网络覆盖，则覆盖率为x/ (m × n) 。

　　②被测区域内WSN 网络所有传感器节点具有相同的感知半径和通信半径，且在通信半径大于等于两倍的感知半径时，假如WSN 网络能够实现对监测区域的感知范围全覆盖，则所有传感器节点必然联通。

　　1.2 覆盖模型描述

　　将被测区域离散化为m × n 个像素点，WSN 网络中有N 个传感器节点，所有节点感知(覆盖)半径均为r 。传感器节点集合为G ={g1, g2,…, gN} ，其中，第i 个传感器节点为gi(i = 1, 2,…, N) ，它的坐标为(xi , yi) 。设像素点H 的坐标为(xH , yH )，则该像素点到第i 个传感器节点的距离为d(gi , H)= (xH - xi)2 + (yH - yi)2 。传感器感知模型这里使用布尔(0- 1) 感知模型，所以像素点H 处被传感器节点i 感知的概率为：

　　一般情况下，一个传感器节点可以被多个传感器节点同时感知，那么像素点H 处的传感器节点被WSN 网络节点集合G 感知的联合概率为：式(3)就是无线传感器网络覆盖优化模型的目标函数。

　　2 粒子群优化(PSO)算法简介

　　粒子群优化(PSO)算法是一种新的全局优化智能算法，它通过个体之间的协作和信息共享来实现对解空间的全局搜索。PSO 算法的优势在于参数少，能够简单容易的实现许多优化问题，目前已经被广泛应用与各种应用领域当中。

　　PSO 算法的数学描述为：假设粒子群中总共有m个粒子，表示为：X = (x1, x2,…, xm)T ;粒子搜索空间为n 维，于是第i 个粒子可表示为：xi = (xi1, xi2,…, xin)T ，(i = 1, 2,…, m) ，同时，它以vi = (vi1, vi2,…, vin)T 的速度飞行，它代表粒子i 每次迭代的移动位移。算法优化过程中有两个最优解，一个是该粒子本身在迭代过程中的最优解，即局部最优解locbesti = (xli1, xli2,…, xlin)T ，另一个是所有粒子在迭代过程中产生的最优解，即全局最优解globest= (xg1, xg2,…xgn)T 。粒子每次迭代的速度vi 通过locbesti 和globest 进行动态更新。第k + 1次迭代的粒子i 第d 维的速度和位置更新的公式为：

　　其中，wk 为第k 次迭代的惯性权重系数，当wk 较大，算法有较强的全局搜索能力，当wk 较小，算法有良好的局部搜索能力，式(6)说明算法在初期具有很强的全局搜索能力，而在后期具有不错的局部搜索能力;c1 和c2 为跟踪局部最优解和全局最优解的学习因子，rand() 为0~1 的随机数;vk + 1id 和vkid 分别为粒子i 在第k + 1次迭代和第k 次迭代中第d 维的速度，xk + 1id 和xkid 分别为粒子i 在第k + 1次迭代后和第k 次迭代后第d 维的位置，xklid 和xkgd 分别表示粒子i 在第k 次迭代中后第d 维的局部最优解和全局最优解，d = 1, 2,…, n ，kmax 为最大迭代次数。

　　由于算法对惯性权重系数wk 的变化非常敏感。而通过公式(5)可以看出wk 只是随着迭代次数的增大而减小，没有考虑粒子群进化程度和聚合程度的实时变化：进化程度包括单个粒子寻优程度、粒子群局部最优平均值寻优程度和粒子群全局最优值寻优程度，聚合程度主要是当前粒子群平均函数值相对于粒子群局部最优值平均值的整体接近程度，因此算法实时性能较差;同时，随着迭代次数的增加，粒子群内多个粒子可能会在搜索空间内出现重叠，需要采取措施将重叠的粒子弹离。

　　3 基于碰撞弹回策略的改进自适应PSO 算法

　　本文将粒子群进化程度和聚合程度引入惯性权重系数中，使之具有很强的自适应能力，利于算法的寻优效果;同时，在算法迭代过程中引入碰撞回弹策略，减小粒子群粒子在搜索空间中的重叠程度，保证粒子群的多样性。

　　3.1 进化因子和聚合因子

　　设粒子xi 第k 次迭代后的函数值为f (xki ) ，局部最优函数值为f (locbestki ) ，第k 次迭代后粒子群全局最优函数值为f (globestk) 。在设计进化因子和聚合因子之前，我们先定义粒子群中第k 次迭代后每个粒子的局部最优值的平均值为：

　　3.1.1 进化因子

　　上节中讲到，进化程度受单个粒子局部最优值寻优程度、粒子群局部最优平均值寻优程度和粒子群全局最优值寻优程度影响。

　　3.1.2 聚合因子

　　上节中讲到，聚合程度主要是当前粒子群平均函数值相对于粒子群局部最优值平均值的整体接近程度。

　　3.2 改进自适应惯性权重系数wi

　　惯性权重系数较大，算法有较强的全局搜索能力;惯性权重系数较小，算法有良好的局部搜索能力。当进化因子较大，粒子群进化程度较差，需要减小惯性权重系数以增强算法局部搜索能力，而当聚合因子较大，粒子群聚合度较高，需要增大惯性权重系数以增强算法全局搜索能力。因此，定义第k 次迭代时粒子i 的改进自适应惯性权重系数公式为：

　　wk

　　其中，w 为原始惯性权重系数(常数)，b1 和b2 分别为进化因子和聚合因子的调节系数，0< b1, b2 < w且b1 + b2 = 1。

　　所以第k + 1次迭代时粒子i 第d 维的改进速度更新公式为：

　　4 WSN 覆盖优化算法设计

　　本文设计改进算法的优化目标为：将第1 节中提出的WSN 网络覆盖优化模型的目标函数(式(3))最大化，输出优化后的网络覆盖率和所有传感器节点的坐标。

　　其中，粒子群中的一个粒子表示WSN 网络所有传感器节点的一个覆盖分布(不是某个传感器节点)。粒子的维数为区域内传感器节点数的两倍，其中第2d - 1维表示第d 个节点的横坐标，第2d 维表示第d 个节点的纵坐标。局部最优值表示每个粒子在经过一定次数迭代后各自达到的网络最大覆盖率，而全局最优值表示经过一定次数迭代后粒子群达到的网络最大覆盖率。

　　在选取碰撞最小阈值Δr 时，首先要确定粒子之间维数对应的两个传感器节点的平均距离平方的最小值r2d ，假设WSN 网络中有x 个传感器节点，则Δr 的取值为：

　　Δr = x·r2d (17)

　　当粒子之间距离小于Δr ，说明两个粒子表示的WSN 网络节点覆盖分布重叠率较高，粒子之间维数对应的两个传感器节点的距离都过于接近。

　　5 仿真实验和分析

　　5.1 实验环境

　　为了验证本文所设计的基于碰撞回弹策略的改进自适应PSO 算法的性能，在VC++6.0 中对其进行仿真实验并通过Matlab 进行展示。同时，通过设置不同的参数值后将实验结果与相关文献算法的仿真结果作对比。

　　5.2 相关参数设置与实验结果对比

　　5.2.1 与文献-4，6-7作对比

　　设监测区域为50 m×50 m 的正方形区域，将其离散化为51×51 个像素点;区域内分布40 个传感器节点，每个传感器节点的感知半径为5 m，通信半径为10 m;参数a1 = 0.2 ，a2 = 0.2 ，a3 = 0.6 ，b1 = b2 = 0.5 ;rd = 10 m，则Δr = 20 。

　　和 分别为本文覆盖优化算法结果和优化后节点覆盖分布图，本文算法与文献，4，6-7算法在相同条件下的优化结果对比如 所示。

　　5.2.2 与文献作对比

　　设监测区域为50 m×50 m 的正方形区域，将其离散化为51×51 个像素点;区域内分布50 个传感器节点，每个传感器节点的感知半径为5 m，通信半径为10 m;参数a1 = 0.1 ，a2 = 0.3 ，a3 = 0.6 ，b1 = b2 = 0.5 ;rd = 12.5m ，则Δr = 25。

　　和 分别为本文优化算法结果和优化后节点覆盖分布图，本文算法与文献算法在相同条件下的优化结果对比如 所示。

　　5.2.3 与文献和文献作对比设监测区域为100 m×100 m 的正方形区域，将其离散化为101×101 个像素点;区域内分布30 个传感器节点，每个传感器节点的感知半径为13 m，通信半径为26 m;参数a1 = 0.2 ，a2 = 0.3 ，a3 = 0.5 ，b1 = b2 = 0.5 ;rd = 30 m，则Δr = 30 。

　　和 分别为本文优化算法结果和优化后节点覆盖分布图，本文算法与文献和文献算法在相同条件下的优化结果对比如所示。

　　5.3 实验分析

　　通过上述仿真实验结果对比可以看出，本文设计的改进自适应PSO 算法在WSN 网络覆盖优化的应用中取得了不错的效果，优化后网络覆盖率都高于97.5%，相比其它文献中的优化结果均有2%以上的提升，且算法容易实现，应用适应性更强。从、、 可以看出，经过本文算法优化，WSN 网络传感器节点分布均匀，基本达到了监测区域全覆盖，虽然图中存在一些较小的覆盖漏洞，但这在无线传感器网络的联通范围内是允许存在的，不会影响WSN 网络的正常运行。

　　6 结束语

　　本文在综合分析粒子群优化(PSO)算法的基本原理和不足之处的基础上，提出了一种改进自适应粒子群优化算法，相比传统PSO 算法，该算法：

　　①将进化因子和聚合因子引入惯性权重系数wi(不同粒子相同迭代次数的惯性权重系数不同)中，实时调整每个粒子的迭代速度。

　　②粒子群迭代后，通过碰撞回弹策略调整所有粒子在搜索空间内的位置，适当增加粒子群的多样性，避免算法陷入局部最优。

　　通过实验结果表明：本文算法有效提高了粒子群对空间的搜索能力，相比其它文献WSN 覆盖优化算法，本文算法对WSN 网络优化后的覆盖率均有2%到6%的提升，且算法容易实现，应用适应性更强。从优化后传感器节点分布图可以看出WSN网络传感器节点分布更加均匀，基本达到了监测区域全覆盖。因此，本文设计的改进自适应PSO 算法能够在一定程度上提高无线传感器网络的性能。

【改进自适应粒子群算法在WSN覆盖优化中的应用论文】相关文章：

初中物理教学中的应用论文05-21

计算机应用中的论文范文05-15

和声理论在高校钢琴教学中应用论文11-19

传感器在生活中的应用的论文05-16

以人为本理念在家具设计中的应用论文05-08

物联网应用论文10-19

【荐】物联网应用论文10-21

[荐]物联网应用论文10-22

计算机应用论文06-25

物联网应用论文(精华)07-21