混沌粒子群和差分进化算法的xmli质心定位算法

混沌粒子群和差分进化算法的xmli质心定位算法

无线传感器网络（无线传感器网络）是由大量传感器通过自组织或多跳转组成的无线网络。它具有高效率和可扩张性，是一种由许多传感器组成的无线网络。传感器类型众多，在军事作战、环境监测、室内监控等领域具有广阔的应用前景。然而在真实环境中抛洒大量带有GPS定位的节点会导致成本过高，并且传感器的使用环境大多较为苛刻，无法保证所有的传感器都带有GPS定位。因此，节点的定位技术成为WSN领域的关键技术之一，而提高节点的定位精度则成为WSN领域中的一大热点。无线传感器网络定位大致分为两类，基于测距的range-based定位与无需测距的range-free定位目前，国内外学者对于传感器网络中的节点定位问题已经取得了诸多研究成果。Singh等传统的质心定位算法的定位原理是将多个锚节点连接起来组成一个多边形，多边形质心的位置即为估算的未知节点的位置，即未知节点的坐标为多个锚节点坐标求和取平均值。质心算法实现容易，耗费成本较低，但定位精度也较低。所以在现有研究的基础上，本文将混合粒子群（Particleswarmoptimization,PSO）与差分进化算法（Differencealgorithm,DE）以及基于RSSI测距的质心算法相结合，建立以未知节点坐标为参数的适应度函数；并利用混沌搜索的随机性、遍历性以及动态变化的惯性权重来提高算法的搜索能力，进一步减小节点的定位误差。1在线搜索算法和xsb1.1自由空间传输模型无线传感器网络中的信号传播模型主要包括3种：自由空间传输模型（Freespacepropagationmodel)式中：PL(d1.2周围锚节点的影响传统的质心算法是由距离未知节点最近的几个锚节点（x质心算法实现简单，但未知节点的定位容易受到周围锚节点数量的影响。周围的锚节点越多，定位精度越高。反之，定位精度则较低。为了防止单个锚节点对未知节点的位置测量影响较大，加权质心算法2优化算法是psode-rri2.1适应度函数的循环迭代适应度函数是节点定位技术中的误差评价标准。为了减小定位误差，需要多次进行循环迭代求出适应度函数的最小值。本文适应度函数的构建选取距离未知节点最近的三个锚节点（x根据RSSI测距得到的三个锚节点与未知节点的真实距离为df值越小，节点定位精度越高。2.2优化差分法的pso-de-原理粒子群算法参数设置简单，搜索速度快，但在种群规模大，搜索空间维度高时，种群中个体的差异会随着时间的推移而减小，从而陷入局部最优解无法跳出。差分进化算法会随机选择种群中的个体来构造差分向量，将产生的变异个体与原始种群中的个体进行交叉操作构造后代，并选择种群中适应度较好的个体来更新种群。粒子群算法进行快速寻优后，可以通过差分进化算法继续进行优化，使得陷入局部最优的个体快速跳出当前区域，进而探索全局最优解。本文采用的PSO-DE-RSSI算法，先通过RSSI测距找到与未知节点最近的三个锚节点，利用三个锚节点构造三角形，并设置群粒子在三角形的质心位置；再将粒子群与差分进化算法相结合并进行混沌搜索，去计算未知节点的位置。PSO-DE-RSSI算法的步骤：步骤1：初始化种群，设置种群规模与最大迭代次数，初始化粒子的位置x(t)与速度v(t)，计算种群中每个粒子的适应度值。步骤2：更新粒子的速度与位置步骤3：计算种群的平均适应度，将种群中适应度值较高的个体执行差分进化算法中的变异、交叉、选择操作。变异：在每次迭代中随机生成三个染色体x交叉：将第t代的种群个体x选择：选择父代个体与交叉后的种群中适应度较小的个体步骤4：将原始种群中低于平均适应度的个体，与经过差分进化算法更新后的种群进行合并。步骤5：在每代的最优解附近进行混沌搜索，将混沌搜索后得到的个体与每代最优解进行适应度比较，取适应度最优的个体。步骤6：判断算法是否满足最大迭代次数，如果满足则比较每代最优解的适应度值，取适应度值最低的个体作为全局最优解输出，否则返回步骤2继续进行迭代。算法流程如图1所示。3提高算法3.1改进的局部搜索能力惯性权重是粒子群算法中评价粒子速度的重要参数，惯性权重越大，粒子的速度越快，粒子的全局搜索能力就会越强。惯性权重越小，粒子的速度越小，粒子就会具有较强的局部搜索能力。惯性权重不变的粒子群算法虽然具有较快的收敛速度，但后期容易陷入局部最优。Shi等提出了惯性权重线性递减的策略式中：ω本文在惯性权重的递减公式中加入正态函数，对式（10）进行改进，让惯性权重按照正态函数递减的方式进行变化，使前期的惯性权重变化较快，算法的收敛速度降低，容易获得局部最优解；使后期惯性权重变化较慢，提高算法的收敛速度。式中：a,b为常数，可根据算法的迭代次数选择不同的值。加入ω3.2混沌算法介绍混沌运动是一种非随机运动，存在于非线性动力系统中，具有随机性和遍历性。混沌运动的遍历性可以帮助算法避免落入局部陷阱。目前，混沌技术已引入到优化算法中，混沌系统动力学模型种类繁多，选用较为经典的Logistic方程式中：c本文在粒子群算法中用混沌变量代替随机变量，并在算法每代最优解附近继续进行混沌搜索，利用混沌变量的随机性与遍历性来提高算法的搜索能力。原始的粒子群算法速度更新为式中：ω是惯性权重；c加入混沌搜索式中：c为了提高算法的深度搜索能力，本文将粒子群与差分进化算法结合后，再在每代的最优解附近进行精细搜索式中：n是在每代最优解附近进行混沌搜索的次数；C4锚节点个数对平均定位误差的影响为了验证本文提出的PSO-DE-RSSI算法的性能，将本文提出的算法与其它算法通过MATLAB仿真实验比较算法的优劣。仿真实验中，在1000m×1000m的正方形区域内随机抛洒1000个传感器节点，包括未知节点与锚节点。节点的分布如图3所示。锚节点周期性地向周围环境发送自身信息，其它节点根据接受的信号强度判断自身与锚节点之间的邻居关系。节点的邻居关系如图4所示。无线传感器网络通常采用平均定位误差作为评价标准。节点的平均定位误差是传感器网络中所有未知节点的定位误差的平均值，定义为式中：N是未知节点的个数；R是节点的通信半径；（x,y）是节点的真实位置；（x改变锚节点的个数与锚节点的通信半径，对比本文PSO-DE-RSSI算法与普通的粒子群算法和基于RSSI的加权质心算法的节点定位误差。节点的参数设置：节点个数300、种群粒子个数20、惯性权重初始值0.9、学习因子2、最大迭代次数500、变异概率0.5、交叉概率0.6。图5是锚节点半径为210m，锚节点个数为90个时的节点定位误差图。图中的实线代表估计的未知节点的位置与节点真正所在位置的距离。实线越短，定位的误差越小。图6是锚节点的个数为90时，通信半径与定位误差的关系。随着通信半径的增大，三个算法的平均定位误差都是呈下降的趋势。因为锚节点的通信半径越大，未知节点周围的锚节点也就越多，更有利于节点定位，也说明锚节点的通信半径影响着节点的定位误差。通信半径相同时，与粒子群算法与基于RSSI的加权质心算法相比，PSO-DE-RSSI算法的平均定位误差最低。这是因为该算法将差分进化与粒子群算法结合，加强了算法的全局寻优能力，避免算法陷入局部最优解的陷阱，该算法可以提高节点的定位精度。图7为锚节点的个数与平均定位误差的关系。随着锚节点个数的增多，三个算法的平均定位误差都在减小。说明锚节点的个数越多，定位精度越高。而本文提出的算法的平均定位误差比基于RSSI的加权质心定位算法下降了10%～15%，比普通的粒子群算法下降了6%左右。5局部最优算法本文将智能优化算法与基于RSSI测距的质心算法相结合，来减小节点的定位误差。粒子群算法虽然搜索速度快、效率高，但容易陷入局部最