无线传感器网络中的节点定位算法

【 摘 要 】 无线传感器网络是由部署在监视区域的大量微型的具有无线通信及计算能力的传感器节点，以无线多跳通信方式构成的分布式自组织网络系统。它能根据环境需要，通过功能有限的传感器节点之间的协同工作，对监控区域内的环境或监测对象的信息进行实时感知、采集和处理，获得详尽而准确的侦测数据。本文主要分析无线传感器网络中的定位技术，研究如何降低网络中的能量消耗，延长网络寿命。

【 关键词 】 无线传感器网络；节点定位；锚节点；能量消耗

【 中图法分类号 】 TP393 【 文献标识码 】 A

1 引言

无线传感器网络（Wireless Sensor Networks，WSN）是一种由成百上千的传感节点组成的非结构化的无线网络，通过这些传感节点间的互相协作，WSN同时具备了信息获取、信息处理和信息传播等多种功能。

对于无线传感器网络这个全新的研究领域，吸引了很多学者的目光，尤其是在节点的定位研究方面。对定位的研究能使无线传感器网络的应用更广泛，而高效的定位算法能提高无线传感器网络的其他研究领域的效率。本文首先分析了无线传感器网络的基本概念和结构，然后介绍了常见的节点测距方法，再分析根据各种节点测距方法构造的各不相同的节点定位算法，比较各个算法的优缺点，最后对无线传感器中的节点定位算法的研究未来进行展望。

2 无线传感器网络的概念及结构

无线传感器网络是由大量具有传感功能、数据处理功能和无线通信功能的传感器节点构成的分布式自组织网络，它能根据环境需要，通过功能有限的微小的传感器节点进行协同工作，完成对网络覆盖的地理区域中的对象进行感知、采集、处理和感知信息等任务。

无线传感器网络中的节点根据功能的不同，可以分为普通传感器节点（Sensor Node）、网关（汇聚）节点（Sink Node）和管理节点三类。而传感器节点主要由传感器模块、处理器模块、无线通信模块和能量供应模块四个部分组成。传感器模块负责对监测区域内的信息进行采集以及数据转换，处理器模块是整个传感器节点的中心，它负责完成节点的所有计算、存储和控制等工作，无线通信模块负责与其它传感器节点进行无线通信，完成交换控制信息和传输数据的通信工作，能量供应模块负责为传感器模块、处理器模块和无线通信模块供给能源，提供传感器节点正常工作所必需的能量。

3 无线传感器网络节点的测距方法

无线传感器网络的节点定位是通过被定位节点与已知位置的节点之间的相关性来确定它们空间坐标之间的相关性。在节点定位和目标跟踪算法中主要使用的测量方法有RSSI、TOA、TDOA、AOA等。

RSSI测距方法通过信号传输模型计算出接收信号强度和距离的对应关系，在测量距离时使用本身的无线收发器就能完成信号的收发，不用增加新的硬件设备，降低了设备成本但是定位的精度不是很高。

TOA 通过测量信号从发送节点到接收节点的传播时间来计算节点之间的距离。TOA方法的精度较高，但是需要额外安装特殊的硬件设备来实现信号的接收，增加了硬件成本，此外，TOA要求接收节点和发送节点之间实现严格的时间同步，使得这种测距方法的应用受到了一定的限制。

TDOA通过两种不同信号传播的时间差来计算两个节点间的距离。TDOA测距方法不需要节点之间严格的时间同步，对时间精度的要求较低，计算量小，但是这种方法需要传感节点附加特殊的硬件，增加了传感节点的成本。TDOA方法中使用的超声波受空气的温度、湿度及风速的影响，遇到障碍物，会出现反射、折射和衍射等现象，这些情况会产生较大的误差，影响测距结果。

AOA通过感知信号到达方向，计算节点之间的相对方位或角度，再通过角度计算节点间距离。AOA方法扩展了测距的方法，但是要在传感器节点上安装智能阵列天线，增加了节点的硬件尺寸和能量消耗，而角度的测量有时也会受外界环境影响，产生较大的误差。

4 无线传感器网络中的节点定位算法

定位是无线传感器网络中的一个重要的研究方向，定位算法的优劣直接影响着无线传感器网络在实际应用中是否可行。

质心算法基于网络连通性对未知节点进行定位，当未知节点收到的信标信号数量超过预设门限时，就计算发送信息的锚节点所组成的多边形的质心，把这个多边形的质心作为未知节点的坐标位置。质心算法是一种又简单又易于实现的定位算法，它无需锚节点与未知节点进行协同操作，算法的可扩展性也非常好。但是质心算法的定位精度是由网络中的锚节点的密度决定的，锚节点较少的时候，网络的定位精度较差。

APS （Ad Hoc Positioning System） 是一系列分布式定位算法的统称，包括DV-Hop、DV-distance、Euclidean、DV-coordinate、DV-Bearing和DV-Radial共6种算法。其中，DV-Hop算法APS中最具代表性的算法。DV-Hop算法是一种通过网络中节点跳数来计算距离的算法，用跳数计算出未知节点和至少3个锚节点的距离，再用这些距离计算出未知节点的具置。DV-Hop定位算法的计算量相对较小，节点的能量消耗少，而且传感器节点不需要额外安装其他硬件，降低了网络的成本和能量损耗。但是，DV-Hop定位算法对网络的组织要求较多，在网络节点密度比较大时，定位精度较好，在锚节点分布在监测区域的外侧时，定位精度较好。

MDS-MAP定位算法的基本思想是先从全局角度生产网络拓扑连通图，生成节点间距矩阵，然后用多维标度技术MDS（Multi-dimensional Scaling）生成网络的相对坐标系统，最后把n维的相对坐标系统转化为绝对坐标系统。MDS-MAP定位算法非常灵活，既可以使用测距方法来定位，也可以只使用网络的连通性来进行定位。它的应用范围也较广，既可以应用于锚节点稀疏的无线传感器网络，也可以应用于非凸区域的定位。但是当网络规模增加时，消耗的存储空间较大，计算复杂度和通信复杂度也较高，网络的能耗高。

SDP （Semi-definite Programming）算法是把网络中每个节点之间的通信连接做为节点位置的集合约束，把整个网络模型转化为一个凸集，然后使用半定规划和线性规划得到一个全局优化的解决方案，最终确定节点位置坐标。SDP定位算法是一种集中式定位算法，它把定位问题转化为凸约束优化问题，极大地拓展了定位算法的思路，但是算法的时间复杂度较大，通信开销也较大，而锚节点必须部署在网络边缘，否则节点的位置估算会向网络中心偏移。

目前，无线传感器网络中的定位算法各有特点，分别有各自的适应环境，同时也都存在着不同的不足，还没有一种定位算法能完全满足无线传感器网络的要求，研究更好的定位算法是未来无线传感器网络的一个研究趋势。

5 结束语

无线传感器网络由成千甚至上万的具有感知和传输信息等功能的传感节点组成，这些网络节点通过自组织的方式构成网络，以节点间的互相协作完成信息获取、信息处理与信息传输等网络功能。节点定位技术是无线传感器网络中一项重要的支撑技术，它是无线传感器网络中其他很多应用的基础，节点定位一直都被各国学者和研究机构广泛重视，研究高效的节点定位算法是未来研究的总体趋势之一。

参考文献

[1] 任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）：1282～1291.

[2] 章磊，黄光明.基于RSSI的无线传感器网络节点定位算法[J].计算机工程与设计，2010，31（2）：291～294.

[3] 王伟，陈岱，周勇.基于测距修正和位置校正的RSSI定位算[J].计算机工程与设计，2011，32（2）：409～412.

[4] 苟胜难.基于改进的RSSI无线传感器网络节点定位算法研究[J].计算机应用研究，2012，29（5）：1867～1869.

[5] 诸燕平，黄大庆，李勃.基于AOA的无线传感器网络节点定位算法[J].传感器与微系统，2010，29（1）：98～101.

[6] 林金朝，李小玲，刘海波.无线传感器网络DV-Hop算法改进与性能[J].重庆大学学报自然科学版，32（2）：127～132.

[7] 孙泽宇，魏巍. 一种改进无线传感器网络定位算法的研究[J]. 计算机仿真， 2010， 27（9）：125～127.

作者简介：

陈凤娟（1979-），女，汉族，辽宁本溪人，硕士，副教授，计算机学会会员；主要研究领域：粗糙集、无线传感器网络。