基于ASGSO算法的改进DV-Hop算法*

赵晓青，毛永毅

（西安邮电大学 电子工程学院，陕西 西安 710061）

基于ASGSO算法的改进DV-Hop算法*

赵晓青，毛永毅

（西安邮电大学 电子工程学院，陕西 西安 710061）

针对无线传感器网络定位技术中DV-Hop算法在最后阶段计算待定位节点坐标时定位精度低的问题，提出了一种基于自适应步长萤火虫优化算法的改进DV-Hop算法（ASGSODV-Hop）。该算法将DV-Hop算法在估算节点坐标阶段所使用的最小二乘法用ASGSO算法代替，采用ASGSO智能算法的自适应迭代寻优对DV-Hop算法定位求解的问题建立特定的适应度函数并进行多次迭代计算实现优化，最终使待定位节点坐标与真实值更为接近。仿真结果表明，该算法的平均定位误差约为23.58%；相比于传统DV-Hop算法，ASGSODV-Hop算法可在无需附加通信开销的情况下使定位误差降低约46.49%，提高了节点的定位精度。

无线传感器网络；DV-Hop算法；ASGSO算法；自适应迭代；定位精度

0 引言

无线传感器网络 （Wireless Sensor Networks，WSNs）是一种集信息采集、处理和传输于一身的智能网络信息系统［1］，可在任何时间、地点和环境下获取各种详细、精确的目标信息，实现人与物理世界的通信和信息交互，节点定位技术为WSN的关键技术。目前与定位相关的算法可分为测距和非测距两种，测距定位算法通常有很高的精度，但需要较大的通信开销和能耗；非测距定位算法是通过网络连通性来实现定位，无需附加的硬件支持，是目前定位机制的研究重点。传统的非测距定位算法有质心算法［2］、DV-Hop算法［3-4］、近三角形内点测试法（Approximate Point-in-triangulation Test，APIT）［5］等。

DV-Hop算法采取距离向量—跳段机制，由于其实现难度低，是一种常见的非测距定位算法。目前很多学者提出了一些改进算法以提高定位精度：文献［6］采用改进的加权最小二乘法得到待定位节点的坐标以提高定位精度，但通信量过大；文献［7］采用蝙蝠算法（Bat Algorithm，BA）对DV-Hop算法的定位结果进行优化，但消耗了过多的资源；文献［8］采用误差跳距加权策略修正平均跳距，并利用自适应步长粒子群优化（Self-adaptive Step Particle Swarm Optimization，ASPSO） 算法对DV-Hop算法的估计位置进行优化，精度有所提升，但增加了计算量和通信开销。本文采用自适应步长萤火虫优化 （Self-adaptive Step Glowworm Swarm Optimization，ASGSO）算法［9］对估算位置进行优化。仿真结果表明，在无需附加通信量和计算开销的基础上可减少定位误差，经过优化后算法的定位精度远大于DV-Hop算法的精度。

1 DV-Hop算法

DV-Hop算法是由Rutgers大学的 Dragons等人依据距离矢量路由和全球定位系统 （Global Positioning System，GPS）提出的一种非测距定位算法。其原理是采用距离矢量路由法得到待定位节点与信标节点间的跳数最小值，同时计算出平均跳距，以平均跳距与跳数最小值的乘积作为信标节点和待定位节点的估算间距，并通过极大似然估计法计算出待定位节点的坐标。DV-Hop算法可大体分为以下 3个阶段：

（1）获取待定位节点和信标节点间的最小跳数

由信标节点向相邻节点传送自身信标信息，包含信标节点的标识符、位置及跳数值，将跳数初始化为0。记录并更新所接收信标信息的邻居节点到每一信标节点的最小跳数并忽略较大的信标信息，跳数的值增加 1，继续向其邻居节点广播自身信息。当网路中的全部待定位节点均记下距每一信标节点的跳数最小值后此阶段终止。

（2）待定位节点与信标节点间距离的估计

经过第一阶段，信标节点 i得到与其余信标节点之间的位置信息和最小跳数后，用式（1）可计算出信标节点i与其余信标节点之间的平均跳距：

其中，（xi，yi），（xj，yj）分别表示信标节点 i、j的坐标，hj表示i距 j的跳数。

然后，信标节点将平均跳距分组扩散至整个网络内，可通过最小跳数和式（2）获取待定位节点与其他信标节点的间距。

（3）待定位节点自身位置的估算

已知（xi，yi）是第 i个信标节点的坐标，它到待定位节点M的距离为di，设（x，y）是待定位节点M的坐标，则有：

将式（3）变换成线性方程组 AX=b的形式，其中：

2 改进的DV-Hop算法

WSN定位问题实质上是对非线性方程组进行求解，为NP难解问题。DV-Hop算法在计算待定位节点和信标节点的间距时，由于待定位节点认为它到信标节点的平均跳距是相同的，会造成较大的定位误差。目前为止，已有学者提出用元启发式算法对定位后期的位置进行优化，如前文提到的BA算法和ASPSO算法。本文采用ASGSO算法对DV-Hop算法求出的待定位节点位置进行优化。

2.1 ASGSO算法

2.1.1 自适应步长调整策略

萤火虫群优化 （Glowworm Swarm Optimization，GSO）算法［10］是一种群智能算法，利用萤火虫发光吸引同伴这一现象进行模拟，发光越强便可吸引越多的同伴，每个萤火虫通过移向目标区域内最亮萤火虫寻求最优解。

原始GSO算法存在易陷入局部最优的缺陷，其计算精度较低，且最后阶段收敛速度较慢，这些问题与步长密切相关。寻优时萤火虫的移动步长越大则越容易寻求到全局最优解，但其寻优精度随之降低，甚至会出现震荡；移动步长小会造成寻优速度慢，但寻优精度得到提高。

针对此问题提出的ASGSO算法解决了原始GSO算法中存在的问题，有极好的寻优能力和寻优精度。引入荧光因子：

其中，Xi为第 i只萤火虫的状态，Xext为荧光素浓度最大的萤火虫的状态，dmax为最优萤火虫与剩余萤火虫的最大距离。

自适应步长调整办法为：

式中，smax和 smin为寻优步长的最大值和最小值，Hi为荧光因子。

根据式（7）、（8）自适应变换迭代步长，当萤火虫个体与目标萤火虫距离较近时，Hi值减小，则 si值相应减小，使用略小的步长si可使萤火虫接近目标个体，精度得以提高；当萤火虫与目标萤火虫距离较远时，Hi值的增大会造成 si值增大，可使萤火虫在步长略大时实现快速寻优。ASGSO通过灵活调整搜索步长提升了寻优的速度和精度。

2.1.2 算法描述

ASGSO算法流程如下：

（1）初始化。n只萤火虫组成萤火虫群，设定搜索维数m，感知最大半径rs及其变化系数β，最大迭代次数itermax，荧光素挥发系数 ρ及其更新率 γ，优秀萤火虫个体数 nt，原始位置 xi（0），原始荧光素大小 l0和感知范围r0，原始步长 si（0），最大步长 smax，最小步长 smin。

（2）荧光素更新。 J（xi（t））为迭代位置 xi（t）的目标函数。将萤火虫在 t次迭代位置 xi（t）相对应的 J（xi（t））转换成荧光素值 li（t）=（1-ρ）li（t-1）+γJ（xi（t）），萤火虫选取比自身荧光素高的个体组成邻域集 Ni（t），其中，0＜rdi（t）≤rs，rs为萤火虫的感知半径。

（3）概率选择。 个体 i移至邻域集个体 j的概率 pij用轮盘赌选取个体 j。

（4）自适应步长改变。利用式（7）计算每个个体的荧光因子，用式（8）计算出步长值。

（5）位置更新。根据xi（t+1）=xi（t）+s更新位置。

（6）更替决策域。 由 rdi（t+1）=min｛rs，max｛0，rdi（t）+ β（ni-|Ni（t）|）｝｝更新动态决策域半径。

（7）迭代结束。判断是否完成所设定的迭代次数，如果是则输出结果；否则转至步骤（2）。

2.2 基于ASGSO算法的改进DV-Hop算法

DV-Hop算法进行定位时，由于距离的不确定性导致误差存在。定位问题的要点是使误差达到最小，即提高定位精度，因此提出一种基于 ASGSO算法的改进DV-Hop算法，即ASGSODV-Hop算法。

设待定位节点的坐标为（x，y），利用式（2）可得待定位节点与第 i个信标节点的估算间距为 di，信标节点的估计间距与真实间距的偏差为 εi，则式（3）可改为：

通过观察式（9）可以看出，当（|ε1|+|ε2|+…+|εn|）的值最小时，所求得的未知节点（x，y）与真实节点位置最为接近。由于信标节点与待定位节点间的跳数越多会导致两者间距的估计偏差越大，故将其跳数的倒数当作权重设置ASGSO算法的适应度函数，如式（10）所示。完成所设定的运算次数后即可结束 ASGSO算法，以所寻求的最优值当作优化后的估算值。

其中，hi为待定位节点（x，y）与信标节点（xi，yi）间的跳数，1/hi为权重。

3 仿真实验

为评估ASGSODV-Hop算法的性能，分别对DVHop算法改进前后进行仿真，分析比对仿真得到的结果。将若干节点散播在 100m×100m正方形感知区域内，信标节点占 10%，待定位节点占 90%。为了降低随机性误差，在同等参数条件下进行 100次仿真，取其均值作为实验结果。

本文选取文献［11］提到的定位误差作为性能评价指标，如式（11）所示：

其中，R为通信半径，（xr，yr）为待定位节点的真实坐标，（xi，yi）为使用ASGSODV-Hop算法得出的待定位节点坐标，N为待定位节点的个数。

3.1 算法参数设置

设定种群规模 n=50，维数m=2，挥发系数 ρ=0.4，更新率 γ=0.6，初始荧光素大小 l0=5，感知范围 r0=10，初始步长 si（0）=0.03，变化系数 β=0.08，最大迭代次数itermax=200。

3.2 算法仿真结果分析

将 200个节点随机部署在上述网络拓扑结构中，通信半径设置为R=30m，图1和图2分别为DV-Hop算法和 ASGSODV-Hop算法的定位误差图，图中‘*’表示信标节点，‘o’ 表示待定位节点估计位置，‘▽’ 表示待定位节点实际位置，‘o’和‘▽’之间的连线表示待定位节点的定位误差，线段越长，定位误差越大，反之越小。从图中可看出，改进算法的估计位置和实际位置之间的线段更短，即它们之间的定位误差更小。通过DV-Hop算法得出的平均定位误差为 17.48， 定位精度为 34. 96%，ASGSODV-Hop算法的平均定位误差为 10.62，定位精度为21.24%。由此可知ASGSODV-Hop算法的平均定位误差和定位精度明显优于传统DV-Hop算法。

图1 传统DV-Hop定位误差

图2 ASGSODV-Hop定位误差

在定位技术中，通信半径、节点数及网络连通度的变化都会影响定位精度，下面分别讨论两种算法在不同通信半径、不同信标节点数以及不同网络连通度条件下的定位精度。

（1）不同通信半径

图3表示通信半径从 15m～40m时两种算法的平均定位误差曲线图，在区域内随机部署 200个节点，20个信标节点。从图中可知，在同样参数条件下，两种算法的平均定位误差均随通信半径的不断增加逐渐降低，并且当通信半径在 15m～30m范围内时，平均定位误差下降速率较快；通信半径在 30m以后时，平均定位误差趋于稳定，并且在稳定区域内，ASGSODV-Hop算法的平均定位误差比 DV-Hop减小约35.28%。在整个通信半径变化区域内，与DV-Hop算法相比较，ASGSODV-Hop算法的平均定位误差可降低约 43.51%，使精度明显提升。

图3 不同通信半径下平均定位误差曲线图

（2）不同节点数

图4表示通信半径为 R=30m、信标节点数为 20时，节点总数由 100变化至 400的平均定位误差曲线。从图中可看出，在相同条件下两种算法的平均定位误差均随节点数的增大而减小，并且当节点数在 200～400之间时，待定位节点误差趋于稳定。经分析可知 ASGSODV-Hop算法的平均定位误差比 DV-Hop算法降低了约47.98%；当节点数小于200时两种算法的定位误差下降幅度较大，此时与传统DV-Hop算法相比，ASGSODV-Hop算法的平均定位误差可下降约52.73%。

图4 不同节点数下平均定位误差曲线图

（3）不同网络连通度

由于 DV-Hop算法是根据网络连通性来进行定位的，网络连通度这个概念一定意义上可反映定位区域中节点间的相互位置、节点通信半径以及节点数量间的相互关系。图5为不同网络连通度下两种算法的平均定位误差曲线，从图中可清晰看出随着网络连通度参数值的升高定位误差逐渐减小，当网络连通度大于20时，两种算法的定位误差值变化都比较平缓。与传统DV-Hop算法相比，ASGSODV-Hop算法的平均定位误差降低约51.76%。

4 结论

图5 不同网络连通度下平均定位误差曲线图

本文在充分研究DV-Hop算法的基础上，针对定位精度较低这一缺点，在无需附加硬件和通信量的条件下采用ASGSO算法对DV-Hop算法的待定位节点坐标进行优化。通过理论分析和算法仿真实验证明，经ASGSO算法优化后的 DV-Hop算法使定位误差下降约46.49%，定位精度得到明显提高。此外，ASGSO算法的高效运行可有效提高 DV-Hop算法在 WSN中的适用性，使其应用更为广泛。

［1］郑军，张宝贤.无线传感器网络技术［M］.北京：机械工业出版社，2012.

［2］BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less low cost outdoor localization for very smal devices［J］.IEEE PersonalCommunications Magazine，2000，7（5）：28-34.

［3］NICULESCU D，NATH B.DV-based positioning in ad hoc networks［J］.Journal of Telecommunication Systems，2003，22（1）：267-280.

［4］NICOLESCU D，NATH B.Ad-Hoc positioxung systems（APS）［C］.Proc.of the 2001 IEEE Global Telecommunications Conference，San Antonio，USA，2001：2926-2931.

［5］He Tian，Huang Chengdu，BRIANm B，et al.Range-free localization schemes for large scale sensor networks［C］.In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，New York，USA，ACM Press，2003：81-95.

［6］涂巧玲，宋佳，胡涛.一种加权的DV-Hop定位改进算法［J］.通信技术，2013，46（9）：58-60.

［7］曹欲晓，张倩，李艳冰，等.基于蝙蝠算法的 DV-Hop定位改进［J］.计算机测量与控制，2015，23（4）：1273-1275.

［8］李仁和，丁勤，王洪元，等.基于自适应粒子群算法的改进DV-Hop定位算法 ［J］.计算机与应用化学，2014，31（10）：1201-1204.

［9］欧阳喆，周永权.自适应步长萤火虫优化算法［J］.计算机应用，2011，31（7）：1804-1807.

［10］吕聪颖.智能优化方法的研究及其应用［M］.北京：中国水利水电出版社，2014.

［11］张万里，宋启祥.遗传算法的 DV-Hop算法改进［J］.重庆大学学报，2015，38（3）：159-166.

The improved DV-Hop algorithm based on ASGSO algorithm

Zhao Xiaoqing，Mao Yongyi
（School of Electronic Engineering，Xi′an University of Posts and Telecommunications，Xi′an 710061，China）

Aiming at the coordinate′s low accuracy of unlocated node at the last step of DV-Hop algorithm in wireless sensor network，an improved DV-Hop algorithm （ASGSODV-Hop）based on self-adaptive step glowworm swarm optimization algorithm is adopted.Using ASGSO algorithm at the step of estimating the nodes coordinate of DV-Hop algorithm instead of the Least Square Method，the adaptive iteration optimization of ASGSO algorithm is adopted to construct a particular fitness function for the problem to be solved when using DV-Hop algorithm at the process of locating，and the optimization can be realized by multiple iteration which make the unlocated node more closed with the true value.The simulation result indicates that the average location error is about 23.58%.Compared with traditional DV-Hop algorithm，ASGSODV-Hop algorithm makes the location error reduced by 46.49%without adding communication cost and improves the location accuracy of the node.

wireless sensor network；DV-Hop algorithm；ASGSO algorithm；adaptive iteration；positional accuracy

TP393

A

1674-7720（2015）23-0058-04

赵晓青，毛永毅.基于ASGSO算法的改进DV-Hop算法［J］.微型机与应用，2015，34（23）：58-61.

2015-08-07）

赵晓青（1989-），女，硕士研究生，主要研究方向：卫星导航与定位。

陕西省自然科学基金资助项目（2014JM2-6088）

毛永毅（1969-），男，博士，教授，主要研究方向：移动台定位、无线传感器网络定位。