一种基于跳距修正的物联网中节点定位算法

唐一韬，邓河

(长沙民政职业技术学院 通识教育中心,长沙 410004)

0 引言

随着智能终端设备的日增以及无线网络的普及，人们的生活与物联网关系也日益紧密[1].由微型传感节点构成的无线传感网络 (WSN)是物联网的基石[2-3].传感节点先感知环境数据，再通过邻居节点的转发，将数据传输至控制中心.

节点感知的数据离不开节点的位置.因此，定位是基于WSN 物联网应用的关键.尽管卫星定位系统已被广泛应用，但将其应用于WSN 的成本高，不适合大规模部署.多数节点只能依据网络拓扑知识或者节点间的连通信息估计自己的位置信息.

针对WSN 的定位问题，学者已提出不同的定位算法.这些定位算法可粗略分为基于测距定位(Rangbased)和非测距定位(Rang-free)算法两类[4].不失一般性，测距定位算法的精度优于非测距定位算法的精度.但是非测距定位算法易实施，部署成本低.

因此，非测距定位算法更适用于低功耗、低成本的物联网.非测距定位算法不是建立在节点间距离值，而是网络拓扑信息，如质心算法[5]、DV-Hop 算法[6]、近似三角形内点测试(APIT)算法[7].

因避免直接测量节点间距离，DV-Hop 算法成为非测距定位算法的代表.DV-Hop 算法先利用距离矢量路由方法估计锚节点与未知节点间的最小跳数，再结合平均跳距测量锚节点与未知节点间的距离，最后利用三边测量法估计未知节点位置.

简之，DV-Hop 算法主要涉及到最小跳数、平均跳距和估计节点位置三个环节.任一个环节的估计或者测量误差，均会降低估计节点位置的精度.此外，前两个环节的误差会累加至估计节点位置的环节.其中最小跳数估计、平均跳距的计算易受网络拓扑以及通信半径影响.

针对DV-Hop 算法的定位精度问题，学者已着手对其进行改进.例如张晶等[8]提出基于DV-Hop 算法的三次修正的定位算法.该算法先根据接收信号强度值(RSSI)对跳数进行连续性划分，再利用平方误差适应度函数修正跳距值，最后利用泰勒展开式估计节点位置.然而，测量发送端与接收端间RSSI 值容易受环境影响.同一对收发端的RSSI 值也可能存在较大差异.同一个节点接收的多个RSSI 值可能波动较大.因此，利用RSSI 修正跳距效果并不好.

针对DV-Hop 算法的问题，提出基于狮群优化算法的节点定位 (NLLSO) 算法.NLLSO 算法根据DVHop 算法的特点，对其进行有针对性地改进.主要工作如下：1)采用不同通信半径传输Beacon，进而提升估计跳数的精度；2) 修正平均跳距；3)利用狮群优化算法 (LSO) 估计未知节点位置.性能分析表明，NLLSO算法提高了定位精度.

1 网络模型及LSO 概述

1.1 网络模型

N个传感节点随机分布于二维网络l×l，其中锚节点占比为p%，未知节点占比为(100-p)%.令αi表示第i个锚节点，其位置坐标为令sj表示第j个未知节点，其位置坐标为如图1 所示,在100 m×120 m区域内随机部署N=50 个未知节点.锚节点占比p=10 .

图1 网络模型

1.2 LSO 概述

作为智能优化算法，LSO 模拟了自然界中狮群的觅食行为.LSO 中主要涉及三类角色：狮王、母狮和幼狮.它们遵照自然界法则生存，并采用不同的位置更新方式更新自己的位置.相比于母狮和幼狮，狮王的位置更新更快、收敛快、不易陷入局部最优，能够快速地搜索到全局最优解[9].因此，选择LSO 估计节点位置.表1 给出LSO 中相关符号的物理意义.

表1 LSO 的相关符号

假定在二维空间中分布了M只狮子，其中成年狮的比例为 β .每个成年狮群中只有一只公狮，余下的成年狮为母狮.幼狮数量为M(1-β) .

2 NLLSO 算法

2.1 基于多通信半径的最小跳数估计

传统估计最小跳数的算法将通信半径内的跳数值都看成一跳[10].例如，若节点1 离节点2 的距离为30 m，节点1 离节点3 的距离为20 m.如果节点1 的通信半径大于30 m,节点2 和3 节点就在其一跳通信范围内.依据传统估计最小跳数估计算法，节点2、3 离节点1 的跳数均为1.当平均跳距为d时，节点1 离节点2、3 的距离均为d，而实际上，节点1 离节点2、3 的距离分别为30 m、20 m.

为此，采用动态的通信半径.通过调整发射功率，锚节点选择不同的通信半径.令R表示默认的节点通信半径.锚节点采用5 种通信半径，分别为 0.2R、0.4R、0.6R、0.8R和R.

具体实现过程如下：最初网络中所有锚节点采用0.2R的通信半径广播Beacon 包，Beacon 包携带了锚节点位置以及ID 号.在0～ 0.2R传播范围内的节点收到Beacon 包，未知节点就获取离锚节点的最小跳数为0.2 跳.

然后再逐步增加通信半径(从 0.4R～ 0.6R，再提升到0.8R～R)，相应地，未知节点获取不同通信半径下的跳数值.

2.2 跳距的修正

利用离其他锚节点的距离和其他锚节点位置(已知信息)，锚节点修正自己的跳距值.即锚节点 αi先利用式(4)计算平均跳距AHDi

再利用hi j和 AHDi，估计锚节点 αi离 αj的距离(估计距离)

不失一般性，实际距离dij与估计距离间存在误差，并且该误差是已知的.因此，可利用该书籍信息修正平均跳距.即通过最小化误差对平均跳距进行修正

考虑到锚节点间跳数影响了AHDi的值，式(1)所估计 AHDi可能存在误差.为了降低误差，引用权值对平均跳距进行约束，进而降低因平均跳距误差引起的测距误差.

依式(5)可知，锚节点 αi离 αj的跳数越大，估计距离的误差越大.因此，将跳数大的两节点间的权值变小，可降低其对测距的影响.为了求解方便，对式(7)进行矩阵化表述

2.3 位置估计

NLLSO 算法采用狮群优化估计未知节点位置.为此，先设定目标函数

式中，fj(x,y)为求解未知节点sj所建立目标函数.

节点sj建立的适应值函数

具体的基于LSO 求解未知节点位置的步骤如步骤1～6 所示：

步骤1：在二维空间中随机初始化N个节点位置，并将其作为狮群中狮子的位置，并设置最大迭代次数T和成年狮比例.

步骤2：计算狮群中不同角色狮子数量，狮王位置设置为初始种群最优位置，设置个体历史最优位置为各狮的当前位置.

步骤3：依据式(1)～(3)更新狮王、母狮和幼狮的位置，并根据式(12)计算适应度值.

步骤4：更新自身和狮群历史最优位置.检测两次最优值的差值的绝对值是否小于预设的精度值.若小于，则跳转步骤6，否则转入步骤5.

步骤5：每隔10 次重新排序，确认狮王、母狮和幼狮的位置，再跳转到步骤3.

步骤6：输出狮王的位置，即未知节点的位置.

3 性能仿真

3.1 仿真环境

利用MATLAB 2018 a 软件建立仿真平台，N个节点随机分布于100 m×100 m，其中锚节点数比例p%从10%～31%变化.节点的传输功率从-5～-15 dBm变化，具体的仿真参数如表2 所示.每次仿真独立进行20 次，取平均值作为最终定位数据.

表2 仿真参数

为了更好地分析NLLSO 定位算法的性能，选同类算法DV-Hop[11]、基于RSSI 测距修正的四边形加权质心定位(QWCRC)算法[12]进行比较.并分析它们的归一化定位误差

式中：m为未知节点数，即m=N-N×p% ；为节点的平均通信半径.

3.2 定位误差随锚节点数变化情况

先分析定位误差随锚节点数的变化情况.图2 显示归一化定位误差随锚节点数的变化曲线.总的节点数为150，锚节点数占比从0.1～0.31 变化，通信半径R=36 m.

图2 归一化定位误差随锚节点数变化情况

由图2 可知，在总的节点数一定时，增加锚节点数提升定位精度.但值得注意的是，当锚节点数达到一定量后，定位精度的提升也存在“饱和”现象.这也说明，优化锚节点数也是定位算法须考量的问题之一.

此外，在同等条件下，NLLSO 算法的定位精度优于DV-Hop 算法和QWCRC 算法，且分别提高了相比于DV-Hop 和QWCRC 算法，NLLSO 算法9%和5%.这说明NLLSO 算法通过平均跳距的修正和基于LSO，可以有效地提高平均定位精度.

3.3 定位误差随通信半径变化情况

本小节分析定位误差随通信半径的变化情况.图3 描述了定位误差随通信半径的变化曲线.总的节点数为150，锚节点数占比为0.2，通信半径约为21～45 m 变化.

图3 定位误差随通信半径的变化情况

由图3 可知，增加通信半径可提高定位精度.这主要因为节点通信半径越大，数据传输路径的跳数越小，这有利于降低估计最小跳数和跳距的误差.更准确的跳数值和跳距有利于提高定位精度.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地降低定位误差，且分别降低约8%和3%.

3.4 定位误差随节点数变化情况

最后分析定位误差随总节点数的变化情况.图4描绘了归一化定位误差随总节点数的变化曲线.锚节点数占比为0.2，总节点数从100～200 变化.节点通信半径为36 m.

图4 节点数对归一化定位误差的影响

由图4 的曲线走势可知，增加总节点数降低了定位误差.最初，增加总节点数能够快速地降低定位误差.但当总节点数增加到140 后，定位误差的下降速度变缓慢，趋于直线.原因在于：最初网络内节点数的增加，增加测距精度和估计最小跳数的精度.但当网络内节点数达到一定量后，再增加节点数，就增加了网络负担，出现“饱和现象”.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地提升了定位精度.

3.5 算法复杂度

在Windows 7 操作系统、8 GB 内存，Core i7 CPU的PC 运行算法，并记录运算时间.运行50 次，取平均值作为最终的数据，如表3 所示.由表3 可知，DVHop 算法的运行时间最短，NLLSO 算法的运行时间次之，QWCRC 算法的运行时间最长.原因在于：NLLSO 算法利用LSO 估计节点位置，增加了算法的复杂度.结合定位误差的数据可知，NLLSO 算法能够在定位误差与复杂度间达到较好地平衡.

表3 算法的复杂度

4 结束语

NLLSO 算法针对传统DV-Hop 算法在跳数估计、跳距测量和定位三个环节上的问题进行了一定的改进.通过采用不同通信半径传输Beacon 包，提升估计最小跳数的精度.并引用权重对平均跳距的修正，降低测距误差.通过LSO 估计节点位置，性能分析表明，相比于传统DV-Hop 算法 NLLSO 算法降低了定位误差.

然而，本文仅关注了NLLSO 算法在定位精度方面的优势，并没有考虑了多通信半径过程中所产生开销.后期，将考虑如何降低节点间的通信量，控制节点能量消耗，这将是后期的工作方向.