无线传感器网络生成的网络拓扑中,如果没有拓扑控制,所有节点都会以最大功率工作。在这种情况下,节点有限的能量将被快速消耗。对网络的拓扑结构进行控制是一种重要的节省能量消耗、延长网络寿命的策略。传感器节点由电池提供能量,且分布在恶劣环境中,电池不能够随意更换或再充电,需要尽量节省能量,提高能量的有效利用率。本文主要研究无线传感器网络中的拓扑控制及能量有效利用问题,主要内容如下:第一章绪论中概述了本论文所用到的有关图论和组合优化的基本概念。第二章主要介绍了无线传感器网络中拓扑控制问题及其相关研究工作。对网络拓扑控制问题,介绍拓扑控制的定义和拓扑控制的方法。从拓扑控制研究的不同目标,对文献进行了综述介绍。第三章研究半径可变的容错性连通覆盖问题,即给定一个由传感器集合D组成的无线传感器网络和一个需要监测的区域?,如何选择一个传感子集M ,并对M中的任一传感器分配传感和通讯半径,使选择的子集在满足2-连通k -覆盖条件下的能量费用最少。对此问题设计了一个贪婪算法,得到的近似因子为O ( r log khn ),其中r为相连路长, n为传感器网络中传感器的个数, h为传感器可以选择的传感半径的个数。第四章研究延长连通覆盖集合的网络寿命问题。在寻找到满足连通覆盖要求的不同的传感器集合后,如何给这些集合分配工作时间,使得网络总的工作时间最长。文中给出此问题的具有指数个变量的LP形式,用The Garg-K?nemann Algorithm求解此问题,给出了具有近似性能比为(r 1 +ε) (1 + log d),ε>0的算法,r为相连路长,d为在任一传感区域的最多面的个数。第五章研究无线传感器网络中的能量有效利用问题,介绍了能量有效利用研究的现状。同时研究双层传感器网络中的能量有效利用问题,利用簇策略减少能量消耗及延长网络寿命,把研究的问题转化为最小费用流问题,从而找到了求解问题的最优算法。第六章是对全文的总结概括,并对下一步的工作做了展望。