基于跳距修正与狮群优化的WSNs三维定位算法*

苟平章，刘学治，孙梦源，何 博

(西北师范大学计算机科学与工程学院，甘肃 兰州 730070)

1 引言

无线传感器网络WSNs (Wireless Sensor Networks)中的节点用来感知、采集和处理网络分布在比较危险的复杂区域内时各种环境和监测对象的信息，如果节点位置无法确定，收集到的各种监测信息将毫无意义[1]。因此，进行节点感知半径优化，减少节点定位过程中锚节点能耗，提高节点定位精度成为WSNs研究中的重要问题之一。实际应用中WSNs节点一般不会分布于绝对的二维平面，三维定位算法更符合实际定位需求，如何减少基于三维空间的节点定位误差已成为研究热点[2]。

文献[3]提出一种结合DV-Hop(Distance Vector-Hop)和RSSI(Received Signal Strength Indicator)的优化算法，通过将计算出的待定位节点与锚节点间的距离作为单隐层前馈神经网络训练好的网络模型的输入，形成完整的拓扑训练集，取代网络拓扑结构，得到待定位节点的位置，使得节点定位精度和抗干扰性得到提高。文献[4]使用MAC(Media Access Control)层发现信标节点的邻居节点，以减少传输过程的冲突，将单跳邻居节点分为2种进行通信降低了能耗，利用修正因子降低定位误差。文献[5]提出一种增强的拉格朗日矩阵填充算法，根据测量值来填充未测距离并分离噪声数据，采用MDS(Multi-Dimensional Scaling)方法实现节点的精确定位。文献[6]将差分进化DE (Differential Evolution)算法和DV-Hop相结合，使用最小均方误差准则计算每跳平均距离，将改进的DE算法应用于求解待定位节点估计位置对应的全局最优解，降低了节点的平均定位误差，提高了算法的收敛速度和稳定性，但是算法的复杂度有所增加。文献[7]结合粒子群算法和混合复杂进化算法的优点，提出2种三维定位算法，提高了节点的定位精度，但是没有考虑到定位过程中待定位节点到锚节点之间距离的误差。文献[8]通过使用RSS(Received Signal Strength)和AOA(Angle Of Arrival)混合测量相结合的方法，提升了不同场景下的定位性能。文献[9]使用迭代定位的方法减少了远距离待定位节点的累积误差，将计算出坐标值的待定位节点升级为辅助锚节点，利用辅助锚节点平衡了网络能量消耗，并对网络跳数、跳距和计算方法进行了优化，减少了算法的定位误差和计算量。文献[10]利用改进的二次栅格扫描定位算法完成初步定位，使用三角形质心迭代定位算法提升了定位精度。文献[11]提出一种通过质心迭代计算待定位节点坐标的三维定位方法，提高了节点定位精度和定位覆盖率。文献[12]将三维空间划分成网格单元，把数据对象嵌入三维空间，使用一个密度阈值来识别稠密单位，通过MeanShift算法迭代计算出概率密度的最优解，达到对节点的精确定位。

综合以上研究，本文针对三维DV-Hop的跳数划分、跳距设置和计算方法造成的定位精度不高的问题，提出一种基于跳距修正与狮群优化LSO(Lion Swarm Optimization)的WSNs三维定位算法HCLSO-3D(3D positioning algorithm based on Hop Correction and Lion Swarm Optimization)来提高节点定位精度。首先，使用多通信半径的方法，对传统DV-Hop模型中跳数进行细化，得到更合理的跳数，减少对平均跳距和待定位节点到锚节点距离计算带来的累积误差。其次，使用相似路径搜索算法，获取与待定位节点到相应锚节点之间最相似的锚节点对的路径，对此路径的平均跳距进行修正，并作为待定位节点到对应锚节点的平均跳距，减少其他锚节点的影响，降低平均跳距的误差。最后，使用狮群优化算法对待定位节点的坐标进行计算，得到最优的坐标值。

2 三维DV-Hop算法和狮群优化算法

2.1 传感器节点监测区域

无线传感器节点被随机分布在三维空间的监测区域中，图1所示为仿真模拟出的一个典型的含有多个波峰和波谷的三维空间监测区域地形图，被随机抛洒到区域中的传感器节点通过三维DV-Hop定位算法确定自身位置，然后将自身坐标及监测信息传输到汇聚节点，进行下一步数据处理。

Figure 1 A topographic map of a monitoring area in three-dimensional space图1 三维空间监测区域地形图

2.2 三维DV-Hop定位算法

DV-Hop定位算法[13]是一种距离无关的定位算法，三维DV-Hop定位算法是从二维空间向三维空间的一种推广，其基本过程与二维DV-Hop定位算法过程类似，主要步骤如下：

步骤1节点间信息传播与跳数估算。网络中所有锚节点广播自身的位置和跳数信息，在锚节点通信半径内的所有节点将获得锚节点的信息并保存，节点将跳数信息加1后向邻居节点传播自身的标识信息、更新后的跳数信息和接收到的锚节点信息，在信息传递过程中，待定位节点只保存到各个锚节点的最小跳数，网络中所有节点获得锚节点信息后传播过程结束。

步骤2待定位节点与锚节点之间跳距的估算。所有锚节点保存了到其余锚节点的最小跳数，每个锚节点计算平均距离，并且在网络中传播平均跳距信息，锚节点最近范围内的待定位节点保存平均跳距并计算到各个锚节点的距离。

Hopsizei=

(1)

其中，(xi,yi,zi)和(xj,yj,zj)为锚节点i和锚节点j的实际坐标位置；i、j为锚节点的标识，其值的范围由网络中的锚节点个数决定；hij是锚节点i和锚节点j的最小跳数;Hopsizei表示锚节点i的平均跳距。锚节点i和锚节点j之间的估算距离dij为：

dij=Hopsizei×hij

(2)

步骤3待定位节点坐标计算。在三维空间中，得到4个及以上的待定位节点到锚节点之间的估计距离后，通过极大似然估计法计算出待定位节点的坐标。

2.3 狮群优化算法

狮群优化LSO算法[14,15]是一种群体智能算法，模拟自然界中狮群的行为模式，算法中有3种角色，分别为：狮王、母狮及幼狮。按照自然界的“适者生存”法则，不同角色的狮子具有不同的位置更新方式。狮子位置更新方式的多样化保证算法快速收敛，不易陷入局部最优，精度较高，能较好地获得全局最优解。

在D维空间中初始化狮群数量为N，成年狮数量为NL。

(3)

其中，成年狮所占比例因子β为(0,1)的随机数，一般取值小于0.5。成年狮中仅有一头为公狮，剩余为母狮，幼狮数量为N-NL,第i头狮子位置表示为：

xi=(xi1,xi2,xi3,…,xiD),1≤i≤N

(4)

狮王、母狮及幼狮分别按照式(5)～式(7)更新自身位置：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

3 HCLSO-3D定位算法

3.1 多通信半径设置和跳数优化

传统的三维 DV-Hop算法在划分跳数时，锚节点通信半径内的所有节点都称为单跳节点，但这些节点与锚节点之间的距离往往并不相等，导致距离估计产生误差。在计算平均跳距时，跳数的误差会影响平均跳距的值，估计距离与待定位节点和锚节点之间的真正距离有明显差异。本文采用多通信半径的方式对锚节点所有通信范围内的节点跳数进行重新计算和划分，进而影响多跳的划分，减少由跳数不合实际带来的累积误差，其基本步骤如下：

步骤1设置预传播半径。考虑锚节点和待定位节点在总节点中所占的比例，设置预传播半径R:

(12)

其中，R为预传播半径；n为多通信半径数量，其值为锚节点占总节点比例的倒数值取整；r为最大通信半径。锚节点比例越大，WSNs三维空间中锚节点覆盖的待定位节点数越少，预传播半径的划分越粗糙，反之，预传播半径的划分越精细。

步骤2预传播。预传播阶段中，各个锚节点使用设置的预传播半径进行多通信半径的传播，将原本通信范围内的所有单跳节点通过不同的通信半径进行划分，使得待定位节点到锚节点的跳数计算得更加准确。

步骤3全网络传播阶段。按照传统三维DV-Hop步骤1进行节点信息的传播和跳数估计，此时各个锚节点和单跳范围内被细化跳数值的节点向外传播信息，多跳的跳数值受到单跳值的影响，被划分得更加细致、精确。

3.2 跳距修正

在传统三维DV-Hop定位模型中，待定位节点的平均跳距由距离其最近的锚节点计算得出，待定位节点保存并利用平均跳距计算到各个锚节点之间的距离。传统的计算方法使用同一个平均跳距计算待定位节点到所有不同锚节点之间的距离，由于不同锚节点对待定位节点的影响不同，会使得平均跳距产生较大的误差，影响距离的计算。本文采用相似路径搜索算法[16]得到一条与待定位节点到对应锚节点之间路径最相似的锚节点对的路径，计算此路径的平均跳距并进行修正，作为此待定位节点到对应锚节点的平均跳距值。随着对应锚节点的改变，平均跳距值也会相应地改变，最终利用平均跳距与被优化的跳数值相乘得到精确的距离。其基本步骤如下：

步骤1相似路径搜索。节点在网络中传播信息时会将自身的标识和到各个锚节点的跳数信息传递给邻居节点，在网络传播完成之后，每个待定位节点会存储到各个锚节点所经过的最短路径节点序列，每个锚节点会存储到各个锚节点所经过的最短路径节点序列。本文使用相似度系数SC来表示路径间的相似程度，其定义如式(13)所示：

(13)

其中，A表示待定位节点到目标锚节点的最短路径序列集合，B表示其余锚节点到目标锚节点的最短路径序列集合，n()为集合中元素的个数。计算集合A与不同集合B之间的相似度系数，其中相似度系数值最大的路径即为搜索结果。

步骤2平均跳距计算。相似路径搜索得到的结果是与待定位节点到目标锚节点路径最为相似的2个锚节点之间的路径。2个锚节点通过式(1)得到它们之间的平均跳距值，作为此待定位节点到目标锚节点的平均跳距。

步骤3平均跳距修正。在三维空间中，网络拓扑更加复杂，2个锚节点计算得出的平均跳距与它们之间的实际最优跳距(最大通信半径)存在偏差。本文计算得出平均跳距和最大通信半径之间的修正量φi，进而对平均跳距进行修正，定义误差系数ωi为：

ωi=(r-Hopsize)/r

(14)

其中，r为最大通信半径，Hopsize为计算得到的平均跳距。定义修正量φi为：

φi=Hopsize×ωi

(15)

修正量φi表示平均跳距与最大通信半径r之间的校正值，反映了平均跳距与理想距离r之间的差异。修正之后的平均跳距Hopsize′由式(16)计算得出：

Hopsize′=Hopsize+φi

(16)

步骤4依次计算所有待定位节点到各个锚节点之间修正后的平均跳距值。

通过多通信半径进行跳数优化及跳距修正的算法伪代码描述如算法1所示：

算法1跳数优化与跳距修正

输入:锚节点个数，总节点个数，最大通信半径r，多通信半径数量n。

输出:待定位节点到各个锚节点的距离。

1. Initial network environment;//初始化网络环境

2.fori=1 tondo //多通信半径广播

4.if(unknown nodes don’t receive the same signal)then

6.endif

7.endfor

8. Anchor nodes broadcast their packets;//多跳传播

9.if(unknown nodes receive the anchor nodes packets)then

10.Hop++;

11.Forward the message;

12.endif

13.if( the unknown node receive anchor nodes messages numbers < 4 )then//定位条件判断

14. the unknown node can’t be located;

15.else

16. Search path set ofB;//路径搜索

17. ComputingSCandHopsizeunknownby equation(13) and equation(1);//计算相似度与平均跳距

18. Corrected forHopsizeunknown;//平均跳距修正

19. Computing the distance from unknown nodes to anchor nodes by equation(2);//计算距离

20.endif

3.3 LSO算法求解待定位节点坐标

LSO算法对初值的要求不高，算法寻优速度较快，有较强的全局寻优能力。表1为在30维空间中，LSO算法、标准粒子群算法和人工蜂群算法对Sphere函数的寻优结果[14]。可以看出，LSO在高维空间中，具有收敛速度快、精度高和能较好地获得全局最优解的优点。本文将待定位节点坐标值的计算看作一种寻优问题，通过设置适应值函数，使用LSO在问题的求解空间中找到符合条件最优解，即为待定位节点的坐标值。

Table 1 Test results of three algorithms on Sphere function 表1 3种算法在Sphere函数上的测试结果

目标函数和LSO的适应值函数定义如下：

(17)

(18)

(19)

其中，(x,y,z)为狮群优化算法求解的待定位节点坐标；(xi,yi,zi)为锚节点坐标；di为待定位节点到锚节点i的距离；M为锚节点数量；εi为锚节点与搜索得到的待定位节点的距离与优化后的三维DV-Hop算法计算出的距离的差值；f(x,y,z)是在不同的权值条件下每一个εi的和，当求和最小时，得到的解即为最优解；fit为适应值函数，在进行寻优时，适应值越大，解越接近最优值。

狮群优化算法求解坐标的步骤如下：

步骤1在三维空间中随机初始化N个坐标值作为狮群中狮子的位置，设置最大迭代次数T，成年狮比例因子β。

步骤2计算狮群中不同角色狮子数量，狮王位置设置为初始种群最优位置，设置个体历史最优位置为各狮的当前位置。

步骤3根据式(5)～式(7)更新狮王、母狮和幼狮的位置，并根据式(19)计算适应度值。

步骤4更新自身和狮群历史最优位置。判断算法是否满足结束条件(发现理论值最优值或与最后2次最优值之差的绝对值小于设定精度)，如果满足转步骤6，否则转步骤5。

步骤5每隔一定迭代次数，重新排序(约10次)，确定狮王、母狮及幼狮位置，转步骤3。

步骤6输出狮王的位置，即待定位节点的坐标值，算法结束。

利用LSO算法求解待定位节点坐标的伪代码描述如算法2所示：

算法2狮群优化算法求解坐标值

输入:锚节点坐标，待定位节点到对应锚节点距离。

输出:待定位节点估计坐标值。

1. Initial number of lions:N, adult lion population:NL,Dimension:D,generation:G;//初始化参数值

2.g=-1;

3.fori=1 toNdo//初始化狮群位置

4.forj=1 toDdo

6.endfor

7.endfor

8.fori=1 toNdo

10.endfor

12.while(|fit(x)|>=ε)‖(g≤G)do/*迭代终止条件判断*/

17. Update;//更新个体最优和全局最优

18.endwhile

19.returnthe best solutionkingx.

4 仿真结果与分析

4.1 仿真实验设计与环境设置

本节使用Matlab进行编程仿真，对比分析锚节点个数、通信半径和节点个数3个参数的变化对HCLSO-3D定位算法、3D-DVHop和文献[16]定位算法的影响，证明HCLSO-3D定位算法的有效性和优越性。在相同环境下进行100次仿真实验，取平均值作为仿真实验最终结果，仿真实验区域设定为正立方体，在设定区域内随机生成100个包括待定位节点和锚节点的传感器网络节点。

网络环境与相关参数值设置如表2所示。

Table 2 Network environment and parameter settings表2 网络环境与参数设置

图2为仿真实验区域内WSNs随机生成的节点分布图，其中方形代表信标节点即锚节点，圆形代表待定位节点。

Figure 2 Random distribution of three-dimensional spatial nodes图2 三维空间节点随机分布图

在不同环境下的仿真实验结果需要相同的定位标准来衡量算法的定位效果，本文采用所有节点的平均定位误差作为衡量标准，其计算方法如式(20)所示：

ErrEavg=

(20)

其中，ErrEavg代表平均定位误差,(x′i,y′i,z′i)代表待定位节点i的实际坐标值，(xi,yi,zi)代表待定位节点i的估计坐标值，r为节点的最大通信半径，P为待定位节点的总数。

4.2 锚节点数与平均定位误差分析

图3为节点总数为100，通信半径为15 m条件下的不同锚节点数对3种算法定位效果的影响，3种定位算法的误差随着锚节点数量的增加都有不同程度的减小。HCLSO-3D定位算法在不同条件下定位误差置信区间为[45.9%,56.1%],[36%,44%],[28.8%,35.2%],[26.1%,31.9%],[23.94%,29.26%]。当锚节点数量为15～25时，HCLSO-3D定位算法平均定位误差低于3D-DVHop定位算法和文献[16]定位算法24.5%～27%和2%～6%，表明HCLSO-3D定位算法优势明显，具有较高的定位精度。因为HCLSO-3D定位算法不仅考虑了跳距和计算方法的影响，同时还对跳数进行了优化，文献[16]算法只对跳距和节点计算方法进行了优化。

Figure 3 Effect of the number of anchor nodes on the average positioning error of the algorithm图3 锚节点个数对算法平均定位误差的影响

4.3 不同通信半径与平均定位误差分析

图4是锚节点比例为15%情况下，不同通信半径对待定位节点平均定位误差的影响。HCLSO-3D定位算法在不同条件下定位误差置信区间为[45%,55%],[40.5%,49.5%],[34.2%,41.8%],[27%,33%],[22.5%,27.5%]。可以看出，HCLSO-3D定位算法在通信半径增加时，定位效果优于前2种算法。这是因为本文采用多通信半径和跳距修正的方式，使得利用优化跳数计算出的估计距离更接近实际距离，狮群优化算法求解的目标更准确，而前2种算法并没有考虑到这些因素对定位精度的影响。

Figure 4 Effect of communication radius on the average positioning error of the algorithm图4 通信半径对算法平均定位误差的影响

4.4 节点总数与平均定位误差分析

图5为节点总数的变化对待定位节点平均定位误差的影响。HCLSO-3D定位算法在不同条件下定位误差置信区间为[45.9%,56.1%],[40.95%,50.05%],[37.8%,46.2%],[32.4%,39.6%],[26.55%,32.45%],[24.12%,29.48%]。本文提出的算法整体性能相对稳定，定位效果相比3D-DVHop定位算法和文献[16]定位算法明显更好。仿真区域内节点总数的增加导致网络的连通性更好，锚节点通信范围内覆盖的待定位节点增加，使得节点的定位精度有所提高。

Figure 5 Effect of the number of nodes on the average positioning error of the algorithm图5 节点总数对算法平均定位误差的影响

4.5 计算开销分析

本节将算法的平均运行时间作为算法计算开销指标进行分析。表3为相同实验条件下所统计的HCLSO-3D定位算法、3D-DVHop算法和文献[16]算法的平均运行时间。由实验结果可以看出，HCLSO-3D定位算法平均运行时间略大于3D-DVHop算法和文献[16]算法的。因为HCLSO-3D定位算法使用多通信半径和智能算法求解待定位节点坐标，导致运算量加大，计算开销略有增加，但是定位精度明显提高。

Table 3 Average running time of the three algorithms表3 3种算法的平均运行时间

5 结束语

本文使用多通信半径的方法细化传统DV-Hop模型中的跳数，考虑跳数以及不同锚节点对待定位节点的影响不同，为减少对平均跳距和待定位节点到锚节点距离计算带来的累积误差，使用相似路径搜索算法获取与待定位节点到相应锚节点之间最相似的锚节点对的路径，修正此路径平均跳距为待定位节点到对应锚节点的平均跳距，减少其他锚节点的影响，降低平均跳距误差。由于狮群算法对初值的要求不高，算法寻优速度较快，有较强的全局寻优能力，本文使用狮群优化算法对待定位节点的坐标进行计算，得到了最优的坐标值，从而提高了定位精度。