Reverse Optimization Algorithm for QoS Routing Problem
QoS路由问题的反向优化算法

Finding the path satisfying two additive QoS constraints is the key question of QoS research. The linear search algorithm is one of important approximation algorithms. This paper proposes a new linear search algorithm combined with the reverse optimization scheme. If the path found by the linear search procedure does not satisfy the QoS constraints, the proper nodes of the path are chosen to make the reverse optimization. The time complexity of proposed algorithm is O(K(m nlog2(n))). The simulation shows that the new approach extends the search fields and improves the succeeding ratio of finding the feasible paths.