1、基于 SPSOhop 无线传感器网络节点定位算法摘 要针对无线传感器网络无需测距 DV-Hop 定位算法中，利用多边测量法计算未知节点坐标时存在较大误差的问题，提出了一种基于模拟退火粒子群算法的 DV-Hop 无线传感器网络定位算法。该算法首先将DV-Hop 算法的定位问题转化成全局最优化问题；再将模拟退火算法与粒子群算法的计算最优化问题的优势相结合，提出了一种模拟退火粒子群算法；最后将此算法对 DV-Hop 算法定位得到的节点位置进行校正。经过Matlab 仿真表明，相同的仿真环境中，新算法产生的平均定位误差比原始 DV-hop 算法产生的平均定位误差更低，有效地提高了定位精度。 关键词无线
2、传感器网络；节点定位；DV-Hop 算法；粒子群算法 中图分类号：U6 文献标识码：A 文章编号：1009-914X（2015）10-0008-02 引言 随着无线通信技术的发展，孕育出的无线传感器网络（WSN）以其低成本、低功耗、多功能的特点促进了传感器的快速发展。在军事、商业、环境监测、家庭自动化等领域获得越来越多的应用，它已成为无线通信技术中的重点研究对象。其中节点定位是无线传感器网络（WSN）的一个关键问题1-2。 现有的定位方法分为基于测距和免测距两类。基于测距的方法对硬件要求高而且在通信过程中开销大。免测距的方法无需任何额外的硬件设备，直接通过网络连通性进行对未知节点进行定位，使其
3、网络能量的开销小且经济有效5。其中 DV-Hop 作为一种典型的免测距定位算法，以其成本低、能耗小等优势 得到广泛使用。但存在着定位精度低、误差大的缺陷。 文献3将蚁群算法、粒子群算法引入到 DV-Hop 算法未知节点计算阶段，从而提高了定位精度。文献4使用多边测量法，比较路径的中心节点与两个锚节点之间的夹角，除去了锚节点共线的问题。文献5利用蛙跳算法来求解平均每跳距离，使其更接近实际值，从而提高最终定位结果的精确度。这些算法在一定程度上都起到了提高定位精度的作用，但仍有不足，因此如何提高定位精度，减少定位误差成为了研究的主要问题。本文在 DV-Hop 定位算法研究的基础上，做了进一步的改进，
4、提出了一种基于模拟退火粒子群算法的 DV-hop 无线传感器网络定位算法。 1 DV-Hop 算法的分析 1.1 DV-Hop 算法 DV-Hop 算法是 Niculescu 和 Nath 提出的一种基于计算跳数信息的分布式定位算法（APS） ，是目前最广泛无需测距的定位算法的一种。在 DV-Hop 算法定位过程分为三个步骤： 第一步：锚节点通过泛洪的方式发送数据包（包括锚节点的 ID、坐标、锚节点接收信息节点的跳数） ，跳数初始值设置为 0，每个临界点接收到信息后就保存和更新最小跳数，并将跳数加 1，并继续向邻节点转发，以此机制就会获得未知节点与每个锚节点之间的最小跳数。 第二步：获取其它锚
5、节点的跳数以及坐标，根据公式（1）估计出每个锚节点每跳的平均每跳距离值。为锚节点的每跳平均距离，表示锚节点到锚节点之间最小的跳数且 ，锚节点与锚节点的坐标为、 。 1.2 DV-HOP 算法的不足 由于测距误差、环境因素、通信等影响，测量距离总存在一定误差。在通常解出未知节点与锚节点的矩离，会利用三边测量法或极大似然估计法来求解的坐标。由于向量中的每个元素都包含锚节点的平均每跳矩离值，而是带有误差测量距离，所以在这种情况下，求解出的估计坐标会与真实坐标之间产生一定偏差，从而降低最终定位精度。所以可以将误差最小化转化为全局最优化求解问题。 2 DV-Hop 算法的改进 2.1 粒子群算法 粒子群
6、算法（PSO，Particle Swarm Optimizion）从随机解出发，对于 n 维的优化问题，随机生成 m 个粒子的初始种群，第 i 个粒子的飞行速度和位置将其代入优化目标函数得出适应值，更新粒子速度 Vi 和 Xi位置，通过迭代寻求最优解。其中第 i 个粒子搜索到目前为止的最优位置。整个粒子群迄今为止搜索到的最优位置记为 pb。可用下列公式（7） 、（8）对粒子的速度和位置进行更新。 2.2 模拟退火粒子群算法算法 模拟退火算法（SA，Simulated Annealing）是一种模拟热力学中高温物体降过程。模拟退火算法在冷却过程中，粒子在温度时达到平衡状态时，以内能为目标函数值。
7、本文结合模拟退火算法，通过粒子群优化算法中每个粒子的位置进行局部寻优，提出了一种模拟退火粒子群算法SPSO（Simulated Annealing Particle Swarm Optimizion） 。首先计算初始粒子群计算的最大目标函数适应值和最小目标函数，设置初始接受概率为，则初始温度为： 本文利用 SPSO 算法对 DV-Hop 算法定位后期部分中求出的未知节点坐标进行校正。优化具体步骤如下： Step1：通过 DV-Hop 算法的第一步和第二步，得出平均跳距和最小跳数。 Step2：在一个维的搜索的空间，在此空间中有个粒子成为了一个群体。并且第个粒子在维向量的表示为，其中。每个粒子的
8、位置都存在着一个潜在的解。第个粒子的飞行速度也是维向量，其中。其中第个粒子搜索到目前为止的最优位置。整个粒子群迄今为止搜索到的最优位置记为。设置初始化迭代次数。 Step3：根据公式（12）计算适应值。 Step4：按照式（7） ， （8）更新每一个粒子的位置和速度，并计算其适应度值。 Step5：计算每个新粒子的适应度和平均适应度。并且计算粒子两次位置变化所引起的适应值变化量，若或则接受新粒子的态，更新其个体及全体最优位置。否则进行 Step6。 Step6：更新迭代次数；更新惯性权重、退火温度等参数。 Step7：判断算法是否达到终止条件。若达到最大迭代次数，则输出结果；否则进行从 1 到
9、 N 的循环部分，返回 Step5。 3 实验仿真与结果分析 为了验证本文算法的有效性和可行性，对本文算法、DV-Hop 算法、PSO-Hop 算法利用 Matlab 进行试验仿真实验仿真，并对结果进行对比分析。在 100100（m）的二维平面随机产生未知 图 2 为在相同的节点总数情况下，平均定位误差随锚节点比例变化的曲线。从图 2 可以看出，随着锚节点比例的增加，各种定位算法的平均定位误差都会逐渐下降，经过 SPSO 算法的校正后，平均定位误差进一步减小，说明利用 SPSO-Hop 定位算法更为精确。 图 3 是锚节点比例相同的情况下，平均定位误差随节点数量变化的关系。从图 3 可以看出随
10、着节点数量的增加，基于 SPSO-Hop 算法的改算法平均定位误差是最小的，且在节点数量为 90 时较 DV-hop 的平均定位误差降低了 11.21%。 4 结论 本文在 DV-Hop 算法的基础上，采用了一种新的传感器定位算法SPSO-Hop。此算法结合了模拟退火算法和优化粒子群混合算法（SPSO） ，通过最小化与 DV-Hop 的适应度函数，进一步优化改进的 DV-Hop 算法。仿真结果证明，该算法在一定程度上能有效提高 DV-Hop 算法的定位精度，可有效的应用于 WSN 的定位算法中。 参考文献 1 Haas Z J，Halpern J Y，Li L.Gossip-Based ad
11、hoc routing C/Pro cof the IEEE INFOCOM.New Yo-rk：IEEE Commuications Society，2002：1707-1716. 2 Akyildiz I， Su W，Sankarasubramaniam Y，et alA survey on sensor network J.IEEE Communicatio-ns Magazine，2002，40（8）：102-114. 3 叶蓉，赵灵锴.基于蚁群粒子群混合的无线传感器网络定位算法J.计算机测量与控制，2011，19（3）：732-735. 4 李亚红，冯东华.基于物联网的传感器节点易移动 型监测区域定位算法J.计算机测量与控制，2012，20（11）：2916-2918. 5 葛宇，王学平，梁静.基于蛙跳算法的 DV-Hop 定位改进 J.计算机应用，2011，31（4）：922-925. 作者简介 韩彦春（1983-） ，女，辽宁阜新人，工程师，硕士研究生，主要从事电力电子仿真、机电控制设计等方面的研究。
