一种无需GPS分布式迭代无线传感器网络节点定位算法

丁自咏 崔艳荣

摘要：针对无线传感器网络中需依赖装配有GPS的信标节点来进行节点定位可能产生的问题进行了分析。首先分析了基于信标节点定位算法的不合理性，利用安装了GPS的信标系节点会增大节点能量消耗，引起能量空洞，缩短网络生存期。提出一种无需GPS分布式迭代定位算法，算法的目的是减少节点对硬件的依赖，减少节点在定位过程信息传递和最小化交换的信息量以及最小化坐标设置时间。将算法与现有的无GPS定位算法进行比较，在算法复杂度、信息交换量以及坐标形成时间上有很大的改进。

关键词：无线传感器网络；GPS；分布式；迭代；定位

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

文章编号：1009-3044（2019）10-0019-03

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

A Distributed and Iteration without GPS Positioning for Sensor Networks

DING Zi-yong， CUI Yan-rong

（The Yangtz university， Jingzhou 434023， China）

Abstract： Focusing on the possible problem in wireless sensor networks that rely on beacon nodes equipped with GPS to locate nodes. Firstly， the irrationality of the algorithm based on beacon node positioning is analyzed. The use of GPS-equipped beacon nodes will increase the energy consumption of nodes，cause the problem of energy hole in wireless and shorten network lifetime. A distributed and iteration without GPS positioning algorithm is proposed. The purpose of the algorithm is reduce the dependence of the node on the hardware， to reduce the information transfer， to minimize the amount of information exchanged and to minimize the time of set coordinates. Compared with the existing GPS-free positioning algorithm， the algorithm complexity， the quantity of information exchanged and the coordinate formation time has been greatly improved.

Key words： wireless sensor networks； GPS； distributed； iteration； positioning

1 引言

無线传感器网络WSNs（wireless sensor networks）是具有空间范围大、节点能量有限、存储空间较小、需进行分布式协调等特点的自适应网络。在大规模WSNs中为了实现诸如：位置感知路由、资源有效协调、削弱能量空洞、均衡网络负载、降低节点能耗、提高网络性能等功能确定节点位置至关重要。有许多学者针对不同应用领域已经设计出很多的WSNs节点定位系统和算法。目前关于WSNs中节点定位的文献大多是基于信标节点来定位的，预先在信标节点上装载有GPS接收器，通过接收到的GPS信号来计算出自己所在的位置。参考文献[1]中从集中式和分布式定位两个方面介绍了利用信标节点进行定位的算法。在传感器节点上安装GPS接收器使其作为信标节点优先知道位置信息这是不合理的，安装了GPS系统会加快节点能量消耗，减少网络生存期。为了减少节点对硬件的依赖，延长网络生存期本文提出一种无需GPS分布式迭代的无线传感器网络节点定位算法。

2 典型的无信标节点定位算法

参考文献[3]中，作者提出了一种在移动自组网中实现无GPS定位的分布式定位算法。该算法选择网络中节点密度最大处的一组节点作为建立全局坐标的参考点，将这组节点中连通度最大的节点作为全局坐标系的原点。先根据节点之间测得的距离在每个节点建立一个局部坐标系。然后每个节点通过节点间的信息交换将其坐标单独重定向到原点的坐标。由于所有的节点都需要进行坐标的建立和转换计算，因此此过程中节点信息交换数量大，通信开销需消耗大量的节点能量。

参考文献[4]中，作者针对上述算法的缺陷，设计了一种基于分簇的无线传感器节点定位算法。节点部署后，每个节点开始递减一个随机计时器，如果节点i的计时器在任何其他节点与它联系前过期，则i成为主节点并广播一条将自己建立为主节点（main node）的消息。所有接收到i广播消息的节点停止计时器成为i的从节点。分簇形成后在每个簇内建立局部坐标系。主节点i中的一些从节点也可以接收到其它主节点发送的消息，这些节点称为边界节点（border node）。局部坐标系通过边界节点向主节点ID小的簇进行坐标转换，逐步建立一个全局的坐标系。该算法无须每个节点都进行坐标的转换，通信开销相比前面的算法开销更小，更适合大规模网络中节点定位。但该算法进行坐标系的转换时算法较复杂、所需时间较长，本文在此基础上提出限定局部坐标系方向的算法以此来减少算法复杂度和坐标形成时间。

3 改进的无GPS定位算法

本文提出的算法采用分簇的方法来建立全局坐标系。整个过程分为3个阶段：簇的形成、局部坐标系的建立、全局坐标系的建立。

3.1 分簇

假设节点在给定平均密度的地理区域内随机部署。节点部署完后每个节点产生一个0到1之间的随机数，如果节点i的随机数小于阈值T （根据网络规模合理设计）则i广播一条自己是主节点的消息。所有接收到i广播消息的节点成为节点i的从节点。主节点i中的一些边界节点也可以从其他主节点哪里接收消息，利用边界节点进行坐标的平移。当某个节点的随机数小于阈值T时就会成为主节点并发送M1消息，收到M1消息的其他节点就会成为该主节点的成员节点，当某个节点接收到2个或2个以上的M1消息时，它将作为边界节点。如下算法1描述节点分簇过程。

3.2 局部坐标系

无线传感器网络中节点间测距的方法有：信号强度法RSSI、到达角度分AOA、到达时间法TOA和到达时间差法TDOA。节点定位是否能够满足精度要求，很大程度上取决于距离测量的精度。造成测量误差的主要原因是测量误差和非视距误差。参考文献[5]中详细地分析了RSSI测距技术的特点。本文采用RSSI来测量节点间的距离。

分簇完成后为了建立局部坐标系，需获得节点间的距离估计值，在本算法中采用不同类型的消息进行通信。节点可以发送以下5种类型的消息：

M1： [節点ID， M1，消息体]，M1消息由主节点发送给从节点，告知邻居节点自己将作为它的主节点；

M2： [节点ID，主节点ID，M2，消息体]，M2 消息让节点用来测其与邻居节点的距离；

M3： [节点ID，主节点ID，M3，消息体]，M3消息由从节点发送给主节点包含从节点到其邻居节点的距离；

M4： [节点ID， M4，消息体]，M4消息由主节点发送，主要包含坐标转换信息；

M5： [节点ID，主节点ID， M5，消息体]，M5消息由边界节点发送给主节点，用于查找发送感兴趣消息的节点。

局部坐标形成时，簇内成员节点发送M2消息测量它与邻居节点间的距离。当成员节点j获得到2个或2个以上的距离估计值时，j就发送M3消息将这些距离估计值发送给它的主节点。主节点收集到所有成员节点的距离估计值后使用三角测量法来建立局部坐标系。簇中存在多个边界节点时，主节点选取ID较大的边界节点来建立X轴，边界节点与主节点连线作为正X轴，主节点作为原点建立Y轴。如下算法2中描述了局部坐标系的建立过程。

α是△pik中ip和ik的夹角。主节点中其他节点借助已经定位的节点用相同的方法来定位。如图1所示是局部坐标系中节点定位示意图。

3.3 全局坐标系

当所有主节点建立了本地坐标系以后，通过边界节点建立全局坐标系。假设主节点i和j共享边界节点k，在局部坐标系建立完成后，将Y轴平移到k点，则此时i点坐标为（dik，0），k点坐标为（0，0）。坐标发生变化后主节点i发送M4消息告诉从节点位置发生变化。从节点更改其坐标。这一过程一直持续到系统收敛到ID最小的边界节点。如图2所示是全局坐标系建立示意图。

4 结论

与参考文献[4]中的定位算法与本文提出的无GPS定位算法进行分析比较。在文献[4]中在形成全局坐标系的过程中，需要借助2个边界节点来测量两主节点间的距离和坐标需要旋转的角度，算法复杂度较高。计算出坐标平移过程中所需的角度和距离后，主节点广播这些消息，从节点重新进行定位计算通信开销和计算开销都比较大。而本文提出的定位方案中，在收敛到全局坐标系时，只需要将坐标系Y轴进行平移，算法复杂度低，主节点只需广播其到边界节点的距离即可，通信开销小。在形成局部坐标系时采用随机数的方法可以减少坐标建立时间。综上所述，本文提出的算法性能优于文献[4]中算法，更适合于大规模无线传感器网络中节点定位。

参考文献：

[1] 于耕，任武君.无线传感器网络节点定位算法研究[J].价值工程， 2018， 37（30）：194-196.

[2] 胡鹏莎.基于DV-HOP无线传感器的网络节点定位算法[J].电子技术与软件工程， 2019， （2）：19-21.

[3] S. Capkun， M. Hamdi and J.-P. Hubaux， “GPS-free positioning in mobile ad-hoc networks，” Proceedings of Hawaii International Conference on System Sciences， pp. 3481-3490， Maui， HW， January 2001.

[4] R Iyengar ； B Sikdar. Scalable and distributed GPS free positioning for sensor networks[J]. IEEE International Conference on Communications ，2003 ，1 ：338-342.

[5] 詹杰，吴伶锡，唐志军.无线传感器网络RSSI测距方法与精度分析[J].电讯技术， 2010， （4）：83-87.

[6] 蔡志强，谷雨，胡燏翀，许胤龙.一种无信标无线传感器网络中的目标定位策略[J].计算机应用， 2007，（8）：1835-1838.

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

[8] 郭建全，赵伟，黄松岭.大规模无线传感器网络分布式无锚节点定位算法[J].高技术通讯，2011（6）：555-561.

[9] 基于质心迭代估计的无线传感器网络节点定位算法[J].物理学报，2016 （3）：9-17.

【通联编辑：梁书】