摘 要

本文首先对无线传感器网络定位算法的基本概念、基本原理进行了叙述，接着介绍了六种经典的无线传感器网络定位算法，并对其中的三种进行了仿真，最后从误差加权的角度对极大似然估计法进行了改进，提高了其定位精度。

论文主要研究了锚节点密度、节点个数以及锚节点分布对质心定位算法、APIT定位算法的影响，并比较了APS中的DV-Hop与DV-distance算法的定位精度，另外从误差权重分析的角度提出了一种基于RSSI加权的极大似然估计法。

研究结果表明：增大节点密度或合理部署锚节点可以提高质心定位算法的定位精度；增大锚节点密度可以提高APIT算法的定位精度；APS算法中DV-distance定位精度明显优于DV-Hop；通过对误差进行加权，可以明显提高极大似然估计法的定位精度。

关键词：无线传感器网络；定位；加权；RSSI；极大似然估计法

Abstract

This paper first describes the basic concept and principle of wireless sensor networks positioning algorithm, then introduces six classical wireless sensor networks positioning algorithms, and three of them are simulated. Finally, the maximum likelihood estimation method is improved from the perspective of error weighting to improve its positioning accuracy.

This paper mainly studies the influence of anchor node density, node number and anchor node distribution on the centroid localization algorithm and APIT localization algorithm, and compares the positioning accuracy of the APS dv-hop and dv-distance algorithms. In addition, a maximum likelihood estimation method based on RSSI weighting is proposed from the perspective of error weight analysis.

The results show that increasing node density or reasonably deploying anchor nodes can improve the positioning accuracy of the centroid positioning algorithm. Increasing the density of anchor nodes can improve the positioning accuracy of APIT algorithm. The localization accuracy of dv-distance is better than dv-hop in APS algorithm. By weighting the errors, the positioning accuracy of mle can be improved obviously.The features of this paper are as follows: the influence of multiple factors on the accuracy of the positioning algorithm is explored, and the weight is determined from the Angle of error generation to improve the positioning accuracy of the maximum likelihood estimation method.

Key Words：Wireless sensor networks；Positioning；Weighted；RSSI；Maximum likelihood estimation

目录

第1章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究进展 1

1.2.1 国外研究现状 1

1.2.2 国内研究现状 2

1.3 论文内容及章节安排 2

第2章 无线传感器网络定位基本理论 4

2.1 定位问题基本描述 4

2.1.1 基本概念 4

2.1.2 基本术语 4

2.2 定位算法分类 4

2.2.1 基于测距和非测距的定位算法 4

2.2.2 集中式计算定位和分布式计算定位 5

2.2.3 基于锚节点定位和无锚节点辅助的定位算法 5

2.2.4 紧密耦合定位与松散耦合定位 5

2.3 性能评价指标 6

2.4 定位基本原理 7

2.4.1 测距技术 7

2.4.2 节点位置的计算方法 8

第3章 无线传感器网络定位经典算法 13

3.1定位经典算法纵览 13

3.1.2 凸规划定位算法 13

3.1.1 质心定位算法 13

3.1.3 包围盒定位算法 14

3.1.4 APIT定位算法 14

3.1.5 APS算法 16

3.1.6 Amorphous定位算法 17

3.2算法仿真与性能分析 17

3.2.1 质心定位算法 17

3.2.2 APIT定位算法 19

3.2.3 APS定位算法 20

第4章 基于RSSI加权的极大似然估计法 23

4.1 问题引入 23

4.2 理论推导 23

4.3 算法仿真与结果分析 25

第5章 结论 28

5.1 论文总结 28

5.2 前景展望 28

参考文献 29

致 谢 30

第1章 绪论

1.1 研究背景与意义

无线传感器网络（Wireless Sensor Networks）是由用来检测物理或环境情况的独立的分布式传感器设备组成的无线网络。无线传感器网络由一系列相互连接的微型传感器节点组成，这些传感器节点除了可以对周围环境进行感知外，相互之间还可以进行通信和数据交换。无线传感器网络主要用于对区域和实体的监测，在军事监测、抢险救灾、城市管理以及医疗卫生等领域有着很大的应用价值^[1]。无线传感器网络的优势在于整个传感器网络的节点排布，而不要求单个节点具有较高的性能。由于单个节点的造价不高，所以在有限区域内大量布置传感器节点是可行的，通过区域内较多传感器节点的排布，可以提高所构成网络的稳定性。

节点的位置信息十分重要，获得传感器节点的位置信息是实现诸如目标定位和追踪、森林防火检测、结构检测、区域环境参数监测、抢险救灾信息采集和传输等应用的基础。如果节点都配备了全球定位系统（GPS），那么获得自身位置是非常容易的。但在实际情况中为网络中的每个节点都配置GPS接收器是不可行的，首先GPS接收器很昂贵，为每个节点都配置GPS会极大地增加网络部署的成本，其次GPS耗能较大，不适用于资源短缺的网络。通常会在网络中布置一些位置已知的节点作为信标节点或者锚节点，位置未知节点与锚节点进行通信，获得一些关于定位的信息后，确定出自身的位置。

1.2 国内外研究进展

近年来，无线传感器网络作为物联网领域的重要技术基础，得到了广泛的研究，定位技术作为其中的支撑技术之一也吸引了不少的关注。关于定位技术，国内外已经提出了很多经典的算法，除此之外，还有很多针对各类算法的改进，下面对其中的经典算法和研究热点做一个概述。

1.2.1 国外研究现状

2000年，南加州大学（USC）的Nirupama Bulusu等人提出了质心算法，这是一种不依赖于测距，仅基于网络连通性的室外定位算法。在质心定位算法中，锚节点会发送包含自身ID和坐标的消息，未知节点接收到锚节点发送的消息后，利用锚节点的分布规划出一个多边形，将多边形的质心作为位置的估计值。质心定位算法完全基于网络的连通性，无需测距，且计算量小，易于实现，但其定位精确度依赖于节点密度。

2000，加州大学伯克利分校（UC Berkeley）的Doherty等人提出了凸规划（Convex Optimization）定位算法，这是一种完全基于网络连通性诱导约束的定位算法。其将整个网络作为一个凸集，将点到点的通信连接视为对点的几何约束，那么未知节点与锚节点之间建立的通信连接将转换为一系列的几何约束，将产生的一系列的几何约束组合起来，就得到了未知节点存在的可能区域。

2003年，美国UVA的Tian He等人提出了APIT（Approximate Point-In-Triangulation Test）算法。APIT算法无需测距，通常适用于大规模网络的分布式定位。

2003年，美国Columbia University的Shang Yi等人提出了MDS-MAP定位算法。MDS-MAP是一种集中式定位算法，可在测距和非测距两种情况下运行。

2003年，美国Rutgers University的Dragos Niculescu和Badri Nath等人提出一系列分布式定位算法，合称APS（Ad-Hoc Positioning System）。APS基于距离矢量路由（Distance Vector Routing）和GPS定位原理，其包括DV-Hop，DV-distance，Euclidean，DV-coordinate，DV-Bearing和DV-Radial六种定位算法^[2]。

2005年，瑞典斯德哥尔摩的Y.Chraibi将包围盒（Bounding Box）算法应用在无线传感器网络的定位中。包围盒算法利用体积稍大的矩形代替圆形，显著降低了定位的运算量。

1.2.2 国内研究现状

2002年，在国家自然科学资金的引导下，国内许多高校开始研究无线传感器网络研究，尤其是2006年国家发改委专项和 973基础研究计划将无线传感器网络列入研究重点后，国内对无线传感网络技术的研究更为热烈 ^[3]。近年来，国内的无线传感器网络技术研究取得了不错的成果，其中2006年，陈克维等提出节点影响力的概念，对质心算法进行基于RSSI测距的加权^[4]，取得了不错定位效果。2007年，张翰等人在凸规划算法中采用三角形内点测试法（PIT），缩小了节点可能存在范围，提高了定位精度。2013年马骏等将RSSI与凸规划相结合，兼顾凸规划算法简单实用的同时小幅度提高了定位精度^[5]。2013年，李牧东等提出一种人工蜂群优化的DV-Hop算法，将定位问题转化为全局优化问题，提高了算法在不同锚节点比例和节点数下的定位精度^[6]。2014年，向满天等对凸规划算法进行改进，提出Convex –CIS算法，用内接圆圆心代替质心估计未知节点位置^[7]，运算较复杂，但精度并没有很大提升。

1.3 论文内容及章节安排

本文针对无线传感器网络定位算法研究的经典领域和近年来的热门方向，作了以下工作：

在对无线传感器网络定位中的经典算法进行理论推导的基础上进行仿真，研究锚节点比例以及节点密度对于不同算法定位精度的影响。

从误差分析的角度提出基于RSSI加权的极大似然估计算法，并对其进行了仿真，验证了其在定位精度方面的提高。

本文的章节安排如下：

第1章：阐述本论文研究背景及意义、国内外现状。

第2章：介绍无线传感器网络定位的基本概念、术语以及相关理论。

第3章：对经典算法进行仿真，分析节点密度、锚节点密度以及锚节点分布对于各个算法定位精度的影响。

第4章：对算法进行改进，提出基于加权的极大似然估计法，并进行仿真实验。

第5章：对论文进行总结，并对未来的工作进行展望。

第2章 无线传感器网络定位基本理论

2.1 定位问题基本描述

2.1.1 基本概念

无线传感器网络的基本组成单元是传感器节点。在无线传感器网络中，“定位”是指传感器节点在不使用外部设施的条件下确定自身的位置^[8]。定位是无线传感器网络的支撑技术之一，节点只有确定了自身的位置之后，得到的监测数据才有价值。在网络部署完成后，首先要确定节点的位置。使用全球定位系统（GPS）可以获得高精度的节点位置，但在实际情况中，由于GPS造价昂贵、能耗高等原因，通常不会为每个传感器节点都配备GPS^[9]。常见的做法是选取一定比例的节点配备GPS，其余节点与配备了GPS的节点进行通信，获得包含距离，坐标等信息的数据，计算出自身的坐标。

2.1.2 基本术语

未知节点（Unknown Node）：部署时未知自身位置的节点，通常未知节点随机地分布在监测区域内，例如，使用飞机随机抛洒的方式部署传感器节点^[8]。

锚节点（Anchor Node）：配备了GPS或在部署时就已知自身位置的传感器节点，通常我们认为锚节点的坐标是可靠的，用于协助未知节点定位，所以在某些资料中锚节点也称为参考节点（Reference Node）、信标节点（Beacon Node）。

邻居节点（Neighbor Node）：能与传感器节点进行通信的节点叫做该节点的邻居节点。

跳数（Hop Count）：两个节点之间可以直接通信，这两个节点之间的跳段数目为1，如果两个节点必须借助第三个点才能建立通信，那么此条通信路径上两个节点之间的跳段数目为2。这里的跳段数目就是跳数。

网络平均连通度（Average Network Connectivity）:网络中所有节点的邻居节点数的平均值。

2.2 定位算法分类

国内外在无线传感器网络定位研究方面已经提出了很多算法，各种算法都有自身的优点和缺点。目前无线传感器网络的定位算法的类别还没有一个通用的划分标准，下面将从四个方面对定位算法进行分类^[2]。

2.2.1 基于测距和非测距的定位算法

根据定位时是否需要获得未知节点到通信半径内锚节点的距离可以将定位算法划分为基于测距（Range-Based）和非测距（Range-Free）的定位算法。基于测距的定位算法需要测量出未知节点到锚节点的绝对距离和方位等信息，再利用三边测量法、三角测量法或者极大似然估计法等方法计算出未知节点的位置；而非测距的定位算法则通过估计未知节点到锚节点的距离或者获得未知节点存在的区域范围等方式计算未知节点的位置。

2.2.2 集中式计算定位和分布式计算定位

集中式计算（Centralized Computation）定位就是将网络中的节点信息发送到一个独立的中心节点，来计算出所有节点的位置。集中式定位的优势在于对整个网络进行统筹规划，节点定位精度高。但同时由于整个网络中节点信息都要汇集到一个计算中心计算，中心节点及其邻居节点会产生较大通信开销，容易造成中心节点附近节点能量过早消耗殆尽导致整个网络与中心节点的通信中断，无法定位。另外当网络扩展时，整个网络的开销会呈几何倍数增长，所以集中式计算定位仅适用于小规模网络。

分布式计算（Distributed Computation）定位指的是，未知节点通过信息交换的方式获得网络中其余节点的情况，自己计算自身的坐标。分布式计算定位是一种并发式的定位算法，节点间不需要进行大量的信息交换，相应的不会产生很大的通信开销，这在无线传感器网络节点的定位中是个很大的优势，因为电能对于造价低廉的传感器节点来说是十分重要的。

2.2.3 基于锚节点定位和无锚节点辅助的定位算法

基于锚节点定位和无锚节点辅助的定位算法的区别在于是否使用锚节点作为参考点。基于锚节点定位的算法以锚节点的绝对坐标为参考，产生所有节点的绝对坐标系统，所以基于锚节点定位也叫绝对定位。而无锚节点辅助的定位算法仅根据节点间的相对位置，计算得到整个网络的相对坐标系统，所以无锚节点辅助定位也叫相对定位。目前绝大多数的定位系统和算法都采用基于锚节点定位产生整个网络的绝对坐标系统，某些算法也可以根据网络的不同配置实现相对定位和绝对定位。

2.2.4 紧密耦合定位与松散耦合定位

紧密耦合定位系统不仅对锚节点的部署位置有着十分严格的要求，而且需要锚节点与中心控制器间建立有线连接。紧密耦合系统具有实时性好、定位精度高的优点，另外时间同步和锚节点间的协调问题也容易解决，但其网络扩展性差、部署费用高，不适用于难以进行布线工作的室外环境。典型的紧密耦合系统有Active Badge、Smart Floor和3D-iD等。

松散耦合定位依赖于节点与其邻居节点之间的信息交换，没有中心控制器。其牺牲定位的精确性来换取部署的灵活性，许多定位系统和算法如AHLos和APIT等都采用了松散耦合定位方式。

2.3 性能评价指标

无线传感器网络定位算法的优劣与其应用的场景有关，场景不同，对于算法的要求也不同。例如对于室内定位系统，我们通常希望其具有较高的定位准确性，而对于野外等资源短缺情况下的定位，我们通常希望在达到一定的定位精度的条件下，尽可能地降低节点功耗，以延长整个传感器网络的续航时间。

评价一个定位算法的性能，可以从定位精度、网络平均连通度、规模、锚节点密度、节点密度、功耗、成本、容错性和自适应性等方面考虑。在选择定位算法时，要根据具体的应用场景对算法的各个方面进行权衡，选出最合适的算法。下面对这些评价指标进行具体分析。

定位精度：定位精度可以用归一化平均定位误差来衡量，即用所有节点估计位置与实际位置间欧氏距离的平均值与节点通信半径的比值来表示，定位的精度是评测算法时的一个很重要的指标。

网络平均连通度：即网络中节点的平均节点数目。

规模：基础设施或者定位时间一定的情况下，定位算法可以定位的目标数目也是设计算法时关心的一个方面。例如MDS MAP算法可以做到实时地定位一个房间或一层楼的目标，但随着传感器网络规模的扩大，定位算法的时间开销急剧增加，导致无法实时地对目标进行定位。

锚节点密度：锚节点密度是指无线传感器网络中锚节点数目与节点数目总量的比值。通常锚节点会配置GPS或在部署时就知道了其准确位置，锚节点比例的增高能提高定位精度，但同时也会增大部署的成本，所以锚节点密度也是评价定位算法的一个重要指标。

节点密度：节点密度是指单位面积区域内部署节点的数量，通常也用网络的平均连通度表示，节点密度增大会增大网络的部署费用^[10]，同时会因为有线带宽的问题导致节点间通信冲突。