一种基于松弛算法改进的最小组播树生成方法  

An Improved Multicast Spanning Tree Method Based on Relax Algorithm

作　　者：向雄 李羡童 XIANG Xiong;LI Mu-tong(South China Institute of Software Engineering,Guangzhou University,Guangzhou 510990)

机构地区：[1]广州大学华软软件学院网络技术系

出　　处：《现代计算机》2019年第27期9-15,共7页Modern Computer

基　　金：广东省普通高校特色创新项目(No.2016KTSCX188);广州大学华软软件学院教学、科学研究项目(No.ky201613);广州大学华软软件学院信息管理与信息系统特色专业建设(No.ZDZY201701)

摘　　要：最小组播树是一个经典的网络传输问题。组播树生成问题可泛化为斯坦纳树问题,但后者通常情况下是一个NP完全问题。目前已经存在很多包括松弛算法在内的近似算法用于组播树的生成,但没有一种能达到最优。分析松弛算法执行过程中的所形成的环路,发现其中有些环路是可优化的,优化之后即可降低整棵树的传播低价,于是提出一种通过破除可优化环来生成最小组播树的方法。该方法首先分析可优化环的条件,分析环路中的中转节点的特点,设计寻找环的分支节点的子算法和破环的子算法,最终得出寻找最小代价组播树的方法,数据模拟结果表明,在不增加时间复杂度的前提下该方法能够获得目前为止最小的组播树代价。Minimum multicast tree is a classical issue in network transmission. A multicast tree problem can be generalized to a Steiner tree problem which is proved to be a NP-complete problem. At present, there are many approximate algorithms including relaxation algorithm to generate multicast tree, but none of them can achieve optimal results. Analyzes the rings formed during the execution of relaxation algorithm in depth,and proposes a method named ring optimization to generate single-source minimum multicast tree by breaking the optimizable rings. The simulation results show that the method can achieve the minimum total cost of multicast tree so far without increasing the time complexity.

关 键 词：组播 斯坦纳树 最短路径 松弛算法 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]