无线传感器网络是由多个节点组成的面向任务的无线自组织网络。它综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等，通过卫星传感器对目标信息进行实时监测，对信息进行处理，从而将信息传递给远程监控中心。无线传感器网络具有感知、计算和通信能力。大量的无线传感器节点分布在需要监测的区域，监测特定的信息、物理参量等。但是无线传感器节点往往分布在恶劣的环境中，传感器节点很容易损坏，且传感器网络是由电池供电的，电池的续航能力较小。在许多应用领域中，常常无法更换电池或对电池充电，当传感器节点电能用完，该节点就失去了作用。因此在对进行无线传感器网络设计时，能耗问题是我们关注的一大问题。通过向无线传感器网络中放置功能更加强大的中继器也成为了减少网络能耗延长网络使用寿命的的重要策略。本文的主要研究工作集中在双层无线传感器网络的中继器放置问题的一类特殊问题。由于中继器的成本相对较高，所以我们希望通过放置数目最少的中继器以实现的网络的连通性和覆盖性。本文所讨论的问题都是NP问题，所以针对的相应的问题的设计的算法均是近似算法。本文结构如下：第1章绪论介绍了本文有关图论与网络的基本知识、组合优化问题中的有关定义、算法的基本内容，为后面的章节做铺垫。第2章概述了无线传感器网络中放置问题的发展历史、研究现状及意义,分别介绍了单层无线传感器网络模型、双层无线传感器网络模型和混合型无线传感器网络模型。对于其中的某些文献，给出了单层、双层、混合型无线传感器网络的现有算法以及算法的性能比。本章对这些同类型问题的不同算法的结果进行了比较，并分析了这些算法的优缺点。第3章为本文的重要章节，由于传感器节点容易损坏，所以容错性研究在无线传感器网络的研究领域至关重要。本章首先研究了二维平面中含有基站的双层无线传感器网络放置问题。根据特定的中继器与传感器传输半径关系以及不同的算法分区因子，针对k-覆盖2连通问题分别设计了性能比为常数的近似算法，并给出算法的界估计。在此基础上，加以推广，设计了k-覆盖k-连通问题的近似算法，并给出算法的性能比分析。第4章在第三章的基础上，研究了三维空间上的无线传感器网络的中继器放置问题。随着研究的深入和实际应用的需求，三维无线传感器网络的需求也逐渐增大。本章将无线传感器网络的研究从二维平面延伸到三维空间中，对于三维空间中的无线传感器网络的k-覆盖2连通问题，设计算法，给出性能比及分析，紧接着将其容错性研究推广到k-覆盖k-连通问题，并设计相应的算法，给出常数性能比。第5章对全本文进行归纳与总结，指出无线传感器网络中未来有待解决的问题，并对相关工作进行了展望。