毕业论文初稿1

华中农业大学楚天学院本科毕业论文（设计）

目 录

摘 要 ·························· 错误！未定义书签。 关键词 ·························· 错误！未定义书签。 Abstract ························· 错误！未定义书签。 Key words························· 错误！未定义书签。

一、概论 ························· 错误！未定义书签。

1.1 无线传感器网络研究背景及研究意义 ········· 错误！未定义书签。

1.2 国内外研究现状 ·················· 错误！未定义书签。

1.3 无线传感器网络的应用前景 ······················ 2

1.3.1 军事防御 ··························· 2

1.3.2 环境监测 ··························· 2

1.3.3 医疗卫生 ··························· 2

1.3.4 反恐抗灾 ··························· 2

1.3.5 其它领域 ··························· 2

二、无线传感器网络定位技术 ····················· 3

2.1 无线传感器网络概述 ······················· 3

2.2无线传感器网络节点的结构 ······················ 3

2.3基于测距技术的定位算法分析 ····················· 3

2.3.1三边测量法 ·························· 4

2.3.2三角测量法 ·························· 4

2.3.3 最大似然估计定位 ······················· 5

2.4 无需测距技术的定位算法分析 ····················· 5

2.4.1 质心算法 ··························· 6

2.4.2 DV-hop算法 ·························· 7

2.5 节点定位算法分析 ·························· 7

2.6 典型的相对定位算法 ························· 8

2.6.1 1SPA算法 ··························· 9

2.6.2 聚类SPA算法 ························· 9

2.7 功耗与代价 ····························· 9

三、两种基本算法的仿真分析 ························· 9

3.1 三边测量法定位 ·························· 10

3.2 质心算法定位 ··························· 10

3.3 定位算法的仿真实验 ················ 错误！未定义书签。

3.3.1 三边测量法仿真 ··············· 错误！未定义书签。

3.4 三边质心定位算法仿真 ··············· 错误！未定义书签。

3.5 运用Matlab对节点定位精度仿真 ··················· 11

四、分析 ································· 12 参考文献 ································· 13 致 谢 ·································· 14

无线传感器网络定位算法分析与研究

摘 要

节点位置信息是无线传感器网络应用的基础，在许多应用中都需要知道节点的位置，并且在某

[1]些特定环境下还需要获得节点的相对位置。论文在查阅大量文献的基础上，综述介绍了无线传感

器网络自身定位系统和算法的性能评价标准和分类方法,综述了近年来该领域具有代表性的算法及系统的原理和特点,并指出未来的研究方向。并且分别对无需测距技术的传感器网络定位算法和基于测距技术的传感器网络定位算法进行精度仿真比较，并且各选取一种算法进行仿真，并且着重讨论和分析了其中两种典型的基本算法--三边测量法以及三边质心算法，并且分析两者的优缺点及其应用范围。最后本文从理论分析和仿真实验的两个方面评估了所提出的定位算法的性能。仿真结果表明在基于测距技术基础上的三边测量法显示的结果更加精确。

关键词

无线网络传感器；基于测距技术；无需测距技术；三边测量法；三边质心算法；

Wireless sensor network localization algorithm analysis and research

Abstract

The information of node localization is the base in application of Wireless Sensor Networks，In many applications need to know the position of the node，And in some special conditions is needed to obtain the relative positions of nodes。The paper on the basis of references，Overview of wireless sensor network localization system and Algorithm performance evaluation criteria and classification method。Summarized the field representative algorithm and system principle and characteristics in recent years。And pointed out the future research direction。As a result of range-free technology sensor network localization algorithm based on distance measurement technology is not so accurate sensor network localization algorithm。So this paper will research basic ranging technology network technology of sensor network localization algorithm。And emphatically discusses and analyzes the two kinds of basic algorithm-- Three

edge measuring method and triangulation method。And an analysis of both advantages and disadvantages and application scope。Finally, this article from the theoretical analysis and MATLAB simulation experiment of two assessment of the proposed algorithm performance。The simulation results show that based on the distance measuring technology based on the three edge measuring method showed more accurate results。

Key words

Wireless sensor network；Range-based；Range-free；Three edge measuring method;

algorithm；

Three edge centroid

1 概论

1.1 无线传感器网络研究背景及研究意义

无线传感器网络被列为21世纪最有影响的21项技术和改变世界的10大技术之一。随着半导体技术，微机电系统、通信技术和计算机技术的飞速发展，在20世纪90年代末，美国开发了具有现代意义的无线传感器网络技术（WSN）。无线传感器网络以其低功耗，低成本，以及分布式的优点被一些重要机构预测为讲改变世界的重要新技术之一，它将在信息感知领域带来一场变革。

无线传感器网络作为一种新兴的技术出现，它的应用也为我们带来了技术的挑战，而节点的准确定位就是其中一项重要的支撑技术。首先，无线传感器网络中的节点所探测到的信息必须结合节点自身的位置,才使得这些信息具有现实意义，否者失去节点的位置信息，节点所探测到的数据将由于不知道具体位置而失去应用的意义。其次，节点的准确位置也是高效的路由选择以及外部目标追踪的基础和必要信息。因此，对节点自身的准确定位在无线传感器网络应用发挥着重要的作用。

无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络。它的目的是协作地感知，采集并且处理其覆盖领域中感知其监测目标的信息，并且最终发送给观察者，由于无线传感器网络的远程监控，能在恶劣的环境或者人为不可达环境中工作的特点，它可以广泛应用于各种领域，比如环境监测，军事国防，交通管理，医疗卫生等。

对于节点的定位一直比较直接的想法是为每一个节点配备GPS定位装备，然而无线传感器网络由大量的节点组成，如果使用GPS将无疑极大的增加网络成本。另外GPS装备非常耗电，而无线传感器网络的节点是利用电池供电，电池能量有限并且无法及时充电，客观上也不允许在每个节点上装备GPS装备。因此，在设计无线传感器网络的定位算法时必须考虑到成本，能量有限等特点。无线传感器网络在国内仍处于初期研究阶段，在国外也没有一个成熟的算法作为标准，因此对于无线传感器网络定位技术仍处于早期的研究阶段。

当前对于无线传感技术的研究仍然处在一个高速发展的阶段，低功耗就是其发展方向之一，而低功耗与高性能的结合实现还不完全。因此，为了更好的实现无线传感模块的功能，增加模块的可靠性和使用寿命，通过对无线传感节点的硬件功耗的分析，确定无线传感模块各单元的基本功率消耗，并进行相应比较，确定需重点降耗的单元，在此基础上结合当前对低功耗无线传感模块的研究，通过对比分析选择合适的芯片完成对低功耗无线传输模块的自主设计和制作。并辅助软件开发人员完成各子模块的驱动编写，实现低功耗无线传感模块的整体通信功能。

无线传感网络是一种开创了新应用领域的新兴概念和技术。当前，传感技术、传感网络已经被认定为最重要的研究之一。无线传感器网络节点的稳定运行是整个网络可靠性的重要保障。低功耗无线传感模块研究具有极其重要的学习和研究价值，其功能的实现具有极其重要的理论和现实意义。

首先，现有的众多研究中，将性能和低功耗相结合的较少，有的只考虑低功耗而性能不高，有的性能高但是功耗太大。本文综合了性能和低功耗的共同需求，经过深入的分析和对芯片的数据比较，提出了低功耗无线传感模块的硬件设计思路。

其次，增加无线传感模块的应用。无线传感模块应用已非常广泛，除去组成无线传感网络的应用外，无线传感技术还广泛的应用于环境监测，如车间温湿度、压力等；短距无线通信等。实现了无线传感模块的低功耗，其对电能的需求就会更小，应用的范围将会进一步的扩大。

[2]

1.2 国内外研究现状

无线传感器网络的构想最初是由美国军方提出的，美国国防部高级研究所计划署（DARPA）于1978年开始资助卡耐基－梅隆大学进行分布式传感器网络的研究，这被看成是无线传感器网络的雏形。在这些项目取得进展的同时，其应用也从军用转向民用。在森林火灾、洪水监测之类的环境应用中，在人体生理数据监测、药品管理之类的医疗应用中，在家庭环境的智能化应用以及商务应用中都已出现了它的身影。早在上世纪70年代，就出现了将传统传感器采用点对点传输、连接传感控制器而构成传感器网络雏形，我们把它归之为第一代传感器网络。随着相关学科的的不断发展和进步，传感器网络同时还具有了获取多种信息信号的综合处理能力，并通过与传感控制器的相联，组成了有信息综合和处理能力的传感器网络，这是第二代传感器网络。而从上世纪末开始，现场总线技术开始应用于传感器网络，人们用其组建智能化传感器网络，大量多功能传感器被运用，并使用无线技术连接，无线传

[3]感器网络逐渐形成。

随着无线传感器网络的兴起，节点的自身定位引起了许多学者极大的关注，也成为无线传感器定位的研究热点之一。定位问题是无线传感器网络各种各样应用的基础，总的来说，定位的机制和算法分为两个部分：节点的自身定位和外部目标定位。而前者是后者的基础 虽然国内外在定位这一问题上取得了一些的成果，但是仍处于研究初期阶段。尽管目前开发了一些算法来解决定位问题，在定位效果上也取得了不错的成绩，但是每一种算法都是适合某类具体的应用，没有一个通用的算法可以涵盖所有的应用因此没有形成行业标准。 关于无线传感器网络自身定位算法的研究成果，可以按照无线传感器定位算法的发展分成三大类：

1. 第一类是偏重于基于基础设施的定位算法（Infrastructure-Based Algorithm）。 这类算法的典型代表为1992年AT&T Badge定位系统，在1999年设计了Active Bat定位系统，都用于室内的定位，2000年MIT发开了Cricket定位系统，采用射频信号和超声波信号实现节点定位。微软于2003年开发了RADAR系统，实现系统定位与跟踪。第一类的算法依赖于外部的基础设施为定位系统提供硬件支持，因此对硬件要就较高，实现的成本也较高。

2. 针对第一类偏重于基础设施的定位算法的缺点，第二类算法提出依赖于锚节点的定位算法（Beacon—Based Algorithm）。它与无线传感器网络中将部分节点配备特殊装置或者人工部署来得到这部分节点的先验节点位置，通过节点之间的信息转发、记录和传播等信息的交换，按照某种定位的机制来计算其他节点的位置，这样可以得到网络中所有节点的位置。

3. 第三类算法提出了不基于锚节点的定位算法，利用节点分布概率的模型来实现网络中所有节点的定位。如KPS（Deployment Knowledge-based Positioning System）算法和ABC（Assumption Based Coordinates）算法，以及AFL（Anchor-Free Localization）算法。这类算法无须锚节点，但是需要预先知道网络部署的模型以及特殊的设备来实现定位，因此其应用的范围也受到一定的限制。

1.3 无线传感器网络的应用前景

1.3.1 军事防御

a．军事传感器网络探测和获取敌军情报。由于战场情况复杂，如果靠人去收集敌方情报是很危险的，而通过将传感器网络放置在敌军阵地却可以安全地获得精确的信息，同时也不容易被敌军察觉。

b．在士兵、装备及军火上加装传感器以供识别，分清敌我，防止误打。监控战场上的状态。通过飞机空投等方式将大量廉价微型的传感器节点散布在预定区域，通过这些传感器节点实时监测周围环境的变化，并将监测到的数据通过卫星信道等方式发回基地，这样就可以实时地监控战场上的状态。

c. 跟踪射击对象的位置。通过传感器节点对射击对象的跟踪、定位，实现精确制导。 d. 探测及判定化学、生物、放射、核子等物质和攻击。利用传感器网络及时、准确地判断是否有生化武器及核武器的攻击，确定生化源、爆炸中心的位置，为军队提供反应时间，从而最大可能地减小伤亡。

1.3.2 环境监测

目前的环境状况逐渐恶化，已引起人们广泛的关注。加强对环境的研究，防止进一步的恶化，具有重大的意义。环境监测主要包括以下几个方面：

a．监测平原、森林、海洋等的环境变化；

b．提供遭受化学污染的位置并检定出化学染的种类，避免工作人员冒险进入受污染区域； c．灾害判定；

d．监测空气污染、水污染及土壤污染；

e．生态上的监控，例如生物栖息地与觅食习惯。

1.3.3 医疗卫生

a．佩戴在病人身上，对血压、心率等各项健康指标进行实时监测；

b．作为隔离病房的监控设备，减少医生护士进病房的次数。

1.3.4 反恐抗灾

美国911 事件的发生，使反恐成为各国普遍关注的问题。反恐问题主要是要及时的收集信息，加强对周围环境的监测，能够及时有效地应对突发事件，将传感器网络技术应用于反恐问题，可以有效地放置恐怖袭击事件的发生。

1.3.5 其它领域

另外还有在工业制造、交通控制、空间探索、能源、食品安全等领域中都有着广泛的应用。

2 无线传感器网络定位技术

2.1 无线传感器网络概述

无线传感器网络是由散布在工作区域中大量的体积小，成本低，具有无线通信、传感和数据处理能力的传感器节点组成的。每个节点可能具有不同的感知形态，例如声纳、震动波、红外线等，节点却可以完成对目标信息的采集、传输、决策制定与实施，实现区域监控、目标跟踪、定位和预测等任务。每一个节点都具有存储、处理、传输数据的能力。通过无线网络，传感器节点之间可以相互交换信息，也可以把信息传送到远程端。传感器网络是由大量节点组成的，为加强对这些节点的控制，还可以设置一个基站，用来获取各个传感器节点的位置信息、探测到的目标信息等。传感器、感知对象和观察者是传感器网络的三个基本要素；有线或无线网络是传感器之间、传感器与观察者之间的通信方式，用于在传感器与观察者之间建立通信路径；协作地感知、采集、处理、发布感知信息是传感器网络的基本功能。一组功能有限的传感器协作地完成大的感知任务是传感器网络的重要特点。传感器网络中的部分或全部节点可以移动。传感器网络的拓扑结构也会随节点的移动而不断地动态变化。节点间以Ad Hoc 方式进行通信，每个节点都可以充当路由器的角色，并且每个节点都具备动态索定位和恢复连接的能力。观察者是传感器网络的用户，是感知信息的接受和应用者。观察者可以是人，也可以是计算机或其他设备。一个传感器网络可以有多个观察者。一个观察者也可以是多个传感器网络的用户。观察者可以主动地查询或收集传感器网络的感知信息，也可以被动地接收传感器网络发布的信息。观察者将对感知信息进行观察、分析、挖掘、制定决策，或对感知对象采取相应的行动。感知对象是观察者感兴趣的监测目标，也是传感器网络的感知对象，如坦克、军队、动物、有害气体等。感知对象一般通过表示物理现象、化学现

象或其他现象的数字量来表征，如温度、湿度等。一个传感器网络可以感知网络分布区域内的多个对象。一个对象也可以被多个传感器网络所感知。

2.2无线传感器网络节点的结构

传感器网络系统通常包括传感器节点（sensor）、汇聚节点（sink node）和管理节点。大量传感器节点随机部署在监测区域（sensor field）内部或附近，能够通过自组织方式构成网络。传感器节点监测的数据沿着其他传感器节点逐跳地进行传输，在传输过程中监测数据可能被多个节点处理，经过多跳后路由到汇聚节点，最后通过互联网或卫星到达管理节点。

[4]用户通过管理节点对传感器网络进行配置和管理，发布监测任务以及收集监测数据。

传感器网络节点的组成和功能包括如下四个基本单元：传感单元（由传感器和模数转换功能模块组成）、处理单元（由嵌入式系统构成，包括CPU、存储器、嵌入式操作系统等）、通信单元（由无线通信模块组成）、以及电源部分。此外，可以选择的其它功能单元包括：定位系统、运动系统以及发电装置等。

传感器网络节点一般由数据采集单元、数据处理单元、数据传输单元组成。如图1所示:

图 1 传感器网络节点组成图

数据采集单元包括传感器和A/D 转换设备，负责目标信息的采集。传感器根据不同的目标特定采用不同的传感形态，如声纳、超声波、红外、温度、烟雾等。数据处理单元一般由单片机或微处理器、嵌入式操作系统、应用软件等组成，负责将采集到的目标信息进行处理。它将节点的位置信息、采集到的目标信息以及目标信息的空间时间变量综合分析，然后将处理结果送到数据传输单元或存储在本地。这里将使用一些算法实现对目标的识别、跟踪、定位等。对于可以移动的节点，它还可以根据分析结果对运动机构如机器人进行控制，使之朝着靠近目标的方向前进。数据传输单元一般是由无线收发模块组成，负责数据的接收和发送。它可以是节点之间的通信，也可以是节点和基站之间的通信。

2.3基于测距技术的定位算法分析

2.3.1三边测量法

三边测量法是一种基于距离的定位算法，其算法描述如下：设未知节点D坐标（x，y），已知A,B,C3个点坐标分别为（x 1, y1），（x2，y2），（x3，y3），它们到D的距离分别为r1，r2，r3.因此可以得公式如下：

2(X1x)2(Y1y)2r1222(Xx)(Yy)r222

222(X3x)(Y3y)r3

由于现有的测距方法受环境噪声、多径效应和障碍物干扰等影响，测得的距离存在一定的误差，导致节点定位也产生误差，将会导致三个圆不能相交于一点，在这种情况要用最大近似法估计节点位置。

2.3.2三角测量法

在二维空间中,知道了1个点到3个点或者3个以上点的距离,就可以确定该点的位置。三边测量法的基本原理就是求3个已知半径和坐标圆心的圆的交点。在传感器网络的部署中大多采用平面部署,属于二维部署的问题,因此可以采用此法。在基于测距的定位算法中,三边测量法是计算坐标的基本途径。如图2，所示,三边测量定位法的基本原理就是求3个已知半径和坐标圆心的圆的交点。假设已知3个锚节点A、B、C的坐标,未知节点D的距离分别为d1,d2,d3,根据二维空间距离计算公式,联立解方程组就可得到未知节点D的坐标。三边测量法的缺点是:若在测距过程中存在误差,上述3个圆无法交于一点,以存在误差的a1,a2,a3去解方程时便无法得到正确解。因此,在实际计算坐标时,一般不采用上述解方程

[5]的方法,而采用极大似然估计或其他方法.

图2 三边测量法示意图

2.3.3 最大似然估计定位

最大似然估计法必须要超过3个锚节点的位置信息，所以应用受到一定限制，毕竟网络

[6]中锚节点数目有限。基本思想是当一个节点可以获得足够多的锚节点信息形成多个方程

组，协作定位出多个节点的位置。如图3(a)和(b)所示，图(a)很容易求节点位置，图(b)中有两个未知节点，四个锚节点，节点2有三个邻居节点1、3、4，节点4的三个邻居节点为2、5、6，且1、3、5、6都是已知的节点，5个距离方程中有4个未知数(节点2和4的坐标)，利用节点间协作计算出未知节点2和4的位置。

6 (a) 锚节点

图 3 (b) 未知节点

图 4 质心算法示意图

[2.4.2 DV-hop算法

DV-Hop(Distance Vector-Hop)算法是一种基于距离矢量计算跳数的算法,该算法的核心思想是未知节点通过路由方法“测量”与信标节点之间的最少跳数,并计算每跳的平均距

[7]离,以最少跳数和平均跳距的乘积作为未知节点和信标节点之间的距离估计。DV-Hop算法

简单,不需要进行节点间的距离测量,可以避免测量时带来的误差,对于各向同性密集网络,可以得到合理的平均每跳距离,从而能够达到适当定位精度。但DV-Hop算法定位精度依赖于具体网络的部署条件,通信费用较高。

DV-Hop 算法由 3 个阶段组成。首先使用典型的距离矢量交换协议,使网络中所有节点获得距锚节点的跳数(distance in hops)。第 2 阶段,在获得其他锚节点位置和相隔跳距之后,锚节点计算网络平均每跳距离,然后将其作为一个校正值(correction)广播至网络中。校正值采用可控洪泛法在网络中传播,这意味着一个节点仅接受获得的第 1 个校正值,而丢弃所有后来者,这个策略确保了绝大多数节点可从最近的锚节点接收校正值.在大型网络中,可通过为数据包设置一个 TTL 域来减少通信量.当接收到校正值之后,节点根据跳数计算与锚节点之间的距离。当未知节点获得与 3 个或更多锚节点的距离时,则在第 3 阶段执行三边测量定位。

假设有信标节点i 、j 、k ，信标节点i 与 j 和k之间的实际距离已知，分别为dij 和dik，其中dijCi，跳数hij为 3 跳，hik为 4 跳，则信标节点i 计算的平均每离为跳距：

Cidijdik

hijhikdijdik34 2.5 节点定位算法分析

距离测定：就是获得两个节点之间距离的方法，

可分为基于测距和无需测距。基于测距的算法(range-based)通过节点自身携带的测距功能直接测量两个节点之间的距离。当前比较重要的测距方法主要是到达时间(TOA)、到达时间差(TDOA)和信号强度测距(RSSI)或者到达角度(AOA)。

TOA(TimeofArrival)：该技术通过测量信号传播时间来测量距离。使用TOA技术最基本的定位系统是GPS，GPS系统需要昂贵、高性能的电子设备来精确同步卫星时钟。因WSN节点硬件尺寸、价格和功耗限制，GPS和其他TOA技术无法广泛应用于WSN。

TDOA(TimeDifferenceOnArrival)：TDOA测距技术被广泛应用于WSN

定位方案中。通过记录两种不同信号(常使用RF和超声波)到达时间差异，基于已知信号传播速度，直接把时间转化为距离。已有多种定位算法使用TDOA实现测距。但该技术受限于超声波传播距离有限(超声波信号通常传播距离仅为20-30英尺，因而网络需要密集部署)和NLOS(Non-Line-Of-Sight)问题对超声波信号的传播影响。虽然已有发现并减轻NLOS影响的技术，但都需要大量计算和通信开销，不适用于低功耗的WSN应用中。

RSSI(ReceivedSignalStrengthIndicator)：已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或是经验的信号传播模型将传播损耗转化为距离，该技术主要使用RF信号。因传感器节点具有无线通信能力，故是一种低功率、廉价的测距方式，RADAR、SpotON等许多项目中使用了该技术。他的主要误差来源是环境影响所造成的信号传播模型的建模复杂性；反射、多径传播、NLOS)、天线增益等问题都会对相同的距离产生显著不同的传播损耗。通常将其看为一种粗糙的测距技术，它可能产生50%的测距误差。 AOA(Angleofarrival)：该技术是估算邻居节点发送信号方向，可通过天线阵列或多个接收器来实现，除定位外，还能提供方向信息，如MIT的TheCricketCompass等项目中都使用AOA技术。

无需测距的算法(range-free)不需要节点自身的测距设备，通过跳数或是其他信息估计自身到选定的信标节点的距离值，由于是估计得到的数值，相对于基于测距的算法获得的距离值误差偏大。

2.6 典型的相对定位算法

2.6.1 1SPA算法

瑞士洛桑联邦工业大学的SrdjanCapkun等人最早针对没有基础设施的移动无线自组

[8]网，提出SPA(self–positioningalgorithm)算法。它以网络中节点密度最大的地方选取

一个参考点作为全局相对坐标系的原点，其余每个节点分别通过测距功能测得邻居节点之间的距离值，实线表示二者距离可测得，虚线表示二者不是邻居节点。每个节点在邻居节点中选取两个点A、B，选取原则是这两个点本身也是邻居节点，并且三个点不在同一直线上。以直线OA作为x轴，以B点在OA上的投影BxB为y轴正方向建立局部相对坐标系。所有的局部坐标系建立完成后，相邻的坐标系通过坐标变换实现坐标统一，最终所有节点都变换形成以选取的参考点为原点的坐标系实现定位。

由于每个节点都要参与多次的坐标变换，计算量和通信开销都非常大。此算法开始是针对无线自组网提出的，不太考虑功耗问题，但是用到无线传感器网络当中，这种通信开销和节点数量呈指数比上升的算法需要根据实际情况进行改进。

2.6.2 聚类SPA算法

RajagopalIyengar等人提出的聚类SPA(clustering-basedself–positioningalgorithm)算法是针对上述SPA算法通信量过大而提出的改进算法。首先通过运行随机的定时器选取网络中的主节点，主节点一跳范围内的其他节点成为它的从节点。每个主节点使用SPA算法中相似的方法建立局部相对坐标系，并计算得到其余从节点的局部坐标。完成第一步之后，相邻的局部坐标系依据ID号由大到小的原则进行坐标变换，最终以ID号最小的主节点为原点建立相对坐标系，从而实现定位。由于算法以节点簇为单位进行坐标变换，计算量和通信量相对SPA算法来说都得到大幅度减少，基本与节点个数呈线性比。该算法由于簇之间变换要求拓扑结构比较规则，通信无障碍，所以在地形复杂，节点之间通信容易产生冲突的环境下，定位效果不是很好，节点覆盖率比较低。

2.7 功耗与代价

相对定位算法由于无需事先布置锚节点，很大程度上节约了硬件成本，受外界信号干扰的影响较小，适合用于对节点硬件成本，算法计算能耗以及节点分布有严格限制的无线传感器网络。本文从通信量、覆盖率和定位精度三个主要的性能指标对现有的几种典型定位算法进行了综合分析，通过图表的形式比较节点密度和节点分布两个方面对算法的影响，阐述了各算法在不同的节点布置环境下性能对比，说明了算法具体的适用范围，并提出了适当的改进方案。目前存在的算法大都需要在节点密度较高的环境下能获得比较理想的定位效果，如何通过节点之间的消息传输和节点协作使得算法在某些节点密度较低的环境中也能实现定位精度和节点覆盖率二者很好结合的问题，将是相对定位算法需要主要关注的方面。 3 两种基本算法的仿真分析

根据是否需要测量实际节点间的距离将定位算法分为基于距离定位和与距离无关的定位算法．基于距离的方法又分为:基于到达时间的测距;基于到达时间差的测距;基于达到角度的测距;基于接收信号强度的测距．距离无关的定位方法分为:质心算法;DV－HOP算法;Amorfous算法;APIT算法.三边测量法是基于距离的基本定位方法，质心算法是距离无关方法的典型代表．为分析这两种定位方法的精度，这里对三边测量法和质心算法这两种基本的定位方法进行了介绍，并进行了定位仿真实验．

8

3.1 三边测量法定位

设未知盲节点（简称盲节点）D（x，y）可以感知三个节点A（xa，ya），B（xb，yb），C（xc，

yc），且未知盲节点到该三个节点的距离分别为da，

db，dc，如图5

所示

A

图1 三角测量法示意图 图2 质心定位算法图示

da根据两点距离计算公式得：dbdc11 求解方程组（1）就可以求得D点的定位坐标(简称定位节点)为2222222(xx)2(yy)xxxyyddacacacacca2(xx)2(yy)222222ybcbcxascybycdcdb

因此，借助参考点A,B,C和距离测量，就可以求得未知盲节点D的位置坐标。 (2)

3.2 质心算法定位

质心算法就是采用未知盲节点所在区域的质心作为估计位置。如图（2）所示，设未知盲节点(x，y)所在的区域内可以感知的参考信标节点为（x1，y1），（x2，y2），......，（xn，yn），其中N为未知盲节点在周边区域内可感知节点总数，r0为未知盲节点通信感知半径且满足 [9]

1x

Ny1

Nxi1Ni1Niy作为未知盲节点的定位坐标。

i

3.3 定位算法的仿真实验

此处分别使用基于测距技术和无需测距技术两种技术进行仿真实验，且分别使用两种代表性算法--三边测量法和三边质心算法进行仿真，计算其精度，并且运用Matlab对节点定位精度仿真，对比两种不同技术算法的精度，确定哪种算法更加精确，为日后实际应用和科研发展提供选择。

3.3 三边测量法仿真

9

在区域

1000米x1000米矩形区域内随机分布1000个位置已知的参考节点，随机分布200个位置未知盲节点。假设每个未知节点任意获取三个参考节点的位置坐标，计算着三点间的距离，然后采用三边测量法进行自身的定位计算。定位结果如图6所示，可见盲节点通过三边测量法计算的定位与盲节点重合很好，表明精度很高。

图6 三边测量法定位结果

图7 三边质心定位算法定位结果

3.4 三边质心定位算法仿真

在区域1000米x1000米矩形区域随机分布1000个位置已知的参考节点，随机分布200个位置未知盲节点。假设每个未知盲节点区用感知范围内的参考节点的位置坐标来进行质心算法定位计算，去感知半径100米，先计算位置节点到所有参考节点的距离，去距离小于100米的所有参考节点，然后采用质心算法进行特定计算。定位结果如图7，课件盲节点通过质心计算的定位与盲节点有很多不重合，表明存在较大误差。

3.5 运用Matlab对节点定位精度仿真

无线传感器网络节点定位算法的优劣主要从及诶单定位精度、网络中参考节点的密度、节点密度、网络规模等几个方面进行评估。此处只针对算法本身所计算出来的节点定位精度

[10-12]进行仿真分析。

应用Matlab仿真软件对三边质心算法与三边测量法的优劣性进行分析比较，仿真过程如下：

1）在大小20x20的平面坐标中随机产生3个点，假设分别为A点（x1，y1），B点（x2，

10

y2），C点（x3，y3）; 2）在三角形

ABC的内部随机产生D点，假设为（x4，y4）;

3)计算AD,BD,CD的距离假设分别为d1，d2，d3；

4）为d1，d2，d3分别加上随机误差（服从-1到+1的均匀分布）后假设为D1，D2，D3；

5）根据A,B,C三点的坐标和D1，D2，D3分别利用三边测量法与改进算法计算未知节点的坐标，假设计算结果分别为（E1，F1）,(E2，F2);

6)分别用2中算法估算出来的坐标值（E1，F1）,(E2，F2)与D点真实值（x4，y4）做距离计算，将计算出来的距离作为误差；

7)重复以上过程100次（仿真100个节点的误差），仿真结果如图8所示

图 8 三边质心定位算法与三边测量法计算误差比较图

4 分析

从三边测量法与质心算法实验可见，基于测距的三边测量定位法定位准确性搞，而与距离无关的质心算法误差大。这是因为基于测距的定位方法是通过感知区域内三个参考节点及其准确的测距，有数学精确求解得到唯一确定的定位坐标。而基于距离无关的质心算法误差大。这是因为基于测距的定位方法是通过感知区域内三个参考节点及其准备的测距，有数学精确求解得到唯一确定的定位坐标。而基于距离无关的质心算法定位是采用感知区域内的参考节点进行计算，一旦区域内感知参考节点确定，则质心也确定了，而区域内感知参考节点确定，则质心也确定了，而区域内的未知节点位置却是不确定的。质心算法正是采用质心代替区域内位置节点的定位坐标，因为误差较大。通过缩小区域，尽管可以提高质心算法的精度，但未知节点在区域内的位置仍然是不定的，因而总是存在误差。

定位具有实际意义，通过这两种基本定位算法，通过仿真实验结果课件基于距离的定位相对于距离无关定位方法精确度更高。这位进一步开展新的定位算法和技术提高了积极的指导意义。

11

参考文献

[1] 陆峰.无线传感器网络定位算法分析与比较[J].科技情报开发与经济，2008，第18卷，第18期；12-20.

[2]陈雄，杜以书，唐国新. 无线传感器网络的研究现状及发展趋势[J].系统仿真技术，2005，第2期；5-12.

[3]高雷，郑相全，张鸿. 无线传感器网络中一种基于三边测量法和质心算法的节点定位算法[J].重庆工学院学报，2009，第23卷，第7期；53-57.

[4] 王福豹, 史 龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报,2005,16(5):857-867.

[5]A.M.Korcteqkae. 关于三边测量法与三角测量法的精度比较问题[J].测绘译丛，1992，第1期；34-36.

[6]陈帅，张水峰，束仁义，郑晓东.两种基本定位算法算法仿真分析[J].通化师范学院学报，2012，第33卷，第2期；73-76.

[7]崔轶东. 三角测量法与三角测量思维[J]. 经济师，2008，第八期；23-25.

[8]范乐昊，邱晓辉，汤一彬. 无线传感器网络中节点的自身定位算法分析[J].电信系统通信，2007，第一期；45-53.

[8]张琳. 基于测距技术的无线传感节点定位技术研究[M].西安工业大学出版社，2011，第1期；25-42.

[9]张政，洪沙，任天娟.无线传感器网络节点定位算法分析[J].贵州大学学报自然科学版，2010，第一期;12-16.

[11] Girod L, Bychovskiy V, Elson J, Estrin D. Locating tiny sensors in time and space: A case study. In: Werner B, ed. Proc. of the 2002 IEEE Int’l Conf. on Computer Design: VLSI in Computers and Processors. Freiburg: IEEE Computer Society, 2002. 214-219.

[12] Harter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc. of the 5th Annual ACM/IEEE Int’l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 59-68.

[13] Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing. In: Proc. of the IEEE/RSJ Int’l Conf. on Intelligent Robots and Systems (IROS 01). Vol.3, Maui: IEEE Robotics and Automation Society, 2001. 1312-1320.

12

致 谢

在此论文撰写过程中，要特别感谢我的指导老师赵良老师的指导与督促，同时感谢她的谅解与包容，由于选题较难，在完成论文的过程中遇到了种种困难，但是在老师的悉心指导下，将这些困难一一克服，最终让我出色我完成了论文的撰写。求学过程是艰苦的，但又是快乐的，只有在不断求新的基础上，我的学习能力才会不断加强。在此我要特别感谢我的同学，在遇到一些阻碍时都乐意帮助我一一解决，让我在苦恼时给我带来欢乐。最后还要感谢我的爸爸妈妈，焉得谖草，言树之背，养育之恩，无以回报，你们含辛茹苦供养我上大学，让我在求学期间没有后顾之忧，终于我学业完满结束，对于你们的爱，你们的恩德，无法言表。同时也感谢学院为我提供良好的做毕业设计的环境。

最后再一次感谢所有在毕业设计中曾经帮助过我的良师益友和同学，以及在设计中被我引用或参考的论著的作者，谢谢你们的帮助。

13