计算机网络原理论文模板

无线传感器网络的定位算法综述

林海燕

（三明学院 数学与计算机科学系 07数媒）

摘要：作为一种全新的信息处理和获取技术,无线传感器网络广泛的在应用领域内实现复杂的追踪

任务和大规模监测,介绍了无线传感器网络算法的性能评价标准和自身定位系统及分类方法, 着重讲述了近年来该领域具有代表性的算法及系统的特点和原理,并指出未来研究的方向.

关键词：无线传感器网络;节点定位;定位算法; 仿真系统. 引 言

随着微机无线通信、数字电子技术和电系统(MEMS)的发展,无线传感器网络(WSN)在目标追踪、军事应用、环境监测、医疗保健、空间探索等领域都广泛得到应用传感器应用网络,节点定位

[ 3 ]

[ 1,2 ]

。节点位置信息的基础是无线

技术在具有无线传感器网络中重要的地位。

在应用中,明确传感器节点自身位置才能详细说明“在什么区域或位置发生了什么特定的事件”,不知道传感器位置所感知的数据是没有多大的意义。对外部目标的追踪和定位。可以提高路由效率从了解传感器节点位置信息可知,提供命名空间的网络,报告网络的覆盖,实现网络拓扑的自配置及网络的负载均衡以.

现有的定位方法大多数都包含两个基本过程: ②计算定位;①节点间的角度(或距离)测量。

1 节点定位计算方法

把未知节点即需要定位的节点;通过已知位置即锚节点，邻居节点即是可直接通信的节点，必须是一个节点通信半径内。

在获得自身未知节点到3个或3个以上锚节点的(角度或距离)后可以采用三边测量法、三角测量法、最小最大法计算自身的位置或极大似然估计法。

1.1基本概念

定位节点算法的目的，让所有邻居节点之间的测量距离值，计算未知节点的位置，使其能与相一

1

计算机网络 ——论文名称

致的测距结果。无线传感器网络定位节点技术的中涉定义及到的定位一些基本概念如： （1）邻居节点（neighbor node）

在一传感器节点通信半径内，可以直接进行通信的节点构成的集合就称为该节点的邻居节点。 （2）锚节点（anchor node）

无线传感器网络中，已知相对全网坐标系位置信息，为其它节点提供位置参考，协助其它节点定位的节点则称为锚节点。

（3）未知节点（unknown node）

未知节点通过锚节点的点定位算法及节位置信息来确定自身位置。在网络中，除比例很少或者没有的锚节点，而其它节点都为未知节点。 （4）节点连接度（node degree）

节点可以通信发现的邻居节点数目称为节点连接度。 （5）网络密度（network density）

包括所有节点的邻居节点平均的数目称为网络密度，通常记为μ(R)。若N个节点分布在面积为A的区域，节点通信半径为R，则可求网络密度为式（2-1）

(R)NRA2 式（2-1）

（6）跳段距离（hop distance）

两个节点间隔的各跳段距离之和，则称为两个节点之间的跳段距离。 （7）跳数（hop count）

两个节点之间间隔的跳段的总数，则称为两个节点之间的跳数。 1. 2 三角测量法

[4]

三角测量定位方法也称为方位测量定位法或信号到达角度(AOA)定位法,如图1所示。

假设未知节坐标为( x0 , y0 )的点A ,锚节点测得分别B、C ( x1 , y1 ) , ( x2 , y2 )分别为其坐标θ1 和θ2分别为信号发出到达的 角度,则有:

tan(i)x0xiy0yi（i=1,2） （1）

上述非线性方程求解得,可( x0 , y0 )未知节点的得到位置。

2

计算机网络 ——论文名称

1. 3 三边测量法

三边测量法是在基于测距的定位算法中坐标计算的基本途径。如图2所示, 三边测量定位法的基本原理就是求3个已知半径和坐标圆心的圆的交点。

假设已知点A、B、C的坐标的3个锚节,距离分别为d1 , d2，d3的未知节点D,由二维空间计算距离公式,可以解方程组就未知节点D可得到坐标。

1. 4 极大似然估计法

极大似然估计法定位的原理如图3所示。已知坐标分别为 ( x1 , y1 ) , ( x2 , y2 ) ,( x3 , y3 ) , „,

( xn , yn )的n个锚节点 ,距离分别为d1 , d2 , d3 ,„, dn 到未知节点D,假设( x, y)是D坐标,则:

222（x1x）(y1y)d1 （2） 222(xx)(yy)dnnn第1个方程可以分别减去最后一个方程, 就可以求解

22222x1xn2(x1xn)yn1yn2(y1yn)yd1dn (3) 222222xx2(xx)yy2(yy)yddnn1nn1nn1nn1nn1 用 式(3)线性方程组表示，其中:

(x1xn)(y1yn)xA2;X;

y(xx)(yy)nn1nn1x12xn2y12yn2dn2d12b

222222xn1xnyn1yndndn1由此求出未知节点的解的非线性最小二乘估计节点及极大似然估计D的位置:

T1TX(AA)Ab

3

计算机网络 ——论文名称

缺点在于此方法的要进行浮点的较多运算,所以计算带来的能量开销是不容忽视。

2 无线传感器节点定位基于测距技术的定位和无需测距技术的定位分类

定位过程可根据是否测量节点间的实际距离,算法定位可分为:无需测距技术的定位和基于测距技术的定位两类。

定位机制需要测量相邻节点间的绝对方位或者距离,并节点间的利用来计算未知节点的实际距离位置。使用减小测距误差对定位的各种算法来影响,包括循环定位求精、多次测量等,但是不可避免的产生大量通信和计算开销,所以并不适用于低成本、低功耗的应用领域。

无需测量定位技术节点间的绝对方位或距离,而估计距离是用来进行节点间的计算节点位置。MDS2MAP[5]、凸规划和DV2Hop[6]等都是典型的Range2Free[7]算法定位。因成本和功耗等因素,再者定位能够满足大多数应用。

3 无线传感器网络自身定位系统和算法的性能评价

节点定位算法的性直接影响无线传感器网络的可用性，因此，需要有评价标准来反映各算法的优劣。本文对无线传感器网络节点定位算法评价标准做出简要的介绍。

（1）节点密度

通常节点密度用无线传感器网络平均连通度来进行表示。 （2）锚节点密度

锚节点密度是对无线传感器网络节点定位算法性能评价的重要指标之一。通常锚节点由人工部署，且由相对的定位系统定位。

（3）定位误差

节点定位算法首要要评价的指标是定位误差，一般用相对值或绝对值来表示[8]。为了简单且相对公平的评价性能标准，通常把式(2-27)作为算法的定位精度。由此可看，定位误差越小，定位算法的精度越高。

nPPi1in,i1,2,,n 式(2-27)

（4）定位规模

在给定数量的基础设施内或在一段时间内，可以定位多少未知节点是其中一个重要的评价性能指标。不同的定位算法在不同的区域内实现，如，RADAR系统只可以在建筑物的一层内实现定位，Active Office定位系统（剑桥）[9]每200ms定位一个节点。

（5）自适应性和容错性

4

计算机网络 ——论文名称

现实环境中，无线传感器网络定位节点常遇到的问题包括：网络部署环境中严重地存在多径传播、通信盲点、非视距(NLOS)、衰减等问题。

（6）代价

节点定位算法的代价可从资金、空间和时间代价来评价。资金代价则包括实现某一种节点定位算法的节点设备、基础设施的总费用。空间代价包括节点定位算法所需的和网络节点的数量基础设施、硬件尺寸等。时间代价包括系统的定位所需时间、配置时间、安装时间等

（6）功耗

功耗是节点定位算法实现和设计过程中影响比较大的指标之一。电池能量有限，所以在保证定位精度的前提下，要与功耗相关的定位所有的时间复杂性、通信开销、存储开销、计算量是一组关键的指标

[11]

[10]

。

。

上述无线传感器网络的7种性能评价指标评价不仅是其定位算法的标准，同时也是其实现和设计的优化目标。

5

计算机网络 ——论文名称

小 结

整体上看来,一些循环求精算法近年来被提出,WSN的特点更加充分发挥处理,单个节点利用节点间的协同工作实现无法完成的任务.很多的这些算法不仅提高了精度,自由度还给予用户更大的提高,一个新的类别正逐渐形成.

深入研究了关键内容之一的网络管理。研究和查阅与无线传感器网络定位技术相关的资料文献，对无线传感器网络中已有的定位算法，对无线传感器网络的性能评价、体系结构、网络特点以及无线传感器网络定位的性能评价标准和分类方法进行了研究分析，并深入分析定位技术的基本原理和测距技术，并对典型的定位算法原理进行了分析。尤其是距离无关的定位算法进行分类总结，并通过相应的标准对算法的性能进行评价，对其优点及不足之处进行比较分析。

仿真显示,许多系统的定位精度和算法都还有很大的空间提高.总之,定位无线传感器网络的问题研究作为WSN的一个技术难点,也成为关键点之一.

参考文献：

[1]STEERED C,BAPTISTA A. Research challenges in envi2ronmental observation and forecast- ting systems[C ]2000:292-299.

[2]PETRIUEM, GEO GANASN D, PETRIUDC.IEEE In strumentation and Measurement Magazine.2000, 26(10):31-35.

[3]王福豹,史龙,任丰原. 无线传感器网络中的自身定位系统和算法[ J ].软件学报,2005,16(5): 857-8687.

[4]HET,HUANGCD,BLUMBM.Range2free localization schemes in large scale sensor networks [C].USA:ACMPress,2003,81-95.

NICULESCUD,NATHB. Adhoc positioning system(APS) using AoA[C]. IEEE,2003: 1734-1743. [5]HIGHTOWERJ,BORIELLOG. Location systems for ubiquitous computing[ J]. Computer, 2001, 34(8):57-66.

[6]NICULESCUD, NATHB. Localized positioning in ad hocnetworks[C]. IEEE Communications Societies,2003,42-50.

[7]HIGHTOWER,JBORIELLO G, WANT R. AnIndoor 3D Location Sensing TechnologyBased on RF Signal Strength[R].2002,452-463.

[8]孙庭波.无线传感器网络定位算法研究[D].中国科学技术大学博士论文,2008.4.

[9]Harter A,Jones A,Hooper A.A new location technique for the active office.IEEE Personal Communications,1997.

[10]宋琛.移动无线传感器网络蒙特卡罗定位算法研究[D].湖大大学硕士论文,2008,4.

6