基于改进粒子群优化的无线传感器网络定位算法.docVIP

基于改进粒子群优化的无线传感器网络定位算法 摘要:无线电干涉定位系统获取的干涉距离是4个传感器节点间距离的线性组合值。针对以两个节点间距离作为输入的传统定位算法无法直接利用上述干涉距离进行定位的问题，提出一种基于改进粒子群优化的定位方法。利用干涉距离的实验数据，分析比较了遗传算法和改进粒子群优化在无线传感器网络节点定位问题中的性能。结果表明，基于改进粒子群优化的定位方法的平均耗费时间远远小于基于遗传算法的定位方法，具有更高的优化效率。 关键词:无线传感器网络；干涉定位；粒子群优化；遗传算法 1引言 在无线传感器网络(WSN)的各种应用中，监测到事件之后人们关注的一个重要问题即是该事件发生的位置。因此，位置信息是传感器节点采集数据中不可缺少的部分，没有位置信息的监测通常毫无意义。确定事件发生的位置或采集数据的传感器节点位置是WSN最基本的功能之一，对WSN应用的有效性起着关键的作用。 近年来，越来越多的应用对定位精度不断提出更高的要求，从低精度区域定位，到米级，甚至厘米级、毫米级的高精度无线空间三维定位。如何提高节点定位精度已成为当前WSN定位技术的研究热点。 Maroti等人以新的实现形式将传统的无线电干涉原理应用到无线传感器平台上，组建了无线电干涉定位系统(RIPS)。实验表明，在多径效应很小的理想环境下，该系统的定位精度可达到厘米级，从而证明该原理很有可能实现高精度的定位目标。目前，该方法距离实用化还有一段距离，存在许多关键问题需要解决。 RIPS中获得的干涉距离是4个传感器节点间距离的线性组合值dABCD，即两个发送节点A和B以及两个接收节点c和D间距离的线性组合值，计算方法如图1所不，其中dij为两个节点间的距离，而且是未知的。 现有的定位算法都是以两个节点间的距离dij作为输入，无法直接利用上述干涉距离dABCD计算节点 图1干涉距离 位置。 Maroti等人采用基于遗传算法的最优化方法有哪些信誉好的足球投注网站节点坐标的近似值，但是遗传算法的复杂度高且收敛速度较慢。对此，木文采用计算简单、收敛速度快的粒子群优化方法有哪些信誉好的足球投注网站节点坐标的近似值，并利用干涉距离的实验数据分析比较两种最优化方法在RIPS节点定位问题中的性能。 2基于遗传算法的RIPS节点定位 2．1遗传算法 1975年Michigan大学的Holland教授提出了遗传算法 (GA)，这是一种基于自然选择和基因遗传学原理的高度并行性全局有哪些信誉好的足球投注网站算法。GA由代表问题所在解集的一个种群开始，该种群由经过基因编码的一定数目的个体组成。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。如同自然进化一样，后代种群比前代种群更加适应环境。该过程循环执行直到满足结束条件。末代种群中的最优个体经过解码便可作为问题的近似最优解。 2．2基于遗传算法的定位方法 给定n个待定位节点和一组干涉距离测量值M,待定位节点i的三维坐标为(Xi Yi Zi)。其中:0≤ Xi≤X_MAX, 0≤ Yi≤Y_MAX, 0≤Zi≤Z_MAX,x_max,y_max,z_max为节点坐标允许的最大取值，由定位算法的有哪些信誉好的足球投注网站空间决定。基于无线电干涉测距的定位问题可描述为如下的最优化问题: 其中:s为GA中的一个个体，即解空间的一个解，亦即所有待定位节点的坐标集合｛(Xi Yi Zi)｝i=1,…,n; m为M干涉距离的数量;dABCD为测量得到的干涉距离，dABCD 为根据s计算得到的干涉距离。 基于GA的定位方法采用式(1)的误差函数作为适应度函数.为了获得充分的定位约束条件，需要对不同的节点组合进行多次测量.基于GA的定位方法通过有哪些信誉好的足球投注网站寻找使测量得到的干涉距离和计算得到的干涉距离误差最小的节点坐标近似值.基于遗传算法的定位方法具体步骤如下: Step1:生成初始种群，群体规模大小为populationSize。 Step2:在初始种群中随机选择得到被选种群，群体规模大小为subpopulationSize。 Step3:用式((1)评估被选种群中的所有个体。 Step4:根据误差大小对被选种群按升序排列。 Step5:淘汰掉被选种群中最差的20%个体，从最好的20%个体中随机选择两个个体作为父代，利用交叉算子和变异算子生成新的个体，直到获得新的被选种群。 Step6:检验是否符合结束条件，如果当前的迭代次数达到了预先设定的最大次数或者达到最小错误要求，则输出最优解;否则，转Step2。 上述方法中采用了如下的遗传算子生成新的个体: 1)交叉算子。对于每一个待定位节点，随机选择一个父代个体中的坐标近似值作为新个体s中的坐标。 2)