A novel and effective multi-constrained QoS routing scheme in WMNs

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.

Keywords

energy function / multi-constrained routing / mean field annealing (MFA) / simulated annealing (SA)

References

[1] Bruno R, Conti M, Gregori E. Mesh networks: Commodity multihop ad hoc networks. IEEE Communications Magazine, 2005, 3(3): 123–131

[2] Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks. IEEE Wireless Communications, 2003, 10(5): 8–14

[3] Jaffe J M. Algorithms for finding paths with multiple constraints. Networks, 1984, 14(1): 95–116

[4] Wang Z, Crowcroft J. QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228–1234

[5] 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

[6] Yuan X.Heuristic algorithms for multiconstrained quality-of-service routing. IEEE/ACM Transactions on Networking, 2002, 10(2): 244–256

[7] 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

[8] 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

[9] Chen S, Nahrstedt K. On finding multi-constrained paths. In: Proceedings of IEEE International Conference on Communications. Atlanta, 1998, 2: 874–879

[10] Korkmaz T, Krunz M. A ranomized algorithm for finding a path subject to multiple QoS constraints. Computer Networks, 2001, 36(3): 251–268

[11] 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

[12] 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

[13] 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

[14] 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

[15] 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

[16] Chen S, Nahrstedt K. Distributed quality-of-service routing in ad-hoc networks. IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1–18

[17] 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

[18] Liu L, Feng G. Simulated annealing based multi-constrained QoS routing in mobile ad hoc networks. Wireless Personal Communications, 2007, 41(3): 393–405

[19] Huang X, Fang Y. Multiconstrained QoS multipath routing in wireless sensor networks. Wireless Networks, 2008, 14(4): 465–478

[20] 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

[21] Pham D T, Karaboga D. Intelligent optimisation techniques.London: Springer-Verlagnt, 2000, 10–105

[22] Aarts E, Korst J. Simulated annealing and Boltzmann machine—a stochastic approach to combinatorial optimization and neural computing.New York: Wiley, 1989, 8–36

[23] Peterson C, Soderberg B. A new method for mapping optimization problems onto neural network. International Journal of Neural Systems, 1989, 1(1): 3–22

[24] 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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg