性能可调的启发式多约束路由算法

崔勇; 徐恪; 吴建平

您当前的位置：

首页 >

文章列表页 >

性能可调的启发式多约束路由算法

学术论文 | 更新时间：2025-07-16

- 性能可调的启发式多约束路由算法
- An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem
- 电子学报 2002年30卷第S1期页码：1968-1972
- 作者机构：
  
  清华大学计算机科学与技术系,北京,100084
- 作者简介：
- 基金信息：
  
  国家“八六三”项目 (No.2002AA103067);国家自然科学基金 (No.69725003,90104002)
- DOI：
  中图分类号： TP393.01
- 纸质出版：2002
- 稿件说明：
移动端阅览
崔勇, 徐恪, 吴建平. 性能可调的启发式多约束路由算法[J]. 电子学报, 2002,30(S1):1968-1972.

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.
崔勇, 徐恪, 吴建平. 性能可调的启发式多约束路由算法[J]. 电子学报, 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

浏览量

1160

下载量

CSCD

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

提交

工具集

关联资源

基于链路状态的多约束路由预计算算法

基于高可靠性的重负载Ⅰ类双星网络性能评价的数学建模

基于距离向量深度的多约束路径选择算法