节能是无线传感器网络研究的核心问题。传感器随机分布在恶劣环境中,能量由电池提供,电池不能够随意更换。但是长距离通讯中能量消耗以距离指数形式增长,因此放置功能强大的中继器成为了减少能量损耗的重要方法。本文主要研究在不同类型的无线传感器网络中放置最少数目的中继器达到一定的覆盖和连通要求。首先从图与网络及组合优化的基本理论知识入手,为后续章节作铺垫。第2章阐述无线传感器网络相关知识背景和研究进展,主要针对重要文献,介绍常用的数学模型和典型方法、算法,并对其优缺点进行比较、分析。第3章至第5章为本文重点内容,这里讨论的问题均为NP-hard问题,故针对每个问题设计了相应的近似算法。第3章首先讨论含有基站的单层无线传感器网络放置问题,根据传感器和中继器传输半径的不同情况,分别设计了性能比为3和7的近似算法,并且对于后者,给出了算法的下界估计。继而在双层无线传感器网络中引入基站,设计了性能比为5 +ε的近似算法,为第4章的研究奠定基础。传感器节点很容易被破坏,在任何情况下都可能由于能量损耗、环境侵蚀或是受到恶意攻击而失效,因此有关容错性的设计至关重要。第4章分别研究了含有基站的单层和双层无线传感器网络的容错性。对于单层无线传感器网络,研究k -连通问题;对于双层无线传感器网络,首先对双覆盖双连通问题设计近似算法,并将其容错性推广到k -覆盖2-连通,给出算法及性能比。随着定位系统的日益发展,二维空间的研究渐渐不能够满足人们的需求。第5章中研究三维无线传感器网络的中继器放置问题,主要针对双层无线传感器网络上的单覆盖单连通和容错性问题,根据算法因子的取值不同,设计相应的算法,给出常数性能比。因此拓宽了无线传感器网络的研究及应用领域。最后在第6章中对本文进行总结与展望,并指出有关无线传感器网络放置问题中的一些有待继续研究的问题。