[毕业设计 论文 精品]无线传感器网络基于移动信标优化路径的定位算法研究

a1a3I学位论文(工学)基于移动信标优化路径的定位算法研究二零一零年五月a4a0a2a5II摘要无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。无线传感器网络应用的大多数领域,如：目标监测与跟踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需要研究更为有效的定位算法，降低定位成本，提高定位精度。针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法进行了研究，该定位算法能够实现节点的高效率定位。文章在DV-Hop定位算法中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本文的主要完成的工作有：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按g20056定的路径移动并g993g7041的g5203g6785g14270g5061的位置信息，g5430成多个g15406g6323信标，研究g5191g3355g17351距g12175的g2164g7447算法和信标节点的动态选择算法，降低定位的成本和g5079网的g3809g7446度，提高节点定位的精度和效率。3、g13479g2524基于移动信标改进的DV-Hop定位算法，提出了g19766g2533无线传感器网络的移动信标的路径g16280g2022g7053法，g6238g3282论引入信标移动路径g16280g2022，获取针对g6164g3800网络g17842g17902g10378况的优化信标移动路径，提高算法的定位精度，g1955g4581算法定位g17819g12255的g17902信g5332g19156，提高算法的效率。g7380g2530在OMNeT+g1235g11507g10627g3671g991，g1235g11507基于移动信标的定位算法，g5326g12447g2265g6336移动g7246能节点和g7234g17902节点的g1235g11507g8181g3423，g17902g17819定位g17819g12255的g17902信和数g6466g3800g10714计算g7422知节点的位置，g1235g11507g15932g7138，基于移动信标优化路径的定位算法g7094改g2904了定位的精度，g2460g1955g4581了定位算法的g17902信g5332g19156，提高无线传感器网络节点定位效率。关键词：无线传感器网络g727移动信标g727优化路径g727OMNeT+g727g7246能节点a8a6a7a9a10a8a11a9IIIABSTRACTWirelesssensornodelocalizationisoneofthekeytechnologiesforwirelesssensornetworks.Itsthefoundationofmostwirelesssensornetworkapplications,suchas:targetsurveillanceandtracking,routingandotherlocationinformationacquiring,alloftheseneedtoknowthelocationinformationofthenodes.Soweneedmoreeffectivelocalizationalgorithmtoreducethecostandincreasetheprecision.Inresponse,thepaperresearchthenodeslocalizationalgorithmforwirelesssensornetworkbaseonmobilebeaconwithoptimalpath.Thisalgorithmcanachievehighefficiencyofpositioningnodes.WeintroducedmobilebeaconnodeintoDV-Hoplocalizationalgorithm,andstudythedynamicbeaconnodeselectionalgorithmandmovingpathoptimalalgorithm.Thesemajorworksare:1.Summarizescommonrange-freelocalizationalgorithmandthealgorithmsbaseonbeacon,studythepositioningmechanismoflocalizationalgorithmsbaseonbeacon.2.ImprovingDV-Hoplocalizationalgorithmbasedonmobilebeacon,thealgorithmuseamobilebeaconnodetomoveinthenetworkaccordingtoapredeterminedpathandbroadcastitslocationinformationthatcreatevirtualbeacons.Westudytheweightedaveragehopdistancealgorithmandthedynamicbeaconnodeselectionalgorithmtoreducelocalizationcostsandcomplexityofdistributionnetworksandimproveaccuracyandefficiencyofnodelocalization.3.CombinedwiththeimprovedDV-Hoplocalizationalgorithmbasedonmobilebeacon,weproposedmobilebeaconpathplanningmethodforwirelesssensornetworks.Graphtheoryisintroducedintothemobilepathplanning;byacquiringconnectivityconditionsofthenetworkweoptimizethepathofmobilebeacon.Thesemakeincreaseofpositioningaccuracyofpositioningalgorithmandreducecommunicationcosts,improveefficiencyofthealgorithm.Finally,wesimulatemobilebeaconbaselocalizationalgorithminOMNeT+a12a13a14a15IVsimulationenvironmentbymodelingmobileintelligentnodesandordinarynodesinthenetwork.Thenetworkcomputestheunknownnodeslocationthroughthepositioningprocessofcommunicationanddataprocessing.Thesimulationresultsshowthatthealgorithmbaseonmobilebeaconwithoptimalpathnotonlyimprovesthepositioningaccuracybutalsoreducethecommunicationoverheadoflocatingm,theseimprovetheefficiencyofwirelesssensornodeslocalization.Keywords:WSNg727Mobileanchorg727Optimalpathg727OMNeT+g727Smartnodea16a17V目录摘g3要.IIABSTRACT.III目g3录.VCONTENTS.VII第一章g3绪g3论.11.1本论文的研究g13984g7235及g5859g10研究g13984g7235与g5859g10g16850g20076来g9316.31.2g3281g1881g3818研究现g10378.31.3本论文的主要研究g1881g4493与g13479g7512.5第二章g3传感器网络常用节点定位算法相关研究.72.1无线传感器网络基于信标节点的定位算法.72.1.1g11468关工作.72.1.2基于信标定位算法的优点.92.2无线传感器网络常用的定位g7053g5347的实现.102.2.1g7509大g1296g9994g1284计法.102.2.2g989g17805测g18339定位法.112.2.3g989g16294测g18339定位法.122.3常用的节点定位算法.132.3.1常用的Range-base节点定位算法.132.3.2常用的Range-free节点定位算法.162.4本章g4579g13479.18第三章g3基于移动信标的节点定位算法.193.1无线传感器网络基于移动信标改进的DV-Hop定位算法.193.1.1g3DV-Hop定位算法.203.1.2移动信标节点定位算法.23a18a19a20a21VI3.1.3g1235g11507分析.263.2基于移动信标动态选择改进DV-Hop定位算法.283.2.1DV-Hop定位算法g5191g3355g17351距g12175计算g16835g5058来g9316分析.293.2.2基于移动信标动态选择的改进g3423DV-Hop定位算法g17819g12255.313.2.3g1235g11507分析.343.3本章g4579g13479.35第四章g3无线传感器网络移动信标的路径优化.364.1无线传感器网络移动信标的移动g8181g3423分析.364.1.1g3g19555机移动RWP(RandomWayPoint)g8181g3423.364.1.2高g7043g20544g4584g2499g3839移动Gauss-Markovg8181g3423.374.1.3g15758线移动g8181g3423.384.2g19766g2533无线传感器网络节点定位的移动信标的路径优化.384.2.1基于g3282论的信标移动路径g16280g2022g7053法.394.2.2g19766g2533传感器网络的移动信标路径g16280g2022的g1235g11507实现.404.3本章g4579g13479.42第五章g3基于移动信标优化路径定位算法的仿真实现.435.1g1235g11507实g20576工g1867和实g20576g7053法g12628g17860.435.1.1OMNeT+g1235g11507实g20576g5191g2500g1183g13473.435.1.2定位算法g5627能g16792g1227g6363标及分析g7053法.445.2基于移动信标的传感器网络定位算法的g16786计.455.2.1无线传感器网络g1235g11507g12255g5219g8181g3423及g12255g5219g16786计.465.2.2定位g17819g12255g1235g11507g12255g5219g16786计.515.3基于移动信标优化路径的定位算法g5627能分析.525.4本章g4579g13479.55结论与展望.56参g3考g3文g3献.57攻读学位期间发表的学术论文.60攻读学位期间参加的科研项目.61独创性声明.62致g3g3谢.63a22a23a24a25a26a24a25a27VIICONTENTSABSTRACT(Chinese).IIABSTRACT(English).IIICONTENTS(Chinese).VCONTENTS(English).VIIChapter1Introduction.11.1ResearchBackgroundandMeaningofThisSubject.11.1.1ResearchBackgroundandMeaning.11.1.2SourceofThisSubject.31.2DomesticandForeignResearchStatus.31.3MainContentandStructureofThisSubject.5Chapter2CommonNodesLocalizationforSensorNetwork.72.1LocalizationAlgorithmBaseonBeacon.72.1.1Realativework.72.1.2TheAdvantageofLocalizationAlgorithmBaseonBeacon.92.2ImplementofCommonLocalizationWays.102.2.1Maximumlikelihoodestimation.102.2.2TrilaterationMethodLocalization.112.2.3TriangulationMethodLocalization.122.3CommonNodesLocalizationAlgorithm.132.3.1CommonRange-baseNodesLocalizationAlgorithm.132.3.2CommonRange-freeNodesLocalizationAlgorithm.162.4SummaryofThisChapter.18Chapter3LocalizationAlgorithmbasedonMobileBeacon.193.1ImprovingDV-HopAlgorithmbaseonMobileBeacon.193.1.1DV-HopLocalizationAlgorithm.203.1.2NodesLocalizationAlgorithmbaseonMobileBeacon.233.1.3SimulationResult.263.2ImprovingDV-HopAlgorithmbaseonMobileBeaconDynamicSelection.283.2.1AnalysistheErrorResourceofDV-HopAveragerHopDistance.293.2.2TheProcessoftheImprovingLocalizationAlgorithm.313.2.3SimulationResult.343.3SummaryofThisChapter.35a28a29a30a31VIIIChapter4MobileBeaconMovingPathOptimization.364.1AnalysistheMovingModelofMobileBeacon.364.1.1RWP(RandomWayPoint)MovingModel.364.1.2Gauss-MarkovMovingModel.374.1.3SpireMovingModel.384.2MobileBeaconMovingPathOptimizationforWSNs.384.2.1MobileBeaconPathPlanningbaseonGraphTheory.394.2.2SimulationoftheMobileBeaconPathPlanning.404.3SummaryofThisChapter.42Chapter5SimulationofLocalzaitionAlgorithmbaseonMobileBeacon.435.1IntroductionofSimulationToolsandEnvironment.435.1.1IntroductionofOMNeT+.435.1.2LocalizationAlgorithmPerformanceEvaluationandAnalysis.445.2LocalizationAlgorithmDesignbaseonMobileBeacon.455.2.1ProgrammingandModelingLocalizationAlgorithm.465.2.2ProgrammingtheProcessoftheLocalizationAlgorithm.515.3PerformanceEvaluationandAnalysisoftheLocalizationAlgrithmbaseonOptimizePath.525.4SummaryofThisChapter.55ConclusionandProspect.56References.57PublishedPapers.60ParticipantProjects.61OriginalCreativeStatement.62Acknowledgements.63a32a33a34a35a301第一章绪论1.1本论文的研究背景及意义1.1.1研究背景与意义无线传感器网络g13520g2524了传感器、g4896入g5347计算、分g5079g5347信息g3800g10714和无线g17902信等技术，由g16780多g11468g2528g6122g993g2528g12879g3423传感器节点g17902g17819无线g17902信实现g14270g13464g13467，g5430成分g5079g5347g14270g8847网络。g4439g6183g11784了传g13491的点对点的数g6466信息g1144g1126g7053g5347，g5114来了一种g1852g7044的信息获取和g3800g10714g8181g53471。无线传感器网络(WirelessSensorNetworks，WSN)是由部署在监测区g1881大g18339的廉g1227微g3423传感器节点g13464成，g17902g17819无线g17902信g7053g5347g5430成的一个多g17351的g14270g13464g13467的网络系g13491，其目的是协作地感知、采集和g3800g10714网络覆盖区域g1881感知对象的信息，并传送给观察者2。传感器网络节点在部署时往往是g993g2499控制的，比如在大g3423的无线传感器网络应用中，g17902常将节点撒g6785在很g5203的区域里，网络中大部分的节点的位置是g7422知的，事先g993能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才g2499能获取到网络中事件的发生位置和信息来g9316位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，g993知道节点位置而感知的数g6466是没有g5859g1053的。只有在传感器节点g14270身正确定位g2530，才能确定传感器节点监测到的事件及信息发生的g1867体位置3。节点必须g7138确g14270身位置才能详细说g7138“在什么位置g6122区域发生了特定事件”，实现对g3818部目标的定位和追踪。此g3818，在g16786计路由协议时利用节点位置信息还g2499以提高路由效率，为网络提供命名空间，g2533网络部署者报告网络的覆盖质g18339，实现网络的负载g3355衡以及网络拓扑的g14270配置4。因此，节点的定位问g20076已经成为无线传感器网络的一个重要的研究g7053g2533。传感器节点g14270身定位就是一种g17902g17819g1284计至邻居节点的距g12175g6122邻居数目，利用节点间的信息g1144换来确定各节点g14270身位置的机制。在传感器网络中，节点能够g14270主确定位置被认为是其基本能力和系g13491的基本服务之一。对于WSN来说，人工a36a37a38a392部署g6122为g6164有网络节点配置GPS装置都会受到成本、功耗、拓展g5627等问g20076的限制，因此，寻求WSNg14270身定位机制成为g16780多研究机g7512和学者共g2528探讨的问g200764。无线传感器网络中，根g6466定位g17819g12255中是否实际测g18339节点间的距g12175，g6238定位机制分为：基于测距的(range-based)定位和距g12175无关的(range-free)定位g7053法5。前者需要测g18339g11468邻节点间的绝对距g12175g6122g7053位，g9994g2530利用该实际距g12175来确定g7422知目标节点位置g727g2530者则仅利用节点间距g12175关联关系计算目标节点位置。Range-based算法g17902g17819测g18339g11468邻节点间的实际距g12175g6122g7053位进行定位，测g18339距g12175的g1867体的g7053法有TimeofArrival(TOA)6，TimeDifferenceofArrival(TDOA)7，RadioSignalStrength(RSSI)8和AngleofArrival(AOA)9等。Range-based算法能够实现精确定位，但由于需要在节点中g2164入GPSg6122其g4439附g2164的测距的硬件g16786备，在实际应用中g6164需的成本较高。而Range-free定位算法由于降低了对节点硬件的要求，引起了更多的关注，典g3423算法有DV-Hop10算法,基于RSSI的DV-Hop11算法,基于g17842g17902g5627的定位算法12等。目前基于距g12175的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的g5079置和密度要求高，如g989g17805、多g17805测g18339定位、基于g16294度测g18339定位等算法，都需要移动节点至g4581获得3个g6122者3个以上信标节点提供的坐标和距g1217513。另一种思想则是使信标g6122者信标运动起来，g17902g17819g5114有GPS的已知位置的移动信标按某一g16280g2022g3921的路径g6122运动g8181g3423g17953g2394g7422知节点的区域，并发送定位信g2507，其g4439节点获取这g1135信g2507来进行定位计算。动态算法的研究是g7380g17829g1864起的一个g9921点，g10714论还g993完g2904，有g2047于静态算法g6164g9053及的都是g3278定节点，其主要是讨论对传感网中移动节点定位的g7053法14，g2265g6336g5465测节点的运动和信标节点的运动。g5415g9994g1186g10714论上g16774，完g1852g2499以g1523g18504静态已有的成g10099算法，计算出特定时g2063的节点位置，但因为节点的运动，对定位算法的实时g5627要求较高，g17902常的改进g7053法是g2164入对节点运动的g20056测g1284计15，g6122是使定位算法能g14270动g17878应g993g2528节点运动的g7053g5347，g1186而提高对运动节点的定位g1946确g5627。g15441g9994节点的移动g5627使定位g17819g12255g3809g7446化，但是利用节点的移动g5627g2499提高定位精度，g1955g4581定位g1207g1227。在Bergamo等的研究中，网络中有2个g3278定的信标g2533g1852网传送坐标信息，其g1325g3800于运动g10378态的节点根g6466g6521g6922到的信g2507g5390度进行g14270身定位16。g3281g1881g3818学者对定位问g20076进行了大g18339研究，提出了几种比较典g3423的定位算法a40a41a42a43a38317。但这g1135算法g7234g17953g4396在以g991g4628限18：g311g1393g17194特g8542硬件的g6915g6357g727g312需要特g8542的网络拓扑g13479g7512。而在无线传感器网络中引入移动节点，g2499以g3698g5390其功能。如文g1049819g17902g17819将几个g7422知节点移动到网络节点密度g11468对g12244g11107的区域以g5369g15929节点密度度分g5079g993g3355g2260的g993g17287。文g1049820提到利用移动g2454g13783节点和RSSI(g6521g6922信g2507g5390度g6363g12046)g7053法对g7422知节点进行定位，但是在现实g10627g3671中，g9213度、g19568g11873g10301、传g6785g8181g5347等g7477件往往都是g2476化的，使得RSSI技术在实际应用中g1185g9994g4396在g3268g19602。g4600其是节点对能耗，体g12227等要求g1017g7696时，更多的时g1517并g993能应用这种基于测距的定位技术。g1825测距的定位算法g993需要测g18339节点间的距g12175，而是利用距g12175g11702g18339路由、网络g17842g17902情况g6122者GPS定位等思想提出的一种分g5079g5347定位g7053法，无需测距，这无g11109降低了g13464网成本。但由于没有g11468应的硬件测距g6915g6357，定位g4396在一定g12255g5219的g16835g5058，g5415网络中g4396在g19568g11873g10301时，节点间的g8443g8675距g12175会因为g5379g7366路径而g1147生较大的g16835g5058，精度g1075g11468应的降低21。因此如何提高这种g1825测距定位算法的精度g1075成为了一个研究的g9921点g7053g2533。1.1.2课题来源本g16850g20076来g9316于g3281g4490g14270g9994g12197学基g18341g17176g2173g20045目g708g13546g2507：60673132g709g727g5203g1008g11477g14270g9994g12197学基g18341重点g20045目g708g13546g2507：0