基于移动锚节点与多级通信的三维传感器网络节点自定位算法研究*

景秀眉,张仁贡

(1.浙江同济科技职业学院信息系,杭州 311231;2.浙江同济科技职业学院机电系,杭州 311231)



基于移动锚节点与多级通信的三维传感器网络节点自定位算法研究*

景秀眉1*,张仁贡2

(1.浙江同济科技职业学院信息系,杭州 311231;2.浙江同济科技职业学院机电系,杭州 311231)

在基于移动锚节点的三维传感器网络节点自定位算法SNLSFA(Sensor Node Localization Scheme based on Flying Anchors)的基础上,提出了一种新的基于移动锚节点与多级通信的三维传感器网络节点自定位算法SNLSFAMC(Sensor Node Localization Scheme based on Flying Anchors and Multi-level Communication)。首先由移动锚节点提供3个或4个辅助定位点,再由辅助定位点得到两条非平行线段,然后过线段中点分别做垂直于线段的平面,经两平面相交后得到一条经过待定位节点的直线,最后利用辅助定位点与待定位节点之间的距离作为通信半径即可得到待定位节点的位置。仿真结果表明,与SNLSFA相比,在相同锚节点数量下,SNLSFAMC提高了定位精度,且在相同定位精度下,SNLSFAMC降低了对锚节点数量的需求,提高了算法的响应时间。

移动锚节点;多级通信;三维节点自定位

无线传感器网络WSN(Wireless Sensor Network)是一种传感器节点通过自组织方式快速形成的分布式网络。各个节点采集的数据必须结合其位置信息才有意义,且网络的覆盖控制、目标跟踪等都依赖于对各个节点的有效定位[1-7]。因此,如何确定节点的自身位置是传感器网络的一项重要支撑技术。

现有的定位技术大多使用安装GPS的锚节点为待定位节点提供位置信息,根据锚节点是否移动,定位算法可分为基于静态锚节点和基于移动锚节点的定位。基于静态锚节点的定位算法中,为完成对整个网络未知位置节点的定位,需要布设较多的锚节点,大大增加了整个网络的成本以及定位算法的计算负荷和网络的通讯负荷[8-12]。基于移动锚节点的定位算法中,由于锚节点可自由移动,因此仅需布设较少的锚节点,降低了定位算法对锚节点密度的依赖程度,且能降低网络拓扑结构复杂度及网络能耗[13-15]。因此利用移动锚节点辅助定位已成为节点自定位算法的重要研究方向。

Zhang等人提出了一种Landscape-3D空间定位算法[16],采用一种辅助定位装置LA(Location Assistant)在监测区域上空飞行并周期性广播自身位置信息,待定位节点接收信息后采用RSSI技术测量其与LA之间的距离,进而计算出自身位置。

Fu Y等人提出了一种基于单个移动锚节点的与测距无关的三维节点自定位算法[17],锚节点遍历整个三维空间收集待定位节点的信息,并根据移动模型计算节点位置,当锚节点再次穿越待定位节点的通信球体时,实现对待定位节点的再定位。

Yu等人提出了一种协作定位算法[18],传感器节点从移动锚节点组接收消息并估计位置,移动锚节点组由3个移动锚节点组成,每个锚节点分别位于等边三角形的一个顶点,定位精度与锚节点数量成正比。算法要求锚节点间具有较强的协调能力,且锚节点组的成本较高。

Chia-Ho Ou等人[19]提出了一种基于移动锚节点的二维传感器网络节点自定位算法,由锚节点的移动特性求出待定位节点通信圆周上的临界通信点,并利用圆周上的两个临界通信点作线段,然后作该线段的中垂线,由两条中垂线相交求出待定位节点的估计位置。在此基础上,Chia-Ho Ou提出了基于移动锚节点的三维传感器网络节点自定位算法SNLSFA(Sensor Node Localization Scheme based on Flying Anchors)[20],其原理与文献[19]的算法相似,亦是利用两条垂直于通信球内切圆平面的直线相交进而得到待定位节点的估计位置。与其他利用移动锚节点的三维传感器网络节点自定位算法相比,SNLSFA只需移动锚节点与待定位节点之间的通信信息便可估计出待定位节点位置,使其在小范围的三维传感器网络节点自定位应用中有较大优势。

但是SNLSFA存在以下问题:①定位精度依赖于锚节点密度;②定位需要较长时间,实时性不高;③依靠两垂线的交点得到待定位节点位置,实际的通信模型中节点的通信范围并不一定是完美的球形,即算法得到的两条垂线不一定相交,使定位精度受到影响。

本文在SNLSFA的基础上提出了一种基于移动锚节点与多级通信的三维传感器网络节点自定位算法SNLSFAMC(Sensor Node Localization Scheme based on Flying Anchors and Multi-level Communication),通过移动锚节点提供3个或4个非共面的辅助定位点,由辅助定位点得到两条非平行线段,过线段中点分别作垂直于线段的平面,经两平面相交得到一条经过待定位节点的直线,利用辅助定位点与待定位节点间的距离为通信半径得到待定位节点的位置。避免了SNLSFA中两直线不相交的情形,同时SNLSFAMC只需3个临界通讯信息点即可开始定位,与SNLSFA相比减少了一个临界通讯信息点,并且SNLSFAMC将待定位节点的通讯半径分为两级,使锚节点在穿越待定位节点通信覆盖范围时多了一次获得待定位节点临界通讯信息点的机会,降低了对锚节点数量的需求并提高了算法响应时间。仿真结果表明,在相同的锚节点数下,相对于SNLSFA,SNLSFAMC的定位精度明显提高,且在相同定位精度下,SNLSFAMC降低了对锚节点数量的需求,提高了算法的实时性。

1 算法原理与流程

1.1 算法原理

SNLSFAMC是一种基于移动锚节点与多级通信的三维空间节点自定位算法,与SNLSFA类似,算法分为准备阶段与定位阶段。

1.1.1 准备阶段

假设节点发射功率可调节,且分为两级,Ⅰ级通信半径为50 m,Ⅱ级通信半径为100 m,如图1所示。

图1 节点通信级别图

图2 锚节点运动轨迹图

同时假设锚节点可在监测区域内自由移动,其运动轨迹如图2所示,当锚节点进入或离开待定位节点的通信范围时,待定位节点记录锚节点在t1,t2,t3,t4时刻的位置,分别以A,B,C,D四点表示。当A,B,C,D四点在同一平面时,其坐标的求解过程与SNLSFA类似,在此不再赘述(详见文献[20])。当A,B,C,D四点不在同一平面时,SNLSFAMC进入定位阶段。

1.1.2 定位阶段

(1)

(2)

图3 SNLSFAMC定位原理图

由式(3)得到经过点S1且垂直于向量AB的平面方程N1:

(3)

同理,已知向量CD及其中点S2,由式(4)得到经过点S2且垂直于向量CD的平面方程N2:

(4)

由于点S为待定位节点通信球的球心,因此线段SA与SB长度相等,且点S1为线段AB的中点,根据等腰三角形特性可知,线段SS1垂直于线段AB,如图4所示。

图4 线段垂直于线段AB图

由于线段SS1经过点S1,因此SS1必定在经过点S1且垂直于线段AB的平面N1上,即待定位节点通信球心在平面N1上。同理,线段SS2必定在经过点S2且垂直于线段CD的平面N2上,即待定位节点通信球心同样在平面N2上,因此点S位于平面N1与N2的相交线上。

联立式(3)与式(4)可得出平面N1与N2的相交线的一般方程,如式(5)所示:

(5)

进而得到直线l的方向向量l(i,j,k),如式(6)所示:

(6)

取直线l上的任意一点P(xp,yp,zp)代入式(6)可得到直线对称方程,如式(7)所示:

(7)

已知点A及直线l的方向向量l(i,j,k),即可求出经过A点并且垂直于直线l的平面NT:

NT:i(x-xa)+j(y-ya)+k(z-za)=0

(8)

联立式(7)与式(8)得到平面NT与直线l的交点的坐标,这里记为点H(xh,yh,zh):

(9)

根据点A坐标及三维空间中点到直线的距离公式,得到点A到直线l的距离da,则圆心的坐标如式(10)所示:

(10)

同理,可求出B点在直线l上的投影点Q的坐标如式(11)所示:

(11)

根据点B坐标及三维空间中点到直线的距离公式,得到点B到直线l的距离db,则圆心坐标如式(12)所示:

(12)

联立式(10)、(12)得到待定位节点的估计位置(xs,ys,zs),定位过程结束。

从上述SNLSFAMC的算法原理可以看出,通过移动锚节点提供3个或4个非共面的辅助定位点,由辅助定位点得到两条非平行线段,过线段中点分别作垂直于线段的平面,经两平面相交得到一条经过待定位节点的直线,利用辅助定位点与待定位节点之间的距离为通信半径即可得到待定位节点的位置。避免了SNLSFA中出现两直线不相交的情形,同时SNLSFAMC只需3个临界通讯信息点即可开始定位,与SNLSFA相比减少了一个临界通讯信息点的需求,并且SNLSFAMC将待定位节点的通讯半径分为两级,使锚节点在穿越待定位节点通信覆盖范围时多了一次获得待定位节点临界通讯信息点的机会,降低了对锚节点数量的需求,提高了算法实时性。

1.2 算法流程

2 算法仿真与分析

2.1 仿真参数设置

为分析SNLSFAMC的有效性,对SNLSFAMC与SNLSFA的相对定位误差、定位时长、可定位节点数等指标进行仿真、分析和比较。节点广播时隙、锚节点运动速度均参照文献[18],其他参数如表1所示。

表1 仿真参数设置

相对定位误差定义为:

(13)

2.2 仿真算例

SNLSFAMC与SNLSFA都需要锚节点反复穿越待定位节点的覆盖空间以帮助待定位节点获取辅助定位信息。仿真时,设置锚节点每0.3 s随机改变一次运动方向,以此完成遍历整个三维空间的运动。当锚节点为50个,算法运行60 s后的锚节点运动轨迹如图5所示,可以看出锚节点几乎遍历了整个三维空间。

图5 锚节点运动轨迹图

图6为SNLSFAMC与SNLSFA的相对定位误差随锚节点数量变化对比图,可以看出SNLSFAMC与SNLSFA的相对定位误差均随锚节点数量增加而下降,SNLSFAMC的相对定位误差始终小于SNLSFA,说明SNLSFAMC对锚节点密度依赖较小,相对于SNLSFA,达到相同的定位精度,需要更少的锚节点。这是因为SNLSFAMC引入了通信半径分级机制,当锚节点穿过待定位节点通信范围时,锚节点提供了两次相对位置信息,实现了对锚节点的再利用,而在SNLSFA中,每次锚节点穿过待定位节点通信范围时,只提供一次相对位置信息。因此在相同的锚节点数量下,SNLSFAMC中待定位节点获得的辅助定位信息更丰富,定位更准确、相对定位误差更低。

图6 相对定位误差随锚节点数量变化对比图

图7为SNLSFAMC与SNLSFA定位网络95%以上待定位节点所需时间随锚节点数量变化对比图,可以看出,SNLSFAMC与SNLSFA完成定位所需时间均随锚节点数量增加而减少。当锚节点数量小于210个时,在相同的锚节点数量下,SNLSFA定位所需时间始终大于SNLSFAMC,当锚节点数量为10个时,SNLSFA定位95%待定位节点所需时间在140 s左右,而SNLSFAMC定位95%待定位节点所需时间在100 s左右。当锚节点数量大于210个时,两者定位所需时间基本相同。这是因为SNLSFAMC中引入了通信半径分级方法使得锚节点得以再次利用,且只需3个辅助定位点即可开始定位,缩短了定位时间,而SNLSFA需要4个辅助定位点才可开始定位,因此在相同锚节点数量下,SNLSFAMC定位所需时间小于SNLSFA所需时间。

图7 算法定位时长随锚节点数量变化对比图

图8 已定位节点数量随算法执行时间变化关系图

图8为当锚节点数量为50个时,SNLSFAMC与SNLSFA已定位节点数量随算法执行时间变化对比图,可以看出,当算法运行相同时间时,SNLSFAMC完成定位的节点数量始终大于SNLSFA。当算法运行10 s时,SNLSFAMC定位了近150个节点,SNLSFA定位了约100个节点。当算法运行50 s时,SNLSFAMC定位了约470个节点,SNLSFA法定位了约420个节点。这是因为SNLSFAMC只需3个辅助定位点节点即可开始定位,而SNLSFA需要4个辅助定位点才开始定位。因此算法开始运行的一段时间内,SNLSFAMC所定位的节点数量要多于SNLSFA所定位的节点数量。当算法运行时间大于50 s后,SNLSFAMC与SNLSFA所定位的节点数量差距逐渐缩小且定位增速越来越慢。这是因为无论SNLSFAMC还是SNLSFA,随着算法的运行网络中已定位的节点越来越多,网络所能提供的辅助定位点信息也越来越丰富,导致两者可定位节点数的差距越来越小,同时由于在前面的一段时间内锚节点所遍历的区域内待定位节点多数已被定位,剩余的待定位节点需要靠锚节点运动至某些角落区域方可定位,导致可定位节点数的增速越来越慢。

图9为锚节点数量为50个、节点广播时隙为0.3 s时,SNLSFAMC与SNLSFA的相对定位误差随锚节点运动速度变化对比图,可以看出,SNLSFAMC与SNLSFA的定位误差均随锚节点运动速度增大而增大。这是因为当节点广播时隙为0.3 s、锚节点速度为10 m/s时,锚节点每次在时隙中的运动距离为3 m,因此辅助定位节点位置的误差在3 m以内,可以得到较精确的定位结果。随着锚节点运动速度增加时,辅助定位信息误差越大,对算法的影响也越来越大,因此相对定位误差也随之增大。但是在相同的锚节点运动速度下,SNLSFAMC的相对定位误差小于SNLSFA。当锚节点速度为30 m/s时,SNLSFA的相对定位误差在0.08左右,SNLSFAMC的相对定位误差在0.06左右。这是因为SNLSFAMC采用了通讯半径分级的方式使得在相同的锚节点穿越次数下,待定位节点能获得较多的辅助定位点位置,并且辅助定位点数量为3个时算法即可开始定位,所以当锚节点运动速度相同时,SNLSFAMC的相对定位误差始终小于SNLSFA。

图9 待定位节点相对定位误差随锚节点运动速度变化关系图

3 结语

本文在基于移动锚节点的三维传感器网络节点自定位算法SNLSFA的基础上,提出了一种新的基于移动锚节点与多级通信的三维传感器网络节点自定位算法SNLSFAMC。与SNLSFA相比,SNLSFAMC只需3个临界通讯信息点即可开始定位,减少了一个临界通讯信息点,同时SNLSFAMC将待定位节点的通讯半径分为两级,当锚节点在穿越待定位节点通信覆盖范围时,使得待定位节点多了一次获取临界通讯信息点的机会,提高了锚节点的利用率。仿真结果表明,在相同的锚节点数量下,相对于SNLSFA,SNLSFAMC的定位精度显著提高,且在相同定位精度的情况下,SNLSFAMC降低了对锚节点数量的需求,提高了算法的响应时间。

[1] Mao G,Fidan B,Anderson B.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529-2553.

[2]Viani F,Rocca P,Oliveri G,et al.Localization,Tracking,and Imaging of Targets in Wireless Sensor Networks:An Invited Review[J].Radio Science,2011,46(5):21-30.

[3]Pal A.Localization Algorithms in Wireless Sensor Networks:Current Approaches and Future Challenges[J].Network Protocols and Algorithms,2010,2(1):46-73.

[4]Wang J,Ghosh R K,Das S K.A Survey on Sensor Localization[J].Journal of Control Theory and Applications,2010,8(1):2-11.

[5]Suo H,Wan J,Huang L,et al.Issues and Challenges of Wireless Sensor Networks Localization in Emerging Applications[C]//International Conference on Computer Science and Electronics Engineering,2012:447-451.

[6]Kuriakose J,Joshi S,Raju R V,et al.A Review on Localization in Wireless Sensor Networks[M].Advances in Intelligent Systems and Computing,Springer International Publishing,2014:599-610.

[7]Han G,Xu H,Duong T Q,et al.Localization Algorithms of Wireless Sensor Networks:A Survey[J].Telecommunication Systems,2013,52(4):2419-2436.

[8]Wei N,Guo Q,Shu M L,et al.Three-Dimensional Localization Algorithm of Wireless Sensor Networks Base on Particle Swarm Optimization[J].The Journal of China Universities of Posts and Telecommunications,2012,19(2):7-12.

[9]Guo H,Low K S,Nguyen H A.Optimizing the Localization of a Wireless Sensor Network in Real Time Based on a Low-cost Microcontroller[J].IEEE Transactions on Industrial Electronics,2011,58(3):741-749.

[10]Kumar A,Khosla A,Saini J S,et al.Stochastic Algorithms for 3D Node Localization in Anisotropic Wireless Sensor Networks[C]//7th International Conference on Bio-Inspired Computing:Theories and Applications.Springer India,2013:1-14.

[11]Jiang H,Zhang Y,Cui H,et al.Fast Three-Dimensional Node Localization in UWB Wireless Sensor Network Using Propagator Method Digest of Technical Papers[C]//2013 IEEE International Conference on Consumer Electronics,2013:627-628.

[12]Chaurasiya V K,Jain N,Nandi G C.A Novel Distance Estimation Approach for 3D Localization in Wireless Sensor Network Using Multi-Dimensional Scaling[J].Information Fusion(Special issue),2014,15:5-18.

[13]Hongyang C.Mobile Element Assisted Cooperative Localization for Wireless Sensor Networks with Obstacles[J].IEEE Transactions on Wireless Communications,2010,9(3):956-963.

[14]Guerrero E,Alvarez J,Rivero L.3D-ADAL:A Three-Dimensional Distributed Range-Free Localization Algorithm for Wireless Sensor Networks Based on Unmanned Aerial Vehicles[C]//5th International Conference on Digital Information Management,2010:332-338.

[15]Erol-Kantarci M.A Survey of Architectures and Localization Techniques for Underwater Acoustic Sensor Networks[J].IEEE Communications Surveys and Tutorials,2011,13(3):478-502.

[16]Zhang L,Zhou X B,Cheng Q.Landscape-3D:A Robust Localization Scheme for Sensor Networks over Complex 3D Terrains[C]//IEEE Conference on Local Computer Networks,2006:239-246.

[17]Fu Y J,Lee T H,Chang L,et al.A Single Mobile Anchor Localization Scheme for Wireless Sensor Networks[C]//IEEE International Conference on High Performance Computing and Communications,2011:946-950.

[18]Zhang Z,Yu F.Collaborative Localization Algorithm for Wireless Sensor Networks Using Mobile Anchors[C]//Asia-Pacific Conference on Computational Intelligence and Industrial Applica-tions,2009:309-312.

[19]Chia-Ho O.Range-Free Node Localization for Mobile Wireless Sensor Networks[C]//Wireless Pervasive Computing,2008:535-539.

[20]Chia-Ho O,Kuo-Feng S.Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks[J].IEEE Transactions on Mobile Computing,2008,7(9):1084-1097.

景秀眉(1975-),女,硕士,浙江同济科技职业学院副教授,主要研究方向为无线传感器网络、计算机技术及应用;

张仁贡(1975-),男,博士,浙江同济科技职业学院副教授,主要研究方向为无线传感器网络、工业自动化。

Three-DimensionalSensorNetworkNodeSelf-LocalizationAlgorithmBasedonMobilityAnchorNodesandMulti-LevelCommunication*

JINGXiumei1*,ZHANGRengong2

(1.Department of Information,Zhejiang Tongji Vocational College of Science and Technology,Hangzhou 311231,China;2.Department of Mechanical and Electrical Engineering,Zhejiang Tongji Vocational College of Science and Technology,Hangzhou 311231,China)

A new sensor node localization algorithm based on the flying anchor and the multi-level communication(SNLSFAMC)on the basis of the sensor node localization scheme with flying anchors(SNLSFA)is present.First,the mobile anchor nodes provide three or four auxiliary anchor points,which help us to get two non-parallel line segments.And then we can get two planes which are perpendicular to the two line segments and go through the midpoint of them.These two planes will intersect with each other to form a line which goes through the node to be positioned.Finally,the distance between the auxiliary anchor point and the un-positioned node,as the communication radius,can be used to obtain the position of the un-positioned node.The simulation results show that on the condition of the same number of nodes,the SNLSFAMC algorithm can improve the positioning accuracy compared with SNLSFA algorithm;And on the condition of the same positioning accuracy,the SNLSFAMC algorithm need less anchor nodes,as well as can improve the response time.

mobile anchor nodes;multi-level communication;three-dimensional node self-localization

项目来源:国家“十二五”支撑计划项目(2012BAD10B01);浙江省重点科技创新团队项目(2012BAD10B01);浙江省科技厅高技能人才培养和创新技术项目(2013R30058);浙江省教育厅高等教育改革项目(jg2013391)

2014-05-12修改日期:2014-05-29

10.3969/j.issn.1004-1699.2014.06.022

TP393

:A

:1004-1699(2014)06-0828-07