无线传感器网络是由大量成本较低,能量较少的传感器构成的。传感器最重要的任务是监控一定区域,采集信息,并把信息传输到基站。在真实环境中存在某些位置不能放置中继器。这些位置可能受到各种信号干扰过强,或者在具体问题中不能被考虑,或者其他原因而不能放置中继器。为了解决这个问题,我们可以考虑事先给出大量的可供选择放置中继器的位置,从中选出数量最少的位置放置中继器来实现网络连通。网络寿命决定无线传感器网络采集信息的数量。向无线传感器网络中添加中继器不仅可以使网络连通,而且能延长网络寿命。中继器不是为了监控环境、采集信息而是能够与传感器保持通讯,使得传感器采集的信息通过若干个中继器到达基站。由于中继器成本比较高,我们希望放置数量最少的中继器使网络寿命达到T。本文的主要工作是讨论双层无线传感器网络上,具有位置限制的单覆盖单连通中继器放置问题和网络寿命最大化的中继器放置问题。因为这些问题是NP-hard,所以本文对第一个问题设计一个近似算法并且给出其性能比,对第二个问题设计一个启发式算法。本文结构如下:第一章为绪论,主要介绍图论和组合优化的相关重要基础知识。第二章介绍无线传感器网络的背景和无线传感器网络中继器放置问题的相关研究成果及进展,内容包括对重要文献所用方法的描述和对相同类型问题不同算法的特点分析。第三章针对双层网络模型具有位置限制的单覆盖单连通中继器放置问题设计了一个近似算法并给出性能比。该算法先找到数量最少的可选位置放置中继器来覆盖网络中的传感器,再找到数量最少的可选位置放置中继器使得覆盖传感器的中继器和基站网络连通。本章证明了该算法性能比为9 + log 2d,d为一个中继器所能覆盖传感器个数最大值。第四章基于贪婪算法思想,对无线传感器网络寿命最大化的中继器放置问题设计一个启发式算法并通过例子对该算法得到的解与最优解比较。该算法先放置数量尽可能少的中继器使得整个无线传感器网络连通,再对已放置的中继器进行数量补充来使网络寿命达到T。第五章是全文内容的概括总结,并对接下来的工作进行了展望。