Concepts.

• An ad hoc network is a simple network in which the communications are established in a given coverage area without the use of a hotspot. The stations then communicate in a point-2-point mode. Ad hoc network infraestructure (such as Wifi access points, etc).
• A metropolitan ad hoc network (MANET) is an ad hoc network populated with the mobile devices of the citizens. These devices are laptops, PDAs and mobile phones. They may be endowed with a Wi-Fi interface, a Bluetooth interface or both.
• The mobility of the devices is constrained by streets, corridors, etc. The radio propagation is constrainted by walls. This leads to a specific network topology.
• Madhoc is a Java metropolitan ad hoc network simulator which provides extended models for the network devices, their mobility, the radio wave propagation,…
• Broadcasting over the metropolitan ad hoc network consists in emiting a message from one device to as many devices as possible in a limited time (the lifetime of the broadcast message).
• Delayed Flooding ith Cumulative Neighborhood (DFCN) is a efficient 1-hop neighborhood-aware broadcasting protocol developed at Le Havre and Luxembourg universities.

The problem.

Given a metropolitan network MANET, the problem consists of tuning the broadcasting service for a particular network and a particular class of application. For this reason it is necessary to determine the most suitable parameters for the broadcasting service. The broadcasting optimization can be formulated as a multiobjective problem:

• Reach as many stations as possible (coverage).
• Minimize the network utilization (bandwidth).
• Reduce the broadcasting time (makespan).

In this strategy of broadcasting, DFCN is applied. We consider the following multiobjective heuristics in order to solve this problem:

• NSGA-II.
• Multiobjective Differential Evolution based on NSGA-II.
• Multiobjective Differential Evolution with external archive.

Parameters and fitness function.

In this problem each individual of the population is formed by 5 parameters (decision variables) which define a DFNC configuration:

• ProD is an integer value in the interval [0, 100] and it represents the maximal density for which it is still needed using proactive behaviour for completing the reactive behaviour.
• MinGain is a real value and its range is from 0.0 to 1.0. It is the minimum gain for rebroadcasting and this parameter is very important for tuning DFNC.
• SafeDensity represents a int value which ranges from 0 to 100 devices. It defines a maximum safe density of the threshold.
• [lowerBoundRAD, upperBoundRAD] are two real values in the interval [0.0, 10.0] milliseconds and define the RAD (Random Assessment Delay) value in DFCN.

The fitness function is a call to ExecSimulator program to execute MADHOC. After executing ExecSimulator, three numerical values are obtained, which correspond with the bandwidth, the coverage, and the broadcasting time respectively. All of obtained solutions (of the 3 algorithms) are normalized. The following statistical tests have been performed: Kolmogorov-Smirnov, ANOVA and Kruskal-Wallis.

References.

• "Optimizing the DFCN Broadcast Protocol with a Parallel Cooperative Strategy of Multi-Objective Evolutionary Algorithms", in: "Evolutionary Multi-Criterion Optimization" . Carlos Segura, Alejandro Cervantes, Antonio J. Nebro, María D. Jaraíz, Eduardo Segredo, Sandra García, Francisco Luna, Juan A. Gómez-Pulido, Gara Miranda, Cristobal Luque, Enrique Alba, Miguel A. Vega-Rodríguez, Coromoto León, Inés M. Galván. Springer-Verlag, Berlin Heidelberg, Germany, 2009, pag:305-319. ISBN:978-3-642-01019-4.
• "Metaheuristic Approaches for Optimal Broadcasting Design in Metropolitan MANETs", in: "Computer Systems Aided Theory" . E. Alba, A. Cervantes, J.A. Gómez, P. Isasi, M.D. Jaraíz, C. León, C. Luque, F. Luna, G. Miranda, A.J. Nebro, R. Pérez, and C. Segura. R. Moreno-Díaz et al. (Eds.), Springer-Verlag, Berlin Heidelberg, Germany, 2007, pag:755-763. ISBN:978-3-540-75866-2.
• "Parallel Differential Evolution for Multi-objective Optimization applied to the DFCN Broadcasting Strategy in MANETs". María D. Jaraíz-Simón, Juan A. Gómez-Pulido, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez. Computer Aided Systems Theory - Extended Abstracts, A. Quesada, J. Rodriguez, R. Moreno. IUCTC. Universidad de Las Palmas de Gran Canaria, Las Palmas de Gran Canaria, Spain, 2009, pag:238-239. ISBN:978-84-691-8502-5.
• "Metaheuristics approaches for optimal broadcasting design in metropolitan MANETs". E. Alba, A. Cervantes, J.A. Gomez, P. Isasi, M.D. Jaraiz, C. Leon, C. Luque, F. Luna, G. Miranda, A. J. Nebro, R. Perez and C. Segura. Computer Aided Systems Theory - Extended Abstracts, A. Quesada, J. Rodriguez, R. Moreno. IUCTC. Universidad de Las Palmas de Gran Canaria, Las Palmas de Gran Canaria, Spain, 2007, pag:262-263. ISBN:978-84-690-3603-7.

Contact.

• Juan Antonio Gómez Pulido.