多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展 ,多播技术应用日益广泛 .多播路由是要寻找连接源节点和一组目的节点的一棵多播树 ,这个问题在数学上归结为 Steiner树问题 ,它是一个 NPC问题 .在实际网络中 ,网络节点具备不同的多播能力 ,有些节点不支持多播 ,有些节点支持多播 ,但为了保证网络速度和节点负载平衡 ,支持多播的节点要限制其复制信息的数量 ,即节点的多播能力受限 .在这种情况下 ,寻找多播树变得更加困难 .该文用节点的度约束来表示每个节点具备的多播能力 ,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题 ,其仍是一个 NPC问题 .该文提出了一种求解带度约束多播路由问题的双层遗传算法 .算法的基本思想是最优多播树应是一棵满足度约束的最小生成树 ,因此问题的关键在于如何找到包括在最优生成树中的 Steiner节点 .遗传算法采用二进制编码方式 ,内层算法用于求解满足度约束的最小生成树 ;外层算法进行全局搜索 .该文将算法在稀疏图上进行实验 ,为了更好地模拟真实网络 ,稀疏图中每个节点具有不同的多播能力 ,并且多播目的节点数目相比于网络节点数要小 .实验对算法进行了三方面的比较 :(1)解的质量 ;(2 )计算时间 ;(3)算法的收敛性 .实验结果表明 ,文中提出的遗传算法能够找到费用较小的多播