基于BPSDV—Hop的无线传感器网络节点定位算法

戴天虹 王硕

摘 要 为了尽量避免误差的扩大化，定位更加准确，增强无线传感器网络节点的灵敏程度，混合粒子群在BA校正的基础上，不断优化无线传感器网络定位，充分利用BPSDV-Hop定位算法，这一算法先通过优化混合粒子群对一些未知节点精细计算，计算出跳距范围，其次在应用DV-Hop算法计算未知节点的自身位置时摒弃以往常用的最小二乘法，对于那些未知节点的坐标的判断要利用好蝙蝠算法，通过这一特性不断优化定位方法，确定精度，最后要充分发挥Matlab平台的作用，利用这一平台，对算法细致化分析与探究。据可靠分析显示：BPSDV-Hop定位算法远远优越于DV-Hop定位算法，它对未知坐标的判断和定位准确度非常之高，在WSN中具有广泛的应用前景。

【关键词】BPSDV-HOP算法 无线传感器网络 DV-HOP算法 混合粒子群优化算法 蝙蝠算法

节点定位技术是无线传感器网络（Wireless Sensor Network，WSN）的基础，在WSN研究中，将节点定位技术当作现阶段研究的首要任务，它的应用前景极为广泛，在一些复杂多变的环境中有很高的利用价值，众所周知的安全探测、军事环境等，运用极多。

目前，国内外专家和学者对WSN其展开了一系列的分析探索，定位算法有测距和非测距之分，作用各不相同。DV-Hop 算法是免测距算法中比较成熟的算法，它的定位方法比起其它算法来说较为容易，通过一少部分的锚节点就能实现快捷定位，但缺点是定位精度略低。因此，学者们对 DV-Hop 算法进行了一系列的改进用于提高其定位精度，例如：在DV-Hop算法的节点距离计算中使用RSSI策略，缩小节点之间的误差，提高WSN定位精度；将介质访问机制引进DV-Hop算法中优化距离误差；在锚节点间进行距离计算时，为实现平均跳距计算的准确性，采用最佳调整因子不断优化经过一系列分析得出的定位结果；运用混合粒子群优化算法求解DV-Hop 定位算法中未知节点的平均跳距，减少定位误差提高定位准确性；不过这些算法仍然存在较多的问题，不能充分考虑到算法的全面性，从而忽视了搜索的空间大小问题，对WSN节点的定位精度产生重要影响。为了避免这种情况，我们要开拓思维另辟蹊径。终于在2010年，蝙蝠算法（BA）正式被杨新社教授提出，他充分利用蝙蝠的回声定位的特性，进行大量实验数据分析提出该算法，蝙蝠算法在实际应用中具有很多优良特性，尤其表现在迭代寻优方面，且不需要对大量的参数进行调整，所以为了减少误差，提高WSN节点的定位精度，本文将引入BA算法为校正DV-Hop 算法的误差提供一种新的研究思路。

本文提出一种基于BA校正的混合粒子群优化WSN定位算法即BPSDV-Hop定位算法，这一算法先通过优化混合粒子群对一些未知节点精细计算，计算出跳距范围，其次在应用DV-Hop算法计算未知节点的自身位置时摒弃以往常用的最小二乘法，对于那些未知节点的坐标的判断要利用好蝙蝠算法，通过这一特性不断优化定位方法，确定精度，准确定位WSN节点。

1 DV-Hop定位算法及误差分析

1.1 DV-Hop定位算法

第一步，获取锚节点和计算跳距范围；

第二步，获取跳段距离。锚节点i的平均每跳距离计算公式为：

式中，hij是锚节点i和j之间的跳数，（xi，yi）、（xj，yj）是节点i和j的坐标。之后将所有锚节点的跳距的范围平均映射到每一部分，未知节点的每次跳距之间的距离范围即映射得到的锚节点的跳距范围相同，锚节点的跳段距离就是平均每跳的距离范围与最小的跳数之积。

最后，计算未知节点的坐标：设这n个锚节点的坐标为，待定节点的坐标为（x，y），待定节点与锚节点估计距离分别为d1，d2，…，dn，由此可建立如下方程：

在WSN测距过程当中难免產生数据错误，因此线性方程组为AL+N=b，其中，N为误差向量，最小二乘法距离方程为：

1.2 DV-Hop定位误差分析

先假设锚节点i和未知节点之间的实际距离为ri，测距误差为εi，（x，y）符合约束条件|ri-di|<εi，求解（x，y），使得

由式（4）知，节点所在位置必定不会超出该区域范围，且f（x，y）为定位总误差，当其获取最小值时，该定位判断得到的误差最小，未知节点的最优值即为坐标（x，y），采用数学化模型的方法优化定位问题，利用蝙蝠算法求解未知坐标，防止误差扩大化。

此外，DV-Hop定位算法的定位原理为将锚节点当作未知节点，它们之间的平均跳距用两锚节点之间的平均跳距表示，这就很容易在两点之间的定位出现误差。因此，本文采用混合粒子群优化算法求解未知节点的平均跳距，减少定位误差。

2 BPSDV-Hop定位算法

2.1 蝙蝠算法

将蝙蝠的回声定位理想化，每个虚拟蝙蝠在位置xi（问题的解）均有对应的飞行速度vi，刚开始寻找猎物时，蝙蝠发出低频高声强的超声波，用以扩大搜索范围，发现猎物后，逐渐减小声强并增加脉冲的频率，以精确定位猎物。

其中，虚拟蝙蝠的实时位置和速度如式（5）所示：

式中，fi，fmax，fmin依次表示为当前时刻第i只蝙蝠发出的脉冲频率，最大脉冲频率和最小脉冲频率，按照均匀分布原则，其中β为随机因子，x*为此前最优解。在搜索产生局部新解的过程中，要充分利用随机游走的原则，当其中一个最优解被选中时，按照原则进行合理化分析判断：

式中，随机变量，At为所有蝙蝠的平均声强。声强和脉冲发射率的更新公式如式（7）所示：

2.2 混合粒子群优化算法

相对粒子群算法（PSO）的弊端较为明显，经常出现最优解判断不全等问题；显而易见，模拟退火算法则很好的解决了这一问题，它的优势不仅体现在搜索的全面性上，它的搜索效率也比PSO算法显著提高；这里提到的混合粒子群优化算法（PSO-SA），本质上就是上面两种算法的结合体，将优势相融合，还具有一定的学习能力，充分利用了模拟退火算法的特性--退火特征。为了避免陷入局部最优解，按照Metropolis机制对粒子的位置和速度进行合理化的判断分析，及时进行数据更新，对初始种群中的粒子进行最优解的搜索，确定其初始参数，再执行其退火过程。

假设当前网络中存在N个未知节点和M个锚节点，节点的坐标集为，其中，锚节点的坐标分别为，则未知节点的坐标为，，，则定位问题就可用下面的公式来描述

表示第i个锚节点与未知节点之间的实际距离与测量距离的误差，而定位问题相应的转化为定位误差的最小值。

在混合粒子群优化算法中，温度对粒子群算法影响不是很大，根据模拟退火算法的特性，对温度T的进行如下设置：从粒子群中选出粒子的适应度最小与最大的粒子，其中适应度值为fmin，fmax，在退火过程中按蒙特卡罗准则以一定概率p0接受重要状态，设初始温度为，同时，在粒子进行迭代过程中，按照的速度降低温度，。在实际过程中，当p0=0.85，λ=0.95时，算法才有最好的优良性能。在混合粒子群优化算法中，粒子群优化算法的结束的条件是给定粒子群的最大速度和坐标情况，当算法达到这个值时，算法结束；然而，对于模拟退火算法，它的结束条件则通过比较相邻之间最优解的目标函数增量△f与一定程度ε的大小来判断是否进行降温处理。混合粒子群优化算法流程图如图1所示。

2.3 适应值函数设计

蝙蝠的优劣位置是通过对混合粒子群优化算法的特点分析和适应度的关系来判断的，其中适应度函数计算公式为：

式中，M为锚节点的个数，表示未知节点与第i个锚节点之间测量距离的权重大小，权重的大小是由未知节点到锚节点的跳数决定的，权重值和跳数的关系是相反的，这完全符合实际情况。其次，未知节点的估计距离是根据最小化适应度函数的目标值来判断确定的。

2.4 BPSDV-Hop定位算法的工作流程

首先，混合粒子群在BA校正的基础上，不断优化无线传感器网络定位，将求解位置坐标问题转化成一个全局最优化问题，其次在应用DV-Hop算法计算未知节点的自身位置时摒弃以往常用的最小二乘法，对于那些未知节点的坐标的判断要利用好蝙蝠算法，通过这一特性不断优化定位方法，确定精度，从而获取更加理想的WSN定位结果，具体实现流程如图2所示。

3 仿真实例

3.1 仿真环境

充分利用Matlab仿真平台，在相同网络环境下对比实验DV-Hop定位算法测试验证BPSDV-Hop算法的定位性能，在其他条件相同的前提下，改变锚节点的密度、通讯半径以及节点的数量，采用平均定位误差对比两种算法的定位性能，具体如下：

在100m×100m的二维空间内随机安排100个节点，其中节点的通信半径为30m，锚节点占全部节点的10%，参数设置如下：蝙蝠种群大小m=100，最大声强A=0.20，声强衰减系数及脉冲频度增加系数均为0.05，搜索脉冲频率范围[0，100]，最大脉冲频度r0=0.75，所有结果为平均运行50次后取平均值。

3.2 结果与分析

3.2.1 对两种算法的定位误差进行比较

DV-Hop算法和BPSDV-Hop算法的未知节点的定位误差如图3所示。由图3知，BPSDV-Hop算法的定位的平均误差并不大且明显小于DV-Hop算法的误差值，结果表明，BPSDV-Hop算法提高了定位精度。

3.2.2 锚节点个数对算法定位性能的影响

在比较锚节点个数对算法定位性能的影响时，保持节点个数不变，使锚节点得比例不同，两种算法的定位误差变化曲线如图4所示。由图4知，当锚节点的比例相同时，BPSDV-Hop算法的定位误差更小，且其能在较小的锚节点密度下实现更精确的定位。

3.2.3 通信半径对算法定位性能的影响

节点个数不变，锚节点比例为10%，当通信半径不同，两种定位算法的变化趋势如图5所示。由图5知，相同通信半径条件下，BPSDV-Hop算法的定位精度提高了25%-35%，有效降低了WSN节点的定位误差。

3.2.4 节点个数对算法定位性能的影响

在判断节点个数对算法定位性能的影响时，保持锚节点的比例不变，使节点个数不同，这两种算法的定位变化趋势如图6所示。由图6可知，节点数量的变化对BPSDV-Hop算法的影响相对较小，实验结果表明，BPSDV-Hop定位算法具有良好的鲁棒性。

4 结束语

为了尽量避免误差的扩大化，定位更加准确，增强无线传感器网络节点的灵敏程度，混合粒子群在BA校正的基础上，不断优化无线传感器网络定位，充分利用BPSDV-Hop定位算法，这一算法先通过优化混合粒子群对一些未知节点精细计算，计算出跳距范围，其次在应用DV-Hop算法计算未知节点的自身位置时摒弃以往常用的最小二乘法，对于那些未知节点的坐标的判断要利用好蝙蝠算法，通过这一特性不断优化定位方法，确定精度。实验结果表明：BPSDV-Hop定位算法远远优越于DV-Hop定位算法，它对未知坐标的判断和定位准确度非常之高，在WSN中具有广泛的应用前景。

参考文献

[1]Gao Y，Zhao W S，Jing C，et al.WSN node localization algorithm based on adaptive swarm optimization[J].Applied Mechanics and Materials，2012（143）：303-306.

[2]叶蓉，赵灵锴.基于蚁群粒子群混合的无线传感器网络定位算法[J].计算机测量与控制，2011，19（03）：732-735.

[3]赵仕俊，孙美玲，唐懿芳.基于遗传模拟退火算法的无线传感器网络定位算法[J].计算机应用与软件，2009，26（10）：189-192.

[4]白进京，严新平.基于加权质心和DV-hop混合算法WSN定位方法研究[J].计算机应用研究，2009，26（06）：2248-2251.

[5]谭爱平，陈浩，吴伯桥.基于BADV-Hop的傳感器节点定位方法[J].计算机工程与应用，2014，50（17）：125-129.

[6]刘运杰，金明录，崔承毅.基于RSSI的无线传感器网络修正加权定位算法[J].传感技术学报，2009，23（05）：717-721.

[7]邓力.基于遗传算法WSN节点定位算法研究[J].计算机仿真，2011，28（09）：161-164.

[8]王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（05）：857-868.

[9]李辉，熊盛武，刘毅等.无线传感器网络DV-HOP定位算法的改进[J].传感技术学报，2011，24（12）：1782-1786.

[10]刘少飞，赵清华.基于平均跳距估计和位置修正的DV-Hop定位算法[J].传感器技术学报，2009，22（08）：1154-1158.

[11]Yang X S，Gandomi A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computations，2012，29（05）：464-483.

[12]陈志翔，殷树言，卢振洋.基于遗传模拟退火算法的弧焊机器人系统协调路径规划[J]. 机械工程学报，2005（02）：194-198+204.

[13]凌琳.基于混合粒子群算法的无线传感网络节点定位研究[D].江西师范大学，2013.

作者单位

东北林业大学机电工程学院 黑龙江省哈尔滨市 150040