无线传感器节点定位技术的研究及改进

周亚罗 刘文广 王莎莎 程锐涵

【关键词】DV-HOP算法 跳距 修正

无线传感器网络（Wireless Sensor Networks， WSN）是一种分布式传感网络，由大量微型、低成本、低功耗的传感器节点组成，通过无线通信方式形成了一个多跳的自组织的网络系统。传感器节点自身定位是无线传感器网络定位机制的核心内容，定位技术是无线传感器网络的关键技术之一，对节点定位技术的研究具有重要的理论意义和应用价值。

由于成本原因，传感器节点中只有少数装有GPS，称为锚节点，所谓节点定位技术是只利用少数锚节点的位置坐标计算出大量未知节点的坐标位置。现有的节点定位算法主要分为两类：一类是基于测距技术的定位算法，利用节点间的距离或角度来测距，常见的信号强度法（Received Signal Strength Indication，RSSI）、时间法（Time of Arrival，TOA）、时间差法（Time Difference of Arrival，TDOA）和角度法（Angle of Arrival，AOA）。基于测距技术的定位算法，定位精度相对较高，但硬件成本较高，容易受到环境因素的影响。另一类是基于网络连通性的定位算法主要包括：质心法、APIT算法、DV-HOP算法等。对硬件要求低、功耗小，可扩展性强，更能满足传感器网络低功耗、低成本的要求。

1 传统DV-HOP算法概述

DV-HOP 算法主要根据网络的连通性，利用多跳特性进行定位。算法简单，成本低，在各向同性的密集网络中可以得到理想的定位精度。在恶劣的网络拓扑环境中，定位精度有待提高。DV—Hop算法的定位过程分为四步：

第一步：计算未知节点与每个锚节点的最小跳数

锚节点在网络中周期性发送自身信息，包含编号ID、自身坐标和跳数，初始跳数为0。通信范围内的其他节点收到信息后，与同一ID号的跳数比较，记录下这些信息中的最小跳数值并将跳数值加1，转发给它的邻居节点。锚节点周期性广播，直至未知节点记录下与每个锚节点之间的最小跳数

第二步：计算每个锚节点每跳平均跳距HopSizeii。

利用各个锚节点之间的距离和跳数，求取每个锚节点对应的每跳平均跳距。

（1）

式中：

（xi，yi） ，（xj，yj） 分别为锚节点i和j的坐标；

hij是节点i和节点j之间的的跳数。

第三步：确定未知节点跳距校正值，求取未知节点与各锚节点之间的距离。

校正值为未知节点与锚节点之间的每跳距离，未知节点与每个锚节点之间的距离=跳距校正值×跳数。传统DV-HOP 算法采用距离未知节点跳数最小的锚节点的平均每跳距离作为校正值，并在网络中广播。

第四步：计算未知节点坐标。

根据未知节点与锚节点之间的距离di、锚节点坐标（xi，yi），求取未知节点坐标（x，y）。根据距离公式，列出未知节点与各锚节点的距离相应的方程组：

解方程组，分别用第1个，第2个…第n-1个方程减去最后一个方程得到以下方程组：

上述方程组可用线性方程表示：AX=B，通过最小均方差估计方法，得到未知节點的坐标为。

2 传统DV-HOP算法存在的问题及改进

DV-HOP 算法的核心算法是距离=跳数×跳距，但无论是锚节点的每跳距离还是未知节点每跳距离的校正值采用的都是平均或最小估计，在WSN节点密度非常高的情况下，定位精度较高。最后一步利用距离求坐标，一般采用的三边定位或极大似然估计法，误差较大。

2.1 平均每跳距离的估计值

网络节点随机分布，没有规律，且各锚节点之间的跳数不成直线，但在计算锚节点平均每跳距离时采用的是各锚节点之间的直线距离，因此计算锚节点平均每一跳距离存在误差，影响定位精度。冯江，朱强等提出对锚节点的平均每一跳距离进行加权，提出基于加权系数矩阵的DV-Hop改进算法；马淑丽，赵建平提出最佳指数值概念，用最佳指数值下的公式计算锚节点平均每一跳距离。

2.2 未知节点每跳跳距的校正值

未知节点与每个锚节点之间的距离=跳距校正值×跳数，跳数一定的情况下，跳距校正值对定位是否准确起着决定性作用。传统算法无论是采用距离未知节点跳数最小的锚节点的平均每跳距离还有采用全网所有锚节点的平均值作为未知节点的校正值，计算未知节点与各锚节点间距离，误差都是比较大的。使用单个锚节点的平均每跳距离的估计值不能准确地反映网络中节点的真实情况，采用全网锚节点平均值受到与未知节点距离较远的锚节点的影响会使得误差增大，且计算量加大。赵雁航，钱志鸿等在研究中只接收最近3个锚节点的平均每跳距离值进行加权计算未知节点的校正值。

2.3 未知节点的坐标定位计算

传统DV-Hop算法，未知节点的坐标计算一般情况下采用的是极大似然估计法，对矩阵AB依赖性强，且当ATA为病态矩阵时，通过多边定位法所估计出的未知节点坐标不仅误差很大，而且定位精度的稳定性较差，有时甚至得出错误的结果。一些学者将节点定位问题转化为求最优解问题，乔欣，常飞等用拟牛顿法对未知节点坐标的最小二乘解进行迭代优化，李道全，刘月月，孙付龙等将DV-Hop算法初步定位结果作为初解，引入steffensen迭代模型进行迭代求最优解；赵雁航，钱志鸿等用改进的粒子群（PSO）算法解未知节点坐标，改进粒子群算法，优化定位中的迭代过程，能够快速找到最优解，提高了定位精度，降低了计算量和网络开销。

3 本文对DV-HOP 算法的改进

本文针对影响 DV-HOP 算法精度的两个方面，分别在定位阶段和位置估计阶段对原算法进行了改进。

3.1 对锚节点跳距进行修正

式（1）中的每个锚节点每跳平均跳距HopSizeii，是利用锚节点之间的直线距离求出的平均跳距，而实际节点之间大部分都是非直线距离，因此该计算一定存在误差。我们要利用估算锚节点与其他锚节点之间估算距离与实际距离之间的误差来修正该锚节点的每跳平均跳距。设有n个锚节点，第i个锚节点的跳距修正值为ΔHOPi，则

其中：

dij为锚节点i，j之间的实际距离；

dij为锚节点i，j之间的估算距离，

hij为锚节点I，j之间的最小跳数；

修正后，锚节点i的每跳跳距HOPi=HopSizei+ΔHopi。

3.2 未知节点跳距的校正值的计算

未知节点每跳跳距的校正值采用最近节点跳距和全网平均跳距均有较大误差，节点之间非直线分布，导致节点之间跳数越多，累积误差越大，定位精度就越低。赵雁航，钱志鸿等在研究中只接收最近3个锚节点的平均每跳距离值，曾子维，冯章皓研究中只接收相应未知节点周围跳数在10跳及以内的锚节点的跳距。但距离与跳数之间并不成正比的关系，尤其在节点数量较少的情况下，跳数少但有可能距离大。因此，本研究采用n跳范围内m个距离最近的个锚节点跳距加权计算未知节点的跳距校正值。设未知节点i附近满足条件的m个锚节点跳距权值为wij，则有

3.3 坐标估算

取与未知节点n跳范围内的锚节点，再利用极大似然估计的方法计算自身位置。为消除累计误差对最后计算结果的影响，在原计算方法的基础上，引入一个加权矩阵W，加权系数为

，si为相应未知节点周围跳数在n跳及以内的锚节点总数， 加权矩阵W如下式：

可得出未知节点的坐标为。

4 算法仿真及结果分析

为实验改进后DV-HOP算法的定位精度，采用MATLAB平台进行仿真验证。定位过程中，节点数目及分布、锚节点的密度、通信半径等参数对定位精度影响很大。仿真环境设置在100m×100m的正方形区域内，100个网络节点随机分布，利用5跳距离内最近的3个锚节点跳距加权计算得出未知节点校正值，通信半径R=20，锚节点密度分别为10%，20%，30%，40%，50%，计算其定位误差。定位誤差ERR用定位距离误差与通信距离之间的比值来表示，

。式中，（x，y）为定位坐标，（xi，yi）为实际坐标，R为通信半径，N为待定位节点个数

为验证算法，节点随机分布，☆代表锚节点，○代表未知节点，利用锚节点已知坐标通过改进的DV-HOP算法定位未知节点的坐标位置。如图1、2所示。

从仿真结果中看出，随着锚节点数量的增多，传统的DV-Hop算法和改进的DV-Hop算法的定位精度均有所提高，但改进后的算法定位精度更高，误差下降更平稳，说明改进后的算法稳定性更强，对于任意分布的WSN定位系统的适应性更强。

参考文献

[1]冯江，朱强，吴春春.改进的DV-Hop定位算法研究[J].计算机工程， 2012，38（19）：74-81.

[2]马淑丽，赵建平.无线传感器网络中DV—Hop定位算法的改进[J].通信技术，2015，48（07）：840-844.

[3]赵雁航，钱志鸿，尚小航，程超。基于跳距修正粒子群优化的WSN定位算法[J].通信学报，2013，34（9）：105-114.

[4]乔欣，常飞，丁恩杰，王桃.基于跳距修正的WSN 拟牛顿迭代定位算法[J].传感技术学报，2014，27（6），797-801.

[5]李道全，刘月月，孙付龙.基于DV-Hop的WSN网络节点定位算法[J].计算机仿真，2014，31（4）：303-306.

[6]曾子维，冯章皓.WSN中基于不同跳距修正的改进DV-HOP定位算法[J].辽宁科技大学学报，2015，38（5）：376-381.