基于宽度优先搜索的性能可调启发式服务质量路由方法

摘要

基于宽度优先搜索的性能可调启发式服务质量路由方法属于互联网路由技术领域，其特征在于：在向计算机输入服务质量请求的各项参数后，以目的节点为树根基于线性能量函数用Dijkstra算法建立反向最短路径树，计算反向最短路径树各节点至目的节点的k重权值并据此对所有节点反向标号；最后基于非线性能量函数用Dijkstra算法计算正向最短路径树，在把一个节点加入到该树时，需要考虑其搜索深度H以内的所有子节点(含父节点)是否最优，判断从源节点到达该节点的路径是否满足约束条件：满足则成功返回该路径，否则返回路径计算失败。随着约束个数增加，只要增加搜索深度，依然能保持很高的性能，而且同时对网络规模具有良好的可扩展性。

主权项

1.基于宽度优先搜索的性能可调启发式服务质量路由方法，其特征在于，它依次含有以下步骤：(1)向计算机输入：宽度优先搜索深度H、网络拓扑图G、服务质量请求的源节点和目的节点对(s，t)，各链路的k重度量值即权值以及k重约束向量c＝(c1，c2，…，ck)；(2)以连接请求的目的节点t作为树根，基于线性能量函数$g_{\lambda =1}\left(p\right)={\Sigma }_{l=1}^k{w}_l\left(p\right)/c_l,$ 使用反向Dijkstra算法建立反向最短路径树SPT，其中1≤l≤k而wl(p)是链路具有k重度量时路径p的度量值；(3)计算反向最短路径树上各个节点的各自到达目的节点t的k重度量值即权值，再根据这些k重权值对所有节点进行反向标号；(4)基于非线性能量函数$g_{\lambda =\infty }\left(p\right)={\max }_{l=1}^k{w}_l\left(p\right)/c_l,$ 用Dijkstra算法计算正向最短路径树，在将一个节点加入到正向最短路径树时要考虑其搜索深度H以内的子节点是否最优；(5)判断沿着正向最短路径树，从源节点s到目的节点t的路径的度量值是否满足约束条件c：如果满足，则成功返回该路径；否则返回路径计算失败。