基于DV-hop的无线传感器网络定位算法研究.pdf

第 2 4卷 第 1 O期 2 0 1 1年 1 0月 传 感 技 术 学 报 CHI N E S E J OU RNA L O F S E NS OR S AN D AC T U AT O RS Vo 1 2 4 No 1 0 0c t 2 01 1 Re s e a r c h o f P o s it io n in g T e c h n o lo g y in Wir e le s s S e n s o r Ne t wo r k B a s e d o n DV h o p Z HA NG Z h e n Y A N L i a n s h a n L lU j ia n g t a o H Xia o y in C e n t e r r I n f o r ma t i o n P hot o n i c s C o m mu n i c a t i o n s S c h o o l of I n f o r m a t i o n S c i e n c e T e c h n o l o g y S o u t h w e s t J i a o t o n g U n i v e r s i t y C h e n g d 6 1 0 0 3 1 C h i n a Ab s t r a c t D V h o p is a t y p ic a l lo c a t io n a lg o r it h m i n wir e le s s s e n s o r n e t w o r k s T h is p a p e r a n a ly z e s D V h o p a lg o r it h m p a r a me t e r s in c lu d in g n o d e c o mmu n ic a t io n r a d iu s t h e n u mb e r o f a n c h o r n o d e s a n d t h e t o t a l n u mb e r o f n o d e s o f w h ic h p a r a me t e r s imp a c t o n t h e p o s it i o n in g e r r o r a n d t h e s i mu la t i o n r e s u lt s are g i v e n T h r o u g h t h e s imu la t io n r e s u l t s t h e o p t imu m v a lu e o f t h e p a r a me t e r i n D V h o p al g o r it h m h a v e b e e n o b t a in e d T h e o r e t ic al a n a l y s e s a n d s imu la t io n r e s u lt s d e mo n s t r a t e t h a t p a r a me t e r s o f t h e o p t i mi z e d a lg o r it h m e f f e c t i v e ly i mp r o v e the n o d e lo c a t io n e r r o r Ke y wo r d s w ir e le s s s e n s o r n e t wo r k D V h o p lo c a t io n a lg o r it h m p o s i t io n in g e r r o r E E ACC 6 1 5 0 P d o i 1 0 3 9 6 9 j i i s s n 1 0 0 4 1 6 9 9 2 0 1 1 1 0 0 2 0 基于 D V h o p的无线传感器 网络定位算法研究 术 张 震 闫连 山 刘江涛 李晓银 西南交通大学 信息科学与技术学院信息光子与通信研究中心 成都 6 1 0 0 3 1 摘 要 D V h o p 算法是无线传感器网络中一种典型的定位算法 系统分析了D V h o p 算法中对定位误差有较大影响的节点 通信半径 锚节点个数 总节点个数等几个重要参数 并进一步给出仿真结果 通过仿真结果分析得出上述参数的较优值 降 低使用 D V h o p算法时无线传感器网络的定位误差 理论分析和仿真结果表明 参数优化后的算法有效的降低了节点的定位 误差 关键词 无线传感器网络 D V h o p 定位算法 定位误差 中图分类号 T P 3 9 3 文献标识码 A 文章编号 1 0 0 4 1 6 9 9 2 0 1 1 1 0 1 4 6 9 0 4 无线传感网络 Wi r e l e s s S e n s o r N e t w o r k WS N 由大量无线传感器节点组成 现已广泛应用在军事 环境 医疗等领域 1 节点定位技术是无线传感 网络得以广泛应用的前提条件 网络中的传感器节 点发回监测区域内的温度 压力 湿度等数据信息只 有与位置信息相关联才有意义 3 节点的定位技 术是无线传感网络获取信息的关键技术 正逐步受 到了越来越多的关注 5 J 现有的无线传感器节点定位技术可以分为两 类 基于测距 的定 位技术 和无需 测距 的定 位技 术 基于测距的定位技术需要测量节点间的距 离或角度信息 测量精度高 无需测距的定位技术不 需要直接测量节点间的距离或角度信息 对节点的 硬件要求低 出于对传感器网络成本 功耗等因数 的考虑 以及在大多数应用场合下对节点的定位精 度要求不高 所以现阶段对无需测距的定位技术研 究较多 D V h o p算法是 目前研究 和应用最为广泛 的无 需测距定位算法 但在计算未知节点和锚节点间的 距离时估算较粗糙 现阶段 对 D V h o p算法的改 进方法 主要 有 1 与其 他 的定位算 法相结 合 2 修正未知节点与锚节点问的距离l 1 3 改进 最后一步的定位计算方法 1 等 而对 D V h o p算法 本身的参数优化研究 较少 本文对 D V h o p算法 中 的参数进行了详细的分析 并通过仿真对参数进行 优化 仿真结果表明 通过参数优化可以有效地提 高 D V h o p 算法的定位精度 1 D V h o p算法介绍 D V h o p I 1 2 13 算法主要通过距离矢量和跳数来 估测未知节点到锚节点的距离 然后使用三边或多 边测量法求出未知节点的位置信息 在未知节点的 项目来源 国家自然科学基金项目 6 0 9 7 2 0 0 3 教育部新世纪优秀人才项目 N C E T 一 0 8 0 8 2 1 收稿 日期 2 0 1 1 0 5 0 7 修改 13 期 2 0 1 1 0 7 1 4 1 47 0 传感技术学报 W W W c h in a t r a n s d u c e r s c o rn 第 2 4卷 通信范围内 锚节点数目并不多 采用上述方法可以 得到节点到其通信范围外的多个锚节点的距离信 息 D V h o p 算法主要由以下三步组成 第 1 阶段 通过典型的距离矢量路由协议 使网 络中所有的节点获得到锚节点最小跳数值 第 2 阶段 锚节点计算平均每跳距离值 如果一 个锚节点的坐标为 Y 则平均每跳距离计算公 式为 使用标准的最小均方差估计方法可以得到未知节点 的坐标为 AT A 一 A b 5 D V h o p算法定位误差 主要来源于用曲线距 离代表直线距离 平均每跳距离的估计很粗糙 并 且多方面影 响距离的估测 如锚节点数 目 节点的通 信半径 总节点数目等 2 D V h o p算法参数分析 1 2 1 锚节点数 目 式中 y f 表示锚节点 的坐标 f 表示锚节点 到 锚节点 i的最小跳数 H o p S i z e 表示锚节点 i计算的 平均每跳距离 将 H o p S i z e 作为一个校正值 在传 感器网络中采用可控泛洪法进行广播 传感器节点 只保存第一个校正值 以此保证节点接收到的校正 值是最近的一个锚节点发送过来的 未知节点收到 校正值后就可 以根据跳数和校正值计算其到锚节点 的距离 第 3阶段 当未知节点至少获得到三个锚节点 的距离时 通过使用最小二乘法计算未知节点的坐 标 给定一个锚节点集 R Y i 1 2 M 表示锚节点的数 目 并且未知节点 x Y 到 锚节点i的最小跳数是 因此未知节点 Y 到锚节点 i的距离值为d H o p S i z e 未知节点 的坐标可以通过下列公式计算得 f 一 y 一 y d 2 l 戈 x y d 将前面的 M 1 个方程依次减去最后一个方程 得到 一 2 M 一 2 x 1 M x C y 2M 一 2 y 1 一 Y M y 一 d 广 x 2 x 一 一 y 2 一 2 y M 一 y M y 厂 3 式 3 的线性方程表示方式为 AX b 4 其中 2 x 1 一 2 y 一 Y 肘 A 一 i l 2 x 肘 一 1 一 埘 2 Y 一 1 y l 2 2 2 2 2N 1 X M Y i Y M a M 一 l d 1 l l I l 21 一 2 十 y 2l y M2 十 肘2 一 d f 在 D V h o p 定位算法中 未知节点的位置是根 据估算的未知节点到锚节点的距离 并利用三边定 位法 计算出未知节点的坐标 由于锚节点和未知 节点都是随机分布的 如果锚节点分布在一条直线 上或近似在一条直线上 或者锚节点相距很近 那么 式 2 中的某些方程就可 以约去 导致最后参与未 知节点位置估计的锚节点只有几个甚至式 5 不成 立 又由于估测出来的未知节点到锚节点 的距离 d 本身就有一定的误差 因此锚节点的数目及分布情 况对节点的定位精度有很大的影响 2 2 节点通信半径 D V h o p 算法是通过跳数和平均每跳距离来估 测未知节点到锚节点的距离 而跳数和节点的通信 半径有关系 节点通信半径不同会使两个节点之间 的跳数不 同 如图 1所示 O 一o O O o O O 0 o O O 0 a 0 0 0 0 o 二 i 0 0 b 图 1 不 同 的 节 点 通信 半径 和 跳 数 的 关 系 在图1 中 由于节点的通信半径不同 在图 1 a 中节点 A与节点 B之间的跳数是 1 跳 而在图 1 b 中 节点 A与节点 B之间的跳数是 2跳 在不同的 节点通信半径下 估测出来的两节点之间的距离就相 差很大 从而影响节点的定位精度 因此节点的通信 半径不同会导致不同的定位精度 2 3 总节点数 目 在一定面积的传感区域内 不同的传感器节点总 数同样影响 D V h o p 算法的定位精度 如图2 所示 在相同的节点通信半径下 节点总数不同 平均一跳 内的节点数目会相差很大 如果节点数目过少 可能 会出现在锚节点的通信范围内没有节点 其它节点接 收不到锚节点的信息 导致节点无法定位的情况 第 1 0 期 张震 闰连山等 S t D V h o p的无线传感器网络定位算法研究 1 4 7 1 同的节点数 目 3 仿真结果及分析 由上述分析可知 D V h o p算法中锚节点的个 数 节点的通信半径 节点的总个数均会对节点 的定 位误差产生影响 本小节具体给出了在 1 0 0 mx 1 0 0 m的无线传感器网络区域内 当锚节点个数 节点的 通信半径 总节点个数变化时的节点定位误差的仿 真结果 并对其做了分析 在无线传感器网络中锚节点个数不同 节点的定 位精度不同 仿真结果如图3 所示 在图3 a 中 传感 器节点总数为 1 0 0 个 取节点通信半径 R分别为 1 5 2 5 5 0 对应锚节点的个数 B从 3 3 0变化时 在图 3 b 中 节点通信半径为2 5 取传感器节点总数分别 从 1 0 0 3 0 0 5 0 0 对应锚节点的个数 B从 3 3 0变化 7 0 0 5 1 0 1 5 2 O 2 5 3 O 锚节点数目 a 节点总数为1 0 0 6 0 口 5 0 4 0 3 0 2 0 1 O 0 5 1 0 1 5 2 O 2 5 3 0 锚节点数目 b 节点通信半径为2 5 m 图3 锚节点个数不同时节点的定位精度 从图3 a 和 b 中可以看出 当节点的通信半 径和节点总数分别不同时 锚节点的个数 B 1 2 左 右 节点的定位误差能降低到较小值 当锚节点的个 数从 3 1 0变化时 节点的定位误差迅速减少 随着 锚节点个数继续增加 节点的定位误差虽有所减小 但幅度趋于平缓 由以上分析可知 当锚节点的个 数达到一定数量时 其对节点定位误差的影响降低 且锚节点本身成本较高 说明节点通信半径和节点 总数不同时 在锚节点个数为 l2处 节点定位误差 基本接近最小值 为了研究节点的通信半径 不同时 节点定位误 差的变化情况 本文给出了在总节点数为 1 0 0 锚节点 个数分别为6 8 1 0 l2时 节点通信半径 R从 1 0 5 0 变化 节点的定位误差变化情况 结果如图4 所示 图 4 在不 同的节点通信半径下定位误差值 在图4中 给出了不同锚节点个数下 节点通信 半径 从 1 0 5 0变化时节点的定位误差 从 图 4 可以看出 随着锚节点个数的逐渐增加 6 1 2变化 时 节点的定位误差相应的降低 在不同锚节点个 数下 当节点通信半径从 1 0 2 0变化时 节点定位 误差迅速减少 并达到最小值 随着节点通信半径的 继续增加 节点 的定位误差也开始增加 说 明当锚节 点不同时 总节点数 1 0 0时 存在最优 R值 为了使仿真的结果更加真实有效 图 3和图4 中的数值均是 1 0 0次仿真结果求得的平均值 综合 考虑图3 和图4可以得出 在 1 0 0 m 1 0 0 m的区域 内 总节点数 目为 1 0 0的条件下 当锚节点的个数 日 1 2 节点的通信半径 R 2 2 m时 节点的定位误差 较小 在本文的后续仿真中 在 1 0 0 m 1 0 0 I n的无 线传感器网络区域内 取锚节点的个数为 l2 为了研究无线传感器网络区域内总节点个数不 同时 最优节点通信半径是否变化 以及最低节点定 位误差的变化情况 图 5分别给出了总节点数在 1 0 0 3 0 0 5 0 0 处 节点通信半径 从 5 5 0变化时 节点定位误差的变化情况 董 露 1斗 节点通信半径 图5 在不同的节点通信半径下定位误差值 1 4 7 2 传感技术学报 W W W c h i n a t r a n s d u c e r s c o rn 第2 4卷 从图 5中可以看 出 随着总节点数的增加 节点 的定位误差整体都在下降 并且最优的节点通信半 径也在变化 表 1给出了在不同总节点数下 对应的 最优节点通信半径和相应的最低节点定位误差值 表 1 不同总节点数下的最优节点通信半径和定位误差 综合图5和表 1 可得 在不同的总节点数 目条件 下 存在最优的节点通信半径 使定位误差降低到最 低值 要想使 D V h o p算法 的定位精度达到最好 可 以根据表 1 在不同总节点数 目下 选择最优的节点 通信半径 从而使节点的定位误差降低到最小值 4 结论 本文主要对基于 D V h o p 算法的无线传感器网 络 自身定位 进行 了研究 首先 详细介 绍 了 D V h o p 算法的步骤 然后分析了影响 D V h o p算法的定位 精度的主要参数包括 锚节点个数 节点的通信半 径 网络中的总节点数 经分析和仿真结果表明 在 1 0 0 m 1 0 0 1 3 1 监测 区域内 锚点节点个数 为 1 2左 右 并且针对不同总节点数 选择合适的节点通信半 径 可 以使节点的定位误差降低到较低值 参考文献 1 R e n F Y H u a n g H N n C Wi r e l e s s S e n s o r N e t w o r k J J o u r n a l 张震 1 9 8 4 一 男 汉族 湖北孝感 人 硕士研究生 西南交通大学信息科 学与技术学院通信与信息系统专业 主要从事无线传感器网络 光纤传感技 术 光通信的研究 o f S o f t w a r e 2 0 0 3 4 7 1 2 8 2 1 2 9 1 2 A k y il d i z L F S u W S a n k a r a s u b r a r n a n i a m Y e t a1 A S u r v e y o n S e n s o r N e t w o r k s J I E E E C o m m u n i c a t i o n s M a g a z i n e 2 0 0 2 4 0 8 1 0 2 1 1 4 3 李晓维 徐勇军 任丰原 无线传感器网络技术 M 北京 北 京工业大学出版社 2 0 0 7 1 1 7 4 戴莹 王建平 张崇巍 无线传感器网络节点定位算法的研究 也改进 J 传感技术学报 2 0 1 0 2 3 4 5 6 7 5 7 0 5 王福豹 史龙 任丰原 无线传感器网络中的自身定位系统和 协议 J 软件学报 2 0 0 5 1 6 5 8 5 7 8 6 8 6 X i a o J R e n L R T a n J D R e s e arc h o f T D O A B a s e d S e l f L o c a l i z a t i o n A p p r o a c h i n Wir e l e s s S e n s o r N e t w o r k J I n t e l li G e n t R o b o t s a n d S y s t e ms 2 0 0 6 1 0 2 0 3 5 2 0 4 0 7 L i M L i u Y H R e n d e r e d P a t h R a n g e F r e e L o c a li z a t i o n i n A n i s o t r o p i c S e n s o r N e t w o r k s w i t h H o le s J I E E E AC M T r a n s a c t i o n s o n N e t w o r k i n g 2 0 1 0 1 8 1 3 2 0 3 3 2 8 赵清华 刘少飞 张朝霞 等 一种无需测距节点定位算法的分 析和改进 J 传感技术学报 2 0 1 0 2 3 1 1 2 2 1 2 7 9 胡斌 李方敏 刘新华 基于 R S S I 量化模型的定位算法研究 J 武汉 理工大学学报 2 0 0 9 3 1 2 3 9 2 9 5 1 O 刘少飞 赵清华 王华奎 基于平均跳距估计和位置修正的 D V H o p 定位算法 J 传感技术学报 2 0 0 9 2 2 8 1 1 5 4 1 1 5 8 1 1 王书锋 侯义斌 黄樟钦 等 无线感知网络最小二乘法定位算 法 的误差分析与优化 J 系统仿真 学报 2 0 0 9 2 1 1 9 6 2 1 l 一 6 21 5 1 2 N i c u l e s c u D N a t h B D V B a s e d P o s i t i o n i n g i n a d h o c N e t w o r k s J J o u r n a l o f T e l e c o m m u n i c a t i o n S y s t e m s 2 0 0 3 2 2 1 4 2 6 7 2 8 0 1 3 N i c u l e s c u D N a t h B A d h o c P o s i t i o n i n g S y s t e m AP S U s i n g A O A c I N F O C O M 2 0 0 3 2 2 n d A n n u a l J o i n t C o n f e r e n c e o f t h e I EEE Co mp u t e r a n d Co mmu n ic a t io n s S a n F r a n c is c o US A 2