一种自适应的分布式目标定位算法

冯燕 徐琨

摘要：在基于无线传感网络的分布式定位中，由于网络中的传感节点计算能力有限，会导致出现无法求解出最优解的问题。针对这个问题，该文提出了一种动态调整步长的分布式目标定位算法，提出算法在每次迭代求解过程中都动态调整步长大小，并考虑不同距离下锚节点的可靠性问题，利用目标对象前一次得到的位置估算值和相应的梯度值，求出目标对象在当前步的位置信息。采用实测数据对提出算法进行验证，结果显示和已有的经典分布式定位算法相比，提出算法能降低定位误差，获得较高的定位精度。

关键词：无线传感网络；分布式；优化；目标定位

中图分类号：TP393      文献标识码：A

文章编号：1009-3044（2022）27-0001-04

开放科学（资源服务）标识码（OSID）：

1 概述

无线传感网络[1]（Wireless Sensor Networks， WSN）是物联网[2]（Internet of Thing， IoT）系统的骨干网络，具有易于部署、自组网络、多跳通信和协同感知等优点，使其被广泛地应用于医疗健康[3]、环境监控[4]、智能家居[5]和目标追踪[6]等各个领域。近十几年以来，国内外的企业、研究机构和学者开展了大量基于WSN网络的研究，在网络拓扑结构、目标定位与轨迹追踪、网络路由和协同感知等领域取得了大量的研究成果，推动了WSN网络在实际应用中的快速发展。目标定位是WSN网络的关键基础技术，是实现网络高阶应用的重要支撑基础，得到了研究机构的大量关注，是WSN领域的研究热点。

在WSN网络中，遍布监测区域的微型WSN传感节点能够感知到周围环境中的各种信息，通过无线网络将采集到的信息传送到服务器或云平台，其中，位置信息是最重要的基础数据，是确保网络功能准确实施和应用的关键，没有位置信息的数据是没有任何意义的。集中式定位[7]和分布式定位[8]是应用于WSN网络目标定位的两种重要类别。在WSN网络发展的早期阶段，由于硬件设备的限制，网络中的终端节点由于芯片处理能力较低，常在网络中部署一个或多个中心节点实现节点自身和目标的定位，网络中的终端节点将采集到的信息以多跳路由的方式传送给网关节点，由网关节点集中处理后再发回控制指令和信息给终端节点[9]。集中式定位方法能够高效地实现对网络终端节点的自定位和网络目标的定位，但是也存在很大的缺陷，WSN网络不同于传统网络，终端节点多、网络冗余度大、能耗低和带宽有限是其最大的特点，所有的终端节点都将数据传输到网关节点统一处理，会给WSN网络带来非常大的通信开销，造成很大的能耗，降低网络的生存周期，当多个终端节点同时向网络节点传输信息时，由于是采用多条路由的传输方式，会在网关节点附近出现网络堵塞，导致发生丢包的问题[10]。近几年来，芯片技术和无线传输技术的飞速发展，在功耗和成本没有明显增加的情况下，传感节点的处理能力越来越强，分布式的定位方式能够将信息在终端进行自主处理，无须将终端节点采集到的信息集中在网关节点统一处理，而且分布式处理方式能够降低网络的通信开销，平衡网络负载均衡，提高网络的生存周期，被越来越多的企业和研究机构所青睐。

在分布式定位中，网络中的传感节点能够通过接收周围节点或目标的信息，自主进行定位，但是WSN网络中的传感节点计算能力有限，会出现无法求解出最优解的问题。针对这个问题，本文提出了一种动态调整步长的分布式目标定位算法，提出算法考虑不同距离下锚节点的009657可靠性问题，每轮迭代过程中都动态推导步长大小，根据目标对象前一位置的加权平均值和对应的梯度值，迭代优化出目标对象当次的位置，每次求出的位置估算值都将广播给下一个邻居节点。根据实测数据对提出算法进行验证，结果表明相比于其他传统的分布式定位算法，提出算法具有更优的定位性能。

2 网络模型

在一个室内环境中部署由N个传感节点和M个目标对象组成的WSN网络，其中，N个传感节点被随机地部署在室内环境中，[Pi=pi，qi]，其位置已知，这些传感节点会周期性地向周围区域发送包含自身位置信息的无线信号，也会接收来自邻近传感节点或目标对象的无线信号，一般将其称为锚节点。M个目标对象也随机分布在室内环境中，其位置未知，[Xi=xi，yi]，需要利用位置已知的锚节点估算出目标对象的位置。目标对象能接收通信范围内锚节点广播的信标报文，报文中包含锚节点的位置信息和信号强度，传感节点广播的信标报文如图1所示。

信号强度在空气中传输时，会随着距离的增大逐渐衰减，锚节点和目标对象之间的距离与信号强度之间存在映射关系。目标对象能够根据接收到的多个锚节点的位置信息和接收信号强度估算自己的位置，目标对象s接收到的第i个锚节点的接收信号强度为Ri，[s=x，y]，根据对数-正态衰减模型可以将其表示为：

[Ri=R0-10?np?log10did0+Ωi]     （1）

其中，Ri表示目标对象s收到的第i个锚节点的接收信號强度值，单位为dBm；R0表示目标对象s和锚节点距离为1m时的参考接收信号强度值；[di=s-Pi]表示目标对象s和第i个锚节点之间的欧氏距离；d0表示目标对象s和参考节点之间的欧氏距离，通常设为1m；np表示路径衰减因子，它是一个随监测环境变化的变量，一般在室内环境中取值在2～6之间；[Ωi]表示无线信号传输时的遮蔽效应，它是一个服从对数正态分布的高斯变量。

式（1）描述了接收信号强度Ri和距离di之间的映射关系，可以采用最大似然估计算法对其进行求解。[Ωi]服从对数正态分布，则求解出来的目标对象s的位置坐标[s=x，y]是其真实坐标的概率密度函数为：

[Px=xT，y=yT=12πσNexpi=1Ns-Pi-di2] （2）

其中，[xT，yT]表示目标对象s在网络中的真实坐标，用最大似然估计算法对式（2）进行求解，目标位置[s=x，y]的最大似然估计量为：

[s=argmaxx，yPx=xT，y=yT]                 （3）

在WSN网络中，离目标对象s较近的锚节点由于相隔距离比较短，广播的信标报文会比距离较远的锚节点具有更高的可靠性，进而在求解目标对象s的位置坐标时能提供更多的价值。因此在求解式（3）描述的定位问题时，需要考虑锚节点和目标对象s之间的距离，距离越近的锚节点可靠性越高。将式（2）中的具体项代入式（3），考虑不同距离下锚节点的可靠性问题，式（3）可以被进一步表示为：

[s=argmaxx，ywi?i=1Ns-Pi-di2]     （4）

其中，[wi]是一个加权系数，表示锚节点对目标对象的可靠程度，离目标对象较近的锚节点的[wi]值较大，通过这个加权系统可以突出在定位过程中占重要位置的锚节点，提供对目标对象的定位精度。

令[fs=wi?i=1Ns-Pi-di2]，将式（4）进一步简化为：

[s=argmaxx，yfs]                     （5）

式（5）中存在非线性项[s-Pi]，采用最大似然算法求解最优值是一件非常困难的事情，而且计算复杂度非常高。针对式（5）中存在非线性项的问题，结合WSN网络低能耗和有限处理能力的特点，将采用分布式的迭代优化算法进行求解。

3 基于动态步长的分布式定位算法

在对网络中的目标对象进行定位时，由于存在[s-Pi]这一非线性项，直接对其处理是非常困难的，因此需要对式（5）中包含的[s-Pi]进行线性化处理，降低计算的复杂度，让其能够便利地求出最优解。为了便于迭代优化算法求出最优解，将求最大化的问题等价转换为求最小化问题，然后将式（5）按照一级泰勒级数展开，可以将其转换为：

[s=argmin[x，y]i=1Nfis+?fix0?s-s]   （6）

其中，[x0=x0，y0]表示泰勒级数展开的初始位置，取值为使[fiΔs+?fix0?s-Δs≥0]的任意点；[?fix0]表示函数[fs]在点[x0]处的梯度值；[s]表示前一阶段的目标对象的估算位置。在对式（6）采用迭代方式进行最优值求解时，需要进行多次迭代循环。针对网络中存在多个目标对象的情况，采用分布式的迭代优化方式对式（6）进行求解。

在对目标对象的坐标[[x，y]]进行迭代时，对于每一步迭代，都需要向梯度[?fi]的反方向对上一次求出的坐标进行更新。当采用分布式方式进行迭代时，每一个目标对象都将经历m次循环迭代过程，每次迭代，目标对象都要根据接收到的多个锚节点的接收信号强度和位置信息进行迭代计算。目标对象在第k次迭代循环后得到的位置估计值为：

[sk=arg minxk，yki=1kfis+?fix0s-s， k=1，2，…m]    （7）

其中，[sk=xk，yk]表示目标对象在第k次迭代后得到的位置估值，经过m次迭代循环后求出目标对象位置的最优值，实现对目标对象的定位。由于非线性项的存在，只能通过最小化[fis+?fix0s-s]的值来求出[xk，yk]的最优解。但是如果存在[xk，yk]，能使[fis+?fix0s-s=0]时，可以得到式（7）的最小值，从而求出[xk，yk]的最优解。

令[fis+?fix0s-s=0]，可以将求解式（7）最优解的问题进行等价变换，其表示形式为：

[?fix0?ss=sk=?fix0?s-fis]              （8）

用第k-1次迭代得到的目標对象的坐标位置[sk-1=xk-1，yk-1]代替式（8）中的[x0]和[s]，经过整理后的表达式为：

[?fisk-1?sk=?fisk-1?sk-1-fisk-1] （9）

其中，[?fisk-1]表示函数[fi]在[sk-1]处的梯度值，式（9）中有两个参数，分别是[sk-1]和[sk]，[sk-1]表示第k-1个迭代后求出的目标对象的位置估计值，[sk]表示第k个迭代后求出的目标对象的位置估计值。在迭代优化过程中，第k个位置估计值要基于第k-1次迭代后的位置估计值进行估算，经过变换后的式（9）能够很好地描述第k-1次迭代和第k个迭代之间的转换关系，其表示形式为：

[sk=sk-1-fisk-1W??fisk-1]                   （10）

其中，[?fisk-1]表示函数[fi]在位置[sk-1]处的梯度值；[fisk-1W]表示在第i次迭代时的步长大小，[W=1?fisk-12]表示步长的分母部分。式（10）很好地反映了第k-1次迭代后的估算结果和第k次迭代的估算结果之间的映射关系。根据第k-1次的坐标位置、第k-1次迭代的梯度值和步长值，能够估算出第k次的目标对象坐标位置。而且从式（10）可以看出，[W]和[fisk-1]都只和第k-1次迭代时的目标对象的估算位置[sk-1]有关，和之前其他的迭代估算结果无关。令[λ=-fisk-1W]，将式（10）进一步表示为：

[sk=sk-1+λ??fisk-1]                     （11）

式（11）描述了目标对象第k次迭代的估算位置和第k-1次迭代的估算位置之间的关系。其中，[λ]表示每次迭代时的步长，它的值都会根据前一次的迭代结果动态地求出。因此，当目标对象第k-1次迭代后估算出位置为[sk-1]时，利用步长[λ]和梯度[?fisk-1]，可以推导出目标对象第k次迭代后的估算位置[sk]；根据式（11）可以进一步得到，当目标对象第k次迭代后估算出位置为[sk]时，利用步长[λ]和梯度[?fisk]，可以推导出目标对象第k+1次迭代后的估算位置[sk+1]，依此类推。

根据上述的求解过程，基于动态步长的分布式定位算法的实现可以用以下步骤进行描述：

步骤1：定义迭代变量：设置k=1；

步骤2：选择开始迭代的初始值：设置目标对象的初始位置为[s0=x0，y0]；

步骤3：计算梯度：根据[?fis0]求出对应的梯度值；

步骤4：计算步长：根据[λ=-fis0W]求出步长值；

步骤5：迭代：根据式（11），利用动态步长[λ]估算目标对象在第一次迭代优化中求解的位置估算值[s1=x1，y1]；

步骤6：进行下一次迭代：[sk=sk-1+λ??fisk-1]，k=k+1；

步骤7：开始下一次迭代：跳转到步骤3重复执行；

步骤8：求出最优解：当k=m时，停止迭代，求出目标对象位置信息的最优解。

4 性能分析

从一个已经部署好WSN网络的室内办公区域采集实验数据，该区域位于一栋办公大楼的第四层，在一个40*20平方米的区域内部署了28个传感节点，2个移动机器人作为目标对象，所有传感节点和目标对象都装配TI公司的CC2530作为无线收发设备，安装1/4波长的全向天线，工作在2.4GHz频段。将所有传感节点按顺时针方向排序，周期性地向目标对象广播包含自身位置和接收信号强度的信标报文，目标对象接收通讯范围内传感节点发送的信标报文，重复执行10000次试验。

在一台中央处理器为Intel Core i9-10900k，核心数为8核，主频2.90GHz，内存64G的计算机上进行所有的验证实验，根据在上述办公环境中得到的实测数据，R0表示目标对象s和锚节点距离为1m时的参考接收信号强度值R0=32.57dBm；参考距离d0定义为1m；路径衰减因子[np]在2～6之间随机取值。

将提出算法和期望最大算法（Expectation Maximization， EM）、加权增量次梯度（Weighted Incremental Subgradient， WIG）等分布式定位算法进行比较。将所有算法的初始坐标都设为[s0=1，1]，设置加权增量次梯度算法的步长为0.08，提出算法的步长动态生成。为了验证算法的性能，采用均方根定位误差[MMSE=1mi=1m（x-xT）2+（y-yT）2]作为评判标准。

不同分布式定位算法的误差累计分布函数如图2所示，从图中可以看出，提出算法定位性能要明显优于期望最大算法和加权增量次梯度算法。期望最大算法的定位性能最差，90%的定位误差在3.3米以内；加权增量次梯度算法有90%的定位误差在2.7米以内；提出算法的定位性能最好，90%的定位误差在2.2米以内。

目标对象定位时，通信范围内锚节点的数量会对定位性能产生影响，不同锚节点数量下，各种分布式定位算法的定位误差如图3所示。从图中可以看出，当锚节点数量增多时，三种分布式定位算法的定位误差都逐渐降低，提出算法的定位误差降低的速度最快，定位性能最优；当锚节点数量增多到一定程度时，三种分布式定位算法误差降低的程度都逐渐变缓。当锚节点数量相同时，提出算法定位误差最小，定位性能最优；期望最大算法的定位误差最大。

不同分布式定位算法迭代次数和均方根误差的关系如图4所示，从图中可以看出，当迭代次数增加时，所有定位算法的定位误差都得到了显著降低，其中，期望最大算法的定位性能最差；提出算法的定位误差降低的程度最高，定位性能明显优于其他两个分布式定位算法。

5 结束语

集中式定位和分布式定位是WSN网络中最常用的两种定位形式，分布式定位由于无须中心节点，能降低网络的通信开销，是目前的研究热点。针对分布式定位会出现无法求解出最优解的问题，提出了一种动态计算步长的分布式定位算法，该算法考虑锚节点的可靠性问题并将其表示为权重形式，在每次迭代时动态调整步长大小，根据上一步估算出的位置信息，结合步长和梯度值求出当前步的位置信息。将提出算法和期望最大算法、加权增量次梯度算法等分布式定位算法进行比较，结果表明提出算法的定位误差要明显低于传统的两种分布式定位算法，具有较好的定位性能。

参考文献：

[1] 刘瑞兴，段中兴，李博.改进DV-Hop定位算法在钢构建筑健康监测中的应用[J].仪器仪表学报，2022，43（4）：38-49.

[2] 程杰，董云玲，陈嘉兴，等.一种具有连续跳数值的三维DV-Hop改进算法[J].电子学报，2020，48（11）：2122-2130.

[3] 徐莎莎，周芳，李杨剑，等.一种新的传感器节点分布式定位算法[J].西安电子科技大学学报，2022，49（2）：89-96，172.

[4] 蒋俊正，赵海兵.基于超级节点的分布式传感器节点定位算法[J].控制与决策，2020，35（12）：2898-2906.

[5] 余修武，周利興，余齐豪，等.基于刚分簇与鸡群优化的深井无线传感网络定位算法[J].西南交通大学学报，2019，54（4）：870-878.

[6] 刘宏，韩亚波，张时斌，等.基于自适应罚函数优化粒子群的WSN定位算法[J].传感技术学报，2018，31（8）：1253-1257，1265.

[7] 王芳.射频RSS聚类与多传感器融合的室内定位算法[J].计算机工程与设计，2018，39（6）：1553-1558，1585.

[8] 汪晗，成昂轩，王坤，等.无线传感器网络分布式迭代定位误差控制算法[J].电子与信息学报，2018，40（1）：72-78.

[9] 陈为业，刘广怡，沈智翔，等.基于数据融合的辐射源目标定位EM算法研究[J].信息工程大学学报，2021，22（4）：399-404.

[10] 单好民，陈才学.基于RSSI高斯滤波的人工蜂群定位算法[J].传感技术学报，2021，34（7）：979-983.

【通联编辑：谢媛媛】