Solving the Wireless Mesh Network Design Problem using Genetic Algorithm and Simulated Annealing Optimization Methods

Print
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 96 - Number 11
Year of Publication: 2014
Authors:
Moheb R. Girgis
Tarek M. Mahmoud
Bahgat A. Abdullatif
Ahmed M. Rabie
10.5120/16835-6680

Moheb R Girgis, Tarek M Mahmoud, Bahgat A Abdullatif and Ahmed M Rabie. Article: Solving the Wireless Mesh Network Design Problem using Genetic Algorithm and Simulated Annealing Optimization Methods. International Journal of Computer Applications 96(11):1-10, June 2014. Full text available. BibTeX

@article{key:article,
	author = {Moheb R. Girgis and Tarek M. Mahmoud and Bahgat A. Abdullatif and Ahmed M. Rabie},
	title = {Article: Solving the Wireless Mesh Network Design Problem using Genetic Algorithm and Simulated Annealing Optimization Methods},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {96},
	number = {11},
	pages = {1-10},
	month = {June},
	note = {Full text available}
}

Abstract

Mesh clients, mesh routers and gateways are components of Wireless Mesh Network (WMN). In WMN, gateways connect to Internet using wireline links and supply Internet access services for users. Multiple gateways are needed, which take time and cost budget to set up, due to the limited wireless channel bit rate. WMN is a highly developed technology that offers to end users a wireless broadband access. It offers a high degree of flexibility contrasted to conventional networks; however, this attribute comes at the expense of a more complex construction. Therefore, a challenge is the planning and optimization of WMNs. This paper concentrates on the challenge using a genetic algorithm and simulated annealing. The genetic algorithm and simulated annealing enable searching for a low-cost WMN configuration with constraints and determine the number of used gateways. Experimental results proved that the performance of the genetic algorithm and simulated annealing in minimizing WMN network costs while satisfying quality of service. The proposed models are presented to significantly outperform the existing solutions.

References

  • I. F. Akyildiz, X. Wang, and W. Wang, Wireless mesh networks: a survey, Computer Networks 47(4), pp. 445–487, 2005.
  • E. Amaldi, A. Capone, M. Cesana, I. Filippini, and F. Malucelli, Optimization models and methods for planning wireless mesh networks, Computer Networks, vol. 52, no. 11, pp. 2159–2171, August 2008.
  • Ch. Chen and Ch. Chekuri, Urban Wireless mesh network planning: the case of directional antennas, Tech Report No. UIUCDCS-R-2007-2874, Department of Computer Science, University of Illinois at Urbana-Champaign, 2007.
  • J. Holland, Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, 1975.
  • Z. Michalewicz, Genetic algorithms + data structures = evolution program, 3rd Edition, Springer-Verlag, Berlin, 1996.
  • S. Kirkpatrik, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, science, vol. 220, pp. 671-680, 1983.
  • I. Bohachevsky, M. E. Johnson and M. L. Stein, Generalized simulated annealing for function optimization, in Technometrics, vol. 28, pp. 209-217, 1986.
  • A. Beljadid, A. S. Hafid, and M. Gendreau, Optimal design of broadband wireless mesh networks, in Proc. of the 50th International Conference on GLOBECOM 07, 2007.
  • A. K. Das, H. M. K. Alazemi, R. Vijayakumar, and S. Roy, Optimization models for fixed channel assignment in wireless mesh networks with multiple radios, IEEE SECON 2005, pp. 463–474, 2005.
  • A. Raniwala K. Gopalan and T-C. Chiueh, Centralized channel assignment and routing algorithms for multi channel wireless mesh networks, Comput. Commun. Rev. , vol. 8, no. 2, pp. 50–65, 2004.
  • M. Alicherry, R. Bhatia, and L. E. Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, MobiCom '05, pp. 58–72, 2005.
  • P. Kyasanur and N. Vaidya, Routing and interface assignment in multichannel multi-interface wireless networks, WCNC, 2005.
  • B. Aoun, R. Boutaba, Y. Iraqi, G. Kenward, Gateway placement optimization in wireless mesh networks with QoS constraints, IEEE JSAC, vol. 24, Issue 11, pp. 2127–2136, Nov. 2006.
  • J. L. Qiu, R. Chandra, K. Jain, and M. Mahdian, Optimizing the placement of integration points in multi-hop wireless networks, Proc. ICNP'04, pp. 271–282, Oct. 2004.
  • Nomura, N. Funabiki, and T. Nakanishi, A proposal of access-point channel assignment algorithm and an evaluation of access-point allocation algorithm in wireless infrastructure mesh networks, in Proc. 3rd ANWS, pp. 113–116, Jan. 2006.
  • S. Tajima, T. Higashino, N. Funabiki, and S. Yoshida, An internet gateway access-point selection problem for wireless infrastructure mesh networks, in Proc. of the 7th International Conference on MDM '06, 2006.
  • A. Kashyap, K. Lee, and M. Shayman, Rollout algorithms for integrated topology control and routing in wireless optical backbone networks, ISR Tech. Report TR2003-51, 2003.
  • Y. Ding and L. Xiao, Channel allocation in multi-channel wireless mesh networks, Computer Communications, vol. 34, pp. 803–815, 2011.
  • L. Hui, A novel QoS routing algorithm in wireless mesh networks, TELKOMNIKA, vol. 11, no. 3, pp. 1652–1664, ISSN: 2087-278X, March 2013.
  • M. Kodialam and T. Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, MobiCom '05, pp. 73–87, 2005.
  • S. Ghosh, P. Ghosh, K. Basu, and S. K. Das, GaMa, An evolutionary algorithmic approach for the design of mesh-based radio access networks, in LCN '05: Proceedings of the IEEE Conference on Local Computer Networks 30th Anniversary, Washington, DC, USA, pp. 374–381, November 2005.
  • J. Jun and M. L. Sichitiu, The nominal capacity of wireless mesh networks, IEEE Wireless Communications, Oct 2003.
  • A. So and B. Liang, Minimum cost configuration of relay and channel infrastructure in heterogeneous wireless mesh networks, in Networking, Atlanta, GA, USA, pp. 275–286, May 2007.
  • B. He, B. Xie, and D. P. Agrawal, Optimizing deployment of internet gateway in wireless mesh networks, Computer Communications, vol. 31, no. 7, pp. 1259–1275, 2008.
  • L. Badia, A. Botta, and L. Lenzini, A genetic approach to joint routing and link scheduling for wireless mesh networks, Elsevier Ad Hoc Networks Journal, vol. Special issue on Bio- Inspired Computing, p. 11, April 2008.
  • T. Vanhatupa, M. H¨annik¨ainen, and T. D. H¨am¨al¨ainen, Genetic algorithm to optimize node placement and configuration for WLAN planning, 4th International Symposium on Wireless Communication Systems, 2007. ISWCS 2007, Trondheim, Norway, pp. 612–616, October 2007.
  • T. Vanhatupa, M. H¨annik¨ainen, and T. D. H¨am¨al¨ainen, Performance model for IEEE 802. 11s wireless mesh network deployment design, Journal of Parallel and Distributed Computing, vol. 68, no. 3, pp. 291–305, March 2008.
  • C. Ying-Yu, L. Chen-Chun and C. Chien, Channel assignment and routing for multi-channel wireless mesh networks using simulated annealing, Global Communications Conference GLOBECOM, vol. 27, pp. 1-5, 2006.
  • F. Xhafa, C. Sanchez, L. Barolli and R. Miho, An annealing to router nodes placement problem in wireless mesh networks, International Conference on Complex Intelligent and Software Intensive Systems, pp. 245-252, 2010.
  • H. Chun-Yen, C. Jean-Lien, W. Shun-Te, H. Chi-Yao, Survivable and delay-guaranteed backbone wireless mesh network design, J. Parallel Distrib. Comput. 68, pp. 306–320, 2008.
  • K. A. De Jong, Evolutionary computation: A unified approach, MIT Press, 2006.
  • L. Ting-Yu, H. Kai-Chiuan, H. Hsin-Chun, Applying genetic algorithms for multiradio wireless mesh network planning, IEEE Transactions on Vehicular Technology, vol. 61, no. 5, pp. 2256–2270, June 2012.
  • S. Sakamoto, E. Kulla, T. Oda, M. Ikeda, L. Barolli and F. Xhafa, A comparison study of simulated annealing and genetic algorithm for node placement problem in wireless mesh networks, Journal of Mobil Multimedia, vol. 9, pp. 101-110, 2013
  • S. Kazem, K. Maryam, Y. Mohammed, D. Houssien, Localization in wireless sensor networks using tabu search and simulated annealing, Computer and Automation Engineering (ICCAE), 2nd International Conference On Singapore, vol. 2, pp. 752–757, 2010.