论文部分内容阅读
随着当前Internet的发展和各种多媒体应用的出现，组播技术得到大量应用。组播指将同一信息从源结点传送到网络中多个结点（不一定是网络中所有结点）。实现组播的一般方式是建立组播树, 组播树的优点在于：首先，信息以并行方式沿着树枝发送到不同的组播终点，从而降低了信息传递的时延；其次，信息的复制只在树的分支处进行，因此网络中需要传送的复制信息量最少，能够节约网络带宽资源，降低网络负载，减少拥塞。因此组播成为目前研究最多、应用最广的网络信息传输方式。组播路由算法主要用来建立一棵性能良好的组播树，并使它能够满足各种业务的服务质量需求。本文首先对网络路由选择技术，包括单播路由、组播路由和基于遗传算法的组播路由选择技术进行了分析总结，指出简单性、通用性、外延性、层次型路由和不精确状态信息下的路由是未来服务质量组播路由的研究重点。然后分析了组播和组播路由选择技术的原理，组播路由算法通常采用启发式技术，要么太复杂难以求解，要么太费时不能实际应用，而遗传算法简单高效，非常适用于组播路由选择。随后介绍了遗传算法的基本思想和运行过程以及遗传算法的数学基础，并对遗传算法的基本要素设计技术和改进策略进行了分析总结。在此基础上，将多种群并行技术和退火技术相结合，以克服现有基于遗传算法的组播路由算法过早收敛和后期搜索速度较慢的缺陷，且使用树状编码方法，提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小组播树的多种群并行退火遗传组播路由算法。从理论和实验上验证了算法的正确性，并分析了算法的最坏时间复杂度和空间复杂度，其最坏时间复杂度为(max(e+n㏒+k ,n2))，最坏空间复杂度为( kn2)，它们均为多项式解，表明算法也是有效的。