一种改进DV-HOP无线传感器网络定位算法

邬春明，杨　涛，马冬梅，郭　健，赵宇新

(1.东北电力大学 信息工程学院，吉林 吉林 132012；2.国网吉林供电公司 信息通信分公司，吉林 吉林 132012)



一种改进DV-HOP无线传感器网络定位算法

邬春明1，杨涛1，马冬梅2，郭健2，赵宇新2

(1.东北电力大学 信息工程学院，吉林 吉林 132012；2.国网吉林供电公司 信息通信分公司，吉林 吉林 132012)

针对大型网络不规则性及翻转歧义造成距离向量-跳段(DV-HOP) 定位算法性能较差的问题，提出了一种改进的DV-HOP定位算法。针对不规则网络，提出了一种基于节点密度的误差修正方法。网络区域部署节点数量大，节点翻转歧义误差不可避免，故提出了一种基于半圆模型的定位误差修正方法。仿真实验表明：本文改进算法比现有改进算法的定位精度提高了6%，并且能够有效地弱化翻转歧义造成的误差，因此能够较好地实现对未知节点的实时精准定位。

距离向量-跳段；节点密度；翻转歧义；半圆模型；无线传感器

0　引言

目前，无线传感器网络应用于越来越多的领域，而且对监测事物的坐标精度要求越来越高。通常，装有全球定位系统 (globalpositioningsystem，GPS)装置的传感器节点能够实现较高的定位精度，但其定位成本太高，若能找到一种利用少量装有GPS装置的传感器节点就能实现对未知节点定位的算法，则无线传感器网络的节点定位成本将大大降低。因此，无线传感器网络定位算法的研究成为科研工作者的关注重点[1-2]。

距离向量-跳段(distancevector-hop,DV-HOP)定位算法通过计算网络中平均跳距和跳数方式来计算未知节点与锚节点之间的距离，从而利用三边测距或极大似然法计算未知节点的坐标。影响其定位精度的因素有网络的不规则、平均跳距值的误差和节点的翻转歧义误差等[3-4]。翻转歧义误差的定位算法主要弱化其对算法精度的影响，例如，文献[5]中IIBM算法(iterativeinflexiblebodymergingalgorithm)、文献[6]中IP-TNB算法(iterativeprocessingmethodbasedontriangularnodeblocks)和文献[7]中RAMP算法(refinementalgorithmbasedontheideaofmagneticpole)。IIBM算法提出了一种基于节点块状合并的翻转歧义修正算法，但由于该算法使用了多种节点块形状，造成变形，同时其通信开销也较大。为了解决该问题，文献[6]提出了IP-TNB算法，该算法主要运用了稳定性更好的三角节点块和网络连通度信息对其进行修正，但是该算法容错性较差，并且对测距误差敏感。针对不规则网络造成的定位误差，文献[8]提出无线传感器网络DV-HOP算法的一种优化方法，该方法利用多个信标节点的平均跳距值的加权处理值替代节点间平均跳距值，再利用交叉粒子群算法对定位结果进行优化，该算法能够使精度提高，但是计算量较大，且未考虑网络中存在的节点翻转歧义问题，故仍存在改进空间。因此，本文针对不规则网络和翻转歧义造成的定位误差，提出了一种适用于农田环境的改进DV-HOP定位算法。

1　基于节点密度的误差修正方法

由于大型网络区域的节点是通过飞机随机部署的，容易形成不规则网络，区域内的节点密度不同，如图1所示。图1中：S1,S2,S3,S4和S5均为锚节点，A为未知节点，各锚节点通过网络中其他锚节点计算其平均跳距，并将该值广播至全网，各未知节点保存第1次接收到的平均跳距。节点S1的平均跳距通过与其他4个锚节点之间的欧氏距离和跳数计算而来。显然，利用保存的平均跳距，节点A到锚节点S2、S3、S4和S5的距离值与真实值之间存在误差，这将影响节点的定位精度。

图1　大型网络区域节点分布图

针对上述问题，本文提出了基于密度的节点误差修正方法。先定义几个符号含义：

HopCounti为未知节点到锚节点的跳数；NodeCount为节点周围1跳节点的数量；a_ID、s_ID和rec_ID 分别为锚节点、传感器节点和接收节点的ID号。

假设在某一区域内至少有两个锚节点,锚节点i广播一个含有{a_IDi，s_IDi，Pos，HopCounti}的消息，并将s_IDi初始化为a_IDi，HopCounti初始化为0，当一邻居节点接收到该消息后，a_IDi，s_IDi和Pos保持不变，HopCounti加1，该邻居节点保留这一新消息，并将s_IDi保存至rec_IDj，同时将s_IDi设置为s_IDj。事实上，每次邻居节点收到消息后都会检查rec_IDj是否与之前收到值相同，若不同，则保留，同时NodeCountj加1。按上述方式继续向全网广播，最终各锚节点也会检查rec_IDj与之前保存值s_IDi是否相同，若不同，则NodeCounti加1，则各节点可以统计出周围节点数量。利用下式可求出各节点周围节点密度：

(1)

由式(1)可知：n_ratej越小，节点的密度越靠近，若n_ratej<β，则可认为这两个节点处于同一密度区域内(β为阈值，在本文中设定β为0.15)。但是有一些边界节点并不符合这一规律，故在本文中，若某一节点不与任何节点处于同一密度区域，则将其视为与其最近的锚节点具有相同的密度区域。在同一密度区域的节点保存该区域内由锚节点广播的平均跳距hop_len。至此，节点分区完毕，下一步将计算未知节点到各锚节点之间的距离值。

首先，每个锚节点广播消息至全网，当某一未知节点收到该消息后，检查HopCounti是否小于之前收到值，若满足，则HopCounti加1，并向全网继续广播，否则丢弃该消息；其次，同时检查收到的hop_len是否等于之前保存值，若相同，则利用下式计算该未知节点距离目标锚节点的距离值：

new_ddis=hopleni+a_dis,

(2)

其中：new_adis为某一未知节点距目标锚节点的距离值;a_dis为最短路径中上一中继节点更新的距离值。若不相同，则利用下式计算该未知节点距离目标锚节点的距离值：

new_adis=hoplenj+a_dis,

(3)

其中：hoplenj为该未知节点保存的平均跳距值。

每个未知节点同时可作为中继节点转发消息，其中,未知节点的new_adis保存至a_dis中，并伴随消息广播至全网。最终,各未知节点可计算出与各锚节点的距离值，再利用三边测量法或极大似然法计算未知节点的坐标值。

2　基于半圆模型的弱化节点的翻转歧义误差修正方法

图2　节点分布图

针对大型无线传感器网络产生的翻转歧义误差，本文提出了基于半圆模型的弱化节点的翻转歧义误差修正方法。节点分布图见图2。图2中：P为未知节点；A、B、C为锚节点。节点P利用三边测量法计算节点的坐标时，若锚节点A、B、C呈线性关系，则节点P计算出的坐标存在一个镜像坐标P′，该镜像坐标继续参与其他节点定位，则会造成整个算法的定位精度降低，这种误差被称为“翻转歧义误差”[9]。

该误差修正方法由两步组成：节点翻转歧义误差检测和误差修正。其中，节点翻转歧义误差检测是通过文献[7]提出的“跳数-距离矛盾”理论来检测节点是否存在翻转歧义误差。“跳数-距离矛盾”理论为：当某一节点与邻居节点之间的距离大于最大通信半径或与二跳节点的距离小于最大通信半径时，则认为其存在“跳数-距离矛盾”。为了具体描述这种矛盾的大小，提出了下面的公式：

(4)

(5)

(6)

若Ei(k)满足以下条件：

(7)

则该节点存在翻转歧义误差，需要对其进行误差修正；反之，则为有效节点。其中：Wi为节点i周围1跳节点的数量。

图3　半圆模型节点分布图

为了弱化节点翻转歧义误差，提出半圆模型方法，该方法通过缩小误差节点所在的误差区域面积，同时利用射线法及最小二乘法计算节点的最小误差坐标。半圆模型节点分布图如图3所示。图3中：节点P存在翻转歧义误差；A、B和C为节点P的3个邻居锚节点；R为最大通信半径。以A、B、C为圆心，R为半径，分别作圆，则节点P所在的最大误差面积为3个圆的相交部分。

若节点C更靠近节点A，则以A为圆心， dac为半径作圆；反之则以B为圆心， dbc为半径作圆，误差节点所在区域图如图4所示。首先分析第1种情况，半圆与鱼形椭圆的相交，将鱼形椭圆分为S1、S2两部分，则节点P位于S1或S2区域内。若满足条件RSSIAC>RSSIPC，则位于S1区域内；反之，则位于S2区域内。按照相同的方式，可判断第2种情况下，节点位于S3或S4区域内。

图4　误差节点所在区域图

图5　节点P新的所在区域面积图

假定Mn={M1,M2,…,Mn}为锚节点C周围的一系列有效节点，分别以这些节点为圆心，dMn,C为半径作圆，则可得到一系列的半圆SCS(Mn,C)={SCS(M1,C),SCS(M2,C),…,SCS(Mv,C)}。图5为节点P新的所在区域面积图。图5中：SCS(M1,C)为以M1圆心，dM1,C为半径的半圆，则半圆与S1相交部分为S5，再比较RSSIM1C与RSSIPC的大小，则可判断节点P所在的区域。

事实上，每次作半圆后判断RSSIMnC与RSSIPC的大小都可以得到一个新的位置区域面积，最终可以获得一个误差节点所在的最小区域面积，如图6所示。图6中：Sf为最小区域面积。

图6　节点P的最小区域面积

假定Uv={U1,U2,…,Uv}为节点P周围一系列有效节点，以Uv为圆心，dUv,p为半径作圆，则可得到一系列与Sf的交点。由于最小误差区域为形状不规则的区域，本文采用射线法判断这些节点是否位于最小误差区域内部。射线法原理如下：

作一系列以交点的纵坐标k的射线，并让射线穿过Sf，若射线与最小误差区域的交点个数为奇数时，则该点位于该区域内，反之则不在。射线的可用公式表示如下：

(8)

其中：(xc,yc),(xp,yp)分别为节点C和节点P的坐标。

为了从这些区域内部的交点中选出节点P的最小误差坐标，首先定义了以下公式：

(9)

其中：W为所有的邻居节点；dij为节点i与节点j之间的欧氏距离。

利用上述方法即可求出节点P的最小误差坐标，从而提高定位精度。

3　仿真实验

为了验证本文算法的性能，采用MATLAB7.0对其进行仿真，并与经典DV-HOP算法、文献[8]中的DV-HOP算法和文献[10]中的DV-HOP算法进行比较分析。

3.1仿真参数设置

在实验中，为了与大型随机部署节点的无线传感器网络特性相符合，首先，在150 m×150 m正方形区域内按相同某一通信半径R随机部署了100个节点，并在不同的通信半径情况下，通过部署不同的锚节点数量去验证算法的性能；其次，为了分析节点数量对算法精度的影响，固定最大通信半径20 m，锚节点数量所占比例为0.15，在该区域内改变节点的数量，分别部署50～300个节点，分析其对节点定位误差的影响。定义未知节点的平均定位误差公式为：

(10)

(11)

3.2实验结果分析

图7是最大通信半径分别为20 m和30 m时，节点的归一化平均定位误差随区域内锚节点数量的关系。从图7可以看出：随着锚节点数量增多，节点的定位误差开始下降，并最终趋于稳定。本文算法的性能优于其他3种算法，这是因为本文算法计算的未知节点到锚节点之间的距离值更接近真实值，且本文提出的翻转歧义修正方法能够有效地弱化节点翻转歧义造成的误差。

固定锚节点数量为15个，并将最大通信半径从30 m到60 m变化，观察其对节点定位精度的影响，其结果如图8所示。由图8可知:本文算法的性能优于其他3种算法，节点的平均定位误差下降缓慢并最终趋于稳定，且节点的最大通信半径为40 m时，这4种算法均能够获得一个较好的定位精度。

图9显示了节点数量对节点定位精度的影响。由图9可知:随着节点数量增加，前3种算法的定位误差是一个先下降后平稳，然后再上升再平稳的过程，但本文算法的定位误差则是先下降后逐步平稳，故其性能更优。主要是因为随着节点数量增多，网络连通度提高，节点定位精度也随之提高。此外，网络中随着节点数量的增加，发生节点翻转歧义误差的概率会增大，而本文算法正好能够弱化其误差。

图7　节点的归一化平均定位误差随区域内锚节点数量的关系

4　结束语

本文针对大型不规则无线传感器网络及节点产生的翻转歧义误差对定位算法精度的影响，提出了一种改进DV-HOP算法。该算法针对不规则网络提出了一种基于密度的误差修正方法来修正未知节点与各锚节点之间的距离值。同时，针对节点存在翻转歧义误差，提出了一种基于半圆模型的误差修正方法。本文算法能够有效地提高定位精度，其定位性能优于经典DV-HOP定位算法及其改进算法。

[1]BEN S Y,BLAUNSTEIN N.Localization and positioning of any subscriber in indoor environments on the basis of analysis of joint AOA-TOA signal distribution[C]//IEEE APS Topical Conference on Antennas and Propagation in Wireless Communications.2013.

[2]KONE C T,HAFID A,BOUSHABA M.Performance management of IEEE 802.15.4 wireless sensor network for precision agriculture[J].IEEE sensors journal,2015,15(10):5734-5747.

[3]WANG Y,FANG Z Y,CHEN L.A new type of weighted DV-Hop algorithm based on correction factor in WSNs[J].Journal of communications,2014,9(9):699-705.

[4]WANG S Z,LI Y.Node localization algorithm based on RSSI in wireless sensor network[C]//Proceedings of 2012 6th International Conference on Signal Processing and Communication Systems.2012.

[5]XIAO Q J,XIAO B,BU K.Iterative localization of wireless sensor networks:an accurate and robust approach[J].IEEE/ACM transactions on networking,2014,22(2):1-14.

[6]董恩清,刘伟,宋洋.采用三角形节点块处理无线传感器网络节点定位中节点翻转歧义的迭代方法[J].西安交通大学学报,2015,49(4):1-7.

[7]YAO Y B,JIANG N L.Distributed refinement algorithm for WSN localization[J].Journal on communications,2015,36(1):1-10.

[8]李海龙,李宝华,韩彦春.无线传感器网络DV-Hop算法的一种优化方法[J].辽宁工程技术大学学报(自然科学版),2016,35(5):523-528.

[9]LIU W,DONG E Q,SONG Y,et al.An improved flip ambiguity detection algorithm in wireless sensor networks node localization[C]//21st International Conference on Telecommunications(ICT).2014.

[10]邬春明,张金强,焦龙龙.基于RSSI跳数连续的DV-HOP改进算法[J].重庆邮电大学学报(自然科学版),2015,27(2):184-188.

国家自然科学基金项目(61301257);吉林省科技发展计划基金项目(20130206050GX)

邬春明(1966-),男,吉林省吉林市人,教授,硕士,硕士生导师,主要研究方向为无线传感器网络节点定位算法.

2016-05-16

1672-6871(2016)06-0055-06

10.15926/j.cnki.issn1672-6871.2016.06.012

TN92

A