《一种具有时延约束的组播路由算法研究.doc》由会员分享，可在线阅读，更多相关《一种具有时延约束的组播路由算法研究.doc（8页珍藏版）》请在三一文库上搜索。
1、一种具有时延约束的组播路由算法研究doi:10.3969/j.issn.1001-3695.2009.09.016 New delay-bounded constraint multicast routing algorithm ZHOU Xian-wei,LIU Zhen-zhen,LIN Lin, LIU Tao, WANG Chao (Dept. of Communication Engineering, School of Information Engineering, University of Science & Technology Beijing, Beijing 10008
2、3, China) Abstract:For real-time multicast business such as multimedia applications, multicast routing algorithms must optimize both cost and delay.In response to this problem, proposed a heuristic algorithm DCMA, which joined destination nodes to the multicast tree dynamically.This algorithm was ba
3、sed on DDMC algorithm and improved by using new indicator function and link choice function.Considering the optimization of delay and cost, the algorithm efficiently guarantees the performance of multicast tree, with advantage of low time complexity and easy operation in real system. Key words:multi
4、cast routing algorithm; delay-constraint; Steiner tree 0 引言 随着通信技术的发展,人们的应用需求越来越多样化,不同的应用对服务质量的要求也不相同。组播应用的QoS要求主要有带宽、时延、时延抖动等。对于视频点播、电视会议等采用组播方式的多媒体业务来说,时延和代价是两个必须考虑的指标。如果时延过长,就会引起用户听觉和视觉上的不适应,甚至引起语义无法理解。因而时延约束的组播路由问题的研究是目前组播路由算法研究的重要问题1,2。 Alpert等人在文献3中所提出的AHHK算法来源于两种著名的算法,即Prim的最小生成树算法和Dijkstra的最
5、短路径树算法,并采用基于贪婪策略的思想将两者进行结合。 Matta等人4在文献1中所提的QDMR算法调整了DDMC算法,使其能够根据到目的节点的时延与给定的时延上限的比值来动态调整建树的策略。如果到目的节点的时延与给定的时延上限还相差很远,QDMR算法给予目的节点高优先级,将其作为源节点看待。如果已经快逼近时延上限,QDMR算法将给目的节点较低的优先级,从而生成多分支树,以尽量避免违反时延上限。 Aissa等人在文献2中提出的EPDT算法是基于QDMR算法进行改进的,该算法通过改变QDMR算法的指示函数来进一步降低组播树的开销。对于节点时延逼近时延上限时是有效的,但是在算法初始阶段,即到目的节
6、点的时延与给定的时延上限还相差很远时,所建组播树的代价并不一定优于QDMR。 在以上所述的三种算法的基础上,本文提出一种新的具有时延约束的组播路由算法,即DCMA。 1 问题定义 具有时延约束的组播路由问题,本章给出数学描述。 用赋权图G=(V,E)来表示网络。其中:V是网络节点的集合,每个节点表示主机或路由器;E为连接网络节点的通信链路的集合。在每条链路e=(u, v)E上定义两个权值函数:a)链路代价函数C(e):ER+,表示每条链路的费用(这里的费用是一个广义的费用,它可以根据有关链路的各种因素定义);b)链路时延函数D(e):ER+,链路时延为数据包经过链路的度量,包括排队、发送和传输
7、时延等。 对图G,给定一个源节点sV和目的节点集合D,DV-s称为组播组成员。给定一个时延上限,即为从源节点到任一目的节点所允许的时延上限。假定从源节点到目的节点的路径为P(s, v),则时延受限Steiner树问题就是要寻找一棵覆盖给定目的节点集合D且费用最小的满足时延约束的最优Steiner树T=(VT,ET),其中DVTV,ETE,即考虑下述优化问题: mineTC(e) eP(s,v)D(e)?沪?vD 构建最小代价树问题可形式化为图论中的Steiner树问题的求解,后者已经证明是一个NP完全问题5,即不可能在多项式时间内求得其精确解。在可接受的计算时间内,只能计算得到一棵近似的最优组
8、播树,而不可能获得真正意义上的最优组播树。 2 MST-SPT算法的结合 Prim的最小生成树(MST)算法最小化了图中生成树的费用,但可能会导致比最优树更大的路径费用(路径费用指的是树中源节点到单个目的节点路径的最大费用);相对的,SPT只是最小化了路径费用但是可能会引起更大的开销3。因此这两种经典算法一般并不直接用于组播建树。 AHHK算法通过利用一个值在(0,1)区间的指示函数结合了这两种经典算法。如文献3所述,当AHHK算法中指示函数的值增加时,它所建立的树有着更高的总体开销和更小的路径费用;当指示函数是0时,AHHK与Prim算法是一样的,建立的树是最小开销;当指示函数是1时,AHH
9、K与Dijkstra算法一样,最小化了路径费用。 文献2指出,当指示函数的值在(0,1/2)时,此时得到的树代价较低,路径费用较大,相比起(1/2,1)区域内所得的树更为可取。在本文所提算法中,将指示函数ID(u)控制在(0,1/2)的区间内,保证所获得组播树的低代价。 3 算法描述 3.1 指示函数 DDMC4是一种无约束的建立低代价组播树的算法,它定义了一个新加入节点vT经由节点uT的开销: cost(v)=ID(u)cost(u)+c(u,v) 其中:cost(v)是从源节点s到新加入节点v的路径的总费用,c(u,v)是从节点u到节点v的费用。 指示函数ID(u)定义如下: ID(u)=
10、 0 当uD 1 其他 其中:D是目的节点集合。 如上式所示,当添加新节点连到树T时,通过目的节点的路径优先级更高,但是这可能导致组播树更像是目的节点的一条链,会使某些目的节点违反时延约束。 时延约束算法QDMR修改了DDMC算法,通过检查源节点到目的节点的时延与时延上限之间的比值大小来动态地调整树。那些离时延上限越远的目的节点,作为其他新加入的节点的父节点的可能性越高。如果对某些目的节点而言,时延约束将要违反,那么会生成多分支树将这些节点连入。 QDMR算法的指示函数如下: ID(u)=delay(u)/?A 当uD1其他 其中:delay(u)是指树T中从源节点s到节点u的所有链路时延的总
11、和,是给定的时延上限。QDMR的指示函数有个很大的缺点,那就是只有delay(u)远远小于时延上限时才会有效2。当delay(u)越接近,它对目的节点和非目的节点的区分就越小,越无法提高链路的共享性,使得组播树的代价偏大。 文献2中所提的EPDT算法对QDMR的这个缺点作了改进。该算法的指示函数是: ID(u,v)=delay(u)/(delay(v)+delay(u)?A当uD1其他 从该式可以看出,当delay(u)/的值大于1/2时,即delay(u)接近时延上限时,delay(v)+delay(u)的值一定大于,同时还一定大于delay(u)的2倍,此时所建的组播树比QDMR更有效。但
12、是算法初始时, 即delay(u)/的值小于1/2时,delay(v)+delay(u)的值与的大小关系无法判定,此时比起QDMR,它所建树的开销反而可能更大。而且EPDT算法的指示函数给予了链路时延(即delay(v)大的目的节点更高的优先级,这是不合理的。因为这会导致新选择加入的节点到源节点的时延偏大、剩余时延偏小,选路受到的限制更多。所以笔者发现EPDT算法并不能保证它所建的树的性能一定优于QDMR 。因此,文献2中的EPDT所建树的代价小于QDMR的定理并不成立。 为了在初始阶段及树的边界阶段使得算法所建的树都具有较低的开销,本文提出的指示函数如下: ID(u)=delay(u)/(+
13、delay(u)?A 当uD1其他 显而易见,对于任何目的节点uD,指示函数ID(u)均满足:ID(u)1/2。 DCMA的指示函数ID(u)1/2,也就是说它符合文献2中的指示函数在(0,1/2)区间的条件,能够得到代价较低的树。这是更可取的。 定理1 与QDMR算法相比,DCMA算法所建立的组播树的代价更小。 证明 按照文献2,3所述,指示函数值越小,所产生的费用就越少;随着指示函数值的增加,算法AHHK建的组播树的费用将会增加,路径费用将会减少。本文所提算法和QDMR算法的指示函数值都是ID(u)。因此,为了证明定理1,实际需要证明的就是ID(u)QDMR?邯?ID(u)DCMA 。即 delay(u)/Delay(u)/(+delay(u) 很明显+delay(u)?邯?,定理1得证。 证明DCMA算法所建立的组播树代价小于EPDT算法的方法同上。该证明方法与文献2类似。 3.2 链路选择函数 对于时延受限问题,为无约束问题设计的DDMC算法,它只考虑了优化费用而没有考虑时延约束,会导致许多源节点到目的节点的路径不满足时延上限。QDMR指示函数只考虑了时延上限,未考虑加入树的节点的剩余时延。而且EPDT和QDMR只是直接考虑费用累加最小,在本文中将时延和费用进行折中。对此,