一种基于DV-Hop的无线传感器网络节点定位算法

王景珲

(国家数字交换系统工程技术研究中心,郑州450001)

一种基于DV-Hop的无线传感器网络节点定位算法

王景珲

(国家数字交换系统工程技术研究中心,郑州450001)

针对无线传感器网络节点的自身定位问题,提出一种基于分布式协作的DV-Hop改进算法。在距离计算的基础上,采用最大似然估计方法选取共线度较低的参考点作为锚节点。综合考虑所有锚节点,以可信度为准则,通过加权平均计算每一个未知节点的平均跳距。计算未知节点的定位误差,将误差低于预设阈值的未知节点转化为锚节点,扩大定位范围。仿真结果表明,在初始锚节点数和通信半径相同的情况下,该算法的定位误差比DVHop算法减少约20%,尤其当节点密度较小时,其定位误差可稳定在40%以下。当节点通信半径超过10 m时,该算法的剩余节点比例可降低约30%。

无线传感器网络;DV-Hop算法;锚节点;共线度;协作定位

1 概述

无线传感器网络的节点定位技术是网络应用的关键支撑技术之一。对于无线传感器网络应用来说,节点的位置信息非常重要。传感器节点的位置可以标示监测数据源的位置,为网络管理提供拓扑结构,并可生成用于数据传输的路由协议。传感器节点的位置可以通过配置GPS定位装置或人工定位布置获得,但由于传感器网络的节点数量较大,GPS定位装置的费用较高,因此目前常用的做法是,网络中的少量锚节点配备GPS接收器或人工布置,其他节点依靠锚节点的位置信息和节点间的通信或测距技术,通过相应的节点定位算法来获得其位置信息[1-2]。

迄今为止,研究人员分别从不同的角度来考虑WSN节点的定位问题,如网络拓扑、设备能力、定位精度和能量需求等,并提出了很多行之有效的节点定位算法。美国Rutgers大学的Niculescu提出了一系列分布式定位算法APS(Ad hoc Location System),其中DV-Hop定位算法DV-Hop(DistanceVector-Hop)是目前应用最为广泛的一种,该算法根据距离矢量路由和GPS定位原理,仅依靠网络的连通度就能实现对未知节点的定位,而且传感器节点不需要任何的额外硬件设施。对于节点分布较规则、锚节点密度较大的传感器网络,该算法具有定位速度快、计算复杂度低、扩展性较好等优势。

协作定位是近年来提出的新概念,是对传统节点定位方法的扩展[3]。在传统方法中,定位参数主要是指锚节点和未知节点间的距离、角度等信息,未知节点间的信息被忽略。而在协作方式中,任意2个未知节点间可以相互得到测量数据,能够使不在锚节点传输距离内的节点也能被定位。利用协作思想,未知节点获取自身位置信息后可以有条件地转化为锚节点,从而获得冗余信息,用来进一步提高定位算法的精度和鲁棒性。文献[4-5]都将协作思想应用于节点定位算法,通过循环求精的过程来得到较高的定位精度。

本文在DV-Hop算法的基础上,提出DC DVHop算法。以最大似然估计准则为依据选取最优锚节点集合,并逐步将符合相应条件的未知节点转化为锚节点,从而在相同的初始锚节点数量下扩大定位范围和定位精度。

2 DV-Hop定位算法及误差分析

DV-Hop算法的定位过程分3个步骤:

(1)距离矢量交换阶段:锚节点以泛洪的方式向其邻居节点发送广播消息,消息中包含该锚节点的编号、位置坐标和跳数信息。通过锚节点的广播消息,利用距离矢量路由交换协议,网络中每个节点都获得了与其他所有锚节点之间的最小跳段数。

(2)校正值计算和广播阶段:每个锚节点根据与其他锚节点的实际距离和第1步得到的2个锚节点之间的跳段数信息,可以求得每跳平均距离,最后将其作为校正值以广播的形式发送到网络中。未知节点根据接收到的最近锚节点的校正值,计算得到与各个锚节点的估计距离。锚节点i的平均跳距计算公式如下:

其中,(xi,yi)和(xj,yj)为锚节点i和j的坐标;hj为锚节点i和j之间的跳数。

(3)坐标计算阶段:当未知节点获得3个或3个以上锚节点的估计距离信息后,利用极大似然估计法计算未知节点坐标信息。

若选取3个锚节点进行三边测量法,则未知节点U1的坐标(x,y)可通过求解以下方程组得到:

其中,(xi,yi)(i=1,2,3)代表锚节点Mi的精确坐标;di(i=1,2,3)为锚节点Mi与U1的估算距离。

DV-Hop算法使用最近锚节点的平均跳距来计算未知节点与锚节点之间的实际距离。但事实上,由于节点分布的不均匀,使用单个锚节点估计的平均跳距值无法准确地反映全网络的实际平均跳距,造成距离估计误差较大;其次,在利用极大似然估计法计算未知节点位置时,如果所选取的3个锚节点位置共线度较强,则位置估算误差较大;另外,由于传感器节点在播撒过程中的随机性,其分布很不均匀,可能出现大量的孤立节点,在其通信范围内可能无法找到足够的锚节点以实现定位计算[6-7]。

针对以上对 DV-Hop算法的分析,本文提出一种改进的协作式节点定位算法(DC DV-Hop算法),首先,在选取用来计算未知节点位置的候选锚节点问题上,综合考虑各个锚节点与未知节点之间的距离及相互位置,选取与未知节点距离最近且共线度最弱的3个锚点参与最大似然估计;其次,未知节点的平均跳距不是采用其最近锚节点的值,而是根据各个锚节点平均跳距的可信度,通过加权计算而获得;最后,根据未知节点的定位误差计算,将误差范围符合相关条件的已知位置节点转化为锚节点,从而增加锚节点密度,扩大定位范围。

3 DC DV-Hop算法原理

3.1 基于共线度计算的锚节点筛选

传感器网络的部分拓扑如图1所示,M1～M4为靠近未知节点U1的4个锚节点,根据DV-Hop算法的最大似然估计原理,在二维平面上,U1至少需要选择3个锚节点来估计自已的位置信息。

图1 候选锚节点的选取

以选取锚节点M1～M3为例,如图1所示,其组成的三角形的一个内角α满足:

其中,M1M2,M2M3,M1M3为相应2个锚节点之间的距离。

由文献[4]可知,当3个候选锚节点的共线度DC=π/3时,定位误差最小。所以,算法预先设定一个阈值C(0＜C＜0.5),当未知节点接收到N个锚节点的路由信息后,首先根据式(2)计算离未知节点距离最近的3个锚节点的共线度,当其共线度满足时,则进行三边测量法求未知节点位置信息;否则,如图1所示,算法自动选择距U1距离次近的另一个锚节点M4代替M3作为候选锚节点,直到共线度满足上述条件[8-9]。

3.2 锚节点的可信度

如图2所示,未知节点U1与锚节点M1～M4相连通,且4个锚节点两两之间的距离值相近,U1与M3和M4的连接较靠近直线,但与M2的连接较为曲折。按照式(1)计算平均跳距的方法,锚节点M2参与计算导致平均跳距比实际偏小。由于误差的传递,未知节点U1与锚节点M2的距离计算也会受到影响。

图2 平均跳距的可信度计算

针对上述问题,本文提出锚节点信任度的计算方法[10]。假设传感器网络共有N个锚节点,若锚节点i与其余N-1个锚节点的单条路径的平均跳距表示为HSij(j≠i),则单条路径的平均跳距和锚节点i的总平均跳距的偏差程度,再经归一化处理后,可用来表示锚节点j相对于锚节点i的信任度,具体计算方式如下:

可以看出,当HSij与Hi的偏差较大时,可信度wij的值较小,表明锚节点i与锚节点j的单条路径上比较曲折,导致平均跳距计算误差较大。

3.3 未知节点平均跳距的计算

在DV-Hop算法采用三边测量法估计未知节点位置时,默认参与计算的3个锚节点的可信度相同。但根据上文分析,锚节点因分布的不均匀导致可信度不同,可信度较低的锚节点参与计算会降低定位的精确度。鉴于此,当未知节点接收到多个锚节点的平均跳距信息后,首先选择离其最近的锚节点的平均跳距为参考,然后根据其他锚节点相对该锚节点的信任度进行加权平均[11]。

如图2所示,未知节点U1接收到的4个锚节点的平均跳距分别为HS1～HS4,M1离未知节点U1最近,M2～M4的相对M1的可信度分别为w21,w31,w41,则U1的平均跳距计算公式为:

在获取HSU后,根据U1与各个锚节点之间的最小跳数,两者相乘估算出U1和候选锚节点之间的距离,然后运用式(1)计算U1的位置。

3.4 协作节点的转化条件

协作定位算法的基本思想是将通过定位后的节点有条件地转化为锚节点,从而参与其他未知节点的定位。只有定位结果精度足够高的节点才可转化为锚节点,否则以其估计位置来定位其他未知节点时,会使误差累积[12]。

如图 1所示,未知节点U1的位置由锚节点M1,M2,M4通过三边测量法计算获得,其定位误差的分析如下:将U1与任一锚节点(M1)进行身份互换,然后根据另2个锚节点(M2和M4)来估算被互换的锚节点(M1)的位置。因为锚节点的位置已知,M1的估算位置若与实际位置较吻合,则表明节点的定位精度较高。假设M1的实际坐标位置为(x,y),而经过互换后的估算位置为(x′,y′),节点间的通信半径为R,则归一化定位误差可表示为:

未知节点转化为锚节点的条件是:预先设定误差阈值M,仅当节点定位的归一化误差满足e≤M时,才可将其转化为锚节点参与其他未知节点的定位计算。

4 DC DV-Hop算法流程

DC DV-Hop算法的流程如下:

(1)通过锚节点的泛洪信息,各个未知节点得知与自己相连通的锚节点的个数、跳距;

(2)未知节点按照跳数从近到远的原则选取符合共线度准则的3个锚节点;

(3)以距离未知节点最近的锚节点为参考计算其他节点的可信度,按式(5)计算其平均跳距;

(4)计算未知节点与各个锚节点之间的距离,执行三边测量法估算未知节点的位置;

(5)按照3.4节的方法计算定位结果的误差,将符合误差条件的节点转化为锚节点;

(6)以新的锚节点集循环以上步骤,直到网络中没有符合定位条件的未知节点为止。

5 仿真及结果分析

使用Matlab作为仿真工具,设定传感器网络为100 m×100 m的正方形区域,锚节点和未知节点的位置为随机分布,所有节点通信半径相同。

图3和图4分别给出了节点通信半径为15 m或20 m时,2种算法的归一化定位误差和剩余节点比随锚节点数的变化规律。剩余节点比指的是当定位算法执行完毕后,网络中未能定位的节点占总节点数的比例。

图3 平均定位误差随锚节点数的变化

图4 剩余节点比例随锚节点数的变化

从图中可以看出,在锚节点数和通信半径相同的情况下,改进算法比DV-Hop算法拥有更小的定位误差和剩余节点比,而且可以看到,在锚节点较小的情况下,改进算法能够获得较低的定位误差和剩余节点比。在锚节点数相同的情况下,通信半径越大,DC DV-Hop算法的定位误差和剩余节点比越小。当锚节点数超过40个后,2个参数取值都趋于稳定,说明DC DV-Hop算法具有较好的鲁棒性。

图5和图6分别给出了锚节点数总数不变和锚节点比例不变2种情况下,平均定位误差同节点密度之间的关系。从图中可以看出,在2种情况下,改进算法都比原始算法的定位误差小,尤其在节点密度较小的情况下,改进算法仍具有较低的定位误差,性能优势更明显。在相同节点密度下,通信半径越大,定位误差越小。

图5 平均定位误差随节点密度的变化(锚节点数不变)

图6 平均定位误差随节点密度的变化(锚节点比例不变)

图7和图8分别给出了锚节点为15个或20个时,平均定位误差和剩余节点比例与节点通信半径之间的关系。从图7可以看出,节点通信半径相同的情况下,改进算法的定位误差比原始算法小,尤其在通信半径较小时(10 m),改进算法的平均定位误差不到原始算法的1/2。随着节点通信半径的增加,平均定位误差的减小趋于平缓,对于相同算法,锚节点数越大,平均定位误差越小。

图7 平均定位误差随节点通信半径的变化

图8 剩余节点比例随通信半径的变化

从图8可以看出,相同节点通信半径的情况下,改进算法的剩余节点比小于原始算法,当通信半径为10 m时,改进算法的剩余节点比约为原始算法的7/10。随着通信半径的增大,2种算法的剩余节点比例都变小,而且对于同一种算法,锚节点数越大,剩余节点比例越小。

6 结束语

本文在DV-Hop算法的基础上,提出了一种基于分布式协作的改进算法。针对参与三边测量定位的锚节点位置关系,提出根据共线度对候选锚节点进行筛选;针对平均跳距计算误差较大的问题,提出以锚节点的可信度为参考进行加权平均处理;最后,为减小定位的剩余节点比例,提出以计算定位误差为条件将部分未知节点转化为锚节点参与其他节点的定位。通过仿真可以证明,当锚节点密度和节点通信半径较小的情况下,改进算法的定位误差和节点剩余比例明显优于原始算法。

下一步将应用该算法实现传感器网络的信息融合,在节点快速精确定位的基础上,提高信息融合算法中节点选取的合理性。

[1] 王福豹,史 龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[2] 杨新宇,孔庆茹,戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报,2010,44(8):1-5.

[3] 郭建全,赵 伟,黄松岭.大规模无线传感器网络分布式无锚节点定位算法[J].高技术通讯,2011,21(6): 555-561.

[4] Savvides A,Han C C,Srivastava M B.Dynamic Finegrained Localization in Ad-hoc Networks of Sensors [C]//Proceeding ofthe7th AnnualInternational ConferenceonMobileComputingandNetworking Rome.[S.l.]:ACM Press,2001:166-179.

[5] Avvides A,Park H,Srivastava M B.The Bits and Flops of the N-hop Multilateration Primitive for Node Localization Problems[C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta,USA:ACM Press,2002:112-121.

[6] Niculescu D,Nath B.Error Characteristics of Ad Hoc Location Systems(APS)[C]//Proceedings of MobiHoc’04.Roppongil,Japan:[s.n.],2004:20-30.

[7] Jin Seung-Hwan,Yoo Sang-Jo.Improved Location Scheme Based on DV-hop for Wireless Sensor Network[C]// Proceedings ofthe9th InternationalSymposium on Communications and Information Technology.[S.l.]: IEEE Press,2009:69-74.

[8] Lee Byeong-Tae,Kim Sunwoo.Scalable DV-hop Localization forWirelessSensorNetworks[C]// Proceedings of the 14th Asia-Pacific Conference on Communications.Akihabara,Tokyo:[s.n.],2008:1-4.

[9] Lee J,Chung W,Kim E,Hong I W.Robust DV-hop Algorithm for Localization in Wireless Sensor Network[C]//Proceedings of International Conference on ControlAutomation and Systems.Orlando,USA: [s.n.],2010:2506-2509.

[10] Agashe A A,Patil R S.Evaluation of DV Hop Localization Algorithm in Wireless Sensor Networks[C]// Proceedings of International Conference on Advances in Mobile Network,Communication and Its Applications. London,UK:[s.n.],2012:79-82.

[11] Tomic S,MezeiI.Improved DV-Hop Localization Algorithm forWireless Sensor Networks[C]// Proceedings of the 10th Jubilee International Symposium on Intelligent Systems and Informatics.[S.l.]:IEEE Press,2012:389-394.

[12] Li Li,KunzT.Cooperative Node Localization for Tactical Wireless Sensor Networks[C]//Proceedings of Military Communications Conference.Orlando,USA: IEEE Press,2007:1-7.

编辑 金胡考

A Node Location Algorithm in Wireless Sensor Network Based on DV-Hop

WANG Jinghui
(National Digital Switching System Engineering&Technological R&D Center,Zhengzhou 450001,China)

Aiming at the problem of node location in Wireless Sensor Network(WSN),this paper proposes an improved algorithm for DV-Hop based on distributed collaboration.It depends on calculating distance between nodes,and selects the nodes as the anchor nodes which have lower collinear degrees by maximum likelihood estimation.It considers of all anchor nodes,and calculates each nodes average hops by the weighted average algorithm based on their credibility. It calculates the location error of unknown nodes,and turns some nodes as anchor nodes which have lower error,to expand the location scope.Simulation results show that,the improved algorithm can reduce the location error by about 20%compare,with DV-Hop with the same number of anchor nodes and the communication distance between nodes. Especially if the nodes density is smaller,DC DV-Hop can control the location error below 40%,and when the communication distance between nodes is more than 10 meters,this improve algorithm can reduce the ratio of remaining nodes by approximately 30%.

Wireless Sensor Network(WSN);DV-Hop algorithm;anchor node;collinear degree;cooperative localization

1000-3428(2015)01-0082-05

A

TP393

10.3969/j.issn.1000-3428.2015.01.015

王景珲(1969-),男,高级工程师,主研方向:移动通信网络。

2013-11-25

2014-03-06 E-mail:wjinghui@sina.com

中文引用格式:王景珲.一种基于DV-Hop的无线传感器网络节点定位算法[J].计算机工程,2015,41(1):82-86.

英文引用格式:Wang Jinghui.A Node Location Algorithm in Wireless Sensor Network Based on DV-Hop[J].Computer Engineering,2015,41(1):82-86.