基于演化算法qos约束选播路由地研究.pdf

摘要
选播是 IPv6 中新定义的一种标准通信模式,它能使得用户通过一个选播地址
就可以访问到该地址所标识的一组服务器中对用户来说是“最优”的一个。选播通
信可以有效地改善网络流量分布,增强服务的可用性,具有广阔的应用空间。同
时,随着互联网的快速普及,计算机网络技术的不断发展,人们对网络服务质量
也提出了越来越高的要求,因而在选播通信中如何解决多 QoS 约束的选播路由问
题变得十分迫切。
本论文的主要创新点如下:
(1)提出了一种根据选播组中成员服务器的负载来初始化种群的优化方法。
该方法生成的初始种群中包含了从源主机到选播组中各个成员服务器的可行路
径,使得路径的条数与服务器的负载成反比,这样能够有效地克服传统算法未考
虑选播组服务器负载均衡的不足,增加了初始种群的多样性,避免算法陷入局部
最优,有利于改善网络流量分布,提高网络的吞吐量。
(2)提出了一种区分度更高的 QoS 约束惩罚函数。在解决 QoS 约束选播路由
问题的传统演化算法中,对于满足 QoS 约束的可行路径设置的惩罚函数过于简
单,不能够有效地区分出两条满足 QoS 要求路径的优劣,而使用区分度更高的
QoS 约束惩罚函数可以克服这点不足,使得算法在演化过程中能够找到具有更好
QoS 性能的可行路径,收敛到全局最优解而不仅是只找到满意解。
(3)针对选播组服务器的负载不均衡问题,提出了一种基于演化算法的 QoS
网络负载均衡选播路由算法(QLBE)。该算法引入了基于选播组负载的种群初始化
方法,使用了区分度更高的 QoS 约束惩罚函数来组成适应度函数。在随机生成的
Waxman 网络拓扑环境下进行仿真实验,实验结果表明,与传统算法相比,QLBE
算法得到的最优选播路由能够有效地均衡选播组服务器负载,且能在更少的代数内
收敛,有利于改善网络流量分布,提高网络吞吐量。
(4)针对选播路由的 QoS 性能最优化问题,提出了一种基于精英迁移策略演
化算法的 QoS 性能最优选播路由算法(BQEM)。该算法将网络路径搜索空间依据
选播组的大小划分为子种群,在各个子种群独立演化过程中,构造一种精英迁移
策略,将各个子种群的最优个体迁移到其他的子种群,充分发挥优良个体的导向
作用,避免子种群演化的盲目性,有利于提高算法的全局寻优能力。最后在仿真
实验中,通过与 EAs 算法进行对比,结果说明了 BQEM 算法获得的最优路由具有
更优的时延和带宽性能。

关键词:选播路由;演化算法;服务质量;负载均衡;QoS 约束
I
Abstract
Anycast is a new munication method defined in IPv6, users can access the
“best” one from a group of servers which identified by only one anycast address. The
distribution work traffic can be effectively balanced and the availability of services can be
enhanced by anycast which has broad application space. Meanwhile, with the rapid prevalence
speed of and the continued development work technologies, people are putting
forward higher requirements for Quality of Service (QoS) works, as a result how to fix the
routing problems with multi QoS constraints of anycast has became urgent.
The major work and innovations in this thesis are as follows:
(1) An approach to initialize population based on the load of member server in an anycast
group is proposed. By this approach, the initial population posed of various routes that
from the source host to each server o