遗传组播路由算法

　　引言

　　随着多媒体技术的高速发展导致大量多媒体业务出现，如视频点播、视频/音频会议、远程教学、多人游戏等，这些都要求网络必需具备点到多点(组播)通信的能力。原来的点对点通信就难以适应以视听多媒体业务为核心的业务发展。因此组播路由问题成为网络资源优化问题研究的热点之一。

　　所谓组播，指的是一个源节点向多个目的节点发送信息的通信方式，参与组播的多个目的端点组成了一个组播组，每个端节点称为组播组成员。算法要寻找连接源节点和一组目的节点的一棵树，不仅要使网络进行通信的费用最小，还要求源节点与各目的节点间的通信时延满足约束条件，它是网络中的一个NP完全问题[1]，这类问题不能求出其最优解，只能求出其近似最优解或满意解[2~3]。

　　为此，本文探讨了遗传组播路由算法，该算法有效地克服了早熟现象;而且通过引入交叉和变异算子，加快了收敛速度。仿真表明，该算法是有效可行的。

　　组播路由问题描述

　　通常，通信网络可以被表示为一个连通图),(EVG，V表示节点(路由器)的集合，E为任意两相邻节点x和y间通信链路(x,y)的集合。对于Eyx∈∀),(，均有两个正实数 ，分别表示链路(x,y)的时延和费用。对于Vba∈∀,，则a和b间路径P(a,b)的时延函数和费用函数为:

　　在多媒体实时业务的QoS传输中，基于时延受限的组播路由优化问题可表述为：给定源节点s和目的节点集合D∈V-{s}，以及寻找从源节点s到所有目的节点v(D∈v)的组播树并且满足条件：

　　其中Δ为实时业务允许时延的上限值，),(vsPT为GA中从源节点s经组播树到目的节点v的路径。