WSN中2-连通2-支配集构造算法

《WSN中2-连通2-支配集构造算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南昌航空大学硕士学位论文攻读硕士学位期间发表论文情况南昌航空大学硕士学位论文原创性声明本人郑重声明：所呈交的硕士学位论文，是我个人在导师指导下，在南昌航空大学攻读硕士学位期间独立进行研究工作所取得的成果。尽我所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中作了明确地说明并表示了谢意。本声明的法律结果将完全由本人承担。签名：日期：南昌航空大学硕士学位论文使用授权书本论文的研究成果归南昌航空大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解南昌航空大学关于保存、使用学位论文的规定

2、，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权南昌航空大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。（保密的学位论文在解密后适用本授权书）签名：导师签名：日期：58万方数据摘要通过向监测区域内随机投放大量多功能的、低成本的、低功耗的微型传感器节点，各微型传感器之间以无线通信的方式连接并构建出一个多跳自组织网络系统，该网络系统即为我们所熟悉的无线传感器网络(WirelessSen

3、sorNetworks,WSN)。能广泛适用于军事国防、交通运输管理、环境的科学监测、医疗保健、智能家居、空间探索等诸多领域。为有效提高传感器节点间的信息广播效率，又避免泛洪（flooding）算法引起的广播风暴，一般通过在图论中构造连通支配集形成虚拟骨干网来分层路由。由于采用构造连通支配集作为网络虚拟骨干网，使得节点信息传输大部分在连通支配集中进行，导致连通支配集中的节点可能因能量耗尽失效。另外无线传感器网络自身的不稳定性特点决定了节点和链路失效经常发生，因此必须考虑它的容错能力。构造一个容错性好的连通支配集使其尽可能减少网络开销，并在某些支配节点失效

4、或链路失败时仍能正常工作以延长网络生命周期，是一个很重要的研究课题。本文主要借助虚拟骨干网理论，研究无线传感器网络中连通支配集的算法构造，并将研究问题抽象为研究简单无向图中连通支配集问题。如何在简单图中构造最小连通支配集（MinimumCDS，MCDS）已然公认是NP完全问题，一般只能采取求解近似值。本文通过综合研究节点度、节点剩余能量、能量阈值等因素对构造容错连通支配集的影响，提出一种能量均衡的最小2-连通2-支配集的分布式算法（DA-EBM）。首先通过研究影响生命周期的各个因素，主要分析支配节点度与理想支配节点数目之间、节点剩余能量与能量阈值之间的关

5、系，并综合考虑剩余能量和节点度等因素的权值公式作为支配点选取的最佳选取策略。其次，算法DA-EBM主要分为容错连通支配集的构造阶段和冗余优化阶段两部分进行描述，通过尽可能的选取节点度接近理想支配度以及节点能量高于阈值的节点作为支配点，进一步优化冗余从而得到能量均衡的最小2-连通2-支配集。通过算法仿真实验及相关性能分析表明，DA-EBM算法综合考虑剩余能量和节点度等因素，采用权值公式所构造的容错连通支配集，不仅能有效节省节点能耗，而且能更好地均衡整个网络，减少整个网络的通信开销，从而达到有效延长网络生命周期的目的。关键词：无线传感器网络；能量均衡；分布式

6、算法；2-连通2-支配集I万方数据AbstractOntheconditionthatagreatamountoftinysensornodesofmulti-function,lowcost,lowpowerconsumptionaresetintomonitoringarea,andthesemicrosensorslinkeachotherbywirelessandbuildupamultiplehopsself-organizingnetworksystem.Thisnetworksystemisthewell-knownWirelessSens

7、orNetwork(WSN).WSNcanbeuniversallyusedinmilitaryaffairs,nationaldefense,environmentalmonitoring,healthcare,smarthome,andspaceexplorationandsoon.Toeffectivelyboosttheefficiencyofbroadcastinformationbetweenthesensornodesandavoidfloodingbroadcaststormcausedbyflooding,theconnecteddom

8、inatingsetsingraphtheoryusuallywillworka