An efficient QoS routing algorithm for solving MCP in ad hoc networks |
| |
Authors: | Noureddine Kettaf Hafid Abouaissa Thang Vu duong Pascal Lorenz |
| |
Affiliation: | (1) Haute Alsace University, 34 rue de Grillenbreit, 68008 Colmar,Cedex, France;(2) France Telecom R&D, 2, avenue Pierre Marzin, 22307 Lannion, Cedex, France |
| |
Abstract: | Providing guaranteed quality of service (QoS) in wireless networks is a key issue for deploying multimedia applications. To
support such a QoS, an arduous problem concerning how to find a feasible end to end path to satisfy multiple QoS constraints
should be studied. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that
cannot be exactly solved in polynomial time. Approximation algorithms and heuristics with polynomial and pseudo-polynomial
time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational
complexities that cannot be used for multimedia applications in ad hoc networks characterized by mobility and performance
constraints (e.g., limited energy, wireless medium, etc.). Recently a promising heuristic algorithm H_MCOP using a non linear
Lagrange relaxation path functions has demonstrated an improvement in its success rate and in finding feasible paths. However,
the H_MCOP is not suitable for ad hoc networks and has not exploited the full capability that a Lagrange relaxation could
offer. In this paper, we propose an efficient multi-constrained path heuristic called E_MCP, which exploits efficiently the
Lagrange relaxation and enhances the path search process to be adequate to mobile ad hoc networks. Using extensive simulations
on random mobile network with correlated and uncorrelated link weights, we show that the same level of computational complexity,
E_MCP can achieve a higher success ratio of finding feasible paths. |
| |
Keywords: | Multiple constraints Path selection QoS routing Ad hoc |
本文献已被 SpringerLink 等数据库收录! |
|