An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem

CUI Yong; XU Ke; WU Jian-ping

您当前的位置：

首页 >

文章列表页 >

An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem

更新时间：2025-07-16

- An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem
- Acta Electronica Sinica Vol. 30, Issue S1, Pages: 1968-1972(2002)
- 作者机构：
  
  清华大学计算机科学与技术系,北京,100084
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393.01
- Published：2002
- 稿件说明：
移动端阅览
CUI Yong, XU Ke, WU Jian-ping. An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem[J]. Acta Electronica Sinica, 2002, 30(S1): 1968-1972.
DOI：

CUI Yong, XU Ke, WU Jian-ping. An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem[J]. Acta Electronica Sinica, 2002, 30(S1): 1968-1972. DOI：

摘要

作为下一代互联网的核心问题之一

多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.由于QoSR具有NPC的复杂度

为此我们结合线性、非线性能量函数将多个Qos度量转化成单一能量值

设计了可调节的启发式算法BFS_MCP.该算法将深度可调的广度优先搜索策略引入传统Dijkstra算法中

使它能够随路由器CPU负载和实际网络规模而实时调节算法的运行时间

因而BFS-MCP算法具有广泛的适应性.此外

广泛深入的实验结果表明

广度优先的搜索策略能够极大地提高算法性能.

Abstract

As a challenging problem of the upcoming next-generation networks

mufti-constrained quality-of-service routing (QoSR) is to find a feasible path satisfying multiple constraints simultaneously. For the NP complete complexity of QoSR

we propose an adjustable heuristic BFS-MCP based on converting multiple weights to a single metric with linear and non-linear energy functions. Bringing the breadth-first search with the adjustable depth to the standard Dijkstra's algorithm

BFS_MCP can adjust its computation complexity according to the CPU load on a muter in real time. Therefore

it has an extensive adaptability. Furthermore

extensive simulations show that the breadth-first search increases the performance greatly.

关键词

Keywords

references

Views

1160

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Link State-Based Precomputation for Multi-Constrained Routing

Mathematical Modeling Based on Performance Evaluation of Type Ⅰ High Reliable and Heavy Load Double-Star Network

Multi-Constrained Path Selection Algorithm Based on the Depth of the Distance Vector

Related Author

QI Xiao-gang

LIU San-yang

CUI Yong

XU Ke

LU Zhao-yi

SUN Li-jun

LIU Fei

QI Xiao-gang

Related Institution

Department of Applied Mathematics,Xidian University

School of Information EngineeringQingdao UniversityQingdaoShandong 266071China

China Merchants Securities Co.LTDQingdao branchQingdaoShandong 266555China

School of Information Science and TechnologyQingdao University of Science and TechnologyQingdaoShandong 266061China

School of Information Engineering, Qingdao University

⁰