无线传感器网络中虚拟骨干网构造算法研究

发布时间：2017-09-18 11:03

  本文关键词：无线传感器网络中虚拟骨干网构造算法研究

  更多相关文章： 无线传感器网络 圆盘图 最小m-连通k-全控制集 最小r-跳k-控制

【摘要】：本文主要研究无线传感器网络中的虚拟骨干网构建所产生的相关组合优化问题。由于其广泛的应用性,无线传感器网络(WSN)近十几年来得到了深入研究。它是一个没有基础设施的自组织无线移动网络,并且传感器网络中的节点很容易发生故障或者能量耗尽导致通信中断,因此提出了在网络中构建虚拟骨干网来负责数据的路由转发。虚拟骨干网作为路由协议可以很好的解决由泛洪带来的广播风暴,从而减少大量的冗余信息,减少节点通信时的能耗,进而改善网络性能。 本文研究的主要内容包括两个方面。首先,我们针对无向圆盘图中的最小m-连通k-全控制集问题(其中,m,k为任意正整数),提出了一个近似算法,对此算法进行了理论分析,得到一个较好的近似比。其次,我们研究了无向圆盘图中最小r-跳k-控制集问题(其中,k,r为任意正整数),给出一个两阶段的近似算法。第一阶段,利用三色算法得到一个极大r-跳独立集；第二阶段向控制集加入节点使得满足连通性要求,从而得到连通控制集,最后通过对算法的分析得到了近似比。 本文的主要贡献是推广了相关的虚拟骨干网优化构造问题,并设计了这些问题的近似算法,得到了较好的近似比。
【关键词】：无线传感器网络 圆盘图 最小m-连通k-全控制集 最小r-跳k-控制
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP212.9;TN929.5;O157.5
【目录】：

• 摘要4-6
• ABSTRACT6-8
• 目录8-9
• 第一章 绪论9-14
• 1.1 研究背景9
• 1.2 体系结构9-10
• 1.3 无线虚拟骨干网络的研究意义10-12
• 1.4 相关工作12
• 1.5 论文结构12-14
• 第二章 基本知识14-20
• 2.1 图论中的术语14-15
• 2.2 连通控制集15-16
• 2.2.1 控制集15-16
• 2.2.2 m-连通k-控制集16
• 2.2.3 k-全控制集16
• 2.3 常见算法构造的基本思想16-18
• 2.3.1 先控制再连通17
• 2.3.2 先形成回路再构造控制17
• 2.3.3 基于概率的算法17-18
• 2.4 网络模型18-20
• 2.4.1 单位圆盘图18-19
• 2.4.2 无向圆盘图19-20
• 第三章 最小m-连通k-全控制集问题算法设计与分析20-27
• 3.1 引言20
• 3.2 算法设计与分析20-25
• 3.2.1 1-连通k-全控制集的近似算法21-23
• 3.2.2 m-连通k-全控制集的近似算法23-25
• 3.3 算法的性能分析25-27
• 第四章 最小r-跳k-控制集问题的近似算法27-46
• 4.1 引言27
• 4.2 算法设计27-30
• 4.2.1 极大r跳独立集算法28-29
• 4.2.2 连通r-跳k-控制集算法29-30
• 4.3 算法的性能分析30-46
• 第五章 总结与展望46-47
• 参考文献47-50
• 致谢50-51
• 攻读学位期间发表的学术论文目录51

【参考文献】

中国期刊全文数据库 前1条

1 帅天平;李业芳;艾文宝;;传感器网络中最小k-连通m-控制集问题的近似算法[J];工程数学学报;2012年05期

，

本文编号：875127