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

An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem

作　　者：崔勇[1] 徐恪[1] 吴建平[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《电子学报》2002年第12A期1968-1972,共5页Acta Electronica Sinica

基　　金：国家"八六三"项目(No.2002AA103067);国家自然科学基金(No.69725003;90104002)

摘　　要：作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.由于QoSR具有NPC的复杂度,为此我们结合线性、非线性能量函数将多个Qos度量转化成单一能量值,设计了可调节的启发式算法BFS_MCP.该算法将深度可调的广度优先搜索策略引入传统Dijkstra算法中,使它能够随路由器CPU负载和实际网络规模而实时调节算法的运行时间,因而BFS-MCP算法具有广泛的适应性.此外,广泛深入的实验结果表明,广度优先的搜索策略能够极大地提高算法性能.As a challenging problem of the upcoming next-generation networks, multi-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 router in real time. Therefore, it has an extensive adaptability. Furthermore, extensive simulations show that the breadth-first search increases the performance greatly.

关 键 词：能量函数 QOS路由 可调算法 多约束 服务质量 互联网 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]