基于改进的遗传算法实现多约束移动IP路由选择

摘要

移动IP 是解决IP 网络中用户节点移动问题的网络层技术，其中，路由选择是关键,它与一般路由技术的不同之处在于：路由必须经过一个家乡代理，即过定点，同时在实际路由选择时要满足不同服务质量(QoS)的约束。本文主要对多约束QoS移动IP 路由选择算法进行研究，其任务就是在网络中寻找一条既过定点，又能满足其带宽、时延和费用等要求的最佳通路。 论文全面总结了当前QoS路由研究的目标、度量、背景和趋势。阐述了当前研究取得的各种成果和QoS路由研究中的难点及存在的问题。 接着提出了用遗传算法(GA)处理路由选择问题，介绍了GA的原理、缺陷和改进的方法，其中分布式遗传算法(DGA)作为对标准遗传算法(SGA)的改进具有很好的效果。为了使算法性能更优，本文结合Cascade GA 模型，在DGA基础上加入了动态迁移算子，把这种改进后的算法称为改进的分布式遗传算法(EDGA)。给出了EDGA基本模型和整个算法的流程图，对EDGA实现的步骤作了详细说明，并对EDGA 理论性质进行了分析。 然后，分析了多约束QoS移动IP 路由选择的网络模型，把EDGA 应用于多约束QoS移动IP 路由选择中。本文采用矩阵编码，使用基于轮盘赌选择法的选择算子，保证每一代选择适应度较大的个体参与交叉；使用均匀交叉的交叉算子，保证种群尽可能在整个解空间搜索；使用基于矩阵编码的变异算子，使算法能够跳出局部最优；使用动态的迁移算子，使进化能力好的子种群得到更大的空间来搜索最优值，同时尽可能把进化能力弱的子种群中的精英个体吸收到进化能力更好的子种群中去，保证整个种群的进化更具指导性。 本文第五章是仿真结果的分析，在相同控制参数和求解问题的条件下，给出了SGA、DGA、EDGA的求解结果，仿真结果表明，EDGA 无论在收敛速度还是在求解值的精度上都得到了较大的提高。实验结果证明了EDGA处理多约束QoS移动IP 路由选择问题的有效性。 最后对全文的工作和今后研究重点进行了总结和说明。