基于粒子群优化的Ad Hoc网络多播路由算法

摘要

Ad Hoc网络是一种多跳、自组织、分布式的无线网络。整个网络没有固定的基础设施,每个节点都是移动和动态变化的,可以随时随地快速进行部署。然而,无线信道固有的特点及节点移动造成网络拓扑的频繁变化,使得传统用于Internet网络的路由技术无法直接在Ad Hoc网络中使用,需要根据其网络特点设计新的路由协议。多播通信方式可以减少从单个源节点或多个源节点发送相同的信息到多个目的节点的通信代价,并且能够节省网络的传输带宽、路由的处理时间和传输时延,对于Ad Hoc网络这种带宽资源紧张、系统资源有限的网络环境具有重要的应用价值。节点间的通信费用、传输带宽、延时和延时抖动是影响Ad Hoc网络多播树性能的主要因素。本文以搜索Ad Hoc网络最优多播树为研究目标,从分析粒子群算法的原理和Ad Hoc网络的特点两方面入手,对Ad Hoc网络多播路由算法进行较深入的研究。具体研究内容如下:1.针对基本粒子群算法的易陷入局部极值、搜索精度不高等缺点改进了标准粒子群算法,把线性递减的惯性权重因子设计为自适应惯性权重因子,并在此基础上提出了一种自适应粒子群优化的Ad Hoc网络多播路由算法(APSO),将微粒在解空间中的飞行搜索过程映射为多播树的树形变换过程。同时构建了Ad Hoc网络中QoS多播网络模型,采用罚函数处理约束条件来设计适应度函数。描述了APSO算法求解Ad Hoc网络多播路由问题的实现过程,设计了一种新的整数编码方案,将QoS多播路由优化问题转化为整数计算问题。仿真分析了APSO算法搜索到多播树的费用值、延时、延时抖动随迭代次数和网络规模的变化趋势,并和传统的GA算法和标准PSO算法搜索到的多播树的性能进行比较。2.根据粒子群算法的缺点和模拟退火算法的优点将两个算法进行结合,提出一种基于模拟退火粒子群优化的Ad Hoc网络多播路由算法,描述了算法的实现过程,并利用轮盘赌策略产生模拟退火的新解。在20网络节点、1个源节点、5个目的节点的网络环境下,分析该算法搜索到的多播树随迭代次数的变化;并计算不同网络规模下算法达到收敛时的多播树的适应值。实验显示出该算法能快速的找到Ad Hoc网络中满足QoS要求的最优多播树,尤其在大规模网络下更能显示该算法的有效性和可靠性。

目录

摘要

Abstract

第1章 绪论

1.1 课题背景简述

1.2 Ad Hoc网络简述

1.2.1 Ad Hoc网络发展历史

1.2.2 Ad Hoc网络的特点

1.2.3 Ad Hoc网络的应用

1.3 Ad Hoc网络的研究现状

1.4 本课题研究内容和意义

1.5 论文结构

第2章 QoS多播路由研究

2.1 引言

2.2 多播的概念

2.3 多播路由的QoS约束

2.3.1 QoS的概念

2.3.2 QoS度量指标

2.3.3 QoS路由策略

2.4 QoS多播路由问题的分类

2.5 QoS多播路由算法

2.6 Ad Hoc网络的QoS多播路由

2.7 本章小结

第3章 粒子群优化算法研究

3.1 引言

3.2 粒子群优化算法

3.2.1 粒子群算法的基本原理

3.2.2 标准粒子群算法

3.2.3 标准PSO算法流程

3.3 粒子群优化算法的改进

3.3.1 离散二进制PSO算法

3.3.2 混合PSO算法

3.3.3 协同PSO算法

3.3.4 自适应PSO算法

3.4 PSO算法与遗传算法的比较

3.5 本章小结

第4章 基于APSO的Ad Hoc网络多播路由算法

4.1 引言

4.2 APSO算法

4.2.1 PSO算法早熟收敛分析

4.2.2 自适应调整策略

4.2.3 APSO算法描述

4.3 基于APSO的Ad Hoc网络多播路由算法

4.3.1 算法的基本思想

4.3.2 编码

4.3.3 Ad Hoc网络模型

4.3.4 适应度函数

4.3.5 速度更新

4.3.6 树形变换

4.3.7 算法描述

4.3.8 算法参数的确定

4.4 仿真结果与分析

4.4.1 迭代次数对算法性能的影响

4.4.2 网络规模对算法性能的影响

4.5 本章小结

第5章 基于模拟退火粒子群优化的Ad Hoc网络多播路由算法

5.1 引言

5.2 模拟退火算法简述

5.2.1 固体物理退火和Metropolis准则

5.2.2 模拟退火算法

5.2.3 模拟退火算法(SA)的有限时间实现

5.2.4 模拟退火算法的基本过程

5.3 模拟退火粒子群算法

5.4 基于模拟退火粒子群优化的Ad Hoc网络多播路由算法

5.4.1 算法的基本思想

5.4.2 新解的产生

5.4.3 算法的描述

5.4.4 算法参数的确定

5.5 仿真结果分析

5.6 本章小结

第6章 结论

6.1 总结

6.2 研究展望

参考文献

致谢

攻读硕士期间发表的学术论文