一个有效的时延约束最小代价多播路由算法  

An Effective Delay Constrained and Minimum Cost Multicast Routing Algorithm

作　　者：陈月云[1] 刘亲亲[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《空军工程大学学报（自然科学版）》2011年第3期68-72,共5页Journal of Air Force Engineering University(Natural Science Edition)

基　　金：北京市自然科学基金资助项目(4102041);博士后专项基金资助项目(20090006110014)

摘　　要：基于时延约束多播路由问题考虑链路代价,提出一种新的时延约束最小代价路径(DCM-CA)算法,作为搜寻节点间最短路径的算法;在此基础上又改进了基于代价-时延比率(CDR)函数的有效中心节点选择算法;基于CBT树,应用上述2种算法提出一种基于中心选择的时延约束最小代价多播路由(CS-DCMCMR)算法,该算法在搜寻路径和中心节点选择的问题上同时考虑路径的时延和代价。仿真证明CS-DCMCMR算法的时间复杂度为O(mlogn),与CSDVC算法和CCLDA算法相比,该算法在没有增加复杂度和满足时延及时延抖动约束的条件下,较大程度地减小了最终多播树的总代价。Based on the problem of considering the link cost into delay constraint,this paper proposes a new delay constrained minimum cost path algorithm（DCMC） which is used for searching the shortest path between nodes.On this basis,an efficient center node selection method is further modified based on the cost-delay ratio（CDR）.Based on application of CBT a center selection for delay constrained minimum cost multicast routing（CS_DCMCMR） algorithm is proposed by using the above two algorithms.In the use of this algorithm,both cost and delay are taken into consideration simultaneously in path search and central node selection.The simulation results show that the time complexity of CS_DCMCMR algorithm is O（mlogn）,compared with CSDVC and CCLDA algorithms,the use of this algorithm can largely reduce the total cost of the final multicast tree in the case of meeting delay and delay variation constraints without the increase of complexity.

关 键 词：时延 时延抖动 多播树 最小代价 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]