一种无线传感器的Amorphous定位算法改进

刘 颖

（江苏食品职业技术学院 计算机应用技术系，淮安 223003）

一种无线传感器的Amorphous定位算法改进

刘 颖

（江苏食品职业技术学院 计算机应用技术系，淮安 223003）

0 引言

无线传感器网络主要由部署在监测区域内的微型、具有感知及无线通信能力的传感器节点组成,节点间以无线通信方式构成一个多跳的自组织网络[1]。对无线传感器网络的多数应用来说,无时空标识数据是没有价值的,所以获得传感器节点位置是需要知道的最基本的信息之一[2]。近年,无线传感器网络节点定位问题已成为研究热点。

根据节点定位过程中是否需要知道节点间的绝对距离或相对角度等信息,将无线传感器网络定位算法分为:距离相关定位算法和距离无关定位算法。距离相关定位算法可获得较高的定位精度,但对传感器节点要求较高,且易受外界环境影响,典型的算法有TOA、AOA以及RSSI等。距离无关定位算法利用节点间估算距离来计算节点位置,无需额外硬件支持、功耗和成本低、定位精度适中,典型算法有质心算法、凸规划算法、DV-hop算法、Amorphous算法等。与距离相关定位算法相比,距离无关定位算法更加适合大规模无线传感器网络的应用。

本文首先对Amorphous定位算法基本原理进行介绍,并指出该算法的不足,接下来提出改进的Amorphous算法,最后通过算法仿真比较验证算法性能。

1 Amorphous定位算法

1.1 基本原理

Amorphous同DV-Hop算法,该算法思想是利用两节点之间跳段距离代表二者之间的直线距离。其实现大致分三个步骤:

1)计算未知节点距各信标节点的最小跳数

各信标节点通过泛洪等方式广播分组消息,使网络中所有节点获得各信标节点的位置信息与距各信标节点的最小整数跳数,并用式(1)计算h局部跳数来代替整数跳数。

各参数定义如下:

s(i,k):未知节点i到信标节点k的跳数h(i,k):未知节点j到信标节点k的整数跳数h(i,k):未知节点i到信标节点k的整数跳数nbrs(i):未知节点i的邻居节点集合 |nbrs(i)|:未知节点i的邻居节点个数。

2)计算平均每跳距离

采用式(2)来计算平均每跳距离:

其中,r为节点通信半径,nlocal为网络平均连通度。

根据平均每跳距离及距各信标节点的局部跳数,计算未知节点距各信标节点的距离,如(3)式所示。

其中,HopSizei为未知节点i获得的平均每跳距离,hop (i, j)则代表未知节点i到信标节点j的最小跳数。

3)采用三边测量法或极大似然估计法进行定位

当未知节点获得了距三个或三个以上信标节点的估算距离,便可以采用三边测量法或极大似然法计算自身位置。

利用最小二乘法对上述方程进行求解,可求得未知节点位置。

其中,(x1,y1),(x2,y3),(x3,y3),…,(xn,yn) 对应n个信标节点的坐标,(x,y) 为未知节点的坐标,未知节点到各信标节点的距离依次为d1,d2,d3,…,dn。

1.2 缺点分析

1.2.1 累积误差

图1为传感器节点个数为150,随机分布区域为300×300 (m2),信标节点比例为17.2%,平均网络连通度为15.3%时,Amorphous定位算法所对应的跳数值与累积误差关系图。

图1 跳数值与累积误差关系图

由图1可以看出,随着未知节点与信标节点之间的跳数值的增大,二者间估算距离与真实距离的误差也随之增大。未知节点到达信标节点每增加一跳,便引入不同程度的累积误差。如何减少由于跳数值过大而引入的累积误差,是Amorphous算法要解决的一个问题。

1.2.2 不良参考节点的引入

在无线传感器网络的定位算法中,有这样一个结论:在未知节点的定位过程中,参与定位的信标节点数目越多,未知节点的定位精度越高。但是在基于跳段距离的定位算法中,这个结论并不总是正确的[3]。

图2 三边测量法与极大似然测量法定位性能比较

图2为信标节点比例为10%,平均网络连通度为10时,Amorphous算法分别采用三边测量法与极大似然测量法的定位性能比较图。其中,横坐标对应节点定位精度,纵坐标为各定位精度以内的节点比例。由图2可知,定位精度在40%(绝大多数应用已满足)以内时,三边测量法对应的未知节点比例大于极大似然法。这说明采用极大似然法进行定位会引入不良信标节点,可降低未知节点定位精度。

1.2.3 需要较大信标节点比例

在基于跳段距离的定位算法中,需要较高的信标节点比例,才能获得较高的定位精度。但若信标节点比例太高,又大大增加无线传感器网络的成本。AHLos[4]算法中将定位成功的未知节点全部转化为信标节点,虽然在一定程度上缓解了该问题,但同时也引入了更大的定位误差。

2 改进的Amorphous定位算法

针对基于跳段距离算法的缺点,本文提出一种改进的Amorphous算法,该算法的实现大致分为以下几个阶段:

1)初始化跳数阀值

设置跳数阀值,如果信标节点距未知节点跳数大于此阀值,则其不参与未知节点定位。

2)求未知节点距各信标节点最小跳数及距离

3)择优选取信标节点定位

判断未知节点周围满足跳数阀值限制的信标节点数,如果它大于3个,则从中择优选择3个,之后采用三边测量法进行定位。我们用图3中来说明择优选取信标节点的过程。

图3 择优选取信标节点实例图

接下来,用式(8)来比较L1的估算坐标与真实坐标的误差。

其中,L1的真实坐标为 (xreal,yreal) , (xi,yi) ,(1≤i≤6)为上述六种情况下计算所得的L1的估算坐标,R为节点通信半径大小。

假设L16所对应的Erro最小,则可推出未知节点A的最优解为A6。

4)将未知节点转化成信标节点

如果未知节点估算位置满足一定约束条件,则将其转化为信标节点,用以帮助其他未知节点进行定位。我们仍以图3为例,假设未知节点A估算位置为A',如果A'满足以下约束条件,则将其转化为信标节点。

5) 更新跳数阀值

当本轮定位结束后,判断是否有新的未知节点转化为信标节点。如果有,则保持跳数阀值不变;如果没有,则将跳数阀值加一。之后跳转至第二阶段,重新对剩余未知节点进行定位。直至所有未知节点定位完成。

6)定位结束

3 仿真

定位精度是评价定位性能的极为重要的一个指标。一般用未知节点真实位置与估算位置的距离与其通信半径的比值来表示。定位精度值越小,说明算法定位性能越好。无论在不同的信标节点比例还是在不同平均网络连通度下,改进Amorphous算法定位精度均远高于原始算法。且相比原始算法,改进算法所对应的定位精度曲线较为平滑,定位精度随着信标节点比例及平均网络连通度的增大而增大。可见,改进Amorphous算法在很大程度上降低了累积误差对定位精度的影响。

4 结束语

本文改进的Amorphous算法,因采用分轮定位机制,当节点分布不规则时,部分未知节点可能需要多轮定位过程才能完成自身定位,计算量较大。所以,如何在保证定位精度的前提下,尽量减少算法复杂度将成为接下来需要研究的重点。

[1]Akyildiz IF,Su W,Sankarasurbramaniam Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002,38 (4): 393-422.

[2]Bachrach J, Taylor C. Handbook of Sensor Networks:Algorithms and Architectures[M]. Wiley Interscience,2005: 552.

[3]Tian S, Zhang X, Wang X, et al. A Selective Anchor Node Localization Algorithm for Wireless Sensor Net-Works International Conference on Digital Object Identifier.Gyeongju 2007.

[4]Andreas S,Chih-Chieh H,Srivastava MB.Dynamic finegrained localization in ad-hoc networks of sensors[C].Proceedings of the 7th annual international conference on Mobile computing and networking Rome,Italy.2001: 166-1.

An adaptive multi-hop distance localization algorithm in WSN

LIU Ying

无线传感器网络中的Amorphous定位算法，利用跳段距离来代替两节点之间的直线距离，虽然实现简单，但在定位过程中会产生较大的累积误差。本文引入了自适应跳数阀值，并提出了一种改进的Amorphous定位算法。仿真实验结果表明，与原始算法相比，改进算法降低了累积误差，同时提高了算法的定位精度和鲁棒性。

无线传感器网络；Amorphous算法；累积误差；定位精度；鲁棒性

刘颖(1974－),男,江西宜春人,实验师,硕士,主要从事计算机应用和现代教育技术研究工作。

TN92

A

1009-0134(2011)1(上)-0161-03

10.3969/j.issn.1009-0134.2011.1(上).49

2010-10-02