基于三重修正的WSN节点定位方法

王 枭,刘瑞敏,毛剑琳

(昆明理工大学 信息工程与自动化学院,昆明 650500)

无线传感器网络是一种被部署在受控区域的多跳自组织网络,它由大量的具有通信与感知能力的传感器节点构成,在入侵检测、工业自动化、智能建筑等众多领域有着极其广泛的应用[1-4]。在任何领域中，只要涉及到无线传感器网络的应用,那么它的节点定位就起着不可估量的作用。目前,在节点定位技术中,主要有基于测距和基于非测距的定位技术。虽然基于测距的定位技术通过节点间的绝对距离来计算节点的位置,精度相对较高,但是，在大型区域中它会产生较高的硬件成本,同时也会产生较高的能耗。然而，基于非测距的定位技术仅需要节点间的互连来实现定位,因需要较少的硬件支持,成本比较低廉而受到青睐[5]。在测距定位中,研究较为广泛的是TOA，TDOA，RSSI，AOA等技术;在非测距定位中,对于Centroid，APIT，DV-HOP技术的研究较为广泛。

本文在DV-HOP算法的基础上进行改进优化，使得定位效果更佳。DV-HOP技术通过锚节点与未知节点间的相互通信来获取每个未知节点到锚节点的最小跳数值,然后，根据锚节点间的跳数与距离,计算出锚节点的平均跳距,最后，未知节点通过跳距计算出到锚节点距离,再根据某种计算方法计算出未知节点的坐标。DV-HOP算法由于其在实际环境定位中无需测距设备,可以大大降低网络的成本,因此，在实际应用中具有独特的优势。当DV-HOP在大规模网络中被应用时,它的关键问题是如何设计跳数机制、如何能有效降低跳距的误差以及如何能较准确地求出未知节点的定位算法。实际上,由于网络中未知节点的数量多于锚节点数的原因,利用锚节点的跳距来求锚节点与未知节点间的距离是造成距离误差的一个因素;另外,由于锚节点间的跳数可能会存在不是整跳数的情况,按照传统整数跳数机制就会使得跳距出现偏差;最后,在定位算法中由于没有对未知节点与锚节点间的距离进行误差校正而使得定位效果较差。但是由于DV-HOP定位精度较低的缺点,使得许多研究人员致力于定位精度优化算法的研究[6]。因此,国内外的研究学者们纷纷对DV-HOP算法做了不同的改进与优化。赵雁航等[7]首先对跳距进行修正,然后，通过粒子群优化算法来降低定位误差;文献[8]通过距离校正因子结合传感器节点的通信半径校正未知节点到信标节点的平均跳距;文献[9]引入跳数因子,通过跳距的误差加权来进行跳距的修正,最后，通过加权最小二乘来定位;文献[10]中锚节点先将跳距传播给邻居的未知节点,然后，依据此跳距计算出锚节点间的估计距离，计算出与锚节点间实际距离的误差,并且将此误差的百分比作为权重来计算未知节点的跳距;文献[11]依据最小均方误差来求出每个锚节点的跳距,然后，将某个锚节点间跳数的倒数与所有锚节点间跳数的倒数之和的比作为加权值来对跳距进行加权,最后，采用双曲线定位算法进行定位;徐慧娟等[12]利用相似度对测距值进行校正,然后，将最小二乘法得到的未知节点坐标作为遗传模拟退火算法的初始解进行迭代，得到比较优良的未知节点坐标;刘登峰等[13]将定位问题转换为优化问题,利用布谷鸟差分优化算法进行优化求解,可以有效地规避定位过程中误差积累的缺点。虽然一直有许多研究学者在DV-HOP方面做出了大量的研究与改进,但是依旧有些问题是需要继续研究的,包括未知节点到锚节点的跳距、符合实际情况的跳数机制、在定位算法中未知节点到锚节点的距离误差校正等问题。

本文提出一种基于三重修正的无线传感器网络定位算法(triple correction localization algorithm),以下简称TC定位算法。在计跳阶段,采用新的跳数计跳机制;在跳距阶段,通过质心定位算法来对锚节点的跳距加权得出未知节点的跳距,减小节点的距离误差;在定位阶段,采用最小二乘法校正传感器节点的距离矩阵。最后，通过高斯牛顿算法进行定位求解,有效地减小定位过程中产生的误差。

1 定位模型

该算法模型共含有3个步骤:

step1估计所有节点跳数。锚节点以泛洪的方式将它自身的信息传播到整个网络中,这些信息分别包括坐标、id、跳数。直到网络中的节点全部连通时,所有的未知节点即可获取到锚节点的跳数。当多个锚节点给同一未知节点传播坐标信息时,未知节点只保留跳数值最小的信息。这样就得到了未知节点到所有锚节点的跳数信息。

step2估计锚节点的平均跳距。锚节点根据自己的坐标与到其他锚节点的跳数信息计算锚节点的平均跳距,然后，锚节点将本身的平均跳距传播到网络中。锚节点i到其他未知节点的平均跳距如式(1)所示，

(1)

其中：(xi,yi)，(xi,yj)分别表示锚节点i，j的坐标;N表示锚节点的个数；Hi,j表示锚节点i，j之间的跳数。根据已经得到的跳数信息与锚节点的平均跳距计算出未知节点z到锚节点i的距离，如式(2)所示，

Di,z=WHD_i×Hi,z。

(2)

其中：Hi,z表示锚节点i到未知节点z的跳数；Di,z表示锚节点i到到未知节点z的距离。

step3估计未知节点坐标。根据第2步中未知节点与锚节点的距离信息,利用定位算法估计未知节点的坐标。

2 TC定位算法

传统DV-HOP算法在计跳阶段以整数的形式对节点间的跳数来计量,但实际中的跳数并不都是整数,所以，在整个网络中会造成误差的积累;在锚节点的平均跳距阶段,由于每个锚节点到所有未知节点的跳距相同,当未知节点较多时,也会出现误差较大的情况;另外,由于跳数、跳距获得过程中累积的误差,在计算未知节点到锚节点间的距离时，势必会产生较大偏差,所以，应该在定位阶段加入校正未知节点到锚节点距离的环节。因此,文中首先利用新的跳数机制实现非整数的计跳,再通过质心算法对不同锚节点到每个未知节点的跳距进行加权，得出较合理的未知节点的跳距,然后，利用最小二乘法对未知节点到锚节点的距离矩阵进行校正,最后，根据校正后的距离矩阵，利用高斯牛顿算法来得出比较准确的未知节点位置。

2.1 新的跳数机制

按照传统的计数方式,当节点在它的通信半径内可以与其他节点通信时，就认为这些节点间的跳数为1跳,但这种办法在实际应用中是不太合理的,所以，将跳数机制修正成式(3)，

(3)

其中，

(4)

(5)

ai=min(Dalli,j)。

(6)

其中：Dalli,j表示锚节点i，j的距离；Di表示其他锚节点到锚节点i的平均距离；ai表示与锚节点i距离最近的锚节点的距离值。

2.2 跳距修正

通过质心定位算法[14]对锚节点的跳距进行加权，作为未知节点的跳距。锚节点的跳距是在已经校正跳数的前提下按照式(1)计算得到。未知节点z的跳距如式(7)所示，

WHD_z=HOPT×Cent_Weigh。

(7)

其中：HOP是锚节点的跳距矩阵,是一个N行1列的矩阵;Cent_Weigh是一个N行1列的矩阵,这个矩阵中第i个元素为

Cent_Weigh(i)=

(8)

其中：(xi,yi)是锚节点的坐标；(xz,yz)是由质心算法计算出的未知节点的坐标；N表示锚节点的个数。

2.3 定位算法

未知节点的求解过程可以看作求解非线性方程组,而高斯牛顿法是求解非线性方程组的一种有效方法[15]。但是，直接利用高斯牛顿算法会由于锚节点与未知节点间的距离误差而造成定位精度下降,所以，在采用高斯牛顿算法定位前，应对未知节点到锚节点的距离进行校正。

在经过计跳与跳距修正以后,可以得到未知节点z到锚节点i之间的距离，

Diz=WHD_z×Hi,z。

(9)

通过最小二乘法对式(9)的距离进行校正,

Derror＿iz=

(10)

其中：(xls_z,yls_z)表示由最小二乘法得到的第z个未知节点的坐标；Diz表示第i个锚节点到第z个未知节点的距离；Derror＿iz表示锚节点i与未知节点z的距离误差。

经过校正后的未知节点z到锚节点i的距离为

Dcor＿iz=Diz+Derror＿iz。

(11)

其中,Dcor＿iz表示已经经过校正的未知节点z与锚节点i的距离。

假定Xz为未知节点,未知节点坐标为(xz,yz)。Bi为n个锚节点中的第i个锚节点,它的坐标为(xBi,yBi)。Diz表示未知节点Xz到锚节点i的距离, 是经过校正的,即Diz∈Dcor_z。未知节点z到锚节点的距离的方程组如式(12)所示，

(12)

其中:‖·‖表示欧几里得范数；n表示锚节点的个数。

经过前期的校正算法后,得到了比较高效的未知节点与锚节点之间的距离矩阵,最后，将问题转化为求解式(13)中的非线性方程组,采用高斯牛顿算法进行求解。将未知节点求解的问题转化最小二乘问题,如式(13)所示，

(13)

其中,dz如式(14)所示，

(14)

设Xk为经过k次迭代所得到的未知节点坐标,根据式(13)可以得到第k+1次的未知坐标，

X(k+1)=X(k)+λ×ΔX，

(15)

ΔX=-[JT(X)J(X)]-1J(X)e(X)，

(16)

e(X)=‖Xz-B‖-Dz。

(17)

其中,λ为迭代步长,需要根据实验进行设置,式(16)中J为雅克比矩阵。

具体的TC定位算法步骤如下：

step1部署网络,锚节点以泛洪方式在整个网络中传播自己的信息,并且根据式(3)，(7)，(9)来计算锚节点到位置节点的距离,再通过式(11)对未知节点到锚节点间的距离矩阵进行校正；

step2对未知节点z的位置X、迭代次数iter、迭代步长λ、迭代误差ε和当前迭代次数k进行初始化；

step3计算式(16)的雅克比矩阵,根据式(14)进行迭代更新；

step4只要f(x)的值满足迭代误差,则将此时未知节点z的坐标输出，否则，返回至step3继续迭代,令k=k+1,直至达到迭代次数要求；

step5输出位置节点的坐标。

3 仿真实验与分析

为了验证文中所提算法的性能,在Matlab上进行仿真实验。文献[9，11]中的定位算法是在DV-HOP的基础上进行改进的，所以，本文与文献[9，11]中的算法进行比较。另外,在本文修正跳距、跳数的基础上,利用最小二乘法(LS)进行定位,并与本文所提算法进行对比。布置传感器的检测区域为100m×100m,随机撒200个节点,传感器的通信半径为25m,锚节点的比例为s%,假定抛撒之后的传感器节点不移动,并且锚节点的通信半径都是相同的.每次实验在相互独立的条件下进行50次，取50次的平均误差值作为定位误差值。

将归一化的定位误差作为衡量定位性能的标准,如式(18)所示，

(18)

其中：(xtl,ytl)和(xl,yl)分别是传感器节点的真实坐标和估计坐标；s为未知节点的个数；r为传感器节点的通信半径。

图1给出了传感总节点数与平均定位误差的关系曲线。设置信标节点的比例为25%,通信半径为25m。从图1中可知,随着传感器节点数量的增加,本文所提算法的定位效果均优于其他3种定位算。

图2为锚节点的通信半径变化对定位误差的影响。设置信标节点的比例为25%,传感器总节点数为200。从图2可以得知,随着通信半径的增加,在25m与35m之间,本文所提算法的定位误差比其他3种定位误差小。但是在35m之后,本文所提算法的精度开始有所下降,进而可以得知,在适当的通信半径范围之内,对未知节点与锚节点间的距离校正会起到正向作用,如果超出通信半径范围，由于距离校正起到反作用，从而导致定位精度反倒下降。多跳方式是引起距离测量误差的一种因素，通信半径变大到一定程度,即图2中的35m,锚节点可以与更多的未知节点在通信半径内进行通信,减少了需要多跳方式进行通信的未知节点,所以，加上跳数与跳距环节的修正,通信半径较大的锚节点与未知节点间的距离测量误差本来就很小了，在这个情况下加入距离校正,会导致图2中过校正的情况。

图1 传感器总节点数变化对定位误差的影响Fig.1 The effect of the total number of sensors on the positioning error

图2 通信半径变化对定位误差的影响Fig.2 Effect of communication radius change on positioning error

图3中给出了锚节点比例对定位误差的影响曲线关系。设置传感器总节点数为200,通信半径为25m。从图3中可以看出,随着锚节点比例的增加,本文所提算法的误差在不断减小,由此可以得知所提算法的有效性。另外,在图3中可以看到,本文所提算法的定位误差均比其他3种算法的误差小,可以得知，本文算法在定位中具有较好的优势,能够提高定位精度。

图3 锚节点比例变化对定位误差的影响Fig.3 Effect of anchor node ratio change on positioning error

4 结 语

为了有效应对传感器网络定位误差较大的问题,本文提出一种基于三重修正的定位算法。首先，给出了新的计跳机制计算公式；然后，结合质心定位算法计算未知节点的跳距；再利用最小二乘法对未知节点与锚节点间的距离矩阵进行修正；最后，利用高斯牛顿法对未知节点与锚节点所组成的非线性方程组进行优化求解。另外,再通过Matlab实验平台进行仿真实验,分析不同因素对定位误差的影响。通过对比其他算法的定位效果,验证了本文所提算法能够有效提高定位精度。在下一步的研究中,可以与多位标度、模糊翻转等技术结合，开发更加完备的无测距定位算法。