一种基于K最短路径的QoS路由选择算法  

Selection Algorithm for QoS Routing Based on K-shortest Paths

作　　者：齐小刚[1] 刘三阳[1] 

机构地区：[1]西安电子科技大学应用数学系,西安710071

出　　处：《吉林大学学报（工学版）》2005年第5期526-530,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金资助项目(69972036);教育部跨世纪优秀人才培养基金(2002);陕西省自然科学基金资助项目(2004A02).

摘　　要：针对多约束服务质量路由问题,提出了一种基于K最短路径路由选择算法QRBKP。该算法首先计算针对各约束度量参数的K最短路径,然后在所有的最短路径中选择满足多约束的QoS路由,其中最短路径数k根据各QoS约束自适应变化。基于此,本文提出了节点对之间的路由空间再分配技术和节点对内部的路由空间再分配技术,确保总的路由表空间不会超过设计路由空间。理论分析表明,QRBKP不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题。仿真结果表明:在求解QoS路由问题时,在相同的计算次数下,QRBKP算法比同类算法具有更高的路由计算成功率。Facing the problem of multiple constraint Quality of Service Routing （QoSR）, a novel selection algorithm based on K shortest paths, QRBKP, was proposed. This algorithm calculated the K shortest paths first according to each constraint parameter. Then the QoSR satisfying multiple constraints was selected among all shortest paths with the value of k changing adaptively to the QoS constraints. Both intra-node-pair reassignment method and inter-node-pair reassignment method were proposed to assure the routing table space not out of the range of designed routing table space. Theoretical analysis shows QRBKP can solve QoSR not only with additive constraint parameters, but also with non-additive constraint parameters. Simulation results show that the routing computational success ratio of QRBKP is higher than that of current algorithms in solving QoSR under the same computational time.

关 键 词：计算机系统结构 服务质量(QoS) 多约束 QOS路由 K最短路径 NP完全 

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