无线传感器网络是由大量随机分布在恶劣环境中的价格低廉的传感器节点组成,这些传感器节点具有区域监测、数据处理和短距离通讯的功能,由于传感器节点本身安装的电池不能随意更换或者充电,而传输信息需要消耗能量,并且通讯能量的消耗也是以距离的指数形式增长,因而如何减少信息传输过程中的能量损耗将是今后重点研究的课题。本文的主要工作是讨论无线传感器网络中具有不同条件的两个中继器放置问题,对这两个问题都设计了近似算法并且给出其相应的性能比的证明,本文结构如下:第一章为绪论,主要介绍图、网络以及组合优化的相关基础知识。第二章主要介绍无线传感器网络的发展背景、无线传感器网络中继器放置问题目前已经取得的主要研究成果以及进展,主要是简单描述一些重要参考文献中所用的方法,以及在相同类型的问题中,针对不同的文章提出的算法的特点进行分析。第三章针对单层网络模型上具有位置限制且连通度要求不同的中继器放置问题设计了一个近似算法,并给出该算法性能比的证明。该算法首先是通过给每条边设定不同的权值,然后找出满足不同传感器到基站之间有不同数目的点不相交的路的要求,并且最终的网络是所有边的权重之和最小的连通网络,经证明该算法的性能比是10。第四章讨论无线传感器网络上当R = r时的中继器放置问题,通过设计算法,满足每个传感器到基站都至少存在两条点不相交的路的要求,并给出了其性能比的证明。第五章主要是全文内容的概括和总结,并对接下来的研究进行了展望。