无线传感器网络由大量随机分布在恶劣环境中的传感器组成,且能量不可再生。在较长距离的通讯中能量消耗以距离的指数形式增长,因而节能自然而然成为无线传感器网络重点研究的课题。放置功能更为强大的中继器,增强网络的容错性,对网络的拓扑结构进行控制等都是较为重要的降低能量损耗,延长网络寿命的重要策略。本文正是从以上两个方面着手研究节能问题,具体内容如下:第1章介绍与本文相关的图论和组合优化的基本概念和基础理论。第2章对后文研究内容进行综述介绍,阐述关于无线传感器网络容错性及拓扑控制问题的研究现状以及理论成果,并对相关问题做简单比较和分析。第3章重点讨论了含有基站的双层无线传感器网络中的容错性问题。传感器节点很容易被破坏,在任何情况下都可能由于能量损耗、环境侵蚀或是受到恶意攻击而失效,因此有关容错性的设计至关重要。本章首先针对2-覆盖2-连通问题给出了性能比为(10 +ε)的近似算法,其次,对3-覆盖3-连通问题设计相关算法,并最终推广到k -覆盖3-连通。第4章从拓扑控制角度研究节能问题。利用半径可变的连通感应覆盖集合来研究网络寿命问题,即如何给寻找到的半径可变的无线传感器网络传感器集合分配工作时间,使得整个网络的工作时间最长,并且任一传感器最终总能耗值不能超过其能量初始值。利用The Garg-konemann algorithm和原始对偶思想求解相关问题,给出了性能比为r (1 +ε)(1 + 2log hn)(ε> 0)的近似算法,其中r为相连路长,n为整个网络中传感器的个数,h为任一传感器可供选择的传感半径的个数。第5章设计了一个贪婪的启发式算法,通过寻找数目最多的覆盖连通集合,来达到增大网络寿命的目的。其中涉及了线性规划和整数规划问题。第6章对本文研究工作进行总结与归纳,并指出无线传感器网络中的一些有待继续研究的问题。