一种基于DV-Hop节点的室内定位改进算法

干建勇, 张 静

(上海师范大学 信息与机电工程学院,上海 200234)

一种基于DV-Hop节点的室内定位改进算法

干建勇, 张 静

(上海师范大学 信息与机电工程学院,上海 200234)

对现有基于最小二乘法的DV-Hop定位算法进行分析和仿真,针对该算法定位精度依赖信标节点之间跳距和跳数这两个信息的不足,给出一种可对信标节点之间的跳距和跳数关系做出误差修正的改进的误差修正DV-Hop(ECDV-Hop)算法.仿真结果表明:在相同的室内环境下,ECDV-Hop算法与传统DV-Hop算法相比,定位精度得到一定的提高.

无线传感器网络; 室内定位; DV-Hop; 最小二乘法; 误差修正

0 引 言

随着信息科技的发展,无线传感器网络(WSN)的应用越来越多地跨学科交织、融合.在室内定位应用中,如何用已知定位信息的锚节点(信标节点)来确定该环境下未知节点的信息是目前WSN热门研究课题之一.

WSN定位算法可以分成两类,即基于距离的定位和与距离无关的定位.基于距离的定位算法需要掌握信标节点和未知节点之间任意的一种相互度量关系,如角度、距离、信号强度等,以此来计算未知节点的位置[1],测距方法包括TOA法、TDOA法、AOA法和RSSI 法[2];与距离无关的定位算法主要有质心算法、DV-Hop算法、APIT算法等[3].其中DV-Hop算法具有部署网络成本低的优点,缺点是精度不够高.[4-6]改进了该算法并取得了一定的效果,但每种改进算法均存在一定的缺陷.

本文作者在DV-Hop算法的基础上,通过修正信标节点之间的跳数信息和相对距离来提高定位精度,提出了改进的定位算法ECDV-Hop,并仿真对比了改进算法与DV-Hop算法的优劣.

1 DV-Hop定位算法

DV-Hop算法的基本思想是通过计算平均每跳距离来获取未知节点到信标节点之间的距离,然后使用最小二乘法求出未知节点的位置信息.算法主要分为3个阶段:

1)计算所有未知节点到每个信标节点的最小跳数.每个信标节点向邻节点广播自身的位置信息,每个未知节点都有一张数据表(xi,yi,hi),其中xi和yi是该节点收到的某一个信标节点的坐标,hi是该节点到信标节点的最小跳数.未知节点只有在与邻节点交换信息时才会更新该表.未知节点记录每个信标节点到自身的最小跳数,忽略来自同一个信标节点的较大跳数.然后将跳数值加1并转发给邻节点.通过这个方法,网络中的所有未知节点能够记录其到每个信标节点的最小跳数[4].

2)计算未知节点到信标节点的平均距离.每个信标节点根据第一个阶段中记录的位置和跳数信息,得到每跳的平均距离为

(1)

式中hij是信标节点i和j(i≠j)之间的跳数,(xi,yi)、(xj,yj)分别为信标节点i、j的坐标,n为整个网络中的信标节点总数.

未知节点从距其最近的信标节点获得平均每跳距离,并转发给邻节点.这个广播策略确保大多数未知节点从其最近的信标节点处获得平均每跳距离.未知节点根据每跳跳数和平均每跳距离计算其到信标节点的跳距

(2)

式中h是未知节点到信标节点i的跳数.

3)计算未知节点的坐标.在已知3个或者更多信标节点信息的情况下,利用最小二乘法计算未知节点坐标.设(x,y)是未知节点P的坐标,(xi,yi)是第i个信标节点的坐标,di是第i个信标节点到P的距离,有[5]:

(3)

将(3)式中所有等式两边平方,用前n-1个等式分别减去第n式后,变换为:

AX=B,

(4)

(5)

2 改进的ECDV-Hop定位算法

2.1 误差分析

图1 DV-Hop平均跳距示意图

传统DV-Hop算法的主要误差来源是将平均跳距和平均跳数作为未知节点到信标节点的距离,未知节点仅仅将信标节点的平均跳距作为该节点自身的平均跳距,但是,随机部署的网络拓扑结构通常不规则,从而导致估算距离的误差;同时,信标节点间的跳距只是通过两个信标节点间的距离和与总跳数之比计算得出,在一定程度上会影响定位精度,如图1所示,其中信标节点L1、L2、L3位置已知,相互之间的欧式距离分别为DL1L2、DL1L3、DL1L3.

根据DV-Hop定位算法求得的信标节点间的跳数值为hL1L2=2,hL1L3=7,hL2L3=5,利用(2)式计算得到信标节点的平均跳距为:

由图1可知,信标节点与未知节点、信标节点与信标节点间的跳段距离往往不是直线,直接用(2)式计算信标节点的平均跳距必然存在着较大的误差.并在定位过程中不断累加,因此信标节点的平均跳距的精确度十分重要.

2.2 改进算法ECDV-Hop

针对上述的传统DV-Hop算法的不足,改进算法首先是将每跳距离平均得到全网的平均每跳距离,然后计算每个信标节点每跳距离的平均误差,得到更加准确的网络平均每跳距离:

(6)

则每个未知节点计算到各个信标节点的估计距离为

(7)

利用整个网络平均跳距替代最近的信标节点的平均每跳距离,使未知节点与各信标节点之间的估算距离更接近实际距离,从而提高定位精度.但当用计算出的全网平均跳距去计算信标节点之间的距离时,发现仍旧存在着误差.因此,在已知平均每跳距离的基础上,通过分析每个信标节点的平均跳距误差,多次迭代来修正之前得到的全网平均跳距,进一步提高定位精度[6].

信标节点i的平均每跳距离误差为

(8)

为了实施改进算法,需在定位的第二个阶段增加信标节点转发信息到邻节点的阶段,通过计算整个网络的平均跳距,用(8)式多次迭代计算各个信标节点的平均每跳距离误差,并且将该误差广播至其他信标节点.每个未知节点接收到erri后,继续向其邻节点广播.经过该阶段的多次广播和转发后,所有节点(包括信标节点和未知节点)都已知所有信标节点计算的平均跳距误差,然后再将所有的平均每跳距离误差取平均,误差修正后得到全网的平均每跳距离误差:

(9)

由此迭代得到整个网络的平均每跳距离,修正得到新的网络平均每跳距离为

(10)

式中k为变量参数,取值随具体的网络环境而定,k的取值大小也影响着误差修正的效果,从而影响定位精度.

循环(8)～(10)式进行K次迭代,直到误差修正的变化值趋于稳定,此时,每个未知节点到各个信标节点的估算距离为

(11)

当未知节点得到信标节点的估算距离之后,利用(5)式就能算出自己的估计坐标.

3 实验仿真与比较

3.1 迭代次数的选择

根据(8)～(10)式,在100 m×100 m的正方形区域内,随机放置200个传感器节点(包括20个信标节点和180个未知节点),每个节点的通信距离是50 m,k都取0.6,比较多次迭代的效果选出最优迭代次数.当迭代次数为2时,根据全网平均每跳距离得到的定位误差最小,因此选此时的平均距离作为估计距离值,如图2所示.

图2 平均定位误差与迭代次数关系图

3.2k的选择

在ECDV-Hop算法的式(10)中,k的值影响着定位精度.在实验中,通过改变k(从-1到1,以0.1为间隔)观察其对定位误差的影响,仿真结果如图3所示.由图3可知,当节点总数和信标节点数固定的情况下,定位误差取决于k的值.当k从-1增加到0.6时,定位误差随k值的变大而减小,因此当k=0.6时,定位误差最小,定位精度最高.以下都取k=0.6.

3.3 节点通信距离对定位精度的影响

在实验中,通过改变节点的通信距离来观察其对定位误差的影响,仿真结果如图4所示.从图4可知,在相同的网络环境下,ECDV-Hop算法的定位误差比 DV-Hop小,定位误差随着节点的通信距离变大而增大,需找到平均定位误差和通信距离之间的平衡,以下通信距离选为40 m.

图3 平均定位误差与k值关系图

图4 平均定位误差与通信距离关系图

3.4 信标节点数对定位精度的影响

定位误差和信标节点数的关系如图5所示,图中的传感器节点总数为300个,其中信标节点为20个.从图5可知,DV-Hop算法和ECDV-Hop算法的定位误差都随着信标节点数的增加而减少.ECDV-Hop算法的误差减少更加显著,因为在ECDV-Hop算法中,信标节点的覆盖率越高,平均每跳距离更接近于实际每跳距离;随着信标节点数的增加,未知节点到信标节点的跳数减小,定位误差也随之变小.

最后,设置仿真环境为在100 m×100 m的区域内随机放置100个传感器节点,其中包括10个信标节点,通信的平均距离为40 m,进行多遍不同次数的仿真,结果如图6所示.由图6可知,ECDV-Hop算法的定位误差要明显地小于DV-Hop算法,通过计算可以得知,ECDV-Hop算法的平均定位误差为0.2633,DV-Hop算法的平均定位误差为0.3122,因此改进算法具有一定的精度优势.

图5 平均定位误差与信标节点数关系图

4 结 论

分析了DV-Hop算法的原理和误差并且给出了改进的ECDV-Hop算法.该改进算法采用加权每跳距离来修正全网平均每跳距离的误差,使其更接近于实际的平均每跳距离.该算法不需要额外的硬件支持.仿真结果表明,改进算法的定位精度优于传统算法.与此同时,改进算法也存在不足,通信量和计算量要高于传统算法,这也导致了更大的算法代价.

[1] Wang L H,Zhang G X,Shen X F.Mobile anchor nodes aided DV-hop(M-A-DV-hop) algorithm [J].Journal of Hangzhou Dianzi University,2008(5):312-315.

[2] 林金朝,刘海波,李国军,等.无线传感器网络中DV-Hop节点定位改进算法研究 [J].计算机应用研究,2009,26(4):1272-1275.

Lin J C,Liu H B,Li G J,et al.Study for improved DV-Hop localization algorithm in WSN [J].Application Research of Computers,2009,26(4):1272-1275.

[3] Brito L A,Liu Y,Garcia Y.An improved error localization on DV-Hop scheme for wireless sensors networks [J].2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE),2010,6:V2-80-V2-84.

[4] Cui H M,Wang Y F,Liu L N.Improvement of DV-HOP localization algorithm [C]//IEEE.Identification and Control (ICMIC),Sousse:IEEE,2015.

[5] 彭刚,曹元大,孙利民.无线传感器网络节点定位机制的研究 [J].计算机工程与应用,2004,40(35):27-29.

Peng G,Cao Y D,Sun L M.Study of localization schemes for wireless sensor networks [J].Computer Engineering and Applications,2004,40(35):27-29.

[6] Wei Q,Han J,Zhong D,et al.An improved multihop distance estimation for DV-Hop localization algorithm in wireless sensor networks [C]//IEEE.2012 IEEE Vehicular Technology Conference (VTC Fall),Quebec City:IEEE,2012.

(责任编辑：顾浩然,包震宇)

An improved algorithm of indoor positioning based on DV-Hop nodes

Gan Jianyong, Zhang Jing

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

In this paper,we analyzes and simulates DV-Hop algorithms based on the least square estimation frame.The accuracy of the algorithms depends on the information of jump number among beacon nodes.To overcome this drawback,we presents an improved algorithm of error correction DV-Hop (ECDV-Hop).The simulation results show that,in the same indoor environment,the positioning accuracy of ECDV-Hop algorithm is higher than DV-Hop algorithm.

wireless sensor networks; indoor positioning; DV-Hop; least squares; error correction

10.3969/J.ISSN.1000-5137.2017.01.009

2016-11-29

干建勇(1993-),男,硕士研究生,主要从事移动信号室内定位方面的研究.E-mail:76038645@qq.com

导师简介: 张 静(1971-),女,博士,副教授,硕士生导师,主要从事移动通信信号处理方面的研究. E-mail:jannety@shnu.edu.cn(通信联系人)

TN 929.5

A

1000-5137(2017)01-0048-06