QoS约束下的链路分离路径问题研究  

Researches on the problem of link disjoint paths pair with QoS constraints

作　　者：张品[1] 章坚武[1] 李乐民[2] 王晟[2] 

机构地区：[1]杭州电子科技大学通信学院,浙江杭州310018 [2]电子科技大学光纤通信重点实验室,四川成都610054

出　　处：《通信学报》2006年第6期36-42,共7页Journal on Communications

基　　金：国家自然科学基金资助项目(60472008);浙江省自然科学基金资助项目(R105473)~~

摘　　要：研究了QoS约束下的链路分离路径问题,建立了2种QoS约束下的链路分离优化路径问题的模型。首先证明无向图的不具备端到端QoS约束的链路分离路径问题可以转化为其链路分裂图的对应问题,而具备端到端QoS约束的相应问题则无法进行类似转换。同时证明2种QoS约束下的链路分离优化路径问题都属于NP完全问题,最后对其近似算法进行研究并对算法进行比较测试。The problem of link disjoint paths pair with QoS constraints was discussed. Two routing models about link disjoint optimal paths pair with QoS constraints were constructed. First it proved that the problem of link disjoint paths pair in the undirected graph without end to end QoS constraints counld be converted to the correspond problem in its link split graph, while the problem with end to end QoS constraints counld not be converted. Then it＇s proved that both of these questions are NP complete. Finally the approximation algorithms is given and simulation on them is made.

关 键 词：链路分离路径 QOS约束 链路分裂图 

分 类 号：TN915.01[电子电信—通信与信息系统]