无线传感器网络是一种特殊的Ad-Hoc网络，是基于数据采集、数据处理、数据传输于一体的复杂系统，它是由大量随机分布的具有无线通信模块、无线处理模块、传感器模块和电源模块的无线传感器节点组成。单个传感器节点可以感知它的周围环境、执行简单且有效的计算，并与其通信半径内的邻居节点进行信息传输，把所采集的信息最终传输到基站。由于一个低能量的传感器节点会导致网络过早的瘫痪，人们希望通过在网络中放置具有高能量的中继器来延长网络的使用寿命。然而，现实中存在着许多不定性因素，这使得有些位置不允许放置中继器，为了解决这个问题，就要从事先给定的可放置中继器的位置集合中选出满足网络连通性要求的最小位置子集合来放置中继器。中继器的作用不是为了感知它的周围环境和采集信息，而是为了与传感器及其他中继器保持通信，使传感器采集的信息可以通过若干个中继器成功的传输到基站。由于中继器的成本比较高，所以放置最少数量的中继器也满足了降低成本的需求。在本文中，我们讨论了双层带位置限制的无线传感器网络模型，研究了怎样放置最少个数的中继器使无线传感器网络满足单覆盖单连通或双覆盖双连通，提出了解决这个问题的近似算法并给出了算法性能比分析。本文概述如下：第一章介绍了有关图论、算法理论和组合优化方向的一些概念和定义。第二章重点介绍无线传感器网络理论和无线传感器网络中继器放置问题的研究成果。第三章针对双层带位置限制能量收获无线传感器网络的中继器放置问题展开研究，得到了一个满足单覆盖单连通要求性能比为9.75ε的近似算法和一个满足双覆盖双连通要求性能比为O (log n)的近似算法。第四章主要研究了无线传感器网络低干扰中继器放置问题，研究目的是在网络中放置尽可能少的中继器使网络满足所要求的连通水平并且总干扰值尽可能的小。本章设计了一个满足单连通要求性能比为7.75的近似算法和一个满足双连通要求性能比为15的近似算法。第五章主要讨论了双层带限制无线传感器网络中继器放置问题，设计了一个使无线传感器网络满足k覆盖2连通要求的近似算法。最后一章对全文研究结果进行了概括，并且对进一步能研究的问题进行了简单介绍。