一种基于RSSI的无线传感器网络的改进定位算法*

冯成旭 刘 忠 程远国

(海军工程大学电子工程学院 武汉 430033)

1 引言

在无线传感器网络的许多应用中,监测到事件的位置信息至关重要,定位技术是关键的技术之一。提到定位技术,我们不难想到全球定位系统GPS。但是采用GPS技术的系统,往往用户节点能耗高、体积大、成本高,这些特点使得GPS技术并不适用于低成本自组织的无线传感器网络。因此,无线传感器网络定位已经成为当今一个很重要的研究方向和热点问题。

在传感器网络中,定位算法通常划分为基于距离(range-based)的定位算法和与距离无关(rangefree)的定位算法[2]。基于距离的定位中,常采用的方法有:基于到达时间 TOA的定位、基于到达时间差TDOA的定位、基于接受信号强度指示RSSI的定位和基于到达角度AOA的定位等。与距离无关的定位算法主要有:质心算法、DV-Hop算法、Amorphous算法、APIT算法等等[1]。其中最常用的是利用锚节点到未知节点的RSSI(接受信号强度指示)[4]值来估算未知节点到锚节点的距离,从而实现未知节点的定位,因为它不需要添加任何额外的硬件设备,只是在现有的硬件基础上读取信号的场强值再经过数据处理和算法实现便可定位。

2 算法原理

2.1 三边测量法

图1 三边测量法

在基于RSSI的定位中,最常见的便是三角形质心定位算法[6]和加权质心定位算法[3]。而三角形质心定位算法的理论基础是三边测量法[1]。如图1所示。

如图 1所示,已知A、B、C三个节点的坐标分别是(xa,ya)、(xb,yb)、(xc,yc),D点的坐标是(x,y),它们到D点的距离分别为da,db,dc,则它们存在下列关系:

2.2 三角形质心定位法

然而,在实际的基于RSSI距离的定位中,由锚节点到未知节点的RSSI值换算出来的距离值并不是精确的,而且由于电磁场信号的衰减,换算出来的这个距离值要大于从未知节点到锚节点的实际距离。因此,三边测量法只是理想状态下的模型,然而真实的模型应该是如图2所示。

图2 三角形质心定位算法

如图2所示,D为未知节点,A、B、C为锚节点。分别以通过 A、B、C 到D 的 RSSI值换算出的距离值为半径作圆。由于D必定在A、B、C相应的通信半径以内,因此三圆必定会有重叠的区域,如图中弧EF、弧FG和弧GE所包围的区域就是该重叠区域。而且,未知节点D的实际位置必定在该重叠区域内。然后,再对△EFG求质心,未知节点D的位置就是该质心的坐标。即D的坐标为

2.3 改进的算法分析

但是,三角形质心定位算法在实际环境测试中也有诸多不足:

1)三角形质心定位算法只适用于理想三角形,即未知节点的位置在三个参与定位的锚节点所构成的三角形的内部如图3。在实际的环境中,因为锚节点是大规模随机布放的,因此必定存在一些非理想的三角形的情形并不适用于三角形质心定位算法,如图 4未知节点并不在锚节点三角形ABC的内部;如图5,与未知节点相邻的3个锚节点并不能构成三角形。在这些非理想三角形的情形下,三角形质心定位算法并不适用,如果不予考虑的话必定带来更严重的误差。所以,考虑将该算法进行优化,在进行三角形质心定位算法之前进行理想三角形验证。验证未知节点D是否在由三个锚节点所构成的三角形内部,如果不在其内部则将该三角形进行舍弃,继续寻找,直到找到理想的三角形后再进行三角形质心定位算法。

2)三角形质心定位算法只是采用了3个锚节点的RSSI数据进行定位,并未利用整个网络的数据,从而造成了有效资源的浪费。而且,当这锚节点因偶然因素造成数据失真时,会给定位带来更大的误差。因此,考虑将网络中更多的理想三角形参与定位,从而给未知节点一个更准确的定位。

3)三角形质心定位算法并没有考虑RSSI数值对距离的影响程度。在实际的无线电传播路径损耗模型中,RSSI值的衰减与距离的增加并不是线性关系。随着未知节点到锚节点距离的增加,由RSSI数值的偏差产生的换算距离的误差会迅速增大。因此,考虑在进行定位算法时引入权重系数来体现锚节点对未知节点位置的影响程度,从而来减小误差。其基本思想是:RSSI数值越大的锚节点,对未知节点位置的影响力越大。在进行质心定位算法时,将每一个决定质心的点的坐标都乘以一个权重系数,以此来综合权衡计算得出最终的未知节点位置。

2.4 改进的算法原理

针对第一个问题,理想三角形优选的解决方案,最佳莫过于近似三角形内点测试法APIT[4]中的核心思想。APIT测试的基本原理如图6、图7所示。

假设存在一个方向,节点D沿着这个方向移动时会同时接近或者远离A、B、C三个节点,那么节点D位于△ABC之外,如图7;否则节点D位于△ABC之内,如图6。

而在实际的环境测试中,如果未知节点D收到的RSSI数值在增大,则说明D在远离锚节点;反之,如果D收到的RSSI数值在减小,则说明D在接近锚节点。

利用APIT算法的核心思想来进行理想三角形的优化选择,可以看到如上图中的两种非理想三角形在APIT测试中会得出未知节点D在△ABC之外,对这种三角形予以舍弃,只保留未知节点在其内部的理想三角形。

对于第二个问题,改进后的算法采用了更多的锚节点的有效数据。对RSSI数值达到一定门限的锚节点都认为是可以参与定位算法的有效节点。而RSSI数值低于这个门限的锚节点因为会带来比较大的误差所以就予以舍弃。

3 算法过程

定位算法的整体流程:

1)收集所有锚节点到未知节点的RSSI数值,并多次采集取其均值。然后,设定一个RSSI值门限,将RSSI数值低于这个门限的锚节点予以舍弃,高于这个门限的锚节点视为有效节点,将其数据保留。

2)将所有有效节点按照 RSSI数值的大小进行降序排序,假设有n个有效的锚节点即(R1,R2,R3,…,Rn),这里R1为最大的 RSSI值,Rn为最小的RSSI值。

4)将所有的有效锚节点所组成的三角形集,进行理想三角形的优化选择。因此,共有个三角形,进行次近似三角形内点测试后,将测试结果为理想的三角形予以保留,非理想的三角形予以舍弃。

5)将保留的理想三角形进行如图2所示的质心定位算法,得出未知节点第一阶段定位的近似位置(xi,yi),共有m组近似位置。

7)将所有的理想三角形的输出结果(即未知节点第一阶段定位的近似位置(xi,yi))分别与其相应的权重系数相乘,进行加权质心定位。最后的输出结果就是未知节点的坐标(X,Y),即

4 算法仿真

在Matlab平台上进行该改进的定位算法仿真。组建一个虚拟的实验场景,初始条件为无线传感器网络在一个100m*100m的正方形区域内。在此,锚节点是随机的分布在这个正方形的区域内的。节点的有效通信半径设定为50m。每次仿真结果都是通过运行算法100次,然后取平均值得到的。

图8 仿真结果分析

由图 8分析可知,当锚节点数目较少(10个)的时候,改进的算法对于普通的质心定位算法误差并没有明显的提升。但是随着锚节点数目的增加(20个以上),误差就明显减小了。

5 结语

本文提出了一种基于RSSI的改进定位算法。仿真结果表明,本文算法比传统的RSSI定位算法有更好的定位精度。将近似三角形内点测试的核心思想引入理想三角形的筛选,加权算法中权重系数模型的选择,都能够明显减小定位误差。但是同时也带来了算法复杂度的提高。因此,下一步的工作是研究理想三角形的优化选择机制,以降低算法的复杂度。以进一步优化算法的整体性能,从而得到更好的定位效果。

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

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

[3]陈维克,李文峰,首珩,等.基于 RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报(交通科学与工程版),2006,30(2)

[4]He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int'l Conf on M obile Computing and Networking(M obiCom),San Diego,CA.,2003:81～95

[5]赵昭,陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报,2009(3)

[6]林玮,陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J].现代电子技术,2009(2)

[7]周四清,陈锐标.无线传感器网络APIT定位算法及其改进[J].计算机工程,2009(4)