无线节点定位算法研究硕论.doc

无线节点定位算法研究
摘要
无线传感器网络将逻辑上的信息世界与客观上的物理世界有机的联系起来，改变了人类与自然界的交互方式，实现了一种新的感知自然界的方式，被认为是能对21世纪产生巨大影响力的技术之一。在无线传感器网络的各种应用中，节点定位都有着十分重要的价值，然而，传感器网络规模通常比较大，给网络中所有节点均安装GPS收发器或者人工配置节点位置会受到成本、功耗、效率等问题的限制，因此必须采用一定的机制实现无线传感器网络的自身定位，本文基于这一背景进行了无线传感网络中无线节点定位算法分析，主要进行了以下研究内容：首先探讨了几种经典的无线节点定位算法，然后针对DV-Hop算法进行了基于粒子群优化算法的改进研究中，并给出了粒子群改进算法的技术仿真和性能分析。仿真分析表明，改进算法在精度上有了一定提高，能够满足大部分节点定位精度的需求。
关键词：无线传感器；定位算法；DV-Hop算法；粒子群优化算法

Abstract
Wireless sensor networks (WSNs) linking to the physical world organic logically and objectively, changing the way humans interact with the natural world, enabling a new way of perception of nature，is considered to be one of the technologies of the 21st century to make a big impact. In all these WSNs' applications, node localization is of extreme importance .However, the scale of WSNs is usually too large ,it’s impossible to make the all node are installed GPS sender and receiver, or to configuration node location artificially, because of the limit of cost, power, and efficiency. Therefore we must use some algorithms to achieve the self-positioning of WSNs. Basing on this background, this article makes some analyses on WSNs self-positioning algorithm analysis, and focuses on the following research contents: we discusses some classic WSNs positioning algorithms. And basing on the Particle Swarm Optimization algorithm, we improve the DV-Hop algorithm and make some simulation analyses and performance analyses. The analyses indicate that the proved algorithm makes some progresses on localization accuracy and satisfies most location requirements in WSNs.
key words: wireless sensor positioning algorithm DV-Hop algorithm Particle Swarm Optimization algorithm

目录
无线节点定位算法研究 1
摘要 1
Abstract 1
目录 2
第一章 绪论 5
1.1研究背景和意义 5
1.2 国内外研究概述 6
1.3无线传感器网络的体系结构及特点 6
1.4无线传感器网络的主要应用 8
1.5节点定位技术及其意义 10
第二章无线传感器网络定位技术综述 11
2.1概念和术语 11
3.2 与距离有关的定位算法分析 12
2.2.1 基于测距的定位方法 12
2.2.2 到达时间（TOA）定位法法 12
2.2.3 时间差（TDOA）定位法 13
2.3 与距离无关的定位算法分析 13
2.3.1 质心算法 13
2.3.2 DV-Hop算法 14
2.4小结 16
第四章 DV-Hop算法改进的定位技术 16
4.1 DV-Hop算法的缺陷 16
4.2 DV-Hop算法的改进 18
4.2.1 DV-Hop算法的距离误差校正 18
4.2.2 MIN-MAX方法与加权最小二乘法的结合 19
4.2.3 改进算法的流程图 22
4.3 DV-Hop算法流程图 24
4.4DV-Hop算法仿真结果分析 26
4.4.1 仿真设计 26
4.4.2 DV-Hop算法仿真程序 28
4.4.3 仿真结果分析 31
4 .5算法改进对比 39
4.5.1 节点位置对比 39
4.5.2 平均定位误差对比 40
4.6 本章小结 41
第五章 总结和展望 42
5.1 总结 42
参考文献： 42
致 谢 47
作者在学期间取得的学术成果 48

第一章 绪论
1.1研究背景和意义
随着科学不断进步，其为发展微型传感器节点提供了技术支持。微型传感器因其成本投入低，能量消耗低，占用空间小的特点而受到青睐，除此以外，微型传感节点具有信息感知、数据处理和无线通信等功能[1-3]。目前，研究人员从事与其相关技术的研究并取得不错的成绩，而这些成绩的取得也进一步促进微型传感器节点的发展。同时这些技术的出现也使得建立无线传感器网络（Wireless Sensor Networks，简称WSN）成为可能。无线传感器网络同传统传感器网络获取及处理信息的方式不同，它不再需要固定的网络基础设备，同时它与传感器传统相比，它具有获取信息速度更快，使用寿命更长等优点。其主要适合应用于不适于人员值守的环境，或是对人体有害的环境。尤其在战场监视、环境监测、医疗、空间探索和抢险救灾等特殊领域有着广阔的应用前景。只要在整个区域内覆盖大量的大量无线传感器节点，并可以对该区域内的所有感知对象进行监测，并将采集到的有关监控对象的信息传感数据，传送到基站，在这里将对信息进行相关处理然后传送给用户终端。无线传感器网络打破传统通信的方式，它将自然信息与逻辑信息进行交汇建立起了两者的联系。它提供了一种新型的可以感知自然界的方式，因而被认为是改变世界的一项伟大技术，同时其吸引个各个领域研究人员的目光，并进行相关课题的研究，其中许多研究学者都侧重研究无线传感器网络的定位技术。定位技术处于整个网络的核心位置。首先我们应当说明的是无论利用无线传感器网络进行何种应用，其节点的感知数据同位置有密切联系必，如果没有获得位置信息，则感知到的数据也就没有存在的实际意义了。除此以外，利用定位技术获取位置信息可以有效使提高路由效率，同时节省能量，加强整个网络的安全性稳定性。但是，传感器网络中有大量的节点给每个节点均配置GPS收发器或者利用人工配置节点位置都是回到种种条件的制约。基于上述情景，应当研制出方法可以让无线传感器网络节点实行自动定位，这就是所谓的无线传感器网络节点的定位技术研究。基于以上原因，研究与发展无线传感器网络的定位技术是十分必要的，许多研究人员已经投身于这一课题的研究[16-20]。本文中主要针对静态无线传感器网络模型的定位精度、定位覆盖率、以及算法可扩展性进行研究，并以此为基础，然后根据不同网络模型特点研究与其相适应的定位技术及相关问题。
1.2 国内外研究概述
国际上目前比较有代表性和影响力的无线传感网络实用和研发项目主要应用于军事方面。民用方面，美日等发达国家在对该技术不断研发的基础上在多领域进行了应用。
对于国内的研究现状。我国许多高校已经着手于有关无线传感器网络方面的的工作研究[30-42]。同时一些国产企业也开始了这一课题的研究 [35-39]。不过从整体来看，我国关于无线传感器网络的研究仍处于起步阶段。
1.3无线传感器网络的体系结构及特点
如图1.1所示，首先将传感器节点均匀的分布在监测区域，所谓无线传感器网络就是有这些节点以自组织的方式构建的。

图1.1无线传感器网络体系结构
从上图为无线传感器网络体系结构。传感器节点的主要任务是感知被监测区域的对象并对相关信息进行采集，可对所采集的数据先进行预处理然后再发送出去，其传送路径是有章可循，其最终将所采集的信息传递到汇聚节点该节点也叫做数据中心或基站，该中心主要是用来处理数据，储存相关信息，传递数据的，它是实现整个网络同外部互联网络相连接必不可少的一部分。数据传送到汇聚节点后，汇聚节点会对该数据进行再处理，经互联网或卫星将处理后的数据传送到用户端，供用户端进行数据处理。同时用户也可以对传感器网络进行参数调整进而对其控制管理。
所谓无线传感器网络(Wireless Sensor Networks)就是有一定数量的传感器节点以其自行组织的方式形成网络。其中这些传感器节点均具有感知、计算和无线通信的能力。大量的节点抛撒到向监测区域，各传感器节点通过自组织方式组建无线通信网络。被分散到监测区域的各个节点。利用其内置的传感器件对其附近环境进行观察，并收集相关信息。下面详细介绍一下无线传感器网络的特点:
1.电源能量受限：无线传感器网络中的节点在工作过程如果其供电电池没电了，不允许给其更换电池换是充电。
2.原料资源受限：由于无线传感网络整个网络投入资本少、占用空间少、能量消耗低的特点，所以很难找到符合其要求的硬件和软件资源。
3.不存在中心：无线传感器网络的网络结构通常是对称的。
4.自行进行组织：无线传感器网络没有固定的基础设施即可实现布设和展开
5.多跳路由：两节点进行会因距离太远而受到限制，如果距离较远时，可以通过中间节点多跳路由来实现。
6.动态拓扑：在该传感器网络中，其节点不是固定不动的它是动态的，因而其网络的拓扑结构也是动态。
7.节点数量众多，分布密集：监测区域的节点众多，分布密集，利用高密度性以确保整个系统的容错性和抗毁性。
总体来说：无线传感器网络是特殊的adhoc网络。它的特殊之处在于其节点数量较多分不较密集，通常不采用统一的编址，其电源容量有限，要严格控制电量消耗，该网络的拓扑结构是动态的。除此以外，无线传感器节点硬件结构简单，通信和计算能力有限，不具备人机控制界面，节点间通信自动协作和交换。可见无线传感网络并不完善，有许多问题有待解决。
管理平台可分为能量、移动和任务管理平台。能量管理平台主要工作是管理节点怎样处理其能量的，例如节点接收到其临近节点发送的信息好其将关闭接受机关以免再次接受同样信息造成浪费，如果该节点没有电量了，其也会通知临近节点其没电了，这样就不会再向它发送信息。移动管理平台能够监测并记录节点的移动。任务管理平台的主要任务是给各个节点安排具体的工作。
1.4无线传感器网络的主要应用
无线传感器网络无线传感器网络同传统传感器网络获取及处理信息的方式不同，它不再需要固定的网络基础设备，同时它与传感器传统相比，它具有获取信息速度更快，使用寿命更长等优点。其主要适合应用于不适于人员值守的环境，或是对人体有害的环境例如：
（1）军事领域：美国军事部门在一定程度下促使了这一网络的产生与发展。因为无线传感器网络其自组织，配置方便，价格适中等优点，是条件环境恶劣战场的最佳选择。可以利用飞机或弹炮将其散射到敌方，然后可以近距离的收集敌方战场信息。
（2）环境监测：经济的不断发展，但同时也带来了一定的环境问题。随着人们生活质量的不断提高，人们对环境的要求也越来越高，所以保护环境已经成为一个热门话题。利用无线传感器网络的特有优势可以在环境监测方面提供很大的帮助。首先，传感器节点可以集成各类传感模块的传感器节点，可以对环境中各种因素进行监测，例如大气、温度等，除此以外还可以用于跟踪鸟类迁徙从而进一步分析该物种。其次，由于无线传感器网络的覆盖范围较大，可以利用这一点对大区域进行监测，利用此网络对湖泊、河流沙漠等进行监测将会减少资金投入；再者，其还可以应用到人工作业存在危险的环境。
（3）医疗护理：无线传感器网络在医疗护理方面的应用前景也十分令人期待的。例如可以监测病人的各项指数。
（4）建筑监控及智能家居：高楼建筑及桥梁往往会受到外界环境及其自身负荷的影响，从而存在一定的安全隐患。如果在楼宇中安装无线传感器网络，可以时刻监测该楼宇的各项指标，当其出现异常时会向管理部门进行报告并作为修复的决策依据。Straser和Kiremidjian首次运用采用无线传感器网络监测建筑物状态，随后许多学者也对之一课题进行研究同时无线传感器网络可以实现家居智能化，使人们家庭生活更加舒适、安逸。例如，可以在房间内安装可以感知温度、空气指数等无线传感器，从而可以掌握房间的相关因数从而控制门窗及其他家电进行自动控制。除此以外可以给家电安装上传感器节点，通过外部网络实现远程遥控。
（5）空间探索：空间技术在一定程度上标志着一个国家的综合实力，因而各国科学家都热衷于外星球的探索。将传感器节点散播在外星球的表面能够对其进行有效的监控。采用这种方式进行外星球的探索，在一定程度上节省资金成本，同时其所占空间小，可以很好的同地面进行交流。
（6）其他应用：无线传感器网络在其它一些领域也具有巨大的应用价值。例如发生矿难时，利用无线传感器网络，可以迅速而准确的确定受困人员的位置，及井下情况，进而指导受困人员逃离现场或是制定营救措施。在交通；领域应用无线传感器网络，采集各个路口的车辆信息可以有效的抑制交通堵塞现象的发生。
1.5节点定位技术及其意义
无线传感器网络的定位技术[12]是无线传感器网络[3]的研究热点之一。同时定位技术是无线传感网络的进行应用的基础。如果我们不清楚感知节点的位置信息那么感知节点所采集的数据信息是没有实际意义的。只有将两者结合起来才算完成了一个监测对象的确认。由此可见获取节点位置信息的重要性。
获得节点位置信息的传统方法是用GPS系统实现定位。GPS系统需要接收的卫星信号来估算自身和卫星的距离，对于接收机的时钟要求很高，，且无线信号容易受外界因素干扰，能耗较高。因为考虑到节点的价格较低、所占空间较小、能量消耗较低同时软硬件资源较缺乏等，为每个节点配置一台GPS设备并不现实。目前，主要解决方法是利用少量位置信息已知节点（GPS定位或者人工预设位置信息），通过一定的节点定位算法，来获得其他未知节点的位置信息。
最近这几年，海内外许多学者投身于无线传感器网络节点自身定位技术的研究并取得了不错的成绩，同时针对这一问题又提出许多新的课题与想法。对于不同的问题和不同的应用就要采取不同的解决方案和算法。在实际应用中，针对不同的应用需求定位问题的解决方式也有所不同。总之，现在该技术并不完善，下面简单介绍一下其存在的问题：
1） 用于定位技术的资金投入较大；
2） 受自身能量的限制，制定方案时要综合考虑；
3） 目前测距的方法缺乏高精确度；
4） 节点存在的误差会因节点数目太大而累积；
5） 定位所需要的时间会很长；
6） 移动节点定位技术不是很成熟。
尽管无线传感器网络技术作为一新兴技术，其还处于起步阶段，很多地方还不完善，有待改进。针对这一技术目前首要解决的是其定位算法的研究选择，与此同时要对其将来的发展方向进行预测，其以后的发展方向可能有：
1）标准的仿真技术和仿真系统可用来模拟定位算法；
2）对于定位算法的性能评价，可以实现模型化和量化；
3）在变化的网络环境中，定位算法能够具有自调整的性能；
4）大规模或者超大规模网络自身定位的实现和节点定位的高精度的实现。

第二章无线传感器网络定位技术综述
海内外许多研究学界从事无线节点定位这一问题的研究，并取得了一定的成就，提出大量的算法。这些算法大体可以分为两类一是基于测距的(Range-based)算法另一种是基于非测距的(Range-free) 算法。在这一章首先会介绍一些基础概念和一些相关术语，然后会介绍与距离有关的一些定位算法并进行分析总结对当前已有算法的优缺点进行说明。
2.1概念和术语
无线传感网为了获取节点位置信息，考虑成本、功耗、环境的各因素的限制，通常会布置一定数目自身位置信息已知的节点，通过这些界定与其他位置信息未知的节点之间通信与计算，获取每一个节点的位置信息。此过程中常用的概念与术语如下：
锚节点（anchor nodes）：也称为导标节点（beacon nodes），网络初始状态自身位置信息已知的节点。
未知节点（unknown nodes）：网络中锚节点以外的其他节点，网络初始状态自身位置信息未知，通过网络与锚节点互联计算获取位置信息。
邻居节点（neighboring nodes）：每个节点的通信范围内节点的集合。
节点度（node degree）：与一节点相邻节点的个数。
跳数（hop count）：一节点到另一节点的跳段的总和。
跳距（hop distance）：从一节点到另一节点的所有跳段的距离和。
上文中提到将定位算法大体有两类，一类是基于测距的定位算法，另一类是基于非测距的定位机制算法，这两种算法的机制有明显的不同，前者必须在已知未知节点与锚节点之间的距离或者角度信息情况下，再进行测量。而后者不是根据距离进行定位的而是由整个网络的连通性等相关信息从而得出节点的位置。
3.2 与距离有关的定位算法分析
2.2.1 基于测距的定位方法
这是常用的定位方法。不过利用这种方法事先要知道两个节点的位置关系的信息，例如距离或角度，其过程大体分为三个阶段：
（1）测距阶段。测量锚节点与其临近已知节点的位置信息角度或距离，在测量所求未知节点到该已知节点距离或角度，进而得到它到锚节点的直线距离。
（2）定位阶段。根据未知节点到与其临近的三个或以上锚节点的距离或角度，利用相关算法即可求出位置节点的坐标；
（3）修正阶段。主要针对阶段（2）所得到的坐标进行进一步求解已到达减小误差的目的。
2.2.2 到达时间（TOA）定位法法
TOA[24]技术是通过测量信号传播时间来测量距离。其实质上是利用速度乘以时间两者的积为距离。利用这种定位方法必须要确保节点有非常精确的时钟。
2.2.3 时间差（TDOA）定位法
TDOA[24]测距是通过计算两种不同无线信号到达未知节点的时间差，再根据两种信号传播速度来计算得到未知节点与锚节点之间的距离。
平面解析几何中定义双曲线法是到两定点的距离差为常数的点的集合，其中这两个定点叫做焦点。TDOA定位同双曲线的几何意义相类似它将两个锚节点设为双曲线的焦点，则未知节点到两锚节点的距离差即为双曲线的实轴，经过测量即可得到未知节点所属的两个以上双曲线方程时，则他们的交点即为未知节点的位置。利用这种方法虽然对时间的同步性要求不高，但仍要求要有准确的计时功能。不过这种方法因为无线传感器网络其传感器节点数量较大其无线通信范围小实现起来并不容易。
2.3 与距离无关的定位算法分析
2.3.1 质心算法
质心算法[9]的中心思想是：未知节点将其信息可以传递到的最大范围内的所有锚节点的几何质心视为自己估计位置。
在该算法中，锚节点每隔一定时间临近的节点广播同一个信标信号，当未知节点在一定时间内所接收到信标信号的数量超过设定值以后，该未知节点则认为它通锚节点建立了连通。
而所谓质心算法则体现在未知节点将其自己的位置确定为所有与之连通的锚节点所组成的多边形的质心。
值得说明的是信标节点中携带着该节点的各种位置信息和标识号等。
该方法较其他算法较简单，同时处理的数量较少，适合于无线传感网络，但利用这种方法需要大量的锚节点。
多边形ABCDE的顶点坐标分别为：A，B，C、
D、E，其质心坐标：
。
采用质心定位算法其第一步是要首先确定未知节点所处的区域，然后算出整个区域的质心，将这个质心视为未知节点的位置。在这种算法中，信标节点会定期向其临近节点广播信标分组，而当未知节点所接收到的不同信标节点的信标分组数量超过设定值或是接收时间超过规定值，就确定自身位置为这些信标节点所组成的多边形的质心。
该算法以网络连通性为基础，操作简便，容易实现
2.3.2 DV-Hop算法
DV-Hop算法：锚节点会以泛洪的形式将携带其自身的位置信息和一个初始值为1的跳数的信标在网络中广播出去。当信标被其他节点转发时，它的跳数将会加1。则接收节点只会保存有关该锚节点的跳数最小的信标，将跳数较大的信标舍弃。利用这一方法，网络中所有节点(包括其他锚节点)都获得了到每一个锚节点的最小跳数值。表示了网络中的节点到锚节点A的跳数值。
求一个锚节点到另一个锚节点的实际距离，利用平均每跳的平均估算值乘以从该锚节到另一个锚节点的跳数即可。通过计算可以得到锚节点每跳的平均距离，然后将这个值广播到网络中，则这个值被叫做校正值，一旦其它节点接收到这个值，并可估算其到锚节点的距离。如果是未知节点，其得到3个以上校正值并可利用最小二乘法就可以估算出其自身的位置。
DV-Hop算法同基于测距算法的原理基本相似，不过他们通过不同的方法获得距离，其中DV-Hop算法是通过网络中拓扑结构信息来计算得到的，基于测距算法通过无线电波信号的测量得到的。
DV-Hop算法同基于测距的算法相比不再局限于其节点自己射频所能覆盖区域范围的锚节点的距离，它获其射程以外的锚节点的距离，利用这种方法可以有限提高定位精度。
Sum-dist一个缺点便是当进行多跳传播的时候，节点的测距误差会发生累积效应。这种累积误差会受到网络规模较大小或锚节点数量等因素的影响。Ad-Hoc positioning中将其称为DV-Hop，Robust positioning中则将其称为Hop-TERRAIN。DV-Hop实际上由两波的洪泛组成，第一波洪泛中类似于Sum-dist，节点获得锚节点的位置信息和离锚节点的最小跳数。在第二波洪泛中将跳数信息转换为距离信息。每个锚节点根据第一波中记录的跳数信息和相距距离，利用式（3-1）估算平均每跳实际距离
（3-1）
式中 ，为锚节点的坐标；为锚节点i和 j(i≠j )之间的跳数。锚节点计算完每跳平均距离后，用带有生存期字段的消息分组广播到网络中，未知节点会将收到的第一个每跳平均距离记录下来，并将其转发给临近点。这个策略确保了绝大多数节点从最近的锚节点接收到每跳平均距离值。未知节点接收到平均每跳距离后，在根据其先前记录的跳数，即可算出其到各个锚节点的距离。
DV-Hop算法包括三个步骤。第一步，主要求的锚节点到除图自己以外所有节点的跳数 (distance in hops)。第二步，在完成第一步以后，要计算锚节点到其他节点每跳的平均距离，将这个值作为校正值(correction)将以可控洪泛的形式广播到网络中去。每个节点一旦接受到一个校正值后就不在接受其他的校正值了，之所以不在接受其他校正值视为了确保它是从离它最近的锚节点接受的。第三步，主要利用未知节点所获得与3个或更多锚节点的距离利用三边测量进行定位。
从图3-4我们可以看出，已知锚节点L1与L2，L3为已知锚节点间，它们的距离及跳数从图中可以看出。已知L2的校正值为 (40+75)/(2+5)=16.42。假设未知节点A从L2获得校正值，由此可以得到它到3个锚节点之间的距离分别为L1-3*1.642，L2-2*1.642，L3-3*16.4，通过这三个数再利用三边测量法即可得到节点A的位置。
75m

L2
L1
A
L3
100m

40m

图3-1 DV-Hop算法
2.4小结
进过上面的介绍，我们可以发现现有的定位算法都各有其优缺点。一般而言，与距离有关的定位算法需要增加配备硬件装置，导致所需的能量和成本加大，受环境影响大，通用性差。而与距离无关的定位算法不需要额外的硬件配置，通用行佳，虽然定位精度不如前者，但是在大多数的传感器网络实际应用中，这样的精度是可以满足应用需求的。我们将提出一种改进的粒子群算法，对DV-Hop算法进行优化，以获得更佳的定位精度。
第四章 DV-Hop算法改进的定位技术
4.1 DV-Hop算法的缺陷
(1)下面介绍一下无线传感器网络中的bad节点；
(i)图4-1是第一类bad节点的示意图，节点M为已知节点，其位置坐标为已知，节点N是未知节点，其位置不确定，它可能在N1，也可能在N2、…Nn但它的一跳节点只能是M，则这样的节点N被称为 bad节点。

图4-1 第1类bad节点的示意图

图4-2 第2类bad节点的示意图
(ii)图4-2为第2类bad节点的示意图，其中E，F为已知节点，它们的位置坐标是已知的，节点N为未知节点，它的位置不确定可能出现在N1…Nn ，这个N个位置，但节点N的一跳节点为E或F
(iii)图4-3是第3类bad节点示意图，其中节点M为已知节点，其位置坐标是已知的，bad节点是节点群，该节点群的各个节点均为未知节点，通过该图可以看出该节点群要同网络进行通信，必须经过节点M。

图4-3 第3类bad节点的示意图
(2) 利用已知节点间的平均每跳距离来代替未知节点与已知节点之间的跳数的实际测量值，显然这种方法存在很大的误差。
(3)已知节点数量同其可监测的面积成正比。而监测覆盖的面积又同节点的定位覆盖率成正比。当已知节点数目较少时，未知节点所要经过的跳数就要随之增多，才能通其进行通信，显然这样误差就会增大。
(4)在过程3的定位阶段，使用三边测量法进行估计待测节点的坐标。这种测量方法存在一定的误差。
4.2 DV-Hop算法的改进
4.2.1 DV-Hop算法的距离误差校正
在先前传统算法中，将未知节点到已知节点的距离用已知节点间的平均每跳距离HopDisef乘以跳数代替，显然那这种算法存在很大的误差。而且事实上，未知节点到已知节点的距离并不是简单的直线，多数情况下是曲线。
步骤1已知节点将会利用广播的形式将其各种信息发送给其它已知的节点，当另一个已知节点收到该已知节点发送的信息后，就可以确定出它们之间的实际距离。计算出用RSSI测量的距离值与每跳距离的均值，则两已知节点的总长度误差校正值lenef，即为每跳均值与实际长度的差
总长度误差校正值的表达式为：
（4-1）
Disef：己知节点e到已知节点f动实际长度；
disef：已知节点e到己知节点哟每跳长度和；
注意e和 f不是同一个节点
路径损耗的分布模型：
（4-2）
（4-3）
K0：接收点的参照长度（k0=1），
K0：接收点的参照长度（k0=1），
q：路径损耗系数，它的取值在（2,4）内
Y0：0均值的高斯分布随机变量。
在公式（4-1）中，有以下成立：
（4-4）
（4-5）
m为：己知节点e到已知节点f的总跳数
HopDisef：己知节点e的平均每跳长度

步骤2，各个未知节点到同一已知节点的长度并不相同，因而所产生的距离误差也不同，不能够使用统一的校正修正值来计算，因此求e到节点f的平均每跳误差校正值avgeef：
（4-6）
M：已知节点e到己知节点f的总跳数是m
在无线传感网络中，已知节点会将自己到其它已知节点的m、lenef、avgeef以广播形式传递出去，当另一个节点接收到这些数据后将会保存在一个路由表{IDk，xk，yk，hopk}内，接着这个节点将会在将这些数据传送给与它邻近的抑制节点，不过跳数将变成m+1。
当已知节点得到跳数后，会将{IDk，xk，yk，hopk，mm、lenef、avgeef}中hopk新值同旧值进行对比。如果新的hopk值比旧的的hopk值小，则用其代替旧值若果新的hopk值比旧的的hopk值大，它将被舍弃。通过两者的对比，即可得到未知节点到已知节点的最小长度。
步骤3，利用以上两步找到离待测节点最近的3个已知节点。或是多于3个，同时还要获得这些已知节点的lenef值和avgeef值，通过这两个值，即可得到待测节点到其与所有已知节点的长度
利用上述方法求出待测节点w与己知节点e的距离Dwe:
（4-7）
M：待测节点w与已知节点e之间的总跳数
avgeef：已知节点e、润的平均每跳误差校正值
HopDise*M：待测节点w与已知节点e的每跳距离和
4.2.2 MIN-MAX方法与加权最小二乘法的结合
MIN-MAX算法同传统的三边测量法相比，在求解未知节点的坐标过程中，相对减少了浮点运算量。但其定位的精度要根据节点数量而定。不过当已知节点数量较多时，其能量消耗及成本都将会有所提高所以此次采用MIN-MAX与加权最小二乘法相结合的算法。
利用该方法主要分为两部分:首先先利用MIN-MAX算法，进行待测节点位置的粗略求解然后利用加权最小二乘法求出估计待测节点的坐标。
(l)MIN-MAX算法
图4-4 为MIN-MAX算法示意图，从图中可以看出将将已知节点设为圆心，待测节点到它的估算值设为半径，建立一个圆形，同时做一个外切于圆的正方形
利用同样的方法建立多个正方形，取它们的交集的几何中心，该中心即为利待测节点的估算位置。

图4-4 MIN-MAX算法示意图
已知节点(xs，ys)的范围由[(xs-ks)，(ys-ks)]*[(xs+ks)，(ys+ks)]得到。其中，ks指待测节点到己知节点的估算长度。交集范围可由公式(4-8)求解出:
（4-8）
待测节点的估算位置是此交叉范围的几何中心，见公式（4-9）：
（4-9）
(2)加权最小二乘法
求解待测节点的估算坐标值：
（4-10）
ts(x)：是由有G个待测节点到已知节点的长度估算所构造的值残差方程
注意上式只适用于不知道距离时进行估算。
加权最小二乘的估算值:
（4-11）
ws：加权系数
注意上式只有在知道所有的距离估计值时才可以使用。
残差方程的表达式如下:
（4-12）
(x，y)：待测节点的位置
(xs，ys) ：已知节点的位置
ks：度量的长度
其中ts(x，y)是非线性函数，在求解它的过程时要用到非线性最优化理论。线性化求解ts(x，y)的表达式，具体如下:
（4-13）
（4-14）
式（4-13）减去式（4-14）之后，有以下方程组：
（4-15）
最终整理为：
（4-16）
设有以下方程组成立：
（4-17）
线性处理后，最小二乘的结果如下：
（4-18）
用矩阵可表示成：
（4-19）
加权最小二乘法（WLS）的估算坐标是：
（4-20）
在公式（4-20）中，
（4-21）
（4-22）
（4-23）
为最小方差无偏估计的其判定的依据是W为对称正定矩阵。当时估算值的均方误差最小。（M为长度误差的方差矩阵）。
在此阶段，设已知节点的权值是1，待测节点的权值在0.1的基础上逐渐增加，它的取值范围是[0，l]。步长是0.05，循环求精时，待测节点的权值依次增加0.05。
(3)定位过程
过程1，主要是对待测位置进行粗略的估算。这一过程主要利用MIN-MAX算法。求出未知节点的粗略坐标，同时引入了加权系数。
过程2，利用加权最小二乘法来改变求的未知节点的精确坐标。
4.2.3 改进算法的流程图
图4-5和图4-4分别为改进算法的已知节点程序流程图和改进算法的未知节点程序流程图，由图可知未知节点和已知节点改进过的程序流程图并不相同 。

图4-5 改进算法的已知节点程序流程图

图4-6 改进算法的未知节点程序流程图
4.3 DV-Hop算法流程图
该算法由三阶段组成。具体实现见第3章的DV-Hop算法部分。
在该算法中将会用到两种重要的路由协议[9]：洪泛协议和距离矢量路由协议。
（1）洪泛协议，是最简单的路由协议，此协议中没有任何路由算法。当数据没有达到目的节点时，节点会相其周围的所有临近节点广播其所收到的数据。如果达到数据报的最大跳数还未传到目的节点，也会停止广播。洪泛协议的缺点是容易引起信息重叠，造成网络拥塞。
（2）距离矢量路由协议，是简单路径的分布式路由算法。每个节点维护一张到网络中已知位置节点的距离估计和下一跳的路由表。每个节点只记录到目的节点的跳数和通向目的节点的下一跳。节点接收到数据后，根据数据包头部的目的地址来查找路由表，并将其转发到下一跳所指定的节点。
该算法的总体流程图如下：

图4-7 网络总体流程图

图4-8 网络流程图

图4-9 锚节点模块流程图
4.4DV-Hop算法仿真结果分析
4.4.1 仿真设计
已知无线传感器网络的侧重点，现在将要对进行节点定位的网络做如下安排：以此类推
（1）无线传感器网络节点部署在二维的平面区域上，这样未知节自身定位时仅需三个锚节点的位置和距离信息；以此类推要是三维空间则，则需要四个锚节点的位置和距离信息。
（2）传感器节点所采用的模型是自由空间电波传播模型，该节点在一个圆内进行通信。
（3）传感器节点可以感知其周围存在的节点，并进行通信没有限制。
（4）两个传感器节点间它们的通信能力是对称的，它们之间传递的消息都将可以正确接收。
（5）由于种种限制，只有部分传感器节点装有定位装置进而成为锚节点，但其他节点也具有这种处理能力。
（6）节点拥有两种不同的标记：anchor、single，分别用来表示锚节点和无法定位的节点。
参数设置如下：
BorderLength：正方形区域的边长，单位：m
NodeAmount：网络节点的个数
BeaconAmount：信标节点数
Sxy：用于存储节点的序号，横坐标，纵坐标的矩阵
Beacon：信标节点坐标矩阵，BeaconAmount*BeaconAmount
UN：未知节点坐标矩阵，2*UNAmount
Distance：未知节点到信标节点距离矩阵，2*BeaconAmount
H：节点间初始跳数矩阵
X：节点估计坐标初始矩阵，X=[x，y]
R：节点的通信距离