| 摘要 | 第1-6页 |
| ABSTRACT | 第6-10页 |
| 1 绪论 | 第10-14页 |
| ·图的基本定义 | 第10页 |
| ·组合优化问题和计算复杂性 | 第10-11页 |
| ·问题与实例 | 第10页 |
| ·组合优化问题及其数学模型 | 第10-11页 |
| ·计算复杂性 | 第11页 |
| ·介绍 P，NP 及 NP-hard 概念 | 第11-12页 |
| ·优化问题的判定形式 | 第11页 |
| ·多项式问题类(P 问题) | 第11页 |
| ·非确定多项式问题类(NP 问题) | 第11-12页 |
| ·完全问题类（NPC 问题）及困难问题（NP-hard 问题） | 第12页 |
| ·近似算法与性能比 | 第12-13页 |
| ·论文主要内容及其结构 | 第13-14页 |
| 2 无线传感器其网络中继器放置问题研究发展 | 第14-18页 |
| ·无线传感器网络的简介 | 第14-15页 |
| ·放置问题相关研究 | 第15-17页 |
| ·单层无线传感器网络 | 第15-16页 |
| ·双层无线传感器网络 | 第16-17页 |
| ·本章小结 | 第17-18页 |
| 3 中继器放置的 2-连通问题研究 | 第18-24页 |
| ·问题描述 | 第18-19页 |
| ·单层网络的 2-连通问题模型 | 第18-19页 |
| ·双层网络的 2-覆盖 2-连通问题模型 | 第19页 |
| ·k -几何圆盘覆盖的基本定义 | 第19页 |
| ·单层网络 2-连通问题算法设计与分析（ R= r） | 第19-22页 |
| ·近似算法设计 | 第19-20页 |
| ·算法性能比分析 | 第20-22页 |
| ·双层网络 2-覆盖 2-连通问题算法设计与分析（ R≥ r） | 第22-23页 |
| ·本章小结 | 第23-24页 |
| 4 中继器放置的k -连通问题研究 | 第24-31页 |
| ·单层网络的k -连通和k -全连通问题（ R= r） | 第24-28页 |
| ·k -连通和k -全连通问题的基本定义 | 第24页 |
| ·k -连通问题算法设计与分析（ R= r） | 第24-27页 |
| ·k -全连通问题算法设计与分析（ R= r） | 第27-28页 |
| ·双层网络中继器放置的k -覆盖k -连通问题（ R≥ r） | 第28-30页 |
| ·k -覆盖k -连通问题基本定义 | 第28页 |
| ·不含基站的k -覆盖k -连通问题（ R≥ r） | 第28-29页 |
| ·含有基站的k -覆盖k -连通问题（ R ≥r） | 第29-30页 |
| ·本章小结 | 第30-31页 |
| 5 总结与展望 | 第31-33页 |
| ·论文总结 | 第31页 |
| ·问题展望 | 第31-33页 |
| ·容错性研究 | 第31页 |
| ·混合无线传感器网络 | 第31-32页 |
| ·位置限制的中继器放置问题 | 第32-33页 |
| 致谢 | 第33-34页 |
| 参考文献 | 第34-38页 |
| 附录 | 第38页 |
