基于连续跳数的DV-Hop改进定位算法

张 航,龙道银,覃 涛,王 霄,3,杨 靖,3

1(贵州大学 电气工程学院,贵阳 550025)

2(中国电建集团贵州工程有限公司,贵阳 550025)

3(贵州省互联网+协同智能制造重点实验室,贵阳 550025)

1 引 言

无线传感器网络(Wireless Sensor Network,WSN)是由大量耗能少、价格低的微型传感器组成的网络系统[1].WSN常被用于信息感知及数据采集与处理,在军事、环境监测、物联网、网络物理系统、家庭办公自动化、天气预报、预警和救援等领域得到了广泛应用[2].在这些应用中节点定位是关键技术之一[3],若传感器采集的数据没有地理位置信息,则采集的数据将失去应用价值[4].

WSN定位算法的分类有多种,依据是否需要测量距离可分为测距算法和非测距算法[5].测距算法的定位精度高,但需要额外的测距设备;非测距算法只需利用网络连通性、拓扑关系即可实现定位,尽管定位精度不如测距算法,但因其成本低、定位过程简单而被广泛采用.

DV-Hop算法是一种经典的非测距定位算法,针对其定位精度较低的问题,很多学者提出了改进策略[6].文献[7,8]和文献[9]分别提出了基于双通信半径、多通信半径的定位算法,通过信标节点多次广播优化最小跳数,但是这种方式只优化了信标节点与未知节点间的最小跳数,未知节点与未知节点间的跳数的并未得到优化.文献[10]提出了一种具有跳数校正和平均跳数加权的DV-Hop定位算法.节点将接收到的信号强度值通过Shadowing传播模型转换为节点之间的距离,用距离值与节点间通信半径的比值校正跳数,但是将信号强度值转换为距离时未进行滤波处理,导致转换后的距离误差较大.文献[11]将加权双曲线法和加权DV-Hop算法融合,用加权DV-Hop算法估计待定位节点与信标节点间的距离,用加权双曲线法计算相关权重,提高了定位精度,但信标节点较少时定位效果较差.

除了对跳数和平均跳距值进行优化外,也有不少学者利用群智能优化算法对DV-Hop算法进行改进.文献[12,13]分别利用粒子群优化(Particle Swarm optimization,PSO)、遗传算法取代最小二乘法,以距离为约束条件对未知节点的最优位置进行搜索,提高了节点的定位精度,但由于算法中所测得的距离误差较大,导致提高的定位精度有限.文献[14]利用相邻节点间的公共节点个数优化跳数,并结合差分进化算法(Differential Evolution Algorithm,DE)估算未知节点坐标,但由于相邻节点间距离的计算较复杂,导致算法运行时间较长,使得该算法较难应用到对实时性有要求的场合.

针对已有算法的不足,本文首先对DV-Hop算法的误差来源及连续跳数模型进行分析;然后提出一种PSO优化的基于连续跳数的DV-Hop改进定位算法(PSOCHDV-Hop),该算法引入Ochiai系数逼近相邻节点间的通信重叠面积,利用泰勒公式简化现有连续跳数模型中节点间距离的计算,采用最小均方差准则对平均跳距进行优化并利用粒子群算法对未知节点位置进行求解;最后通过仿真验证本文算法的有效性.

2 相关理论

2.1 DV-Hop算法

DV-Hop定位算法最初由美国路特葛斯大学的Dragos Niculescu等人提出的[15],主要分为以下3个阶段.

Step 1.所有信标节点以泛洪的模式将自身位置信息和初始跳数值0发送给通信区域内的所有节点,未知节点接收到该数据后,保留该数据,并将接收到的跳数值加1,继续转发至网络中的所有未知节点均能获得到每个信标节点的最小跳数.

Step 2.估算节点间单跳距离并计算未知节点到信标节点间的距离.利用Step 1获得的数据通过式(1)计算节点间平均单跳距离：

(1)

式中：(xi,yi)与(xj,yj)为信标节点i和j的实际位置坐标,hij为信标节点i与j之间的最小跳数,Hopsizei为信标节点i的平均单跳距离.

然后估算出未知节点到各信标节点间的距离duj,具体计算如式(2)所示：

duj=Hopsizeuj×huj

(2)

Step 3.通过最小二乘法求出未知节点位置.

2.2 DV-Hop算法误差

DV-Hop算法主要误差来源是未知节点与信标节点间的最小跳数及平均单跳距离的计算.首先,离散跳数很难克服节点间距离不同、跳数值相同的不足.其次,DV-Hop算法采用折线距离代替直线距离,由式(1)计算的平均跳距对于每条传输路径而言并不是最优的.最后,由于未知节点的估计值易受到最小二乘法累加误差的影响,导致定位算法精度不高.

2.3 连续跳数模型与分析

在图1所示的无线传感器网络的监测区域内任取两个相邻节点i和j,设相邻节点i和j通信范围的相交区域为Sij、节点i和j的距离为lij,R为通信范围的半径.则Sij与lij之间的几何关系为：

图1 相邻节点的交集

(3)

假设Sij已知,则lij的具体数值可由式(3)求出.记节点i和节点j之间的连续跳数为CHij,则CHij的计算如式(4).

(4)

理论上节点间跳数的连续化可有效解决同一节点通信范围内所有节点与该节点跳数相同、距离不同的问题,而且,跳数的连续化可有效提高定位精度.文献[16]在不考虑噪声的干扰下,利用接收信号强度值将跳数连续化,平均定位误差可降至10%以下.但是如何根据网络已有信息计算Sij是需要解决的难点,此外根据式(3)求解lij需要借助特定的数学函数,由于WSN规模大、节点计算能力弱等特性,利用数学函数进行求解会消耗过多的运行时间和节点能量,不利于连续跳数模型在WSN定位中的推广.

3 PSOCHDV-Hop算法

本文算法首先引入Ochiai系数从已有的节点连通信息中求得相邻接节点通信范围相交区域的面积,然后利用泰勒公式对连续跳数模型进行化简,得到相邻节点间的连续跳数,其次利用最小均方误差准则对跳距进行优化,并由连续跳数和优化后的跳距计算出未知节点与各信标节点间的距离,最后采用PSO优化算法计算未知节点的位置.

3.1 跳数连续化

针对连续跳数模型中Sij的求解,本文使用 Ochiai 系数进行计算[17],Ochiai系数的定义如式(5)所示：

(5)

式中：A和B是集合,γ()表示集合中的元素个数,Ochiai(A,B) 表示集合A和集合B的相似度.在本文中分别将Pi、Pj、Pij视作A、B、A∩B中元素的个数,则Sij计算如式(6)所示：

(6)

为简化式(4)中lij的计算,本文运用泰勒公式对其进行化简,具体见式(7)、式(8).

(7)

(8)

式中：

(9)

则由式(7)、式(8)、式(9)及式(3)可得：

(10)

根据计算所得的lij再由式(4)将相邻节点i和j间的跳数连续化.

3.2 跳距修正

针对平均单跳距离对定位精度影响较大这一问题,本文采用最小均方误差准则对信标节点计算的平均跳距进行校正[18],校正后的平均每跳距离为：

(11)

式中：hopsij为信标节点i和j之间的真实跳数,dij为信标节点i和j之间的欧式距离.

3.3 节点位置计算

PSO算法是由R.Eberhart和J.Kennedy博士提出的一种智能优化算法[19],其原理为：在目标区域内使用一定数量的粒子,通过粒子的速度和位置更新,不断寻找最优解.本文将WSN定位问题转换为数学优化问题,并定义适应度函数：

(12)

式中：(xu,yu)为第t次迭代中未知节点u的坐标估计值,(xi,yi)为第i个信标节点的坐标,m为信标节点的个数.

利用式(12)计算出粒子的适应度值,更新粒子的局部最优值和全局最优值,并用式(13)、式(14)更新粒子速度和粒子位置,不断循环此过程,直至达到最大迭代次数.此时计算所得的(xu,yu)即为节点的最优位置.

(13)

(14)

式中：w为粒子的惯性权重,c1、c2为学习因子,w1、w2取[0,1]范围内的均匀随机数.

本文通过实验的方法,在保证节点距离、种群规模、迭代次数完全相同的情况下,对比了粒子群优化、差分进化、灰狼优化3种群体智能优化算法在取代最小二乘法后的定位精度、运行耗时,如表1所示.由表1可知,3种优化算法所取得的定位精度误差不足1%,其中PSO所得到的定位精度最高,且运行耗时最短.因此本文采用PSO计算未知节点位置.

表1 3种优化算法取代最小二乘法的比较

3.4 算法流程图

PSOCHDV-Hop算法的流程图如图2所示.

图2 PSOCHDV-Hop算法流程图

4 MATLAB仿真结果与分析

本文仿真实验环境：Windows 10 操作系统,Intel(R)Core(TM)i5-4210M CPU @2.6G主频,8G内存,Matlab 2019b.本文针对PSOCHDV-Hop、DV-Hop 算法[15]、基于粒子群的DV-Hop 改进算法(PSODV-Hop)[12]、基于双通信半径的DV-Hop算法(2RDV-Hop)[7]、基于DV-Hop和差分进化的连续定位算法(DECHDV-Hop)[14]在测距精度、定位精度、算法时间复杂度等方面进行了仿真和分析.仿真结果均为运行 100 次后的平均值,采用的测距精度(ADE)、定位精度(ALE)性能指标如式(15)、式(16),所采用的模型参数见表2-表4.

表2 信标节点可变时的仿真参数

表3 总节点数可变时的仿真参数

表4 通信半径变化时的仿真参数

(15)

(16)

PSODV-Hop算法与本文在位置估计阶段所采用的PSO算法参数保持一致,具体见表5;DECHDV-Hop算法在位置估计阶段所采用的DE算法参数与原文献保持一致.

表5 粒子群算法的仿真参数

4.1 距离估计精度

图 3(a)-图3(c)分别表示了信标节点比例、总节点数及通信半径的仿真参数变化时,5种算法的测距精度表现.其中DV-Hop算法和PSODV-Hop算法的最大区别在于节点位置计算方法的选择上,而在第1、第2阶段定位方法完全一提高,5种算法的测距误差都呈下降趋势,本文算法测距精度最高;随着节点总数增加,本文算法的测距精度均优于其余4种算法;随着通信半径增大,DV-Hop算法、PSODV-Hop算法在通信半径大于20m、2RDVHop算法大于30m时测距误差随着通信半径的增大而增加,这是因为节点的通信半径越大,离散跳数所对应的误差就越大,而DECHDV-Hop算法、PSOCHDV-Hop采用了连续跳数,通信半径越大通信范围内的节点数就越多,连续跳数的值就会更加精确,因此DECHDV-Hop算法、PSOCHDV-Hop 的测距误差会随半径的增大而减小,其中本文算法的测距误差较小.在上面场景中,本文算法的测距精度整体表现较高.

图3 测距误差分析图

4.2 平均定位误差

图 4(a)-图4(c)分别表示了信标节点比例、节点个数及通信半径的仿真参数变化时,5种算法的定位精度表现.随着信标节点比例提高,本文算法较之原 DV-Hop 平均定位精度可提高约14.3%,较之 PSODV-Hop平均定位精度可提高约4.8%,较之2RDV-Hop平均定位精度可提高约4.7%,较之 DECHDV-Hop平均定位精度可提高约1.8%;随着节点总数增加,本文算法较之原 DV-Hop、PSODV-Hop、DECHDV-Hop平均定位精度可分别提高约16%、6%、4%和1.5%;随着通信半径增大,本文算法较之原 DV-Hop、PSODV-Hop、DECHDV-Hop平均定位精度可分别提高约16.7%、7.4%、6.6%和1.8%.在各类场景下,本文算法的定位精度整体表现较高.

图4 平均定位误差分析图

4.3 时间复杂度

在WSN定位算法中,由于能量受限,算法的复杂度也是一项重要指标.假设WSN的总节点数为n,未知节点数为m,整个网络内共有q对相邻节点,DECHDV-Hop算法在计算节点坐标时采用的DE及PSODV-Hop算法、本文算法采用的PSO的迭代次数为G、种群数目为N、空间维数为D,其中N≫D,省略低阶项后,各阶段的时间复杂度如表6所示.

表6 5种算法各阶段的时间复杂度

从表6可以看出DV-Hop算法的时间复杂度为Ο(n3)+Ο(n)+Ο(m),PSODV-Hop算法的时间复杂度为Ο(n3)+Ο(n)+6×Ο(m×G×N),2RDV-Hop算法的时间复杂度与DV-Hop算法相同,DECHDV-Hop算法的复杂度为Ο(n3)+2×Ο(n2)+q×Ο(f)+Ο(n)+9×Ο(m×G×N),其中Ο(f)为计算一对相邻节点的时间复杂度,PSOCHDV-Hop算法的时间复杂度为Ο(n3)+Ο(n2)+Ο(n)+6×Ο(m×G×N).综上,本文算法的时间复杂度虽略高于DV-Hop、PSODV-Hop、2RDV-Hop,但低于现有连续DV-Hop算法,即DECHDV-Hop算法.

从综合性能上看,本文算法在定位精度和计算复杂度上得到了较好的平衡.

5 结 论

对于DV-Hop算法定位精度不高、DECHDV-Hop算法运行耗时过长等不足,本文提出了一种基于连续跳数的改进DV-Hop定位算法PSOCHDV-Hop.首先,采用ochiai系数求出相邻接点的通信重叠面积并运用泰勒级数对现有连续跳数模型进行了简化;然后,运用最小均方误差准则对节点间的平均单跳距离进行改进,提高了算法的测距精度;最后,在节点位置估计阶段,将定位问题转换为优化问题,并利用PSO算法进行求解,得到了较高的定位精度.实验仿真结果表明,本文设计的改进算法PSOCHDV-Hop在时间复杂度上要优于现有的连续DV-Hop定位算法,在测距精度、定位精度方面较DV-Hop算法、PSODV-Hop算法、2RDV-Hop算法、DECHDV-Hop算法表现出了更好的性能.