混合型双层网络上的中继器放置问题

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 网络与图的基本概念
• 1.2 组合优化问题
• 1.2.1 问题与实例
• 1.2.2 组合最优化问题
• 1.3 算法与时间复杂性
• 1.4 优化问题分类
• 1.4.1 多项式问题（P）
• 1.4.2 非确定多项式问题类（NP）
• 1.4.3 NP 完全问题（NPC）
• 1.5 近似算法和启发式算法
• 1.5.1 近似算法（approximation algorithm）
• 1.5.2 启发式算法（heuristic algorithm）
• 1.6 论文的组织
• 第2章 无线传感器网络中的放置问题研究现状
• 2.1 无线传感器网络中的放置问题
• 2.2 无线传感器网络放置问题研究
• 2.2.1 单层无线传感器网络
• 2.2.2 双层无线传感器网络
• 第3章 混合型双层网络的连通与容错问题
• 3.1 连通问题描述
• 3.1.1 算法设计
• 3.1.2 算法的性能比分析
• 3.1.3 结论
• 3.2 容错问题描述
• 3.2.1 算法与设计
• 3.2.2 算法的性能比分析
• 3.2.3 结论
• 第4章 带基站的混合型双层网络的放置问题的改进算法
• 4.1 问题描述
• 4.1.1 定义和术语
• 4.1.2 问题模型
• 4.2 算法分析与设计
• 4.2.1 数据结构和标记
• 4.2.2 算法设计
• 4.3 算法的复杂性分析
• 4.4 结论
• 第5章 总结和展望
• 5.1 主要结论
• 5.2 后续工作展望
• 致谢
• 参考文献
• 作者在读期间发表的学术论文及参加的科研项目
• 一. 完成的学术论文
• 二. 参加的科研项目
• 详细摘要