CAJ | 학술논문

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优．该问题是一个NP一完全问题．提出了一种新的基于整数线性规划模型选择路由的方法．思路是将复杂约束引入到目标函数作为罚项，得到一个松弛整数线性规划问题．因为约束系数矩阵是全幺模矩阵，松弛问题可以通过线性规划很快地求解．拉格朗日乘子的调整用罚函数的方法很容易计算．数值实验表明提出的方法是有效的．
QoS로유적임무시재망락중심조일조만족다개약속조건적로경사망락자원적이용체도최우．해문제시일개NP일완전문제．제출료일충신적기우정수선성규화모형선택로유적방법．사로시장복잡약속인입도목표함수작위벌항，득도일개송이정수선성규화문제．인위약속계수구진시전요모구진，송이문제가이통과선성규화흔쾌지구해．랍격랑일승자적조정용벌함수적방법흔용역계산．수치실험표명제출적방법시유효적．
The task of quality of service （QoS） routing is to find a route in the network that satisfies a set of constraints while maintaining high utilization of network resources. It is well-known that this problem is NP-complete. In this paper, a new method of integer linear program model for QoS routing problem was proposed. The idea is to include complicating constraints in the objective function with the ＂penalty＂ term, and then obtain the Lagrangian relaxation integer linear problem. For the constraint matrix is totally unimodular, the relaxation can be solved rapidly from a linear program. Updating of Lagrangian multipliers are calculated easily by penalty function method. Numerical computational results indicate that the proposed method is effect.