一种基于麻雀算法的优化DV-Hop定位算法

2022-09-15张国华孙国福

无线互联科技 2022年13期

陆霞,张国华,叶苗,孙国福

(南京师范大学泰州学院信息工程学院,江苏泰州 225300)

0 引言

无线传感网(Wireless Sensor Network, WSN)是由大量传感器节点构成的自组织无线通信网络,在农业、军事、医疗等领域广泛应用[1]。目前,传感器节点定位算法的研究主要集中在距离式定位和非距离式定位两个方面[2],RSSI,AOA,TOA等属于距离式定位算法[3];CL,APIT,DV-Hop等属于非距离式算法。其中,DV-Hop算法简单,运行开销低,当节点获取到3个及以上信标节点位置信息后就可以实现定位,使用较为普遍,但是对未知节点位置判断存在定位误差大、时间开销大等问题。

近年来,种群智能优化算法成为许多领域的研究热点,很多学者以此为契机针对DV-Hop算法提出了较多改进措施。林凤德等[4]在算法中引入遗传变异算子在种群中进行全局搜索,再使用蚁群算法进一步搜索,保留最优个体,算法提升了DV-Hop的定位精度,但仍有提升空间。石琴琴等[5]使用相似路径搜索算法估算节点跳距,并使用灰狼算法进一步修正跳距值,提升了DV-Hop算法的定位精度,但收敛性还有待进一步提高。麻雀搜索算法(Sparrow Search Algrithm,SSA)是一种新型的种群智能优化技术,相比较其他群体智能优化算法具有结构简单、速度快、易于扩充等优势[6]。本文提出的基于麻雀算法的DV-Hop优化定位算法具备更强的搜索能力,更快的收敛速度,即使在节点分布不均的WSN中,也能优化DV-Hop算法中未知节点坐标,进而提升定位精度。

实验结果对比分析,通过改变信标节点数量、通信半径、种群数量和迭代次数等条件,本文提出的优化算法相较于经典DV-Hop算法,在定位精度和收敛性能上有了显著提升。

1 DV-Hop算法分析

DV-Hop算法不使用直接测距的方法进行定位,而是借鉴了计算机网络中基于距离向量的路由机制,具体原理如图1所示。DV-Hop算法主要包含3个步骤。

图1 DV-Hop算法原理

(1)信标节点将包含自身信息的分组(包含编号、位置、到其他节点的跳数等)向邻居节点进行广播。通过广播所有节点不仅可以获取信标节点的位置,还能确定和信标节点之间的最小跳数。

(2)估算未知节点和信标节点间的距离。信标节点利用第一阶段中获取到的最小跳数,结合其他信标节点的位置,估算自身每跳的距离Hopi,再将包含跳距的信息分组广播转发给邻居节点,未知节点将收到信标节点的跳距乘以最小跳数,估算到各个信标节点之间的距离dij。

式中:(xi,yi)(xj,yj)是信标节点i和j的坐标,M是信标节点总数,hij是信标节点i与j(i≠j)之间的跳段数。

式中:Hopi是距离未知节点i最近的信标节点每跳的距离,hij是未知节点i与信标节点j之间的最小跳数。

(3)当未知节点获取到3个以上信标节点的距离数据,使用式(3)三边测量法估算未知节点的位置坐标[7]。

式中:(x,y)表示待估算的未知节点坐标,(xi,yi)表示信标节点坐标(i=1,2,…n),di表示未知节点和信标节点之间的距离。

通过上述对DV-Hop算法的描述发现,该算法实现容易、成本较低。但无线传感网中,传感器节点分布不均,且每个节点拥有的能量不等,DV-Hop算法也存在2个主要不足。

(1)算法实现过程中需要进行2次洪泛广播,第1次是未知节点从信标节点获取最小跳数和位置信息;第2次是信标节点告知估算得到的自身跳距。每次洪泛广播中,绝大部分节点都将参与其中,容易造成节点能量的浪费,增加无线传感网的能耗开销。

(2)误差的积累会造成未知传感器节点定位精度的降低。误差主要由2方面原因构成:①使用Hopi估算信标节点每跳的跳距,计算结果存在误差,进而使得求解未知节点距离信标节点的距离dij也存在误差。②在算法的第3个阶段,未知节点至少收到3个信标节点才能使用估算算法计算坐标,若信标节点组合中存在3点共线或近似共线问题,或者1个信标节点距离未知节点远,另外,2个信标节点距离未知节点近,未知节点定位精度会受到很大影响甚至会出错[8]。

2 基于麻雀算法的DV-Hop优化定位算法

DV-Hop算法中,根据第2阶段估算得到的距离,可以得到未知节点位置和距离之间的满足:

式中:δi表示误差值(i=1,2,…n)。建立优化算法的目标是将δi降低到最小,那么优化定位算法需要解决的问题可以归纳为:

即求F(xi,yi)的最小值。

2.1 优化定位算法数学模型

麻雀喜欢群居,圈养麻雀主要包含2种身份:发现者(Producer)和跟随者(Scrounger)。其中,发现者负责寻找食物并为整个种群提供觅食的区域和方向,跟随者则是利用发现者获取食物[6]。麻雀觅食过程使用“发现者-跟随者”模型,每只麻雀在种群中可以使用位置属性进行描述。

麻雀算法通过合适的迭代次数不断更新搜索范围,更新收敛最佳位置。麻雀觅食数学模型可以分为种群初始化、扩大觅食搜索范围和觅食位置定位3个过程。

2.1.1 种群初始化

种群中麻雀个体数量为n,指定位置较好的m只麻雀为发现者,剩余的(n-m)只麻雀为追随者,发现者数量变化范围[ul,ur],确定最大迭代次数T。种群初始化位置公式为:

使用式(4)作为每只麻雀的适应度函数。

2.1.2 扩大觅食搜索范围

发现者可以为种群觅食提供更大的搜索范围,便于种群觅得更多的食物。每次迭代过程中,发现者位置更新公式为:

式中:t表示当前迭代次数,α表示[0,1]之间的随机数。的更新参照式(7)计算。

2.1.3 觅食位置定位

觅食搜索过程中,跟随者时刻监视发现者动向,当它们察觉到发现者找到更好的食物,则立即前往食物所在位置,争夺发现者的食物。跟随者位置更新公式为:

式中:xworst表示第t次迭代时麻雀的最差位置,xp表示发现者目前最佳位置,表示发现者在t+1次迭代的最佳位置,A+表示每个元素随机赋1或-1的1×d的矩阵。当k＞时,表示第i个跟随者没有获得食物,觅食失败;当k≤时,表示第k个跟随者已经到达最优位置xp附近。的更新参照式(8)计算。

2.2 优化定位算法描述

基于麻雀算法的DV-Hop优化定位算法主要包含以下步骤:

步骤1:根据式(3)和式(4)使用经典DV-Hop算法估算未知节点和信标节点之间的跳距。

步骤2:初始化麻雀算法的基本参数(发现者数量及变化范围、种群数量、初始位置等),将未知节点周围已知的信标节点坐标作为初始麻雀的基本位置信息,根据式(6)将适应度取值低的麻雀作为发现者。

步骤3:在既定的最大迭代次数范围内,根据式(7)和式(8)不断更新发现者和跟随者的位置信息。

步骤4:在迭代过程中,若跟随者位置连续多次无更新,需进行种群个体变异,重新选择新的发现者继续进行位置更新,否则转步骤5。

步骤5:如果已达到最大迭代次数,输出最佳位置,最佳位置即为优化后的未知节点坐标,算法结束,否则重复步骤3和步骤4。

改进后的DV-Hop优化定位算法流程如图2所示。

图2 DV-Hop优化定位算法流程

3 实验结果与分析

3.1 实验环境

为了验证改进算法的定位精度,使用如表1所示的实验平台提供运行环境支持。假设所有传感器节点结构相同,且区域内任意2个节点均可通信,仿真网络环境参数设置如表2所示。以上述实验环境和参数设置为依据,分别变换信标节点数量、通信半径、种群数量和迭代次数,将DV-Hop算法、基于麻雀算法的DVHop算法(下文简称SSA DV-Hop)进行性能比对。采用平均相对定位误差作为评定指标,计算公式为: