基于三维球形分割的无线传感器网络定位算法*

徐 兵,项顺伯,吴宪君

(广东石油化工学院 计算机与电子信息学院,广东 茂名 525000)

随着科学技术的飞速发展,无线传感器网络WSN(Wireless Sensor Network)在各个行业及领域都得到了极大的应用;当前阶段,WSN节点定位已经成为研究的趋势与焦点[1-7],它直接影响数据检测、路由等信息。当前,无线传感器网络的节点定位技术主要包括非测距与测距。非测距定位算法成本相对偏低,容易实施,但是定位精度偏低,而测距定位算法具有较高的精度,但其成本开销也相应较大。基于测距的定位算法通过分析RSSI根据路径传输损耗模型计算接收距离,此方法需要依赖充足的经验,且计算结果容易受环境变化的影响。而无需测距的定位算法主要利用网络连通性等信息、通过布置信标节点来实现定位,定位精度较高。传统非测距定位算法主要分为如下3个阶段:①锚节点通过广播自身信息,让其余节点获得与锚节点相同的最小跳数;②根据步骤①获得跳数及位置信息计算锚节点之间的平均距离;③重复上述步骤①、步骤②直到待定位节点获取到 3个或3个以上的锚节点位置时,通过几何算法对待定位节点位置进行确定,结束算法。

基于测距的定位方法有RSSI、ARL、SzAPSO、CALL等。文献[8]提出一种比较常用的通信测距的方式,即不确定性数据聚类方式,借助数学统计特征以实现较高精度定位。文献[9]明确指出,ARL定位算法可以对节点之间的平均距离予以准确估算,继而获得准确的位置信息,同时检验该信息是否可信,通过仿真实验表明了算法具有有效性和安全性。文献[10]通过利用SzAPSO方法和相邻未知节点之间的距离约束实现定位,这样可以降低锚节点密度,并且无需至少和3个锚节点相邻。文献[11]通过提出构件方式来建立一种CALL定位算法,以此提高节点之间的合作关系。通过大量文献数据,我们找到几种以非测距定位方法,具体包括以下几种类型,分别为MDS-MAP、DV-hop等。文献[12]详细地阐述了 DV-hop 算法存在的问题,并予以完善及修正,显著提升定位精度,其核心思路是基于锚节点信任度求解未知节点与锚节点的距离。文献[13]使用辅助变量将自定位问题表述为线性最小二乘问题,并基于封闭形式的解决方案建立了一种新的基于辅助变量的伪线性估计器。文献[14]提出了一种新的与位置相关的密钥管理协议LKMP,并且与现有的依赖于位置的端到端数据安全性和MKMP方案相比,该方案在数据机密性、计算和通信方面具有较大优势。文献[15]提出的Hophole定位方法是基于跳数距离的,并且能够较好地解决有洞的各项异性的网络节点定位问题。文献[16]在分簇机制上以选择邻居节点最多的节点作为起始节点,融合三角不等式法则和最短路径法测距,实现了较小的定位误差。

在上述工作的基础上,本文基于三维球形分割[17-18]提出了一种新的无线传感器网络定位算法。该算法给出了未知节点到各个锚节点距离和定位误差计算方法,详细阐述了位置节点的三维坐标获取方法,并通过实验仿真算法的有效性。本文结构如下:第1节对无线传感器定位相关性能指标进行阐述;第2节对定位算法建模过程进行分析和阐述;第3节主要进行数学仿真;第4节对全文进行总结。

1 性能指标

在无线传感器网络中,锚节点将跳数数据包周期性地传送至临近的邻居节点,内部包含有相关联的位置信息;初始状态下,我们将其设置为0;当邻居节点接收到上述数据信息时,首先对锚节点等进行更新,而且以最小跳数为单元予以更新,然后将数据信息予以存储,并转发传输。具体应用过程中,hij代表锚节点i和j之间的跳数,锚节点i对应的坐标可以由(xi,yi)予以表示,锚节点j坐标为(xj,yj),则锚节点之间的每跳平均距离表达公式如下:

(1)

假设未知节点x和y到锚节点i的最小跳数分别为dmin(x,i)和dmin(y,i),节点x是未知的,对应的所有邻居节点集合可以由nbs(x)予以表示,那么我们将x与i之间的跳数表示为d(x,i);x周边区域所有邻居节点数目可以由|nbs(x)|予以表示,然后通过式(2)计算未知节点到锚节点的跳数,具体如下:

(2)

同时令R表示节点通信半径,S表示监测区域总面积,n表示节点总数,则利用式(3)可以计算得到网络平均连通度N为:

N=(n/S)πR2

(3)

平均每跳距离D:

(4)

由此得到未知节点到各个锚节点的距离:

(5)

平均定位误差定义为:

(6)

通常情况下,未知节点必须通过某种有效的方式获取3个锚节点对应的数据信息,才能够保证后续计算工作的开展,针对未知节点坐标则可以通过我们比较常用的最小二乘法予以实现;设未知节点坐标为(x,y),各个锚节点坐标分别为(x1,y1),(x2,y2),…,(xn,yn),那么未知节点与锚节点相互之间的平均距离可以由以下数学公式予以计算,分别用d1,d2,…,dn予以表示:

(7)

利用式(6)中的前n-1项依次与最后一项做减法得到式(7):

(8)

式(7)可用线性方程表示,即为:

AX=b

(9)

式中:

(10)

(11)

(12)

化简可得:

X=(ATA)-1ATB

(13)

因此,由式(13)可得待定位未知节点的位置坐标。

2 改进算法

目前,针对二维空间的无线传感网络节点定位算法研究比较深入,而三维空间的定位算法则相对薄弱。对此,本文基于三维球形分割来建立无线传感器网络定位算法。如图1所示结构中,假设无线传感器网络位于第1象限中,在未知节点Nj影响范围内,Ai表示对应范围的标识符为i的锚节点,mj表示Nj影响范围内的锚节点个数,未知节点Nj的标识符表示为j。同时,假设锚距离ai表示原点与Ai间的距离,锚线OAi(i∈M)表示原点与Ai间的连线,锚角αi、βi、γi(i∈M)分别表示锚线OAi与对应平面的夹角。

图1 定位示意图

如果通信半径固定,那么节锚之间距离的最大通信范围设定为R,否则Nj到Ai的距离设定为dij。同时,锚球Cij表示最大传输半径为R,球心为Ai的球面。则锚节点密度ρ的计算公式如下:

(14)

令测量值与真实值之间的误差值与节点无线范围的比值由ξ予以表示,我们将其称之为测距误差,Ai与Nj实际距离可以由eij表示;Nj测得与Ai之间的距离由dij表示。假设μ代表(0,1)之间随机数,由此可得到节锚距离的测量值与真实值间的关系:

dij=eij+ξ×R×(1-2μ),1≤i≤m,m+1≤j≤n

(15)

假设4个已知节点的坐标分别为A(a1,b1,c1)、B(a2,b2,c2)、C(a3,b3,c3)、D(a4,b4,c4),利用改进的多策略粒子群优化人工神经网络模型得到位置节点到A、B、C、D的距离分别为d1、d2、d3、d4。分别以A、B、C、D做球心,d1、d2、d3、d4做半径,做球A、球B、球C、球D。假设球A与球B不相交,可得参考点E的坐标:

(16)

球A、球B、球C、球D两两为一组可得到6个参考点坐标,将距离值的倒数设为参照权因子可得权值为:

(17)

由此可得位置节点的三维坐标为:

(18)

(19)

(20)

(21)

(22)

惯性权重w对粒子的飞行速度影响较大,固定的w会导致粒子无法遍历整个搜索空间,使用迭代次数线性递减的w使前期搜索能力较强,后期较弱。本文提出改进的混沌惯性权重策略,添加随机数r3,并且r3为(0,1)内的随机变量,降低粒子后期在解空间飞行时的趋同性:

wt+1=4r3×wt(1-wt)

(23)

t为迭代次数,w1∈(0,1),wt为对应的惯性权重。具体应用过程中,粒子聚拢度较高时,速度和位置变化很小,无法继续在全局范围内搜索,需要适时引入扰动策略,本文基于高斯分布和柯西分布提出了一种卡方(ε2(n))变异扰动因子,当自由度n很大时,分布近似为高斯分布。对粒子位置进行修改得:

(24)

式(22)中,k∈[0,1]。由上述公式及第1节提出的相关描述可得出本文基于三维球形分割的无线传感器网络定位算法如下:

Step 1 初始化人工神经网络,设置三层拓扑结构,将所有权值和阈值编码成粒子,并改进多策略粒子群优化模型参数;

Step 2 计算适应度值并更新pbest和gbest:

Step 3 判断是否满足终止条件;假设达到最大迭代次数Tmax或小于最小误差minError,则保存全局最优粒子位置,输出最优权值和阈值;否则重新返回至Step 3;

Step 4 构建改进的多策略粒子群优化人工神经网络模型,输入RSSIA、B、C、D;

Step 7 算法结束。

3 仿真实验

为了检验上述算法的适用性,本文搭建了无线传感网仿真环境,并利用MATLAB进行仿真实验。假设通信半径R=10 m,在4/3πR3的球体内随机投掷一定数量的节点作为锚节点。节点A、B、C、D的坐标分别为A(1,0,0.8)、B(3,0,2.02)、C(0,3.1,1.2)、D(3.5,3.1,1.2),同时初始化改进的多策略粒子群优化人工神经网络模型参数:Tmax=200,粒子最大速度Vmax=0.6,改进混沌惯性权重w1=0.30,学习因子c1=1.98,c2=2.02,minError=0.000 1,种群规模NP=50,ε2(n)变异扰动因子中自由度取11。

锚节点信息是多维质心定位算法的最主要信息,会对定位算法的性能产生重要干扰与影响;ξ为0.05时,其结果参如图2所示。从图2可以看出,随着锚节点密度的增大定位误差随之减小。并且未知节点周围的平均锚节点数为3时,本算法的定位误差大约在38%附近。而当未知节点附件的锚节点数量达到8时,本文算法的定位误差下降到28%以下。若锚节点密度持续增加,本文算法的定位误差仍呈直线下降趋势。

图2 锚节点密度对定位误差的影响

图3 测距误差对定位误差的影响

为了获得更为准确的定位信息,需要依靠较为可靠的通信环境和节点设备。图3给出了不同测距误差对算法的敏感性影响情况。这里设置锚节点密度为3,锚节点比值为10%,测距误差的变化范围为0～1。从图3可以看出,本算法的定位误差随测距误差的增加整体上呈现上升趋势。并且当锚节点比例和密度不变时,测距误差为0时,所对应的最小定位误差大约为35%左右,随后因测距误差的递增,定位误差变化缓慢。因此可以看出测距误差对本文算法性能影响较小。

节点网络连通度的大小主要受节点密度大小的影响,因此有必要分析节点密度对算法性能的影响。假设测距误差为0.05,锚节点比例为10%,图4给出了算法定位性能与节点密度之间的关系。从图4可以看出,随着节点密度的增加,定位误差呈现先降低后逐渐增大的趋势。当节点密度小于9时,网络中的定位误差呈现缓慢下降的趋势;当节点密度位于9～15之间时,定位误差呈上升趋势;当节点密度大于15时,定位误差呈现快速增长趋势。因此,将节点密度设置为9能够得到最低的定位误差,使得算法性能最优。

图4 节点密度对定位误差的影响

这里进一步对网络节点数对定位误差的影响进行研究。本文算法在锚节点分布率分别取10%、20%、30%时,图5给出了网络总结点数对节点定位性能的对比曲线,其中,实验结果为100次仿真实验的平均取值。在图中,随着网络节点总数的增加,节点定位的误差呈现下降趋势;仔细观察,我们发现,当锚节点分布越密集时,则系统产生的定位精度越高,对应的误差数值也就越小。这是因为,网络连通性会随着网络总节点数的增加而增强,即未知节点可用多跳的形式与锚节点进行通信,并且,当锚节点数量增加时,网络连通性也会变好,此时与锚节点直接通信的节点数目也会增加,因此,综合上述两个原因,定位误差会逐渐减小。

图5 锚节点密度对节点定位的均方误差影响

图6 不同算法中未知节点数目对节点误差能耗积的影响曲线

最后,图6给出了不同算法的未知节点数目对节点误差能耗积的影响曲线。其中,假设节点通信半径都相同,为10 m。节点数目的变化范围为75个～280个。可观察到,随着节点数目的快速增加,两种算法的误差能耗积都有上升趋势,但DV-HOP算法增幅明显,本文算法增幅极小。综上所述,我们认为本文计算方法可以在能耗、定位精度两个方面取得较好优势。

4 结论

针对无线传感器网络定位精度问题,本文基于三维球形分割技术建立了一种新的定位算法。首先,在计算过程中,将各个锚节点之间的网络连通度、平均距离予以综合考量,进而计算未知节点与锚节点相互之间的距离,然后将对应的数据予以存储,同时更新与锚节点的最小跳数并进行转发。当未知节点获取到至少3个信标节点信息时,通过最小二乘法求得出未知节点的坐标。其次,基于三维球形分割对上述指标进行优化,为了使寻求最优解效率达到较优,本文在PSO中添加反向学习策略,并建立了无线传感器网络定位算法。最后,通过仿真实验深入研究影响该算法的关键因素。通过比较分析节点密度、信标节点个数、定位误差和测距误差等参数。实验结果表明,该算法较DV-HOP和加权质心算法在性能得到较大提高。在后续研究中,可以考虑结合融合多种测距和非测距定位算法来提高无线传感器网络的定位精度。