无线传感器网络单元定位算法研究与实现.docx

1、无线传感器网络单元定位算法研究与实现 绪论1.1 选题背景和研究意义微电子、无线通讯与计算机技术的发展，促使低能耗多用途传感器被广泛运用在各个领域。无线传感器网络1(Wireless Sensor Network，WSN)由许多小、价格低的传感器节点构成，它们被撒播在监测范围中，利用无线通讯自组织成为具有多跳的系统。WSN能够感应、获取监测范围内的数据，之后把这些感兴趣的数据传递给监测人员。传感技术的任务是获取数据，通讯技术的任务是传递数据，计算机技术的任务是处理数据。在真实的运用环境中，获取数据会遇到以下难题:不容易布置线路、获取信息的面积大。在传感器网络中，位置信息对传感器网络的监测活动至

2、关重要，事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没有位置信息的监测消息往往毫无意义对于这些问题，传感器节点必须首先知道自身的地理位置信息，这是进一步采取措施和做出决策的基础。定位信息除用做报告事件发生的地点外，还具有下列用途:目标跟踪实时监视目标的行动路线，预测目标的前进轨迹;协助路由，为网络提供命名空间，如直接用节点位置信息进行数据传递的地理路由一协议，避免信息在整个网络中的扩散，并可以实现定向的信息查询；进行网络管理，利用传感器节点传回的位置信息构建网络拓扑图，并实时统计网络覆盖隋况，对节点密度低的区域及时采取必要的措施，实现网络负载均衡以及网络拓扑的自配

3、置，等等。因此在传感器网络中，传感器节点的精确、快速定位对各种应用有着重要的作用。WSN在国防军事、环境监控、灾害预测等多个领域被广泛运用。在WSN中，若有某几个节点被蓄谋攻击致使不能使用，这将不可能使网络整体瘫痪。如果我们认为互联网组建了虚拟世界，使人们的通讯方式发生了变化，则WSN便融合了虚拟世界与现实世界，这无疑使人和自然的交流发生了变化。这会让我们现在的生活发生翻天覆地的变化。一般情况下，我们会认为采用GPS(Global Positioning System)来确定节点的坐标。但在WSN中，并不完全适合使用GPS进行定位，具体理由如下:首先，传感器(sensor)节点2使用电池供电(

4、2节五号电池)，其能量受限，并不能及时更换电池来维持能量。因为GPS消耗能量特别大，所以不适合给每个传感器节点都配置能耗较大的GPS设备。其次，WSN的工作环境特别复杂，不能一定使接收仪器与卫星之间可以无阻碍的进行通讯。在没有阻碍物的情况下，GPS设备才能够正常工作。再次，传感器节点的体积较小，然而GPS设备增大了传感器节点的体积，不符合WSN中传感器节点小的特性。最后，WSN中的传感器节点被大量分布在监测范围内，数量达到了几千乃至上万个。用GPS定位使得成本增大，不符合WSN的价格低廉性。由于监测是一个长期与漫长的过程，一般情况下，监测范围的环境都比较恶劣，监测人员不容易抵达这些区域，故不能

5、及时给传感器节点补充能量。又因传感器节点具有以下特性:能量受限、通讯能力受限、密集且随机分布，故节省能耗和效率高是实现WSN节点定位技术需要考虑的第一因素。考虑到传感器节点在能量、体积、环境、价格等方面的一些要素，可知GPS不完全适用于WSN。这就要求我们必须设计出适合在WSN中使用的节点定位算法。1.2 国内外研究现状国际上比较有代表性和影响力的无线传感网络实用和研发项目有遥控战场传感器系统2（Remote Battlefield Sensor System，简称REMBASS -伦巴斯）、网络中心战2（NCW）及灵巧传感器网络2（SSW）、智能尘2（smart dust）、Intel Mo

6、te、Smart-Its项目、行为习性监控2（Habitat Monitoring）项目等。尤其是今年最新试制成功的低成本美军“狼群”地面无线传感器网络标志着电子战领域战术的最新突破。俄亥俄州正在开发“沙地直线”（A Line in the Sand）无线传感器网络系统。这个系统能够散射电子网（tripwires）到任何地方。民用方面，美日等发达国家在对该技术不断研发的基础上在多领域进行了应用。对于国内的研究现状。清华大学、中国科技大学、浙江大学、华中科技大学、天津大学、南开大学、北京邮电大学、东北大学、西北工业大学、西南交通大学、沈阳理工大学和上海交通大学等单位纷纷开展了有关无线传感器网络方

7、面的基础研究工作。一些企业如中兴通讯公司等单位也加入无线传感器网络研究的行列。但是我国的关于无线传感器网络的研究仍旧处于起步阶段。1.3 研究前景WSN是新出现的传感器网络，它的发展与运用给人们生活与生产中不同领域都产生了有意义的影响。无基本设备支撑的无线自组织网，其具有以下特性:多跳、自组织与可重构。这类网络的拓扑结构与信道环境都会因节点走动而动态变换。它能够为普通领域的运用与国防军事领域的运用迅速搭设通讯环境。未来移动通讯网3不仅能使数据进行传递，而且还要求在无专用通讯基本设备的情况下，应该具备以下特性:自适应能力与生存能力。因此，WSN与自组织网，能够对其发展起到促进作用。小型传感器节点

8、具备感知、计算与通讯能力，在监测范围内撒播的这些传感器节点构成了WSN。任意一个传感器节点至少装一类感知器(声、红外线或磁感应器等)。监测范围内的所有传感器节点之间，都通过特定协议进行传递与获取数据，最终定位并跟踪对象。通讯、嵌入式与传感器这3项技术的逐渐成熟，使得WSN快速发展。这使得学者与专业研究人员高度重视WSN。在国防军事、环境监控、医疗护理等众多领域，WSN都被广泛运用。在WSN中，获取位置是其监测对象的重要任务，知道事件准确发生地是整个监测活动的重要环节。传感器节点一般被随机撒播在监测范围内，例如它们被撒播在监测生态环境、火灾现场等场所，这些传感器节点并不清楚自己的位置，故要求传感

9、器节点一旦被分布，就应该可以快速自定位。除了这些描述，定位技术还具有别的功能:网络管理、改善路由、目标跟踪等。对于网络管理，获取的传感器节点数据被用来构造拓扑结构图，为了及时知道网络的涵盖范围，使得节点不太多的地方可以快速采取相应挽救措施。节点坐标数据还有一个特别功能，就是用来辅助实现路由。在知道任意一个节点与其周边节点的坐标后，网络才可以达到改善路由的目的。优化路由的好处是:改善系统的性能、安全性与节约电量。因此，在WSN的任何一类运用中，准确定位传感器节点起着举足轻重的作用。准确定位是WSN运用的基础，是其支撑技术。可以看出，WSN节点定位技术的运用前景相当好。1.4 论文主要研究内容和结

10、构本研究旨在设计与实现一种高效、鲁棒性4好、代价小的无线传感器网络节点定位算法，使之适应于一些复杂环境下的定位需要。由于传感器网络部署完成之后，我们要面临的首要问题就是无线传感器网络目标节点的定位。所以可知，定位技术是WSN的一项重要支撑技术。本文研究了基于测距和无需测距的定位算法，并总结了这类算法的优劣势。其中重点研究与分析了己有的DV-HOP5算法及其改进和基于多维标度定位算法的定位原理。针对DV-HOP算法固有的一些不足，提出了一种改进方案。对于本论文重点研究的DV-HOP定位算法，重点研究了以下内容：计算出用RSSI测量的距离值与每跳距离和的均值，然后利用该均值与实际距离的差值，得到总

11、距离与平均每跳的距离误差校正值。用MIN-MAX5与加权最小二乘法的混合定位法替换了三边测量法。该算法不仅降低了平均定位误差、提高了节点的定位覆盖率，同时还减少了计算代价。本文的主要内容安排如下:第一章首先简单介绍了论文的选题背景和国内外研究现状，之后，简要说明了此课题的国内外研究现状和存在的问题。最后是介绍了论文的主要研究内容和论文结构。第二章主要介绍无线传感器网络相关背景知识。阐包括无线传感器网络的基本概念及其体系结构；分析了无线传感器网络不同于传统网络的一些自身特点。第三章根据WSN的特点介绍了WSN的体系结构和特征；然后重点研究了基于测距技术的定位算法分析和与距离有关、与距离无关的定位

12、算法分析。 第四章重点对DV-HOP的改进。重点研究了以下内容：计算出用RSSI5测量的距离值与每跳距离和的均值，然后利用该均值与实际距离的差值，得到总距离与平均每跳的距离误差校正值。用MIN-MAX与加权最小二乘法的混合定位法替换了三边测量法。该算法不仅降低了平均定位误差、提高了节点的定位覆盖率，同时还减少了计算代价。同时对DV-Hop算法进行了MATLAB仿真结果分析，得出结论，给出最佳方案。最后是参考文献、致谢、附录。1.5 本章小结本章首先简单介绍了无线传感器网络的起源和研究进展状况，之后，简要分析了节点定位技术对无线传感器网络的意义并详细描述了定位技术的国内外研究趋势和研究热点。最后

13、简要描述了本文的组织结构和内容安排。第2章 无线传感器网络2.1 无线传感器网络的体系结构2.1.1 无线传感器网络结构图2-1表示了无线传感器网络的体系结构。WSN由以下几个部分组成:传感器节点(sensor node)、网关12(或汇聚节点sink node)、互联网或通讯卫星、任务管理节点。图2-1 无线传感器网络体系结构在WSN中，人们通过飞机撒播或手动分布等方式，把许多传感器节点随意撒播在监控区域（sensor field）中或者周边，这些传感器节点自组织组建了网络。传感器节点把感知信息通过除它之外的传感器节点进行传递，在逐跳传递时，其它很多节点也许会处理这些感知信息(比如数据融合等

14、)，感知数据凭借多跳路由的方式抵达汇聚节点。它们最终借助卫星或Internet到管理节点。监测人员通过任务管理节点配置与管理WSN，发布监测任务及获取监测数据。一般情况下，传感器节点是一类很小的嵌入式系统。因为电池给传感器节点提供电量，所以传感器节点的计算、储蓄与通讯能力都不太强。节点的通讯长度较短，通常只与周边节点交换数据，它借助多跳路由来传递这些内容。故从网络用途的角度来考虑，所有传感器节点都具备普通网络节点的2个功能:终端与路由。所有传感器节点不只需要获取与处理信息，还需保存、管理与融合其它节点传输来的信息。它们共同合作来实现一系列功能。与普通节点相比，汇聚节点具有相对强的计算、储蓄与通

15、讯能力。它实现了WSN与外部网络的互连，能够使2个协议栈间的通讯协议相互转变，并且广播管理节点的感知内容，最后监测到的信息被传递给互联网。汇聚节点不仅能是无通讯功能的网关仪器，而且同样能是含多用途的传感器节点。2.1.2 传感器节点结构运用需求不一样，使得传感器节点的结构也不完全一样。但通常情况下，传感器节点都包含以下4个模块:传感器模块、处理器模块、无线通讯模块与能量供应模块。传感器节点结构14的示意图如图2-2所示:图2-2 传感器节点结构传感器模块的作用是，获取监控范围中的数据与转换这些内容。它的类型通常取决于被监控信号的种类。处理器模块的作用是，操作所有的传感器节点，保存与处理自己获取

16、的信息与除它之外的节点传递给它的信息。处理器一般会采用嵌入式CPU。无线通讯模块的作用是，能够使传感器节点与除它之外的传感器节点取得联系(通讯)，并互换操作的数据、获取并发送监测信息。长度短、能耗小的无线通讯仪器构成了无线通讯模块。能量供应模块的作用是，供给传感器节点运行时总共要的电量。在一般情况下，使用特别小的电池为其供应电量。2.2 无线传感器网络的特征2.2.1 无线传感器网络的特点无线传感器网络主要包含以下特征:(1)传感器节点数量大、密度高，用空间位置寻址为了确保网络的生存周期，WSN中可能会有数以千计的传感器节点。因为传感器节点量多且密集，所以网络中任意2个节点间进行一对一通讯一般

17、不会被支持。又因为每个节点不能被唯一识别，故不需要用Internet的IP来寻址。监测人员不关注数据来源于哪一个节点，但它们关注数据所在的具体坐标。因此，数据在传递的过程中，使用空间位置寻址。(2)传感器节点的能源与计算、储蓄、通讯能力都有限传感器节点的能量取决于电池的供应，遇到电池用完的情况，经常换电池是不现实的，故传感器节点的能源有限。传感器节点的计算与储蓄能力不太高，所以说，WSN不适合较复杂的计算，也不适合大量保存信息。WSN的一个重要特征是，如何有效使用能量。(3)无线传感器网络的拓扑结构易变化，它具有自组织能力对于WSN，我们需要考虑传感器节点的节能性，所以这些节点应该能在运行与休

18、眠状态下方便切换。在WSN中，传感器节点可能被损坏，导致它不起任何作用，也可能会增添新的传感器节点，描述的这些情形都会使得WSN的拓扑结构出现改变。若节点移动，则也能引起WSN的拓扑改变。因为WSN的拓扑结构具有易变的特点，所以要求传感器节点必须具备自组织与配置等能力。WSN的自组织能力，可以满足该拓扑结构易变的要求。(4)传感器节点具有数据融合能力在WSN中，中间节点通常会具备特别的能力:它能融合许多传感器节点获取到的同一类型数据，并且能够把这些同类型的数据传递给信息处理总部。数据融合，不仅减少了多余信息，同时也减少了信息传递过程中使用的电量。数据融合使得网络的生存期延长了。(5)无线传感器

19、网络具有可靠性在WSN中，传感器节点也许会被撒播在非常糟糕的环境下，也许会被撒播在人们不容易进入的区域。它也许会在露天完成任务，也许会被无意间损害。因为传感器节点通常被随意撒播(如被飞行器随机撒播在监测范围内)，所以传感器节点必须牢固耐用，可以在不同的糟糕环境中生存。(6)无线传感器网络以数据为中心Internet以IP地址为中心。在WSN中，节点被任意分布，它的编号和位置是无绝对关联的。在WSN的运用中，监测人员在乎事件发生的坐标信息与时间信息，但不在乎它被哪个节点感知到。因此，我们认为WSN以数据为中心。(7)网络的应用相关性因为传感器网络的运用背景有差别，所以它的运用需求也有差别。在WS

20、N中，软硬件环境与网络协议都存在着许多不一样的地方。因此，WSN没有通用的通讯协议。在WSN的运用方面，尽管它们具有许多相同的地方，然而人们却重视它们在实际使用中的区别。WSN技术是专门考虑实际运用而探索的，这是它与普通网络的一个最明显区别。2.2.2 与现有无线网络的区别移动无线自组网 8(Mobile Ad-Hoc Network)是一种对等网络，具备多跳移动、动态组网、无线通讯等特点，含有几十、甚至几百个节点。在一般情况下，总是需要给节点不断提供能源。尽管无线传感器网络与无线自组网有类似的地方，但仍然含有许多不同之处。它们的区别如下:(1)WSN是一种特殊的网络，它具有无线通讯、监控与处

21、理等功能。节点数量可能会达到成千上万个，它们被紧密地部署在监测范围中。(2)节点会因周围环境的变化而发生变化，它的能量也是有限的，即电量有可能被用完。因此，节点较易失效。(3)环境的干预与节点的失效，容易导致网络拓扑结构发生较大的改变。但在一般情形下，大部分传感器节点的位置不会改变。(4)WSN与普通无线网络的最关键区别是:普通无线网，首先考虑如何使带宽的使用率增大、如何使服务的质量变好，其次才重视节省能量的问题。但是，WSN首先需要考虑如何增强能量的利用率。2.3 本章小结本章全面介绍了无线传感器网络的概念、体系结构，并且对无线传感器网络的特征进行了详细的描述。第3章 无线传感器网络定位技术

22、3.1 WSN定位技术分类关于无线传感器网络的定位问题分为两类，一类是无线传感器网络对自身传感器节点的定位9，另一类是无线传感器网络对外部目标的定位9。本文主要讨论前者。获得节点位置最直接的一个直接想法就是利用GPS来实现。但是，在无线传感器网络中使用GPS来获得所有节点的位置受到价格、体积、功耗以及可扩展性等因素限制。因此，本论文的目前主要的研究工作是利用传感器网络中少量已知位置的节点来获得其他未知位置节点的位置信息。3.2 基于测距技术的定位算法分析基于测距技术的定位10需特定的硬件设备来测量节点间的距离或角度信息，然后再使用三边测量、三角测量或最大似然估计定位计算方法来计算节点位置。其常

23、用的测距技术有RSSI，TOA，TDOA和AOA。与距离无关的定位则无需距离或角度信息，或者不用直接测量这些信息，仅根据网络的连通性等信息实现节点的定位。相对于基于测距技术的定位算法而言，距离无关定位在网络密度、通信开销方面比较大，但在能量、可扩张性方面具有较大的优势。距离无关定位算法其定位精度稍差，但定位精度对大多数应用已足够，所以在目前的节点定位算法研究中距离无关定位算法倍受关注。根据具体的定位机制，可以将现有的无线传感器网络定位方法分为两类：基于测距的(Range-based)方法和基于非测距的(Range-free)方法。基于测距的定位机制需要测量未知节点与锚节点之间的距离或者角度信息

24、，然后使用三边测量法、三角测量法或最大似然估计法计算未知节点的位置。而基于非测距的定位机制无需距离或角度信息，或者不用直接测量这些信息，仅根据网络的连通性等信息实现节点的定位。如果未知节点估计出到其它邻居节点的距离并满足节点计算条件，那么就可利用距离来计算出未知节点自身的位置。目前已知的与距离有关的的定位计算方法包括以下三种:三边测量法，三角测量法和最大似然估计法。3.2.1 三边测量定位技术三边测量法9是一种基于几何计算坐标的方法，使用条件是：一个节点到至少三个锚节点的估计距离已知。这个的方法是利用以三个锚节点为中心的圆交点作为未知节点的位置。如图3-1所示。三个锚节点A1、A2、A3的坐标

25、事先知道，它们的坐标依次是、,这三个锚节点到未知节点A的距离依次是。如果未知节点A的坐标是(x，y)，则会有以下公式成立: （3-1）推导公式（3-1），计算出未知节点A的坐标是: （3-2）图3-1 三边测量法的几何意义通过以上分析，看一看出这种定位方法非常简单。但是，由于无线传感器网络节点的硬件和能耗限制，所以节点间测距误差较大，因此可能会出现三个圆无法交于一点的情况。如果这三个圆不能交于一点，该方法就不可行，这时就需要使用最大似然估计定位法来处理这个距离误差。3.2.2 三角测量法三角测量法9可通过以下两种方式来实现：（1）“点在三角形中”的测试即任意选取三个锚节点组成三角形，以测试未知

26、节点是否落在该三角形内。根据测试结果的交集，大致确定未知节点的位置。这种方式前提是已知锚节点数，另外其位置估算的精度会随着测试次数的增加而增加；（2）结合角度测量即通过方向性天线，利用AOA测量的角度值来定位。在二维平面中，利用两个或更多AOA测量值，按照AOA定位算法确定多条方位线(未知节点接收器天线或天线阵列测出锚节点发射电波的入射角，由此构成一根从未知节点到锚节点的径向连线，称为方位线)的交点即可计算出未知节点的估计位置如图3-2所示假定未知节点A的坐标是(x，y)，三个节点A1、A2、A3的坐标事先知道，它们的坐标依次是(xa1，ya1)、(xa2，ya2)、(xa3，ya3)，未知节

27、点A到三个锚节点A1、A2、A3的角度依次是A1AA3，A1AA3，A2AA3。针对节点A1和A3以及A1A2A3，假设弧A1A3在A1A2A3的范围里面，则仅可以得到一个圆。如果圆心的坐标是 C1(xc1，yc1)，半径是d1,则=A1C1A3=(2-2A1AA3)。因此会有下面的公式成立： （3-3）通过公式(3-3)的推导，即可以得到圆心C1的坐标和半径d1。类推可知，A1、A2、A1AA2的圆心坐标是C2(xc2，yc2)、半径是d2，A2、A3、A2AA3的圆心坐标是C3(xc3，yc3)、半径是d3。接下来我们依据三边测量法，通过点A(x，y)、C1(xc1，yc1)、C2(xc2

28、，yc2)、C3(xc3，yc3)计算得到A点的坐标。图3-2 三角测量法的几何意义3.2.3 极大似然估计法极大似然估计法9与三边测量法的思想相似，它的几何意义示意图如图3-3所示。假设有m个节点的坐标事先知道，它们的坐标是(xi，si)(i=l，2，m)，己知节点的个数m必须大于等于3(m3)；ri表示第i个已知节点与未知节点N之间的长度。依据几何平面中任意两点的欧式距离公式，如果未知节点N的坐标是(x，y），则会有以下的方程组成： （3-4）图3-3 极大似然估计法的几何意义把公式（3-4）中的前m-1个方程式依次减去第m个方程式，整理后有了以下的方程式： （3-5）我们把公式（3-5）

29、中的方程组用Ax=d的线性方程式来描述，有利用标准的最小二乘法，计算出未知节点N的坐标是。3.3 与距离有关的定位算法分析3.3.1 基于测距的定位方法这是常用的定位方法。在这种定位机制中需要先得到两个节点之间的距离或者角度信息，具体过程通常分为三个阶段：（1）测距阶段。未知节点首先测量到邻居节点的距离或角度，然后进一步计算到临近锚节点的距离或角度，在计算到临近锚节点的距离时，可以计算未知节点到锚节点的直线距离，也可以用二者之间的跳段距离作为直线距离的近似；（2）定位阶段。未知节点在计算出到达三个或三个以上锚节点的距离或角度后，利用三边测量法、三角测量法或极大似然估计法计算位置节点的坐标；（3

30、）修正阶段。对求得的节点的坐标进行求精，提高定位精度，减少误差。3.3.2 到达时间（TOA）及时间差测距法TOA24技术是通过测量信号传播时间来测量距离。在这种方法中，若电波从锚节点到未知节点的传播时间为t，电波传播速度为c，则锚节点到未知节点的距离为t*c。TOA要求接收信号的锚节点或未知节点知道信号开始传输的时刻，并要求节点有非常精确的时钟。使用TOA技术比较典型的定位系统是GPS。TDOA测距技术在无线传感器网络定位方案中得到了较多的应用。通过记录两种不同信号的到达时间差异，根据已知的两种信号的传播速度，直接把时间差转化为距离。该技术受到超声波传播距离的限制和非视距问题对超声波信号传播

31、的影响，不仅需要精确的时钟记录两种信号的到达时间差异，还需要传感器节点同时具备感知两种不同信号的能力。3.3.3 时间差定位法TDOA24测距是通过计算两种不同无线信号到达未知节点的时间差，再根据两种信号传播速度来计算得到未知节点与锚节点之间的距离。TDOA定位与TOA测距不同，TDOA定位计算两个锚节点信号到达未知节点的时间差，将其转换成到两个锚节点的距离之差，未知节点通过到多组锚节点的距离之差得出自身的位置。在二维平面上的，双曲线的几何意义是到两个定点的距离之差为一个常数的所有点的集合，两个定点称作焦点。因此：得到未TDOA定位在二维平面上的几何意义为知节点与两个锚节点的距离之差，即可知未

32、知节点定位于以两个锚节点为焦点的双曲线方程上，通过测量得到未知节点所属的两个以上双曲线方程时，这些双曲线唯一的交点即为未知节点的位置。由于这种方法不是采用到达的绝对时间来确定节点的位置，降低了对时间同步的要求，但是仍然需要较精确的计时功能，同时由于无线传感器网络具有分布密集和无线通信范围小的特点，这种方法实现起来难度较大。3.4 与距离无关的定位算法分析3.4.1 质心算法质心算法9的中心思想是：未知节点以所有在其通信范围内的锚节点的几何质心作为自己的估计位置。具体过程为：锚节点每隔一段时间向邻居节点广播一个信标信号，信号中包含有锚节点自身的ID和位置信息。当未知节点在一段侦听时间内接收到来自锚节点的信标信号数量超过某一个预设的门限后，该节点认为与此锚节点连通，并将自身位置确定为所有与之连通的锚节点