基于Steffensen迭代和模糊信息的节点定位算法

齐小文

(郑州工程技术学院信息工程学院,郑州 450044)

无线传感器网络[1]WSN(Wireless Sensor Network)是集无线传感技术、网络技术、通信技术于一体的新兴网络。在无线传感器网络中,传感节点的位置确定是进行其他数据采集与发送的基础。节点的定位算法已成为无线传感网络研究的重点和热点[2-3]。为了提高节点的定位精度,学者们在经典定位算法的基础上做了进一步的改进。文献[4]在加权质心定位算法和RSSI测距模型分析的基础,提出了一种基于自适应迭代搜索的三维质心定位算法;文献[5]在直线模糊信息的基础上,提出了一种基于简单Delaunay三角剖分的模糊信息定位算法,不仅提高了节点定位精度还降低了网络能耗;文献[6]引入邻域思想,将网络节点与周围节点按跳数划分为不同阶邻域,提出一种基于邻域旋跳迭代机制的节点定位算法;文献[7]运用海伦公式的四面体体积公式,并结合二维LLSE算法,提出一种低复杂度和低成本的三维定位算法;文献[8]提出了近似投影校正的无线传感器网络非测距三维定位算法;文献[9]提出了一种基于阶次序列和近似三角形内点法的混合定位算法。文献[10]针对TOF测距提出了一种应用于稀疏网络的定位算法,算法通过引入泰勒级数展开的最小二乘法计算节点位置,根据无效节点的不同情况实现节点的定位。文献[11]提出了一种基于方位角的区域定位方法(3D-ADAL)。文献[12]通过卡尔曼滤波和线性插值法对随机误差进行补偿以获得较精确的定位节点并与参考节点进行距离估计,并采用改进的三角质心定位进行测试,使传统加权质心定位精度有了明显提高算法利用定向天线确定的旋转角和倾斜角实现节点的定位。不同定位算法采用不同的定位策略,也就造成了不同的定位精度和复杂度。

实际的无线网络中,网络拓扑复杂多变,节点能耗、信息传送与感知能力有限,种种因素会使无线网络定位节点带有随机性和模糊性。而模糊定位法则是通过视线交叉测得的方向角、俯仰角来定位节点[13-14]。本文在借鉴前人研究成果的基础上,提出了一种基于Steffensen迭代和模糊信息的节点定位算法。算法在节点模糊信息定位的基础上引入Steffensen迭代,通过迭代计算,修正第1阶段粗略定位的节点位置,实现精确定位。

图1 传感器模糊观测几何定位

1 相关定义

1.1 模糊信息

(1)

(2)

1.2 Steffensen迭代算法

对于非线性方程f(x)=0,可划成等价的方程:

x=φ(x)

(3)

选取初始近似值x0构造迭代次序,迭代公式如下:

xk+1=φ(xk),k=0,1,2,…

(4)

式(4)称为不动点迭代,其中φ(x)为迭代函数。

Steffensen迭代法是一种改进不动点迭代的加速迭代法,能有效的求解非线性方程的根。不仅具有二阶收敛速度还具有较高的计算精度[15]。其迭代函数为:

(5)

(6)

Steffensen 加速迭代算法如下:

步骤1 取初始点x0,设最大迭代次数为Num、迭代精度为ε,置k=0;

步骤3 若|xk+1-xk|<ε,则停止计算;

步骤4 若k=Num,则停止计算;否则,置k=k+1,转到步骤2。

1.3 有效锚节点

在无线传感器网络中,已知位置节点称为锚节点,位置不明节点为未知节点。未知节点的定位一般会基于位置确定的锚节点,但是由于节点间通信易受干扰,在进行未知节点定位前,需要对锚节点的有效性进行确定。初始锚节点的位置会通过北斗或GPS系统获得,无线网络初始化各节点的位置分布示意图如图2所示。

图2 无线网络节点初始位置示意

图2中星型状的代表未知节点,圆圈状的代表锚节点,两个锚节点Bi(xi,yi,zi)、Bj(xj,yj,zj)之间的距离为:

(7)

两个锚节点Bi(xi,yi,zi)、Bj(xj,yj,zj)之间的路径损耗指数L(Bi,Bj),根据文献[5]路径耗损公式可得:

RSSI(Bi,Bj)=Pt-PL(d0)-10×L(Bi,Bj)×
lg[d(Bi,Bj)/d0]-X0

(8)

(9)

Pt表示发射功率,PL(d0)表示在d0处的经验路径损耗,d0表示天线远场参考距离。对于每一个锚节点Bi,在其通信半径范围内的路径损耗指数L(Bi):

(10)

定义锚节点局部信号路径损耗的阈值为τ,在进行未知节点定位时,首先要对锚节点的有效性进行检验,即比较锚节点Bi的路径损耗指数L(Bi)与L(Bi,Bj)的差值与阈值τ的大小,当差值小于阈值时,锚节点Bi是无效的,其中锚节点Bj是有效锚节点:

|n(Bi)-n(Bi,Bj)|<τ

(11)

2 本文节点定位算法

2.1 基于连通度和剩余能量选择移动锚节点

为了提高节点定位速度,本文需要在网络中设置一个移动锚节点,通过移动锚节点在网络中的运动轨迹,辅助其他锚节点对未知节点定位,文章利用移动锚节点的连通度和剩余能量来确定移动锚节点,图3是移动锚节点运动轨迹示意图。

图3 移动锚节点运动轨迹

在定位前,选择一个锚节点作为移动锚节点。设某一节点Bi的邻居节点数为Num(Bi),节点总数n,节点Bi与其他邻居节点间的平均连接性能为:

(12)

锚节点与其他邻居锚节点间的连通性能和能量剩余情况是选择移动锚节点必须考虑的两点,定义无线网络内某一节点Bi选票值为vote(Bi),节点Bi的剩余能量为E(Bi),初始能量为Es,文章采用与文献[16]相同的无线节点能耗模型,网络内节点的最好平均连通度为f(max),则可以得到vote(Bi):

(13)

其中μ和η分别表示连接度和剩余能量的影响系数。利用文献[17]无线网络能耗模型求解点Bi的剩余能量为E(Bi)。对于选中的移动锚节点,在每轮循环开始前,都要对移动锚节点的位置信息进行更新:

(14)

(15)

2.2 基于Steffensen迭代模型求解节点位置

设空间内随机部署n个节点,其中锚节点个数为m(m

根据已知有效移动锚节点的坐标信息,建立如下模型:

(16)

由此,定位问题转化为求式(16)的最小值,即通过Steffensen迭代运算求得当式(16)取得最小值时的坐标,以此作为第2次定位后的结果。

(17)

要使式(17)取得最小值时,所需的必要条件为:

(18)

对式(18)的各等式进行求解,其中可得:

(19)

(20)

(21)

令Δi为:

(22)

(23)

(24)

(25)

同理,对变量yi进行迭代,可得:

(26)

(27)

(28)

同理,对变量zi进行迭代,可得:

(29)

(30)

(31)

综合以上内容,基于Steffensen迭代和模糊信息的三维节点定位算法步骤如下:

步骤1 初始化无线传感网络,设定路径损耗阈值τ,迭代最大次数N、迭代精度ε等参数;

步骤2 通过式(7)～式(11)寻找有效锚节点;

步骤3 通过式(12)和式(13)筛选移动锚节点;

步骤4 利用式(1)和式(2)运用模糊信息定位实现节点粗定位(xi,yi,zi);

步骤5 判断迭代次数是否大于T,迭代精度是否小于ε,若都不是,执行步骤6;否则执行步骤7;

步骤6 根据式(17)～式(31)对步骤4中的粗定位坐标(xi,yi,zi)进行Steffensen迭代求精;

步骤7 定位坐标迭代求精结束,输出精准定位坐标,并根据式(14)和式(15)对无效锚节点位置更新,循环下一轮。

3 网络性能对比分析

3.1 网络延时

文章将对比分析文献[10]和文献[11]的网络延时,无线网络延时主要包括发送单位比特数据延时ttran、接收单位比特数据的延时trec、位置定位延时tloca、模糊信息计算延时tvag、位置更新延时tupdata,则本文、文献[10]、文献[11]网络总延时为Ttext、Ttof、T3D-ADAL。

(32)

(33)

(34)

式(33)减去式(32)可得:

(35)

式(34)减去式(32)可得:

T3D-ADAL-Ttext=(M-3)·T·(N-M)tloca

(36)

对于式(35),在无线网络中节点的个数肯定大于3即n>3,并且锚节点的个数也会远远小于未知节点即N-M>M,定位循环T>2,而tloca>tvag,R≥2,所以Ttof-Ttext>0。本文算法的延时小于文献[10]。

对于式(36),在无线网络中锚节点的个数肯定大于3即M>3,并且锚节点的个数也会远远小于未知节点即N-M>M,所以T3D-ADAL-Ttext>0。本文算法的延时小于文献[11],综上可知,本文算法的延时少于文献[10]和文献[11]。

3.2 能耗分析

无线网络能耗主要包括发送单位比特数据能耗etran、接收单位比特数据的能耗erec、位置定位能耗eloca、模糊信息计算能耗evag、位置更新能耗eupdata,则本文、文献[10]、文献[11]网络总能耗为Etext、Etof、E3D-ADAL。

(37)

(38)

(39)

式(38)减去式(37)可得:

(40)

式(39)减去式(37)可得:

E3D-ADAL-Etext=(M-3)·T·(N-M)eloca

(41)

对于式(40),在无线网络中节点的个数肯定大于3即n>3,并且锚节点的个数也会远远小于未知节点即N-M>M,定位循环T>2,而eloca>evag,R≥2,所以Etof-Etext>0。本文算法的能耗小于文献[10]。

对于式(41),在无线网络中锚节点的个数肯定大于3即M>3,并且锚节点的个数也会远远小于未知节点即N-M>M,所以E3D-ADAL-Etext>0。本文算法的嫩好小于文献[11],综上可知,本文算法的能耗少于文献[10-11]。

4 实验仿真与分析

为了检验算法的性能,本文在MATLAB平台上进行仿真和比较分析。设节点分布在500 m×500 m×500 m的区域内,节点的坐标随机产生,总数为150,节点初始能量为1 500 J,节点的通信半径为10 m,节点感知半径为8 m,发送节点发送数据k=5 byte,位置更新数据包长度l=1 byte,模糊定位精度ε=0.1,连接度和剩余能量影响系数μ=0.6,η=0.4,对3种算法运行100次并求各自的平均值,分析比较各算法的性能。本文定位误差率通过式(42)计算:

(42)

4.1 定位算法节点变化

图4为本文定位算法过程中节点变化的比较:在图4(a)中可见未知节点、普通锚节点和一个移动锚节点,此时为无线网络的初始分布,节点的实际坐标为(162,185,148);图4(b)为通过模糊信息粗定位后的无线网络节点分布,相比图4(a),在图4(a)中增加了已定位节点;图4(c)是在图4(b)基础上迭代求精后的节点分布,图4(c)和图4(b)对比可知,部分已定位节点位置发生变化,由此可以看出,经过本文的迭代求精,可以一定程度上提高节点的定位精度,降低误差率。

图4 本文算法定位过程中节点位置变化比较

图5 本文算法误差率比较

4.2 算法定位误差率

从图5可以看出随着节点通信半径的增大,本文定位算法误差率降低,这是由于通信半径的增大,加大节点间的连通,提高了节点的利用率,对同一节点可定位的锚节点个数增多,增加了迭代求精的次数,从而提高了定位精度;在一定的通信半径上,随着锚节点移动速度的加快,定位误差率也在下降,且当锚节点移动速度增加到一定程度时,误差率不再大幅度降低,这是因为当节点移动速度和迭代求精速度差距太大,使得定位误差率降低较慢。在定位过程中,在保证定位误差率的同时,为了节省网络能量,锚节点移动速度不宜太大。

图6 3种定位算法误差率比较

从图6可以看出随着算法执行次数的增加,文献[10]、文献[11]和本文3种算法的定位误差率呈下降趋势,这是因为随着执行次数的增加,越来越多的未知节点被定位,已定位节点加入到锚节点队列中,锚节点的位置更新提高了定位精度,而本文算法采用模糊信息定位,利用Steffensen迭代求精,与文献[10]、文献[11]的质心定位和加权定位算法相比,精度更高。

4.3 网络中已定位节点个数比较

由图7为锚节点个数与已定位节点个数的关系曲线。从图7(a)中M=20到图(d)M=60,文献[10]、文献[11]和本文3种算法已定位节点的个数总体呈增加趋势,但各有差异。3D-ADAL算法中已定位节点个数增加缓慢且最低,改进TOF算法中已定位节点数增加适中。本文算法已定位节点数增值幅度最大。这是因为本文算法中模糊信息定位增大了锚节点的可利用率,通过静态锚节点辅助移动锚节点完成节点定位,利用节点的动态性提高了节点定位速度。定位后的迭代求提高了定位精度,因此本文算法相比其他两种算法不仅定位速度较快而且定位节点数量多。

图7 3种算法中已定位节点个数比较

4.4 算法消耗能量比较

从图8可以看出,3种算法随着节点通信半径的增大,能耗逐渐降低,本文算法能耗降低幅度最大且能耗最低,3D-ADAL算法的能耗最大且降低最慢,改进TOF算法的能耗居中。本文算法根据连通度和剩余能量选择移动锚节点,虽使得局部能耗增加,但静态锚节点能耗相比其他算法中锚节点能耗低,并且利用模糊信息定位,利用迭代求精提高定位精度,不仅降低了定位算法对初始锚节点个数要求,还降低了网络能耗。

图8 3种定位算法中消耗的能量比较

5 总结

针对无线传感器网络节点定位算法定位精度低的问题,本文在借鉴前人研究的基础上提出了一种基于Steffensen迭代和模糊信息的节点定位算法,该算法将锚节点分为移动锚节点和混合锚节点,通过空间中节点之间的模糊信息实现粗定位,然后通过Steffensen迭代求精提高节点的定位精度。仿真对比验证,本文算法具有较高的定位精度,且定位速度较快,能耗较低。

[1] Massimo Vecchio,Roberto Lopez-Valcarce,Francesco Marcelloni. A Two-Objective Evolutionary Approach Based on Topological Constraints for Node Localization in Wireless Sensor Networks[J]. Applied Soft Computing,2012,12(7):1891-1901.

[2] Vijay K Chaurasiya,Neeraj Jain,Nandi G C. A Novel Distance Estimation Approach for 3D Localization in Wireless Sensor Network Using Multi-Dimensional Scaling[J]. Information Fusion,2014,15:5-18.

[3] Dimitrios Zorbas,Tahiry Razafindralambo. Prolonging Network Lifetime Under Probabilistic Target Coverage in Wireless Mobile Sensor Networks[J]. Computer Communications,2013:1039-1053.

[4] 郑德忠,李雪,袁鹏,等. 基于自适应迭代搜索的三维质心定位算法[J]. 计量学报,2017,38(3):356-362.

[5] 党小超,李芬芳,郝占军. Delaunay三角剖分的节点模糊信息三维定位方法[J]. 计算机工程与应用,2016,52(23):115-122.

[6] 曹世华,王琦晖,王李东. 基于邻域旋跳迭代机制的无线传感器网络节点定位[J]. 计算机工程,2016,42(7):94-100.

[7] 黄庆宇,刘新华. 基于线性最小二乘估计的传感网节点三维测距定位算法[J]. 计算机工程,2016,42(12):11-16.

[8] 胡中栋,谢金伟. 基于近似投影校正的无线传感器网络三维定位机制[J]. 传感技术学报,2014,27(11):1573-1578.

[9] 韩睿松,杨维. 一种基于SBL和APIT的混合定位算法[J]. 传感技术学报,2014,27(8):1094-1099.

[10] 鲁旭阳,张效义,刘广怡. 稀疏无线传感器网络的节点自定位算法[J]. 计算机工程,2012,38(18):83-86.

[11] Guerrero E,Wang Hao,Alvarez J,et al. A Three-Dimensional Range-Free Localization Algorithm Based on Mobile Beacons for Wireless Sensor Networks[J]. Computer-Aided Design,Drafting and Manufacturing,2010,20(1):83-92.

[12] 赵大龙,白凤山,董思宇,等. 一种基于卡尔曼和线性插值滤波的改进三角质心定位算法[J]. 传感技术学报,2015,28(7):1086-1090.

[13] Raju Dutta,Sajal Saha,Asish K. Mukhopadhyay. Tracking Hetergeneous Dynamic Sensor Node using Fuzzy Logic to Prolong System Lifetime in WSN[J]. Procedia Engineering,2012:522-527.

[14] Lü Zhen,Zhang Ying. Hybrid Optimization in WSN Node Localization Algorithm[J]. Computer Systems and Applications,2014,23(7):121-125.

[15] Ezquerro J A,Hernndez-Verón M A. Increasing the Applicability of Steffensen’s Method?[J]. Journal of Mathematical Analysis and Applications,2014,418(2):1062-1073.

[16] Wang Haobo,Ren Weizheng,Cui Yansong. An Adaptive WSN Node Tracking Algorithm Based on Rough-Set Neural Network[J]. Procedia Engineering,2012:1750-1754.

[17] 傅菊平,齐小刚. 基于剩余能量和节点度的无线传感器网络分簇算法[J]. 计算机应用研究,2011,28(1):250-253.

[18] 张志东,孙雨耕,刘洋,等. 无线传感网络模型[J]. 天津大学学报,2007,40(9):1029-1035.