２０１９年 第２期仪表技术与传感器Ｉｎｓｔｒｕｍｅｎｔ Ｔｅｃｈｎｉｑｕｅ ａｎｄ Ｓｅｎｓｏｒ２０１９ Ｎｏ２
收稿日期：２０１８－０１－０２基于累加跳距和校正因子的无线传感网定位算法
孙博文，韦素媛，李东林（火箭军工程大学，陕西西安 ７１００２５）
摘要：针对无线传感网中ＤＶ－Ｈｏｐ定位算法利用平均跳距乘以跳数来估算距离，并未对估计节点
坐标重新评价而导致误差较大的问题，提出一种基于累加跳距和校正因子的ＤＶ－Ｈｏｐ定位算法。该算
法首先利用最小均方误差法求出各锚节点平均跳距，未知节点根据所有锚节点平均跳距加权求出自身
平均跳距，然后累加链路中各未知节点平均跳距求出节点间距离，最后估算锚节点位置并与实际锚节
点位置比较，得出校正因子修正未知节点坐标。仿真结果表明，该算法与传统ＤＶ－Ｈｏｐ算法及相关文
献算法相比，能够有效降低距离误差，提高定位精度。
关键词：无线传感网；ＤＶ－Ｈｏｐ算法；累加跳距；校正因子；最小均方误差
中图分类号：ＴＰ３９３ 文献标识码：Ａ 文章编号：１００２－１８４１（２０１９）０２－０１０９－０５
ＬｏｃａｌｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍｓｆｏｒＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋ
ＢａｓｅｄｏｎＡｃｃｕｍｕｌａｔｅｄＨｏｐＤｉｓｔａｎｃｅａｎｄＣａｌｉｂｒａｔｉｏｎＦａｃｔｏｒ
ＳＵＮＢｏ⁃ｗｅｎ，ＷＥＩＳｕ⁃ｙｕａｎ，ＬＩＤｏｎｇ⁃ｌｉｎ
（ＴｈｅＲｏｃｋｅｔＦｏｒｃｅＵｎｉｖｅｒｓｉｔｙｏｆＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎ７１００２５，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：ＴｈｅＤＶ－Ｈｏｐｌｏｃａｔｉｏｎａｌｇｏｒｉｔｈｍｓｅｓｔｉｍａｔｅｔｈｅｄｉｓｔａｎｃｅｂｙｔｈｅａｖｅｒａｇｅｈｏｐｄｉｓｔａｎｃｅｍｕｌｔｉｐｌｉｅｄｂｙｔｈｅｎｕｍｂｅｒｏｆｈｏｐｓ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｄｏｎｔｒｅａｓｓｅｓｓｔｈｅｅｓｔｉｍａｔｅｄｎｏｄｅｃｏｏｒｄｉｎａｔｅｓ，ｗｈｉｃｈｕｓｕａｌｌｙｒｅｓｕｌｔｓｉｎｌａｒｇｅｒｅｒｒｏｒ．Ｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｎｏｖｅｌａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｗａｓｂａｓｅｄｏｎｔｈｅａｃｃｕｍｕｌａｔｅｄｈｏｐｄｉｓｔａｎｃｅａｎｄｃａｌｉｂｒａｔｉｏｎｆａｃ⁃ｔｏｒ．Ｆｉｒｓｔｌｙ，ｔｈｅａｌｇｏｒｉｔｈｍｐｅｒｆｏｒｍｓｔｈｅｍｉｎｉｍｕｍｍｅａｎｓｑｕａｒｅｅｒｒｏｒｒｕｌｅ（ＭＭＳＥ）ｃａｌｃｕｌａｔｅｄｔｈｅａｖｅｒａｇｅｈｏｐｄｉｓｔａｎｃｅｏｆｅａｃｈａｎ⁃ｃｈｏｒｎｏｄｅ．Ｔｈｅｕｎｋｎｏｗｎｎｏｄｅｓｃａｌｃｕｌａｔｅｄｔｈｅｉｒｏｗｎａｖｅｒａｇｅｈｏｐｄｉｓｔａｎｃｅａｃｃｏｒｄｉｎｇｔｏｔｈｅｗｅｉｇｈｔｅｄａｖｅｒａｇｅｈｏｐｄｉｓｔａｎｃｅｏｆａｌｌｔｈｅａｎｃｈｏｒｎｏｄｅｓ，ａｎｄｔｈｅｎａｃｃｕｍｕｌａｔｉｎｇｔｈｅａｖｅｒａｇｅｈｏｐｄｉｓｔａｎｃｅｏｆｔｈｅｕｎｋｎｏｗｎｎｏｄｅｓｉｎｔｈｅｌｉｎｋｃａｌｃｕｌａｔｅｄｔｈｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎａｌｌｎｏｄｅｓ．Ｆｉｎａｌｌｙ，ｔｈｅｌｏｃａｔｉｏｎｏｆａｎｃｈｏｒｎｏｄｅｓｗａｓｅｓｔｉｍａｔｅｄｔｏｃｏｍｐａｒｅｗｉｔｈｔｈｅａｃｔｕａｌａｎｃｈｏｒｎｏｄｅｐｏｓｉｔｉｏｎｔｏａｍｅｎｄｔｈｅｕｎ⁃ｋｎｏｗｎｎｏｄｅｃｏｏｒｄｉｎａｔｅｓ．ＴｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｔｈｅｄｉｓｔａｎｃｅｅｒｒｏｒａｎｄｉｍｐｒｏｖｅｓｔｈｅｐｏｓｉｔｉｏｎｉｎｇａｃｃｕｒａｃｙｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｃｏｎｖｅｎｔｉｏｎａｌＤＶ－Ｈｏｐａｌｇｏｒｉｔｈｍｓａｎｄｔｈｅｒｅｌａｔｅｄｌｉｔｅｒａｔｕｒｅａｌｇｏｒｉｔｈｍｓ．Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ；ＤＶ⁃Ｈｏｐａｌｇｏｒｉｔｈｍ；ａｃｃｕｍｕｌａｔｅｄｈｏｐｄｉｓｔａｎｃｅ；ｃａｌｉｂｒａｔｉｏｎｆａｃｔｏｒ；ｍｉｎｉｍｕｍｍｅａｎｓｑｕａｒｅｅｒｒｏｒｒｕｌｅ
０ 引言
无线传感器网络（Ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔ⁃ｗｏｒｋ，ＷＳＮ）
是由若干个具有数据采集、处理、传输功能的节点通
过自组织方式形成的网络，节点之间进行信息传递，
达到对特定区域敏感数据实时监测的功能［１］。它在
目标跟踪、环境监测等领域有广泛的应用，引起学术
界的广泛关注和研究［２－３］。在应用中，节点时常被随
机布置或播撒在监测目标区域内，因此事件发生的位
置或获取信息的节点位置是传感器节点监测消息中
的重要信息，定位技术也就成为ＷＳＮ应用中的一项
关键技术［４］。根据在定位过程中是否直接测量节点
间的距离，可将ＷＳＮ定位算法分为测距（Ｒａｎｇｅ⁃ｂａｓｅｄ）定位算法和非测距（Ｒａｎｇｅ⁃ｆｒｅｅ）定位算法［５］。
与基于测距的定位算法相比，基于非测距的定位算法
具有成本低、功耗小、抗测量噪声能力强以及硬件设
备简单等优势，且能够提供误差允许范围内的定位服
务［６］，受到越来越多的瞩目。
在基于非测距定位算法中，ＤＶ－Ｈｏｐ算法是比较
经典的定位算法之一，但当ＷＳＮ中传感器节点分布
不均匀和不规则时，ＤＶ－Ｈｏｐ算法存在定位误差较大
的缺陷［７］。为了使定位的结果更加准确，研究者对其
算法进行了不同程度的改进。文献［８］考虑了在计算
锚节点间距离时可能存在彼此处于通信半径之内的
情况，细化了锚节点间距离，使得平均跳距更加准确；
文献［９］采用多通信半径的方法由锚节点多次广播信
息，有效改善了定位精度，但是提高了网络连通度，影 １１０ ＩｎｓｔｒｕｍｅｎｔＴｅｃｈｎｉｑｕｅａｎｄＳｅｎｓｏｒＦｅｂ２０１９
响网络成本与节点能耗；文献［１０］提出将全网中所有
锚节点平均跳距的平均值作为统一跳距，再通过细菌
觅食算法来定位节点位置，但忽略了未知节点各自跳
距的差异；文献［１１］提出引入校正因子的概念，调整
未知节点到锚节点的距离，达到了提高定位精度的目
的；文献［１２］先利用加权质心定位算法估算位置，再
结合ＴＤＯＡ信标节点计算未知节点的坐标并修正，但
该算法增加了成本且算法复杂度较高。
本文提出一种改进的ＤＶ－Ｈｏｐ定位算法，通过优
化并累加未知节点平均跳距的方法计算出未知节点
与锚节点间的距离，并引入校正因子进行二次定位修
正未知节点估算坐标，使得未知节点估算坐标更接近
实际值，提高了算法的定位精度。１ ＤＶ－Ｈｏｐ定位算法及误差分析
１．１ 传统ＤＶ－Ｈｏｐ定位算法简介
ＤＶ－Ｈｏｐ定位算法由Ｎｉｃｕｌｅｓｃｕ等提出［１３］，其主
要定位步骤分为以下３部分：（１）锚节点先通过距离矢量交换协议路由广播自
身信息，网络中所有节点记录下锚节点的坐标及相应
的最小跳数［１４］，锚节点广播消息结构如图１所示。
图１ 锚节点广播消息结构（２）锚节点接收到其他锚节点的数据后，根据公
式（１）计算平均跳距。锚节点ｉ和ｊ的坐标分别为（ｘｉ，
ｙｉ）和（ｘｊ，ｙｊ）；ｈｉｊ为锚节点ｉ和ｊ之间的最小跳数；Ｈｏｐ⁃ｓｉｚｅｉ为锚节点ｉ的平均跳距；锚节点ｉ会将自身的平
均跳距信息广播到网络中。
Ｈｏｐｓｉｚｅｉ＝∑
ｊ≠ｉ（ｘｉ－ｘｊ）２＋（ｙｉ－ｙｊ）２
∑
ｊ≠ｉｈｉｊ（１）
每个未知节点ｕ接收到距离其最近的锚节点的
平均跳距信息，舍弃其他锚节点传来的信息，再根据
步骤（１）中获取的跳数信息，估算出未知节点ｕ与各
个锚节点之间的距离。计算方法见式（２）。ｄｕｊ＝Ｈｏｐｓｉｚｅｕ×ｈｕｊ（２）
式中：ｄｕｊ为未知节点ｕ与锚节点ｊ间的距离；Ｈｏｐｓｉｚｅｕ为未知节点选取的平均跳距；ｈｕｊ为未知节点与锚节点
间的跳数。（３）当未知节点确定了与３个或３个以上锚节点
间距离后，利用极大似然法或三边测量法估计未知节
点的坐标。１．２ 误差分析
（１）在计算锚节点自身平均跳距时，锚节点利用
的是除自身以外其他所有锚节点，得到的平均跳距反
应的是全局范围内的锚节点分布情况，但是忽略了各
锚节点贡献度的大小情况。因此，若网络分布不均匀
时造成的平均跳距误差会较大。（２）计算未知节点与锚节点间距离时，根据一个
未知节点平均跳距乘以跳数的方法，没有考虑链路中
其余节点的平均跳距，误差较大。（３）传统的ＤＶ－Ｈｏｐ法得到未知节点坐标后便结
束了，没有对坐标精度进行修正的过程，可以通过已
有的条件进行调整优化。２ 改进ＤＶ－Ｈｏｐ算法描述
２．１ 平均跳距的改进２．１．１ 基于最小均方误差准则求锚节点平均跳距
传统ＤＶ－Ｈｏｐ定位算法在计算锚节点平均跳距
时采用的是基于无偏估计准则，即通过公式（３）求得：
ｆ１＝１
Ｍ－１∑
ｊ≠ｉ（ｄｉｊ－Ｈｏｐｓｉｚｅｉ×ｈｉｊ）（３）
式中：ｄｉｊ为锚节点间距离；Ｈｏｐｓｉｚｅｉ为需要求的平均跳
距；ｈｉｊ为跳数；令ｆ１等于零即可求出平均跳距。
然而，经过多次试验发现，误差服从高斯分布。
根据参数估计理论，作为估计子误差的代价函数，使用最小均方差比使用无偏估计更为合理［６］。本文采
用基于最小均方差准则来计算锚节点平均跳距，即对
公式（４）求偏导来求Ｈｏｐｓｉｚｅｉ的值。
ｆ２＝１
Ｍ－１∑ｊ≠ｉ（ｄｉｊ－Ｈｏｐｓｉｚｅｉ×ｈｉｊ）２（４）
求偏导时，要求∂ｆ２∂Ｈｏｐｓｉｚｅｉ＝０，经过等式变换可得
到式（５）。
Ｈｏｐｓｉｚｅｉ＝∑
ｊ≠ｉｈｉｊｄｉｊ∑
ｊ≠ｉｈ２ｉｊ（５）
通过上述分析，锚节点ｉ平均跳距是由跳数ｈｉｊ乘
以距离ｄｉｊ的和除以跳数ｈｉｊ平方和得到。２．１．２ 加权求未知节点自身平均跳距
传统的ＤＶ－Ｈｏｐ算法中，规定未知节点接收到第
一个锚节点传来的跳距信息则作为自身平均跳距，此
方法会带来定位误差，有许多学者提出了加权ＤＶ－Ｈｏｐ定位算法的概念［１５－１６］。本文在计算未知节点自
身平均跳距时，不仅考虑离节点最近的锚节点的跳距
信息，同时通过加权系数体现不同锚节点对未知节点
坐标运算的影响力大小，算出加权平均跳距信息为之
