第4 0卷第 1期 2 0 1 3年 1月
计
算
机
科
学
Vo 1 . 4 0 No . 1
Co mp u t e r S c i e n c e
J a n 2 0 1 3
基于跳数修正的 DV— Ho p定位的改进算法 郑久虎钱焕延高德民严筱永 (南京理工大学计算机科技与技术学院南京 2 1 0 O 9 4 ) 摘要 DV— Ho p算法是一种最典型的非测距的节点定位算法。为了提高 D V- Ho p算法的精度,引入了前序节点
( P r e v i o u s No d e, P N)和总平均每跳距离这两个概念,设计了改进的 MHD V- Ho p算法,它只需很低的信标节点比例, 不改变 Dv _ Ho p算法的过程,也不需要额外硬件支持,通过 P N的数量计算出未知节点到信标节点跳数的修正系数, 使得定位精度有很大提高。 关键词无线传感器网络,节点定位, Dv' Ho p,前序节点中图法分类号 T P 3 9 3 文献标识码 A
I mp r o v e d D V- Ho p Po s i t i o n i ng Al g o r i t hm Ba s d e o n Mo di f y i ng Ho p Co u nt s
ZHENG J i u - h u QI AN Hu a n - y u a n GAO De - mi n g YAN Xi a c ̄ y o n g ( S c h o o l o f C o mp u t e r S c i e n c e a n d T e c h n o l o g y, Na n j i n g Un i v e r s i t y o f S c i e n c e a n d Te c h n o l o g y, Na n j i n g 2 1 0 0 9 4, C h i n a )
Ab s t r a c t DV Ho p a l g o r i t h m i s o n e o f t h e mo s t c l a s s i c r a n g e - f r e e l o c a l i z a t i o n a l g o r i t h ms i n wi r e l e s s s e n s o r n e t wo r k s . I n o r d e r t O e n h a n c e t h e l o c a l i z a t i o n a c c u r a c y o f t h e DV- Ho p a l g o r i t h m, t h i s p a p e r i n t r o d u c e d t wo t
e r ms o f t h e p r e v i o u s n o d e a n d To t a l Ho p S i z e, a n d d e s i g n e d a n i mp r o v e d M HDV- Ho p a l g o r i t h m. I n t h e i mp r o v e d a l g o r i t h m, t h e c o r r e c t i o n f a c t o r o f u n k n o wn n o d e t o b e a c o n n o d e h o p s i S c a l c u l a t e d b a s e d o n t h e n u mb e r o f P N. I t n o t o n l y d o n s’ t c h a n g e t h e p o—
s i t i o n i n g p r o c e s s o f t h e DV- Ho p a l g o r i t m h a t l o we r r a t i o o f b e a c o n n o d e s a n d wi t h o u t a d d i t i o n a l h a r d wa r e s u p p o r t, b u t a l s o g r e a t l y m p i r o v e s t h e l o c a l i z a t i o n a c c u r a c y . Ke y wo r d s Wi r e l e s s s e n s o r n e t wo r k s, No d e 1 o c a l i z a t i o n, DV- Ho p, Pr e v i o u s n o d e
节点定位技术是无线传感器网络 ( Wi r e l e s s S e n s o r Ne t— w o r k s, WS N)的核心支撑技术之一,节点所提供的信息往往
定位精度; ( 3 )文献[ 1 3]采用移动信标节点方法来构造均匀分 布的信标节点以提高定位精度; ( 4 )文献[ 1 3]提出了利用夹角
与其位置结合才具有实际意义,缺少位置信息的感知信息往 往是没有意义的_ 1]。WS N由于受节点硬件条件和能量限制,
修正未知节点到信标节点的距离的 A R DV - h o p算法; ( 5 )文献[ 6]提出了利用未知节点与参考节点的范围作为约束条件, 采用信赖域系列二次规划法 ( S QP )优化求解节点位置;文献[ 1 0]、文献[ - 1 4, 1 5]使用 2一 D Hy p e r b o l i c算法
代替三边法和极大似然估计法来计算节点位置;文献[ 1 6, 1 7]采用模拟弹簧方法来计算节点坐标。 上述的 D V- Ho p改进算法对定位精度有一定程度的提
节点定位时要根据精度要求和实际情况选择合适的定位算 法。
WS N节点定位技术分为基于测距 ( Ra n g e - b a s e d )定位算法和无需测距 ( R a n g e - le f e )定位算法_ 2]。基于测距的定位算法要求节点自身具有测量距离或测量角度的能力,其定位精度较高,但其对节点硬件要求也较高。而无需测距的定位算法则根据网络连通性]、未知节和信标节点位置关系、节点间 跳数等信息来计算未知节点到信标节点之间的距离。无需测
高,但有的计算复杂度大大提高,有的引人了 R S S I测距技术 需额外的硬件支持。本文引入了前序节点和总平均单跳距离概念,通过前序节点的数目与到信标节点的距离对未知节点到信标节点的跳数进行修正,并用总单跳距离代替平均单跳距离,从而减小未知节点到信标节点距离的误差,以提高定位精度。本文的算法可在信标节点比例很小的情况下,使定位精度得到较大的提高。
距定位算法定位精度不如基于测距定位算法,但其因不需要额外的硬件支持且大多数无线传感器网络对节点定位精度要求不很高,无需测距定位算法就能满足,而得到了广泛的应用。DV- Ho p C“ ]算法是最常用的一种无需测距定位算法。 目前有很多 D V- Ho p改进算法,它们主要在以下几个方面进行了改进: ( 1 )平均每跳距离计算方法的改进。文献[ 6] 应用最小方差来计算信标节点的平均距离;文献[ 7— 9]引入最
1 D V - Ho p改进算法 1 . 1 D V - H o p算法
小二乘法来计算信标节点的平均每跳距离; ( 2 )文献[ i 0— 1 2] 用 RS S I测距技术代替未知节点到信标节点一跳距离来提高 到稿日期: 2 0 1 2— 0 7— 0 1返修日期: 2 0 1 2一 l l— O 7
D V- Ho p[定位过程分为 3个阶段: ( 1 )计算信标节点到其他节点的最小跳数:每个信标节点
本文受国防科工委应用基础资金资助。
郑久虎 ( 1 9 7 4一),男,博士生,讲师,主要研究方向为无线传感器网络、
信息安全研究, E - m a i l: z h j i u h u@1 6 3 . c o m;钱焕延( 1 9 5 0一),男,教授,博士生导师,主要研究方向为网络技术和信息安全研究。
6 3

区间范围内修正跳数值的Dv-hop定位算法_专业资料。针对Dv-hop算法在估算跳数时引进较大误差的问题,提出了一种基于区间范围内修正跳数(RHWSR)的算法。根据Dv-hop...
一种基于跳数修正的 DV-Hop 定位算法肖丽萍 * , 刘晓红( 燕山大学信息科学与工程学院, 河北 秦皇岛 066004 ) 摘 要: 节点定位技术是无线传感器网络的关键...
一种改进的DV-Hop节点定位算法_专业资料。节点定位是无线传感器网络中的关键技术之一。在经典的DV—Hop算法的基础上,提出一种改进算法。将传统的基于平面的节点...
无线传感器网络中基于DV-Hop定位算法的改进_专业资料。根据信标节点到达未知节点的跳数信息,将未知节点接收到的信标节点划分为3个级别,即到达未知节点跳数为1的...
一种新的DV-Hop定位算法_专业资料。提出了一种新的基于非测距的DV-Hop高精度无线传感网节点定位算法。通过引入权重,改进计算未知节点平均跳距的方法,使计算出的...
基于蛙跳算法的DV-Hop定位改进_专业资料。为减小DV-Hop算法在无线传感器网络节点定位中的误差,针对DV-Hop中平均每跳距离的计算方式进行了改进,利用蛙跳算法来求解...
1 DV-Hop 定位算法简介 DV-Hop 定位算法的基本思想是将未知节点到信 标节点间的距离用网络平均每跳距离与两者间跳数之 积表示,当未知节点获得与三个或更多信标...
DV-Hop算法定位误差和覆盖率的改进_专业资料。通过分析免测距的DV-Hop算法在定位精度及覆盖率方面的不足,提出一种改进的DV-Hop定位算法。规定只有在限定跳数内...
为改进DV-Hop算法,分析和强调了三点近似共线问题对免测距定位的影响,给出了允许最大跳距误差率和最大跳数下检查锚节点组合有效性的三点近似共线准则。基于该...
基于DV-HOP WSN 改进算法的研究与仿真* DV-HOP/定位算法/角度阈值/加权因子 1 引言 随着微机电系统(micro-electro-mechanism system,简称 MEMS)、无线通信和数字...
热门文档