|
|||||
|
|
| 一种求解QoS路由问题的半定规划算法 | |
| 引用本文： | 张亚玲,穆学文,龙熙华,焉琴.一种求解QoS路由问题的半定规划算法[J].西安科技大学学报,2007,27(1):108-111. |
| 作者姓名： | 张亚玲 穆学文 龙熙华 焉琴 |
| 作者单位： | 1. 西安科技大学,计算机科学系,陕西,西安,710054 2. 西安电子科技大学,应用数学系,陕西,西安,710071 3. 青岛市计划生育药具管理站,山东,青岛,266071 |
| 摘 要： | QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题。由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点。本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题。把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性。 |
| 关 键 词： | QoS路由 数学模型 半定规划 |
| 文章编号： | 1672-9315(2007)01-0108-03 |
| 修稿时间： | 2005年11月23 |
A semidefinite programming algorithm for QoS routing problem |
|
| ZHANG Ya-ling,MU Xue-wen,LONG Xi-hua,YAN Qin.A semidefinite programming algorithm for QoS routing problem[J].JOurnal of XI’an University of Science and Technology,2007,27(1):108-111. | |
| Authors: | ZHANG Ya-ling MU Xue-wen LONG Xi-hua YAN Qin |
| Abstract: | The basic problem of QoS routing is an optimal problem satisfying multi-constrained conditions from source node to destination.The semidefinite programming have the advantage of faster convergence and fewer iteration in solving the combinational optimization problems and NP-complete problems.Based on the linear integral network model of QoS routing,the minimal price problem with time delay constraints is researched by the semidefinte programming method.The linear integral network model of QoS routing is relaxed the basic semidefinite programming,and then,we solve it by the inner-point method.Coupled with randomized method,we obtain the suboptimal solution.The simulations show the efficiency of the algorithm. |
| Keywords: | QoS routing mathematic model semidefinite programming |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |