基于改进SSA的DV-Hop传感器定位算法

刘瑞兴,段中兴

(西安建筑科技大学 信息与控制工程学院， 西安 710055)

1 引言

无线传感器网络(WSN)是当今物联网领域的研究热点，它由多个具有数据采集、分析和处理能力以及信息发送和接收能力的微型传感器节点组成。由于WSN中传感器节点的部署位置可以随时改变，灵活的对某些特定区域进行实时监测，在实际中如森林火灾预警、天然气管道泄漏、国防安全保卫工作等诸多领域得到了广泛应用。多数的WSN应用需要获得节点的位置信息，不含位置信息的数据往往是无用的。因此，WSN技术中节点定位问题成为了重点研究内容。WSN中传感器节点定位技术分为两类：第一类基于测距，定位精度高，目前该类型的方法主要有TOA、TDOA、RSSI等；第二类非测距，不需要进行实际物理测量，主要方法有Centroid，Amorphous，DV-Hop等，缺点是定位精度较低。其中，DV-Hop算法作为目前应用较广的定位算法之一，算法功耗小且适应性较强等特点可以满足大部分实际应用的定位需求，得到更多的研究。

传统的DV-Hop定位算法精度较低，研究学者对DV-Hop改进思路有2种：修正节点间的最小跳数和平均跳距；优化未知节点的位置。文献[10]引入遗传算法(GA)对跳数信标节点加权处理优化平均跳距，但是定位精度提升不足；文献[11]引入多通道半径细化节点间的最小跳数，提高定位精度，但是信标节点的多次广播加剧了传感器的能量消耗；文献[12]采用多通信半径方式和距离误差和跳数归一化优化最小跳数和平均跳距，并利用改进蝙蝠算法(BA)定位未知节点，提高了算法定位精度，但是增加了算法的复杂度，收敛速度变慢；文献[13]将斯蒂芬森迭代模型与传统的DV-Hop算法相融合，利用DV-Hop算法粗定位结果作为初值带入史蒂芬森模型得到最优估计位置，提高了算法精度，加快收敛速度，但是该算法仅仅针对DV-Hop的第3阶段进行改进，有很大的提升空间。针对上述研究存在的问题，提出一种基于改进SSA的DV-Hop传感器定位算法来提高定位精度。

2 DV-Hop算法误差分析与改进

2.1 传统DV-Hop算法原理

DV-Hop算法由Niculescu等提出，具体过程可以分为3个阶段：

第1阶段：信标节点通过泛洪向WSN网络中广播自身信息如图1所示，接收节点将收到的信息自建表格记录并根据广播不断更新表格，泛洪结束得到所有节点到信标节点的最小跳数。

第2阶段：利用式(1)计算出信标节点间的平均跳距。

(1)

式中: (,),(,)是信标节点的坐标；是信标节点,之间的跳数。未知节点将接收到第一个平均跳距信息作为自己的平均跳距，并通过式(2)计算其到信标节点的距离。

=×

(2)

第3阶段：采用最小二乘法计算未知节点的位置坐标。

信标节点编码信标节点坐标(x,y)跳数h

2.2 DV-Hop算法误差来源

DV-Hop算法误差主要来自以下3个方面：

1) 针对算法第1阶段进行分析，发现跳数是通过节点间的通信来完成的，相邻节点间相互感知到，即跳数为1，定义1跳的距离为通信半径。如图2(a)所示，跳数为1的实际距离明显不是通信半径，这样选择就会造成引入跳数误差。图中信标节点能与节点、、、进行通信，=1,=1,=1,=2，但是、、的距离相差较大，之间跳数记作2，对信标节点平均跳距影响较大，这种计算跳数的机制导致产生误差。

2) 平均跳距的选择不能通过单一的信标节点反应实际现象，这样选择忽略了其他信标节点的信息，在异构网络中，未知节点的选择不能反应真实的跳距。

3) 最小二乘法估计未知节点的位置会带来累计误差。

图2 多通信半径跳数计算示意图Fig.2 Multi-communication radius hop calculation

2.3 最小跳数修正

误差分析可以看出，节点之间的距离远近不同，只有将通信半径分级细化，才能更好地精确跳数。因此，提出了一种多通信半径优化节点间的跳数值。

如图2(b)所示建立模型，假设网络中信标节点通信半径为，将节点间划分级，网络中节点实际距离为，跳数记作,∈[1,]。

如式(3)所示，取=40,=4，如图2(c)所示=14,=12,=34,=1,=+=54，邻近信标节点跳数值是精确的小数，细化了跳数值提高跳数的准确性，减小定位误差。

(3)

最小跳数修正算法流程如下：

输入：设定,值，令=1；

输出：信标节点、未知节点最小跳数。

Begin

初始化网络；

For=1:

利用式(3)更新广播半径；

信标节点以()为半径通过泛洪向WSN网络中广播自身信息，接收节点将收到的信息自建表格记录，若没有则接收，但不转发；

=+1；

if>

break；

信标节点以为半径通过泛洪向WSN网络中广播自身信息，接收节点将收到的信息自建表格记录，最后将跳数值加1转发到网络中；

end

End

通过多次仿真实验得出∈[2,5]之间比较合适。值过大导致泛洪广播会极大消耗节点的能量，减少网络寿命，值过小导致跳数误差大，所以综合考虑节点定位精度与寿命，仿真实验将选用=4作为通信半径用来分级广播。

误差分析可以看出，节点之间距离远近不同，只有将通信半径分级细化，才能更好的精确跳数。

2.4 平均跳距校正

DV-Hop算法的误差主要是由于信标节点的平均跳距不准确造成的，提出采用加权平均值对信标节点平均跳距误差进行校正。具体流程如下：

Step 1 初始化网络中设定信标节点的数目；计算网络中所有信标节点的平均跳距记作，计算方式如式(4)所示：

(4)

Step 2 误差1通过第2阶段信标节点平均跳距与步骤1中的计算，如式(5)所示：

1=(-)

(5)

(6)

Step 4 全面考虑信标节点的误差来源，将Step 2、Step 3计算出的误差系数利用式(7)计算作为其余信标节点的权值。

(7)

Step 5 再次计算信标节点的平均跳距，计算信标节点的平均跳距方案如下：

1) 信标节点,两节点间的平均跳距为如式(8)所示。

(8)

2) 修正信标节点的平均跳距是信标节点与其余个信标节点的平均跳距加权，=1,2,…,-1，表示信标节点的权值，具体如式(9)所示。

(9)

2.5 建立目标函数

根据第1、2阶段得到的估计距离，将定位问题转化为求解坐标方程如式(10)所示：

(10)

式中:,,…,表示未知节点(,)与信标节点(,),(,),…,(,)之间的距离。第1、2阶段的测距误差为,,…,要求解未知节点(,)，只须使式(11)中的(,)最小，得到的误差值将最小。(,)可以被看作非线性函数进行求解:

(11)

非线性优化问题中，首先需要建立一个目标函数来求解。本文中目标函数如式(12)所示:

(12)

式中：为麻雀个体的适应度值；(,)为未知节点位置；(,)为信标节点的位置；为两者之间的距离。

3 改进麻雀搜索算法

3.1 麻雀搜索算法

麻雀搜索算法(SSA)是一种模拟麻雀种群觅食、逃避捕食者行为的启发式算法，基本思想：初始化种群数量为存在于维搜索空间的麻雀种群，则=[1,2,…]，=1,2,…,=1,2,…，表示第只麻雀在维搜索空间中的位置。

麻雀群体中发现者起主导作用，引领种群不断探索寻找食物，位置更新如式(13)所示：

(13)

跟随者依托发现者寻找食物，并可能和发现者争夺食物，提高自己捕食率，其位置更新如式(14)所示：

(14)

假设预警者约占麻雀种群的10～20，初始位置随机，则位置更新如式(15)所示:

(15)

3.2 改进麻雀搜索算法

3.2.1 精英反向学习策略

反向学习是Tizhoosh等在2005年提出的，通过研究得到反向解有时比原始解更能得到种群的最优值。精英反向学习是针对反向学习策略生成的反向解不一定比原始解更容易搜索到全局最优解这一问题提出的。

(16)

(17)

使用精英反向解对麻雀种群进行初始化时，对于原始麻雀目标函数值小于反向解麻雀，若对其反向区域进行搜索，降低种群的收敛速度。因此，文中将精英反向学习策略引入到SSA对DV-Hop定位算法进行优化，将原始麻雀与反向解麻雀的适应度值相对比，保留种群较优的麻雀个体可以扩大种群的搜索范围，避免盲目搜索也提高了算法的收敛速度。

3.2.2 发现者-跟随者自适应调整

原始SSA算法中，发现者和跟随者的数目比例是恒定的，这将导致在种群迭代前期，发现者的数目相对较少，缺乏引导种群全局探索的能力；后期，跟随者数目较少，缺少精确局部搜索的能力。因此，文中提出发现者-跟随者自适应调整策略，算法在开始阶段，拥有较多的发现者，随着迭代次数的增加，发现者的数目自适应减少，跟随者的数目增多，逐步从全局搜索转为局部精确搜索，从整体上提高算法的收敛精度。发现者和跟随者数目调整如式(19)、式(20)所示。

(18)

=·

(19)

=(1-)·

(20)

其中：为发现者数目；为跟随者数目；为比例系数，用于控制发现者和跟随者之间的数目；为扰动偏离因子，对非线性递减的值进行扰动；∈(0,1)的随机数。

323 柯西变异扰动策略

柯西变异取自连续型概率的柯西分布，主要特点为零处峰值较小，峰值到零值下降缓慢，使变异范围更均匀。变异如式(21)所示：

()=(1+tan(π(-05)))·

(21)

式中：为原来个体位置，()经过柯西变异后的个体位置，∈(0,1)随机数。

3.3 ISSADV-Hop算法流程

ISSADV-Hop算法是针对传统DV-Hop算法精度不高提出的，引入多通信半径优化节点间的跳数值；同时使用误差加权平均值，修正原始跳距；最后使用ISSA对未知节点进行定位。ISSADV-Hop具体算法实现流程：

1初始化网络区域，节点总数、信标节点和未知节点数目，随机初始化节点位置，通信半径，初始跳数=0，循环次数；

2利用改进后DV-Hop算法得到最小跳数和平均跳距，然后按照式(2)计算出未知节点到信标节点之间的距离；

3麻雀种群初始化，确定种群数量，设置迭代次数，安全阈值，比例系数，扰动偏离因子，以及种群的搜索范围和维数；

4引入精英反向学习策略初始化种群麻雀个体的位置，根据式(16)、式(17)按照要求对种群进行反向求解，进行适应度值的比较筛选出精英种群；

5根据式(19)、式(20)计算发现者和跟随者数量；

6根据式(13)～式(15)更新发现者、跟随者和警戒者位置；

7位置更新后，对种群加入柯西变异扰动，根据式(21)计算出扰动后麻雀的适应度值与前者比较，保留适应度值低的麻雀种群，然后记录当前种群的最优个体的位置；

8循环步骤5、6、7直到达到，得到麻雀种群中全局最优位置，也就是未知节点的近似位置。

ISSADV-Hop算法流程如图3所示。

图3 ISSADV-Hop算法的流程框图Fig.3 ISSADV-Hop algorithm flow

4 实验与结果分析

4.1 实验环境与参数设置

对ISSADV-Hop算法进行仿真和测试，实验环境在MATLAB2018b上运行。应用文中算法与传统DV-Hop算法相互之间进行比较，实验使用系统Window10，CPU：i5-6300U @ 2.40 GHz，RAM：4 GB，实验网络环境参数和ISSA参数初始值的设置见表1和表2。

表1 实验网络环境参数Table 1 Network environment construction

表2 ISSA参数初始值Table 2 The initial values of the parameters of ISSA

如式(22)所示，实验本身存在偶然性，为了减小误差，文中将实验重复200次计算平均值来得到最终结果。

(22)

式中：(,),(′,′)分别表示未知节点原始位置和实验定位出来的位置，表示实验使用的未知节点的数目，表示通信半径。查阅能耗资料，设定通信半径为30 m，节点数目设为100个，信标节点设为30个，与DV-Hop算法进行比较，进行200次仿真实验结果对比，结果如图4所示。

通过传统DV-Hop算法与文中提出ISSADV-Hop算法在相同实验条件下进行计算，图4(a)为节点初始化分布图；图4(b)为DV-Hop算法误差图，可以看出偏差大；图4(c)为本文中ISSADV-Hop算法定位出实际位置和估计未知的数据，可以清楚的看到改进后算法定位精度有大幅度提升；图4(d)为循环200次的误差，可以清楚的看到原始算法定位误差在0.3019，改进后算法精度保持在0.105 5，相比于改进前归一化定位误差降低了19.64%，定位精度有显著的提升。

为了进一步研究参数不同对定位精度的影响，将文中改进算法与DV-Hop、SSADV-Hop和IGWODV-Hop三种算法相对比进行仿真，通过改变通信半径、节点数量和信标节点数分别进行实验验证。

图4 节点初始化ISSADV-Hop、DV-Hop误差与迭代200次误差图Fig.4 ISSADV-Hop and DV-Hop error comparison

4.2 通信半径的影响

实验中部署节点数量为100个，信标节点数为30个，通信半径设置为20～50 m。实验结果如图5所示，随着网络中通信半径的增大可以提高算法的定位精度，通信半径的增加一定程度上可以为网络中传感器之间进行信息交流，改善网络中传感器的定位精度。与DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法归一化定位误差分别降低了7.54%、12.77%和5.48%。

图5 变通信半径对定位精度的影响曲线Fig.5 The influence of variable communication radius on positioning accuracy

4.3 节点数量的影响

实验中保持节点通信半径30 m不变，信标节点比例设为30%，节点数量设置在50～300个之间。从图6可以看出，增加节点数量可以改善网络的连通信，改善网络中传感器的定位精度。与DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法归一化定位误差分别降低了22.89%、14.46%和8.51%。

图6 变节点数目对定位误差的影响曲线Fig.6 The effect of changing the number of nodes on positioning error

4.4 信标节点的影响

实验中保持节点通信半径30 m不变，节点数量设置为100个之间信标节点数为10～40个。实验结果如图7所示，随着信标节点数量的不断增加提高了算法精度，这是由于信标节点数的增加精确了信标节点平均跳距。与DV-Hop、IGWODV-Hop、SSADV-Hop算法相比，ISSADV-Hop算法归一化定位误差分别降低了20.06%、12.95%和6.81%。

图7 变信标节点对定位误差的影响曲线Fig.7 The influence of variable beacon nodes on positioning error

4.5 定位耗时

实验构建过程，先通过跳数值和平均跳距的优化。然后使用精英反向学习构建麻雀种群、自适应策略以及添加扰动优化麻雀搜索算法来定位未知节点。可以发现计算量的增加主要是由于无线传感器网络中节点数量确定。

选取100 m×100 m的网络区域，通信半径为30 m，信标节点的比例为30%，节点数量设置在50～200个之间，迭代100次。本文算法与DV-Hop、SSADV-Hop和IGWODV-Hop三种算法相对比进行仿真，仿真消耗时间如表3所示。

表3 不同节点数量中4种算法的平均定位时间Table 3 Average positioning time of 4 algorithms in different numbers of nodes

表3中数据可以看出，节点数量和运行时间基本成比例上升。在物联网应用领域中，无线传感器一般都有较强的寿命更换周期较长，刚安装完毕也需要调试，所以文中提供的定位算法消耗的时间在可以承受范围内。而且，虽然文中提出的算法运行时间较长，但ISSADV-Hop算法极大的提升定位精度，这在定位算法评价指标中起着决定性的作用。

5 结论

利用提出的多通信半径方式优化节点间的跳数值，使跳数值更加精确；采用加权平均值校正平均跳距的误差。使用改进后的麻雀搜索算法对未知节点的位置进行估计，并优化了DV-Hop算法的总体框架，减小位置偏差提升定位精度。采用具体的仿真实例，与传统DV-Hop平均值比较精度有较大提高。

通过改变实验参数中不同因素对实验精度的影响，比传统的DV-Hop、SSADV-Hop和IGWODV-Hop算法更有效提升了定位精度。对比上述4种算法的定位耗时，文中提出的改进算法增加了一定的运行定位时间，后期研究工作将重点关注降低算法计算量和复杂度。