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.

Key words： energy function; multi-constrained routing; mean field annealing (MFA); simulated annealing (SA)

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61002016 and 60702081); the Natural Science Foundation of Zhejiang Province of China (Grant No. Y107309); the University Scientific Research Program of the Education Department of Zhejiang Province of China (No. 20070364); the Scientific Research Foundation of Zhejiang Sci-Tech University(Nos. 0704698 and 0704697); the Xinmiao Talent Project of Zhejiang Province(2009).

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

PMID