无线传感器网络生成的网络拓扑中,由于传感器的能耗与其传输距离d的k次幂d k成正比,k是不小于2的数,所以进行长距离的传输需要非常昂贵的成本。为了延长无线传感器网络的寿命,同时为了保证整个网络的连通性,向网络中添加若干具有更强通讯能力和计算能力的中继器成为了主要的解决方法。本文主要研究无线传感器网络中的混合型双层网络上的中继器放置问题,主要内容如下:第一章绪论中列出了研究问题的背景,概述了本论文所用到的有关图论、组合优化算法和复杂性的基本概念。第二章主要介绍了无线传感器网络中中继器放置问题及其相关研究工作。对中继器放置问题,介绍了放置问题的定义及其分类。从放置问题研究的不同目标,对文献进行了综述介绍。第三章在混合型的双层无线传感器网络上研究了整个网络的连通性,即在传感器传感半径不全相等且传感器之间不具有数据传输功能的情况下,把问题转化为解决集合覆盖这一问题,通过贪婪的方法放置最少数目的中继器使得整个网络连通。同时又进一步对混合型的双层无线传感器网络上的容错性进行了研究,给出相应的性能比。第四章研究了在带基站的混合型双层网络的连通问题上通过在已选定的中继器的传输边界上选择一个能够覆盖最多数目传感器的位置来放置下一个中继器,直到所有的传感器点都被覆盖这一方法给出复杂性为о（N~3）的启发式算法。第五章是对全文的总结概括,并对下一步的工作做了展望。