基于全局人工鱼群算法优化的DV-Hop定位算法

余修武，秦晓坤，刘 永，余 昊

(南华大学 资源环境与安全工程学院，湖南 衡阳 421001)

在无线传感器网络（wireless sensor network, WSN）中，捕捉到有效的位置信息对于WSN的监测行为至关重要。因此，定位技术对于WSN有着无可替代的地位。定位技术的实现往往依赖于定位算法，现阶段的研究中，定位算法可以大致分为两类：第1类是基于距离（range-bases）的定位算法，该类算法通常需要硬件技术支持且能耗相对较高；第2类则是距离无关（range-free）的定位算法，该类算法无需测量节点间的距离或者角度，减少了对使用硬件设施的依赖，能耗也有所降低。基于range-free的定位算法主要有质心算法、Amorphous定位算法、APIT定位算法、DV-Hop定位算法。与基于range-bases的定位算法相比，基于range-free的定位算法在定位过程中往往会出现较大的误差，因此许多学者对该类算法提出了改进。

宋倩雯等利用行列式提供的几何约束对信标节点和未知节点的距离测量值进行修正，虽然提升了定位精度但增加了算法的复杂度。程超等先使用误差与距离的权值处理信标节点的平均每跳距离，再选择合适的跳段距离计算方法，最后使用改进的遗传算法优化未知节点坐标，但遗传算法参数较多，很难确定合适的参数。李文军等使用接收的信号强度指示(received signal strength indication，RSSI)测距技术测量DV-Hop定位算法中未知节点到信标节点的1跳距离，定位精度提高的同时却增加了硬件成本。Messous等提出同时使用 RSSI 技术和多项式近似来更好地估计未知节点和锚节点的距离的精度，虽提升了定位精度，但也增加了成本以及能耗。Mohamed等提出将位置估计转化为求解最小化问题，使用松鼠搜索算法进行寻优计算，但松鼠搜索算法结构较复杂，自适应参数较多，虽然提升了定位精度，但同时增加了算法复杂度。Rabhi等使用果蝇算法优化DV-Hop算法（DV-Hop and the fruit fly meta-heuristic，DV-Hop (FOA)），计算未知节点位置，该算法收敛速度快，参数少，但寻优精度不高。李娟等提出一种基于双通信半径的无线传感器网络DV-Hop定位算法，该算法仅仅优化了最小跳数，定位精度提升不够。林维维等提出CVLR（correction vector based distributed localization refinement algorithm）算法，构建位置校正矢量，将求精过程转换为最小化问题，使用迭代搜索算法求解，提升了定位精度，但增加了算法复杂度及能耗。Wang等提出逆距离加权方法对平均距离改进，并且用包容性检查规则来选择适当的锚点，虽然一定程度上提升了定位精度且没有增加算法复杂度，但定位精度提升不够。

针对DV-Hop定位算法存在定位误差问题，基于上述文献的研究，本文提出了一种基于全局人工鱼群算法优化的DV-Hop定位算法。该算法的主要思想是先对信标节点分配双通信半径来广播信息，利用最小均方误差准则计算出各信标节点的平均每跳距离；之后，计算出实际距离与计算距离的误差，并赋予权重，以此求得附近未知节点的平均每跳距离；然后，根据未知节点与信标节点的位置关系选择合适的计算距离的公式；最后，使用全局人工鱼群算法求得未知节点坐标。相比于人工鱼群算法，全局人工鱼群算法更容易跳出局部最优，提升算法收敛速度和寻优精度，在不增加硬件成本的同时实现精准定位。

1 DV-Hop定位算法及误差分析

1.1 DV-Hop定位算法

DV-Hop定位算法可以分为3个步骤：

1）记录信标节点与未知节点间的最小跳数。所有的信标节点向其通信半径范围内的所有节点传递自身位置信息及初始跳数（初始跳数为0）的数据分组，接收节点记录来自每个信标节点的跳数并比较跳数大小，只保留来自最小跳数的信标节点的数据分组，令跳数值加1并转发给其他节点。

2）获取信标节点与未知节点间的距离。信标节点利用步骤1）中得到的其他信标节点的位置信息及最小跳数，计算出自身的平均每跳距离，并将该信息通过广播的方式传递到网络，未知节点接收并记录第1个信标节点传来的平均每跳距离后，拒绝其他信标节点传来的此类信息。未知节点通过已有的跳数信息和平均每跳距离信息计算出到每个信标节点的距离。

3）未知节点计算自身位置。未知节点通过已知到信标节点的距离，利用3个或3个以上信标节点坐标计算自身位置。

1.2 DV-Hop算法误差分析

从上述定位过程中可以看出，误差的产生主要在步骤1）和步骤2）。信标节点利用自身与信标节点间的实际距离与最小跳数的比值求得平均每跳距离，即用直线距离来代替跳段距离。由于节点是随机分布的，各跳段并不在一条直线上，所以跳数越大，所造成的误差越大，导致定位出现误差。

未知节点在计算与信标节点距离时，仅仅采用与其最近的信标节点的平均每跳距离，而单个信标节点无法反映整个网络的节点部署信息，如果该信标节点平均每跳距离误差很大，则使得计算出的未知节点与信标节点间的距离也会存在很大误差，从而导致定位误差问题。

为解决上述定位误差问题，本文对DV-Hop算法进行了改进。

2 DEWF-D定位算法

本文提出的DEWF-D定位算法。首先，改进了最小跳数的获取方式，将最小跳数进行精确化处理；然后，改进了未知节点平均每跳距离的计算方法，使得到的结果误差更小；最后，使用全局人工鱼群算法代替极大似然估计法计算未知节点的坐标，使得到的结果更加精准。算法流程如图1所示。具体内容由第2.1～2.3节详细展开。

图1 DEWF-D算法流程图Fig. 1 Flow chart of DEWF-D algorithm

2.1 获取最小跳数

在DV-Hop算法中，未知节点在获取最小跳数时，无论距离信标节点远近，只要位于信标节点的感知范围内都会记为1跳，当不同的未知节点在计算与信标节点距离时采用相同的最小跳数，最终导致计算出的定位坐标有很大的误差。为此做出以下改进：

改进的跳数计算模型如图2所示，节点

A

为信标节点，其余为未知节点，

R

为通信半径。首先，节点

A

第1次以

R

/2广播信息，此时只有节点

B

可以接收到，节点

B

记录跳数值为0.5；然后，节点

A

第2次以

R

广播信息，节点

B

已经接收到了节点

A

的第1次的信息，舍弃节点

A

的第2次的信息并将接收的信息和跳数值0.5转发给邻居节点，节点

C

接收节点

A

的此次信息，将跳数记为1并转发给邻居节点。最后，节点

D

会接收到来自节点

B

、

C

的信息，因为节点

B

跳数较小，所以只保留节点

B

传来的信息，同时跳数加1，即节点

D

的跳数为1.5。

图2 跳数计算模型Fig. 2 Hop count calculation model

2.2 计算未知节点平均每跳距离

在DV-Hop算法中，未知节点获取平均每跳距离的方式是接收最近的信标节点的平均每跳距离。而信标节点计算的平均每跳距离会有很大误差，而且单个信标节点无法反映未知节点附近的节点部署信息。为此做出以下改进：

首先，改进信标节点的平均每跳距离。

在一般情况下，测量误差服从高斯分布，根据参数估计理论,均方误差作为估计子误差的代价函数比使用方差或误差更为合理。因此，本文采用均方误差作为误差的代价函数来计算信标节点的平均每跳距离。代价函数表达式为：

然后，计算信标节点平均每跳距离的误差及误差权重。

通过式（4）计算出信标节点平均每跳距离的误差：

通过式（5）计算误差权值：

由仿真计算得出未知节点在接收到最近的3个信标节点发来的信息时，误差最小，所以

m

的最佳取值为3。

最后，未知节点对来自3个最近的信标节点的平均每跳距离进行误差归一化加权处理，计算其平均每跳距离：

2.3 计算未知节点坐标

在DV-Hop算法中,求解定位坐标一般采用极大似然估计法，由于计算得出的未知节点到信标节点的距离并不是准确距离，采用该方法计算出的定位坐标会有很大的误差，为了减小误差，本文将定位问题转化为优化估算距离的问题，计算过程采用全局人工鱼群算法。

2.3.1 确定适应度函数

适应度函数表达式为：

2.3.2 确定适应度函数的搜索区域

如图3所示，节点

A

、

B

、

C

为距离未知节点最近的3个信标节点，由式（8）求出这3个节点到未知节点的距离，分别为

R

、

R

、

R

，以信标节点为圆心，各自到未知节点的距离为半径做圆，圆心分别用(

x

,

y

)、(

x

,

y

)、(

x

,

y

)表示。因为式（8）求出的距离往往会大于实际距离，所以未知节点必然会位于3个圆相交的公共区域。已知圆心坐标和半径，就可以求出3个圆的函数表达式：

图3 搜索区域计算模型Fig. 3 Search area calculation model

通过式（9）求出3个圆的交点

D

、

E

、

F

的坐标。以点

D

、

E

、

F

为顶点做三角形，设边

EF

为三角形的最长边，线段

DG

为三角形的高。以边

EF

为长、

DG

为宽做出矩形，该矩形就是所要确定的搜索区域。

2.3.3 全局人工鱼群算法求解适应度函数

本文采用全局人工鱼群算法求解适应度函数。

每条人工鱼被封装为函数和变量两个部分：函数包括行为函数（人工鱼进行的各种行为，包括觅食、聚群、追尾、跳跃、吞食等）和目标函数；变量包括人工鱼总数

W

、状态

X

、最大步长

S

、视野

V

、尝试次数

T

、拥挤度因子δ，以及个体之间的距离

R

。行为函数描述如下：

1）觅食行为

设人工鱼的状态为

X

，由式（10）选择一个状态

X

，

若不满足，则继续选择。一直尝试

T

次后，如果仍不满足前进条件，则更新：

2）聚群行为

否则，执行觅食行为。

3）追尾行为

否则，执行觅食行为。

4）跳跃行为

迭代了

I

次后，若最优人工鱼的适应度值不满足预期要求，就随机选取一些人工鱼，并随机设定其参数为：

式中， β可以是一个参数，也可以是使人工鱼的参数产生突变的函数。

5）吞食行为

算法迭代

I

/2次后，若某条人工鱼的适应度值总是高于预设值，则舍弃该鱼，且人工鱼的总数

W

减1。

全局人工鱼群算法求解适应度函数的步骤如下：

Step1：初始化参数，包括人工鱼总数

W

、每条人工鱼的初始位置、步长

S

、视野

V

、尝试次数

T

、迭代次数

I

、拥挤度因子δ、执行吞食行为的阈值；

Step2：计算每条人工鱼的适应度值，并记录全局最优的人工鱼状态；

Step3：对每条人工鱼进行评价，对其要执行的行为进行选择，包括觅食行为、聚群行为、追尾行为、吞食行为、跳跃行为；

Step4：执行人工鱼选择的行为，基于全局信息和局部信息更新人工鱼的位置信息；

Step5：更新全局最优人工鱼的状态；

Step6：若满足循环结束的条件则输出结果，否则跳转到Step2。

3 仿真实验结果与分析

用MATLAB（R2018b）软件进行仿真测试，测试使用的电脑配置为Intel(R) Core(TM) i5–7200U CPU@ 2.50 GHz，系统为Windows 10 家庭中文版。对比算法为DV-Hop算法、DV-Hop (FOA)算法和CVLR算法。主要给出了节点定位误差，及信标节点密度和通信半径对定位精度的影响。仿真参数设置如表1所示。

表1 仿真参数
Tab. 1 Simulation parameters

参数取值网络区域面积Z/(m×m)100×100节点总数X100信标节点数量M5、10、15、20、25、30通信半径/m10、15、20、25、30人工鱼总数W20迭代次数I100人工鱼步长S/m0.6视野V/m1.5尝试次数T50 δ拥挤度因子0.1

评价算法的性能指标选用归一化平均定位误差公式如下：

式中，(

x

,

y

)为节点

i

的真实坐标，()为节点

i

的计算出来的坐标，

N

为未知节点个数，

R

为通信半径。

3.1 节点定位误差

图4是DEWF-D与DV-Hop算法定位节点坐标的误差对比。两种算法参数统一，其中，信标节点数量设为25，未知节点数量设为75，通信半径设为30 m。

图4 两种算法节点定位误差Fig. 4 Node positioning errors of two algorithms

从图4中可以看出：DV-Hop算法定位误差值在4～30 m，平均误差为18.6 m；而DEWF-D算法定位误差在2～15 m，平均误差为6.5；DEWF-D算法定位误差减少了12.1 m，说明本文改进的DEWF-D算法能有效提升传统DV-Hop算法的定位精度。

3.2 信标节点密度对定位的影响

采用DEWF-D、DV-Hop、CVLR和DV-Hop (FOA)算法，对比信标节点密度对定位精度的影响如图5所示。其中，节点数量总共为100，分别对信标节点数量为5、10、15、20、25、30时进行测试，每种情况测试70次，选用式（16）得到归一化平均定位误差，并取70次的平均值。

图5 不同算法、信标节点密度下的定位误差Fig. 5 Positioning errors under different algorithms and beacon node densities

从图5可以观察出：随着信标节点的数量从5逐步增加至30，4种算法的定位误差都在不同程度上减小，用DEWF-D算法算出的定位误差总是比其余3种算法得到的定位误差小。DEWF-D算法的平均定位误差比DV-HOP算法、CVLR算法和DV-Hop (FOA)算法定位误差分别减少了28.3%、6.9%、12.5%。说明在不同信标节点密度下，本文改进的DEWF-D算法要优于其他对比的定位算法。

3.3 通信半径对定位的影响

采用DEWF-D、DV-Hop、CVLR和DV-Hop (FOA)算法，对比通信半径对定位精度的影响如图6所示。网络区域内设置100个节点，其中，信标节点数量为25，未知节点数量为75。设置5组不同的通信半径进行测试，分别为10、15、20、25、30。每组测试50次，选用式（16）得到归一化平均定位误差公式，并取50次的平均值。

图6 不同算法、通信半径下的定位误差Fig. 6 Positioning errors under different algorithms and communication radius

从图6可以观察出：随着通信半径逐步增大，4种算法的定位误差都存在不同程度的减小；而DEWF-D算法的定位误差明显比其余3种算法的定位误差小；DEWF-D算法的平均定位误差比DV-HOP、CVLR和DV-Hop (FOA)算法的定位误差分别减少了24.4%、7.6%、14.8%。说明在不同通信半径下，本文改进的DEWF-D算法要优于其他定位算法。

4 结 论

为解决DV-Hop定位算法存在较大定位误差的问题，本文在DV-Hop定位算法的基础上做出改进，提出了DEWF-D算法。首先，改进了最小跳数的获取方式，将最小跳数进行精确化处理；然后，改进了未知节点平均每跳距离的计算方法，使得到的结果误差更小；最后，使用全局人工鱼群算法代替极大似然估计法计算未知节点的坐标，使得到的结果更加精准。仿真实验表明：在无需增加成本的情况下，相比于DV-Hop定位算法、CVLR算法和DV-Hop (FOA)算法，DEWF-D定位算法可以有效提升定位精度。由于在改进最小跳数时增加了信标节点的通信次数，而且计算节点坐标时使用了群智能算法，虽然提升了定位精度，但是使得节点能耗增加，因此如何降低节点的能耗将做进一步研究。