超图理论在无线传感器网络中的应用

《超图理论在无线传感器网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京邮电大学硕士研究生学位论文摘要摘要无线传感器网络是由随机分布的集成有传感器、数据处理单元和通信模块等微小节点通过自组织方式构成的网络。由于传感器大都采用电池供电，能量有限，由于节点众多更换电池不现实。因此，如何提高能源效率以实现有效延长网络生存周期是传感器网络的研究重点。LEACH算法就是针对于无线传感器网络而提出的一种典型的分簇算法。该算法可以有效地解决传感器节点能量限制的问题，有效地延长整个网络的生命周期。其后的很多算法如LEACHC算法、HEED算法和PEGASIS算法等都是由LEACH算法改进而来。上述算法都是基于图论理论通过构建最小生成树来实现有效路由，构建生成树需要大量的控制

2、消息，并且对已构建的生成树需要实时维护，以保证树图的连通。这样大量的构建和维护生成树信息都将过多地占用网络带宽和节点能量，不利于提高网络性能。而采用超图理论将大规模、高连通度的传感器网络拓扑结构抽象为超图模型，可以有效解决这一问题。据此，本文引入超图理论，提出了一种基于超图理论的预分簇最小生成超树路由算法(PCMSHT算法)。该算法通过预先均匀分簇，避免了传统算法中频繁建簇引起能量不断损耗的问题，以及分簇不均匀引起的各节点耗能差异过大而导致部分节点过早死亡的问题，而且簇首选取简单，通过引入剩余能量参数，使簇首选取更具合理性。最后通过超边归并操作，构建最小生成超树实现路由，有效减少控制信息。◆

3、乇最后经过仿真比较，证实了PCMSHT算法可以有效地节省网络能量，延长了网络生一命周期，在一定程度上解决了LEACH算法能量利用率低的问题，达到了改进的目的。关键词：分簇算法，能量，簇首，簇域，超图模型◆’，t．舅南京邮电大学硕士研究生学位论文ABSTRACTWirelesssdlsornetworkisconstitutedbythewayofself-organizing，composingofmanyrandomdistributedtinynodesthatintegratedbysensors，dataprocessingunitsandcommunicationmodules．A

4、sthesensorsaremostlybattery-powered，energyislimited，andthenodesnumberisSOlargethatreplaceallthebatteriesisnotrealistic．Therefore，howtoimproveenergyefficiencyinordertoachievetheeffectiveextensionofthenetworklifecycleisthefocusofthestudyaboutsensornetworks．LEACHalgorithmisatypicalhierarchicalroutinga

5、lgorithmthatproposedforwirelesssensornetworks．111ealgorithmcflnsolvethesensornodes’energy-constrainedproblemefficiently,andextendthelifecycleoftheentirenetworksignificantly．Manyfollowingalgorithms，suchasLEACH—Calgorithm，HEEDalgorithmandPEGASISalgorithmere．areallresultingfromLEACHalgorithm．111ealgor

6、ithmsabovearebasedongraphtheorybyconstructingaminimumspanningtreetoachieveefficientrouting,constructspanningtreewillneedtobuildalargenumberofcontrolmessages，anditneedareal-timemaimcnanceforthespanningtreethathasbeenconstructed，toensuretheconnectivityofthetree．Suchalargebuildandmaintainthespanningtr

7、eeinformationwilltakeuptoomuchnetworkbandwidthandnodeenergy,itisnotconducivetoimprovingnetworkperformance．Thehyper-graphtheoryCanresolvethisissueeffectivelybyabstractingthelarge—scale，‘high-connectivityofth