Overcoming partitioning in large ad hoc networks using genetic algorithms

ABSTRACT

We deal in this paper with the important problem of partitioning in ad hoc networks. In our approach, we assume that some devices might have other communication interfaces rather than Wi-Fi and/or Bluetooth allowing to connect remote devices (e.g., technologies such as GPRS or HSDPA). This would allow us to build hybrid networks for overcoming the network partitioning. Hence, the problem considered in this work is to establish remote links between devices (called bypass links) in order to maximize the QoS of the network by optimizing its properties to make it small world. Additionally, the number of this kind of links in the network should be minimized as well, since we consider that not all the devices have these communication capabilities, or it could be a requirement to minimize the use of the long range network (for example, in the case its use supposes some cost). We face the problem with four different GAs (both parallel and sequential) and compare their behaviors on six different network instances. All the algorithms were tested with a new encoding of the problem, which is demonstrated to provide more accurate results than the previously existing one.

REFERENCES

• 1: Enrique Alba , Bernab Dorronsoro, Cellular Genetic Algorithms, Springer Publishing Company, Incorporated, 2008
• 2: T. Bäck, D. Fogel, and Z. Michalewicz, editors. Handbook of Evolutionary Computation. Oxford University Press, 1997.
• 3: Gregoire Danoy , Enrique Alba , Pascal Bouvry , Matthias R. Brust, Optimal design of ad hoc injection networks by using genetic algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277391]
• 4: B. Dorronsoro, G. Danoy, P. Bouvry, and E. Alba. Evaluation of different optimization techniques in the design of ad hoc injection networks. In Opt. Issues in Grid and Parallel Computing Environments, part of the High Performance Comp. and Simulation Conf. (HPCS), pages 290--296, 2008.
• 5: K. Herrmann and K. Geihs. Self-Organization in Mobile Ad hoc Networks based on the Dynamics of Interaction, 2003. Frühjahrstreffen der GI-Fachgruppe Betriebssysteme.
• 6: L. Hogie, P. Bouvry, F. Guinand, G. Danoy, and E. Alba. Simulating Realistic Mobility Models for Large Heterogeneous MANETS. In ACM/IEEE Int. Symp. on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM'06), pages 129--141. IEEE, October 2006.
• 7: Mitchell A. Potter , Kenneth A. De Jong, A Cooperative Coevolutionary Approach to Function Optimization, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.249-257, October 09-14, 1994
• 8: F. Seredynski, A. Zomaya, and P. Bouvry. Function optimization with coevolutionary algorithms. In Intelligent Inf. Processing and Web Mining, pages 13--22. Springer, 2003.
• 9: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Performance

Keywords:
cellular gas, cooperative coevolutionary gas, topology control