论文部分内容阅读
通过向监测区域内随机投放大量多功能的、低成本的、低功耗的微型传感器节点,各微型传感器之间以无线通信的方式连接并构建出一个多跳自组织网络系统,该网络系统即为我们所熟悉的无线传感器网络(Wireless Sensor Networks,WSN)。能广泛适用于军事国防、交通运输管理、环境的科学监测、医疗保健、智能家居、空间探索等诸多领域。为有效提高传感器节点间的信息广播效率,又避免泛洪(flooding)算法引起的广播风暴,一般通过在图论中构造连通支配集形成虚拟骨干网来分层路由。由于采用构造连通支配集作为网络虚拟骨干网,使得节点信息传输大部分在连通支配集中进行,导致连通支配集中的节点可能因能量耗尽失效。另外无线传感器网络自身的不稳定性特点决定了节点和链路失效经常发生,因此必须考虑它的容错能力。构造一个容错性好的连通支配集使其尽可能减少网络开销,并在某些支配节点失效或链路失败时仍能正常工作以延长网络生命周期,是一个很重要的研究课题。本文主要借助虚拟骨干网理论,研究无线传感器网络中连通支配集的算法构造,并将研究问题抽象为研究简单无向图中连通支配集问题。如何在简单图中构造最小连通支配集(Minimum CDS,MCDS)已然公认是NP完全问题,一般只能采取求解近似值。本文通过综合研究节点度、节点剩余能量、能量阈值等因素对构造容错连通支配集的影响,提出一种能量均衡的最小2-连通2-支配集的分布式算法(DA-EBM)。首先通过研究影响生命周期的各个因素,主要分析支配节点度与理想支配节点数目之间、节点剩余能量与能量阈值之间的关系,并综合考虑剩余能量和节点度等因素的权值公式作为支配点选取的最佳选取策略。其次,算法DA-EBM主要分为容错连通支配集的构造阶段和冗余优化阶段两部分进行描述,通过尽可能的选取节点度接近理想支配度以及节点能量高于阈值的节点作为支配点,进一步优化冗余从而得到能量均衡的最小2-连通2-支配集。通过算法仿真实验及相关性能分析表明,DA-EBM算法综合考虑剩余能量和节点度等因素,采用权值公式所构造的容错连通支配集,不仅能有效节省节点能耗,而且能更好地均衡整个网络,减少整个网络的通信开销,从而达到有效延长网络生命周期的目的。