基于SPSO―hop无线传感器网络节点定位算法

[摘 要]针对无线传感器网络无需测距DV-Hop定位算法中，利用多边测量法计算未知节点坐标时存在较大误差的问题，提出了一种基于模拟退火粒子群算法的DV-Hop无线传感器网络定位算法。该算法首先将DV-Hop算法的定位问题转化成全局最优化问题；再将模拟退火算法与粒子群算法的计算最优化问题的优势相结合，提出了一种模拟退火粒子群算法；最后将此算法对DV-Hop算法定位得到的节点位置进行校正。经过Matlab仿真表明，相同的仿真环境中，新算法产生的平均定位误差比原始DV-hop算法产生的平均定位误差更低，有效地提高了定位精度。

[关键词]无线传感器网络；节点定位；DV-Hop算法；粒子群算法

中图分类号：U6 文献标识码：A 文章编号：1009-914X（2015）10-0008-02

引言

随着无线通信技术的发展，孕育出的无线传感器网络（WSN）以其低成本、低功耗、多功能的特点促进了传感器的快速发展。在军事、商业、环境监测、家庭自动化等领域获得越来越多的应用，它已成为无线通信技术中的重点研究对象。其中节点定位是无线传感器网络（WSN）的一个关键问题[1-2]。

现有的定位方法分为基于测距和免测距两类。基于测距的方法对硬件要求高而且在通信过程中开销大。免测距的方法无需任何额外的硬件设备，直接通过网络连通性进行对未知节点进行定位，使其网络能量的开销小且经济有效[5]。其中DV-Hop作为一种典型的免测距定位算法，以其成本低、能耗小等优势

得到广泛使用。但存在着定位精度低、误差大的缺陷。

文献[3]将蚁群算法、粒子群算法引入到DV-Hop算法未知节点计算阶段，从而提高了定位精度。文献[4]使用多边测量法，比较路径的中心节点与两个锚节点之间的夹角，除去了锚节点共线的问题。文献[5]利用蛙跳算法来求解平均每跳距离，使其更接近实际值，从而提高最终定位结果的精确度。这些算法在一定程度上都起到了提高定位精度的作用，但仍有不足，因此如何提高定位精度，减少定位误差成为了研究的主要问题。本文在DV-Hop定位算法研究的基础上，做了进一步的改进，提出了一种基于模拟退火粒子群算法的DV-hop无线传感器网络定位算法。

1 DV-Hop算法的分析

1.1 DV-Hop算法

DV-Hop算法是Niculescu和Nath提出的一种基于计算跳数信息的分布式定位算法（APS），是目前最广泛无需测距的定位算法的一种。在 DV-Hop算法定位过程分为三个步骤：

第一步：锚节点通过泛洪的方式发送数据包（包括锚节点的ID、坐标、锚节点接收信息节点的跳数），跳数初始值设置为0，每个临界点接收到信息后就保存和更新最小跳数，并将跳数加1，并继续向邻节点转发，以此机制就会获得未知节点与每个锚节点之间的最小跳数。

第二步：获取其它锚节点的跳数以及坐标，根据公式（1）估计出每个锚节点每跳的平均每跳距离值。为锚节点的每跳平均距离，表示锚节点到锚节点之间最小的跳数且 ，锚节点与锚节点的坐标为、。

1.2 DV-HOP算法的不足

由于测距误差、环境因素、通信等影响，测量距离总存在一定误差。在通常解出未知节点与锚节点的矩离，会利用三边测量法或极大似然估计法来求解的坐标。由于向量中的每个元素都包含锚节点的平均每跳矩离值，而是带有误差测量距离，所以在这种情况下，求解出的估计坐标会与真实坐标之间产生一定偏差，从而降低最终定位精度。所以可以将误差最小化转化为全局最优化求解问题。

2 DV-Hop算法的改进

2.1 粒子群算法

粒子群算法（PSO，Particle Swarm Optimizion）从随机解出发，对于n维的优化问题，随机生成m个粒子的初始种群，第i个粒子的飞行速度和位置将其代入优化目标函数得出适应值，更新粒子速度Vi和Xi位置，通过迭代寻求最优解。其中第i个粒子搜索到目前为止的最优位置。整个粒子群迄今为止搜索到的最优位置记为pb。可用下列公式（7）、（8）对粒子的速度和位置进行更新。

2.2 模拟退火粒子群算法算法

模拟退火算法（SA，Simulated Annealing）是一种模拟热力学中高温物体降过程。模拟退火算法在冷却过程中，粒子在温度时达到平衡状态时，以内能为目标函数值。本文结合模拟退火算法，通过粒子群优化算法中每个粒子的位置进行局部寻优，提出了一种模拟退火粒子群算法SPSO（Simulated Annealing Particle Swarm Optimizion）。首先计算初始粒子群计算的最大目标函数适应值和最小目标函数，设置初始接受概率为，则初始温度为：

本文利用SPSO算法对DV-Hop算法定位后期部分中求出的未知节点坐标进行校正。优化具体步骤如下：

Step1：通过DV-Hop算法的第一步和第二步，得出平均跳距和最小跳数。

Step2：在一个维的搜索的空间，在此空间中有个粒子成为了一个群体。并且第个粒子在维向量的表示为，其中。每个粒子的位置都存在着一个潜在的解。第个粒子的飞行速度也是维向量，其中。其中第个粒子搜索到目前为止的最优位置。整个粒子群迄今为止搜索到的最优位置记为。设置初始化迭代次数。

Step3：根据公式（12）计算适应值。

Step4：按照式（7），（8）更新每一个粒子的位置和速度，并计算其适应度值。

Step5：计算每个新粒子的适应度和平均适应度。并且计算粒子两次位置变化所引起的适应值变化量，若或则接受新粒子的态，更新其个体及全体最优位置。否则进行Step6。

Step6：更新迭代次数；更新惯性权重、退火温度等参数。

Step7：判断算法是否达到终止条件。若达到最大迭代次数，则输出结果；否则进行从1到N的循环部分，返回Step5。

3 实验仿真与结果分析

为了验证本文算法的有效性和可行性，对本文算法、DV-Hop算法、PSO-Hop算法利用Matlab进行试验仿真实验仿真，并对结果进行对比分析。在100×100（m）的二维平面随机产生未知

图2为在相同的节点总数情况下，平均定位误差随锚节点比例变化的曲线。从图2可以看出，随着锚节点比例的增加，各种定位算法的平均定位误差都会逐渐下降，经过SPSO算法的校正后，平均定位误差进一步减小，说明利用SPSO-Hop定位算法更为精确。

图3是锚节点比例相同的情况下，平均定位误差随节点数量变化的关系。从图3可以看出随着节点数量的增加，基于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 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-），女，辽宁阜新人，工程师，硕士研究生，主要从事电力电子仿真、机电控制设计等方面的研究。