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

doi:10.1007/s11460-011-0118-2

Front Elect Electr Eng Chin

2011, Vol. 6

Issue (4) : 507-514 https://doi.org/10.1007/s11460-011-0118-2

RESEARCH ARTICLE

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

Lianggui LIU¹(

), Weiqiang XU^1,2, Huiling JIA¹, Jie WU¹

1. College of Informatics & Electronics, Zhejiang Sci-Tech University, Hangzhou 310018, China; 2. Deptartment of Control, Zhejiang University, Hangzhou 310027, China

Download: PDF(243 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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)

Corresponding Author(s): LIU Lianggui,Email:lgliu@zstu.edu.cn

Issue Date: 05 December 2011

Cite this article:

Lianggui LIU,Weiqiang XU,Huiling JIA, et al. A novel and effective multi-constrained QoS routing scheme in WMNs[J]. Front Elect Electr Eng Chin, 2011, 6(4): 507-514.

URL:

https://academic.hep.com.cn/fee/EN/10.1007/s11460-011-0118-2
https://academic.hep.com.cn/fee/EN/Y2011/V6/I4/507

Fig.1 Procedure flow graph of MFN

Fig.2 A given WMN with bi-directional wireless links

Fig.3 Convergence time of MFA-RS w.r.t. different annealing schedule

Fig.4 Success ratio of MFA-RS w.r.t. different annealing schedule

Fig.5 Convergence time versus the number of nodes (routes) ( = 0.90)

Fig.6 SR of MFA-RS and SA-RS used in WMNs ( = 0.90)

1	Bruno R, Conti M, Gregori E. Mesh networks: Commodity multihop ad hoc networks. IEEE Communications Magazine , 2005, 3(3): 123–131 doi: 10.1109/MCOM.2005.1404606
2	Jun J, Sichitiu M L. The nominal capacity of wireless mesh networks. IEEE Wireless Communications , 2003, 10(5): 8–14 doi: 10.1109/MWC.2003.1241089
3	Jaffe J M. Algorithms for finding paths with multiple constraints. Networks , 1984, 14(1): 95–116 doi: 10.1002/net.3230140109
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 doi: 10.1109/MCOM.2002.1106159
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 doi: 10.1016/S1389-1286(00)00209-7
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 doi: 10.1109/TMC.2002.1081755
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 doi: 10.1006/jpdc.1999.1613
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 doi: 10.1109/49.779926
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 doi: 10.1007/s11277-006-9149-z
19	Huang X, Fang Y. Multiconstrained QoS multipath routing in wireless sensor networks. Wireless Networks , 2008, 14(4): 465–478 doi: 10.1007/s11276-006-0731-9
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 doi: 10.1142/S0129065789000414
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 doi: 10.1073/pnas.79.8.2554 pmid:6806813

[1]	Lincong WANG, Shuxue ZOU, Yao WANG. Algorithmic challenges in structure-based drug design and NMR structural biology[J]. Front Elect Electr Eng, 2012, 7(1): 69-84.
[2]	ZHAO Bao-jun, LI Dong. Improved Snake algorithm for complex target’s boundary detection[J]. Front. Electr. Electron. Eng., 2006, 1(2): 141-145.

Viewed

Full text

Abstract

Cited

Shared

Discussed