无线传感器网络是由基站和大量价格低廉、能量较少的传感器组成的。在无线传感器网络中，传感器主要作用是感知周围的环境，并把收集到的信息传送给基站。传感器节点在恶劣的环境中随机的分布，能量只能由不能随意更换的电池提供。但是能量消耗在长距离通讯中却以距离指数的形式快速增加，所以研究者们提出了在无线传感网络中放置一定数目的中继器的思路，这成为了减少能量损耗的重要方法。其中放置问题的容错性研究是无线传感器网络中非常重要的问题。容错性就是当系统发生一些故障或错误时，仍然能够正常工作的能力。如果某些节点遭到恶意攻击或受到损坏，那么无论在何种类型的无线传感器网络中，整个系统都可能会崩溃，因此容错性研究对于放置问题是至关重要的。本文的主要工作是讨论含有基站的单层和双层无线传感器网络上具有不同条件的中继器放置问题。因为这些问题都是NP-hard，所以本文对每一个问题都设计了一个近似算法并且给出其性能比。本文结构如下：第1章绪论介绍图论及组合优化等基本理论知识，为后续章节作铺垫。第2章介绍无线传感器网络的发展背景、中继器放置问题的相关研究成果以及进展，简单描述了一些重要参考文献中常用的数学模型和典型的算法，并对其优缺点进行比较，以及对相同类型问题不同算法的特点分析。第3章和第4章为本文重点内容。第3章首先讨论含有基站的单层无线传感器网络放置问题，对于2-连通问题，在R=r的情形下给出了性能比为12的近似算法。继而在双层无线传感器网络2-覆盖2-连通问题中引入基站，针对R≥r的情形设计了性能比为在16的近似算法。这两个算法为第4章的研究奠定基础。第4章研究了k-连通问题，对于单层无线传感器网络，研究R r的情形下的k-连通和k-全连通问题；对于双层无线传感器网络，讨论R≥r的情形下的不含基站和含有基站的k-覆盖k-连通问题，并给出算法及性能比。第5章是对论文内容进行的概括与对未来工作的展望，指出了一些有待我们进一步深入研究的无线传感器网络问题。