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

2019年7月July摇2019COMPUTERTECHNOLOGYANDDEVELOPMENT

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

(1.南京邮电大学物联网学院,江苏南京210003;

张欣慧1,熊肖肖2,赵学健2,孙知信2

2.南京邮电大学现代邮政学院,江苏南京210003)

摘摇要:无线传感器网络在监测过程中,节点的位置信息具有重要的作用,没有位置信息的事件是毫无意义的。因此,定位技术在无线传感器网络应用中具有关键作用。文中在分析无线传感器网络中基于费马点模型的定位算法的基础上,结合利用中垂线划分测试三角形平面的思想,提出了一种用于三维传感网定位的VTM-APIT-3D算法。该算法首先利用费马点模型确定所定位节点所在的测试三棱锥,然后在测试三棱锥中使用三角形中线垂面对空间进行划分以提高定位精度。仿真结果表明,与其他使用费马点模型的DFPLE算法和FM-APIT-3D算法相比,该算法在定位精度和网络覆盖率上均有显著提高。当无线通信半径为30时,其定位精度提高至多约17.2%,网络覆盖率始终是100%。关键词:无线传感器网络;三维定位;空间划分;三角形中线;垂面

中图分类号:TP393摇摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇文章编号:1673-629X(2019)07-0060-05doi:10.3969/j.issn.1673-629X.2019.07.012

AnImprovedLocalizationAlgorithmforWirelessSensorNetworks

(1.SchoolofInternetofThings,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China;2.SchoolofModernPosts,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China)

ZHANGXin-hui1,XIONGXiao-xiao2,ZHAOXue-jian2,SUNZhi-xin2

Abstract:Inthemonitoringofwirelesssensornetworks(WSNs),thelocationinformationofnodesplaysanimportantrole,andeventswithoutlocationinformationaremeaningless.Therefore,thelocationtechnologyiscrucialinWSNs.BasedontheanalysisofthelocalizationalgorithmbasedonFermatpointmodelinWSNsandtheideaofdividingthetestingtriangleplanebythemidline,aVTM-APIT-3Dalgorithmforthelocalizationof3Dsensornetworkisproposed.ThisalgorithmfirstusestheFermatpointmodeltodeterminethetriangularpyramidwherethenodeislocated,andthentheverticalplaneoftrianglemidlinetoimprovethepositioningaccuracy.Sim鄄ulationshowsthatVTM-APIT-3DalgorithmcanremarkablyimprovethelocalizationaccuracyandcoverageratecomparedtoDFPLEalgorithmandFM-APIT-3Dalgorithm.Whenthewirelesscommunicationradiusis30,itspositioningaccuracyisincreasedbyatmost17.2%,andthenetworkcoveragerateisalways100%.

Keywords:wirelesssensornetworks;three-dimensionallocalization;spacedivision;trianglemidline;verticalplane

0摇引摇言

无线传感器网络具有低功耗、低成本、分布式和自组织的特征,可以广泛构造信息访问的平台以实现一些新的功能,例如对各种检测对象的信息收集,检测与跟踪指定范围内的复杂目标,等等。为了在无线传感器网络中监测传感器网络的活动情况以实现一些具体的网络操作和网络应用,节点的位置信息非常重要[1]。

事件发生的位置以及节点的信息都建立在监测信息的基础上,毋庸置疑,没有定位信息的监测消息往往是毫无意义的[2]。因此,位置信息在无线传感器网络应用中起到了关键作用。

(ToA)、到达时间差(TDoA)、到达角度(AoA)和接收信号强度指示器(RSSI)等等。这种类型的算法虽然

在现阶段,常见的测距方法包括:到达时间

收稿日期:2018-07-12摇摇摇摇摇摇修回日期:2018-11-13摇摇摇摇摇摇网络出版时间:2019-03-21

基金项目:国家自然科学基金(61373135,61672299);国家自然青年科学基金(61702281,20140883);江苏省基础研究计划(自然科学基金)作者简介:张欣慧(1994-),女,硕士研究生,研究方向为无线传感器网络、软件定义网络;赵学健,副教授,硕导,通信作者,CCF会员

(88401M),研究方向为无线传感器网络、大数据及物联网关键技术;孙知信,教授,博导,研究方向为计算机网络与安全、多媒体通信、移动互联网。

网络出版地址:http://kns.cnki.net/kcms/detail/61.1450.TP.20190321.0909.022.html

(BK20140883,BK201404,BK20150869);江苏省研究生科研与实践创新计划项目(KYCX17_0773)

摇第7期摇摇摇摇摇摇摇摇摇摇摇摇摇张欣慧等:一种改进的无线传感器网络定位算法·61·

精度较高,但同时也带来了硬件要求极高和通信消费严重等问题。因此,这些方法并不适用于低能耗或低成本的应用程序。具体的定位算法可以根据节点处理信息的方式划分为集中式定位和分布式定位,或根据是否需要测量距离或角度信息划分为基于测距的定位和无需测距的定位。无需测距的定位算法不需要测量绝对距离或方向,依靠网络连通性的信息或其他方法即可完成定位。常见的此类算法有凸定位算法、质心定位算法、DV-hop定位算法、不定型定位算法、APIT算法等。

立方体空间中,即可借助正中面和通信半径去除无节点包含的立方体,以缩小节点的定位范围。文献[10]在APIT中使用蒙特卡洛方法和RSSI滤波器采样方10%。文献[11]提出一种融合了APIT,RSSI和PSO且无需测距的定位算法。该算法在信标节点交换信息的过程中对信标节点的相邻节点的RSSI测量结果进行加权,基于强度来测量距离。通过PSO和成本函数对相邻节点的位置和速度矢量连续迭代,最终使用APIT通过PSO计算的信标节点和相邻节点的距离来法,仿真结果表明MC-APIT的最低位置误差高达

文中首先介绍了APIT算法的演变史并总结了每种算法的优缺点,指出了未来的研究方向。在此基础上,详细分析了费马点模型及基于中垂线分割的PB-APIT算法的思想,提出了一种基于三角形中线垂面分割的APIT-3D的改进算法(verticalplaneoftrianglemidline-approximatepoint-in-triangulationtest-3D,VTM-APIT-3D),并通过仿真来验证和评估算法的性能。

1摇相关技术研究

APIT算法于2003年提出

[3]

括:(1)锚节点稀疏时对网络覆盖率影响较大,存在的一些问题包

,网络边缘处的未知节点定位难,可扩展性较弱;(2)需要判断测试三角形内的静止未知节点是否出现假阳性;(3)重叠区域中节点的定位精确度需要改进。对于APIT算法存在的问题,提出了一些改进算法:文献[4]提出了一种基于三角形重心扫描的改进APIT算法,显著地提高了节点的平均精度。文献[5]提出了近似三角形内点APIT定位算法和DV-HOP定位算法相结合的混合定位算法,并证明了其有效性。文献[6]将未知节点升级为锚节点,提出了一种基于中垂线分割的算法,命名为PB-APIT。三角形被每一边的垂直平分线划分为4或6个子区域,通过检测的信号强度来确认未知节点位于某一个子区域,该方案使定位精度大约提高18%,解决了问题1;文献[7]降低了“In-To-OutError冶和“Out-To-InError冶误判的可能性,以增加判断的正确性;文献[8]提出将重叠区域划分为多个子区域以减小三角形区域的大小,解决了问题3。然而,由于无线传感器网络的节点是随机分布的,网络拓扑结构的建立相当困难,上面讨论的改进算法只能分析一些特殊情况,随机性问题仍然是一个难点。

此外,现实中的无线传感器网络往往被布局在复杂的三维地形中,为了实现三维环境下更为精确的节点定位,一些文献对二维的APIT算法进行了改进,将其扩展到三维定位上来。文献[9]在APIT-3D算法中使用了正中面的概念。如果传感器网络部署在近似

计算未知节点的坐标。文献[12]认为APIT算法的网络覆盖率过低,因此提出了结合DV-hop的APIT算法,改进后的算法解决了未知节点周围的邻居信标节点少于三个就无法定位的问题。实验结果表明,该算法的定位精度提高了7.4%,网络覆盖率提高了31郾了基于费马点分离的3%。通过对这些研究的深入分析FM-APIT-3D算法,文献,利用费马点[13]提出将大三棱锥划分为四块小三棱锥。当无线通信半径为盖率始终是30时,该算法的定位精度提高至多约100%。

17.2%,网络覆上述文献均为了解决无线传感器网络中更为精确的节点定位问题,但是以上大部分定位算法仅适用于二维平面中,部分可用于三维环境中的定位算法也存在定位精度与网络覆盖率较低的问题。故文中利用数学模型对现有的三维定位算法进行改进,以提高定位精度与网络覆盖率。

2摇2.1摇基础模型分析

费马点模型

费马点是三维空间内的特殊点,类似于质心和内部中心。如果存在一个点,它到某有限点集的所有顶点的距离和最小,这一点便被称为费尔马点。在任意三棱锥中,费马点必然唯一存在且可以将三棱锥划分为四个子三棱锥。建立三维坐标系后,三棱锥的四个顶点为A(xD(x,1,y1,z1)、B(x2,y2,z2)、C(x3,y3,z3)ìy4

x-x,y、44,z4),可以通过式1计算费马点F(xFF,zF):

ïiïï移

i=1(x-xi)2+(y-yi2=0ïí4y-y)2+(z-zi)iï移i=12ï(x-xi)+(y-y2z=0i4)+(z-i)2(1)ïz-zïi

î移

i=1文献[14](x提出的-xi

)2+(y-y=iFM-APIT)2+(z-zi-3D算法和文献)2

0

[12]提出的DFPLE算法均使用费马点模型定位未知节点。除此之外,费马点模型还可被用于其他算法中。文献

·摇62摇·摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第29卷

[15]提出了一种允许计算是从云跨越到网络的无线传感器网络分布式平台,它减少了传感器网络中的传输、中间网络以及云基础设施。该平台是完全分布式的,允许均匀网络中的每一个节点接受来自用户的连续查询,找到所有满足用户查询的节点,再找到一个最佳节点(费马点)对网络进行查询,并为用户提供结果。文献[16]提出了一种基于三角剖分的bmO(nlogn)最短路径算法,结合改进的Dijkstra算法和费马点构建一个低能见度图,可以在较短的时间内计算出近似最短路径。文献[17]提出利用费马点进都大于或小于未知节点所接收到的,则该未知节点位于测试三角形内;反之,则位于测试三角形外。

(3)如果未知节点位于某测试三角形的内部,则

利用测试三角形三边的中垂线对测试三角形进行分割。对于直角三角形和钝角三角形,可被分割为四个小区域;对于锐角三角形,可被分割为六个。

(4)由于已经比较过未知节点从测试三角形的三

个锚节点接收到信号的强弱,故可以直接判断出未知节点位于哪个小区域内。

PB-APIT算法与APIT算法的不同之处在于,有行3D注视定位,该方法使用基于3D重建场景的激光雷达对一个自由漫游的眼动仪进行定位,提供了在复杂的静态环境(例如犯罪现场)中进行搜索任务的策略。

以上算法均通过使用费马点划分空间来达到优化定位模型的目的,但仍存在一些问题:

但因分割前后均使用(1)费马点模型借助费马点来估计节点的位置APIT-3D算法来判断未知节点,的有效范围,算法过程重复且单一。

三棱锥的有效范围内(2)费马点模型多次把未知节点估计在一个形为

,再通过计算这些三棱锥重叠范围的质心来估计未知节点的坐标。由于同为三棱锥的估计范围容易造成累积误差,导致定位精度较低。

概率会少于四个(3)未知节点通信范围内的邻居锚节点有很大的

,这会严重影响定位精度或导致网络覆盖率降低。锚节点的密度是影响定位精度的关键因素,锚节点越多,定位精度越高,但单纯地添加锚节点又会增加能耗和成本。

的未知节点来模拟运动(4)APIT算法选择周围邻居节点密度相对较高

。当未知节点周围的邻居节点密度较低时,势必会影响到算法的实施过程。

因此,文中提出一种新的使用费马点模型的三维定位算法,其定位精度和网络覆盖率与FM-APIT-3D算法和DFPLE算法相比均有所提高。2.2摇PB-APIT算法

PB-APIT算法针对二维的APIT算法进行改进,是一种仅适用于二维平面的二维定位算法。该算法的执行步骤如下:

邻居节点交换各自从测试三角形的三个锚节点接收到(1)第一步与APIT算法相似,未知节点与周围的

的信息,比较二者接收到的信号强弱,也顺便比较未知节点自身从测试三角形的三个锚节点接收到的信号强弱。

的内部或外部(2)利用PIT。若未知节点周围存在一个邻居节点算法判断未知节点位于测试三角形

,它接收到的来自测试三角形的三个锚节点的信号强度

效区域不再是三角形而是分割后的小区域,求出所有小区域的重叠区域,其质心即为未知节点的坐标。有效区域从三角形到多边形小区域的改变,减少了累积误差的产生,提高了定位精度,有着较好的使用前景。但由于现实中的无线传感器网络往往被布局在复杂的三维地形中,二维的PB-APIT算法在现实场景中使用受限,故文中将适用于三维环境的费马点模型与PB-APIT算法中的分割思想结合,提出一种基于三角形中线垂面分割的APIT-3D的改进算法(简称VTM-APIT-3D)。

3摇3.1摇VTM-APIT-3D算法流程

算法

知节点的三棱锥(1)通过执行。

APIT-3D算法找到所有包含有未点,将该点链接到其他四个顶点(2)在某一三棱锥中找到一个名为费马点的特殊

,把三棱锥分割成四个部分,然后通过APIT-3D算法判断哪个子三棱锥中包含有未知节点。

角形(3),取其任意一边作该边的中线在该子三棱锥内,找到顶点不含费马点的三,再过这条中线作三角形面的中线垂面,把该三棱锥划分为两部分。

得出未知节点从该三角形的三个锚节点接收到信号的

(4)之前执行步骤2中的APIT-3D算法时已经

强弱,根据信号强弱判断未知节点位于中线垂面两侧的哪一侧。若存在两个锚节点接收到的信号强度一样大的情况,则可认为未知节点位于中线垂面两侧的任意小区域中。

分割小区域(5)再通过同样的方法找到其他包含未知节点的

,通过求这些不规则小区域重叠范围的质心来估计未知节点的坐标。3.2摇三角形中线垂面的定义

VTM-APIT-3D算法中所提到的三角形中线垂面是指在某三角形的任一边作它的中线,然后过这条线作一个与该三角形所在平面垂直的面,这个面便被称为三角形中线垂面。如图1所示,三角形的三个顶

摇第7期摇摇摇摇摇摇摇摇摇摇摇摇摇张欣慧等:一种改进的无线传感器网络定位算法·63·

点坐标分别为A(x1,y1,z1),B(x2,y2,z2),C(x3,y3,z3),M为BC的中点。

点),则所有未知节点的平均定位误差如下:

M

直线AM的方程可简写为:x-mx1=y-ny1=z-q

z1

(2)寅

平面ABC的法向量可简写为:n1=(a,b,c)

(3)

三角形中线垂面AMPQ的方程为:

nx+(nqanc--mqbqb-m)y-n2nca--mnbqb

z-nx1+

my1-nqanc--mqbqby1+n2nca--mnb

qbz1

=0

(4)

如图1所示,三角形ABC的中线为直线AM,其中线垂面为面AMPQ。通过APIT-3D算法已得知未知节点N位于三棱锥F-ABCN内,且已比较过未知节点N从三角形ABC的三个锚节点接收到信号的强弱。若锚节点B接收到的来自未知节点N的信号强度比锚节点C接收到的信号强度都大,则N位于中线垂面偏B的一侧;反之,N位于中线垂面偏C的一侧。

AQFBDMNPfermat-pointCactualpoint图1摇三角形中线垂面分割模型

4摇实验仿真和结果分析

本节对VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能进行详细的对比和分析。仿真模拟实验在Intel双核2.3GHzCPU,4GB内存,Matlab2014a的平台上进行。所采用的网络布局为随机分布在100m伊100m伊100m大小的立方体网络中的200个节点,并选中其中N个节点作为锚节点,其余为未知节点。4.1摇性能评估

算法改进的目的之一就是提高定位精度,定位精度由定位误差判断,定位误差越小,定位精度越高。未知节点i的定位误差计算公式如下:

Error(i)=

(xi-act-xi-est)2

2

R

+(yi-act-yi-est)

其中,(x(5)

i-acti-acty,y)为节点i的实际位置;(xi-est,i-est)假设该网络中一共有为节点i的估计位置M;R个节点为节点,其中i的通信半径N个为锚节

。

点(i=1至i=N为锚节点,i=N+1至i=M为未知节

Averageerror=

i移=N+M1

Error(-N

i)

(6)

下文从定位精度与网络覆盖率的角度,比较VTM-APIT-3D算法、DFPLE算法和FM-APIT-3D算法的性能。

4.2摇VTM-APIT-3D算法仿真结果

取随机分布在100m伊100m伊100m大小的立方体网络中的200个节点进行仿真实验,其中20个节点为锚节点,其余为未知节点。定位结果如表1所示。

表1摇定位结果分析(R=15)

定位误差节点数目0臆0.1

150.141.1~0.5.50~1.048逸~1.15.511摇较高摇从表,所有的未知节点都能被定位且定位误差较小1可以看出,VTM-APIT-3D12

算法定位精度,因此该算法在优化定位方面效果较为理想。4.3摇不同锚节点数量下的定位精度

如图2所示,当节点通信半径R=16,且锚节点的

数目N从1逐渐增加到50时,三种算法的定位精度均有所提高。由于参考节点数量和测试三棱锥数量的增加,未知节点定位的估计范围被缩小,定位精度自然就提高了。此外,锚节点对节点定位的可能性有直接影响。当锚节点数量较少时,VTM-APIT-3D算法的定位精度明显优于DFPLE算法和FM-APIT-3D算法。VTM-APIT-3D算法改进了定位模块的划分,缩小了定位的估计范围,加快了定位速度。定位的估计范围可减少至其他算法的二分之一。更重要的是,VTM-APIT-3D算法可以解决无法定位的情况,所以定位精度有较大提高。

1.00.80.60.40.20图2摇不同锚节点数量下的平均定位误差4.4摇不同通信半径下的定位精度

如图3所示,当锚节点数量N=18,且节点通信半径R从1逐渐增加到30时,三种算法的平均定位误差都快速降低。这是因为R的增大使未知节点可以与更

·摇摇·摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第29卷

多的锚节点进行通信,所以测试三棱锥的数量不断增长,节点的估计范围逐渐减小。由于节点通信半径的大小对定位精度的影响尤为明显,可以得出结论:VTM-APIT-3D算法的定位精度明显优于DFPLE算法和FM-APIT-3D算法。随着R的增加,一跳通信范围内的锚节点数目也会更多,VTM-APIT-3D算法获得的测试三棱锥数量也更多。当R=30时,VTM-APIT-3D算法的定位精度提高了约17.2%。

2.01.5[5]摇刘春刚,刘松林,杨文超,等.无线传感器网络中基于APIT

学报,2017,15(3):432-437.

[6]摇YANGJ,LIUF.AmodifiedlocalizationalgorithmofAPIT

与DV-HOP的混合定位算法[J].太赫兹科学与电子信息

basedonperpendicularbisectorfeatureforwirelesssensornetwork[J].ChineseJournalofSensorsandActuators,

[7]摇WANGJizeng,JINHongxu.ImprovementonAPITlocaliza鄄

tionalgorithmforwirelesssensornetworks[C]//Internation鄄alconferenceonnetworkssecurity,wirelesscommunicationsandtrustedcomputing.Wuhan,Hubei,China:IEEE,2009:2008,21(8):1453-1457.

1.00.50图3摇不同通信半径下的平均定位误差

5摇结束语

文中提出利用中线垂面切割三维区域的思想,减少了使用费马点模型的算法中多次把未知节点估计在三棱锥形状的有效范围内造成的累积误差。仿真结果表明,与其他使用费马点模型的DFPLE算法和FM-APIT-3D算法相比,利用VTM-APIT-3D算法在三维环境中对未知节点进行定位,定位精度和网络覆盖率均有明显提高。当无线通信半径为30时,其定位精度提高至多约17.2%,网络覆盖率始终是100%。当然,该算法相对于DFPLE算法和FM-APIT-3D算法而言时间复杂度较高,网络能耗也有所增加,今后的研究方向应在提高定位精度和网络覆盖率的同时注重减少定位所需的能量消耗。

参考文献:

[1]摇PANDEYanddatagatheringO,MAHAJANoversmallA,HEGDEworldWSNRM.withJointoptimallocalization

dataMULEallocation[J].IEEETransactionsonVehicularTech鄄nology,2018,67(7):6518-6532.

[2]摇LUcymonitoringM,ZHAOandX,HUANGrescueinY.disasterFastlocalizationscenariosbasedforemergen鄄

onWSN

[icsC]and//Internationalvision.[s.l.conference]:IEEE,2017:1-6oncontrol.

,automation,robot鄄[3]摇HElocalizationTian,HUANGschemesChengduinlarge,BLUMscalesensorBM,etnetworksal.Range[C-free

]//Proceedingsofthe9thannualinternationalconferenceonmobilecomputingandnetworking.SanDiego,CA,USA:ACM,2003:81-95.

[4]摇周APIT摇勇无线传感器网络自定位算法,夏士雄,丁世飞,等.基于三角形重心扫描的改进

[J].计算机研究与发展,2009,46(4):566-574.

[8]摇VIVEKANANDAN719-723.

beaconslocalizationVfor,wirelessWONGsensorVWS.networksConcentric[C]/anchor

/IEEEinternationalconferenceoncommunications.Istanbul,Tur鄄key:IEEE,2006:3972-3977.

[9]摇刘志强[J].计算机工程,王行甫.,2010,36(14):90-92基于中垂面分割的WSN.三维定位方法[10]WANGmethodofJialocalization,FUJingqi.algorithmResearchforonwirelessAPITandsensorMontenetworks

Carlo

[linM:]Springer//Life,2010:128-137systemmodeling.

andintelligentcomputing.Ber鄄[11]JAINtionalgorithmS,SINGHinAwireless,KAURsensorA,etnetworksal.Improved[C]APIT//International

localiza鄄

conferenceonsignalprocessing,computingandcontrol.So鄄lan,India:IEEE,2017:77-81.

[12]ANTHRAYOSEproximatepointinS,triangulationPAYALA.(ComparativeAPIT)andDVanalysis-HOPofalgo鄄ap鄄

rithmsforsolvinglocalizationprobleminwirelesssensornet鄄works[C]//Internationaladvancecomputingconference.[13]XIONG[s.l.]:tionalgorithmXiaomingIEEE,2017:372-378of,APITYANbasedChuan..

onThreefermat-dimensional-pointdividedlocaliza鄄

forwirelesssensornetworks[C]//Seventhinternationalsympo鄄siumoncomputationalintelligenceanddesign.Hangzhou,China:IEEE,2014:521-524.

[14]HUANGdistributedPfermatH,CHEN-pointJLlocation,LAROSAforYwirelessT,etal.sensorEstimationnetwor鄄of

king[J].Sensors,2011,11(4):4358-4371.

[15]KOLCUNnodediscoveryR,BOYLEalgorithmD,MCCANNfordistributedJA.Optimalcomputingprocessing

inIoT[SeoulC]/,/5SouththinternationalKorea:IEEEconference,2015:72-79onthe.

internetofthings.[16]JANrithmGbasedE,SUNonCdelaunayC,TSAIWtriangulationC,etal.An[shortestJ].IEEEpath/ASME

algo鄄

TransactionsonMechatronics,2013,19(2):660-666.[17]PIESZALAtionandvisualizationJ,DIAZGusing,PELZLiDARJ,etal.-based3Dgaze3Dreconstructionspointlocaliza鄄

[applications.C]//BiennialCharlestonACMsymposium,SouthCarolinaoneye:trackingACM,2016:201research&-204.