A genetic approach for wireless mesh network planning and optimization

ABSTRACT

Wireless Mesh Networks (WMNs) are gaining an increasingly important role in next generation last mile access. They offer more flexibility compared to traditional networks but on the expense of a complex structure. Thus, planning and optimization of WMNs is a challenge. In this paper we focus on routing and channel assignment in WMNs for throughput maximization using genetic algorithms. Genetic algorithms provide a good solution for large-scale WMNs in relatively small computation time. The results prove the effectiveness of the genetic operators and show the advantages of a genetic optimization. However, these operators have to be configured carefully to avoid local optima. We will show the influence of the selection principles as well as evaluation functions on the optimization.

REFERENCES

• 1: Leonardo Badia , Alessio Botta , Luciano Lenzini, A genetic approach to joint routing and link scheduling for wireless mesh networks, Ad Hoc Networks, v.7 n.4, p.654-664, June, 2009 [doi>10.1016/j.adhoc.2008.04.005]
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: P. Calégari, F. Guidec, P. Kuonen, and D. Wagner. Genetic Approach to Radio Network Optimization for Mobile Systems. In 47th Vehicular Technology Conference (IEEE-VTC 97), Phoenix, AZ, USA, May 1997.
• 4: Konstantinos P. Ferentinos , Theodore A. Tsiligiridis, Adaptive design optimization of wireless sensor networks using genetic algorithms, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.4, p.1031-1051, March, 2007 [doi>10.1016/j.comnet.2006.06.013]
• 5: Samik Ghosh , Preetam Ghosh , Kalyan Basu , Sajal K. Das, GaMa: An Evolutionary Algorithmic Approach for the Design of Mesh-Based Radio Access Networks, Proceedings of the The IEEE Conference on Local Computer Networks 30th Anniversary, p.374-381, November 15-17, 2005 [doi>10.1109/LCN.2005.72]
• 6: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 7: S. Hussain, A. Matin, and O. Islam. Genetic algorithm for hierarchical wireless sensor networks. JOURNAL OF NETWORKS, 2(5), 2007.
• 8: J. Jun and M. L. Sichitiu. The Nominal Capacity of Wireless Mesh Networks. IEEE Communications Magazine, 10(5):8--14, October 2003.
• 9: David Montana , Jason Redi, Optimizing parameters of a mobile ad hoc network protocol with a genetic algorithm, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068342]
• 10: R. Pries, D. Staehle, and M. Stoykova. On the Usability of Genetic Algorithms for Wireless Mesh Network Planning and Optimization. Technical Report 451, Universtiy of Würzburg, Würzburg, Germany, November 2008.
• 11: D. Staehle, B. Staehle, and R. Pries. Max-Min Fair Throughput in Multi-Gateway Multi-Rate Mesh Networks. Technical Report 454, University of Würzburg, January 2009.
• 12: Timo Vanhatupa , Marko Hännikäinen , Timo D. Hämäläinen, Performance model for IEEE 802.11s wireless mesh network deployment design, Journal of Parallel and Distributed Computing, v.68 n.3, p.291-305, March, 2008 [doi>10.1016/j.jpdc.2007.05.001]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Performance

Keywords:
genetic algorithms, optimization, planning, routing, wireless mesh networks