基于误差加权的三维双曲线定位算法

2017-05-24任克强

传感技术学报 2017年5期

关键词：定位精度距离定位

任克强,李娜

(江西理工大学信息工程学院,江西赣州 341000)

基于误差加权的三维双曲线定位算法

任克强*,李娜

(江西理工大学信息工程学院,江西赣州 341000)

为了减小三维空间中对未知节点定位的误差,提高三维DV-Hop算法的定位精度,提出一种基于误差加权和三维双曲线定位的三维DV-Hop改进算法。改进算法首先采用误差加权的方法处理未知节点的平均每跳距离,然后分类选择未知节点与锚节点之间的跳段距离,最后将二维双曲线法扩展到三维空间计算未知节点的坐标。仿真实验结果表明,改进算法在三维WSN环境中可以对未知节点进行有效的定位,平均定位误差和定位精度显著优于三维DV-Hop算法,相较于对比文献也有一定的提升,并且锚节点密度和通信半径对平均定位误差和定位精度的影响较小。

无线传感器网络;节点定位;三维DV-Hop算法;误差加权;双曲线定位

无线传感器网络WSN(Wireless Sensor Network)是由多个低成本、低功耗的传感器节点经过近距离通信和数据交换构成的自适应网络[1-2]。这种传感器网络具有感知功能、计算功能、信息处理功能以及无线通信功能,可以对信息进行实时监测和处理,然后传送给观测者[3]。WSN在包括结构监测、环境监测、战场监视和动物跟踪等许多领域被广泛地应用,其使用价值能否成功体现出来,关键在于节点的位置信息是否准确[4],因此,确定事情发生的具体所在地对于传感器节点来说是最根本的功能之一。

WSN定位算法的研究成果众多,但大多是针对二维平面的定位[5-6],对于三维复杂环境空间的定位算法相对较少,而三维环境定位比二维平面定位对于位置信息的要求更加充分,其空间的复杂度和对网络的连通度、密度也相应的增加,因此二维平面情况下的定位算法不能直接应用在三维环境中[7-8]。围绕在三维空间中实现较高精确度的节点定位问题,国内外的相关研究人员提出了众多三维空间节点定位算法。文献[9]基于二维Euclidean算法,把节点距离估算问题转换成求解六面体模型各个顶点间的距离问题,并利用坐标法和四边定位法对未知节点坐标进行确定,可以有效实现三维环境节点定位,但该算法需要节点进行两次洪泛,增加了计算通信量,且该算法的抗干扰性也有待加强。文献[10]将加权平均思想引入到三维DV-Hop定位算法中,建立加权平均跳距的思想来达到减小节点定位误差的目的,但该算法没有考虑三维DV-Hop定位算法在计算求解未知节点坐标时其自身本就存在着较大误差问题。文献[11]将APIT算法延伸至三维空间环境中,形成3D-GPIT算法,通过获取未知节点的最佳估算区域,使用三维网格方法对其估算区域进行优化,有效降低了定位误判的问题,但该算法在节点稀少的条件下不能完成网格定位而失效。文献[12]在三维APIT基础上提出了一种基于多面体质心循环迭代的APIT定位算法,用质心迭代法代替网格扫描法提高算法的计算效率,并且对节点稀少的情况进行再次定位,解决了三维WSN环境中APIT定位算法覆盖率低的问题。文献[13]通过采取粒子群优化技术的惯性权重的方法,对三维DV-Hop算法得到的未知节点估算坐标进行修正,在不增添格外的硬件设施和通讯成本的情形下提升了算法定位精度和稳定性。文献[14]通过MDS-MAP算法对节点的坐标位置进行计算,并且采用更加有效的坐标映射方法来实现更高精度的坐标转化,这使得节点在三维环境定位精度上有很大的提升。文献[15]加入了计算未知节点时出现的偏差值,使用DV-Hop算法中节点间跳数和平均每跳距离的求解方法,并且利用加权质心方法对未知节点估算坐标进行修正,获得了较好的定位性能。

针对三维空间中的节点定位问题,本文在分析和研究经典三维DV-Hop算法的基础上,提出一种基于误差加权的三维DV-Hop改进算法,以改善三维空间的节点定位精度,提高三维DV-Hop算法的定位性能。

1 三维DV-Hop算法分析

1.1 三维DV-Hop算法原理

三维DV-Hop定位算法是由二维DV-Hop定位算法拓展而来,它的基本思想与二维定位算法类似,其定位过程主要分为3个阶段:

①锚节点通过广播的方式在网络中发送自身节点的信息,其中包括自身位置的坐标信息和跳数值信息,并设置为0。接收到此信息的所有节点都仅保存最小跳数信息后,将跳数的值加上1发送给邻居节点,直到全部节点都获得到整个网络的锚节点的最小跳数值。

②获取到整个网络的锚节点具体位置信息和相距最小跳数值后,采用式(1)可以求解出锚节点i的平均每跳距离。

(1)

式中:(xi,yi,zi)、(xj,yj,zj)分别为锚节点i与锚节点j的实际位置坐标,hij是锚节点i与锚节点j(i≠j)两者间的最小跳数值。

然后锚节点将获得的平均每跳距离信息发送到网络当中,未知节点只是保留最开始得到的锚节点数据信息,并发送给邻居节点,再根据到全部锚节点的最小跳数值可以求解其与全部锚节点间的跳段距离。

③当未知节点得到4个或4个以上已知锚节点的具体信息后,选择用极大似然估计法[16]来确定自己的位置坐标。

1.2 三维DV-Hop算法存在的问题

三维DV-Hop算法具有对硬件设施条件要求不高,计算简单等优点,但此算法的定位主要是依靠网络连通度来进行,故在对节点定位时本身就会形成一定误差。

①节点的精度和覆盖率都会因为已知的锚节点密集程度及其分布情况的变化而变化。锚节点位置越密集,分布越均匀,则节点的定位精确度就会越高。而在实际情况下,常常随机的将锚节点安置在被监测的区域中,因此其分布极大可能是不均匀的。另外一方面,锚节点一般是携带GTP定位技术的节点,其费用非常的高,大量且均匀放置锚节点是不经济的。所以,只是靠网络中少数锚节点数据信息来进行定位会有较大误差形成,网络边沿的未知节点也会因为接收到少量锚节点的信息或者接收不到锚节点的信息而不能进行定位,这会降低节点的定位覆盖率。

②未知节点和锚节点用它们间的跳数值乘上锚节点的平均每跳距离来表示它们之间的跳段距离,但在实际环境情况中锚节点到未知节点的途径一般都不成直线,并且节点密度越小折线率越高,估算出来的距离偏差就会越大,定位精度就会越不准确。例如在图1中,S1、S2、S3是3个锚节点,节点A和其他节点是未知节点,如果已知全部锚节点间的实际距离和各节点间的跳数值,那么就可以求解出各锚节点的平均每跳距离。

图1 未知节点与锚节点距离示意图

由式(1)得到S2的平均每跳距离是(40+85)/(2+5)=17.85m,因为A是从距离它最近的锚节点获取平均每跳距离的,所以A到S1、S2、S3的距离分别是:

如假设节点A到S1、S2和S3之间呈一条直线,则实际上A到S1、S2和S3之间的距离分别为88m、48m和68m,那么节点A由跳数值和平均每跳距离相乘得到的距离与实际距离就分别相差16.6m、12.3m和14.45m。由此可见,计算距离与实际跳距有着较大的误差,而且实际节点之间的每一跳距离都不是相等的,因为在节点的通信区域内未知节点相距锚节点的远近程度基本上都不一样,但未知节点从自己得到的信息来考虑都认为自己是在距离锚节点一跳的地方。例如在图2中,假设实心圆点代表锚节点,空心圆点代表未知节点,R代表节点的通信半径,那么节点A的1跳范围如图2所示。

图2 节点的一跳区域示意图

由图2可以看出,节点A到节点B的距离比到节点C的距离要短得多,但是节点A判断节点B、C都在它的一跳位置。根据三维DV-Hop算法计算出来的A到B的跳段距离和A到C的跳段距离相等,但实际上A到B的距离与A到C的距离并不相等,所以求解出的跳段距离和实际距离有着较大的偏差。

③在未知节点获取锚节点的平均每跳距离之后,选择用极大似然估计法来求解得出它的坐标。采用极大似然估计法求解未知节点坐标时,即求解线性方程Ax=b,而两个矩阵A和b都会对未知节点坐标的求解产生很大影响,因为矩阵b中有些未知节点与锚节点的距离偏差比较大,直接用于求解会出现不小的误差。另一方面是由于硬件设备自身的某些缺陷也会对矩阵A造成一定的误差。

2 三维DV-Hop算法的改进

本文为了降低三维DV-Hop算法定位不准确、误差较大两方面的问题,分别从未知节点平均每跳距离、未知节点到锚节点间的跳段距离以及求解未知节点坐标3个方面对三维DV-Hop算法进行改进。

2.1 求解未知节点平均每跳距离的改进

在节点随机放置的WSN环境中,所有锚节点的平均每跳距离误差值都不一样,未知节点仅仅依据距离最近的锚节点来求解其平均每跳距离,求解出来的结果会有较大的误差,而且一个最近的锚节点并不能确切地说明全网实际周边的相关情况。因此,本文算法在计算未知节点平均每跳距离时,将把全部锚节点的平均每跳距离都考虑进去,并采用跳距误差加权策略对接收到的全部锚节点平均每跳距离做加权处理,对误差较小的锚节点赋给较大权值,通过这样的权值处理就可以平衡总体影响未知节点定位误差的因素,从而可以更好地说明未知节点周围网络的情况,以提升算法对节点的定位精度。

如果用(xi,yi,zi)和(xj,yj,zj)分别代表锚节点i和j的实际位置坐标,则锚节点i的平均每跳距离HoTPizei可以用式(1)计算得到。

按照各锚节点间的最小跳数值可以求出锚节点i与j之间的跳段距离:

(2)

已经知道锚节点间的坐标信息,则可以得到锚节点i与j之间的实际距离:

(3)

在WSN中,假定锚节点数量为m,那么通过式(2)中的跳段距离和式(3)中的实际距离可以得到锚节点i的平均每跳距离误差:

(4)

通过式(4)中得到的平均每跳距离误差可以求解出锚节点i的有效平均每跳距离:

HoTPizeeff(i)=HoTPizei+errori

(5)

全部锚节点通过式(4)得到平均每跳距离误差后,相加求其平均值当作该网络的平均每跳距离误差,再对该网络的平均每跳距离进行修正。则全网锚节点平均每跳距离误差:

(6)

网络中如果锚节点和未知节点相距越近,那么它们之间的平均每跳距离误差就会越小,则对未知节点跳段距离的估算就能越准确。假设未知节点M已经得到n个锚节点位置信息,则未知节点M对得到的n个锚节点位置信息赋给不同的权值。对n个锚节点的权值按式(7)所示进行处理:

(7)

最后,未知节点对得到的n个锚节点有效平均每跳距离做出基于wi的加权处理,所以它自身的平均每跳距离:

(8)

2.2 求解未知节点到锚节点间的跳段距离的改进

三维DV-Hop算法中未知节点选择用存在误差的跳段距离来替代节点间的实际距离,这无疑会使得该方法本身就存在误差。本文在求解未知节点到锚节点的跳段距离时,将考虑它们的相关信息,因为在WSN中未知节点与锚节点离得越近其定位就能越准确,所以在求解未知节点到相距1跳的锚节点的距离时使用三维DV-Hop算法的思想来求解,而在求解未知节点到相距非1跳锚节点的距离时则采用以下方法求解。

将未知节点A附近的锚节点按跳数分成1跳锚节点和非1跳锚节点两大类,例如在图3中,C、D都是距离A非1跳锚节点,而B则是距离A的1跳锚节点。

图3 锚节点跳数分类示意图

假定s是离未知节点非1跳锚节点,j是离未知节点1跳的锚节点。Dsj为s与j之间的实际距离,hsj为s与j之间的最小跳数。

对于距离未知节点1跳的锚节点,用式(9)求解它们两者间的跳段距离。

dij=Hi×hij

(9)

对于距离未知节点非1跳锚节点,用式(10)求解它们两者间的跳段距离。

(10)

2.3 求解未知节点坐标的改进

三维DV-Hop算法运用极大似然估计法这一经典方法来求解未知节点位置坐标时,其求解结果会产生较大偏差。本文的策略是将二维双曲线法引入到三维空间中代替原始算法中的经典方法求解节点位置坐标,以进一步提升算法对节点的定位精度。

假设锚节点i的实际坐标是(xi,yi,zi),未知节点的位置坐标是(x,y,z),则它们两者之间的欧氏距离是:

(11)

展开式(11)得:

(12)

(13)

GaZa=Ha

(14)

利用最小二乘法可得:

(15)

最后得到未知节点i的坐标:

(16)

通过双曲线方法,可以避免方程组的直接相减,减少由估距误差带来的累积误差,能够有效提高定位算法的精度。

3 仿真结果及分析

为了测试本文算法的性能,基于Windows7+MATLAB R2015b仿真平台对三维DV-Hop算法、文献[15]算法和本文算法进行仿真比较,并对仿真得出的结果进行对照分析。仿真实验环境:在100 m×100 m×50 m的三维空间环境区域内随机安置500个节点,包括未知节点和锚节点,图4是一次实验的节点随机部署图,图中实心圆点代表未知节点,菱形代表锚节点。

图4 节点随机分布图

(17)

(18)

式中:(xi,yi,zi)和(ai,bi,ci)分别为未知节点i的估算坐标和实际坐标。

图5是在相同场景下三维DV-Hop算法与本文算法对未知节点的定位误差对比图。由图5可以得出,除了极少数的几个点外,本文算法的定位误差显然小于三维DV-Hop算法,且本文算法的定位误差波动也比较稳定。

图5 未知节点定位误差对比图

图6是在通信半径R=30 m,锚节点取从20到45之间变化情形下,三维DV-Hop算法、文献[15]算法和本文算法的定位性能对比曲线。在取定节点总量和通信半径条件下3种算法的平均定位误差和定位精度曲线都随着锚节点数量的不断增加而呈现递减变化,即平均定位误差降低、定位精度提升;当锚节点数量一样时,本文改进算法的平均定位误差和定位精度均比三维DV-Hop算法和文献[15]算法要好,且本文改进算法的平均定位误差曲线和定位精度曲线始终处于最下方。由此可见,本文所提出的算法相比三维DV-Hop算法很显然减小了节点定位误差,提升了算法定位精度,算法性能优于三维DV-Hop算法和文献[15]算法,且节点平均定位误差曲线和定位精度曲线都较为平稳,受锚节点数量的影响较小。

图6 不同锚节点数量的算法定位性能对比曲线

图7 不同通信半径的算法定位性能对比曲线

图7是在锚节点数量为20,通信半径取从20 m到45 m之间变化的情形下,三维DV-Hop算法、文献[15]算法和本文算法的定位性能对比曲线。在取定节点总量和锚节点数量条件下,随着通信半径的不断加大3种算法的平均定位误差都有缓慢增大的趋势,如图7(a)所示,这是因为通信半径的不断加大会使得节点间跳数的误差增大,导致节点平均每跳距离误差增大,所以平均定位误差会随着节点通信半径的加大而有所增大;但3种算法的定位精度都随着通信半径的加大而呈现递减变化,如图7(b)所示。当通信半径一样时,本文改进算法的平均定位误差和定位精度均比三维DV-Hop定位算法和文献[15]算法要好,且本文改进算法的平均定位误差曲线和定位精度曲线同样始终处于最下方。由此可见,本文所提出的算法相比三维DV-Hop算法很显然减小了节点定位误差,提升了节点定位精度,算法性能优于三维DV-Hop算法和文献[15]算法,且平均定位误差曲线和定位精度曲线都比较稳定,受通信半径的影响相对要小一些。

4 结论

分析了三维DV-Hop算法在估算节点跳距和未知节点坐标时存在的缺陷,在此基础上,以降低节点定位误差,提升节点定位精度为目的,提出了一种基于误差加权和三维双曲线定位的三维DV-Hop改进算法。改进算法采用误差加权、锚节点按跳数分类以及三维双曲线定位3种策略对三维DV-Hop算法进行改进,并在节点总量不变、锚节点数量和节点通信半径变化的三维WSN环境下进行了算法定位性能比较仿真实验。从实验数据可以得出,本文改进方案在不增加硬件设施和通信成本的前提下,改进方案的性能均好于三维DV-Hop算法及相关文献,且本文改进方案的平均定位误差和定位精度受锚节点密度和通信半径的影响较小,可以更好的适应随机分布的三维WSN环境。如何进一步改善三维空间的节点定位精度是后续研究的重点工作。

[1] Zhu C,Zheng C L,Shu L,et al. A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks[J]. Journal of Network and Computer Applications,2012,35(2):619-632.

[2] 钱志鸿,王义君. 面向物联网的无线传感器网络综述[J]. 电子与信息学报,2013,35(1):215-227.

[3] Gui L Q,Val T,Wei A,et al. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2015,24(Part B):55-73.

[4] Xu E Y,Ding Z,Dasgupta S. Source Localization in Wireless Sensor Network from Signal Time-of-Arrival Measurements[J]. IEEE Transations on Signal Processing,2011,59(6):2887-2897.

[5] 周玲,康志伟,何怡刚. 基于三角不等式的加权双曲线定位DV-Hop算法[J]. 电子测量与仪器学报,2013,27(5):389-395.

[6] 范时平,罗丹,刘艳林. 基于跳距与改进粒子群算法的DV-Hop定位算法[J]. 传感技术学报,2016,29(9):1410-1415.

[7] 舒坚,刘琳岚,陈宇斌,等. 3D-RABLC:一种基于LQI置信度的三维空间定位求精算法[J]. 通信学报,2012,33(7):125-134.

[8] Zhang B,Fan J,Dai G,et al. A Hybrid Localization Approach in 3D Wireless Sensor Network[J]. Internation Journal of Distributed Sensor Networks,2015,2015:1-11.

[9] 唐良瑞,宫月,罗艺婷,等. 一种基于Euclidean的无线传感器网络三维定位算法[J]. 电子学报,2012,40(4):821-825.

[10] 李琳,赵可,林志贵,等. 基于加权的三维DV-Hop定位算法[J]. 控制工程,2015,22(4):761-764.

[11] 相卫华,贾超,王华奎,等. 无线传感器网络三维APIT网格化算法[J]. 传感技术学报,2012,25(5):639-643.

[12] 胡伟,朱西平,文红,等. 基于四面体质心迭代的三维APIT定位算法研究[J]. 传感技术学报,2013,26(10):1432-1436.

[13] Chen X,Zhang B. 3D DV-Hop Localization Scheme Based on Particle Swarm Optimization in Wireless Sensor Networks[J]. International Journal of Sensor Networks,2014,16(2):100-105.

[14] 张亚杰,段渭军,王福豹,等. 改进的距离重构三维定位算法[J]. 传感技术学报,2014,27(12):1681-1686.

[15] 江禹生,冯砚毫,管芳,等. 无线传感网非测距三维节点定位算法[J]. 西安电子科技大学学报(自然科学版),2012,39(5):140-147.

[16] Safa H. A Novel Localization Algorithm for Large Scale Wireless Sensor Networks[J]. Computer Communications,2014,45(3):32-46.

Three Dimensional Hyperbolic Localization Algorithm Based on Error Weighting

REN Keqiang*,LI Na

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

In order to reduce the error of localization for unknown nodes in the three dimensional space,an improved three dimensional DV-Hop algorithm based on the error weighting and the three dimensional hyperbolic localization was proposed to enhance the localization accuracy of three dimensional DV-Hop algorithm. Firstly,the improved algorithm used the error weighting method to deal with the average per-hop distance of unknown nodes. Then,the hop distance between unknown nodes and anchor nodes was classified and selected. Finally,the two dimensional hyperbolic method is extended to the three dimensional space to calculate the coordinates of unknown nodes. The simulation experimental results show that the improved algorithm can effectively locate unknown nodes in the three dimensional WSN environment,the average localization error and localization accuracy are obviously superior to three dimensional DV-Hop algorithm,compared with comparative literature also has a certain improvement,and anchor node density and communication radius have less effect on the average localization error and localization accuracy.

wireless sensor network;node localization;3D DV-Hop algorithm;error weighting;hyperbolic localization