论文部分内容阅读
多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。
Multi-constrained QoS routing optimization is an important issue in the current network research. Restricted shortest-path problem (RSP) is a basic problem of QoS routing. It is NP-complete and has many heuristic solver algorithms with polynomial time and pseudo-polynomial time. However, these methods can only solve some RSPs with linear constraints. For some non-linear constraints (such as loss rate constraints) are mostly solved mathematically into linear constraints, which increases the complexity of the problem. In this paper, a new heuristic algorithm with pseudo-polynomial time is proposed to solve this type of RSP with nonlinear constraints. The main idea is to use non-linear constraints as test conditions. When each solution gets a solution, check if the solution satisfies the nonlinear constraint. If satisfied, the final solution is obtained; otherwise, a linear constraint is added to the original problem. The new constraint will remove the solution that has been found so that the solution space of the original problem will be further reduced until the final solution is obtained. The simulation example shows the effectiveness of the algorithm.