无线传感器网络中继器放置问题算法研究

论文摘要

无线传感器网络是由大量随机分布在恶劣环境中的价格低廉的传感器节点组成,这些传感器节点具有区域监测、数据处理和短距离通讯的功能,由于传感器节点本身安装的电池不能随意更换或者充电,而传输信息需要消耗能量,并且通讯能量的消耗也是以距离的指数形式增长,因而如何减少信息传输过程中的能量损耗将是今后重点研究的课题。本文的主要工作是讨论无线传感器网络中具有不同条件的两个中继器放置问题,对这两个问题都设计了近似算法并且给出其相应的性能比的证明,本文结构如下:第一章为绪论,主要介绍图、网络以及组合优化的相关基础知识。第二章主要介绍无线传感器网络的发展背景、无线传感器网络中继器放置问题目前已经取得的主要研究成果以及进展,主要是简单描述一些重要参考文献中所用的方法,以及在相同类型的问题中,针对不同的文章提出的算法的特点进行分析。第三章针对单层网络模型上具有位置限制且连通度要求不同的中继器放置问题设计了一个近似算法,并给出该算法性能比的证明。该算法首先是通过给每条边设定不同的权值,然后找出满足不同传感器到基站之间有不同数目的点不相交的路的要求,并且最终的网络是所有边的权重之和最小的连通网络,经证明该算法的性能比是10。第四章讨论无线传感器网络上当R = r时的中继器放置问题,通过设计算法,满足每个传感器到基站都至少存在两条点不相交的路的要求,并给出了其性能比的证明。第五章主要是全文内容的概括和总结,并对接下来的研究进行了展望。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 图论的基本概念
• 1.2 组合优化问题和计算复杂性的概念
• 1.2.1 组合优化问题
• 1.2.2 算法的复杂性介绍
• 1.3 介绍 P,NP,及NP-hard 概念
• 1.3.1 多项式问题（P）
• 1.3.2 非确定多项式问题类（NP）
• 1.3.3 完全问题类（NPC）及困难问题（NP-hard）
• 1.4 近似算法和启发式算法
• 1.4.1 启发式算法
• 1.4.2 近似算法
• 1.5 论文的组织
• 第2章 无线传感器网络中继器放置问题的研究进展
• 2.1 无线传感网络的介绍
• 2.2 无线传感器网络中继器放置问题研究现状简介
• 2.2.1 单层无线传感器网络
• 2.2.2 双层无线传感器网络
• 2.2.3 混合型无线传感器网络
• 2.3 本章小结
• 第3章 传感器连通度要求不同的无线传感网络放置问题
• 3.1 问题描述及基本引理
• 3.2 问题描述
• 3.3 连通度要求不同的无线传感器网络放置问题算法
• 3.4 本章小结
• 第4章 单层网络上的中继器放置问题
• 4.1 问题模型与基本定义
• 4.1.1 单层无线传感器网络模型与基本概念
• 4.2 算法设计与性能比分析
• 4.3 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 可供进一步研究的问题
• 5.2.1 连通度要求不同的放置问题
• 5.2.2 有位置约束的中继器放置问题
• 5.2.3 混合无线传感器网络
• 5.2.4 三维空间中的放置问题
• 致谢
• 参考文献
• 附录
• 详细摘要