logo资料库

论文研究-改进的DV-HOP算法 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.22M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    中国科技论文在线 http://www.paper.edu.cn 改进的 DV-HOP 算法 杨名权，周东清* （大连理工大学电信学院，辽宁 大连 116024） 摘要：在无线传感器网络中，节点的定位对所有应用都至关重要的作用。DV-Hop 算法作为 与测距无关的算法，有算法简单、实现代价低等显著的优势。同时 DV-Hop 算法定位精度偏 低。本文提出了一种 DV-Hop 算法的改进方法 SDV-Hop（Series-based DV-Hop）算法。在没 有增加任何硬件实施，又没有明显增加算法复杂性的前提下，大大提高了算法的定位精度。 仿真实验表明，改进的算法比原算法定位精度提高了约 14%。 关键词：无线传感器网络；节点定位；距离向量算法 中图分类号：TP393 An Improved DV-Hop Algorithm Yang Mingquan, Zhou Dongqing LiaoNing DaLian 116024) (The School of Electronic and Information Engineering,Dalian University of Technology, Abstract: In wireless sensor networks, node positioning vital role in all applications. DV-Hop algorithm as the Rang-Free algorithm, has the significant advantages of low cost. But DV-HOP algorithm accuracy is low.This paper presents an improved DV-Hop Algorithm SDV-Hop(Series-based DV-Hop). Without adding any hardware implementation, and no significant increase in the premise of algorithmic complexity, greatly improving the positioning accuracy of the algorithm.Simulation results show that the improved algorithm to improve accuracy than the original algorithm by about 14%. Keywords:Wireless Sensor Network; Node Location; DV-Hop 0 引言 无线传感器网络是集成了传感器、嵌入式、网络和无线通信四大技术而形成一种全新的 信息获取和处理技术。在现代军事、医疗、救援、交通管理及地理探测等领域有着广泛的应 用。为了节点间协同工作，节点的位置信息必须能够精确得到。因此节点定位一直是无线传 感器网络应用中的关键的基础技术[1]。目前无线传感器网络节点定位方法主要有基于测距和 与测距无关两类算法。基于测距的算法，通过精确测量节点间的距离或角度信息来估计了同 节点的位置。现在流行的测距方法有：信号到达时间（TOA，time of arrival）[2]、信号到达 时间差（TDOA，time difference on arrival）[3]、信号到达角度（AOA，angle of arrival）[4] 和信号接受强度（RSSI，received signal strength indicator）[5]等。这类算法定位精度高，但 易受外界环境的影响，而且需要额外的硬件支持。与测距无关的算法，不需要增添硬件，算 法相对简单就能实现节点定位。常用的算法有：APS（ad hoc positioning system） [6]、质心 算法（Centroid）[7]、和 APIT（Approximate Point in Triangle Test）[8]。 本文对 DV-Hop 算法进行了研究，第 1 部分对传统的 DV-Hop 算法进行了分析，提出了 问题的所在。第 2 部分提出了对 DV-Hop 算法的改进算法 SDV-Hop 算法。第 3 部分，通过 仿真实验，对 SDV-Hop 进行了性能的分析和评价。最后是对全文的总结和今后研究的展望。 作者简介：杨名权，（1981-），男，学生，主要研究方向：无线传感器定位技术. E-mail: yangmquan@126.com - 1 -
    中国科技论文在线 1 DV-HOP 定位方法 http://www.paper.edu.cn 2001 年 Dragos Niculescu 和 Badri Nath 提出了 DV-Hop 算法。DV-Hop 算法由如下四个 步骤完成[1]： 首先，信标节点以洪泛的方式广播类似于{xi，yi，hi}的信息包，其中（xi，yi）是信标 节点的坐标，hi 是跳数，初始为 0。然后，信标节点计算平均每跳距离。每个信标节点计算 根据公式（1.1）计算平均第跳距离。 y i x i − + − y ) ( ( 2 2 j ∑ j ≠ i Hopsize i = j x ) ∑ j ≠ i h j （1.1） 其中（xi，yi），（xj，yj）是信标节点坐标，hj 是信标节点 i 到信标节点 j 的最小跳数。 这样每个信标节点将得到一个 Hopsizej。接着，信标节点广播计算得到的 Hopsizej，未知节点 使用收到的第一个 Hopsize 作为自己的平均每跳距离。这样未知节点就可以得到与所有信标 节点的距离 d。最后，未知节点得到与 3 个信标节点的距离就可以使用三边定位法计算自己 的位置了。假如某未知节点的坐标为（x，y），它与 n 个坐标分别为（x1，y1),（x2，y2）， （x3，y3）…（xn，yn）的信标点的距离分别为 d1，d2，d3…dn。建立如下等式： 2 2 2 2 2 ( ( 2 2 − − + + y 1 y − − = = x ) x ) d 2 1 d y ) y ) x ( 1 x ( 2 x ( 整理等式（1.2）可得等式：AX=B。其中： = − + − d y y x 2 n ) ( ) n n 2 2 (1.2) x 1 x 2 x n x n ) ) − − (2 (2 y 1 y 2 − − y n y n x n + + − x 2 n x 2 n (2) y 2 1 y 2 2 y n y y 2 n 2 n − d d 1 − + + y 2 n 2 n 1 − − − ) ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ n d − d − ) 2 1 2 2 − − − − x 2 n + y 2 n 1 − y 2 n + d 2 n − d 2 n 1 − n (2 (2 x (2 x 2 1 x 2 2 ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎢ ⎢ ⎢ ⎢ x 2 ⎢ ⎣ n 1 − x ⎡ ⎤ ⎢ ⎥ y ⎣ ⎦ A = B = X = ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ T ( ) 1 − = BAAA T 使用最大似然估计法可得 X 的解： ^ X 这样第个未知节点就可以计算得到自己的位置信息。 从传统的 DV-Hop 算法我们可以发现，该算法核心的工作是计算 Hopsize。而算法中采 用的公式(1.1)中，距离使用两点间的直线距离，但是信息在传感器网络中的传输不是直线传 输的[9]。这必然造成较大的误差。本文针对这一问题，提出了一个算法简单，易实现的解决 方法。 - 2 -
    中国科技论文在线 2 改进的 DV-HOP 算法 http://www.paper.edu.cn 本文的算法在从改进 Hopsize 的精度入手，提出了一种更加符合实际的 SDV-Hop 算法。 通过适当的修正网络中信息曲线传输的影响来实现更精确的定位。并且限制了传输的距离， 减小了因累积产生的误差。 2.1 设置跳数非增数列 如图（1）所示，在一无线传感器网络中 N1，N2，N3 是信标节点，K 为未知节点。现在 要定位 K 的位置。N1，N2，N3 分别广播信息包，在原算法中，N2 将得到距 N1，N3 的跳数 和距离组成的二元组分别是(2，50)，(6，100)。同样 N2，N3 将分别收到(2，50)，(5，80)和 (5，80)，(6，100)。这样算出来的 Hopsize 存在较大的误差。我们提出一种非整数跳数的方 法。在信息包传输时不再是对跳数简单的加 1，而是预设一个非增非负的数列。当未知节点 收到信息后首先判断该信息是否有效。如果是有效信息则将信息保存。然后，将信息中的跳 数加上数列中对应的值后转发给邻居节点。邻居节点重复这个过程。直到整个网络不再有更 新。 图 1 网络示例 Fig. 1 An Example of Network 计算 Hopsize 时也采用经过同一数列处理过的跳数。这样两信标节点间的距离是直线距 离，跳数也更接近直线传播的跳数。而且，距离信标节点越远的节点获得的权值越小。对结 果的影响也越小。在未知节点计算与信标节点距离时，因为跳数是经过修正的，误差也就更 小。同里由于数列的非增性，较远信标节点的对定位影响较小，较近信标节点对定位影响较 大。从而可以更好的利用近距离信标节点的信息，从而实现更高的定位精度。 在上面改进的基础上，我们对数列再作进一步的改进。数列的最后一项设置为不可达。 这一改进目的是减小距离较远节点之间通信带来的无用负担。因为距离越远信息非直线传输 带来的影响越大。还会出现累积的误差。至于这个数列应该有几项，在什么位置设置为不可 达，经过仿真实验我们得到了以下 3 点参考标准。 （1） 数列与网络的节点密度的关系。如果节点密度大则数列应该缓慢减小，而且不应 该出现 0 项。最后设置为不可达。如果节点密度较小，非直线传输对定位精度的影响较大， 数列应该快速减小，可以出现 0 项，甚至出现多于一个的 0 项。然后设置不可这项以防止信 - 3 -
    中国科技论文在线 息过远传输。 http://www.paper.edu.cn （2） 数列与节点传播半径的关系。假如某传感器网络中的节点传播半径为 R，网络覆 盖范围最大直径为 L。跳数的最大值应不大于 L/R。结合第（1）项如果网节点密度较大， 数列应该较长；反之如果网络节点密度较小数列应该较短。 （3） 数列与锚节点比例的关系。信标节点的比例对定位的精度有至关重要的影响。所 以要有效的利用信标节点信息实现定位。如果信标节点比例较大，在局部范围内就可以出现 三个以上信标节点，从而完成定位。因此，数列可以设置的较小。如果信标比例较小，就需 要利用全局的信标信息，而较远距离的信标节点信息是存在较大误差的，这就需要较长的数 列，同时数列前几项减小速度较慢以提高较近信标节点的价值，而后几项减小不试较大以减 小较远信标节点信息带来的误差。 2.2 算法流程 通过上面的分析我们现在详细介绍 SDV-Hop 算法的流程。 1）预设数列。在网络节点布署完成后，根据能获得的网络的节点分布情况，如：节点 的传播半径、锚节点比例等运用 3 条参考标准为每个节点预设跳数数列。我们以数组的形式 存储在节点内。在节点需要转发锚节点的数据包时查询该数组，将跳数增大后直接转发。 2）每个锚节点将位置信息包广播到网络中，信息包包括锚节点的 ID、坐标及跳数等信 息。初始化跳数为 0，接收到信息包的节点判断该信息是否有效，如果是第一次收到该锚节 点的信息包，将跳数增加数列中相应的数值，然后转发该信息。如果已经收到过该锚节点的 信息，判断信息包中的跳数是否比存储的跳数小，如果小则更新存储并转发，否则丢弃该信 息包不做其它处理。 3）锚节点根据公式(1.1)计算出平均每跳距离。这里使用的跳数是非整数的跳数，这个 跳数更接近数据沿直线传输的跳数，因而平均每跳距离更准确。 4）锚节点将自己的平均每跳距离广播至网络中，未知节点存储第一个到达的平均每跳 距离信息，并转发给邻居节点，忽略后到达的所有平均每跳距离。 5）未知节点根据平均每跳距离和跳数计算到锚节点的距离。由第 2 步每个未知节点都 得到了到所有锚节点的跳数 Hopi，再根据接收到的 Hopsize，将 Hopi 与 Hopsize 的乘积作为 锚节点 i 的距离。 6）利用最大似然估计法计算得到节点坐标信息。当未知节点得到距 3 个锚节点的距离 信息时就可以使用三边定位法估计自己的位置了。如果获得了 3 个以上的距锚节点距离信 息，我们使用最大似然估计法计算未知节点的位置，以增加定位的精度。 3 实验仿真 我们利用 MATLAB 对 SDV-Hop 算法进行仿真，并通过多次实验分析在不同网络节点 密度和不同的锚节点比例情况下与 DV-Hop 算法的定位效果进行比较。，实验基于以下的网 络模型： 1）网络中所有节点是各向同性的。 2）所有节点的通信范围相同且固定。节点的通信半径为 15m。 3）所有节点随机分布在一个 100m×100m 正方形区域内。 如图（2）所示，因为节点密度越大计算出的平均每跳距离越接近节点的通信半径，随 着节点密度的增加 DV-Hop 算法和 SDV-Hop 算法的定位误差都会降低。在节点密度较小时， - 4 -
    中国科技论文在线 http://www.paper.edu.cn 定位误差对节点密度的变化更敏感，DV-Hop 算法实现的定位误差较大不能满足需要，而 SDV-Hop 算法仍可实现可以接受的定位效果。当每个节点的平均邻居节点达到 6 时，节点 密度对定位精度的影响开始变小。节点密度继续增大，SDV-Hop 算法失去优势，和 DV-Hop 算法的定位精度趋于相同。 Fig. 2 The relationship between localization accuracy and node density 图 2 定位精度与节点密度关系 如果固定节点密度，而单纯的增大锚节点比例 DV-Hop 算法和 SDV-Hop 算法的定位精 度都会越来越小。这是因为锚节点比例的增大，未知节点可以使用的定位信息会大增加，定 位精度也会提高。从图（3）中可以得出 SDV-Hop 算法和 DV-Hop 算法对锚节点比例要求类 似，在相同的锚节点比例下 SDV-Hop 算法的定位精度要优于 DV-Hop 算法。 图 3 定位精度与锚节点比例关系 Fig. 3 The relationship between localization accuracy and anchor ratio 我们通过实验分析两个算法定位的精度与网络节点密度和锚节点比例的关系，实验数据 显示出 SDV-Hop 算法的定位效果明显优于 DV-Hop 算法，定位精度提高了约 14%。 - 5 -
    中国科技论文在线 4 结论 http://www.paper.edu.cn DV-Hop 算法是一种与测距无关的 WSN 节点定位算法，得到了广泛的应用。本章在对 该算法进行了分析研究的基础上，提出了一种改进的算法 SDV-Hop。SDV-Hop 算法引入了 非整数跳数的概念，采用数列的方式使计算节点间的跳数，实现更准确的平均每跳距离的计 算，从而达到更好的定位效果。最后通过实验仿真分析了比较了 SDV-Hop 与 DV-Hop 在不 同的节点密度和锚节点比例的情况下的定位误差。实验数据显示 SDV-Hop 的定位精度比 DV-Hop 提高了 14%。 [参考文献] (References) [1] NICULESU Dragos, NATH Badri. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems, 2003, 22(1/4):267～280. [2] HARTER Andy, HOPPER Andy, STEGGELS Pete et al. The anatomy of a context-aware application[J]. IEEE Int’l Conf. on Mobile Computing and Networking, 1999, 59～68. [3] GIROD L, ESTRIN D, Robust range estimation using acoustic and multimodal sensing[J]. Proc. of the IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems, 2001, 3: 1312～1320. [4] PRIYANTHA NB, MIU AKL, BALAKRISHNAN H et al. The cricket compass for context-aware mobile applications[J]. Proc. of the 7th Annual Int’l Conf. on Mobile Computing and Networking, 2001, 1～14. [5] GIROD L, BYCHOVSHIY V, ELSON J et al. Locating tiny sensors in time and space: A case study[J]. Werner B, ed. Proc. of the 2002 IEEE Int’l Conf. on Computer Design: VLSI in Computers and Processors, 2002, 214～219. [6] NICULESU Dragos, NATH Badri. Ad Hoc Positioning System(APS)[J]. Proc. of the IEEE GLOBECOM ,2001, 2926～2931. [7] DOHERTY L, PISTER KSJ, GHAOUI LE. Convex position estimation in wireless sensor networks[J]. Proc. of the IEEE INFOCOM 2001, 2001, 1655～1663. [8] TIAN He, HUANG Chengdu, BLUM Brian M et al. Range-free localization and its impact on large scale sensor networks[J]. ACM Transactions on Embedded Computing Systems,2005,4(4):877～906. [9] 孙利民,李建中,陈渝等.无线传感器网络[M].北京:清华大学出版社,2005. - 6 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料