基于改进演化蚁群算法的无线自组网多播路由研究

摘要

随着计算机网络技术和多媒体业务应用的迅速发展,大众对网络的需求不再局限于有线网络技术,无线自组网技术的提出和广泛应用已经逐渐成为有线网络技术的有益补充。无线自组网是一种多跳的和动态变化的网络,与传统的蜂窝式网络不同,无线自组网没有固定的基础设施和路由器,它是由各移动的主机本身通过无线连接而形成的自主系统,且移动主机本身不仅充当路由器,同时也是作为一个通信的端节点。由于无线自组网中移动主机的动态变化性容易引起网络的拓扑结构随着主机的移动而发生变化,从而导致主机本身能够提供的带宽都变得十分有限。因此,对无线自组网中的路由算法协议的研究就显得尤为重要。
　　此外,随着多媒体技术应用的发展和普及,多媒体业务具有的数据量大、时延敏感性强和持续时间长等问题都是不能忽视的,因此确保无线自组网络的服务质量(Quality of Service,简称QoS)也是非常重要和迫切的。多播路由技术正是解决无线网络中确保服务质量问题的关键技术。多播技术不同于传统的单播和广播技术,它是一种一点对多点、多点对多点的网络技术,能够有效地节省网络的带宽资源。
　　由于无线自组网本身的特性和QoS多播路由的特点,无线自组网的QoS多播路由问题不仅是一个满足多约束的问题,同时也是一个NP完全问题,用传统的路由算法难以有效地解决。演化算法和蚁群算法作为求解NP完全问题的有效工具,已经得到了诸多研究人员的关注。本论文在深入地研究了已有的网络多播路由算法协议的基础上,提出一种基于改进演化蚁群算法的无线自组网多播路由算法(IEAMRA),该算法克服了传统路由算法在解决无线自组网QoS多播路由方面的不足,有效地提高了路由效率,节省了网络资源。
　　本论文的主要创新点包括:
　　1、提出了一种基于改进演化蚁群算法的无线自组网QoS多播路由算法,该算法结合了演化算法和改进的蚁群算法的优点,有效地利用了演化算法的全局搜索能力和改进蚁群算法的并行性。
　　2、针对无线自组网QoS多播路由的特点,对传统蚁群算法进行了改进。首先在路径上不再是按照以往的状态转移公式选择下一步,而是设定一个引导性公式来进行状态转移。此外,在信息素更新方式上也进行改进,不再是待蚂蚁走完一步就对路径上的信息素进行局部更新调整,而是通过引入一个反馈的因子,通过该因子反馈先前的蚂蚁搜索的消息,从而避免了蚂蚁走回头路浪费搜索时间。同时待蚂蚁循环搜索完一次后也不再对所有所求的解采用全局的信息素更新调整,而是在记录蚁群搜索的最优和最差的路径后,只对最优路径上的信息素进行更新,较差路径上的信息素采取削减的方式,从而引导蚂蚁更好的搜索。
　　3、结合演化算法和改进的蚁群算法,并将其应用到无线自组网的QoS多播路由问题求解,通过与基本遗传蚁群算法(GAAC)进行比较得出,该算法在求解无线自组网的QoS多播路由问题时不仅有着更好的搜索路由效率,同时还能明显改善算法各方面的性能。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题研究背景与意义

1.2 国内外研究现状

1.3 本论文的主要工作

第二章 无线自组网的QoS多播路由

2.1无线自组网的基本概念

2.2 多播应用及QoS约束

2.3 无线自组网的多播路由

2.4 求解无线自组网中的QoS多播路由问题的仿生算法概述

2.5 本章小结

第三章 演化算法与传统蚁群算法介绍

3.1 演化算法概述

3.2 传统蚁群算法概述

3.3 本章小结

第四章 现有的QoS多播路由改进算法

4.1 引言

4.2 蚁群系统

4.3 引入变异算子的蚂蚁算法

4.4 改进的遗传算法

4.5 BWAS算法

4.6 本章总结

第五章 基于改进演化蚁群算法的无线自组网多播路由研究

5.1 引言

5.2 无线自组网的网络模型和问题描述

5.3 IEAMRA的基本思想

5.4 IEAMRA算法设计

5.5 基于IEAMRA算法的描述和实现

5.6 仿真实验与结果分析

5.7 本章小结

第六章 总结与展望

6.1 论文的主要工作和贡献

6.2 下一步的工作和展望

参考文献

致谢

个人简历、在学期间发表的学术论文与研究成果

声明