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

余修武 秦晓坤 刘永 余昊

余修武, 秦晓坤, 刘永, 等. 基于全局人工鱼群算法优化的DV-Hop定位算法 [J]. 工程科学与技术, 2022, 54(4): 228-234. doi: 10.15961/j.jsuese.202100251
引用本文: 余修武, 秦晓坤, 刘永, 等. 基于全局人工鱼群算法优化的DV-Hop定位算法 [J]. 工程科学与技术, 2022, 54(4): 228-234. doi: 10.15961/j.jsuese.202100251
YU Xiuwu, QIN Xiaokun, LIU Yong, et al. DV-Hop Localization Algorithm Optimized Based on Global Artificial Fish Swarm Algorithm [J]. Advanced Engineering Sciences, 2022, 54(4): 228-234. doi: 10.15961/j.jsuese.202100251
Citation: YU Xiuwu, QIN Xiaokun, LIU Yong, et al. DV-Hop Localization Algorithm Optimized Based on Global Artificial Fish Swarm Algorithm [J]. Advanced Engineering Sciences, 2022, 54(4): 228-234. doi: 10.15961/j.jsuese.202100251

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

基金项目: 湖南省市联合自然科学基金项目(2021JJ50093);湖南省重点研发计划项目(2018SK2055) ;国家自然科学基金项目(11875164);湖南省研究生科研创新项目 (CX20200921)
详细信息
    • 收稿日期:  2021-03-24
    • 网络出版时间:  2022-07-05 04:11:40
  • 作者简介:

    余修武(1976—),男,教授,硕士生导师,博士. 研究方向:无线传感器网络与智能安全监控、铀矿冶安全与核污染在线监测预警和电气安全工程. E-mail:yxw2008xy@163.com

    通信作者:

    秦晓坤, E-mail: 2499856398@qq.com

  • 中图分类号: TP393

DV-Hop Localization Algorithm Optimized Based on Global Artificial Fish Swarm Algorithm

  • 摘要: 无线传感器网络具有大规模、自组织、可靠性、以数据为中心、集成化等特点,被广泛应用于军事、医疗、矿山监测、安全生产等领域。然而现有的无线传感器网络非测距定位算法存在定位误差较大的问题。针对该问题,本文提出一种基于全局人工鱼群算法优化的DV-Hop(distance vector-hop)定位算法,即DEWF-D定位算法。该算法对非测距定位算法中的DV-Hop算法出现误差的步骤进行优化处理,通过减小算法过程中出现的误差,最终得到较为精准的定位坐标。首先,使信标节点以两种不同的通信半径传递消息,将跳数进行精确化处理,以减少跳数带来的误差;然后,用最小均方误差准则和误差加权方式计算平均每跳距离;最后,利用全局人工鱼群算法替换三边测量法进行坐标计算。仿真验证表明,在不同信标节点密度下,本文提出的DEWF-D算法与DV-Hop算法及其他算法相比定位精度分别提升28.3%、6.9%、12.5%;而在不同通信半径下,定位精度分别提升了24.4%、7.6%、14.8%。证明DEWF-D算法能有效提升定位精度,解决了定位算法中出现的定位误差较大问题。

     

    Abstract: Wireless sensor networks have the characteristics of large scale, self-organization, reliability, data-centricity, integration, etc., and are widely used in military, medical, mine monitoring, safety production and other fields. However, the existing non-ranging positioning algorithms for wireless sensor networks suffer from large positioning errors. Aiming at this problem, a DV-Hop (distance vector-hop) localization algorithm based on the global artificial fish swarm algorithm optimization was proposed, namely DEWF-D localization algorithm. In the algorithm, the error-prone steps of the DV-Hop algorithm were optimized in the non-ranging positioning algorithm, and finally more accurate positioning coordinates were obtained by reducing the errors in the algorithm process. First, messages were transmitted by the beacon nodes with two different communication radii, and the number of hops was precisely processed to reduce the error caused by the number of hops; then, the average distance per hop was calculated using the minimum mean square error criterion and the error weighting method; Finally, the global artificial fish swarm algorithm was used to replace the trilateration method for coordinate calculation. Simulation results showed that, compared with the DV-Hop algorithm and other algorithms, the positioning accuracy of the proposed algorithm is respectively improved by 28.3%, 6.9%, and 12.5% under different beacon node densities; and under different communication radii, the positioning accuracy is improved by 24.4%, 7.6%, 14.8%, respectively. It was demonstrated that the DEWF-D algorithm can effectively improve the positioning accuracy and solve the problem of large positioning errors in previous positioning algorithms.

     

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

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

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

    DV-Hop定位算法[19-21]可以分为3个步骤:

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

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

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

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

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

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

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

    图  1  DEWF-D算法流程图
    Fig.  1  Flow chart of DEWF-D algorithm
    下载: 全尺寸图片

    在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
    下载: 全尺寸图片

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

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

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

    $$ {f}_{i}=\frac{\text{1}}{M-\text{1}}{\displaystyle \sum _{i\ne j}{\left({d}_{ij}-{H}_{i}\cdot{h}_{ij}\right)}^{\text{2}}} $$ (1)

    式中:M为信标节点个数; ${H_i}$ 为信标节点 $i$ 的平均每跳距离; ${h_{ij}}$ 为信标节点 $i$ $j$ 之间的最小跳数; ${d_{ij}}$ 为信标节点 $i$ $j$ 的实际距离,表达式为:

    $$ {d_{ij}} = \sqrt {{{\left( {{x_i} - {x_j}} \right)}^{\text{2}}} + {{\left( {{y_i} - {y_j}} \right)}^{\text{2}}}} $$ (2)

    $\dfrac{{\partial {f_i}}}{{\partial {H_i}}} = {\text{0}}$ ,得:

    $$ {H}_{i}=\frac{{\displaystyle \sum _{i\ne j}{d}_{ij}\cdot{h}_{ij}}}{{\displaystyle \sum _{i\ne j}{h}_{ij}^{\text{2}}}} $$ (3)

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

    通过式(4)计算出信标节点平均每跳距离的误差:

    $$ {\varepsilon }_{i}={\displaystyle \sum _{i\ne j}\frac{{H}_{i}\cdot{h}_{ij}-{d}_{ij}}{{h}_{ij}}} $$ (4)

    通过式(5)计算误差权值:

    $$ {\omega _i} = \frac{{{{\text{1}} \mathord{\left/ {\vphantom {{\text{1}} {{\varepsilon _i}}}} \right. } {{\varepsilon _i}}}}}{{\displaystyle\sum\limits_{j = {\text{1}}}^m {{{\text{1}} \mathord{\left/ {\vphantom {{\text{1}} {{\varepsilon _i}}}} \right. } {{\varepsilon _i}}}} }} $$ (5)

    由仿真计算得出未知节点在接收到最近的3个信标节点发来的信息时,误差最小,所以m的最佳取值为3。

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

    $$ d={\displaystyle \sum _{i=\text{1}}^{\text{3}}{\omega }_{i}\cdot{H}_{i}} $$ (6)

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

    2.3.1   确定适应度函数

    适应度函数表达式为:

    $$ F(x,y) = \sum\limits_{i = 1}^m \left({D_i} - \sqrt {{{\left( {x - {x_i}} \right)}^{\text{2}}} + {{\left( {y - {y_i}} \right)}^{\text{2}}}} \right) $$ (7)

    式中, $ m $ 为信标节点个数, ${(x,y)}$ 为未知节点坐标, ${({x_i},{y_j})}$ 为信标节点 $i$ 的坐标, ${{D_i}}$ 为未知节点到信标节点 $i$ 的实际距离,表达式为:

    $$ {D}_{i}=d\cdot{h}_{i} $$ (8)
    2.3.2   确定适应度函数的搜索区域

    图3所示,节点A、B、C为距离未知节点最近的3个信标节点,由式(8)求出这3个节点到未知节点的距离,分别为 $ {R_A} $ $ {R_B} $ $ {R_C} $ ,以信标节点为圆心,各自到未知节点的距离为半径做圆,圆心分别用 $ ({x_a},{y_a}) $ $ ({x_b},{y_b}) $ $ ({x_c},{y_c}) $ 表示。因为式(8)求出的距离往往会大于实际距离,所以未知节点必然会位于3个圆相交的公共区域。已知圆心坐标和半径,就可以求出3个圆的函数表达式:

    图  3  搜索区域计算模型
    Fig.  3  Search area calculation model
    下载: 全尺寸图片
    $$ \left\{ \begin{gathered} {(x - {x_a})^2} + {(y - {y_a})^2} = R_A^2, \hfill \\ {(x - {x_b})^2} + {(y - {y_b})^2} = R_B^2, \hfill \\ {(x - {x_c})^2} + {(y - {y_c})^2} = R_C^2 \hfill \\ \end{gathered} \right. $$ (9)

    通过式(9)求出3个圆的交点DEF的坐标。以点DEF为顶点做三角形,设边EF为三角形的最长边,线段DG为三角形的高。以边EF为长、DG为宽做出矩形,该矩形就是所要确定的搜索区域。

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

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

    每条人工鱼被封装为函数和变量两个部分:函数包括行为函数(人工鱼进行的各种行为,包括觅食、聚群、追尾、跳跃、吞食等)和目标函数;变量包括人工鱼总数W、状态X、最大步长S、视野V、尝试次数T、拥挤度因子 $\delta $ ,以及个体之间的距离R。行为函数描述如下:

    1)觅食行为

    设人工鱼的状态为 ${X_i}$ ,由式(10)选择一个状态 ${X_j}$

    $$ {X}_{j}={X}_{i}+V\cdot {\rm{rand}}() $$ (10)

    式中, ${\rm{rand}}()$ 为一个位于0和1之间的随机数。若 $ {X_j} $ 的目标函数值优于 ${X_i}$ 的目标函数值,则选择该状态并向全局最优位置 ${X_{\rm b}}$ 前进1步;反之,重新选择 $ {X_j} $ ,再判断是否满足上述条件,若满足,则更新:

    $$ {X}_{i}^{t+1}={X}_{i}^{t}+\frac{\left({X}_{j}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)}{\Vert \left({X}_{j}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)\Vert }\cdot S\cdot {\rm{rand}}() $$ (11)

    若不满足,则继续选择。一直尝试T次后,如果仍不满足前进条件,则更新:

    $$ {X}_{i}^{t+1}={X}_{i}^{t}+V\cdot {\rm{rand}}() $$ (12)

    2)聚群行为

    设人工鱼状态为 $ {X_i} $ ,检索视野范围内的人工鱼数目为 $ {\eta _{\rm f}} $ ,其中心位置为 $ {X_{\rm c}} $ 。若 ${X}_{\rm c}\cdot{\eta }_{\rm f} \lt \delta \cdot{X}_{i}$ ,表明检测的位置有充足的食物且有足够的空间,则向其中心位置和全局最优位置 $ {X_{\rm b}} $ 前进1步:

    $$ {X}_{i}^{t+\text{1}}={X}_{i}^{t}+\left(\frac{\left({{X}}_{\rm c}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)}{\Vert \left({{X}}_{\rm c}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)\Vert }\right)\cdot S\cdot {\rm{rand}}() $$ (13)

    否则,执行觅食行为。

    3)追尾行为

    设人工鱼状态为 $ {X_i} $ ,检索视野内人工鱼中 $ {Y_j} $ $ {X_j} $ 的目标函数值)最小的 ${X_j}$ 。若 $Y_{j} \cdot \eta_{\rm f}< \delta \cdot Y_{i}$ ,说明 ${X_j}$ 的状态具有充足的食物且其周围有足够的空间,则朝 ${X_j}$ 的方向和全局最优位置 $ {X_{\rm b}} $ 前进1步:

    $$ {X}_{i}^{t+1}={X}_{i}^{t}+\frac{\left({X}_{j}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)}{\Vert \left({X}_{j}-{X}_{i}^{t}\right)+\left({X}_{\rm b}-{X}_{i}^{t}\right)\Vert }\cdot S\cdot {\rm{rand}}() $$ (14)

    否则,执行觅食行为。

    4)跳跃行为

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

    $$ {X}_{\rm s}^{t+1}={X}_{\rm s}^{t}+\beta \cdot V\cdot {\rm{rand}}() $$ (15)

    式中, $\; \beta $ 可以是一个参数,也可以是使人工鱼的参数产生突变的函数。

    5)吞食行为

    算法迭代I/2次后,若某条人工鱼的适应度值总是高于预设值,则舍弃该鱼,且人工鱼的总数W减1。

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

    Step1:初始化参数,包括人工鱼总数W、每条人工鱼的初始位置、步长S、视野V、尝试次数T、迭代次数I、拥挤度因子 $\delta $ 、执行吞食行为的阈值;

    Step2:计算每条人工鱼的适应度值,并记录全局最优的人工鱼状态;

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

    Step4:执行人工鱼选择的行为,基于全局信息和局部信息更新人工鱼的位置信息;

    Step5:更新全局最优人工鱼的状态;

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

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

    表  1  仿真参数
    Table  1  Simulation parameters
    参数 取值
    网络区域面积Z/(m×m) 100×100
    节点总数X 100
    信标节点数量M 5、10、15、20、25、30
    通信半径/m 10、15、20、25、30
    人工鱼总数W 20
    迭代次数I 100
    人工鱼步长S/m 0.6
    视野V/m 1.5
    尝试次数T 50
    拥挤度因子 $\delta $ 0.1

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

    $$ {E}_{i}=\frac{{\displaystyle \sum _{i=1}^{N}\sqrt{{\left({x}_{i}-{x}^{*}_{i}\right)}^{\text{2}}+{\left({y}_{i}-{y}^{*}_{i}\right)}^{\text{2}}}}}{N\cdot R} $$ (16)

    式中, ${({x_i},{y_j})}$ 为节点 $ i $ 的真实坐标, ${({x^*_i},{y^*_j})}$ 为节点 $ i $ 的计算出来的坐标,N为未知节点个数,R为通信半径。

    图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算法的定位精度。

    采用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算法要优于其他对比的定位算法。

    采用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算法要优于其他定位算法。

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

  • 图  1   DEWF-D算法流程图

    Fig.  1   Flow chart of DEWF-D algorithm

    下载: 全尺寸图片

    图  2   跳数计算模型

    Fig.  2   Hop count calculation model

    下载: 全尺寸图片

    图  3   搜索区域计算模型

    Fig.  3   Search area calculation model

    下载: 全尺寸图片

    图  4   两种算法节点定位误差

    Fig.  4   Node positioning errors of two algorithms

    下载: 全尺寸图片

    图  5   不同算法、信标节点密度下的定位误差

    Fig.  5   Positioning errors under different algorithms and beacon node densities

    下载: 全尺寸图片

    图  6   不同算法、通信半径下的定位误差

    Fig.  6   Positioning errors under different algorithms and communication radius

    下载: 全尺寸图片

    表  1   仿真参数

    Table  1   Simulation parameters

    参数 取值
    网络区域面积Z/(m×m) 100×100
    节点总数X 100
    信标节点数量M 5、10、15、20、25、30
    通信半径/m 10、15、20、25、30
    人工鱼总数W 20
    迭代次数I 100
    人工鱼步长S/m 0.6
    视野V/m 1.5
    尝试次数T 50
    拥挤度因子 $\delta $ 0.1
  • [1] 梁久祯.无线定位系统[M].北京:电子工业出版社,2013.
    [2] Waqas Khan M,Khan M,Hafeez A.Localisation of wireless nodes with partial connectivity in wireless sensor systems[J].IET Wireless Sensor Systems,2020,10(6):299–307. doi: 10.1049/iet-wss.2019.0202
    [3] 钱志鸿,孙大洋,LEUNG Victor.无线网络定位综述[J].计算机学报,2016,39(6):1237–1256. doi: 10.11897/SP.J.1016.2016.01237

    Qian Zhihong,Sun Dayang,Victor L.A survey on localization model in wireless networks[J].Chinese Journal of Computers,2016,39(6):1237–1256 doi: 10.11897/SP.J.1016.2016.01237
    [4] Anwit R,Tomar A,Jana P K.Tour planning for multiple mobile sinks in wireless sensor networks:A shark smell optimization approach[J].Applied Soft Computing,2020,97:106802. doi: 10.1016/j.asoc.2020.106802
    [5] Ahmad Najib Y N,Daud H,Abd Aziz A.Singular value thresholding algorithm for wireless sensor network localization[J].Mathematics,2020,8(3):437. doi: 10.3390/math8030437
    [6] 张高驰.基于非测距算法的无线传感器网络定位技术研究[D].南京:南京邮电大学,2021.

    Zhang Gaochi.Research on wireless sensor network positioning technology based on non-ranging algorithm[D].Nanjing:Nanjing University of Posts and Telecommunications,2021.
    [7] 余修武,余昊,刘永,等.基于加权混合滤波和重心法的APIT定位算法[J].北京邮电大学学报,2019,42(4):32–37. doi: 10.13190/j.jbupt.2018-313

    Yu Xiuwu,Yu Hao,Liu Yong,et al.APIT location algorithm based on weighted hybrid filtering and center of gravity method[J].Journal of Beijing University of Posts and Telecommunications,2019,42(4):32–37 doi: 10.13190/j.jbupt.2018-313
    [8] Gupta V,Singh B.Performance evaluation of DV-HOP localization algorithm in wireless sensor networks[M]//Soft Computing:Theories and Applications.Singapore:Springer,2018:433–440.
    [9] 宋倩雯,郭松涛,柏艾林,等.无线传感器网络中一种改进的DV-Hop定位算法[J].重庆大学学报,2015,38(4):128–136. doi: 10.11835/j.issn.1000-582X.2015.04.018

    Song Qianwen,Guo Songtao,Bai Ailin,et al.An improved localization algorithm based on DV-Hop in wireless sensor networks[J].Journal of Chongqing University,2015,38(4):128–136 doi: 10.11835/j.issn.1000-582X.2015.04.018
    [10] 程超,钱志鸿,付彩欣,等.一种基于误差距离加权与跳段算法选择的遗传优化DV-Hop定位算法[J].电子与信息学报,2015,37(10):2418–2423. doi: 10.11999/JEIT141205

    Cheng Chao,Qian Zhihong,Fu Caixin,et al.Genetic optimization DV-hop localization algorithm based on error distance weighted and hop algorithm selection[J].Journal of Electronics & Information Technology,2015,37(10):2418–2423 doi: 10.11999/JEIT141205
    [11] 李文军,华强,谭立东,等.DV-HOP和接收信号强度指示结合的改进算法[J].吉林大学学报(工学版),2019,49(5):1689–1695. doi: 10.13229/j.cnki.jdxbgxb20180819

    Li Wenjun,Hua Qiang,Tan Lidong,et al.An improved algorithm for combination of DV-HOP and RSSI[J].Journal of Jilin University(Engineering and Technology Edition),2019,49(5):1689–1695 doi: 10.13229/j.cnki.jdxbgxb20180819
    [12] Messous S,Liouane H,Cheikhrouhou O,et al.Improved recursive DV-hop localization algorithm with RSSI measurement for wireless sensor networks[J].Sensors,2021,21(12):4152. doi: 10.3390/s21124152
    [13] Abd El Ghafour M G,Kamel S H,Abouelseoud Y.Improved DV-Hop based on Squirrel search algorithm for localization in wireless sensor networks[J].Wireless Networks,2021,27(4):2743–2759. doi: 10.1007/s11276-021-02618-x
    [14] Rabhi S,Semchedine F.Localization in wireless sensor networks using DV-hop algorithm and fruit fly meta-heuristic[J].Advances in Modelling and Analysis B,2019,62(1):18–23. doi: 10.18280/ama_b.620103
    [15] 李娟,刘禹,钱志鸿,等.基于双通信半径的传感器网络DV-Hop定位算法[J].吉林大学学报(工学版),2014,44(2):502–507. doi: 10.13229/j.cnki.jdxbgxb201402036

    Li Juan,Liu Yu,Qian Zhihong,et al.Improved DV-Hop localization algorithm based on two communication ranges for wireless sensor network[J].Journal of Jilin University(Engineering and Technology Edition),2014,44(2):502–507 doi: 10.13229/j.cnki.jdxbgxb201402036
    [16] 林维维,姚英彪,邹柯,等.基于校正矢量的分布式DV-Hop求精算法[J].计算机研究与发展,2019,56(3):585–593. doi: 10.7544/issn1000-1239.2019.20170841

    Lin Weiwei,Yao Yingbiao,Zou Ke,et al.Correction vector based distributed DV-hop localization refinement algorithm[J].Journal of Computer Research and Development,2019,56(3):585–593 doi: 10.7544/issn1000-1239.2019.20170841
    [17] Wang Jing,Hou Anqi,Tu Yuanfei,et al.An improved DV-hop localization algorithm based on selected anchors[J].Computers,Materials & Continua,2020,65(1):977–991. doi: 10.32604/cmc.2020.011003
    [18] Shen Shikai,Yang Bin,Qian Kaiguo,et al.On improved DV-hop localization algorithm for accurate node localization in wireless sensor networks[J].Chinese Journal of Electronics,2019,28(3):658–666. doi: 10.1049/cje.2019.03.013
    [19] 杨博雄.无线传感网络[M].北京:人民邮电出版社,2015:102–105.
    [20] 冯秀芳,王丽娟,关志艳.无线传感器网络研究与应用[M].北京:国防工业出版社,2014.
    [21] Shi Qinqin,Wu Chengji,Xu Qiang,et al.Optimization for DV-Hop type of localization scheme in wireless sensor networks[J].The Journal of Supercomputing,2021,77(12):13629–13652. doi: 10.1007/s11227-021-03818-0
    [22] Liu Guiqi,Qian Zhihong,Wang Xue.An Improved DV-Hop Localization algorithm based on hop distances correction[J].China Communications,2019,16(6):200–214. doi: 10.23919/JCC.2019.06.016
    [23] 张贤达.现代信号处理[M].2版.北京:清华大学出版社,2002.
    [24] 江铭炎,袁东风.人工鱼群算法及其应用[M].北京:科学出版社,2012
    [25] 费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016,49(6):581–588. doi: 10.11784/tdxbz201501007

    Fei Teng,Zhang Liyi,Bai Yu,et al.Improved artificial fish swarm algorithm based on DNA[J].Journal of Tianjin University(Science and Technology),2016,49(6):581–588 doi: 10.11784/tdxbz201501007
图(6)  /  表(1)

本文结构

    /

    返回文章
    返回