室内无线传感器网络中移动节点的改进质心定位算法

李 彬, 施 泱

(山西大学,数学科学学院,山西 太原 030006)



室内无线传感器网络中移动节点的改进质心定位算法

李 彬, 施 泱

(山西大学,数学科学学院,山西 太原 030006)

目前室内定位方法往往精度不高，价格也较为昂贵.文章介绍一种传统的质心定位算法，并且提出一种基于参考点计算质心的改进室内移动节点质心定位算法.仿真结果表明，该方法能够有效提高节点的定位精度.

移动节点；质心算法；室内无线传感器网络；节点定位

1 概述

无线传感器网络(WSN)中的节点定位是传感器网络最基本的功能之一,对传感器网络应用有着重要作用.定位算法从定位手段上分为:基于距离的(Range-Based)定位算法和距离无关(Range-Free)的定位算法[1].在无线传感器网络的实际应用中,很多情形都需要对某些移动节点进行快速准确定位,如军事、交通、反恐等场景中节点位置伴随着被监控对象的移动而变化.由于未知节点的移动特性,其相应的定位算法通常也要求快速准确.如何能快速准确地定位未知节点,成为了无线传感器网络中移动节点的定位问题研究的热点之一[2].文献[3]提出了一种基于RSSI的加权质心定位算法,定位精度有了一定的提升.但由于节点要将RSSI值转化为距离信息,同时定位过程中要进行质心的加权运算,当节点快速移动时该算法较难满足定位的实时性要求.文献[4]较好的解决了节点分布不均对传统定位算法的影响,但算法中对RSSI的可信选取方案还有进一步讨论的必要.

之前的定位算法主要依赖于可通信节点对未知节点的位置约束来定位节点.与其不同的是,本文针对室内传感器网络,通过同时考虑与未知节点可通信的和不可通信的锚节点的位置信息,在定位区域内引入比对点来计算质心,保证定位的快速性的同时,提高了定位精度.

2 算法模型

2.1 一种传统的定位算法

传统的质心算法(Centroid Algorithm)是一种基于连通性且无需距离信息的简单定位算法.其核心思想是把在未知节点通信范围之内的信标节点所构成的几何图形的质心作为未知节点的估计位置[5].

如图1,设O1,O2,O3为锚节点,且有相同的通信半径,每一个锚节点的通信覆盖范围为一个以锚节点为圆心的圆.A,B,C分别为三个圆的交点.若未知节点能与它们相互通信,则未知节点应处于三个锚节点所覆盖的公共区域内,质心定位算法取A,B,C三点形成的三角形的质心作为未知节点的位置估计.

2.2 改进的质心定位算法

2.2.1 定位范围的改进

在室内无线传感器网络节点的定位过程中,锚节点可以一定范围内较为自由的部署,且相对部署密度较大,如何充分利用锚节点位置已知的条件是提高未知节点定位精度的关键.然而以往的定位算法只关心可通信的锚节点对未知节点定位起到的作用,忽略了不可通信的锚节点在未知节点定位中的作用.不可通信的锚节点同样可以用来缩小定位范围,提高定位精度.如图2所示,在图1的基础上增加一个与O1,O2,O3有相同的通信半径的锚节点O4.若未知节点不能与O4节点通信,那么未知节点的位置只能在C,D,E所形成的阴影区域内,记此区域为SCDE.再利用质心定位算法取C,D,E三点形成的三角形的质心作为未知节点的位置估计.

可以看出相对于一般质心算法,此方法有效的缩小了未知节点的定位范围.

图1 传统质心定位算法

图2 改进质心定位算法

2.2.2 质心计算方法的改进

由于此算法对于未知节点定位范围的质心计算只选取了很少的边界点,计算过程依然很粗糙.若能够知道区域内更多的点的坐标,在计算区域质心时将更为准确.因此,我们在未知节点定位范围内选取出更多的比对点,利用这些比对点与锚节点的通信情况将之分类,有相同通信情况的比对点归为一类.如图2中,SCDE中的所有点只能与O1，O2，O3相互通信,与其他锚节点均不能通信.反之,能与O1，O2，O3相互通信的所有可能节点也都含在SCDE中.我们将此区域称为定位划分区,定位划分区内的比对点有相同的通信信息.在SCDE中引入更多的比对点,将使得质心的计算更为准确.

我们在监测区域内引入比对点,将比对点与锚节点的距离信息转化为通信信息,建立通信矩阵C=(cij)k1×k2，m.若第i个比对点可以与第j个锚节点通信,则cij=1,否则cij=0.然后将移动节点的通信信息与比对点的通信信息进行比对.若通信信息相同,则比对点与移动节点在相同的定位划分区内.然后利用比对点的质心作为定位划分区的质心,估计出移动节点的位置.

2.3 算法步骤

锚节点通过泛洪方式周期性的广播自己的位置信息,未知节点接收到此信息则认为二者可相互通信,同时也意味着二者的距离小于锚节点的通信半径R.对于分布着m个锚节点的矩形监测区域[0，a]×[0，b],我们采用以下步骤求出未知节点的存在区域.

Step1 建立坐标系,在[0，a]×[0，b]内等距插入节点,间距为λ,则

其中x=n,xn=b,y=0,yn=b,λ称为分割细度.将{xi},{yi}做笛卡尔集,这样就可在X+Y平面内插入k1+k2个比对点,我们将这些插入点称为比对点.定位时要求比对点的数量足够多.

Step2 将比对点与锚节点的距离信息转化为通信信息,建立通信矩阵C=(cij)k1×k2,m.若第i个比对点可以与第j个锚节点通信,则cij=1,否则cij=0.

Step4 求出与移动节点同类的比对点的质心作为移动节点(x，y)的位置估计.

3 实验结果

3.1 定位误差

实验在MATLAB环境下进行.在40 m×40 m的感知区域内均匀分布25个传感器节点,设传感器节点的通信半径R=10 m，移动节点在40 s内非均速通过感知区域.

从图3中可以看出,改进质心算法与传统质心算法相比有着较好的定位效果.而且由于改进质心算法不需要测距信息,所以能够保证定位的实时性要求.

从图4中可以看出,整个定位过程中改进质心算法对移动节点的定位误差不超过2.5 m,平均定位误差为0.943 9 m.相较于质心定位算法,平均定位误差提高约50%.

图3 改进质心算法定位误差

图4 定位误差曲线

4 结论

本文提出一种在室内存在部分信标节点情形下的移动节点改进质心定位算法.该算法充分考虑了通信信息对移动节点定位的作用,而且不需要测距信息,设计简单.另外,对比传统质心算法可知我们的方法定位误差更小,此方法更适用于实际.

对于此算法,考虑到实际中锚节点的部署情况将直接影响定位精度,因此讨论锚节点的部署形式将进一步提高测距精度.参考文献：

[1] G.Blumrosen,B.Hod,T.Anker,D.Dolev,and B.Rubinsky,Enhanced calibration technique for rssi-based ranging in body area networks[J].Journal on Ad Hoc Networks,2013,11(1):555-569

[2] 梅 举,陈 涤,辛 玲.基于蒙特卡罗的移动传感器网节点定位优化算法[J].传感技术学报,2013,5(26):689-694

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

[4] 陈维克,李文锋,首 珩,等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报,2006,30(2):256-268

[5] 杨新宇,孔庆茹,戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报,2010,44(8):1-4

Localization for Indoor WSN

LI Bin，SHI Yang

(School of Mathematical Sciences，Shanxi University, Taiyuan 030006, China)

The positioning accuracy of the indoor positioning method is not high at present. In this paper, a traditional centroid localization algorithm is analyzed, and an improved algorithm based on the centroid of reference point is proposed. Simulation results show that the location precision can be improved effectively.

mobile node; centroid algorithm; indoor WSN; node localization

2016-05-09

李 彬(1980-),男,山东威海人,硕士,山西大学讲师,主要从事无线传感器网络与控制工程研究.

1672-2027(2016)03-0057-03

TP393

A