"Noiseless" thermal noise measurement of atomic force microscopy cantilevers Basile Pottier [START_REF] Hutter | Calibration of atomicforce microscope tips[END_REF] and Ludovic Bellon 1, a) Univ Lyon, Ens de Lyon, Univ Claude Bernard Lyon 1, CNRS, Laboratoire de Physique, F-69342 Lyon, France (Dated: 8 March 2017)

When measuring quadratic values representative of random fluctuations, such as the thermal noise of Atomic Force Microscopy (AFM) cantilevers, the background measurement noise cannot be averaged to zero. We present a signal processing method that allows to get rid of this limitation using the ubiquitous optical beam deflection sensor of standard AFMs. We demonstrate a two orders of magnitude enhancement of the signal to noise ratio in our experiment, allowing the calibration of stiff cantilevers or easy identification of higher order modes from thermal noise measurements.

A common procedure to calibrate the stiffness of Atomic Force Microscopy (AFM) cantilevers uses the thermal noise driven fluctuations of its deflection [START_REF] Hutter | Calibration of atomicforce microscope tips[END_REF][START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] . Implemented in most commercial devices, this method consists in measuring the mean-square amplitude of the cantilever's deflection x 2 at thermal equilibrium around x = 0. The equipartition principle states that the energy stored in the spring is in average equal to the thermal energy thus

1 2 k x 2 = 1 2 k B T (1)
where k B (the Boltzmann's constant) and T (the temperature) are known, and k is the spring constant to calibrate. At room temperature, these tiny mechanical fluctuations range from 200 pm rms for a soft probe (0.1 N/m) to only 10 pm rms for a stiff probe (40 N/m).

One is thus very sensitive to presence of the noise in the measurement. Indeed, let

X = x + η (2)
be the measured value of the deflection x and η the measurement noise, the contribution of the latter doesn't vanish when computing mean square quantities even after a long averaging:

X 2 = x 2 + η 2 = k B T k + η 2 (3)
where the cross term 2 xη = 2 x η averages to 0 since the two stochastic signals are uncorrelated and of zero mean. The stiffer the cantilever, the smaller is the signal to noise ratio x 2 / η 2 and the less accurate is the spring constant calibration.

In order to isolate the contribution of the mechanical fluctuations, one studies the Power Spectral Density (PSD) S X 2 of the signal X:

S X 2 (f ) = | X(f )| 2 ∆f (4)
a) Electronic mail: ludovic.bellon@ens-lyon.fr where X(f ) is the Fourier transform of X and ∆f the spectral bins bandwidth. Indeed, thanks to the resonant behavior of the cantilever near its normal modes, the energy of mechanical fluctuations is mainly stored around the resonance frequencies (especially the first one) [START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] . The measurement noise, on the contrary, is often only a white noise, its energy being flat across all the frequency spectrum. This is the case for instance for the shot noise of an optical measurement. It is thus convenient to study the first resonance of the measured spectrum S X 2 , which can be fitted by the prediction of the Fluctuation-Dissipation Theorem (FDT) for a Simple Harmonic Oscillator (SHO), with an additional white noise S η 2 :

S X 2 (f ) = S x 2 (f ) + S η 2 (5) = 2k B T πkf 0 1/Q (1 -u 2 ) 2 + u 2 /Q 2 + S η 2 (6)
where Q is the quality factor and u = f /f 0 is the frequency normalized to the resonance one f 0 . The equipartition theorem (1) can be recovered from the FDT by integrating this last equation over all frequencies, but thanks to the resonance the signal to noise ratio is increased by a factor Q near f 0 . This strategy is efficient and can give reasonable results for stiffnesses up to 1 N/m, but uncertainty is large for stiffer cantilevers, for which the mechanical fluctuation S x 2 only stand above the background noise S η 2 in a tiny frequency range around the resonance. Minimizing the S η 2 contribution to the PSD is thus highly desirable.

To get rid of this problem, let us perform two simultaneous independent measurements X 1 and X 2 of the deflection x, each being plagued by an independent noise η 1 and η 2 :

X 1 = x + η 1 , X 2 = x + η 2 (7)
The Cross Spectrum Density (CSD) S X1X2 of these two signal then directly averages to the PSD of interest 3,4 S x 2 :

S X1X2 (f ) = X1 (f ) X * 2 (f ) ∆f = S x 2 (f ) (8)
Indeed, all cross spectra corresponding to uncorrelated stochastic signals ( xη 1 , xη 2 , η 1 η 2 ) average to 0. This simple operation thus allows the complete canceling of the measurement noise, as long as it is uncorrelated to the mechanical fluctuations of the cantilever. In this letter, we present an implementation of this technique using the ubiquitous optical beam deflection (OBD) technique. Let us first review the classic OBD method and its limitations. Introduced by Meyer and Amer 5 , this technique is the most widely used in laboratory and commercially available AFMs: it combines ease of use and high resolution. It consists in illuminating the free end of the cantilever with a focused laser beam and detecting the fluctuations of the reflected beam position with a 4-quadrants photodiode (figure 1). The reflected beam position is function of the local slope of cantilever free end, thus representative of its flexion (angle θ) and torsion (θ ′ ). Practically the position of reflected beam is measured by computing a contrast function C 0 of the photocurrents I n delivered by the 4 quadrants n = 1 to 4 of the photodiode:

C 0 = I 1 + I 2 -I 3 -I 4 I 1 + I 2 + I 3 + I 4 (9)
A downward flexion of the cantilever will move the laser spot towards the top quadrants (1,2), increasing I 1 and I 2 and decreasing I 3 and I 4 , thus C 0 is a measurement of the flexion angle θ, hence of the deflection x. A similar contrast C ′ 0 between left (1,3) and right (2,4) quadrants intensities gives a measurement of the torsion angle θ ′ .

At first order, C 0 is proportional to θ or x:

C 0 = σ θ θ + η 0 = σ x x + η 0 ( 10
)
with η 0 the measurement noise, and σ θ or σ x the sensitivity of the sensor. The thermal fluctuations spectra S x 2 or S θ 2 will thus be hidden when the amplitude of the noise is too high:

S C 2 0 = σ 2 θ S θ 2 + S η 2 0 = σ 2 x S x 2 + S η 2 0 (11)
Using gaussian beam optics, the theoretical value of the angular sensitivity can be computed 6 :

σ θ = √ 8π R λ ( 12
)
where λ is the laser wavelength and R the radius of the beam waist. The deflection sensitivity σ x depends on the cantilever length L and the oscillation mode m of the cantilever: using an Euler-Bernoulli description of a rectangular cantilever 2 , it can be shown that

σ x = β m σ θ /L, with β 1 ≈ 1.38, β 2 ≈ 4.78, . . . β m ≈ (m -1/2)π.
In practice, σ x is approximately calibrated for mode 1 using a force curve on a hard surface (usually σ x is given in nm/V in commercial AFMs).

The source of noises contributing to η 0 can be classified into two categories: classical noise, like the light source having fluctuation in intensity or beam direction, and quantum noise, like the photon shot noise at the detector and the back-action of the light on the cantilever [START_REF] Smith | Limits of Force Microscopy[END_REF] . The effects of classical noise can be reduced by proper experimental design: the effect of fluctuations in light intensity for example are canceled using the contrast C 0 where the difference between the intensities on the top quadrants and the bottoms ones is normalized by the total intensity (eq. 9). On the other hand, quantum mechanical noises are unavoidable. The optical shot noise, which is due to the counting statistics of the photons, is in most cases the dominant source of detection noise and limits the resolution of the OBD technique. According to the Poisson distribution of the light source, the shot noise is frequency independent and appears as a white noise in all measured intensities I n : S SN I 2 n = 2eI n , with e the elementary charge. Using the definition of C 0 (eq. 9), assuming the beam is centered on the photodiode, we compute the flat baseline which represents the shot noise limit for the deflection measurement:

S SN η 2 0 = 4 n=1 ∂C 0 ∂I n 2 S SN I 2 n = 2e I 0 ( 13
)
where I 0 = 4 n=1 I n is the total photocurrent. Other contributions may sum on top of this shot noise limit, such as the ones from the conditioning electronics (Johnson-Nyquist noise of the current amplifier (white noise), 1/f noise, high frequency electronics noise, etc.), from the analog to digital convertion. . . One might notice that we can reduce the shot noise level by increasing the light beam power. However in practice the laser power is limited. Besides, because of partial light absorption by the cantilever, raising the power risks to significantly heat the cantilever, which may alter its stiffness or functionality 8 . Typical shot noise limit is

S SN η 2 0 /σ 2
x ≈ 4 × 10 -26 m 2 /Hz (numerical application for a L = 125 µm long cantilever, using a 0.1 mW laser beam at λ = 633 nm focused on a R = 5 µm radius spot, with a photodiode efficiency of 0.4 A/W). This is close to the thermal fluctuations expected at resonance for a stiff cantilever: S x 2 (f 0 ) ≈ 9 × 10 -26 m 2 /Hz for f 0 = 300 kHz, Q = 400, k = 40 N/m at room temperature. Note that for AFM experiments where the cantilever is immersed in water rather than in air (corresponding to a smaller quality factor Q), the viscosity of the environment broadens the structural resonances and decreases the peak amplitude. In these cases, the calibration procedure is restricted to even less stiff cantilevers. We should note that the usage of nonclassical light technique (e.g. squeezed states of light [START_REF] Caves | Quantum-Mechanical Noise in an Interferometer[END_REF][START_REF] Fabre | Quantum limits in the measurement of very small displacements in optical images[END_REF] ) provides ways of decreasing the noise floor of OBD technique below the shot noise limit [START_REF] Treps | Surpassing the Standard Quantum Limit for Optical Imaging Using Nonclassical Multimode Light[END_REF] . Nevertheless these quantum optics techniques involve exotic experimental setup and the gained factor on the signal-to-noise ratio is at most ten [START_REF] Raphael | Ultrasensitive measurement of microcantilever displacement below the shot-noise limit[END_REF][START_REF] Vahlbruch | Observation of Squeezed Light with 10-dB Quantum-Noise Reduction[END_REF] . In the next paragraph we show that our classical technique, easy to implement, allows to statistically average to zero the shot noise contribution in the measured power spectrum.

The drawback of the cross correlation approach presented in the introduction (eq. 8) is the need of two independent measurement of the deflection, apparently implying a second sensor [START_REF] Mitsui | Direct optical observations of surface thermal motions at sub-shot noise levels[END_REF][START_REF] Mitsui | Measurements of liquid surface fluctuations at sub-shot-noise levels with michelson interferometry[END_REF] . We propose here a patented method 14 using only the common 4-quadrants photodetector (figure 1). Indeed, this sensor directly gives access to two independent measurements of the deflection. We define for this purpose two contrasts

C 1 = I 1 -I 3 I 1 + I 3 , C 2 = I 2 -I 4 I 2 + I 4 (14)
Those signals are equivalent to the global contrast C 0 , in the sense that they are each a direct measurement of the angular deflection θ (or vertical deflection x) of the cantilever: C n = σ θ θ + η n = σ x x + η n for n = 0 to 2. Since each contrast C 1 and C 2 involves an independent pair of quadrants, the detection noises η 1 and η 2 associated to the two signals are independent. The CSD will then converge to the PSD of thermal fluctuations of the cantilever:

S C1C2 = σ 2 θ S θ 2 = σ 2 x S x 2 (15)
This method is very simple to implement, as it does not imply any modification of conventional AFM setups, except for the data acquisition and processing. Note that torsion has no effect on C 1 and C 2 , as the normalisation per pair cancels any lateral positioning effect: if the laser beam move leftwards for instance, both I 1 and I 3 increase, but their ratio (thus C 1 ) stay unchanged. Swapping the role of quadrant 2 and 3 in the formulas, one can equivalently define two signals only sensitive to torsion. In order to illustrate the effectiveness of the noise reduction method, we compare the thermal fluctuation spectra of a cantilever computed in the usual way (with S C 2 0 ) and using the cross correlation procedure (S C1C2 )

CSD: S C ′ 1 C ′ 2 /σ 2 θ PSD: S C ′2 0 /σ 2 θ CSD: S C 1 C 2 /σ 2 θ PSD: S C 2 0 /σ 2 θ Tors. S θ ′2 (rad 2 /Hz) Flex.
Frequency f (kHz)

FIG. 2. (Color online)

Thermal noise spectra on a stiff cantilever. The 2 top graphs present the thermal noise spectra measured in flexion and torsion on the full frequency range from a 10 s data acquisition, and the 3 bottom graphs are zooms on the resonances (2 in flexion, 1 in torsion). On the top graph, the y scale is dual: angular deflection can be read on the left scale, vertical deflection on the right scale (note that the right scale calibration is only valid for mode 1). On each graph, the PSD (blue) is shot noise limited: a noise floor at 10 -18 rad 2 /Hz hides any features of the thermal fluctuations of the cantilever below this level. This shot noise contribution averages toward zero for the CSD (red): the rms value of the remaining noise is 40 times smaller after 10 s averaging. The black dashed curves are fits of the resonances with the prediction of the FTD for a simple harmonic oscillator.

on the same acquisition data. The measurements are performed in air at room temperature (T = 295 K) on a commercial silicon cantilever with aluminium reflex coating (Olympus AC160TS-R3). Its nominal characteristics are: length L = 160 µm, stiffness k = 26 N/m, resonant frequency f 0 = 300 kHz. We use a home built OBD setup, with a stabilized solid state laser from Spectra Physics (1 mW at λ = 532 nm). The laser beam is focused on the tip with a 30 mm achromatic lens, resulting in a diffraction limited circular spot (measured radius: R = 5.4 µm).

After reflection, the laser beam is sent at the center of a 4 quadrants photodiode (SPOT-4D from Osioptoelectronics). The photocurrents delivered by each quadrant of the segmented photodiode are converted to voltages by 4 independent home made low noise preamplifiers (AD8067 operational amplifiers with 100 kΩ retroaction and 1 MHz bandwidth). Analog to digital conversion is performed by NI-PXI 5922 digitizers (ADC, 18 bits, sampling rate 6 MHz, National Instruments). Therefore we measure the four photocurrents I n , and using post-acquisition signal processing, we compute numerically the contrasts C 0 , C 1 and C 2 for the flexion, and their equivalent for torsion.

We then compute the thermal noise through the PSD of C 0 , and through the CSD of C 1 and C 2 , both in flexion and torsion. Each PSD or CSD is computed using a Welch averaging on the same given time window (T = 10 s), using 2 [START_REF] Pottier | High bandwidth linear viscoelastic properties of complex fluids from the measurement of their free surface fluctuations[END_REF] points for the Fourier transform. This results in a ∆f = 183 Hz spectral resolution. We use the theoretical value for the sensitivity σ x or σ θ . Note that σ x is mode dependent, we use here only the value of mode 1: the scale for S x 2 , in m 2 /Hz, is thus only meaningful for the first mode in figure 2. The scale for S θ 2 , in rad 2 /Hz, is accurate on all the frequency range.

Figure 2 displays the measured spectra, with a zoom on the two first modes in flexion and the first mode in torsion that are visible in the explored frequency range. The background noise of the PSD is mainly due to the shot noise of the photodiodes: it is frequency-independent and its magnitude corresponds to the theoretical amplitude calculated according to Eq. ( 13), with I 0 = 164 µA for this specific measurement. Above 200 kHz, the experimental noise of the PSD deviates slightly from the expected white noise due to an additional contribution from the conditioning electronics. We can observe on the CSD that using the cross correlation approach, the background noise is decreased with respect to the PSD by a factor of around 40 after only 10 seconds of averaging. In fact, when the cantilever thermal noise is not dominant, the amplitude of the CSD tends to zero in average, and we only see the positive values in the displayed spectrum due to the log scale (the CSD is complex, we display only its real part which can be negative). This is also the reason why there are some blanks in the CSD curve far away from the resonances. The thermal fluctuations of the cantilever are much easier to see on the CSD than on the PSD: the torsional mode for example presents a signal to noise ratio below one with the PSD, but clearly emerges from the background noise in the CSD. Let us now discuss the efficiency of the crosscorrelation technique. In every frequency bin of the CSD, the root mean square value (rms) of the shot noise contribution during the averaging process decays as 1/ √ N , where N is the number of averages. This number of averages N depends on the frequency resolution ∆f and acquisition length T : N = T ∆f . The reduction of noise that can be reached depends on the properties of the signal. Here with ∆f = 183 Hz and T = 10 s , we have for instance N=1830. So the apparent noise in m 2 /Hz or rad 2 /Hz is reduced by a factor √ 1830 ≈ 42. In order to verify the decay rate 1/ √ N of the remaining rms noise, we plot in figure 3 the mean value of the PSD and the root mean square value of the CSD for the measurement in flexion around 700 kHz (where only measurement noise is expected) as a function of the number of averages N . While the PSD converges towards the background level of 10 -18 rad 2 /Hz, the CSD starts from the same background noise but decreases as 1/ √ N . At the last point displayed N = 5.5 × 10 4 , corresponding to 5 minutes of acquisition, the cross-correlation gained a factor of around 237 when we expect √ N = 234. In conclusion, the presented method allows a significant reduction of the background noise in the measurement of thermal fluctuations of an AFM cantilever. It is easy to implement as it consists only in a signal processing technique applied to the the common optomechanical setup used in most AFMs. The only requirement is the direct access to the signals of the 4 quadrants of the photodiode. It can be used to enhance the signal to noise ratio, noteworthily for the calibration of stiff cantilevers, or for higher order modes identification. This simple method can be directly applied to other research areas where fluctuations are measured with a 4 quadrants photodiode, such as passive rheology 3,4,15-17 .

FIG. 1 .

 1 FIG. 1. Schematic representation of the optical beam deflection technique: the beam of the laser (a) is focused with lens (b) on the free end of the cantilever (c). The reflected beam is centered on the four quadrants photodiode (d). Its position is a function of the local slope of the cantilever. The fluctuations of the beam position (measured through the photocurrents delivered by the quadrants) therefore provide a measurement of the fluctuations of the cantilever flexion and torsion.

C 1 C 2 ) 2 /σ 2 θPSD: S C 2 0 17 FIG. 3 .

 12222173 FIG.3. Mean value of the PSD and rms value of the real part of the CSD against the number of averages N . Each value is computed from the spectrum in flexion in the frequency range 650 kHz < f < 750 kHz. While the PSD directly converges towards a background noise, the CSD starts from the same level but the rms of the remaining noise decreases as 1/ √ N .

ACKNOWLEDGMENTS

We thank F. Ropars and F. Vittoz for technical support, C. Fretigny, L. Talini, A. Petrosyan, S. Ciliberto for stimulating discussions. This work has been supported by the ANR project HiResAFM (ANR-11-JS04-012-01) of the Agence Nationale de la Recherche in France.


Philippe David Perrain
email: david.perrain@iedom-reunion.fr

Philippe Jean-Pierre

A NEW APPROACH TO TOURISM SATELLITE ACCOUNT COMPILATION AN APPLICATION IN REUNION ISLAND

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

er the decades, tourism has experienced continuous rowth and deepenin di ersi cation to become one of the fastest rowin economic sectors in the world Since , the international tourism arri als ha e expanded at an annual rate of 7.5%, growin from million to million tra elers in In the last twent ears, this number doubled worldwide owada s, the business olume of tourism e uals or e en surpasses that of oil exports, food products or automobiles. International tourism generates billion S dollars billion uros) in export and emplo s more than hundred thousands of people in the world This spread of tourism in industriali ed states has produced economic bene ts in man related sectors -from construction to agriculture By 2020 international arrivals are expected to exceed 1.5 billion people.

Before some developments, the observation of tourism growth consists in the description of the visitors characteristics, of the conditions in which they travelled and stayed, the purpose of their visit, etc. Statistics system of tourism gave only physical data that enable to follow the frequentation of a destination. Indeed, the administrations in charge of the promotion focus on the isitors: their number, characteristics,… The activities linked to the travel of visitors, such as accommodation, sport or recreational activities, transports and food and beverages, are also observed. Furthermore, one of the main preoccupations of public sector is to measure the inbound tourism, i.e. the activities of a non-resident visitor within the country of reference on inbound trips. Resident visitors are usually left out from of the observation.

However, without economic indicators in value terms, it is difficult to "sell" tourism as significant activity for an economy and "to compare" its importance with that of other economic activities. Tourism satellite account (TSA) gives a description of economic reality of the tourism activity as relevant and as complete as possible. That is why, this paper aim is analyze the structure of a TSA and to propose an alternative approach to its implement. The first section shows the necessity of a tourism economic measurement and the utility of a TSA. The second section makes an overview of TSA methodology developed by the UNWTO. Then, the third section provides the description of this alternative approach, called supplyside approach, because it is based on the production side of the national account. At last, the last section shows the results of this implementation in a French overseas region, Reunion Island.

METHODOLOGY

Necessity of a tourism economic measurement

Tourism refers generally to the activities of visitors, and their role in the acquisition of goods and services. The focus of tourism statistics is mainly on non-monetary data. Nevertheless, with these types of data, there is no possible common language with the one used in describing other economic activities: without economic indicators in value terms, it is difficult to "sell" tourism as a significant activity for an economy and "to compare" its importance with other economic activities. There is an increasing awareness on the role that tourism plays and can play, directly, indirectly or through induced effects in the economy in terms of value added, employment, etc. These indicators are usually established from a supply side. In tourism, it is a matter of productive activities that appeal mainly to visitors. However, data mostly refer only to so called "tourism activities", i.e. accommodation, restaurants and some recreational activities. They are also not always compatible with the needs of properly identifying the characteristics of tourism activities. Furthermore, in most cases, there is no intent made to compare these data to any type of information concerning demand. The relationship between tourism supply and tourism demand is not straightforward.

Thus, an economic measurement requires going beyond traditional tourism analysis. It has to be in line with similar kinds of economic measurement in other areas. It must create a strong implication between the demand side and supply side. The use of a reference framework such as national accounts (particularly the supply and use framework) is necessary to describe this activity with indicators which help to determine the size of tourism in monetary term.

When you are seeking to describe the weight of an economy, its structure or its operation, it usually turns to national accounts aggregates and the most famous: the Growth domestic product (GDP). Indeed, the National Account gives a description of economic reality as relevant and as complete as possible. The accounting framework of the System of National Account (SNA) allows economic statistics to be compiled and presented in a data format that is designed for economic analysis purposes, decision-taking and policymaking. It also includes a specific framework showing the interface between demand for goods and services and the supply of these goods and services within an economy, namely the supply and use tables (SUT).

The SNA covers all activities in a territory but, sometimes, it is not the most appropriate tool to describe in details some of its aspects such as education, research or tourism. Classifications, which are relevant in general terms, are problematic when analyzing the tourism activity. Specific characteristics of the visitor cannot be made explicit within the core of the SNA. It already is in the SNA but it is scattered. The tourism sector is not measured as a sector in itself in National Account. It is not clearly defined industry in the international Standard Industrial Classification of all economic activities (ISIC), but rather is an amalgamation of industries such as transportation, accommodation, food and beverage services, recreation and entertainment, travel agencies, etc.

In this way, it seems appropriate to develop a specific framework concerning tourism that is now at the centre of the system. The SNA articulation is strong enough so that a great deal of flexibility can be applied (SNA, 2008). A further and more extensive form of flexibilit is that of a satellite account "Its inclusion in the revised SNA represents the maturing of a tool that has been found to add substantial flexibility to a nation's system of accounts" Grimm, ) The term "satellite" evokes a link between a specific satellite system and the main one, although the nature and intensity of the link itself is specific to each design of a satellite account. In some cases, the link will be very strong. In other cases, the link might be weaker. For instance, in a Satellite Account for transportation, it might be relevant to consider as separate productive activities all the transportation done on own account as ancillary activities. Likewise, a satellite account for the environment will usually include some types of valuation for the destruction of the environment.

Within this perspective, several international institutions such as the United Nations, the World Tourism Organization (UNWTO), the OECD and the Eurostat decided to set up the Tourism Satellite Account (TSA).

TSA Overview

TSA aims

The first recommendation on the development of the TSA conceptual framework was proposed in 2001 with the Recommended Methodological Framework (TSA:RMF) which was updated in 2008. In these guidelines, the accounting framework is designed to measure goods and services associated with tourism according to international standards, concepts, classifications and definitions. The revision of the classification of products (goods and services) and productive activities is one of the main flexibility brought by the TSA to the core of the statistic system. The International Recommendations for Tourism Statistics 2008 provide a list of tourism-characteristic products and tourism-characteristic activities to ensure consistency in the goods and services used in the TSA. The classification refers to products, mainly those belonging to tourism expenditures, and productive activities that are the basis for defining tourism industries.

These recommendations also provide definitions and concepts coming from the SNA which are essential to the understanding of the scope of the TSA. Among them, the difference between the residence of an economic agent and its nationality (is presented as an interest to the tourism). Indeed, a visitor is defined by his living in a country i.e. when they have a centre of economic interest in the economic territory of that country. It answers to most of the interrogations concerning the idea of tourism: the description of tourism consumption according to all forms of tourism; It narrows down the difference between the various demand elements of tourism consumption such as final consumption, intermediate consumption, expenditures on consumer durables or gross fixed capital.

Likewise, TSA consists in analyzing in detail all the aspects of demand for goods and services which might be associated with tourism, in establishing the interface with the supply of such goods and services within the economy of reference, or outside and in describing how this supply interacts with other economic activities. It uses the Supply and Use Table (SUT) as a reference. The SUT is a core table in the System of National Accounts. It presents the resources and uses of goods and services and how products are supplied either as domestic production by industries or as imports. The flow of goods and services is therefore traced from their producers to their users. Eventually, TSA provides macroeconomic aggregates that describe the size and the economic contribution of tourism, such as tourism value added and tourism direct gross domestic product. It is one of the main objectives of the TSA compilation (OECD, 2000).

Set of table

The UNWTO suggests to develop the TSA in the form of ten tables. They are derived from the SUT but they are different due to the presentation and the availability of the required. The first three tables identify the tourism consumption by products and forms of tourism. The table 1 focuses on inbound tourism, the table 2 on domestic tourism and the table 3 on outbound tourism. They describe all the components of tourism consumption: tourism expenditures The are defined "as the total consumption spendin made b a visitor or on behalf of a isitor for and durin his/her trip and sta at destination" nwto, 2008). They remain close to the concept of household final consumption expenditures in the SNA (apart from intermediate consumption of enterprises). The fourth table leads to the estimation of total internal consumption. It combines domestic tourism expenditures and inbound tourism expenditures. It also includes the other components of tourism consumption such as all imputed services associated with vacation accommodation on own account, tourism social transfers in kind (individual non market services) and other imputed consumption.

These tables follow the same classification of products. Therefore, three main subgroups are defined: tourism characteristic products, tourism connected products and non tourism-related consumption products. The first one aggregates goods or services which would cease to exist in meaningful quantity or those for which the level of consumption would be significantly reduced in the absence of visitors, and for which statistical information seems possible to obtain. Secondly, connected tourism goods and services include latest are appreciably affected in the absence of tourism. At last, non tourism-related tourism products are those that may be consumed by visitors, incidental to their role as visitors, and are of little interest.

Table 5 is the supply table. Its scope is similar to production accounts in the National Account. Nevertheless, classifications and some treatments are different. It presents (in rows) all goods and services that circulate in the economy of reference and (in columns) which industries produce them. It especially focuses on tourism characteristics industries.

"Table is the core of the TSA s stem: it is where the confrontation and the reconciliation between supply and internal tourism consumption take place" UNWTO, 2008). This table gives a description on how this demand is met by domestic supply and imports. It enables to evaluate aggregates like tourism value added or tourism GDP.

The seventh table gives the estimate of employment in the tourism industry. The Table 8 presents the detailed fixed capital formation of the compiling economy of produced fixed assets specific to tourism acquired by the tourism industries and by producers outside the tourism industries. Table 9 suggests a compilation of tourism collective non-market services by type of services and level of government. The last table, Table 10, presents a few quantitative indicators.

The UNWTO recommends countries to focus initially on getting at least the first six tables implemented (and also not to emphasize non-monetary flows of tourism consumption in the initial stages of developing a TSA). Thus, the aim is to estimate the tourism value added and tourism jobs.

The TSA:RMF : A demand side approach

The RMF:TSA defines tourism as a demand side phenomenon referring to the activities of visitors and their role in the acquisition of goods and services. It gives particular relevance to the aggregates that focus on expenditures and consumptions within an economy (RMF:TSA, 2008). Indeed, tourism is demand side activity. It involves that tourism has to be analyzed of standpoint of visitors, notably their purchases. It means that it had to be measured from a demand side approach (Eurostat, 2005). The first step of this approach is to estimate the internal tourism consumption. In fact, it is the core of the measurement of TSA. It is based on specific surveys on visitors trips, their expenditure,… Completing the RMF-Tables requires available data related to inbound and domestic tourism. Then, the internal tourism consumption is compared to tourism industries and others industries. The share of internal tourism consumption is established for each component of supply concerned. Thus, a tourism portion of gross value added can be associated with the value of part of the output of a productive unit and which tourism direct gross value added (TDGVA) or Tourism direct gross domestic product (TDDGP), with some adjustments.

The figure 8.1 describes the demand side approach.

A supply side approach

Why the necessity to develop this approach?

This TSA compilation requires statistics data not only for inbound expenditures but also domestic consumption. Yet, as seen previously resident visitors expenditures are usually left out from of the observation. The lack of this data (or conversely data of inbound tourism consumption) does not allow a direct internal tourism consumption estimate.

Then, tourism valued added is not directly observable. It is estimated based on visitor surveys (OECD, 2000). They have the specialists and policymakers preference because they give the ways for analyzing the links between tourist spending size and several main practical characteristics of tourists trips. Nevertheless, value added refers to the production generated by the supply side in the SNA. Assessing this aggregate from survey breaks up this link although "satellite" in TSA evokes this relationship.

At last, estimates of internal tourism consumption from surveys do not automatically match with National Account data. In France, the administration in charge of TSA compilation has highlighted this drawback. Hotel accommodation services are fully consumed by visitors. Its internal tourism consumption should be equivalent to the total production of this activity. However, in 2005, these expenditures extracted from resident and non resident visitors survey amounted to 9 billion Euros although French national accounted records 15 billion Euros.

Description of supply side approach

The first methodological frameworks emphasize the importance of the reference to SNA. In order to reinforce this link, estimates of TSA components (products and activities) have to derive directly from the data compiled in the SUT. It allows the reconciliation between visitor consumption and the corresponding supply of goods and services. It maintains the logical, accounting and statistical consistency with the SNA (Australian Bureau of Statistics, 1998). Furthermore, there are a multitude of different compilation practices. In the practice of national accounting, gross domestic product is calculated with three approaches (i.e. production approach, income approach, and spending approach) which reflect gross domestic product and its composition from different aspects. According to the statistic system, each country chooses one of them or several approaches simultaneously to estimate GDP. The majority of countries apply the production approach (United Nations, 1999). The statistical sources that are used range from specific surveys and censuses (agriculture, industry, etc.) to business accounts of public and private enterprises as well as administrative sources. TSA have to maintain the link with the approach selected by each country or by the most used: the production approach.

Visitors surveys

Internal tourism consumption

Comparison to supply component

Tourism share of each industry

Tourism direct gross value added

The regional economic account provides input-output accounts, and notably the general supply and use tables (SUT). These tables describe the general economic balance of goods and services and the production accounts of the producers. They thus enable to analyze the link between final demand and industrial output levels, as well as specific tourism transactions hidden in accounts. Commodities are broken down by each industry and by each final use. We tried to respect, as much as possible, this link starting to production estimates of tourism characteristic activities and other activities to visitors consumption This is wh this method is called a "suppl -side approach" Producers data are extracted from the supply table of the SUT. It displays an adequate breakdown into activity groups. That detailed level offers the required degree of information to obtain tourism characteristic productions.

The total internal tourism consumption is directly derived from the data compiled in the uses table, taking into consideration the share consumed by visitors. Indeed, in addition to connected or non specific activities, tourism characteristic activities are also consumed by non-visitors. Thus, a tourism share has to be estimated for each one of them. Some activities are totally designed for visitors. For instance, the service production of all the accommodation is only consumed by visitors. For these activities, the internal tourism consumption is equal to the final consumption in the SUT. Conversely, the production of food and beverage serving services or retail trade are also consumed by non-visitors. To take this fact into account, the share of visitors consumption has to be measured. Usually, the comparison between the internal tourism consumption and the production of tourism industries and others industries determines tourism ratios for each component of supply concerned.

Estimates of tourism ratios

The lack of data and the voluntary to reinforce the link with regional accounts are compelled to find another solution. Sources and estimates methods can differ from one activity to another. However, we mainly used results of a CSO study of tourism employees. It allows producing tourism share of employment that are applied to define the production boundaries of tourism. Indeed, the CSO developed a methodology which allows estimating the number of direct employment related to the tourism activities for each establishment according different criteria. The aim of this study is to better account spatial effects. Thus, an establishment can be described as "tourism" and its job then recorded as "tourism", according to more or less of its tourism activity and the level of tourism facilities in the municipality .Moreover, the employment seasonality in each activity enables to take into account the surplus of jobs related to the presence of visitors. The methodology also tries to measure the impact of tourism in living areas where there is very little seasonality such as major cities (Paris, Lyon, etc.). In this case, they estimated the number of jobs related to the resident population and, by subtraction, the number of tourism, according to the ratio "emplo ment per population" in similar li in areas The crossin of these criteria permits to define decision rules (cf. figure 1).

Thus, if the industry is not 100% tourism, tourism shares of employment are used, except some cases such as fuel expenditures or sport activities. The ratio is calculated with estimates of visitors (inbound and domestic) consumption reported into the SUT. Nonmonetary indicators are also used.

The table 8.1 represents decision rules in terms of tourism employment according the activity and the localization of the establishment.

The main source: an administrative registration

The main source of these works is an administrative registration: the annual declaration of social data (ADSD). The ADSD is a declaratory formality which has to be fulfilled by any enterprise with employees. It is a common document for the social security and the fiscal administration. This database contents information relating to the establishment and its employees. Thus, for each employee the following information is reported: the nature of the employment and qualification, date of start and end of pay period, the number of employed hours, the condition of employment (full time, part-time), the amount of compensation paid, etc. The ADSD field covers all the establishments with employees, except central administrations and the state agents. This administrative obligation existed since 1947, in France, and the CSO used this information since 1970. Usually, the problem with registrations is that they are set up for administrative and not for statistical reasons. However, in this case, it enables to produce robust statistics on wages and employment, notably their characteristics. Employees data are consolidated at the establishment level.

Tourism direct gross value added and internal tourism consumption

Similarly to the National Account, the main purpose of this method is to estimate tourism value added. Tourism ratio enables to estimate a touristic fraction of value added for each activity. The sum of all these portions over all industries is called tourism direct gross value added (TDGVA). Thus:

, where Touri is the tourism share for the activity i and VAi, the value added of the activity i. To obtain the tourism direct Gross Domestic Product (TDGDP), it is necessary to add to TDGVA, the taxes on production and imports less subsidies on products and imports related to tourism products.

The SUT enables the transition between producers and visitors. It ensures the link with the tourism value added (in basic price) for each activity and the internal tourism consumption (in purchase price) for each product. Both estimates of domestic tourism consumption and inbound tourism consumption derive from the estimate of internal tourism consumption. The repartition between these two components differs from one product to another. The main source used is an inbound tourism survey. Since 1989, the regional agency of CSO and the regional tourism administration conducted a survey of tourist flows from passengers departing from airports in the island. Its objective is to estimate the numbers of tourists and to know their motivations, their modes of accommodation and their expenditures in accommodation, foods and beverages, souvenirs, etc. Surveys were continuously realized every three days. Thus, 376 flights were surveyed, 21 826 cards collected on average every year. For the products which the inbound tourism expenditures provided this survey, the domestic consumption is obtained by subtracting from internal tourism expenditures. Others sources are also used. Physical indicators give also information about the origin of visitors, who use some tourism characteristic services. For example, hotel accommodation and occupancy surveys record on overnight stays distributed by country of residence of the travellers. At last, in the absence of quantitative data, professional advices can help in this method.

The RTSA contents also tables of physical data and tourism employment. The last one goes beyond the recommendations, in covering employees and self-employed in tourismdependent industries, not only in tourism industries. Nevertheless, this table of employment tourism has been too much generalized. It cannot allow treating this tourism component as a social phenomenon and a tradeable product on a (labour) market.

The figure 8.2 shows a representation of the supply-side approach

Results

Reunion Island is a French overseas region and an ultra-peripheral region of Europe. Born of two volcanic eruptions, the island is a tropical island off the east coast of Africa in the Indian Ocean. The island offers an interesting alternative to the typical tropical getaway. It treats the travelers to a diversity of landscape which includes tropical forests, jagged mountain peaks, lava fields and coastal resort towns. Consequently, Tourism is to gain more and more to gain importance for public deciders. Consequently, it appeared necessary to develop observation tools such as a tourism satellite account.

This approach was applied on data dating from 2005. The internal tourism consumption was estimated at 846 million Euros. On the one hand, it includes non-resident expenditures for and during their trip. On the other hand, it integrates all the resident expenses on the island as well as in enterprises oriented to outgoing tourism and set up on this French region. The transport (by road, water or air) is the first expenditure with 30% of the internal tourism consumption. It is the largest one because Reunion Island is far from its clients who mostly come from mainland France (more than two thirds derive from air transport). Furthermore, the island is mainly visited by car which explains the large place of car rental (22% of transport spending). Visitors spend 242 million euros in retailers, street markets or directly from producers to purchase goods, in particular gifts, souvenirs and fuel. It represents the second source of spending and it is ahead of the emblematic tourist acti ities: "hotel and restaurant" one uarter of the total) Domestic tourism consumption is estimated at 480 million euros. With 57% of the internal tourism consumption in 2005, it is superior to the inbound one. Reunion Island has a tourism economic model different from the small island developing states such as Mauritius -the nearest island -where domestic expenditures represent only 15 % of the internal tourism expenditures. In fact, this domestic component almost reaches of the average of the 36 European Travel Commission member countries.

The distribution fluctuates between domestic and inbound tourism depending on the activity. Resident visitor expenditures are more significant in travel agencies (75 % of this expenditure is carried out by residents), in retailers (70%) and in food and beverages (55%). Conversely, non-resident visitor expenditures are larger in car rental (81% of rental expenses) and in recreational activities (57%) because it is a further activities during their trip. Sometimes, sport or recreational activities are the vary aim of their trip. Finally, in all of the accommodation, inbound visitors represent 53 % of these service expenditures. This proportion varies according to the accommodation. It is higher in the hotel industry (67%).

In the figure 8.3, we can observe the repartition of expenditures by residence visitors in Reunion Island in 2005. The tourism consumption structure results from different behaviors according to the isitors' origin. For residents, tourism expenditures are based on two main themes: the desire to vacation outside the island (36% of their expenditure are allocated in transport and travel agencies) and the need to get away while remaining on the island which explains the weight of expenditures on trades (35%). The distance weighs on non-resident expenses. Transport corresponds to 27% of total expenditures. Moreover, the requirement for leisure and business visitors of housing, feeding (food service) and moving around the island leads to greater use of these services (39% of expenditures for non-resident visitors against 23% for domestic visitors).

The direct value added generated by all the activities that provide goods and services to visitors is estimated at 290 million Euros or 2.6% of the total added value created in the department in 2005. Accommodation activity is the largest contributor with more than one quarter of tourism value added. In this application, the tourism share on total GDP was not calculated. Indeed, some tourism activities such as accommodation receive subsidies on investment or on operating expenses. It is difficult to identify exactly their impacts on GDP. Furthermore, taxes on tourism products are depending on the activity. The tourism contribution of wealth creation is lower than some destinations such as Mauritius where tourism represents 11.2% of the GDP. Nevertheless, the tourism industry of the island is undersized compared to the "sister island" For example, in , Reunion had less than one uarter of the hotel room capacity Mauritius had. However, its part to the wealth of the island is greater than the primary sector (1.8%) or the food industry (2.1%). In this way, tourism contributes to the diversification of the economy of the island. It is also the principal export earner. It generates 40% more revenue than the total exports of manufactured goods. Tourism creates 9 000 direct jobs in all the island, i.e. 4% of the total employment.

CONCLUSIONS

The aim of this paper was to propose a new approach to tourism satellite account with an application in Reunion Island. In fact, our motivations were to overcome the traditional analysis of tourism based on observation of tourism growth and the description of the visitors characteristics, etc. On the contrary, we tried to deep inside the economic reality of the tourism activity using the tool of the Tourism Satellite Account adding to the classical framework based on the demand side an alternative way called the supply side approach. Moreover, this work put a new light on the tourism strategy employed by Reunion Island.

This article can open new researches. In the first, it is necessary to investigate on the share of tourism of each tourism activity to evaluate their robustness. Secondly, the comparison with other countries is a second axe of research in order to test our approach to others methodologies. At last, The TSA:RMF does not take enough into account the tourism employment. Its measure in the table 7 of this guideline is not adequate. The employment estimates have to move beyond this picture and to describe the nature of employment, the quality of employees, etc. To remedy at this lack, it is important extend the scope of the RTSA, by including a set of detailed employment tables -an employment module -such as proposed the OECD.

Figure 8 . 1 :

 81 Figure 8.1: Representation of demand side approachSource: the autors

Figure 8 . 2 :

 82 Figure 8.2: Representation of supply-side approachSource: the autors

Figure 8 . 3 :

 83 Figure 8.3: Repartition of expenditures by residence visitors in Reunion Island in 2005 Source: CEROM 2009

  8.4, we can observe the repartition of value added by industry in Reunion Island in 2005.

Figure 8 . 4 :

 84 Figure 8.4: Repartition of value added by industry in Reunion Island in 2005 Source: CEROM 2009

Table 8 .1: Decision rules in terms of tourism employment according the activity and the localization of the establishment

 8

	Living area	High level of tourism	Middle level of tourism	Low level of tourism
	Activity	facilities	facilities	facilities
	100% tourism	all employment	all employment	all employment
	Highly tourism	Total employment less resident employment	Total employment less resident employment	None employment
	Middle tourism	Total employment less resident employment	Total employment less referent* employment	None employment
	Low tourism	Total employment less referent* employment	None employment	None employment
	No tourism	None employment	None employment	None employment
		* Referent employment: employment except tourism seasons
		Source : INSEE


Evolutionary Epidemic Routing

Keywords: Wireless networks, delay-tolerant networks, epidemic forwarding, evolving protocols, genetic algorithms

In this work, we introduce a framework which allows forwarding schemes to evolve in order to adapt to changing and a priori unknown environments. The framework is inspired by genetic algorithms: at each node a genotype describes the forwarding scheme used, a selection process fosters the diffusion of the fittest genotypes in the system and new genotypes are created by combining existing ones or applying random changes. This framework is illustrated through a simple case study and simulations are undertaken to evaluate its performance.

Introduction

Epidemic-style forwarding [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF] has been proposed as an approach for achieving packet delivery in Delay-Tolerant Networks (DTNs) [START_REF] Fall | A delay-tolerant network architecture for challenged Internets[END_REF], in order to ensure system-wide dissemination of messages in face of frequent disconnections [START_REF] Zhang | Routing in intermittently connected mobile ad hoc networks and delay tolerant networks : Overview and challenges[END_REF][START_REF] Pelusi | Opportunistic networking : data forwarding in disconnected mobile ad hoc networks[END_REF]. DTNs are sparse and/or highly mobile wireless ad hoc networks where no continuous connectivity guarantees can be assumed. Epidemic-style forwarding in DTNs is based on a "store-carry-forward" paradigm : a node receiving a message buffers it and carries that message as it moves, passing the message on to new nodes that it encounters. Analogous to the spread of infectious diseases, each time a message-carrying node encounters a new node that does not have a copy of that message, the carrier may decide -according to some specific policies -to infect this new node by passing on a message copy ; newly infected nodes, in turn, behave similarly. The destination receives the message when it first meets an infected node.

An unconstrained epidemic forwarding scheme (in which an infected node spreads the epidemic to all nodes it encounters) is able to achieve minimum delivery delay at the expense of an increased use of resources such as buffer space, bandwidth, and transmission power. Variations of epidemic forwarding have been recently proposed in order to exploit the trade-off between delivery delay and resource consumption. This family includes, among the others, K-hop schemes [START_REF] Groenevelt | Message delay in mobile ad hoc networks[END_REF], K-copy techniques [START_REF] Chaintreau | Impact of human mobility on the design of opportunistic forwarding algorithms[END_REF], probabilistic forwarding [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF][START_REF] Haas | A new networking model for biological applications of ad hoc sensor networks[END_REF], and spray-and-wait [START_REF] Spyropoulos | Spray and wait : an efficient routing scheme for intermittently connected mobile networks[END_REF][START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF]. These schemes differ in their "infection process", i.e., the spreading of a message in network. They need to be combined with a "recovery process" that deletes copies of a message at infected nodes, following the successful delivery of the message to the destination. Various recovery schemes have been proposed : some are simply based on timers, others actively spread in the network the information that a copy has been delivered to the destination, using so-called antipackets [START_REF] Haas | A new networking model for biological applications of ad hoc sensor networks[END_REF].

Depending on the specific application scenario, different performance metrics could be envisaged. These include, e.g., the probability to successfully deliver a message to the destination, the delivery time, the total energy consumption in the system or a combination of the previous ones. For a given optimization goal the choice of a specific forwarding scheme and the configuration of its parameters depend in general on the number of nodes in the system, on their mobility patterns and on the traffic generated in the networks [START_REF] Neglia | Optimal delay-power tradeoff in sparse delay tolerant networks : a preliminary study[END_REF]. In many scenarios, these characteristics cannot be known at system design and deployment time and can also significantly change across time and space. For example, let us consider a personal digital assistant carried by a user in its daily activities. During the day the node can travel at different speeds (e.g. from zero up to car speed), moving from highly crowded areas (supermarkets, classrooms,...) to less crowded ones, with very different trajectories (straight along a highway or following a random walk from shop to shop) and different levels of power availability.

In order to deal with these issues, various adaptive techniques for message forwarding can be envisaged. This approach is limited in that it requires an a priori definition of the actions to be taken to optimize the mechanism for some specific situation. The approach we propose is different. We want to embed the ability to evolve autonomously in the forwarding service itself. This is achieved by using concepts and tools from the Genetic Algorithms (GAs) field. Each node employs a (potentially different) forwarding policy, which prescribes the operations to be undertaken when receiving a message destined to another node. Such policy is described by an array of parameters called the genotype. Genotypes are associated with a fitness measure which, roughly speaking, indicates the ability of the current set of parameters to achieve good performance in the current environment. Fitness is evaluated using local information and feedback which is sent from the destination backwards within ACK messages, which act also as antipackets. When two nodes meet, they may exchange genotypes (and associated fitness levels), updating the pools they maintain. Each node periodically generates a new genotype judiciously using those in its pool and implements the corresponding policy. The whole system is engineered in such a way to present a drift towards higher fitness levels.

The rest of the report is organized as follows. Section 2 overviews the evolutionary delay-tolerant forwarding service engineered in this report, and presents the multiple components of this service : the forwarding policy followed by each node and its unified representation ; the selection process of good forwarding policies and the fitness evaluation process ; and the generation of new policies. A case-study implementation is described in details in Section 3. The outcomes of a simulative study, performed using a freely available software tool, are reported in Section 4. Section 5 concludes the report describing some open research issues.

A Framework for Evolution of Forwarding Services

As mentioned in the previous section, in this work we aim to develop a framework that will allow the forwarding service to evolve online in order to optimize a given performance metric and to adapt autonomously to the actual system operating conditions. In order to increase the readability of the report, all the notation employed is summarized in Table 1.

We first observe that multiple forwarding schemes can co-exist at the same time in the network. In fact this form of information delivery, based on the presence of multiple copies in the network, does not need nodes to be compliant with a specific behavior, enhancing system robustness with respect to conventional schemes. This flexibility comes from the completely distributed nature of the forwarding process in epidemic-style relaying, which allows node to use different policies in an uncoordinated fashion.

In our framework, each node can apply a distinct forwarding policy to relay messages to other nodes. We want nodes to learn online what is the best forwarding policy (or what are good policies) in the current scenario and change consequently the one they employ. We note that a node cannot evaluate by itself whether its current policy fits the current scenario, because it is in general not aware of the consequences of its actions. For example a given node can never know by itself whether its decisions -according to its forwarding policy -to relay or not to relay a message were the right ones or not. Thus, a node may be relaying a message when the latter has already been delivered to its destination, hence wasting resources. On the other hand, a node may refrain from relaying a message when it happens to be the key node in the message delivery process, e.g., if it is the only node traveling between two disconnected clusters of nodes in the network. It should be clear therefore that only other nodes in the system can evaluate the fitness of a node's forwarding policy. We also observe that the goodness (or fitness) of a node's policy depends on the policies implemented by the other nodes as well. Message delivery is in fact a collaborative process, whose performance depends on the behaviors of all nodes, so that a specific policy can be beneficial or detrimental depending on other nodes actions.

INRIA

The previous considerations imply the need of an online distributed fitness evaluation process and raises an issue about the use of the fitness in the evolution process. Once a node get marks for its own policy, how should these be used in order to change the policy ? We opt for a blind evolutionary approach, which relies on the following assumption : Assumption 2. [START_REF] Blum | Metaheuristics in combinatorial optimization : Overview and conceptual comparison[END_REF] The set of nodes in the network can be partitioned in "large" groups of homogeneous nodes having similar mobility models and traffic patterns.

If this assumption holds then each node can learn from nodes in the same group : it can make its policy more similar to those policies presenting a higher level of fitness. This suggests that two other components are required in our framework : a unified description of the policies, so that each node can communicate to other nodes the one in use, and mechanisms for the derivation of new (hopefully better) policies from existing ones.

Here we summarize the three fundamental components in our evolutionary framework using genetic algorithms terminology. These components are :

1. the possibility to share with other nodes a description of the specific forwarding mechanism deployed at each node (the genotype associated to the forwarding policy employed at the node) ;

2. the possibility for each node to modify its forwarding scheme taking into account the schemes of other nodes (what we call, with a slight abuse of terminology, the genotype evolution) ;

3. a consistent process for evaluating the fitness of the schemes employed, rewarding "good" solutions in such a way to foster the diffusion of the fittest forwarding genotypes (performing a sort of natural selection).

In the following, we will describe in more detail these three components. But first we briefly describe the differences with respect to conventional genetic algorithms or genetic programming approaches.

Differences with Genetic Algorithms

A genetic algorithm (or GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems, using techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossing-over [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF].

GAs have been successfully employed and showed to perform well over a wide range of optimization problems arising in sciences. It is nonetheless worth recalling that, in general, GAs do not outperform other search techniques (this is a direct consequence of the classical no-free-lunch theorem [START_REF] Wolpert | No free lunch theorems for optimization[END_REF]), but it all depends on the peculiar structure (also referred to as "fitness landscape") of the problem under study. We decided to focus on GAs since they already showed to be able to perform well over commonly found fitness landscapes, while on the other hand presenting a low complexity from an algorithmic perspective.

Let F (x) denote the function to optimize, where x is an abstract representation (called the genotype) of a candidate solution. The fitness of a genotype x i is defined as φ i := F (x i ), i.e. the function to optimize evaluated at x = x i . Genetic algorithms are implemented as a computer simulation in which a population of genotypes evolves toward better solutions, i.e., solutions characterized by a higher fitness level. The evolution usually starts from a population of randomly generated individuals and occurs in discrete steps ("generations"). In each generation, the fitness of every individual in the population is first evaluated, then multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly mutated) to form a new population. The new population is hence used in the next iterative step of the algorithm. The procedure stops when a "good enough" solution (i.e., one whose fitness level exceeds a given threshold) is found.

In our framework, the population is the set of genotypes present in the system, each genotype representing the forwarding policy of a node in the network. Let us assume there are N nodes and thus N genotypes. Coherently with the above notation, we denote as F (.) the function to be optimized (usually the expectation of a metric of interest), and x i the genotype used by node i. According to the discussion presented at the begin of Section 2, the performance metric depends, in our case, on all genotypes present in the system, i.e.,

F = F (x 1 , x 2 , • • • , x N ). So a candidate INRIA
solution is no longer a single genotype, but rather an array of N genotypes1 . A simple N -times repetition of the same genotype may well be an optimal solution. However, in general, this will not be case. Since F depends on all genotypes present in the system, we cannot consider φ i , the fitness of genotype x i , to be the corresponding value of the function to optimize (like in conventional GAs) 2 . We need to have a new definition of the fitness such that fitter genotypes yield better performance according to F . We are going to provide it in Section 2.3.

Another difference in comparison to standard GAs is that many functions F (•) we are interested in (e.g. delivery delay and number of copies) have no closed form in general, but can only be estimated online measuring the performance of the actual running system. This estimation (and hence the estimation of fitness values) will potentially be affected by the randomness inherently present in nodes' mobility, data traffic pattern and wireless channels fluctuations.

Further, in our framework, evolution is an open-ended process, in that the system needs to be able to react to unpredictable changes in the environment. While some of these issues are not new in the community working on evolutionary computing strategies [START_REF] Jin | Evolutionary optimization in uncertain environments -a survey[END_REF], their application in the proposed framework is far from being straightforward.

The Forwarding Policy

A first step towards an evolutionary forwarding service consists in a formal representation of a generic forwarding scheme. Such descriptions represent the genotypes of the implemented forwarding schemes.

A forwarding policy consists of a set of actions to undertake upon message reception. It defines what nodes do when they become within mutual transmission range. The actions can be specified using parameters and may rely on information contained in message headers (like message generation time or count of hops the message has traversed). For instance, a node can transmit a message with probability P as long as the message has not been forwarded more than H times. The values of the two parameters uniquely specify one forwarding policy. A simple binary string can be used to represent the policy as illustrated in Fig. 1, where the genotype spans 12 bits. The 6 leftmost bits represent the numerator a of the fraction a/63, which is the forwarding probability value P , while the 6 rightmost bits represent the maximum number of hops H. Hence, out of such representation it is possible to reconstruct the corresponding forwarding policy.

The behavior of a generic forwarding scheme can thus be changed by tuning the values of the parameters that specify the actions to be undertaken.

The Selection Process

The natural selection process promotes the diffusion of organisms presenting a high fitness level. In much the same way, we want to engineer mechanisms for promoting the diffusion of "good" genotypes already present in the population. Those would be the genotypes yielding good performance for the optimization goal. At the same time, new genotypes can be generated in order to explore new possible solutions. In this section, we focus on the first issue letting the next section discuss how new genotypes can be generated from existing ones.

In traditional GAs, reproduction is a process which selects existing genotypes to create new offsprings. At discrete time intervals, genotypes are randomly selected from the population to generate offsprings : genotype x i is selected with probability proportional to its fitness, namely, p i := φ i / j φ j . This procedure tends by itself to increase the average fitness of the population. However, in the considered mobile network scenario the different genotypes are distributed over all the nodes of the network. This means that standard GAs reproduction phase can not occur without resorting to a centralized solution where a central node (i) stores the genotypes, (ii) applies GA operators, (iii) distribute back the produced offsprings to the mobile nodes. In order to overcome this limitation, we assume that upon meeting nodes exchange information about their respective genotypes and the corresponding fitness indexes. As depicted in Fig. 2, in our system each node maintains a pool of available genotypes (including the one currently in use) and their corresponding fitness values. At regular time intervals, each node goes into a reproduction phase, running the selection process on the genotypes currently stored in its own pool.

We now need to devise a new definition of the fitness (cf. Section 2.1). For the sake of simplicity, we consider that the function to optimize, F , is the expected value of some performance metric, say f , which can be evaluated for a specific infection process. More formally let I refer to the complete history of a generic infection process in the network. An infection I m reports all of the infection steps since the generation of message m until the cancellation of the message and all its copies. For example it specifies which nodes are infected at a given time instant. The infection I m depends on the genotypes and the mobility patterns of all nodes involved in the infection process but also on the concurrent data traffic at these nodes. The function that we want to optimize can be rewritten as F = E[f (I)] where the expectation is taken with respect to the probability measure defined by the mobility and message generation processes. Examples of performance metric f (I) are the time needed to deliver a message to the intended destination, the time before an infection dies (i.e., when all copies are erased from the network), the number of copies done for a given message and the power required to propagate the message.

Observe that an infection I will most likely involve only a subset of the nodes in the system. Conversely, a given node i will take part in only a subset of all infections. The fitness of a genotype x i can be defined then as

φ i = E[f (I) | node i contributed to infection I] . (1)
This ensures that the genotypes of nodes taking part in "good" delivery processes get on average a higher fitness than those involved in "bad" diffusion processes.

According to [START_REF] Blum | Metaheuristics in combinatorial optimization : Overview and conceptual comparison[END_REF], for a node to estimate the fitness of the genotype it is using, it should average the performance metric f (I) over all infections it had taken part in. A difficulty arises from the fact that the forwarding service is intrinsically a cooperative distributed service and a node is in general not able to evaluate by itself f (I). For example the node does not know whether or not a message has been delivered, when or how many times it has been copied in the system, and so on. Some communication among nodes is thus required in order to let each node be able to evaluate f (I).

In many cases, the process of evaluating f (I) can be triggered by the destination node of a message as it is the best entitled to evaluate the outcome of the infection process. The destination node propagates then the evaluation of f (I) or at least information needed for this evaluation to all nodes involved in the infection process. The communication cost can become significant so that a communication-cost versus information-accuracy trade-off arises. Beside the communication overhead, another aspect to consider is the time needed to evaluate the performance metric f (I). If information is delivered to a node long after message delivery, the node could have changed its genotype, so that the evaluation would not refer to the current genotype.

Generation of New Forwarding Policies

New forwarding policies are generated applying GA-like operators to the genotypes maintained by a node in its pool. The two following operators can be used to create new genotypes from existing ones. Crossing-over consists in breaking two genotypes at a randomly chosen position and exchanging the tails of the genotypes. Two offsprings, called crossovers, are produced, and one is selected at random. Mutation consists in a random change occurring in the genotypes. As an example, mutation can be implemented by randomly swapping, with some probability, the bits of a binary representation of the genotype. For ensuring stability, mutation should occur with small probability.

Adaptation vs. Evolution

A possible critic to the framework presented is that it embeds a complex form of adaptation rather than a form of evolution, because the nodes will finally select one genotype out of a finite set. We think that the distinction between adaptation and evolution is in part a problem of scale. Even human DNA has only a finite number of possible different combinations, enabling natural evolution to only choose in a limited set of genotypes. The critical point seems to be the expression capacity of the adopted genotype description. The higher this capacity (and a higher capacity in general requires a more complex language), the larger the number of possible behaviors, perhaps to the extent that the system will start exhibiting some new (unforeseen) behaviors.

Mechanism Specifications

In this section we propose a case-study implementation of the proposed approach, aiming at gaining insight into the applicability of the proposed approach to epidemic-style forwarding in delaytolerant networks. In particular, our purpose is to provide a first answer to the following questions :

(i) Does the distributed genetic algorithm "converge" ? (ii) If so, what does the convergence point look like and how much time is required for the convergence ? (iii) What are the performance with respect to an optimally configured static forwarding scheme ? These questions will be tackled by implementing a (reduced) version of the proposed framework, and running numerical simulations to evaluate, in a realistic scenario, the behavior of the system.

Implementation of the Evolutionary Process

We consider a simple fixed-length genotype comprising one parameter, which is the probability P to copy a message upon encountering a new node.

Let W denote the set of nodes which contributed to the delivery of the first copy to reach the destination. As optimization goal we consider the minimization of the expectation of the weighted sum of the delivery time, T D , and the number of message copies made by the nodes in W . The cost INRIA function is then

F = E T D + γ i∈W C i , ( 2
)
where γ is a parameter which can be understood as the time-equivalent cost of a copy. Should the optimization goal be to minimize solely the expected delivery time, then the evolutionary forwarding scheme will trivially converge, in a underloaded network -i.e., when traffic is small in comparison to the available capacity -to standard epidemic routing, where messages are flooded in the entire network. Conversely, the presence of the number of copies in the cost function makes also an underloaded network (a realistic case and faster to simulate) an interesting scenario to study. The evolutionary forwarding scheme will limit the number of copies depending on the value of the parameter γ. Taking into account the number of copies is also meaningful because they are strongly related to bandwidth usage and power consumption. A more natural choice would be to consider the total number of copies done in the network (i.e. N i=1 C i ), but a heavier communication overhead would be required. In our case-study we opt for light signaling.

We assume that all nodes are synchronized and that the message header contains a field specifying the time at which the payload was generated at the source 3 . In such a way the destination can evaluate the delivery time as soon as it receives the first copy of a message. On the other hand, each node knows the number of times it has copied a message, but not the delivery time. We assume that each node, before forwarding a copy of a message, adds its own identifier to the message header (this is analogous to what is done in source routing in mobile ad hoc networks). The set W is nothing but the set of node IDs present in the header of the first copy reaching the destination. The destination node sends to nodes in W a new acknowledgment (ACK) message. This message specifies the delivery delay and the number of hops (h = |W |) traveled by the message before reaching the intended destination. In this way each node i along the path of the first copy delivered has the following information available : the delivery time, the number of hops in the path and the number of copies it did C i , the latter value being computed locally at each node. The node evaluates the "reward" obtained for having taken part to the infection, as a decreasing function of the quantity T D /h + γC i , which we refer to as the "reward" obtained for having taken part to the infection. The fitness of the genotype is then estimated as the average of the rewards obtained. During the selection phase, nodes select genotypes with higher fitness level, so they implicitly select genotypes yielding smaller T D /h + γC i . The intuition behind this choice is that in this way the system is minimizing 4 :

E i∈W (T D /h + γC i ) = E T D + γ i∈W C i ,
which is exactly the cost function given in [START_REF] Chaintreau | Impact of human mobility on the design of opportunistic forwarding algorithms[END_REF]. We note that considering the total number of copies would have required each node to be informed about the number of copies done by every other node in the system.

We consider the following expression for the reward at node i :

r i = max 1 - T D /h + γC i R , 0 (3)
where R is set to a high enough value, for instance 2E[T D ] + γN . Upon receiving the n-th ACK message and computing the reward r i (n) according to Eq. 3, node i updates its estimation of the genotype fitness as follows :

φi (n) = n -1 n φi (n -1) + 1 n r i (n), (4)
which corresponds to averaging all rewards received. When two nodes meet, they transmit to each other their own genotype and its current fitness level estimation. Each node maintains a pool of available genotypes (including the one currently in use) and their fitness. We use G j to denote the pool at node j and φi,j to denote the fitness value of node i genotype known by node j ( φi,j is the value of φi at the time of the last meeting between node i and node j, so at a given time instant these two values can be different). We consider a synchronized reproduction phase. Every T g seconds, the generation lifetime, nodes synchronously create a new offspring each, i.e., they update their own genotype. This synchronism allows to clearly identify different generations during the evolution. Crossing-over is performed with probability p c and requires to select two genotypes from the pool, otherwise only one genotype has to be selected. At each node, e.g., at node j, genotypes are selected with a probability proportional to their own fitness 5 , namely, p i,j = φi,j /( l φl,j ) where the sum is over all genotypes contained in the pool G i . Finally each bit of the current genotype, directly selected from the pool or obtained through a crossing-over of two genotypes, can mutate with probability p m . The genotype pool is emptied after every generation, and the fitness value of the genotype that will be used is set to zero. If the network is large, the node's pool may not be large enough to keep all genotypes discovered in a generation. Should this be the case, a node may keep only the fittest genotypes, or alternatively select the genotypes according to a fitness-biased distribution.

Message Structures and Communications

Two nodes are able to exchange messages when they get within mutual communication range. Once it happens, they perform the following steps :

1. exchange node IDs ; 2. exchange header information of data messages ; 3. each node decides which messages should be forwarded to the other node ; 4. messages are exchanged ; 5. each node can drop some messages from its buffer (if full) in order to free space for new messages.

The evolving protocol makes use of two types of messages to be exchanged over the network : DATA messages and ACK messages. DATA messages are those carrying the payload transmitted by any mobile node to a specific destination, whereas ACK messages are used for the following purposes :

-to acknowledge the successful delivery of the message at its intended destination ; -to feed back the reward to the nodes along the successful path from source to destination (rewarding) ; -to serve as anti-DATA, by blocking the diffusion of already delivered messages and removing them from nodes buffer. The fields common to all message headers are (i) [message ID], which is the (unique) identifier (ID) of each message and also specifies whether it is a DATA or an ACK message (ii) [GenTime], which describes the time at which the message has been generated.

Further, data messages include a hop-count field [hops] and the labels of all nodes which forwarded the message along the path from the source to the actual node. ACK messages, on the other hand, include the complete set of nodes involved in the forwarding path and a field, called [Feedback], containing the value of the rewarding metric T d /h, where T d is the DATA message delivery time, and h is the value of the field [hops] when the DATA message was received by the destination (i.e., the length of the source-to-destination path).

Each mobile node maintains two internal data structures dedicated to the storage of DATA and ACK messages respectively. In the structure storing DATA messages, each item additionally stores a counter of the number of copies of that message already disseminated in the network.

Whenever a node receives a DATA message to be relayed, it first adds its own node ID to the header and then increments by one the [hops] field of the message. The message is kept in the node's internal memory until the corresponding ACK message is received.

In addition to DATA messages, mobile nodes diffuse also ACK messages. Unlike the case of DATA messages, no limiting policy is applied to the forwarding of these messages (ACK messages are simply flooded into the network according to the VACCINE recovery scheme [START_REF] Zhang | Performance modeling of epidemic routing[END_REF]).

Whenever it receives an ACK message, a node first adds the received ACK message to the internal message list. It then checks whether the corresponding DATA message is present in its internal memory and, in case, removes it. If the corresponding DATA message was present and the node has contributed to the successful path to the destination (Node ID ∈ W = {Node ID 1, . . . , Node ID M }), it applies the proper rewarding scheme to update its own fitness, as described in the previous section. The overall procedure is summarized in Algorithm 1.

Algorithm 1 Algorithm performed by a node upon reception of an ACK message.

1: Add the received ACK message to the internal ACK messages list 2: if msgID ∈ {msgID 1, . . . , msgID L} then 3:

Remove the corresponding DATA message from the internal structure.

Numerical Results

In order to evaluate the performance of the presented algorithms, we run extensive simulations using the freely available simulation tool OMNeT++ [START_REF]OMNeT++ Discrete Event Simulation System[END_REF].

We consider N mobile nodes, moving at constant speed v over a L × L square playground according to the random direction mobility model [START_REF] Royer | An Analysis of the Optimum Node Density for Ad hoc Mobile Networks[END_REF]. Each node selects the angular direction of its next movement uniformly in [0, π], moves along this direction with a uniform speed ; upon reaching the border, it generates a new angular direction and moves accordingly. The initial locations of nodes are sampled from a uniform distribution which is the stationary distribution of nodes' location under this mobility model (perfect simulation).

Distinct nodes are considered to be in communication range if the mutual distance falls below a threshold r, the communication range. Each mobile node generates a DATA message in a time interval which is uniformly distributed between 0 and T s seconds, with a destination chosen uniformly among the nodes in the simulation. Each message generated is stored in the out queue of the generating node. The position of every mobile node in the simulation is updated every T step seconds. Each generation lasts for T g units of time.

The specific values used are in Table 2. Genetic algorithm parameters (p c , crossover probability, and p m , mutation probability) are taken to be fixed. The investigation of performance sensitivity to these parameters is left to future work.

As regards the genotype, the forwarding probability P has been quantized non-uniformly using 5 bits for the representation. Such parameter can take values in the set (i/31) 1.5 , i = 0, 1, . . . , 31 .

INRIA A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A 0 10

Static Scenario

We first consider a case where the number of nodes is kept constant (N = 20) throughout the simulation run. The time-equivalent cost of one message copy is set to γ = 800. The N initial forwarding probabilities are chosen independently in the set of possible values according to a uniform distribution.

Figure 3 depicts the forwarding probability values present in each generation. As it might be seen, after a few generations only small probabilities are used across the population, but for some occasional high values due to random mutations. Simulations with different initial random seeds show similar results.

Figure 4 shows the corresponding evolution over time of the cost (2), expressed in seconds. Observe how the cost rapidly decreases across the first generations and how it "converges" to an almost constant value after 6 generations. Again, running simulations with different initial random seeds yields similar conclusions.

Comparison with Probabilistic Forwarding

We have conducted a series of simulation runs in which message dissemination was achieved through traditional probabilistic forwarding [START_REF] Lindgren | Probabilistic routing in intermittently connected networks[END_REF] ; that is, a scheme in which all nodes use the same constant forwarding probability. We ran simulations varying the forwarding probability P from 0 to 1 and computed the cost for γ in {100, 400, 800, 1600}. For each value of γ we conducted simulations using our evolutionary forwarding scheme.

Figure 5 reports the cost, as expressed in (2), achieved by the probabilistic forwarding scheme against the forwarding probability. The cost achieved by our scheme is also reported for the sake of comparison. As it might be expected, for low values of γ, like γ = 100 (corresponding, roughly speaking, to a scenario where resources are not an issue but low delays are required), the cost function is monotonically decreasing in P and flooding (P = 1) is the best forwarding policy. On the other hand, if the value of γ is high (resource-constrained scenario, e.g. γ = 1600), the minimum is for P = 0 and nodes should make no copy letting the source deliver its message to the destination. For intermediate values of γ (in our case γ = 800), a minimum exists and a tradeoff between low delay and low resource consumption can be found. The graph reports also the performance achieved by our evolutionary scheme, after the initial convergence transient. The scheme is able to achieve almost optimal performance for all different values of γ. FIG. 6 -Cost vs. time for a dynamic scenario, in which every 20 generations the number of nodes in the network is increased, with N ∈ {5, 10, 20, 30, 40}, γ = 800. The evolutionary forwarding scheme proposed is compared to the traditional probabilistic forwarding scheme with the forwarding probability set to its optimal value when N = 20.

Dynamic Scenario

Last, we consider a simulation case in which N , the number of nodes in the system, varies with time. In particular, it is increased every 20 generations, following the sequence 5, 10, 20, 30, 40. This dynamic scenario challenges the ability of the proposed framework to track the variations in the network and adapt its parameters accordingly. The time-equivalent cost of a copy is set to γ = 800. We compute the cost (in seconds) achieved by our evolutionary forwarding scheme in each generation. The results are reported in Fig. 6 which depicts as well the performance of the traditional probabilistic forwarding scheme with the forwarding probability set to its optimal value when N = 20 (approximately 0.06, as can be seen from Fig. 5).

As expected, probabilistic forwarding exhibits steady performance as long as the number of nodes does not change. Instead the cost plot of our evolutionary forwarding scheme presents spikes whenever N increases. The abrupt change is mainly due to the arrival of new nodes, whose initial forwarding probability is set at random. During the transient following the spike, genotypes fitter to the new scenario are identified and the cost reduces.

Given a network scenario, our proposed solution exhibits performance similar to a traditional probabilistic forwarding scheme tuned for the specific scenario. But the evolutionary solution outperforms probabilistic forwarding whenever the scenario changes.

Outlook and Future Work

In the report, we have presented a framework for embedding autonomous evolution in epidemicstyle forwarding schemes. The proposed approach is based on the application of a GA-like mechanism to parameters arrays describing policies employed by the nodes in the system. The simulation results presented indicate in particular that the proposed case-study implementation is able to track changes in the system conditions (e.g., number of nodes in the scenario considered), and achieves similar if not better performance than solutions statically optimized for a given operating point.

The technique proposed in the report represents a first step towards the application of dynamic optimization techniques to forwarding schemes in DTN-like scenarios. In particular, effects of factor like (i) mobility and traffic pattern, (ii) nodes cooperation level, (iii) network heterogeneity, have not been accounted for in the present report, and deserve future studies. Another interesting direction concerns the application of other metaheuristics [START_REF] Blum | Metaheuristics in combinatorial optimization : Overview and conceptual comparison[END_REF] for run-time optimization.

13 FIG. 1 -

 131 FIG.1-Example of forwarding policy mapping : from the binary representation to the forwarding algorithm.

FIG. 2 -

 2 FIG.2-Considered system architecture : each node employs a policy, characterized by a genotype with associated fitness value. Each node maintains a pool of candidate solutions used in the reproduction phase to generate new genotypes.

4 :if Node ID ∈ W then 5 :

 45 Update node's fitness value (REWARDING).

  Parameters L = 500 m T s = 3000 s T g = 120000 s r = 25 m T step = 2 s p c = 0.10 v = 1 m/s γ = 100, 400, 800, 1600 s p m = 0.01 Static scenario N = 20 Dynamic scenario N varies in {5, 10, 20, 30, 40}

FIG. 3 -

 3 FIG.3-Evolution of the forwarding probabilities with γ = 800.

FIG. 4 -FIG. 5 -

 45 FIG.4-Cost averaged over all messages delivered in a generation vs. generation, with γ = 800.

RR n°6140

In a homogeneous scenario, all nodes play the same role, hence F does not depend on the order of the genotypes. A candidate solution is just a multiset of N genotypes.

We would haveφ 1 = φ 2 = • • • φ N = F (x 1 , x 2 , • • • , x N ).RR n°6140

If local clocks are enough accurate at the message delivery time-scale, then there is another solution which does not require synchronization. Message header should have a field which indicates the time since the payload was generated. This field can be updated by each node before forwarding the message. In this case the node should keep track of the time running since it has received the message.

We observe that this is not exact since the number of nodes in W is not constant but it depends itself on the genotypes present in the network.RR n°6140

In practice, scaled fitness values are used instead of the raw fitness values φi,j . This is common in GAs and has a twofold purpose. First it avoids having in the first generations few extraordinary genotypes taking over a significant proportion of the finite population in a single generation. Second, should the best fitness values be close to the average ones, more best genotypes than average ones will appear in future generations. We can linearly scale the fitness values such that the best fitness value is double the average fitness value which remains unchanged. In generations where the scaling produces negative normalized fitness values, an alternative scaling is used. The latter maintains equality of the raw and scaled average fitness values, but maps the minimum raw fitness to a null value.INRIA

Acknowledgments

The authors would like to thank Lidia Yamamoto for the helpful discussions and the bibliographical references she provided, and Eitan Altman, Konstantin Avrachenkov and Philippe Nain for the interesting brainstorming sessions at early stages of this research.