一种基于移动信标节点加余弦定理的DV-Hop改进算法

胡平霞 丁锋 邓阿琴 曾斯 朱鹏

摘   要：为提高无线传感器网络节点定位精度，文章提出了一种基于移动信标节点加余弦定理的MCDV-Hop改进算法。该算法从改变移动信标节点移动轨迹基础上通过余弦定理修正跳距，在模拟WSN场景下，通过仿真实验表明，MCDV-Hop改进算法提高了网络资源利用率，在一定程度上表现出较稳定的定位精度。

关键词：无线传感器网络;定位;移动信标节点;余弦定理

中图分类号： TP393          文献标识码：A

1 引言

无线传感器网络（Wireless Sensor Networks， WSN）作为一个新的网络模型在军事、民用及商用领域都有着巨大的应用价值，逐渐成为国内外学者的研究热点。由于无线传感器网络应用的复杂性，网络节点的位置信息显得尤为重要，节点定位技术成为WSN的关键技术之一。节点定位技术是指在无线传感器网络中，通过已知节点位置信息估算未知节点位置信息的一种技术。在无线传感器网络中，已知节点称为信标节点，由于相对未知节点来说信标节点成本高，且需硬件支持，因此通常根据实际应用部署少量的信标节点，通过信标节点的位置信息来测算未知节点的位置。

根据节点定位过程中是否需要测量信标节点和未知节点间的距离，将定位算法分成免测距定位算法（Range-free）和基于测距定位算法（Range-based）两种。其中，无需测距定位算法由于在不增加硬件开销的情况下其定位精度基本上能满足实际应用，具有较大的研究价值，引起国内外学者的关注。文献[1～8]就不同的思路對非测距定位技术进行不同的研究，提出了不同的解决方案。其中，文献[5]介绍了一种利用最邻近信标节点的平均跳距以及加权后的M跳内信标节点的平均跳距，来测算未知节点的位置信息，M为增设的门限值。文献[6]介绍了通过信标节点的功率控制，通过信标节点的辅助提出了基于全网信标节点修正单个信标节点的平均跳距。文献[7]在经典DV-Hop算法的基础上，对节点间的跳数值和平均每跳跳距进行校正和修正。文献[8]使用加权双曲线定位算法（WH）思想及加权DV-Hop（WDV-Hop）思想相结合的思路。非测距定位算法，不论是在理论方面，还是技术应用方面，都是未来的重要研究方向，高精度的定位成为研究关键技术之一。本文所做的工作就是以提高定位精度为目标提出改进的DV-Hop算法。

2 介绍经典算法

2.1经典DV-Hop算法

经典DV-Hop算法根据网络中的跳数测算未知节点到信标节点直线距离，从而得到未知节点的位置信息。经典DV-Hop算法由于不需要增加额外硬件开销且计算量相对较小、容易实现等特点得到国内外研究者的关注。经典DV-Hop算法对未知节点的定位过程为三点。

（1）确定未知节点与网络中信标节点间的最小跳数值

信标节点全网广播本节点位置信息，其它传感节点收到信息后保存自身到信标节点数据信息，信标节点i的位置信息表示为，未知节点到网络中其它信标节点i的最小跳数值表示为，该数据信息记为。

（2）估算未知节点与信标节点间的距离

①信标节点自身平均跳距估算

公式1

通过公式1计算信标节点间的平均跳距，，分别表示是信标节点i、j的坐标，是信标节点i和信标节点j之间的最小跳数。

②未知节点到信标节点距离估算

公式2

通过公式2来估算未知节点到信标节点的距离，是未知节点选择最近的信标节点i的跳距平均值，是未知节点u到信标节点v的最小跳数值。

（3）确定未知节点位置

网络中的未知节点根据第（2）步的估算结果，建立自身的位置矩阵，形成线性方程式，最后通过最小二乘法计算未知节点位置。

2.2 基于移动信标节点的DV-Hop改进算法

MADV-Hop[9]是一种基于移动信标节点的DV-Hop改进算法，通过在固定位置配置移动信标节点，移动信标节点按一定轨迹移动构建出多个虚拟信标节点、采用多个虚拟信标节点的位置信息来估算未知节点位置，取多次估算的平均值。仿真结果表明，该算法在降低成本和提高定位精度方面都有不错的表现。

3 MCDV-Hop改进算法

本文提出了一种基于移动信标节点加余弦定理的MCDV-Hop算法，优化了移动信标节点位置及移动轨迹，在一定程度上降低了信标节点广播浪费，通过余弦定理修正跳距[10]提高定位精准度。

3.1 改进思路

（1）优化移动信标节点部署及移动轨迹

MADV-Hop算法部署的移动信标节点呈矩形分布，如图1所示，在中心位置、四个角及区域内部署Q、A1-A4、B1-B4共9个移动信标节点。其中，四个角的移动信标节点在广播时，有一半的广播信息面向区域外，存在广播浪费现象，因此对移动信标节点位置和移动轨迹的优化十分必要。

改进后的算法在的监测区域中的固定位置部署9个移动信标节点，如图2所示。其中，信标节点G部署在位置（），且为唯一的固定的信标节点，a1-a4 4个移动信标节点分别部署在正方形监测区域的4边的中间（即）位置，而b1-b4 4个移动信标节点分别部署在距离4个边缘的中间部分。

以移动信标节点a1、b1为例，它们各自按一定的间距△d沿着外圆和内圆逆时针移动，会形成一定数量的虚拟信标节点。每次移动到新位置就广播一次位置信息，为减少浪费，每次移动的新位置不能与之前广播过的虚拟信标节点位置重复。当全部移动信标节点所形成的虚拟信标节点对自身位置广播达到一定次数（一般取4次）或更多时，停止移动。由于移动信标节点是沿圆形轨迹运动，移动后的新位置坐标在原位置基础上，通过余弦定理和移动距离△d进行计算。

（2）余弦定理校正平均跳距

由于网络中节点的分布存在紧密和稀疏的差异，当节点稀疏且呈不均匀分布时经典DV-Hop算法的定位结果会出现较大概率的误差，从而影响了定位精度，通过余弦定理对估算后的平均跳距离进行修正，减少误差，提高定位精度。

根据连接到每个信标节点最小跳数的传输路线，选择路线中间节点。如图3和图4所示，为奇数时，选择路径的中间节点即可;为偶数时，选择路径中间的两跳都将作为中间节点。其中，中间节点和信标节点连接所形成的夹角为。

可以证明[10]当为奇数时：

公式3

当为偶数时：

公式4

是两个信标节点间的跳次，是两个信标节点间的跳数。最后的校正调整值correct_ value可由平均跳距、实际跳距和跳数得出：

公式5

通过上述跳距校正值来校正跳距。

3.2 MCDV-Hop算法定位思想

改进算法伪代码描述如图5所示，定位过程描述为八点。

（1）启动网络并完成初始化。初始化工作包括节点信息、移动信标节点移动轨迹。

（2）信标节点使用洪泛算法广播自身位置信息，广播次数为4次。

（3）邻节点处理到达的数据包。邻节点判断到达的数据包是不是首次来自该信标节点，若是首次收到则直接保存;不是则比较当前数据包的最小跳数和已经保存数据包的最小跳数，选择跳数较小的数据包保存。

（4）计算平均跳距，并计算未知节点到信标节点的距离。

（5）修正平均跳距。选择中间节点，获得角度，使用余弦定理修正跳距，见公式3、公式4、公式5，使用修正后的平均跳距計算未知节点距离。

（6）估算未知节点位置坐标。根据信标节点坐标信息和未知节点到信标节点间的距离信息建立位置矩阵，采用最小二乘法计算未知节点坐标。

（7）信标节点按△d移动，更新位置后返回第（2）步。

（8）在未知节点至少得到3次以上自身坐标后，取平均值。

4 模拟仿真实验

4.1 仿真环境及参数说明

仿真实验在Matlab2016a环境下进行，仿真参数如表1所述。

模拟WSN场景为二维平面区域，节点分布见图6，其中三角形代表信标节点，菱形代表未知节点。在100m×100m的正方形区域内布置100个未知节点和9个移动信标节点，其中未知节点坐标随机，移动信标节点坐标预设，初始化后所有节点均能正常工作。考虑未知节点坐标的随机性，选择100次仿真计算的平均值作为对比结果。

平均相对定位误差计算公式为：

公式6

其中U是节点数，v 是信标节点数，M为通信半径，truei为坐标真实值，cali为坐标估算值。

4.2 仿真实验结果

（1）定位误差分析

改进算法的定位误差如图7所示，纵轴为估算的节点坐标与实际坐标的偏差，横轴为未知节点个数，最小误差在5%以下，最大误差约为25%。

（2）通信半径对定位精度影响分析

在其它仿真参数不变的情况下改变通信半径，对DV-Hop算法、MADV-Hop算法及改进后的算法MCDV-Hop的定位精度进行对比，定位半径分别为20m、25m、30m、35m、40m、45m。图8表明3种算法的定位精度在较大通信半径情况下表现良好，随着通信半径增加定位误差呈下降趋势。DV-Hop算法定位精度受通信半径变化的影响相对较小;通信半径有30m以下时，改进算法MCDV-Hop的定位精度由于移动信标节点按圆形轨迹运动，以减少广播资源浪费为前提牺牲少许覆盖率，因此定位精度略小于原MCDV-Hop算法;MCDV-Hop改进算法在通信半径30m处开始保持平缓下降趋势，因此当通信半径较大时，MCDV-Hop算法表现出比DV-Hop算法、MADV-Hop算法较优的定位精度。

5 结束语

通过定位误差仿真实验及通信半径对定位精度仿真实验影响仿真实验可以看出，改进算法MCDV-Hop仿真环境下保持较稳定的定位误差，对比DV-Hop算法和MADV-Hop算法，在节约资源降低成本前提下当通信半径达到一定值时，表现出稳定、较小的定位精度。

基金项目：

1.衡阳市科技计划项目（项目编号：2016KJ20）;

2.湖南省教育厅科学研究项目（项目编号：16C0565）;

3.衡阳市社会科学联合会项目（项目编号：2017D107）;

4.湖南环境生物职业技术学院支柱工程项目（项目编号：湘环院教字〔2017〕46号）。

参考文献

[1] Koen Langendoen，Niels Reijers.Distributed localization in wireless sensor networks： a quantitative comparison [J]. Computer Networks， 2003， 43（4）： 499-518.

[2] Zhongmin Pei，Zhidong Deng，Shuo Xu，Xiao Xu.Anchor-Free localization methord for moblie targets in coal mine wireless sensor networks[J].SENSORS， 2009， 9（4）：2836-2850.

[3] Yun Wang， Xiaodong Wang， Demin Wang，and Dharma P. Agrawal. Range-free localization algorithm using expected[J].IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS， 2009， 20（10）：1540-1552.

[4] He Yuanhua， Li Hongsheng.A distributed node localization algorithm based on believable factor wireless sensor network[A].Proceedings-5th International Conference on wireless Communications， Networking and Mobile Computing （WiCOM 2009） [C]. Beijing， 2009：1-4.

[5] HU Y，LI X. An improvement of DV-Hop localization algorithm for wireless sensor networks [J]. Telecommunication Systems，2013，53（1）：13-18.

[6] 陶志勇，魏强，刘影.多功率锚节点辅助的DV-Hop定位算法[J].计算机工程与应用，2014（21） ：121-124，156.

[7] 夏少波，邹建梅，朱晓丽，等.无线传感器网络DV-Hop定位算法的改进[J].计算机应用，2015（2） ：340-344.

[8] MASS-SANCHEZ J，RUIZ-IBARRA E，et al. Weighted Hyperbolic DV-Hop Positioning Node Localination Algorithm in WSNs[J].Wireless Personal Communications，2017，96（1-23）：5011-5033.

[9] 冯友兵，马艳，魏玉婷.基于移动锚节点的改进DV-Hop算法[[J].计算机科学，2015， 42（s2）：277-279.

[10] Wu H， Deng M， Xiao L， et al. Cosine Theorem-based DV-Hop Localization Algorithm in Wireless Sensor Networks[J]. Information Technology Journal， 2011，10（2）：239-245.

作者簡介：

胡平霞（1984-），女，汉族，湖南永州人，广西师范大学，硕士，湖南环境生物职业技术学院，副教授;主要研究方向和关注领域：计算机软件与理论、职业教育教学改革。

丁锋（1984-），男，汉族，湖南常德人，中南林业科技大学，本科，湖南环境生物职业技术学院，助理研究员;主要研究方向和关注领域：计算机软件与理论。

邓阿琴（1980-），女，汉族，湖南醴陵人，南华大学，硕士，湖南环境生物职业技术学院，副研究员;主要研究方向和关注领域：网络理论基础研究。

曾斯（1984-），女，汉族，湖南衡阳人，衡阳师范学院，硕士，湖南环境生物职业技术学院，讲师;主要研究方向和关注领域：网络基础理论研究、计算机教育。

朱鹏（1981-），男，汉族，湖南衡阳人，东华理工大学，本科，湖南环境生物职业技术学院，实验师;主要研究方向和关注领域：计算机网络应用。