基于局部信息的时延和时延差约束的组播路由  

Delay and delay-variation bounded multicast routing algorithm based on local information

作　　者：刘维群[1] 李元臣[1] 

机构地区：[1]洛阳师范学院信息技术学院,河南洛阳471022

出　　处：《计算机工程与应用》2012年第34期76-80,共5页Computer Engineering and Applications

基　　金：河南省科技攻关项目(No.102102210467;No.112102310527);河南省自然科学基金资助项目(No.2008B520027)

摘　　要：组播通信是从一个源节点同时向网络中的多个目的节点发送分组的通信服务,它一般提供一个以上的端到端的服务约束,实际的路由算法在应用时可以受到多重约束,解决这类问题的组播路由算法是NP完全的。在研究了构建组播树的相关算法后,提出了一种新的时延和时延差约束的低代价组播路由算法—DDVMC。该算法采用基于贪婪策略的Dijkstra最小生成树算法,利用局部信息来构建低代价组播树,很好地平衡了树的代价、时延和时延差。仿真表明,该算法能正确地构造出满足约束的组播树,同时还具有较低的代价和计算复杂度。Multicasting is a communication service that allows a source to efficiently transmit copies of data packet to destination nodes for meeting end-to-end QoS （Quality of Service） requirements of real-time applications and its algorithm must be NP-completeness. QoS provisioning generally assumes more than one QoS measure which implies that a routing algorithm may have multiple constraints： delay, delay-variation and cost, etc. After research of related algorithm for constructing the multicast tree, a delay and delay-variation bounded minimum cost multicast routing algorithm （DDVMC） is proposed in this paper. The DDVMC algorithm uses a greedy strategy based on Dijkstra minimal spanning trees and local information to construct lower cost multicast tree. Furthermore, this algorithm offers a good balance between tree cost, delay and delay-variation. Simulation results show that this algorithm not only can construct constrained multicast tree correctly, but also has a less cost and a lower computational complexity.

关 键 词：组播通信 局部信息 Dijkstra最小生成树 端到端服务质量 STEINER树 

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