[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An efficient QoS routing algorithm for solving MCP in ad hoc networks

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. T. Korkmaz and M. Krunz, Multi-constrained optimal path selection, in: INFOCOM (2001) pp. 834–843.

  2. N. Kettaf et al., Admission Control enables Routing Protocol -ACOR- Internet draft, IETF, (draft-kettaf-manet-acor-00.txt), July 2006, (Work in progress).

  3. A. Alles, ATM internetworking, White Paper, Cisco Systems, Inc., (May, 1995).

  4. Z. Wang, On the complexity of quality of service routing, Information Processing Letters 69(3) (1999) 111–114.

    Article  Google Scholar 

  5. Z. Wang and J. Crowcroft, Bandwidth-delay based routing algorithms, in: Proceedings of the GLOBECOM ’95 Conference. IEEE, (1995) Vol. 3, pp. 2129–2133.

  6. D.H. Lorenz, A. Orda, D. Raz and Y. Shavitt, Efficient QoS partition and routing of unicast and multicast, in: IWQoS 2000, (June 2000) pp. 75–83.

  7. M.V. Jean-Yves Le Boudec, Perfect simulation and stationarity of a class of mobility models, INFOCOM (2005) pp. 834–843.

  8. B. Szviatovszki et al., Lagrange relaxation based method for the qos routing problem, INFOCOM (2001) pp. 782–791.

  9. D.S. Reeves, et al., A distributed algorithm for delay-constrained unicast routing, IEEE/ACM Transactions on Networking 8(2) (2000) 230–250.

    Article  Google Scholar 

  10. F. Gang and M. Kia, An efficient approximate algorithm for delay-cost-constrained qos routing. International Conference on Computer Communications and Networks (ICCCN’01) (2001) p. 395.

  11. G. Cheng, Y. Tian, A new qos routing framework for solving MCP, IEICE Transaction on Communications, E86-B(2) (2003) 534–541.

  12. R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, New Jersey, 1993).

    Google Scholar 

  13. S.D. Patek, R. Venkateswaran and J. Liebeherr, Simple alternate routing for differentiated services networks, Computer Networks 37 (2001) 447–466.

    Article  Google Scholar 

  14. W.C. Lee, M.G. Hluchyi and P.A. Humblet, Routing subject to quality of service constraints in integrated communication networks, in: IEEE Network (July/August 1995) pp. 46–55.

  15. E.I. Chong, S.R. Sanjeev Rao Maddila and S.T. Morley, On finding single-source single-destination k- shortest paths, in: the Seventh International Conference on Computing and Information (ICCI ’95), (July:1995) pp. 40–47.

  16. J. Jaffe, Algorithms for finding paths with multiple constraints, Networks 14(1) (1984) 95–116.

    Google Scholar 

  17. S. Chen and K. Nahrstedt, On finding multi-constrained paths, in: Proc. IEEE ICC’98 (1998) pp. 874–879.

  18. D. Bertsekas and R. Gallager, Data Networks, 2nd edn, (Prentice-Hall, 1992).

  19. T. Korkmaz and M. Krunz, A randomized algorithm for finding a path subject to multiple QoS constraints, in: Proc. IEEE GLOBECOM’99 (Dec. 1999) pp. 1694–1698.

  20. D. Blokh and G. Gutin, An approximation algorithm for combinatorial optimization problems with two parameters, IMADA preprint (May 1995) pp. 1995–14 http://www.imada.ou.dk/Research/Preprints/ Abstracts/1995/14.html

  21. T. Korkmaz, M. Krunz and S. Tragoudas, An efficient algorithm for finding a path subject to two additive constraints, in: Proc. ACM SIGMETRICS’00 (June, 2000) pp. 318–327.

Download references

Author information

Authors and Affiliations

  1. Haute Alsace University, 34 rue de Grillenbreit, 68008, Colmar,Cedex, France

    Noureddine Kettaf, Hafid Abouaissa & Pascal Lorenz

  2. France Telecom R&D, 2, avenue Pierre Marzin, 22307, Lannion, Cedex, France

    Thang Vu duong

Authors
  1. Noureddine Kettaf
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hafid Abouaissa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thang Vu duong
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pascal Lorenz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thang Vu duong.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kettaf, N., Abouaissa, H., duong, T.V. et al. An efficient QoS routing algorithm for solving MCP in ad hoc networks. Telecommun Syst 33, 255–267 (2006). https://doi.org/10.1007/s11235-006-9014-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11235-006-9014-0

Keywords

Search

Navigation