Abstract
Multi-constrained quality of service (QoS) routing aims at finding an optimal path that satisfies a set of QoS parameters, as an NP complete problem, which is also a big challenge for wireless mesh networks (WMNs). 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 mesh networks. In this paper, we propose a novel routing scheme based on mean field annealing (MFA-RS) to solve this problem. MFA-RS first uses a function of two QoS parameters, wireless link’s delay and transmission success rate as the cost function, and then seeks to find a feasible path by MFA. Because MFA-RS uses a set of deterministic equations to replace the stochastic process in simulated annealing (SA) and uses saddle point approximation in the calculation of the stationary probability distribution at equilibrium, the convergence time is much less than the routing scheme based on SA (SA-RS). Simulation results demonstrate that MFA-RS is an effective algorithm and is very fit for WMNs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bruno R, Conti M, Gregori E. Mesh networks: Commodity multihop ad hoc networks. IEEE Communications Magazine, 2005, 3(3): 123–131
Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks. IEEE Wireless Communications, 2003, 10(5): 8–14
Jaffe J M. Algorithms for finding paths with multiple constraints. Networks, 1984, 14(1): 95–116
Wang Z, Crowcroft J. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228–1234
Kuipers F, Mieghem P V, Korkmaz T, Krunz M. An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine, 2002, 40(12): 50–55
Yuan X. Heuristic algorithms for multiconstrained quality-ofservice routing. IEEE/ACM Transactions on Networking, 2002, 10(2): 244–256
Chen S. Routing support for providing guaranteed end-to-end quality-of-service. Dissertation for the Doctoral Degree. Urbana-Champaign: University of Illinois at Urbana-Champaign, 1999, 23–79
Korkmaz T, Krunz M. Multi-constrained optimal path selection. In: Proceedings of Twentieth annual Joint Conference of the IEEE Computer and Communications Societies. 2001, 2: 834–843
Chen S, Nahrstedt K. On finding multi-constrained paths. In: Proceedings of IEEE International Conference on Communications. Atlanta, 1998, 2: 874–879
Korkmaz T, Krunz M. A ranomized algorithm for finding a path subject to multiple QoS constraints. Computer Networks, 2001, 36(3): 251–268
Khadivi P, Samavi S, Todd T D, Saidi H. Multi-constraint QoS routing using a new single mixed metric. In. Proceedings of IEEE International Conference on Communications., 2004, 4: 2042–2046
Xiao H, Seah W K G, Lo A, Chua K C. A flexible quality of service model for mobile ad-hoc networks. In: Proceedings of the 51st IEEE Vehicular Technology Conference. 2000, 1: 78–89
Ahn G S, Campbell A T, Veres A, Sun L H. Supporting service differentiation for real-time and best-effort traffic in stateless wireless ad hoc networks (SWAN). IEEE Transactions on Mobile Computing, 2002, 1(3): 192–207
Lee S B, Ahn G S, Zhang X, Campbell A T. INSIGIA: An IP based quality of service framework for mobile Ad Hoc networks. Journal of Parallel and Distributed Computing, 2000, 60(4): 374–406
Sivakumar R, Sinha P, Bharghavan V. CEDAR: A core-extraction distributed Ad-Hoc routing algorithm. IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1454–1465
Chen S, Nahrstedt K. Distributed quality-of-service routing in adhoc networks. IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1–18
Barolli L, Koyama A, Shiratori N A. QoS routing method for ad-hoc networks based on genetic algorithm. In: Proceedings of the 14th International Workshop on Database and Expert Systems Applications. 2003, 175–179
Liu L, Feng G. Simulated annealing based multi-constrained QoS routing in mobile ad hoc networks. Wireless Personal Communications, 2007, 41(3): 393–405
Huang X, Fang Y. Multiconstrained QoS multipath routing in wireless sensor networks.Wireless Networks, 2008, 14(4): 465–478
Liu L, Chen Z. Multi-constrained QoS path selection in wireless multimedia sensor networks. In: Proceedings of the 1st International Conference on Information Science and Engineering. 2009, 5362–5365
Pham D T, Karaboga D. Intelligent Optimisation Techniques. London: Springer-Verlagnt, 2000, 10–105
Aarts E, Korst J. Simulated Annealing and Boltzmann Machine—a Stochastic Approach to Combinatorial Optimization and Neural Computing. New York: Wiley, 1989, 8–36
Peterson C, Soderberg B. A new method for mapping optimization problems onto neural network. International Journal of Neural Systems, 1989, 1(1): 3–22
Hopfield J J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences of the United States of America, 1982, 79(8): 2541–2554
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Liu, L., Xu, W., Jia, H. et al. A novel and effective multi-constrained QoS routing scheme in WMNs. Front. Electr. Electron. Eng. China 6, 507–514 (2011). https://doi.org/10.1007/s11460-011-0118-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11460-011-0118-2