Abstract
Multicast routing is a crucial issue in wireless networks in which the same content should be delivered to a group of recipients simultaneously. Multicast is also considered as a key service for audio and video applications as well as data dissemination protocols over the last-mile backhaul Internet connectivity provided by multi-channel multi-radio wireless mesh networks (MCMR WMNs). The multicast problem is essentially related to a channel assignment strategy which determines the most suitable channel-radio associations. However, channel assignment brings about its own complications and hence, solving the multicast problem in MCMR WMNs will be more complicated than that of traditional networks. This problem has been proved to be NP-hard. In the major prior art multicast protocols developed for these networks, channel assignment and multicast routing are considered as two separate sub-problems to be solved sequentially. The work in this article is targeted at promoting the adoption of learning automata for joint channel assignment and multicast routing problem in MCMR WMNs. In the proposed scheme named LAMR, contrary to the existing methods, these two sub-problems will be solved conjointly. Experimental results demonstrate that LAMR outperforms the LCA and MCM proposed by Zeng et al. (IEEE Trans. Parallel. Distrib. Syst. 21(1):86–99, 2010) as well as the genetic algorithm-, tabu search-, and simulated annealing-based methods by Cheng and Yang (Int. J. Appl. Soft Comput. 11(2):1953–1964, 2011) in terms of achieved throughput, end-to-end delay, average packet delivery ratio, and multicast tree total cost.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Akyildiz IF, Wang X (2005) wireless mesh networks: a survey. Elsevier J Comput Netw 47(4):445–487
Martínez J, Bafalluy JM (2010) A survey on routing protocols that really exploit wireless mesh network features. J Commun 5(3):211–231
Ma L, Zhu G, Yin B (2008) Optimization models of multi-channel assignment in multi-radio wireless mesh networks. In: 4th international conference on wireless communications, networking and mobile computing, pp 1–5
Baul P, Adya A, Padhye J, Walman A (2004) Reconsidering wireless systems with multiple radios. ACM SIGCOMM Comput Commun Rev 34(5):39–46
Das A, Vijayakumar R, Roy S (2006) Static channel assignment in multi-radio multi-channel 802.11 wireless mesh networks: issues, metrics and algorithms. In: 49th IEEE global telecommunications conference (GLOBECOM), San Francisco, California, USA
Gupta P, Kumar PR (2000) The capacity of wireless networks. IEEE Trans Inf Theory 46(2):388–404
Skalli H, Ghosh S, Das SK, Conti M (2007) Channel assignment strategies for multiradio wireless mesh networks: issues and solutions. IEEE Commun Mag 45(11):86–95
Subramanian AP, Gupta H, Das SR (2007) Minimum interference channel assignment in multi-radio wireless mesh networks. In: Annual IEEE communications society conference on sensor, mesh and ad hoc communications and networks (SECON’07), pp 481–490
Mohsenian AH, Wong V (2006) Joint optimal channel assignment and congestion control for multi-channel wireless mesh networks. In: IEEE international conference on communications (ICC 2006), Istanbul, Turkey
Ramachandran K, Belding E, Almeroth K, Buddhikot M (2006) Interference aware channel assignment in multi-radio wireless mesh networks. In: IEEE INFOCOM, pp 1–12
Marina M, Das S (2005) A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks. In: 2nd international conference on broadband networks (BROADNETS 2005), Boston, Massachusetts, USA
Das A, Alazemi H, Vijayakumar R, Roy S (2005) Optimization models for fixed channel assignment in wireless mesh networks with multiple radios. In: 2nd IEEE communications society conference on sensor and ad hoc communications and networks (SECON), Santa Clara, California, USA, pp 463–474
Alicherry M, Bhatia R, Li L (2005) Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In: 11th ACM international conference on mobile computing and networking (MOBICOM 2005), Cologne, Germany
Tang J, Xue G, Zhang W (2005) Interference-aware topology control and QoS routing in multichannel wireless mesh networks. In: ACM MOBIHOC, pp 68–77
Raniwala A, Gopalan K, Chiueh T (2004) Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. Mob Comput Commun Rev 8(2):50–65
Tasaki F, Tamura H, Sengoku M, Shinoda S (2004) A new channel assignment strategy towards the wireless mesh networks. In: APCC’04, pp 71–75
Kodialam M, Nandagopal T (2005) Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In: 11th ACM international conference on mobile computing and networking (MOBICOM 2005), Cologne, Germany, pp 73–87
Keegan B, Kowalik K, Davis M (2008) Optimisation of multicast routing in wireless mesh networks. In: Information technology and telecommunications conference, Galway, Mayo Institute of Technology
Ruiz PM, Gomez-Skarmeta AF (2005) Approximating optimal multicast trees in wireless multihop networks. In: IEEE ISCC05, pp 686–691
Nguyen U, Xu J (2007) Multicast routing in wireless mesh networks: minimum cost trees or shortest path trees? IEEE Commun Mag 45(11):72–77
Nguyen UT (2008) On multicast routing in wireless mesh networks. Elsevier J Comput Commun 31(7):1385–1399
Roy S, Koutsonokolas D, Das S, Hu YC (2008) High-throughput multicast routing metrics in wireless mesh networks. Ad Hoc Netw 6(7):878–899
Zhao X, Chou CT, Guo J, Jha S (2006) Protecting multicast sessions in wireless mesh networks. In: IEEE Conference on Local Computer Networks LCN’06, pp 467–474
Yuan J, Li Z, Yu W, Li B (2006) A cross-layer optimization framework for multihop multicast in wireless mesh networks. IEEE J Sel Areas Commun 24(11):2092–2103
Shittuet WA et al (2008) A proposed QoS multicast routing framework for next-generation wireless mesh network. Int J Comput Sci Netw Secur 8(9):280–284
Ruiz PM, Galera FJ, Jelger C, Noel T (2006) Efficient multicast routing in wireless mesh networks connected to internet. In: First international conference on integrated internet ad hoc & sensor networks
Akyildiz IF, Wang X (2008) Cross-layer design in wireless mesh networks. IEEE Trans Veh Technol 57(2):1061–1076
Karimi OB, Liu J, Li Z (2010) Multicast in multi-channel wireless mesh networks. In: Networking. LNCS, vol 6091, pp 148–159
Xu J (2006) Multicast in wireless mesh networks. MS Thesis, York University, Toronto
Gopinathan A, Li Z, Williamson C (2009) Optimal multicast in multi-channel multi-radio wireless networks. In: The proceedings of 16th IEEE/ACM international symposium on modeling, analysis, and simulation of computer and telecommunication systems (MASCOTS), Imperial College, London, UK, pp 21–23
Zeng GW, Ding B, Xiao YL, Mutka M (2007) Multicast algorithms for multi-channel wireless mesh networks. In: IEEE international conference on network protocols (ICNP’07), pp 1–10
Zeng GW et al (2010) Efficient multicast algorithms for multichannel wireless mesh networks. IEEE Trans Parallel Distrib Syst 21(1):86–99
Nguyen HL, Nguyen UT (2008) Minimum interference channel assignment for multicast in multi-radio wireless mesh networks. In: IEEE international wireless communications and mobile computing conference (IWCMC’08), pp 626–631
Nguyen HL, Nguyen UT (2009) Channel assignment for multicast in multi-channel multi-radio wireless mesh networks. Wiley J Wirel Commun Mobile Comput 9:557–571. Special Issue on Next Generation Wireless Communications and Mobile Computing Networking Technologies
Yin Z, Li Z, Chen M (2007) A novel channel assignment algorithm for multicast in multi-radio wireless mesh networks. In: IEEE ISCC’07, pp 283–288
Cheng H, Yang S (2008) A genetic-inspired joint multicast routing and channel assignment algorithm in wireless mesh networks. In: The 8th annual workshop on computational intelligence, UK, pp 159–164
Cheng H, Yang S (2008) Joint channel assignment and multicast routing in multiradio multichannel wireless mesh networks using simulated annealing. In: SEAL. LNCS, vol 5361, pp 370–380
Cheng H, Yang S (2011) Joint QoS multicast routing and channel assignment in multiradio multichannel wireless mesh networks using intelligent computational methods. Int J Appl Soft Comput 11(2):1953–1964
Nguyen HL, Nguyen UT (2009) Bandwidth efficient multicast routing in multi-channel multi-radio wireless mesh networks. In: International conference on ultra modern telecommunications & workshops, pp 1–8
Lim S, Kim C, Ko Y, Vaidya NH (2009) An efficient multicasting for multi-channel multi-interface wireless mesh networks. In: IEEE military communications conference (MILCOM), pp 1–7
Xu Y, Qu R (2012) A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems. J Appl Intell 36(1):229–241
Araújo AF, Garrozi C (2010) MulRoGA: a multicast routing genetic algorithm approach considering multiple objectives. J Appl Intell 32(3):330–345
Kim SJ, Choi MK (2007) Evolutionary algorithms for route selection and rate allocation in multirate multicast networks. J Appl Intell 26(3):197–215
Crichigno J, Wu MY, Shu W (2008) Protocols and architectures for channel assignment in wireless mesh networks. Ad Hoc Netw 6(7):1051–1077
Palomar DP, Chiang M (2006) A tutorial on decomposition methods for network utility maximization. IEEE J Sel Areas Commun 24(8):1439–1451
Hossain E, Leung KK (2008) Wireless mesh networks, architectures and protocols. Springer, Berlin
Ding Y, Huang Y, Zeng G, Xiao L (2008) Channel assignment with partially overlapping channels in wireless mesh networks. In: 4th annual international conference on wireless internet, pp 963–978
Thathachar MAL, Sastry PS (2002) Varieties of learning automata: an overview. IEEE Trans Syst Man Cybern, Part B, Cybern 32(6):711–722
Narendra KS, Thathachar MAL (1989) Learning automata: an introduction. Prentice Hall, New York
Granmo OC, Oommen BJ (2010) Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem. Appl Intell 33(1):3–20
Torkestani JA, Meybodi MR (2010) Mobility-based multicast routing algorithm in wireless mobile ad hoc networks: a learning automata approach. J Comput Commun 33(6):721–735
Yazidi A, Granmo OC, Oommen BJ (2012) Service selection in stochastic environments: a learning-automaton based solution. J Appl Intell 36(3):617–637
Vafashoar R, Meybodi MR, Momeni AH (2011) CLA-DE: a hybrid model based on cellular learning automata for numerical optimization. J Appl Intell 36(3):735–848
Raniwala A, Chiueh TC (2005) Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In: IEEE INFOCOM, pp 2223–2234
Johnson OT (2004) Information theory and the central limit theorem. Imperial College Press, London, p 88. ISBN 1860944736
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jahanshahi, M., Dehghan, M. & Meybodi, M.R. LAMR: learning automata based multicast routing protocol for multi-channel multi-radio wireless mesh networks. Appl Intell 38, 58–77 (2013). https://doi.org/10.1007/s10489-012-0357-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-012-0357-9