无线传感器网络DV-Hop定位算法的研究.pdf
《无线传感器网络DV-Hop定位算法的研究.pdf》由会员分享，可在线阅读，更多相关《无线传感器网络DV-Hop定位算法的研究.pdf（56页珍藏版）》请在冰点文库上搜索。
太原理工大学硕士学位论文无线传感器网络DV-Hop定位算法的研究姓名：
姜晓荣申请学位级别：
硕士专业：
计算机应用技术指导教师：
白凤娥20100501太原理工大学硕士学位论文I无线传感器网络DV-Hop节点定位算法的研究摘要20世纪90年代以来，随着嵌入式系统、无线通信、分布式信息处理技术及微电子机械系统（MEMS）等技术的快速发展，具有感知、计算和无线网络通信能力的传感器以及由其构成的无线传感器网络（WirelessSensorNetworks，简称WSN）引起了人们的极大关注。
WSN将逻辑上的信息世界与客观上的物理世界融合在一起，改变了人类与自然界的交互方式。
现实生活中人们可以通过无线传感器直接的感知现实的物理世界，从而扩展了人类认识世界的能力，以及促进了网络功能的发展。
布局和覆盖、节点定位、网络通信协议是无线传感器网络研究中的几个基本问题。
其中，节点定位技术是无线传感器网络主要支撑技术之一，对其研究具有重要的意义。
因为它是传感器网络进行目标识别、监控、跟踪等众多应用的前提。
由于传感器节点受成本、能量和体积等因素的限制，且通常工作在人类难以或不宜接近的场合，因此定位技术的基本途径是：
部署少量已知坐标的锚节点，其他未知坐标的节点依据相对位置关系、网络连通性或通过测量与锚节点的距离、角度进行一定的计算得出自身的坐标。
本文对无线传感器网络节点定位技术进行详细介绍和全面分析,并对RSSI、AOA、质心定位算法、APIT、DV-Hop等几种典型定位算法进行分析和比较，重点对距离无关定位算法中的DV-Hop算法进行了研究。
DV-Hop算法通过收集未知节点与锚节点的最小跳数,并使用跳段距离代替实际距离来估算未知节点的位置坐标。
DV-Hop算法作为一种不基于测距的定位算法，太原理工大学硕士学位论文II有它的优势，但是不可避免也有一些不足之处。
本文针对这些不足，对DV-Hop算法进行了改进。
改进后的算法通过限制未知节点接收锚节点跳数的方法分轮次对未知节点进行定位，将先定位的节点上升为锚节点参与未定位节点的定位。
然后用Matlab集成数学工具软件对改进前后两种算法进行仿真。
仿真结果表明，与传统算法相比，改进后的算法在定位精度和覆盖率方面都有很大改善，显著提高了算法的定位性能。
最后，论文对无线传感器网络DV-Hop节点定位算法的研究做了总结与展望。
关键字：
无线传感器网络，节点定位，DV-Hop，定位精度，覆盖率太原理工大学硕士学位论文IIIRESEARCHONDV-HOPALGORITHMFORWIRELESSSENSORNETWORKABSTRACTIn1990s,withtherapiddevelopmentofembeddedsystems,wirelesscommunications,distributedinformationprocessingtechnologyandmicroelectronicmechanicalsystems（MEMS）technologies,thewirelesssensornetwork,whichisconstitutiveofsensorswiththeabilityofsensing,computingandwirelesscommunicating,hasarousedgreatconcern.Deployment，coverage，nodeslocalizationandnetworkcommunicationprotocolareseveralbasicquestionsofresearchonWirelessSensorNetwork.Amongthesequestions,nodeslocalizationisoneofthemainsupportingtechnologies.Thisisbecausemanyapplicationsofwirelesssensornetworksdependonthelocationinformationofsensornodes.Limitedbyvolume,cost,powerandhardtogetclosetotheworkplace,thebasiclocalizationwayistodeployafewanchors,othersensorscomputetheirowncoordinationbyestimatingdistance,angel,locationrelationandnetworkconnectivity.ThethesisprovidesadetailedintroductionandcompleteanalysistothenodelocalizationofWSN.Itanalyzesandcomparessometypicallocalization太原理工大学硕士学位论文IValgorithmsuchasRSSI,AOA,centroidlocationalgorithm,APIT,DV-Hop,andthethesisfocusesontheinvestigationofDV-Hoplocalizationalgorithm.Bycollectingtheminimumnumberofhopsbetweenunknownnodesandanchornodes,DV-Hopalgorithmestimatestheunknownnodespositioncoordinatesusinghopdistanceinsteadofactualdistance.AsaRange-freealgorithm,DV-Hophasadvantages,butinevitablytherearealsosomeshortcomings.BasedonDV-Hopalgorithm，aimprovednodelocalizationalgorithmisdesignedforsolvingtheaboveshortcomings.Improvedalgorithmfinishtheunknownnodelocationaftermultipleroundsbylimitingthenumberofhopsfromanchornodes.Andlocatednodeswillberaisedtoanchornodesinvolvingtheunknownnodeslocation.Then,thetwoalgorithmaretestedwithMatlabplatform.TheexperimentalresultsshowthatthelocationaccuracyandcoverageoftheimprovedalgorithmaresignificantlyimprovedcomparedwiththeDV-Hopalgorithm.Finally,wesumupthisthesisandprospectforfuturework.KEYWORDS:
wirelesssensornetwork,nodelocalization,DV-Hop,locationaccuracy,coverage太原理工大学硕士研究生学位论文声明本人郑重声明：
所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。
除文中已经注明引用的内容外，本论文不包含其他个人或集体己经发表或撰写过的科研成果。
对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。
本声明的法律责任由本人承担。
论文作者签名：
日期：
关于学位论文使用权的说明本人完全了解太原理工大学有关保管、使用学位论文的规定，其中包括：
1学校有权保管、并向有关部门送交学位论文的原件与复印件；2学校可以采用影印、缩印或其它子复制手段复制并保存学位论文；3学校可允许学位论文被查阅或借阅；4学校可以学术交流为目的，复制赠送和交换学位论文；5学校可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。
签名：
日期：
导师签名：
日期：
太原理工大学硕士学位论文7第一章绪论1.1课题背景在无线通信、集成电路、传感器以及微机电系统等技术的飞速发展和日益成熟的基础上，生产大量的微型传感器成为了现实。
这些传感器一般都集成了信息采集、数据处理和无线通信等多种功能，而且成本低、功耗低、功能多。
随着大量微型传感器的生产，研究者对微型传感器构成的无线传感器网络产生了广泛的关注。
在组建网络时无线传感器网络不需要基础设施，它通常使用飞行器将大量传感器节点抛撒到感兴趣的区域，这些节点会自动快速形成一个多跳的自组织无线网络。
传感器节点会利用内置的传感器测量人们感兴趣区域中的热能、声纳、地震波等，为研究者提供他们感兴趣的数据信息，如温度、湿度、光强度、土壤成分、噪声以及运动物体的大小、速度和方向。
这些信息通过网络传送给用户。
目前无线传感器网络在军事、环境监测和预报、健康护理、智能家居、复杂机械等方面都有了广泛的应用1。
随着深入的研究传感器网络，其优越的性能得到了人们的认可和应用，不久的将来传感器网络会应用到人们生活的方方面面。
因传感器网络具有很大的应用价值和科学意义，美国技术评论杂志在2003年2月份评出的对未来世界产生重大深远意义的十大新兴科学技术，将它排在了第一位。
无线传感器也被科学家预测为信息革命的引领者。
2003年8月25日出版的美国商业周刊杂志在其“未来技术专版”中发表文章指出全球未来的四大高科技产业分别是：
效用计算、仿生人体器官、塑料电子学和传感器网络，并且指出他们也将会引发新的产业革命浪潮。
20世纪90年代末期，人们开始了对无线传感器网络这种新兴技术的的研究。
从2000年起，国际上一些关于传感器网络的研究成果被报道出来。
2003年美国自然科学基金委员会为支持传感器网络有关的基础理论的研究，制定了专门的研究计划。
美国国防部和各军事部门也把传感器网络的研究放到了很高的位置，设立了很多的军事传感器网络研究项目。
一些信息巨头公司也开始了对传感器网络方面的研究工作，比如美国英特尔公司、微软公司等。
除了美国以外，其他一些科技发达国家在发现无线传感器网络具有十分重要的价值意义之后，也表现出了很大的兴趣，并开展了积极的研究工作。
而我国在太原理工大学硕士学位论文8传感器网络方面的研究工作处于起步的时期，但是，作为一门新兴的无线传感器网络技术，对其应用研究还处于探索的阶段，距离实际需求的商业产品还有一段的距离要走。
1.2无线传感器网络中的定位技术无线传感器网络是一门新兴的、多学科交叉的技术，它的出现为研究人员提出了很多挑战性的研究课题，本文要研究的定位问题就是一个非常具有挑战性的课题。
对于投入应用的无线传感器网络，一个很重要的问题就是节点的位置信息。
因为仅知道监测数据，而不知道数据来源的节点位置，那些信息就是没有意义的。
譬如，对移动目标的跟踪、恶劣环境的监控等，那些可以确定位置的感知数据的节点对应用来说才是有意义的。
在实际的各种应用中，传感器节点发现一个事件后接着就判定该事件发生来自于何处，然后才能做出相关的决策和采取具体的措施处理事件。
构成无线传感器网络的传感器节点一般被随机撒布在各种监测区域执行各种任务，监测区域包括环境险恶，人类无法或者难以接近的地方，如武器实验现场、战场、火山爆发处等。
造价、大小、重量等因素影响着单个传感器节点的能量承载力一般是不充足的，而且在恶劣的环境条件下补充能量也是很困难的。
由于在实际的应用环境中，人工部署节点时，一开始并不是所有的节点的位置都已知，而且由于成本的原因，也不可能在每个节点上配备比较成熟的全球定位系统。
因为无线传感器网络一个重要特性就是价格低廉，而GPS设备的价格通常昂贵。
这种不现实从其它方面也突显出来，比如无线传感器网络要求低功耗，而GPS接收器耗能很多；GPS定位适合遮挡物较少的旷野，在室内或者高楼大厦较多的大城市，其定位效果不是很理想。
而且传感器网络工作在卫星信号达不到的地方也是有可能的。
因此，必须结合根据无线传感器网络的特点来设计节点定位机制和算法。
现在已经提出很多关于定位的算法。
1.3国内外研究现状在美国先进国防研究项目局（DARPA-DefenseAdvancedResearchProjectsAgency）的一个研究项目中传感器网络诞生了，那是在冷战时期，在海洋中布置了大量的传感器，利用监测到的信息实时掌握敌方潜艇的行动。
但是，在当时的技术条件下，传感器网络的推广和发展是不容易的，只能应用于军方的一些项目。
随着现代微电子机械系统、计太原理工大学硕士学位论文9算机网络技术、无线通信技术、片上系统的发展，传感器网络也开始引起人们的广泛关注，其应用前景也越来越广。
目前在国外已有多家研究机构、大学和公司投入了大量的人力财力进行了这方面的研究，并取得了相应的进展。
美国先进国防研究项目局（DARPA-DefenseAdvancedResearchProjectsAgency）、美国国家航空航天局（NationalAeronauticsandSpaceAdministrationNASA）部门支持有实力的科研单位、常青藤高校进行无线传感器领域的研究，洛杉矶加利福尼亚大学于1993年开始了WINS（WirelessIntegratedNetworkSensors）项目；加利福尼亚大学伯克利分校在美国先进国防研究项目局资助下进行的SmartDust项目，其硬件平台的微型化已经到一个很高的水平。
由SmartDust项目支持下开发的嵌入式数据库管理系统TinyDB和嵌入式操作系统TinyOS进入了实用化的阶段；Crossbow公司开发出的一系列MICA传感器平台开始在民用领域中使用2。
在最近的几年，我国的科研机构和高等院校也开始了对无线传感器的研究，包括理论方面和实际应用方面。
这样的研究机构和高校主要有沈阳市自动化研究所、合肥自动技术研究所、中科院上海研究所、清华大学、西安电子科技大学、浙江大学、上海交大大学、北京邮电大学等。
目前我国对无线传感器网络的无线通信网络技术的研究还不多，研究重点有穿戴式计算、智能教室、上下文感知环境等领域。
无线传感器网络发展到现在，对它研究的历程经历了两个阶段，一是侧重利用微机电系统（Micro-Electro-MechanicalSystems）技术设计小型化的节点设备，其代表性的研究项目有无线集成网络传感器（WINS）和智能微尘（SmartDust）。
二是侧重对无线传感器网络本身问题的研究与关注，目前研究人员对此研究很感兴趣。
不仅传感器网络本身问题，无线传感器网络节点的定位问题，数据融合，软、硬件的设计和制造等也引起了人们的广泛的兴趣。
全球定位系统定位的原理是GPS接收机会收到几个卫星信号，而且这几个信号到达到接收机的时间是不一样的；根据传播时间我们就可以得到接收机到几个卫星的距离，这样就可以大致计算出节点的位置。
在传感器网络还没出现之前，都是利用全球定位系统进行节点定位的。
但是前面已经提到GPS不适合用到无线传感器网络中。
1992年AT&TLaboratoriesCambridge开发出了室内定位系统ActiveBadge，从那时开始，科研人员就对自定位的系统和算法的开发产生越来越浓厚的兴趣。
截止到现在，一些适用于无线传感器网络的定位系统被提了出来。
其中比较有代表性的是MicrosoftS太原理工大学硕士学位论文10RADAR3，ActiveBadge4，SpotON5，AHLoS，Cricket6等。
目前国内对无线传感器网络的定位技术相关的研究还不多，可以借鉴的有下面的一些。
史龙介绍了已经得到广泛应用的六种定位算法，并对它们进行了比较；除此之外还对定位算法和测距技术的局限性进行了分析说明；最后对自身定位问题的研究方向做了展望7。
孙怡宁和马祖长为了提高节点定位的可靠性，依据多个参照节点的冗余坐标信息，提出了一种新的节点定位算法8。
王永才介绍了一种节点自身定位算法，该算法利用电磁波与声波传播时间差进行测距，而且在Mica2系统上完成了该算法的实现9。
前面都是基于静态节点进行研究的，孙学斌则对移动的节点的定位进行了研究，并提出了一种新的算法。
新算法的原理是首先找到一个先前观察到目标的节点，接下来借助该节点相邻节点的信息得到目标的活动路径10。
在无线传感网络中，为了能够对节点自身定位，很多定位系统和算法被提了出来。
可是，这些定位系统和算法都是支持不同的应用或者是解决不同的问题，因此它们在用于定位的网络组成、物理现象、基础设施、能量需求和时空的复杂性等许多方面有所不同，因此还很不完善，有待进一步的研究和探索。
总体而言，现行技术仍然存在着下列一些问题11,12：
（1）节点定位带来的通讯开销比较大；
（2）所有节点完成定位过程所需时间比较长；（3）缺乏更加有效精确的测距方法；（4）大规模无线传感器网络中存在误差累积；（5）目前的研究成果大部分都是基于静态网络的，对移动节点定位研究相对较少。
（6）由于传感器节点的能量限制，怎么折衷算法的复杂度和算法能量的消耗能为一个问题。
1.4课题研究的目的和意义作为一种全新的多学科交叉的技术，有关无线传感器网络的许多挑战性的研究课题摆在了人们的面前，而节点位置的确定即定位就是其中之一。
它具有很重要的研究价值。
定位是大多数应用的基础。
它包括：
节点自身定位和外部目标定位，在本课题中主要研究的是节点自身定位，它是外部目标定位的基础。
无线传感器网络中定位技术的方法是：
在网络中部署少量的锚节点，它们的位置是太原理工大学硕士学位论文11明确的；网络中那些位置不明确的节点，则通过一定的测量机制或算法计算出自身的位置。
可以通过测量得到与坐标信息已知的节点的距离、角度或者是依据与它们的网络连通性或相对位置关系，然后就可以得出未知节点的坐标。
这样做是因无线传感器网络低成本，低能量，小体积的限制；且工作的区域一般是不适宜人们靠近的。
和全球定位系统GPS相比，这样的定位技术可以减少固定的基础设施，从而节约了成本。
DV-Hop算法是由美国RutgersUniversity的DragosNiculescu等人提出的一种不基于测量的定位算法，它是基于跳数的。
它利用了距离矢量路由和GPS定位原理。
该算法比较简单，但只有在各向同性的密集网络中,计算出的平均每跳距离才比较合理。
为了改善在锚节点有限的稀疏网络中DV-Hop算法的定位精度以及提高节点的覆盖率，本课题对DV-Hop算法进行改进，提出了一种通过限制未知节点与锚节点间的跳数将待定位节点分轮次定位并升级为锚节点的IDV-Hop算法。
这样就能在不提高节点硬件成本的情况下既能减小定位误差又能提高节点的覆盖率。
1.5组织结构本文组织如下。
第一章介绍了无线传感器网络及其定位技术的发展背景、国内外研究现状以及本课题的研究意义。
并介绍了本文的主要工作和组织结构。
第二章介绍了无线传感器网络的基本概念、无线传感器网络结构和无线传感器网络的特点和无线传感器网络的一些技术及其性能评价。
在本章的最后介绍了无线传感器网络在实际中的应用情况。
第三章详细介绍了无线传感器网络中节点自身定位技术，并对目前一些典型的定位算法进行分析介绍，指出了它们的优点和不足。
在本章的最后还对其中的几种算法做了对比。
第四章在DV-Hop定位算法的基础上，提出了一种改进的定位算法。
该算法是在阅读了大量的相关参考文献后，借鉴了一些已有的思想提出的，还有待进一步改进。
最后还对DV-Hop算法和改进算法进行了仿真，并对结果进行了比较分析。
第五章对研究课题进行了总结和展望。
太原理工大学硕士学位论文12第二章无线传感器网络简介2.1无线传感器网络的定义当前有关无线传感器网络的定义，常用的是：
无线传感器网络是指由一组按需随机分布的集成有传感器、数据处理单元和通信模块的传感器节点以自组织方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖范围内感知对象的信息，并传送到信息用户。
无线传感器网络综合了传感器技术、现代网络及无线通信技术、计算技术、分布式信息处理技术等，并以其低功耗、低成本、分布式和自组织的特点带来了信息感知的一场变革。
2.2无线传感器网络体系结构传感器网络发展到现在共经历了四代。
其中点对点的传输为第一代传感器网络，它产生的时间是20世纪70年代，第一代传感器网络可以获取简单信息；第二代传感器网络采用传感控制器与串/并接口相联，具有多种信息获取的综合能力：
第三代传感器网络是智能传感器采用现场总线连接传感控制器构成的局域网络，它出现在20世纪90年代后期。
我们现在研究的是第四代传感器网络，它以无线传感器网络为标志。
2.2.1网络结构一个典型的无线传感器网络主要是由五部分组成，它们分别是传感器节点、任务管理节点、网关节点或者说sink节点、因特网或通信卫星等。
在人们指定的监测区域内，传感器节点被随机散布在里面，其中每个节点都具有收集信息数据的功能，这些采集到的数据最终会被传送到Sink节点。
传送的过程是监测数据沿着其它传感器节点逐跳地在网络中进行传输，而且在传输过程中数据可能被其他多个节点处理。
采用同样的方法Sink节点将它收集及处理后的数据发送给其他各节点。
为了实现任务管理节点与网络中所有传感器节点之间的通信，Sink节点直接与因特网或通信卫星相连。
如图2-1所示。
太原理工大学硕士学位论文13图2-1典型传感器网络结构Fig.2-1Thetypicalstructureofsensornetwork在无线传感器网络中，传感器节点是重要的组成部分。
传感器节点可以说是一个微型化的嵌入式系统，它具有有限的处理能力、存储能力、通信能力，它的能量由电池供应。
传感器网络中的节点一般只与紧挨的节点进行通信，因为它们的节点的通信距离较短。
在整个网络中信息数据是通过多跳的方式传输的。
2.2.2无线传感器节点结构特点传感器节点主要由四个基本模块组成8，它们依次是：
数据采集模块，处理模块，传输模块和电源管理模块。
定位模块和编号模块是附加的功能模块。
它们之间的关系如图2-2所示。
数据采集模块负责监测区域内信息的采集和数据转换，是节点从外界感知信息的窗口。
它负责观测目标，采集目标运动的参数信息，完成信息的数字化过程，并将其送入处理模块进行处理。
处理模块是传感器节点的核心，由嵌入式系统构成，包括CPU、存储器、嵌入式操作系统等。
它首先应调节各模块协同工作。
它不仅要完成对感知信息处理，而且在节点太原理工大学硕士学位论文14初始化时应能处理定位信息，控制节点编号过程。
此外，它还必须能通过通信模块与其他节点交互，实现节点间的合作。
传输模块是信息传递的桥梁。
它负责与其它传感器节点进行无线通信，交换控制消息和收发采集数据。
依据通信协议，该模块将数据分段，打包，成帧，最终通过无线信道发送给其他节点。
该模块内应包含适合于传感器网络的媒体接入控制协议，路由协议，以保证数据通信的可靠性，有效性。
电源管理模块是最基本也是非常重要的模块。
它负责对节点电能的使用进行优化。
电源管理模块通过合理安排节点的工作时间，减少了节点对能量可能的浪费，从而使节点能量的利用率得到提高。
有了电源管理模块，就能相对延长节点的工作时间和提高网络的寿命。
在无线传感器网络的应用中，节点在工作时，都需要依据自身和其他节点相对准确的位置信息。
这些节点
升级会员 