Ad Hoc网络中基于多条件的最优路径选择

Multi-Constrained Optimal Path Selection in Ad Hoc Network

在无线移动Ad Hoc网络(mobile Ad Hoc network,简称MANET)中,提供端到端QoS保证的关键问题之一是确定一条可行的、满足一组QoS(如带宽、延迟抖动和丢失率)约束的路径。一般说来,寻找一条满足多个附加约束条件路径的问题,是NP完全问题,这导致了许多启发式算法的提出。本文提出了一种在Ad hoc网络中基于启发式多条件约束的最优路径选择算法MCOPS(Multi-Constrained Optimal Path Selection),此算法首先裁减掉那些从源节点到目的节点不可行的路径,然后,在每条可行路径上使用K+1次Reverse-Dijkstra算法,随后,在图上随机地移动,发现那些到达最终目的结点的机会较大的结点。MCOPS算法由于是利用局部状态信息分布地计算,使其可方便地进行扩展到其他QoS约束的路由问题。仿真实验结果表明,该算法能够以较小的代价开销获得较高的路由成功率。

One of the key issues in providing end-to-end Quality-of-Service（QoS）guarantees in mobile Ad Hoe network is how to determine a feasible route that satisfies a set of QoS requirements（such as bandwith, delay, delay-jitter, and loss） of a connection request. In general, finding a path subject to multiple constraints such as delay and dela-jitter is a NP-complete problem. Multiple constrained QoS routing optimization is an important problem in the curren Ad Hoe communication network research. in this paper,we propose heuristic MCOPS （Multi-Constrained Optimal Path Selection） for this problem, the algorithm first prunes all the links that cannot be on any feasible path from resource to destination, it then uses a randomized search to find a feasible path, in order to achieve efficient utilization of network resources, the algorithm tries to select a path with minimum-de- lay among all feasible paths. Simulation results show that MCZ）PS algorithm performs much better than the Jaffe routing algorithm under the circumstances of mobile Ad Hoe networks.