基于粒子群算法的wsn覆盖优化研究

基于粒子群算法的wsn覆盖优化研究

0wsn覆盖优化方法无线传感器网络（wsd）由大量廉价微型传感器节点组成，通过无线通信完成目标监控和信息采集任务。对网络覆盖的测量能够使人们了解监测区域的网络覆盖状况,重新调整传感器节点分布或者指导在将来添加传感器节点时可采取的改进措施,保证测量数据的可靠性,减少资源浪费,延长网络寿命。近年来,国内外学者在WSN覆盖控制方面进行了大量研究,取得了一定进展。暴露穿越覆盖控制算法采用分布式执行方式,从而得到精度不同的暴露路径。最坏与最佳情况覆盖算法,在最佳与最差两种度量条件下分别得到了临界的网络路径规划结果,指导网络节点的配置。在国内,刘永生等人用随机调度子集划分最优解的方法优化覆盖率;Wang等人提出了两种移动节点的部署方法;周彤等人提出了基于虚拟力的混合感知网络节点部署方法。标准粒子群算法在空间搜索时,粒子向自身历史最佳位置或群体历史最佳位置聚集,限制了粒子的搜索范围。为了避免陷入早熟,就要增加种群的粒子数或者减弱粒子对当前种群搜索到的全局最优位置的追逐,而增加粒子数将导致算法复杂度加大,减弱粒子对全局最优点的追逐使得算法不易收敛。本文所提出的基于碰撞理论的分簇粒子群覆盖优化策略(CCPSO)是在标准粒子群算法的基础上,采用分簇思想和碰撞策略调整传感器节点,使整个网络覆盖性能得到优化。1无线传感器网络系统的模型和问题描述1.1基于多个传感器节点同时测量目标的方法假设二维平面监测区域P被数字离散化为m×n个像素,该目标在该区域上参数相同的传感器节点数目为N,每个节点的坐标均已知,感知半径均为r。传感器节点集表示C={c1,c2,c3,…,cN},点A被ci所覆盖的事件发生的概率ρcov(x,y,ci)表示为其中:ci=(xi,yi,r)表示以节点坐标(xi,yi)为圆心,感知半径为r的圆;为像素点A(x,y)与ci之间的距离。基于二元感知模型,文献提出了一种采用多个传感器节点同时测量监测目标的方法来提高监测目标的测量概率。其中ρcov(C)为节点集联合测量概率。1.2基于区域覆盖率对于区域覆盖率的研究,文献提到将目标区域离散为许多格点,用所有格点被传感器节点覆盖的覆盖率来代表目标区域的区域覆盖率,从而将区域覆盖率的问题转换为点覆盖的问题。由于节点集C的区域覆盖率R(C)为节点集C的覆盖面积与监测区域P的总面积之比,监测区域P被数字离散化为m×n个像素。用节点集联合测量概率衡量每个像素点是否被传感器节点集所覆盖,得到节点集C的区域覆盖率:基于以上理论,得出区域覆盖率的计算步骤如下:a)根据式(1)计算一个像素点对每个传感器节点的覆盖率。b)根据式(2)计算一个像素点对传感器节点集合的联合覆盖率。c)重复步骤a)和b)计算监测区域每一个像素点对传感器节点集C的联合覆盖率。d)根据式(3)计算传感器节点集C的区域覆盖率R(C),并将R(C)作为以后覆盖优化算法的优化目标函数。2基于冲突理论的集群颗粒群算法2.1u3000无线传感器网络的局部寻优算法粒子群算法(PSO)是目前普遍应用的用于解决多目标优化问题的经典算法之一。其基本思想是随机初始化一群没有体积、没有质量的粒子,将每个粒子视为优化问题的一个可行解,粒子的好坏由一个事先设定的适应度函数来确定。每个粒子在搜索空间中以一定的速度飞行,并根据对个体和群体的飞行经验综合分析来动态调整速度。每一代中,粒子将跟踪两个极值,一个是粒子本身迄今为止找到的最优解,另一个是整个群体迄今为止找到的最优解。假设一个由m个粒子组成的群体在n维搜索空间以一定的速度飞行,粒子i在t时刻的状态属性设置如下:第i个粒子在n维空间的当前位置为Xi=(Xi1,Xi2,Xi3,…,Xin),第i个粒子在n维空间的当前飞行速度为Vi=(Vi1,Vi2,Vi3,…,Vin),第i个粒子经历的最好位置为Pi=(Pi1,Pi2,Pi3,…,Pin),也是微粒i所经历的具有最好适应值的位置,称为个体最好位置pbest。设f(x)为最大化的目标函数,根据优化目标不同f(x)也有不同定义。在无线传感器网络中,f(x)通常是指传感器节点的覆盖率,则微粒i的当前最好位置由下式确定:该群体所有m个粒子中经历过的最好位置为Pg(t),即全局最好位置gbest,满足粒子在t+1时刻的位置更新通过下式获得:其中:i表示第i个粒子,j表示粒子所搜索空间的维数;t表示迭代次数;c1是粒子自身加速度权重系数,c2是全局加速度权重系数,通常取c1=c2=2;r1、r2为均匀分布在(0,1)区间的随机数;w为惯性权重系数,计算公式为其中:t为当前迭代次数,tmax为算法的总迭代次数。Shi指出较大的权重有利于展开全局寻优,较小的权重有利于局部寻优。式(8)使粒子群算法在初期有良好的全局搜索性能,后期具有良好的局部搜索性能。2.2基于约束弹离的分簇粒子群算法为了克服粒子群早熟现象,避免算法过度复杂化,本文将搜索空间划分为多个簇,并根据粒子的位置判定其属于哪个簇。每次对粒子位置和速度进行更新的时候,用簇中心来代替簇内粒子的全局最佳位置。算法对各簇中的粒子群进行独立优化,使其在追逐个体最佳位置的同时向簇中心靠拢;同时为了避免簇内粒子覆盖重叠,设计了碰撞弹离策略。粒子a、b的距离可以由欧式距离公式算出:其中:Δr为本文设定的阈值,Xa、Xb、Va、Vb分别为a、b的位置和速度。当d(Xa,Xb)<Δr时,就判定这两个粒子即将碰撞,采用弹离策略将其弹开。弹离距离大小为该方向上速度乘以一个随机因子:其中:k=1,2,…,n;rand为0~1的随机数。弹开后的粒子a、b的位置更新为粒子与边界的碰撞原理与此类似,如果粒子下一次更新的位置超过了目标区域,就判断粒子与边界发生了碰撞。按照反向弹离策略,也朝原运动方向反向弹离一段距离,粒子c与边界发生了碰撞,位置更新为其中:Δd(Xck)=Vck×rand,k=1,2,…,n。基于碰撞理论的分簇粒子群算法进行覆盖优化的基本过程如下:a)在目标区域初始化m个传感器节点,随机产生每个传感器节点的位置和速度,并且将目标区域划分成若干个簇。b)通过粒子坐标判断其属于哪个簇。c)对每个簇中的各个粒子,按式(6)~(8)更新速度和位置。d)对各个粒子,判断其位置是否越界,如果该粒子位置Xi离开了目标区域,则粒子位置不更新并且按照式(11)反向弹离一段距离。e)对m个传感器节点分别计算两两节点间的距离,判断是否发生碰撞,如果满足碰撞条件,按照式(9)(10)更新其位置。f)根据优化目标函数计算每个传感器节点的覆盖率。g)根据优化目标函数计算该传感器节点集的区域覆盖率。h)更新后的传感器节点集的区域覆盖率与节点集最好位置矩阵pbest的区域覆盖率相比较,如果较好,则重新设置pbest。i)如果达到停止条件(预设最大迭代次数)停止运算,返回结果;否则返回步骤b)继续运行。3根据冲突理论，集群颗粒联合算法的覆盖优化实验3.1仿真结果分析为了考察分簇数对无线传感器网络覆盖性能的影响,对改进的粒子群覆盖算法进行仿真。仿真环境为MATLAB7,参数设置为:边长100m的正方形测量区域中布置30个无线传感节点,传感节点感知半径r=13m,,碰撞阈值为7m,最大迭代次数为300。粒子群分簇数分别为1、4、9、16。图1~8及表1显示了不同分簇数时的仿真结果。以上仿真结果显示,当分簇数为1时,虽然碰撞理论在一定程度上避免了群体粒子对全局最优位置的追逐,从图1看,粒子覆盖的重叠性依然较高,覆盖率仅有90%;分簇数为4后,将目标区域内粒子网格化,每个网格独立优化,减弱了整个目标区域内所有粒子的快速趋同,图3中无线传感器网络节点分布更加均匀,图4覆盖率曲线比图2提高了4%;继续增加簇数到9簇,图6显示覆盖率没有明显提高,这是因为簇数变大一方面提高了算法的复杂度,增加了迭代次数,另一方面,粒子碰撞的空间减小,碰撞性能发挥不佳;簇数为16时,图7显示重叠度增加,图8显示覆盖率只有89.5%,这是因为粒子活动范围更促狭,粒子向簇内的全局最优位置靠拢。基于以上仿真条件和结果,选定分簇数为4时最优。3.2仿真结果分析通过改变不同的阈值对传感器节点的布局以及覆盖率进行研究,分析碰撞阈值Δr对传感器节点覆盖率的影响。在边长100m的正方形测量区域中随机布置30个无线传感节点,传感节点感知半径为r=13m,c1=c2=2,最大迭代次数为300,分簇数为4。图9~22及表2显示不同Δr值的仿真结果。由表2看出,当碰撞阈值Δr从4m变化到7m时,传感器覆盖圆分布均匀,覆盖率从82.5%增大到94%,迭代次数减少了20次。碰撞阈值Δr从7m变化到10m时,传感器覆盖范围变化不明显,而迭代次数增加了85次,影响了算法的执行效率。由于传感器网络节点寿命有限,从优化覆盖和节约系统资源两方面综合考虑,选取Δr=7m比较合适。3.3节点重叠区的表征基于碰撞理论的分簇粒子群算法覆盖与标准粒子群算法覆盖性能比较如图23、24所示。图23中,传感器节点分布不是十分均匀,节点重复严重,目标区域边界吸附着很多节点,较多的区域没有被覆盖。这是由于标准粒子群算法没有限制粒子之间的距离和粒子与边界的距离,标准粒子群算法对全局最优位置的追逐容易导致早熟,形成多节点重叠区。图24中,传感器节点分布均匀,靠近边界的的节点较少,粒子重复覆盖部分较少。这是由于基于碰撞理论的分簇粒子群覆盖算法采用了分簇的思想,独立优化每个网格内的粒子群,减弱了早熟的趋势。碰撞策略的引入限制了粒子的过度重叠及靠近边界。本文提出的基于碰撞理论的分簇PSO算法(CCPSO)与标准粒子群算法(SPSO)、文献中的粒子进化的多粒子群算法(MPSO)、拟物力导向的粒子群算法(VMFPSO),以及文献中的传统遗传算法(CGA)、新量子遗传算法(VMFPSO)在相同条件下覆盖性能比较如表3所示。从表3的比较可以得出,本文所提出的CCPSO算法在覆盖性能方面比基本粒子群算法提高了30%,比粒子进化的多粒子群算法提高了4.5%,比拟物力导向的的粒子群算法提高了3%、比传统遗传算法提高了6%,比新量子遗传算