论文部分内容阅读
组播服务器复制是一种改善组播服务性能、提高可扩展性的新技术。它存在多个放置在网络不同位置并且提供同种服务的服务器,依据拓扑结构的特点和当前网络负载状况,它们将分别为不同的客户群提供组播服务。很显然,一旦引入多台服务器,就必然引起如下问题:为了达到网络整体收益最大化目标,将如何对客户端分组,将不同的子组分配给某台服务器;如何在一个子组内建立组播树。这一问题属于复制组播服务器选择问题。它已被证明是NP问题。现有解决这一问题的算法,存在着适用范围窄或求解质量不高的缺陷。针对这种状况,本文提出了基于遗传算法的复制组播服务器选择算法GA-RMSS(Genetic Algorithm based Replicated Multicast Server Selection)。 本文首先将问题空间映射到染色体空间,即将合法的选择方式视为染色体,并对其进行编码。我们设计了二级染色体编码方案。第一级编码表示服务器分配方式,第二级编码表示各子组组播树。在第二级编码中,提出了随机组播树生成算法DRMT(Dijkstra-based Random Multicast Tree),它利用Dijkstra算法和随机扰动生成丰富的子组组播树,满足遗传算法的要求;同时,这一算法所生成的组播树都是合法的,避免了对非法编码的检查和修复,减小了实现难度,加快了生成速度。对于生成的组播树,我们提出了以路由矩阵进行存储的方法,这种方法既能表达丰富的信息,同时又具有矩阵操作简单易行的特点。 针对求解目标,我们设计了整合的适应度函数。通过选取不同的参数,它不仅可以体现平均接收速率或公平性的单个目标,还可同时表达多个目标,扩大了算法的适用范围。GA-RMSS算法的选择操作采用最佳个体保存法,交叉操作对第一级编码实行随机一点交叉,变异操作对第一级编码实行随机一点变异,交叉和变异后代的第二级编码利用DRMT算法重新生成。交叉、变异操作的实质是对原有的服务器选择方式进行合法的重组,以期产生更好的选择结果。⑨硕士学位论文MASTER’5 THESIS 为深入研究GA~RMSS算法的性能,本文通过大量实验将它与目前广泛使用的最短路径法和最宽路径法进行了对比。实验分别比较了在稀疏网络和密集网络中的各种配置下,三种算法对三组适应度参数的求解质量。实验结果表明,GA-RMSS算法对优化目标的求解具有绝对优势,并且它在提供备份路由、网络负载均衡等方面也有较好的表现。