Skip to main content
SpringerLink
Log in

Simulated Annealing Based Multi-constrained QoS Routing in Mobile ad hoc Networks

  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

Abstract

Multi-constrained quality-of-service routing (QoSR) is to find a feasible path that satisfies multiple constraints simultaneously, which is a big challenge for mobile ad hoc networks (MANETs) where the topology may change constantly. It has been proved that such a problem is NP-complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions, most of which suffered either from excessive computational complexities or from low performance were proposed only for wired networks and cannot be used directly in wireless MANETs. In this paper a novel QoS routing algorithm based on Simulated Annealing (SA_RA) is proposed. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by simulated annealing. The paper outlines simulated annealing algorithm and analyzes the problems met when we apply it to QoSR in MANETs. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximation algorithms showing better performance than the other pertinent algorithm in seeking the (approximate) optimal configuration within a period of polynomial time.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Jaffe J.M (1984). “Algorithms for Finding Paths with Multiple Constraints”. Networks 14, 95–116

    MATH  MathSciNet  Google Scholar 

  2. Wang Z, Crowcroft J, (1996). “QoS routing for Supporting Resource Reservation”. IEEE J. Selected Areas Commun 14, 1228–1234

    Article  Google Scholar 

  3. Chen S, Nahrstedt K (1999). “Distributed Quality-of-Service Routing in Ad-Hoc Networks”. IEEE J. Selected Areas Commun. 17(8): 1–18

    Google Scholar 

  4. Kuipers F, Mieghem P.V, Korkmaz T, and Krunz M, “An Overview of Constraint-Based Path Selection Algorithms for QoS Routing”, IEEE Commmun. Magazine, Vol. 40. No. 12, pp. 50–55, Dec 2002.

  5. Yuan X, “Heuristic Algorithms for Multiconstrained Quality-of-Service Routing”, IEEE/ACM Trans. Networking. Vol. 10, No. 2, pp. 244–256, Apr. 2002.

  6. Chen S, Routing Support for Providing Guaranteed End-To-End Quality-Of- Service. Ph.D. thesis, Univ. of IL at Urbana-Champaign, http://cairo.cs.uiuc.edu/ papers/Cthesis. ps, 1999.

  7. Korkmaz T, and Krunz M, “Multi-constrained Optimal Path Selection”, in Proc. of INFOCOM 2001, Vol. 2, Anchorage, AK, IEEE, pp. 834–843, Apr. 2001.

  8. Chen S, and Nahrstedt K, “On Finding Multi-Constrained Paths”, Proc. of IEEE Int. Conf. Commun. (ICC’98), Atlanta, GA. Vol. 2, pp. 874 – 879, June 1998.

  9. Korkmaz T, Krunz M (2001). “A Ranomized Algorithm for Finding a Path Subject to Multiple QoS Constraints. Computer Networks” 36(2–3): 251–268

    Article  Google Scholar 

  10. Khadivi P, Samavi S, T. D. Todd, and Saidi H, Multi-constraint QoS Routing Using a New Single Mixed Metric. Proc. of IEEE In. Conf. Commun. (ICC’04), Vol. 4. pp. 2042–2046, June 2004.

  11. Xiao H, W.Seah K.G, Lo A, and Chua K.C, “A Flexible Quality of Service Model for Mobile Ad-Hoc Networks”, Proc. of IEEE VTC2000, Tokyo, Appendix: Springer-Author Discount, pp. 78–89,

  12. Ahn G.S, Campbell A.T, Veres A, Sun L.H, (2002). “Supporting Service Differentiation for Real-Time and Best-Effort Traffic in Stateless Wireless Ad Hoc Networks (SWAN)”. IEEE Trans. Mobile Comput 1(3): 192–207

    Article  Google Scholar 

  13. Lee S.B, Ahn G.S, Zhang X, Ampbell A.T, (2000). “INSIGIA: An IP Based Quality of Service Framework for Mobile Ad Hoc Networks”. J. Parallel Distributed Comput 60, 374–406

    Article  Google Scholar 

  14. Sivakumar R, Sinha P, Bharghavan V, (1999). “CEDAR: A Core-Extraction Distributed Ad-Hoc Routing Algorithm”. IEEE J. Selected Areas Commun 17(8): 1454–1465

    Article  Google Scholar 

  15. Barolli L, Koyama A, and Shiratori N, A QoS Routing Method for Ad-Hoc Networks Based on Genetic Algorithm. Proc. of the14th International Workshop on Database and Expert Systems Applications (DEXA’03), Prague, Czech Republic, pp. 175–179, Sep 2003.

  16. P.J.M. Van Laarhoven, and E.H.L. Aarts, Simulated Annealing: Theory and Applications. D. Reidel, 1st edn., 1987.

  17. Pham D.T, and Karaboga D, Intelligent Optimisation Techniques. Springer-Verlag London Limited, 1st edn., 2000.

  18. Koyama A, Barolli L, and Matsumoto K,etc., A GA-based Multi-purpose Optimization Algorithm for QoS Routing. in Proc. of the 18th International Conference on Advanced Information Networking and Application(AINA’04), Fukuoka, Japan. Vol. 1, pp. 23–28, March 2004.

Download references

Author information

Authors and Affiliations

  1. Department of Communications Engineering, Nanjing University of Posts & Telecommunications, 210003, Nanjing, China

    Lianggui Liu & Guangzeng Feng

Authors
  1. Lianggui Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guangzeng Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lianggui Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, L., Feng, G. Simulated Annealing Based Multi-constrained QoS Routing in Mobile ad hoc Networks. Wireless Pers Commun 41, 393–405 (2007). https://doi.org/10.1007/s11277-006-9149-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11277-006-9149-z

Keywords

Search

Navigation