无线传感器网络定位理论和算法研究

赵立新

摘 要：无线传感器网络在目前社会发展和个人生活中有着广泛的应用，作为无线传感器网络设计实现及应用当中的关键组成部分，定位技术承担了提供位置信息服务的重要作用，属于无线传感器网络的支撑技术之一。本文首先对无线传感器网络定位理论进行叙述，分析了目前定位系统及算法的不足，然后结合当前典型定位算法设计思想及适用范围，对其网络定位理论及算法的未来研究方向进行探索。

关鍵词：无线传感网络 定位理论 算法

中图分类号：TP212.9 文献标识码：A 文章编号：1672-3791（2018）03（b）-0007-02

无线传感网络能够实现物理世界与网络世界的相互连接，目前广泛应用于军事与民用领域，为了提高传感器在外界信息获取的准确程度，形成具体的物理事件，需要采取定位算法来实现精准定位，但是在某些特定领域的定位计算中仍旧存在一定的误差，同时忽略了各节点之间可能存在的潜在联系，影响定位结果的精度。基于以上情况，需要在对无线传感器网络定位理论进行分析的基础上，研究高性能定位算法，保证定位结果的精确程度。

1 无线传感网络和定位技术概述

1.1 无线传感网络

无线传感网络是由部署在需要监控区域中大量微型传感器节点所形成的，根据实际检测需求，这些传感器由人工或者飞机播撒的方式进行部署，其主要作用是对该区域感知对象的信息进行采集，然后通过无线网络将所收集到的信息传输给观察者。无线传感网络主要包括检测节点、汇聚节点、网络和终端[1]。对于传感器网络节点来说，其作用包括数据采集、数据处理、数据传输和电源，根据检测需求，监测节点中传感器包括温度、湿度、振动、压力和热量等模块。

1.2 定位技术

定位技术在监测节点中起着至关重要的作用，依靠定位技术，能够准确获得位置信息，没有位置信息的监测数据无法解释成具体物理事件，缺乏可用性。在另外一个方面，定位技术也可以为其他网络模块提供服务，比如：采用定位技术辅助路由，路由表不需要节点进行储存和维护，从而实现无状态路由。总的来说，由于节点无法准确获得自身的位置，所以需要在部署传感器之后进行实时准确的定位，而定位技术就是根据一些已知的位置节点，按照特定算法计算出自身位置的过程[2]。

2 定位技术基本概念

2.1 锚节点

锚节点也被称为信标节点，指的是能够直接获取自身位置信息的节点。

2.2 未知节点

除了锚节点之外的节点被称为未知节点。当此节点需要特殊定位的情况下，未知节点也被称为目标节点。一些定位成功的未知节点也被称为伪锚节点。

2.3 参考节点

当对某些节点进行定位的时候，需要借助其临近节点位置信息来进行，这样的节点就是参考节点。锚节点和未知节点都可以作为参考节点来使用[3]。

2.4 测距图

测距图G一般用来表示给定网络，测距信息G=（V，E），其中的V是网络节点，边（i，j）∈E为i节点与j节点之间的距离。通过V节点与E来表示测距信息，通过这两个信息获得未知节点的位置，这个图G就是测距图。

2.5 可定位网络

针对对应的定位问题，一个定位成功的网络是可解的。

2.6 可定位节点

在给定网络及相应测距图的基础上，通过锚节点和测距信息获得最大可定位节点，这样的节点就被成为可定位节点，其他节点为不可定位节点，这些不可定位节点不能用任何定位算法进行定位[4]。

2.7 定位问题

在给定网络和测距图的情况下，计算可定位节点物理位置的问题就是定位问题。

2.8 定位算法性能。

给定网络和测距图，定位问题能够采用这个定位算法顺利解决，其性能就是根据定位可定位节点的比例来确定的。

3 无线传感器网络定位理论分析

3.1 定位理论基本定义

根据以上定位技术的基本定义可以看出，在给定网络与测距图的情况下，通过锚节点与测距信息，来对临近节点进行定位，并且将已经定位的节点当作参考节点，进行下一次的未知节点定位，直到成功定位所有可定位节点为止，这样重复的定位过程显得更加复杂，在此基础上，如果锚节点和测距信息不能同时获得，或者得到的信息并不精准，相应定位问题将变得更加复杂。当前普遍通过刚性理论描述网络可定位性，相关定义如下：

（1）基础图。在测距图GN中的边合集EN中增加所有锚节点所连接的边，所得出的G'N=V，EN∪（i，j），这样图就是基础图。

（2）刚性。测距图顶点间距离不改变的情况下，不能连续进行形变，说明此图是刚性的。

（3）冗余刚性。在图G为刚性的情况下，删除途中任何一条边，图G仍然是刚性的，说明图G是冗余刚性。

（4）点行。在基础图当中，d维空间中点的合集定义为P，所对应的点形为Fp，Fp=（p，L），L为对应基础图边合集的链接合集。点形Fp只能确定唯一基础图，以此来表示点与点之间的连接属性[5]。

3.2 网络可定位条件分析

结合以上定位..理论基本定义中的刚性理论，可以知道网络可定位的条件包括这些方面：在给定d（d=2，3）维空间网络N的情况下，包括m个锚节点，对应位置为p，其中包括n—m个锚节点，表示为（m+1），（m+2）···，n，对应位置P为Pm+1，Pm+2···，Pn，如果d=3，m≥4，可以用典型Fp来表示网络N，这样的网络N能够被定位，同时对于Fp是刚性的。但是，在二维空间d中，同样存在一些特殊情况，能够使刚性图不完全满足刚性，这样的特殊情况包括翻转和折转，针对折转来说，网络N中的一些锚节点翻转到镜像位置，从而发生形变，导致刚性图不能完全满足刚性。

4 无线传感器网络定位算法分析

目前关于无线传感器网络定位算法的研究有很多，根据定位需求选择不同的定位算法，结合定位过程，对节点之间的距离进行测量是不是必要的，目前的定位算法可以分成基于硬件测距的定位算法和不需要硬件测距的定位算法。

4.1 基于硬件测距的定位算法

基于硬件測距的定位算法，是一种测量节点之间距离来进行定位的，而硬件测距工具和相关测量技术决定了定位精度，主要体现在以下几个方面。

（1）基于时间测距的定位。基于时间测距的定位技术，也就是通过无线信号的传播时间，和已知无线信号传播速度，计算两个节点之间的距离，也就是信号发射到信号接收之间的距离，然后对锚节点距离进行计算，从而得出相应的参考节点，目前基于时间测距的定位算法包括三边测量法[6]。目前这种算法是最常用的定位算法，其主要原因是对成本和硬件要求较低，但是影响测距精度的因素有很多，首先，大气环境条件会影响无线信号传播速度，噪声、传播路径和环境差异也会在一定程度上影响测量精确度，所以，在采用此方法进行测量的情况下，需要在最大程度上控制好环境及硬件测量工具条件，以此来有效提高定位精度。

（2）基于到达时间差距的定位技术。这种定位技术与基于时间测距定位技术有着相似之处，主要是通过两种速率不同信号的传输时间差，结合其传输速度，来对节点之间的距离进行测定，其算法体如下。

比如两种不同速度的信号被同时发出，速度为C1、C2、接收器接收信号到达时间为T1、T2、两节点之间距离测定公式为：

（T2-T1）×（C1C2/C1-C2） （1）

基于信号强度测距的定位技术。从信号发射器发射相应无线信号，记录信号发射时的强度，然后在接收到信号时候，将其信号强度与信号发射强度进行对比，结合信号传播衰减模型，计算信号传输损耗规律，从而得出两个节点之间的距离。在有相关模型的情况下，这样的定位技术较为简单，但是容易受到非视距和噪声的影响，适合精度要求低的节点定位。

4.2 基于非硬件测距的定位算法

4.2.1 质心算法

质心为几何多边形的中心，质心坐标位置就是多边形定点坐标的平均值，假设质心坐标为（x，y），多边形A、B、C、D、E的顶点坐标分别为A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4），E（x5，y5），质心坐标（x，y）=（x1+x2+x3+x4+x5/5，y1+y2+y3+y4+y5/5）。在进行质心算法的过程中，Anchor node能够不断地向邻近节点发送信息，包括Anchor node的位置信息，在对这些信息进行接收的过程中，会设置相应阈值，当不符合阈值要求的情况下，能够自动停止接收数据，根据接收到的坐标位置信息，根据以上公式进行计算，得出质心坐标，也就是锚节点的位置。

4.2.2 基于DC的定位算法

DC（delaunay complex）是三角剖分的扩展，DC能够对整个网络进行划分，在网络是完全刚性的情况下，可以先对网络边界和中轴进行识别，然后选取地标节点，构建相应的DC，进行平面镶入，最后结合节点位置，实现节点定位。

5 结语

定位技术在无线传感网络中占据了非常终于重要的位置，需要根据实际适用领域需求，选择合适的定位算法，当前定位算法仍旧存在着算法定位能力与理论上限处于同一水平、复杂程度过高、精确程度不足和误差处理影响性能等问题，结合定位算法刚性理论，未来的定位算法存在极大研究空间，期待定位算法的提升完善能够推动无线传感网络的快速发展。

参考文献

[1] 王小平，罗军，沈昌祥.无线传感器网络定位理论和算法[J].计算机研究与发展，2011，48（3）：353-363.

[2] 王刚刚，王正.无线传感器网绪定位算法原理与研究进展概述[J].木工机床，2016（2）：18-20.

[3] 张可.无线传感器网络分布式定位算法研究[D].燕山大学，2012.

[4] 宫月.无线传感器网络定位算法研究[D].华北电力大学，2013.

[5] 李牧东，熊伟，梁青，等.无线传感器网络DV-Hop定位算法研究[J].空军工程大学学报：自然科学版，2012，13（4）：75-79.

[6] 张欣慧，徐晶晶，许必宵，等.无线传感器网络三维定位算法研究[J].计算机技术与发展，2016，26（12）：195-199.