当前位置:首页 >> 其它课程 >> 毕业论文初稿1

毕业论文初稿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
I

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

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; Three edge centroid algorithm;

II

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

1 概论
1.1 无线传感器网络研究背景及研究意义
无线传感器网络被列为 21 世纪最有影响的 21 项技术和改变世界的 10 大技术之一 。 随着半导体技术,微机电系统、通信技术和计算机技术的飞速发展,在 20 世纪 90 年代末, 美国开发了具有现代意义的无线传感器网络技术(WSN) 。无线传感器网络以其低功耗,低成 本, 以及分布式的优点被一些重要机构预测为讲改变世界的重要新技术之一, 它将在信息感 知领域带来一场变革。 无线传感器网络作为一种新兴的技术出现,它的应用也为我们带来了技术的挑战,而 节点的准确定位就是其中一项重要的支撑技术。 首先, 无线传感器网络中的节点所探测到的 信息必须结合节点自身的位置,才使得这些信息具有现实意义,否者失去节点的位置信息, 节点所探测到的数据将由于不知道具体位置而失去应用的意义。 其次, 节点的准确位置也是 高效的路由选择以及外部目标追踪的基础和必要信息。 因此, 对节点自身的准确定位在无线 传感器网络应用发挥着重要的作用。 无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成,通过无线 通信方式形成的一个多跳自组织网络。 它的目的是协作地感知, 采集并且处理其覆盖领域中 感知其监测目标的信息,并且最终发送给观察者,由于无线传感器网络的远程监控,能在恶 劣的环境或者人为不可达环境中工作的特点,它可以广泛应用于各种领域,比如环境监测, 军事国防,交通管理,医疗卫生等。 对于节点的定位一直比较直接的想法是为每一个节点配备 GPS 定位装备,然而无线传 感器网络由大量的节点组成, 如果使用 GPS 将无疑极大的增加网络成本。 另外 GPS 装备非常 耗电,而无线传感器网络的节点是利用电池供电,电池能量有限并且无法及时充电,客观上 也不允许在每个节点上装备 GPS 装备。 因此, 在设计无线传感器网络的定位算法时必须考虑 到成本,能量有限等特点。无线传感器网络在国内仍处于初期研究阶段,在国外也没有一个 成熟的算法作为标准,因此对于无线传感器网络定位技术仍处于早期的研究阶段。 当前对于无线传感技术的研究仍然处在一个高速发展的阶段,低功耗就是其发展方向 之一, 而低功耗与高性能的结合实现还不完全。 因此, 为了更好的实现无线传感模块的功能, 增加模块的可靠性和使用寿命, 通过对无线传感节点的硬件功耗的分析, 确定无线传感模块 各单元的基本功率消耗,并进行相应比较,确定需重点降耗的单元,在此基础上结合当前对 低功耗无线传感模块的研究, 通过对比分析选择合适的芯片完成对低功耗无线传输模块的自 主设计和制作。 并辅助软件开发人员完成各子模块的驱动编写, 实现低功耗无线传感模块的 整体通信功能。 无线传感网络是一种开创了新应用领域的新兴概念和技术。当前,传感技术、传感网 络已经被认定为最重要的研究之一。 无线传感器网络节点的稳定运行是整个网络可靠性的重 要保障。 低功耗无线传感模块研究具有极其重要的学习和研究价值, 其功能的实现具有极其 重要的理论和现实意义。 首先,现有的众多研究中,将性能和低功耗相结合的较少,有的只考虑低功耗而性能 不高,有的性能高但是功耗太大。本文综合了性能和低功耗的共同需求,经过深入的分析和 对芯片的数据比较,提出了低功耗无线传感模块的硬件设计思路。 其次,增加无线传感模块的应用。无线传感模块应用已非常广泛,除去组成无线传感 网络的应用外,无线传感技术还广泛的应用于环境监测,如车间温湿度、压力等;短距无线 通信等。实现了无线传感模块的低功耗,其对电能的需求就会更小,应用的范围将会进一步 的扩大。
1
[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.在士兵、装备及军火上加装传感器以供识别,分清敌我,防止误打。监控战场上的状态。 通过飞机空投等方式将大量廉价微型的传感器节点散布在预定区域, 通过这些传感器节点实 时监测周围环境的变化, 并将监测到的数据通过卫星信道等方式发回基地, 这样就可以实时 地监控战场上的状态。
2

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

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 方式进行通信,每个节点都可以充当路由器的角色,并且每个节点都具备动态索 定位和恢复连接的能力。观察者是传感器网络的用户,是感知信息的接受和应用者。观察者 可以是人,也可以是计算机或其他设备。一个传感器网络可以有多个观察者。一个观察者也 可以是多个传感器网络的用户。 观察者可以主动地查询或收集传感器网络的感知信息, 也可 以被动地接收传感器网络发布的信息。观察者将对感知信息进行观察、分析、挖掘、制定决 策,或对感知对象采取相应的行动。感知对象是观察者感兴趣的监测目标,也是传感器网络 的感知对象,如坦克、军队、动物、有害气体等。感知对象一般通过表示物理现象、化学现
3

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

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

2.2 无线传感器网络节点的结构
传感器网络系统通常包括传感器节点(sensor) 、汇聚节点(sink node)和管理节点。 大量传感器节点随机部署在监测区域(sensor field)内部或附近,能够通过自组织方式构 成网络。 传感器节点监测的数据沿着其他传感器节点逐跳地进行传输, 在传输过程中监测数 据可能被多个节点处理, 经过多跳后路由到汇聚节点, 最后通过互联网或卫星到达管理节点。 [4] 用户通过管理节点对传感器网络进行配置和管理,发布监测任务以及收集监测数据 。 传感器网络节点的组成和功能包括如下四个基本单元: 传感单元 (由传感器和模数转换 功能模块组成) 、处理单元(由嵌入式系统构成,包括CPU、存储器、嵌入式操作系统等) 、 通信单元(由无线通信模块组成) 、以及电源部分。此外,可以选择的其它功能单元包括: 定位系统、运动系统以及发电装置等。 传感器网络节点一般由数据采集单元、数据处理单元、数据传输单元组成。如图1所示:

定位系统

运动或执行机构

传感器

A/D 转换

处理器单元 存储器

数据传输单元 发送 接收





图 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.因此可以得公式如下:
4

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

2 ?( X 1 ? x) 2 ? (Y1 ? y ) 2 ? r 1 ? 2 2 2 ?( X 2 ? x) ? (Y2 ? y ) ? r2 ? 2 2 2 ( X ? x ) ? ( Y ? y ) ? r 3 3 3 ?
由于现有的测距方法受环境噪声、多径效应和障碍物干扰等影响,测得的距离存在一定 的误差,导致节点定位也产生误差,将会导致三个圆不能相交于一点,在这种情况要用最大 近似法估计节点位置。 2.3.2 三角测量法 在二维空间中,知道了 1 个点到 3 个点或者 3 个以上点的距离,就可以确定该点的位置。 三边测量法的基本原理就是求 3 个已知半径和坐标圆心的圆的交点。 在传感器网络的部署中 大多采用平面部署,属于二维部署的问题,因此可以采用此法。在基于测距的定位算法中,三 边测量法是计算坐标的基本途径。如图 2,所示,三边测量定位法的基本原理就是求 3 个已 知半径和坐标圆心的圆的交点。假设已知 3 个锚节点 A、B、C 的坐标,未知节点 D 的距离分 别为 d1,d2,d3,根据二维空间距离计算公式,联立解方程组就可得到未知节点 D 的坐标。三 边测量法的缺点是 : 若在测距过程中存在误差 , 上述 3 个圆无法交于一点 , 以存在误差的 a1,a2,a3 去解方程时便无法得到正确解。因此,在实际计算坐标时,一般不采用上述解方程 [5] 的方法,而采用极大似然估计或其他方法 .

A a1 a3 D a2 C B

图 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 的位置。

5

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

1

5

2

4

6 3

(a) 锚节点 图 3

(b) 未知节点

2.4 无需测距技术的定位算法分析
2.4.1 质心算法 质心定位算法是一种仅基于网络连通性的室外定位算法,该算法的核心思想是未知节点 以所有在其通信范围内的信标节点的几何质心作为自己的位置坐标估计值。 E r0 A (x,y) C B D

图 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 阶段执行三边测 量定位。
6

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

dik dij
i j p k

图 5

DV-Hop 算法示意图

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

Ci ?

dij ? dik hij ? hik

?

dij ? dik 3? 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 技术。
7

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

无需测距的算法(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 所示 E A a1 a3 D a2 C B 图 1 三角测量法示意图 图 2 质心定位算法图示 B A r0 (x,y) C D

? ( x ? x )2 ? ( y ? y )2 ? d a a a ? ? 2 2 根据两点距离计算公式得: ? ( x ? xb ) ? ( y ? yb ) ? d b ? ( x ? xc ) 2 ? ( y ? yc ) 2 ? d c ? ?
?1

?1?

求 解 方程 组 ( 1)就 可 以求 得 D 点的 定 位坐 标 ( 简称定 位 节点 ) 为

? x ? ? 2( xa ? xc ) 2( ya ? yc ) ? ? xa2 ? xc2 ? ya2 ? yc2 ? dc2 ? da2 ? ? ? ? ? 2( x ? x ) 2( y ? y ) ? ? ? 2 2 2 2 2 2 ? ? y? ? b c b c ? ? 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 ?
3.3 定位算法的仿真实验

?x
i ?1 N i ?1

N

i

?y

作为未知盲节点的定位坐标。

i

此处分别使用基于测距技术和无需测距技术两种技术进行仿真实验,且分别使用两种 代表性算法--三边测量法和三边质心算法进行仿真,计算其精度,并且运用 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


更多相关文档:

毕业论文初稿1

毕业论文初稿1_其它课程_高中教育_教育专区。计算机专业 华中农业大学楚天学院本科毕业论文(设计) 目录 摘要··· 错误!未定义书签。 关键词 ··· 错误!未定义...

毕业论文初稿

毕业论文初稿_文学_高等教育_教育专区。专科毕业论文 浙江大学远程教育学院专科...(三)合同履行中的风险 1、对方违约的合同法律风险。在合同履行时,最无法避免的...

毕业论文初稿

毕业论文初稿_文学_高等教育_教育专区。毕 业论文 (2015 届) 题 目: A Study...1.3 The Development of Public Relations in Intercultural Communication Some ...

毕业论文初稿 (1)

毕业论文初稿 (1)_教育学_高等教育_教育专区。武汉轻工大学毕业设计(论文) 毕业(论文)设计(题目):大型特买网站的购物车子系统开发 姓学 名号 何正义 100511223 ...

毕业论文初稿

毕业论文初稿_文学_高等教育_教育专区。成都理工大学毕业设计(论文) 成都追银族饰品有限公司网络营销策略分析作者姓名: 邹祖强 专业: 市场营销 学号: 201008020415 指导...

毕业论文,初稿1

毕业论文,初稿1_理学_高等教育_教育专区。本科毕业论文(设计) 题目:黄粉虫热休克蛋白 70 基因片段的克隆与序列分析 学生:纪成兴 学院:生命科学学院 入学时间:2010...

毕业论文初稿

毕业论文初稿_工学_高等教育_教育专区。西安理工大学电气工程西安理工大学本科生毕业设计(论文 ) 毕业设计(论文)题目 专班学 业级生 指导教师 2014 年 第 1 页...

毕业论文初稿 1

最新修改毕业论文初稿1 暂无评价 23页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

毕业论文初稿修改1

毕业论文初稿修改1_小学作文_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档毕业论文初稿修改1_小学作文_小学教育_教育专区。福建华南女子职业学院 国际...

毕业论文初稿修改1

毕业论文初稿修改1_教育学_高等教育_教育专区。福建华南女子职业学院 国际经济与贸易专业 2012 届毕业论文 题 目: 浅谈国际货物贸易中的预期违约制度 班姓级: 名...
更多相关标签:
毕业论文初稿 | 毕业论文初稿怎么写 | 毕业论文初稿格式 | 毕业论文初稿范文 | 毕业论文初稿模板 | 本科毕业论文初稿格式 | 毕业论文初稿评语 | 毕业论文初稿是什么 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com