改进的时延约束Steiner树算法

徐剑 1; 2; 倪宏 2; 邓浩江 2; 刘磊 2

doi:10.7652/xjtuxb201308007

您当前的位置：

首页 >

文章列表页 >

改进的时延约束Steiner树算法

更新时间：2025-05-08

- 改进的时延约束Steiner树算法
- An Advanced Algorithm for Delay-Constrained Steiner Tree
- 西安交通大学学报 2013年47卷第8期页码：38-43
- 作者机构：
  
  1. 中国科学院大学,北京,100049
  2. 中国科学院声学研究所国家网络新媒体工程技术研究中心,北京,100190
- 作者简介：
- 基金信息：
  
  : 2012-09-28。作者简介: 徐剑(1985—),男,博士生;倪宏(通信作者),男,研究员,博士生导师。基金项目: 国家高技术研究发展计划资助项目(2011AA01A102);国家科技支撑计划资助项目(2011BAH11B04);中国科学院战略性先导科技专项子课题(XDA06010302)
- DOI：10.7652/xjtuxb201308007
  中图分类号： TP393
- 网络首发：2013-08-10，
  
  纸质出版：2013
- 稿件说明：
移动端阅览
徐剑 1, 2, 倪宏 2, 等. 改进的时延约束Steiner树算法[J]. 西安交通大学学报, 2013,47(8):38-43.

An Advanced Algorithm for Delay-Constrained Steiner Tree[J]. 2013, 47(8): 38-43.
徐剑 1, 2, 倪宏 2, 等. 改进的时延约束Steiner树算法[J]. 西安交通大学学报, 2013,47(8):38-43. DOI： 10.7652/xjtuxb201308007.

An Advanced Algorithm for Delay-Constrained Steiner Tree[J]. 2013, 47(8): 38-43. DOI： 10.7652/xjtuxb201308007.

摘要

针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题

提出了一种改进的时延约束Steiner树算法。该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法

在快速搜索阶段

依次搜索到当前树有最小可行代价的节点

将目的节点通过最小可行代价路径加入组播树; 在异常处理阶段

将遗漏的目的节点通过最小时延路径加入组播树

进而生成满足时延约束的Steiner树。理论分析和实验结果表明

与同类算法相比

该算法能够以较低的时间复杂度

取得较好的组播树代价。

Abstract

An advanced algorithm for delay-constrained Steiner tree is proposed to focus on the problem that the existing delay-constrained Steiner tree algorithms usually lead to high multicast cost and high time complexity. The proposed algorithm adopts the idea of path increasing in Dijkstra algorithm and the method of link sharing. It iteratively searches the node with the least feasible cost to the current tree and adds the destination node to the current tree through its feasible least cost path in the fast search stage. The missing destination nodes are added to the current tree through its least delay path in the exception handling stage of the algorithm. The delay-constrained Steiner tree is constructed through these two stages of the algorithm. Theoretical analysis

experimental results and comparisons with similar algorithms show that the proposed algorithm can construct multicast tree in lower cost and time complexity.

关键词

Keywords

references

DEERING S E, CHERITON D R. Multicast routing in a datagram internetworks and extended LANs [J]. ACM Transactions on Computer Systems, 1990,8(2):85-110.

SHI S Y, TURNER J S. Multicast routing and bandwidth dimensioning in overlay networks [J]. IEEE Journal on Selected Areas in Communications, 2002,20(8):1444-1455.

BANERJEE S, KOMMAREDDY C, KAR K, et al. Construction of an efficient overlay multicast infrastructure for real-time applications [C]∥IEEE International Conference on Computer Communications. Piscataway,NJ,USA:IEEE, 2003:1521-1531.

WINTER P. Steiner problem in networks: a survey [J]. Networks, 1987,17(2):129-167.

HWANG F K, RICHARDS D S. Steiner tree problems [J]. Networks, 1992,22(1):55-89.

KOMPELLA C S, PASQUALE J C, POLYZOS G C. Multicasting for multimedia applications [C]∥IEEE International Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 1992:2078-2085.

ZHU Q, PARSA M, GARCIA-LUNA-ACEVES J J. A source-based algorithm for delay-constrained minimum-cost multicasting [C]∥IEEE International Conference on Computer Communications. Piscataway, NJ, USA: IEEE, 1995:377-385.

SALAMA H F, REEVES D S, VINIOTIS Y. Evaluation of multicast routing algorithms for real-time communication on high-speed networks [J]. IEEE Journal on Selected Areas in Communications, 1997,15(3):332-345.

周灵,孙亚民. 基于MPH的时延约束Steiner树算法 [J]. 计算机研究与发展, 2008,45(5):810-816.

ZHOU Ling, SUN Yamin. A delay-constrained Steiner tree algorithm using MPH [J]. Journal of Computer Research and Development, 2008,45(5):810-816.

CHEN Shigang, SONG M, SAHNI S. Two techniques for fast computation of constrained shortest paths [J]. IEEE/ACM Transactions on Networking, 2008,16(1):105-115.

WAXMAN B M. Routing of multipoint connections [J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617 -1622.

汪志伟,曹建福,郑辑光. 一种面向分簇无线传感器网络的多信道跨层协议. 2013, 47(6): 61-67.[doi:10.7652/xjtuxb 201306011]

李琳琪,杨新宇,刘蔚.高动态网络的自决策式地理机会主义路由. 2013, 47(2):7-13. [doi:10.7652/xjtuxb201302 002]

夏秦,王志文,卢柯.入侵检测系统利用信息熵检测网络攻击的方法, 2013, 47(2): 14-19. [doi:10.7652/xjtuxb2013 02003]

温彦,刘晨,韩燕波.一种用户主导的跨组织数据按需集成方法, 2013, 47(2): 116-123. [doi:10.7652/xjtuxb201302 020]

张赛,徐恪,李海涛.微博类社交网络中信息传播的测量与分析, 2013, 47(2): 124-130. [doi:10.7652/xjtuxb201302 021]

陈国强,王宇平.采用离散粒子群算法的复杂网络重叠社团检测, 2013, 47(1): 107-113. [doi:10.7652/xjtuxb2013 01021]

盖炳帅,王劲林,刘学.采用Petri网的业务性能分析方. 2012, 46(12):12-17. [doi:10.7652/xjtuxb201212003]

伍文,孟相如,马志强,等.模块化动态博弈的网络可生存性态势跟踪方法. 2012, 46(12): 18-23. [doi:10.7652/xjtuxb 201212004]

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种修复网络拓扑的Steiner树移动控制算法

EBSILON软件在热电联产系统优化中的应用综述

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

离子液体改性燃料的电流体动力学效应研究

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究