无线网络容错拓扑控制算法研究

摘要

无线 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-容错性,并通过理论分析证明了算法的近似比,仿真实验证明算法的优越性。第五章总结全文,并给出了目前容错拓扑控制研究中存在的问题以及下一步的工作。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究背景和研究意义

1.2问题确定

第二章 网络模型和算法概述

2. 1基本模型

2.2相关定义

2.3容错拓扑控制算法分类

2.4容错拓扑控制算法综述与比较

第三章 无线网络中基于分簇的能量高效的广播树构造

3.1相关工作和网络模型

3.2 混合算法CBEEB

3.3算法分析

3.4仿真结果

3.5本章小结

第四章 无线Ad-Hoc网络中k-容错拓扑构造的一种近似算法

4.1相关工作和基础知识

4.2 k-广播

4.3 k-组播和k-汇播

4.4性能比较与仿真

4.5本章小结

第五章 总结和展望

参考文献

在校期间发表的学术论文

致谢