无线传感器网络定位研究综述

陈俊逸　陈琳

摘要：节点定位技术是无线传感器网络的关键技术之一，而定位算法则是定位技术中的核心。在节点定位的过程中，由于节点数目、节点距离以及环境等因素，会对节点的定位精确度造成影响，基于此，提出了各种对定位算法的改进以提高节点定位的精确度。本文基于测距以及非测距两方面介绍了各种节点定位算法，并详细介绍了几种比较经典和新颖的改进方法。

关键词：无线传感器网络;节点定位技术;定位算法;质心定位算法;定位精度

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

文章编号：1009-3044（2021）01-0041-02

Abstract： Node localization technology is one of the key technologies in wireless sensor networks， and localization algorithm is the core of localization technology.In the process of node localization， due to the number of nodes， the distance between nodes and the environment and other factors， the accuracy of node location will be affected. Based on this， a variety of improvements to the positioning algorithm are proposed to improve the accuracy of node positioning.This paper introduces various node localization algorithms based on ranging and non ranging， and introduces several improved methods for Centroid Localization Algorithm in detail.

Key words： wireless sensor network; node positioning technology; location algorithm; centroid localization algorithm; positioning accuracy

1 引言

无线传感器网络（wireless sensor network）是由大量能量、功耗有限制的传感器节点在环境中分布组成的。这些节点可以感知周围环境，并将这些物理信息轉换成为数字信息，进行各种计算并存储。但是如果传感器的位置是未知的，那么从中得到的数据基本是没有任何实际意义的，只有在知道了自身的位置信息后，才能够通过接收到的数据信息来了解外部的环境以及发生的事件。如果采用人工去部署传感其网络节点或者为每一个节点都安装GPS，那么花费的成本将是非常庞大的，由此，就需要研究出一定的算法或措施来使传感其网络对其自身的节点进行定位。

1992 年 ，室内定位系统 Active Badge由AT&T Laboratories Cambridge 开发出来，后来无数的定位算法开始被研究开发出来，目前已经有大量的节点定位算法可以实现节点的自定位。每一种定位算法适用于不同的应用，在各种应用环境下都有不同的精确度。故本文以基于测距和非测距两种前提条件来总结了近年来的一些经典定位算法，并对目前几种与机器学习算法结合的质心定位算法的改进进行研究总结。

2 定位技术介绍

2.1  定位技术的相关概念

一些相关概念如下：

锚节点：WSN中的已知位置信息的传感器节点，又可称为信标节点。

未知节点：WSN中锚节点之外的位置未知的所有节点。

通信半径：传感器节点可以对数据进行接收、存储以及传送，由于节点的传输距离有限，故节点的通信半径就是节点能够传输信息的最大距离。

跳数：在WSN中，当两个无法直接通信的节点通信时所经过的中间节点的数目加1就是这两个节点之间的跳数。

测距：测距就是通过一定的手段来获取两个节点之间的大致物理距离。

RSSI：一个节点发射信号，另一个节点会收到这个节点所发射的信号，这个接收信号的节点所接收到的信号强度就称为RSSI。

2.2  定位算法的分类

目前已经存在的定位算法分类有很多，现在介绍三种主要的分类方法[1]。

2.2.1 集中式算法和分布式算法

集中式定位算法是在传感器网络中设置一个中心节点，其他节点都将信息传输给中心节点来进行处理。此算法适用于监测和控制的应用场景，该算法精确度高，但要求中心节点有较强的计算能力和对信息的处理能力，对能量消耗较大。

分布式算法则是传感器网络中的各个节点互相交换信息，并自己对信息进行处理，计算出自己的位置。此算法降低了网络的通信度，但对于节点有较高的计算能力要求和能量要求。

2.2.2 单跳算法和多跳算法

单跳算法是未知节点与锚节点直接进行数据信息的交流，计算出自身的位置，该算法简单易行，但对锚节点的数量有要求，并且其密度需要偏高。

多跳算法则是未知节点通过一系列的节点与锚节点进行通信，从而计算出自身位置，此种算法解决了测量范围小的问题，但是容易形成误差的累积。

2.2.3 基于测距的算法和基于非测距的算法

基于测距的算法由测距和位置估算两步组成。首先通过算法来测量锚节点与未知节点之间的距离，再使用三边测量等方法来进行估算得到未知节点的估计位置。

此类算法定位精确度高，但传感器节点需要有比较高的硬件性能。

基于非测距的算法根据网络连通度来估计节点之间的距离。常用的基于非测距的方法有质心定位算法、Dv-Hop算法等。

3 定位算法分析

目前学者们研究的定位算法主要是分为基于测距的定位算法和基于非测距的定位算法。对于定位精确度不够高这个问题，国内外的学者们都做了大量的研究以及对于算法的改进。接下来就介绍一些比较经典和新颖的改进算法。

3.1 基于测距的定位算法

目前，大多数学者对于基于测距的定位算法的研究都集中在基于RSSI的定位算法上，因该种算法对于节点的硬件要求以及能耗要求都比较低，但同样的定位精确度比较低，故对其进行研究改进可以大大提升传感器网络节点定位的精确度。

基于RSSI测距是通过传感器网络中的未知节点接收到的锚节点发射的信号强度来计算路径传播损耗，再估算出未知节点与锚节点之间的距离。但是此种测距方法很容易受到如障碍物、反射等外界因素的干扰，从而造成定位的误差。

杨颖辉等人提出了一种基于优化RSS测距的算法[2]。第一步先改进RSSI测距过程，选取了多个锚节点，得到它们之间的距离以及接受功率，然后将其作为参考数值，代入传统的RSSI测距模型公式中，计算出距离的估计值，以此来降低测距误差，之后将定位问题转换成数学求解问题，并使用拉格朗日算法对其求解。此算法降低了定位误差，但略微增加了算法复杂度。

龙海燕等人[3]提出的算法首先对未知节点收到的信号强度通过高斯滤波进行预处理，再通过一个小区域内的锚节点的位置信息来估计该区域的路径损耗模型参数，即一个未知节点与三个或更多相邻的锚节点通信，然后比较收到的RSSI值，选择其中RSSI值最大的节点参与定位，并得到该未知节点区域内的路径损耗模型参数，并建立经验库。该算法提高了定位的精确度，并且增强了测距的抗干扰性。

3.2 基于非测距的定位算法

3.2.1 质心定位算法

质心定位算法是由美国加州大学的学者研究提出来的，其原理是锚节点定期向网络广播自身的信息，当网络中的未知节点收到一定数量的信息后，就用未知节点收到信息的锚节点作为多边形顶点，由此组成的多边形的质心就是未知节点的预估坐标。质心定位算法的优点是简单易行。但是传统的质心定位算法对各组数据的处理采用的权值是相等的，由于各个锚节点本身带有的能量不同，以此估算的未知节点坐标很容易造成误差。基于此，很多学者对其进行了研究改进，并有不错的效果。

张维[4]等人改进的算法，就是用权值来对具有误差的数据进行加权处理，以估算的节点坐标的误差倒数作为权值，较小误差的倒数对应的权值较大。此算法提高了定位的精确度。

张乙竹[5]结合k-means聚类算法对质心定位算法进行了改进。其大致思路是首先利用k-means算法对传感器网络中的节点进行分簇，并得到k个聚类以及每个聚类包含的节点数目n，然后将聚类中心点作为质心定位算法中的多邊形顶点，包含节点数目越多的聚类对应的权值就越大，然后再计算得到未知节点的位置。

3.2.2 DV-Hop定位算法

DV-Hop算法主要是由以下三步组成。第一步，锚节点会通过泛洪的方式将自己的信息传输到整个无线传感器网络中，网络中的节点收到信息后会得到一个跳数就是距离锚节点距离。第二步，当锚节点获得跳距后，会计算出一个平均跳距，然后将这个数据同样采用泛洪的方式传播到无线传感器网络中。第三步，使用一定的方法进行定位计算得到未知节点的坐标。DV-Hop算法的优点时对硬件性能的要求不是很高，缺点是对传感器网络中的节点分布要求比较均匀地分布，不然定位的精确度会比较差。

刘燕等人[6]将改进的蜂群算法与定位算法相结合。此算法首先改进了蜂群算法，对区域进行了限定，然后将改进优化后的蜂群算法应用到DV-Hop算法的第三步节点定位中，优化了多边定位的执行。

朱晓娟等人[7]基于灰狼算法提出了一种改进的方式。此算法是锚节点在计算网络的平均跳距时采用灰狼算法，并计算与其他所有锚节点之间距离，细化平均跳距。最后使用最大似然估计法对未知节点的估算坐标和真实坐标进行一个误差的校正。

4 结论

由于在不同的环境和应用中，具体应用的传感器网络节点定位算法也不同，故研究出适用于普遍场景的定位算法一直是国内外学者的研究重点。本文对目前存在的定位算法做了一个比较简单的介绍，并对其中的一种分类方法进行了较为详细的介绍，结合一些参考文献对于几种改进的定位算法进行了分析和总结。并且从中我们可以发现，现在很多学者开始结合机器算法来对定位算法进行改进，并且都具有不错的改进效果，并且都具有不错的普遍适用性。随着定位技术的发展以及我们生活中的需要，研究出能够通用的定位算法是必需的，也是一定能够成功的。

参考文献：

[1] 吕淑芳.无线传感器网络节点定位研究综述[J].传感器与微系统，2016，35（5）：1-3，8.

[2] 杨颖辉，杨群亭，高铁杠.基于改进RSS测距的拉格朗日优化定位算法[J].火力与指挥控制，2019，44（12）：30-34.

[3] 龙海燕，张天飞，丁娇，等.基于RSSI的测距技术的自动修正定位算法[J].东莞理工学院学报，2019，26（1）：23-27.

[4] 张维，赵亮.基于加权质心算法的无线网络节点定位方法[J/OL].沈阳工业大学学报：1-4[2020-09-12].http：//kns.cnki.net/kcms/detail/21.1189.T.20200909.2048.041.html.

[5] 张乙竹，周礼争，唐瑞，等.基于K-means聚类点密度的WSNs加权质心定位算法[J].传感器与微系统，2015，34（7）：125-127，131.

[6] 刘燕，高丽.改进人工蜂群优化的DV-Hop定位算法[J/OL].激光与光电子学进展：1-13[2020-09-12].http：//kns.cnki.net/kcms/detail/31.1690.TN.20200601.1723.131.html.

[7] 朱晓娟，陈智丽.基于灰狼算法和极大似然估计的改进DV-HOP算法[J].物联网技术，2020，10（5）：38-42.

【通联编辑：梁书】