Main Article Content

Abstract

Given a mesh of wireless nodes for WiFi customers covering a city district, we describe a genetic algorithm-based approach to the problem of selecting a small fixed number of nodes as gateways to the internet, and linking the remaining nodes to the gateways either directly or by 'hopping', to create an efficient mesh network structure. The algorithm uses a modification of k-means clustering to allocate nodes to gateways.

 

 

Keywords

Genetic algorithms Mesh WiFi network.

Article Details

References

  1. BEASLEY, J.E. 1983. Route first-cluster second methods for vehicle routing. Omega, 11:403-408.
  2. CHEN, W-K. 2003. Net Theory and its Applications: Flows in Networks. Imperial College Press, London, UK.
  3. DORIGO, M. and STUETZLE, T, 2004. Ant Colony Optimization. MIT Press, Cambridge, Massachusetts, USA.
  4. EISELT, H.A., GENDREAU, M. and LAPORTE, G. 1995. Arc-routing problems, Part II: The Rural Postman Problem. Operations Research, 43(3): 399-414.
  5. GOLDBERG, D.E. 1997. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley.
  6. HO, W., HO, G.T.S., JI, P. and LAU, H.C.W. 2008. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4):548-557.
  7. HOLLAND, J. 1975. Adaption in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
  8. LLOYD, S.P. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28:129-137.
  9. NASH, S. 2007. Motorola: Mesh Wifi Gateway Optimisation. M.Sc. Dissertation, Dept. of Mathematical Sciences, University of Bath, UK.
  10. TUZUN, D. and BURKE, L.I. 1999. A two-phase tabu search approach to the location routing problem. European Journal of Operations Research, 116(1):87-99.