无线传感器网络分布式定位算法研究与仿真_图文

1、无线传感器网络分布式定位算法研究与仿真姜伟,赵方北京邮电大学软件学院,北京(100876E-mail:Jiangwei1231摘要:无线传感器网络是一种全新的信息获取和处理技术,能够实时监测、感知和采集各种环境或监测对象的信息。传感器多节点协调的自身定位是各种应用的基础,论文深入分析比较了在无线传感器网络领域中有代表性的三种分布式定位算法(Bounding box,Euclidean 和Robust position,并在OMNET+平台上作了性能的仿真检验;分别从理论和实际仿真结果上,对各定位算法的性能作了定量分析,并对各算法的应用环境给出了建议;对Robust position算法的改进提

2、出了建议,并对无线传感器网络定位算法的未来研究作了展望。关键词:无线传感器网络;自身定位;定位;仿真1. 引言1近些年来,微电子技术、计算技术和无线通信技术的进步,推动了低功耗多功能传感器的快速发展,使其在微小的体积内能够集成信息采集、数据处理和无线通信等多种功能。由于传感器节点在部署时的不可控制性(例如通过飞机撒放,网络中大多数节点位置不能事先确定,而无线传感器网络的大量应用都需要网络中节点的地理位置信息,从而获知信息来源的准确位置。此外,节点的位置信息还可以辅助实现数据路由。人工部署和为所有网络节点安装GPS 接收器都会受到成本、功耗、扩展性等问题的限制,甚至在某些场合可能根本无法实现,因

3、此必须采用一定的机制与算法实现WSN的自身定位。由于传感器网络对能耗十分敏感,所以不宜将大量的通信和计算固定于某个或者某些节点,否则,这些节点的电能会很快耗尽,出现网络的“空穴”。要求要尽量采用分布式的节点定位算法,尽量延长传感器网络的生命期。对定位算法性能的评价标准主要有:定位精度、规模、锚节点密度、节点密度、容错性和自适应性、功耗、代价等。1本课题得到国家高技术研究发展计划(863资助(No. 2007AA12Z321。论文对定位算法仿真的意义在于能够在尽量接近现实的环境中得出算法性能的数据,进行定量分析,从而得出算法的应用环境和不足之处,以待改进。论文要通过研究无线传感器网络中典型的分布

4、式定位算法,选择Bounding box, Euclidean和Robust Position三种算法进行实现,并在OMNET+平台上对他们进行仿真比较,研究环境参数(测距误差,锚节点密度,连通度变化对他们性能的影响。论文最后给出这些算法性能的评估和应用环境的建议,并对算法改进提出建议。2. 分布式定位算法总结分布式定位算法,大都分为三个模块:确定未知节点和锚节点间距离模块;计算每个未知节点位置模块;循环精确节点位置模块。首先,未知节点通过基于测距或非测距方法确定其到锚节点的距离;然后,通过到锚节点的距离来计算每个未知节点的位置;最后,对未知节点的位置进行迭代求精,最终所有未知节点报告它们的位

5、置。分布式定位算法的每个模块中都有几种可选算法。其中确定未知节点和锚节点间的距离模块中可选算法有基于RSSI的测距算法,美国路特葛斯大学(Rutgers University的Dragos Niculescu1等人提出的Euclidean,DV-Hop,DV-distance三种算法;计算未知节点位置模块中可选算法有三边测量法,多边形算法法,Min-Max 算法;位置求精模块主要有由Savarese 2等提出的根据所有可获得的节点信息重复执行三边测量或多边形算法过程重新确定节点位置。2.1 确定未知节点到锚节点距离模块可选算法在这个模块中,未知节点通过共享信息确定其到锚节点的距离,以便在第二个

6、模块中可以计算节点的初始位置。 2.1.1 RSSI 算法4此算法已知节点发射功率,在接收节点测量接收功率,计算传播损耗,然后使用理论或经验的信号传播模型将传播损耗转化为距离。所用公式如下:X d d (log 10d (PL P d (P 0100T +=的随机变量期望为方差为是一个服从正态分布的是一个信号衰减指数时信号强度的损耗是在两节点距离为是信号发射的强度时的信号强度为两节点相距为其中0X d d (PL P d d (P 200T 根据如上公式可推导出信号强度转换距离的公式:0T d 10P(d-PL(d -P X 10expd ×+= (2-1实际应用中的情况要复杂的多,

7、尤其是在分布密集的无线传感器网络中。反射、多径传播、非视距、天线增益等问题都会对相同距离产生显著不同的传播损耗。因此这种方法的主要误差来源是环境影响所造成的信号传播模型的复杂性。信号强度测距法通常属于一种粗糙的测距技术,在现实环境中,温度、障碍物、传播模式等条件往往都是变化的,使得该技术在实际应用中仍存在困难,通常会产生50%左右的测距误差。然而,基于射频信号强度的RSSI 方法成本很低,适合于无线传感器网络的部署要求,所以前景很好。 2.1.2 DV-distance 算法DV-distance 算法很简单,在泛洪传输中仅通过在每个节点上累加测得的距离来确定其距锚节点的距离。算法从锚节点开始

8、,它们发送一个包含其身份,位置和设为0路径长度的信息包。每个接收到信息的节点将测得的其距发送点距离加到路径长度上,如果可控泛洪允许的话继续广播这个消息。另一个限制是,当节点再次收到以前接收过的节点信息时,只有当前信息中距锚节点路径长度小于原先信息中距锚节点路径长度时,才允许发送这个消息,并更新自身信息。最终结果是,每个节点将存储它们距锚节点的最短路径长度。DV-distance 算法的缺点是,当距离信息在多跳中传播时,测距误差被累加放大。在锚节点很少或测距硬件差的大型网络中,这种累计误差很大。2.1.3 DV-Hop 算法DV-hop 算法可以克服DV-distance 算法的缺点,它通过计算

9、跳数而不是累加有误差的测距获得网络拓扑信息。定位算法可以分为两个阶段,即两次广播过程。第一个阶段,每个锚节点采用广播方式将其位置信息传递给其邻居节点。广播的信息包格式为:Id i ,x i ,y i ,Hops i ,其中包含了该节点的标识Id i 、位置坐标(x i ,y i ,以及跳数Hops i 信息。初始Hops i 为0,接收到此数据的每个节点将此信息记录到一张表中。然后继续向其邻居节点广播,每广播一次就将Hops i 加1。当节点接收到一个相同Id 的数据包时,便要与原来的Hops i 进行比较,如果新的跳数小于原表中的跳数,就用新的跳数更新表中的跳数信息,意味着找到了一条更短的到

10、达该锚节点的路径。如果新的跳数大于原表中的跳数,就丢弃该数据包,也不再进行转发。经过第一阶段的广播过程后,锚节点也获得其它所有锚节点的坐标及跳数距离,而且所有传感器节点都已经得到所有锚节点的坐标和跳数距离。这样,每个锚节点即可用式2-2计算出锚节点i 到其它锚节点j 的每跳的平均间隔距离C ij : (2-2其中j是除i之外的所有其它锚节点。第二个阶段,每个锚节点广播其计算出的每跳平均距离,数据包的格式为:Id i, C i。C i是该锚节点到所有其它锚节点的每跳平均距离。每个接收到此数据的节点将此信息添加到表中,然后继续向其邻居广播。重复ID的数据包就丢弃。经过此阶段的广播后,所有节点都已知

11、所有锚节点计算的每跳平均距离C i。然后再将所有的每跳平均距离相加取平均: (2-3其中n为所有锚节点的个数。由此得到了全网所有锚节点之间的每跳平均距离。此时,各个节点也得到与各个锚节点的跳数。由此可计算出该节点到锚节点的距离:D i = hops × cc。图1 DV-hop定位算法示意图如图1所示,已知锚节点L1与L2,L3之间的距离和跳数,L2计算得到平均每跳距离为(40+75/(2+5=16.42。同理,L1与L3也计算出平均每跳距离。节点A将分别从L1,L2与L3获得平均每跳距离,然后去这三个距离的平均值cc。用cc乘以节点A到L1,L2与L3的跳数即可得到A到这三个锚节点

12、的距离。2.1.4Euclidean算法Dv-hop算法的缺点是不适用于极为不规则的网络拓扑结构,这种结构中,实际每跳间的距离差别很大。Niculescu和Nath提出了另一种称之为Euclidean的算法,这种测距算法是基于围绕锚节点的未知节点的局部几何算法。同样,信息也从锚节点开始泛洪传输,但测距算法比前几种情况复杂的多。如图2(a所示,假设节点拥有RSSI测距能力,已知未知节点B,C在锚节点L的无线射程内,BC距离已知或通过RSSI测量获得;节点A与B、C相邻。对于四边形ABCL,所有边长和一条对角线BC已知,根据三角形的性质可以计算出AL的长度(节点A与L的距离。使用这种方法,当未知节

13、点获得与3个或更多锚节点之间的距离后定位自身。未知节点B、C与锚节点L 两两相邻,节点A 与B、C相邻。对于四边形ABCL,所有边长和一条对角线BC已知,根据简单的几何原理可计算出AL 的长度。但节点A有两个可能的位置A和A,假如A还有其他邻居节点D 与锚节点L相邻,并与B或C之一相邻,那么可以使用D来替换B或C,再次计算AL的距离,则A节点就能在两个可能的位置中选择出正确的一个。使用这种方法,当未知节点获得与三个或更多锚节点距离后定位自身。由基本的几何知识,可以得出: (2-4 以上是在理想情况下,当四边形是凹四边形时情况要复杂一些。如图2(b所示,一个节点(self有两个邻居节点n1和n2

14、,n1距锚节点的距离估算为a,n2距锚节点的距离为估算为b。再加上已知距离c,d和e, Euclidean算法能获得self节点距锚节点距离的可能值r1和r2。Niculescu描述了两种确定使用哪个值(如果有两个的算法。如果存在第三个邻居节点n3,n3距锚节点的距离已估算出,且与n1或n2连通,可使用neighbor vote算法进行测距。用n3代替n2(或n1又将产生两个估算距离。正确的距离是这两对距离的一部分,且被一个简单的投票算法选出。当然,为了选出更精确的距离,可以考虑很多邻居节点。 (a (b图2 Euclidean 算法示意图2.2 计算节点位置模块可选算法 在此阶段,通过模块1

15、提供的未知节点到若干锚节点间的估算距离计算未知节点的初始位置。此阶段有三边测量法、多边形算法和Min-Max 等算法。 2.2.1 三边测量法 图3 三边测量法示意图三边测量法是最简单的定位方法,在二维平面上用几何图形表示出来的意义是:当得到未知节点到一个锚节点的距离时,就可以确定此未知节点在以此锚节点为圆心、以距离为半径的圆上。得到未知节点到3个锚节点的距离时,3个圆的交点就是未知节点的位置,如图3所示。从被估测的距离(di 和已知的锚节点的位置(xi ,yi 中我们可以得到一组方程:(x 1 - x2 + (y 1 - y2 =21d (2-6 (x 2 - x2 + (y 2 - y2

16、=22d (2-7(x 3 - x2 + (y 3 - y2 =23d (2-8求出(x ,y即是节点位置。2.2.2 多边形算法多边形算法源于三边测量法,当参考节点数量超过3个时,就是通过定义方程组,利用冗余信息能够更精确地计算节点的位置。假设未知节点坐标是( x ,y ,锚节点坐标分别为( x 1,y 1 ,( x 2,y 2 ,( x k , y k ,未知节点到锚节点的距离分别是r 1,r 2,r k ,我们可以得到一组方程:(2-9式(2-9可以线性化为:Ax = b 其中:(2-10(2-11由于存在测距误差,合理的线性模型应该是:Ax +N = b其中,N 为k - 1维随机误差

17、向量。利用最小二乘法原理,x 的值应当使模型误差N = b - Ax 达到最小,即通过最小化Q ( x = |N|2d3d2d1B(x1,y1C(x2,y2A(x0,y0D= |b Ax|2。求x的估计,对Q ( x关于x求导并令其等于零,可以求解未知节点的最小二乘位置估计:$x=(ATA-1ATb2.2.3 Bounding box算法基于最小二乘估计的多边测量定位法是最常用的定位方法,在很多定位算法中得到应用。多边测量定位的缺点是需要大量的浮点运算。针对这个问题,加州大学伯克利分校的Semic提出了一种更为简单的算法Bounding box。该方法的主要思想是利用锚节点的位置和测距值划出边

18、界框(bounding box,求解边界框的交集(图4中的黑框,黑框的中心就是未知节点的估计位置,从图中可以看到Bounding box算法与三边测量算法求解的差异。该算法实质是将求解二次方程组的问题简化为求解一次方程问题,从而避免了复杂的最小二乘解法,可以大大减少计算开销。 图4 Bounding box算法示意图算法主要思想是,用距离估计和锚节点位置为每个锚节点构建一个限定大小的盒子,然后确定这些盒子的重合部分。未知节点的位置即被设为重合部分的中心。如图2-7所示,用Min-Max算法确定一个已知到三个锚节点距离估计的节点的位置。值得注意的是,用Min-Max算法估测的节点位置接近于用多边

19、形算法计算出的位置(也就是,三个圆的重合部分。锚节点a的盒子是通过a的坐标(x a,y a加上和减去估测距离(d a得到的:x a-d a,y a-d a×x a+d a,y a+d a (2-12盒子的重合部分是通过取所有锚节点坐标与估测距离之差的最大值和所有锚节点坐标与估测距离之和的最小值计算得到的: max(x i-d i,max(y i-d i×min(x i+d i,min(y i+d i(2-13 2.3 循环定位求精模块算法这个阶段的目的是使在第二阶段计算得出的(初始节点位置更精确。即使在好的条件下(高连通度,低测距误差,这些节点定位也不可能很精确。原因是前两

20、个阶段并没有用到所有可获得的信息。由Savarese3等提出的精确过程正是当节点更新他们的位置信息时考虑了与所有节点间的距离。在每步开始时,一个节点广播它的位置并相应地从它的邻居节点那里接收邻居节点位置和距离,然后执行阶段二的多边形算法计算过程以确定它的新位置。在很多情况下,由到邻居节点距离所限,将迫使新的位置向节点真实的位置靠近。经过几步迭代后,当节点位置更新过程收敛时,精确过程结束并报告最终位置。3. 算法仿真对定位算法的仿真的意义在于能够在接近现实的环境中得出算法性能的数据,进行定量分析,从而得出算法的应用环境和不足之处,以待改进。仿真工具选择的是布达佩斯技术大学电信学院开发的OMNET

21、+离散事件模拟器。3.1 仿真算法选择本文选择完全的分布式算法,即节点位置的计算在节点本地完成。这种算法可以应用于大规模的无线传感器网络。这样的网络要满足:(1自组织,不依赖于全局基础设施(如卫星;(2健壮,能容忍节点失效和测距误差;(3节能,只需要较少的计算和通信开销。根据上述条件,排除了凸规划(Convex Position,MDS-MAP等集中式算法。此外,质心算法,APIT算法需要较高的锚节点密度,也被排除在外。本文对满足以上条件的三种定位算法,Bounding box算法, Euclidean算法和Robust Position算法做了仿真分析,这三种算法具有良好的可实现性和代表性。

22、将上述三个算法分解,得到他们各个模块的算法:表1 仿真算法按模块分解3.2 仿真网络环境设计鉴于无线传感器网络是自组织的,所以节点放置时是随机的,因此仿真环境中的节点是随机部署的。锚节点需要通过安装特殊的定位系统和采取人工部署来确定其位置,所以仿真环境中锚节点的位置可以人为确定。仿真环境中的重要参数有:网络中的节点数量;锚节点密度;节点通信半径(连通度。仿真由100个节点组成的无线传感器网络,开始时,依据上述参数产生一个随机的网络拓扑结构,节点在一个正方形区域内随机分布。通过指定通信半径可以控制连通度。3.3 仿真测距误差模块1中得到的未知节点到锚节点的距离在实际中是有误差的,这种误差在使用基

23、于测距的RSSI方法时表现得更为明显。因此在算法仿真中凡是用到RSSI测距时都要模拟引入的误差,这样建模才能和实际相符。因此,如何引入这个误差是我们要考虑的问题。相关方面的论文有许多,最为经典的是Noisy Disk模型,其数学模型如下:=则未定义若其中maxijmaxijijij dddd,d(d(3-1其中ijd为节点i到节点j的实际距离, maxd为节点最大连通距离,ijd为节点i到节点j之间的引入误差后的距离。由此可知,该模型假设节点之间估测的距离服从正态分布。其中期望为真实距离,方差凭经验指定,因实际环境的不同而异。这种方法较容易在计算机中实现,但算法在计算机中的模拟结果往往与实际中

24、的运行结果相差很大。在这里再介绍了另一种构建模拟环境的方法。这种方法通过获取大量的实际数据构建经验数据库。算法在计算机上进行模拟时就可以从经验数据库中抽取相应的数据,以得到与实际环境更加贴近的仿真环境。本文中所述算法的模拟环境是Noisy Disk方法的一种变形。由于传感器主要是通过测量RSSI值来获得信号强度进而获得节点间距离的,所以此处把测量的RSSI值当作一个服从正态分布的随机变量。4. 仿真结果和算法性能评估4.1 算法仿真结果在检测算法的定位精度性能的仿真实验中,将通信半径设定为15。这里将测距误差定义为一个比值,即算法计算得出的节点位置与真实位置之间的偏差比上节点到锚节点的距离估计

25、。仿真实验获得了一组在不同锚节点密度下三个算法在定位误差方面的数据,如图5所示。在检测算法的定位覆盖率性能的仿真实验中,将通信半径也设定为15。仿真实验获得了一组在不同锚节点密度下三个算法在定位覆盖率方面的数据,如图6所示。模块Boundingbox Euclidean RobustPosition1 2 3 DV-distanceMin-max无Euclidean多边形算法无DV-hop多边形算法有在检测算法能量消耗性能的仿真实验中,依然将通信半径定为15,锚节点密度定为10%,所以网络平均连通度C(邻居节点个数为6。能量开销包括通信开销和计算开销,实验获得了一组在不同节点个数下三个算法在能

26、量消耗方面的数据。如图7、8所示。 图5 三个算法的定位精度仿真结果从定位精度仿真实验中,可以看到,三个算法的定位误差均随锚节点密度的增大而降低。其中,Bounding box算法对网络中锚节点密度最为敏感,锚节点密度从3%变化到10%时,定位精度显著提升。Euclidean 算法和Robust position算法对锚节点密度没有如此敏感。 图6 三个算法的覆盖率仿真结果定位覆盖率是考察定位算法性能的重要指标,它表示通过执行某个定位算法,网络中被正确定位(定位误差在可接受的范围内的比例。从定位覆盖率的仿真实验中,可以看到,三个算法的定位覆盖率均随锚节点密度的增大而提高。其中,Bounding

27、 box算法和Euclidean算法对网络中锚节点密度很敏感,尤其当锚节点密度从3%变化到10%时,这两个算法的定位覆盖率显著提升。Robust position算法对锚节点密度并不敏感,在锚节点密度很小(只有3%时,其定位覆盖率已达90%,在10%的锚节点密度下,覆盖率已达100%。 图7 三个算法的通信开销仿真结果能量消耗包括通信开销和计算开销,它是无线传感器网络的瓶颈所在。因此,一切研究都要考虑尽量降低能量消耗。从能量消耗的仿真实验中,可以看到,三个算法的通信开销随网络规模的增长基本呈线性变化。其中,Bounding box算法的能量开销随网络中节点数的增加增长得很快。Euclidean

28、在这三个算法中的能量开销最小。 图8 三个算法的计算开销仿真结果图8显示了仿真试验中三个定位算法的计算开销。其中,Bounding box算法在模块2中计算节点位置信息时用Min-max方法代替了多边形测量法,从而避免了复杂的最小二乘法,所以运算次数最少。而Robust Position算法不仅在模块2中用了多边形算法,而且引入了模块3的迭代求精过程,所以计算开销最大。4.2 算法性能评估算法的性能主要从以下三个方面进行评估:定位误差、通信开销和定位覆盖率。在评估算法性能时,用到了如下的参数: N网络中节点数量,A锚节点数量, C平均邻居节点数量(网络连通度, K参加一次多边形测量计算的锚节点

29、个数。4.2.1 Bounding Box算法通信开销:锚节点发送广播消息,消息只传播到其邻居,邻居节点并不转发,每个节点需与其邻居节点通信一次,所以整个网络发送消息数量为NC。计算开销:该算法的计算包括求每个交集的两对最大值和最小值,对于每个交集,需要2C次比较运算和4C次加法运算,所以总的运算开销为6C次。该算法需要非常少的计算和通讯开销,算法的覆盖速度很快,位置估计的精度随着锚节点数量的增加而提高。算法的主要缺点是需要较高的锚节点密度,否则定位精度和覆盖率将会很低。该算法适合于节点的计算能力非常有限的情况。4.2.2 Euclidean算法通讯开销:每个锚节点发送TTL为2的数据包,即数

30、据包只转发两跳,锚节点的邻居节点转发一次数据包,整个网络发送的数据包数量为A +AC。计算开销:算法的计算开销包括距离计算和最小二乘算法。其中距离计算需要做44 × 2 + 2 = 90次。得到正确的距离AL,多边测量定位需要17 k - 17 + 23 / 3次。算法的网络通讯开销为A + AC,节点计算开销为(17k + 73 + 23 / 3。与DV-hop算法不同, Euclidean算法依赖于局部几何拓扑,适用于网络拓扑不规则的网络,由于数据包只传送两跳,该算法通讯开销较小,同时具有适当的计算开销和定位精度。但该算法的覆盖度受锚节点密度和局部几何拓扑的影响较大。4.2.3

31、Robust Position算法通讯开销:初始阶段与DV-hop类似,由每个锚节点发送广播数据包,中间节点只发送未发送的数据包,所以网络中每个节点平均发送A个数据包。在求精阶段,节点只广播其位置信息到其一跳邻居节点,所以每个节点发送s (迭代次数个数据包。通过优化可以减少这个数量,例如只有当位置信息变化较大时才广播更新位置,这样就比估计的通讯开销要小。计算开销:在初始阶段的DV-hop算法过程中,每个节点将执行17( k - 1 + 23 /3次。求精的每一次迭代,节点将做一次最小二乘估计并产生新的置信矩阵。如果算法共迭代s次,对于求精,每一次最小二乘估计将包含节点的一跳邻居。因此,每一次最

32、小二乘运算将消耗17( C -1 + 23 /3次。每一个置信度计算需要C次加法和1次除法。在整个求精过程中,每个节点需要s 17(C - 1 + 23 / 3+ C + 1 = s 18C - 16 + 23 / 3 次。该算法能够达到较好的精度,在网络连通度较高的情况下能较好地容忍距离误差。因为节点主要和其一跳邻居节点通讯,该算法也是一个可扩展的算法。但是,由于迭代的过程,该算法是强计算的。如果初始位置估计非常不准确或误差是相关的,算法可能不能达到精确的估计。由于依赖于网络拓扑,该算法可能需要很长的覆盖时间。5. 算法比较和改进建议5.1 算法性能比较上述三种算法均为完全分布式定位算法,且

33、均可扩展,即每个节点的计算复杂度与网络规模无关。从能耗方面分析,计算与通信开销最小的是Bounding Box算法;Euclidean算法的计算和通信开销适中;Robust Position算法的计算与通信开销最大。从定位精度上看,Bounding Box算法只有当网络中锚节点密度较高时才能获得较好的定位精度;相比之下,Euclidean算法的在不同的网络环境下定位精度都适中;而Robust Position算法采用了迭代求精过程,可以达到较高的定位精度。从覆盖率的角度上说,Bounding Box算法和Euclidean算法的覆盖率都与锚节点密度有关,但后者由于采用与锚节点两跳的距离估算,能

34、够获得较高的覆盖率。出于成本方面考虑,Bounding Box算法需要较高的锚节点密度,增加了网络的成本。可见,从多种角度和不同网络环境衡量,没有一种算法是最优的。在某一个环境下,这三种算法之一会优于其他两种算法,而且,每种算法都有可优化和提升的空间。5.2 算法改进建议从上述分析中,我们看到Robust Position算法在定位精度、容错性、网络成本等方面有较大的优势。但算法的计算复杂度较高,可以考虑在计算节点初始位置阶段采用Bounding Box算法的思想,其实质是将求解二次方程组的问题转化为求解一次方程问题,从而避免了复杂的最小二乘法,可以大大减少计算开销。6. 总结6.1 论文总结

35、论文深入研究了三种具有良好可实现性和代表性的无线传感器网络分布式自身定位算法:Bounding box算法,Euclidean 算法和Robust Position算法,并设计了仿真程序,在OMNET+平台上对三种定位算法进行了仿真检验,在仿真结果的基础上对这三种算法的性能做了比较分析,并对他们的应用环境给出了建议。论文最后提出了算法的改进意见和未来研究方向展望。Bounding box算法,Euclidean算法和Robust Position算法都是完全分布式算法,且均可扩展,即每个节点的计算复杂度与网络规模无关。这三个算法均满足自组织、健壮和节能这三个WSN定位算法的基本条件,且具有典型

36、性和良好的可实现性。论文主要对这三种定位算法的定位精度、覆盖率和能量开销三个方面进行仿真检验和性能评估。通过对仿真结果分析,比较了在不同网络环境下这三个算法的表现,并对他们的应用环境给出了建议。论文的主要结论是从多种角度和不同网络环境衡量,没有一种算法是最优的。在某一个环境下,这三种算法之一会优于其他两种算法,而且,每种算法都有可优化和提升的空间。从仿真结果可以看到,Robust Position 算法在定位精度、容错性、网络成本等方面有较大的优势。但算法的计算复杂度较高,可以考虑在计算节点初始位置阶段采用Bounding Box算法的思想,其实质是将求解二次方程组的问题转化为求解一次方程问题

37、,从而避免了复杂的最小二乘法,可以大大减少计算开销。6.2 未来研究工作在WSN自身定位领域,当今主要是对定位算法本身进行研究,在将来以下三个方向有可能成为热点:(1定位算法性能评价的量化和模型化。WSN自身定位算法的性能直接影响其可用性,至关重要。如何评价是一个需要深入研究的问题。虽然已有几个常用标准,例如定位精度、锚节点密度、节点密度、功耗等,但这些标准还没有达到实用程度,需要进一步地模型化和量化。(2自身定位仿真系统。如何建立一套标准的仿真技术和仿真系统来模拟WSN 自身定位算法的实现,将会极大地降低费用和时间成本,有利于各种定位算法的评测。(3移动性问题。以往的WSN自身定位算法大都假

38、设网络是静止的,所以在网络移动条件下,如何实现低成本、低功耗和高精度的定位,也是面临的挑战之一。参考文献1 Nicolescu D. Nath B. Ad2hoc positioning systems (APS A. Proceedings of the 2001 IEEE Global Telecommunications Con2ference C. New York. USA: IEEE. 2001. 29262931.2 Savarese C. Rabaey JM. Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Intl Conf. on Acoustics. Speech. and Signal. V ol.4. Salt Lake: IEEE Signal Processing Society. 2001. 20372040.3 Savarese C. Rabaey J M.