遗传组播路由算法

　　仿真实验

　　仿真网络的生成采用了改进的Waxman随机网络模型[6]，它保证了生成网络的连通性，并保证每个节点的度数大于等于2。在该模型中，任意两个节点u，v间存在链路的概率为

　　其中，d(u,v)为节点u到节点v的欧氏距离，L为任意节点间最大距离同，参数α和β控制产生网络的特征，其值在(0,1)之间，参数α控制网络中短边与长边之比，β用来调节网络节点的平均度数,采用的网络的坐标空间为4000×4000Rm2，α为0.26， β为0.4，节点的平均度数为4，时延上限Δ为100。

　　我们以最短路径组播树算法(STP)为比较基础，采用如下的性能指标:

　　其中M表示实验次数，R值小于1表示遗传算法(GA)的平均性能优于STP，R值变大，则说明GA的平均性能变差。实验中，遗传算法的参数设置如下:种群规模N=100, pm=0.2, pc=0.6，进化代数为100。

　　算法随网络节点数增长的性能比较

　　在本节实验中，我们将GA和STP的性能比较。固定目的节点占网络节点数比例记为r，分别为5%，10%，20%，考察算法在不同网络节点数下的性能比较。网络节点数从20到100,每隔10采样，在每个采样点上GA和STP各独立运行10次。图1给出了GA和STP比较的结果。从实验来看，R小于1且比较稳定，这充分表明GA较STP更优的性能和良好的扩展性。

　　GA的收敛性结果

　　利用Waxman网络模型，生成一个具有100节点的随机网络，仿真目的节点占网络总节点不同比例时GA的收敛情况，实验结果如图2。

　　从图2，可以明显发现：与SPT相比，GA对组播树费用的改善比较明显，收敛速度也比较快。

　　结论

　　针对传统算法求解时延受限组播路由问题出现的搜索空间过小而无法获得满意解的缺点，本文探讨了一种遗传组播路由算法。该算法设计了交叉和变异算子以实现全局优化的目的，并通过前K-shortest方法克服搜索空间过大的缺点。在实验中，给出了该算法与传统最短路径法(STP)随目的节点和网络节点数增长的性能比较。结果表明，该算法比STP具有更强的搜索能力和更快的收敛速度，同时具有良好的扩展性。