基于跳距修正的WSN拟牛顿迭代定位算法*

乔 欣,常 飞,丁恩杰*,王桃

(1.中国矿业大学 物联网(感知矿山)研究中心,江苏 徐州 221008;2.矿山互联网应用技术国家地方联合工程实验室,江苏 徐州 221008;3.中国矿业大学信息与电气工程学院,江苏 徐州 221008)



基于跳距修正的WSN拟牛顿迭代定位算法*

乔 欣1,2,3,常 飞1,2,3,丁恩杰1,2,3*,王桃1,2,3

(1.中国矿业大学 物联网(感知矿山)研究中心,江苏 徐州 221008;2.矿山互联网应用技术国家地方联合工程实验室,江苏 徐州 221008;3.中国矿业大学信息与电气工程学院,江苏 徐州 221008)

针对DV-Hop算法在节点随机分布的网络拓扑环境下存在误差较大的问题,提出了一种基于跳距修正的WSN拟牛顿迭代定位算法(CNDV-Hop)。在详细分析DV-Hop算法过程与误差原因的基础上,提出相应改进:首先设定跳数阈值,对锚节点进行优选;然后采用新的方法校正锚节点跳距,利用对应锚节点跳距的校正值计算节点间的距离;最后用拟牛顿法对未知节点坐标的最小二乘解进行迭代优化。仿真结果表明,本文改进算法能有效地降低估计误差对定位准确度的影响,与现有改进DV-Hop算法相比精度更高。

跳数阈值;DV-Hop定位算法;平均跳距;拟牛顿法

无线传感器网络由布撒在区域内的大量传感节点组成的网络,通常被用于环境监测、智能空间、医疗服务、军事目标跟踪等领域[1]。其中,节点的位置信息是非常重要的,因此,节点定位技术成为WSN中的重要研究课题。

对于大型、不易布置节点的监测网络,能耗是整个网络生存的最关键因素,因此,需要一种能耗低、计算复杂度低、定位精度相对较高的定位技术。DV-Hop是一种典型的无需测距定位算法,具有方法简单,定位精度相对较高、通信开销小等优点[2],该算法被经常用于大型WSN中。但是,在需要高精度定位的灾害环境监测区域下,DV-Hop算法仍然存在不足,目前国内外的研究学者对DV-Hop定位算法提出了许多的改进方案[3]。文献[4]提出了一种改进加权DV-Hop算法,该算法通过减小距离权值而得到定位精度;文献[5]提出了利用RSSI测距技术代替DV-Hop算法中到锚节点一跳距离测量并采用2-D Hyperbolic算法代替三边测量法;文献[6]提出了一种最优节点通信半径的改进方法;文献[7]提出在定位阶段采用人工蜂群的智能算法进行计算。以上改进均是单方面对DV-Hop算法进行改进,并没有综合考虑该定位算法的误差因素。基于此,提出了一种综合的改进方法(CNDV-Hop)。首先简要描述了该方法的过程,然后对其定位误差进行了分析,最后从3个方面分别对DV-Hop算法进行改进,并且与文献[6]、文献[7]进行了仿真对比,在不明显增加节点的计算和通信开销的前提下,CNDV-Hop具有更高的定位精度。

1 DV-Hop定位算法简介

DV-Hop算法是由Niculescu D等[8]人提出的,其基本思想是将未知节点到锚节点之间的距离用网络平均每跳距离和两者之间跳数的乘积表示[9]。如图1所示,在网络拓扑结构中,i,j,k3个节点为锚节点,p为待求未知节点。算法过程如下:

图1 网络结构图

首先,锚节点广播自身信息到整个网络,其他节点能够接收到其ID、跳数、坐标信息。锚节点根据其接收到其他锚节点的信息计算出自身的平均跳距AHD

(1)

最后,当未知节点获得3个或者更多与锚节点的距离时,执行三边定位法或最大似然估计法求解未知节点的估计坐标[10]。

2 DV-Hop误差分析

DV-Hop算法定位误差较大有以下几个原因:

①平均每跳距离

节点间的估计距离采用的是平均每跳距离乘以两者之间的跳数表示,未知节点将最先接收到的锚节点平均跳距信息作为其平均跳距,然而,WSN网络节点随机分布,仅根据单个锚节点的平均跳距并不能代表整个网络的平均跳距,因此,定位精度会受到平均每跳距离值的影响。

②跳数信息

DV-Hop算法测量未知节点与锚节点的距离是通过跳数与平均跳距的乘积计算的,在节点随机分布的网络拓扑环境下,当接收到不合理的跳数值后,不仅对平均跳距有直接的影响,而且会带来累积误差,节点跳数越多,累积误差越大。

③定位计算方法

当平均跳距和跳数信息存在误差时,而两者之间的乘积d也会带来很大的误差。另外,在仿真过程中发现,当ATA为病态矩阵时,通过多边定位法所估计出的未知节点坐标不仅误差很大,而且定位精度的稳定性较差,有时甚至得出错误的结果。

3 CNDV-Hop定位算法

本节中,在不明显增加网络通信量、硬件开销,不改变DV-Hop算法过程的条件下,本文对平均跳距、跳数和定位估计3个因素带来的误差进行了改进。

3.1 跳数优化

在随机的WSN中,节点跳数越多,对距离进行估计产生的误差就越大。本文首先设定跳数阈值δ,当锚节点到未知节点的跳数大于δ时,未知节点舍弃该锚节点的信息,δ通过多次仿真得到经验值。然而,在WSN的定位计算中,锚节点的信息至关重要,当能够通信的锚节点较少或者小于3个时会导致定位精度过低甚至无法定位。因此要选择合适的δ,其相关因素包括:锚节点比例、通信半径、无线传感器网络范围等,具体可参考表1。

表1 跳数和平均跳距改进对精度的影响

3.2 平均跳距的校正

从平均跳距的误差分析和3.1节可知,较为合理的锚节点数量参与定位能够提高定位精度,故提出综合多个锚节点的平均跳距进行改进。假设通过跳数阈值δ限制后,未知节点能够与mδ个锚节点进行通信,结合式(1),则mδ个锚节点的平均跳距值为:

(2)

结合式(2),改进后的锚节点i的平均跳距计算公式如下:

(3)

针对跳数阈值与平均跳距校正的合理性,进行了如下仿真,设置无线传感器网络区域为100×100,锚节点比例为20%。通信半径R变化时,跳数阈值的设定与平均跳距的校正给整个网络定位精度带来的影响。hm表示跳数最大值,APδ表示设置跳数阈值后定位精度提高百分比,APϖ表示平均跳距校正后定位精度提高百分比。

3.3 基于拟牛顿法优化求精

由DV-Hop误差分析可知,多边定位的误差较大[11]。故本文提出采用最小二乘法和无约束拟牛顿法[12]相结合的算法求解未知节点的估计坐标,首先通过最小二乘法获得未知节点的估计坐标,然后把估计坐标作为拟牛顿算法的初值,进一步对未知节点坐标迭代优化。

假设待求未知节点p坐标为(x,y),第i个锚节点的坐标记为(xi,yi),节点p到锚节点i的距离记为di。若WSN中有m个锚节点能够与未知节点p通信,则未知节点p的坐标可以根据式(4)方程组估计得出。

(4)

上述方程组可转换成AX=b的形式,通过最小二乘法解未知节点的估计坐标为:

X=(ATA)-1ATb

(5)

将式(4)转化为求非线性最小二乘优化的问题,即:

(6)

式中,xi,yi分别为锚节点i的横坐标和纵坐标,di为未知节点到锚节点i的距离。对于最优化求解问题,目的就是求出目标函数f(x,y),x∈R+且y∈R+的最优解X*(x*,y*)。我们知道当f(x,y)在X*处取得局部极小值时,需满足:

(7)

3.4CNDV-Hop算法实现步骤

CNDV-Hop算法通过对跳数阈值设定、平均跳距校正,同时将拟牛顿算法引入,克服了DV-Hop算法定位误差较大的缺点。其具体实现步骤如下:

第1步 网络初始化及仿真变量说明。

BorderLength:WSN区域边长

NodeAmount:节点总数

SimulationTimes:仿真次数

AnchorAmount:锚节点数

UNAmount:未知节点数

Hopsthreshold:跳数阈值

R:节点通信半径

gxmax:迭代次数

h(i,j):跳数矩阵

Anchor(2,AnchorAmount):锚节点坐标矩阵

UN(2,UNAmount):未知节点实际坐标矩阵

Dhop(AnchorAmount,1):锚节点平均跳距

第2步 锚节点发送自身信息至网络中。

第3步 通过最短路径法计算出节点间的跳数,锚节点根据式(3)计算改进后的平均跳距,未知节点保存其与锚节点间的最小跳数。

第4步 锚节点将改进平均跳距发送至网络中,设置跳数阈值,优选后锚节点的跳数和平均跳距参与计算未知节点与各个锚节点的估计距离。

第5步 通过最小二乘法计算出未知节点的估计坐标,并将该坐标作为拟牛顿法的初值X(0),对结果进行求精。

第6步 根据式(8)、式(9)、式(10)对该算法的定位精度进行评价。

4 仿真与结果

4.1 仿真环境及评估方法

为了验证算法的性能,本文利用MATLAB 2010b平台对CNDV-Hop算法分析,并同近两年DV-Hop改进方法进行对比。将文献[6]所述方法记为ORDV-Hop,文献[7]所述方法记为ABDV-Hop。仿真环境设置:WSN区域大小为100 m×100 m,节点数目为100个,SimulationTimes为100,迭代次数gxmax为20。仿真相关公式定义如下:

(8)

式中,N为未知节点的个数,K为仿真次数,取100。

②归一化的平均定位误差(NAE)为

NAE=AE/R

(9)

③算法的性能评价,通常使用均方根(root mean square)作为算法性能的评价指标,归一化均方根误差(NRMSE)为:

(10)

式中,e(i)为估计坐标,r(i)为实际坐标,N为未知节点数目,R通信半径。

图2 网络节点分布

4.2 仿真结果分析

图2仿真了网络的节点分布,锚节点比例为20%,其中红色为锚节点,黑色为信标节点。

图3、图4中分别仿真了传统DV-Hop算法与CNDV-Hop算法未知节点的实际位置与估计位置,设置通信半径为30,锚节点比例为20%,跳数阈值为4。从两图中可以看出,改进后的定位精度明显比DV-Hop算法精度高的多。

图3 DV-Hop算法实际位置与估计位置误差

图4 CNDV-Hop算法实际位置与估计位置误差

图5中仿真了4种定位算法锚节点比例与归一化平均定位误差的关系,设置通信半径为30,跳数阈值为4。从图中可以看出CNDV-Hop算法比现有改进算法具有更低的定位误差,比传统DV-Hop算法提高了约40%的定位精度。

图5 归一化平均定位误差与锚节点比例之间的关系

图6 归一化均方根误差与通信半径之间的关系

图6中仿真了4种定位算法通信半径与归一化均方根误差的关系,设置锚节点比例为20%,跳数阈值随通信半径不同,部分设置可参考第1步。从图中可以看出CNDV-Hop算法定位精度更高、稳定性更强。

5 结论

针对传统的DV-Hop定位算法定位精度不高的问题,本文提出了一种基于跳距修正的WSN拟牛顿迭代定位算法。改进后的算法主要是从设定跳数阈值、平均跳距校正、对估计坐标进行迭代优化来进行改进,从仿真结果可以看出,CNDV-Hop算法使得定位的精度和稳定性都有所提高,并且明显降低了WSN的定位误差,该算法并没有改变传统DV-Hop算法的定位过程,且无需额外的硬件支持,是一种理想的与距离无关的定位算法。

[1] Jennifer Yick,Biswanath Mukherjee,Dipak Ghosal.Wireless Sensor Network Survey[J].Computer Networks,2008,52:2292-2330.

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

[3]江禹生,冯砚毫.一种新的DV-Hop定位算法[J].传感技术学报,2011,23(12):1815-1818.

[4]Li Jian,Zhang Jianmin.A Weighted DV-Hop Localization Scheme for Wireless Sensor Networks[C]//Proc of the Eighth IEEE Inter-national Conference on Embedded Computing and IEEE Interna-tional Conference on Scalable Computing and Communications,June,2009:269-272.

[5]刘衍珩,刘炳日,孙大洋,等.WSN中一种DV-Hop定位精度改进算法[J].吉林大学学报(工学版),2010,40(5):763-768.

[6]吴玉成,李江雯.基于最优节点通信半径的改进DV-Hop定位算法[J].华南理工大学学报(自然科学版),2012,40(6),35-42.

[7]李牧东,熊伟,梁青.基于人工蜂群改进算法的无线传感器网络定位算法[J].传感技术学报,2013,26(2):241-245.

[8]Niculescu D,Nath B.Ad Hoc Positioning System(APS)Using AOA[C]//Proceedings of the IEEE Infocom 2003.Francisco(Canada),3:1734-1743.

[9]Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems,2003,22(1-4):267-280.

[10]石为人,贾传江,梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报,2011,24(1):83-87.

[11]嵇玮玮,刘中.DV-Hop定位算法在随机传感器网络中的应用研究[J].电子与信息学报,2008,30(4):970-974.

[12]陈兰平,焦宝聪.非凸无约束优化问题的广义拟牛顿法的全局收敛性[J].应用数学,2005,18(4):573-579.

乔欣(1988-),女,硕士研究生,主要研究方向为无线传感器网络定位与ZigBee通信技术;

丁恩杰(1962-),男,教授,博士,博士生导师,主要研究方向为井下无线传感器网络与矿山物联网,enjied@cumt.edu.cn。

ModifyingAverageHoppingDistancesBasedIterativeAlgorithmforQuasi-NewtoninWSN*

QIAOXin1,2,3,CHANGFei1,2,3,DingEnjie1,2,3*,WANGTao1,2,3

(1.CUMT-IoT Perception Mine Research Center,Xuzhou Jiangsu 221008,China;2.The National and Local Joint Engineering Laboratory of Internet Application Technology on Mine,Xuzhou Jiangsu 221008,China;3.School of Information and Electrical Engineering CUMT,Xuzhou Jiangsu 221008,China)

This paper provided with one modifying average hopping distances based iterative algorithm for quasi-newton in WSN.It put forward improvement based on analysis DV-Hop algorithm progress and source of error:firstly,setting hop threshold,then optimizing anchor nodes;secondly,revising nodes hopping distance with new method and calculating distance between nodes by utilizing adjusted value of the corresponding anchor nodes hopping distances;finally,iterative optimizing least square solution of unknown node coordinates by quasi-newton method.Simulation result shows that the improved algorithm presented in this paper can effectively reduce the influence which evaluated error on location accuracy,and this algorithm is better than the existing improved DV-hop algorithm in precision.

hop count threshold;DV-Hop location algorithm;average hop distance;quasi-newton method

项目来源:国家科技支撑计划项目(2012BAH12B01,2012BAH12B02)

2014-04-07修改日期:2014-05-14

10.3969/j.issn.1004-1699.2014.06.017

TP393

:A

:1004-1699(2014)06-0797-05