An Advanced Algorithm for Delay-Constrained Steiner Tree

doi:10.7652/xjtuxb201308007

您当前的位置：

首页 >

文章列表页 >

An Advanced Algorithm for Delay-Constrained Steiner Tree

更新时间：2025-05-08

- An Advanced Algorithm for Delay-Constrained Steiner Tree
- Vol. 47, Issue 8, Pages: 38-43(2013)
- 作者机构：
  
  1. 中国科学院大学,北京,100049
  2. 中国科学院声学研究所国家网络新媒体工程技术研究中心,北京,100190
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201308007
  CLC： TP393
- Online First：10 August 2013，
  
  Published：2013
- 稿件说明：
移动端阅览
An Advanced Algorithm for Delay-Constrained Steiner Tree[J]. 2013, 47(8): 38-43.
DOI：

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]

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Steiner Tree Movement Control Algorithm for Topology Recovery

Effects of Expansion Angle Crater Film Hole on the Film Cooling Characteristics of a Double-Wall Structure

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

Turbulent Kinetic Energy Dissipation Mechanism of Supercritical Carbon Dioxide Leakage Flow in a Scallop Bionic Seal Cavity

Mechanism and Optimal Control Strategy for Hysteresis in Rapid Dehumidification Response of Indirect Thermal Systems in Electric Vehicles

Related Author

闫中江

沈中

常义林

张颖

代亮

Related Institution

State Key Laboratory of Integrated Service Networks, Xidian University

⁰