基于改进DV-Hop 的水质WSN 节点定位算法研究

陈柄全，郭星锋，黄元峰，杨明润

（武汉工程大学 电气信息学院，湖北 武汉 430205）

0 引言

随着现代工业化的高速发展，各种化工厂的污水处理不当使得水环境污染问题日益严重，因此有必要对相关水域进行水质节点检测后定位，以便水环保工作者对具体污染源位置进行精确处理[1]。无线传感器网络水质检测系统由分布在水质检测区域的大量水质检测节点通过无线网络方式连接到PC端而组成，由于多数水质检测节点不具有GPS 定位功能，因此水质检测节点采集到的数据信息不包含自身位置信息[2]。如果水质传感器节点采集到了大量的水质数据却不能将自身的位置信息传送给相关工作人员，那么水质检测后的数据信息将变得毫无意义。基于此，研究水质无线传感器节点定位具有一定的实际应用价值。

通过大量的文献阅读，结合无线传感器网络水质检测系统的实际应用环境，发现非测距定位算法中的DV-Hop 节点定位算法更适合应用在大面积的水质检测场景[3]。传统DV-Hop 算法复杂度低且易实现，但存在平均跳距计算误差和最小二乘法计算节点坐标误差等问题。针对传统DV-Hop 算法存在的问题，相关研究工作者提出了很多改进的方式。例如：SHI 等人[4]提出了一种路径匹配算法来寻找最优锚点-锚点最短路径；SHI 等人[5]采用改进的余弦相似度参数来度量路径对之间的相似度；程等人[6]提出了基于误差与距离的权值处理锚节点间的平均单位跳距，然后利用遗传算法取代最小二乘法输出未知节点坐标；LI 等人[7]提出了一种新的启发式算法并行紧凑型优化算法；石等人[8]、孙等人[9]则引进了灰狼算法对DV-Hop 进行改进。但是，以上改进算法仍存在定位精度不足、通信开销变大、算法复杂度增大等问题。针对上述问题，本文将DV-Hop 节点定位算法作为基本算法并进行改进，以提高水质检测节点的定位精度。

1 DV-Hop 算法概述

传统DV-Hop 节点定位算法由NICULESCU 等人[10]提出，算法原理分析如下。通过广播搜集每个节点的最小跳数信息并保存，计算任意信标节点i的平均跳距Hi：

式中：hij表示信标节点i与j的最小跳数。

利用式（1）计算出的结果，即可求解任意未知节点u与信标节点j之间的距离，即：

计算出距离后，即可估算未知节点坐标。

传统DV-Hop 节点定位误差的来源主要有两个方面，分别是计算平均跳距带来的误差和最小二乘法计算节点坐标时产生的误差[11]。本文针对DV-Hop这两个误差进行改进，以提高其定位精度。

2 基于灰狼算法改进的DV-Hop 水质WSN 节点定位算法

通过对DV-Hop 的误差分析，本文根据数学原理推导出修正任意节点的修正因子通式，利用平均跳距修正因子修正传统DV-Hop 中的平均跳距值。此外，引入改进的灰狼算法对传统DV-Hop 算法估计出的未知节点初始坐标进行优化。改进算法流程如图1 所示。

图1 基于灰狼算法改进的DV-Hop 定位算法流程

由于无线传感器网络节点定位中存在节点分布不均匀的问题，因此会产生计算误差。一般规定节点之间的最小跳数为单位跳数，如果存在节点随机分布不均匀的情况，就会造成平均跳距计算误差。根据式（1）可知，计算平均跳距时需要用到跳数。如果两个节点之间的跳数在单位跳数范围内，则计算平均跳距时视两节点的跳数为1，然而实际情况是小于1 跳，从而导致平均跳距计算误差。通过上述问题描述，可假设信标节点a和b的坐标分别为(ax,ay)和(bx,by)，则a和b之间的距离为：

式中：hab表示节点a和b之间的跳数。

a和b之间的实际距离为：

利用式（3）和式（4）可以推出信标节点a和b之间实际距离与计算距离的偏差为：

根据式（3），（4），（5）推出本文所提出的平均跳距修正因子为：

利用定义的修正因子ci即可推导出修正距离和修正后跳数hit的关系为：

将灰狼算法与DV-Hop 相结合，首先需要将后者的输出信息转变为前者的输入信息，其次通过灰狼算法进行自身内部迭代寻优，最后输出最优未知节点坐标。通过分析灰狼算法的原理，将未知节点信息比作猎物坐标信息，这样就可以利用灰狼算法搜索出猎物的坐标，满足一定条件后作为未知节点坐标输出。

利用排序函数将DV-Hop 运算出的未知节点与信标节点的距离进行升序排序并保存，然后选出距离最小的5 个进行保存，同时记录其序号。初始化灰狼个体，设灰狼个体的位置坐标为(x,y)，将保存的5 个最小距离记为{d1,d2,d3,d4,d5}。将最近5 个信标节点坐标{(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)}作为灰狼算法中适应度函数的输入信息，计算适应度函数值并比较每次循环后的适应度值，找出最小的值保存，通过灰狼算法内部循环迭代找出最佳的狼的位置。当达到算法迭代条件时，输出适应度值对应的灰狼个体坐标作为未知节点坐标输出，否则继续下一步。其中，适应度函数为：

计算所有个体的适应度值后，从中选出新的狼群个体位置信息作为初始值重新迭代寻优。利用算法迭代完成后，即可将最优个体狼的位置信息作为未知节点的坐标输出。

3 仿真实验

仿真软件为Matlab 2016b，通过分别改变水质检测信标节点数、水质检测节点数以及水质检测节点之间的通信半径大小，对比本文所提算法与传统DV-Hop 算法、黄等人[12]所提基于粒子群算法改进的DV-Hop 算法、易等人[13]所提基于加权双曲线改进的DV-Hop 算法（Improved DV-Hop location algorithm based on weighted hyperbola，WH-DVHop）的定位精度。首先在Matlab 上编写4 种对比算法的程序并作为Function 函数，其次编写主函数，最后利用主函数调用4 个算法编写的Function 函数得出最终的节点定位仿真对比结果。

在Matlab 上模拟水质节点分布区域，随机生成N个水质传感器未知节点(xi,yi)和m个已知坐标信息的水质传感器节点，所有水质传感器节点通信半径均设置为R。假设未知节点的估计坐标为对水质节点定位精度进行归一化处理：

为了验证水质传感器信标节点数量对节点定位算法的定位精度影响，控制水质传感器节点数量和水质传感器节点之间的通信半径大小不变。设置水质传感器节点数为100 个、水质传感器之间的通信半径为15 m，通过改变信标节点数来仿真对比不同节点定位算法的定位精度，结果如图2 所示。

图2 水质传感器信标节点数对定位性能的影响

为了验证水质传感器节点数量对节点定位的影响，控制水质传感器信标节点数和水质传感器节点之间的通信半径不变。设置水质传感器信标节点数为15 个、水质传感器之间的通信半径为15 m，通过改变水质传感器节点数量来仿真对比本文算法和其他3 种算法的定位精度，结果如图3 所示。

图3 水质传感器节点数对定位性能的影响

为了验证水质传感器节点之间的通信半径大小对不同节点定位算法的定位精度影响，控制水质传感器信标节点数和水质传感器节点数不变。设置水质传感器信标节点数为15 个、水质传感器节点数为100 个，通过改变水质传感器之间的通信半径大小来进行仿真对比实验，结果如图4 所示。

图4 通信半径对定位性能的影响

综合分析上述仿真结果，任意改变一个变量时，本文所提算法的定位精度都比另外3 种算法高，性能较优，具有一定的可行性。

4 结语

本文基于DV-Hop 的两个误差来源分析，提出基于灰狼算法改进的DV-Hop 水质检测节点定位算法。实验结果表明，该改进方法能很好地提高水质检测节点的定位精度。由于引入了平均跳距修正系数，在一定程度上增加了算法的计算时间，因此后期将继续深入研究如何降低算法计算时间。