论文部分内容阅读
多播通信,首先建立一棵满足QoS的多播树,信源发出的数据包沿着多播树进行转发.该多播树由QoS多播路由算法决定,因此研究构造多播树的QoS多播路由算法非常重要.该文对时延约束时延约束的最小费用多播路由进行深入研究,具体内容如下:首先,在分析BSMA算法的基础上,以改进K最短路径算法降低BSMA算法时间复杂度.与其他时延约束最小费用路由算法相比,BSMA费用性能最优,但是运算复杂度最高.BSMA算法先是构造了一棵最小时延树,然后利用超级边的方法进行费用优化.其中,对超级边的优化过程中,使用K最短路径算法.BSMA计算时间集中在K最短路径计算,我们引入分支结构和路径替换方法,在多播成员相对网络规模较小的情况下,有效降低BSMA算法的计算时间,使得BSMA算法更具有实用性.改进后的BSMA算法的时间复杂度从O(kn<3>log(n))降为O(knlog(n)(m+nlog(n))),有Ω(n)因子的优化.其次,通过对约束条件下最短路径问题研究,给出全多项式近似解法(FPAS)的多播路由算法.FPAS多播路由算法是一种低复杂度的、时延约束费用最小多播路由算法.约束条件下最短路径问题是NP完全的,不存在多项式时间精确算法.我们首先运用取整和缩放方法得到全多项式近似解法.然后,利用动态规划过程给出受限最短路径问题的两个伪多项式精确算法,并给出保证多项式时间近似解法的检验过程.在近似算法中给出的FPAS的时间复杂度为O(loglog(UB/LB)<*>(|E|n/ε+loglog(UB/LB))).我们将FPAS引入多播路由问题,针对时延受限最小费用路由问题,提出一种新的多播路由算法,它的时间复杂度为|D|O(loglog(UB/LB)(|E|n/ε+loglog(UB/LB))).