文档介绍：分类号:TP393 学校单位代码:10446
硕士学位论文
论文题目:无线网络容错拓扑控制算法研究
研究生姓名: 姜洪璐
学科、专业: 计算机应用技术
研究方向: 计算机网络与通信
导师姓名、职称: 禹继国教授
论文完成时间: 2012 年 4 月
硕士学位论文
快速分形图像压缩并行算法研究与实现
研究生姓名: 姜洪璐
业专科学: 计算机应用技术
向方究研: 计算机网络与通信
名姓: 禹继国
师导
称职: 教授
论文完成时间: 2012 年 4 月
曲阜师范大学研究生学位论文原创性说明
(根据学位论文类型相应地在“□”划“√”)
本人郑重声明:此处所提交的博士□/硕士□论文《无线网络容错拓扑控
制算法研究》,是本人在导师指导下,在曲阜师范大学攻读博士□/硕士□学
位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含他人已
经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人和集体,
均已在文中已明确的方式注明。本声明的法律结果将完全由本人承担。
作者签名: 日期:
曲阜师范大学研究生学位论文使用授权书
(根据学位论文类型相应地在“□”划“√”)
《无线网络容错拓扑控制算法研究》系本人在曲阜师范大学攻读博士□/
硕士□学位期间,在导师指导下完成的博士□/硕士□学位论文。本论文的研
究成果归曲阜师范大学所有,本论文的研究内容不得以其他单位的名义发表。
本人完全了解曲阜师范大学关于保存、使用学位论文的规定,同意学校保留
并向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅。本人
授权曲阜师范大学,可以采用影印或其他复制手段保存论文,可以公开发表
论文的全部或部分内容。
作者签名: 日期:
导师签名: 日期:
无线网络容错拓扑控制算法研究
摘要
无线 Ad-Hoc 网络是由一组带有无线通信收发设备的移动节点组成的多跳、临时、无
中心的自治系统,是一种不需要基础设施、可以在任何地点任何时刻迅速构建的移动自组
织网络。网络中的移动节点本身具有路由和分组转发功能,可以通过无线方式构成任意的
拓扑。无线传感器网络是一种无中心节点的全分布系统,以自组织和多跳的方式构成网络,
大量静止或移动的传感器节点通过随机投放的方式被密集部署于监控区域。各个传感器节
点之间有良好的协作能力,整个网络的全局任务通过局部的数据交换完成。包含无线
Ad-Hoc 和传感器网络的无线网络近年来越来越多的引起人们的注意,它们在抢险救灾、战
场监控、环境监测、医疗卫生、健康应用中具有重要的使用价值和广阔的应用前景。
近年来,容错通信机制和能量高效是无线网络中的研究重点和热点。拓扑控制是提高
网络连通性、可靠性、容错性以及节省能耗的最有效的方法之一。容错拓扑控制的主要目
标是在保证网络的一些拓扑特性(比如连通性)的基础上,通过功率控制或者骨干网节点
的选择,使网络的总能耗最小。本文总结了近年来提出的各种容错拓扑控制算法及其主要
设计思想,从容错性、能量高效性、算法复杂度和稳定性等方面综合分析现有的容错算法,
并对现有文献中的容错算法进行分类和总结。在此基础上,针对广播、组播和汇播问题提
出新的容错拓扑控制算法,根据图论、线性规划、控制论等数学知识,从理论上证明算法
的正确性以及算法的综合性能,仿真实验表明网络总能耗较小,算法可以有效的延长网络
寿命。
本文共包括五个部分。第一章介绍了无线传感器网络和无线 Ad-Hoc 网络的基础概念,
针对目前的研究现状,提出了具体的研究问题和研究意义。第二章主要介绍了无线网络中
的网络模型、能量模型、容错性相关定义,并对目前的容错拓扑控制算法进行了分类总结。
第三章提出了一个能量高效的广播树构造算法 CBEEB(Clustering-based Energy-Efficient
Broadcast Tree),该算法包含一个分簇算法和 IBIP(Improved BIP 算法)。首先网络中的各节
点计算自己的权值,并选出簇头节点和簇成员节点,簇成员节点作为广播树的叶子节点,
网络广播时叶子节点的能耗为零;在簇头节点集合上执行 IBIP 算法,构造广播树。第四章
研究了无线 Ad-Hoc 网络在 k-容错准则下 k-广播、k-组播和 k-汇播三种不同的拓扑控制问
题;其目标是在保证网络是 k-容错的前提下使网络的总能量消耗最小。针对不同的拓扑控
制问题,提出了一种新的通用近似算法保证了网络拓扑的 k-容错性,并通过理论分析证明
了算法的近似比,仿真实验证明算法的优越性。第五章总结全文,并给出了目前容错拓扑
控制研究中存在的问题以及