无线传感器网络单元定位算法研究与实现

第1章 绪论

绪论

1.1 选题背景和研究意义

微电子、无线通讯与计算机技术的发展，促使低能耗多用途传感器被广泛运用在各个领域。无线传感器网络[1](Wireless Sensor Network，WSN)由许多小、价格低的传感器节点构成，它们被撒播在监测范围中，利用无线通讯自组织成为具有多跳的系统。WSN能够感应、获取监测范围内的数据，之后把这些感兴趣的数据传递给监测人员。传感技术的任务是获取数据，通讯技术的任务是传递数据，计算机技术的任务是处理数据。在真实的运用环境中，获取数据会遇到以下难题:不容易布置线路、获取信息的面积大。

在传感器网络中，位置信息对传感器网络的监测活动至关重要，事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没有位置信息的监测消息往往毫无意义对于这些问题，传感器节点必须首先知道自身的地理位置信息，这是进一步采取措施和做出决策的基础。

定位信息除用做报告事件发生的地点外，还具有下列用途:目标跟踪实时监视目标的行动路线，预测目标的前进轨迹;协助路由，为网络提供命名空间，如直接用节点位置信息进行数据传递的地理路由一协议，避免信息在整个网络中的扩散，并可以实现定向的信息查询；进行网络管理，利用传感器节点传回的位置信息构建网络拓扑图，并实时统计网络覆盖隋况，对节点密度低的区域及时采取必要的措施，实现网络负载均衡以及网络拓扑的自配置，等等。因此在传感器网络中，传感器节点的精确、快速定位对各种应用有着重要的作用。

WSN在国防军事、环境监控、灾害预测等多个领域被广泛运用。在WSN中，若有某几个节点被蓄谋攻击致使不能使用，这将不可能使网络整体瘫痪。如果我们认为互联网组建了虚拟世界，使人们的通讯方式发生了变化，则WSN便融合了虚拟世界与现实世界，这无疑使人和自然的交流发生了变化。这会让我们现在的生活发生翻天覆地的变化。

一般情况下，我们会认为采用GPS(Global Positioning System)来确定节点的坐标。但在WSN中，并不完全适合使用GPS进行定位，具体理由如下:

1

燕山大学本科生毕业设计（论文）

首先，传感器(sensor)节点[2]使用电池供电(2节五号电池)，其能量受限，并不能及时更换电池来维持能量。因为GPS消耗能量特别大，所以不适合给每个传感器节点都配置能耗较大的GPS设备。其次，WSN的工作环境特别复杂，不能一定使接收仪器与卫星之间可以无阻碍的进行通讯。在没有阻碍物的情况下，GPS设备才能够正常工作。再次，传感器节点的体积较小，然而GPS设备增大了传感器节点的体积，不符合WSN中传感器节点小的特性。最后，WSN中的传感器节点被大量分布在监测范围内，数量达到了几千乃至上万个。用GPS定位使得成本增大，不符合WSN的价格低廉性。

由于监测是一个长期与漫长的过程，一般情况下，监测范围的环境都比较恶劣，监测人员不容易抵达这些区域，故不能及时给传感器节点补充能量。又因传感器节点具有以下特性:能量受限、通讯能力受限、密集且随机分布，故节省能耗和效率高是实现WSN节点定位技术需要考虑的第一因素。考虑到传感器节点在能量、体积、环境、价格等方面的一些要素，可知GPS不完全适用于WSN。这就要求我们必须设计出适合在WSN中使用的节点定位算法。

1.2 国内外研究现状

国际上比较有代表性和影响力的无线传感网络实用和研发项目有遥控战场传感器系统[2]（Remote Battlefield Sensor System，简称REMBASS --伦巴斯）、网络中心战[2]（NCW）及灵巧传感器网络[2]（SSW）、智能尘[2]（smart dust）、Intel ?Mote、Smart-Its项目、行为习性监控[2]（Habitat Monitoring）项目等。尤其是今年最新试制成功的低成本美军“狼群”地面无线传感器网络标志着电子战领域战术的最新突破。俄亥俄州正在开发“沙地直线”（A Line in the Sand）无线传感器网络系统。这个系统能够散射电子网（tripwires）到任何地方。民用方面，美日等发达国家在对该技术不断研发的基础上在多领域进行了应用。

对于国内的研究现状。清华大学、中国科技大学、浙江大学、华中科技大学、天津大学、南开大学、北京邮电大学、东北大学、西北工业大学、西南交通大学、沈阳理工大学和上海交通大学等单位纷纷开展了有关无线传感

2

第1章 绪论

器网络方面的基础研究工作。一些企业如中兴通讯公司等单位也加入无线传感器网络研究的行列。但是我国的关于无线传感器网络的研究仍旧处于起步阶段。

1.3 研究前景

WSN是新出现的传感器网络，它的发展与运用给人们生活与生产中不同领域都产生了有意义的影响。无基本设备支撑的无线自组织网，其具有以下特性:多跳、自组织与可重构。这类网络的拓扑结构与信道环境都会因节点走动而动态变换。它能够为普通领域的运用与国防军事领域的运用迅速搭设通讯环境。

未来移动通讯网[3]不仅能使数据进行传递，而且还要求在无专用通讯基本设备的情况下，应该具备以下特性:自适应能力与生存能力。因此，WSN与自组织网，能够对其发展起到促进作用。小型传感器节点具备感知、计算与通讯能力，在监测范围内撒播的这些传感器节点构成了WSN。任意一个传感器节点至少装一类感知器(声、红外线或磁感应器等)。监测范围内的所有传感器节点之间，都通过特定协议进行传递与获取数据，最终定位并跟踪对象。通讯、嵌入式与传感器这3项技术的逐渐成熟，使得WSN快速发展。这使得学者与专业研究人员高度重视WSN。在国防军事、环境监控、医疗护理等众多领域，WSN都被广泛运用。

在WSN中，获取位置是其监测对象的重要任务，知道事件准确发生地是整个监测活动的重要环节。传感器节点一般被随机撒播在监测范围内，例如它们被撒播在监测生态环境、火灾现场等场所，这些传感器节点并不清楚自己的位置，故要求传感器节点一旦被分布，就应该可以快速自定位。除了这些描述，定位技术还具有别的功能:网络管理、改善路由、目标跟踪等。

对于网络管理，获取的传感器节点数据被用来构造拓扑结构图，为了及时知道网络的涵盖范围，使得节点不太多的地方可以快速采取相应挽救措施。节点坐标数据还有一个特别功能，就是用来辅助实现路由。在知道任意一个节点与其周边节点的坐标后，网络才可以达到改善路由的目的。优化路由的好处是:改善系统的性能、安全性与节约电量。

3

燕山大学本科生毕业设计（论文）

因此，在WSN的任何一类运用中，准确定位传感器节点起着举足轻重的作用。准确定位是WSN运用的基础，是其支撑技术。可以看出，WSN节点定位技术的运用前景相当好。

1.4 论文主要研究内容和结构

本研究旨在设计与实现一种高效、鲁棒性[4]好、代价小的无线传感器网络节点定位算法，使之适应于一些复杂环境下的定位需要。

由于传感器网络部署完成之后，我们要面临的首要问题就是无线传感器网络目标节点的定位。所以可知，定位技术是WSN的一项重要支撑技术。本文研究了基于测距和无需测距的定位算法，并总结了这类算法的优劣势。其中重点研究与分析了己有的DV-HOP[5]算法及其改进和基于多维标度定位算法的定位原理。针对DV-HOP算法固有的一些不足，提出了一种改进方案。

对于本论文重点研究的DV-HOP定位算法，重点研究了以下内容：计算出用RSSI测量的距离值与每跳距离和的均值，然后利用该均值与实际距离的差值，得到总距离与平均每跳的距离误差校正值。用MIN-MAX[5]与加权最小二乘法的混合定位法替换了三边测量法。该算法不仅降低了平均定位误差、提高了节点的定位覆盖率，同时还减少了计算代价。

本文的主要内容安排如下:

第一章首先简单介绍了论文的选题背景和国内外研究现状，之后，简要说明了此课题的国内外研究现状和存在的问题。最后是介绍了论文的主要研究内容和论文结构。

第二章主要介绍无线传感器网络相关背景知识。阐包括无线传感器网络的基本概念及其体系结构；分析了无线传感器网络不同于传统网络的一些自身特点。

第三章根据WSN的特点介绍了WSN的体系结构和特征；然后重点研究了基于测距技术的定位算法分析和与距离有关、与距离无关的定位算法分析。

第四章重点对DV-HOP的改进。重点研究了以下内容：计算出用RSSI[5]测量的距离值与每跳距离和的均值，然后利用该均值与实际距离的差值，得

4

第1章 绪论

到总距离与平均每跳的距离误差校正值。用MIN-MAX与加权最小二乘法的混合定位法替换了三边测量法。该算法不仅降低了平均定位误差、提高了节点的定位覆盖率，同时还减少了计算代价。同时对DV-Hop算法进行了MATLAB仿真结果分析，得出结论，给出最佳方案。

最后是参考文献、致谢、附录。

1.5 本章小结

本章首先简单介绍了无线传感器网络的起源和研究进展状况，之后，简要分析了节点定位技术对无线传感器网络的意义并详细描述了定位技术的国内外研究趋势和研究热点。最后简要描述了本文的组织结构和内容安排。

5

燕山大学本科生毕业设计（论文）

使用TOA技术比较典型的定位系统是GPS。

TDOA测距技术在无线传感器网络定位方案中得到了较多的应用。通过记录两种不同信号的到达时间差异，根据已知的两种信号的传播速度，直接把时间差转化为距离。该技术受到超声波传播距离的限制和非视距问题对超声波信号传播的影响，不仅需要精确的时钟记录两种信号的到达时间差异，还需要传感器节点同时具备感知两种不同信号的能力。

3.3.3 时间差定位法

TDOA[24]测距是通过计算两种不同无线信号到达未知节点的时间差，再根据两种信号传播速度来计算得到未知节点与锚节点之间的距离。TDOA定位与TOA测距不同，TDOA定位计算两个锚节点信号到达未知节点的时间差，将其转换成到两个锚节点的距离之差，未知节点通过到多组锚节点的距离之差得出自身的位置。

在二维平面上的，双曲线的几何意义是到两个定点的距离之差为一个常数的所有点的集合，两个定点称作焦点。因此：得到未TDOA定位在二维平面上的几何意义为知节点与两个锚节点的距离之差，即可知未知节点定位于以两个锚节点为焦点的双曲线方程上，通过测量得到未知节点所属的两个以上双曲线方程时，这些双曲线唯一的交点即为未知节点的位置。由于这种方法不是采用到达的绝对时间来确定节点的位置，降低了对时间同步的要求，但是仍然需要较精确的计时功能，同时由于无线传感器网络具有分布密集和无线通信范围小的特点，这种方法实现起来难度较大。

3.4 与距离无关的定位算法分析

3.4.1 质心算法

质心算法[9]的中心思想是：未知节点以所有在其通信范围内的锚节点的几何质心作为自己的估计位置。

具体过程为：锚节点每隔一段时间向邻居节点广播一个信标信号，信号中包含有锚节点自身的ID和位置信息。当未知节点在一段侦听时间内接收到来自锚节点的信标信号数量超过某一个预设的门限后，该节点认为与此锚节点连通，并将自身位置确定为所有与之连通的锚节点所组成的多边形的质

16

第3章 无线传感器网络定位技术

心。

质心定位算法的最大优点是它非常简单，计算量小，完全基于网络的连通性，但是需要较多的锚节点。

多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。多边形ABCDE的顶点坐标分别为：A(x1,y1)，B(x2,y2)，C(x3,y3)、

D(x4,y4)、E(x5,y5)，其质心坐标：

(x,y)?[(x1?x2?x3?x4?x5)/5,(y1?y2?y3?y4?y5)/5]。 质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置。在质心定位算法中，信标节点周期性地向临近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息。当未知节点接收到来自不同信标节点的信标分组数量超过某一门限或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。

由于质心算法完全基于网络连通性，无需信标节点和未知节点之间的协调，因此简单、易于实现。

3.4.2 DV-Hop算法

DV-Hop算法是由D.Niculescu和B.Nath等人提出的。DV-Hop定位算法的原理与经典的距离矢量路由算法比较相似。在DV-Hop算法中，锚节点向网络广播一个信标，信标中包含有此锚节点的位置信息和一个初始值为1的表示跳数的参数。此信标在网络中被以泛洪的方式传播出去，信标每次被转发时跳数都增加1。接收节点在它收到的关于某一个锚节点的所有信标中保存具有最小跳数值的信标，丢弃具有较大跳数值的同一锚节点的信标。通过这一机制，网络中所有节点(包括其他锚节点)都获得了到每一个锚节点的最小跳数值。表示了网络中的节点到锚节点A的跳数值。

为了将跳数值转换成物理距离，系统需要估计网络中平均每跳的距离。锚节点具有到网络内部其他锚节点的跳数值以及这些锚节点的位置信息，因此锚节点可以通过计算得到距其他锚节点的实际距离。经过计算，一个锚节点得到网络的平均每跳距离，并将此估计值广播到网络中，称作校正值，任何节点一旦接收到此校正值，就可以估计自己到这个锚节点的距离如果一个

17

燕山大学本科生毕业设计（论文）

节点能够获得到3个以上锚节点的估计距离，它就可以利用最小二乘法估计其自身的位置。

DV-Hop算法与基于测距算法具有相似之处，就是都需要获得未知节点到锚节点的距离，但是DV-Hop获得距离的方法是通过网络中拓扑结构信息的计算而不是通过无线电波信号的测量。

在基于测距的方法中，未知节点只能获得到自己射频覆盖范围内的锚节点的距离，而DV-Hop算法可以获得到未知节点无线射程以外的锚节点的距离，这样就可以获得更多的有用数据，提高定位精度。

Sum-dist一个缺点便是当进行多跳传播的时候，节点的测距误差会发生累积效应。这种累积误差当网络规模很大或锚节点数量比较少和节点测距硬件误差比较大的时候表现更为明显。一个更具有鲁棒性的方法是利用网络的拓扑信息通过计算跳数而不是累加距离来完成。Ad-Hoc positioning中将其称为DV-Hop，Robust positioning中则将其称为Hop-TERRAIN。DV-Hop实际上由两波的洪泛组成，第一波洪泛中类似于Sum-dist，节点获得锚节点的位置信息和离锚节点的最小跳数。在第二波洪泛中将跳数信息转换为距离信息。每个锚节点根据第一波中记录的跳数信息和相距距离，利用式（3-6）估算平均每跳实际距离

?Hopsize?j?i(xi?xj)2?(yi?yj)2?Hopsij?i （3-6）

式中 (xi,yi)，(xj,yj)为锚节点的坐标；Hopj为锚节点i和 j(i≠j )之间的跳数。锚节点计算完每跳平均距离后，用带有生存期字段的消息分组广播到网络中，未知节点仅记录接收到的第一个每跳平均距离，并转发给邻居节点。这个策略确保了绝大多数节点从最近的锚节点接收到每跳平均距离值。未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个锚节点的距离。

DV-Hop算法由3个阶段组成。首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节点的跳数(distance in hops)。第2阶段，在获得其他锚节点位置和相隔跳距之后，锚节点计算网络平均每跳距离，然后将其作为一个校正值(correction)广播至网络中。校正值采用可控洪泛法在网络中

18

第3章 无线传感器网络定位技术

传播，这意味着一个节点仅接受获得的第1个校正值，而丢弃所有后来者，这个策略确保了绝大多数节点可从最近的锚节点接收校正值。在大型网络中，可通过为数据包设置一个TTL域来减少通信量。当接收到校正值之后，节点根据跳数计算与锚节点之间的距离。当未知节点获得与3个或更多锚节点的距离时，则在第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 40m L3 A L1 100m 图3-4 DV-Hop算法

3.5 本章小结

由以上研究明显可以得出：基于测距的定位算法有明显的缺点。例如：使传感器节点造价增高；消耗了有限的电池资源；在测量距离和角度的准确性方面需要大量的研究。而不基于测距的算法不需要知道未知节点到锚节点的距离或者不需要直接测量此距离，在成本和功耗方面比基于测距的方法具有优势。

19

燕山大学本科生毕业设计（论文）

第4章 DV-Hop算法改进和MATLAB仿真

4.1 DV-Hop算法的缺陷

(1)在无线传感器网络中，由于节点被随机分布，所以会存在一些bad节点；

(i)节点N在一跳之内仅存在1个节点。节点M的坐标是已知的，节点N在一跳之内，又仅知道节点M的位置。如图4-1所示，节点N能够出现在N1、N2、…Nn等任何一个地方。即可知，节点N的位置不唯一。换句话说，我们无法判断节点N所在的地方。因此，称节点N为bad节点。

NN1M网络N2Nn图4-1 第1类bad节点的示意图

N

FEN1

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

(ii)节点N在一跳之内仅存在2个节点。节点E、F的坐标是己知的，节点N在一跳之内又仅知道节点E和F的坐标。如图4-2所示，节点N同样也能够出现在N这个地方。即可知，节点N无法确定其所在之处。换句

20

燕山大学本科生毕业设计（论文）

致谢

在论文结束之际，我向曾经给予帮助我的老师、家人及朋友致以最诚挚的谢意，正是他们无私的帮助、鼓励与支持，才使我的大学本科阶段顺利度过。

本论文是在燕山大学张立国导师悉心指导下完成的，衷心地感谢我的导师。老师严谨的治学精神，精益求精的工作作风，值得我学习。在论文期间，感谢导师在百忙之中对论文进行认真的审阅和修改。半年以来，感谢老师为我提供了良好的学习环境，并且在课题工作上给予细心指导，在此致以最诚挚的谢意和最崇高的敬意。

最要感激的是我父母，因为他们在我慢慢的求学路上一直默默的、辛勤的、艰难的支持着我。感谢父母多年来支持我在学业上不断前进，他们在精神和物质上给予我巨大的帮助，让我有条件完成学业。特别要感谢我一个最要好的朋友，感谢他一如既往的支持与鼓励。感谢他给我生活与学习方面的无私帮助，让我有了奋斗的勇气和力量。无私的支持与信任是我完成学业的动力。

感谢父母、弟弟、好朋友对我的关心、支持与鼓励!特别将我的本科毕业论文献给他们，他们无私的爱永远是我前进的动力。

在此向曾经帮助过我的所有人表示崇高的谢意！

最后，向百忙之中抽出宝贵时间评阅本文的老师表示深深的谢意！

46

附录1 DV-Hop算法仿真程序

附录1 DV-Hop算法仿真程序

%~~~~~~~~~~~~~~~~~~~~~~~~~ DV-Hop算法 ~~~~~~~~~~~~~~~~~~~~~~~~ %~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ % BorderLength-------正方形区域的边长，单位：m % NodeAmount-------网络节点的个数 % BeaconAmount------信标节点数

% Sxy---------------用于存储节点的序号，横坐标，纵坐标的矩阵 % Beacon------------信标节点坐标矩阵；BeaconAmount*BeaconAmount % UN---------------未知节点坐标矩阵；2*UNAmount

% Distance-----------未知节点到信标节点距离矩阵；2*BeaconAmount % h-----------------节点间初始跳数矩阵

% X----------------节点估计坐标初始矩阵,X=[x,y] % R----------------节点的通信距离，一般为10-100m

clear,close all; BorderLength=100; NodeAmount=200; BeaconAmount=20;

UNAmount=NodeAmount-BeaconAmount; R=60;

% D=zeros(NodeAmount,NodeAmount);%未知节电到信标节点距离初始矩阵；BeaconAmount行NodeAmount列

h=zeros(NodeAmount,NodeAmount);%初始跳数为0；BeaconAmount行NodeAmount列

X=zeros(2,UNAmount);%节点估计坐标初始矩阵

%~~~~~~~~~~~~~~在正方形区域内产生均匀分布的随机拓扑~~~~~~~~~~~~~~ C=BorderLength.*rand(2,NodeAmount);

47

毕业设计（论文）杜撰

%带逻辑号的节点坐标 Sxy=[[1:NodeAmount];C];

Beacon=[Sxy(2,1:BeaconAmount);Sxy(3,1:BeaconAmount)];%信标节点坐标 UN=[Sxy(2,(BeaconAmount+1):NodeAmount);Sxy(3,(BeaconAmount+1):NodeAmount)];%未知节点坐标 %画出节点分布图

plot(Sxy(2,1:BeaconAmount),Sxy(3,1:BeaconAmount),'r*',Sxy(2,(BeaconAmount+1):NodeAmount),Sxy(3,(BeaconAmount+1):NodeAmount),'k.') xlim([0,BorderLength]); ylim([0,BorderLength]);

title('* 红色信标节点 . 黑色未知节点')

%~~~~~~~~~~~~~~~~~~~~~初始化节点间距离、跳数矩阵~~~~~~~~~~~~~~~~~~ for i=1:NodeAmount for j=1:NodeAmount

Dall(i,j)=((Sxy(2,i)-Sxy(2,j))^2+(Sxy(3,i)-Sxy(3,j))^2)^0.5;%所有节点间相互距离

if (Dall(i,j)<=R)&(Dall(i,j)>0) h(i,j)=1;%初始跳数矩阵 elseif i==j h(i,j)=0; else h(i,j)=inf; end end end

%~~~~~~~~~~~~~~~~~~最短路经算法计算节点间跳数~~~~~~~~~~~~~~~~~~~~ for k=1:NodeAmount for i=1:NodeAmount for j=1:NodeAmount

if h(i,k)+h(k,j)

48

附录1 DV-Hop算法仿真程序

h(i,j)=h(i,k)+h(k,j); end end end end h

%~~~~~~~~~~~~~~~~~~~~~求每个信标节点的校正值~~~~~~~~~~~~~~~~~~~~~ h1=h(1:BeaconAmount,1:BeaconAmount); D1=Dall(1:BeaconAmount,1:BeaconAmount); for i=1:BeaconAmount

dhop(i,1)=sum(D1(i,:))/sum(h1(i,:));%每个信标节点的平均每跳距离 end

D2=Dall(1:BeaconAmount,(BeaconAmount+1):NodeAmount);?aconAmount行UNAmount列 for i=1:BeaconAmount for j=1:UNAmount if min(D2(:,j))==D2(i,j)

Dhop(1,j)=D2(i,j);%未知节点从最近的信标获得校正值 end end end Dhop

%~~~~~~~~~~~~~~~~~~~~~~~~~用跳数估计距离~~~~~~~~~~~~~~~~~~~~~~~~~ hop1=h(1:BeaconAmount,(BeaconAmount+1):NodeAmount)%未知节点到信标跳数，BeaconAmount行UNAmount列 for i=1:UNAmount

hop=Dhop(1,i);%hop为从最近信标获得的校正值 Distance(:,i)=hop*hop1(:,i);%?acon行UN列； end

49

毕业设计（论文）杜撰

% %~~~~~~~~~~~~~~~~~~~~最小二乘法求未知点坐标~~~~~~~~~~~~~~~~~~~~ d=Distance; for i=1:2

for j=1:(BeaconAmount-1)

a(i,j)=Beacon(i,j)-Beacon(i,BeaconAmount); end end A=-2*(a'); % d=d1';

for m=1:UNAmount

for i=1:(BeaconAmount-1)

B(i,1)=d(i,m)^2-d(BeaconAmount,m)^2-Beacon(1,i)^2+Beacon(1,BeaconAmount)^2-Beacon(2,i)^2+Beacon(2,BeaconAmount)^2; end

X1=inv(A'*A)*A'*B; X(1,m)=X1(1,1); X(2,m)=X1(2,1); end UN X

for i=1:UNAmount

error(1,i)=(((X(1,i)-UN(1,i))^2+(X(2,i)-UN(2,i))^2)^0.5); end

figure;plot(error,'-o')

title('每个未知节点的误差') error=sum(error)/UNAmount Accuracy=error

50

第4章 DV-Hop算法改进和MATLAB仿真

话说，我们无法判断节点N的具体坐标。因此，称节点N为bad节点。

(iii)bad节点是节点群。如图4-3所示，节点M的坐标是已知的，假若此节点群经过节点M才能和网络进行通信，并且这个节点群中不存在已知节点，则该群能够在已知节点M的周围转动。换句话说，我们无法判断它们所在的具体位置。因此，称这个节点群中全部节点为bad节点。

M网络 图4-3 第3类bad节点的示意图

(2)待测节点与已知节点之间的每跳跳距，是用已知节点之间的平均每跳距离来表示的。每跳跳距的值不可能一样，所以使用该方法会使误差增大。

(3)在已知节点数量不太多的情况下，可以监测到的面积也相对很少。监测覆盖的面积越少，节点的定位覆盖率也就越低。待测节点要和已知节点取得联系，就一定要经过中间节点刁一可以取得联系。因为己知节点数量不多，所以要让它们之间可以通信，就会使得中间的跳数增多。随着中间跳数的增多，引发的距离误差也会相应地增大。

(4)在过程3的定位阶段，使用三边测量法进行估计待测节点的坐标。用这个方法求出的坐标，存在一定的误差，且定位精度不高。

4.2 DV-Hop算法的改进

4.2.1 DV-Hop算法的距离误差校正

在原始算法中，把已知节点间的平均每跳距离[30]HopDisef。看成是待测节点到已知节点的平均每跳距离。即待测节点到已知节点的距离等于平均每跳距离x跳数。但在真实的环境中，待测节点到已知节点的路程通常都是曲线，用原算法会产生较大误差。

步骤1，全部己知节点的坐标、跳数等内容，均以广播形式发送给其它己知节点。在任意一个己知节点获取了其它已知节点的数据后，就能够依据

21

燕山大学本科生毕业设计（论文）

2个已知节点的坐标，求解出它们之间的实际长度。计算出用RSSI测量的距离值与每跳距离和的均值，然后利用该均值与实际长度的差值，得到已知节点e、f的总长度误差校正值lenef。

假若己知节点e的平均每跳长度用HopDisef表示，已知节点e到f(e≠f）的总跳数是m，Disef已知节点e到己知节点哟每跳长度和，Disef己知节点e到已知节点动实际长度。总长度误差校正值：

lenef=??RSSI+disef??2-Disef （4-1）

路径损耗的分布模型：

PL?k?=PL?k0?+10qlog?k/k0?+Y0 （4-2）

RSSI=PL?k0?-10log?k? （4-3） 在公式（4-1）中，有以下成立：

Disef=HopDisef?m （4-4） Disef=?x-x?+?y-y?2efef2 （4-5）

在公式（4-2）中与公式（4-3）中，K0：接收点的参照长度（k0=1），k：接收方到发送方的长度。PL(k0)：k0点的接收功率。q：路径损耗系数，它的取值在（2,4）内。Y0：0均值的高斯分布随机变量。

步骤2，由于每个待测节点到已知节点的长度都不一样，所以它们的距离误差值也不一样。故应该使用不一样的误差校正值来参与运算。假若已知节点e到己知节点1的总跳数是m，那么，e到动平均每跳误差校正值avgeef是:

?avgeef=????RSSI+Disef?/2-Disef?/m （4-6）

网络内，所有已知节点把自身到其它已知节点的m、lenef、avgeef都广播出去。使得任意一个已知节点都能得到其它已知节点的m、lenef、avgeef等值。己知节点一旦获取到了其它已知节点的m、lenef、avgeef得值，就会把这些内容都保存在一个路由表{IDk，xk，yk，hopk}内。已知节点接着会给其它邻居节点传递这些信息，同时给跳数值加一。

在每个节点得到跳数之后，总是和{IDk，xk，yk，hopk，mm、lenef、avgeef}中的hopk旧值做对比。如果新的hopk值比旧的的hopk值小，则用 hopk的

22

第4章 DV-Hop算法改进和MATLAB仿真

新值来代替{IDk，xk，yk，hopk，mm、lenef、avgeef}中的旧值；否则抛弃掉此信息。在这个过程中，同时进行了总长度误差校正与平均每跳误差校正。通过以上步骤，表明求出了待测节点与已知节点的最小长度。

步骤3，通过前两个步骤的信息传递，使得待测节点拥有了离它最近的3个已知节点

或者大于3个已知节点的信息，该信息中包含总长度误差校正值lenef与平均每跳误差校正值avgeef。通过使用lenef值与avgeef值，待测节点即可得到其与所有已知节点的长度。

假若已知节点e与比间有一个待测节点w，M表示待测节点w与已知节点e之间的总跳数，待测节点w与已知节点e的每跳距离和用HopDise*M表示，avgeef成示已知节点e、润的平均每跳误差校正值。求出待测节点w与己知节点e的距离Dwe:

Dwe=HopDisef?M-avgeef?M=?HopDisef-avfeef??M

（4-7）

4.2.2 MIN-MAX方法与加权最小二乘法的结合

用三边测量法求解待测节点的坐标，会产生一些误差，同时产生的浮点运算量也相对高一些。MIN-MAX算法减少了浮点运算量，使它的计算代价变小。定位精度的高低主要取决已知节点数量的多少。增多了已知节点的数量，势必引起了成本的提高，同时也增大了功耗。因此，用MIN-MAX与加权最小二乘法的结合方法，来替换三边测量法。

该方法主要有两个过程:第一个过程，使用MIN-MAX算法，依据少许的已知节点坐标，来求解待测节点的粗略位置；第二个过程，使用加权最小二乘法进一步准确地估计待测节点的坐标。

(l)MIN-MAX算法

MIN-MAX算法用已知节点做圆心，把待测节点到此已知节点的长度估算值看作半径，并创建此圆的外接正方形。用这些估算值、坐标创建一些正方形，找出正方形的交集，其几何中心就是待测节点的估算位置。

在平面坐标系中，若节点的通讯模型是圆，半径是ks。估计节点的坐标时，把圆的外接正方形看成是它的通讯范围，它在一跳内的最大通讯长度是

23

燕山大学本科生毕业设计（论文）

t=2ks(正方形的边长是2ks)。如果未知节点的邻居已知节点数是v，则它的坐标一定在这些已知节点通讯范围的交集中，如图4-4所示。

Max3Max2Anchor2Anchor3Max1(x,y)Min2Min3Anchor1Min1

图4-4 MIN-MAX算法示意图

已知节点(xs，ys)的范围由[(xs-ks)，(ys-ks)]*[(xs+ks)，(ys+ks)]得到。其中，ks指待测节点到己知节点的估算长度。交集范围可由公式(4-8)求解出:

??max?xs-ks?,max?ys-ks??????max?xs+ks?,max?ys+ks???,s=1,2,...v （4-8）

?s0,y?s0?是此交叉范围的几何中心，待测节点的估算位置?x见公式（4-9）：

1?s0,y?s0?=?min?xs+ks?-max?xs-ks?,min?ys+ks?-max?ys-ks???x??（4-9） 2 (2)加权最小二乘法

有G个待测节点到已知节点的长度估算值，用此值构造的残差方程是ts(x)。在无距离估算值的前提下，使用公式(4-10)，来求解待测节点的估算坐标值。

?=argmin?ts2?x? （4-10） xs=1G假若知道了所有的距离估算值，则凭借这些值构造加权系数ws。因此，加权最小二乘的估算值是:

?=argmin?wsts2?x? （4-11） xs=1G 24

第4章 DV-Hop算法改进和MATLAB仿真

若待测节点的位置是(x，y)，已知节点的位置是(xs，ys)，度量的长度是ks，则残差方程的表达式如下:

ts?x,y?=ks-?xs-x?+?ys-y?22 （4-12）

ts(x，y)是非线性函数，求解ts(x，y)的值，实际用非线性最优化来处理。线性化求解ts(x，y)的表达式，具体如下:

k222s=?xs-x?+?ys-y?

k221=?x1-x?+?y21-y?

式（4-13）减去式（4-14）之后，有以下方程组：

k2s-d21=x22s-x1+2x1x-2xsx+y2s-y21+2y1y-2ysy 最终整理为：

k2s-k221=xs-x21+y22s-y1-2?xs-x1?x-2?ys-y1?y 设有以下方程组成立：

??p=2?x-x??qs1=2?y-y ???r=x2-x2+y2s1s-y21-d2s+d2s11线性处理后，最小二乘的结果如下：

?GGGG??pr2s1s1?qs1-?qs1rs1?ps1qs1??x?=s=1s=1s=1s=1GG2?p22?G???s1?qs1-??ps1qs1?s=1s=1?s=1?? ?GG2GG??qs1rs1?ps1-?ps1rs1?ps1qs1?y?=s=1s=1s=1s=1?GG???p2q2?G?2s1s=1?s1-s=1???ps1qs1s=1??用矩阵可表示成：

x?=?ATA??1ATb 加权最小二乘法（WLS）的估算坐标是：

X???ATWA??1ATWb 在公式（4-20）中，

25

（4-13） （4-14）

（4-15）

（4-16）

（4-17） （4-18） （4-19） （4-20）

燕山大学本科生毕业设计（论文）

2?yG-y1???2?xG-x1?x????=??,A=?x?? （4-21） y????2?xG-xG?1?2?yG-yG?1???222?x12-xG?y12-yG?kG-k12???b=?? （4-22）

222222??xG-x?y-y?k-k?1GG?1GGG?1???w10?? （4-23） W??????0wG???为最小方差无偏估计。只有W是对称正定矩阵，才能确定x在W?M?1?的均方误差达到最低，其中M表示长度误差的方差矩的情况下，估算值x阵。

在此阶段，设已知节点的权值是1，待测节点的权值在0.1的基础上逐渐增加，它的取值范围是[0，l]。步长是0.05，循环求精时，待测节点的权值依次增加0.05。

(3)定位过程

过程1，该过程进行粗略估算位置。利用MIN-MAX算法，未知节点凭借邻居已知节点的位置与通讯模型，根据公式 (4-10)，能够求解出它所处的范围。进一步使用公式(4-11)，可以估计出未知节点的粗略坐标，同时引入了加权系数。若公式 (4-10)求解得到的区域越小，则用公式 (4-11)估计的未知节点坐标就越准确，且权值同时也在增大。

过程2，该过程是定位求精。节点利用加权最小二乘法来改变它的坐标等数据。在执行完过程1之后，其它未知节点都拥有了初始坐标。再使用加权最小二乘法进行循环求精，每改变一次未知节点的坐标，就需要把周边节点的加权系数增大一次，权值在0.1的基础上，每循环一次其就增加0.05。

随着循环次数的不断增多，未知节点的权值也在不断增大，该值慢慢地朝己知节点的权值1接近。未知节点的权值一旦大于1，或者连续2次得到的坐标极其接近，则终止该循环步骤。在全部未知节点都执行了此过程时，即全部未知节点都己定位，本算法终止。

26

第4章 DV-Hop算法改进和MATLAB仿真

4.2.3 改进算法的流程图

在定位的过程中，己知节点与未知节点的执行步骤不一样。因此，它们的程序流程图也不一样。已知节点的程序流程图如图(4-5)所示，未知节点的程序流程图如图(4-6)所示。

初始化广播已知节点的坐标和跳数信息获取和传递其他已知节点信息YN是否第一次收到已知节点的数据包Y邻居节点接收数据包计算出用RSSI测量的距离值与每跳距离和的均值，利用该均值与实际距离的差值，得到总距离误差校正值平均每跳误差校正值=总距离误差校正值/已知节点间的跳数判断是否小于现有的跳数N更新已知节点跳数丢弃数据包跳数+1向其他邻居节点转发已知节点信息广播总距离误差校正值与平均每跳误差校正值已知节点个数是否等于或大于3Y求出未知节点到已知节点的距离结束N 图4-5 改进算法的已知节点程序流程图

27

燕山大学本科生毕业设计（论文）

初始化接收和转发已知节点信息Y已知节点数是否=或>3N获取和传递其他已知节点信息是否首次获得某个已知节点信息YN是否小于已有的跳数YN丢弃数据包跳数+1更新已知节点跳数转发数据包得到总距离误差校正值与平均每跳误差校正值Y是否首次获得平均每跳距离校正值N获取平均每跳距离校正值丢弃此数据包未知节点到已知节点的距离=（平均每跳距离-平均每跳误差校正值）*总跳数利用MIN-MAX方法与加权最小二乘法的混合方法来计算未知节点的坐标结束 图4-6 改进算法的未知节点程序流程图

28

第4章 DV-Hop算法改进和MATLAB仿真

4.3 DV-Hop算法流程图

该算法由三阶段组成。具体实现见第3章的DV-Hop算法部分。 在DV-hop算法中，使用到两种重要的路由协议[9]：洪泛协议和距离矢量路由协议。

（1）洪泛协议，是最简单的路由协议，此协议中没有任何路由算法。节点向它的所有邻居节点广播所收到的数据，直到数据到达目的节点或达到数据报的最大跳数。洪泛协议的缺点是容易引起信息重叠，造成网络拥塞。

（2）距离矢量路由协议，是简单路径的分布式路由算法。每个节点维护一张到网络中已知位置节点的距离估计和下一跳的路由表。每个节点只记录到目的节点的跳数和通向目的节点的下一跳。节点接收到数据后，根据数据包头部的目的地址来查找路由表，并将其转发到下一跳所指定的节点。

DV-Hop算法由3个阶段组成总体流程图如下：

网络初始化Y节点剩余能量N调用DV-Hop保存多次测量结果进行由大到小排序延时最小值是否为0叠加返回

图4-7 网络总体流程图

29

燕山大学本科生毕业设计（论文）

网络初始化接收信息获取锚节点获得节点跳数信息计算每个锚节点间的每跳平均信息定位自身结束Y是否锚节点N 图4-8 网络流程图

初始化定时广播锚节点信息接收和转发其他锚节点信息是否第一次接收锚节点信息Y将接收到的信息存入锚节点信息表N判断跳数是否小于已存跳数Y更新锚节点信息表中的跳数N丢弃该数据包N锚节点信息表中的锚节点是否大于2Y计算平均每跳距离并广播 图4-9 锚节点模块流程图

30

第4章 DV-Hop算法改进和MATLAB仿真

4.4 MATLAB仿真环境简介

MATLAB[30]产品家族是美国Math Works公司开发的用于概念设计、算法开发、建模仿真和实时实现的理想的集成环境。由于其完整的专业体系和先进的设计开发思路，使得MATLAB在多种领域都有广阔的应用空间。特别是在MATLAB的主要应用方向：科学计算、建模仿真以及信息工程系统的设计开发上。并且在这些方向上MATLAB已经成为行业内的首选设计工具。

在MATLAB产品家族中，MATLAB工具箱是整个体系的基座，它是一个语言编程型（M语言）开发平台，提供了体系中其他工具所需要的集成环境（比如M语言的解释器）。同时由于MATLAB对矩阵和线性代数的支持使得工具箱本身也具有强大的数学计算能力。MATLA产品体系的演化历程中最重要的一个体系变更是引入了Simulink，用来对动态系统建模仿真。其框图化的设计方式和良好的交互性，对工程人员本身计算机操作与编程的熟练程度的要求降到了最低，工程人员可以把更多的精力放到理论和技术的创新上去。

4.5 DV-Hop算法仿真结果分析

根据无线传感器网络所关注的重点，我们对需要进行节点定位的无线传感器网络作如下设定：

（1）无线传感器网络节点部署在二维的平面区域上，这样未知节自身定位时仅需三个锚节点的位置和距离信息；如果是在三维空间条件下进行自身定位，则需要四个锚节点的位置和距离信息。

（2）传感器节点采用自由空间电波传播模型，即节点的通信范围一个圆。

（3）传感器节点能够发现其邻居节点，邻居节点间可以自由通信。 （4）传感器节点间具有对称的通信能力，通信半径一致，并且所有的消息最终都可被正确接收。

（5）只有一些传感器节点通过配备GPS接收器或人工部署已经现定位，成为锚节点，其余其它节点则均具有相同的处理能力。

31

燕山大学本科生毕业设计（论文）

（6）节点拥有两种不同的标记：anchor、single，分别用来表示锚节点和无法定位的节点。

参数设置如下：

BorderLength正方形区域的边长，单位：m NodeAmount网络节点的个数 BeaconAmount信标节点数

Sxy用于存储节点的序号，横坐标，纵坐标的矩阵 Beacon信标节点坐标矩阵，BeaconAmount*BeaconAmount UN未知节点坐标矩阵，2*UNAmount

Distance未知节点到信标节点距离矩阵，2*BeaconAmount h节点间初始跳数矩阵

X节点估计坐标初始矩阵，X=[x，y] R节点的通信距离，一般为10-100

在对定位算法进行仿真之前，首先对算法基于的网络结构和通信模型及有关参数进行定义。

网络结构：

假设一个二维无线传感器网络中有N个传感器节点，它们均匀的随机分布于一块L?L的正方形区域内，无障碍或干扰，其中有一小部分节点坐标已知（GPS定位或人工部署），称为锚节点（Beacon Node）。

通信模型：假设节点的通信模型是以自身为中心的圆，通信半径用 R 表示；锚节点与未知节点的通信能力相同，通信半径均为 R；节点间具有对称的通信能力，发送和接收能力相同。

用MATLAB 仿真软件对无线传感器网络中传感器节点的定位算法进行仿真：

（1）产生节点均匀随机分布的网络拓扑，用符合均匀分布的随机数生成每个节点的坐标(x,y)。

（2）实现节点间跳数计数。未仿真信息发布的过程；未考虑节点间通信的时间及通信冲突问题，假设未知节点和信标节点之间一定可以成功通信。将节点间距离分级得到节点间跳数并使得未知节点从距它最近的信标节

32

第4章 DV-Hop算法改进和MATLAB仿真

点获得校正值（平均每条距离）。利用此得到以跳数估计的距离。

（3） 实现了用最小二乘法解非线性方程求得未知节点的位置。 （4） 改变各网络参数，如节点总数、通信半径、信标节点密度等观察和分析定位算法精度。

用未知节点实际估测的位置和节点位置的真实值之间的距离值表示每个节点的定位误差。算法的平均误差定义为：

error??((xi?1ncal?xreal)2?(ycal?yreal)2)n

取基本方案（方案1）如下： BorderLength=100； NodeAmount=200； BeaconAmount=20；

UNAmount=NodeAmount-BeaconAmount； R=60；

此时error =38.9140 ，Accuracy（定位精度） =0.6486 仿真结果如图4-10，图4-11：

方案 1 2 3 4 5 6 Border Length 100 200 100 100 100 50 表格 定位方案

Node Beacon Amount Amount 200 20 200 20 100 20 200 10 200 20 100 10 R 60 60 60 60 40 40 Error 34.9382 57.6661 34.3157 33.3250 30.9272 16.8312 Accuracy 0.5823 0.9611 0.5719 0.5554 0.7732 0.4208 方案2仿真结果如图4-12和4-13； 方案3仿真结果如图4-14和4-15； 方案4仿真结果如图4-16和4-17； 方案5仿真结果如图4-18和4-19； 方案6仿真结果如图4-20和4-21；

通过修改基本方案1的参数，每次只改变一个，从而得到对比性很强的

33

燕山大学本科生毕业设计（论文）

方案2到方案5。

对比以上的结果，通过研究可以得到如下关系：error和BorderLength成正比关系；和NodeAmount成反比关系；和BeaconAmount成反比关系；和R成正比关系。Accuracy和BorderLength成正比关系；和NodeAmount成反比关系；和BeaconAmount成反比关系；和R成反比关系。

由以上对比结果我们设定一个最佳方案，即方案6。 方案6参数如下： BorderLength=50； NodeAmount=100； BeaconAmount=10；

UNAmount=NodeAmount-BeaconAmount； R=40；

此时error =16.8312 ，Accuracy =0.4208 仿真结果如图4-20，图4-21。 和方案1对比error 和Accuracy 都有明显的减小。

* 红色信标节点 . 黑色未知节点10090807060504030201000102030405060708090100

图4-10 方案1网络节点分布图

34

第4章 DV-Hop算法改进和MATLAB仿真

每个未知节点的误差6050403020100020406080100120140160180

图4-11 方案1每个未知节点的误差

* 红色信标节点 . 黑色未知节点200180160140120100806040200020406080100120140160180200

图4-12 方案2网络节点分布图

35

结论

结论

本论文的主要工作就是：利用传感器网络中较少已知节点的位置信息来求取大量未知节点的位置信息。针对对课题的理解我主要做了以下三方面的工作：

（1）指出无线传感器网络自身定位系统和算法的性能评价的几个常用的标准，对WSN自身定位系统和算法的分类进行了描述，依据传感器网络本身的特点指出了WSN定位系统设计面临的挑战。

（2）介绍了无线传感器网络中当前主要采用的几种定位技术和各自的特点，对现有的定位技术进行了分类和比较。在比较Range-free和Range-based算法优劣性基础上，将其中的Range-free定位算法作为本文研究的主要内容，并对其中的DV-Hop算法进行了分析。

（3）深入研究Range-free的WSN节点自定位算法中的DV-Hop算法，针对该定位机制的基本原理和实现方法，对该定位算法用Matlab进行了仿真。考虑不同的因素对仿真结果进行了比较。

通过以上的工作，对比仿真所得到的结果，对比研究可以得到如下关系：Error和BorderLength成正比关系；和NodeAmount成反比关系；和BeaconAmount成反比关系；和R成正比关系。Accuracy和BorderLength成正比关系；和NodeAmount成反比关系；和BeaconAmount成反比关系；和R成反比关系。

由以上对比结果我们设定一个最佳方案，即方案6。 方案6参数如下： BorderLength=50； NodeAmount=100； BeaconAmount=10；

UNAmount=NodeAmount-BeaconAmount； R=40；

此时error =16.8312 ，Accuracy =0.4208 仿真结果如图4-20，图4-21。 和方案1对比error 和Accuracy 都有明显的减小。

41

燕山大学本科生毕业设计（论文）

参考文献

1 宋文，无线传感器网络技术与应用，电子工业出版社，2007

2 罗立辉，张耀南，无线传感器网络在冰川环境监测中的应用 Journal of Glaciology and Geocryology l00020240(2008)0621018206 Dec.2008 3 李善仓，张克旺，无线传感器网络原理与应用，机械工业出版社，2008.1 4 任丰原，黄海宁，林闯.无线传感器网络[J].软件学报.2003 14(8).1281-1291.

5 史龙.无线传感器网络自身定位算法研究[D].西北工业大学.2005. 6 陈茜.移动自组织网络中的定位技术研究[D].国防科学技术大学硕士学位 论文.2004

7 刘伟莉，基于直方图分布估计算法的无线传感器网络定位技术.中山大学 硕士学位论文.2010.5

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

9 肖玲，基于多维标度的无线传感器定位算法研究与实现[D]，湖南大学硕 士学位论文 2006

10 孙利民，李建中，陈渝等.无线传感器网络(第1版)[M].北京:清华大学 出版社，2005

11 李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展 [J].软件学报，2003，13(10):17-17

12 于海斌，曾鹏，王中锋等.分布式无线传感器网络通信协议研究[J].通信 学报，2004，25(10):102-110

13 马祖长，孙怡宁.无线传感器网络节点的定位算法[J].计算机工程，2004， 30(7):13-03

14 刘运杰，金明录，崔承毅.基于RSSI的无线传感器网络修正加权质心定 位算法[J].传感技术学报.2010，23(5):0717-05

15 汪场，黄刘生等.一种基于RSSI校验的无线传感器网络节点定位算法小 型微型计算机系统.2009，30(l):59-04

42

参考文献

16 王建刚，王福豹，段渭军.加权最小二乘估计在无线传感器网络定位中的 应用[J].计算机应用研究，2006，36(9):41-03

17 陈鹏，钱徽，朱森良.基于加权最小二乘的卡尔曼滤波算法[J1.计算机科 学，2009，36(11):230-03

18 K-F.Simon Wong，W·Tsang， Victor Cheung，S-H.Gary Chan，James T.Kwok.Position Estimation for Wireless Sensor Networks.IEEE Globecom 2005.5:2772-2776

19 Yi Shang，Wheeler Ruml.Improved MDS-Based Localization.IEEE INFOCOM 2004.0-7803-8356-7

20 Chris Savarese，Jan Rabaey.Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks.Faculty of Information Technology and Systems Delft University of Technology.

21 Andreas Savvides，Heemin Park and Mani B.Srivastava.The Bits and Flops of the N-hoP Multilateration Primitive for Node Localization Problems.WSNA， September 28，2002，Atlanta，Georgia，USA.ACM 1-58113-589-0/02/0009 22 R.Nagpal，H.E.Shrobe and J.Bachraeh，Organizing a Global Coordinate System From Local Information on an Ad Hoc Sensor Network，Lecture notes in computer science，ISSN 0302-9743

23 X.-L.Luo and Z.-J.Wu:Least-square approximations in geometric buildup for solving distance geometry problems，Journal of Optimization Theory and Applications(SCI)，2010.

24 R.-Z.Li，X.-L.Luo and J.-R.Lin:Weighted centroid correction localization in cellular systems，American Journal of Engineering and Applied Sciences， 2010.

25 Savarese C,Rabaey J，Beutel J.Location in Distributed Ad Hoc Wireless Sensor Networks[C].In Proceeding of ICASSP.May 2001.2037-2040. 26 Priyantha N，Balakrishnan H，Demaine E，et al.Anchor Free Distributed localization in Sensor Networks[R].Technical Report TR-892，MIT LCS.APril 2003.

43

燕山大学本科生毕业设计（论文）

27 Wang Shu，Liu Kezhong，Hu FuPing，et al.A Distributed Sensor Network Localization Scheme Motivated by Graph Rigidity Theory[J].The Mediterranean Journal of Measurement and Control.2005，1(4).155-190. 28 De Oliveira H A B F， Nakamure E F，Loureiro A A F，et al.Directed Estimation:a Recursive Localization Approach for Wireless Sensor

Networks[C].In Proceeding of the 14th International Conference on Computer Communication and Networks.October，2005.557-562.

29 Bulusu N，Heidemann J， Estrin D.GPS-less low-cost outdoor localization for very small devices[J].personal Communication，IEEE.2000，7(5).28-34. 30 Ss K-F，Ou C-H，Jiau H C.Localization with Mobile Anchor Points in Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology.May 2005，54(3).1187-1197.

31 Miodrag Potkonjak，JessieaFeng，Lewis Girod.Location discovery using data drive Statistical error modeling[J].IEEE IN FOCOM，2006，26(8):43-47 32 HDemaine，Teller S，Priyantha，N.B.Balakrishnan.Mobile assisted localization in Wireless sensor networks[J] Inproc.of IEEE In foeom 05 2005，65(3):323-329

33 Borgl,Groener P.Modern multidimensional scaling theory and applications.New York:Springer-Verlag，1997，10-35.

34 Hopper A，Steggles P，Ward A.The Anatomy of a Context-Aware Application[C].Proc.of 5th Annual.Mobile Computing and Networking (Mobicom99).1999.59-68.

35 Welch G Bishop G Vicci L.The HiBall Tracker:high-Performance wide-area tracking for virtual and augmented environments[J].Proceedings of the ACM symposium on Virtual reality software and technology.1999.1-10 36 Hightower J.An indoor 3D location sensing technology based on RF signal strength[D].University of Washington，Department of Computer Science and Engineering.200O.

37 Tian H，Chengdu H，Brian M.B.Range-free localization schemes for large

44

参考文献

scale sensor networks[C].Proceedings of the 9th annual international conference on Mobile eomputing and networking， San Diego，CA， USA.2O03.81-95.

38 Orr R.J，Abowd G.D.A Mechanism for Natural User Identification and Traekong[C].Proc.2OOO Conf.Human Factors in Computing System.2000.275-276.

39 Priyantha N.B，Chakraborty A，Balakrishnan H.The Crieket location-support system[C].Proceedings of the 6th annual international conference on Mobile computing and networking.2000.32-43

40 Shang Y，Ruml W，Zhang Y.Localization from mere

connectivity[C].Proceedings of the 4th ACM international symposium on Mobile ad-hoc networking&computing.2003.201-212.

41 Capkun S，Hamdi M，Hubaux J.P.GPS-free Positioning in Mobile Ad-Hoc Networks[J].Cluster Computing.2002，5(2).157-167.

42 Doherty L，Pister K.S.J，EI Ghaoui L.Convex Position estimation in wireless sensor networks[C].INFOCOM 200l.Twentieth Annual Joint Conference of the IEEE Computer and communication Societies.Proceedings，IEEE， Anchorage，AK，USA.2001.1655-1663.

45

本文来源：https://www.bwwdw.com/article/4trv.html