无线Ad Hoc网络中的组播路由算法研究

摘要

随着现代无线通信技术和因特网的发展与进步，任何人在任何时间、任何地点都能够获取信息并与他人通信，已经成为人们对现代信息网络的切实要求。无线Ad Hoc网络是一种移动通信技术和计算机网络技术相结合的网络，是由彼此对等的、自主的移动节点组成的多跳自组织无线网络。无线Ad Hoc网络无需固定基础设施支持，能快速、简单组网，并且按照其设计的初衷，能够自组织、自修复，因此，正在成为下一代无线网络的有力竞争者。在Ad Hoc网络中，网络的住处交换采用了计算机网络中的分组交换机制，组网却不受地理位置和有无固定的通信基础设施的限制，可独立组网，也可联入其他网络。此外，用户终端可以自由移动，每个终端都兼有路由器和主机两种功能。 由于架构无线Ad Hoc网络非常方便，而且可快速适应网络的动态拓扑变化，所以它可广泛应用于灾难救助、战场指挥、临时会议、协同工作等场合，这些应用通常都有一个共同的特征，就是一到多或是多到多的数据传输，因此，组播通信在无线Ad Hoc网络中具有非常重要的作用。 在无线Ad Hoc网络中，一个通信请求可以通过单跳完成，也可以通过若干个中继节点完成，因此，在设计路由算法时必须要考虑中继节点的选择，另外，由于网络中节点是依靠电池供应能量的，所以，节能问题是无线Ad Hoc网络中的一个核心问题。本文就无线Ad Hoc网络的组播节能问题进行了研究，并取得了一定的成果。 本文的主要工作和贡献包括： 1.研究了无线Ad Hoc网络的研究热点以及现有的组播路由协议，并深入分析了基于源端的树型结构组播路由算法，研究了该类算法的不足，并提出了改进方案。 2.提出了一个最小化能量组播路由算法。在无线Ad Hoc网络中，能量消耗是路由算法的一个重要衡量标准。本文先利用图理论为该问题建模，简单分析了网络中只有三个节点的情况，并推广到一般网络。然后在分析现有算法不足的基础上，提出了一个以最小化能量为目标的路由算法GMBR(Greedy Maximum-Branch Replacement)，并比较了该算法和已有算法的性能，实验结果显示所提算法在节省总能量消耗方面优于原算法，能够有效地减少能量消耗，并且很容易改进成一个并行算法进一步提高效率。最后将该算法扩展到了组播情况。 3.提出了一个最大化网络生命期组播路由算法。在无线Ad Hoc网络中，如果只是以最小化能量为目标，势必会导致网络中某一部分节点能量消耗过快，从而会缩短网络生命期。因此，在前面章节的基础上，本文研究了节能问题的另一方面一最大化网络生命期。本文首先给出了该问题的理论模型，并分析了节点初始能量相等和不相等两种情况，然后针对节点初始能量不相等的情况提出了一个贪心算法WMST(Weighted Minimum Spanning Tree)，该算法考虑了节点的能量和链路的能量消耗。实验结果表明，算法存优化生命期方面优于已有算法。 4.提出了一个平衡能量负载组播路由算法。本文先证明了最大化网络生命期并不能保证总能量最小，然后在前面提出的最大化网络生命期算法WMST的基础上，本文作出了进一步改进，提出了Improved WMST算法，目标是更好地兼顾最大化网络生命期和最小化总能量消耗这两个目标，尽可能的平衡网络中节点的能量消耗。实验结果表明，算法的性能介于WMST和BIP之间。在平衡能量负载方面优于已有算法。最后针对资源有限的情况对该算法做出了扩展。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章绪论

1.1研究背景

1.2研究现状

1.2.1无线Ad Hoc网络的发展现状

1.2.2当前无线Ad Hoc网络研究的热点

1.2.3无线Ad Hoc网络路由协议的研究热点

1.2.4无线Ad Hoc网络组播的发展和方向

1.3研究目标

1.4论文结构

第2章无线Ad Hoc网络概述

2.1无线Ad Hoc网络的定义

2.2无线Ad Hoc网络的特点

2.3无线Ad Hoc网络的体系结构

2.3.1无线Ad Hoc网络拓扑结构

2.3.2无线Ad Hoc网络协议栈结构

2.4无线Ad Hoc网络的应用

2.5本章小结

第3章无线Ad Hoc网络组播路由协议

3.1与传统路由协议的区别

3.2设计原则

3.3组播路由协议

3.3.1基于树型结构的组播路由协议

3.3.2基于网格结构的组播路由协议

3.3.3组播路由协议的比较

3.4存在的问题

3.5算法的改进

3.5.1避免回路的产生

3.5.2节点数目较大的情况

3.5.3网络通信参数较大的情况

3.5本章小结

第4章最小化能量消耗组播路由算法

4.1概述

4.2问题模型

4.2.1问题假定

4.2.2节点数目为3的情况

4.2.3复杂度分析

4.3 GMBR算法

4.3.1改进方案

4.3.2算法描述

4.3.3性能分析

4.4实验结果

4.4.1节点数目的影响

4.4.2通信媒质参数的影响

4.4.3总结

4.5算法的扩展

4.5.1针对组播请求

4.5.2和BIP算法结合

4.5.3分布式算法

4.6本章小结

第5章能量负载平衡组播路由算法

5.1概述

5.2问题模型

5.2.1广播连通性

5.2.2网络生命期

5.2.3理论模型

5.2.4节点初始能量相等的特例

5.3 WMST算法

5.3.1算法描述

5.3.2算法举例

5.3.3性能分析

5.4进一步改进

5.4.1改进的必要性

5.4.2改进方案

5.4.3性能分析

5.5实验结果

5.5.1性能指标

5.5.2结果分析

5.6算法的扩震

5.6.1收发器有限的情况

5.6.2可用频率有限的情况

5.7本章小结

第6章结束语

6.1论文工作总结

6.2进一步的工作

6.3其他工作

参考文献

已发表的论文

参加的科研工作

致谢