改进自适应粒子群算法在WSN覆盖优化中的应用4046.pdf

《改进自适应粒子群算法在WSN覆盖优化中的应用4046.pdf》由会员分享，可在线阅读，更多相关《改进自适应粒子群算法在WSN覆盖优化中的应用4046.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第 1 页 改进自适应粒子群算法在 WSN 覆盖优化中的应用 目前，WSN 网络的节点部署方式可以分为确定性节点部署和自组织节点部署，由于在实际应用中，确定性部署方式存在局限性，自组织节点部署方式得到了广泛的应用。对一个 WSN 网络来说，假如能准时检测网络的掩盖率并做有效的调整，能够提高网络中数据的传输质量，削减资源铺张，延长网络生命周期。近年来，很多国内外学者对 WSN 网络的掩盖优化策略进行了大量的讨论和改良：文献设计了基于共轭梯度法的改良人工萤火虫算法，对 WSN 网络节点进行优化后，节点分布匀称，掩盖率较高，但是边界盲区较多;文献提出了基于分群和视野动态调整的改良鱼群算法指导 WS

2、N 网络传感器节点的部署，它能使节点较匀称地分布于整个监测区域，相比基本人工鱼群算法的优化结果，掩盖率提高了17.4%;文献在视野自适应改变的基础上将变异因子引入适应度差的个体中，提出了一种改良人工鱼群算法，在 WSN 网络掩盖优化应用中取得了不错的效果，提高了网络的掩盖率，然而节点掩盖冗余度较高;文献提出了一种人工鱼群算法与模式搜寻法相结合的混合算法，优化后节点掩盖匀称，但存在很多较大盲区;文献通过引入混沌初始化、自适应步长以及视野的机制对人工鱼群算法算法做相应改良，提高了优化稳定性，获得了较高的网络掩盖率，但是边界存在较多盲区，中心冗余度较高;文献提出了一种基于划分搜寻空间的粒子群优化算法

3、，算法全局收敛力量较强，能够快速找到掩盖率较高的 WSN 网络节点分布，然而算法优化后期局部搜寻力量较弱;文献则采纳混沌逃逸粒子 第 2 页 群优化算法对 WSN 网络掩盖率进行优化，效率较高，收敛速度快，但掩盖率较低;文献设计了一种基于逐维推断 PSO 算法值的 WSN 网络掩盖优化策略，优化效果较抱负。然而，这些 WSN 网络掩盖优化算法都有一些缺乏之处，比方改良的人工鱼群算法和萤火虫算法的收敛速度缓慢，虽然能得到较高的 WSN 网络掩盖率，但运行时间较长，而改良的粒子群算法虽然收敛速度快，但是稳定性较低，局部搜寻力量较差，优化后 WSN 网络掩盖率不抱负。针对以上算法的缺乏以及 WSN

4、网络掩盖优化目标，本文设计了基于碰撞回弹策略的一种惯性因子动态改变的自适应粒子群优化算法并应用于 WSN 网络的掩盖优化当中，最终通过试验结果验证了本文算法的优越性。1 WSN 掩盖模型 1.1 问题分析 由于 WSN 网络中每个传感器节点的掩盖范围都是以自身为中心固定半径的圆内，全部传感器节点对监测区域的总掩盖率难以用公式求解，所以，为了简化区域内的掩盖问题，被测区域可以离散化为 m n 个像素点，假设有 x 个像素点被 WSN 网络掩盖，则掩盖率为 x/(m n)。被测区域内 WSN 网络全部传感器节点具有相同的感知半径和通信半径，且在通信半径大于等于两倍的感知半径时，假如 WSN 网络能

5、够实现对监测区域的感知范围全掩盖，则全部传感器节点必定联 第 3 页 通。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 感知的概率为：一般状况下，一个传感器节点可以被多个传感器节点同时

6、感知，那么像素点 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=(v

7、i1,vi2,vin)T 的速度飞行，它代表粒子 i 每次迭代的移动位移。算法优化过程中有两个最优解，一个是该粒子本 第 4 页 身在迭代过程中的最优解，即局部最优解 locbesti=(xli1,xli2,xlin)T，另一个是全部粒子在迭代过程中产生的最优解，即全局最优解 globest=(xg1,xg2,xgn)T。粒子每次迭代的速度 vi 通过locbesti 和 globest 进行动态更新。第 k+1 次迭代的粒子 i 第 d 维的速度和位置更新的公式为：其中，wk 为第 k 次迭代的惯性权重系数，当 wk 较大，算法有较强的全局搜寻力量，当 wk 较小，算法有良好的局部搜寻力量，

8、式(6)说明算法在初期具有很强的全局搜寻力量，而在后期具有不错的局部搜寻力量;c1 和c2 为跟踪局部最优解和全局最优解的学习因子，rand()为 01 的随机数;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 只是随着迭代次数的增大而减小

9、，没有考虑粒子群进化程度和聚合程度的实时改变：进化程度包括单个粒子寻优程度、粒子群局部最优平均值寻优程度和粒子群全局最优值寻优程度，聚合程度主要是当前粒子群平均函数值相对于粒子群局部最优值平均值的整体接近程度，因此算法实时性能较差;同时，随着迭代次数的增加，粒子群内多个粒子可能会在搜寻空间内消失重叠，需要实行措施将重叠的粒子弹离。第 5 页 3 基于碰撞弹回策略的改良自适应 PSO 算法 本文将粒子群进化程度和聚合程度引入惯性权重系数中，使之具有很强的自适应力量，利于算法的寻优效果;同时，在算法迭代过程中引入碰撞回弹策略，减小粒子群粒子在搜寻空间中的重叠程度，保证粒子群的多样性。3.1 进化因

10、子和聚合因子 设粒子 xi 第 k 次迭代后的函数值为 f(xki)，局部最优函数值为 f(locbestki)，第 k 次迭代后粒子群全局最优函数值为 f(globestk)。在设计进化因子和聚合因子之前，我们先定义粒子群中第 k 次迭代后每个粒子的局部最优值的平均值为：3.1.1 进化因子 上节中讲到，进化程度受单个粒子局部最优值寻优程度、粒子群局部最优平均值寻优程度和粒子群全局最优值寻优程度影响。3.1.2 聚合因子 上节中讲到，聚合程度主要是当前粒子群平均函数值相对于粒子群局部最优值平均值的整体接近程度。3.2 改良自适应惯性权重系数 wi 惯性权重系数较大，算法有较强的全局搜寻力量;

11、惯性权重系数较小，算法有良好的局部搜寻力量。当进化因子较大，粒子群进化程度较差，需要减小惯性权重系数以增添算法局部搜寻力量，而当聚合因子较大，粒子群聚合度较高，需要增大惯性权重系数以增添算法全局搜寻力量。因此，定义第 k 次迭代时粒子 i 的改良自适应惯性 第 6 页 权重系数公式为：wk 其中，w 为原始惯性权重系数(常数)，b1 和 b2 分别为进化因子和聚合因子的调整系数，0 b1,b2 w 且 b1+b2=1。所以第k+1次迭代时粒子i 第d 维的改良速度更新公式为：4 WSN 掩盖优化算法设计 本文设计改良算法的.优化目标为：将第 1 节中提出的 WSN 网络掩盖优化模型的目标函数(

12、式(3)最大化，输出优化后的网络掩盖率和全部传感器节点的坐标。其中，粒子群中的一个粒子表示 WSN 网络全部传感器节点的一个掩盖分布(不是某个传感器节点)。粒子的维数为区域内传感器节点数的两倍，其中第 2d-1 维表示第 d 个节点的横坐标，第 2d 维表示第 d 个节点的纵坐标。局部最优值表示每个粒子在经过肯定次数迭代后各自到达的网络最大掩盖率，而全局最优值表示经过肯定次数迭代后粒子群到达的网络最大掩盖率。在选取碰撞最小阈值 r 时，首先要确定粒子之间维数对应的两个传感器节点的平均距离平方的最小值 r2d，假设 WSN 网络中有 x 个传感器节点，则 r 的取值为：r=xr2d(17)当粒子

13、之间距离小于 r，说明两个粒子表示的 WSN 网络节点掩盖分布重叠率较高，粒子之间维数对应的两个传感器节点的距离都过于接近。第 7 页 5 仿真试验和分析 5.1 试验环境 为了验证本文所设计的基于碰撞回弹策略的改良自适应 PSO 算法的性能，在 VC+6.0 中对其进行仿真试验并通过 Matlab 进行展现。同时，通过设置不同的参数值后将试验结果与相关文献算法的仿真结果作对比。5.2 相关参数设置与试验结果对比 5.2.1 与文献-4，6-7 作对比 设监测区域为 50 m50 m 的正方形区域，将其离散化为5151 个像素点;区域内分布 40 个传感器节点，每个传感器节点的感知半径为 5

14、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 m50 m 的正方形区域，将其离散化为5151 个像素点;区域内分布 50 个传感器节点，每个传感器节点的感知半径为 5 m，通信半径为 10 m;参数 a1=0.1，a2=0.3，a3=0.6，b1=b2=0.5;rd=12.5m，则 r=25。和 分别为本文优化算法结果和优化后节点掩盖分布图，本文算法与文

15、献算法在相同条件下的优化结果对比方 所示。5.2.3 与文献和文献作对比设监测区域为 100 m100 m 的正 第 8 页 方形区域，将其离散化为 101101 个像素点;区域内分布 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 网络掩盖优化的应用中取得了不错的效

16、果，优化后网络掩盖率都高于 97.5%，相比其它文献中的优化结果均有 2%以上的提升，且算法简单实现，应用适应性更强。从、可以看出，经过本文算法优化，WSN 网络传感器节点分布匀称，基本到达了监测区域全掩盖，虽然图中存在一些较小的掩盖漏洞，但这在无线传感器网络的联通范围内是允许存在的，不会影响 WSN 网络的正常运行。6 结束语 本文在综合分析粒子群优化(PSO)算法的基本原理和缺乏之处的基础上，提出了一种改良自适应粒子群优化算法，相比传统 PSO 算法，该算法：将进化因子和聚合因子引入惯性权重系数wi(不同粒子相同迭代次数的惯性权重系数不同)中，实时调整每个粒子的迭代速度。粒子群迭代后，通过碰撞回弹策略调整全部粒子在搜寻空间内的位置，适当增加粒子群的多样性，避开算法陷入局部最优。第 9 页 通过试验结果说明：本文算法有效提高了粒子群对空间的搜寻力量，相比其它文献 WSN 掩盖优化算法，本文算法对 WSN 网络优化后的掩盖率均有 2%到 6%的提升，且算法简单实现，应用适应性更强。从优化后传感器节点分布图可以看出 WSN 网络传感器节点分布更加匀称，基本到达了监测区域全掩盖。因此，本文设计的改良自适应PSO 算法能够在肯定程度上提高无线传感器网络的性能。